bt_verify.c

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

		/*
		 * 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
			if (i == 0 && bi->len != 0) {
				isbad = 1;
				EPRINT((dbp->dbenv,
		"Page %lu: lowest key on internal page of nonzero length",
				    (u_long)pgno));
			}
#endif
			break;
		case P_LBTREE:
		case P_LDUP:
			bk = GET_BKEYDATA(dbp, h, i);
			if (B_TYPE(bk->type) == B_OVERFLOW) {
				bo = (BOVERFLOW *)bk;
				goto overflow;
			} else {
				p2->data = bk->data;
				p2->size = bk->len;
			}
			break;
		default:
			/*
			 * This means our caller screwed up and sent us
			 * an inappropriate page.
			 */
			TYPE_ERR_PRINT(dbp->dbenv,
			    "__bam_vrfy_itemorder", pgno, TYPE(h))
			DB_ASSERT(0);
			ret = EINVAL;
			goto err;
		}

		if (0) {
			/*
			 * If ovflok != 1, we can't safely go chasing
			 * overflow pages with the normal routines now;
			 * they might be unsafe or nonexistent.  Mark this
			 * page as incomplete and return.
			 *
			 * Note that we don't need to worry about freeing
			 * buffers, since they can't have been allocated
			 * if overflow items are unsafe.
			 */
overflow:		if (!ovflok) {
				F_SET(pip, VRFY_INCOMPLETE);
				goto err;
			}

			/*
			 * Overflow items are safe to chase.  Do so.
			 * Fetch the overflow item into p2->data,
			 * NULLing it or reallocing it as appropriate.
			 *
			 * (We set p2->data to buf2 before the call
			 * so we're sure to realloc if we can and if p2
			 * was just pointing at a non-overflow item.)
			 */
			p2->data = buf2;
			if ((ret = __db_goff(dbp,
			    p2, bo->tlen, bo->pgno, NULL, NULL)) != 0) {
				isbad = 1;
				EPRINT((dbp->dbenv,
			    "Page %lu: error %lu in fetching overflow item %lu",
				    (u_long)pgno, (u_long)ret, (u_long)i));
			}
			/* In case it got realloc'ed and thus changed. */
			buf2 = p2->data;
		}

		/* Compare with the last key. */
		if (p1->data != NULL && p2->data != NULL) {
			cmp = func(dbp, p1, p2);

			/* comparison succeeded */
			if (cmp > 0) {
				isbad = 1;
				EPRINT((dbp->dbenv,
				    "Page %lu: out-of-order key at entry %lu",
				    (u_long)pgno, (u_long)i));
				/* proceed */
			} else if (cmp == 0) {
				/*
				 * If they compared equally, this
				 * had better be a (sub)database with dups.
				 * Mark it so we can check during the
				 * structure check.
				 */
				if (pip != NULL)
					F_SET(pip, VRFY_HAS_DUPS);
				else if (hasdups == 0) {
					isbad = 1;
					EPRINT((dbp->dbenv,
	"Page %lu: database with no duplicates has duplicated keys",
					    (u_long)pgno));
				}

				/*
				 * If we're a btree leaf, check to see
				 * if the data items of these on-page dups are
				 * in sorted order.  If not, flag this, so
				 * that we can make sure during the
				 * structure checks that the DUPSORT flag
				 * is unset.
				 *
				 * At this point i points to a duplicate key.
				 * Compare the datum before it (same key)
				 * to the datum after it, i.e. i-1 to i+1.
				 */
				if (TYPE(h) == P_LBTREE) {
					/*
					 * Unsafe;  continue and we'll pick
					 * up the bogus nentries later.
					 */
					if (i + 1 >= (db_indx_t)nentries)
						continue;

					/*
					 * We don't bother with clever memory
					 * management with on-page dups,
					 * as it's only really a big win
					 * in the overflow case, and overflow
					 * dups are probably (?) rare.
					 */
					if (((ret = __bam_safe_getdata(dbp,
					    h, i - 1, ovflok, &dup_1,
					    &freedup_1)) != 0) ||
					    ((ret = __bam_safe_getdata(dbp,
					    h, i + 1, ovflok, &dup_2,
					    &freedup_2)) != 0))
						goto err;

					/*
					 * If either of the data are NULL,
					 * it's because they're overflows and
					 * it's not safe to chase them now.
					 * Mark an incomplete and return.
					 */
					if (dup_1.data == NULL ||
					    dup_2.data == NULL) {
						DB_ASSERT(!ovflok);
						F_SET(pip, VRFY_INCOMPLETE);
						goto err;
					}

					/*
					 * If the dups are out of order,
					 * flag this.  It's not an error
					 * until we do the structure check
					 * and see whether DUPSORT is set.
					 */
					if (dupfunc(dbp, &dup_1, &dup_2) > 0)
						F_SET(pip, VRFY_DUPS_UNSORTED);

					if (freedup_1)
						__os_ufree(dbp->dbenv,
						    dup_1.data);
					if (freedup_2)
						__os_ufree(dbp->dbenv,
						    dup_2.data);
				}
			}
		}
	}

err:	if (pip != NULL && ((t_ret =
	    __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0) && ret == 0)
		ret = t_ret;

	if (buf1 != NULL)
		__os_ufree(dbp->dbenv, buf1);
	if (buf2 != NULL)
		__os_ufree(dbp->dbenv, buf2);

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

/*
 * __bam_vrfy_structure --
 *	Verify the tree structure of a btree database (including the master
 *	database containing subdbs).
 *
 * PUBLIC: int __bam_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t,
 * PUBLIC:     u_int32_t));
 */
int
__bam_vrfy_structure(dbp, vdp, meta_pgno, flags)
	DB *dbp;
	VRFY_DBINFO *vdp;
	db_pgno_t meta_pgno;
	u_int32_t flags;
{
	DB *pgset;
	VRFY_PAGEINFO *mip, *rip;
	db_pgno_t root, p;
	int t_ret, ret;
	u_int32_t nrecs, level, relen, stflags;

	mip = rip = 0;
	pgset = vdp->pgset;

	if ((ret = __db_vrfy_getpageinfo(vdp, meta_pgno, &mip)) != 0)
		return (ret);

	if ((ret = __db_vrfy_pgset_get(pgset, meta_pgno, (int *)&p)) != 0)
		goto err;
	if (p != 0) {
		EPRINT((dbp->dbenv,
		    "Page %lu: btree metadata page observed twice",
		    (u_long)meta_pgno));
		ret = DB_VERIFY_BAD;
		goto err;
	}
	if ((ret = __db_vrfy_pgset_inc(pgset, meta_pgno)) != 0)
		goto err;

	root = mip->root;

	if (root == 0) {
		EPRINT((dbp->dbenv,
		    "Page %lu: btree metadata page has no root",
		    (u_long)meta_pgno));
		ret = DB_VERIFY_BAD;
		goto err;
	}

	if ((ret = __db_vrfy_getpageinfo(vdp, root, &rip)) != 0)
		goto err;

	switch (rip->type) {
	case P_IBTREE:
	case P_LBTREE:
		stflags = flags | ST_TOPLEVEL;
		if (F_ISSET(mip, VRFY_HAS_DUPS))
			stflags |= ST_DUPOK;
		if (F_ISSET(mip, VRFY_HAS_DUPSORT))
			stflags |= ST_DUPSORT;
		if (F_ISSET(mip, VRFY_HAS_RECNUMS))
			stflags |= ST_RECNUM;
		ret = __bam_vrfy_subtree(dbp,
		    vdp, root, NULL, NULL, stflags, NULL, NULL, NULL);
		break;
	case P_IRECNO:
	case P_LRECNO:
		stflags = flags | ST_RECNUM | ST_IS_RECNO | ST_TOPLEVEL;
		if (mip->re_len > 0)
			stflags |= ST_RELEN;
		if ((ret = __bam_vrfy_subtree(dbp, vdp,
		    root, NULL, NULL, stflags, &level, &nrecs, &relen)) != 0)
			goto err;
		/*
		 * Even if mip->re_len > 0, re_len may come back zero if the
		 * tree is empty.  It should be okay to just skip the check in
		 * this case, as if there are any non-deleted keys at all,
		 * that should never happen.
		 */
		if (mip->re_len > 0 && relen > 0 && mip->re_len != relen) {
			EPRINT((dbp->dbenv,
			    "Page %lu: recno database has bad re_len %lu",
			    (u_long)meta_pgno, (u_long)relen));
			ret = DB_VERIFY_BAD;
			goto err;
		}
		ret = 0;
		break;
	case P_LDUP:
		EPRINT((dbp->dbenv,
		    "Page %lu: duplicate tree referenced from metadata page",
		    (u_long)meta_pgno));
		ret = DB_VERIFY_BAD;
		break;
	default:
		EPRINT((dbp->dbenv,
	    "Page %lu: btree root of incorrect type %lu on metadata page",
		    (u_long)meta_pgno, (u_long)rip->type));
		ret = DB_VERIFY_BAD;
		break;
	}

err:	if (mip != NULL && ((t_ret =
	    __db_vrfy_putpageinfo(dbp->dbenv, vdp, mip)) != 0) && ret == 0)
		ret = t_ret;
	if (rip != NULL && ((t_ret =
	    __db_vrfy_putpageinfo(dbp->dbenv, vdp, rip)) != 0) && ret == 0)
		ret = t_ret;
	return (ret);
}

/*
 * __bam_vrfy_subtree--
 *	Verify a subtree (or entire) btree with specified root.
 *
 *	Note that this is public because it must be called to verify
 *	offpage dup trees, including from hash.
 *
 * PUBLIC: int __bam_vrfy_subtree __P((DB *, VRFY_DBINFO *, db_pgno_t, void *,
 * PUBLIC:     void *, u_int32_t, u_int32_t *, u_int32_t *, u_int32_t *));
 */
int
__bam_vrfy_subtree(dbp,
    vdp, pgno, l, r, flags, levelp, nrecsp, relenp)
	DB *dbp;
	VRFY_DBINFO *vdp;
	db_pgno_t pgno;
	void *l, *r;
	u_int32_t flags, *levelp, *nrecsp, *relenp;
{
	BINTERNAL *li, *ri, *lp, *rp;
	DB *pgset;
	DB_MPOOLFILE *mpf;
	DBC *cc;
	PAGE *h;
	VRFY_CHILDINFO *child;
	VRFY_PAGEINFO *pip;
	db_indx_t i;
	db_pgno_t next_pgno, prev_pgno;
	db_recno_t child_nrecs, nrecs;
	u_int32_t child_level, child_relen, level, relen, stflags;
	u_int8_t leaf_type;
	int (*func) __P((DB *, const DBT *, const DBT *));
	int isbad, p, ret, t_ret, toplevel;

	mpf = dbp->mpf;
	ret = isbad = 0;
	nrecs = 0;
	h = NULL;
	relen = 0;
	leaf_type = P_INVALID;
	next_pgno = prev_pgno = PGNO_INVALID;
	rp = (BINTERNAL *)r;
	lp = (BINTERNAL *)l;

	/* Provide feedback on our progress to the application. */
	if (!LF_ISSET(DB_SALVAGE))
		__db_vrfy_struct_feedback(dbp, vdp);

	if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
		return (ret);

	cc = NULL;
	level = pip->bt_level;

	toplevel = LF_ISSET(ST_TOPLEVEL) ? 1 : 0;
	LF_CLR(ST_TOPLEVEL);

	/*
	 * If this is the root, initialize the vdp's prev- and next-pgno
	 * accounting.
	 *
	 * For each leaf page we hit, we'll want to make sure that
	 * vdp->prev_pgno is the same as pip->prev_pgno and vdp->next_pgno is
	 * our page number.  Then, we'll set vdp->next_pgno to pip->next_pgno
	 * and vdp->prev_pgno to our page number, and the next leaf page in
	 * line should be able to do the same verification.
	 */
	if (toplevel) {
		/*
		 * Cache the values stored in the vdp so that if we're an
		 * auxiliary tree such as an off-page duplicate set, our
		 * caller's leaf page chain doesn't get lost.
		 */
		prev_pgno = vdp->prev_pgno;
		next_pgno = vdp->next_pgno;
		leaf_type = vdp->leaf_type;
		vdp->next_pgno = vdp->prev_pgno = PGNO_INVALID;
		vdp->leaf_type = P_INVALID;
	}

	/*
	 * We are recursively descending a btree, starting from the root
	 * and working our way out to the leaves.
	 *
	 * There are four cases we need to deal with:
	 *	1. pgno is a recno leaf page.  Any children are overflows.
	 *	2. pgno is a duplicate leaf page.  Any children
	 *	   are overflow pages;  traverse them, and then return
	 *	   level and nrecs.
	 *	3. pgno is an ordinary leaf page.  Check whether dups are
	 *	   allowed, and if so, traverse any off-page dups or
	 *	   overflows.  Then return nrecs and level.
	 *	4. pgno is a recno internal page.  Recursively check any
	 *	   child pages, making sure their levels are one lower
	 *	   and their nrecs sum to ours.
	 *	5. pgno is a btree internal page.  Same as #4, plus we
	 *	   must verify that for each pair of BINTERNAL entries
	 *	   N and N+1, the leftmost item on N's child sorts
	 *	   greater than N, and the rightmost item on N's child
	 *	   sorts less than N+1.
	 *
	 * Furthermore, in any sorted page type (P_LDUP, P_LBTREE, P_IBTREE),
	 * we need to verify the internal sort order is correct if,
	 * due to overflow items, we were not able to do so earlier.
	 */
	switch (pip->type) {
	case P_LRECNO:
	case P_LDUP:
	case P_LBTREE:
		/*
		 * Cases 1, 2 and 3.
		 *
		 * We're some sort of leaf page;  verify
		 * that our linked list of leaves is consistent.
		 */
		if (vdp->leaf_type == P_INVALID) {
			/*
			 * First leaf page.  Set the type that all its
			 * successors should be, and verify that our prev_pgno
			 * is PGNO_INVALID.
			 */
			vdp->leaf_type = pip->type;
			if (pip->prev_pgno != PGNO_INVALID)
				goto bad_prev;
		} else {
			/*
			 * Successor leaf page. Check our type, the previous
			 * page's next_pgno, and our prev_pgno.
			 */
			if (pip->type != vdp->leaf_type) {
				EPRINT((dbp->dbenv,
	"Page %lu: unexpected page type %lu found in leaf chain (expected %lu)",
				    (u_long)pip->pgno, (u_long)pip->type,
				    (u_long)vdp->leaf_type));
				isbad = 1;
			}
			if (pip->pgno != vdp->next_pgno) {
				EPRINT((dbp->dbenv,
	"Page %lu: incorrect next_pgno %lu found in leaf chain (should be %lu)",
				    (u_long)vdp->prev_pgno,
				    (u_long)vdp->next_pgno, (u_long)pip->pgno));
				isbad = 1;
			}
			if (pip->prev_pgno != vdp->prev_pgno) {
bad_prev:			EPRINT((dbp->dbenv,
	"Page %lu: incorrect prev_pgno %lu found in leaf chain (should be %lu)",
				    (u_long)pip->pgno, (u_long)pip->prev_pgno,
				    (u_long)vdp->prev_pgno));
				isbad = 1;
			}
		}
		vdp->prev_pgno = pip->pgno;
		vdp->next_pgno = pip->next_pgno;

		/*
		 * Overflow pages are common to all three leaf types;
		 * traverse the child list, looking for overflows.
		 */
		if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0)
			goto err;
		for (ret = __db_vrfy_ccset(cc, pgno, &child); ret == 0;
		    ret = __db_vrfy_ccnext(cc, &child))
			if (child->type == V_OVERFLOW &&
			    (ret = __db_vrfy_ovfl_structure(dbp, vdp,
			    child->pgno, child->tlen,
			    flags | ST_OVFL_LEAF)) != 0) {