lib/tdb: add tdb_check()

ctdb wants a quick way to detect corrupt tdbs; particularly, tdbs with
loops in their hash chains.  tdb_check() provides this.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

8 files changed, 441 insertions, 3 deletions

diff --git a/lib/tdb/common/check.c b/lib/tdb/common/check.c
new file mode 100644
index 0000000000..94240bbed1
--- /dev/null
+++ b/lib/tdb/common/check.c
@@ -0,0 +1,422 @@
+ /*
+   Unix SMB/CIFS implementation.
+
+   trivial database library
+
+   Copyright (C) Rusty Russell		   2009
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+#include "tdb_private.h"
+
+/* Since we opened it, these shouldn't fail unless it's recent corruption. */
+static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
+{
+	struct tdb_header hdr;
+
+	if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), DOCONV()) == -1)
+		return false;
+	if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
+		goto corrupt;
+
+	CONVERT(hdr);
+	if (hdr.version != TDB_VERSION)
+		goto corrupt;
+
+	if (hdr.rwlocks != 0)
+		goto corrupt;
+
+	if (hdr.hash_size == 0)
+		goto corrupt;
+
+	if (hdr.hash_size != tdb->header.hash_size)
+		goto corrupt;
+
+	if (hdr.recovery_start != 0 &&
+	    hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
+		goto corrupt;
+
+	*recovery = hdr.recovery_start;
+	return true;
+
+corrupt:
+	tdb->ecode = TDB_ERR_CORRUPT;
+	TDB_LOG((tdb, TDB_DEBUG_ERROR, "Header is corrupt\n"));
+	return false;
+}
+
+/* Generic record header check. */
+static bool tdb_check_record(struct tdb_context *tdb,
+			     tdb_off_t off,
+			     const struct list_struct *rec)
+{
+	tdb_off_t tailer;
+
+	/* Check rec->next: 0 or points to record offset, aligned. */
+	if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->header.hash_size)){
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d too small next %d\n",
+			 off, rec->next));
+		goto corrupt;
+	}
+	if (rec->next + sizeof(*rec) < rec->next) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d too large next %d\n",
+			 off, rec->next));
+		goto corrupt;
+	}
+	if ((rec->next % TDB_ALIGNMENT) != 0) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d misaligned next %d\n",
+			 off, rec->next));
+		goto corrupt;
+	}
+	if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0))
+		goto corrupt;
+
+	/* Check rec_len: similar to rec->next, implies next record. */
+	if ((rec->rec_len % TDB_ALIGNMENT) != 0) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d misaligned length %d\n",
+			 off, rec->rec_len));
+		goto corrupt;
+	}
+	/* Must fit tailer. */
+	if (rec->rec_len < sizeof(tailer)) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d too short length %d\n",
+			 off, rec->rec_len));
+		goto corrupt;
+	}
+	/* OOB allows "right at the end" access, so this works for last rec. */
+	if (tdb->methods->tdb_oob(tdb, off+sizeof(*rec)+rec->rec_len, 0))
+		goto corrupt;
+
+	/* Check tailer. */
+	if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
+			 &tailer) == -1)
+		goto corrupt;
+	if (tailer != sizeof(*rec) + rec->rec_len) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d invalid tailer\n", off));
+		goto corrupt;
+	}
+
+	return true;
+
+corrupt:
+	tdb->ecode = TDB_ERR_CORRUPT;
+	return false;
+}
+
+/* Grab some bytes: may copy if can't use mmap.
+   Caller has already done bounds check. */
+static TDB_DATA get_bytes(struct tdb_context *tdb,
+			  tdb_off_t off, tdb_len_t len)
+{
+	TDB_DATA d;
+
+	d.dsize = len;
+
+	if (tdb->transaction == NULL && tdb->map_ptr != NULL)
+		d.dptr = (unsigned char *)tdb->map_ptr + off;
+	else
+		d.dptr = tdb_alloc_read(tdb, off, d.dsize);
+	return d;
+}
+
+/* Frees data if we're not able to simply use mmap. */
+static void put_bytes(struct tdb_context *tdb, TDB_DATA d)
+{
+	if (tdb->transaction == NULL && tdb->map_ptr != NULL)
+		return;
+	free(d.dptr);
+}
+
+/* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
+ * See: http://burtleburtle.net/bob/c/lookup3.c
+ */
+#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
+static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
+{
+	uint32_t a,b,c;
+
+	/* Set up the internal state */
+	a = b = c = 0xdeadbeef + *pc;
+	c += *pb;
+	a += key;
+	c ^= b; c -= rot(b,14);
+	a ^= c; a -= rot(c,11);
+	b ^= a; b -= rot(a,25);
+	c ^= b; c -= rot(b,16);
+	a ^= c; a -= rot(c,4);
+	b ^= a; b -= rot(a,14);
+	c ^= b; c -= rot(b,24);
+	*pc=c; *pb=b;
+}
+
+/*
+  We want to check that all free records are in the free list
+  (only once), and all free list entries are free records.  Similarly
+  for each hash chain of used records.
+
+  Doing that naively (without walking hash chains, since we want to be
+  linear) means keeping a list of records which have been seen in each
+  hash chain, and another of records pointed to (ie. next pointers
+  from records and the initial hash chain heads).  These two lists
+  should be equal.  This will take 8 bytes per record, and require
+  sorting at the end.
+
+  So instead, we record each offset in a bitmap such a way that
+  recording it twice will cancel out.  Since each offset should appear
+  exactly twice, the bitmap should be zero at the end.
+
+  The approach was inspired by Bloom Filters (see Wikipedia).  For
+  each value, we flip K bits in a bitmap of size N.  The number of
+  distinct arrangements is:
+
+	N! / (K! * (N-K)!)
+
+  Of course, not all arrangements are actually distinct, but testing
+  shows this formula to be close enough.
+
+  So, if K == 8 and N == 256, the probability of two things flipping the same
+  bits is 1 in 409,663,695,276,000.
+
+  Given that ldb uses a hash size of 10000, using 32 bytes per hash chain
+  (320k) seems reasonable.
+*/
+#define NUM_HASHES 8
+#define BITMAP_BITS 256
+
+static void bit_flip(unsigned char bits[], unsigned int idx)
+{
+	bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
+}
+
+/* We record offsets in a bitmap for the particular chain it should be in.  */
+static void record_offset(unsigned char bits[], tdb_off_t off)
+{
+	uint32_t h1 = off, h2 = 0;
+	unsigned int i;
+
+	/* We get two good hash values out of jhash2, so we use both.  Then
+	 * we keep going to produce further hash values. */
+	for (i = 0; i < NUM_HASHES / 2; i++) {
+		hash(off, &h1, &h2);
+		bit_flip(bits, h1 % BITMAP_BITS);
+		bit_flip(bits, h2 % BITMAP_BITS);
+		h2++;
+	}
+}
+
+/* Check that an in-use record is valid. */
+static bool tdb_check_used_record(struct tdb_context *tdb,
+				  tdb_off_t off,
+				  const struct list_struct *rec,
+				  unsigned char **hashes,
+				  int (*check)(TDB_DATA, TDB_DATA, void *),
+				  void *private_data)
+{
+	TDB_DATA key, data;
+
+	if (!tdb_check_record(tdb, off, rec))
+		return false;
+
+	/* key + data + tailer must fit in record */
+	if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d too short for contents\n", off));
+		return false;
+	}
+
+	key = get_bytes(tdb, off + sizeof(*rec), rec->key_len);
+	if (!key.dptr)
+		return false;
+
+	if (tdb->hash_fn(&key) != rec->full_hash) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Record offset %d has incorrect hash\n", off));
+		goto fail_put_key;
+	}
+
+	/* Mark this offset as a known value for this hash bucket. */
+	record_offset(hashes[BUCKET(rec->full_hash)+1], off);
+	/* And similarly if the next pointer is valid. */
+	if (rec->next)
+		record_offset(hashes[BUCKET(rec->full_hash)+1], rec->next);
+
+	/* If they supply a check function and this record isn't dead,
+	   get data and feed it. */
+	if (check && rec->magic != TDB_DEAD_MAGIC) {
+		data = get_bytes(tdb, off + sizeof(*rec) + rec->key_len,
+				 rec->data_len);
+		if (!data.dptr)
+			goto fail_put_key;
+
+		if (check(key, data, private_data) == -1)
+			goto fail_put_data;
+		put_bytes(tdb, data);
+	}
+
+	put_bytes(tdb, key);
+	return true;
+
+fail_put_data:
+	put_bytes(tdb, data);
+fail_put_key:
+	put_bytes(tdb, key);
+	return false;
+}
+
+/* Check that an unused record is valid. */
+static bool tdb_check_free_record(struct tdb_context *tdb,
+				  tdb_off_t off,
+				  const struct list_struct *rec,
+				  unsigned char **hashes)
+{
+	if (!tdb_check_record(tdb, off, rec))
+		return false;
+
+	/* Mark this offset as a known value for the free list. */
+	record_offset(hashes[0], off);
+	/* And similarly if the next pointer is valid. */
+	if (rec->next)
+		record_offset(hashes[0], rec->next);
+	return true;
+}
+
+int tdb_check(struct tdb_context *tdb,
+	      int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
+	      void *private_data)
+{
+	unsigned int h;
+	unsigned char **hashes;
+	tdb_off_t off, recovery_start;
+	struct list_struct rec;
+	bool found_recovery = false;
+
+	if (tdb_lockall(tdb) == -1)
+		return -1;
+
+	/* Make sure we know true size of the underlying file. */
+	tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
+
+	/* Header must be OK: also gets us the recovery ptr, if any. */
+	if (!tdb_check_header(tdb, &recovery_start))
+		goto unlock;
+
+	/* We should have the whole header, too. */
+	if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
+		tdb->ecode = TDB_ERR_CORRUPT;
+		TDB_LOG((tdb, TDB_DEBUG_ERROR, "File too short for hashes\n"));
+		goto unlock;
+	}
+
+	/* One big malloc: pointers then bit arrays. */
+	hashes = calloc(1, sizeof(hashes[0]) * (1+tdb->header.hash_size)
+			+ BITMAP_BITS / CHAR_BIT * (1+tdb->header.hash_size));
+	if (!hashes) {
+		tdb->ecode = TDB_ERR_OOM;
+		goto unlock;
+	}
+
+	/* Initialize pointers */
+	hashes[0] = (unsigned char *)(&hashes[1+tdb->header.hash_size]);
+	for (h = 1; h < 1+tdb->header.hash_size; h++)
+		hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
+
+	/* Freelist and hash headers are all in a row: read them. */
+	for (h = 0; h < 1+tdb->header.hash_size; h++) {
+		if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
+				 &off) == -1)
+			goto free;
+		if (off)
+			record_offset(hashes[h], off);
+	}
+
+	/* For each record, read it in and check it's ok. */
+	for (off = TDB_DATA_START(tdb->header.hash_size);
+	     off < tdb->map_size;
+	     off += sizeof(rec) + rec.rec_len) {
+		if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
+					   DOCONV()) == -1)
+			goto free;
+		switch (rec.magic) {
+		case TDB_MAGIC:
+		case TDB_DEAD_MAGIC:
+			if (!tdb_check_used_record(tdb, off, &rec, hashes,
+						   check, private_data))
+				goto free;
+			break;
+		case TDB_FREE_MAGIC:
+			if (!tdb_check_free_record(tdb, off, &rec, hashes))
+				goto free;
+			break;
+		case TDB_RECOVERY_MAGIC:
+		case 0: /* Used for invalid (or in-progress) recovery area. */
+			if (recovery_start != off) {
+				TDB_LOG((tdb, TDB_DEBUG_ERROR,
+					 "Unexpected recovery record at offset %d\n",
+					 off));
+				goto free;
+			}
+			found_recovery = true;
+			break;
+		default:
+			tdb->ecode = TDB_ERR_CORRUPT;
+			TDB_LOG((tdb, TDB_DEBUG_ERROR,
+				 "Bad magic 0x%x at offset %d\n",
+				 rec.magic, off));
+			goto free;
+		}
+	}
+
+	/* Now, hashes should all be empty: each record exists and is referred
+	 * to by one other. */
+	for (h = 0; h < 1+tdb->header.hash_size; h++) {
+		unsigned int i;
+		for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
+			if (hashes[h][i] != 0) {
+				tdb->ecode = TDB_ERR_CORRUPT;
+				TDB_LOG((tdb, TDB_DEBUG_ERROR,
+					 "Hashes do not match records\n"));
+				goto free;
+			}
+		}
+	}
+
+	/* We must have found recovery area if there was one. */
+	if (recovery_start != 0 && !found_recovery) {
+		TDB_LOG((tdb, TDB_DEBUG_ERROR,
+			 "Expected %s recovery area, got %s\n",
+			 recovery_start ? "a" : "no",
+			 found_recovery ? "one" : "none"));
+		goto free;
+	}
+
+	free(hashes);
+	tdb_unlockall(tdb);
+	return 0;
+
+free:
+	free(hashes);
+unlock:
+	tdb_unlockall(tdb);
+	return -1;
+}
diff --git a/lib/tdb/config.mk b/lib/tdb/config.mk
index 38b03b93b6..b2e322cebc 100644
--- a/lib/tdb/config.mk
+++ b/lib/tdb/config.mk
@@ -10,7 +10,7 @@ CFLAGS = -I$(tdbsrcdir)/include
 LIBTDB_OBJ_FILES = $(addprefix $(tdbsrcdir)/common/, \
 	tdb.o dump.o io.o lock.o \
 	open.o traverse.o freelist.o \
-	error.o transaction.o)
+	error.o transaction.o check.o)
 
 ################################################
 # Start BINARY tdbtool
diff --git a/lib/tdb/configure.ac b/lib/tdb/configure.ac
index 2b4d8de0c5..52ecff4bbb 100644
--- a/lib/tdb/configure.ac
+++ b/lib/tdb/configure.ac
@@ -2,7 +2,7 @@ AC_PREREQ(2.50)
 AC_DEFUN([SMB_MODULE_DEFAULT], [echo -n ""])
 AC_DEFUN([SMB_LIBRARY_ENABLE], [echo -n ""])
 AC_DEFUN([SMB_ENABLE], [echo -n ""])
-AC_INIT(tdb, 1.1.6)
+AC_INIT(tdb, 1.1.7)
 AC_CONFIG_SRCDIR([common/tdb.c])
 AC_CONFIG_HEADER(include/config.h)
 AC_LIBREPLACE_ALL_CHECKS
diff --git a/lib/tdb/docs/README b/lib/tdb/docs/README
index 454e4ba032..4eb809fdf4 100644
--- a/lib/tdb/docs/README
+++ b/lib/tdb/docs/README
@@ -244,3 +244,14 @@ int tdb_transaction_prepare_commit(TDB_CONTEXT *tdb)
    tdb_transaction_commit() or tdb_transaction_cancel(). Preparing
    allocates disk space for the pending updates, so a subsequent
    commit should succeed (barring any hardware failures).
+
+----------------------------------------------------------------------
+int tdb_check(TDB_CONTEXT *tdb,
+	      int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
+	      void *private_data);)
+
+   check the consistency of the database, calling back the check function
+   (if non-NULL) with each record.  If some consistency check fails, or
+   the supplied check function returns -1, tdb_check returns -1, otherwise
+   0.  Note that logging function (if set) will be called with additional
+   information on the corruption found.
diff --git a/lib/tdb/include/tdb.h b/lib/tdb/include/tdb.h
index c00b6cb33e..e849f20641 100644
--- a/lib/tdb/include/tdb.h
+++ b/lib/tdb/include/tdb.h
@@ -139,6 +139,9 @@ void tdb_add_flags(struct tdb_context *tdb, unsigned flag);
 void tdb_remove_flags(struct tdb_context *tdb, unsigned flag);
 void tdb_enable_seqnum(struct tdb_context *tdb);
 void tdb_increment_seqnum_nonblock(struct tdb_context *tdb);
+int tdb_check(struct tdb_context *tdb,
+	      int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
+	      void *private_data);
 
 /* Low level locking functions: use with care */
 int tdb_chainlock(struct tdb_context *tdb, TDB_DATA key);
diff --git a/lib/tdb/libtdb.m4 b/lib/tdb/libtdb.m4
index 8c84736304..feae1c2cc6 100644
--- a/lib/tdb/libtdb.m4
+++ b/lib/tdb/libtdb.m4
@@ -13,7 +13,7 @@ if test x"$tdbdir" = "x"; then
    AC_MSG_ERROR([cannot find tdb source in $tdbpaths])
 fi
 TDB_OBJ="common/tdb.o common/dump.o common/transaction.o common/error.o common/traverse.o"
-TDB_OBJ="$TDB_OBJ common/freelist.o common/freelistcheck.o common/io.o common/lock.o common/open.o"
+TDB_OBJ="$TDB_OBJ common/freelist.o common/freelistcheck.o common/io.o common/lock.o common/open.o common/check.o"
 AC_SUBST(TDB_OBJ)
 AC_SUBST(LIBREPLACEOBJ)
 
diff --git a/lib/tdb/tdb.exports b/lib/tdb/tdb.exports
index f3dcd1514b..cf287d8f32 100644
--- a/lib/tdb/tdb.exports
+++ b/lib/tdb/tdb.exports
@@ -9,6 +9,7 @@
            tdb_chainlock_unmark;
            tdb_chainunlock;
            tdb_chainunlock_read;
+           tdb_check;
            tdb_close;
            tdb_delete;
            tdb_dump_all;
diff --git a/lib/tdb/tdb.signatures b/lib/tdb/tdb.signatures
index 140e35a62f..93edb071be 100644
--- a/lib/tdb/tdb.signatures
+++ b/lib/tdb/tdb.signatures
@@ -56,4 +56,5 @@ void tdb_remove_flags (struct tdb_context *, unsigned int);
 void tdb_setalarm_sigptr (struct tdb_context *, volatile sig_atomic_t *);
 void tdb_set_logging_function (struct tdb_context *, const struct tdb_logging_context *);
 void tdb_set_max_dead (struct tdb_context *, int);
+int tdb_check (struct tdb_context *, int (*)(TDB_DATA, TDB_DATA, void *), void *);
 TDB_DATA tdb_null;