#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;
}
}
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, 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++) {
- 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;
+ size = 1UL << t->bits;
+ for (i = 0; i < size; i++)
+ nr_elements += t->d[i].journal_seq > flushed_seq;
- if (last_evicted != old)
- victim = old;
- }
+ new_bits = t->bits + (nr_elements * 3 > size);
- /* Failed to find an empty slot: */
- swap(new, *victim);
- last_evicted = victim;
+ 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/%lu elements",
+ nr_rehashes, nr_elements, 1UL << b->t->bits);
out:
mutex_unlock(&b->lock);
{
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;
}
projects / bcachefs-tools-debian / blobdiff