X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fstr_hash.h;h=89fdb7c21134ebbb6c145a88ed5b1943ab54588a;hb=3bd4653767bb5eadd253e382fe8503ceb6bef5d1;hp=091bf7a8957755c092636177ae13bce9a5af6998;hpb=f96ba8e0aac91f2650270e9639359243cb9ac2d1;p=bcachefs-tools-debian diff --git a/libbcachefs/str_hash.h b/libbcachefs/str_hash.h index 091bf7a..89fdb7c 100644 --- a/libbcachefs/str_hash.h +++ b/libbcachefs/str_hash.h @@ -8,49 +8,68 @@ #include "error.h" #include "inode.h" #include "siphash.h" +#include "subvolume.h" #include "super.h" #include #include -#include +#include + +typedef unsigned __bitwise bch_str_hash_flags_t; + +enum bch_str_hash_flags { + __BCH_HASH_SET_MUST_CREATE, + __BCH_HASH_SET_MUST_REPLACE, +}; + +#define BCH_HASH_SET_MUST_CREATE (__force bch_str_hash_flags_t) BIT(__BCH_HASH_SET_MUST_CREATE) +#define BCH_HASH_SET_MUST_REPLACE (__force bch_str_hash_flags_t) BIT(__BCH_HASH_SET_MUST_REPLACE) + +static inline enum bch_str_hash_type +bch2_str_hash_opt_to_type(struct bch_fs *c, enum bch_str_hash_opts opt) +{ + switch (opt) { + case BCH_STR_HASH_OPT_crc32c: + return BCH_STR_HASH_crc32c; + case BCH_STR_HASH_OPT_crc64: + return BCH_STR_HASH_crc64; + case BCH_STR_HASH_OPT_siphash: + return c->sb.features & (1ULL << BCH_FEATURE_new_siphash) + ? BCH_STR_HASH_siphash + : BCH_STR_HASH_siphash_old; + default: + BUG(); + } +} struct bch_hash_info { u8 type; - union { - __le64 crc_key; - SIPHASH_KEY siphash_key; - }; + /* + * For crc32 or crc64 string hashes the first key value of + * the siphash_key (k0) is used as the key. + */ + SIPHASH_KEY siphash_key; }; static inline struct bch_hash_info -bch2_hash_info_init(struct bch_fs *c, - const struct bch_inode_unpacked *bi) +bch2_hash_info_init(struct bch_fs *c, const struct bch_inode_unpacked *bi) { /* XXX ick */ struct bch_hash_info info = { .type = (bi->bi_flags >> INODE_STR_HASH_OFFSET) & - ~(~0U << INODE_STR_HASH_BITS) + ~(~0U << INODE_STR_HASH_BITS), + .siphash_key = { .k0 = bi->bi_hash_seed } }; - switch (info.type) { - case BCH_STR_HASH_CRC32C: - case BCH_STR_HASH_CRC64: - info.crc_key = bi->bi_hash_seed; - break; - case BCH_STR_HASH_SIPHASH: { + if (unlikely(info.type == BCH_STR_HASH_siphash_old)) { SHASH_DESC_ON_STACK(desc, c->sha256); u8 digest[SHA256_DIGEST_SIZE]; desc->tfm = c->sha256; - desc->flags = 0; crypto_shash_digest(desc, (void *) &bi->bi_hash_seed, sizeof(bi->bi_hash_seed), digest); memcpy(&info.siphash_key, digest, sizeof(info.siphash_key)); - break; - } - default: - BUG(); } return info; @@ -68,13 +87,16 @@ static inline void bch2_str_hash_init(struct bch_str_hash_ctx *ctx, const struct bch_hash_info *info) { switch (info->type) { - case BCH_STR_HASH_CRC32C: - ctx->crc32c = crc32c(~0, &info->crc_key, sizeof(info->crc_key)); + case BCH_STR_HASH_crc32c: + ctx->crc32c = crc32c(~0, &info->siphash_key.k0, + sizeof(info->siphash_key.k0)); break; - case BCH_STR_HASH_CRC64: - ctx->crc64 = crc64_be(~0, &info->crc_key, sizeof(info->crc_key)); + case BCH_STR_HASH_crc64: + ctx->crc64 = crc64_be(~0, &info->siphash_key.k0, + sizeof(info->siphash_key.k0)); break; - case BCH_STR_HASH_SIPHASH: + case BCH_STR_HASH_siphash_old: + case BCH_STR_HASH_siphash: SipHash24_Init(&ctx->siphash, &info->siphash_key); break; default: @@ -87,13 +109,14 @@ static inline void bch2_str_hash_update(struct bch_str_hash_ctx *ctx, const void *data, size_t len) { switch (info->type) { - case BCH_STR_HASH_CRC32C: + case BCH_STR_HASH_crc32c: ctx->crc32c = crc32c(ctx->crc32c, data, len); break; - case BCH_STR_HASH_CRC64: + case BCH_STR_HASH_crc64: ctx->crc64 = crc64_be(ctx->crc64, data, len); break; - case BCH_STR_HASH_SIPHASH: + case BCH_STR_HASH_siphash_old: + case BCH_STR_HASH_siphash: SipHash24_Update(&ctx->siphash, data, len); break; default: @@ -105,11 +128,12 @@ static inline u64 bch2_str_hash_end(struct bch_str_hash_ctx *ctx, const struct bch_hash_info *info) { switch (info->type) { - case BCH_STR_HASH_CRC32C: + case BCH_STR_HASH_crc32c: return ctx->crc32c; - case BCH_STR_HASH_CRC64: + case BCH_STR_HASH_crc64: return ctx->crc64 >> 1; - case BCH_STR_HASH_SIPHASH: + case BCH_STR_HASH_siphash_old: + case BCH_STR_HASH_siphash: return SipHash24_End(&ctx->siphash) >> 1; default: BUG(); @@ -124,60 +148,76 @@ struct bch_hash_desc { u64 (*hash_bkey)(const struct bch_hash_info *, struct bkey_s_c); bool (*cmp_key)(struct bkey_s_c, const void *); bool (*cmp_bkey)(struct bkey_s_c, struct bkey_s_c); + bool (*is_visible)(subvol_inum inum, struct bkey_s_c); }; -static __always_inline struct btree_iter * +static inline bool is_visible_key(struct bch_hash_desc desc, subvol_inum inum, struct bkey_s_c k) +{ + return k.k->type == desc.key_type && + (!desc.is_visible || + !inum.inum || + desc.is_visible(inum, k)); +} + +static __always_inline int bch2_hash_lookup(struct btree_trans *trans, + struct btree_iter *iter, const struct bch_hash_desc desc, const struct bch_hash_info *info, - u64 inode, const void *key, + subvol_inum inum, const void *key, unsigned flags) { - struct btree_iter *iter; struct bkey_s_c k; + u32 snapshot; int ret; - for_each_btree_key(trans, iter, desc.btree_id, - POS(inode, desc.hash_key(info, key)), - BTREE_ITER_SLOTS|flags, k, ret) { - if (iter->pos.inode != inode) - break; + ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); + if (ret) + return ret; - if (k.k->type == desc.key_type) { + for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id, + SPOS(inum.inum, desc.hash_key(info, key), snapshot), + POS(inum.inum, U64_MAX), + BTREE_ITER_SLOTS|flags, k, ret) { + if (is_visible_key(desc, inum, k)) { if (!desc.cmp_key(k, key)) - return iter; - } else if (k.k->type == KEY_TYPE_whiteout) { + return 0; + } else if (k.k->type == KEY_TYPE_hash_whiteout) { ; } else { /* hole, not found */ break; } } + bch2_trans_iter_exit(trans, iter); - return ERR_PTR(ret ?: -ENOENT); + return ret ?: -BCH_ERR_ENOENT_str_hash_lookup; } -static __always_inline struct btree_iter * +static __always_inline int bch2_hash_hole(struct btree_trans *trans, + struct btree_iter *iter, const struct bch_hash_desc desc, const struct bch_hash_info *info, - u64 inode, const void *key) + subvol_inum inum, const void *key) { - struct btree_iter *iter; struct bkey_s_c k; + u32 snapshot; int ret; - for_each_btree_key(trans, iter, desc.btree_id, - POS(inode, desc.hash_key(info, key)), - BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) { - if (iter->pos.inode != inode) - break; + ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); + if (ret) + return ret; - if (k.k->type != desc.key_type) - return iter; - } + for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id, + SPOS(inum.inum, desc.hash_key(info, key), snapshot), + POS(inum.inum, U64_MAX), + BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) + if (!is_visible_key(desc, inum, k)) + return 0; + bch2_trans_iter_exit(trans, iter); - return ERR_PTR(ret ?: -ENOSPC); + return ret ?: -BCH_ERR_ENOSPC_str_hash_create; } static __always_inline @@ -186,48 +226,51 @@ int bch2_hash_needs_whiteout(struct btree_trans *trans, const struct bch_hash_info *info, struct btree_iter *start) { - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; + int ret; - iter = bch2_trans_copy_iter(trans, start); - if (IS_ERR(iter)) - return PTR_ERR(iter); + bch2_trans_copy_iter(&iter, start); - bch2_btree_iter_next_slot(iter); + bch2_btree_iter_advance(&iter); - for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) { + for_each_btree_key_continue_norestart(iter, BTREE_ITER_SLOTS, k, ret) { if (k.k->type != desc.key_type && - k.k->type != KEY_TYPE_whiteout) + k.k->type != KEY_TYPE_hash_whiteout) break; if (k.k->type == desc.key_type && desc.hash_bkey(info, k) <= start->pos.offset) { - bch2_trans_iter_free_on_commit(trans, iter); - return 1; + ret = 1; + break; } } - return bch2_trans_iter_free(trans, iter); + bch2_trans_iter_exit(trans, &iter); + return ret; } static __always_inline -int bch2_hash_set(struct btree_trans *trans, - const struct bch_hash_desc desc, - const struct bch_hash_info *info, - u64 inode, struct bkey_i *insert, int flags) +int bch2_hash_set_snapshot(struct btree_trans *trans, + const struct bch_hash_desc desc, + const struct bch_hash_info *info, + subvol_inum inum, u32 snapshot, + struct bkey_i *insert, + bch_str_hash_flags_t str_hash_flags, + int update_flags) { - struct btree_iter *iter, *slot = NULL; + struct btree_iter iter, slot = { NULL }; struct bkey_s_c k; bool found = false; int ret; - for_each_btree_key(trans, iter, desc.btree_id, - POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))), + for_each_btree_key_upto_norestart(trans, iter, desc.btree_id, + SPOS(insert->k.p.inode, + desc.hash_bkey(info, bkey_i_to_s_c(insert)), + snapshot), + POS(insert->k.p.inode, U64_MAX), BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) { - if (iter->pos.inode != inode) - break; - - if (k.k->type == desc.key_type) { + if (is_visible_key(desc, inum, k)) { if (!desc.cmp_bkey(k, bkey_i_to_s_c(insert))) goto found; @@ -235,83 +278,104 @@ int bch2_hash_set(struct btree_trans *trans, continue; } - if (!slot && - !(flags & BCH_HASH_SET_MUST_REPLACE)) { - slot = bch2_trans_copy_iter(trans, iter); - if (IS_ERR(slot)) - return PTR_ERR(slot); - } + if (!slot.path && + !(str_hash_flags & BCH_HASH_SET_MUST_REPLACE)) + bch2_trans_copy_iter(&slot, &iter); - if (k.k->type != KEY_TYPE_whiteout) + if (k.k->type != KEY_TYPE_hash_whiteout) goto not_found; } - if (slot) - bch2_trans_iter_free(trans, slot); - bch2_trans_iter_free(trans, iter); + if (!ret) + ret = -BCH_ERR_ENOSPC_str_hash_create; +out: + bch2_trans_iter_exit(trans, &slot); + bch2_trans_iter_exit(trans, &iter); - return ret ?: -ENOSPC; + return ret; found: found = true; not_found: - if (!found && (flags & BCH_HASH_SET_MUST_REPLACE)) { - ret = -ENOENT; - } else if (found && (flags & BCH_HASH_SET_MUST_CREATE)) { + if (!found && (str_hash_flags & BCH_HASH_SET_MUST_REPLACE)) { + ret = -BCH_ERR_ENOENT_str_hash_set_must_replace; + } else if (found && (str_hash_flags & BCH_HASH_SET_MUST_CREATE)) { ret = -EEXIST; } else { - if (!found && slot) { - bch2_trans_iter_free(trans, iter); - iter = slot; - } + if (!found && slot.path) + swap(iter, slot); - insert->k.p = iter->pos; - bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, insert)); - bch2_trans_iter_free_on_commit(trans, iter); + insert->k.p = iter.pos; + ret = bch2_trans_update(trans, &iter, insert, update_flags); } - return ret; + goto out; +} + +static __always_inline +int bch2_hash_set(struct btree_trans *trans, + const struct bch_hash_desc desc, + const struct bch_hash_info *info, + subvol_inum inum, + struct bkey_i *insert, + bch_str_hash_flags_t str_hash_flags) +{ + u32 snapshot; + int ret; + + ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); + if (ret) + return ret; + + insert->k.p.inode = inum.inum; + + return bch2_hash_set_snapshot(trans, desc, info, inum, + snapshot, insert, str_hash_flags, 0); } static __always_inline int bch2_hash_delete_at(struct btree_trans *trans, const struct bch_hash_desc desc, const struct bch_hash_info *info, - struct btree_iter *iter) + struct btree_iter *iter, + unsigned update_flags) { struct bkey_i *delete; int ret; + delete = bch2_trans_kmalloc(trans, sizeof(*delete)); + ret = PTR_ERR_OR_ZERO(delete); + if (ret) + return ret; + ret = bch2_hash_needs_whiteout(trans, desc, info, iter); if (ret < 0) return ret; - delete = bch2_trans_kmalloc(trans, sizeof(*delete)); - if (IS_ERR(delete)) - return PTR_ERR(delete); - bkey_init(&delete->k); delete->k.p = iter->pos; - delete->k.type = ret ? KEY_TYPE_whiteout : KEY_TYPE_deleted; + delete->k.type = ret ? KEY_TYPE_hash_whiteout : KEY_TYPE_deleted; - bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, delete)); - return 0; + return bch2_trans_update(trans, iter, delete, update_flags); } static __always_inline int bch2_hash_delete(struct btree_trans *trans, const struct bch_hash_desc desc, const struct bch_hash_info *info, - u64 inode, const void *key) + subvol_inum inum, const void *key) { - struct btree_iter *iter; + struct btree_iter iter; + int ret; - iter = bch2_hash_lookup(trans, desc, info, inode, key, + ret = bch2_hash_lookup(trans, &iter, desc, info, inum, key, BTREE_ITER_INTENT); - if (IS_ERR(iter)) - return PTR_ERR(iter); + if (ret) + return ret; - return bch2_hash_delete_at(trans, desc, info, iter); + ret = bch2_hash_delete_at(trans, desc, info, &iter, 0); + bch2_trans_iter_exit(trans, &iter); + return ret; } #endif /* _BCACHEFS_STR_HASH_H */