tjh.dev
Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
1// SPDX-License-Identifier: GPL-2.0
2
3#include "bcachefs.h"
4#include "buckets_waiting_for_journal.h"
5#include <linux/hash.h>
6#include <linux/random.h>
7
8static inline struct bucket_hashed *
9bucket_hash(struct buckets_waiting_for_journal_table *t,
10 unsigned hash_seed_idx, u64 dev_bucket)
11{
12 return t->d + hash_64(dev_bucket ^ t->hash_seeds[hash_seed_idx], t->bits);
13}
14
15static void bucket_table_init(struct buckets_waiting_for_journal_table *t, size_t bits)
16{
17 unsigned i;
18
19 t->bits = bits;
20 for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++)
21 get_random_bytes(&t->hash_seeds[i], sizeof(t->hash_seeds[i]));
22 memset(t->d, 0, sizeof(t->d[0]) << t->bits);
23}
24
25u64 bch2_bucket_journal_seq_ready(struct buckets_waiting_for_journal *b,
26 unsigned dev, u64 bucket)
27{
28 struct buckets_waiting_for_journal_table *t;
29 u64 dev_bucket = (u64) dev << 56 | bucket;
30 u64 ret = 0;
31
32 mutex_lock(&b->lock);
33 t = b->t;
34
35 for (unsigned i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) {
36 struct bucket_hashed *h = bucket_hash(t, i, dev_bucket);
37
38 if (h->dev_bucket == dev_bucket) {
39 ret = h->journal_seq;
40 break;
41 }
42 }
43
44 mutex_unlock(&b->lock);
45
46 return ret;
47}
48
49static bool bucket_table_insert(struct buckets_waiting_for_journal_table *t,
50 struct bucket_hashed *new,
51 u64 flushed_seq)
52{
53 struct bucket_hashed *last_evicted = NULL;
54 unsigned tries, i;
55
56 for (tries = 0; tries < 10; tries++) {
57 struct bucket_hashed *old, *victim = NULL;
58
59 for (i = 0; i < ARRAY_SIZE(t->hash_seeds); i++) {
60 old = bucket_hash(t, i, new->dev_bucket);
61
62 if (old->dev_bucket == new->dev_bucket ||
63 old->journal_seq <= flushed_seq) {
64 *old = *new;
65 return true;
66 }
67
68 if (last_evicted != old)
69 victim = old;
70 }
71
72 /* hashed to same slot 3 times: */
73 if (!victim)
74 break;
75
76 /* Failed to find an empty slot: */
77 swap(*new, *victim);
78 last_evicted = victim;
79 }
80
81 return false;
82}
83
84int bch2_set_bucket_needs_journal_commit(struct buckets_waiting_for_journal *b,
85 u64 flushed_seq,
86 unsigned dev, u64 bucket,
87 u64 journal_seq)
88{
89 struct buckets_waiting_for_journal_table *t, *n;
90 struct bucket_hashed tmp, new = {
91 .dev_bucket = (u64) dev << 56 | bucket,
92 .journal_seq = journal_seq,
93 };
94 size_t i, size, new_bits, nr_elements = 1, nr_rehashes = 0, nr_rehashes_this_size = 0;
95 int ret = 0;
96
97 mutex_lock(&b->lock);
98
99 if (likely(bucket_table_insert(b->t, &new, flushed_seq)))
100 goto out;
101
102 t = b->t;
103 size = 1UL << t->bits;
104 for (i = 0; i < size; i++)
105 nr_elements += t->d[i].journal_seq > flushed_seq;
106
107 new_bits = ilog2(roundup_pow_of_two(nr_elements * 3));
108realloc:
109 n = kvmalloc(sizeof(*n) + (sizeof(n->d[0]) << new_bits), GFP_KERNEL);
110 if (!n) {
111 struct bch_fs *c = container_of(b, struct bch_fs, buckets_waiting_for_journal);
112 ret = bch_err_throw(c, ENOMEM_buckets_waiting_for_journal_set);
113 goto out;
114 }
115
116retry_rehash:
117 if (nr_rehashes_this_size == 3) {
118 new_bits++;
119 nr_rehashes_this_size = 0;
120 kvfree(n);
121 goto realloc;
122 }
123
124 nr_rehashes++;
125 nr_rehashes_this_size++;
126
127 bucket_table_init(n, new_bits);
128
129 tmp = new;
130 BUG_ON(!bucket_table_insert(n, &tmp, flushed_seq));
131
132 for (i = 0; i < 1UL << t->bits; i++) {
133 if (t->d[i].journal_seq <= flushed_seq)
134 continue;
135
136 tmp = t->d[i];
137 if (!bucket_table_insert(n, &tmp, flushed_seq))
138 goto retry_rehash;
139 }
140
141 b->t = n;
142 kvfree(t);
143
144 pr_debug("took %zu rehashes, table at %zu/%lu elements",
145 nr_rehashes, nr_elements, 1UL << b->t->bits);
146out:
147 mutex_unlock(&b->lock);
148
149 return ret;
150}
151
152void bch2_fs_buckets_waiting_for_journal_exit(struct bch_fs *c)
153{
154 struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
155
156 kvfree(b->t);
157}
158
159#define INITIAL_TABLE_BITS 3
160
161int bch2_fs_buckets_waiting_for_journal_init(struct bch_fs *c)
162{
163 struct buckets_waiting_for_journal *b = &c->buckets_waiting_for_journal;
164
165 mutex_init(&b->lock);
166
167 b->t = kvmalloc(sizeof(*b->t) +
168 (sizeof(b->t->d[0]) << INITIAL_TABLE_BITS), GFP_KERNEL);
169 if (!b->t)
170 return -BCH_ERR_ENOMEM_buckets_waiting_for_journal_init;
171
172 bucket_table_init(b->t, INITIAL_TABLE_BITS);
173 return 0;
174}