r19960: Add code to check for loops in the free list.

Should help us validate tdb's against corruption.
Jeremy.
(This used to be commit bd0710fa09799cb496b1f9f365c57c3b542445f3)

5 files changed, 119 insertions, 4 deletions

diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c
index 9d1ae59801..0efe47f879 100644
--- a/source4/lib/tdb/common/freelist.c
+++ b/source4/lib/tdb/common/freelist.c
@@ -29,7 +29,7 @@
 #include "tdb_private.h"
 
 /* read a freelist record and check for simple errors */
-static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec)
+int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec)
 {
 	if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
 		return -1;
diff --git a/source4/lib/tdb/common/freelistcheck.c b/source4/lib/tdb/common/freelistcheck.c
new file mode 100644
index 0000000000..3f79a016b8
--- /dev/null
+++ b/source4/lib/tdb/common/freelistcheck.c
@@ -0,0 +1,108 @@
+/*
+   Unix SMB/CIFS implementation.
+
+   trivial database library
+
+   Copyright (C) Jeremy Allison                    2006
+
+     ** NOTE! The following LGPL license applies to the tdb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+#include "tdb_private.h"
+
+/* Check the freelist is good and contains no loops.
+   Very memory intensive - only do this as a consistency
+   checker. Heh heh - uses an in memory tdb as the storage
+   for the "seen" record list. For some reason this strikes
+   me as extremely clever as I don't have to write another tree
+   data structure implementation :-).
+ */
+
+static int seen_insert(struct tdb_context *mem_tdb, tdb_off_t rec_ptr)
+{
+	TDB_DATA key, data;
+
+	memset(&data, '\0', sizeof(data));
+	key.dptr = (char *)&rec_ptr;
+	key.dsize = sizeof(rec_ptr);
+	return tdb_store(mem_tdb, key, data, TDB_INSERT);
+}
+
+int tdb_validate_freelist(struct tdb_context *tdb, int *pnum_entries)
+{
+	struct tdb_context *mem_tdb = NULL;
+	struct list_struct rec;
+	tdb_off_t rec_ptr, last_ptr;
+	int ret = -1;
+
+	*pnum_entries = 0;
+
+	mem_tdb = tdb_open("flval", tdb->header.hash_size,
+				TDB_INTERNAL, O_RDWR, 0600);
+	if (!mem_tdb) {
+		return -1;
+	}
+
+	if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
+		tdb_close(mem_tdb);
+		return 0;
+	}
+
+	last_ptr = FREELIST_TOP;
+
+	/* Store the FREELIST_TOP record. */
+	if (seen_insert(mem_tdb, last_ptr) == -1) {
+		ret = TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+		goto fail;
+	}
+
+	/* read in the freelist top */
+	if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1) {
+		goto fail;
+	}
+
+	while (rec_ptr) {
+
+		/* If we can't store this record (we've seen it
+		   before) then the free list has a loop and must
+		   be corrupt. */
+
+		if (seen_insert(mem_tdb, rec_ptr)) {
+			ret = TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+			goto fail;
+		}
+
+		if (rec_free_read(tdb, rec_ptr, &rec) == -1) {
+			goto fail;
+		}
+
+		/* move to the next record */
+		last_ptr = rec_ptr;
+		rec_ptr = rec.next;
+		*pnum_entries += 1;
+	}
+
+	ret = 0;
+
+  fail:
+
+	tdb_close(mem_tdb);
+	tdb_unlock(tdb, -1, F_WRLCK);
+	return ret;
+}
diff --git a/source4/lib/tdb/include/tdb.h b/source4/lib/tdb/include/tdb.h
index 4d29cece04..cbcaf9023c 100644
--- a/source4/lib/tdb/include/tdb.h
+++ b/source4/lib/tdb/include/tdb.h
@@ -136,6 +136,7 @@ int tdb_chainunlock_read(struct tdb_context *tdb, TDB_DATA key);
 /* Debug functions. Not used in production. */
 void tdb_dump_all(struct tdb_context *tdb);
 int tdb_printfreelist(struct tdb_context *tdb);
+int tdb_validate_freelist(struct tdb_context *tdb, int *pnum_entries);
 
 extern TDB_DATA tdb_null;
 
diff --git a/source4/lib/tdb/libtdb.m4 b/source4/lib/tdb/libtdb.m4
index 35bac96e02..fefa5912c2 100644
--- a/source4/lib/tdb/libtdb.m4
+++ b/source4/lib/tdb/libtdb.m4
@@ -13,8 +13,9 @@ if test x"$tdbdir" = "x"; then
    AC_MSG_ERROR([cannot find tdb source in $tdbpaths])
 fi
 TDBOBJ="common/tdb.o common/dump.o common/transaction.o common/error.o common/traverse.o"
-TDBOBJ="$TDBOBJ common/freelist.o common/io.o common/lock.o common/open.o"
+TDBOBJ="$TDBOBJ common/freelist.o common/freelistcheck.o common/io.o common/lock.o common/open.o"
 AC_SUBST(TDBOBJ)
+AC_SUBST(LIBREPLACEOBJ)
 
 AC_CHECK_FUNCS(mmap pread pwrite getpagesize utime)
 AC_CHECK_HEADERS(getopt.h sys/select.h sys/time.h)
diff --git a/source4/lib/tdb/tools/tdbtest.c b/source4/lib/tdb/tools/tdbtest.c
index c7a09789fe..1564a42bc4 100644
--- a/source4/lib/tdb/tools/tdbtest.c
+++ b/source4/lib/tdb/tools/tdbtest.c
@@ -219,6 +219,7 @@ static void merge_test(void)
 {
 	int i, seed=0;
 	int loops = 10000;
+	int num_entries;
 	char test_gdbm[] = "test.gdbm";
 
 	unlink("test.gdbm");
@@ -232,8 +233,6 @@ static void merge_test(void)
 		fatal("db open failed");
 	}
 
-	tdb_logging_function(db, tdb_log);
-	
 #if 1
 	srand(seed);
 	_start_timer();
@@ -248,6 +247,12 @@ static void merge_test(void)
 	for (i=0;i<loops;i++) addrec_db();
 	printf("tdb got %.2f ops/sec\n", i/_end_timer());
 
+	if (tdb_validate_freelist(db, &num_entries) == -1) {
+		printf("tdb freelist is corrupt\n");
+	} else {
+		printf("tdb freelist is good (%d entries)\n", num_entries);
+	}
+
 	compare_db();
 
 	printf("traversed %d records\n", tdb_traverse(db, traverse_fn, NULL));