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 static inline enum bch_str_hash_type 19 bch2_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_siphash 29 : BCH_STR_HASH_siphash_old; 30 default: 31 BUG(); 32 } 33 } 34 35 struct bch_hash_info { 36 u8 type; 37 /* 38 * For crc32 or crc64 string hashes the first key value of 39 * the siphash_key (k0) is used as the key. 40 */ 41 SIPHASH_KEY siphash_key; 42 }; 43 44 static inline struct bch_hash_info 45 bch2_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 67 struct bch_str_hash_ctx { 68 union { 69 u32 crc32c; 70 u64 crc64; 71 SIPHASH_CTX siphash; 72 }; 73 }; 74 75 static 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 96 static 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 116 static 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 132 struct 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 143 static 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 151 static __always_inline struct bkey_s_c 152 bch2_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 182 static __always_inline struct bkey_s_c 183 bch2_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 198 static __always_inline int 199 bch2_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 224 static __always_inline 225 int 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 254 static __always_inline 255 struct 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; 291 out: 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; 295 found: 296 found = true; 297 not_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 314 static __always_inline 315 int 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 336 static __always_inline 337 int 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 352 static __always_inline 353 int 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 378 static __always_inline 379 int 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