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