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