diff options
Diffstat (limited to 'storage/bdb/hash/hash_verify.c')
| -rw-r--r-- | storage/bdb/hash/hash_verify.c | 1079 |
1 files changed, 1079 insertions, 0 deletions
diff --git a/storage/bdb/hash/hash_verify.c b/storage/bdb/hash/hash_verify.c new file mode 100644 index 00000000000..e6f5a2b0d65 --- /dev/null +++ b/storage/bdb/hash/hash_verify.c @@ -0,0 +1,1079 @@ +/*- + * See the file LICENSE for redistribution information. + * + * Copyright (c) 1999-2002 + * Sleepycat Software. All rights reserved. + * + * $Id: hash_verify.c,v 1.53 2002/08/06 05:35:02 bostic Exp $ + */ + +#include "db_config.h" + +#ifndef lint +static const char revid[] = "$Id: hash_verify.c,v 1.53 2002/08/06 05:35:02 bostic Exp $"; +#endif /* not lint */ + +#ifndef NO_SYSTEM_INCLUDES +#include <sys/types.h> + +#include <string.h> +#endif + +#include "db_int.h" +#include "dbinc/db_page.h" +#include "dbinc/db_verify.h" +#include "dbinc/btree.h" +#include "dbinc/hash.h" + +static int __ham_dups_unsorted __P((DB *, u_int8_t *, u_int32_t)); +static int __ham_vrfy_bucket __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t, + u_int32_t)); +static int __ham_vrfy_item __P((DB *, + VRFY_DBINFO *, db_pgno_t, PAGE *, u_int32_t, u_int32_t)); + +/* + * __ham_vrfy_meta -- + * Verify the hash-specific part of a metadata page. + * + * Note that unlike btree, we don't save things off, because we + * will need most everything again to verify each page and the + * amount of state here is significant. + * + * PUBLIC: int __ham_vrfy_meta __P((DB *, VRFY_DBINFO *, HMETA *, + * PUBLIC: db_pgno_t, u_int32_t)); + */ +int +__ham_vrfy_meta(dbp, vdp, m, pgno, flags) + DB *dbp; + VRFY_DBINFO *vdp; + HMETA *m; + db_pgno_t pgno; + u_int32_t flags; +{ + HASH *hashp; + VRFY_PAGEINFO *pip; + int i, ret, t_ret, isbad; + u_int32_t pwr, mbucket; + u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t)); + + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + return (ret); + isbad = 0; + + hashp = dbp->h_internal; + + if (hashp != NULL && hashp->h_hash != NULL) + hfunc = hashp->h_hash; + else + hfunc = __ham_func5; + + /* + * If we haven't already checked the common fields in pagezero, + * check them. + */ + if (!F_ISSET(pip, VRFY_INCOMPLETE) && + (ret = __db_vrfy_meta(dbp, vdp, &m->dbmeta, pgno, flags)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + + /* h_charkey */ + if (!LF_ISSET(DB_NOORDERCHK)) + if (m->h_charkey != hfunc(dbp, CHARKEY, sizeof(CHARKEY))) { + EPRINT((dbp->dbenv, +"Page %lu: database has different custom hash function; reverify with DB_NOORDERCHK set", + (u_long)pgno)); + /* + * Return immediately; this is probably a sign + * of user error rather than database corruption, so + * we want to avoid extraneous errors. + */ + isbad = 1; + goto err; + } + + /* max_bucket must be less than the last pgno. */ + if (m->max_bucket > vdp->last_pgno) { + EPRINT((dbp->dbenv, + "Page %lu: Impossible max_bucket %lu on meta page", + (u_long)pgno, (u_long)m->max_bucket)); + /* + * Most other fields depend somehow on max_bucket, so + * we just return--there will be lots of extraneous + * errors. + */ + isbad = 1; + goto err; + } + + /* + * max_bucket, high_mask and low_mask: high_mask must be one + * less than the next power of two above max_bucket, and + * low_mask must be one less than the power of two below it. + * + * + */ + pwr = (m->max_bucket == 0) ? 1 : 1 << __db_log2(m->max_bucket + 1); + if (m->high_mask != pwr - 1) { + EPRINT((dbp->dbenv, + "Page %lu: incorrect high_mask %lu, should be %lu", + (u_long)pgno, (u_long)m->high_mask, (u_long)pwr - 1)); + isbad = 1; + } + pwr >>= 1; + if (m->low_mask != pwr - 1) { + EPRINT((dbp->dbenv, + "Page %lu: incorrect low_mask %lu, should be %lu", + (u_long)pgno, (u_long)m->low_mask, (u_long)pwr - 1)); + isbad = 1; + } + + /* ffactor: no check possible. */ + pip->h_ffactor = m->ffactor; + + /* + * nelem: just make sure it's not astronomical for now. This is the + * same check that hash_upgrade does, since there was a bug in 2.X + * which could make nelem go "negative". + */ + if (m->nelem > 0x80000000) { + EPRINT((dbp->dbenv, + "Page %lu: suspiciously high nelem of %lu", + (u_long)pgno, (u_long)m->nelem)); + isbad = 1; + pip->h_nelem = 0; + } else + pip->h_nelem = m->nelem; + + /* flags */ + if (F_ISSET(&m->dbmeta, DB_HASH_DUP)) + F_SET(pip, VRFY_HAS_DUPS); + if (F_ISSET(&m->dbmeta, DB_HASH_DUPSORT)) + F_SET(pip, VRFY_HAS_DUPSORT); + /* XXX: Why is the DB_HASH_SUBDB flag necessary? */ + + /* spares array */ + for (i = 0; m->spares[i] != 0 && i < NCACHED; i++) { + /* + * We set mbucket to the maximum bucket that would use a given + * spares entry; we want to ensure that it's always less + * than last_pgno. + */ + mbucket = (1 << i) - 1; + if (BS_TO_PAGE(mbucket, m->spares) > vdp->last_pgno) { + EPRINT((dbp->dbenv, + "Page %lu: spares array entry %d is invalid", + (u_long)pgno, i)); + isbad = 1; + } + } + +err: if ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0) + ret = t_ret; + return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret); +} + +/* + * __ham_vrfy -- + * Verify hash page. + * + * PUBLIC: int __ham_vrfy __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t, + * PUBLIC: u_int32_t)); + */ +int +__ham_vrfy(dbp, vdp, h, pgno, flags) + DB *dbp; + VRFY_DBINFO *vdp; + PAGE *h; + db_pgno_t pgno; + u_int32_t flags; +{ + VRFY_PAGEINFO *pip; + u_int32_t ent, himark, inpend; + db_indx_t *inp; + int isbad, ret, t_ret; + + isbad = 0; + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + return (ret); + + /* Sanity check our flags and page type. */ + if ((ret = __db_fchk(dbp->dbenv, "__ham_vrfy", + flags, DB_AGGRESSIVE | DB_NOORDERCHK | DB_SALVAGE)) != 0) + goto err; + + if (TYPE(h) != P_HASH) { + TYPE_ERR_PRINT(dbp->dbenv, "__ham_vrfy", pgno, TYPE(h)); + DB_ASSERT(0); + ret = EINVAL; + goto err; + } + + /* Verify and save off fields common to all PAGEs. */ + if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + + /* + * Verify inp[]. Each offset from 0 to NUM_ENT(h) must be lower + * than the previous one, higher than the current end of the inp array, + * and lower than the page size. + * + * In any case, we return immediately if things are bad, as it would + * be unsafe to proceed. + */ + inp = P_INP(dbp, h); + for (ent = 0, himark = dbp->pgsize, + inpend = (u_int32_t)((u_int8_t *)inp - (u_int8_t *)h); + ent < NUM_ENT(h); ent++) + if (inp[ent] >= himark) { + EPRINT((dbp->dbenv, + "Page %lu: item %lu is out of order or nonsensical", + (u_long)pgno, (u_long)ent)); + isbad = 1; + goto err; + } else if (inpend >= himark) { + EPRINT((dbp->dbenv, + "Page %lu: entries array collided with data", + (u_long)pgno)); + isbad = 1; + goto err; + + } else { + himark = inp[ent]; + inpend += sizeof(db_indx_t); + if ((ret = __ham_vrfy_item( + dbp, vdp, pgno, h, ent, flags)) != 0) + goto err; + } + +err: if ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0) + ret = t_ret; + return (ret == 0 && isbad == 1 ? DB_VERIFY_BAD : ret); +} + +/* + * __ham_vrfy_item -- + * Given a hash page and an offset, sanity-check the item itself, + * and save off any overflow items or off-page dup children as necessary. + */ +static int +__ham_vrfy_item(dbp, vdp, pgno, h, i, flags) + DB *dbp; + VRFY_DBINFO *vdp; + db_pgno_t pgno; + PAGE *h; + u_int32_t i, flags; +{ + HOFFPAGE hop; + HOFFDUP hod; + VRFY_CHILDINFO child; + VRFY_PAGEINFO *pip; + db_indx_t offset, len, dlen, elen; + int ret, t_ret; + u_int8_t *databuf; + + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + return (ret); + + switch (HPAGE_TYPE(dbp, h, i)) { + case H_KEYDATA: + /* Nothing to do here--everything but the type field is data */ + break; + case H_DUPLICATE: + /* Are we a datum or a key? Better be the former. */ + if (i % 2 == 0) { + EPRINT((dbp->dbenv, + "Page %lu: hash key stored as duplicate item %lu", + (u_long)pip->pgno, (u_long)i)); + } + /* + * Dups are encoded as a series within a single HKEYDATA, + * in which each dup is surrounded by a copy of its length + * on either side (so that the series can be walked in either + * direction. We loop through this series and make sure + * each dup is reasonable. + * + * Note that at this point, we've verified item i-1, so + * it's safe to use LEN_HKEYDATA (which looks at inp[i-1]). + */ + len = LEN_HKEYDATA(dbp, h, dbp->pgsize, i); + databuf = HKEYDATA_DATA(P_ENTRY(dbp, h, i)); + for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) { + memcpy(&dlen, databuf + offset, sizeof(db_indx_t)); + + /* Make sure the length is plausible. */ + if (offset + DUP_SIZE(dlen) > len) { + EPRINT((dbp->dbenv, + "Page %lu: duplicate item %lu has bad length", + (u_long)pip->pgno, (u_long)i)); + ret = DB_VERIFY_BAD; + goto err; + } + + /* + * Make sure the second copy of the length is the + * same as the first. + */ + memcpy(&elen, + databuf + offset + dlen + sizeof(db_indx_t), + sizeof(db_indx_t)); + if (elen != dlen) { + EPRINT((dbp->dbenv, + "Page %lu: duplicate item %lu has two different lengths", + (u_long)pip->pgno, (u_long)i)); + ret = DB_VERIFY_BAD; + goto err; + } + } + F_SET(pip, VRFY_HAS_DUPS); + if (!LF_ISSET(DB_NOORDERCHK) && + __ham_dups_unsorted(dbp, databuf, len)) + F_SET(pip, VRFY_DUPS_UNSORTED); + break; + case H_OFFPAGE: + /* Offpage item. Make sure pgno is sane, save off. */ + memcpy(&hop, P_ENTRY(dbp, h, i), HOFFPAGE_SIZE); + if (!IS_VALID_PGNO(hop.pgno) || hop.pgno == pip->pgno || + hop.pgno == PGNO_INVALID) { + EPRINT((dbp->dbenv, + "Page %lu: offpage item %lu has bad pgno %lu", + (u_long)pip->pgno, (u_long)i, (u_long)hop.pgno)); + ret = DB_VERIFY_BAD; + goto err; + } + memset(&child, 0, sizeof(VRFY_CHILDINFO)); + child.pgno = hop.pgno; + child.type = V_OVERFLOW; + child.tlen = hop.tlen; /* This will get checked later. */ + if ((ret = __db_vrfy_childput(vdp, pip->pgno, &child)) != 0) + goto err; + break; + case H_OFFDUP: + /* Offpage duplicate item. Same drill. */ + memcpy(&hod, P_ENTRY(dbp, h, i), HOFFDUP_SIZE); + if (!IS_VALID_PGNO(hod.pgno) || hod.pgno == pip->pgno || + hod.pgno == PGNO_INVALID) { + EPRINT((dbp->dbenv, + "Page %lu: offpage item %lu has bad page number", + (u_long)pip->pgno, (u_long)i)); + ret = DB_VERIFY_BAD; + goto err; + } + memset(&child, 0, sizeof(VRFY_CHILDINFO)); + child.pgno = hod.pgno; + child.type = V_DUPLICATE; + if ((ret = __db_vrfy_childput(vdp, pip->pgno, &child)) != 0) + goto err; + F_SET(pip, VRFY_HAS_DUPS); + break; + default: + EPRINT((dbp->dbenv, + "Page %lu: item %i has bad type", + (u_long)pip->pgno, (u_long)i)); + ret = DB_VERIFY_BAD; + break; + } + +err: if ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0) + ret = t_ret; + return (ret); +} + +/* + * __ham_vrfy_structure -- + * Verify the structure of a hash database. + * + * PUBLIC: int __ham_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t, + * PUBLIC: u_int32_t)); + */ +int +__ham_vrfy_structure(dbp, vdp, meta_pgno, flags) + DB *dbp; + VRFY_DBINFO *vdp; + db_pgno_t meta_pgno; + u_int32_t flags; +{ + DB *pgset; + DB_MPOOLFILE *mpf; + HMETA *m; + PAGE *h; + VRFY_PAGEINFO *pip; + int isbad, p, ret, t_ret; + db_pgno_t pgno; + u_int32_t bucket, spares_entry; + + mpf = dbp->mpf; + pgset = vdp->pgset; + h = NULL; + ret = isbad = 0; + + if ((ret = __db_vrfy_pgset_get(pgset, meta_pgno, &p)) != 0) + return (ret); + if (p != 0) { + EPRINT((dbp->dbenv, + "Page %lu: Hash meta page referenced twice", + (u_long)meta_pgno)); + return (DB_VERIFY_BAD); + } + if ((ret = __db_vrfy_pgset_inc(pgset, meta_pgno)) != 0) + return (ret); + + /* Get the meta page; we'll need it frequently. */ + if ((ret = mpf->get(mpf, &meta_pgno, 0, &m)) != 0) + return (ret); + + /* Loop through bucket by bucket. */ + for (bucket = 0; bucket <= m->max_bucket; bucket++) + if ((ret = + __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + + /* + * There may be unused hash pages corresponding to buckets + * that have been allocated but not yet used. These may be + * part of the current doubling above max_bucket, or they may + * correspond to buckets that were used in a transaction + * that then aborted. + * + * Loop through them, as far as the spares array defines them, + * and make sure they're all empty. + * + * Note that this should be safe, since we've already verified + * that the spares array is sane. + */ + for (bucket = m->max_bucket + 1; spares_entry = __db_log2(bucket + 1), + spares_entry < NCACHED && m->spares[spares_entry] != 0; bucket++) { + pgno = BS_TO_PAGE(bucket, m->spares); + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + goto err; + + /* It's okay if these pages are totally zeroed; unmark it. */ + F_CLR(pip, VRFY_IS_ALLZEROES); + + /* It's also OK if this page is simply invalid. */ + if (pip->type == P_INVALID) { + if ((ret = __db_vrfy_putpageinfo(dbp->dbenv, + vdp, pip)) != 0) + goto err; + continue; + } + + if (pip->type != P_HASH) { + EPRINT((dbp->dbenv, + "Page %lu: hash bucket %lu maps to non-hash page", + (u_long)pgno, (u_long)bucket)); + isbad = 1; + } else if (pip->entries != 0) { + EPRINT((dbp->dbenv, + "Page %lu: non-empty page in unused hash bucket %lu", + (u_long)pgno, (u_long)bucket)); + isbad = 1; + } else { + if ((ret = __db_vrfy_pgset_get(pgset, pgno, &p)) != 0) + goto err; + if (p != 0) { + EPRINT((dbp->dbenv, + "Page %lu: above max_bucket referenced", + (u_long)pgno)); + isbad = 1; + } else { + if ((ret = + __db_vrfy_pgset_inc(pgset, pgno)) != 0) + goto err; + if ((ret = __db_vrfy_putpageinfo(dbp->dbenv, + vdp, pip)) != 0) + goto err; + continue; + } + } + + /* If we got here, it's an error. */ + (void)__db_vrfy_putpageinfo(dbp->dbenv, vdp, pip); + goto err; + } + +err: if ((t_ret = mpf->put(mpf, m, 0)) != 0) + return (t_ret); + if (h != NULL && (t_ret = mpf->put(mpf, h, 0)) != 0) + return (t_ret); + return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD: ret); +} + +/* + * __ham_vrfy_bucket -- + * Verify a given bucket. + */ +static int +__ham_vrfy_bucket(dbp, vdp, m, bucket, flags) + DB *dbp; + VRFY_DBINFO *vdp; + HMETA *m; + u_int32_t bucket, flags; +{ + HASH *hashp; + VRFY_CHILDINFO *child; + VRFY_PAGEINFO *mip, *pip; + int ret, t_ret, isbad, p; + db_pgno_t pgno, next_pgno; + DBC *cc; + u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t)); + + isbad = 0; + pip = NULL; + cc = NULL; + + hashp = dbp->h_internal; + if (hashp != NULL && hashp->h_hash != NULL) + hfunc = hashp->h_hash; + else + hfunc = __ham_func5; + + if ((ret = __db_vrfy_getpageinfo(vdp, PGNO(m), &mip)) != 0) + return (ret); + + /* Calculate the first pgno for this bucket. */ + pgno = BS_TO_PAGE(bucket, m->spares); + + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + goto err; + + /* Make sure we got a plausible page number. */ + if (pgno > vdp->last_pgno || pip->type != P_HASH) { + EPRINT((dbp->dbenv, + "Page %lu: impossible first page in bucket %lu", + (u_long)pgno, (u_long)bucket)); + /* Unsafe to continue. */ + isbad = 1; + goto err; + } + + if (pip->prev_pgno != PGNO_INVALID) { + EPRINT((dbp->dbenv, + "Page %lu: first page in hash bucket %lu has a prev_pgno", + (u_long)pgno, (u_long)bucket)); + isbad = 1; + } + + /* + * Set flags for dups and sorted dups. + */ + flags |= F_ISSET(mip, VRFY_HAS_DUPS) ? ST_DUPOK : 0; + flags |= F_ISSET(mip, VRFY_HAS_DUPSORT) ? ST_DUPSORT : 0; + + /* Loop until we find a fatal bug, or until we run out of pages. */ + for (;;) { + /* Provide feedback on our progress to the application. */ + if (!LF_ISSET(DB_SALVAGE)) + __db_vrfy_struct_feedback(dbp, vdp); + + if ((ret = __db_vrfy_pgset_get(vdp->pgset, pgno, &p)) != 0) + goto err; + if (p != 0) { + EPRINT((dbp->dbenv, + "Page %lu: hash page referenced twice", + (u_long)pgno)); + isbad = 1; + /* Unsafe to continue. */ + goto err; + } else if ((ret = __db_vrfy_pgset_inc(vdp->pgset, pgno)) != 0) + goto err; + + /* + * Hash pages that nothing has ever hashed to may never + * have actually come into existence, and may appear to be + * entirely zeroed. This is acceptable, and since there's + * no real way for us to know whether this has actually + * occurred, we clear the "wholly zeroed" flag on every + * hash page. A wholly zeroed page, by nature, will appear + * to have no flags set and zero entries, so should + * otherwise verify correctly. + */ + F_CLR(pip, VRFY_IS_ALLZEROES); + + /* If we have dups, our meta page had better know about it. */ + if (F_ISSET(pip, VRFY_HAS_DUPS) && + !F_ISSET(mip, VRFY_HAS_DUPS)) { + EPRINT((dbp->dbenv, + "Page %lu: duplicates present in non-duplicate database", + (u_long)pgno)); + isbad = 1; + } + + /* + * If the database has sorted dups, this page had better + * not have unsorted ones. + */ + if (F_ISSET(mip, VRFY_HAS_DUPSORT) && + F_ISSET(pip, VRFY_DUPS_UNSORTED)) { + EPRINT((dbp->dbenv, + "Page %lu: unsorted dups in sorted-dup database", + (u_long)pgno)); + isbad = 1; + } + + /* Walk overflow chains and offpage dup trees. */ + if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0) + goto err; + for (ret = __db_vrfy_ccset(cc, pip->pgno, &child); ret == 0; + ret = __db_vrfy_ccnext(cc, &child)) + if (child->type == V_OVERFLOW) { + if ((ret = __db_vrfy_ovfl_structure(dbp, vdp, + child->pgno, child->tlen, flags)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + } else if (child->type == V_DUPLICATE) { + if ((ret = __db_vrfy_duptype(dbp, + vdp, child->pgno, flags)) != 0) { + isbad = 1; + continue; + } + if ((ret = __bam_vrfy_subtree(dbp, vdp, + child->pgno, NULL, NULL, + flags | ST_RECNUM | ST_DUPSET | ST_TOPLEVEL, + NULL, NULL, NULL)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + } + if ((ret = __db_vrfy_ccclose(cc)) != 0) + goto err; + cc = NULL; + + /* If it's safe to check that things hash properly, do so. */ + if (isbad == 0 && !LF_ISSET(DB_NOORDERCHK) && + (ret = __ham_vrfy_hashing(dbp, pip->entries, + m, bucket, pgno, flags, hfunc)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + + next_pgno = pip->next_pgno; + ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip); + + pip = NULL; + if (ret != 0) + goto err; + + if (next_pgno == PGNO_INVALID) + break; /* End of the bucket. */ + + /* We already checked this, but just in case... */ + if (!IS_VALID_PGNO(next_pgno)) { + DB_ASSERT(0); + EPRINT((dbp->dbenv, + "Page %lu: hash page has bad next_pgno", + (u_long)pgno)); + isbad = 1; + goto err; + } + + if ((ret = __db_vrfy_getpageinfo(vdp, next_pgno, &pip)) != 0) + goto err; + + if (pip->prev_pgno != pgno) { + EPRINT((dbp->dbenv, + "Page %lu: hash page has bad prev_pgno", + (u_long)next_pgno)); + isbad = 1; + } + pgno = next_pgno; + } + +err: if (cc != NULL && ((t_ret = __db_vrfy_ccclose(cc)) != 0) && ret == 0) + ret = t_ret; + if (mip != NULL && ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, mip)) != 0) && ret == 0) + ret = t_ret; + if (pip != NULL && ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0) && ret == 0) + ret = t_ret; + return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret); +} + +/* + * __ham_vrfy_hashing -- + * Verify that all items on a given hash page hash correctly. + * + * PUBLIC: int __ham_vrfy_hashing __P((DB *, + * PUBLIC: u_int32_t, HMETA *, u_int32_t, db_pgno_t, u_int32_t, + * PUBLIC: u_int32_t (*) __P((DB *, const void *, u_int32_t)))); + */ +int +__ham_vrfy_hashing(dbp, nentries, m, thisbucket, pgno, flags, hfunc) + DB *dbp; + u_int32_t nentries; + HMETA *m; + u_int32_t thisbucket; + db_pgno_t pgno; + u_int32_t flags; + u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t)); +{ + DBT dbt; + DB_MPOOLFILE *mpf; + PAGE *h; + db_indx_t i; + int ret, t_ret, isbad; + u_int32_t hval, bucket; + + mpf = dbp->mpf; + ret = isbad = 0; + + memset(&dbt, 0, sizeof(DBT)); + F_SET(&dbt, DB_DBT_REALLOC); + + if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0) + return (ret); + + for (i = 0; i < nentries; i += 2) { + /* + * We've already verified the page integrity and that of any + * overflow chains linked off it; it is therefore safe to use + * __db_ret. It's also not all that much slower, since we have + * to copy every hash item to deal with alignment anyway; we + * can tweak this a bit if this proves to be a bottleneck, + * but for now, take the easy route. + */ + if ((ret = __db_ret(dbp, h, i, &dbt, NULL, NULL)) != 0) + goto err; + hval = hfunc(dbp, dbt.data, dbt.size); + + bucket = hval & m->high_mask; + if (bucket > m->max_bucket) + bucket = bucket & m->low_mask; + + if (bucket != thisbucket) { + EPRINT((dbp->dbenv, + "Page %lu: item %lu hashes incorrectly", + (u_long)pgno, (u_long)i)); + isbad = 1; + } + } + +err: if (dbt.data != NULL) + __os_ufree(dbp->dbenv, dbt.data); + if ((t_ret = mpf->put(mpf, h, 0)) != 0) + return (t_ret); + + return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret); +} + +/* + * __ham_salvage -- + * Safely dump out anything that looks like a key on an alleged + * hash page. + * + * PUBLIC: int __ham_salvage __P((DB *, VRFY_DBINFO *, db_pgno_t, PAGE *, + * PUBLIC: void *, int (*)(void *, const void *), u_int32_t)); + */ +int +__ham_salvage(dbp, vdp, pgno, h, handle, callback, flags) + DB *dbp; + VRFY_DBINFO *vdp; + db_pgno_t pgno; + PAGE *h; + void *handle; + int (*callback) __P((void *, const void *)); + u_int32_t flags; +{ + DBT dbt, unkdbt; + db_pgno_t dpgno; + int ret, err_ret, t_ret; + u_int32_t himark, tlen; + u_int8_t *hk; + void *buf; + u_int32_t dlen, len, i; + + memset(&dbt, 0, sizeof(DBT)); + dbt.flags = DB_DBT_REALLOC; + + memset(&unkdbt, 0, sizeof(DBT)); + unkdbt.size = (u_int32_t)strlen("UNKNOWN") + 1; + unkdbt.data = "UNKNOWN"; + + err_ret = 0; + + /* + * Allocate a buffer for overflow items. Start at one page; + * __db_safe_goff will realloc as needed. + */ + if ((ret = __os_malloc(dbp->dbenv, dbp->pgsize, &buf)) != 0) + return (ret); + + himark = dbp->pgsize; + for (i = 0;; i++) { + /* If we're not aggressive, break when we hit NUM_ENT(h). */ + if (!LF_ISSET(DB_AGGRESSIVE) && i >= NUM_ENT(h)) + break; + + /* Verify the current item. */ + ret = __db_vrfy_inpitem(dbp, + h, pgno, i, 0, flags, &himark, NULL); + /* If this returned a fatality, it's time to break. */ + if (ret == DB_VERIFY_FATAL) + break; + + if (ret == 0) { + hk = P_ENTRY(dbp, h, i); + len = LEN_HKEYDATA(dbp, h, dbp->pgsize, i); + if ((u_int32_t)(hk + len - (u_int8_t *)h) > + dbp->pgsize) { + /* + * Item is unsafely large; either continue + * or set it to the whole page, depending on + * aggressiveness. + */ + if (!LF_ISSET(DB_AGGRESSIVE)) + continue; + len = dbp->pgsize - + (u_int32_t)(hk - (u_int8_t *)h); + err_ret = DB_VERIFY_BAD; + } + switch (HPAGE_PTYPE(hk)) { + default: + if (!LF_ISSET(DB_AGGRESSIVE)) + break; + err_ret = DB_VERIFY_BAD; + /* FALLTHROUGH */ + case H_KEYDATA: +keydata: memcpy(buf, HKEYDATA_DATA(hk), len); + dbt.size = len; + dbt.data = buf; + if ((ret = __db_prdbt(&dbt, + 0, " ", handle, callback, 0, vdp)) != 0) + err_ret = ret; + break; + case H_OFFPAGE: + if (len < HOFFPAGE_SIZE) { + err_ret = DB_VERIFY_BAD; + continue; + } + memcpy(&dpgno, + HOFFPAGE_PGNO(hk), sizeof(dpgno)); + if ((ret = __db_safe_goff(dbp, vdp, + dpgno, &dbt, &buf, flags)) != 0) { + err_ret = ret; + (void)__db_prdbt(&unkdbt, 0, " ", + handle, callback, 0, vdp); + break; + } + if ((ret = __db_prdbt(&dbt, + 0, " ", handle, callback, 0, vdp)) != 0) + err_ret = ret; + break; + case H_OFFDUP: + if (len < HOFFPAGE_SIZE) { + err_ret = DB_VERIFY_BAD; + continue; + } + memcpy(&dpgno, + HOFFPAGE_PGNO(hk), sizeof(dpgno)); + /* UNKNOWN iff pgno is bad or we're a key. */ + if (!IS_VALID_PGNO(dpgno) || (i % 2 == 0)) { + if ((ret = __db_prdbt(&unkdbt, 0, " ", + handle, callback, 0, vdp)) != 0) + err_ret = ret; + } else if ((ret = __db_salvage_duptree(dbp, + vdp, dpgno, &dbt, handle, callback, + flags | SA_SKIPFIRSTKEY)) != 0) + err_ret = ret; + break; + case H_DUPLICATE: + /* + * We're a key; printing dups will seriously + * foul the output. If we're being aggressive, + * pretend this is a key and let the app. + * programmer sort out the mess. + */ + if (i % 2 == 0) { + err_ret = ret; + if (LF_ISSET(DB_AGGRESSIVE)) + goto keydata; + break; + } + + /* Too small to have any data. */ + if (len < + HKEYDATA_SIZE(2 * sizeof(db_indx_t))) { + err_ret = DB_VERIFY_BAD; + continue; + } + + /* Loop until we hit the total length. */ + for (tlen = 0; tlen + sizeof(db_indx_t) < len; + tlen += dlen) { + tlen += sizeof(db_indx_t); + memcpy(&dlen, hk, sizeof(db_indx_t)); + /* + * If dlen is too long, print all the + * rest of the dup set in a chunk. + */ + if (dlen + tlen > len) + dlen = len - tlen; + memcpy(buf, hk + tlen, dlen); + dbt.size = dlen; + dbt.data = buf; + if ((ret = __db_prdbt(&dbt, 0, " ", + handle, callback, 0, vdp)) != 0) + err_ret = ret; + tlen += sizeof(db_indx_t); + } + break; + } + } + } + + __os_free(dbp->dbenv, buf); + if ((t_ret = __db_salvage_markdone(vdp, pgno)) != 0) + return (t_ret); + return ((ret == 0 && err_ret != 0) ? err_ret : ret); +} + +/* + * __ham_meta2pgset -- + * Return the set of hash pages corresponding to the given + * known-good meta page. + * + * PUBLIC: int __ham_meta2pgset __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t, + * PUBLIC: DB *)); + */ +int __ham_meta2pgset(dbp, vdp, hmeta, flags, pgset) + DB *dbp; + VRFY_DBINFO *vdp; + HMETA *hmeta; + u_int32_t flags; + DB *pgset; +{ + DB_MPOOLFILE *mpf; + PAGE *h; + db_pgno_t pgno; + u_int32_t bucket, totpgs; + int ret, val; + + /* + * We don't really need flags, but leave them for consistency with + * __bam_meta2pgset. + */ + COMPQUIET(flags, 0); + + DB_ASSERT(pgset != NULL); + + mpf = dbp->mpf; + totpgs = 0; + + /* + * Loop through all the buckets, pushing onto pgset the corresponding + * page(s) for each one. + */ + for (bucket = 0; bucket <= hmeta->max_bucket; bucket++) { + pgno = BS_TO_PAGE(bucket, hmeta->spares); + + /* + * We know the initial pgno is safe because the spares array has + * been verified. + * + * Safely walk the list of pages in this bucket. + */ + for (;;) { + if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0) + return (ret); + if (TYPE(h) == P_HASH) { + + /* + * Make sure we don't go past the end of + * pgset. + */ + if (++totpgs > vdp->last_pgno) { + (void)mpf->put(mpf, h, 0); + return (DB_VERIFY_BAD); + } + if ((ret = + __db_vrfy_pgset_inc(pgset, pgno)) != 0) { + (void)mpf->put(mpf, h, 0); + return (ret); + } + + pgno = NEXT_PGNO(h); + } else + pgno = PGNO_INVALID; + + if ((ret = mpf->put(mpf, h, 0)) != 0) + return (ret); + + /* If the new pgno is wonky, go onto the next bucket. */ + if (!IS_VALID_PGNO(pgno) || + pgno == PGNO_INVALID) + break; + + /* + * If we've touched this page before, we have a cycle; + * go on to the next bucket. + */ + if ((ret = __db_vrfy_pgset_get(pgset, pgno, &val)) != 0) + return (ret); + if (val != 0) + break; + } + } + return (0); +} + +/* + * __ham_dups_unsorted -- + * Takes a known-safe hash duplicate set and its total length. + * Returns 1 if there are out-of-order duplicates in this set, + * 0 if there are not. + */ +static int +__ham_dups_unsorted(dbp, buf, len) + DB *dbp; + u_int8_t *buf; + u_int32_t len; +{ + DBT a, b; + db_indx_t offset, dlen; + int (*func) __P((DB *, const DBT *, const DBT *)); + + memset(&a, 0, sizeof(DBT)); + memset(&b, 0, sizeof(DBT)); + + func = (dbp->dup_compare == NULL) ? __bam_defcmp : dbp->dup_compare; + + /* + * Loop through the dup set until we hit the end or we find + * a pair of dups that's out of order. b is always the current + * dup, a the one before it. + */ + for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) { + memcpy(&dlen, buf + offset, sizeof(db_indx_t)); + b.data = buf + offset + sizeof(db_indx_t); + b.size = dlen; + + if (a.data != NULL && func(dbp, &a, &b) > 0) + return (1); + + a.data = b.data; + a.size = b.size; + } + + return (0); +} |