397 lines · c
1/* SPDX-License-Identifier: GPL-2.0 */2#ifndef _BCACHEFS_STR_HASH_H3#define _BCACHEFS_STR_HASH_H4 5#include "btree_iter.h"6#include "btree_update.h"7#include "checksum.h"8#include "error.h"9#include "inode.h"10#include "siphash.h"11#include "subvolume.h"12#include "super.h"13 14#include <linux/crc32c.h>15#include <crypto/hash.h>16#include <crypto/sha2.h>17 18static inline enum bch_str_hash_type19bch2_str_hash_opt_to_type(struct bch_fs *c, enum bch_str_hash_opts opt)20{21 switch (opt) {22 case BCH_STR_HASH_OPT_crc32c:23 return BCH_STR_HASH_crc32c;24 case BCH_STR_HASH_OPT_crc64:25 return BCH_STR_HASH_crc64;26 case BCH_STR_HASH_OPT_siphash:27 return c->sb.features & (1ULL << BCH_FEATURE_new_siphash)28 ? BCH_STR_HASH_siphash29 : BCH_STR_HASH_siphash_old;30 default:31 BUG();32 }33}34 35struct bch_hash_info {36 u8 type;37 /*38 * For crc32 or crc64 string hashes the first key value of39 * the siphash_key (k0) is used as the key.40 */41 SIPHASH_KEY siphash_key;42};43 44static inline struct bch_hash_info45bch2_hash_info_init(struct bch_fs *c, const struct bch_inode_unpacked *bi)46{47 /* XXX ick */48 struct bch_hash_info info = {49 .type = INODE_STR_HASH(bi),50 .siphash_key = { .k0 = bi->bi_hash_seed }51 };52 53 if (unlikely(info.type == BCH_STR_HASH_siphash_old)) {54 SHASH_DESC_ON_STACK(desc, c->sha256);55 u8 digest[SHA256_DIGEST_SIZE];56 57 desc->tfm = c->sha256;58 59 crypto_shash_digest(desc, (void *) &bi->bi_hash_seed,60 sizeof(bi->bi_hash_seed), digest);61 memcpy(&info.siphash_key, digest, sizeof(info.siphash_key));62 }63 64 return info;65}66 67struct bch_str_hash_ctx {68 union {69 u32 crc32c;70 u64 crc64;71 SIPHASH_CTX siphash;72 };73};74 75static inline void bch2_str_hash_init(struct bch_str_hash_ctx *ctx,76 const struct bch_hash_info *info)77{78 switch (info->type) {79 case BCH_STR_HASH_crc32c:80 ctx->crc32c = crc32c(~0, &info->siphash_key.k0,81 sizeof(info->siphash_key.k0));82 break;83 case BCH_STR_HASH_crc64:84 ctx->crc64 = crc64_be(~0, &info->siphash_key.k0,85 sizeof(info->siphash_key.k0));86 break;87 case BCH_STR_HASH_siphash_old:88 case BCH_STR_HASH_siphash:89 SipHash24_Init(&ctx->siphash, &info->siphash_key);90 break;91 default:92 BUG();93 }94}95 96static inline void bch2_str_hash_update(struct bch_str_hash_ctx *ctx,97 const struct bch_hash_info *info,98 const void *data, size_t len)99{100 switch (info->type) {101 case BCH_STR_HASH_crc32c:102 ctx->crc32c = crc32c(ctx->crc32c, data, len);103 break;104 case BCH_STR_HASH_crc64:105 ctx->crc64 = crc64_be(ctx->crc64, data, len);106 break;107 case BCH_STR_HASH_siphash_old:108 case BCH_STR_HASH_siphash:109 SipHash24_Update(&ctx->siphash, data, len);110 break;111 default:112 BUG();113 }114}115 116static inline u64 bch2_str_hash_end(struct bch_str_hash_ctx *ctx,117 const struct bch_hash_info *info)118{119 switch (info->type) {120 case BCH_STR_HASH_crc32c:121 return ctx->crc32c;122 case BCH_STR_HASH_crc64:123 return ctx->crc64 >> 1;124 case BCH_STR_HASH_siphash_old:125 case BCH_STR_HASH_siphash:126 return SipHash24_End(&ctx->siphash) >> 1;127 default:128 BUG();129 }130}131 132struct bch_hash_desc {133 enum btree_id btree_id;134 u8 key_type;135 136 u64 (*hash_key)(const struct bch_hash_info *, const void *);137 u64 (*hash_bkey)(const struct bch_hash_info *, struct bkey_s_c);138 bool (*cmp_key)(struct bkey_s_c, const void *);139 bool (*cmp_bkey)(struct bkey_s_c, struct bkey_s_c);140 bool (*is_visible)(subvol_inum inum, struct bkey_s_c);141};142 143static inline bool is_visible_key(struct bch_hash_desc desc, subvol_inum inum, struct bkey_s_c k)144{145 return k.k->type == desc.key_type &&146 (!desc.is_visible ||147 !inum.inum ||148 desc.is_visible(inum, k));149}150 151static __always_inline struct bkey_s_c152bch2_hash_lookup_in_snapshot(struct btree_trans *trans,153 struct btree_iter *iter,154 const struct bch_hash_desc desc,155 const struct bch_hash_info *info,156 subvol_inum inum, const void *key,157 enum btree_iter_update_trigger_flags flags,158 u32 snapshot)159{160 struct bkey_s_c k;161 int ret;162 163 for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id,164 SPOS(inum.inum, desc.hash_key(info, key), snapshot),165 POS(inum.inum, U64_MAX),166 BTREE_ITER_slots|flags, k, ret) {167 if (is_visible_key(desc, inum, k)) {168 if (!desc.cmp_key(k, key))169 return k;170 } else if (k.k->type == KEY_TYPE_hash_whiteout) {171 ;172 } else {173 /* hole, not found */174 break;175 }176 }177 bch2_trans_iter_exit(trans, iter);178 179 return bkey_s_c_err(ret ?: -BCH_ERR_ENOENT_str_hash_lookup);180}181 182static __always_inline struct bkey_s_c183bch2_hash_lookup(struct btree_trans *trans,184 struct btree_iter *iter,185 const struct bch_hash_desc desc,186 const struct bch_hash_info *info,187 subvol_inum inum, const void *key,188 enum btree_iter_update_trigger_flags flags)189{190 u32 snapshot;191 int ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);192 if (ret)193 return bkey_s_c_err(ret);194 195 return bch2_hash_lookup_in_snapshot(trans, iter, desc, info, inum, key, flags, snapshot);196}197 198static __always_inline int199bch2_hash_hole(struct btree_trans *trans,200 struct btree_iter *iter,201 const struct bch_hash_desc desc,202 const struct bch_hash_info *info,203 subvol_inum inum, const void *key)204{205 struct bkey_s_c k;206 u32 snapshot;207 int ret;208 209 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);210 if (ret)211 return ret;212 213 for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id,214 SPOS(inum.inum, desc.hash_key(info, key), snapshot),215 POS(inum.inum, U64_MAX),216 BTREE_ITER_slots|BTREE_ITER_intent, k, ret)217 if (!is_visible_key(desc, inum, k))218 return 0;219 bch2_trans_iter_exit(trans, iter);220 221 return ret ?: -BCH_ERR_ENOSPC_str_hash_create;222}223 224static __always_inline225int bch2_hash_needs_whiteout(struct btree_trans *trans,226 const struct bch_hash_desc desc,227 const struct bch_hash_info *info,228 struct btree_iter *start)229{230 struct btree_iter iter;231 struct bkey_s_c k;232 int ret;233 234 bch2_trans_copy_iter(&iter, start);235 236 bch2_btree_iter_advance(&iter);237 238 for_each_btree_key_continue_norestart(iter, BTREE_ITER_slots, k, ret) {239 if (k.k->type != desc.key_type &&240 k.k->type != KEY_TYPE_hash_whiteout)241 break;242 243 if (k.k->type == desc.key_type &&244 desc.hash_bkey(info, k) <= start->pos.offset) {245 ret = 1;246 break;247 }248 }249 250 bch2_trans_iter_exit(trans, &iter);251 return ret;252}253 254static __always_inline255struct bkey_s_c bch2_hash_set_or_get_in_snapshot(struct btree_trans *trans,256 struct btree_iter *iter,257 const struct bch_hash_desc desc,258 const struct bch_hash_info *info,259 subvol_inum inum, u32 snapshot,260 struct bkey_i *insert,261 enum btree_iter_update_trigger_flags flags)262{263 struct btree_iter slot = {};264 struct bkey_s_c k;265 bool found = false;266 int ret;267 268 for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id,269 SPOS(insert->k.p.inode,270 desc.hash_bkey(info, bkey_i_to_s_c(insert)),271 snapshot),272 POS(insert->k.p.inode, U64_MAX),273 BTREE_ITER_slots|BTREE_ITER_intent|flags, k, ret) {274 if (is_visible_key(desc, inum, k)) {275 if (!desc.cmp_bkey(k, bkey_i_to_s_c(insert)))276 goto found;277 278 /* hash collision: */279 continue;280 }281 282 if (!slot.path && !(flags & STR_HASH_must_replace))283 bch2_trans_copy_iter(&slot, iter);284 285 if (k.k->type != KEY_TYPE_hash_whiteout)286 goto not_found;287 }288 289 if (!ret)290 ret = -BCH_ERR_ENOSPC_str_hash_create;291out:292 bch2_trans_iter_exit(trans, &slot);293 bch2_trans_iter_exit(trans, iter);294 return ret ? bkey_s_c_err(ret) : bkey_s_c_null;295found:296 found = true;297not_found:298 if (found && (flags & STR_HASH_must_create)) {299 bch2_trans_iter_exit(trans, &slot);300 return k;301 } else if (!found && (flags & STR_HASH_must_replace)) {302 ret = -BCH_ERR_ENOENT_str_hash_set_must_replace;303 } else {304 if (!found && slot.path)305 swap(*iter, slot);306 307 insert->k.p = iter->pos;308 ret = bch2_trans_update(trans, iter, insert, flags);309 }310 311 goto out;312}313 314static __always_inline315int bch2_hash_set_in_snapshot(struct btree_trans *trans,316 const struct bch_hash_desc desc,317 const struct bch_hash_info *info,318 subvol_inum inum, u32 snapshot,319 struct bkey_i *insert,320 enum btree_iter_update_trigger_flags flags)321{322 struct btree_iter iter;323 struct bkey_s_c k = bch2_hash_set_or_get_in_snapshot(trans, &iter, desc, info, inum,324 snapshot, insert, flags);325 int ret = bkey_err(k);326 if (ret)327 return ret;328 if (k.k) {329 bch2_trans_iter_exit(trans, &iter);330 return -BCH_ERR_EEXIST_str_hash_set;331 }332 333 return 0;334}335 336static __always_inline337int bch2_hash_set(struct btree_trans *trans,338 const struct bch_hash_desc desc,339 const struct bch_hash_info *info,340 subvol_inum inum,341 struct bkey_i *insert,342 enum btree_iter_update_trigger_flags flags)343{344 insert->k.p.inode = inum.inum;345 346 u32 snapshot;347 return bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot) ?:348 bch2_hash_set_in_snapshot(trans, desc, info, inum,349 snapshot, insert, flags);350}351 352static __always_inline353int bch2_hash_delete_at(struct btree_trans *trans,354 const struct bch_hash_desc desc,355 const struct bch_hash_info *info,356 struct btree_iter *iter,357 enum btree_iter_update_trigger_flags flags)358{359 struct bkey_i *delete;360 int ret;361 362 delete = bch2_trans_kmalloc(trans, sizeof(*delete));363 ret = PTR_ERR_OR_ZERO(delete);364 if (ret)365 return ret;366 367 ret = bch2_hash_needs_whiteout(trans, desc, info, iter);368 if (ret < 0)369 return ret;370 371 bkey_init(&delete->k);372 delete->k.p = iter->pos;373 delete->k.type = ret ? KEY_TYPE_hash_whiteout : KEY_TYPE_deleted;374 375 return bch2_trans_update(trans, iter, delete, flags);376}377 378static __always_inline379int bch2_hash_delete(struct btree_trans *trans,380 const struct bch_hash_desc desc,381 const struct bch_hash_info *info,382 subvol_inum inum, const void *key)383{384 struct btree_iter iter;385 struct bkey_s_c k = bch2_hash_lookup(trans, &iter, desc, info, inum, key,386 BTREE_ITER_intent);387 int ret = bkey_err(k);388 if (ret)389 return ret;390 391 ret = bch2_hash_delete_at(trans, desc, info, &iter, 0);392 bch2_trans_iter_exit(trans, &iter);393 return ret;394}395 396#endif /* _BCACHEFS_STR_HASH_H */397