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_next_slot(iter);
 241
 242         for_each_btree_key_continue(iter, BTREE_ITER_SLOTS, k) {
 243                 if (k.k->type != desc.key_type &&
 244                     k.k->type != desc.whiteout_type)
 245                         return false;
 246
 247                 if (k.k->type == desc.key_type &&
 248                     desc.hash_bkey(info, k) <= start->pos.offset)
 249                         return true;
 250         }
 251         return btree_iter_err(k);
 252 }
 253
 254 static inline int bch2_hash_set(const struct bch_hash_desc desc,
 255                                const struct bch_hash_info *info,
 256                                struct bch_fs *c, u64 inode,
 257                                u64 *journal_seq,
 258                                struct bkey_i *insert, int flags)
 259 {
 260         struct btree_iter iter, hashed_slot;
 261         struct bkey_s_c k;
 262         int ret;
 263
 264         bch2_btree_iter_init(&hashed_slot, c, desc.btree_id,
 265                 POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))),
 266                 BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 267         bch2_btree_iter_init(&iter, c, desc.btree_id, hashed_slot.pos,
 268                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 269         bch2_btree_iter_link(&hashed_slot, &iter);
 270 retry:
 271         /*
 272          * On hash collision, we have to keep the slot we hashed to locked while
 273          * we do the insert - to avoid racing with another thread deleting
 274          * whatever's in the slot we hashed to:
 275          */
 276         ret = bch2_btree_iter_traverse(&hashed_slot);
 277         if (ret)
 278                 goto err;
 279
 280         /*
 281          * On -EINTR/retry, we dropped locks - always restart from the slot we
 282          * hashed to:
 283          */
 284         bch2_btree_iter_copy(&iter, &hashed_slot);
 285
 286         k = bch2_hash_lookup_bkey_at(desc, info, &iter, bkey_i_to_s_c(insert));
 287
 288         ret = btree_iter_err(k);
 289         if (ret == -ENOENT) {
 290                 if (flags & BCH_HASH_SET_MUST_REPLACE) {
 291                         ret = -ENOENT;
 292                         goto err;
 293                 }
 294
 295                 /*
 296                  * Not found, so we're now looking for any open
 297                  * slot - we might have skipped over a whiteout
 298                  * that we could have used, so restart from the
 299                  * slot we hashed to:
 300                  */
 301                 bch2_btree_iter_copy(&iter, &hashed_slot);
 302                 k = bch2_hash_hole_at(desc, &iter);
 303                 if ((ret = btree_iter_err(k)))
 304                         goto err;
 305         } else if (!ret) {
 306                 if (flags & BCH_HASH_SET_MUST_CREATE) {
 307                         ret = -EEXIST;
 308                         goto err;
 309                 }
 310         } else {
 311                 goto err;
 312         }
 313
 314         insert->k.p = iter.pos;
 315         ret = bch2_btree_insert_at(c, NULL, NULL, journal_seq,
 316                                   BTREE_INSERT_ATOMIC|flags,
 317                                   BTREE_INSERT_ENTRY(&iter, insert));
 318 err:
 319         if (ret == -EINTR)
 320                 goto retry;
 321
 322         /*
 323          * On successful insert, we don't want to clobber ret with error from
 324          * iter:
 325          */
 326         bch2_btree_iter_unlock(&iter);
 327         bch2_btree_iter_unlock(&hashed_slot);
 328         return ret;
 329 }
 330
 331 static inline int bch2_hash_delete_at(const struct bch_hash_desc desc,
 332                                       const struct bch_hash_info *info,
 333                                       struct btree_iter *iter,
 334                                       u64 *journal_seq)
 335 {
 336         struct btree_iter whiteout_iter;
 337         struct bkey_i delete;
 338         int ret = -ENOENT;
 339
 340         bch2_btree_iter_init(&whiteout_iter, iter->c, desc.btree_id,
 341                              iter->pos, BTREE_ITER_SLOTS);
 342         bch2_btree_iter_link(iter, &whiteout_iter);
 343
 344         ret = bch2_hash_needs_whiteout(desc, info, &whiteout_iter, iter);
 345         if (ret < 0)
 346                 goto err;
 347
 348         bkey_init(&delete.k);
 349         delete.k.p = iter->pos;
 350         delete.k.type = ret ? desc.whiteout_type : KEY_TYPE_DELETED;
 351
 352         ret = bch2_btree_insert_at(iter->c, NULL, NULL, journal_seq,
 353                                   BTREE_INSERT_NOFAIL|
 354                                   BTREE_INSERT_ATOMIC,
 355                                   BTREE_INSERT_ENTRY(iter, &delete));
 356 err:
 357         bch2_btree_iter_unlink(&whiteout_iter);
 358         return ret;
 359 }
 360
 361 static inline int bch2_hash_delete(const struct bch_hash_desc desc,
 362                                   const struct bch_hash_info *info,
 363                                   struct bch_fs *c, u64 inode,
 364                                   u64 *journal_seq, const void *key)
 365 {
 366         struct btree_iter iter, whiteout_iter;
 367         struct bkey_s_c k;
 368         int ret = -ENOENT;
 369
 370         bch2_btree_iter_init(&iter, c, desc.btree_id,
 371                              POS(inode, desc.hash_key(info, key)),
 372                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 373         bch2_btree_iter_init(&whiteout_iter, c, desc.btree_id,
 374                             POS(inode, desc.hash_key(info, key)),
 375                             BTREE_ITER_SLOTS);
 376         bch2_btree_iter_link(&iter, &whiteout_iter);
 377 retry:
 378         k = bch2_hash_lookup_at(desc, info, &iter, key);
 379         if ((ret = btree_iter_err(k)))
 380                 goto err;
 381
 382         ret = bch2_hash_delete_at(desc, info, &iter, journal_seq);
 383 err:
 384         if (ret == -EINTR)
 385                 goto retry;
 386
 387         bch2_btree_iter_unlock(&whiteout_iter);
 388         bch2_btree_iter_unlock(&iter);
 389         return ret;
 390 }
 391
 392 #endif /* _BCACHEFS_STR_HASH_H */