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