hash_verify.c

这是linux下运行的mysql软件包,可用于linux 下安装 php + mysql + apach 的网络配置

/*-
 * 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;