fs/bcachefs/buckets_waiting_for_journal.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "buckets_waiting_for_journal.h"
   5 #include <linux/hash.h>
   6 #include <linux/random.h>
   7
   8 static inline struct bucket_hashed *
   9 bucket_hash(struct buckets_waiting_for_journal_table *t,
  10             unsigned hash_seed_idx, u64 dev_bucket)
  11 {
  12         return t->d + hash_64(dev_bucket ^ t->hash_seeds[hash_seed_idx], t->bits);
  13 }
  14
  15 static void bucket_table_init(struct buckets_waiting_for_journal_table *t, size_t bits)
  16 {
  17         unsigned i;
  18
  19         t->bits = bits;
  20         for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++)
  21                 get_random_bytes(&t->hash_seeds[i], sizeof(t->hash_seeds[i]));
  22         memset(t->d, 0, sizeof(t->d[0]) << t->bits);
  23 }
  24
  25 bool bch2_bucket_needs_journal_commit(struct buckets_waiting_for_journal *b,
  26                                       u64 flushed_seq,
  27                                       unsigned dev, u64 bucket)
  28 {
  29         struct buckets_waiting_for_journal_table *t;
  30         u64 dev_bucket = (u64) dev << 56 | bucket;
  31         bool ret = false;
  32         unsigned i;
  33
  34         mutex_lock(&b->lock);
  35         t = b->t;
  36
  37         for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) {
  38                 struct bucket_hashed *h = bucket_hash(t, i, dev_bucket);
  39
  40                 if (h->dev_bucket == dev_bucket) {
  41                         ret = h->journal_seq > flushed_seq;
  42                         break;
  43                 }
  44         }
  45
  46         mutex_unlock(&b->lock);
  47
  48         return ret;
  49 }
  50
  51 static bool bucket_table_insert(struct buckets_waiting_for_journal_table *t,
  52                                 struct bucket_hashed *new,
  53                                 u64 flushed_seq)
  54 {
  55         struct bucket_hashed *last_evicted = NULL;
  56         unsigned tries, i;
  57
  58         for (tries = 0; tries < 10; tries++) {
  59                 struct bucket_hashed *old, *victim = NULL;
  60
  61                 for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) {
  62                         old = bucket_hash(t, i, new->dev_bucket);
  63
  64                         if (old->dev_bucket == new->dev_bucket ||
  65                             old->journal_seq <= flushed_seq) {
  66                                 *old = *new;
  67                                 return true;
  68                         }
  69
  70                         if (last_evicted != old)
  71                                 victim = old;
  72                 }
  73
  74                 /* hashed to same slot 3 times: */
  75                 if (!victim)
  76                         break;
  77
  78                 /* Failed to find an empty slot: */
  79                 swap(*new, *victim);
  80                 last_evicted = victim;
  81         }
  82
  83         return false;
  84 }
  85
  86 int bch2_set_bucket_needs_journal_commit(struct buckets_waiting_for_journal *b,
  87                                          u64 flushed_seq,
  88                                          unsigned dev, u64 bucket,
  89                                          u64 journal_seq)
  90 {
  91         struct buckets_waiting_for_journal_table *t, *n;
  92         struct bucket_hashed tmp, new = {
  93                 .dev_bucket     = (u64) dev << 56 | bucket,
  94                 .journal_seq    = journal_seq,
  95         };
  96         size_t i, size, new_bits, nr_elements = 1, nr_rehashes = 0, nr_rehashes_this_size = 0;
  97         int ret = 0;
  98
  99         mutex_lock(&b->lock);
 100
 101         if (likely(bucket_table_insert(b->t, &new, flushed_seq)))
 102                 goto out;
 103
 104         t = b->t;
 105         size = 1UL << t->bits;
 106         for (i = 0; i < size; i++)
 107                 nr_elements += t->d[i].journal_seq > flushed_seq;
 108
 109         new_bits = ilog2(roundup_pow_of_two(nr_elements * 3));
 110 realloc:
 111         n = kvmalloc(sizeof(*n) + (sizeof(n->d[0]) << new_bits), GFP_KERNEL);
 112         if (!n) {
 113                 ret = -BCH_ERR_ENOMEM_buckets_waiting_for_journal_set;
 114                 goto out;
 115         }
 116
 117 retry_rehash:
 118         if (nr_rehashes_this_size == 3) {
 119                 new_bits++;
 120                 nr_rehashes_this_size = 0;
 121                 kvfree(n);
 122                 goto realloc;
 123         }
 124
 125         nr_rehashes++;
 126         nr_rehashes_this_size++;
 127
 128         bucket_table_init(n, new_bits);
 129
 130         tmp = new;
 131         BUG_ON(!bucket_table_insert(n, &tmp, flushed_seq));
 132
 133         for (i = 0; i < 1UL << t->bits; i++) {
 134                 if (t->d[i].journal_seq <= flushed_seq)
 135                         continue;
 136
 137                 tmp = t->d[i];
 138                 if (!bucket_table_insert(n, &tmp, flushed_seq))
 139                         goto retry_rehash;
 140         }
 141
 142         b->t = n;
 143         kvfree(t);
 144
 145         pr_debug("took %zu rehashes, table at %zu/%lu elements",
 146                  nr_rehashes, nr_elements, 1UL << b->t->bits);
 147 out:
 148         mutex_unlock(&b->lock);
 149
 150         return ret;
 151 }
 152
 153 void bch2_fs_buckets_waiting_for_journal_exit(struct bch_fs *c)
 154 {
 155         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
 156
 157         kvfree(b->t);
 158 }
 159
 160 #define INITIAL_TABLE_BITS              3
 161
 162 int bch2_fs_buckets_waiting_for_journal_init(struct bch_fs *c)
 163 {
 164         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
 165
 166         mutex_init(&b->lock);
 167
 168         b->t = kvmalloc(sizeof(*b->t) +
 169                         (sizeof(b->t->d[0]) << INITIAL_TABLE_BITS), GFP_KERNEL);
 170         if (!b->t)
 171                 return -BCH_ERR_ENOMEM_buckets_waiting_for_journal_init;
 172
 173         bucket_table_init(b->t, INITIAL_TABLE_BITS);
 174         return 0;
 175 }