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

   1  /*
   2    Trivial Database 2: free list/block handling
   3    Copyright (C) Rusty Russell 2010
   4
   5    This library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 3 of the License, or (at your option) any later version.
   9
  10    This library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  17 */
  18 #include "private.h"
  19 #include <ccan/likely/likely.h>
  20 #include <ccan/asearch/asearch.h>
  21
  22 /* We keep an ordered array of offsets. */
  23 static bool append(tdb_off_t **arr, size_t *num, tdb_off_t off)
  24 {
  25         tdb_off_t *new = realloc(*arr, (*num + 1) * sizeof(tdb_off_t));
  26         if (!new)
  27                 return false;
  28         new[(*num)++] = off;
  29         *arr = new;
  30         return true;
  31 }
  32
  33 static bool check_header(struct tdb_context *tdb)
  34 {
  35         uint64_t hash_test;
  36         struct tdb_header hdr;
  37
  38         if (tdb_read_convert(tdb, 0, &hdr, sizeof(hdr)) == -1)
  39                 return false;
  40         /* magic food should not be converted, so convert back. */
  41         tdb_convert(tdb, hdr.magic_food, sizeof(hdr.magic_food));
  42
  43         hash_test = TDB_HASH_MAGIC;
  44         hash_test = tdb_hash(tdb, &hash_test, sizeof(hash_test));
  45         if (hdr.hash_test != hash_test) {
  46                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  47                          "check: hash test %llu should be %llu\n",
  48                          (long long)hdr.hash_test,
  49                          (long long)hash_test);
  50                 return false;
  51         }
  52
  53         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0) {
  54                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  55                          "check: bad magic '%.*s'\n",
  56                          (unsigned)sizeof(hdr.magic_food), hdr.magic_food);
  57                 return false;
  58         }
  59
  60         /* Don't check reserved: they *can* be used later. */
  61         return true;
  62 }
  63
  64 static bool check_hash_tree(struct tdb_context *tdb,
  65                             tdb_off_t off, unsigned int group_bits,
  66                             uint64_t hprefix,
  67                             unsigned hprefix_bits,
  68                             tdb_off_t used[],
  69                             size_t num_used,
  70                             size_t *num_found);
  71
  72 static bool check_hash_record(struct tdb_context *tdb,
  73                               tdb_off_t off,
  74                               uint64_t hprefix,
  75                               unsigned hprefix_bits,
  76                               tdb_off_t used[],
  77                               size_t num_used,
  78                               size_t *num_found)
  79 {
  80         struct tdb_used_record rec;
  81
  82         if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1)
  83                 return false;
  84
  85         if (rec_data_length(&rec)
  86             != sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS) {
  87                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  88                          "tdb_check: Bad hash table length %llu vs %llu\n",
  89                          (long long)rec_data_length(&rec),
  90                          (long long)sizeof(tdb_off_t)<<TDB_SUBLEVEL_HASH_BITS);
  91                 return false;
  92         }
  93         if (rec_key_length(&rec) != 0) {
  94                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  95                          "tdb_check: Bad hash table key length %llu\n",
  96                          (long long)rec_key_length(&rec));
  97                 return false;
  98         }
  99         if (rec_hash(&rec) != 0) {
 100                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 101                          "tdb_check: Bad hash table hash value %llu\n",
 102                          (long long)rec_hash(&rec));
 103                 return false;
 104         }
 105
 106         off += sizeof(rec);
 107         return check_hash_tree(tdb, off,
 108                                TDB_SUBLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS,
 109                                hprefix, hprefix_bits,
 110                                used, num_used, num_found);
 111 }
 112
 113 static int off_cmp(const tdb_off_t *a, const tdb_off_t *b)
 114 {
 115         /* Can overflow an int. */
 116         return *a > *b ? 1
 117                 : *a < *b ? -1
 118                 : 0;
 119 }
 120
 121 static uint64_t get_bits(uint64_t h, unsigned num, unsigned *used)
 122 {
 123         *used += num;
 124
 125         return (h >> (64 - *used)) & ((1U << num) - 1);
 126 }
 127
 128 static bool check_hash_tree(struct tdb_context *tdb,
 129                             tdb_off_t off, unsigned int group_bits,
 130                             uint64_t hprefix,
 131                             unsigned hprefix_bits,
 132                             tdb_off_t used[],
 133                             size_t num_used,
 134                             size_t *num_found)
 135 {
 136         unsigned int g, b;
 137         const tdb_off_t *hash;
 138         struct tdb_used_record rec;
 139
 140         hash = tdb_access_read(tdb, off,
 141                                sizeof(tdb_off_t)
 142                                << (group_bits + TDB_HASH_GROUP_BITS),
 143                                true);
 144         if (!hash)
 145                 return false;
 146
 147         for (g = 0; g < (1 << group_bits); g++) {
 148                 const tdb_off_t *group = hash + (g << TDB_HASH_GROUP_BITS);
 149                 for (b = 0; b < (1 << TDB_HASH_GROUP_BITS); b++) {
 150                         unsigned int bucket, i, used_bits;
 151                         uint64_t h;
 152                         tdb_off_t *p;
 153                         if (group[b] == 0)
 154                                 continue;
 155
 156                         off = group[b] & TDB_OFF_MASK;
 157                         p = asearch(&off, used, num_used, off_cmp);
 158                         if (!p) {
 159                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 160                                          "tdb_check: Invalid offset %llu "
 161                                          "in hash\n",
 162                                          (long long)off);
 163                                 goto fail;
 164                         }
 165                         /* Mark it invalid. */
 166                         *p ^= 1;
 167                         (*num_found)++;
 168
 169                         if (is_subhash(group[b])) {
 170                                 uint64_t subprefix;
 171                                 subprefix = (hprefix
 172                                      << (group_bits + TDB_HASH_GROUP_BITS))
 173                                         + g * (1 << TDB_HASH_GROUP_BITS) + b;
 174
 175                                 if (!check_hash_record(tdb,
 176                                                group[b] & TDB_OFF_MASK,
 177                                                subprefix,
 178                                                hprefix_bits
 179                                                        + group_bits
 180                                                        + TDB_HASH_GROUP_BITS,
 181                                                used, num_used, num_found))
 182                                         goto fail;
 183                                 continue;
 184                         }
 185                         /* A normal entry */
 186
 187                         /* Does it belong here at all? */
 188                         h = hash_record(tdb, off);
 189                         used_bits = 0;
 190                         if (get_bits(h, hprefix_bits, &used_bits) != hprefix
 191                             && hprefix_bits) {
 192                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 193                                          "check: bad hash placement"
 194                                          " 0x%llx vs 0x%llx\n",
 195                                          (long long)h, (long long)hprefix);
 196                                 goto fail;
 197                         }
 198
 199                         /* Does it belong in this group? */
 200                         if (get_bits(h, group_bits, &used_bits) != g) {
 201                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 202                                          "check: bad group %llu vs %u\n",
 203                                          (long long)h, g);
 204                                 goto fail;
 205                         }
 206
 207                         /* Are bucket bits correct? */
 208                         bucket = group[b] & TDB_OFF_HASH_GROUP_MASK;
 209                         if (get_bits(h, TDB_HASH_GROUP_BITS, &used_bits)
 210                             != bucket) {
 211                                 used_bits -= TDB_HASH_GROUP_BITS;
 212                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 213                                          "check: bad bucket %u vs %u\n",
 214                                          (unsigned)get_bits(h,
 215                                                             TDB_HASH_GROUP_BITS,
 216                                                             &used_bits),
 217                                          bucket);
 218                                 goto fail;
 219                         }
 220
 221                         /* There must not be any zero entries between
 222                          * the bucket it belongs in and this one! */
 223                         for (i = bucket;
 224                              i != b;
 225                              i = (i + 1) % (1 << TDB_HASH_GROUP_BITS)) {
 226                                 if (group[i] == 0) {
 227                                         tdb->log(tdb, TDB_DEBUG_ERROR,
 228                                                  tdb->log_priv,
 229                                                  "check: bad group placement"
 230                                                  " %u vs %u\n",
 231                                                  b, bucket);
 232                                         goto fail;
 233                                 }
 234                         }
 235
 236                         if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1)
 237                                 goto fail;
 238
 239                         /* Bottom bits must match header. */
 240                         if ((h & ((1 << 11)-1)) != rec_hash(&rec)) {
 241                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 242                                          "tdb_check: Bad hash magic at"
 243                                          " offset %llu (0x%llx vs 0x%llx)\n",
 244                                          (long long)off,
 245                                          (long long)h,
 246                                          (long long)rec_hash(&rec));
 247                                 goto fail;
 248                         }
 249                 }
 250         }
 251         tdb_access_release(tdb, hash);
 252         return true;
 253
 254 fail:
 255         tdb_access_release(tdb, hash);
 256         return false;
 257 }
 258
 259 static bool check_hash(struct tdb_context *tdb,
 260                        tdb_off_t used[],
 261                        size_t num_used, size_t num_flists)
 262 {
 263         /* Free lists also show up as used. */
 264         size_t num_found = num_flists;
 265
 266         if (!check_hash_tree(tdb, offsetof(struct tdb_header, hashtable),
 267                              TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS,
 268                              0, 0, used, num_used, &num_found))
 269                 return false;
 270
 271         if (num_found != num_used) {
 272                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 273                          "tdb_check: Not all entries are in hash\n");
 274                 return false;
 275         }
 276         return true;
 277 }
 278
 279 static bool check_free(struct tdb_context *tdb,
 280                        tdb_off_t off,
 281                        const struct tdb_free_record *frec,
 282                        tdb_off_t prev, tdb_off_t flist_off, unsigned int bucket)
 283 {
 284         if (frec_magic(frec) != TDB_FREE_MAGIC) {
 285                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 286                          "tdb_check: offset %llu bad magic 0x%llx\n",
 287                          (long long)off, (long long)frec->magic_and_meta);
 288                 return false;
 289         }
 290         if (frec_flist(frec) != flist_off) {
 291                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 292                          "tdb_check: offset %llu bad freelist 0x%llx\n",
 293                          (long long)off, (long long)frec_flist(frec));
 294                 return false;
 295         }
 296
 297         if (tdb->methods->oob(tdb, off
 298                               + frec->data_len+sizeof(struct tdb_used_record),
 299                               false))
 300                 return false;
 301         if (size_to_bucket(frec->data_len) != bucket) {
 302                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 303                          "tdb_check: offset %llu in wrong bucket %u vs %u\n",
 304                          (long long)off,
 305                          bucket, size_to_bucket(frec->data_len));
 306                 return false;
 307         }
 308         if (prev != frec->prev) {
 309                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 310                          "tdb_check: offset %llu bad prev %llu vs %llu\n",
 311                          (long long)off,
 312                          (long long)prev, (long long)frec->prev);
 313                 return false;
 314         }
 315         return true;
 316 }
 317
 318 static bool check_free_list(struct tdb_context *tdb,
 319                             tdb_off_t flist_off,
 320                             tdb_off_t free[],
 321                             size_t num_free,
 322                             size_t *num_found)
 323 {
 324         struct tdb_freelist flist;
 325         tdb_off_t h;
 326         unsigned int i;
 327
 328         if (tdb_read_convert(tdb, flist_off, &flist, sizeof(flist)) == -1)
 329                 return false;
 330
 331         if (rec_magic(&flist.hdr) != TDB_MAGIC
 332             || rec_key_length(&flist.hdr) != 0
 333             || rec_data_length(&flist.hdr) != sizeof(flist) - sizeof(flist.hdr)
 334             || rec_hash(&flist.hdr) != 1) {
 335                 tdb->log(tdb, TDB_DEBUG_ERROR,
 336                          tdb->log_priv,
 337                          "tdb_check: Invalid header on free list\n");
 338                 return false;
 339         }
 340
 341         for (i = 0; i < TDB_FREE_BUCKETS; i++) {
 342                 tdb_off_t off, prev = 0, *p;
 343                 struct tdb_free_record f;
 344
 345                 h = bucket_off(flist_off, i);
 346                 for (off = tdb_read_off(tdb, h); off; off = f.next) {
 347                         if (off == TDB_OFF_ERR)
 348                                 return false;
 349                         if (tdb_read_convert(tdb, off, &f, sizeof(f)))
 350                                 return false;
 351                         if (!check_free(tdb, off, &f, prev, flist_off, i))
 352                                 return false;
 353
 354                         /* FIXME: Check hash bits */
 355                         p = asearch(&off, free, num_free, off_cmp);
 356                         if (!p) {
 357                                 tdb->log(tdb, TDB_DEBUG_ERROR,
 358                                          tdb->log_priv,
 359                                          "tdb_check: Invalid offset"
 360                                          " %llu in free table\n",
 361                                          (long long)off);
 362                                 return false;
 363                         }
 364                         /* Mark it invalid. */
 365                         *p ^= 1;
 366                         (*num_found)++;
 367                         prev = off;
 368                 }
 369         }
 370         return true;
 371 }
 372
 373 static bool check_linear(struct tdb_context *tdb,
 374                          tdb_off_t **used, size_t *num_used,
 375                          tdb_off_t **free, size_t *num_free)
 376 {
 377         tdb_off_t off;
 378         tdb_len_t len;
 379
 380         for (off = sizeof(struct tdb_header); off < tdb->map_size; off += len) {
 381                 union {
 382                         struct tdb_used_record u;
 383                         struct tdb_free_record f;
 384                 } pad, *p;
 385                 p = tdb_get(tdb, off, &pad, sizeof(pad));
 386                 if (!p)
 387                         return false;
 388                 if (frec_magic(&p->f) == TDB_FREE_MAGIC
 389                     || frec_magic(&p->f) == TDB_COALESCING_MAGIC) {
 390                         len = sizeof(p->u) + p->f.data_len;
 391                         if (off + len > tdb->map_size) {
 392                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 393                                          "tdb_check: free overlength %llu"
 394                                          " at offset %llu\n",
 395                                          (long long)len, (long long)off);
 396                                 return false;
 397                         }
 398                         /* This record is free! */
 399                         if (frec_magic(&p->f) == TDB_FREE_MAGIC
 400                             && !append(free, num_free, off))
 401                                 return false;
 402                 } else {
 403                         uint64_t klen, dlen, extra;
 404
 405                         /* This record is used! */
 406                         if (rec_magic(&p->u) != TDB_MAGIC) {
 407                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 408                                          "tdb_check: Bad magic 0x%llx"
 409                                          " at offset %llu\n",
 410                                          (long long)rec_magic(&p->u),
 411                                          (long long)off);
 412                                 return false;
 413                         }
 414
 415                         if (!append(used, num_used, off))
 416                                 return false;
 417
 418                         klen = rec_key_length(&p->u);
 419                         dlen = rec_data_length(&p->u);
 420                         extra = rec_extra_padding(&p->u);
 421
 422                         len = sizeof(p->u) + klen + dlen + extra;
 423                         if (off + len > tdb->map_size) {
 424                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 425                                          "tdb_check: used overlength %llu"
 426                                          " at offset %llu\n",
 427                                          (long long)len, (long long)off);
 428                                 return false;
 429                         }
 430
 431                         if (len < sizeof(p->f)) {
 432                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 433                                          "tdb_check: too short record %llu at"
 434                                          " %llu\n",
 435                                          (long long)len, (long long)off);
 436                                 return false;
 437                         }
 438                 }
 439         }
 440         return true;
 441 }
 442
 443 /* FIXME: call check() function. */
 444 int tdb_check(struct tdb_context *tdb,
 445               int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
 446               void *private_data)
 447 {
 448         tdb_off_t *free = NULL, *used = NULL, flist;
 449         size_t num_free = 0, num_used = 0, num_found = 0, num_flists = 0;
 450
 451         if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0)
 452                 return -1;
 453
 454         if (tdb_lock_expand(tdb, F_RDLCK) != 0) {
 455                 tdb_allrecord_unlock(tdb, F_RDLCK);
 456                 return -1;
 457         }
 458
 459         if (!check_header(tdb))
 460                 goto fail;
 461
 462         /* First we do a linear scan, checking all records. */
 463         if (!check_linear(tdb, &used, &num_used, &free, &num_free))
 464                 goto fail;
 465
 466         for (flist = first_flist(tdb); flist; flist = next_flist(tdb, flist)) {
 467                 if (flist == TDB_OFF_ERR)
 468                         goto fail;
 469                 if (!check_free_list(tdb, flist, free, num_free, &num_found))
 470                         goto fail;
 471                 num_flists++;
 472         }
 473
 474         /* FIXME: Check key uniqueness? */
 475         if (!check_hash(tdb, used, num_used, num_flists))
 476                 goto fail;
 477
 478         if (num_found != num_free) {
 479                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 480                          "tdb_check: Not all entries are in free table\n");
 481                 return false;
 482         }
 483
 484         tdb_allrecord_unlock(tdb, F_RDLCK);
 485         tdb_unlock_expand(tdb, F_RDLCK);
 486         return 0;
 487
 488 fail:
 489         tdb_allrecord_unlock(tdb, F_RDLCK);
 490         tdb_unlock_expand(tdb, F_RDLCK);
 491         return -1;
 492 }