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
bch2_str_hash_opt_to_type(struct bch_fs * c,enum bch_str_hash_opts opt)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
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 /* 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
bch2_str_hash_init(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info)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
bch2_str_hash_update(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info,const void * data,size_t len)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
bch2_str_hash_end(struct bch_str_hash_ctx * ctx,const struct bch_hash_info * info)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
is_visible_key(struct bch_hash_desc desc,subvol_inum inum,struct bkey_s_c k)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
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)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
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)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
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)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
bch2_hash_needs_whiteout(struct btree_trans * trans,const struct bch_hash_desc desc,const struct bch_hash_info * info,struct btree_iter * start)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
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)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
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_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 #endif /* _BCACHEFS_STR_HASH_H */
397