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