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