git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/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/jhash.h>
   6
   7 static u32 hash_seeds[] = {
   8         2168153708,
   9         1262039142,
  10         1183479835,
  11 };
  12
  13 static inline unsigned bucket_hash(u64 dev_bucket, unsigned hash_seed_idx)
  14 {
  15         return jhash_2words(dev_bucket << 32, dev_bucket, hash_seeds[hash_seed_idx]);
  16 }
  17
  18 bool bch2_bucket_needs_journal_commit(struct bch_fs *c,
  19                                       u64 flushed_seq,
  20                                       unsigned dev, u64 bucket)
  21 {
  22         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
  23         u64 dev_bucket = (u64) dev << 56 | bucket;
  24         bool ret = false;
  25         unsigned i;
  26
  27         mutex_lock(&b->lock);
  28         BUG_ON(!is_power_of_2(b->nr));
  29
  30         for (i = 0; i < ARRAY_SIZE(hash_seeds); i++) {
  31                 u32 h = bucket_hash(dev_bucket, i) & (b->nr - 1);
  32
  33                 if (b->d[h].dev_bucket == dev_bucket) {
  34                         ret = b->d[h].journal_seq > flushed_seq;
  35                         break;
  36                 }
  37         }
  38
  39         mutex_unlock(&b->lock);
  40
  41         return ret;
  42 }
  43
  44 static int bch2_buckets_waiting_for_journal_rehash(struct bch_fs *c)
  45 {
  46         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
  47         u64 flushed_seq = c->journal.flushed_seq_ondisk;
  48         unsigned i, j, h, new_nr = b->nr * 2, elements = 0;
  49         struct bucket_hashed *new_table;
  50
  51         new_table = kvmalloc_array(new_nr, sizeof(*new_table), __GFP_ZERO);
  52         if (!new_table)
  53                 return -ENOMEM;
  54
  55         for (i = 0; i < b->nr; i++) {
  56                 if (b->d[i].journal_seq < flushed_seq)
  57                         continue;
  58
  59                 for (j = 0; j < ARRAY_SIZE(hash_seeds); j++) {
  60                         h = bucket_hash(b->d[i].dev_bucket, j);
  61                         if ((h & (b->nr - 1)) == i)
  62                                 break;
  63                 }
  64
  65                 BUG_ON(j == ARRAY_SIZE(hash_seeds));
  66                 BUG_ON(new_table[h & (new_nr - 1)].dev_bucket);
  67
  68                 new_table[h & (new_nr - 1)] = b->d[i];
  69
  70                 elements++;
  71         }
  72
  73         kvfree(b->d);
  74         b->nr   = new_nr;
  75         b->d    = new_table;
  76         return 0;
  77 }
  78
  79 int bch2_set_bucket_needs_journal_commit(struct bch_fs *c, unsigned dev, u64 bucket,
  80                                          u64 journal_seq)
  81 {
  82         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
  83         struct bucket_hashed new = {
  84                 .dev_bucket     = (u64) dev << 56 | bucket,
  85                 .journal_seq    = journal_seq,
  86         }, *last_evicted = NULL;
  87         u64 flushed_seq = c->journal.flushed_seq_ondisk;
  88         unsigned tries, i;
  89         int ret = 0;
  90
  91         mutex_lock(&b->lock);
  92         BUG_ON(!is_power_of_2(b->nr));
  93 retry:
  94         for (tries = 0; tries < 5; tries++) {
  95                 struct bucket_hashed *old, *victim = NULL;
  96
  97                 for (i = 0; i < ARRAY_SIZE(hash_seeds); i++) {
  98                         old = b->d + (bucket_hash(new.dev_bucket, i) & (b->nr - 1));
  99
 100                         if (old->dev_bucket == new.dev_bucket ||
 101                             old->journal_seq <= flushed_seq) {
 102                                 *old = new;
 103                                 goto out;
 104                         }
 105
 106                         if (last_evicted != old)
 107                                 victim = old;
 108                 }
 109
 110                 /* hashed to same slot 3 times: */
 111                 if (!victim)
 112                         break;
 113
 114                 /* Failed to find an empty slot: */
 115                 swap(new, *victim);
 116                 last_evicted = victim;
 117         }
 118
 119         ret = bch2_buckets_waiting_for_journal_rehash(c);
 120         if (!ret)
 121                 goto retry;
 122 out:
 123         mutex_unlock(&b->lock);
 124
 125         return ret;
 126 }
 127
 128 void bch2_fs_buckets_waiting_for_journal_exit(struct bch_fs *c)
 129 {
 130         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
 131
 132         kvfree(b->d);
 133 }
 134
 135 int bch2_fs_buckets_waiting_for_journal_init(struct bch_fs *c)
 136 {
 137         struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
 138
 139         mutex_init(&b->lock);
 140
 141         b->nr = 8;
 142         b->d = kvmalloc_array(b->nr, sizeof(*b->d), __GFP_ZERO);
 143         if (!b->d)
 144                 return -ENOMEM;
 145
 146         return 0;
 147 }