fs/bcachefs/str_hash.h

   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
  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
  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
  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
  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
 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
 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
 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_max_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
 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
 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_max_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
 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
 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_max_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
 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
 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
 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
 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 struct snapshots_seen;
 397 int __bch2_str_hash_check_key(struct btree_trans *,
 398                               struct snapshots_seen *,
 399                               const struct bch_hash_desc *,
 400                               struct bch_hash_info *,
 401                               struct btree_iter *, struct bkey_s_c);
 402
 403 static inline int bch2_str_hash_check_key(struct btree_trans *trans,
 404                             struct snapshots_seen *s,
 405                             const struct bch_hash_desc *desc,
 406                             struct bch_hash_info *hash_info,
 407                             struct btree_iter *k_iter, struct bkey_s_c hash_k)
 408 {
 409         if (hash_k.k->type != desc->key_type)
 410                 return 0;
 411
 412         if (likely(desc->hash_bkey(hash_info, hash_k) == hash_k.k->p.offset))
 413                 return 0;
 414
 415         return __bch2_str_hash_check_key(trans, s, desc, hash_info, k_iter, hash_k);
 416 }
 417
 418 #endif /* _BCACHEFS_STR_HASH_H */