+static bool check_hash_tree(struct tdb_context *tdb,
+ tdb_off_t off, unsigned int group_bits,
+ uint64_t hprefix,
+ unsigned hprefix_bits,
+ tdb_off_t used[],
+ size_t num_used,
+ size_t *num_found,
+ int (*check)(TDB_DATA, TDB_DATA, void *),
+ void *private_data)
+{
+ unsigned int g, b;
+ const tdb_off_t *hash;
+ struct tdb_used_record rec;
+
+ hash = tdb_access_read(tdb, off,
+ sizeof(tdb_off_t)
+ << (group_bits + TDB_HASH_GROUP_BITS),
+ true);
+ if (!hash)
+ return false;
+
+ for (g = 0; g < (1 << group_bits); g++) {
+ const tdb_off_t *group = hash + (g << TDB_HASH_GROUP_BITS);
+ for (b = 0; b < (1 << TDB_HASH_GROUP_BITS); b++) {
+ unsigned int bucket, i, used_bits;
+ uint64_t h;
+ tdb_off_t *p;
+ if (group[b] == 0)
+ continue;
+
+ off = group[b] & TDB_OFF_MASK;
+ p = asearch(&off, used, num_used, off_cmp);
+ if (!p) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "tdb_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])) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "tdb_check: Invalid chain"
+ " entry subhash");
+ goto fail;
+ }
+ h = hash_record(tdb, off);
+ if (h != hprefix) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "check: bad hash chain"
+ " placement"
+ " 0x%llx vs 0x%llx",
+ (long long)h,
+ (long long)hprefix);
+ goto fail;
+ }
+ if (tdb_read_convert(tdb, off, &rec,
+ sizeof(rec)))
+ goto fail;
+ goto check;
+ }
+
+ if (is_subhash(group[b])) {
+ uint64_t subprefix;
+ subprefix = (hprefix
+ << (group_bits + TDB_HASH_GROUP_BITS))
+ + g * (1 << TDB_HASH_GROUP_BITS) + b;
+
+ if (!check_hash_record(tdb,
+ group[b] & TDB_OFF_MASK,
+ subprefix,
+ hprefix_bits
+ + group_bits
+ + TDB_HASH_GROUP_BITS,
+ used, num_used, num_found,
+ check, private_data))
+ goto fail;
+ continue;
+ }
+ /* A normal entry */
+
+ /* Does it belong here at all? */
+ h = hash_record(tdb, off);
+ used_bits = 0;
+ if (get_bits(h, hprefix_bits, &used_bits) != hprefix
+ && hprefix_bits) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_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) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "check: bad group %llu vs %u",
+ (long long)h, g);
+ goto fail;
+ }
+
+ /* Are bucket bits correct? */
+ bucket = group[b] & TDB_OFF_HASH_GROUP_MASK;
+ if (get_bits(h, TDB_HASH_GROUP_BITS, &used_bits)
+ != bucket) {
+ used_bits -= TDB_HASH_GROUP_BITS;
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "check: bad bucket %u vs %u",
+ (unsigned)get_bits(h,
+ TDB_HASH_GROUP_BITS,
+ &used_bits),
+ bucket);
+ goto fail;
+ }
+
+ /* 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 << TDB_HASH_GROUP_BITS)) {
+ if (group[i] == 0) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "check: bad group placement"
+ " %u vs %u",
+ b, bucket);
+ goto fail;
+ }
+ }
+
+ if (tdb_read_convert(tdb, off, &rec, sizeof(rec)))
+ goto fail;
+
+ /* Bottom bits must match header. */
+ if ((h & ((1 << 11)-1)) != rec_hash(&rec)) {
+ tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_DEBUG_ERROR,
+ "tdb_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;
+ }
+
+ check:
+ 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);