2 Trivial Database 2: free list/block handling
3 Copyright (C) Rusty Russell 2010
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.
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.
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/>.
19 #include <ccan/likely/likely.h>
20 #include <ccan/asearch/asearch.h>
22 /* We keep an ordered array of offsets. */
23 static bool append(tdb_off_t **arr, size_t *num, tdb_off_t off)
25 tdb_off_t *new = realloc(*arr, (*num + 1) * sizeof(tdb_off_t));
33 static bool check_header(struct tdb_context *tdb)
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);
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);
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);
59 /* We check hash_off later. */
61 /* Don't check reserved: they *can* be used later. */
65 static int off_cmp(const tdb_off_t *a, const tdb_off_t *b)
67 /* Can overflow an int. */
73 static bool check_hash_list(struct tdb_context *tdb,
77 struct tdb_used_record rec;
78 tdb_len_t hashlen, i, num_nonzero;
82 hashlen = sizeof(tdb_off_t) << tdb->header.v.hash_bits;
84 if (tdb_read_convert(tdb, tdb->header.v.hash_off - sizeof(rec),
85 &rec, sizeof(rec)) == -1)
88 if (rec_data_length(&rec) != hashlen) {
89 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
90 "tdb_check: Bad hash table length %llu vs %llu\n",
91 (long long)rec_data_length(&rec),
95 if (rec_key_length(&rec) != 0) {
96 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
97 "tdb_check: Bad hash table key length %llu\n",
98 (long long)rec_key_length(&rec));
101 if (rec_hash(&rec) != 0) {
102 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
103 "tdb_check: Bad hash table hash value %llu\n",
104 (long long)rec_hash(&rec));
110 for (i = 0, h = tdb->header.v.hash_off;
111 i < (1ULL << tdb->header.v.hash_bits);
112 i++, h += sizeof(tdb_off_t)) {
113 tdb_off_t off, *p, pos;
114 struct tdb_used_record rec;
117 off = tdb_read_off(tdb, h);
118 if (off == TDB_OFF_ERR)
124 /* FIXME: Check hash bits */
125 p = asearch(&off, used, num_used, off_cmp);
127 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
128 "tdb_check: Invalid offset %llu in hash\n",
132 /* Mark it invalid. */
136 if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1)
139 /* Check it is hashed correctly. */
140 hash = hash_record(tdb, off);
142 /* Top bits must match header. */
143 if (hash >> (64 - 5) != rec_hash(&rec)) {
144 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
145 "tdb_check: Bad hash magic at offset %llu"
146 " (0x%llx vs 0x%llx)\n",
148 (long long)hash, (long long)rec_hash(&rec));
152 /* It must be in the right place in hash array. */
153 pos = hash & ((1ULL << tdb->header.v.hash_bits)-1);
154 if (pos < i - num_nonzero || pos > i) {
155 /* Could be wrap from end of array? FIXME: check? */
156 if (i != num_nonzero) {
157 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
158 "tdb_check: Bad hash position %llu at"
159 " offset %llu hash 0x%llx\n",
169 /* hash table is one of the used blocks. */
170 if (num_found != num_used - 1) {
171 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
172 "tdb_check: Not all entries are in hash\n");
178 static bool check_free(struct tdb_context *tdb,
180 const struct tdb_free_record *frec,
182 tdb_off_t zone_off, unsigned int bucket)
184 if (frec_magic(frec) != TDB_FREE_MAGIC) {
185 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
186 "tdb_check: offset %llu bad magic 0x%llx\n",
187 (long long)off, (long long)frec->magic_and_meta);
190 if (tdb->methods->oob(tdb, off
191 + frec->data_len-sizeof(struct tdb_used_record),
194 if (off < zone_off || off >= zone_off + (1ULL<<frec_zone_bits(frec))) {
195 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
196 "tdb_check: offset %llu outside zone %llu-%llu\n",
199 (long long)zone_off + (1ULL<<frec_zone_bits(frec)));
202 if (size_to_bucket(frec_zone_bits(frec), frec->data_len) != bucket) {
203 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
204 "tdb_check: offset %llu in wrong bucket %u vs %u\n",
207 size_to_bucket(frec_zone_bits(frec), frec->data_len));
210 if (prev != frec->prev) {
211 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
212 "tdb_check: offset %llu bad prev %llu vs %llu\n",
214 (long long)prev, (long long)frec->prev);
220 static tdb_len_t check_free_list(struct tdb_context *tdb,
226 struct free_zone_header zhdr;
230 if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1)
233 for (i = 0; i <= BUCKETS_FOR_ZONE(zhdr.zone_bits); i++) {
234 tdb_off_t off, prev = 0, *p;
235 struct tdb_free_record f;
237 h = bucket_off(zone_off, i);
238 for (off = tdb_read_off(tdb, h); off; off = f.next) {
239 if (off == TDB_OFF_ERR)
241 if (tdb_read_convert(tdb, off, &f, sizeof(f)))
243 if (!check_free(tdb, off, &f, prev, zone_off, i))
246 /* FIXME: Check hash bits */
247 p = asearch(&off, free, num_free, off_cmp);
249 tdb->log(tdb, TDB_DEBUG_ERROR,
251 "tdb_check: Invalid offset"
252 " %llu in free table\n",
256 /* Mark it invalid. */
262 return 1ULL << zhdr.zone_bits;
265 static tdb_off_t check_zone(struct tdb_context *tdb, tdb_off_t zone_off,
266 tdb_off_t **used, size_t *num_used,
267 tdb_off_t **free, size_t *num_free,
268 bool *hash_found, unsigned int *max_zone_bits)
270 struct free_zone_header zhdr;
271 tdb_off_t off, hdrlen;
274 if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1)
277 if (zhdr.zone_bits < INITIAL_ZONE_BITS) {
278 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
279 "check: bad zone_bits %llu at zone %llu\n",
280 (long long)zhdr.zone_bits, (long long)zone_off);
284 /* Zone bits can only increase... */
285 if (zhdr.zone_bits > *max_zone_bits)
286 *max_zone_bits = zhdr.zone_bits;
287 else if (zhdr.zone_bits < *max_zone_bits) {
288 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
289 "check: small zone_bits %llu at zone %llu\n",
290 (long long)zhdr.zone_bits, (long long)zone_off);
294 /* Zone must be within file! */
295 if (tdb->methods->oob(tdb, zone_off + (1ULL << zhdr.zone_bits), false))
298 hdrlen = sizeof(zhdr)
299 + (BUCKETS_FOR_ZONE(zhdr.zone_bits) + 1) * sizeof(tdb_off_t);
300 for (off = zone_off + hdrlen;
301 off < zone_off + (1ULL << zhdr.zone_bits);
304 struct tdb_used_record u;
305 struct tdb_free_record f;
307 p = tdb_get(tdb, off, &pad, sizeof(pad));
310 if (frec_magic(&p->f) == TDB_FREE_MAGIC) {
311 if (frec_zone_bits(&p->f) != zhdr.zone_bits) {
312 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
313 "tdb_check: Bad free zone bits %u"
315 frec_zone_bits(&p->f),
319 /* This record is free! */
320 if (!append(free, num_free, off))
322 len = sizeof(p->u) + p->f.data_len;
323 if (off + len > zone_off + (1ULL << zhdr.zone_bits)) {
324 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
325 "tdb_check: free overlength %llu"
327 (long long)len, (long long)off);
331 uint64_t klen, dlen, extra;
333 /* This record is used! */
334 if (rec_magic(&p->u) != TDB_MAGIC) {
335 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
336 "tdb_check: Bad magic 0x%llx"
338 (long long)rec_magic(&p->u),
343 if (rec_zone_bits(&p->u) != zhdr.zone_bits) {
344 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
345 "tdb_check: Bad zone bits %u"
347 rec_zone_bits(&p->u),
352 if (!append(used, num_used, off))
355 klen = rec_key_length(&p->u);
356 dlen = rec_data_length(&p->u);
357 extra = rec_extra_padding(&p->u);
359 len = sizeof(p->u) + klen + dlen + extra;
360 if (off + len > zone_off + (1ULL << zhdr.zone_bits)) {
361 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
362 "tdb_check: used overlength %llu"
364 (long long)len, (long long)off);
368 if (len < sizeof(p->f)) {
369 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
370 "tdb_check: too short record %llu at"
372 (long long)len, (long long)off);
376 if (off + sizeof(p->u) == tdb->header.v.hash_off)
380 return 1ULL << zhdr.zone_bits;
383 /* FIXME: call check() function. */
384 int tdb_check(struct tdb_context *tdb,
385 int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
388 tdb_off_t *free = NULL, *used = NULL, off;
390 size_t num_free = 0, num_used = 0, num_found = 0;
391 bool hash_found = false;
392 unsigned max_zone_bits = INITIAL_ZONE_BITS;
395 /* FIXME: need more locking? against expansion? */
396 /* This always ensures the header is uptodate. */
397 if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0)
400 if (!check_header(tdb))
403 /* First we do a linear scan, checking all records. */
404 for (off = sizeof(struct tdb_header);
405 off < tdb->map_size - 1;
407 len = check_zone(tdb, off, &used, &num_used, &free, &num_free,
408 &hash_found, &max_zone_bits);
409 if (len == TDB_OFF_ERR)
414 if (tdb->methods->read(tdb, tdb->map_size - 1, &tailer, 1) == -1)
416 if (tailer != max_zone_bits) {
417 tdb->ecode = TDB_ERR_CORRUPT;
418 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
419 "tdb_check: Bad tailer value %u vs %u\n", tailer,
425 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
426 "tdb_check: hash table not found at %llu\n",
427 (long long)tdb->header.v.hash_off);
431 /* FIXME: Check key uniqueness? */
432 if (!check_hash_list(tdb, used, num_used))
435 for (off = sizeof(struct tdb_header);
436 off < tdb->map_size - 1;
438 len = check_free_list(tdb, off, free, num_free, &num_found);
439 if (len == TDB_OFF_ERR)
442 if (num_found != num_free) {
443 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
444 "tdb_check: Not all entries are in free table\n");
448 tdb_allrecord_unlock(tdb, F_RDLCK);
452 tdb_allrecord_unlock(tdb, F_RDLCK);