+ return (h >> (64 - *used)) & ((1U << num) - 1);
+}
+
+static enum TDB_ERROR 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,
+ enum TDB_ERROR (*check)(TDB_DATA,
+ TDB_DATA, void *),
+ void *data)
+{
+ unsigned int g, b;
+ const tdb_off_t *hash;
+ struct tdb_used_record rec;
+ enum TDB_ERROR ecode;
+
+ hash = tdb_access_read(tdb, off,
+ sizeof(tdb_off_t)
+ << (group_bits + TDB_HASH_GROUP_BITS),
+ true);
+ if (TDB_PTR_IS_ERR(hash)) {
+ return TDB_PTR_ERR(hash);
+ }
+
+ 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) {
+ ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_LOG_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])) {
+ ecode = TDB_ERR_CORRUPT;
+ tdb_logerr(tdb, ecode,
+ TDB_LOG_ERROR,
+ "tdb_check: Invalid chain"
+ " entry subhash");
+ goto fail;
+ }
+ h = hash_record(tdb, off);
+ if (h != hprefix) {
+ ecode = TDB_ERR_CORRUPT;
+ tdb_logerr(tdb, ecode,
+ TDB_LOG_ERROR,
+ "check: bad hash chain"
+ " placement"
+ " 0x%llx vs 0x%llx",
+ (long long)h,
+ (long long)hprefix);
+ goto fail;
+ }
+ ecode = tdb_read_convert(tdb, off, &rec,
+ sizeof(rec));
+ if (ecode != TDB_SUCCESS) {
+ 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;
+
+ ecode = check_hash_record(tdb,
+ group[b] & TDB_OFF_MASK,
+ subprefix,
+ hprefix_bits
+ + group_bits
+ + TDB_HASH_GROUP_BITS,
+ used, num_used, num_found,
+ check, data);
+ if (ecode != TDB_SUCCESS) {
+ 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) {
+ ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_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 = tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_LOG_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;
+ ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_LOG_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) {
+ ecode = TDB_ERR_CORRUPT;
+ tdb_logerr(tdb, ecode,
+ TDB_LOG_ERROR,
+ "check: bad group placement"
+ " %u vs %u",
+ b, bucket);
+ goto fail;
+ }
+ }
+
+ ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec));
+ if (ecode != TDB_SUCCESS) {
+ goto fail;
+ }
+
+ /* Bottom bits must match header. */
+ if ((h & ((1 << 11)-1)) != rec_hash(&rec)) {
+ ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT,
+ TDB_LOG_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 k, d;
+ const unsigned char *kptr;
+
+ kptr = tdb_access_read(tdb,
+ off + sizeof(rec),
+ rec_key_length(&rec)
+ + rec_data_length(&rec),
+ false);
+ if (TDB_PTR_IS_ERR(kptr)) {
+ ecode = TDB_PTR_ERR(kptr);
+ goto fail;
+ }
+
+ k = tdb_mkdata(kptr, rec_key_length(&rec));
+ d = tdb_mkdata(kptr + k.dsize,
+ rec_data_length(&rec));
+ ecode = check(k, d, data);
+ tdb_access_release(tdb, kptr);
+ if (ecode != TDB_SUCCESS) {
+ goto fail;
+ }