git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/str_hash.h

   1 #ifndef _BCACHE_STR_HASH_H
   2 #define _BCACHE_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->i_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->i_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->i_hash_seed,
  46                                     sizeof(bi->i_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
 135         do {
 136                 struct bkey_s_c k = bch2_btree_iter_peek_with_holes(iter);
 137
 138                 if (btree_iter_err(k))
 139                         return k;
 140
 141                 if (k.k->type == desc.key_type) {
 142                         if (!desc.cmp_key(k, search))
 143                                 return k;
 144                 } else if (k.k->type == desc.whiteout_type) {
 145                         ;
 146                 } else {
 147                         /* hole, not found */
 148                         break;
 149                 }
 150
 151                 bch2_btree_iter_advance_pos(iter);
 152         } while (iter->pos.inode == inode);
 153
 154         return bkey_s_c_err(-ENOENT);
 155 }
 156
 157 static inline struct bkey_s_c
 158 bch2_hash_lookup_bkey_at(const struct bch_hash_desc desc,
 159                         const struct bch_hash_info *info,
 160                         struct btree_iter *iter, struct bkey_s_c search)
 161 {
 162         u64 inode = iter->pos.inode;
 163
 164         do {
 165                 struct bkey_s_c k = bch2_btree_iter_peek_with_holes(iter);
 166
 167                 if (btree_iter_err(k))
 168                         return k;
 169
 170                 if (k.k->type == desc.key_type) {
 171                         if (!desc.cmp_bkey(k, search))
 172                                 return k;
 173                 } else if (k.k->type == desc.whiteout_type) {
 174                         ;
 175                 } else {
 176                         /* hole, not found */
 177                         break;
 178                 }
 179
 180                 bch2_btree_iter_advance_pos(iter);
 181         } while (iter->pos.inode == inode);
 182
 183         return bkey_s_c_err(-ENOENT);
 184 }
 185
 186 static inline struct bkey_s_c
 187 bch2_hash_lookup(const struct bch_hash_desc desc,
 188                 const struct bch_hash_info *info,
 189                 struct bch_fs *c, u64 inode,
 190                 struct btree_iter *iter, const void *key)
 191 {
 192         bch2_btree_iter_init(iter, c, desc.btree_id,
 193                             POS(inode, desc.hash_key(info, key)));
 194
 195         return bch2_hash_lookup_at(desc, info, iter, key);
 196 }
 197
 198 static inline struct bkey_s_c
 199 bch2_hash_lookup_intent(const struct bch_hash_desc desc,
 200                        const struct bch_hash_info *info,
 201                        struct bch_fs *c, u64 inode,
 202                        struct btree_iter *iter, const void *key)
 203 {
 204         bch2_btree_iter_init_intent(iter, c, desc.btree_id,
 205                             POS(inode, desc.hash_key(info, key)));
 206
 207         return bch2_hash_lookup_at(desc, info, iter, key);
 208 }
 209
 210 static inline struct bkey_s_c
 211 bch2_hash_hole_at(const struct bch_hash_desc desc, struct btree_iter *iter)
 212 {
 213         while (1) {
 214                 struct bkey_s_c k = bch2_btree_iter_peek_with_holes(iter);
 215
 216                 if (btree_iter_err(k))
 217                         return k;
 218
 219                 if (k.k->type != desc.key_type)
 220                         return k;
 221
 222                 /* hash collision, keep going */
 223                 bch2_btree_iter_advance_pos(iter);
 224                 if (iter->pos.inode != k.k->p.inode)
 225                         return bkey_s_c_err(-ENOENT);
 226         }
 227 }
 228
 229 static inline struct bkey_s_c bch2_hash_hole(const struct bch_hash_desc desc,
 230                                             const struct bch_hash_info *info,
 231                                             struct bch_fs *c, u64 inode,
 232                                             struct btree_iter *iter,
 233                                             const void *key)
 234 {
 235         bch2_btree_iter_init_intent(iter, c, desc.btree_id,
 236                             POS(inode, desc.hash_key(info, key)));
 237
 238         return bch2_hash_hole_at(desc, iter);
 239 }
 240
 241 static inline int bch2_hash_needs_whiteout(const struct bch_hash_desc desc,
 242                                            const struct bch_hash_info *info,
 243                                            struct btree_iter *iter,
 244                                            struct btree_iter *start)
 245 {
 246         bch2_btree_iter_set_pos(iter,
 247                         btree_type_successor(start->btree_id, start->pos));
 248
 249         while (1) {
 250                 struct bkey_s_c k = bch2_btree_iter_peek_with_holes(iter);
 251                 int ret = btree_iter_err(k);
 252
 253                 if (ret)
 254                         return ret;
 255
 256                 if (k.k->type != desc.key_type &&
 257                     k.k->type != desc.whiteout_type)
 258                         return false;
 259
 260                 if (k.k->type == desc.key_type &&
 261                     desc.hash_bkey(info, k) <= start->pos.offset)
 262                         return true;
 263
 264                 bch2_btree_iter_advance_pos(iter);
 265         }
 266 }
 267
 268 #define BCH_HASH_SET_MUST_CREATE        (1 << 4)
 269 #define BCH_HASH_SET_MUST_REPLACE       (1 << 5)
 270
 271 static inline int bch2_hash_set(const struct bch_hash_desc desc,
 272                                const struct bch_hash_info *info,
 273                                struct bch_fs *c, u64 inode,
 274                                u64 *journal_seq,
 275                                struct bkey_i *insert, int flags)
 276 {
 277         struct btree_iter iter, hashed_slot;
 278         struct bkey_s_c k;
 279         int ret;
 280
 281         bch2_btree_iter_init_intent(&hashed_slot, c, desc.btree_id,
 282                 POS(inode, desc.hash_bkey(info, bkey_i_to_s_c(insert))));
 283         bch2_btree_iter_init_intent(&iter, c, desc.btree_id, hashed_slot.pos);
 284         bch2_btree_iter_link(&hashed_slot, &iter);
 285 retry:
 286         /*
 287          * On hash collision, we have to keep the slot we hashed to locked while
 288          * we do the insert - to avoid racing with another thread deleting
 289          * whatever's in the slot we hashed to:
 290          */
 291         ret = bch2_btree_iter_traverse(&hashed_slot);
 292         if (ret)
 293                 goto err;
 294
 295         /*
 296          * On -EINTR/retry, we dropped locks - always restart from the slot we
 297          * hashed to:
 298          */
 299         bch2_btree_iter_copy(&iter, &hashed_slot);
 300
 301         k = bch2_hash_lookup_bkey_at(desc, info, &iter, bkey_i_to_s_c(insert));
 302
 303         ret = btree_iter_err(k);
 304         if (ret == -ENOENT) {
 305                 if (flags & BCH_HASH_SET_MUST_REPLACE) {
 306                         ret = -ENOENT;
 307                         goto err;
 308                 }
 309
 310                 /*
 311                  * Not found, so we're now looking for any open
 312                  * slot - we might have skipped over a whiteout
 313                  * that we could have used, so restart from the
 314                  * slot we hashed to:
 315                  */
 316                 bch2_btree_iter_copy(&iter, &hashed_slot);
 317                 k = bch2_hash_hole_at(desc, &iter);
 318                 if ((ret = btree_iter_err(k)))
 319                         goto err;
 320         } else if (!ret) {
 321                 if (flags & BCH_HASH_SET_MUST_CREATE) {
 322                         ret = -EEXIST;
 323                         goto err;
 324                 }
 325         } else {
 326                 goto err;
 327         }
 328
 329         insert->k.p = iter.pos;
 330         ret = bch2_btree_insert_at(c, NULL, NULL, journal_seq,
 331                                   BTREE_INSERT_ATOMIC|flags,
 332                                   BTREE_INSERT_ENTRY(&iter, insert));
 333 err:
 334         if (ret == -EINTR)
 335                 goto retry;
 336
 337         /*
 338          * On successful insert, we don't want to clobber ret with error from
 339          * iter:
 340          */
 341         bch2_btree_iter_unlock(&iter);
 342         bch2_btree_iter_unlock(&hashed_slot);
 343         return ret;
 344 }
 345
 346 static inline int bch2_hash_delete_at(const struct bch_hash_desc desc,
 347                                       const struct bch_hash_info *info,
 348                                       struct btree_iter *iter,
 349                                       u64 *journal_seq)
 350 {
 351         struct btree_iter whiteout_iter;
 352         struct bkey_i delete;
 353         int ret = -ENOENT;
 354
 355         bch2_btree_iter_init(&whiteout_iter, iter->c, desc.btree_id,
 356                              iter->pos);
 357         bch2_btree_iter_link(iter, &whiteout_iter);
 358
 359         ret = bch2_hash_needs_whiteout(desc, info, &whiteout_iter, iter);
 360         if (ret < 0)
 361                 goto err;
 362
 363         bkey_init(&delete.k);
 364         delete.k.p = iter->pos;
 365         delete.k.type = ret ? desc.whiteout_type : KEY_TYPE_DELETED;
 366
 367         ret = bch2_btree_insert_at(iter->c, NULL, NULL, journal_seq,
 368                                   BTREE_INSERT_NOFAIL|
 369                                   BTREE_INSERT_ATOMIC,
 370                                   BTREE_INSERT_ENTRY(iter, &delete));
 371 err:
 372         bch2_btree_iter_unlink(&whiteout_iter);
 373         return ret;
 374 }
 375
 376 static inline int bch2_hash_delete(const struct bch_hash_desc desc,
 377                                   const struct bch_hash_info *info,
 378                                   struct bch_fs *c, u64 inode,
 379                                   u64 *journal_seq, const void *key)
 380 {
 381         struct btree_iter iter, whiteout_iter;
 382         struct bkey_s_c k;
 383         int ret = -ENOENT;
 384
 385         bch2_btree_iter_init_intent(&iter, c, desc.btree_id,
 386                             POS(inode, desc.hash_key(info, key)));
 387         bch2_btree_iter_init(&whiteout_iter, c, desc.btree_id,
 388                             POS(inode, desc.hash_key(info, key)));
 389         bch2_btree_iter_link(&iter, &whiteout_iter);
 390 retry:
 391         k = bch2_hash_lookup_at(desc, info, &iter, key);
 392         if ((ret = btree_iter_err(k)))
 393                 goto err;
 394
 395         ret = bch2_hash_delete_at(desc, info, &iter, journal_seq);
 396 err:
 397         if (ret == -EINTR)
 398                 goto retry;
 399
 400         bch2_btree_iter_unlock(&whiteout_iter);
 401         bch2_btree_iter_unlock(&iter);
 402         return ret;
 403 }
 404
 405 #endif /* _BCACHE_STR_HASH_H */