diff options
Diffstat (limited to 'lib/ntdb/check.c')
-rw-r--r-- | lib/ntdb/check.c | 484 |
1 files changed, 169 insertions, 315 deletions
diff --git a/lib/ntdb/check.c b/lib/ntdb/check.c index be27003a51..2790c68eaf 100644 --- a/lib/ntdb/check.c +++ b/lib/ntdb/check.c @@ -38,8 +38,10 @@ static bool append(struct ntdb_context *ntdb, return true; } -static enum NTDB_ERROR check_header(struct ntdb_context *ntdb, ntdb_off_t *recovery, - uint64_t *features, size_t *num_capabilities) +static enum NTDB_ERROR check_header(struct ntdb_context *ntdb, + ntdb_off_t *recovery, + uint64_t *features, + size_t *num_capabilities) { uint64_t hash_test; struct ntdb_header hdr; @@ -112,374 +114,227 @@ static enum NTDB_ERROR check_header(struct ntdb_context *ntdb, ntdb_off_t *recov return NTDB_SUCCESS; } -static enum NTDB_ERROR check_hash_tree(struct ntdb_context *ntdb, - ntdb_off_t off, unsigned int group_bits, - uint64_t hprefix, - unsigned hprefix_bits, - ntdb_off_t used[], - size_t num_used, - size_t *num_found, - enum NTDB_ERROR (*check)(NTDB_DATA, - NTDB_DATA, void *), - void *data); +static int off_cmp(const ntdb_off_t *a, const ntdb_off_t *b) +{ + /* Can overflow an int. */ + return *a > *b ? 1 + : *a < *b ? -1 + : 0; +} -static enum NTDB_ERROR check_hash_chain(struct ntdb_context *ntdb, - ntdb_off_t off, - uint64_t hash, - ntdb_off_t used[], - size_t num_used, - size_t *num_found, - enum NTDB_ERROR (*check)(NTDB_DATA, - NTDB_DATA, - void *), - void *data) +static enum NTDB_ERROR check_entry(struct ntdb_context *ntdb, + ntdb_off_t off_and_hash, + ntdb_len_t bucket, + ntdb_off_t used[], + size_t num_used, + size_t *num_found, + enum NTDB_ERROR (*check)(NTDB_DATA, + NTDB_DATA, + void *), + void *data) { - struct ntdb_used_record rec; enum NTDB_ERROR ecode; - - ecode = ntdb_read_convert(ntdb, off, &rec, sizeof(rec)); - if (ecode != NTDB_SUCCESS) { - return ecode; + const struct ntdb_used_record *r; + const unsigned char *kptr; + ntdb_len_t klen, dlen; + uint32_t hash; + ntdb_off_t off = off_and_hash & NTDB_OFF_MASK; + ntdb_off_t *p; + + /* Empty bucket is fine. */ + if (!off_and_hash) { + return NTDB_SUCCESS; } - if (rec_magic(&rec) != NTDB_CHAIN_MAGIC) { + /* This can't point to a chain, we handled those at toplevel. */ + if (off_and_hash & (1ULL << NTDB_OFF_CHAIN_BIT)) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash chain magic %llu", - (long long)rec_magic(&rec)); + "ntdb_check: Invalid chain bit in offset " + " %llu", (long long)off_and_hash); } - if (rec_data_length(&rec) != sizeof(struct ntdb_chain)) { - return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check:" - " Bad hash chain length %llu vs %zu", - (long long)rec_data_length(&rec), - sizeof(struct ntdb_chain)); - } - if (rec_key_length(&rec) != 0) { + p = asearch(&off, used, num_used, off_cmp); + if (!p) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash chain key length %llu", - (long long)rec_key_length(&rec)); - } - if (rec_hash(&rec) != 0) { - return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash chain hash value %llu", - (long long)rec_hash(&rec)); + "ntdb_check: Invalid offset" + " %llu in hash", (long long)off); } + /* Mark it invalid. */ + *p ^= 1; + (*num_found)++; - off += sizeof(rec); - ecode = check_hash_tree(ntdb, off, 0, hash, 64, - used, num_used, num_found, check, data); - if (ecode != NTDB_SUCCESS) { - return ecode; + r = ntdb_access_read(ntdb, off, sizeof(*r), true); + if (NTDB_PTR_IS_ERR(r)) { + return NTDB_PTR_ERR(r); + } + klen = rec_key_length(r); + dlen = rec_data_length(r); + ntdb_access_release(ntdb, r); + + kptr = ntdb_access_read(ntdb, off + sizeof(*r), klen + dlen, false); + if (NTDB_PTR_IS_ERR(kptr)) { + return NTDB_PTR_ERR(kptr); + } + + hash = ntdb_hash(ntdb, kptr, klen); + + /* Are we in the right chain? */ + if (bits_from(hash, 0, ntdb->hash_bits) != bucket) { + ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, + NTDB_LOG_ERROR, + "ntdb_check: Bad bucket %u vs %llu", + bits_from(hash, 0, ntdb->hash_bits), + (long long)bucket); + /* Next 8 bits should be the same as top bits of bucket. */ + } else if (bits_from(hash, ntdb->hash_bits, NTDB_OFF_UPPER_STEAL) + != bits_from(off_and_hash, 64-NTDB_OFF_UPPER_STEAL, + NTDB_OFF_UPPER_STEAL)) { + ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, + NTDB_LOG_ERROR, + "ntdb_check: Bad hash bits %llu vs %llu", + (long long)off_and_hash, + (long long)hash); + } else if (check) { + NTDB_DATA k, d; + + k = ntdb_mkdata(kptr, klen); + d = ntdb_mkdata(kptr + klen, dlen); + ecode = check(k, d, data); + } else { + ecode = NTDB_SUCCESS; } + ntdb_access_release(ntdb, kptr); - off = ntdb_read_off(ntdb, off + offsetof(struct ntdb_chain, next)); - if (NTDB_OFF_IS_ERR(off)) { - return NTDB_OFF_TO_ERR(off); - } - if (off == 0) - return NTDB_SUCCESS; - (*num_found)++; - return check_hash_chain(ntdb, off, hash, used, num_used, num_found, - check, data); + return ecode; } -static enum NTDB_ERROR check_hash_record(struct ntdb_context *ntdb, +static enum NTDB_ERROR check_hash_chain(struct ntdb_context *ntdb, ntdb_off_t off, - uint64_t hprefix, - unsigned hprefix_bits, + ntdb_len_t bucket, ntdb_off_t used[], size_t num_used, size_t *num_found, enum NTDB_ERROR (*check)(NTDB_DATA, - NTDB_DATA, - void *), + NTDB_DATA, + void *), void *data) { struct ntdb_used_record rec; enum NTDB_ERROR ecode; + const ntdb_off_t *entries; + ntdb_len_t i, num; - if (hprefix_bits >= 64) - return check_hash_chain(ntdb, off, hprefix, used, num_used, - num_found, check, data); + /* This is a used entry. */ + (*num_found)++; ecode = ntdb_read_convert(ntdb, off, &rec, sizeof(rec)); if (ecode != NTDB_SUCCESS) { return ecode; } - if (rec_magic(&rec) != NTDB_HTABLE_MAGIC) { + if (rec_magic(&rec) != NTDB_CHAIN_MAGIC) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash table magic %llu", + "ntdb_check: Bad hash chain magic %llu", (long long)rec_magic(&rec)); } - if (rec_data_length(&rec) - != sizeof(ntdb_off_t) << NTDB_SUBLEVEL_HASH_BITS) { + + if (rec_data_length(&rec) % sizeof(ntdb_off_t)) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check:" - " Bad hash table length %llu vs %llu", - (long long)rec_data_length(&rec), - (long long)sizeof(ntdb_off_t) - << NTDB_SUBLEVEL_HASH_BITS); + "ntdb_check: Bad hash chain data length %llu", + (long long)rec_data_length(&rec)); } + if (rec_key_length(&rec) != 0) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash table key length %llu", + "ntdb_check: Bad hash chain key length %llu", (long long)rec_key_length(&rec)); } - if (rec_hash(&rec) != 0) { - return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Bad hash table hash value %llu", - (long long)rec_hash(&rec)); - } off += sizeof(rec); - return check_hash_tree(ntdb, off, - NTDB_SUBLEVEL_HASH_BITS-NTDB_HASH_GROUP_BITS, - hprefix, hprefix_bits, - used, num_used, num_found, check, data); -} - -static int off_cmp(const ntdb_off_t *a, const ntdb_off_t *b) -{ - /* Can overflow an int. */ - return *a > *b ? 1 - : *a < *b ? -1 - : 0; -} + num = rec_data_length(&rec) / sizeof(ntdb_off_t); + entries = ntdb_access_read(ntdb, off, rec_data_length(&rec), true); + if (NTDB_PTR_IS_ERR(entries)) { + return NTDB_PTR_ERR(entries); + } -static uint64_t get_bits(uint64_t h, unsigned num, unsigned *used) -{ - *used += num; + /* Check each non-deleted entry in chain. */ + for (i = 0; i < num; i++) { + ecode = check_entry(ntdb, entries[i], bucket, + used, num_used, num_found, check, data); + if (ecode) { + break; + } + } - return (h >> (64 - *used)) & ((1U << num) - 1); + ntdb_access_release(ntdb, entries); + return ecode; } -static enum NTDB_ERROR check_hash_tree(struct ntdb_context *ntdb, - ntdb_off_t off, unsigned int group_bits, - uint64_t hprefix, - unsigned hprefix_bits, - ntdb_off_t used[], - size_t num_used, - size_t *num_found, - enum NTDB_ERROR (*check)(NTDB_DATA, - NTDB_DATA, void *), - void *data) +static enum NTDB_ERROR check_hash(struct ntdb_context *ntdb, + ntdb_off_t used[], + size_t num_used, + size_t num_other_used, + enum NTDB_ERROR (*check)(NTDB_DATA, + NTDB_DATA, + void *), + void *data) { - unsigned int g, b; - const ntdb_off_t *hash; - struct ntdb_used_record rec; enum NTDB_ERROR ecode; + struct ntdb_used_record rec; + const ntdb_off_t *entries; + ntdb_len_t i; + /* Free tables and capabilities also show up as used, as do we. */ + size_t num_found = num_other_used + 1; - hash = ntdb_access_read(ntdb, off, - sizeof(ntdb_off_t) - << (group_bits + NTDB_HASH_GROUP_BITS), - true); - if (NTDB_PTR_IS_ERR(hash)) { - return NTDB_PTR_ERR(hash); - } - - for (g = 0; g < (1 << group_bits); g++) { - const ntdb_off_t *group = hash + (g << NTDB_HASH_GROUP_BITS); - for (b = 0; b < (1 << NTDB_HASH_GROUP_BITS); b++) { - unsigned int bucket, i, used_bits; - uint64_t h; - ntdb_off_t *p; - if (group[b] == 0) - continue; - - off = group[b] & NTDB_OFF_MASK; - p = asearch(&off, used, num_used, off_cmp); - if (!p) { - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, - NTDB_LOG_ERROR, - "ntdb_check: Invalid offset" - " %llu in hash", - (long long)off); - goto fail; - } - /* Mark it invalid. */ - *p ^= 1; - (*num_found)++; - - if (hprefix_bits == 64) { - /* Chained entries are unordered. */ - if (is_subhash(group[b])) { - ecode = NTDB_ERR_CORRUPT; - ntdb_logerr(ntdb, ecode, - NTDB_LOG_ERROR, - "ntdb_check: Invalid chain" - " entry subhash"); - goto fail; - } - h = hash_record(ntdb, off); - if (h != hprefix) { - ecode = NTDB_ERR_CORRUPT; - ntdb_logerr(ntdb, ecode, - NTDB_LOG_ERROR, - "check: bad hash chain" - " placement" - " 0x%llx vs 0x%llx", - (long long)h, - (long long)hprefix); - goto fail; - } - ecode = ntdb_read_convert(ntdb, off, &rec, - sizeof(rec)); - if (ecode != NTDB_SUCCESS) { - goto fail; - } - goto check; - } - - if (is_subhash(group[b])) { - uint64_t subprefix; - subprefix = (hprefix - << (group_bits + NTDB_HASH_GROUP_BITS)) - + g * (1 << NTDB_HASH_GROUP_BITS) + b; - - ecode = check_hash_record(ntdb, - group[b] & NTDB_OFF_MASK, - subprefix, - hprefix_bits - + group_bits - + NTDB_HASH_GROUP_BITS, - used, num_used, num_found, - check, data); - if (ecode != NTDB_SUCCESS) { - goto fail; - } - continue; - } - /* A normal entry */ - - /* Does it belong here at all? */ - h = hash_record(ntdb, off); - used_bits = 0; - if (get_bits(h, hprefix_bits, &used_bits) != hprefix - && hprefix_bits) { - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, - NTDB_LOG_ERROR, - "check: bad hash placement" - " 0x%llx vs 0x%llx", - (long long)h, - (long long)hprefix); - goto fail; - } - - /* Does it belong in this group? */ - if (get_bits(h, group_bits, &used_bits) != g) { - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, - NTDB_LOG_ERROR, - "check: bad group %llu" - " vs %u", - (long long)h, g); - goto fail; - } - - /* Are bucket bits correct? */ - bucket = group[b] & NTDB_OFF_HASH_GROUP_MASK; - if (get_bits(h, NTDB_HASH_GROUP_BITS, &used_bits) - != bucket) { - used_bits -= NTDB_HASH_GROUP_BITS; - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, - NTDB_LOG_ERROR, - "check: bad bucket %u vs %u", - (unsigned)get_bits(h, - NTDB_HASH_GROUP_BITS, - &used_bits), - bucket); - goto fail; - } + ecode = ntdb_read_convert(ntdb, NTDB_HASH_OFFSET, &rec, sizeof(rec)); + if (ecode != NTDB_SUCCESS) { + return ecode; + } - /* There must not be any zero entries between - * the bucket it belongs in and this one! */ - for (i = bucket; - i != b; - i = (i + 1) % (1 << NTDB_HASH_GROUP_BITS)) { - if (group[i] == 0) { - ecode = NTDB_ERR_CORRUPT; - ntdb_logerr(ntdb, ecode, - NTDB_LOG_ERROR, - "check: bad group placement" - " %u vs %u", - b, bucket); - goto fail; - } - } + if (rec_magic(&rec) != NTDB_HTABLE_MAGIC) { + return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, + "ntdb_check: Bad hash table magic %llu", + (long long)rec_magic(&rec)); + } - ecode = ntdb_read_convert(ntdb, off, &rec, sizeof(rec)); - if (ecode != NTDB_SUCCESS) { - goto fail; - } + if (rec_data_length(&rec) != (sizeof(ntdb_off_t) << ntdb->hash_bits)) { + return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, + "ntdb_check: Bad hash table data length %llu", + (long long)rec_data_length(&rec)); + } - /* Bottom bits must match header. */ - if ((h & ((1 << 11)-1)) != rec_hash(&rec)) { - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, - NTDB_LOG_ERROR, - "ntdb_check: Bad hash magic" - " at offset %llu" - " (0x%llx vs 0x%llx)", - (long long)off, - (long long)h, - (long long)rec_hash(&rec)); - goto fail; - } + if (rec_key_length(&rec) != 0) { + return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, + "ntdb_check: Bad hash table key length %llu", + (long long)rec_key_length(&rec)); + } - check: - if (check) { - NTDB_DATA k, d; - const unsigned char *kptr; - - kptr = ntdb_access_read(ntdb, - off + sizeof(rec), - rec_key_length(&rec) - + rec_data_length(&rec), - false); - if (NTDB_PTR_IS_ERR(kptr)) { - ecode = NTDB_PTR_ERR(kptr); - goto fail; - } + entries = ntdb_access_read(ntdb, NTDB_HASH_OFFSET + sizeof(rec), + rec_data_length(&rec), true); + if (NTDB_PTR_IS_ERR(entries)) { + return NTDB_PTR_ERR(entries); + } - k = ntdb_mkdata(kptr, rec_key_length(&rec)); - d = ntdb_mkdata(kptr + k.dsize, - rec_data_length(&rec)); - ecode = check(k, d, data); - ntdb_access_release(ntdb, kptr); - if (ecode != NTDB_SUCCESS) { - goto fail; - } - } + for (i = 0; i < (1 << ntdb->hash_bits); i++) { + ntdb_off_t off = entries[i] & NTDB_OFF_MASK; + if (entries[i] & (1ULL << NTDB_OFF_CHAIN_BIT)) { + ecode = check_hash_chain(ntdb, off, i, + used, num_used, &num_found, + check, data); + } else { + ecode = check_entry(ntdb, entries[i], i, + used, num_used, &num_found, + check, data); + } + if (ecode) { + break; } } - ntdb_access_release(ntdb, hash); - return NTDB_SUCCESS; - -fail: - ntdb_access_release(ntdb, hash); - return ecode; -} + ntdb_access_release(ntdb, entries); -static enum NTDB_ERROR check_hash(struct ntdb_context *ntdb, - ntdb_off_t used[], - size_t num_used, size_t num_other_used, - enum NTDB_ERROR (*check)(NTDB_DATA, NTDB_DATA, void *), - void *data) -{ - /* Free tables and capabilities also show up as used. */ - size_t num_found = num_other_used; - enum NTDB_ERROR ecode; - - ecode = check_hash_tree(ntdb, offsetof(struct ntdb_header, hashtable), - NTDB_TOPLEVEL_HASH_BITS-NTDB_HASH_GROUP_BITS, - 0, 0, used, num_used, &num_found, - check, data); - if (ecode == NTDB_SUCCESS) { - if (num_found != num_used) { - ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, - "ntdb_check: Not all entries" - " are in hash"); - } + if (ecode == NTDB_SUCCESS && num_found != num_used) { + ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, + "ntdb_check: Not all entries are in hash"); } return ecode; } @@ -547,8 +402,7 @@ static enum NTDB_ERROR check_free_table(struct ntdb_context *ntdb, if (rec_magic(&ft.hdr) != NTDB_FTABLE_MAGIC || rec_key_length(&ft.hdr) != 0 - || rec_data_length(&ft.hdr) != sizeof(ft) - sizeof(ft.hdr) - || rec_hash(&ft.hdr) != 0) { + || rec_data_length(&ft.hdr) != sizeof(ft) - sizeof(ft.hdr)) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, "ntdb_check: Invalid header on free table"); } |