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