The branch, v3-5-test has been updated
via 1f3ea87... tdb: rename 'struct list_struct' into 'struct tdb_record'
via d94a4d4... lib/tdb: make tdbtool use tdb_check() for "check" command
via 2e6f7df... lib/tdb: add tdb_check()
via 12da055... lib/tdb: add -t (always use transactions) option to
tdbtorture
via 2b13c21... lib/tdb: wean off TDB_ERRCODE.
via 9797336... lib/tdb: TDB_TRACE support (for developers)
from 129cd3b... s3:Makefile: add some explicit dependencies to libc
http://gitweb.samba.org/?p=samba.git;a=shortlog;h=v3-5-test
- Log -----------------------------------------------------------------
commit 1f3ea8778ae8ef7d3333accaf3f1950637d19c98
Author: Stefan Metzmacher <[email protected]>
Date: Fri Oct 23 13:51:03 2009 +0200
tdb: rename 'struct list_struct' into 'struct tdb_record'
metze
commit d94a4d44ea644c82925c5901af491a35f0ba611d
Author: Rusty Russell <[email protected]>
Date: Thu Oct 22 00:11:34 2009 +1030
lib/tdb: make tdbtool use tdb_check() for "check" command
Also, set logging function so we get more informative messages.
Signed-off-by: Rusty Russell <[email protected]>
commit 2e6f7dfa793e0a5c46397dc18f65974c77a73b23
Author: Rusty Russell <[email protected]>
Date: Thu Oct 22 00:10:34 2009 +1030
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 <[email protected]>
commit 12da0557bc3346972d65eaf05a0c80ce0884c4e0
Author: Rusty Russell <[email protected]>
Date: Thu Oct 22 00:10:54 2009 +1030
lib/tdb: add -t (always use transactions) option to tdbtorture
This means you can kill it at any time and expect no corruption.
Signed-off-by: Rusty Russell <[email protected]>
commit 2b13c2108f8b746dbe866fc14dd5e6045b0d12ea
Author: Rusty Russell <[email protected]>
Date: Thu Oct 22 00:09:43 2009 +1030
lib/tdb: wean off TDB_ERRCODE.
It was a regrettable hack which I used to reduce line count in tdb; in fact
it caused confusion as can be seen in this patch.
In particular, ecode now needs to be set before TDB_LOG anyway, and having
it exposed in
the header is useless (the struct tdb_context isn't defined, so it's doubly
useless).
Also, we should never set errno, as io.c was doing.
Signed-off-by: Rusty Russell <[email protected]>
commit 97973362b405e365b9249d95da02ebf3465bb4e1
Author: Rusty Russell <[email protected]>
Date: Tue Oct 20 12:19:41 2009 +1030
lib/tdb: TDB_TRACE support (for developers)
When TDB_TRACE is defined (in tdb_private.h), verbose tracing of tdb
operations is enabled.
This can be replayed using "replay_trace" from
http://ccan.ozlabs.org/info/tdb.
The majority of this patch comes from moving internal functions to
_<funcname> to
avoid double-tracing. There should be no additional overhead for the
normal (!TDB_TRACE)
case.
Note that the verbose traces compress really well with rzip.
Signed-off-by: Rusty Russell <[email protected]>
-----------------------------------------------------------------------
Summary of changes:
lib/tdb/common/check.c | 422 ++++++++++++++++++++++++++++++++++++++++
lib/tdb/common/dump.c | 4 +-
lib/tdb/common/freelist.c | 23 ++-
lib/tdb/common/freelistcheck.c | 8 +-
lib/tdb/common/io.c | 43 +++--
lib/tdb/common/lock.c | 64 +++++--
lib/tdb/common/open.c | 37 +++-
lib/tdb/common/tdb.c | 271 ++++++++++++++++++++++----
lib/tdb/common/tdb_private.h | 54 +++++-
lib/tdb/common/transaction.c | 70 ++++---
lib/tdb/common/traverse.c | 34 +++-
lib/tdb/config.mk | 2 +-
lib/tdb/configure.ac | 2 +-
lib/tdb/docs/README | 11 +
lib/tdb/docs/tracing.txt | 46 +++++
lib/tdb/include/tdb.h | 5 +-
lib/tdb/libtdb.m4 | 2 +-
lib/tdb/tdb.exports | 1 +
lib/tdb/tdb.signatures | 1 +
lib/tdb/tools/tdbtool.c | 44 +++--
lib/tdb/tools/tdbtorture.c | 41 +++--
source4/min_versions.m4 | 2 +-
22 files changed, 1012 insertions(+), 175 deletions(-)
create mode 100644 lib/tdb/common/check.c
create mode 100644 lib/tdb/docs/tracing.txt
Changeset truncated at 500 lines:
diff --git a/lib/tdb/common/check.c b/lib/tdb/common/check.c
new file mode 100644
index 0000000..4924734
--- /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 tdb_record *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 tdb_record *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 tdb_record *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 tdb_record 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/common/dump.c b/lib/tdb/common/dump.c
index d1c902d..bdcbfab 100644
--- a/lib/tdb/common/dump.c
+++ b/lib/tdb/common/dump.c
@@ -30,7 +30,7 @@
static tdb_off_t tdb_dump_record(struct tdb_context *tdb, int hash,
tdb_off_t offset)
{
- struct list_struct rec;
+ struct tdb_record rec;
tdb_off_t tailer_ofs, tailer;
if (tdb->methods->tdb_read(tdb, offset, (char *)&rec,
@@ -95,7 +95,7 @@ int tdb_printfreelist(struct tdb_context *tdb)
int ret;
long total_free = 0;
tdb_off_t offset, rec_ptr;
- struct list_struct rec;
+ struct tdb_record rec;
if ((ret = tdb_lock(tdb, -1, F_WRLCK)) != 0)
return ret;
diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 3bc3965..8113b54 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -34,7 +34,7 @@
#define USE_RIGHT_MERGES 0
/* read a freelist record and check for simple errors */
-int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct
list_struct *rec)
+int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct
tdb_record *rec)
{
if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
return -1;
@@ -54,7 +54,7 @@ int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off,
struct list_struct
tdb->ecode = TDB_ERR_CORRUPT;
TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read bad magic
0x%x at offset=%d\n",
rec->magic, off));
- return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+ return -1;
}
if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
return -1;
@@ -78,15 +78,16 @@ static int remove_from_freelist(struct tdb_context *tdb,
tdb_off_t off, tdb_off_
/* Follow chain (next offset is at start of record) */
last_ptr = i;
}
+ tdb->ecode = TDB_ERR_CORRUPT;
TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at
off=%d\n", off));
- return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+ return -1;
}
#endif
/* update a record tailer (must hold allocation lock) */
static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
- const struct list_struct *rec)
+ const struct tdb_record *rec)
{
tdb_off_t totalsize;
@@ -98,7 +99,7 @@ static int update_tailer(struct tdb_context *tdb, tdb_off_t
offset,
/* Add an element into the freelist. Merge adjacent records if
neccessary. */
-int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct
*rec)
+int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
{
/* Allocation and tailer lock */
if (tdb_lock(tdb, -1, F_WRLCK) != 0)
--
Samba Shared Repository
