Update bcachefs sources to ba398d2906 bcachefs: Fix reflink repair code

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;
 }