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