krb5 commit: Add bttest unlink page command
Tom Yu
tlyu at mit.edu
Tue Aug 16 21:46:17 EDT 2016
https://github.com/krb5/krb5/commit/f7e4078de12cb77fa55e3f6aaa8137c1ced2e796
commit f7e4078de12cb77fa55e3f6aaa8137c1ced2e796
Author: Tom Yu <tlyu at mit.edu>
Date: Mon Aug 8 08:50:40 2016 -0400
Add bttest unlink page command
To enable testing of recursive btree traversal, add an unlink page
command to the bttest program (used for debugging the libdb2 btree
back end). This new bttest command can unlink a specified page
number, or it can search for and unlink a page that has both a left
and a right sibling. (The user can specify whether to find an
internal page or a leaf page.)
This unlinking makes the page inaccessible to conventional sequential
traversal, simulating some btree corruption that has been seen in the
field.
ticket: 8476
src/plugins/kdb/db2/libdb2/btree/bt_delete.c | 3 +-
src/plugins/kdb/db2/libdb2/btree/extern.h | 8 +-
src/plugins/kdb/db2/libdb2/libdb.exports | 1 +
src/plugins/kdb/db2/libdb2/test/btree.tests/main.c | 88 ++++++++++++++++++++
4 files changed, 94 insertions(+), 6 deletions(-)
diff --git a/src/plugins/kdb/db2/libdb2/btree/bt_delete.c b/src/plugins/kdb/db2/libdb2/btree/bt_delete.c
index 4133aa3..b2f3a75 100644
--- a/src/plugins/kdb/db2/libdb2/btree/bt_delete.c
+++ b/src/plugins/kdb/db2/libdb2/btree/bt_delete.c
@@ -50,7 +50,6 @@ static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
static int __bt_bdelete __P((BTREE *, const DBT *));
static int __bt_curdel __P((BTREE *, const DBT *, PAGE *, u_int));
static int __bt_pdelete __P((BTREE *, PAGE *));
-static int __bt_relink __P((BTREE *, PAGE *));
static int __bt_stkacq __P((BTREE *, PAGE **, CURSOR *));
/*
@@ -634,7 +633,7 @@ dup2: c->pg.pgno = e.page->pgno;
* t: tree
* h: page to be deleted
*/
-static int
+int
__bt_relink(t, h)
BTREE *t;
PAGE *h;
diff --git a/src/plugins/kdb/db2/libdb2/btree/extern.h b/src/plugins/kdb/db2/libdb2/btree/extern.h
index c29b084..9f4082a 100644
--- a/src/plugins/kdb/db2/libdb2/btree/extern.h
+++ b/src/plugins/kdb/db2/libdb2/btree/extern.h
@@ -62,6 +62,7 @@
#define __bt_dpage __kdb2_bt_dpage
#define __bt_dump __kdb2_bt_dump
#define __bt_stat __kdb2_bt_stat
+#define __bt_relink __kdb2_bt_relink
int __bt_close __P((DB *));
int __bt_cmp __P((BTREE *, const DBT *, EPG *));
@@ -90,12 +91,11 @@ int __ovfl_delete __P((BTREE *, void *));
int __ovfl_get __P((BTREE *, void *, size_t *, void **, size_t *));
int __ovfl_put __P((BTREE *, const DBT *, db_pgno_t *));
-#ifdef DEBUG
int __bt_dnpage __P((DB *, db_pgno_t));
int __bt_dpage __P((DB *, PAGE *));
int __bt_dmpage __P((PAGE *));
int __bt_dump __P((DB *));
-#endif
-#ifdef STATISTICS
+
int __bt_stat __P((DB *));
-#endif
+
+int __bt_relink __P((BTREE *, PAGE *));
diff --git a/src/plugins/kdb/db2/libdb2/libdb.exports b/src/plugins/kdb/db2/libdb2/libdb.exports
index 7828da1..0c16891 100644
--- a/src/plugins/kdb/db2/libdb2/libdb.exports
+++ b/src/plugins/kdb/db2/libdb2/libdb.exports
@@ -24,6 +24,7 @@ __kdb2_bt_open
__kdb2_bt_pgin
__kdb2_bt_pgout
__kdb2_bt_put
+__kdb2_bt_relink
__kdb2_bt_ret
__kdb2_bt_search
__kdb2_bt_seq
diff --git a/src/plugins/kdb/db2/libdb2/test/btree.tests/main.c b/src/plugins/kdb/db2/libdb2/test/btree.tests/main.c
index 33de7a2..8281d0e 100644
--- a/src/plugins/kdb/db2/libdb2/test/btree.tests/main.c
+++ b/src/plugins/kdb/db2/libdb2/test/btree.tests/main.c
@@ -33,6 +33,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(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)main.c 8.1 (Berkeley) 6/4/93";
@@ -98,6 +127,7 @@ void rnext __P((DB *, char **));
void rprev __P((DB *, char **));
void usage __P((void));
void user __P((DB *));
+void unlinkpg __P((DB *, char **));
cmd_table commands[] = {
"?", 0, 0, help, "help", NULL,
@@ -138,6 +168,8 @@ cmd_table commands[] = {
#ifdef DEBUG
"sh", 1, 0, show, "show page", "dump a page",
#endif
+ "u", 1, 0, unlinkpg, "unlink pgno|internal|leaf", "unlink a page",
+
{ NULL },
};
@@ -883,3 +915,59 @@ usage()
progname);
exit (1);
}
+
+/* Find a candidate page to unlink. */
+static PAGE *
+candidatepg(BTREE *t, char *arg)
+{
+ PAGE *h = NULL;
+ db_pgno_t pg;
+ u_int32_t sflags;
+
+ if (arg[0] == 'i')
+ sflags = P_BINTERNAL | P_RINTERNAL;
+ if (arg[0] == 'l')
+ sflags = P_BLEAF | P_RLEAF;
+ 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)
+ return h;
+ /* Look for a nonempty page of the correct
+ * type that has both left and right siblings. */
+ if (h->prevpg == P_INVALID || h->nextpg == P_INVALID)
+ continue;
+ if ((h->flags & sflags) && NEXTINDEX(h) != 0)
+ break;
+ }
+ if (pg == t->bt_mp->npages)
+ h = NULL;
+ return h;
+}
+
+void
+unlinkpg(DB *db, char **argv)
+{
+ BTREE *t = db->internal;
+ PAGE *h = NULL;
+ db_pgno_t pg;
+
+ pg = atoi(argv[1]);
+ if (pg == 0)
+ h = candidatepg(t, argv[1]);
+ else
+ h = mpool_get(t->bt_mp, pg, 0);
+
+ if (h == NULL) {
+ fprintf(stderr, "unable to find appropriate page to unlink\n");
+ return;
+ }
+ printf("chain %d <- %d -> %d\n", h->prevpg, h->pgno, h->nextpg);
+ 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);
+}
More information about the cvs-krb5
mailing list