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