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 u8 type;
36 struct unicode_map *cf_encoding;
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
bch2_hash_info_init(struct bch_fs * c,const struct bch_inode_unpacked * bi)45 bch2_hash_info_init(struct bch_fs *c, const struct bch_inode_unpacked *bi)
46 {
47 struct bch_hash_info info = {
48 .type = INODE_STR_HASH(bi),
49 #ifdef CONFIG_UNICODE
50 .cf_encoding = bch2_inode_casefold(c, bi) ? c->cf_encoding : NULL,
51 #endif
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 btree_iter slot = {};
263 struct bkey_s_c k;
264 bool found = false;
265 int ret;
266
267 for_each_btree_key_max_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|flags, 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 && !(flags & STR_HASH_must_replace))
282 bch2_trans_copy_iter(trans, &slot, iter);
283
284 if (k.k->type != KEY_TYPE_hash_whiteout)
285 goto not_found;
286 }
287
288 if (!ret)
289 ret = -BCH_ERR_ENOSPC_str_hash_create;
290 out:
291 bch2_trans_iter_exit(trans, &slot);
292 bch2_trans_iter_exit(trans, iter);
293 return ret ? bkey_s_c_err(ret) : bkey_s_c_null;
294 found:
295 found = true;
296 not_found:
297 if (found && (flags & STR_HASH_must_create)) {
298 bch2_trans_iter_exit(trans, &slot);
299 return k;
300 } else if (!found && (flags & STR_HASH_must_replace)) {
301 ret = -BCH_ERR_ENOENT_str_hash_set_must_replace;
302 } else {
303 if (!found && slot.path)
304 swap(*iter, slot);
305
306 insert->k.p = iter->pos;
307 ret = bch2_trans_update(trans, iter, insert, flags);
308 }
309
310 goto out;
311 }
312
313 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)314 int bch2_hash_set_in_snapshot(struct btree_trans *trans,
315 const struct bch_hash_desc desc,
316 const struct bch_hash_info *info,
317 subvol_inum inum, u32 snapshot,
318 struct bkey_i *insert,
319 enum btree_iter_update_trigger_flags flags)
320 {
321 struct btree_iter iter;
322 struct bkey_s_c k = bch2_hash_set_or_get_in_snapshot(trans, &iter, desc, info, inum,
323 snapshot, insert, flags);
324 int ret = bkey_err(k);
325 if (ret)
326 return ret;
327 if (k.k) {
328 bch2_trans_iter_exit(trans, &iter);
329 return -BCH_ERR_EEXIST_str_hash_set;
330 }
331
332 return 0;
333 }
334
335 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)336 int bch2_hash_set(struct btree_trans *trans,
337 const struct bch_hash_desc desc,
338 const struct bch_hash_info *info,
339 subvol_inum inum,
340 struct bkey_i *insert,
341 enum btree_iter_update_trigger_flags flags)
342 {
343 insert->k.p.inode = inum.inum;
344
345 u32 snapshot;
346 return bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot) ?:
347 bch2_hash_set_in_snapshot(trans, desc, info, inum,
348 snapshot, insert, flags);
349 }
350
351 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)352 int bch2_hash_delete_at(struct btree_trans *trans,
353 const struct bch_hash_desc desc,
354 const struct bch_hash_info *info,
355 struct btree_iter *iter,
356 enum btree_iter_update_trigger_flags flags)
357 {
358 struct bkey_i *delete;
359 int ret;
360
361 delete = bch2_trans_kmalloc(trans, sizeof(*delete));
362 ret = PTR_ERR_OR_ZERO(delete);
363 if (ret)
364 return ret;
365
366 ret = bch2_hash_needs_whiteout(trans, desc, info, iter);
367 if (ret < 0)
368 return ret;
369
370 bkey_init(&delete->k);
371 delete->k.p = iter->pos;
372 delete->k.type = ret ? KEY_TYPE_hash_whiteout : KEY_TYPE_deleted;
373
374 return bch2_trans_update(trans, iter, delete, flags);
375 }
376
377 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)378 int bch2_hash_delete(struct btree_trans *trans,
379 const struct bch_hash_desc desc,
380 const struct bch_hash_info *info,
381 subvol_inum inum, const void *key)
382 {
383 struct btree_iter iter;
384 struct bkey_s_c k = bch2_hash_lookup(trans, &iter, desc, info, inum, key,
385 BTREE_ITER_intent);
386 int ret = bkey_err(k);
387 if (ret)
388 return ret;
389
390 ret = bch2_hash_delete_at(trans, desc, info, &iter, 0);
391 bch2_trans_iter_exit(trans, &iter);
392 return ret;
393 }
394
395 struct snapshots_seen;
396 int __bch2_str_hash_check_key(struct btree_trans *,
397 struct snapshots_seen *,
398 const struct bch_hash_desc *,
399 struct bch_hash_info *,
400 struct btree_iter *, struct bkey_s_c);
401
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)402 static inline int bch2_str_hash_check_key(struct btree_trans *trans,
403 struct snapshots_seen *s,
404 const struct bch_hash_desc *desc,
405 struct bch_hash_info *hash_info,
406 struct btree_iter *k_iter, struct bkey_s_c hash_k)
407 {
408 if (hash_k.k->type != desc->key_type)
409 return 0;
410
411 if (likely(desc->hash_bkey(hash_info, hash_k) == hash_k.k->p.offset))
412 return 0;
413
414 return __bch2_str_hash_check_key(trans, s, desc, hash_info, k_iter, hash_k);
415 }
416
417 #endif /* _BCACHEFS_STR_HASH_H */
418