2
* See the file LICENSE for redistribution information.
4
* Copyright (c) 2000-2002
5
* Sleepycat Software. All rights reserved.
10
#include "db_config.h"
13
static const char revid[] = "$Id$";
16
#ifndef NO_SYSTEM_INCLUDES
17
#include <sys/types.h>
23
#include "dbinc/db_page.h"
24
#include "dbinc/db_verify.h"
25
#include "dbinc/db_am.h"
27
static int __db_vrfy_pageinfo_create __P((DB_ENV *, VRFY_PAGEINFO **));
28
static int __db_vrfy_pgset_iinc __P((DB *, db_pgno_t, int));
31
* __db_vrfy_dbinfo_create --
32
* Allocate and initialize a VRFY_DBINFO structure.
34
* PUBLIC: int __db_vrfy_dbinfo_create
35
* PUBLIC: __P((DB_ENV *, u_int32_t, VRFY_DBINFO **));
38
__db_vrfy_dbinfo_create(dbenv, pgsize, vdpp)
43
DB *cdbp, *pgdbp, *pgset;
48
cdbp = pgdbp = pgset = NULL;
50
if ((ret = __os_calloc(NULL,
51
1, sizeof(VRFY_DBINFO), (void **)&vdp)) != 0)
54
if ((ret = db_create(&cdbp, dbenv, 0)) != 0)
57
if ((ret = cdbp->set_flags(cdbp, DB_DUP)) != 0)
60
if ((ret = cdbp->set_pagesize(cdbp, pgsize)) != 0)
64
cdbp->open(cdbp, NULL, NULL, NULL, DB_BTREE, DB_CREATE, 0600)) != 0)
67
if ((ret = db_create(&pgdbp, dbenv, 0)) != 0)
70
if ((ret = pgdbp->set_pagesize(pgdbp, pgsize)) != 0)
73
if ((ret = pgdbp->open(pgdbp,
74
NULL, NULL, NULL, DB_BTREE, DB_CREATE, 0600)) != 0)
77
if ((ret = __db_vrfy_pgset(dbenv, pgsize, &pgset)) != 0)
80
LIST_INIT(&vdp->subdbs);
81
LIST_INIT(&vdp->activepips);
89
err: if (cdbp != NULL)
90
(void)cdbp->close(cdbp, 0);
92
(void)pgdbp->close(pgdbp, 0);
94
__os_free(dbenv, vdp);
99
* __db_vrfy_dbinfo_destroy --
100
* Destructor for VRFY_DBINFO. Destroys VRFY_PAGEINFOs and deallocates
103
* PUBLIC: int __db_vrfy_dbinfo_destroy __P((DB_ENV *, VRFY_DBINFO *));
106
__db_vrfy_dbinfo_destroy(dbenv, vdp)
110
VRFY_CHILDINFO *c, *d;
115
for (c = LIST_FIRST(&vdp->subdbs); c != NULL; c = d) {
116
d = LIST_NEXT(c, links);
120
if ((t_ret = vdp->pgdbp->close(vdp->pgdbp, 0)) != 0)
123
if ((t_ret = vdp->cdbp->close(vdp->cdbp, 0)) != 0 && ret == 0)
126
if ((t_ret = vdp->pgset->close(vdp->pgset, 0)) != 0 && ret == 0)
129
DB_ASSERT(LIST_FIRST(&vdp->activepips) == NULL);
131
__os_free(dbenv, vdp);
136
* __db_vrfy_getpageinfo --
137
* Get a PAGEINFO structure for a given page, creating it if necessary.
139
* PUBLIC: int __db_vrfy_getpageinfo
140
* PUBLIC: __P((VRFY_DBINFO *, db_pgno_t, VRFY_PAGEINFO **));
143
__db_vrfy_getpageinfo(vdp, pgno, pipp)
146
VRFY_PAGEINFO **pipp;
154
* We want a page info struct. There are three places to get it from,
155
* in decreasing order of preference:
157
* 1. vdp->activepips. If it's already "checked out", we're
158
* already using it, we return the same exact structure with a
159
* bumped refcount. This is necessary because this code is
160
* replacing array accesses, and it's common for f() to make some
161
* changes to a pip, and then call g() and h() which each make
162
* changes to the same pip. vdps are never shared between threads
163
* (they're never returned to the application), so this is safe.
164
* 2. The pgdbp. It's not in memory, but it's in the database, so
165
* get it, give it a refcount of 1, and stick it on activepips.
166
* 3. malloc. It doesn't exist yet; create it, then stick it on
167
* activepips. We'll put it in the database when we putpageinfo
172
for (pip = LIST_FIRST(&vdp->activepips); pip != NULL;
173
pip = LIST_NEXT(pip, links))
174
if (pip->pgno == pgno)
180
memset(&key, 0, sizeof(DBT));
181
memset(&data, 0, sizeof(DBT));
182
F_SET(&data, DB_DBT_MALLOC);
184
key.size = sizeof(db_pgno_t);
186
if ((ret = pgdbp->get(pgdbp, NULL, &key, &data, 0)) == 0) {
188
DB_ASSERT(data.size = sizeof(VRFY_PAGEINFO));
190
DB_ASSERT(pip->pi_refcount == 0);
191
LIST_INSERT_HEAD(&vdp->activepips, pip, links);
193
} else if (ret != DB_NOTFOUND) /* Something nasty happened. */
197
if ((ret = __db_vrfy_pageinfo_create(pgdbp->dbenv, &pip)) != 0)
200
LIST_INSERT_HEAD(&vdp->activepips, pip, links);
201
found: pip->pi_refcount++;
205
DB_ASSERT(pip->pi_refcount > 0);
210
* __db_vrfy_putpageinfo --
211
* Put back a VRFY_PAGEINFO that we're done with.
213
* PUBLIC: int __db_vrfy_putpageinfo __P((DB_ENV *,
214
* PUBLIC: VRFY_DBINFO *, VRFY_PAGEINFO *));
217
__db_vrfy_putpageinfo(dbenv, vdp, pip)
232
if (--pip->pi_refcount > 0)
236
memset(&key, 0, sizeof(DBT));
237
memset(&data, 0, sizeof(DBT));
239
key.data = &pip->pgno;
240
key.size = sizeof(db_pgno_t);
242
data.size = sizeof(VRFY_PAGEINFO);
244
if ((ret = pgdbp->put(pgdbp, NULL, &key, &data, 0)) != 0)
247
for (p = LIST_FIRST(&vdp->activepips); p != NULL;
248
p = LIST_NEXT(p, links))
253
DB_ASSERT(p->pi_refcount == 0);
254
LIST_REMOVE(p, links);
258
DB_ASSERT(found == 1);
261
DB_ASSERT(pip->pi_refcount == 0);
262
__os_ufree(dbenv, pip);
268
* Create a temporary database for the storing of sets of page numbers.
269
* (A mapping from page number to int, used by the *_meta2pgset functions,
270
* as well as for keeping track of which pages the verifier has seen.)
272
* PUBLIC: int __db_vrfy_pgset __P((DB_ENV *, u_int32_t, DB **));
275
__db_vrfy_pgset(dbenv, pgsize, dbpp)
283
if ((ret = db_create(&dbp, dbenv, 0)) != 0)
285
if ((ret = dbp->set_pagesize(dbp, pgsize)) != 0)
287
if ((ret = dbp->open(dbp,
288
NULL, NULL, NULL, DB_BTREE, DB_CREATE, 0600)) == 0)
291
err: (void)dbp->close(dbp, 0);
297
* __db_vrfy_pgset_get --
298
* Get the value associated in a page set with a given pgno. Return
299
* a 0 value (and succeed) if we've never heard of this page.
301
* PUBLIC: int __db_vrfy_pgset_get __P((DB *, db_pgno_t, int *));
304
__db_vrfy_pgset_get(dbp, pgno, valp)
312
memset(&key, 0, sizeof(DBT));
313
memset(&data, 0, sizeof(DBT));
316
key.size = sizeof(db_pgno_t);
318
data.ulen = sizeof(int);
319
F_SET(&data, DB_DBT_USERMEM);
321
if ((ret = dbp->get(dbp, NULL, &key, &data, 0)) == 0) {
322
DB_ASSERT(data.size = sizeof(int));
323
memcpy(&val, data.data, sizeof(int));
324
} else if (ret == DB_NOTFOUND)
334
* __db_vrfy_pgset_inc --
335
* Increment the value associated with a pgno by 1.
337
* PUBLIC: int __db_vrfy_pgset_inc __P((DB *, db_pgno_t));
340
__db_vrfy_pgset_inc(dbp, pgno)
345
return (__db_vrfy_pgset_iinc(dbp, pgno, 1));
349
* __db_vrfy_pgset_dec --
350
* Increment the value associated with a pgno by 1.
352
* PUBLIC: int __db_vrfy_pgset_dec __P((DB *, db_pgno_t));
355
__db_vrfy_pgset_dec(dbp, pgno)
360
return (__db_vrfy_pgset_iinc(dbp, pgno, -1));
364
* __db_vrfy_pgset_iinc --
365
* Increment the value associated with a pgno by i.
369
__db_vrfy_pgset_iinc(dbp, pgno, i)
378
memset(&key, 0, sizeof(DBT));
379
memset(&data, 0, sizeof(DBT));
384
key.size = sizeof(db_pgno_t);
386
data.ulen = sizeof(int);
387
F_SET(&data, DB_DBT_USERMEM);
389
if ((ret = dbp->get(dbp, NULL, &key, &data, 0)) == 0) {
390
DB_ASSERT(data.size == sizeof(int));
391
memcpy(&val, data.data, sizeof(int));
392
} else if (ret != DB_NOTFOUND)
395
data.size = sizeof(int);
398
return (dbp->put(dbp, NULL, &key, &data, 0));
402
* __db_vrfy_pgset_next --
403
* Given a cursor open in a pgset database, get the next page in the
406
* PUBLIC: int __db_vrfy_pgset_next __P((DBC *, db_pgno_t *));
409
__db_vrfy_pgset_next(dbc, pgnop)
417
memset(&key, 0, sizeof(DBT));
418
memset(&data, 0, sizeof(DBT));
419
/* We don't care about the data, just the keys. */
420
F_SET(&data, DB_DBT_USERMEM | DB_DBT_PARTIAL);
421
F_SET(&key, DB_DBT_USERMEM);
423
key.ulen = sizeof(db_pgno_t);
425
if ((ret = dbc->c_get(dbc, &key, &data, DB_NEXT)) != 0)
428
DB_ASSERT(key.size == sizeof(db_pgno_t));
435
* __db_vrfy_childcursor --
436
* Create a cursor to walk the child list with. Returns with a nonzero
437
* final argument if the specified page has no children.
439
* PUBLIC: int __db_vrfy_childcursor __P((VRFY_DBINFO *, DBC **));
442
__db_vrfy_childcursor(vdp, dbcp)
452
if ((ret = cdbp->cursor(cdbp, NULL, &dbc, 0)) == 0)
459
* __db_vrfy_childput --
460
* Add a child structure to the set for a given page.
462
* PUBLIC: int __db_vrfy_childput
463
* PUBLIC: __P((VRFY_DBINFO *, db_pgno_t, VRFY_CHILDINFO *));
466
__db_vrfy_childput(vdp, pgno, cip)
474
VRFY_CHILDINFO *oldcip;
478
memset(&key, 0, sizeof(DBT));
479
memset(&data, 0, sizeof(DBT));
482
key.size = sizeof(db_pgno_t);
485
* We want to avoid adding multiple entries for a single child page;
486
* we only need to verify each child once, even if a child (such
487
* as an overflow key) is multiply referenced.
489
* However, we also need to make sure that when walking the list
490
* of children, we encounter them in the order they're referenced
491
* on a page. (This permits us, for example, to verify the
492
* prev_pgno/next_pgno chain of Btree leaf pages.)
494
* Check the child database to make sure that this page isn't
495
* already a child of the specified page number. If it's not,
496
* put it at the end of the duplicate set.
498
if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0)
500
for (ret = __db_vrfy_ccset(cc, pgno, &oldcip); ret == 0;
501
ret = __db_vrfy_ccnext(cc, &oldcip))
502
if (oldcip->pgno == cip->pgno) {
504
* Found a matching child. Return without
507
if ((ret = __db_vrfy_ccclose(cc)) != 0)
511
if (ret != DB_NOTFOUND) {
512
(void)__db_vrfy_ccclose(cc);
515
if ((ret = __db_vrfy_ccclose(cc)) != 0)
519
data.size = sizeof(VRFY_CHILDINFO);
521
return (cdbp->put(cdbp, NULL, &key, &data, 0));
526
* Sets a cursor created with __db_vrfy_childcursor to the first
527
* child of the given pgno, and returns it in the third arg.
529
* PUBLIC: int __db_vrfy_ccset __P((DBC *, db_pgno_t, VRFY_CHILDINFO **));
532
__db_vrfy_ccset(dbc, pgno, cipp)
535
VRFY_CHILDINFO **cipp;
540
memset(&key, 0, sizeof(DBT));
541
memset(&data, 0, sizeof(DBT));
544
key.size = sizeof(db_pgno_t);
546
if ((ret = dbc->c_get(dbc, &key, &data, DB_SET)) != 0)
549
DB_ASSERT(data.size == sizeof(VRFY_CHILDINFO));
550
*cipp = (VRFY_CHILDINFO *)data.data;
556
* __db_vrfy_ccnext --
557
* Gets the next child of the given cursor created with
558
* __db_vrfy_childcursor, and returns it in the memory provided in the
561
* PUBLIC: int __db_vrfy_ccnext __P((DBC *, VRFY_CHILDINFO **));
564
__db_vrfy_ccnext(dbc, cipp)
566
VRFY_CHILDINFO **cipp;
571
memset(&key, 0, sizeof(DBT));
572
memset(&data, 0, sizeof(DBT));
574
if ((ret = dbc->c_get(dbc, &key, &data, DB_NEXT_DUP)) != 0)
577
DB_ASSERT(data.size == sizeof(VRFY_CHILDINFO));
578
*cipp = (VRFY_CHILDINFO *)data.data;
584
* __db_vrfy_ccclose --
585
* Closes the cursor created with __db_vrfy_childcursor.
587
* This doesn't actually do anything interesting now, but it's
588
* not inconceivable that we might change the internal database usage
589
* and keep the interfaces the same, and a function call here or there
590
* seldom hurts anyone.
592
* PUBLIC: int __db_vrfy_ccclose __P((DBC *));
595
__db_vrfy_ccclose(dbc)
599
return (dbc->c_close(dbc));
603
* __db_vrfy_pageinfo_create --
604
* Constructor for VRFY_PAGEINFO; allocates and initializes.
607
__db_vrfy_pageinfo_create(dbenv, pgipp)
609
VRFY_PAGEINFO **pgipp;
615
* pageinfo structs are sometimes allocated here and sometimes
616
* allocated by fetching them from a database with DB_DBT_MALLOC.
617
* There's no easy way for the destructor to tell which was
618
* used, and so we always allocate with __os_umalloc so we can free
621
if ((ret = __os_umalloc(dbenv,
622
sizeof(VRFY_PAGEINFO), (void **)&pgip)) != 0)
624
memset(pgip, 0, sizeof(VRFY_PAGEINFO));
626
DB_ASSERT(pgip->pi_refcount == 0);
633
* __db_salvage_init --
634
* Set up salvager database.
636
* PUBLIC: int __db_salvage_init __P((VRFY_DBINFO *));
639
__db_salvage_init(vdp)
645
if ((ret = db_create(&dbp, NULL, 0)) != 0)
648
if ((ret = dbp->set_pagesize(dbp, 1024)) != 0)
651
if ((ret = dbp->open(dbp,
652
NULL, NULL, NULL, DB_BTREE, DB_CREATE, 0)) != 0)
655
vdp->salvage_pages = dbp;
658
err: (void)dbp->close(dbp, 0);
663
* __db_salvage_destroy --
664
* Close salvager database.
665
* PUBLIC: void __db_salvage_destroy __P((VRFY_DBINFO *));
668
__db_salvage_destroy(vdp)
671
(void)vdp->salvage_pages->close(vdp->salvage_pages, 0);
675
* __db_salvage_getnext --
676
* Get the next (first) unprinted page in the database of pages we need to
677
* print still. Delete entries for any already-printed pages we encounter
678
* in this search, as well as the page we're returning.
680
* PUBLIC: int __db_salvage_getnext
681
* PUBLIC: __P((VRFY_DBINFO *, db_pgno_t *, u_int32_t *));
684
__db_salvage_getnext(vdp, pgnop, pgtypep)
695
dbp = vdp->salvage_pages;
697
memset(&key, 0, sizeof(DBT));
698
memset(&data, 0, sizeof(DBT));
700
if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0)
703
while ((ret = dbc->c_get(dbc, &key, &data, DB_NEXT)) == 0) {
704
DB_ASSERT(data.size == sizeof(u_int32_t));
705
memcpy(&pgtype, data.data, sizeof(pgtype));
707
if ((ret = dbc->c_del(dbc, 0)) != 0)
709
if (pgtype != SALVAGE_IGNORE)
713
/* No more entries--ret probably equals DB_NOTFOUND. */
716
found: DB_ASSERT(key.size == sizeof(db_pgno_t));
717
DB_ASSERT(data.size == sizeof(u_int32_t));
719
*pgnop = *(db_pgno_t *)key.data;
720
*pgtypep = *(u_int32_t *)data.data;
723
err: (void)dbc->c_close(dbc);
728
* __db_salvage_isdone --
729
* Return whether or not the given pgno is already marked
730
* SALVAGE_IGNORE (meaning that we don't need to print it again).
732
* Returns DB_KEYEXIST if it is marked, 0 if not, or another error on
735
* PUBLIC: int __db_salvage_isdone __P((VRFY_DBINFO *, db_pgno_t));
738
__db_salvage_isdone(vdp, pgno)
747
dbp = vdp->salvage_pages;
749
memset(&key, 0, sizeof(DBT));
750
memset(&data, 0, sizeof(DBT));
752
currtype = SALVAGE_INVALID;
753
data.data = &currtype;
754
data.ulen = sizeof(u_int32_t);
755
data.flags = DB_DBT_USERMEM;
758
key.size = sizeof(db_pgno_t);
761
* Put an entry for this page, with pgno as key and type as data,
762
* unless it's already there and is marked done.
763
* If it's there and is marked anything else, that's fine--we
764
* want to mark it done.
766
ret = dbp->get(dbp, NULL, &key, &data, 0);
769
* The key's already here. Check and see if it's already
770
* marked done. If it is, return DB_KEYEXIST. If it's not,
773
if (currtype == SALVAGE_IGNORE)
774
return (DB_KEYEXIST);
777
} else if (ret != DB_NOTFOUND)
780
/* The pgno is not yet marked anything; return 0. */
785
* __db_salvage_markdone --
786
* Mark as done a given page.
788
* PUBLIC: int __db_salvage_markdone __P((VRFY_DBINFO *, db_pgno_t));
791
__db_salvage_markdone(vdp, pgno)
800
pgtype = SALVAGE_IGNORE;
801
dbp = vdp->salvage_pages;
803
memset(&key, 0, sizeof(DBT));
804
memset(&data, 0, sizeof(DBT));
806
currtype = SALVAGE_INVALID;
807
data.data = &currtype;
808
data.ulen = sizeof(u_int32_t);
809
data.flags = DB_DBT_USERMEM;
812
key.size = sizeof(db_pgno_t);
815
* Put an entry for this page, with pgno as key and type as data,
816
* unless it's already there and is marked done.
817
* If it's there and is marked anything else, that's fine--we
818
* want to mark it done, but db_salvage_isdone only lets
819
* us know if it's marked IGNORE.
821
* We don't want to return DB_KEYEXIST, though; this will
822
* likely get passed up all the way and make no sense to the
823
* application. Instead, use DB_VERIFY_BAD to indicate that
824
* we've seen this page already--it probably indicates a
825
* multiply-linked page.
827
if ((ret = __db_salvage_isdone(vdp, pgno)) != 0)
828
return (ret == DB_KEYEXIST ? DB_VERIFY_BAD : ret);
830
data.size = sizeof(u_int32_t);
833
return (dbp->put(dbp, NULL, &key, &data, 0));
837
* __db_salvage_markneeded --
838
* If it has not yet been printed, make note of the fact that a page
839
* must be dealt with later.
841
* PUBLIC: int __db_salvage_markneeded
842
* PUBLIC: __P((VRFY_DBINFO *, db_pgno_t, u_int32_t));
845
__db_salvage_markneeded(vdp, pgno, pgtype)
854
dbp = vdp->salvage_pages;
856
memset(&key, 0, sizeof(DBT));
857
memset(&data, 0, sizeof(DBT));
860
key.size = sizeof(db_pgno_t);
863
data.size = sizeof(u_int32_t);
866
* Put an entry for this page, with pgno as key and type as data,
867
* unless it's already there, in which case it's presumably
868
* already been marked done.
870
ret = dbp->put(dbp, NULL, &key, &data, DB_NOOVERWRITE);
871
return (ret == DB_KEYEXIST ? 0 : ret);