X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Fcheck.c;h=41acae4e9de3aa13616fadfdd6e6696c1030849f;hp=8c7ed1c4928e3d815dc5a85b7471ee70d3a17438;hb=587982955ca9c61363d6e3004622ee97eda80e4b;hpb=2523e67f154c3f8614a2ddca2cd0170d321a27d4 diff --git a/ccan/tdb2/check.c b/ccan/tdb2/check.c index 8c7ed1c4..41acae4e 100644 --- a/ccan/tdb2/check.c +++ b/ccan/tdb2/check.c @@ -1,7 +1,7 @@ - /* + /* Trivial Database 2: free list/block handling Copyright (C) Rusty Russell 2010 - + This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either @@ -43,7 +43,7 @@ static bool check_header(struct tdb_context *tdb, tdb_off_t *recovery) hash_test = TDB_HASH_MAGIC; hash_test = tdb_hash(tdb, &hash_test, sizeof(hash_test)); if (hdr.hash_test != hash_test) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "check: hash test %llu should be %llu", (long long)hdr.hash_test, (long long)hash_test); @@ -51,7 +51,7 @@ static bool check_header(struct tdb_context *tdb, tdb_off_t *recovery) } if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "check: bad magic '%.*s'", (unsigned)sizeof(hdr.magic_food), hdr.magic_food); return false; @@ -60,7 +60,7 @@ static bool check_header(struct tdb_context *tdb, tdb_off_t *recovery) *recovery = hdr.recovery; if (*recovery) { if (*recovery < sizeof(hdr) || *recovery > tdb->map_size) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: invalid recovery offset %zu", (size_t)*recovery); return false; @@ -95,21 +95,28 @@ static bool check_hash_chain(struct tdb_context *tdb, if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1) return false; + if (rec_magic(&rec) != TDB_CHAIN_MAGIC) { + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "tdb_check: Bad hash chain magic %llu", + (long long)rec_magic(&rec)); + return false; + } + if (rec_data_length(&rec) != sizeof(struct tdb_chain)) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash chain length %llu vs %zu", (long long)rec_data_length(&rec), sizeof(struct tdb_chain)); return false; } if (rec_key_length(&rec) != 0) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash chain key length %llu", (long long)rec_key_length(&rec)); return false; } - if (rec_hash(&rec) != 2) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + if (rec_hash(&rec) != 0) { + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash chain hash value %llu", (long long)rec_hash(&rec)); return false; @@ -149,9 +156,15 @@ static bool check_hash_record(struct tdb_context *tdb, if (tdb_read_convert(tdb, off, &rec, sizeof(rec)) == -1) return false; + if (rec_magic(&rec) != TDB_HTABLE_MAGIC) { + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "tdb_check: Bad hash table magic %llu", + (long long)rec_magic(&rec)); + return false; + } if (rec_data_length(&rec) != sizeof(tdb_off_t) << TDB_SUBLEVEL_HASH_BITS) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash table length %llu vs %llu", (long long)rec_data_length(&rec), (long long)sizeof(tdb_off_t) @@ -159,13 +172,13 @@ static bool check_hash_record(struct tdb_context *tdb, return false; } if (rec_key_length(&rec) != 0) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash table key length %llu", (long long)rec_key_length(&rec)); return false; } if (rec_hash(&rec) != 0) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Bad hash table hash value %llu", (long long)rec_hash(&rec)); return false; @@ -227,7 +240,7 @@ static bool check_hash_tree(struct tdb_context *tdb, p = asearch(&off, used, num_used, off_cmp); if (!p) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: Invalid offset %llu " "in hash", (long long)off); goto fail; @@ -240,7 +253,7 @@ static bool check_hash_tree(struct tdb_context *tdb, /* Chained entries are unordered. */ if (is_subhash(group[b])) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: Invalid chain" " entry subhash"); goto fail; @@ -248,7 +261,7 @@ static bool check_hash_tree(struct tdb_context *tdb, h = hash_record(tdb, off); if (h != hprefix) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "check: bad hash chain" " placement" " 0x%llx vs 0x%llx", @@ -264,7 +277,7 @@ static bool check_hash_tree(struct tdb_context *tdb, if (is_subhash(group[b])) { uint64_t subprefix; - subprefix = (hprefix + subprefix = (hprefix << (group_bits + TDB_HASH_GROUP_BITS)) + g * (1 << TDB_HASH_GROUP_BITS) + b; @@ -287,7 +300,7 @@ static bool check_hash_tree(struct tdb_context *tdb, if (get_bits(h, hprefix_bits, &used_bits) != hprefix && hprefix_bits) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "check: bad hash placement" " 0x%llx vs 0x%llx", (long long)h, (long long)hprefix); @@ -297,7 +310,7 @@ static bool check_hash_tree(struct tdb_context *tdb, /* Does it belong in this group? */ if (get_bits(h, group_bits, &used_bits) != g) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "check: bad group %llu vs %u", (long long)h, g); goto fail; @@ -309,7 +322,7 @@ static bool check_hash_tree(struct tdb_context *tdb, != bucket) { used_bits -= TDB_HASH_GROUP_BITS; tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "check: bad bucket %u vs %u", (unsigned)get_bits(h, TDB_HASH_GROUP_BITS, @@ -325,7 +338,7 @@ static bool check_hash_tree(struct tdb_context *tdb, i = (i + 1) % (1 << TDB_HASH_GROUP_BITS)) { if (group[i] == 0) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "check: bad group placement" " %u vs %u", b, bucket); @@ -339,7 +352,7 @@ static bool check_hash_tree(struct tdb_context *tdb, /* Bottom bits must match header. */ if ((h & ((1 << 11)-1)) != rec_hash(&rec)) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: Bad hash magic at" " offset %llu (0x%llx vs 0x%llx)", (long long)off, @@ -376,12 +389,12 @@ fail: static bool check_hash(struct tdb_context *tdb, tdb_off_t used[], - size_t num_used, size_t num_flists, + size_t num_used, size_t num_ftables, int (*check)(TDB_DATA, TDB_DATA, void *), void *private_data) { - /* Free lists also show up as used. */ - size_t num_found = num_flists; + /* Free tables also show up as used. */ + size_t num_found = num_ftables; if (!check_hash_tree(tdb, offsetof(struct tdb_header, hashtable), TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS, @@ -390,7 +403,7 @@ static bool check_hash(struct tdb_context *tdb, return false; if (num_found != num_used) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Not all entries are in hash"); return false; } @@ -400,18 +413,19 @@ static bool check_hash(struct tdb_context *tdb, static bool check_free(struct tdb_context *tdb, tdb_off_t off, const struct tdb_free_record *frec, - tdb_off_t prev, unsigned int flist, unsigned int bucket) + tdb_off_t prev, unsigned int ftable, + unsigned int bucket) { if (frec_magic(frec) != TDB_FREE_MAGIC) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: offset %llu bad magic 0x%llx", (long long)off, (long long)frec->magic_and_prev); return false; } - if (frec_flist(frec) != flist) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, - "tdb_check: offset %llu bad freelist %u", - (long long)off, frec_flist(frec)); + if (frec_ftable(frec) != ftable) { + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "tdb_check: offset %llu bad freetable %u", + (long long)off, frec_ftable(frec)); return false; } @@ -420,14 +434,14 @@ static bool check_free(struct tdb_context *tdb, false)) return false; if (size_to_bucket(frec_len(frec)) != bucket) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: offset %llu in wrong bucket %u vs %u", (long long)off, bucket, size_to_bucket(frec_len(frec))); return false; } if (prev != frec_prev(frec)) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: offset %llu bad prev %llu vs %llu", (long long)off, (long long)prev, (long long)frec_len(frec)); @@ -435,27 +449,27 @@ static bool check_free(struct tdb_context *tdb, } return true; } - -static bool check_free_list(struct tdb_context *tdb, - tdb_off_t flist_off, - unsigned flist_num, - tdb_off_t free[], - size_t num_free, - size_t *num_found) + +static bool check_free_table(struct tdb_context *tdb, + tdb_off_t ftable_off, + unsigned ftable_num, + tdb_off_t fr[], + size_t num_free, + size_t *num_found) { - struct tdb_freelist flist; + struct tdb_freetable ft; tdb_off_t h; unsigned int i; - if (tdb_read_convert(tdb, flist_off, &flist, sizeof(flist)) == -1) + if (tdb_read_convert(tdb, ftable_off, &ft, sizeof(ft)) == -1) return false; - if (rec_magic(&flist.hdr) != TDB_MAGIC - || rec_key_length(&flist.hdr) != 0 - || rec_data_length(&flist.hdr) != sizeof(flist) - sizeof(flist.hdr) - || rec_hash(&flist.hdr) != 1) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, - "tdb_check: Invalid header on free list"); + if (rec_magic(&ft.hdr) != TDB_FTABLE_MAGIC + || rec_key_length(&ft.hdr) != 0 + || rec_data_length(&ft.hdr) != sizeof(ft) - sizeof(ft.hdr) + || rec_hash(&ft.hdr) != 0) { + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "tdb_check: Invalid header on free table"); return false; } @@ -463,20 +477,20 @@ static bool check_free_list(struct tdb_context *tdb, tdb_off_t off, prev = 0, *p; struct tdb_free_record f; - h = bucket_off(flist_off, i); + h = bucket_off(ftable_off, i); for (off = tdb_read_off(tdb, h); off; off = f.next) { if (off == TDB_OFF_ERR) return false; if (tdb_read_convert(tdb, off, &f, sizeof(f))) return false; - if (!check_free(tdb, off, &f, prev, flist_num, i)) + if (!check_free(tdb, off, &f, prev, ftable_num, i)) return false; /* FIXME: Check hash bits */ - p = asearch(&off, free, num_free, off_cmp); + p = asearch(&off, fr, num_free, off_cmp); if (!p) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: Invalid offset" " %llu in free table", (long long)off); @@ -498,7 +512,7 @@ size_t dead_space(struct tdb_context *tdb, tdb_off_t off) for (len = 0; off + len < tdb->map_size; len++) { char c; - if (tdb->methods->read(tdb, off, &c, 1)) + if (tdb->methods->tread(tdb, off, &c, 1)) return 0; if (c != 0 && c != 0x43) break; @@ -508,7 +522,7 @@ size_t dead_space(struct tdb_context *tdb, tdb_off_t off) static bool check_linear(struct tdb_context *tdb, tdb_off_t **used, size_t *num_used, - tdb_off_t **free, size_t *num_free, + tdb_off_t **fr, size_t *num_free, tdb_off_t recovery) { tdb_off_t off; @@ -538,14 +552,14 @@ static bool check_linear(struct tdb_context *tdb, len = dead_space(tdb, off); if (len < sizeof(rec.r)) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: invalid dead" " space at %zu", (size_t)off); return false; } - tdb_logerr(tdb, TDB_SUCCESS, TDB_DEBUG_WARNING, + tdb_logerr(tdb, TDB_SUCCESS, TDB_LOG_WARNING, "Dead space at %zu-%zu (of %zu)", (size_t)off, (size_t)(off + len), (size_t)tdb->map_size); @@ -555,7 +569,7 @@ static bool check_linear(struct tdb_context *tdb, return false; if (recovery != off) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: unexpected recovery" " record at offset %zu", (size_t)off); @@ -563,14 +577,14 @@ static bool check_linear(struct tdb_context *tdb, } if (rec.r.len > rec.r.max_len) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: invalid recovery length" " %zu", (size_t)rec.r.len); return false; } if (rec.r.eof > tdb->map_size) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: invalid old EOF" " %zu", (size_t)rec.r.eof); return false; @@ -581,33 +595,36 @@ static bool check_linear(struct tdb_context *tdb, len = sizeof(rec.u) + frec_len(&rec.f); if (off + len > tdb->map_size) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: free overlength %llu" " at offset %llu", (long long)len, (long long)off); return false; } /* This record should be in free lists. */ - if (frec_flist(&rec.f) != TDB_FLIST_NONE - && !append(free, num_free, off)) + if (frec_ftable(&rec.f) != TDB_FTABLE_NONE + && !append(fr, num_free, off)) { + tdb_logerr(tdb, TDB_ERR_OOM, + TDB_LOG_ERROR, + "tdb_check: tracking %zu'th" + " free record.", *num_free); return false; - } else { + } + } else if (rec_magic(&rec.u) == TDB_USED_MAGIC + || rec_magic(&rec.u) == TDB_CHAIN_MAGIC + || rec_magic(&rec.u) == TDB_HTABLE_MAGIC + || rec_magic(&rec.u) == TDB_FTABLE_MAGIC) { uint64_t klen, dlen, extra; /* This record is used! */ - if (rec_magic(&rec.u) != TDB_MAGIC) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, - "tdb_check: Bad magic 0x%llx" - " at offset %zu", - (long long)rec_magic(&rec.u), - (size_t)off); + if (!append(used, num_used, off)) { + tdb_logerr(tdb, TDB_ERR_OOM, + TDB_LOG_ERROR, + "tdb_check: tracking %zu'th" + " used record.", *num_used); return false; } - if (!append(used, num_used, off)) - return false; - klen = rec_key_length(&rec.u); dlen = rec_data_length(&rec.u); extra = rec_extra_padding(&rec.u); @@ -615,7 +632,7 @@ static bool check_linear(struct tdb_context *tdb, len = sizeof(rec.u) + klen + dlen + extra; if (off + len > tdb->map_size) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: used overlength %llu" " at offset %llu", (long long)len, (long long)off); @@ -624,18 +641,24 @@ static bool check_linear(struct tdb_context *tdb, if (len < sizeof(rec.f)) { tdb_logerr(tdb, TDB_ERR_CORRUPT, - TDB_DEBUG_ERROR, + TDB_LOG_ERROR, "tdb_check: too short record %llu" " at %llu", (long long)len, (long long)off); return false; } + } else { + tdb_logerr(tdb, TDB_ERR_CORRUPT, + TDB_LOG_ERROR, + "tdb_check: Bad magic 0x%llx at offset %zu", + (long long)rec_magic(&rec.u), (size_t)off); + return false; } } /* We must have found recovery area if there was one. */ if (recovery != 0 && !found_recovery) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: expected a recovery area at %zu", (size_t)recovery); return false; @@ -648,8 +671,8 @@ int tdb_check(struct tdb_context *tdb, int (*check)(TDB_DATA key, TDB_DATA data, void *private_data), void *private_data) { - tdb_off_t *free = NULL, *used = NULL, flist, recovery; - size_t num_free = 0, num_used = 0, num_found = 0, num_flists = 0; + tdb_off_t *fr = NULL, *used = NULL, ft, recovery; + size_t num_free = 0, num_used = 0, num_found = 0, num_ftables = 0; if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0) return -1; @@ -663,33 +686,37 @@ int tdb_check(struct tdb_context *tdb, goto fail; /* First we do a linear scan, checking all records. */ - if (!check_linear(tdb, &used, &num_used, &free, &num_free, recovery)) + if (!check_linear(tdb, &used, &num_used, &fr, &num_free, recovery)) goto fail; - for (flist = first_flist(tdb); flist; flist = next_flist(tdb, flist)) { - if (flist == TDB_OFF_ERR) + for (ft = first_ftable(tdb); ft; ft = next_ftable(tdb, ft)) { + if (ft == TDB_OFF_ERR) goto fail; - if (!check_free_list(tdb, flist, num_flists, free, num_free, - &num_found)) + if (!check_free_table(tdb, ft, num_ftables, fr, num_free, + &num_found)) goto fail; - num_flists++; + num_ftables++; } /* FIXME: Check key uniqueness? */ - if (!check_hash(tdb, used, num_used, num_flists, check, private_data)) + if (!check_hash(tdb, used, num_used, num_ftables, check, private_data)) goto fail; if (num_found != num_free) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_ERROR, + tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, "tdb_check: Not all entries are in free table"); return -1; } tdb_allrecord_unlock(tdb, F_RDLCK); tdb_unlock_expand(tdb, F_RDLCK); + free(fr); + free(used); return 0; fail: + free(fr); + free(used); tdb_allrecord_unlock(tdb, F_RDLCK); tdb_unlock_expand(tdb, F_RDLCK); return -1;