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 enum TDB_ERROR check_header(struct tdb_context *tdb, tdb_off_t *recovery,
  34                                    uint64_t *features)
  35 {
  36         uint64_t hash_test;
  37         struct tdb_header hdr;
  38         enum TDB_ERROR ecode;
  39
  40         ecode = tdb_read_convert(tdb, 0, &hdr, sizeof(hdr));
  41         if (ecode != TDB_SUCCESS) {
  42                 return ecode;
  43         }
  44         /* magic food should not be converted, so convert back. */
  45         tdb_convert(tdb, hdr.magic_food, sizeof(hdr.magic_food));
  46
  47         hash_test = TDB_HASH_MAGIC;
  48         hash_test = tdb_hash(tdb, &hash_test, sizeof(hash_test));
  49         if (hdr.hash_test != hash_test) {
  50                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
  51                                   "check: hash test %llu should be %llu",
  52                                   (long long)hdr.hash_test,
  53                                   (long long)hash_test);
  54         }
  55
  56         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0) {
  57                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
  58                                   "check: bad magic '%.*s'",
  59                                   (unsigned)sizeof(hdr.magic_food),
  60                                   hdr.magic_food);
  61         }
  62
  63         /* Features which are used must be a subset of features offered. */
  64         if (hdr.features_used & ~hdr.features_offered) {
  65                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
  66                                   "check: features used (0x%llx) which"
  67                                   " are not offered (0x%llx)",
  68                                   (long long)hdr.features_used,
  69                                   (long long)hdr.features_offered);
  70         }
  71
  72         *features = hdr.features_offered;
  73         *recovery = hdr.recovery;
  74         if (*recovery) {
  75                 if (*recovery < sizeof(hdr) || *recovery > tdb->map_size) {
  76                         return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
  77                                           "tdb_check:"
  78                                           " invalid recovery offset %zu",
  79                                           (size_t)*recovery);
  80                 }
  81         }
  82
  83         /* Don't check reserved: they *can* be used later. */
  84         return TDB_SUCCESS;
  85 }
  86
  87 static enum TDB_ERROR check_hash_tree(struct tdb_context *tdb,
  88                                       tdb_off_t off, unsigned int group_bits,
  89                                       uint64_t hprefix,
  90                                       unsigned hprefix_bits,
  91                                       tdb_off_t used[],
  92                                       size_t num_used,
  93                                       size_t *num_found,
  94                                       enum TDB_ERROR (*check)(TDB_DATA,
  95                                                               TDB_DATA, void *),
  96                                       void *private_data);
  97
  98 static enum TDB_ERROR check_hash_chain(struct tdb_context *tdb,
  99                                        tdb_off_t off,
 100                                        uint64_t hash,
 101                                        tdb_off_t used[],
 102                                        size_t num_used,
 103                                        size_t *num_found,
 104                                        enum TDB_ERROR (*check)(TDB_DATA,
 105                                                                TDB_DATA,
 106                                                                void *),
 107                                        void *private_data)
 108 {
 109         struct tdb_used_record rec;
 110         enum TDB_ERROR ecode;
 111
 112         ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec));
 113         if (ecode != TDB_SUCCESS) {
 114                 return ecode;
 115         }
 116
 117         if (rec_magic(&rec) != TDB_CHAIN_MAGIC) {
 118                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 119                                   "tdb_check: Bad hash chain magic %llu",
 120                                   (long long)rec_magic(&rec));
 121         }
 122
 123         if (rec_data_length(&rec) != sizeof(struct tdb_chain)) {
 124                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 125                                   "tdb_check:"
 126                                   " Bad hash chain length %llu vs %zu",
 127                                   (long long)rec_data_length(&rec),
 128                                   sizeof(struct tdb_chain));
 129         }
 130         if (rec_key_length(&rec) != 0) {
 131                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 132                                   "tdb_check: Bad hash chain key length %llu",
 133                                   (long long)rec_key_length(&rec));
 134         }
 135         if (rec_hash(&rec) != 0) {
 136                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 137                                   "tdb_check: Bad hash chain hash value %llu",
 138                                   (long long)rec_hash(&rec));
 139         }
 140
 141         off += sizeof(rec);
 142         ecode = check_hash_tree(tdb, off, 0, hash, 64,
 143                                 used, num_used, num_found, check, private_data);
 144         if (ecode != TDB_SUCCESS) {
 145                 return ecode;
 146         }
 147
 148         off = tdb_read_off(tdb, off + offsetof(struct tdb_chain, next));
 149         if (TDB_OFF_IS_ERR(off)) {
 150                 return off;
 151         }
 152         if (off == 0)
 153                 return TDB_SUCCESS;
 154         (*num_found)++;
 155         return check_hash_chain(tdb, off, hash, used, num_used, num_found,
 156                                 check, private_data);
 157 }
 158
 159 static enum TDB_ERROR check_hash_record(struct tdb_context *tdb,
 160                                         tdb_off_t off,
 161                                         uint64_t hprefix,
 162                                         unsigned hprefix_bits,
 163                                         tdb_off_t used[],
 164                                         size_t num_used,
 165                                         size_t *num_found,
 166                                         enum TDB_ERROR (*check)(TDB_DATA,
 167                                                                 TDB_DATA,
 168                                                                 void *),
 169                                         void *private_data)
 170 {
 171         struct tdb_used_record rec;
 172         enum TDB_ERROR ecode;
 173
 174         if (hprefix_bits >= 64)
 175                 return check_hash_chain(tdb, off, hprefix, used, num_used,
 176                                         num_found, check, private_data);
 177
 178         ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec));
 179         if (ecode != TDB_SUCCESS) {
 180                 return ecode;
 181         }
 182
 183         if (rec_magic(&rec) != TDB_HTABLE_MAGIC) {
 184                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 185                                   "tdb_check: Bad hash table magic %llu",
 186                                   (long long)rec_magic(&rec));
 187         }
 188         if (rec_data_length(&rec)
 189             != sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS) {
 190                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 191                                   "tdb_check:"
 192                                   " Bad hash table length %llu vs %llu",
 193                                   (long long)rec_data_length(&rec),
 194                                   (long long)sizeof(tdb_off_t)
 195                                   << TDB_SUBLEVEL_HASH_BITS);
 196         }
 197         if (rec_key_length(&rec) != 0) {
 198                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 199                                   "tdb_check: Bad hash table key length %llu",
 200                                   (long long)rec_key_length(&rec));
 201         }
 202         if (rec_hash(&rec) != 0) {
 203                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 204                                   "tdb_check: Bad hash table hash value %llu",
 205                                   (long long)rec_hash(&rec));
 206         }
 207
 208         off += sizeof(rec);
 209         return check_hash_tree(tdb, off,
 210                                TDB_SUBLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS,
 211                                hprefix, hprefix_bits,
 212                                used, num_used, num_found, check, private_data);
 213 }
 214
 215 static int off_cmp(const tdb_off_t *a, const tdb_off_t *b)
 216 {
 217         /* Can overflow an int. */
 218         return *a > *b ? 1
 219                 : *a < *b ? -1
 220                 : 0;
 221 }
 222
 223 static uint64_t get_bits(uint64_t h, unsigned num, unsigned *used)
 224 {
 225         *used += num;
 226
 227         return (h >> (64 - *used)) & ((1U << num) - 1);
 228 }
 229
 230 static enum TDB_ERROR check_hash_tree(struct tdb_context *tdb,
 231                                       tdb_off_t off, unsigned int group_bits,
 232                                       uint64_t hprefix,
 233                                       unsigned hprefix_bits,
 234                                       tdb_off_t used[],
 235                                       size_t num_used,
 236                                       size_t *num_found,
 237                                       enum TDB_ERROR (*check)(TDB_DATA,
 238                                                               TDB_DATA, void *),
 239                                       void *private_data)
 240 {
 241         unsigned int g, b;
 242         const tdb_off_t *hash;
 243         struct tdb_used_record rec;
 244         enum TDB_ERROR ecode;
 245
 246         hash = tdb_access_read(tdb, off,
 247                                sizeof(tdb_off_t)
 248                                << (group_bits + TDB_HASH_GROUP_BITS),
 249                                true);
 250         if (TDB_PTR_IS_ERR(hash)) {
 251                 return TDB_PTR_ERR(hash);
 252         }
 253
 254         for (g = 0; g < (1 << group_bits); g++) {
 255                 const tdb_off_t *group = hash + (g << TDB_HASH_GROUP_BITS);
 256                 for (b = 0; b < (1 << TDB_HASH_GROUP_BITS); b++) {
 257                         unsigned int bucket, i, used_bits;
 258                         uint64_t h;
 259                         tdb_off_t *p;
 260                         if (group[b] == 0)
 261                                 continue;
 262
 263                         off = group[b] & TDB_OFF_MASK;
 264                         p = asearch(&off, used, num_used, off_cmp);
 265                         if (!p) {
 266                                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
 267                                                    TDB_LOG_ERROR,
 268                                                    "tdb_check: Invalid offset"
 269                                                    " %llu in hash",
 270                                                    (long long)off);
 271                                 goto fail;
 272                         }
 273                         /* Mark it invalid. */
 274                         *p ^= 1;
 275                         (*num_found)++;
 276
 277                         if (hprefix_bits == 64) {
 278                                 /* Chained entries are unordered. */
 279                                 if (is_subhash(group[b])) {
 280                                         ecode = TDB_ERR_CORRUPT;
 281                                         tdb_logerr(tdb, ecode,
 282                                                    TDB_LOG_ERROR,
 283                                                    "tdb_check: Invalid chain"
 284                                                    " entry subhash");
 285                                         goto fail;
 286                                 }
 287                                 h = hash_record(tdb, off);
 288                                 if (h != hprefix) {
 289                                         ecode = TDB_ERR_CORRUPT;
 290                                         tdb_logerr(tdb, ecode,
 291                                                    TDB_LOG_ERROR,
 292                                                    "check: bad hash chain"
 293                                                    " placement"
 294                                                    " 0x%llx vs 0x%llx",
 295                                                    (long long)h,
 296                                                    (long long)hprefix);
 297                                         goto fail;
 298                                 }
 299                                 ecode = tdb_read_convert(tdb, off, &rec,
 300                                                          sizeof(rec));
 301                                 if (ecode != TDB_SUCCESS) {
 302                                         goto fail;
 303                                 }
 304                                 goto check;
 305                         }
 306
 307                         if (is_subhash(group[b])) {
 308                                 uint64_t subprefix;
 309                                 subprefix = (hprefix
 310                                      << (group_bits + TDB_HASH_GROUP_BITS))
 311                                         + g * (1 << TDB_HASH_GROUP_BITS) + b;
 312
 313                                 ecode = check_hash_record(tdb,
 314                                                group[b] & TDB_OFF_MASK,
 315                                                subprefix,
 316                                                hprefix_bits
 317                                                        + group_bits
 318                                                        + TDB_HASH_GROUP_BITS,
 319                                                used, num_used, num_found,
 320                                                check, private_data);
 321                                 if (ecode != TDB_SUCCESS) {
 322                                         goto fail;
 323                                 }
 324                                 continue;
 325                         }
 326                         /* A normal entry */
 327
 328                         /* Does it belong here at all? */
 329                         h = hash_record(tdb, off);
 330                         used_bits = 0;
 331                         if (get_bits(h, hprefix_bits, &used_bits) != hprefix
 332                             && hprefix_bits) {
 333                                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
 334                                                    TDB_LOG_ERROR,
 335                                                    "check: bad hash placement"
 336                                                    " 0x%llx vs 0x%llx",
 337                                                    (long long)h,
 338                                                    (long long)hprefix);
 339                                 goto fail;
 340                         }
 341
 342                         /* Does it belong in this group? */
 343                         if (get_bits(h, group_bits, &used_bits) != g) {
 344                                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
 345                                                    TDB_LOG_ERROR,
 346                                                    "check: bad group %llu"
 347                                                    " vs %u",
 348                                                    (long long)h, g);
 349                                 goto fail;
 350                         }
 351
 352                         /* Are bucket bits correct? */
 353                         bucket = group[b] & TDB_OFF_HASH_GROUP_MASK;
 354                         if (get_bits(h, TDB_HASH_GROUP_BITS, &used_bits)
 355                             != bucket) {
 356                                 used_bits -= TDB_HASH_GROUP_BITS;
 357                                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
 358                                                    TDB_LOG_ERROR,
 359                                                    "check: bad bucket %u vs %u",
 360                                                    (unsigned)get_bits(h,
 361                                                         TDB_HASH_GROUP_BITS,
 362                                                         &used_bits),
 363                                                    bucket);
 364                                 goto fail;
 365                         }
 366
 367                         /* There must not be any zero entries between
 368                          * the bucket it belongs in and this one! */
 369                         for (i = bucket;
 370                              i != b;
 371                              i = (i + 1) % (1 << TDB_HASH_GROUP_BITS)) {
 372                                 if (group[i] == 0) {
 373                                         ecode = TDB_ERR_CORRUPT;
 374                                         tdb_logerr(tdb, ecode,
 375                                                    TDB_LOG_ERROR,
 376                                                    "check: bad group placement"
 377                                                    " %u vs %u",
 378                                                    b, bucket);
 379                                         goto fail;
 380                                 }
 381                         }
 382
 383                         ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec));
 384                         if (ecode != TDB_SUCCESS) {
 385                                 goto fail;
 386                         }
 387
 388                         /* Bottom bits must match header. */
 389                         if ((h & ((1 << 11)-1)) != rec_hash(&rec)) {
 390                                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
 391                                                    TDB_LOG_ERROR,
 392                                                    "tdb_check: Bad hash magic"
 393                                                    " at offset %llu"
 394                                                    " (0x%llx vs 0x%llx)",
 395                                                    (long long)off,
 396                                                    (long long)h,
 397                                                    (long long)rec_hash(&rec));
 398                                 goto fail;
 399                         }
 400
 401                 check:
 402                         if (check) {
 403                                 TDB_DATA key, data;
 404                                 key.dsize = rec_key_length(&rec);
 405                                 data.dsize = rec_data_length(&rec);
 406                                 key.dptr = (void *)tdb_access_read(tdb,
 407                                                    off + sizeof(rec),
 408                                                    key.dsize + data.dsize,
 409                                                    false);
 410                                 if (TDB_PTR_IS_ERR(key.dptr)) {
 411                                         ecode = TDB_PTR_ERR(key.dptr);
 412                                         goto fail;
 413                                 }
 414                                 data.dptr = key.dptr + key.dsize;
 415                                 ecode = check(key, data, private_data);
 416                                 if (ecode != TDB_SUCCESS) {
 417                                         goto fail;
 418                                 }
 419                                 tdb_access_release(tdb, key.dptr);
 420                         }
 421                 }
 422         }
 423         tdb_access_release(tdb, hash);
 424         return TDB_SUCCESS;
 425
 426 fail:
 427         tdb_access_release(tdb, hash);
 428         return ecode;
 429 }
 430
 431 static enum TDB_ERROR check_hash(struct tdb_context *tdb,
 432                                  tdb_off_t used[],
 433                                  size_t num_used, size_t num_ftables,
 434                                  int (*check)(TDB_DATA, TDB_DATA, void *),
 435                                  void *private_data)
 436 {
 437         /* Free tables also show up as used. */
 438         size_t num_found = num_ftables;
 439         enum TDB_ERROR ecode;
 440
 441         ecode = check_hash_tree(tdb, offsetof(struct tdb_header, hashtable),
 442                                 TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS,
 443                                 0, 0, used, num_used, &num_found,
 444                                 check, private_data);
 445         if (ecode == TDB_SUCCESS) {
 446                 if (num_found != num_used) {
 447                         ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 448                                            "tdb_check: Not all entries"
 449                                            " are in hash");
 450                 }
 451         }
 452         return ecode;
 453 }
 454
 455 static enum TDB_ERROR check_free(struct tdb_context *tdb,
 456                                  tdb_off_t off,
 457                                  const struct tdb_free_record *frec,
 458                                  tdb_off_t prev, unsigned int ftable,
 459                                  unsigned int bucket)
 460 {
 461         enum TDB_ERROR ecode;
 462
 463         if (frec_magic(frec) != TDB_FREE_MAGIC) {
 464                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 465                                   "tdb_check: offset %llu bad magic 0x%llx",
 466                                   (long long)off,
 467                                   (long long)frec->magic_and_prev);
 468         }
 469         if (frec_ftable(frec) != ftable) {
 470                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 471                                   "tdb_check: offset %llu bad freetable %u",
 472                                   (long long)off, frec_ftable(frec));
 473
 474         }
 475
 476         ecode = tdb->methods->oob(tdb, off
 477                                   + frec_len(frec)
 478                                   + sizeof(struct tdb_used_record),
 479                                   false);
 480         if (ecode != TDB_SUCCESS) {
 481                 return ecode;
 482         }
 483         if (size_to_bucket(frec_len(frec)) != bucket) {
 484                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 485                                   "tdb_check: offset %llu in wrong bucket"
 486                                   " (%u vs %u)",
 487                                   (long long)off,
 488                                   bucket, size_to_bucket(frec_len(frec)));
 489         }
 490         if (prev != frec_prev(frec)) {
 491                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 492                                   "tdb_check: offset %llu bad prev"
 493                                   " (%llu vs %llu)",
 494                                   (long long)off,
 495                                   (long long)prev, (long long)frec_len(frec));
 496         }
 497         return TDB_SUCCESS;
 498 }
 499
 500 static enum TDB_ERROR check_free_table(struct tdb_context *tdb,
 501                                        tdb_off_t ftable_off,
 502                                        unsigned ftable_num,
 503                                        tdb_off_t fr[],
 504                                        size_t num_free,
 505                                        size_t *num_found)
 506 {
 507         struct tdb_freetable ft;
 508         tdb_off_t h;
 509         unsigned int i;
 510         enum TDB_ERROR ecode;
 511
 512         ecode = tdb_read_convert(tdb, ftable_off, &ft, sizeof(ft));
 513         if (ecode != TDB_SUCCESS) {
 514                 return ecode;
 515         }
 516
 517         if (rec_magic(&ft.hdr) != TDB_FTABLE_MAGIC
 518             || rec_key_length(&ft.hdr) != 0
 519             || rec_data_length(&ft.hdr) != sizeof(ft) - sizeof(ft.hdr)
 520             || rec_hash(&ft.hdr) != 0) {
 521                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 522                                   "tdb_check: Invalid header on free table");
 523         }
 524
 525         for (i = 0; i < TDB_FREE_BUCKETS; i++) {
 526                 tdb_off_t off, prev = 0, *p;
 527                 struct tdb_free_record f;
 528
 529                 h = bucket_off(ftable_off, i);
 530                 for (off = tdb_read_off(tdb, h); off; off = f.next) {
 531                         if (TDB_OFF_IS_ERR(off)) {
 532                                 return off;
 533                         }
 534                         ecode = tdb_read_convert(tdb, off, &f, sizeof(f));
 535                         if (ecode != TDB_SUCCESS) {
 536                                 return ecode;
 537                         }
 538                         ecode = check_free(tdb, off, &f, prev, ftable_num, i);
 539                         if (ecode != TDB_SUCCESS) {
 540                                 return ecode;
 541                         }
 542
 543                         /* FIXME: Check hash bits */
 544                         p = asearch(&off, fr, num_free, off_cmp);
 545                         if (!p) {
 546                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 547                                                   TDB_LOG_ERROR,
 548                                                   "tdb_check: Invalid offset"
 549                                                   " %llu in free table",
 550                                                   (long long)off);
 551                         }
 552                         /* Mark it invalid. */
 553                         *p ^= 1;
 554                         (*num_found)++;
 555                         prev = off;
 556                 }
 557         }
 558         return TDB_SUCCESS;
 559 }
 560
 561 /* Slow, but should be very rare. */
 562 tdb_off_t dead_space(struct tdb_context *tdb, tdb_off_t off)
 563 {
 564         size_t len;
 565         enum TDB_ERROR ecode;
 566
 567         for (len = 0; off + len < tdb->map_size; len++) {
 568                 char c;
 569                 ecode = tdb->methods->tread(tdb, off, &c, 1);
 570                 if (ecode != TDB_SUCCESS) {
 571                         return ecode;
 572                 }
 573                 if (c != 0 && c != 0x43)
 574                         break;
 575         }
 576         return len;
 577 }
 578
 579 static enum TDB_ERROR check_linear(struct tdb_context *tdb,
 580                                    tdb_off_t **used, size_t *num_used,
 581                                    tdb_off_t **fr, size_t *num_free,
 582                                    uint64_t features, tdb_off_t recovery)
 583 {
 584         tdb_off_t off;
 585         tdb_len_t len;
 586         enum TDB_ERROR ecode;
 587         bool found_recovery = false;
 588
 589         for (off = sizeof(struct tdb_header); off < tdb->map_size; off += len) {
 590                 union {
 591                         struct tdb_used_record u;
 592                         struct tdb_free_record f;
 593                         struct tdb_recovery_record r;
 594                 } rec;
 595                 /* r is larger: only get that if we need to. */
 596                 ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec.f));
 597                 if (ecode != TDB_SUCCESS) {
 598                         return ecode;
 599                 }
 600
 601                 /* If we crash after ftruncate, we can get zeroes or fill. */
 602                 if (rec.r.magic == TDB_RECOVERY_INVALID_MAGIC
 603                     || rec.r.magic ==  0x4343434343434343ULL) {
 604                         ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec.r));
 605                         if (ecode != TDB_SUCCESS) {
 606                                 return ecode;
 607                         }
 608                         if (recovery == off) {
 609                                 found_recovery = true;
 610                                 len = sizeof(rec.r) + rec.r.max_len;
 611                         } else {
 612                                 len = dead_space(tdb, off);
 613                                 if (TDB_OFF_IS_ERR(len)) {
 614                                         return len;
 615                                 }
 616                                 if (len < sizeof(rec.r)) {
 617                                         return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 618                                                           TDB_LOG_ERROR,
 619                                                           "tdb_check: invalid"
 620                                                           " dead space at %zu",
 621                                                           (size_t)off);
 622                                 }
 623
 624                                 tdb_logerr(tdb, TDB_SUCCESS, TDB_LOG_WARNING,
 625                                            "Dead space at %zu-%zu (of %zu)",
 626                                            (size_t)off, (size_t)(off + len),
 627                                            (size_t)tdb->map_size);
 628                         }
 629                 } else if (rec.r.magic == TDB_RECOVERY_MAGIC) {
 630                         ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec.r));
 631                         if (ecode != TDB_SUCCESS) {
 632                                 return ecode;
 633                         }
 634                         if (recovery != off) {
 635                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 636                                                   TDB_LOG_ERROR,
 637                                                   "tdb_check: unexpected"
 638                                                   " recovery record at offset"
 639                                                   " %zu",
 640                                                   (size_t)off);
 641                         }
 642                         if (rec.r.len > rec.r.max_len) {
 643                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 644                                                   TDB_LOG_ERROR,
 645                                                   "tdb_check: invalid recovery"
 646                                                   " length %zu",
 647                                                   (size_t)rec.r.len);
 648                         }
 649                         if (rec.r.eof > tdb->map_size) {
 650                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 651                                                   TDB_LOG_ERROR,
 652                                                   "tdb_check: invalid old EOF"
 653                                                   " %zu", (size_t)rec.r.eof);
 654                         }
 655                         found_recovery = true;
 656                         len = sizeof(rec.r) + rec.r.max_len;
 657                 } else if (frec_magic(&rec.f) == TDB_FREE_MAGIC) {
 658                         len = sizeof(rec.u) + frec_len(&rec.f);
 659                         if (off + len > tdb->map_size) {
 660                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 661                                                   TDB_LOG_ERROR,
 662                                                   "tdb_check: free overlength"
 663                                                   " %llu at offset %llu",
 664                                                   (long long)len,
 665                                                   (long long)off);
 666                         }
 667                         /* This record should be in free lists. */
 668                         if (frec_ftable(&rec.f) != TDB_FTABLE_NONE
 669                             && !append(fr, num_free, off)) {
 670                                 return tdb_logerr(tdb, TDB_ERR_OOM,
 671                                                   TDB_LOG_ERROR,
 672                                                   "tdb_check: tracking %zu'th"
 673                                                   " free record.", *num_free);
 674                         }
 675                 } else if (rec_magic(&rec.u) == TDB_USED_MAGIC
 676                            || rec_magic(&rec.u) == TDB_CHAIN_MAGIC
 677                            || rec_magic(&rec.u) == TDB_HTABLE_MAGIC
 678                            || rec_magic(&rec.u) == TDB_FTABLE_MAGIC) {
 679                         uint64_t klen, dlen, extra;
 680
 681                         /* This record is used! */
 682                         if (!append(used, num_used, off)) {
 683                                 return tdb_logerr(tdb, TDB_ERR_OOM,
 684                                                   TDB_LOG_ERROR,
 685                                                   "tdb_check: tracking %zu'th"
 686                                                   " used record.", *num_used);
 687                         }
 688
 689                         klen = rec_key_length(&rec.u);
 690                         dlen = rec_data_length(&rec.u);
 691                         extra = rec_extra_padding(&rec.u);
 692
 693                         len = sizeof(rec.u) + klen + dlen + extra;
 694                         if (off + len > tdb->map_size) {
 695                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 696                                                   TDB_LOG_ERROR,
 697                                                   "tdb_check: used overlength"
 698                                                   " %llu at offset %llu",
 699                                                   (long long)len,
 700                                                   (long long)off);
 701                         }
 702
 703                         if (len < sizeof(rec.f)) {
 704                                 return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 705                                                   TDB_LOG_ERROR,
 706                                                   "tdb_check: too short record"
 707                                                   " %llu at %llu",
 708                                                   (long long)len,
 709                                                   (long long)off);
 710                         }
 711
 712                         /* Check that records have correct 0 at end (but may
 713                          * not in future). */
 714                         if (extra && !features) {
 715                                 const char *p;
 716                                 char c;
 717                                 p = tdb_access_read(tdb, off + sizeof(rec.u)
 718                                                     + klen + dlen, 1, false);
 719                                 if (TDB_PTR_IS_ERR(p))
 720                                         return TDB_PTR_ERR(p);
 721                                 c = *p;
 722                                 tdb_access_release(tdb, p);
 723
 724                                 if (c != '\0') {
 725                                         return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 726                                                           TDB_LOG_ERROR,
 727                                                           "tdb_check:"
 728                                                           " non-zero extra"
 729                                                           " at %llu",
 730                                                           (long long)off);
 731                                 }
 732                         }
 733                 } else {
 734                         return tdb_logerr(tdb, TDB_ERR_CORRUPT,
 735                                           TDB_LOG_ERROR,
 736                                           "tdb_check: Bad magic 0x%llx"
 737                                           " at offset %zu",
 738                                           (long long)rec_magic(&rec.u),
 739                                           (size_t)off);
 740                 }
 741         }
 742
 743         /* We must have found recovery area if there was one. */
 744         if (recovery != 0 && !found_recovery) {
 745                 return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 746                                   "tdb_check: expected a recovery area at %zu",
 747                                   (size_t)recovery);
 748         }
 749
 750         return TDB_SUCCESS;
 751 }
 752
 753 enum TDB_ERROR tdb_check_(struct tdb_context *tdb,
 754                           enum TDB_ERROR (*check)(TDB_DATA key, TDB_DATA data,
 755                                                   void *private),
 756                           void *private)
 757 {
 758         tdb_off_t *fr = NULL, *used = NULL, ft, recovery;
 759         size_t num_free = 0, num_used = 0, num_found = 0, num_ftables = 0;
 760         uint64_t features;
 761         enum TDB_ERROR ecode;
 762
 763         ecode = tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false);
 764         if (ecode != TDB_SUCCESS) {
 765                 return ecode;
 766         }
 767
 768         ecode = tdb_lock_expand(tdb, F_RDLCK);
 769         if (ecode != TDB_SUCCESS) {
 770                 tdb_allrecord_unlock(tdb, F_RDLCK);
 771                 return ecode;
 772         }
 773
 774         ecode = check_header(tdb, &recovery, &features);
 775         if (ecode != TDB_SUCCESS)
 776                 goto out;
 777
 778         /* First we do a linear scan, checking all records. */
 779         ecode = check_linear(tdb, &used, &num_used, &fr, &num_free, features,
 780                              recovery);
 781         if (ecode != TDB_SUCCESS)
 782                 goto out;
 783
 784         for (ft = first_ftable(tdb); ft; ft = next_ftable(tdb, ft)) {
 785                 if (TDB_OFF_IS_ERR(ft)) {
 786                         ecode = ft;
 787                         goto out;
 788                 }
 789                 ecode = check_free_table(tdb, ft, num_ftables, fr, num_free,
 790                                          &num_found);
 791                 if (ecode != TDB_SUCCESS)
 792                         goto out;
 793                 num_ftables++;
 794         }
 795
 796         /* FIXME: Check key uniqueness? */
 797         ecode = check_hash(tdb, used, num_used, num_ftables, check, private);
 798         if (ecode != TDB_SUCCESS)
 799                 goto out;
 800
 801         if (num_found != num_free) {
 802                 ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR,
 803                                    "tdb_check: Not all entries are in"
 804                                    " free table");
 805         }
 806
 807 out:
 808         tdb_allrecord_unlock(tdb, F_RDLCK);
 809         tdb_unlock_expand(tdb, F_RDLCK);
 810         free(fr);
 811         free(used);
 812         return ecode;
 813 }