Commit | Line | Data |
---|---|---|
1c6fdbd8 KO |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | ||
3 | #include "bcachefs.h" | |
1dd7f9d9 KO |
4 | #include "btree_iter.h" |
5 | #include "eytzinger.h" | |
1c6fdbd8 | 6 | #include "journal_seq_blacklist.h" |
1dd7f9d9 | 7 | #include "super-io.h" |
1c6fdbd8 KO |
8 | |
9 | /* | |
10 | * journal_seq_blacklist machinery: | |
11 | * | |
12 | * To guarantee order of btree updates after a crash, we need to detect when a | |
13 | * btree node entry (bset) is newer than the newest journal entry that was | |
14 | * successfully written, and ignore it - effectively ignoring any btree updates | |
15 | * that didn't make it into the journal. | |
16 | * | |
17 | * If we didn't do this, we might have two btree nodes, a and b, both with | |
18 | * updates that weren't written to the journal yet: if b was updated after a, | |
19 | * but b was flushed and not a - oops; on recovery we'll find that the updates | |
20 | * to b happened, but not the updates to a that happened before it. | |
21 | * | |
22 | * Ignoring bsets that are newer than the newest journal entry is always safe, | |
23 | * because everything they contain will also have been journalled - and must | |
24 | * still be present in the journal on disk until a journal entry has been | |
25 | * written _after_ that bset was written. | |
26 | * | |
27 | * To accomplish this, bsets record the newest journal sequence number they | |
28 | * contain updates for; then, on startup, the btree code queries the journal | |
29 | * code to ask "Is this sequence number newer than the newest journal entry? If | |
30 | * so, ignore it." | |
31 | * | |
32 | * When this happens, we must blacklist that journal sequence number: the | |
33 | * journal must not write any entries with that sequence number, and it must | |
34 | * record that it was blacklisted so that a) on recovery we don't think we have | |
35 | * missing journal entries and b) so that the btree code continues to ignore | |
36 | * that bset, until that btree node is rewritten. | |
1c6fdbd8 KO |
37 | */ |
38 | ||
1dd7f9d9 KO |
39 | static unsigned sb_blacklist_u64s(unsigned nr) |
40 | { | |
41 | struct bch_sb_field_journal_seq_blacklist *bl; | |
1c6fdbd8 | 42 | |
1dd7f9d9 KO |
43 | return (sizeof(*bl) + sizeof(bl->start[0]) * nr) / sizeof(u64); |
44 | } | |
1c6fdbd8 | 45 | |
1dd7f9d9 KO |
46 | static struct bch_sb_field_journal_seq_blacklist * |
47 | blacklist_entry_try_merge(struct bch_fs *c, | |
48 | struct bch_sb_field_journal_seq_blacklist *bl, | |
49 | unsigned i) | |
50 | { | |
51 | unsigned nr = blacklist_nr_entries(bl); | |
52 | ||
53 | if (le64_to_cpu(bl->start[i].end) >= | |
54 | le64_to_cpu(bl->start[i + 1].start)) { | |
55 | bl->start[i].end = bl->start[i + 1].end; | |
56 | --nr; | |
57 | memmove(&bl->start[i], | |
58 | &bl->start[i + 1], | |
59 | sizeof(bl->start[0]) * (nr - i)); | |
60 | ||
4637429e KO |
61 | bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist, |
62 | sb_blacklist_u64s(nr)); | |
1dd7f9d9 KO |
63 | BUG_ON(!bl); |
64 | } | |
424eb881 | 65 | |
1dd7f9d9 KO |
66 | return bl; |
67 | } | |
1c6fdbd8 | 68 | |
98c80d6d KO |
69 | static bool bl_entry_contig_or_overlaps(struct journal_seq_blacklist_entry *e, |
70 | u64 start, u64 end) | |
71 | { | |
72 | return !(end < le64_to_cpu(e->start) || le64_to_cpu(e->end) < start); | |
73 | } | |
74 | ||
1dd7f9d9 KO |
75 | int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end) |
76 | { | |
77 | struct bch_sb_field_journal_seq_blacklist *bl; | |
78 | unsigned i, nr; | |
79 | int ret = 0; | |
1c6fdbd8 | 80 | |
1dd7f9d9 | 81 | mutex_lock(&c->sb_lock); |
4637429e | 82 | bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
1dd7f9d9 | 83 | nr = blacklist_nr_entries(bl); |
1c6fdbd8 | 84 | |
98c80d6d KO |
85 | for (i = 0; i < nr; i++) { |
86 | struct journal_seq_blacklist_entry *e = | |
87 | bl->start + i; | |
88 | ||
89 | if (bl_entry_contig_or_overlaps(e, start, end)) { | |
90 | e->start = cpu_to_le64(min(start, le64_to_cpu(e->start))); | |
91 | e->end = cpu_to_le64(max(end, le64_to_cpu(e->end))); | |
92 | ||
93 | if (i + 1 < nr) | |
94 | bl = blacklist_entry_try_merge(c, | |
95 | bl, i); | |
96 | if (i) | |
97 | bl = blacklist_entry_try_merge(c, | |
98 | bl, i - 1); | |
99 | goto out_write_sb; | |
1c6fdbd8 | 100 | } |
1c6fdbd8 KO |
101 | } |
102 | ||
4637429e KO |
103 | bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist, |
104 | sb_blacklist_u64s(nr + 1)); | |
1dd7f9d9 | 105 | if (!bl) { |
65d48e35 | 106 | ret = -BCH_ERR_ENOSPC_sb_journal_seq_blacklist; |
1dd7f9d9 | 107 | goto out; |
1c6fdbd8 KO |
108 | } |
109 | ||
1dd7f9d9 KO |
110 | bl->start[nr].start = cpu_to_le64(start); |
111 | bl->start[nr].end = cpu_to_le64(end); | |
112 | out_write_sb: | |
c0ebe3e4 | 113 | c->disk_sb.sb->features[0] |= cpu_to_le64(1ULL << BCH_FEATURE_journal_seq_blacklist_v3); |
1c6fdbd8 | 114 | |
1dd7f9d9 KO |
115 | ret = bch2_write_super(c); |
116 | out: | |
117 | mutex_unlock(&c->sb_lock); | |
1c6fdbd8 | 118 | |
adbcada4 | 119 | return ret ?: bch2_blacklist_table_initialize(c); |
1c6fdbd8 KO |
120 | } |
121 | ||
1dd7f9d9 KO |
122 | static int journal_seq_blacklist_table_cmp(const void *_l, |
123 | const void *_r, size_t size) | |
1c6fdbd8 | 124 | { |
1dd7f9d9 KO |
125 | const struct journal_seq_blacklist_table_entry *l = _l; |
126 | const struct journal_seq_blacklist_table_entry *r = _r; | |
1c6fdbd8 | 127 | |
3ea2b1e1 | 128 | return cmp_int(l->start, r->start); |
1c6fdbd8 KO |
129 | } |
130 | ||
1dd7f9d9 KO |
131 | bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq, |
132 | bool dirty) | |
1c6fdbd8 | 133 | { |
1dd7f9d9 KO |
134 | struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table; |
135 | struct journal_seq_blacklist_table_entry search = { .start = seq }; | |
136 | int idx; | |
1c6fdbd8 | 137 | |
1dd7f9d9 KO |
138 | if (!t) |
139 | return false; | |
1c6fdbd8 | 140 | |
1dd7f9d9 KO |
141 | idx = eytzinger0_find_le(t->entries, t->nr, |
142 | sizeof(t->entries[0]), | |
143 | journal_seq_blacklist_table_cmp, | |
144 | &search); | |
145 | if (idx < 0) | |
146 | return false; | |
1c6fdbd8 | 147 | |
1dd7f9d9 | 148 | BUG_ON(t->entries[idx].start > seq); |
1c6fdbd8 | 149 | |
1dd7f9d9 KO |
150 | if (seq >= t->entries[idx].end) |
151 | return false; | |
1c6fdbd8 | 152 | |
1dd7f9d9 KO |
153 | if (dirty) |
154 | t->entries[idx].dirty = true; | |
155 | return true; | |
1c6fdbd8 KO |
156 | } |
157 | ||
1dd7f9d9 | 158 | int bch2_blacklist_table_initialize(struct bch_fs *c) |
1c6fdbd8 | 159 | { |
1dd7f9d9 | 160 | struct bch_sb_field_journal_seq_blacklist *bl = |
4637429e | 161 | bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
1dd7f9d9 KO |
162 | struct journal_seq_blacklist_table *t; |
163 | unsigned i, nr = blacklist_nr_entries(bl); | |
1c6fdbd8 | 164 | |
1dd7f9d9 KO |
165 | if (!bl) |
166 | return 0; | |
1c6fdbd8 | 167 | |
1dd7f9d9 KO |
168 | t = kzalloc(sizeof(*t) + sizeof(t->entries[0]) * nr, |
169 | GFP_KERNEL); | |
170 | if (!t) | |
65d48e35 | 171 | return -BCH_ERR_ENOMEM_blacklist_table_init; |
1c6fdbd8 | 172 | |
1dd7f9d9 | 173 | t->nr = nr; |
1c6fdbd8 | 174 | |
1dd7f9d9 KO |
175 | for (i = 0; i < nr; i++) { |
176 | t->entries[i].start = le64_to_cpu(bl->start[i].start); | |
177 | t->entries[i].end = le64_to_cpu(bl->start[i].end); | |
1c6fdbd8 KO |
178 | } |
179 | ||
1dd7f9d9 KO |
180 | eytzinger0_sort(t->entries, |
181 | t->nr, | |
182 | sizeof(t->entries[0]), | |
183 | journal_seq_blacklist_table_cmp, | |
184 | NULL); | |
1c6fdbd8 | 185 | |
adbcada4 | 186 | kfree(c->journal_seq_blacklist_table); |
1dd7f9d9 KO |
187 | c->journal_seq_blacklist_table = t; |
188 | return 0; | |
1c6fdbd8 KO |
189 | } |
190 | ||
efe68e1d KO |
191 | static int bch2_sb_journal_seq_blacklist_validate(struct bch_sb *sb, |
192 | struct bch_sb_field *f, | |
193 | struct printbuf *err) | |
1c6fdbd8 | 194 | { |
1dd7f9d9 KO |
195 | struct bch_sb_field_journal_seq_blacklist *bl = |
196 | field_to_type(f, journal_seq_blacklist); | |
efe68e1d | 197 | unsigned i, nr = blacklist_nr_entries(bl); |
1dd7f9d9 | 198 | |
efe68e1d KO |
199 | for (i = 0; i < nr; i++) { |
200 | struct journal_seq_blacklist_entry *e = bl->start + i; | |
201 | ||
202 | if (le64_to_cpu(e->start) >= | |
203 | le64_to_cpu(e->end)) { | |
401ec4db | 204 | prt_printf(err, "entry %u start >= end (%llu >= %llu)", |
efe68e1d | 205 | i, le64_to_cpu(e->start), le64_to_cpu(e->end)); |
78c0b75c | 206 | return -BCH_ERR_invalid_sb_journal_seq_blacklist; |
efe68e1d KO |
207 | } |
208 | ||
209 | if (i + 1 < nr && | |
210 | le64_to_cpu(e[0].end) > | |
211 | le64_to_cpu(e[1].start)) { | |
401ec4db | 212 | prt_printf(err, "entry %u out of order with next entry (%llu > %llu)", |
efe68e1d | 213 | i + 1, le64_to_cpu(e[0].end), le64_to_cpu(e[1].start)); |
78c0b75c | 214 | return -BCH_ERR_invalid_sb_journal_seq_blacklist; |
efe68e1d | 215 | } |
1dd7f9d9 | 216 | } |
1c6fdbd8 | 217 | |
efe68e1d | 218 | return 0; |
1dd7f9d9 | 219 | } |
1c6fdbd8 | 220 | |
1dd7f9d9 KO |
221 | static void bch2_sb_journal_seq_blacklist_to_text(struct printbuf *out, |
222 | struct bch_sb *sb, | |
223 | struct bch_sb_field *f) | |
224 | { | |
225 | struct bch_sb_field_journal_seq_blacklist *bl = | |
226 | field_to_type(f, journal_seq_blacklist); | |
227 | struct journal_seq_blacklist_entry *i; | |
228 | unsigned nr = blacklist_nr_entries(bl); | |
229 | ||
230 | for (i = bl->start; i < bl->start + nr; i++) { | |
231 | if (i != bl->start) | |
401ec4db | 232 | prt_printf(out, " "); |
1dd7f9d9 | 233 | |
401ec4db | 234 | prt_printf(out, "%llu-%llu", |
1dd7f9d9 KO |
235 | le64_to_cpu(i->start), |
236 | le64_to_cpu(i->end)); | |
237 | } | |
401ec4db | 238 | prt_newline(out); |
1c6fdbd8 KO |
239 | } |
240 | ||
1dd7f9d9 KO |
241 | const struct bch_sb_field_ops bch_sb_field_ops_journal_seq_blacklist = { |
242 | .validate = bch2_sb_journal_seq_blacklist_validate, | |
243 | .to_text = bch2_sb_journal_seq_blacklist_to_text | |
244 | }; | |
9b6e2f1e KO |
245 | |
246 | void bch2_blacklist_entries_gc(struct work_struct *work) | |
247 | { | |
248 | struct bch_fs *c = container_of(work, struct bch_fs, | |
249 | journal_seq_blacklist_gc_work); | |
250 | struct journal_seq_blacklist_table *t; | |
251 | struct bch_sb_field_journal_seq_blacklist *bl; | |
252 | struct journal_seq_blacklist_entry *src, *dst; | |
6bd68ec2 | 253 | struct btree_trans *trans = bch2_trans_get(c); |
9b6e2f1e KO |
254 | unsigned i, nr, new_nr; |
255 | int ret; | |
256 | ||
9b6e2f1e KO |
257 | for (i = 0; i < BTREE_ID_NR; i++) { |
258 | struct btree_iter iter; | |
259 | struct btree *b; | |
260 | ||
6bd68ec2 | 261 | bch2_trans_node_iter_init(trans, &iter, i, POS_MIN, |
9b6e2f1e KO |
262 | 0, 0, BTREE_ITER_PREFETCH); |
263 | retry: | |
6bd68ec2 | 264 | bch2_trans_begin(trans); |
9b6e2f1e KO |
265 | |
266 | b = bch2_btree_iter_peek_node(&iter); | |
267 | ||
268 | while (!(ret = PTR_ERR_OR_ZERO(b)) && | |
269 | b && | |
270 | !test_bit(BCH_FS_STOPPING, &c->flags)) | |
271 | b = bch2_btree_iter_next_node(&iter); | |
272 | ||
549d173c | 273 | if (bch2_err_matches(ret, BCH_ERR_transaction_restart)) |
9b6e2f1e KO |
274 | goto retry; |
275 | ||
6bd68ec2 | 276 | bch2_trans_iter_exit(trans, &iter); |
9b6e2f1e KO |
277 | } |
278 | ||
6bd68ec2 | 279 | bch2_trans_put(trans); |
9b6e2f1e KO |
280 | if (ret) |
281 | return; | |
282 | ||
283 | mutex_lock(&c->sb_lock); | |
4637429e | 284 | bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
9b6e2f1e KO |
285 | if (!bl) |
286 | goto out; | |
287 | ||
288 | nr = blacklist_nr_entries(bl); | |
289 | dst = bl->start; | |
290 | ||
291 | t = c->journal_seq_blacklist_table; | |
292 | BUG_ON(nr != t->nr); | |
293 | ||
294 | for (src = bl->start, i = eytzinger0_first(t->nr); | |
295 | src < bl->start + nr; | |
296 | src++, i = eytzinger0_next(i, nr)) { | |
297 | BUG_ON(t->entries[i].start != le64_to_cpu(src->start)); | |
298 | BUG_ON(t->entries[i].end != le64_to_cpu(src->end)); | |
299 | ||
300 | if (t->entries[i].dirty) | |
301 | *dst++ = *src; | |
302 | } | |
303 | ||
304 | new_nr = dst - bl->start; | |
305 | ||
306 | bch_info(c, "nr blacklist entries was %u, now %u", nr, new_nr); | |
307 | ||
308 | if (new_nr != nr) { | |
4637429e | 309 | bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist, |
9b6e2f1e KO |
310 | new_nr ? sb_blacklist_u64s(new_nr) : 0); |
311 | BUG_ON(new_nr && !bl); | |
312 | ||
313 | if (!new_nr) | |
314 | c->disk_sb.sb->features[0] &= cpu_to_le64(~(1ULL << BCH_FEATURE_journal_seq_blacklist_v3)); | |
315 | ||
316 | bch2_write_super(c); | |
317 | } | |
318 | out: | |
319 | mutex_unlock(&c->sb_lock); | |
320 | } |