git.sesse.net Git - bcachefs-tools-debian/blob - 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
  15 struct bch_hash_info {
  16         u8                      type;
  17         union {
  18                 __le64          crc_key;
  19                 SIPHASH_KEY     siphash_key;
  20         };
  21 };
  22
  23 static inline struct bch_hash_info
  24 bch2_hash_info_init(struct bch_fs *c,
  25                    const struct bch_inode_unpacked *bi)
  26 {
  27         /* XXX ick */
  28         struct bch_hash_info info = {
  29                 .type = (bi->bi_flags >> INODE_STR_HASH_OFFSET) &
  30                         ~(~0U << INODE_STR_HASH_BITS)
  31         };
  32
  33         switch (info.type) {
  34         case BCH_STR_HASH_CRC32C:
  35         case BCH_STR_HASH_CRC64:
  36                 info.crc_key = bi->bi_hash_seed;
  37                 break;
  38         case BCH_STR_HASH_SIPHASH: {
  39                 SHASH_DESC_ON_STACK(desc, c->sha256);
  40                 u8 digest[crypto_shash_digestsize(c->sha256)];
  41
  42                 desc->tfm = c->sha256;
  43                 desc->flags = 0;
  44
  45                 crypto_shash_digest(desc, (void *) &bi->bi_hash_seed,
  46                                     sizeof(bi->bi_hash_seed), digest);
  47                 memcpy(&info.siphash_key, digest, sizeof(info.siphash_key));
  48                 break;
  49         }
  50         default:
  51                 BUG();
  52         }
  53
  54         return info;
  55 }
  56
  57 struct bch_str_hash_ctx {
  58         union {
  59                 u32             crc32c;
  60                 u64             crc64;
  61                 SIPHASH_CTX     siphash;
  62         };
  63 };
  64
  65 static inline void bch2_str_hash_init(struct bch_str_hash_ctx *ctx,
  66                                      const struct bch_hash_info *info)
  67 {
  68         switch (info->type) {
  69         case BCH_STR_HASH_CRC32C:
  70                 ctx->crc32c = crc32c(~0, &info->crc_key, sizeof(info->crc_key));
  71                 break;
  72         case BCH_STR_HASH_CRC64:
  73                 ctx->crc64 = bch2_crc64_update(~0, &info->crc_key, sizeof(info->crc_key));
  74                 break;
  75         case BCH_STR_HASH_SIPHASH:
  76                 SipHash24_Init(&ctx->siphash, &info->siphash_key);
  77                 break;
  78         default:
  79                 BUG();
  80         }
  81 }
  82
  83 static inline void bch2_str_hash_update(struct bch_str_hash_ctx *ctx,
  84                                        const struct bch_hash_info *info,
  85                                        const void *data, size_t len)
  86 {
  87         switch (info->type) {
  88         case BCH_STR_HASH_CRC32C:
  89                 ctx->crc32c = crc32c(ctx->crc32c, data, len);
  90                 break;
  91         case BCH_STR_HASH_CRC64:
  92                 ctx->crc64 = bch2_crc64_update(ctx->crc64, data, len);
  93                 break;
  94         case BCH_STR_HASH_SIPHASH:
  95                 SipHash24_Update(&ctx->siphash, data, len);
  96                 break;
  97         default:
  98                 BUG();
  99         }
 100 }
 101
 102 static inline u64 bch2_str_hash_end(struct bch_str_hash_ctx *ctx,
 103                                    const struct bch_hash_info *info)
 104 {
 105         switch (info->type) {
 106         case BCH_STR_HASH_CRC32C:
 107                 return ctx->crc32c;
 108         case BCH_STR_HASH_CRC64:
 109                 return ctx->crc64 >> 1;
 110         case BCH_STR_HASH_SIPHASH:
 111                 return SipHash24_End(&ctx->siphash) >> 1;
 112         default:
 113                 BUG();
 114         }
 115 }
 116
 117 struct bch_hash_desc {
 118         enum btree_id   btree_id;
 119         u8              key_type;
 120         u8              whiteout_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 inline struct bkey_s_c
 129 bch2_hash_lookup_at(const struct bch_hash_desc desc,
 130                    const struct bch_hash_info *info,
 131                    struct btree_iter *iter, const void *search)
 132 {
 133         u64 inode = iter->pos.inode;
 134         struct bkey_s_c k;
 135
 136         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
 137                 if (iter->pos.inode != inode)
 138                         break;
 139
 140                 if (k.k->type == desc.key_type) {
 141                         if (!desc.cmp_key(k, search))
 142                                 return k;
 143                 } else if (k.k->type == desc.whiteout_type) {
 144                         ;
 145                 } else {
 146                         /* hole, not found */
 147                         break;
 148                 }
 149         }
 150         return btree_iter_err(k) ? k : bkey_s_c_err(-ENOENT);
 151 }
 152
 153 static inline struct bkey_s_c
 154 bch2_hash_lookup_bkey_at(const struct bch_hash_desc desc,
 155                         const struct bch_hash_info *info,
 156                         struct btree_iter *iter, struct bkey_s_c search)
 157 {
 158         u64 inode = iter->pos.inode;
 159         struct bkey_s_c k;
 160
 161         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
 162                 if (iter->pos.inode != inode)
 163                         break;
 164
 165                 if (k.k->type == desc.key_type) {
 166                         if (!desc.cmp_bkey(k, search))
 167                                 return k;
 168                 } else if (k.k->type == desc.whiteout_type) {
 169                         ;
 170                 } else {
 171                         /* hole, not found */
 172                         break;
 173                 }
 174         }
 175         return btree_iter_err(k) ? k : bkey_s_c_err(-ENOENT);
 176 }
 177
 178 static inline struct bkey_s_c
 179 bch2_hash_lookup(const struct bch_hash_desc desc,
 180                 const struct bch_hash_info *info,
 181                 struct bch_fs *c, u64 inode,
 182                 struct btree_iter *iter, const void *key)
 183 {
 184         bch2_btree_iter_init(iter, c, desc.btree_id,
 185                             POS(inode, desc.hash_key(info, key)),
 186                             BTREE_ITER_SLOTS);
 187
 188         return bch2_hash_lookup_at(desc, info, iter, key);
 189 }
 190
 191 static inline struct bkey_s_c
 192 bch2_hash_lookup_intent(const struct bch_hash_desc desc,
 193                        const struct bch_hash_info *info,
 194                        struct bch_fs *c, u64 inode,
 195                        struct btree_iter *iter, const void *key)
 196 {
 197         bch2_btree_iter_init(iter, c, desc.btree_id,
 198                              POS(inode, desc.hash_key(info, key)),
 199                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 200
 201         return bch2_hash_lookup_at(desc, info, iter, key);
 202 }
 203
 204 static inline struct bkey_s_c
 205 bch2_hash_hole_at(const struct bch_hash_desc desc, struct btree_iter *iter)
 206 {
 207         u64 inode = iter->pos.inode;
 208         struct bkey_s_c k;
 209
 210         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
 211                 if (iter->pos.inode != inode)
 212                         break;
 213
 214                 if (k.k->type != desc.key_type)
 215                         return k;
 216         }
 217         return btree_iter_err(k) ? k : bkey_s_c_err(-ENOENT);
 218 }
 219
 220 static inline struct bkey_s_c bch2_hash_hole(const struct bch_hash_desc desc,
 221                                             const struct bch_hash_info *info,
 222                                             struct bch_fs *c, u64 inode,
 223                                             struct btree_iter *iter,
 224                                             const void *key)
 225 {
 226         bch2_btree_iter_init(iter, c, desc.btree_id,
 227                              POS(inode, desc.hash_key(info, key)),
 228                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 229
 230         return bch2_hash_hole_at(desc, iter);
 231 }
 232
 233 static inline int bch2_hash_needs_whiteout(const struct bch_hash_desc desc,
 234                                            const struct bch_hash_info *info,
 235                                            struct btree_iter *iter,
 236                                            struct btree_iter *start)
 237 {
 238         struct bkey_s_c k;
 239
 240         bch2_btree_iter_set_pos(iter,
 241                         btree_type_successor(start->btree_id, start->pos));
 242
 243         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
 244                 if (k.k->type != desc.key_type &&
 245                     k.k->type != desc.whiteout_type)
 246                         return false;
 247
 248                 if (k.k->type == desc.key_type &&
 249                     desc.hash_bkey(info, k) <= start->pos.offset)
 250                         return true;
 251         }
 252         return btree_iter_err(k);
 253 }
 254
 255 static inline int bch2_hash_set(const struct bch_hash_desc desc,
 256                                const struct bch_hash_info *info,
 257                                struct bch_fs *c, u64 inode,
 258                                u64 *journal_seq,
 259                                struct bkey_i *insert, int flags)
 260 {
 261         struct btree_iter iter, hashed_slot;
 262         struct bkey_s_c k;
 263         int ret;
 264
 265         bch2_btree_iter_init(&hashed_slot, c, desc.btree_id,
 266                 POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))),
 267                 BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 268         bch2_btree_iter_init(&iter, c, desc.btree_id, hashed_slot.pos,
 269                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 270         bch2_btree_iter_link(&hashed_slot, &iter);
 271 retry:
 272         /*
 273          * On hash collision, we have to keep the slot we hashed to locked while
 274          * we do the insert - to avoid racing with another thread deleting
 275          * whatever's in the slot we hashed to:
 276          */
 277         ret = bch2_btree_iter_traverse(&hashed_slot);
 278         if (ret)
 279                 goto err;
 280
 281         /*
 282          * On -EINTR/retry, we dropped locks - always restart from the slot we
 283          * hashed to:
 284          */
 285         bch2_btree_iter_copy(&iter, &hashed_slot);
 286
 287         k = bch2_hash_lookup_bkey_at(desc, info, &iter, bkey_i_to_s_c(insert));
 288
 289         ret = btree_iter_err(k);
 290         if (ret == -ENOENT) {
 291                 if (flags & BCH_HASH_SET_MUST_REPLACE) {
 292                         ret = -ENOENT;
 293                         goto err;
 294                 }
 295
 296                 /*
 297                  * Not found, so we're now looking for any open
 298                  * slot - we might have skipped over a whiteout
 299                  * that we could have used, so restart from the
 300                  * slot we hashed to:
 301                  */
 302                 bch2_btree_iter_copy(&iter, &hashed_slot);
 303                 k = bch2_hash_hole_at(desc, &iter);
 304                 if ((ret = btree_iter_err(k)))
 305                         goto err;
 306         } else if (!ret) {
 307                 if (flags & BCH_HASH_SET_MUST_CREATE) {
 308                         ret = -EEXIST;
 309                         goto err;
 310                 }
 311         } else {
 312                 goto err;
 313         }
 314
 315         insert->k.p = iter.pos;
 316         ret = bch2_btree_insert_at(c, NULL, NULL, journal_seq,
 317                                   BTREE_INSERT_ATOMIC|flags,
 318                                   BTREE_INSERT_ENTRY(&iter, insert));
 319 err:
 320         if (ret == -EINTR)
 321                 goto retry;
 322
 323         /*
 324          * On successful insert, we don't want to clobber ret with error from
 325          * iter:
 326          */
 327         bch2_btree_iter_unlock(&iter);
 328         bch2_btree_iter_unlock(&hashed_slot);
 329         return ret;
 330 }
 331
 332 static inline int bch2_hash_delete_at(const struct bch_hash_desc desc,
 333                                       const struct bch_hash_info *info,
 334                                       struct btree_iter *iter,
 335                                       u64 *journal_seq)
 336 {
 337         struct btree_iter whiteout_iter;
 338         struct bkey_i delete;
 339         int ret = -ENOENT;
 340
 341         bch2_btree_iter_init(&whiteout_iter, iter->c, desc.btree_id,
 342                              iter->pos, BTREE_ITER_SLOTS);
 343         bch2_btree_iter_link(iter, &whiteout_iter);
 344
 345         ret = bch2_hash_needs_whiteout(desc, info, &whiteout_iter, iter);
 346         if (ret < 0)
 347                 goto err;
 348
 349         bkey_init(&delete.k);
 350         delete.k.p = iter->pos;
 351         delete.k.type = ret ? desc.whiteout_type : KEY_TYPE_DELETED;
 352
 353         ret = bch2_btree_insert_at(iter->c, NULL, NULL, journal_seq,
 354                                   BTREE_INSERT_NOFAIL|
 355                                   BTREE_INSERT_ATOMIC,
 356                                   BTREE_INSERT_ENTRY(iter, &delete));
 357 err:
 358         bch2_btree_iter_unlink(&whiteout_iter);
 359         return ret;
 360 }
 361
 362 static inline int bch2_hash_delete(const struct bch_hash_desc desc,
 363                                   const struct bch_hash_info *info,
 364                                   struct bch_fs *c, u64 inode,
 365                                   u64 *journal_seq, const void *key)
 366 {
 367         struct btree_iter iter, whiteout_iter;
 368         struct bkey_s_c k;
 369         int ret = -ENOENT;
 370
 371         bch2_btree_iter_init(&iter, c, desc.btree_id,
 372                              POS(inode, desc.hash_key(info, key)),
 373                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 374         bch2_btree_iter_init(&whiteout_iter, c, desc.btree_id,
 375                             POS(inode, desc.hash_key(info, key)),
 376                             BTREE_ITER_SLOTS);
 377         bch2_btree_iter_link(&iter, &whiteout_iter);
 378 retry:
 379         k = bch2_hash_lookup_at(desc, info, &iter, key);
 380         if ((ret = btree_iter_err(k)))
 381                 goto err;
 382
 383         ret = bch2_hash_delete_at(desc, info, &iter, journal_seq);
 384 err:
 385         if (ret == -EINTR)
 386                 goto retry;
 387
 388         bch2_btree_iter_unlock(&whiteout_iter);
 389         bch2_btree_iter_unlock(&iter);
 390         return ret;
 391 }
 392
 393 #endif /* _BCACHEFS_STR_HASH_H */