diff options
Diffstat (limited to 'fs/bcachefs/buckets_waiting_for_journal.c')
-rw-r--r-- | fs/bcachefs/buckets_waiting_for_journal.c | 163 |
1 files changed, 94 insertions, 69 deletions
diff --git a/fs/bcachefs/buckets_waiting_for_journal.c b/fs/bcachefs/buckets_waiting_for_journal.c index 7eb8482d1258..81ab685cdef9 100644 --- a/fs/bcachefs/buckets_waiting_for_journal.c +++ b/fs/bcachefs/buckets_waiting_for_journal.c @@ -2,36 +2,43 @@ #include "bcachefs.h" #include "buckets_waiting_for_journal.h" -#include <linux/jhash.h> +#include <linux/hash.h> +#include <linux/random.h> -static u32 hash_seeds[] = { - 2168153708, - 1262039142, - 1183479835, -}; +static inline struct bucket_hashed * +bucket_hash(struct buckets_waiting_for_journal_table *t, + unsigned hash_seed_idx, u64 dev_bucket) +{ + return t->d + hash_64(dev_bucket ^ t->hash_seeds[hash_seed_idx], t->bits); +} -static inline unsigned bucket_hash(u64 dev_bucket, unsigned hash_seed_idx) +static void bucket_table_init(struct buckets_waiting_for_journal_table *t, size_t bits) { - return jhash_2words(dev_bucket << 32, dev_bucket, hash_seeds[hash_seed_idx]); + unsigned i; + + t->bits = bits; + for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) + get_random_bytes(&t->hash_seeds[i], sizeof(t->hash_seeds[i])); + memset(t->d, 0, sizeof(t->d[0]) << t->bits); } -bool bch2_bucket_needs_journal_commit(struct bch_fs *c, +bool bch2_bucket_needs_journal_commit(struct buckets_waiting_for_journal *b, u64 flushed_seq, unsigned dev, u64 bucket) { - struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal; + struct buckets_waiting_for_journal_table *t; u64 dev_bucket = (u64) dev << 56 | bucket; bool ret = false; unsigned i; mutex_lock(&b->lock); - BUG_ON(!is_power_of_2(b->nr)); + t = b->t; - for (i = 0; i < ARRAY_SIZE(hash_seeds); i++) { - u32 h = bucket_hash(dev_bucket, i) & (b->nr - 1); + for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) { + struct bucket_hashed *h = bucket_hash(t, i, dev_bucket); - if (b->d[h].dev_bucket == dev_bucket) { - ret = b->d[h].journal_seq > flushed_seq; + if (h->dev_bucket == dev_bucket) { + ret = h->journal_seq > flushed_seq; break; } } @@ -41,78 +48,93 @@ bool bch2_bucket_needs_journal_commit(struct bch_fs *c, return ret; } -static int bch2_buckets_waiting_for_journal_rehash(struct bch_fs *c) +static bool bucket_table_insert(struct buckets_waiting_for_journal_table *t, + struct bucket_hashed *new, + u64 flushed_seq) { - struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal; - u64 flushed_seq = c->journal.flushed_seq_ondisk; - unsigned i, j, h, new_nr = b->nr * 2, elements = 0; - struct bucket_hashed *new_table; + struct bucket_hashed *last_evicted = NULL; + unsigned tries, i; - new_table = kvmalloc_array(new_nr, sizeof(*new_table), __GFP_ZERO); - if (!new_table) - return -ENOMEM; + for (tries = 0; tries < 10; tries++) { + struct bucket_hashed *old, *victim = NULL; - for (i = 0; i < b->nr; i++) { - if (b->d[i].journal_seq < flushed_seq) - continue; + for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) { + old = bucket_hash(t, i, new->dev_bucket); - for (j = 0; j < ARRAY_SIZE(hash_seeds); j++) { - h = bucket_hash(b->d[i].dev_bucket, j); - if ((h & (b->nr - 1)) == i) - break; - } + if (old->dev_bucket == new->dev_bucket || + old->journal_seq <= flushed_seq) { + *old = *new; + return true; + } - BUG_ON(j == ARRAY_SIZE(hash_seeds)); - BUG_ON(new_table[h & (new_nr - 1)].dev_bucket); + if (last_evicted != old) + victim = old; + } - new_table[h & (new_nr - 1)] = b->d[i]; + /* hashed to same slot 3 times: */ + if (!victim) + break; - elements++; + /* Failed to find an empty slot: */ + swap(*new, *victim); + last_evicted = victim; } - kvfree(b->d); - b->nr = new_nr; - b->d = new_table; - return 0; + return false; } -int bch2_set_bucket_needs_journal_commit(struct bch_fs *c, unsigned dev, u64 bucket, +int bch2_set_bucket_needs_journal_commit(struct buckets_waiting_for_journal *b, + u64 flushed_seq, + unsigned dev, u64 bucket, u64 journal_seq) { - struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal; - struct bucket_hashed new = { + struct buckets_waiting_for_journal_table *t, *n; + struct bucket_hashed tmp, new = { .dev_bucket = (u64) dev << 56 | bucket, .journal_seq = journal_seq, - }, *old, *victim, *last_evicted = NULL; - u64 flushed_seq = c->journal.flushed_seq_ondisk; - unsigned tries, i; + }; + size_t i, size, new_bits, nr_elements = 1, nr_rehashes = 0; int ret = 0; mutex_lock(&b->lock); - BUG_ON(!is_power_of_2(b->nr)); -retry: - for (tries = 0; tries < 5; tries++) { - for (i = 0; i < ARRAY_SIZE(hash_seeds); i++) { - old = b->d + (bucket_hash(new.dev_bucket, i) & (b->nr - 1)); - if (old->dev_bucket == new.dev_bucket || - old->journal_seq <= flushed_seq) { - *old = new; - goto out; - } + if (likely(bucket_table_insert(b->t, &new, flushed_seq))) + goto out; - if (last_evicted != old) - victim = old; - } + t = b->t; + size = 1UL << t->bits; + for (i = 0; i < size; i++) + nr_elements += t->d[i].journal_seq > flushed_seq; - /* Failed to find an empty slot: */ - swap(new, *victim); - last_evicted = victim; + new_bits = t->bits + (nr_elements * 3 > size); + + n = kvmalloc(sizeof(*n) + (sizeof(n->d[0]) << new_bits), GFP_KERNEL); + if (!n) { + ret = -BCH_ERR_ENOMEM_buckets_waiting_for_journal_set; + goto out; } - ret = bch2_buckets_waiting_for_journal_rehash(c); - if (!ret) - goto retry; +retry_rehash: + nr_rehashes++; + bucket_table_init(n, new_bits); + + tmp = new; + BUG_ON(!bucket_table_insert(n, &tmp, flushed_seq)); + + for (i = 0; i < 1UL << t->bits; i++) { + if (t->d[i].journal_seq <= flushed_seq) + continue; + + tmp = t->d[i]; + if (!bucket_table_insert(n, &tmp, flushed_seq)) + goto retry_rehash; + } + + b->t = n; + kvfree(t); + + pr_debug("took %zu rehashes, table at %zu/%zu elements", + nr_rehashes, nr_elements, 1UL << b->t->bits); out: mutex_unlock(&b->lock); @@ -123,19 +145,22 @@ void bch2_fs_buckets_waiting_for_journal_exit(struct bch_fs *c) { struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal; - kvfree(b->d); + kvfree(b->t); } +#define INITIAL_TABLE_BITS 3 + int bch2_fs_buckets_waiting_for_journal_init(struct bch_fs *c) { struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal; mutex_init(&b->lock); - b->nr = 8; - b->d = kvmalloc_array(b->nr, sizeof(*b->d), __GFP_ZERO); - if (!b->d) - return -ENOMEM; + b->t = kvmalloc(sizeof(*b->t) + + (sizeof(b->t->d[0]) << INITIAL_TABLE_BITS), GFP_KERNEL); + if (!b->t) + return -BCH_ERR_ENOMEM_buckets_waiting_for_journal_init; + bucket_table_init(b->t, INITIAL_TABLE_BITS); return 0; } |