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