From 85df09ef7fa81dc4db8490740cbf8e989204791c Mon Sep 17 00:00:00 2001
From: Tom Yu <tlyu@mit.edu>
Date: Fri, 1 Feb 2008 01:03:11 +0000
Subject: [PATCH] libdb btree page split on zero index corrupts db

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: new
target_version: 1.6.4
tags: pullup
component: krb5-kdc

git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@20214 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