samba-cvs.cvs
[Top] [All Lists]

[SCM] Samba Shared Repository - branch master updated

Subject: [SCM] Samba Shared Repository - branch master updated
From: Rusty Russell
Date: Wed, 21 Oct 2009 08:44:38 -0500 CDT
The branch, master has been updated
       via  0944931... lib/tdb: make tdbtool use tdb_check() for "check" command
       via  022b4d4... lib/tdb: add tdb_check()
       via  0fc6800... lib/tdb: add -t (always use transactions) option to 
tdbtorture
       via  b77f41d... lib/tdb: wean off TDB_ERRCODE.
      from  7030043... lib/tdb: TDB_TRACE support (for developers)

http://gitweb.samba.org/?p=samba.git;a=shortlog;h=master


- Log -----------------------------------------------------------------
commit 094493115971cf3d5a3138ff10ebe02335824723
Author: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
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 <rusty@xxxxxxxxxxxxxxx>

commit 022b4d4aa6861c1e3e6d76484d92555221cb6d14
Author: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
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 <rusty@xxxxxxxxxxxxxxx>

commit 0fc6800005ffb532a5e5699c97f13f1de138d51f
Author: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
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 <rusty@xxxxxxxxxxxxxxx>

commit b77f41d58b05101e02d8ac0e54cb0e30807d89c2
Author: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
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 <rusty@xxxxxxxxxxxxxxx>

-----------------------------------------------------------------------

Summary of changes:
 lib/tdb/common/check.c         |  422 ++++++++++++++++++++++++++++++++++++++++
 lib/tdb/common/freelist.c      |    5 +-
 lib/tdb/common/freelistcheck.c |    6 +-
 lib/tdb/common/io.c            |   35 ++--
 lib/tdb/common/lock.c          |   30 ++-
 lib/tdb/common/open.c          |    6 +-
 lib/tdb/common/tdb.c           |    9 +-
 lib/tdb/common/transaction.c   |    3 +-
 lib/tdb/common/traverse.c      |    3 +-
 lib/tdb/config.mk              |    2 +-
 lib/tdb/configure.ac           |    2 +-
 lib/tdb/docs/README            |   11 +
 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 +-
 19 files changed, 560 insertions(+), 70 deletions(-)
 create mode 100644 lib/tdb/common/check.c


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..94240bb
--- /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/common/freelist.c b/lib/tdb/common/freelist.c
index 3bc3965..dedf78c 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -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,8 +78,9 @@ 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
 
diff --git a/lib/tdb/common/freelistcheck.c b/lib/tdb/common/freelistcheck.c
index efc050d..972b2a4 100644
--- a/lib/tdb/common/freelistcheck.c
+++ b/lib/tdb/common/freelistcheck.c
@@ -67,7 +67,8 @@ int tdb_validate_freelist(struct tdb_context *tdb, int 
*pnum_entries)
 
        /* Store the FREELIST_TOP record. */
        if (seen_insert(mem_tdb, last_ptr) == -1) {
-               ret = TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+               tdb->ecode = TDB_ERR_CORRUPT;
+               ret = -1;
                goto fail;
        }
 
@@ -83,7 +84,8 @@ int tdb_validate_freelist(struct tdb_context *tdb, int 
*pnum_entries)
                   be corrupt. */
 
                if (seen_insert(mem_tdb, rec_ptr)) {
-                       ret = TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
+                       tdb->ecode = TDB_ERR_CORRUPT;
+                       ret = -1;
                        goto fail;
                }
 
diff --git a/lib/tdb/common/io.c b/lib/tdb/common/io.c
index a0b3a3f..cc52bcf 100644
--- a/lib/tdb/common/io.c
+++ b/lib/tdb/common/io.c
@@ -45,11 +45,12 @@ static int tdb_oob(struct tdb_context *tdb, tdb_off_t len, 
int probe)
                        TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_oob len %d beyond 
internal malloc size %d\n",
                                 (int)len, (int)tdb->map_size));
                }
-               return TDB_ERRCODE(TDB_ERR_IO, -1);
+               return -1;
        }
 
        if (fstat(tdb->fd, &st) == -1) {
-               return TDB_ERRCODE(TDB_ERR_IO, -1);
+               tdb->ecode = TDB_ERR_IO;
+               return -1;
        }
 
        if (st.st_size < (size_t)len) {
@@ -59,12 +60,14 @@ static int tdb_oob(struct tdb_context *tdb, tdb_off_t len, 
int probe)
                        TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_oob len %d beyond 
eof at %d\n",
                                 (int)len, (int)st.st_size));
                }
-               return TDB_ERRCODE(TDB_ERR_IO, -1);


-- 
Samba Shared Repository

<Prev in Thread] Current Thread [Next in Thread>