Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/tests/lib/libc/db Add more of the torture tests from the mit...
details: https://anonhg.NetBSD.org/src/rev/8281c588b812
branches: trunk
changeset: 818084:8281c588b812
user: christos <christos%NetBSD.org@localhost>
date: Sat Sep 24 20:12:33 2016 +0000
description:
Add more of the torture tests from the mit kerberos tree.
diffstat:
tests/lib/libc/db/Makefile | 3 +-
tests/lib/libc/db/h_db.c | 61 +++++++-
tests/lib/libc/db/t_db.sh | 301 ++++++++++++++++++++++++++++++++++++++++++++-
3 files changed, 351 insertions(+), 14 deletions(-)
diffs (truncated from 504 to 300 lines):
diff -r ac232999d328 -r 8281c588b812 tests/lib/libc/db/Makefile
--- a/tests/lib/libc/db/Makefile Sat Sep 24 20:12:07 2016 +0000
+++ b/tests/lib/libc/db/Makefile Sat Sep 24 20:12:33 2016 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.3 2015/11/18 18:35:35 christos Exp $
+# $NetBSD: Makefile,v 1.4 2016/09/24 20:12:33 christos Exp $
.include <bsd.own.mk>
@@ -13,6 +13,7 @@
PROGS+= h_db
PROGS+= h_lfsr
+CPPFLAGS.h_db.c += -I${NETBSDSRCDIR}/lib/libc/db/btree
FILESDIR= ${TESTSDIR}
diff -r ac232999d328 -r 8281c588b812 tests/lib/libc/db/h_db.c
--- a/tests/lib/libc/db/h_db.c Sat Sep 24 20:12:07 2016 +0000
+++ b/tests/lib/libc/db/h_db.c Sat Sep 24 20:12:33 2016 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: h_db.c,v 1.1 2011/01/07 15:05:58 pgoyette Exp $ */
+/* $NetBSD: h_db.c,v 1.2 2016/09/24 20:12:33 christos Exp $ */
/*-
* Copyright (c) 1992, 1993, 1994
@@ -39,7 +39,7 @@
#if 0
static char sccsid[] = "@(#)dbtest.c 8.17 (Berkeley) 9/1/94";
#else
-__RCSID("$NetBSD: h_db.c,v 1.1 2011/01/07 15:05:58 pgoyette Exp $");
+__RCSID("$NetBSD: h_db.c,v 1.2 2016/09/24 20:12:33 christos Exp $");
#endif
#endif /* not lint */
@@ -57,12 +57,13 @@
#include <unistd.h>
#include <err.h>
#include <db.h>
+#include "btree.h"
enum S { COMMAND, COMPARE, GET, PUT, REMOVE, SEQ, SEQFLAG, KEY, DATA };
static void compare(DBT *, DBT *);
static DBTYPE dbtype(const char *);
-static void dump(DB *, int);
+static void dump(DB *, int, int);
static void get(DB *, DBT *);
static void getdata(DB *, DBT *, DBT *);
static void put(DB *, DBT *, DBT *);
@@ -73,6 +74,7 @@
static void seq(DB *, DBT *);
static u_int setflags(char *);
static void *setinfo(DBTYPE, char *);
+static void unlinkpg(DB *);
static void usage(void) __attribute__((__noreturn__));
static void *xcopy(void *, size_t);
static void chkcmd(enum S);
@@ -82,6 +84,7 @@
#ifdef STATISTICS
extern void __bt_stat(DB *);
#endif
+extern int __bt_relink(BTREE *, PAGE *);
static DBTYPE type; /* Database type. */
static void *infop; /* Iflags. */
@@ -315,7 +318,13 @@
}
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:
errx(1, "line %zu: %s: unknown command character",
@@ -483,17 +492,17 @@
}
static void
-dump(DB *dbp, int rev)
+dump(DB *dbp, int rev, int recurse)
{
DBT key, data;
int xflags, nflags;
if (rev) {
xflags = R_LAST;
- nflags = R_PREV;
+ nflags = recurse ? R_RPREV : R_PREV;
} else {
xflags = R_FIRST;
- nflags = R_NEXT;
+ nflags = recurse ? R_RNEXT : R_NEXT;
}
for (;; xflags = nflags)
switch (dbp->seq(dbp, &key, &data, xflags)) {
@@ -511,6 +520,40 @@
done: return;
}
+void
+unlinkpg(DB *dbp)
+{
+ BTREE *t = dbp->internal;
+ PAGE *h = NULL;
+ pgno_t pg;
+
+ for (pg = P_ROOT; pg < t->bt_mp->npages;
+ mpool_put(t->bt_mp, h, 0), pg++) {
+ if ((h = mpool_getf(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) {
+ errx(1, "%s: no appropriate page found", __func__);
+ 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);
+}
+
static u_int
setflags(char *s)
{
@@ -725,7 +768,7 @@
usage(void)
{
(void)fprintf(stderr,
- "Usage: %s [-l] [-f file] [-i info] [-o file] type script\n",
- getprogname());
+ "Usage: %s [-lu] [-f file] [-i info] [-o file] [-O file] "
+ "type script\n", getprogname());
exit(1);
}
diff -r ac232999d328 -r 8281c588b812 tests/lib/libc/db/t_db.sh
--- a/tests/lib/libc/db/t_db.sh Sat Sep 24 20:12:07 2016 +0000
+++ b/tests/lib/libc/db/t_db.sh Sat Sep 24 20:12:33 2016 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: t_db.sh,v 1.6 2015/11/18 18:35:35 christos Exp $
+# $NetBSD: t_db.sh,v 1.7 2016/09/24 20:12:33 christos Exp $
#
# Copyright (c) 2008 The NetBSD Foundation, Inc.
# All rights reserved.
@@ -540,6 +540,7 @@
h_repeated()
{
+ local type="$1"
TMPDIR="$(pwd)/db_dir"; export TMPDIR
mkdir ${TMPDIR}
@@ -558,7 +559,7 @@
}
}' >in
- $(prog_db) btree in
+ $(prog_db) $type in
}
atf_test_case repeated_btree
@@ -618,11 +619,10 @@
h_cursor_flags()
{
+ local type=$1
TMPDIR="$(pwd)/db_dir"; export TMPDIR
mkdir ${TMPDIR}
- type=$1
-
echo $SEVEN_SEVEN |
awk '{
for (i = 1; i <= 20; ++i)
@@ -758,6 +758,7 @@
echo p
echo k$i
echo d$i
+ echo S
echo g
echo k$i
done >in
@@ -924,6 +925,292 @@
done
}
+atf_test_case btree_weird_page_split
+btree_weird_page_split_head()
+{
+ atf_set "descr" \
+ "Test for a weird page split condition where an insertion " \
+ "into index 0 of a page that would cause the new item to " \
+ "be the only item on the left page results in index 0 of " \
+ "the right page being erroneously skipped; this only " \
+ "happens with one particular key+data length for each page size."
+}
+btree_weird_page_split_body()
+{
+ for psize in 512 1024 2048 4096 8192; do
+ echo " page size $psize"
+ kdsizes=`awk 'BEGIN {
+ psize = '$psize'; hsize = int(psize/2);
+ for (kdsize = hsize-40; kdsize <= hsize; kdsize++) {
+ print kdsize;
+ }
+ }' /dev/null`
+
+ # Use a series of keylen+datalen values in the right
+ # neighborhood to find the one that triggers the bug.
+ # We could compute the exact size that triggers the
+ # bug but this additional fuzz may be useful.
+
+ # Insert keys in reverse order to maximize the chances
+ # for a split on index 0.
+
+ for kdsize in $kdsizes; do
+ awk 'BEGIN {
+ kdsize = '$kdsize';
+ for (i = 8; i-- > 0; ) {
+ s = sprintf("a%03d:%09d", i, kdsize);
+ for (j = 0; j < kdsize-20; j++) {
+ s = s "x";
+ }
+ printf("p\nka%03d\nd%s\n", i, s);
+ }
+ print "o";
+ }' /dev/null > in
+ sed -n 's/^d//p' in | sort > exp
+ atf_check -o file:exp \
+ "$(prog_db)" -i psize=$psize btree in
+ done
+ done
+}
+
+# Extremely tricky test attempting to replicate some unusual database
+# corruption seen in the field: pieces of the database becoming
+# inaccessible to random access, sequential access, or both. The
+# hypothesis is that at least some of these are triggered by the bug
+# in page splits on index 0 with a particular exact keylen+datalen.
+# (See Test 40.) For psize=4096, this size is exactly 2024.
+
+# The order of operations here relies on very specific knowledge of
+# the internals of the btree access method in order to place records
+# at specific offsets in a page and to create certain keys on internal
+# pages. The to-be-split page immediately prior to the bug-triggering
+# split has the following properties:
+#
+# * is not the leftmost leaf page
+# * key on the parent page is compares less than the key of the item
+# on index 0
+# * triggering record's key also compares greater than the key on the
+# parent page
+
+# Additionally, we prime the mpool LRU chain so that the head page on
+# the chain has the following properties:
+#
+# * record at index 0 is located where it will not get overwritten by
+# items written to the right-hand page during the split
+# * key of the record at index 0 compares less than the key of the
+# bug-triggering record
+
+# If the page-split bug exists, this test appears to create a database
+# where some records are inaccessible to a search, but still remain in
+# the file and are accessible by sequential traversal. At least one
+# record gets duplicated out of sequence.
+
+atf_test_case btree_tricky_page_split
+btree_tricky_page_split_head()
+{
+ atf_set "descr" \
+ "btree: no unsearchables due to page split on index 0"
+}
+btree_tricky_page_split_body()
+{
+ list=`(for i in a b c d; do
+ for j in 990 998 999; do
+ echo g ${i}${j} 1024
+ done
+ done;
+ echo g y997 2014
+ for i in y z; do
+ for j in 998 999; do
Home |
Main Index |
Thread Index |
Old Index