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