]> git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/str_hash.h
Update bcachefs sources to ffe09df106 bcachefs: Verify fs hasn't been modified before...
[bcachefs-tools-debian] / libbcachefs / str_hash.h
1 #ifndef _BCACHEFS_STR_HASH_H
2 #define _BCACHEFS_STR_HASH_H
3
4 #include "btree_iter.h"
5 #include "btree_update.h"
6 #include "checksum.h"
7 #include "error.h"
8 #include "inode.h"
9 #include "siphash.h"
10 #include "super.h"
11
12 #include <linux/crc32c.h>
13 #include <crypto/hash.h>
14 #include <crypto/sha.h>
15
16 struct bch_hash_info {
17         u8                      type;
18         union {
19                 __le64          crc_key;
20                 SIPHASH_KEY     siphash_key;
21         };
22 };
23
24 static inline struct bch_hash_info
25 bch2_hash_info_init(struct bch_fs *c,
26                    const struct bch_inode_unpacked *bi)
27 {
28         /* XXX ick */
29         struct bch_hash_info info = {
30                 .type = (bi->bi_flags >> INODE_STR_HASH_OFFSET) &
31                         ~(~0U << INODE_STR_HASH_BITS)
32         };
33
34         switch (info.type) {
35         case BCH_STR_HASH_CRC32C:
36         case BCH_STR_HASH_CRC64:
37                 info.crc_key = bi->bi_hash_seed;
38                 break;
39         case BCH_STR_HASH_SIPHASH: {
40                 SHASH_DESC_ON_STACK(desc, c->sha256);
41                 u8 digest[SHA256_DIGEST_SIZE];
42
43                 desc->tfm = c->sha256;
44                 desc->flags = 0;
45
46                 crypto_shash_digest(desc, (void *) &bi->bi_hash_seed,
47                                     sizeof(bi->bi_hash_seed), digest);
48                 memcpy(&info.siphash_key, digest, sizeof(info.siphash_key));
49                 break;
50         }
51         default:
52                 BUG();
53         }
54
55         return info;
56 }
57
58 struct bch_str_hash_ctx {
59         union {
60                 u32             crc32c;
61                 u64             crc64;
62                 SIPHASH_CTX     siphash;
63         };
64 };
65
66 static inline void bch2_str_hash_init(struct bch_str_hash_ctx *ctx,
67                                      const struct bch_hash_info *info)
68 {
69         switch (info->type) {
70         case BCH_STR_HASH_CRC32C:
71                 ctx->crc32c = crc32c(~0, &info->crc_key, sizeof(info->crc_key));
72                 break;
73         case BCH_STR_HASH_CRC64:
74                 ctx->crc64 = bch2_crc64_update(~0, &info->crc_key, sizeof(info->crc_key));
75                 break;
76         case BCH_STR_HASH_SIPHASH:
77                 SipHash24_Init(&ctx->siphash, &info->siphash_key);
78                 break;
79         default:
80                 BUG();
81         }
82 }
83
84 static inline void bch2_str_hash_update(struct bch_str_hash_ctx *ctx,
85                                        const struct bch_hash_info *info,
86                                        const void *data, size_t len)
87 {
88         switch (info->type) {
89         case BCH_STR_HASH_CRC32C:
90                 ctx->crc32c = crc32c(ctx->crc32c, data, len);
91                 break;
92         case BCH_STR_HASH_CRC64:
93                 ctx->crc64 = bch2_crc64_update(ctx->crc64, data, len);
94                 break;
95         case BCH_STR_HASH_SIPHASH:
96                 SipHash24_Update(&ctx->siphash, data, len);
97                 break;
98         default:
99                 BUG();
100         }
101 }
102
103 static inline u64 bch2_str_hash_end(struct bch_str_hash_ctx *ctx,
104                                    const struct bch_hash_info *info)
105 {
106         switch (info->type) {
107         case BCH_STR_HASH_CRC32C:
108                 return ctx->crc32c;
109         case BCH_STR_HASH_CRC64:
110                 return ctx->crc64 >> 1;
111         case BCH_STR_HASH_SIPHASH:
112                 return SipHash24_End(&ctx->siphash) >> 1;
113         default:
114                 BUG();
115         }
116 }
117
118 struct bch_hash_desc {
119         enum btree_id   btree_id;
120         u8              key_type;
121
122         u64             (*hash_key)(const struct bch_hash_info *, const void *);
123         u64             (*hash_bkey)(const struct bch_hash_info *, struct bkey_s_c);
124         bool            (*cmp_key)(struct bkey_s_c, const void *);
125         bool            (*cmp_bkey)(struct bkey_s_c, struct bkey_s_c);
126 };
127
128 static __always_inline struct btree_iter *
129 bch2_hash_lookup(struct btree_trans *trans,
130                  const struct bch_hash_desc desc,
131                  const struct bch_hash_info *info,
132                  u64 inode, const void *key,
133                  unsigned flags)
134 {
135         struct btree_iter *iter;
136         struct bkey_s_c k;
137
138         iter = bch2_trans_get_iter(trans, desc.btree_id,
139                                    POS(inode, desc.hash_key(info, key)),
140                                    BTREE_ITER_SLOTS|flags);
141         if (IS_ERR(iter))
142                 return iter;
143
144         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
145                 if (iter->pos.inode != inode)
146                         break;
147
148                 if (k.k->type == desc.key_type) {
149                         if (!desc.cmp_key(k, key))
150                                 return iter;
151                 } else if (k.k->type == KEY_TYPE_whiteout) {
152                         ;
153                 } else {
154                         /* hole, not found */
155                         break;
156                 }
157         }
158
159         return IS_ERR(k.k) ? ERR_CAST(k.k) : ERR_PTR(-ENOENT);
160 }
161
162 static __always_inline struct btree_iter *
163 bch2_hash_hole(struct btree_trans *trans,
164                const struct bch_hash_desc desc,
165                const struct bch_hash_info *info,
166                u64 inode, const void *key)
167 {
168         struct btree_iter *iter;
169         struct bkey_s_c k;
170
171         iter = bch2_trans_get_iter(trans, desc.btree_id,
172                                    POS(inode, desc.hash_key(info, key)),
173                                    BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
174         if (IS_ERR(iter))
175                 return iter;
176
177         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
178                 if (iter->pos.inode != inode)
179                         break;
180
181                 if (k.k->type != desc.key_type)
182                         return iter;
183         }
184
185         return IS_ERR(k.k) ? ERR_CAST(k.k) : ERR_PTR(-ENOSPC);
186 }
187
188 static __always_inline
189 int bch2_hash_needs_whiteout(struct btree_trans *trans,
190                              const struct bch_hash_desc desc,
191                              const struct bch_hash_info *info,
192                              struct btree_iter *start)
193 {
194         struct btree_iter *iter;
195         struct bkey_s_c k;
196
197         iter = bch2_trans_copy_iter(trans, start);
198         if (IS_ERR(iter))
199                 return PTR_ERR(iter);
200
201         bch2_btree_iter_next_slot(iter);
202
203         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
204                 if (k.k->type != desc.key_type &&
205                     k.k->type != KEY_TYPE_whiteout)
206                         return false;
207
208                 if (k.k->type == desc.key_type &&
209                     desc.hash_bkey(info, k) <= start->pos.offset)
210                         return true;
211         }
212         return btree_iter_err(k);
213 }
214
215 static __always_inline
216 int bch2_hash_set(struct btree_trans *trans,
217                   const struct bch_hash_desc desc,
218                   const struct bch_hash_info *info,
219                   u64 inode, struct bkey_i *insert, int flags)
220 {
221         struct btree_iter *iter, *slot = NULL;
222         struct bkey_s_c k;
223
224         iter = bch2_trans_get_iter(trans, desc.btree_id,
225                         POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))),
226                         BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
227         if (IS_ERR(iter))
228                 return PTR_ERR(iter);
229
230         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
231                 if (iter->pos.inode != inode)
232                         break;
233
234                 if (k.k->type == desc.key_type) {
235                         if (!desc.cmp_bkey(k, bkey_i_to_s_c(insert)))
236                                 goto found;
237
238                         /* hash collision: */
239                         continue;
240                 }
241
242                 if (!slot &&
243                     !(flags & BCH_HASH_SET_MUST_REPLACE)) {
244                         slot = bch2_trans_copy_iter(trans, iter);
245                         if (IS_ERR(slot))
246                                 return PTR_ERR(slot);
247                 }
248
249                 if (k.k->type != KEY_TYPE_whiteout)
250                         goto not_found;
251         }
252
253         return btree_iter_err(k) ?: -ENOSPC;
254 not_found:
255         if (flags & BCH_HASH_SET_MUST_REPLACE)
256                 return -ENOENT;
257
258         insert->k.p = slot->pos;
259         bch2_trans_update(trans, BTREE_INSERT_ENTRY(slot, insert));
260         return 0;
261 found:
262         if (flags & BCH_HASH_SET_MUST_CREATE)
263                 return -EEXIST;
264
265         insert->k.p = iter->pos;
266         bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, insert));
267         return 0;
268 }
269
270 static __always_inline
271 int bch2_hash_delete_at(struct btree_trans *trans,
272                         const struct bch_hash_desc desc,
273                         const struct bch_hash_info *info,
274                         struct btree_iter *iter)
275 {
276         struct bkey_i *delete;
277         int ret;
278
279         ret = bch2_hash_needs_whiteout(trans, desc, info, iter);
280         if (ret < 0)
281                 return ret;
282
283         delete = bch2_trans_kmalloc(trans, sizeof(*delete));
284         if (IS_ERR(delete))
285                 return PTR_ERR(delete);
286
287         bkey_init(&delete->k);
288         delete->k.p = iter->pos;
289         delete->k.type = ret ? KEY_TYPE_whiteout : KEY_TYPE_deleted;
290
291         bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, delete));
292         return 0;
293 }
294
295 static __always_inline
296 int bch2_hash_delete(struct btree_trans *trans,
297                      const struct bch_hash_desc desc,
298                      const struct bch_hash_info *info,
299                      u64 inode, const void *key)
300 {
301         struct btree_iter *iter;
302
303         iter = bch2_hash_lookup(trans, desc, info, inode, key,
304                                 BTREE_ITER_INTENT);
305         if (IS_ERR(iter))
306                 return PTR_ERR(iter);
307
308         return bch2_hash_delete_at(trans, desc, info, iter);
309 }
310
311 #endif /* _BCACHEFS_STR_HASH_H */