]> git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/btree_write_buffer.c
Update bcachefs sources to fd381c355c bcachefs: Fix a null ptr deref in fsck check_ex...
[bcachefs-tools-debian] / libbcachefs / btree_write_buffer.c
1 // SPDX-License-Identifier: GPL-2.0
2
3 #include "bcachefs.h"
4 #include "btree_locking.h"
5 #include "btree_update.h"
6 #include "btree_update_interior.h"
7 #include "btree_write_buffer.h"
8 #include "error.h"
9 #include "journal.h"
10 #include "journal_reclaim.h"
11
12 #include <linux/sort.h>
13
14 static int btree_write_buffered_key_cmp(const void *_l, const void *_r)
15 {
16         const struct btree_write_buffered_key *l = _l;
17         const struct btree_write_buffered_key *r = _r;
18
19         return  cmp_int(l->btree, r->btree) ?:
20                 bpos_cmp(l->k.k.p, r->k.k.p) ?:
21                 cmp_int(l->journal_seq, r->journal_seq) ?:
22                 cmp_int(l->journal_offset, r->journal_offset);
23 }
24
25 static int btree_write_buffered_journal_cmp(const void *_l, const void *_r)
26 {
27         const struct btree_write_buffered_key *l = _l;
28         const struct btree_write_buffered_key *r = _r;
29
30         return  cmp_int(l->journal_seq, r->journal_seq);
31 }
32
33 static int bch2_btree_write_buffer_flush_one(struct btree_trans *trans,
34                                              struct btree_iter *iter,
35                                              struct btree_write_buffered_key *wb,
36                                              unsigned commit_flags,
37                                              bool *write_locked,
38                                              size_t *fast)
39 {
40         struct bch_fs *c = trans->c;
41         struct btree_path *path;
42         int ret;
43
44         ret = bch2_btree_iter_traverse(iter);
45         if (ret)
46                 return ret;
47
48         path = iter->path;
49
50         if (!*write_locked) {
51                 ret = bch2_btree_node_lock_write(trans, path, &path->l[0].b->c);
52                 if (ret)
53                         return ret;
54
55                 bch2_btree_node_prep_for_write(trans, path, path->l[0].b);
56                 *write_locked = true;
57         }
58
59         if (!bch2_btree_node_insert_fits(c, path->l[0].b, wb->k.k.u64s)) {
60                 bch2_btree_node_unlock_write(trans, path, path->l[0].b);
61                 *write_locked = false;
62                 goto trans_commit;
63         }
64
65         bch2_btree_insert_key_leaf(trans, path, &wb->k, wb->journal_seq);
66         (*fast)++;
67
68         if (path->ref > 1) {
69                 /*
70                  * We can't clone a path that has write locks: if the path is
71                  * shared, unlock before set_pos(), traverse():
72                  */
73                 bch2_btree_node_unlock_write(trans, path, path->l[0].b);
74                 *write_locked = false;
75         }
76         return 0;
77 trans_commit:
78         return  bch2_trans_update(trans, iter, &wb->k, 0) ?:
79                 bch2_trans_commit(trans, NULL, NULL,
80                                   commit_flags|
81                                   BTREE_INSERT_NOFAIL|
82                                   BTREE_INSERT_JOURNAL_RECLAIM);
83 }
84
85 static union btree_write_buffer_state btree_write_buffer_switch(struct btree_write_buffer *wb)
86 {
87         union btree_write_buffer_state old, new;
88         u64 v = READ_ONCE(wb->state.v);
89
90         do {
91                 old.v = new.v = v;
92
93                 new.nr = 0;
94                 new.idx++;
95         } while ((v = atomic64_cmpxchg_acquire(&wb->state.counter, old.v, new.v)) != old.v);
96
97         while (old.idx == 0 ? wb->state.ref0 : wb->state.ref1)
98                 cpu_relax();
99
100         smp_mb();
101
102         return old;
103 }
104
105 int __bch2_btree_write_buffer_flush(struct btree_trans *trans, unsigned commit_flags,
106                                     bool locked)
107 {
108         struct bch_fs *c = trans->c;
109         struct journal *j = &c->journal;
110         struct btree_write_buffer *wb = &c->btree_write_buffer;
111         struct journal_entry_pin pin;
112         struct btree_write_buffered_key *i, *keys;
113         struct btree_iter iter = { NULL };
114         size_t nr = 0, skipped = 0, fast = 0, slowpath = 0;
115         bool write_locked = false;
116         union btree_write_buffer_state s;
117         int ret = 0;
118
119         memset(&pin, 0, sizeof(pin));
120
121         if (!locked && !mutex_trylock(&wb->flush_lock))
122                 return 0;
123
124         bch2_journal_pin_copy(j, &pin, &wb->journal_pin, NULL);
125         bch2_journal_pin_drop(j, &wb->journal_pin);
126
127         s = btree_write_buffer_switch(wb);
128         keys = wb->keys[s.idx];
129         nr = s.nr;
130
131         /*
132          * We first sort so that we can detect and skip redundant updates, and
133          * then we attempt to flush in sorted btree order, as this is most
134          * efficient.
135          *
136          * However, since we're not flushing in the order they appear in the
137          * journal we won't be able to drop our journal pin until everything is
138          * flushed - which means this could deadlock the journal if we weren't
139          * passing BTREE_INSERT_JOURNAL_RECLAIM. This causes the update to fail
140          * if it would block taking a journal reservation.
141          *
142          * If that happens, simply skip the key so we can optimistically insert
143          * as many keys as possible in the fast path.
144          */
145         sort(keys, nr, sizeof(keys[0]),
146              btree_write_buffered_key_cmp, NULL);
147
148         for (i = keys; i < keys + nr; i++) {
149                 if (i + 1 < keys + nr &&
150                     i[0].btree == i[1].btree &&
151                     bpos_eq(i[0].k.k.p, i[1].k.k.p)) {
152                         skipped++;
153                         i->journal_seq = 0;
154                         continue;
155                 }
156
157                 if (write_locked &&
158                     (iter.path->btree_id != i->btree ||
159                      bpos_gt(i->k.k.p, iter.path->l[0].b->key.k.p))) {
160                         bch2_btree_node_unlock_write(trans, iter.path, iter.path->l[0].b);
161                         write_locked = false;
162                 }
163
164                 if (!iter.path || iter.path->btree_id != i->btree) {
165                         bch2_trans_iter_exit(trans, &iter);
166                         bch2_trans_iter_init(trans, &iter, i->btree, i->k.k.p, BTREE_ITER_INTENT);
167                 }
168
169                 bch2_btree_iter_set_pos(&iter, i->k.k.p);
170                 iter.path->preserve = false;
171
172                 do {
173                         ret = bch2_btree_write_buffer_flush_one(trans, &iter, i,
174                                                 commit_flags, &write_locked, &fast);
175                         if (!write_locked)
176                                 bch2_trans_begin(trans);
177                 } while (bch2_err_matches(ret, BCH_ERR_transaction_restart));
178
179                 if (ret == -BCH_ERR_journal_reclaim_would_deadlock) {
180                         slowpath++;
181                         continue;
182                 }
183                 if (ret)
184                         break;
185
186                 i->journal_seq = 0;
187         }
188
189         if (write_locked)
190                 bch2_btree_node_unlock_write(trans, iter.path, iter.path->l[0].b);
191         bch2_trans_iter_exit(trans, &iter);
192
193         trace_write_buffer_flush(trans, nr, skipped, fast, wb->size);
194
195         if (slowpath)
196                 goto slowpath;
197
198         bch2_fs_fatal_err_on(ret, c, "%s: insert error %s", __func__, bch2_err_str(ret));
199 out:
200         bch2_journal_pin_drop(j, &pin);
201         mutex_unlock(&wb->flush_lock);
202         return ret;
203 slowpath:
204         trace_write_buffer_flush_slowpath(trans, i - keys, nr);
205
206         /*
207          * Now sort the rest by journal seq and bump the journal pin as we go.
208          * The slowpath zapped the seq of keys that were successfully flushed so
209          * we can skip those here.
210          */
211         sort(keys, nr, sizeof(keys[0]),
212              btree_write_buffered_journal_cmp,
213              NULL);
214
215         for (i = keys; i < keys + nr; i++) {
216                 if (!i->journal_seq)
217                         continue;
218
219                 if (i->journal_seq > pin.seq) {
220                         struct journal_entry_pin pin2;
221
222                         memset(&pin2, 0, sizeof(pin2));
223
224                         bch2_journal_pin_add(j, i->journal_seq, &pin2, NULL);
225                         bch2_journal_pin_drop(j, &pin);
226                         bch2_journal_pin_copy(j, &pin, &pin2, NULL);
227                         bch2_journal_pin_drop(j, &pin2);
228                 }
229
230                 ret = commit_do(trans, NULL, NULL,
231                                 commit_flags|
232                                 BTREE_INSERT_NOFAIL|
233                                 BTREE_INSERT_JOURNAL_RECLAIM|
234                                 JOURNAL_WATERMARK_reserved,
235                                 __bch2_btree_insert(trans, i->btree, &i->k, 0));
236                 if (bch2_fs_fatal_err_on(ret, c, "%s: insert error %s", __func__, bch2_err_str(ret)))
237                         break;
238         }
239
240         goto out;
241 }
242
243 int bch2_btree_write_buffer_flush_sync(struct btree_trans *trans)
244 {
245         bch2_trans_unlock(trans);
246         mutex_lock(&trans->c->btree_write_buffer.flush_lock);
247         return __bch2_btree_write_buffer_flush(trans, 0, true);
248 }
249
250 int bch2_btree_write_buffer_flush(struct btree_trans *trans)
251 {
252         return __bch2_btree_write_buffer_flush(trans, 0, false);
253 }
254
255 static int bch2_btree_write_buffer_journal_flush(struct journal *j,
256                                 struct journal_entry_pin *_pin, u64 seq)
257 {
258         struct bch_fs *c = container_of(j, struct bch_fs, journal);
259         struct btree_write_buffer *wb = &c->btree_write_buffer;
260
261         mutex_lock(&wb->flush_lock);
262
263         return bch2_trans_run(c,
264                         __bch2_btree_write_buffer_flush(&trans, BTREE_INSERT_NOCHECK_RW, true));
265 }
266
267 static inline u64 btree_write_buffer_ref(int idx)
268 {
269         return ((union btree_write_buffer_state) {
270                 .ref0 = idx == 0,
271                 .ref1 = idx == 1,
272         }).v;
273 }
274
275 int bch2_btree_insert_keys_write_buffer(struct btree_trans *trans)
276 {
277         struct bch_fs *c = trans->c;
278         struct btree_write_buffer *wb = &c->btree_write_buffer;
279         struct btree_write_buffered_key *i;
280         union btree_write_buffer_state old, new;
281         int ret = 0;
282         u64 v;
283
284         trans_for_each_wb_update(trans, i) {
285                 EBUG_ON(i->k.k.u64s > BTREE_WRITE_BUFERED_U64s_MAX);
286
287                 i->journal_seq          = trans->journal_res.seq;
288                 i->journal_offset       = trans->journal_res.offset;
289         }
290
291         preempt_disable();
292         v = READ_ONCE(wb->state.v);
293         do {
294                 old.v = new.v = v;
295
296                 new.v += btree_write_buffer_ref(new.idx);
297                 new.nr += trans->nr_wb_updates;
298                 if (new.nr > wb->size) {
299                         ret = -BCH_ERR_btree_insert_need_flush_buffer;
300                         goto out;
301                 }
302         } while ((v = atomic64_cmpxchg_acquire(&wb->state.counter, old.v, new.v)) != old.v);
303
304         memcpy(wb->keys[new.idx] + old.nr,
305                trans->wb_updates,
306                sizeof(trans->wb_updates[0]) * trans->nr_wb_updates);
307
308         bch2_journal_pin_add(&c->journal, trans->journal_res.seq, &wb->journal_pin,
309                              bch2_btree_write_buffer_journal_flush);
310
311         atomic64_sub_return_release(btree_write_buffer_ref(new.idx), &wb->state.counter);
312 out:
313         preempt_enable();
314         return ret;
315 }
316
317 void bch2_fs_btree_write_buffer_exit(struct bch_fs *c)
318 {
319         struct btree_write_buffer *wb = &c->btree_write_buffer;
320
321         BUG_ON(wb->state.nr && !bch2_journal_error(&c->journal));
322
323         kvfree(wb->keys[1]);
324         kvfree(wb->keys[0]);
325 }
326
327 int bch2_fs_btree_write_buffer_init(struct bch_fs *c)
328 {
329         struct btree_write_buffer *wb = &c->btree_write_buffer;
330
331         mutex_init(&wb->flush_lock);
332         wb->size = c->opts.btree_write_buffer_size;
333
334         wb->keys[0] = kvmalloc_array(wb->size, sizeof(*wb->keys[0]), GFP_KERNEL);
335         wb->keys[1] = kvmalloc_array(wb->size, sizeof(*wb->keys[1]), GFP_KERNEL);
336         if (!wb->keys[0] || !wb->keys[1])
337                 return -BCH_ERR_ENOMEM_fs_btree_write_buffer_init;
338
339         return 0;
340 }