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