diff options
Diffstat (limited to 'libbcachefs/buckets_waiting_for_journal.c')
-rw-r--r-- | libbcachefs/buckets_waiting_for_journal.c | 164 |
1 files changed, 92 insertions, 72 deletions
diff --git a/libbcachefs/buckets_waiting_for_journal.c b/libbcachefs/buckets_waiting_for_journal.c index 56b37b24..2e5b9550 100644 --- a/libbcachefs/buckets_waiting_for_journal.c +++ b/libbcachefs/buckets_waiting_for_journal.c @@ -2,36 +2,46 @@ #include "bcachefs.h" #include "buckets_waiting_for_journal.h" -#include <linux/jhash.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) +{ + unsigned h = siphash_1u64(dev_bucket, &t->hash_seeds[hash_seed_idx]); + + BUG_ON(!is_power_of_2(t->size)); + + return t->d + (h & (t->size - 1)); +} -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 size) { - return jhash_2words(dev_bucket << 32, dev_bucket, hash_seeds[hash_seed_idx]); + unsigned i; + + t->size = size; + 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]) * size); } -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,84 +51,92 @@ 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, - }, *last_evicted = NULL; - u64 flushed_seq = c->journal.flushed_seq_ondisk; - unsigned tries, i; + }; + size_t i, new_size, 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++) { - struct bucket_hashed *old, *victim = NULL; - for (i = 0; i < ARRAY_SIZE(hash_seeds); i++) { - old = b->d + (bucket_hash(new.dev_bucket, i) & (b->nr - 1)); + if (likely(bucket_table_insert(b->t, &new, flushed_seq))) + goto out; - if (old->dev_bucket == new.dev_bucket || - old->journal_seq <= flushed_seq) { - *old = new; - goto out; - } + t = b->t; + for (i = 0; i < t->size; i++) + nr_elements += t->d[i].journal_seq > flushed_seq; - if (last_evicted != old) - victim = old; - } + new_size = nr_elements < t->size / 3 ? t->size : t->size * 2; - /* hashed to same slot 3 times: */ - if (!victim) - break; + n = kvmalloc(sizeof(*n) + sizeof(n->d[0]) * new_size, GFP_KERNEL); + if (!n) { + ret = -ENOMEM; + goto out; + } - /* Failed to find an empty slot: */ - swap(new, *victim); - last_evicted = victim; +retry_rehash: + nr_rehashes++; + bucket_table_init(n, new_size); + + tmp = new; + BUG_ON(!bucket_table_insert(n, &tmp, flushed_seq)); + + for (i = 0; i < t->size; 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; } - ret = bch2_buckets_waiting_for_journal_rehash(c); - if (!ret) - goto retry; + b->t = n; + kvfree(t); + + pr_debug("took %zu rehashes, table at %zu/%zu elements", + nr_rehashes, nr_elements, b->t->size); out: mutex_unlock(&b->lock); @@ -129,19 +147,21 @@ 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_SIZE 8 + 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) + b->t = kvmalloc(sizeof(*b->t) + sizeof(b->t->d[0]) * INITIAL_TABLE_SIZE, GFP_KERNEL); + if (!b->t) return -ENOMEM; + bucket_table_init(b->t, INITIAL_TABLE_SIZE); return 0; } |