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 18 typedef unsigned __bitwise bch_str_hash_flags_t; 19 20 enum 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 28 static inline enum bch_str_hash_type 29 bch2_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 45 struct 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 54 static inline struct bch_hash_info 55 bch2_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 78 struct bch_str_hash_ctx { 79 union { 80 u32 crc32c; 81 u64 crc64; 82 SIPHASH_CTX siphash; 83 }; 84 }; 85 86 static 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 107 static 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 127 static 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 143 struct 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 154 static 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 162 static __always_inline int 163 bch2_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 192 static __always_inline int 193 bch2_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 205 static __always_inline int 206 bch2_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 231 static __always_inline 232 int 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 261 static __always_inline 262 int 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; 299 out: 300 bch2_trans_iter_exit(trans, &slot); 301 bch2_trans_iter_exit(trans, &iter); 302 303 return ret; 304 found: 305 found = true; 306 not_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 323 static __always_inline 324 int 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 339 static __always_inline 340 int 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 365 static __always_inline 366 int 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