From 08e23fb03ccfe12f492c8a354f0dd63fda6e3ac4 Mon Sep 17 00:00:00 2001
From: Tom Yu <tlyu@mit.edu>
Date: Fri, 1 Feb 2008 01:23:12 +0000
Subject: [PATCH] pull up r20214 from trunk

 r20214@cathode-dark-space:  tlyu | 2008-01-31 20:03:11 -0500
 ticket: new
 target_version: 1.6.4
 tags: pullup
 subject: libdb btree page split on zero index corrupts db
 component: krb5-kdc

 Splitting a btree page on index 0 can corrupt the database if the key
 length plus data length is exactly a certain value.  This certain size
 causes the item to get the left page to itself, and causes the right
 page to contain an erroneous additional index "hole" having an
 uninitialized value.  This bug may be one of the remaining causes of
 unexplained database corruption reported over the years.  Shawn Emery
 provided useful data from actual instances of this corruption.

 Add a test case for this bug.  (Raw libdb test rather than kdb; the
 latter would be much harder.)


ticket: 5880
version_fixed: 1.6.4

git-svn-id: svn://anonsvn.mit.edu/krb5/branches/krb5-1-6@20215 dc483132-0cff-0310-8789-dd5450dbe970
---
 src/plugins/kdb/db2/libdb2/btree/bt_split.c |  4 +-
 src/plugins/kdb/db2/libdb2/test/run.test    | 54 ++++++++++++++++++++-
 2 files changed, 54 insertions(+), 4 deletions(-)

diff --git a/src/plugins/kdb/db2/libdb2/btree/bt_split.c b/src/plugins/kdb/db2/libdb2/btree/bt_split.c
index 62ec823a1..9b2708e76 100644
--- a/src/plugins/kdb/db2/libdb2/btree/bt_split.c
+++ b/src/plugins/kdb/db2/libdb2/btree/bt_split.c
@@ -727,7 +727,7 @@ bt_psplit(t, h, l, r, pskip, ilen)
 	 * the right page.
 	 */
 	if (skip <= off) {
-		skip = 0;
+		skip = (indx_t)-1;
 		rval = l;
 	} else {
 		rval = r;
@@ -737,7 +737,7 @@ bt_psplit(t, h, l, r, pskip, ilen)
 	for (off = 0; nxt < top; ++off) {
 		if (skip == nxt) {
 			++off;
-			skip = 0;
+			skip = (indx_t)-1;
 		}
 		switch (h->flags & P_TYPE) {
 		case P_BINTERNAL:
diff --git a/src/plugins/kdb/db2/libdb2/test/run.test b/src/plugins/kdb/db2/libdb2/test/run.test
index 48c3a63d0..377d6f794 100644
--- a/src/plugins/kdb/db2/libdb2/test/run.test
+++ b/src/plugins/kdb/db2/libdb2/test/run.test
@@ -34,7 +34,7 @@ main()
 	bindir=/bin/.
 
 	if [ $# -eq 0 ]; then
-		for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20; do
+		for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20 40; do
 			test$t
 		done
 	else
@@ -45,7 +45,7 @@ main()
 			[0-9]*)
 				test$1;;
 			btree)
-				for t in 1 2 3 7 8 9 10 12 13; do
+				for t in 1 2 3 7 8 9 10 12 13 40; do
 					test$t
 				done;;
 			hash)
@@ -743,4 +743,54 @@ bsize=$bsize ffactor=$ffactor nelem=25000 cachesize=65536 failed"
 	done
 }
 
+# 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.
+test40 () {
+	echo "Test 40: btree: page split on index 0"
+	e=:
+	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 > $TMP2
+			sed -n 's/^d//p' $TMP2 | sort > $TMP1
+			$PROG -o $TMP3 -i psize=$psize btree $TMP2
+			if (cmp -s $TMP1 $TMP3); then :
+			else
+				echo "test40: btree: page size $psize, \
+keylen+datalen=$kdsize failed"
+				e='exit 1'
+			fi
+		done
+	done
+	$e
+}
+
 main $*
-- 
2.26.2