hash_verify.c

00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1999, 2000
00005  * Sleepycat Software. All rights reserved.
00006  *
00007  * $Id: hash__verify_8c-source.html,v 1.1 2008年06月08日 10:19:40 sebdiaz Exp $
00008  */
00009 
00010 #include "config.h"
00011 
00012 #ifndef lint
00013 static const char revid[] = "$Id: hash__verify_8c-source.html,v 1.1 2008年06月08日 10:19:40 sebdiaz Exp $";
00014 #endif /* not lint */
00015 
00016 #ifndef NO_SYSTEM_INCLUDES
00017 #include <sys/types.h>
00018 
00019 #include <errno.h>
00020 #include <string.h>
00021 #endif
00022 
00023 #include "db_int.h"
00024 #include "db_page.h"
00025 #include "db_verify.h"
00026 #include "btree.h"
00027 #include "hash.h"
00028 
00029 static int __ham_dups_unsorted __P((DB *, u_int8_t *, u_int32_t));
00030 static int __ham_vrfy_bucket __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
00031 u_int32_t));
00032 static int __ham_vrfy_item __P((DB *,
00033 VRFY_DBINFO *, db_pgno_t, PAGE *, u_int32_t, u_int32_t));
00034 
00035 /*
00036  * CDB___ham_vrfy_meta --
00037  * Verify the hash-specific part of a metadata page.
00038  *
00039  * Note that unlike btree, we don't save things off, because we
00040  * will need most everything again to verify each page and the
00041  * amount of state here is significant.
00042  *
00043  * PUBLIC: int CDB___ham_vrfy_meta __P((DB *, VRFY_DBINFO *, HMETA *,
00044  * PUBLIC: db_pgno_t, u_int32_t));
00045  */
00046 int
00047 CDB___ham_vrfy_meta(dbp, vdp, m, pgno, flags)
00048 DB *dbp;
00049 VRFY_DBINFO *vdp;
00050 HMETA *m;
00051 db_pgno_t pgno;
00052 u_int32_t flags;
00053 {
00054 HASH *hashp;
00055 VRFY_PAGEINFO *pip;
00056 int i, ret, t_ret, isbad;
00057 u_int32_t pwr, mbucket;
00058 u_int32_t (*hfunc) __P((const void *, u_int32_t));
00059 
00060 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00061 return (ret);
00062 isbad = 0;
00063 
00064 hashp = dbp->h_internal;
00065 
00066 if (hashp != NULL && hashp->h_hash != NULL)
00067 hfunc = hashp->h_hash;
00068 else
00069 hfunc = CDB___ham_func5;
00070 
00071 /*
00072  * If we haven't already checked the common fields in pagezero,
00073  * check them.
00074  */
00075 if (!F_ISSET(pip, VRFY_INCOMPLETE) &&
00076 (ret = CDB___db_vrfy_meta(dbp, vdp, &m->dbmeta, pgno, flags)) != 0) {
00077 if (ret == DB_VERIFY_BAD)
00078 isbad = 1;
00079 else
00080 goto err;
00081 }
00082 
00083 /* h_charkey */
00084 if (!LF_ISSET(DB_NOORDERCHK))
00085 if (m->h_charkey != hfunc(CHARKEY, sizeof(CHARKEY))) {
00086 EPRINT((dbp->dbenv,
00087 "Database has different custom hash function; reverify with DB_NOORDERCHK set"
00088 ));
00089 /*
00090  * Return immediately; this is probably a sign
00091  * of user error rather than database corruption, so
00092  * we want to avoid extraneous errors.
00093  */
00094 isbad = 1;
00095 goto err;
00096 }
00097 
00098 /* max_bucket must be less than the last pgno. */
00099 if (m->max_bucket > vdp->last_pgno) {
00100 EPRINT((dbp->dbenv,
00101 "Impossible max_bucket %lu on meta page %lu",
00102 m->max_bucket, pgno));
00103 /*
00104  * Most other fields depend somehow on max_bucket, so
00105  * we just return--there will be lots of extraneous
00106  * errors.
00107  */
00108 isbad = 1;
00109 goto err;
00110 }
00111 
00112 /*
00113  * max_bucket, high_mask and low_mask: high_mask must be one
00114  * less than the next power of two above max_bucket, and
00115  * low_mask must be one less than the power of two below it.
00116  *
00117  *
00118  */
00119 pwr = (m->max_bucket == 0) ? 1 : 1 << CDB___db_log2(m->max_bucket + 1);
00120 if (m->high_mask != pwr - 1) {
00121 EPRINT((dbp->dbenv,
00122 "Incorrect high_mask %lu on page %lu, should be %lu",
00123 m->high_mask, pgno, pwr - 1));
00124 isbad = 1;
00125 }
00126 pwr >>= 1;
00127 if (m->low_mask != pwr - 1) {
00128 EPRINT((dbp->dbenv,
00129 "Incorrect low_mask %lu on page %lu, should be %lu",
00130 m->low_mask, pgno, pwr - 1));
00131 isbad = 1;
00132 }
00133 
00134 /* ffactor: no check possible. */
00135 pip->h_ffactor = m->ffactor;
00136 
00137 /*
00138  * nelem: just make sure it's not astronomical for now. This is the
00139  * same check that hash_upgrade does, since there was a bug in 2.X
00140  * which could make nelem go "negative".
00141  */
00142 if (m->nelem > 0x80000000) {
00143 EPRINT((dbp->dbenv,
00144 "Suspiciously high nelem of %lu on page %lu",
00145 m->nelem, pgno));
00146 isbad = 1;
00147 pip->h_nelem = 0;
00148 } else
00149 pip->h_nelem = m->nelem;
00150 
00151 /* flags */
00152 if (F_ISSET(&m->dbmeta, DB_HASH_DUP))
00153 F_SET(pip, VRFY_HAS_DUPS);
00154 if (F_ISSET(&m->dbmeta, DB_HASH_DUPSORT))
00155 F_SET(pip, VRFY_HAS_DUPSORT);
00156 /* XXX: Why is the DB_HASH_SUBDB flag necessary? */
00157 
00158 /* spares array */
00159 for (i = 0; m->spares[i] != 0 && i < NCACHED; i++) {
00160 /*
00161  * We set mbucket to the maximum bucket that would use a given
00162  * spares entry; we want to ensure that it's always less
00163  * than last_pgno.
00164  */
00165 mbucket = (1 << i) - 1;
00166 if (mbucket + m->spares[CDB___db_log2(mbucket + 1)] >
00167 vdp->last_pgno) {
00168 EPRINT((dbp->dbenv,
00169 "Spares array entry %lu, page %lu is invalid",
00170 i, pgno));
00171 isbad = 1;
00172 }
00173 }
00174 
00175 err: if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00176 ret = t_ret;
00177 return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00178 }
00179 
00180 /*
00181  * CDB___ham_vrfy --
00182  * Verify hash page.
00183  *
00184  * PUBLIC: int CDB___ham_vrfy __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
00185  * PUBLIC: u_int32_t));
00186  */
00187 int
00188 CDB___ham_vrfy(dbp, vdp, h, pgno, flags)
00189 DB *dbp;
00190 VRFY_DBINFO *vdp;
00191 PAGE *h;
00192 db_pgno_t pgno;
00193 u_int32_t flags;
00194 {
00195 VRFY_PAGEINFO *pip;
00196 db_indx_t ent, himark, inpend;
00197 int isbad, ret, t_ret;
00198 
00199 isbad = 0;
00200 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00201 return (ret);
00202 
00203 /* Sanity check our flags and page type. */
00204 if ((ret = CDB___db_fchk(dbp->dbenv, "CDB___ham_vrfy",
00205 flags, DB_AGGRESSIVE | DB_NOORDERCHK | DB_SALVAGE)) != 0)
00206 goto err;
00207 
00208 if (TYPE(h) != P_HASH) {
00209 TYPE_ERR_PRINT(dbp->dbenv, "CDB___ham_vrfy", pgno, TYPE(h));
00210 DB_ASSERT(0);
00211 ret = EINVAL;
00212 goto err;
00213 }
00214 
00215 /* Verify and save off fields common to all PAGEs. */
00216 if ((ret = CDB___db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
00217 if (ret == DB_VERIFY_BAD)
00218 isbad = 1;
00219 else
00220 goto err;
00221 }
00222 
00223 /*
00224  * Verify inp[]. Each offset from 0 to NUM_ENT(h) must be lower
00225  * than the previous one, higher than the current end of the inp array,
00226  * and lower than the page size.
00227  *
00228  * In any case, we return immediately if things are bad, as it would
00229  * be unsafe to proceed.
00230  */
00231 for (ent = 0, himark = dbp->pgsize,
00232 inpend = (u_int8_t *)h->inp - (u_int8_t *)h;
00233 ent < NUM_ENT(h); ent++)
00234 if (h->inp[ent] >= himark) {
00235 EPRINT((dbp->dbenv,
00236 "Item %lu on page %lu out of order or nonsensical",
00237 ent, pgno));
00238 isbad = 1;
00239 goto err;
00240 } else if (inpend >= himark) {
00241 EPRINT((dbp->dbenv,
00242 "inp array collided with data on page %lu",
00243 pgno));
00244 isbad = 1;
00245 goto err;
00246 
00247 } else {
00248 himark = h->inp[ent];
00249 inpend += sizeof(db_indx_t);
00250 if ((ret = __ham_vrfy_item(
00251 dbp, vdp, pgno, h, ent, flags)) != 0)
00252 goto err;
00253 }
00254 
00255 err: if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00256 ret = t_ret;
00257 return (ret == 0 && isbad == 1 ? DB_VERIFY_BAD : ret);
00258 }
00259 
00260 /*
00261  * __ham_vrfy_item --
00262  * Given a hash page and an offset, sanity-check the item itself,
00263  * and save off any overflow items or off-page dup children as necessary.
00264  */
00265 static int
00266 __ham_vrfy_item(dbp, vdp, pgno, h, i, flags)
00267 DB *dbp;
00268 VRFY_DBINFO *vdp;
00269 db_pgno_t pgno;
00270 PAGE *h;
00271 u_int32_t i, flags;
00272 {
00273 HOFFPAGE hop;
00274 HOFFDUP hod;
00275 VRFY_CHILDINFO child;
00276 VRFY_PAGEINFO *pip;
00277 db_indx_t offset, len, dlen, elen;
00278 int ret, t_ret;
00279 u_int8_t *databuf;
00280 
00281 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00282 return (ret);
00283 
00284 switch (HPAGE_TYPE(h, i)) {
00285 case H_KEYDATA:
00286 /* Nothing to do here--everything but the type field is data */
00287 break;
00288 case H_DUPLICATE:
00289 /* Are we a datum or a key? Better be the former. */
00290 if (i % 2 == 0) {
00291 EPRINT((dbp->dbenv,
00292 "Hash key stored as duplicate at page %lu item %lu",
00293 pip->pgno, i));
00294 }
00295 /*
00296  * Dups are encoded as a series within a single HKEYDATA,
00297  * in which each dup is surrounded by a copy of its length
00298  * on either side (so that the series can be walked in either
00299  * direction. We loop through this series and make sure
00300  * each dup is reasonable.
00301  *
00302  * Note that at this point, we've verified item i-1, so
00303  * it's safe to use LEN_HKEYDATA (which looks at inp[i-1]).
00304  */
00305 len = LEN_HKEYDATA(h, dbp->pgsize, i);
00306 databuf = HKEYDATA_DATA(P_ENTRY(h, i));
00307 for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
00308 memcpy(&dlen, databuf + offset, sizeof(db_indx_t));
00309 
00310 /* Make sure the length is plausible. */
00311 if (offset + DUP_SIZE(dlen) > len) {
00312 EPRINT((dbp->dbenv,
00313 "Duplicate item %lu, page %lu has bad length",
00314 i, pip->pgno));
00315 ret = DB_VERIFY_BAD;
00316 goto err;
00317 }
00318 
00319 /*
00320  * Make sure the second copy of the length is the
00321  * same as the first.
00322  */
00323 memcpy(&elen,
00324 databuf + offset + dlen + sizeof(db_indx_t),
00325 sizeof(db_indx_t));
00326 if (elen != dlen) {
00327 EPRINT((dbp->dbenv,
00328 "Duplicate item %lu, page %lu has two different lengths",
00329 i, pip->pgno));
00330 ret = DB_VERIFY_BAD;
00331 goto err;
00332 }
00333 }
00334 F_SET(pip, VRFY_HAS_DUPS);
00335 if (!LF_ISSET(DB_NOORDERCHK) &&
00336 __ham_dups_unsorted(dbp, databuf, len))
00337 F_SET(pip, VRFY_DUPS_UNSORTED);
00338 break;
00339 case H_OFFPAGE:
00340 /* Offpage item. Make sure pgno is sane, save off. */
00341 memcpy(&hop, P_ENTRY(h, i), HOFFPAGE_SIZE);
00342 if (!IS_VALID_PGNO(hop.pgno) || hop.pgno == pip->pgno ||
00343 hop.pgno == PGNO_INVALID) {
00344 EPRINT((dbp->dbenv,
00345 "Offpage item %lu, page %lu has bad page number",
00346 i, pip->pgno));
00347 ret = DB_VERIFY_BAD;
00348 goto err;
00349 }
00350 memset(&child, 0, sizeof(VRFY_CHILDINFO));
00351 child.pgno = hop.pgno;
00352 child.type = V_OVERFLOW;
00353 child.tlen = hop.tlen; /* This will get checked later. */
00354 if ((ret = CDB___db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
00355 goto err;
00356 break;
00357 case H_OFFDUP:
00358 /* Offpage duplicate item. Same drill. */
00359 memcpy(&hod, P_ENTRY(h, i), HOFFDUP_SIZE);
00360 if (!IS_VALID_PGNO(hod.pgno) || hod.pgno == pip->pgno ||
00361 hod.pgno == PGNO_INVALID) {
00362 EPRINT((dbp->dbenv,
00363 "Offpage item %lu, page %lu has bad page number",
00364 i, pip->pgno));
00365 ret = DB_VERIFY_BAD;
00366 goto err;
00367 }
00368 memset(&child, 0, sizeof(VRFY_CHILDINFO));
00369 child.pgno = hod.pgno;
00370 child.type = V_DUPLICATE;
00371 if ((ret = CDB___db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
00372 goto err;
00373 F_SET(pip, VRFY_HAS_DUPS);
00374 break;
00375 default:
00376 EPRINT((dbp->dbenv,
00377 "Item %i, page %lu has bad type", i, pip->pgno));
00378 ret = DB_VERIFY_BAD;
00379 break;
00380 }
00381 
00382 err: if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00383 ret = t_ret;
00384 return (ret);
00385 }
00386 
00387 /*
00388  * CDB___ham_vrfy_structure --
00389  * Verify the structure of a hash database.
00390  *
00391  * PUBLIC: int CDB___ham_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t,
00392  * PUBLIC: u_int32_t));
00393  */
00394 int
00395 CDB___ham_vrfy_structure(dbp, vdp, meta_pgno, flags)
00396 DB *dbp;
00397 VRFY_DBINFO *vdp;
00398 db_pgno_t meta_pgno;
00399 u_int32_t flags;
00400 {
00401 DB *pgset;
00402 HMETA *m;
00403 PAGE *h;
00404 VRFY_PAGEINFO *pip;
00405 int isbad, p, ret, t_ret;
00406 db_pgno_t pgno;
00407 u_int32_t bucket;
00408 
00409 ret = isbad = 0;
00410 h = NULL;
00411 pgset = vdp->pgset;
00412 
00413 if ((ret = CDB___db_vrfy_pgset_get(pgset, meta_pgno, &p)) != 0)
00414 return (ret);
00415 if (p != 0) {
00416 EPRINT((dbp->dbenv,
00417 "Hash meta page %lu referenced twice", meta_pgno));
00418 return (DB_VERIFY_BAD);
00419 }
00420 if ((ret = CDB___db_vrfy_pgset_inc(pgset, meta_pgno)) != 0)
00421 return (ret);
00422 
00423 /* Get the meta page; we'll need it frequently. */
00424 if ((ret = CDB_memp_fget(dbp->mpf, &meta_pgno, 0, &m)) != 0)
00425 return (ret);
00426 
00427 /* Loop through bucket by bucket. */
00428 for (bucket = 0; bucket <= m->max_bucket; bucket++)
00429 if ((ret =
00430 __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)) != 0) {
00431 if (ret == DB_VERIFY_BAD)
00432 isbad = 1;
00433 else
00434 goto err;
00435 }
00436 
00437 /*
00438  * There may be unused hash pages corresponding to buckets
00439  * that are part of the current doubling but which are higher
00440  * than max_bucket. Loop through them, too, and make sure they're
00441  * all empty.
00442  */
00443 for (bucket = m->max_bucket + 1; bucket <= m->high_mask; bucket++) {
00444 pgno = bucket + m->spares[CDB___db_log2(bucket + 1)];
00445 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00446 goto err;
00447 
00448 /* It's okay if these pages are totally zeroed; unmark it. */
00449 F_CLR(pip, VRFY_IS_ALLZEROES);
00450 
00451 if (pip->type != P_HASH) {
00452 EPRINT((dbp->dbenv,
00453 "Hash bucket %lu maps to non-hash page %lu",
00454 bucket, pgno));
00455 isbad = 1;
00456 } else if (pip->entries != 0) {
00457 EPRINT((dbp->dbenv,
00458 "Non-empty page %lu in unused hash bucket %lu",
00459 pgno, bucket));
00460 isbad = 1;
00461 } else {
00462 if ((ret = CDB___db_vrfy_pgset_get(pgset, pgno, &p)) != 0)
00463 goto err;
00464 if (p != 0) {
00465 EPRINT((dbp->dbenv,
00466 "Hash page %lu above max_bucket referenced",
00467 pgno));
00468 isbad = 1;
00469 } else {
00470 if ((ret =
00471 CDB___db_vrfy_pgset_inc(pgset, pgno)) != 0)
00472 goto err;
00473 if ((ret =
00474 CDB___db_vrfy_putpageinfo(vdp, pip)) != 0)
00475 goto err;
00476 continue;
00477 }
00478 }
00479 
00480 /* If we got here, it's an error. */
00481 (void)CDB___db_vrfy_putpageinfo(vdp, pip);
00482 goto err;
00483 }
00484 
00485 err: if ((t_ret = CDB_memp_fput(dbp->mpf, m, 0)) != 0)
00486 return (t_ret);
00487 if (h != NULL && (t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00488 return (t_ret);
00489 return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD: ret);
00490 }
00491 
00492 /*
00493  * __ham_vrfy_bucket --
00494  * Verify a given bucket.
00495  */
00496 static int
00497 __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)
00498 DB *dbp;
00499 VRFY_DBINFO *vdp;
00500 HMETA *m;
00501 u_int32_t bucket, flags;
00502 {
00503 HASH *hashp;
00504 VRFY_CHILDINFO *child;
00505 VRFY_PAGEINFO *mip, *pip;
00506 int ret, t_ret, isbad, p;
00507 db_pgno_t pgno, next_pgno;
00508 DBC *cc;
00509 u_int32_t (*hfunc) __P((const void *, u_int32_t));
00510 
00511 isbad = 0;
00512 pip = NULL;
00513 cc = NULL;
00514 
00515 hashp = dbp->h_internal;
00516 if (hashp != NULL && hashp->h_hash != NULL)
00517 hfunc = hashp->h_hash;
00518 else
00519 hfunc = CDB___ham_func5;
00520 
00521 if ((ret = CDB___db_vrfy_getpageinfo(vdp, PGNO(m), &mip)) != 0)
00522 return (ret);
00523 
00524 /* Calculate the first pgno for this bucket. */
00525 pgno = bucket + m->spares[CDB___db_log2(bucket + 1)];
00526 
00527 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00528 goto err;
00529 
00530 /* Make sure we got a plausible page number. */
00531 if (pgno > vdp->last_pgno || pip->type != P_HASH) {
00532 EPRINT((dbp->dbenv, "Bucket %lu has impossible first page %lu",
00533 bucket, pgno));
00534 /* Unsafe to continue. */
00535 isbad = 1;
00536 goto err;
00537 }
00538 
00539 if (pip->prev_pgno != PGNO_INVALID) {
00540 EPRINT((dbp->dbenv,
00541 "First hash page %lu in bucket %lu has a prev_pgno", pgno));
00542 isbad = 1;
00543 }
00544 
00545 /*
00546  * Set flags for dups and sorted dups.
00547  */
00548 flags |= F_ISSET(mip, VRFY_HAS_DUPS) ? ST_DUPOK : 0;
00549 flags |= F_ISSET(mip, VRFY_HAS_DUPSORT) ? ST_DUPSORT : 0;
00550 
00551 /* Loop until we find a fatal bug, or until we run out of pages. */
00552 for (;;) {
00553 if ((ret = CDB___db_vrfy_pgset_get(vdp->pgset, pgno, &p)) != 0)
00554 goto err;
00555 if (p != 0) {
00556 EPRINT((dbp->dbenv,
00557 "Hash page %lu referenced twice", pgno));
00558 isbad = 1;
00559 /* Unsafe to continue. */
00560 goto err;
00561 } else if ((ret = CDB___db_vrfy_pgset_inc(vdp->pgset, pgno)) != 0)
00562 goto err;
00563 
00564 /*
00565  * Hash pages that nothing has ever hashed to may never
00566  * have actually come into existence, and may appear to be
00567  * entirely zeroed. This is acceptable, and since there's
00568  * no real way for us to know whether this has actually
00569  * occurred, we clear the "wholly zeroed" flag on every
00570  * hash page. A wholly zeroed page, by nature, will appear
00571  * to have no flags set and zero entries, so should
00572  * otherwise verify correctly.
00573  */
00574 F_CLR(pip, VRFY_IS_ALLZEROES);
00575 
00576 /* If we have dups, our meta page had better know about it. */
00577 if (F_ISSET(pip, VRFY_HAS_DUPS)
00578 && !F_ISSET(mip, VRFY_HAS_DUPS)) {
00579 EPRINT((dbp->dbenv,
00580 "Duplicates present in non-duplicate database, page %lu",
00581 pgno));
00582 isbad = 1;
00583 }
00584 
00585 /*
00586  * If the database has sorted dups, this page had better
00587  * not have unsorted ones.
00588  */
00589 if (F_ISSET(mip, VRFY_HAS_DUPSORT) &&
00590 F_ISSET(pip, VRFY_DUPS_UNSORTED)) {
00591 EPRINT((dbp->dbenv,
00592 "Unsorted dups in sorted-dup database, page %lu",
00593 pgno));
00594 isbad = 1;
00595 }
00596 
00597 /* Walk overflow chains and offpage dup trees. */
00598 if ((ret = CDB___db_vrfy_childcursor(vdp, &cc)) != 0)
00599 goto err;
00600 for (ret = CDB___db_vrfy_ccset(cc, pip->pgno, &child); ret == 0;
00601 ret = CDB___db_vrfy_ccnext(cc, &child))
00602 if (child->type == V_OVERFLOW) {
00603 if ((ret = CDB___db_vrfy_ovfl_structure(dbp, vdp,
00604 child->pgno, child->tlen, flags)) != 0) {
00605 if (ret == DB_VERIFY_BAD)
00606 isbad = 1;
00607 else
00608 goto err;
00609 }
00610 } else if (child->type == V_DUPLICATE) {
00611 if ((ret = CDB___db_vrfy_duptype(dbp,
00612 vdp, child->pgno, flags)) != 0) {
00613 isbad = 1;
00614 continue;
00615 }
00616 if ((ret = CDB___bam_vrfy_subtree(dbp, vdp,
00617 child->pgno, NULL, NULL,
00618 flags | ST_RECNUM, NULL,
00619 NULL, NULL)) != 0) {
00620 if (ret == DB_VERIFY_BAD)
00621 isbad = 1;
00622 else
00623 goto err;
00624 }
00625 }
00626 if ((ret = CDB___db_vrfy_ccclose(cc)) != 0)
00627 goto err;
00628 cc = NULL;
00629 
00630 /* If it's safe to check that things hash properly, do so. */
00631 if (isbad == 0 && !LF_ISSET(DB_NOORDERCHK) &&
00632 (ret = CDB___ham_vrfy_hashing(dbp, pip->entries,
00633 m, bucket, pgno, flags, hfunc)) != 0) {
00634 if (ret == DB_VERIFY_BAD)
00635 isbad = 1;
00636 else
00637 goto err;
00638 }
00639 
00640 next_pgno = pip->next_pgno;
00641 ret = CDB___db_vrfy_putpageinfo(vdp, pip);
00642 
00643 pip = NULL;
00644 if (ret != 0)
00645 goto err;
00646 
00647 if (next_pgno == PGNO_INVALID)
00648 break; /* End of the bucket. */
00649 
00650 /* We already checked this, but just in case... */
00651 if (!IS_VALID_PGNO(next_pgno)) {
00652 DB_ASSERT(0);
00653 EPRINT((dbp->dbenv,
00654 "Hash page %lu has bad next_pgno", pgno));
00655 isbad = 1;
00656 goto err;
00657 }
00658 
00659 if ((ret = CDB___db_vrfy_getpageinfo(vdp, next_pgno, &pip)) != 0)
00660 goto err;
00661 
00662 if (pip->prev_pgno != pgno) {
00663 EPRINT((dbp->dbenv, "Hash page %lu has bad prev_pgno",
00664 next_pgno));
00665 isbad = 1;
00666 }
00667 pgno = next_pgno;
00668 }
00669 
00670 err: if (cc != NULL && ((t_ret = CDB___db_vrfy_ccclose(cc)) != 0) && ret == 0)
00671 ret = t_ret;
00672 if (mip != NULL && ((t_ret = CDB___db_vrfy_putpageinfo(vdp, mip)) != 0) &&
00673 ret == 0)
00674 ret = t_ret;
00675 if (pip != NULL && ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0) &&
00676 ret == 0)
00677 ret = t_ret;
00678 return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00679 }
00680 
00681 /*
00682  * CDB___ham_vrfy_hashing --
00683  * Verify that all items on a given hash page hash correctly.
00684  *
00685  * PUBLIC: int CDB___ham_vrfy_hashing __P((DB *,
00686  * PUBLIC: u_int32_t, HMETA *, u_int32_t, db_pgno_t, u_int32_t,
00687  * PUBLIC: u_int32_t (*) __P((const void *, u_int32_t))));
00688  */
00689 int
00690 CDB___ham_vrfy_hashing(dbp, nentries, m, thisbucket, pgno, flags, hfunc)
00691 DB *dbp;
00692 u_int32_t nentries;
00693 HMETA *m;
00694 u_int32_t thisbucket;
00695 db_pgno_t pgno;
00696 u_int32_t flags;
00697 u_int32_t (*hfunc) __P((const void *, u_int32_t));
00698 {
00699 DBT dbt;
00700 PAGE *h;
00701 db_indx_t i;
00702 int ret, t_ret, isbad;
00703 u_int32_t hval, bucket;
00704 
00705 ret = isbad = 0;
00706 memset(&dbt, 0, sizeof(DBT));
00707 F_SET(&dbt, DB_DBT_REALLOC);
00708 
00709 if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00710 return (ret);
00711 
00712 for (i = 0; i < nentries; i += 2) {
00713 /*
00714  * We've already verified the page integrity and that of any
00715  * overflow chains linked off it; it is therefore safe to use
00716  * CDB___db_ret. It's also not all that much slower, since we have
00717  * to copy every hash item to deal with alignment anyway; we
00718  * can tweak this a bit if this proves to be a bottleneck,
00719  * but for now, take the easy route.
00720  */
00721 if ((ret = CDB___db_ret(dbp, h, i, &dbt, NULL, NULL)) != 0)
00722 goto err;
00723 hval = hfunc(dbt.data, dbt.size);
00724 
00725 bucket = hval & m->high_mask;
00726 if (bucket > m->max_bucket)
00727 bucket = bucket & m->low_mask;
00728 
00729 if (bucket != thisbucket) {
00730 EPRINT((dbp->dbenv,
00731 "Item %lu on page %lu hashes incorrectly",
00732 i, pgno));
00733 isbad = 1;
00734 }
00735 }
00736 
00737 err: if (dbt.data != NULL)
00738 CDB___os_free(dbt.data, 0);
00739 if ((t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00740 return (t_ret);
00741 
00742 return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00743 }
00744 
00745 /*
00746  * CDB___ham_salvage --
00747  * Safely dump out anything that looks like a key on an alleged
00748  * hash page.
00749  *
00750  * PUBLIC: int CDB___ham_salvage __P((DB *, VRFY_DBINFO *, db_pgno_t, PAGE *,
00751  * PUBLIC: void *, int (*)(void *, const void *), u_int32_t));
00752  */
00753 int
00754 CDB___ham_salvage(dbp, vdp, pgno, h, handle, callback, flags)
00755 DB *dbp;
00756 VRFY_DBINFO *vdp;
00757 db_pgno_t pgno;
00758 PAGE *h;
00759 void *handle;
00760 int (*callback) __P((void *, const void *));
00761 u_int32_t flags;
00762 {
00763 DBT dbt, unkdbt;
00764 db_pgno_t dpgno;
00765 int ret, err_ret, t_ret;
00766 u_int32_t himark, tlen;
00767 u_int8_t *hk;
00768 void *buf;
00769 db_indx_t dlen, len, i;
00770 
00771 memset(&dbt, 0, sizeof(DBT));
00772 dbt.flags = DB_DBT_REALLOC;
00773 
00774 memset(&unkdbt, 0, sizeof(DBT));
00775 unkdbt.size = strlen("UNKNOWN") + 1;
00776 unkdbt.data = "UNKNOWN";
00777 
00778 err_ret = 0;
00779 
00780 /*
00781  * Allocate a buffer for overflow items. Start at one page;
00782  * CDB___db_safe_goff will realloc as needed.
00783  */
00784 if ((ret = CDB___os_malloc(dbp->dbenv, dbp->pgsize, NULL, &buf)) != 0)
00785 return (ret);
00786 
00787 himark = dbp->pgsize;
00788 for (i = 0;; i++) {
00789 /* If we're not aggressive, break when we hit NUM_ENT(h). */
00790 if (!LF_ISSET(DB_AGGRESSIVE) && i >= NUM_ENT(h))
00791 break;
00792 
00793 /* Verify the current item. */
00794 ret = CDB___db_vrfy_inpitem(dbp,
00795 h, pgno, i, 0, flags, &himark, NULL);
00796 /* If this returned a fatality, it's time to break. */
00797 if (ret == DB_VERIFY_FATAL)
00798 break;
00799 
00800 if (ret == 0) {
00801 hk = P_ENTRY(h, i);
00802 len = LEN_HKEYDATA(h, dbp->pgsize, i);
00803 if ((u_int32_t)(hk + len - (u_int8_t *)h) >
00804 dbp->pgsize) {
00805 /*
00806  * Item is unsafely large; either continue
00807  * or set it to the whole page, depending on
00808  * aggressiveness.
00809  */
00810 if (!LF_ISSET(DB_AGGRESSIVE))
00811 continue;
00812 len = dbp->pgsize -
00813 (u_int32_t)(hk - (u_int8_t *)h);
00814 err_ret = DB_VERIFY_BAD;
00815 }
00816 switch (HPAGE_PTYPE(hk)) {
00817 default:
00818 if (!LF_ISSET(DB_AGGRESSIVE))
00819 break;
00820 err_ret = DB_VERIFY_BAD;
00821 /* FALLTHROUGH */
00822 case H_KEYDATA:
00823 keydata: memcpy(buf, HKEYDATA_DATA(hk), len);
00824 dbt.size = len;
00825 dbt.data = buf;
00826 if ((ret = CDB___db_prdbt(&dbt,
00827 0, " ", handle, callback, 0, NULL)) != 0)
00828 err_ret = ret;
00829 break;
00830 case H_OFFPAGE:
00831 if (len < HOFFPAGE_SIZE) {
00832 err_ret = DB_VERIFY_BAD;
00833 continue;
00834 }
00835 memcpy(&dpgno,
00836 HOFFPAGE_PGNO(hk), sizeof(dpgno));
00837 if ((ret = CDB___db_safe_goff(dbp, vdp,
00838 dpgno, &dbt, &buf, flags)) != 0) {
00839 err_ret = ret;
00840 (void)CDB___db_prdbt(&unkdbt, 0, " ",
00841 handle, callback, 0, NULL);
00842 break;
00843 }
00844 if ((ret = CDB___db_prdbt(&dbt,
00845 0, " ", handle, callback, 0, NULL)) != 0)
00846 err_ret = ret;
00847 break;
00848 case H_OFFDUP:
00849 if (len < HOFFPAGE_SIZE) {
00850 err_ret = DB_VERIFY_BAD;
00851 continue;
00852 }
00853 memcpy(&dpgno,
00854 HOFFPAGE_PGNO(hk), sizeof(dpgno));
00855 /* UNKNOWN iff pgno is bad or we're a key. */
00856 if (!IS_VALID_PGNO(dpgno) || (i % 2 == 0)) {
00857 if ((ret = CDB___db_prdbt(&unkdbt, 0, " ",
00858 handle, callback, 0, NULL)) != 0)
00859 err_ret = ret;
00860 } else if ((ret = CDB___db_salvage_duptree(dbp,
00861 vdp, dpgno, &dbt, handle, callback,
00862 flags | SA_SKIPFIRSTKEY)) != 0)
00863 err_ret = ret;
00864 break;
00865 case H_DUPLICATE:
00866 /*
00867  * We're a key; printing dups will seriously
00868  * foul the output. If we're being aggressive,
00869  * pretend this is a key and let the app.
00870  * programmer sort out the mess.
00871  */
00872 if (i % 2 == 0) {
00873 err_ret = ret;
00874 if (LF_ISSET(DB_AGGRESSIVE))
00875 goto keydata;
00876 break;
00877 }
00878 
00879 /* Too small to have any data. */
00880 if (len <
00881 HKEYDATA_SIZE(2 * sizeof(db_indx_t))) {
00882 err_ret = DB_VERIFY_BAD;
00883 continue;
00884 }
00885 
00886 /* Loop until we hit the total length. */
00887 for (tlen = 0; tlen + sizeof(db_indx_t) < len;
00888 tlen += dlen) {
00889 tlen += sizeof(db_indx_t);
00890 memcpy(&dlen, hk, sizeof(db_indx_t));
00891 /*
00892  * If dlen is too long, print all the
00893  * rest of the dup set in a chunk.
00894  */
00895 if (dlen + tlen > len)
00896 dlen = len - tlen;
00897 memcpy(buf, hk + tlen, dlen);
00898 dbt.size = dlen;
00899 dbt.data = buf;
00900 if ((ret = CDB___db_prdbt(&dbt, 0, " ",
00901 handle, callback, 0, NULL)) != 0)
00902 err_ret = ret;
00903 tlen += sizeof(db_indx_t);
00904 }
00905 break;
00906 }
00907 }
00908 }
00909 
00910 if ((t_ret = CDB___db_salvage_markdone(vdp, pgno)) != 0)
00911 return (t_ret);
00912 return ((ret == 0 && err_ret != 0) ? err_ret : ret);
00913 }
00914 
00915 /*
00916  * CDB___ham_meta2pgset --
00917  * Return the set of hash pages corresponding to the given
00918  * known-good meta page.
00919  *
00920  * PUBLIC: int CDB___ham_meta2pgset __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
00921  * PUBLIC: DB *));
00922  */
00923 int CDB___ham_meta2pgset(dbp, vdp, hmeta, flags, pgset)
00924 DB *dbp;
00925 VRFY_DBINFO *vdp;
00926 HMETA *hmeta;
00927 u_int32_t flags;
00928 DB *pgset;
00929 {
00930 PAGE *h;
00931 db_pgno_t pgno;
00932 u_int32_t bucket, totpgs;
00933 int ret, val;
00934 
00935 /*
00936  * We don't really need flags, but leave them for consistency with
00937  * CDB___bam_meta2pgset.
00938  */
00939 COMPQUIET(flags, 0);
00940 
00941 DB_ASSERT(pgset != NULL);
00942 
00943 totpgs = 0;
00944 
00945 /*
00946  * Loop through all the buckets, pushing onto pgset the corresponding
00947  * page(s) for each one.
00948  */
00949 for (bucket = 0; bucket <= hmeta->max_bucket; bucket++) {
00950 pgno = bucket + hmeta->spares[CDB___db_log2(bucket + 1)];
00951 
00952 /*
00953  * We know the initial pgno is safe because the spares array has
00954  * been verified.
00955  *
00956  * Safely walk the list of pages in this bucket.
00957  */
00958 for (;;) {
00959 if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00960 return (ret);
00961 if (TYPE(h) == P_HASH) {
00962 
00963 /*
00964  * Make sure we don't go past the end of
00965  * pgset.
00966  */
00967 if (++totpgs > vdp->last_pgno) {
00968 (void)CDB_memp_fput(dbp->mpf, h, 0);
00969 return (DB_VERIFY_BAD);
00970 }
00971 if ((ret =
00972 CDB___db_vrfy_pgset_inc(pgset, pgno)) != 0)
00973 return (ret);
00974 
00975 pgno = NEXT_PGNO(h);
00976 } else
00977 pgno = PGNO_INVALID;
00978 
00979 if ((ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00980 return (ret);
00981 
00982 /* If the new pgno is wonky, go onto the next bucket. */
00983 if (!IS_VALID_PGNO(pgno) ||
00984 pgno == PGNO_INVALID)
00985 goto nextbucket;
00986 
00987 /*
00988  * If we've touched this page before, we have a cycle;
00989  * go on to the next bucket.
00990  */
00991 if ((ret = CDB___db_vrfy_pgset_get(pgset, pgno, &val)) != 0)
00992 return (ret);
00993 if (val != 0)
00994 goto nextbucket;
00995 }
00996 nextbucket: ;
00997 }
00998 return (0);
00999 }
01000 
01001 /*
01002  * __ham_dups_unsorted --
01003  * Takes a known-safe hash duplicate set and its total length.
01004  * Returns 1 if there are out-of-order duplicates in this set,
01005  * 0 if there are not.
01006  */
01007 static int
01008 __ham_dups_unsorted(dbp, buf, len)
01009 DB *dbp;
01010 u_int8_t *buf;
01011 u_int32_t len;
01012 {
01013 DBT a, b;
01014 db_indx_t offset, dlen;
01015 int (*func) __P((const DBT *, const DBT *));
01016 
01017 memset(&a, 0, sizeof(DBT));
01018 memset(&b, 0, sizeof(DBT));
01019 
01020 func = (dbp->dup_compare == NULL) ? CDB___bam_defcmp : dbp->dup_compare;
01021 
01022 /*
01023  * Loop through the dup set until we hit the end or we find
01024  * a pair of dups that's out of order. b is always the current
01025  * dup, a the one before it.
01026  */
01027 for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
01028 memcpy(&dlen, buf + offset, sizeof(db_indx_t));
01029 b.data = buf + offset + sizeof(db_indx_t);
01030 b.size = dlen;
01031 
01032 if (a.data != NULL && func(&a, &b) > 0)
01033 return (1);
01034 
01035 a.data = b.data;
01036 a.size = b.size;
01037 }
01038 
01039 return (0);
01040 }