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(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) 169 { 170 struct bkey_s_c k; 171 u32 snapshot; 172 int ret; 173 174 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); 175 if (ret) 176 return ret; 177 178 for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id, 179 SPOS(inum.inum, desc.hash_key(info, key), snapshot), 180 POS(inum.inum, U64_MAX), 181 BTREE_ITER_SLOTS|flags, k, ret) { 182 if (is_visible_key(desc, inum, k)) { 183 if (!desc.cmp_key(k, key)) 184 return 0; 185 } else if (k.k->type == KEY_TYPE_hash_whiteout) { 186 ; 187 } else { 188 /* hole, not found */ 189 break; 190 } 191 } 192 bch2_trans_iter_exit(trans, iter); 193 194 return ret ?: -BCH_ERR_ENOENT_str_hash_lookup; 195 } 196 197 static __always_inline int 198 bch2_hash_hole(struct btree_trans *trans, 199 struct btree_iter *iter, 200 const struct bch_hash_desc desc, 201 const struct bch_hash_info *info, 202 subvol_inum inum, const void *key) 203 { 204 struct bkey_s_c k; 205 u32 snapshot; 206 int ret; 207 208 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); 209 if (ret) 210 return ret; 211 212 for_each_btree_key_upto_norestart(trans, *iter, desc.btree_id, 213 SPOS(inum.inum, desc.hash_key(info, key), snapshot), 214 POS(inum.inum, U64_MAX), 215 BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) 216 if (!is_visible_key(desc, inum, k)) 217 return 0; 218 bch2_trans_iter_exit(trans, iter); 219 220 return ret ?: -BCH_ERR_ENOSPC_str_hash_create; 221 } 222 223 static __always_inline 224 int bch2_hash_needs_whiteout(struct btree_trans *trans, 225 const struct bch_hash_desc desc, 226 const struct bch_hash_info *info, 227 struct btree_iter *start) 228 { 229 struct btree_iter iter; 230 struct bkey_s_c k; 231 int ret; 232 233 bch2_trans_copy_iter(&iter, start); 234 235 bch2_btree_iter_advance(&iter); 236 237 for_each_btree_key_continue_norestart(iter, BTREE_ITER_SLOTS, k, ret) { 238 if (k.k->type != desc.key_type && 239 k.k->type != KEY_TYPE_hash_whiteout) 240 break; 241 242 if (k.k->type == desc.key_type && 243 desc.hash_bkey(info, k) <= start->pos.offset) { 244 ret = 1; 245 break; 246 } 247 } 248 249 bch2_trans_iter_exit(trans, &iter); 250 return ret; 251 } 252 253 static __always_inline 254 int bch2_hash_set_snapshot(struct btree_trans *trans, 255 const struct bch_hash_desc desc, 256 const struct bch_hash_info *info, 257 subvol_inum inum, u32 snapshot, 258 struct bkey_i *insert, 259 bch_str_hash_flags_t str_hash_flags, 260 int update_flags) 261 { 262 struct btree_iter iter, slot = { NULL }; 263 struct bkey_s_c k; 264 bool found = false; 265 int ret; 266 267 for_each_btree_key_upto_norestart(trans, iter, desc.btree_id, 268 SPOS(insert->k.p.inode, 269 desc.hash_bkey(info, bkey_i_to_s_c(insert)), 270 snapshot), 271 POS(insert->k.p.inode, U64_MAX), 272 BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) { 273 if (is_visible_key(desc, inum, k)) { 274 if (!desc.cmp_bkey(k, bkey_i_to_s_c(insert))) 275 goto found; 276 277 /* hash collision: */ 278 continue; 279 } 280 281 if (!slot.path && 282 !(str_hash_flags & BCH_HASH_SET_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; 291 out: 292 bch2_trans_iter_exit(trans, &slot); 293 bch2_trans_iter_exit(trans, &iter); 294 295 return ret; 296 found: 297 found = true; 298 not_found: 299 300 if (!found && (str_hash_flags & BCH_HASH_SET_MUST_REPLACE)) { 301 ret = -BCH_ERR_ENOENT_str_hash_set_must_replace; 302 } else if (found && (str_hash_flags & BCH_HASH_SET_MUST_CREATE)) { 303 ret = -EEXIST; 304 } else { 305 if (!found && slot.path) 306 swap(iter, slot); 307 308 insert->k.p = iter.pos; 309 ret = bch2_trans_update(trans, &iter, insert, update_flags); 310 } 311 312 goto out; 313 } 314 315 static __always_inline 316 int bch2_hash_set(struct btree_trans *trans, 317 const struct bch_hash_desc desc, 318 const struct bch_hash_info *info, 319 subvol_inum inum, 320 struct bkey_i *insert, 321 bch_str_hash_flags_t str_hash_flags) 322 { 323 u32 snapshot; 324 int ret; 325 326 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); 327 if (ret) 328 return ret; 329 330 insert->k.p.inode = inum.inum; 331 332 return bch2_hash_set_snapshot(trans, desc, info, inum, 333 snapshot, insert, str_hash_flags, 0); 334 } 335 336 static __always_inline 337 int bch2_hash_delete_at(struct btree_trans *trans, 338 const struct bch_hash_desc desc, 339 const struct bch_hash_info *info, 340 struct btree_iter *iter, 341 unsigned update_flags) 342 { 343 struct bkey_i *delete; 344 int ret; 345 346 delete = bch2_trans_kmalloc(trans, sizeof(*delete)); 347 ret = PTR_ERR_OR_ZERO(delete); 348 if (ret) 349 return ret; 350 351 ret = bch2_hash_needs_whiteout(trans, desc, info, iter); 352 if (ret < 0) 353 return ret; 354 355 bkey_init(&delete->k); 356 delete->k.p = iter->pos; 357 delete->k.type = ret ? KEY_TYPE_hash_whiteout : KEY_TYPE_deleted; 358 359 return bch2_trans_update(trans, iter, delete, update_flags); 360 } 361 362 static __always_inline 363 int bch2_hash_delete(struct btree_trans *trans, 364 const struct bch_hash_desc desc, 365 const struct bch_hash_info *info, 366 subvol_inum inum, const void *key) 367 { 368 struct btree_iter iter; 369 int ret; 370 371 ret = bch2_hash_lookup(trans, &iter, desc, info, inum, key, 372 BTREE_ITER_INTENT); 373 if (ret) 374 return ret; 375 376 ret = bch2_hash_delete_at(trans, desc, info, &iter, 0); 377 bch2_trans_iter_exit(trans, &iter); 378 return ret; 379 } 380 381 #endif /* _BCACHEFS_STR_HASH_H */ 382