diff options
Diffstat (limited to 'libdb/hash/hash_verify.c')
| -rw-r--r-- | libdb/hash/hash_verify.c | 1079 |
1 files changed, 0 insertions, 1079 deletions
diff --git a/libdb/hash/hash_verify.c b/libdb/hash/hash_verify.c deleted file mode 100644 index ebe3feaa5..000000000 --- a/libdb/hash/hash_verify.c +++ /dev/null @@ -1,1079 +0,0 @@ -/*- - * See the file LICENSE for redistribution information. - * - * Copyright (c) 1999-2002 - * Sleepycat Software. All rights reserved. - * - * $Id$ - */ - -#include "db_config.h" - -#ifndef lint -static const char revid[] = "$Id$"; -#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); -} |