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/sha2.h>
16
17 static inline enum bch_str_hash_type
bch2_str_hash_opt_to_type(struct bch_fs * c,enum bch_str_hash_opts opt)18 bch2_str_hash_opt_to_type(struct bch_fs *c, enum bch_str_hash_opts opt)
19 {
20 switch (opt) {
21 case BCH_STR_HASH_OPT_crc32c:
22 return BCH_STR_HASH_crc32c;
23 case BCH_STR_HASH_OPT_crc64:
24 return BCH_STR_HASH_crc64;
25 case BCH_STR_HASH_OPT_siphash:
26 return c->sb.features & (1ULL << BCH_FEATURE_new_siphash)
27 ? BCH_STR_HASH_siphash
28 : BCH_STR_HASH_siphash_old;
29 default:
30 BUG();
31 }
32 }
33
34 struct bch_hash_info {
35 u32 inum_snapshot;
36 u8 type;
37 struct unicode_map *cf_encoding;
38 /*
39 * For crc32 or crc64 string hashes the first key value of
40 * the siphash_key (k0) is used as the key.
41 */
42 SIPHASH_KEY siphash_key;
43 };
44
45 static inline struct bch_hash_info
bch2_hash_info_init(struct bch_fs * c,const struct bch_inode_unpacked * bi)46 bch2_hash_info_init(struct bch_fs *c, const struct bch_inode_unpacked *bi)
47 {
48 struct bch_hash_info info = {
49 .inum_snapshot = bi->bi_snapshot,
50 .type = INODE_STR_HASH(bi),
51 .cf_encoding = bch2_inode_casefold(c, bi) ? c->cf_encoding : NULL,
52 .siphash_key = { .k0 = bi->bi_hash_seed }
53 };
54
55 if (unlikely(info.type == BCH_STR_HASH_siphash_old)) {
56 u8 digest[SHA256_DIGEST_SIZE];
57
58 sha256((const u8 *)&bi->bi_hash_seed,
59 sizeof(bi->bi_hash_seed), digest);
60 memcpy(&info.siphash_key, digest, sizeof(info.siphash_key));
61 }
62
63 return info;
64 }
65
66 struct bch_str_hash_ctx {
67 union {
68 u32 crc32c;
69 u64 crc64;
70 SIPHASH_CTX siphash;
71 };
72 };
73
bch2_str_hash_init(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info)74 static inline void bch2_str_hash_init(struct bch_str_hash_ctx *ctx,
75 const struct bch_hash_info *info)
76 {
77 switch (info->type) {
78 case BCH_STR_HASH_crc32c:
79 ctx->crc32c = crc32c(~0, &info->siphash_key.k0,
80 sizeof(info->siphash_key.k0));
81 break;
82 case BCH_STR_HASH_crc64:
83 ctx->crc64 = crc64_be(~0, &info->siphash_key.k0,
84 sizeof(info->siphash_key.k0));
85 break;
86 case BCH_STR_HASH_siphash_old:
87 case BCH_STR_HASH_siphash:
88 SipHash24_Init(&ctx->siphash, &info->siphash_key);
89 break;
90 default:
91 BUG();
92 }
93 }
94
bch2_str_hash_update(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info,const void * data,size_t len)95 static inline void bch2_str_hash_update(struct bch_str_hash_ctx *ctx,
96 const struct bch_hash_info *info,
97 const void *data, size_t len)
98 {
99 switch (info->type) {
100 case BCH_STR_HASH_crc32c:
101 ctx->crc32c = crc32c(ctx->crc32c, data, len);
102 break;
103 case BCH_STR_HASH_crc64:
104 ctx->crc64 = crc64_be(ctx->crc64, data, len);
105 break;
106 case BCH_STR_HASH_siphash_old:
107 case BCH_STR_HASH_siphash:
108 SipHash24_Update(&ctx->siphash, data, len);
109 break;
110 default:
111 BUG();
112 }
113 }
114
bch2_str_hash_end(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info)115 static inline u64 bch2_str_hash_end(struct bch_str_hash_ctx *ctx,
116 const struct bch_hash_info *info)
117 {
118 switch (info->type) {
119 case BCH_STR_HASH_crc32c:
120 return ctx->crc32c;
121 case BCH_STR_HASH_crc64:
122 return ctx->crc64 >> 1;
123 case BCH_STR_HASH_siphash_old:
124 case BCH_STR_HASH_siphash:
125 return SipHash24_End(&ctx->siphash) >> 1;
126 default:
127 BUG();
128 }
129 }
130
131 struct bch_hash_desc {
132 enum btree_id btree_id;
133 u8 key_type;
134
135 u64 (*hash_key)(const struct bch_hash_info *, const void *);
136 u64 (*hash_bkey)(const struct bch_hash_info *, struct bkey_s_c);
137 bool (*cmp_key)(struct bkey_s_c, const void *);
138 bool (*cmp_bkey)(struct bkey_s_c, struct bkey_s_c);
139 bool (*is_visible)(subvol_inum inum, struct bkey_s_c);
140 };
141
is_visible_key(struct bch_hash_desc desc,subvol_inum inum,struct bkey_s_c k)142 static inline bool is_visible_key(struct bch_hash_desc desc, subvol_inum inum, struct bkey_s_c k)
143 {
144 return k.k->type == desc.key_type &&
145 (!desc.is_visible ||
146 !inum.inum ||
147 desc.is_visible(inum, k));
148 }
149
150 static __always_inline struct bkey_s_c
bch2_hash_lookup_in_snapshot(struct btree_trans * trans,struct btree_iter * iter,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,const void * key,enum btree_iter_update_trigger_flags flags,u32 snapshot)151 bch2_hash_lookup_in_snapshot(struct btree_trans *trans,
152 struct btree_iter *iter,
153 const struct bch_hash_desc desc,
154 const struct bch_hash_info *info,
155 subvol_inum inum, const void *key,
156 enum btree_iter_update_trigger_flags flags,
157 u32 snapshot)
158 {
159 struct bkey_s_c k;
160 int ret;
161
162 for_each_btree_key_max_norestart(trans, *iter, desc.btree_id,
163 SPOS(inum.inum, desc.hash_key(info, key), snapshot),
164 POS(inum.inum, U64_MAX),
165 BTREE_ITER_slots|flags, k, ret) {
166 if (is_visible_key(desc, inum, k)) {
167 if (!desc.cmp_key(k, key))
168 return k;
169 } else if (k.k->type == KEY_TYPE_hash_whiteout) {
170 ;
171 } else {
172 /* hole, not found */
173 break;
174 }
175 }
176 bch2_trans_iter_exit(trans, iter);
177
178 return bkey_s_c_err(ret ?: -BCH_ERR_ENOENT_str_hash_lookup);
179 }
180
181 static __always_inline struct bkey_s_c
bch2_hash_lookup(struct btree_trans * trans,struct btree_iter * iter,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,const void * key,enum btree_iter_update_trigger_flags flags)182 bch2_hash_lookup(struct btree_trans *trans,
183 struct btree_iter *iter,
184 const struct bch_hash_desc desc,
185 const struct bch_hash_info *info,
186 subvol_inum inum, const void *key,
187 enum btree_iter_update_trigger_flags flags)
188 {
189 u32 snapshot;
190 int ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);
191 if (ret)
192 return bkey_s_c_err(ret);
193
194 return bch2_hash_lookup_in_snapshot(trans, iter, desc, info, inum, key, flags, snapshot);
195 }
196
197 static __always_inline int
bch2_hash_hole(struct btree_trans * trans,struct btree_iter * iter,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,const void * key)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_max_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
bch2_hash_needs_whiteout(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,struct btree_iter * start)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(trans, &iter, start);
234
235 bch2_btree_iter_advance(trans, &iter);
236
237 for_each_btree_key_continue_norestart(trans, 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
bch2_hash_set_or_get_in_snapshot(struct btree_trans * trans,struct btree_iter * iter,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,u32 snapshot,struct bkey_i * insert,enum btree_iter_update_trigger_flags flags)254 struct bkey_s_c bch2_hash_set_or_get_in_snapshot(struct btree_trans *trans,
255 struct btree_iter *iter,
256 const struct bch_hash_desc desc,
257 const struct bch_hash_info *info,
258 subvol_inum inum, u32 snapshot,
259 struct bkey_i *insert,
260 enum btree_iter_update_trigger_flags flags)
261 {
262 struct bch_fs *c = trans->c;
263 struct btree_iter slot = {};
264 struct bkey_s_c k;
265 bool found = false;
266 int ret;
267
268 for_each_btree_key_max_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(trans, &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_throw(c, 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_throw(c, 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
bch2_hash_set_in_snapshot(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,u32 snapshot,struct bkey_i * insert,enum btree_iter_update_trigger_flags flags)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_throw(trans->c, EEXIST_str_hash_set);
331 }
332
333 return 0;
334 }
335
336 static __always_inline
bch2_hash_set(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,struct bkey_i * insert,enum btree_iter_update_trigger_flags flags)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
bch2_hash_delete_at(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,struct btree_iter * iter,enum btree_iter_update_trigger_flags flags)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
bch2_hash_delete(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,subvol_inum inum,const void * key)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 int bch2_repair_inode_hash_info(struct btree_trans *, struct bch_inode_unpacked *);
397
398 struct snapshots_seen;
399 int bch2_str_hash_repair_key(struct btree_trans *,
400 struct snapshots_seen *,
401 const struct bch_hash_desc *,
402 struct bch_hash_info *,
403 struct btree_iter *, struct bkey_s_c,
404 struct btree_iter *, struct bkey_s_c,
405 bool *);
406
407 int __bch2_str_hash_check_key(struct btree_trans *,
408 struct snapshots_seen *,
409 const struct bch_hash_desc *,
410 struct bch_hash_info *,
411 struct btree_iter *, struct bkey_s_c,
412 bool *);
413
bch2_str_hash_check_key(struct btree_trans * trans,struct snapshots_seen * s,const struct bch_hash_desc * desc,struct bch_hash_info * hash_info,struct btree_iter * k_iter,struct bkey_s_c hash_k,bool * updated_before_k_pos)414 static inline int bch2_str_hash_check_key(struct btree_trans *trans,
415 struct snapshots_seen *s,
416 const struct bch_hash_desc *desc,
417 struct bch_hash_info *hash_info,
418 struct btree_iter *k_iter, struct bkey_s_c hash_k,
419 bool *updated_before_k_pos)
420 {
421 if (hash_k.k->type != desc->key_type)
422 return 0;
423
424 if (likely(desc->hash_bkey(hash_info, hash_k) == hash_k.k->p.offset))
425 return 0;
426
427 return __bch2_str_hash_check_key(trans, s, desc, hash_info, k_iter, hash_k,
428 updated_before_k_pos);
429 }
430
431 #endif /* _BCACHEFS_STR_HASH_H */
432