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);
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);
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);
70 if ((1ULL << tdb->header.v.zone_bits) * tdb->header.v.num_zones
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);
80 /* We check hash_off and free_off later. */
82 /* Don't check reserved: they *can* be used later. */
86 static int off_cmp(const tdb_off_t *a, const tdb_off_t *b)
88 /* Can overflow an int. */
94 static bool check_hash_list(struct tdb_context *tdb,
98 struct tdb_used_record rec;
99 tdb_len_t hashlen, i, num_nonzero;
103 hashlen = sizeof(tdb_off_t) << tdb->header.v.hash_bits;
105 if (tdb_read_convert(tdb, tdb->header.v.hash_off - sizeof(rec),
106 &rec, sizeof(rec)) == -1)
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),
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));
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));
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;
138 off = tdb_read_off(tdb, h);
139 if (off == TDB_OFF_ERR)
145 /* FIXME: Check hash bits */
146 p = asearch(&off, used, num_used, off_cmp);
148 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
149 "tdb_check: Invalid offset %llu in hash\n",
153 /* Mark it invalid. */
157 if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1)
160 /* Check it is hashed correctly. */
161 hash = hash_record(tdb, off);
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",
169 (long long)hash, (long long)rec_hash(&rec));
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",
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");
199 static bool check_free(struct tdb_context *tdb,
201 const struct tdb_free_record *frec,
203 tdb_off_t zone, unsigned int bucket)
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);
211 if (tdb->methods->oob(tdb, off
212 + frec->data_len-sizeof(struct tdb_used_record),
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",
219 (long long)zone, (long long)zone_of(tdb, off));
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",
226 bucket, size_to_bucket(tdb, frec->data_len));
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",
233 (long long)prev, (long long)frec->prev);
239 static bool check_free_list(struct tdb_context *tdb,
243 struct tdb_used_record rec;
244 tdb_len_t freelen, i, j;
248 freelen = sizeof(tdb_off_t) * tdb->header.v.num_zones
249 * (tdb->header.v.free_buckets + 1);
251 if (tdb_read_convert(tdb, tdb->header.v.free_off - sizeof(rec),
252 &rec, sizeof(rec)) == -1)
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),
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));
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));
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;
283 for (off = tdb_read_off(tdb, h); off; off = f.next) {
284 if (off == TDB_OFF_ERR)
286 if (tdb_read_convert(tdb, off, &f, sizeof(f)))
288 if (!check_free(tdb, off, &f, prev, i, j))
291 /* FIXME: Check hash bits */
292 p = asearch(&off, free, num_free, off_cmp);
294 tdb->log(tdb, TDB_DEBUG_ERROR,
296 "tdb_check: Invalid offset"
297 " %llu in free table\n",
301 /* Mark it invalid. */
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");
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),
321 tdb_off_t *free = NULL, *used = NULL, off;
323 size_t num_free = 0, num_used = 0;
324 bool hash_found = false, free_found = false;
326 /* This always ensures the header is uptodate. */
327 if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0)
330 if (!check_header(tdb))
333 /* First we do a linear scan, checking all records. */
334 for (off = sizeof(struct tdb_header);
338 struct tdb_used_record u;
339 struct tdb_free_record f;
341 p = tdb_get(tdb, off, &pad, sizeof(pad));
344 if (p->f.magic == TDB_FREE_MAGIC) {
345 /* This record is free! */
346 if (!append(&free, &num_free, off))
348 len = sizeof(p->u) + p->f.data_len;
349 if (tdb->methods->oob(tdb, off + len, false))
352 uint64_t klen, dlen, extra;
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"
359 (long long)rec_magic(&p->u),
364 if (!append(&used, &num_used, off))
367 klen = rec_key_length(&p->u);
368 dlen = rec_data_length(&p->u);
369 extra = rec_extra_padding(&p->u);
371 len = sizeof(p->u) + klen + dlen + extra;
372 if (tdb->methods->oob(tdb, off + len, false))
375 if (off + sizeof(p->u) == tdb->header.v.hash_off) {
377 } else if (off + sizeof(p->u)
378 == tdb->header.v.free_off) {
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);
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);
398 /* FIXME: Check key uniqueness? */
399 if (!check_hash_list(tdb, used, num_used))
402 if (!check_free_list(tdb, free, num_free))
405 tdb_allrecord_unlock(tdb, F_RDLCK);
409 tdb_allrecord_unlock(tdb, F_RDLCK);