git.ozlabs.org Git - ccan/blob - ccan/tdb/check.c

   1  /*
   2    Unix SMB/CIFS implementation.
   3
   4    trivial database library
   5
   6    Copyright (C) Rusty Russell             2009
   7
   8      ** NOTE! The following LGPL license applies to the tdb
   9      ** library. This does NOT imply that all of Samba is released
  10      ** under the LGPL
  11
  12    This library is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU Lesser General Public
  14    License as published by the Free Software Foundation; either
  15    version 3 of the License, or (at your option) any later version.
  16
  17    This library is distributed in the hope that it will be useful,
  18    but WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    Lesser General Public License for more details.
  21
  22    You should have received a copy of the GNU Lesser General Public
  23    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  24 */
  25 #include "tdb_private.h"
  26 #include <limits.h>
  27
  28 /*
  29   For each value, we flip F bits in a bitmap of size 2^B.  So we can think
  30   of this as a F*B bit hash (this isn't quite true due to hash collisions,
  31   but it seems good enough for F << B).
  32
  33   Assume that we only have a single error; this is *not* the birthday
  34   problem, since the question is: "does that error hash to the same as
  35   the correct value", ie. a simple 1 in 2^F*B.  The chances of detecting
  36   multiple errors is even higher (since we only need to detect one of
  37   them).
  38
  39   Given that ldb uses a hash size of 10000, using 512 bytes per hash chain
  40   (5M) seems reasonable.  With 128 hashes, that's about 1 in a million chance
  41   of missing a single linked list error.
  42 */
  43 #define NUM_HASHES 128
  44 #define BITMAP_BITS (512 * CHAR_BIT)
  45
  46 /* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
  47  * See: http://burtleburtle.net/bob/c/lookup3.c
  48  */
  49 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  50
  51 #define final(a,b,c) \
  52 { \
  53   c ^= b; c -= rot(b,14); \
  54   a ^= c; a -= rot(c,11); \
  55   b ^= a; b -= rot(a,25); \
  56   c ^= b; c -= rot(b,16); \
  57   a ^= c; a -= rot(c,4);  \
  58   b ^= a; b -= rot(a,14); \
  59   c ^= b; c -= rot(b,24); \
  60 }
  61
  62 static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
  63 {
  64         uint32_t a,b,c;
  65
  66         /* Set up the internal state */
  67         a = b = c = 0xdeadbeef + *pc;
  68         c += *pb;
  69
  70         a += key;
  71         final(a,b,c);
  72         *pc=c; *pb=b;
  73 }
  74
  75 static void bit_flip(unsigned char bits[], unsigned int idx)
  76 {
  77         bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
  78 }
  79
  80 static void add_to_hash(unsigned char bits[], tdb_off_t off)
  81 {
  82         uint32_t h1 = off, h2 = 0;
  83         unsigned int i;
  84         for (i = 0; i < NUM_HASHES / 2; i++) {
  85                 hash(off, &h1, &h2);
  86                 bit_flip(bits, h1 % BITMAP_BITS);
  87                 bit_flip(bits, h2 % BITMAP_BITS);
  88                 h2++;
  89         }
  90 }
  91
  92 /* Since we opened it, these shouldn't fail unless it's recent corruption. */
  93 static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
  94 {
  95         struct tdb_header hdr;
  96
  97         if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), DOCONV()) == -1)
  98                 return false;
  99         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
 100                 goto corrupt;
 101
 102         CONVERT(hdr);
 103         if (hdr.version != TDB_VERSION)
 104                 goto corrupt;
 105
 106         if (hdr.rwlocks != 0)
 107                 goto corrupt;
 108
 109         if (hdr.hash_size == 0)
 110                 goto corrupt;
 111
 112         if (hdr.hash_size != tdb->header.hash_size)
 113                 goto corrupt;
 114
 115         if (hdr.recovery_start != 0 &&
 116             hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
 117                 goto corrupt;
 118
 119         *recovery = hdr.recovery_start;
 120         return true;
 121
 122 corrupt:
 123         tdb->ecode = TDB_ERR_CORRUPT;
 124         return false;
 125 }
 126
 127 static bool tdb_check_record(struct tdb_context *tdb,
 128                              tdb_off_t off,
 129                              const struct list_struct *rec)
 130 {
 131         tdb_off_t tailer;
 132
 133         /* Check rec->next: 0 or points to record offset, aligned. */
 134         if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->header.hash_size))
 135                 goto corrupt;
 136         if (rec->next + sizeof(*rec) < rec->next)
 137                 goto corrupt;
 138         if ((rec->next % TDB_ALIGNMENT) != 0)
 139                 goto corrupt;
 140         if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 1))
 141                 goto corrupt;
 142
 143         /* Check rec_len: similar to rec->next, implies next record. */
 144         if ((rec->rec_len % TDB_ALIGNMENT) != 0)
 145                 goto corrupt;
 146         /* Must fit tailer. */
 147         if (rec->rec_len < sizeof(tailer))
 148                 goto corrupt;
 149         /* OOB allows "right at the end" access, so this works for last rec. */
 150         if (tdb->methods->tdb_oob(tdb, off+sizeof(*rec)+rec->rec_len, 1))
 151                 goto corrupt;
 152
 153         /* Check tailer. */
 154         if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
 155                          &tailer) == -1)
 156                 goto corrupt;
 157         if (tailer != sizeof(*rec) + rec->rec_len)
 158                 goto corrupt;
 159
 160         return true;
 161
 162 corrupt:
 163         tdb->ecode = TDB_ERR_CORRUPT;
 164         return false;
 165 }
 166
 167 static TDB_DATA get_data(struct tdb_context *tdb, tdb_off_t off, tdb_len_t len)
 168 {
 169         TDB_DATA d;
 170
 171         d.dsize = len;
 172
 173         /* We've already done bounds check here. */
 174         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
 175                 d.dptr = (unsigned char *)tdb->map_ptr + off;
 176         else
 177                 d.dptr = tdb_alloc_read(tdb, off, d.dsize);
 178         return d;
 179 }
 180
 181 static void put_data(struct tdb_context *tdb, TDB_DATA d)
 182 {
 183         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
 184                 return;
 185         free(d.dptr);
 186 }
 187
 188 static bool tdb_check_used_record(struct tdb_context *tdb,
 189                                   tdb_off_t off,
 190                                   const struct list_struct *rec,
 191                                   unsigned char **hashes,
 192                                   int (*check)(TDB_DATA, TDB_DATA, void *),
 193                                   void *private)
 194 {
 195         TDB_DATA key, data;
 196
 197         if (!tdb_check_record(tdb, off, rec))
 198                 return false;
 199
 200         /* key + data + tailer must fit in record */
 201         if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len)
 202                 return false;
 203
 204         key = get_data(tdb, off + sizeof(*rec), rec->key_len);
 205         if (!key.dptr)
 206                 return false;
 207
 208         if (tdb->hash_fn(&key) != rec->full_hash)
 209                 goto fail_put_key;
 210
 211         add_to_hash(hashes[BUCKET(rec->full_hash)+1], off);
 212         if (rec->next)
 213                 add_to_hash(hashes[BUCKET(rec->full_hash)+1], rec->next);
 214
 215         /* If they supply a check function, get data. */
 216         if (check) {
 217                 data = get_data(tdb, off + sizeof(*rec) + rec->key_len,
 218                                 rec->data_len);
 219                 if (!data.dptr)
 220                         goto fail_put_key;
 221
 222                 if (check(key, data, private) == -1)
 223                         goto fail_put_data;
 224                 put_data(tdb, data);
 225         }
 226
 227         put_data(tdb, key);
 228         return true;
 229
 230 fail_put_data:
 231         put_data(tdb, data);
 232 fail_put_key:
 233         put_data(tdb, key);
 234         return false;
 235 }
 236
 237 static bool tdb_check_free_record(struct tdb_context *tdb,
 238                                   tdb_off_t off,
 239                                   const struct list_struct *rec,
 240                                   unsigned char **hashes)
 241 {
 242         if (!tdb_check_record(tdb, off, rec))
 243                 return false;
 244
 245         add_to_hash(hashes[0], off);
 246         if (rec->next)
 247                 add_to_hash(hashes[0], rec->next);
 248         return true;
 249 }
 250
 251 /* We do this via linear scan, even though it's not 100% accurate. */
 252 int tdb_check(struct tdb_context *tdb,
 253               int (*check)(TDB_DATA key, TDB_DATA data, void *private),
 254               void *private)
 255 {
 256         unsigned int h;
 257         unsigned char **hashes;
 258         tdb_off_t off, recovery_start;
 259         struct list_struct rec;
 260         bool found_recovery = false;
 261
 262         if (tdb_lockall(tdb) == -1)
 263                 return -1;
 264
 265         /* Make sure we know true size of the underlying file. */
 266         tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
 267
 268         if (!tdb_check_header(tdb, &recovery_start))
 269                 goto unlock;
 270
 271         if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
 272                 tdb->ecode = TDB_ERR_CORRUPT;
 273                 goto unlock;
 274         }
 275
 276         /* One big malloc: pointers then bit arrays. */
 277         hashes = calloc(1, sizeof(hashes[0]) * (1+tdb->header.hash_size)
 278                         + BITMAP_BITS / CHAR_BIT * (1+tdb->header.hash_size));
 279         if (!hashes) {
 280                 tdb->ecode = TDB_ERR_OOM;
 281                 goto unlock;
 282         }
 283
 284         /* Initialize pointers */
 285         hashes[0] = (unsigned char *)(&hashes[1+tdb->header.hash_size]);
 286         for (h = 1; h < 1+tdb->header.hash_size; h++)
 287                 hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
 288
 289         /* Freelist and hash headers are all in a row. */
 290         for (h = 0; h < 1+tdb->header.hash_size; h++) {
 291                 if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
 292                                  &off) == -1)
 293                         goto free;
 294                 if (off)
 295                         add_to_hash(hashes[h], off);
 296         }
 297
 298         for (off = TDB_DATA_START(tdb->header.hash_size);
 299              off < tdb->map_size;
 300              off += sizeof(rec) + rec.rec_len) {
 301                 if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
 302                                            DOCONV()) == -1)
 303                         goto free;
 304                 switch (rec.magic) {
 305                 case TDB_MAGIC:
 306                 case TDB_DEAD_MAGIC:
 307                         if (!tdb_check_used_record(tdb, off, &rec, hashes,
 308                                                    check, private))
 309                                 goto free;
 310                         break;
 311                 case TDB_FREE_MAGIC:
 312                         if (!tdb_check_free_record(tdb, off, &rec, hashes))
 313                                 goto free;
 314                         break;
 315                 case TDB_RECOVERY_MAGIC:
 316                         if (recovery_start != off)
 317                                 goto free;
 318                         found_recovery = true;
 319                         break;
 320                 default:
 321                         tdb->ecode = TDB_ERR_CORRUPT;
 322                         goto free;
 323                 }
 324         }
 325
 326         /* Now, hashes should all be empty: each record exists and is referred
 327          * to by one other. */
 328         for (h = 0; h < 1+tdb->header.hash_size; h++) {
 329                 unsigned int i;
 330                 for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
 331                         if (hashes[h][i] != 0) {
 332                                 tdb->ecode = TDB_ERR_CORRUPT;
 333                                 goto free;
 334                         }
 335                 }
 336         }
 337
 338         /* We must have found recovery area. */
 339         if (recovery_start != 0 && !found_recovery)
 340                 goto free;
 341
 342         free(hashes);
 343         tdb_unlockall(tdb);
 344         return 0;
 345
 346 free:
 347         free(hashes);
 348 unlock:
 349         tdb_unlockall(tdb);
 350         return -1;
 351 }
 352
 353
 354
 355
 356
 357