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