summaryrefslogtreecommitdiff
path: root/libbcache/str_hash.h
diff options
context:
space:
mode:
Diffstat (limited to 'libbcache/str_hash.h')
-rw-r--r--libbcache/str_hash.h352
1 files changed, 352 insertions, 0 deletions
diff --git a/libbcache/str_hash.h b/libbcache/str_hash.h
new file mode 100644
index 00000000..9a718a8e
--- /dev/null
+++ b/libbcache/str_hash.h
@@ -0,0 +1,352 @@
+#ifndef _BCACHE_STR_HASH_H
+#define _BCACHE_STR_HASH_H
+
+#include "btree_iter.h"
+#include "checksum.h"
+#include "siphash.h"
+#include "super.h"
+
+#include <crypto/sha1_base.h>
+#include <linux/crc32c.h>
+
+static const SIPHASH_KEY bch_siphash_key = {
+ .k0 = cpu_to_le64(0x5a9585fd80087730ULL),
+ .k1 = cpu_to_le64(0xc8de666d50b45664ULL ),
+};
+
+struct bch_str_hash_ctx {
+ union {
+ u32 crc32c;
+ u64 crc64;
+ SIPHASH_CTX siphash;
+ };
+};
+
+static inline void bch_str_hash_init(struct bch_str_hash_ctx *ctx,
+ enum bch_str_hash_type type)
+{
+ switch (type) {
+ case BCH_STR_HASH_CRC32C:
+ ctx->crc32c = ~0;
+ break;
+ case BCH_STR_HASH_CRC64:
+ ctx->crc64 = ~0;
+ break;
+ case BCH_STR_HASH_SIPHASH:
+ SipHash24_Init(&ctx->siphash, &bch_siphash_key);
+ break;
+ default:
+ BUG();
+ }
+}
+
+static inline void bch_str_hash_update(struct bch_str_hash_ctx *ctx,
+ enum bch_str_hash_type type,
+ const void *data, size_t len)
+{
+ switch (type) {
+ case BCH_STR_HASH_CRC32C:
+ ctx->crc32c = crc32c(ctx->crc32c, data, len);
+ break;
+ case BCH_STR_HASH_CRC64:
+ ctx->crc64 = bch_crc64_update(ctx->crc64, data, len);
+ break;
+ case BCH_STR_HASH_SIPHASH:
+ SipHash24_Update(&ctx->siphash, data, len);
+ break;
+ default:
+ BUG();
+ }
+}
+
+static inline u64 bch_str_hash_end(struct bch_str_hash_ctx *ctx,
+ enum bch_str_hash_type type)
+{
+ switch (type) {
+ case BCH_STR_HASH_CRC32C:
+ return ctx->crc32c;
+ case BCH_STR_HASH_CRC64:
+ return ctx->crc64 >> 1;
+ case BCH_STR_HASH_SIPHASH:
+ return SipHash24_End(&ctx->siphash) >> 1;
+ default:
+ BUG();
+ }
+}
+
+struct bch_hash_info {
+ u64 seed;
+ u8 type;
+};
+
+struct bch_hash_desc {
+ enum btree_id btree_id;
+ u8 key_type;
+ u8 whiteout_type;
+
+ u64 (*hash_key)(const struct bch_hash_info *, const void *);
+ 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);
+};
+
+static inline struct bkey_s_c
+bch_hash_lookup_at(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct btree_iter *iter, const void *search)
+{
+ u64 inode = iter->pos.inode;
+
+ do {
+ struct bkey_s_c k = bch_btree_iter_peek_with_holes(iter);
+
+ if (btree_iter_err(k))
+ return k;
+
+ if (k.k->type == desc.key_type) {
+ if (!desc.cmp_key(k, search))
+ return k;
+ } else if (k.k->type == desc.whiteout_type) {
+ ;
+ } else {
+ /* hole, not found */
+ break;
+ }
+
+ bch_btree_iter_advance_pos(iter);
+ } while (iter->pos.inode == inode);
+
+ return bkey_s_c_err(-ENOENT);
+}
+
+static inline struct bkey_s_c
+bch_hash_lookup_bkey_at(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct btree_iter *iter, struct bkey_s_c search)
+{
+ u64 inode = iter->pos.inode;
+
+ do {
+ struct bkey_s_c k = bch_btree_iter_peek_with_holes(iter);
+
+ if (btree_iter_err(k))
+ return k;
+
+ if (k.k->type == desc.key_type) {
+ if (!desc.cmp_bkey(k, search))
+ return k;
+ } else if (k.k->type == desc.whiteout_type) {
+ ;
+ } else {
+ /* hole, not found */
+ break;
+ }
+
+ bch_btree_iter_advance_pos(iter);
+ } while (iter->pos.inode == inode);
+
+ return bkey_s_c_err(-ENOENT);
+}
+
+static inline struct bkey_s_c
+bch_hash_lookup(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct cache_set *c, u64 inode,
+ struct btree_iter *iter, const void *key)
+{
+ bch_btree_iter_init(iter, c, desc.btree_id,
+ POS(inode, desc.hash_key(info, key)));
+
+ return bch_hash_lookup_at(desc, info, iter, key);
+}
+
+static inline struct bkey_s_c
+bch_hash_lookup_intent(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct cache_set *c, u64 inode,
+ struct btree_iter *iter, const void *key)
+{
+ bch_btree_iter_init_intent(iter, c, desc.btree_id,
+ POS(inode, desc.hash_key(info, key)));
+
+ return bch_hash_lookup_at(desc, info, iter, key);
+}
+
+static inline struct bkey_s_c
+bch_hash_hole_at(const struct bch_hash_desc desc, struct btree_iter *iter)
+{
+ while (1) {
+ struct bkey_s_c k = bch_btree_iter_peek_with_holes(iter);
+
+ if (btree_iter_err(k))
+ return k;
+
+ if (k.k->type != desc.key_type)
+ return k;
+
+ /* hash collision, keep going */
+ bch_btree_iter_advance_pos(iter);
+ if (iter->pos.inode != k.k->p.inode)
+ return bkey_s_c_err(-ENOENT);
+ }
+}
+
+static inline struct bkey_s_c bch_hash_hole(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct cache_set *c, u64 inode,
+ struct btree_iter *iter,
+ const void *key)
+{
+ bch_btree_iter_init_intent(iter, c, desc.btree_id,
+ POS(inode, desc.hash_key(info, key)));
+
+ return bch_hash_hole_at(desc, iter);
+}
+
+static inline int bch_hash_needs_whiteout(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct btree_iter *iter,
+ struct btree_iter *start)
+{
+ bch_btree_iter_set_pos(iter,
+ btree_type_successor(start->btree_id, start->pos));
+
+ while (1) {
+ struct bkey_s_c k = bch_btree_iter_peek_with_holes(iter);
+ int ret = btree_iter_err(k);
+
+ if (ret)
+ return ret;
+
+ if (k.k->type != desc.key_type &&
+ k.k->type != desc.whiteout_type)
+ return false;
+
+ if (k.k->type == desc.key_type &&
+ desc.hash_bkey(info, k) <= start->pos.offset)
+ return true;
+
+ bch_btree_iter_advance_pos(iter);
+ }
+}
+
+#define BCH_HASH_SET_MUST_CREATE 1
+#define BCH_HASH_SET_MUST_REPLACE 2
+
+static inline int bch_hash_set(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct cache_set *c, u64 inode,
+ u64 *journal_seq,
+ struct bkey_i *insert, int flags)
+{
+ struct btree_iter iter, hashed_slot;
+ struct bkey_s_c k;
+ int ret;
+
+ bch_btree_iter_init_intent(&hashed_slot, c, desc.btree_id,
+ POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))));
+ bch_btree_iter_init_intent(&iter, c, desc.btree_id, hashed_slot.pos);
+ bch_btree_iter_link(&hashed_slot, &iter);
+retry:
+ /*
+ * On hash collision, we have to keep the slot we hashed to locked while
+ * we do the insert - to avoid racing with another thread deleting
+ * whatever's in the slot we hashed to:
+ */
+ ret = bch_btree_iter_traverse(&hashed_slot);
+ if (ret)
+ goto err;
+
+ /*
+ * On -EINTR/retry, we dropped locks - always restart from the slot we
+ * hashed to:
+ */
+ bch_btree_iter_copy(&iter, &hashed_slot);
+
+ k = bch_hash_lookup_bkey_at(desc, info, &iter, bkey_i_to_s_c(insert));
+
+ ret = btree_iter_err(k);
+ if (ret == -ENOENT) {
+ if (flags & BCH_HASH_SET_MUST_REPLACE) {
+ ret = -ENOENT;
+ goto err;
+ }
+
+ /*
+ * Not found, so we're now looking for any open
+ * slot - we might have skipped over a whiteout
+ * that we could have used, so restart from the
+ * slot we hashed to:
+ */
+ bch_btree_iter_copy(&iter, &hashed_slot);
+ k = bch_hash_hole_at(desc, &iter);
+ if ((ret = btree_iter_err(k)))
+ goto err;
+ } else if (!ret) {
+ if (flags & BCH_HASH_SET_MUST_CREATE) {
+ ret = -EEXIST;
+ goto err;
+ }
+ } else {
+ goto err;
+ }
+
+ insert->k.p = iter.pos;
+ ret = bch_btree_insert_at(c, NULL, NULL, journal_seq,
+ BTREE_INSERT_ATOMIC,
+ BTREE_INSERT_ENTRY(&iter, insert));
+err:
+ if (ret == -EINTR)
+ goto retry;
+
+ /*
+ * On successful insert, we don't want to clobber ret with error from
+ * iter:
+ */
+ bch_btree_iter_unlock(&iter);
+ bch_btree_iter_unlock(&hashed_slot);
+ return ret;
+}
+
+static inline int bch_hash_delete(const struct bch_hash_desc desc,
+ const struct bch_hash_info *info,
+ struct cache_set *c, u64 inode,
+ u64 *journal_seq, const void *key)
+{
+ struct btree_iter iter, whiteout_iter;
+ struct bkey_s_c k;
+ struct bkey_i delete;
+ int ret = -ENOENT;
+
+ bch_btree_iter_init_intent(&iter, c, desc.btree_id,
+ POS(inode, desc.hash_key(info, key)));
+ bch_btree_iter_init(&whiteout_iter, c, desc.btree_id,
+ POS(inode, desc.hash_key(info, key)));
+ bch_btree_iter_link(&iter, &whiteout_iter);
+retry:
+ k = bch_hash_lookup_at(desc, info, &iter, key);
+ if ((ret = btree_iter_err(k)))
+ goto err;
+
+ ret = bch_hash_needs_whiteout(desc, info, &whiteout_iter, &iter);
+ if (ret < 0)
+ goto err;
+
+ bkey_init(&delete.k);
+ delete.k.p = k.k->p;
+ delete.k.type = ret ? desc.whiteout_type : KEY_TYPE_DELETED;
+
+ ret = bch_btree_insert_at(c, NULL, NULL, journal_seq,
+ BTREE_INSERT_NOFAIL|
+ BTREE_INSERT_ATOMIC,
+ BTREE_INSERT_ENTRY(&iter, &delete));
+err:
+ if (ret == -EINTR)
+ goto retry;
+
+ bch_btree_iter_unlock(&whiteout_iter);
+ bch_btree_iter_unlock(&iter);
+ return ret;
+}
+
+#endif /* _BCACHE_STR_HASH_H */
generated by cgit v1.2.3 (git 2.46.0) at 2025-07-01 06:42:22 +0000