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
  37         hash_test = TDB_HASH_MAGIC;
  38         hash_test = tdb_hash(tdb, &hash_test, sizeof(hash_test));
  39         if (tdb->header.hash_test != hash_test) {
  40                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  41                          "check: hash test %llu should be %llu\n",
  42                          tdb->header.hash_test, hash_test);
  43                 return false;
  44         }
  45         if (strcmp(tdb->header.magic_food, TDB_MAGIC_FOOD) != 0) {
  46                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  47                          "check: bad magic '%.*s'\n",
  48                          sizeof(tdb->header.magic_food),
  49                          tdb->header.magic_food);
  50                 return false;
  51         }
  52         if (tdb->header.v.hash_bits < INITIAL_HASH_BITS) {
  53                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  54                          "check: bad hash bits %llu\n",
  55                          (long long)tdb->header.v.hash_bits);
  56                 return false;
  57         }
  58
  59         /* We check hash_off later. */
  60
  61         /* Don't check reserved: they *can* be used later. */
  62         return true;
  63 }
  64
  65 static int off_cmp(const tdb_off_t *a, const tdb_off_t *b)
  66 {
  67         /* Can overflow an int. */
  68         return *a > *b ? 1
  69                 : *a < *b ? -1
  70                 : 0;
  71 }
  72
  73 static bool check_hash_list(struct tdb_context *tdb,
  74                             tdb_off_t used[],
  75                             size_t num_used)
  76 {
  77         struct tdb_used_record rec;
  78         tdb_len_t hashlen, i, num_nonzero;
  79         tdb_off_t h;
  80         size_t num_found;
  81
  82         hashlen = sizeof(tdb_off_t) << tdb->header.v.hash_bits;
  83
  84         if (tdb_read_convert(tdb, tdb->header.v.hash_off - sizeof(rec),
  85                              &rec, sizeof(rec)) == -1)
  86                 return false;
  87
  88         if (rec_data_length(&rec) != hashlen) {
  89                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  90                          "tdb_check: Bad hash table length %llu vs %llu\n",
  91                          (long long)rec_data_length(&rec),
  92                          (long long)hashlen);
  93                 return false;
  94         }
  95         if (rec_key_length(&rec) != 0) {
  96                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
  97                          "tdb_check: Bad hash table key length %llu\n",
  98                          (long long)rec_key_length(&rec));
  99                 return false;
 100         }
 101         if (rec_hash(&rec) != 0) {
 102                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 103                          "tdb_check: Bad hash table hash value %llu\n",
 104                          (long long)rec_hash(&rec));
 105                 return false;
 106         }
 107
 108         num_found = 0;
 109         num_nonzero = 0;
 110         for (i = 0, h = tdb->header.v.hash_off;
 111              i < (1ULL << tdb->header.v.hash_bits);
 112              i++, h += sizeof(tdb_off_t)) {
 113                 tdb_off_t off, *p, pos;
 114                 struct tdb_used_record rec;
 115                 uint64_t hash;
 116
 117                 off = tdb_read_off(tdb, h);
 118                 if (off == TDB_OFF_ERR)
 119                         return false;
 120                 if (!off) {
 121                         num_nonzero = 0;
 122                         continue;
 123                 }
 124                 /* FIXME: Check hash bits */
 125                 p = asearch(&off, used, num_used, off_cmp);
 126                 if (!p) {
 127                         tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 128                                  "tdb_check: Invalid offset %llu in hash\n",
 129                                  (long long)off);
 130                         return false;
 131                 }
 132                 /* Mark it invalid. */
 133                 *p ^= 1;
 134                 num_found++;
 135
 136                 if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1)
 137                         return false;
 138
 139                 /* Check it is hashed correctly. */
 140                 hash = hash_record(tdb, off);
 141
 142                 /* Top bits must match header. */
 143                 if (hash >> (64 - 5) != rec_hash(&rec)) {
 144                         tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 145                                  "tdb_check: Bad hash magic at offset %llu"
 146                                  " (0x%llx vs 0x%llx)\n",
 147                                  (long long)off,
 148                                  (long long)hash, (long long)rec_hash(&rec));
 149                         return false;
 150                 }
 151
 152                 /* It must be in the right place in hash array. */
 153                 pos = hash & ((1ULL << tdb->header.v.hash_bits)-1);
 154                 if (pos < i - num_nonzero || pos > i) {
 155                         /* Could be wrap from end of array?  FIXME: check? */
 156                         if (i != num_nonzero) {
 157                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 158                                          "tdb_check: Bad hash position %llu at"
 159                                          " offset %llu hash 0x%llx\n",
 160                                          (long long)i,
 161                                          (long long)off,
 162                                          (long long)hash);
 163                                 return false;
 164                         }
 165                 }
 166                 num_nonzero++;
 167         }
 168
 169         /* hash table is one of the used blocks. */
 170         if (num_found != num_used - 1) {
 171                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 172                          "tdb_check: Not all entries are in hash\n");
 173                 return false;
 174         }
 175         return true;
 176 }
 177
 178 static bool check_free(struct tdb_context *tdb,
 179                        tdb_off_t off,
 180                        const struct tdb_free_record *frec,
 181                        tdb_off_t prev,
 182                        tdb_off_t zone_off, unsigned int bucket)
 183 {
 184         if (frec_magic(frec) != TDB_FREE_MAGIC) {
 185                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 186                          "tdb_check: offset %llu bad magic 0x%llx\n",
 187                          (long long)off, (long long)frec->magic_and_meta);
 188                 return false;
 189         }
 190         if (tdb->methods->oob(tdb, off
 191                               + frec->data_len-sizeof(struct tdb_used_record),
 192                               true))
 193                 return false;
 194         if (off < zone_off || off >= zone_off + (1ULL<<frec_zone_bits(frec))) {
 195                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 196                          "tdb_check: offset %llu outside zone %llu-%llu\n",
 197                          (long long)off,
 198                          (long long)zone_off,
 199                          (long long)zone_off + (1ULL<<frec_zone_bits(frec)));
 200                 return false;
 201         }
 202         if (size_to_bucket(frec_zone_bits(frec), frec->data_len) != bucket) {
 203                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 204                          "tdb_check: offset %llu in wrong bucket %u vs %u\n",
 205                          (long long)off,
 206                          bucket,
 207                          size_to_bucket(frec_zone_bits(frec), frec->data_len));
 208                 return false;
 209         }
 210         if (prev != frec->prev) {
 211                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 212                          "tdb_check: offset %llu bad prev %llu vs %llu\n",
 213                          (long long)off,
 214                          (long long)prev, (long long)frec->prev);
 215                 return false;
 216         }
 217         return true;
 218 }
 219
 220 static tdb_len_t check_free_list(struct tdb_context *tdb,
 221                                  tdb_off_t zone_off,
 222                                  tdb_off_t free[],
 223                                  size_t num_free,
 224                                  size_t *num_found)
 225 {
 226         struct free_zone_header zhdr;
 227         tdb_off_t h;
 228         unsigned int i;
 229
 230         if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1)
 231                 return TDB_OFF_ERR;
 232
 233         for (i = 0; i <= BUCKETS_FOR_ZONE(zhdr.zone_bits); i++) {
 234                 tdb_off_t off, prev = 0, *p;
 235                 struct tdb_free_record f;
 236
 237                 h = bucket_off(zone_off, i);
 238                 for (off = tdb_read_off(tdb, h); off; off = f.next) {
 239                         if (off == TDB_OFF_ERR)
 240                                 return false;
 241                         if (tdb_read_convert(tdb, off, &f, sizeof(f)))
 242                                 return false;
 243                         if (!check_free(tdb, off, &f, prev, zone_off, i))
 244                                 return false;
 245
 246                         /* FIXME: Check hash bits */
 247                         p = asearch(&off, free, num_free, off_cmp);
 248                         if (!p) {
 249                                 tdb->log(tdb, TDB_DEBUG_ERROR,
 250                                          tdb->log_priv,
 251                                          "tdb_check: Invalid offset"
 252                                          " %llu in free table\n",
 253                                          (long long)off);
 254                                 return false;
 255                         }
 256                         /* Mark it invalid. */
 257                         *p ^= 1;
 258                         (*num_found)++;
 259                         prev = off;
 260                 }
 261         }
 262         return 1ULL << zhdr.zone_bits;
 263 }
 264
 265 static tdb_off_t check_zone(struct tdb_context *tdb, tdb_off_t zone_off,
 266                             tdb_off_t **used, size_t *num_used,
 267                             tdb_off_t **free, size_t *num_free,
 268                             bool *hash_found, unsigned int *max_zone_bits)
 269 {
 270         struct free_zone_header zhdr;
 271         tdb_off_t off, hdrlen;
 272         tdb_len_t len;
 273
 274         if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1)
 275                 return TDB_OFF_ERR;
 276
 277         if (zhdr.zone_bits < INITIAL_ZONE_BITS) {
 278                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 279                          "check: bad zone_bits %llu at zone %llu\n",
 280                          (long long)zhdr.zone_bits, (long long)zone_off);
 281                 return TDB_OFF_ERR;
 282         }
 283
 284         /* Zone bits can only increase... */
 285         if (zhdr.zone_bits > *max_zone_bits)
 286                 *max_zone_bits = zhdr.zone_bits;
 287         else if (zhdr.zone_bits < *max_zone_bits) {
 288                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 289                          "check: small zone_bits %llu at zone %llu\n",
 290                          (long long)zhdr.zone_bits, (long long)zone_off);
 291                 return TDB_OFF_ERR;
 292         }
 293
 294         /* Zone must be within file! */
 295         if (tdb->methods->oob(tdb, zone_off + (1ULL << zhdr.zone_bits), false))
 296                 return TDB_OFF_ERR;
 297
 298         hdrlen = sizeof(zhdr)
 299                 + (BUCKETS_FOR_ZONE(zhdr.zone_bits) + 1) * sizeof(tdb_off_t);
 300         for (off = zone_off + hdrlen;
 301              off < zone_off + (1ULL << zhdr.zone_bits);
 302              off += len) {
 303                 union {
 304                         struct tdb_used_record u;
 305                         struct tdb_free_record f;
 306                 } pad, *p;
 307                 p = tdb_get(tdb, off, &pad, sizeof(pad));
 308                 if (!p)
 309                         return TDB_OFF_ERR;
 310                 if (frec_magic(&p->f) == TDB_FREE_MAGIC) {
 311                         if (frec_zone_bits(&p->f) != zhdr.zone_bits) {
 312                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 313                                          "tdb_check: Bad free zone bits %u"
 314                                          " at offset %llu\n",
 315                                          frec_zone_bits(&p->f),
 316                                          (long long)off);
 317                                 return TDB_OFF_ERR;
 318                         }
 319                         /* This record is free! */
 320                         if (!append(free, num_free, off))
 321                                 return TDB_OFF_ERR;
 322                         len = sizeof(p->u) + p->f.data_len;
 323                         if (off + len > zone_off + (1ULL << zhdr.zone_bits)) {
 324                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 325                                          "tdb_check: free overlength %llu"
 326                                          " at offset %llu\n",
 327                                          (long long)len, (long long)off);
 328                                 return TDB_OFF_ERR;
 329                         }
 330                 } else {
 331                         uint64_t klen, dlen, extra;
 332
 333                         /* This record is used! */
 334                         if (rec_magic(&p->u) != TDB_MAGIC) {
 335                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 336                                          "tdb_check: Bad magic 0x%llx"
 337                                          " at offset %llu\n",
 338                                          (long long)rec_magic(&p->u),
 339                                          (long long)off);
 340                                 return TDB_OFF_ERR;
 341                         }
 342
 343                         if (rec_zone_bits(&p->u) != zhdr.zone_bits) {
 344                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 345                                          "tdb_check: Bad zone bits %u"
 346                                          " at offset %llu\n",
 347                                          rec_zone_bits(&p->u),
 348                                          (long long)off);
 349                                 return TDB_OFF_ERR;
 350                         }
 351
 352                         if (!append(used, num_used, off))
 353                                 return TDB_OFF_ERR;
 354
 355                         klen = rec_key_length(&p->u);
 356                         dlen = rec_data_length(&p->u);
 357                         extra = rec_extra_padding(&p->u);
 358
 359                         len = sizeof(p->u) + klen + dlen + extra;
 360                         if (off + len > zone_off + (1ULL << zhdr.zone_bits)) {
 361                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 362                                          "tdb_check: used overlength %llu"
 363                                          " at offset %llu\n",
 364                                          (long long)len, (long long)off);
 365                                 return TDB_OFF_ERR;
 366                         }
 367
 368                         if (len < sizeof(p->f)) {
 369                                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 370                                          "tdb_check: too short record %llu at"
 371                                          " %llu\n",
 372                                          (long long)len, (long long)off);
 373                                 return TDB_OFF_ERR;
 374                         }
 375
 376                         if (off + sizeof(p->u) == tdb->header.v.hash_off)
 377                                 *hash_found = true;
 378                 }
 379         }
 380         return 1ULL << zhdr.zone_bits;
 381 }
 382
 383 /* FIXME: call check() function. */
 384 int tdb_check(struct tdb_context *tdb,
 385               int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
 386               void *private_data)
 387 {
 388         tdb_off_t *free = NULL, *used = NULL, off;
 389         tdb_len_t len;
 390         size_t num_free = 0, num_used = 0, num_found = 0;
 391         bool hash_found = false;
 392         unsigned max_zone_bits = INITIAL_ZONE_BITS;
 393         uint8_t tailer;
 394
 395         /* FIXME: need more locking? against expansion? */
 396         /* This always ensures the header is uptodate. */
 397         if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0)
 398                 return -1;
 399
 400         if (!check_header(tdb))
 401                 goto fail;
 402
 403         /* First we do a linear scan, checking all records. */
 404         for (off = sizeof(struct tdb_header);
 405              off < tdb->map_size - 1;
 406              off += len) {
 407                 len = check_zone(tdb, off, &used, &num_used, &free, &num_free,
 408                                  &hash_found, &max_zone_bits);
 409                 if (len == TDB_OFF_ERR)
 410                         goto fail;
 411         }
 412
 413         /* Check tailer. */
 414         if (tdb->methods->read(tdb, tdb->map_size - 1, &tailer, 1) == -1)
 415                 goto fail;
 416         if (tailer != max_zone_bits) {
 417                 tdb->ecode = TDB_ERR_CORRUPT;
 418                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 419                          "tdb_check: Bad tailer value %u vs %u\n", tailer,
 420                          max_zone_bits);
 421                 goto fail;
 422         }
 423
 424         if (!hash_found) {
 425                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 426                          "tdb_check: hash table not found at %llu\n",
 427                          (long long)tdb->header.v.hash_off);
 428                 goto fail;
 429         }
 430
 431         /* FIXME: Check key uniqueness? */
 432         if (!check_hash_list(tdb, used, num_used))
 433                 goto fail;
 434
 435         for (off = sizeof(struct tdb_header);
 436              off < tdb->map_size - 1;
 437              off += len) {
 438                 len = check_free_list(tdb, off, free, num_free, &num_found);
 439                 if (len == TDB_OFF_ERR)
 440                         goto fail;
 441         }
 442         if (num_found != num_free) {
 443                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
 444                          "tdb_check: Not all entries are in free table\n");
 445                 return false;
 446         }
 447
 448         tdb_allrecord_unlock(tdb, F_RDLCK);
 449         return 0;
 450
 451 fail:
 452         tdb_allrecord_unlock(tdb, F_RDLCK);
 453         return -1;
 454 }