bt_verify.c

这是国外的resip协议栈

	if ((db_indx_t)himark != HOFFSET(h)) {
		EPRINT((dbenv,
		    "Page %lu: bad HOFFSET %lu, appears to be %lu",
		    (u_long)pgno, (u_long)(HOFFSET(h)), (u_long)himark));
		isbad = 1;
	}

	*nentriesp = nentries;

err:	if ((t_ret = __db_vrfy_putpageinfo(dbenv, vdp, pip)) != 0 && ret == 0)
		ret = t_ret;
	if (pagelayout != NULL)
		__os_free(dbenv, pagelayout);
	return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
}

typedef enum { VRFY_ITEM_NOTSET=0, VRFY_ITEM_BEGIN, VRFY_ITEM_END } VRFY_ITEM;

/*
 * __bam_vrfy_inp --
 *	Verify that all entries in inp[] array are reasonable;
 *	count them.
 */
static int
__bam_vrfy_inp(dbp, vdp, h, pgno, nentriesp, flags)
	DB *dbp;
	VRFY_DBINFO *vdp;
	PAGE *h;
	db_pgno_t pgno;
	db_indx_t *nentriesp;
	u_int32_t flags;
{
	BKEYDATA *bk;
	BOVERFLOW *bo;
	DB_ENV *dbenv;
	VRFY_CHILDINFO child;
	VRFY_ITEM *pagelayout;
	VRFY_PAGEINFO *pip;
	u_int32_t himark, offset;		/*
						 * These would be db_indx_ts
						 * but for alignment.
						 */
	u_int32_t i, endoff, nentries;
	int isbad, initem, isdupitem, ret, t_ret;

	dbenv = dbp->dbenv;
	isbad = isdupitem = 0;
	nentries = 0;
	memset(&child, 0, sizeof(VRFY_CHILDINFO));
	if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
		return (ret);

	switch (TYPE(h)) {
	case P_IBTREE:
	case P_LBTREE:
	case P_LDUP:
	case P_LRECNO:
		break;
	default:
		/*
		 * In the salvager, we might call this from a page which
		 * we merely suspect is a btree page.  Otherwise, it
		 * shouldn't get called--if it is, that's a verifier bug.
		 */
		if (LF_ISSET(DB_SALVAGE))
			break;
		TYPE_ERR_PRINT(dbenv, "__bam_vrfy_inp", pgno, TYPE(h));
		DB_ASSERT(0);
		ret = EINVAL;
		goto err;
	}

	/*
	 * Loop through inp[], the array of items, until we either
	 * run out of entries or collide with the data.  Keep track
	 * of h_offset in himark.
	 *
	 * For each element in inp[i], make sure it references a region
	 * that starts after the end of the inp array (as defined by
	 * NUM_ENT(h)), ends before the beginning of the page, doesn't
	 * overlap any other regions, and doesn't have a gap between
	 * it and the region immediately after it.
	 */
	himark = dbp->pgsize;
	if ((ret = __os_calloc(
	    dbenv, dbp->pgsize, sizeof(pagelayout[0]), &pagelayout)) != 0)
		goto err;
	for (i = 0; i < NUM_ENT(h); i++) {
		switch (ret = __db_vrfy_inpitem(dbp,
		    h, pgno, i, 1, flags, &himark, &offset)) {
		case 0:
			break;
		case DB_VERIFY_BAD:
			isbad = 1;
			continue;
		case DB_VERIFY_FATAL:
			isbad = 1;
			goto err;
		default:
			DB_ASSERT(ret != 0);
			break;
		}

		/*
		 * We now have a plausible beginning for the item, and we know
		 * its length is safe.
		 *
		 * Mark the beginning and end in pagelayout so we can make sure
		 * items have no overlaps or gaps.
		 */
		bk = GET_BKEYDATA(dbp, h, i);
		if (pagelayout[offset] == VRFY_ITEM_NOTSET)
			pagelayout[offset] = VRFY_ITEM_BEGIN;
		else if (pagelayout[offset] == VRFY_ITEM_BEGIN) {
			/*
			 * Having two inp entries that point at the same patch
			 * of page is legal if and only if the page is
			 * a btree leaf and they're onpage duplicate keys--
			 * that is, if (i % P_INDX) == 0.
			 */
			if ((i % P_INDX == 0) && (TYPE(h) == P_LBTREE)) {
				/* Flag for later. */
				F_SET(pip, VRFY_HAS_DUPS);

				/* Bump up nentries so we don't undercount. */
				nentries++;

				/*
				 * We'll check to make sure the end is
				 * equal, too.
				 */
				isdupitem = 1;
			} else {
				isbad = 1;
				EPRINT((dbenv, "Page %lu: duplicated item %lu",
				    (u_long)pgno, (u_long)i));
			}
		}

		/*
		 * Mark the end.  Its location varies with the page type
		 * and the item type.
		 *
		 * If the end already has a sign other than 0, do nothing--
		 * it's an overlap that we'll catch later.
		 */
		switch (B_TYPE(bk->type)) {
		case B_KEYDATA:
			if (TYPE(h) == P_IBTREE)
				/* It's a BINTERNAL. */
				endoff = offset + BINTERNAL_SIZE(bk->len) - 1;
			else
				endoff = offset + BKEYDATA_SIZE(bk->len) - 1;
			break;
		case B_DUPLICATE:
			/*
			 * Flag that we have dups; we'll check whether
			 * that's okay during the structure check.
			 */
			F_SET(pip, VRFY_HAS_DUPS);
			/* FALLTHROUGH */
		case B_OVERFLOW:
			/*
			 * Overflow entries on internal pages are stored
			 * as the _data_ of a BINTERNAL;  overflow entries
			 * on leaf pages are stored as the entire entry.
			 */
			endoff = offset +
			    ((TYPE(h) == P_IBTREE) ?
			    BINTERNAL_SIZE(BOVERFLOW_SIZE) :
			    BOVERFLOW_SIZE) - 1;
			break;
		default:
			/*
			 * We'll complain later;  for now, just mark
			 * a minimum.
			 */
			endoff = offset + BKEYDATA_SIZE(0) - 1;
			break;
		}

		/*
		 * If this is an onpage duplicate key we've seen before,
		 * the end had better coincide too.
		 */
		if (isdupitem && pagelayout[endoff] != VRFY_ITEM_END) {
			EPRINT((dbenv, "Page %lu: duplicated item %lu",
			    (u_long)pgno, (u_long)i));
			isbad = 1;
		} else if (pagelayout[endoff] == VRFY_ITEM_NOTSET)
			pagelayout[endoff] = VRFY_ITEM_END;
		isdupitem = 0;

		/*
		 * There should be no deleted items in a quiescent tree,
		 * except in recno.
		 */
		if (B_DISSET(bk->type) && TYPE(h) != P_LRECNO) {
			isbad = 1;
			EPRINT((dbenv, "Page %lu: item %lu marked deleted",
			    (u_long)pgno, (u_long)i));
		}

		/*
		 * Check the type and such of bk--make sure it's reasonable
		 * for the pagetype.
		 */
		switch (B_TYPE(bk->type)) {
		case B_KEYDATA:
			/*
			 * This is a normal, non-overflow BKEYDATA or BINTERNAL.
			 * The only thing to check is the len, and that's
			 * already been done.
			 */
			break;
		case B_DUPLICATE:
			if (TYPE(h) == P_IBTREE) {
				isbad = 1;
				EPRINT((dbenv,
    "Page %lu: duplicate page referenced by internal btree page at item %lu",
				    (u_long)pgno, (u_long)i));
				break;
			} else if (TYPE(h) == P_LRECNO) {
				isbad = 1;
				EPRINT((dbenv,
	"Page %lu: duplicate page referenced by recno page at item %lu",
				    (u_long)pgno, (u_long)i));
				break;
			}
			/* FALLTHROUGH */
		case B_OVERFLOW:
			bo = (TYPE(h) == P_IBTREE) ?
			    (BOVERFLOW *)(((BINTERNAL *)bk)->data) :
			    (BOVERFLOW *)bk;

			if (B_TYPE(bk->type) == B_OVERFLOW)
				/* Make sure tlen is reasonable. */
				if (bo->tlen > dbp->pgsize * vdp->last_pgno) {
					isbad = 1;
					EPRINT((dbenv,
				"Page %lu: impossible tlen %lu, item %lu",
					    (u_long)pgno,
					    (u_long)bo->tlen, (u_long)i));
					/* Don't save as a child. */
					break;
				}

			if (!IS_VALID_PGNO(bo->pgno) || bo->pgno == pgno ||
			    bo->pgno == PGNO_INVALID) {
				isbad = 1;
				EPRINT((dbenv,
			    "Page %lu: offpage item %lu has bad pgno %lu",
				    (u_long)pgno, (u_long)i, (u_long)bo->pgno));
				/* Don't save as a child. */
				break;
			}

			child.pgno = bo->pgno;
			child.type = (B_TYPE(bk->type) == B_OVERFLOW ?
			    V_OVERFLOW : V_DUPLICATE);
			child.tlen = bo->tlen;
			if ((ret = __db_vrfy_childput(vdp, pgno, &child)) != 0)
				goto err;
			break;
		default:
			isbad = 1;
			EPRINT((dbenv, "Page %lu: item %lu of invalid type %lu",
			    (u_long)pgno, (u_long)i, (u_long)B_TYPE(bk->type)));
			break;
		}
	}

	/*
	 * Now, loop through and make sure the items are contiguous and
	 * non-overlapping.
	 */
	initem = 0;
	for (i = himark; i < dbp->pgsize; i++)
		if (initem == 0)
			switch (pagelayout[i]) {
			case VRFY_ITEM_NOTSET:
				/* May be just for alignment. */
				if (i != DB_ALIGN(i, sizeof(u_int32_t)))
					continue;

				isbad = 1;
				EPRINT((dbenv,
				    "Page %lu: gap between items at offset %lu",
				    (u_long)pgno, (u_long)i));
				/* Find the end of the gap */
				for (; pagelayout[i + 1] == VRFY_ITEM_NOTSET &&
				    (size_t)(i + 1) < dbp->pgsize; i++)
					;
				break;
			case VRFY_ITEM_BEGIN:
				/* We've found an item. Check its alignment. */
				if (i != DB_ALIGN(i, sizeof(u_int32_t))) {
					isbad = 1;
					EPRINT((dbenv,
					    "Page %lu: offset %lu unaligned",
					    (u_long)pgno, (u_long)i));
				}
				initem = 1;
				nentries++;
				break;
			case VRFY_ITEM_END:
				/*
				 * We've hit the end of an item even though
				 * we don't think we're in one;  must
				 * be an overlap.
				 */
				isbad = 1;
				EPRINT((dbenv,
				    "Page %lu: overlapping items at offset %lu",
				    (u_long)pgno, (u_long)i));
				break;
			}
		else
			switch (pagelayout[i]) {
			case VRFY_ITEM_NOTSET:
				/* In the middle of an item somewhere. Okay. */
				break;
			case VRFY_ITEM_END:
				/* End of an item; switch to out-of-item mode.*/
				initem = 0;
				break;
			case VRFY_ITEM_BEGIN:
				/*
				 * Hit a second item beginning without an
				 * end.  Overlap.
				 */
				isbad = 1;
				EPRINT((dbenv,
				    "Page %lu: overlapping items at offset %lu",
				    (u_long)pgno, (u_long)i));
				break;
			}

	__os_free(dbenv, pagelayout);

	/* Verify HOFFSET. */
	if ((db_indx_t)himark != HOFFSET(h)) {
		EPRINT((dbenv, "Page %lu: bad HOFFSET %lu, appears to be %lu",
		    (u_long)pgno, (u_long)HOFFSET(h), (u_long)himark));
		isbad = 1;
	}

err:	if (nentriesp != NULL)
		*nentriesp = nentries;

	if ((t_ret = __db_vrfy_putpageinfo(dbenv, vdp, pip)) != 0 && ret == 0)
		ret = t_ret;

	return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD : ret);
}

/*
 * __bam_vrfy_itemorder --
 *	Make sure the items on a page sort correctly.
 *
 *	Assumes that NUM_ENT(h) and inp[0]..inp[NUM_ENT(h) - 1] are
 *	reasonable;  be sure that __bam_vrfy_inp has been called first.
 *
 *	If ovflok is set, it also assumes that overflow page chains
 *	hanging off the current page have been sanity-checked, and so we
 *	can use __bam_cmp to verify their ordering.  If it is not set,
 *	and we run into an overflow page, carp and return DB_VERIFY_BAD;
 *	we shouldn't be called if any exist.
 *
 * PUBLIC: int __bam_vrfy_itemorder __P((DB *, VRFY_DBINFO *, PAGE *,
 * PUBLIC:     db_pgno_t, u_int32_t, int, int, u_int32_t));
 */
int
__bam_vrfy_itemorder(dbp, vdp, h, pgno, nentries, ovflok, hasdups, flags)
	DB *dbp;
	VRFY_DBINFO *vdp;
	PAGE *h;
	db_pgno_t pgno;
	u_int32_t nentries;
	int ovflok, hasdups;
	u_int32_t flags;
{
	BINTERNAL *bi;
	BKEYDATA *bk;
	BOVERFLOW *bo;
	BTREE *bt;
	DBT dbta, dbtb, dup_1, dup_2, *p1, *p2, *tmp;
	DB_ENV *dbenv;
	VRFY_PAGEINFO *pip;
	db_indx_t i;
	int cmp, freedup_1, freedup_2, isbad, ret, t_ret;
	int (*dupfunc) __P((DB *, const DBT *, const DBT *));
	int (*func) __P((DB *, const DBT *, const DBT *));
	void *buf1, *buf2, *tmpbuf;

	/*
	 * We need to work in the ORDERCHKONLY environment where we might
	 * not have a pip, but we also may need to work in contexts where
	 * NUM_ENT isn't safe.
	 */
	if (vdp != NULL) {
		if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
			return (ret);
		nentries = pip->entries;
	} else
		pip = NULL;

	dbenv = dbp->dbenv;
	ret = isbad = 0;
	bo = NULL;			/* Shut up compiler. */

	memset(&dbta, 0, sizeof(DBT));
	F_SET(&dbta, DB_DBT_REALLOC);

	memset(&dbtb, 0, sizeof(DBT));
	F_SET(&dbtb, DB_DBT_REALLOC);

	buf1 = buf2 = NULL;

	DB_ASSERT(!LF_ISSET(DB_NOORDERCHK));

	dupfunc = (dbp->dup_compare == NULL) ? __bam_defcmp : dbp->dup_compare;
	if (TYPE(h) == P_LDUP)
		func = dupfunc;
	else {
		func = __bam_defcmp;
		if (dbp->bt_internal != NULL) {
			bt = (BTREE *)dbp->bt_internal;
			if (bt->bt_compare != NULL)
				func = bt->bt_compare;
		}
	}

	/*
	 * We alternate our use of dbta and dbtb so that we can walk
	 * through the page key-by-key without copying a dbt twice.
	 * p1 is always the dbt for index i - 1, and p2 for index i.
	 */
	p1 = &dbta;
	p2 = &dbtb;

	/*
	 * Loop through the entries.  nentries ought to contain the
	 * actual count, and so is a safe way to terminate the loop;  whether
	 * we inc. by one or two depends on whether we're a leaf page--
	 * on a leaf page, we care only about keys.  On internal pages
	 * and LDUP pages, we want to check the order of all entries.
	 *
	 * Note that on IBTREE pages, we start with item 1, since item
	 * 0 doesn't get looked at by __bam_cmp.
	 */
	for (i = (TYPE(h) == P_IBTREE) ? 1 : 0; i < nentries;
	    i += (TYPE(h) == P_LBTREE) ? P_INDX : O_INDX) {
		/*
		 * Put key i-1, now in p2, into p1, by swapping DBTs and bufs.
		 */
		tmp = p1;
		p1 = p2;
		p2 = tmp;
		tmpbuf = buf1;
		buf1 = buf2;
		buf2 = tmpbuf;

		/*
		 * Get key i into p2.
		 */
		switch (TYPE(h)) {
		case P_IBTREE:
			bi = GET_BINTERNAL(dbp, h, i);
			if (B_TYPE(bi->type) == B_OVERFLOW) {
				bo = (BOVERFLOW *)(bi->data);
				goto overflow;
			} else {
				p2->data = bi->data;
				p2->size = bi->len;
			}

			/*
			 * The leftmost key on an internal page must be
			 * len 0, since it's just a placeholder and
			 * automatically sorts less than all keys.
			 *
			 * XXX
			 * This criterion does not currently hold!
			 * See todo list item #1686.  Meanwhile, it's harmless
			 * to just not check for it.
			 */
#if 0