X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Fcheck.c;h=c7d83837c9772b70c6e47c359993a94c3e21c0d3;hp=1ce75be065f4317b1e63a4c2bc1afb47e446478b;hb=c84c65774a4d4e2b247f47a6e20e474e51aec738;hpb=6804501c350181dea8f531142b28c620b70edbd9 diff --git a/ccan/tdb2/check.c b/ccan/tdb2/check.c index 1ce75be0..c7d83837 100644 --- a/ccan/tdb2/check.c +++ b/ccan/tdb2/check.c @@ -30,7 +30,7 @@ static bool append(tdb_off_t **arr, size_t *num, tdb_off_t off) return true; } -static bool check_header(struct tdb_context *tdb) +static bool check_header(struct tdb_context *tdb, tdb_off_t *recovery) { uint64_t hash_test; struct tdb_header hdr; @@ -45,17 +45,28 @@ static bool check_header(struct tdb_context *tdb) if (hdr.hash_test != hash_test) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "check: hash test %llu should be %llu\n", - hdr.hash_test, hash_test); + (long long)hdr.hash_test, + (long long)hash_test); return false; } if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "check: bad magic '%.*s'\n", - sizeof(hdr.magic_food), hdr.magic_food); + (unsigned)sizeof(hdr.magic_food), hdr.magic_food); return false; } + *recovery = hdr.recovery; + if (*recovery) { + if (*recovery < sizeof(hdr) || *recovery > tdb->map_size) { + tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, + "tdb_check: invalid recovery offset %zu\n", + (size_t)*recovery); + return false; + } + } + /* Don't check reserved: they *can* be used later. */ return true; } @@ -66,7 +77,9 @@ static bool check_hash_tree(struct tdb_context *tdb, unsigned hprefix_bits, tdb_off_t used[], size_t num_used, - size_t *num_found); + size_t *num_found, + int (*check)(TDB_DATA, TDB_DATA, void *), + void *private_data); static bool check_hash_record(struct tdb_context *tdb, tdb_off_t off, @@ -74,7 +87,9 @@ static bool check_hash_record(struct tdb_context *tdb, unsigned hprefix_bits, tdb_off_t used[], size_t num_used, - size_t *num_found) + size_t *num_found, + int (*check)(TDB_DATA, TDB_DATA, void *), + void *private_data) { struct tdb_used_record rec; @@ -106,7 +121,7 @@ static bool check_hash_record(struct tdb_context *tdb, return check_hash_tree(tdb, off, TDB_SUBLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS, hprefix, hprefix_bits, - used, num_used, num_found); + used, num_used, num_found, check, private_data); } static int off_cmp(const tdb_off_t *a, const tdb_off_t *b) @@ -130,7 +145,9 @@ static bool check_hash_tree(struct tdb_context *tdb, unsigned hprefix_bits, tdb_off_t used[], size_t num_used, - size_t *num_found) + size_t *num_found, + int (*check)(TDB_DATA, TDB_DATA, void *), + void *private_data) { unsigned int g, b; const tdb_off_t *hash; @@ -177,7 +194,8 @@ static bool check_hash_tree(struct tdb_context *tdb, hprefix_bits + group_bits + TDB_HASH_GROUP_BITS, - used, num_used, num_found)) + used, num_used, num_found, + check, private_data)) goto fail; continue; } @@ -236,7 +254,7 @@ static bool check_hash_tree(struct tdb_context *tdb, goto fail; /* Bottom bits must match header. */ - if ((h & ((1 << 5)-1)) != rec_hash(&rec)) { + if ((h & ((1 << 11)-1)) != rec_hash(&rec)) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "tdb_check: Bad hash magic at" " offset %llu (0x%llx vs 0x%llx)\n", @@ -245,6 +263,22 @@ static bool check_hash_tree(struct tdb_context *tdb, (long long)rec_hash(&rec)); goto fail; } + + if (check) { + TDB_DATA key, data; + key.dsize = rec_key_length(&rec); + data.dsize = rec_data_length(&rec); + key.dptr = (void *)tdb_access_read(tdb, + off + sizeof(rec), + key.dsize + data.dsize, + false); + if (!key.dptr) + goto fail; + data.dptr = key.dptr + key.dsize; + if (check(key, data, private_data) != 0) + goto fail; + tdb_access_release(tdb, key.dptr); + } } } tdb_access_release(tdb, hash); @@ -257,13 +291,17 @@ fail: static bool check_hash(struct tdb_context *tdb, tdb_off_t used[], - size_t num_used) + size_t num_used, size_t num_flists, + int (*check)(TDB_DATA, TDB_DATA, void *), + void *private_data) { - size_t num_found = 0; + /* Free lists also show up as used. */ + size_t num_found = num_flists; if (!check_hash_tree(tdb, offsetof(struct tdb_header, hashtable), TDB_TOPLEVEL_HASH_BITS-TDB_HASH_GROUP_BITS, - 0, 0, used, num_used, &num_found)) + 0, 0, used, num_used, &num_found, + check, private_data)) return false; if (num_found != num_used) { @@ -277,8 +315,7 @@ 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, - tdb_off_t zone_off, unsigned int bucket) + tdb_off_t prev, tdb_off_t flist_off, unsigned int bucket) { if (frec_magic(frec) != TDB_FREE_MAGIC) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, @@ -286,24 +323,22 @@ static bool check_free(struct tdb_context *tdb, (long long)off, (long long)frec->magic_and_meta); return false; } - if (tdb->methods->oob(tdb, off - + frec->data_len-sizeof(struct tdb_used_record), - true)) - return false; - if (off < zone_off || off >= zone_off + (1ULL<log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "tdb_check: offset %llu outside zone %llu-%llu\n", - (long long)off, - (long long)zone_off, - (long long)zone_off + (1ULL<data_len) != bucket) { + + if (tdb->methods->oob(tdb, off + + frec->data_len+sizeof(struct tdb_used_record), + false)) + return false; + if (size_to_bucket(frec->data_len) != bucket) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "tdb_check: offset %llu in wrong bucket %u vs %u\n", (long long)off, - bucket, - size_to_bucket(frec_zone_bits(frec), frec->data_len)); + bucket, size_to_bucket(frec->data_len)); return false; } if (prev != frec->prev) { @@ -316,30 +351,40 @@ static bool check_free(struct tdb_context *tdb, return true; } -static tdb_len_t check_free_list(struct tdb_context *tdb, - tdb_off_t zone_off, - tdb_off_t free[], - size_t num_free, - size_t *num_found) +static bool check_free_list(struct tdb_context *tdb, + tdb_off_t flist_off, + tdb_off_t free[], + size_t num_free, + size_t *num_found) { - struct free_zone_header zhdr; + struct tdb_freelist flist; tdb_off_t h; unsigned int i; - if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1) - return TDB_OFF_ERR; + if (tdb_read_convert(tdb, flist_off, &flist, sizeof(flist)) == -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->log(tdb, TDB_DEBUG_ERROR, + tdb->log_priv, + "tdb_check: Invalid header on free list\n"); + return false; + } - for (i = 0; i <= BUCKETS_FOR_ZONE(zhdr.zone_bits); i++) { + for (i = 0; i < TDB_FREE_BUCKETS; i++) { tdb_off_t off, prev = 0, *p; struct tdb_free_record f; - h = bucket_off(zone_off, i); + h = bucket_off(flist_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, zone_off, i)) + if (!check_free(tdb, off, &f, prev, flist_off, i)) return false; /* FIXME: Check hash bits */ @@ -358,74 +403,88 @@ static tdb_len_t check_free_list(struct tdb_context *tdb, prev = off; } } - return 1ULL << zhdr.zone_bits; + return true; } -static tdb_off_t check_zone(struct tdb_context *tdb, tdb_off_t zone_off, - tdb_off_t **used, size_t *num_used, - tdb_off_t **free, size_t *num_free, - unsigned int *max_zone_bits) +/* Slow, but should be very rare. */ +size_t dead_space(struct tdb_context *tdb, tdb_off_t off) { - struct free_zone_header zhdr; - tdb_off_t off, hdrlen; - tdb_len_t len; - - if (tdb_read_convert(tdb, zone_off, &zhdr, sizeof(zhdr)) == -1) - return TDB_OFF_ERR; - - if (zhdr.zone_bits < INITIAL_ZONE_BITS) { - tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "check: bad zone_bits %llu at zone %llu\n", - (long long)zhdr.zone_bits, (long long)zone_off); - return TDB_OFF_ERR; - } - - /* Zone bits can only increase... */ - if (zhdr.zone_bits > *max_zone_bits) - *max_zone_bits = zhdr.zone_bits; - else if (zhdr.zone_bits < *max_zone_bits) { - tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "check: small zone_bits %llu at zone %llu\n", - (long long)zhdr.zone_bits, (long long)zone_off); - return TDB_OFF_ERR; + size_t len; + + for (len = 0; off + len < tdb->map_size; len++) { + char c; + if (tdb->methods->read(tdb, off, &c, 1)) + return 0; + if (c != 0 && c != 0x43) + break; } + return len; +} - /* Zone must be within file! */ - if (tdb->methods->oob(tdb, zone_off + (1ULL << zhdr.zone_bits), false)) - return TDB_OFF_ERR; +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 recovery) +{ + tdb_off_t off; + tdb_len_t len; + bool found_recovery = false; - hdrlen = sizeof(zhdr) - + (BUCKETS_FOR_ZONE(zhdr.zone_bits) + 1) * sizeof(tdb_off_t); - for (off = zone_off + hdrlen; - off < zone_off + (1ULL << zhdr.zone_bits); - off += len) { + for (off = sizeof(struct tdb_header); off < tdb->map_size; off += len) { union { struct tdb_used_record u; struct tdb_free_record f; + struct tdb_recovery_record r; } pad, *p; p = tdb_get(tdb, off, &pad, sizeof(pad)); if (!p) - return TDB_OFF_ERR; - if (frec_magic(&p->f) == TDB_FREE_MAGIC) { - if (frec_zone_bits(&p->f) != zhdr.zone_bits) { + return false; + + /* If we crash after ftruncate, we can get zeroes or fill. */ + if (p->r.magic == TDB_RECOVERY_INVALID_MAGIC + || p->r.magic == 0x4343434343434343ULL) { + if (recovery == off) { + found_recovery = true; + len = sizeof(p->r) + p->r.max_len; + } else { + len = dead_space(tdb, off); + if (len < sizeof(p->r)) { + tdb->log(tdb, TDB_DEBUG_ERROR, + tdb->log_priv, + "tdb_check: invalid dead space" + " at %zu\n", (size_t)off); + return false; + } + + tdb->log(tdb, TDB_DEBUG_WARNING, tdb->log_priv, + "Dead space at %zu-%zu (of %zu)\n", + (size_t)off, (size_t)(off + len), + (size_t)tdb->map_size); + } + } else if (p->r.magic == TDB_RECOVERY_MAGIC) { + if (recovery != off) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "tdb_check: Bad free zone bits %u" - " at offset %llu\n", - frec_zone_bits(&p->f), - (long long)off); - return TDB_OFF_ERR; + "tdb_check: unexpected recovery" + " record at offset %zu\n", + (size_t)off); + return false; } - /* This record is free! */ - if (!append(free, num_free, off)) - return TDB_OFF_ERR; + found_recovery = true; + len = sizeof(p->r) + p->r.max_len; + } else if (frec_magic(&p->f) == TDB_FREE_MAGIC + || frec_magic(&p->f) == TDB_COALESCING_MAGIC) { len = sizeof(p->u) + p->f.data_len; - if (off + len > zone_off + (1ULL << zhdr.zone_bits)) { + if (off + len > tdb->map_size) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "tdb_check: free overlength %llu" " at offset %llu\n", (long long)len, (long long)off); - return TDB_OFF_ERR; + return false; } + /* This record is free! */ + if (frec_magic(&p->f) == TDB_FREE_MAGIC + && !append(free, num_free, off)) + return false; } else { uint64_t klen, dlen, extra; @@ -436,32 +495,23 @@ static tdb_off_t check_zone(struct tdb_context *tdb, tdb_off_t zone_off, " at offset %llu\n", (long long)rec_magic(&p->u), (long long)off); - return TDB_OFF_ERR; + return false; } - if (rec_zone_bits(&p->u) != zhdr.zone_bits) { - tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "tdb_check: Bad zone bits %u" - " at offset %llu\n", - rec_zone_bits(&p->u), - (long long)off); - return TDB_OFF_ERR; - } - if (!append(used, num_used, off)) - return TDB_OFF_ERR; + return false; klen = rec_key_length(&p->u); dlen = rec_data_length(&p->u); extra = rec_extra_padding(&p->u); len = sizeof(p->u) + klen + dlen + extra; - if (off + len > zone_off + (1ULL << zhdr.zone_bits)) { + if (off + len > tdb->map_size) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "tdb_check: used overlength %llu" " at offset %llu\n", (long long)len, (long long)off); - return TDB_OFF_ERR; + return false; } if (len < sizeof(p->f)) { @@ -469,25 +519,29 @@ static tdb_off_t check_zone(struct tdb_context *tdb, tdb_off_t zone_off, "tdb_check: too short record %llu at" " %llu\n", (long long)len, (long long)off); - return TDB_OFF_ERR; + return false; } } } - return 1ULL << zhdr.zone_bits; + + /* We must have found recovery area if there was one. */ + if (recovery != 0 && !found_recovery) { + tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, + "tdb_check: expected a recovery area at %zu\n", + (size_t)recovery); + return false; + } + + return true; } -/* FIXME: call check() function. */ 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, off; - tdb_len_t len; - size_t num_free = 0, num_used = 0, num_found = 0; - unsigned max_zone_bits = INITIAL_ZONE_BITS; - uint8_t tailer; + tdb_off_t *free = NULL, *used = NULL, flist, recovery; + size_t num_free = 0, num_used = 0, num_found = 0, num_flists = 0; - /* This always ensures the header is uptodate. */ if (tdb_allrecord_lock(tdb, F_RDLCK, TDB_LOCK_WAIT, false) != 0) return -1; @@ -496,41 +550,25 @@ int tdb_check(struct tdb_context *tdb, return -1; } - if (!check_header(tdb)) + if (!check_header(tdb, &recovery)) goto fail; /* First we do a linear scan, checking all records. */ - for (off = sizeof(struct tdb_header); - off < tdb->map_size - 1; - off += len) { - len = check_zone(tdb, off, &used, &num_used, &free, &num_free, - &max_zone_bits); - if (len == TDB_OFF_ERR) - goto fail; - } - - /* Check tailer. */ - if (tdb->methods->read(tdb, tdb->map_size - 1, &tailer, 1) == -1) - goto fail; - if (tailer != max_zone_bits) { - tdb->ecode = TDB_ERR_CORRUPT; - tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, - "tdb_check: Bad tailer value %u vs %u\n", tailer, - max_zone_bits); + if (!check_linear(tdb, &used, &num_used, &free, &num_free, recovery)) goto fail; + + for (flist = first_flist(tdb); flist; flist = next_flist(tdb, flist)) { + if (flist == TDB_OFF_ERR) + goto fail; + if (!check_free_list(tdb, flist, free, num_free, &num_found)) + goto fail; + num_flists++; } /* FIXME: Check key uniqueness? */ - if (!check_hash(tdb, used, num_used)) + if (!check_hash(tdb, used, num_used, num_flists, check, private_data)) goto fail; - for (off = sizeof(struct tdb_header); - off < tdb->map_size - 1; - off += len) { - len = check_free_list(tdb, off, free, num_free, &num_found); - if (len == TDB_OFF_ERR) - goto fail; - } if (num_found != num_free) { tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv, "tdb_check: Not all entries are in free table\n");