1 | // SPDX-License-Identifier: GPL-2.0 |
2 | |
3 | #include "bcachefs.h" |
4 | #include "btree_iter.h" |
5 | #include "eytzinger.h" |
6 | #include "journal_seq_blacklist.h" |
7 | #include "super-io.h" |
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. |
37 | */ |
38 | |
39 | static unsigned sb_blacklist_u64s(unsigned nr) |
40 | { |
41 | struct bch_sb_field_journal_seq_blacklist *bl; |
42 | |
43 | return (sizeof(*bl) + sizeof(bl->start[0]) * nr) / sizeof(u64); |
44 | } |
45 | |
46 | int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end) |
47 | { |
48 | struct bch_sb_field_journal_seq_blacklist *bl; |
49 | unsigned i = 0, nr; |
50 | int ret = 0; |
51 | |
52 | mutex_lock(&c->sb_lock); |
53 | bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
54 | nr = blacklist_nr_entries(bl); |
55 | |
56 | while (i < nr) { |
57 | struct journal_seq_blacklist_entry *e = |
58 | bl->start + i; |
59 | |
60 | if (end < le64_to_cpu(e->start)) |
61 | break; |
62 | |
63 | if (start > le64_to_cpu(e->end)) { |
64 | i++; |
65 | continue; |
66 | } |
67 | |
68 | /* |
69 | * Entry is contiguous or overlapping with new entry: merge it |
70 | * with new entry, and delete: |
71 | */ |
72 | |
73 | start = min(start, le64_to_cpu(e->start)); |
74 | end = max(end, le64_to_cpu(e->end)); |
75 | array_remove_item(bl->start, nr, i); |
76 | } |
77 | |
78 | bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist, |
79 | sb_blacklist_u64s(nr + 1)); |
80 | if (!bl) { |
81 | ret = -BCH_ERR_ENOSPC_sb_journal_seq_blacklist; |
82 | goto out; |
83 | } |
84 | |
85 | array_insert_item(bl->start, nr, i, ((struct journal_seq_blacklist_entry) { |
86 | .start = cpu_to_le64(start), |
87 | .end = cpu_to_le64(end), |
88 | })); |
89 | c->disk_sb.sb->features[0] |= cpu_to_le64(1ULL << BCH_FEATURE_journal_seq_blacklist_v3); |
90 | |
91 | ret = bch2_write_super(c); |
92 | out: |
93 | mutex_unlock(lock: &c->sb_lock); |
94 | |
95 | return ret ?: bch2_blacklist_table_initialize(c); |
96 | } |
97 | |
98 | static int journal_seq_blacklist_table_cmp(const void *_l, const void *_r) |
99 | { |
100 | const struct journal_seq_blacklist_table_entry *l = _l; |
101 | const struct journal_seq_blacklist_table_entry *r = _r; |
102 | |
103 | return cmp_int(l->start, r->start); |
104 | } |
105 | |
106 | bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq, |
107 | bool dirty) |
108 | { |
109 | struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table; |
110 | struct journal_seq_blacklist_table_entry search = { .start = seq }; |
111 | int idx; |
112 | |
113 | if (!t) |
114 | return false; |
115 | |
116 | idx = eytzinger0_find_le(base: t->entries, nr: t->nr, |
117 | size: sizeof(t->entries[0]), |
118 | cmp: journal_seq_blacklist_table_cmp, |
119 | search: &search); |
120 | if (idx < 0) |
121 | return false; |
122 | |
123 | BUG_ON(t->entries[idx].start > seq); |
124 | |
125 | if (seq >= t->entries[idx].end) |
126 | return false; |
127 | |
128 | if (dirty) |
129 | t->entries[idx].dirty = true; |
130 | return true; |
131 | } |
132 | |
133 | int bch2_blacklist_table_initialize(struct bch_fs *c) |
134 | { |
135 | struct bch_sb_field_journal_seq_blacklist *bl = |
136 | bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
137 | struct journal_seq_blacklist_table *t; |
138 | unsigned i, nr = blacklist_nr_entries(bl); |
139 | |
140 | if (!bl) |
141 | return 0; |
142 | |
143 | t = kzalloc(struct_size(t, entries, nr), GFP_KERNEL); |
144 | if (!t) |
145 | return -BCH_ERR_ENOMEM_blacklist_table_init; |
146 | |
147 | t->nr = nr; |
148 | |
149 | for (i = 0; i < nr; i++) { |
150 | t->entries[i].start = le64_to_cpu(bl->start[i].start); |
151 | t->entries[i].end = le64_to_cpu(bl->start[i].end); |
152 | } |
153 | |
154 | eytzinger0_sort(t->entries, |
155 | t->nr, |
156 | sizeof(t->entries[0]), |
157 | journal_seq_blacklist_table_cmp, |
158 | NULL); |
159 | |
160 | kfree(objp: c->journal_seq_blacklist_table); |
161 | c->journal_seq_blacklist_table = t; |
162 | return 0; |
163 | } |
164 | |
165 | static int bch2_sb_journal_seq_blacklist_validate(struct bch_sb *sb, |
166 | struct bch_sb_field *f, |
167 | struct printbuf *err) |
168 | { |
169 | struct bch_sb_field_journal_seq_blacklist *bl = |
170 | field_to_type(f, journal_seq_blacklist); |
171 | unsigned i, nr = blacklist_nr_entries(bl); |
172 | |
173 | for (i = 0; i < nr; i++) { |
174 | struct journal_seq_blacklist_entry *e = bl->start + i; |
175 | |
176 | if (le64_to_cpu(e->start) >= |
177 | le64_to_cpu(e->end)) { |
178 | prt_printf(err, "entry %u start >= end (%llu >= %llu)" , |
179 | i, le64_to_cpu(e->start), le64_to_cpu(e->end)); |
180 | return -BCH_ERR_invalid_sb_journal_seq_blacklist; |
181 | } |
182 | |
183 | if (i + 1 < nr && |
184 | le64_to_cpu(e[0].end) > |
185 | le64_to_cpu(e[1].start)) { |
186 | prt_printf(err, "entry %u out of order with next entry (%llu > %llu)" , |
187 | i + 1, le64_to_cpu(e[0].end), le64_to_cpu(e[1].start)); |
188 | return -BCH_ERR_invalid_sb_journal_seq_blacklist; |
189 | } |
190 | } |
191 | |
192 | return 0; |
193 | } |
194 | |
195 | static void bch2_sb_journal_seq_blacklist_to_text(struct printbuf *out, |
196 | struct bch_sb *sb, |
197 | struct bch_sb_field *f) |
198 | { |
199 | struct bch_sb_field_journal_seq_blacklist *bl = |
200 | field_to_type(f, journal_seq_blacklist); |
201 | struct journal_seq_blacklist_entry *i; |
202 | unsigned nr = blacklist_nr_entries(bl); |
203 | |
204 | for (i = bl->start; i < bl->start + nr; i++) { |
205 | if (i != bl->start) |
206 | prt_printf(out, " " ); |
207 | |
208 | prt_printf(out, "%llu-%llu" , |
209 | le64_to_cpu(i->start), |
210 | le64_to_cpu(i->end)); |
211 | } |
212 | prt_newline(out); |
213 | } |
214 | |
215 | const struct bch_sb_field_ops bch_sb_field_ops_journal_seq_blacklist = { |
216 | .validate = bch2_sb_journal_seq_blacklist_validate, |
217 | .to_text = bch2_sb_journal_seq_blacklist_to_text |
218 | }; |
219 | |
220 | void bch2_blacklist_entries_gc(struct work_struct *work) |
221 | { |
222 | struct bch_fs *c = container_of(work, struct bch_fs, |
223 | journal_seq_blacklist_gc_work); |
224 | struct journal_seq_blacklist_table *t; |
225 | struct bch_sb_field_journal_seq_blacklist *bl; |
226 | struct journal_seq_blacklist_entry *src, *dst; |
227 | struct btree_trans *trans = bch2_trans_get(c); |
228 | unsigned i, nr, new_nr; |
229 | int ret; |
230 | |
231 | for (i = 0; i < BTREE_ID_NR; i++) { |
232 | struct btree_iter iter; |
233 | struct btree *b; |
234 | |
235 | bch2_trans_node_iter_init(trans, &iter, i, POS_MIN, |
236 | 0, 0, BTREE_ITER_PREFETCH); |
237 | retry: |
238 | bch2_trans_begin(trans); |
239 | |
240 | b = bch2_btree_iter_peek_node(&iter); |
241 | |
242 | while (!(ret = PTR_ERR_OR_ZERO(ptr: b)) && |
243 | b && |
244 | !test_bit(BCH_FS_stopping, &c->flags)) |
245 | b = bch2_btree_iter_next_node(&iter); |
246 | |
247 | if (bch2_err_matches(ret, BCH_ERR_transaction_restart)) |
248 | goto retry; |
249 | |
250 | bch2_trans_iter_exit(trans, &iter); |
251 | } |
252 | |
253 | bch2_trans_put(trans); |
254 | if (ret) |
255 | return; |
256 | |
257 | mutex_lock(&c->sb_lock); |
258 | bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist); |
259 | if (!bl) |
260 | goto out; |
261 | |
262 | nr = blacklist_nr_entries(bl); |
263 | dst = bl->start; |
264 | |
265 | t = c->journal_seq_blacklist_table; |
266 | BUG_ON(nr != t->nr); |
267 | |
268 | for (src = bl->start, i = eytzinger0_first(size: t->nr); |
269 | src < bl->start + nr; |
270 | src++, i = eytzinger0_next(i, size: nr)) { |
271 | BUG_ON(t->entries[i].start != le64_to_cpu(src->start)); |
272 | BUG_ON(t->entries[i].end != le64_to_cpu(src->end)); |
273 | |
274 | if (t->entries[i].dirty) |
275 | *dst++ = *src; |
276 | } |
277 | |
278 | new_nr = dst - bl->start; |
279 | |
280 | bch_info(c, "nr blacklist entries was %u, now %u" , nr, new_nr); |
281 | |
282 | if (new_nr != nr) { |
283 | bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist, |
284 | new_nr ? sb_blacklist_u64s(new_nr) : 0); |
285 | BUG_ON(new_nr && !bl); |
286 | |
287 | if (!new_nr) |
288 | c->disk_sb.sb->features[0] &= cpu_to_le64(~(1ULL << BCH_FEATURE_journal_seq_blacklist_v3)); |
289 | |
290 | bch2_write_super(c); |
291 | } |
292 | out: |
293 | mutex_unlock(lock: &c->sb_lock); |
294 | } |
295 | |