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 /* Since we opened it, these shouldn't fail unless it's recent corruption. */
  29 static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
  30 {
  31         struct tdb_header hdr;
  32
  33         if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), DOCONV()) == -1)
  34                 return false;
  35         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
  36                 goto corrupt;
  37
  38         CONVERT(hdr);
  39         if (hdr.version != TDB_VERSION)
  40                 goto corrupt;
  41
  42         if (hdr.rwlocks != 0)
  43                 goto corrupt;
  44
  45         if (hdr.hash_size == 0)
  46                 goto corrupt;
  47
  48         if (hdr.hash_size != tdb->header.hash_size)
  49                 goto corrupt;
  50
  51         if (hdr.recovery_start != 0 &&
  52             hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
  53                 goto corrupt;
  54
  55         *recovery = hdr.recovery_start;
  56         return true;
  57
  58 corrupt:
  59         tdb->ecode = TDB_ERR_CORRUPT;
  60         return false;
  61 }
  62
  63 /* Generic record header check. */
  64 static bool tdb_check_record(struct tdb_context *tdb,
  65                              tdb_off_t off,
  66                              const struct list_struct *rec)
  67 {
  68         tdb_off_t tailer;
  69
  70         /* Check rec->next: 0 or points to record offset, aligned. */
  71         if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->header.hash_size))
  72                 goto corrupt;
  73         if (rec->next + sizeof(*rec) < rec->next)
  74                 goto corrupt;
  75         if ((rec->next % TDB_ALIGNMENT) != 0)
  76                 goto corrupt;
  77         if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 1))
  78                 goto corrupt;
  79
  80         /* Check rec_len: similar to rec->next, implies next record. */
  81         if ((rec->rec_len % TDB_ALIGNMENT) != 0)
  82                 goto corrupt;
  83         /* Must fit tailer. */
  84         if (rec->rec_len < sizeof(tailer))
  85                 goto corrupt;
  86         /* OOB allows "right at the end" access, so this works for last rec. */
  87         if (tdb->methods->tdb_oob(tdb, off+sizeof(*rec)+rec->rec_len, 1))
  88                 goto corrupt;
  89
  90         /* Check tailer. */
  91         if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
  92                          &tailer) == -1)
  93                 goto corrupt;
  94         if (tailer != sizeof(*rec) + rec->rec_len)
  95                 goto corrupt;
  96
  97         return true;
  98
  99 corrupt:
 100         tdb->ecode = TDB_ERR_CORRUPT;
 101         return false;
 102 }
 103
 104 /* Grab some bytes: may copy if can't use mmap.
 105    Caller has already done bounds check. */
 106 static TDB_DATA get_bytes(struct tdb_context *tdb,
 107                           tdb_off_t off, tdb_len_t len)
 108 {
 109         TDB_DATA d;
 110
 111         d.dsize = len;
 112
 113         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
 114                 d.dptr = (unsigned char *)tdb->map_ptr + off;
 115         else
 116                 d.dptr = tdb_alloc_read(tdb, off, d.dsize);
 117         return d;
 118 }
 119
 120 /* Frees data if we're not able to simply use mmap. */
 121 static void put_bytes(struct tdb_context *tdb, TDB_DATA d)
 122 {
 123         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
 124                 return;
 125         free(d.dptr);
 126 }
 127
 128 /* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
 129  * See: http://burtleburtle.net/bob/c/lookup3.c
 130  */
 131 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
 132 static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
 133 {
 134         uint32_t a,b,c;
 135
 136         /* Set up the internal state */
 137         a = b = c = 0xdeadbeef + *pc;
 138         c += *pb;
 139         a += key;
 140         c ^= b; c -= rot(b,14);
 141         a ^= c; a -= rot(c,11);
 142         b ^= a; b -= rot(a,25);
 143         c ^= b; c -= rot(b,16);
 144         a ^= c; a -= rot(c,4);
 145         b ^= a; b -= rot(a,14);
 146         c ^= b; c -= rot(b,24);
 147         *pc=c; *pb=b;
 148 }
 149
 150 /*
 151   We want to check that all free records are in the free list
 152   (only once), and all free list entries are free records.  Similarly
 153   for each hash chain of used records.
 154
 155   Doing that naively (without walking hash chains, since we want to be
 156   linear) means keeping a list of records which have been seen in each
 157   hash chain, and another of records pointed to (ie. next pointers
 158   from records and the initial hash chain heads).  These two lists
 159   should be equal.  This will take 8 bytes per record, and require
 160   sorting at the end.
 161
 162   So instead, we record each offset in a bitmap such a way that
 163   recording it twice will cancel out.  Since each offset should appear
 164   exactly twice, the bitmap should be zero at the end.
 165
 166   The approach was inspired by Bloom Filters (see Wikipedia).  For
 167   each value, we flip K bits in a bitmap of size N.  The number of
 168   distinct arrangements is:
 169
 170         N! / (K! * (N-K)!)
 171
 172   Of course, not all arrangements are actually distinct, but testing
 173   shows this formula to be close enough.
 174
 175   So, if K == 8 and N == 256, the probability of two things flipping the same
 176   bits is 1 in 409,663,695,276,000.
 177
 178   Given that ldb uses a hash size of 10000, using 32 bytes per hash chain
 179   (320k) seems reasonable.
 180 */
 181 #define NUM_HASHES 8
 182 #define BITMAP_BITS 256
 183
 184 static void bit_flip(unsigned char bits[], unsigned int idx)
 185 {
 186         bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
 187 }
 188
 189 /* We record offsets in a bitmap for the particular chain it should be in.  */
 190 static void record_offset(unsigned char bits[], tdb_off_t off)
 191 {
 192         uint32_t h1 = off, h2 = 0;
 193         unsigned int i;
 194
 195         /* We get two good hash values out of jhash2, so we use both.  Then
 196          * we keep going to produce further hash values. */
 197         for (i = 0; i < NUM_HASHES / 2; i++) {
 198                 hash(off, &h1, &h2);
 199                 bit_flip(bits, h1 % BITMAP_BITS);
 200                 bit_flip(bits, h2 % BITMAP_BITS);
 201                 h2++;
 202         }
 203 }
 204
 205 /* Check that an in-use record is valid. */
 206 static bool tdb_check_used_record(struct tdb_context *tdb,
 207                                   tdb_off_t off,
 208                                   const struct list_struct *rec,
 209                                   unsigned char **hashes,
 210                                   int (*check)(TDB_DATA, TDB_DATA, void *),
 211                                   void *private)
 212 {
 213         TDB_DATA key, data;
 214
 215         if (!tdb_check_record(tdb, off, rec))
 216                 return false;
 217
 218         /* key + data + tailer must fit in record */
 219         if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len)
 220                 return false;
 221
 222         key = get_bytes(tdb, off + sizeof(*rec), rec->key_len);
 223         if (!key.dptr)
 224                 return false;
 225
 226         if (tdb->hash_fn(&key) != rec->full_hash)
 227                 goto fail_put_key;
 228
 229         /* Mark this offset as a known value for this hash bucket. */
 230         record_offset(hashes[BUCKET(rec->full_hash)+1], off);
 231         /* And similarly if the next pointer is valid. */
 232         if (rec->next)
 233                 record_offset(hashes[BUCKET(rec->full_hash)+1], rec->next);
 234
 235         /* If they supply a check function and this record isn't dead,
 236            get data and feed it. */
 237         if (check && rec->magic != TDB_DEAD_MAGIC) {
 238                 data = get_bytes(tdb, off + sizeof(*rec) + rec->key_len,
 239                                  rec->data_len);
 240                 if (!data.dptr)
 241                         goto fail_put_key;
 242
 243                 if (check(key, data, private) == -1)
 244                         goto fail_put_data;
 245                 put_bytes(tdb, data);
 246         }
 247
 248         put_bytes(tdb, key);
 249         return true;
 250
 251 fail_put_data:
 252         put_bytes(tdb, data);
 253 fail_put_key:
 254         put_bytes(tdb, key);
 255         return false;
 256 }
 257
 258 /* Check that an unused record is valid. */
 259 static bool tdb_check_free_record(struct tdb_context *tdb,
 260                                   tdb_off_t off,
 261                                   const struct list_struct *rec,
 262                                   unsigned char **hashes)
 263 {
 264         if (!tdb_check_record(tdb, off, rec))
 265                 return false;
 266
 267         /* Mark this offset as a known value for the free list. */
 268         record_offset(hashes[0], off);
 269         /* And similarly if the next pointer is valid. */
 270         if (rec->next)
 271                 record_offset(hashes[0], rec->next);
 272         return true;
 273 }
 274
 275 int tdb_check(struct tdb_context *tdb,
 276               int (*check)(TDB_DATA key, TDB_DATA data, void *private),
 277               void *private)
 278 {
 279         unsigned int h;
 280         unsigned char **hashes;
 281         tdb_off_t off, recovery_start;
 282         struct list_struct rec;
 283         bool found_recovery = false;
 284
 285         if (tdb_lockall(tdb) == -1)
 286                 return -1;
 287
 288         /* Make sure we know true size of the underlying file. */
 289         tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
 290
 291         /* Header must be OK: also gets us the recovery ptr, if any. */
 292         if (!tdb_check_header(tdb, &recovery_start))
 293                 goto unlock;
 294
 295         /* We should have the whole header, too. */
 296         if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
 297                 tdb->ecode = TDB_ERR_CORRUPT;
 298                 goto unlock;
 299         }
 300
 301         /* One big malloc: pointers then bit arrays. */
 302         hashes = calloc(1, sizeof(hashes[0]) * (1+tdb->header.hash_size)
 303                         + BITMAP_BITS / CHAR_BIT * (1+tdb->header.hash_size));
 304         if (!hashes) {
 305                 tdb->ecode = TDB_ERR_OOM;
 306                 goto unlock;
 307         }
 308
 309         /* Initialize pointers */
 310         hashes[0] = (unsigned char *)(&hashes[1+tdb->header.hash_size]);
 311         for (h = 1; h < 1+tdb->header.hash_size; h++)
 312                 hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
 313
 314         /* Freelist and hash headers are all in a row: read them. */
 315         for (h = 0; h < 1+tdb->header.hash_size; h++) {
 316                 if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
 317                                  &off) == -1)
 318                         goto free;
 319                 if (off)
 320                         record_offset(hashes[h], off);
 321         }
 322
 323         /* For each record, read it in and check it's ok. */
 324         for (off = TDB_DATA_START(tdb->header.hash_size);
 325              off < tdb->map_size;
 326              off += sizeof(rec) + rec.rec_len) {
 327                 if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
 328                                            DOCONV()) == -1)
 329                         goto free;
 330                 switch (rec.magic) {
 331                 case TDB_MAGIC:
 332                 case TDB_DEAD_MAGIC:
 333                         if (!tdb_check_used_record(tdb, off, &rec, hashes,
 334                                                    check, private))
 335                                 goto free;
 336                         break;
 337                 case TDB_FREE_MAGIC:
 338                         if (!tdb_check_free_record(tdb, off, &rec, hashes))
 339                                 goto free;
 340                         break;
 341                 case TDB_RECOVERY_MAGIC:
 342                         if (recovery_start != off)
 343                                 goto free;
 344                         found_recovery = true;
 345                         break;
 346                 default:
 347                         tdb->ecode = TDB_ERR_CORRUPT;
 348                         goto free;
 349                 }
 350         }
 351
 352         /* Now, hashes should all be empty: each record exists and is referred
 353          * to by one other. */
 354         for (h = 0; h < 1+tdb->header.hash_size; h++) {
 355                 unsigned int i;
 356                 for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
 357                         if (hashes[h][i] != 0) {
 358                                 tdb->ecode = TDB_ERR_CORRUPT;
 359                                 goto free;
 360                         }
 361                 }
 362         }
 363
 364         /* We must have found recovery area if there was one. */
 365         if (recovery_start != 0 && !found_recovery)
 366                 goto free;
 367
 368         free(hashes);
 369         tdb_unlockall(tdb);
 370         return 0;
 371
 372 free:
 373         free(hashes);
 374 unlock:
 375         tdb_unlockall(tdb);
 376         return -1;
 377 }
 378
 379
 380
 381
 382
 383