krb5 commit: Recursive btree traversal test case
Tom Yu
tlyu at mit.edu
Tue Aug 16 21:46:18 EDT 2016
https://github.com/krb5/krb5/commit/b88630244995b5a8c7aee29240ced957cf8d7fdb
commit b88630244995b5a8c7aee29240ced957cf8d7fdb
Author: Tom Yu <tlyu at mit.edu>
Date: Mon Aug 8 21:46:16 2016 -0400
Recursive btree traversal test case
Add an unlink page command to the dbtest program. This dbtest command
finds a page that has both a left and a right neighbor and unlinks it,
making it inaccessible to conventional sequential traversal. This
simulates some btree corruption that has been seen in the field.
Unlike the bttest command, the dbtest unlink command always searches
for a leaf page with both a left and a right sibling, and doesn't
allow the user to specify internal pages or a specific page number.
Add a new dbtest command to recursively dump a btree database.
Add a new test case to run.test that uses these new commands to verify
the correct functioning of the recursive btree traversal options.
ticket: 8476
src/plugins/kdb/db2/libdb2/test/dbtest.c | 84 +++++++++++++++++++++++++++---
src/plugins/kdb/db2/libdb2/test/run.test | 43 ++++++++++++++-
2 files changed, 118 insertions(+), 9 deletions(-)
diff --git a/src/plugins/kdb/db2/libdb2/test/dbtest.c b/src/plugins/kdb/db2/libdb2/test/dbtest.c
index 028bf66..ddb1ab2 100644
--- a/src/plugins/kdb/db2/libdb2/test/dbtest.c
+++ b/src/plugins/kdb/db2/libdb2/test/dbtest.c
@@ -30,6 +30,35 @@
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
+/*
+ * Copyright (C) 2016 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
#if !defined(lint) && defined(LIBC_SCCS)
static char copyright[] =
@@ -54,9 +83,7 @@ static char sccsid[] = "@(#)dbtest.c 8.17 (Berkeley) 9/1/94";
#include <unistd.h>
#include "db-int.h"
-#ifdef STATISTICS
#include "btree.h"
-#endif
enum S { COMMAND, COMPARE, GET, PUT, REMOVE, SEQ, SEQFLAG, KEY, DATA };
@@ -68,7 +95,7 @@ enum S { COMMAND, COMPARE, GET, PUT, REMOVE, SEQ, SEQFLAG, KEY, DATA };
void compare __P((DBT *, DBT *));
DBTYPE dbtype __P((char *));
-void dump __P((DB *, int));
+void dump __P((DB *, int, int));
void err __P((const char *, ...)) ATTR ((__format__(__printf__,1,2))) ATTR ((__noreturn__));
void get __P((DB *, DBT *));
void getdata __P((DB *, DBT *, DBT *));
@@ -80,6 +107,7 @@ void *rfile __P((char *, size_t *));
void seq __P((DB *, DBT *));
u_int setflags __P((char *));
void *setinfo __P((DBTYPE, char *));
+void unlinkpg __P((DB *));
void usage __P((void));
void *xmalloc __P((char *, size_t));
@@ -322,7 +350,13 @@ lkey: switch (command) {
}
break;
case 'o':
- dump(dbp, p[1] == 'r');
+ dump(dbp, p[1] == 'r', 0);
+ break;
+ case 'O':
+ dump(dbp, p[1] == 'r', 1);
+ break;
+ case 'u':
+ unlinkpg(dbp);
break;
default:
err("line %lu: %s: unknown command character",
@@ -517,19 +551,20 @@ seq(dbp, kp)
}
void
-dump(dbp, rev)
+dump(dbp, rev, recurse)
DB *dbp;
int rev;
+ int recurse;
{
DBT key, data;
int lflags, nflags;
if (rev) {
lflags = R_LAST;
- nflags = R_PREV;
+ nflags = recurse ? R_RPREV : R_PREV;
} else {
lflags = R_FIRST;
- nflags = R_NEXT;
+ nflags = recurse ? R_RNEXT : R_NEXT;
}
for (;; lflags = nflags)
switch (dbp->seq(dbp, &key, &data, lflags)) {
@@ -552,6 +587,41 @@ dump(dbp, rev)
done: return;
}
+void
+unlinkpg(dbp)
+ DB *dbp;
+{
+ BTREE *t = dbp->internal;
+ PAGE *h = NULL;
+ db_pgno_t pg;
+
+ for (pg = P_ROOT; pg < t->bt_mp->npages;
+ mpool_put(t->bt_mp, h, 0), pg++) {
+ if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
+ break;
+ /* Look for a nonempty leaf page that has both left
+ * and right siblings. */
+ if (h->prevpg == P_INVALID || h->nextpg == P_INVALID)
+ continue;
+ if (NEXTINDEX(h) == 0)
+ continue;
+ if ((h->flags & (P_BLEAF | P_RLEAF)))
+ break;
+ }
+ if (h == NULL || pg == t->bt_mp->npages) {
+ fprintf(stderr, "unlinkpg: no appropriate page found\n");
+ return;
+ }
+ if (__bt_relink(t, h) != 0) {
+ perror("unlinkpg");
+ goto cleanup;
+ }
+ h->prevpg = P_INVALID;
+ h->nextpg = P_INVALID;
+cleanup:
+ mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+}
+
u_int
setflags(s)
char *s;
diff --git a/src/plugins/kdb/db2/libdb2/test/run.test b/src/plugins/kdb/db2/libdb2/test/run.test
index d99b42d..c43992c 100644
--- a/src/plugins/kdb/db2/libdb2/test/run.test
+++ b/src/plugins/kdb/db2/libdb2/test/run.test
@@ -36,7 +36,7 @@ main()
find $bindir -type f -exec test -r {} \; -print | head -100 > $BINFILES
if [ $# -eq 0 ]; then
- for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20 40 41; do
+ for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20 40 41 50; do
test$t
done
else
@@ -47,7 +47,7 @@ main()
[0-9]*)
test$1;;
btree)
- for t in 1 2 3 7 8 9 10 12 13 40 41; do
+ for t in 1 2 3 7 8 9 10 12 13 40 41 50; do
test$t
done;;
hash)
@@ -915,4 +915,43 @@ EOF
fi
}
+# Test for recursive traversal successfully retrieving records that
+# are inaccessible to normal sequential (sibling-link) traversal.
+# This works by unlinking a few leaf pages but leaving their parent
+# links intact. To verify that the unlink actually makes records
+# inaccessible, the test first uses "o" to do a normal sequential
+# traversal, followed by "O" to do a recursive traversal.
+test50 () {
+ echo "Test 50: btree: recursive traversal"
+ fill="abcdefghijklmnopqrstuvwxyzy"
+ script='{
+ for (i = 0; i < 20000; i++) {
+ printf("p\nkAA%05d\nd%05d%s\n", i, i, $0);
+ }
+ print "u";
+ print "u";
+ print "u";
+ print "u";
+ }'
+ (echo $fill | awk "$script"; echo o) > $TMP2
+ echo $fill |
+ awk '{
+ for (i = 0; i < 20000; i++) {
+ printf("%05d%s\n", i, $0);
+ }
+ }' > $TMP1
+ $PROG -o $TMP3 -i psize=512 btree $TMP2
+ if (cmp -s $TMP1 $TMP3); then
+ echo "test50: btree: unexpected success after unlinking pages"
+ exit 1
+ fi
+ (echo $fill | awk "$script"; echo O) > $TMP2
+ $PROG -o $TMP3 -i psize=512 btree $TMP2
+ if (cmp -s $TMP1 $TMP3); then :
+ else
+ echo "test50: btree: failed"
+ exit 1
+ fi
+}
+
main $*
More information about the cvs-krb5
mailing list