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