interconnect: qcom: icc-rpm: Fix peak rate calculation
[linux-2.6-microblaze.git] / fs / bcachefs / backpointers.c
1 // SPDX-License-Identifier: GPL-2.0
2 #include "bcachefs.h"
3 #include "bbpos.h"
4 #include "alloc_background.h"
5 #include "backpointers.h"
6 #include "btree_cache.h"
7 #include "btree_update.h"
8 #include "btree_update_interior.h"
9 #include "btree_write_buffer.h"
10 #include "error.h"
11
12 #include <linux/mm.h>
13
14 static bool extent_matches_bp(struct bch_fs *c,
15                               enum btree_id btree_id, unsigned level,
16                               struct bkey_s_c k,
17                               struct bpos bucket,
18                               struct bch_backpointer bp)
19 {
20         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
21         const union bch_extent_entry *entry;
22         struct extent_ptr_decoded p;
23
24         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
25                 struct bpos bucket2;
26                 struct bch_backpointer bp2;
27
28                 if (p.ptr.cached)
29                         continue;
30
31                 bch2_extent_ptr_to_bp(c, btree_id, level, k, p,
32                                       &bucket2, &bp2);
33                 if (bpos_eq(bucket, bucket2) &&
34                     !memcmp(&bp, &bp2, sizeof(bp)))
35                         return true;
36         }
37
38         return false;
39 }
40
41 int bch2_backpointer_invalid(struct bch_fs *c, struct bkey_s_c k,
42                              enum bkey_invalid_flags flags,
43                              struct printbuf *err)
44 {
45         struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);
46         struct bpos bucket = bp_pos_to_bucket(c, bp.k->p);
47         int ret = 0;
48
49         bkey_fsck_err_on(!bpos_eq(bp.k->p, bucket_pos_to_bp(c, bucket, bp.v->bucket_offset)),
50                          c, err,
51                          backpointer_pos_wrong,
52                          "backpointer at wrong pos");
53 fsck_err:
54         return ret;
55 }
56
57 void bch2_backpointer_to_text(struct printbuf *out, const struct bch_backpointer *bp)
58 {
59         prt_printf(out, "btree=%s l=%u offset=%llu:%u len=%u pos=",
60                bch2_btree_id_str(bp->btree_id),
61                bp->level,
62                (u64) (bp->bucket_offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT),
63                (u32) bp->bucket_offset & ~(~0U << MAX_EXTENT_COMPRESS_RATIO_SHIFT),
64                bp->bucket_len);
65         bch2_bpos_to_text(out, bp->pos);
66 }
67
68 void bch2_backpointer_k_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
69 {
70         prt_str(out, "bucket=");
71         bch2_bpos_to_text(out, bp_pos_to_bucket(c, k.k->p));
72         prt_str(out, " ");
73
74         bch2_backpointer_to_text(out, bkey_s_c_to_backpointer(k).v);
75 }
76
77 void bch2_backpointer_swab(struct bkey_s k)
78 {
79         struct bkey_s_backpointer bp = bkey_s_to_backpointer(k);
80
81         bp.v->bucket_offset     = swab40(bp.v->bucket_offset);
82         bp.v->bucket_len        = swab32(bp.v->bucket_len);
83         bch2_bpos_swab(&bp.v->pos);
84 }
85
86 static noinline int backpointer_mod_err(struct btree_trans *trans,
87                                         struct bch_backpointer bp,
88                                         struct bkey_s_c bp_k,
89                                         struct bkey_s_c orig_k,
90                                         bool insert)
91 {
92         struct bch_fs *c = trans->c;
93         struct printbuf buf = PRINTBUF;
94
95         if (insert) {
96                 prt_printf(&buf, "existing backpointer found when inserting ");
97                 bch2_backpointer_to_text(&buf, &bp);
98                 prt_newline(&buf);
99                 printbuf_indent_add(&buf, 2);
100
101                 prt_printf(&buf, "found ");
102                 bch2_bkey_val_to_text(&buf, c, bp_k);
103                 prt_newline(&buf);
104
105                 prt_printf(&buf, "for ");
106                 bch2_bkey_val_to_text(&buf, c, orig_k);
107
108                 bch_err(c, "%s", buf.buf);
109         } else if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) {
110                 prt_printf(&buf, "backpointer not found when deleting");
111                 prt_newline(&buf);
112                 printbuf_indent_add(&buf, 2);
113
114                 prt_printf(&buf, "searching for ");
115                 bch2_backpointer_to_text(&buf, &bp);
116                 prt_newline(&buf);
117
118                 prt_printf(&buf, "got ");
119                 bch2_bkey_val_to_text(&buf, c, bp_k);
120                 prt_newline(&buf);
121
122                 prt_printf(&buf, "for ");
123                 bch2_bkey_val_to_text(&buf, c, orig_k);
124
125                 bch_err(c, "%s", buf.buf);
126         }
127
128         printbuf_exit(&buf);
129
130         if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) {
131                 bch2_inconsistent_error(c);
132                 return -EIO;
133         } else {
134                 return 0;
135         }
136 }
137
138 int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
139                                 struct bkey_i_backpointer *bp_k,
140                                 struct bch_backpointer bp,
141                                 struct bkey_s_c orig_k,
142                                 bool insert)
143 {
144         struct btree_iter bp_iter;
145         struct bkey_s_c k;
146         int ret;
147
148         k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,
149                                bp_k->k.p,
150                                BTREE_ITER_INTENT|
151                                BTREE_ITER_SLOTS|
152                                BTREE_ITER_WITH_UPDATES);
153         ret = bkey_err(k);
154         if (ret)
155                 goto err;
156
157         if (insert
158             ? k.k->type
159             : (k.k->type != KEY_TYPE_backpointer ||
160                memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp)))) {
161                 ret = backpointer_mod_err(trans, bp, k, orig_k, insert);
162                 if (ret)
163                         goto err;
164         }
165
166         ret = bch2_trans_update(trans, &bp_iter, &bp_k->k_i, 0);
167 err:
168         bch2_trans_iter_exit(trans, &bp_iter);
169         return ret;
170 }
171
172 /*
173  * Find the next backpointer >= *bp_offset:
174  */
175 int bch2_get_next_backpointer(struct btree_trans *trans,
176                               struct bpos bucket, int gen,
177                               struct bpos *bp_pos,
178                               struct bch_backpointer *bp,
179                               unsigned iter_flags)
180 {
181         struct bch_fs *c = trans->c;
182         struct bpos bp_end_pos = bucket_pos_to_bp(c, bpos_nosnap_successor(bucket), 0);
183         struct btree_iter alloc_iter = { NULL }, bp_iter = { NULL };
184         struct bkey_s_c k;
185         int ret = 0;
186
187         if (bpos_ge(*bp_pos, bp_end_pos))
188                 goto done;
189
190         if (gen >= 0) {
191                 k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc,
192                                        bucket, BTREE_ITER_CACHED|iter_flags);
193                 ret = bkey_err(k);
194                 if (ret)
195                         goto out;
196
197                 if (k.k->type != KEY_TYPE_alloc_v4 ||
198                     bkey_s_c_to_alloc_v4(k).v->gen != gen)
199                         goto done;
200         }
201
202         *bp_pos = bpos_max(*bp_pos, bucket_pos_to_bp(c, bucket, 0));
203
204         for_each_btree_key_norestart(trans, bp_iter, BTREE_ID_backpointers,
205                                      *bp_pos, iter_flags, k, ret) {
206                 if (bpos_ge(k.k->p, bp_end_pos))
207                         break;
208
209                 *bp_pos = k.k->p;
210                 *bp = *bkey_s_c_to_backpointer(k).v;
211                 goto out;
212         }
213 done:
214         *bp_pos = SPOS_MAX;
215 out:
216         bch2_trans_iter_exit(trans, &bp_iter);
217         bch2_trans_iter_exit(trans, &alloc_iter);
218         return ret;
219 }
220
221 static void backpointer_not_found(struct btree_trans *trans,
222                                   struct bpos bp_pos,
223                                   struct bch_backpointer bp,
224                                   struct bkey_s_c k)
225 {
226         struct bch_fs *c = trans->c;
227         struct printbuf buf = PRINTBUF;
228         struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
229
230         /*
231          * If we're using the btree write buffer, the backpointer we were
232          * looking at may have already been deleted - failure to find what it
233          * pointed to is not an error:
234          */
235         if (likely(!bch2_backpointers_no_use_write_buffer))
236                 return;
237
238         prt_printf(&buf, "backpointer doesn't match %s it points to:\n  ",
239                    bp.level ? "btree node" : "extent");
240         prt_printf(&buf, "bucket: ");
241         bch2_bpos_to_text(&buf, bucket);
242         prt_printf(&buf, "\n  ");
243
244         prt_printf(&buf, "backpointer pos: ");
245         bch2_bpos_to_text(&buf, bp_pos);
246         prt_printf(&buf, "\n  ");
247
248         bch2_backpointer_to_text(&buf, &bp);
249         prt_printf(&buf, "\n  ");
250         bch2_bkey_val_to_text(&buf, c, k);
251         if (c->curr_recovery_pass >= BCH_RECOVERY_PASS_check_extents_to_backpointers)
252                 bch_err_ratelimited(c, "%s", buf.buf);
253         else
254                 bch2_trans_inconsistent(trans, "%s", buf.buf);
255
256         printbuf_exit(&buf);
257 }
258
259 struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
260                                          struct btree_iter *iter,
261                                          struct bpos bp_pos,
262                                          struct bch_backpointer bp,
263                                          unsigned iter_flags)
264 {
265         if (likely(!bp.level)) {
266                 struct bch_fs *c = trans->c;
267                 struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
268                 struct bkey_s_c k;
269
270                 bch2_trans_node_iter_init(trans, iter,
271                                           bp.btree_id,
272                                           bp.pos,
273                                           0, 0,
274                                           iter_flags);
275                 k = bch2_btree_iter_peek_slot(iter);
276                 if (bkey_err(k)) {
277                         bch2_trans_iter_exit(trans, iter);
278                         return k;
279                 }
280
281                 if (k.k && extent_matches_bp(c, bp.btree_id, bp.level, k, bucket, bp))
282                         return k;
283
284                 bch2_trans_iter_exit(trans, iter);
285                 backpointer_not_found(trans, bp_pos, bp, k);
286                 return bkey_s_c_null;
287         } else {
288                 struct btree *b = bch2_backpointer_get_node(trans, iter, bp_pos, bp);
289
290                 if (IS_ERR_OR_NULL(b)) {
291                         bch2_trans_iter_exit(trans, iter);
292                         return IS_ERR(b) ? bkey_s_c_err(PTR_ERR(b)) : bkey_s_c_null;
293                 }
294                 return bkey_i_to_s_c(&b->key);
295         }
296 }
297
298 struct btree *bch2_backpointer_get_node(struct btree_trans *trans,
299                                         struct btree_iter *iter,
300                                         struct bpos bp_pos,
301                                         struct bch_backpointer bp)
302 {
303         struct bch_fs *c = trans->c;
304         struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
305         struct btree *b;
306
307         BUG_ON(!bp.level);
308
309         bch2_trans_node_iter_init(trans, iter,
310                                   bp.btree_id,
311                                   bp.pos,
312                                   0,
313                                   bp.level - 1,
314                                   0);
315         b = bch2_btree_iter_peek_node(iter);
316         if (IS_ERR(b))
317                 goto err;
318
319         BUG_ON(b->c.level != bp.level - 1);
320
321         if (b && extent_matches_bp(c, bp.btree_id, bp.level,
322                                    bkey_i_to_s_c(&b->key),
323                                    bucket, bp))
324                 return b;
325
326         if (b && btree_node_will_make_reachable(b)) {
327                 b = ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node);
328         } else {
329                 backpointer_not_found(trans, bp_pos, bp, bkey_i_to_s_c(&b->key));
330                 b = NULL;
331         }
332 err:
333         bch2_trans_iter_exit(trans, iter);
334         return b;
335 }
336
337 static int bch2_check_btree_backpointer(struct btree_trans *trans, struct btree_iter *bp_iter,
338                                         struct bkey_s_c k)
339 {
340         struct bch_fs *c = trans->c;
341         struct btree_iter alloc_iter = { NULL };
342         struct bkey_s_c alloc_k;
343         struct printbuf buf = PRINTBUF;
344         int ret = 0;
345
346         if (fsck_err_on(!bch2_dev_exists2(c, k.k->p.inode), c,
347                         backpointer_to_missing_device,
348                         "backpointer for missing device:\n%s",
349                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
350                 ret = bch2_btree_delete_at(trans, bp_iter, 0);
351                 goto out;
352         }
353
354         alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc,
355                                      bp_pos_to_bucket(c, k.k->p), 0);
356         ret = bkey_err(alloc_k);
357         if (ret)
358                 goto out;
359
360         if (fsck_err_on(alloc_k.k->type != KEY_TYPE_alloc_v4, c,
361                         backpointer_to_missing_alloc,
362                         "backpointer for nonexistent alloc key: %llu:%llu:0\n%s",
363                         alloc_iter.pos.inode, alloc_iter.pos.offset,
364                         (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) {
365                 ret = bch2_btree_delete_at(trans, bp_iter, 0);
366                 goto out;
367         }
368 out:
369 fsck_err:
370         bch2_trans_iter_exit(trans, &alloc_iter);
371         printbuf_exit(&buf);
372         return ret;
373 }
374
375 /* verify that every backpointer has a corresponding alloc key */
376 int bch2_check_btree_backpointers(struct bch_fs *c)
377 {
378         struct btree_iter iter;
379         struct bkey_s_c k;
380         int ret;
381
382         ret = bch2_trans_run(c,
383                 for_each_btree_key_commit(trans, iter,
384                         BTREE_ID_backpointers, POS_MIN, 0, k,
385                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
386                   bch2_check_btree_backpointer(trans, &iter, k)));
387         if (ret)
388                 bch_err_fn(c, ret);
389         return ret;
390 }
391
392 struct bpos_level {
393         unsigned        level;
394         struct bpos     pos;
395 };
396
397 static int check_bp_exists(struct btree_trans *trans,
398                            struct bpos bucket,
399                            struct bch_backpointer bp,
400                            struct bkey_s_c orig_k,
401                            struct bpos bucket_start,
402                            struct bpos bucket_end,
403                            struct bpos_level *last_flushed)
404 {
405         struct bch_fs *c = trans->c;
406         struct btree_iter bp_iter = { NULL };
407         struct printbuf buf = PRINTBUF;
408         struct bkey_s_c bp_k;
409         int ret;
410
411         if (bpos_lt(bucket, bucket_start) ||
412             bpos_gt(bucket, bucket_end))
413                 return 0;
414
415         if (!bch2_dev_bucket_exists(c, bucket))
416                 goto missing;
417
418         bp_k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,
419                                   bucket_pos_to_bp(c, bucket, bp.bucket_offset),
420                                   0);
421         ret = bkey_err(bp_k);
422         if (ret)
423                 goto err;
424
425         if (bp_k.k->type != KEY_TYPE_backpointer ||
426             memcmp(bkey_s_c_to_backpointer(bp_k).v, &bp, sizeof(bp))) {
427                 if (last_flushed->level != bp.level ||
428                     !bpos_eq(last_flushed->pos, orig_k.k->p)) {
429                         last_flushed->level = bp.level;
430                         last_flushed->pos = orig_k.k->p;
431
432                         ret = bch2_btree_write_buffer_flush_sync(trans) ?:
433                                 -BCH_ERR_transaction_restart_write_buffer_flush;
434                         goto out;
435                 }
436                 goto missing;
437         }
438 out:
439 err:
440 fsck_err:
441         bch2_trans_iter_exit(trans, &bp_iter);
442         printbuf_exit(&buf);
443         return ret;
444 missing:
445         prt_printf(&buf, "missing backpointer for btree=%s l=%u ",
446                bch2_btree_id_str(bp.btree_id), bp.level);
447         bch2_bkey_val_to_text(&buf, c, orig_k);
448         prt_printf(&buf, "\nbp pos ");
449         bch2_bpos_to_text(&buf, bp_iter.pos);
450
451         if (c->sb.version_upgrade_complete < bcachefs_metadata_version_backpointers ||
452             c->opts.reconstruct_alloc ||
453             fsck_err(c, ptr_to_missing_backpointer, "%s", buf.buf))
454                 ret = bch2_bucket_backpointer_mod(trans, bucket, bp, orig_k, true);
455
456         goto out;
457 }
458
459 static int check_extent_to_backpointers(struct btree_trans *trans,
460                                         struct btree_iter *iter,
461                                         struct bpos bucket_start,
462                                         struct bpos bucket_end,
463                                         struct bpos_level *last_flushed)
464 {
465         struct bch_fs *c = trans->c;
466         struct bkey_ptrs_c ptrs;
467         const union bch_extent_entry *entry;
468         struct extent_ptr_decoded p;
469         struct bkey_s_c k;
470         int ret;
471
472         k = bch2_btree_iter_peek_all_levels(iter);
473         ret = bkey_err(k);
474         if (ret)
475                 return ret;
476         if (!k.k)
477                 return 0;
478
479         ptrs = bch2_bkey_ptrs_c(k);
480         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
481                 struct bpos bucket_pos;
482                 struct bch_backpointer bp;
483
484                 if (p.ptr.cached)
485                         continue;
486
487                 bch2_extent_ptr_to_bp(c, iter->btree_id, iter->path->level,
488                                       k, p, &bucket_pos, &bp);
489
490                 ret = check_bp_exists(trans, bucket_pos, bp, k,
491                                       bucket_start, bucket_end,
492                                       last_flushed);
493                 if (ret)
494                         return ret;
495         }
496
497         return 0;
498 }
499
500 static int check_btree_root_to_backpointers(struct btree_trans *trans,
501                                             enum btree_id btree_id,
502                                             struct bpos bucket_start,
503                                             struct bpos bucket_end,
504                                             struct bpos_level *last_flushed)
505 {
506         struct bch_fs *c = trans->c;
507         struct btree_root *r = bch2_btree_id_root(c, btree_id);
508         struct btree_iter iter;
509         struct btree *b;
510         struct bkey_s_c k;
511         struct bkey_ptrs_c ptrs;
512         struct extent_ptr_decoded p;
513         const union bch_extent_entry *entry;
514         int ret;
515
516         bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0, r->level, 0);
517         b = bch2_btree_iter_peek_node(&iter);
518         ret = PTR_ERR_OR_ZERO(b);
519         if (ret)
520                 goto err;
521
522         BUG_ON(b != btree_node_root(c, b));
523
524         k = bkey_i_to_s_c(&b->key);
525         ptrs = bch2_bkey_ptrs_c(k);
526         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
527                 struct bpos bucket_pos;
528                 struct bch_backpointer bp;
529
530                 if (p.ptr.cached)
531                         continue;
532
533                 bch2_extent_ptr_to_bp(c, iter.btree_id, b->c.level + 1,
534                                       k, p, &bucket_pos, &bp);
535
536                 ret = check_bp_exists(trans, bucket_pos, bp, k,
537                                       bucket_start, bucket_end,
538                                       last_flushed);
539                 if (ret)
540                         goto err;
541         }
542 err:
543         bch2_trans_iter_exit(trans, &iter);
544         return ret;
545 }
546
547 static inline struct bbpos bp_to_bbpos(struct bch_backpointer bp)
548 {
549         return (struct bbpos) {
550                 .btree  = bp.btree_id,
551                 .pos    = bp.pos,
552         };
553 }
554
555 static size_t btree_nodes_fit_in_ram(struct bch_fs *c)
556 {
557         struct sysinfo i;
558         u64 mem_bytes;
559
560         si_meminfo(&i);
561         mem_bytes = i.totalram * i.mem_unit;
562         return div_u64(mem_bytes >> 1, btree_bytes(c));
563 }
564
565 static int bch2_get_btree_in_memory_pos(struct btree_trans *trans,
566                                         unsigned btree_leaf_mask,
567                                         unsigned btree_interior_mask,
568                                         struct bbpos start, struct bbpos *end)
569 {
570         struct btree_iter iter;
571         struct bkey_s_c k;
572         size_t btree_nodes = btree_nodes_fit_in_ram(trans->c);
573         enum btree_id btree;
574         int ret = 0;
575
576         for (btree = start.btree; btree < BTREE_ID_NR && !ret; btree++) {
577                 unsigned depth = ((1U << btree) & btree_leaf_mask) ? 1 : 2;
578
579                 if (!((1U << btree) & btree_leaf_mask) &&
580                     !((1U << btree) & btree_interior_mask))
581                         continue;
582
583                 bch2_trans_node_iter_init(trans, &iter, btree,
584                                           btree == start.btree ? start.pos : POS_MIN,
585                                           0, depth, 0);
586                 /*
587                  * for_each_btree_key_contineu() doesn't check the return value
588                  * from bch2_btree_iter_advance(), which is needed when
589                  * iterating over interior nodes where we'll see keys at
590                  * SPOS_MAX:
591                  */
592                 do {
593                         k = __bch2_btree_iter_peek_and_restart(trans, &iter, 0);
594                         ret = bkey_err(k);
595                         if (!k.k || ret)
596                                 break;
597
598                         --btree_nodes;
599                         if (!btree_nodes) {
600                                 *end = BBPOS(btree, k.k->p);
601                                 bch2_trans_iter_exit(trans, &iter);
602                                 return 0;
603                         }
604                 } while (bch2_btree_iter_advance(&iter));
605                 bch2_trans_iter_exit(trans, &iter);
606         }
607
608         *end = BBPOS_MAX;
609         return ret;
610 }
611
612 static int bch2_check_extents_to_backpointers_pass(struct btree_trans *trans,
613                                                    struct bpos bucket_start,
614                                                    struct bpos bucket_end)
615 {
616         struct bch_fs *c = trans->c;
617         struct btree_iter iter;
618         enum btree_id btree_id;
619         struct bpos_level last_flushed = { UINT_MAX, POS_MIN };
620         int ret = 0;
621
622         for (btree_id = 0; btree_id < btree_id_nr_alive(c); btree_id++) {
623                 unsigned depth = btree_type_has_ptrs(btree_id) ? 0 : 1;
624
625                 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0,
626                                           depth,
627                                           BTREE_ITER_ALL_LEVELS|
628                                           BTREE_ITER_PREFETCH);
629
630                 do {
631                         ret = commit_do(trans, NULL, NULL,
632                                         BTREE_INSERT_LAZY_RW|
633                                         BTREE_INSERT_NOFAIL,
634                                         check_extent_to_backpointers(trans, &iter,
635                                                                 bucket_start, bucket_end,
636                                                                 &last_flushed));
637                         if (ret)
638                                 break;
639                 } while (!bch2_btree_iter_advance(&iter));
640
641                 bch2_trans_iter_exit(trans, &iter);
642
643                 if (ret)
644                         break;
645
646                 ret = commit_do(trans, NULL, NULL,
647                                 BTREE_INSERT_LAZY_RW|
648                                 BTREE_INSERT_NOFAIL,
649                                 check_btree_root_to_backpointers(trans, btree_id,
650                                                         bucket_start, bucket_end,
651                                                         &last_flushed));
652                 if (ret)
653                         break;
654         }
655         return ret;
656 }
657
658 static struct bpos bucket_pos_to_bp_safe(const struct bch_fs *c,
659                                          struct bpos bucket)
660 {
661         return bch2_dev_exists2(c, bucket.inode)
662                 ? bucket_pos_to_bp(c, bucket, 0)
663                 : bucket;
664 }
665
666 static int bch2_get_alloc_in_memory_pos(struct btree_trans *trans,
667                                         struct bpos start, struct bpos *end)
668 {
669         struct btree_iter alloc_iter;
670         struct btree_iter bp_iter;
671         struct bkey_s_c alloc_k, bp_k;
672         size_t btree_nodes = btree_nodes_fit_in_ram(trans->c);
673         bool alloc_end = false, bp_end = false;
674         int ret = 0;
675
676         bch2_trans_node_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
677                                   start, 0, 1, 0);
678         bch2_trans_node_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
679                                   bucket_pos_to_bp_safe(trans->c, start), 0, 1, 0);
680         while (1) {
681                 alloc_k = !alloc_end
682                         ? __bch2_btree_iter_peek_and_restart(trans, &alloc_iter, 0)
683                         : bkey_s_c_null;
684                 bp_k = !bp_end
685                         ? __bch2_btree_iter_peek_and_restart(trans, &bp_iter, 0)
686                         : bkey_s_c_null;
687
688                 ret = bkey_err(alloc_k) ?: bkey_err(bp_k);
689                 if ((!alloc_k.k && !bp_k.k) || ret) {
690                         *end = SPOS_MAX;
691                         break;
692                 }
693
694                 --btree_nodes;
695                 if (!btree_nodes) {
696                         *end = alloc_k.k ? alloc_k.k->p : SPOS_MAX;
697                         break;
698                 }
699
700                 if (bpos_lt(alloc_iter.pos, SPOS_MAX) &&
701                     bpos_lt(bucket_pos_to_bp_safe(trans->c, alloc_iter.pos), bp_iter.pos)) {
702                         if (!bch2_btree_iter_advance(&alloc_iter))
703                                 alloc_end = true;
704                 } else {
705                         if (!bch2_btree_iter_advance(&bp_iter))
706                                 bp_end = true;
707                 }
708         }
709         bch2_trans_iter_exit(trans, &bp_iter);
710         bch2_trans_iter_exit(trans, &alloc_iter);
711         return ret;
712 }
713
714 int bch2_check_extents_to_backpointers(struct bch_fs *c)
715 {
716         struct btree_trans *trans = bch2_trans_get(c);
717         struct bpos start = POS_MIN, end;
718         int ret;
719
720         while (1) {
721                 ret = bch2_get_alloc_in_memory_pos(trans, start, &end);
722                 if (ret)
723                         break;
724
725                 if (bpos_eq(start, POS_MIN) && !bpos_eq(end, SPOS_MAX))
726                         bch_verbose(c, "%s(): alloc info does not fit in ram, running in multiple passes with %zu nodes per pass",
727                                     __func__, btree_nodes_fit_in_ram(c));
728
729                 if (!bpos_eq(start, POS_MIN) || !bpos_eq(end, SPOS_MAX)) {
730                         struct printbuf buf = PRINTBUF;
731
732                         prt_str(&buf, "check_extents_to_backpointers(): ");
733                         bch2_bpos_to_text(&buf, start);
734                         prt_str(&buf, "-");
735                         bch2_bpos_to_text(&buf, end);
736
737                         bch_verbose(c, "%s", buf.buf);
738                         printbuf_exit(&buf);
739                 }
740
741                 ret = bch2_check_extents_to_backpointers_pass(trans, start, end);
742                 if (ret || bpos_eq(end, SPOS_MAX))
743                         break;
744
745                 start = bpos_successor(end);
746         }
747         bch2_trans_put(trans);
748
749         if (ret)
750                 bch_err_fn(c, ret);
751         return ret;
752 }
753
754 static int check_one_backpointer(struct btree_trans *trans,
755                                  struct bbpos start,
756                                  struct bbpos end,
757                                  struct bkey_s_c_backpointer bp,
758                                  struct bpos *last_flushed_pos)
759 {
760         struct bch_fs *c = trans->c;
761         struct btree_iter iter;
762         struct bbpos pos = bp_to_bbpos(*bp.v);
763         struct bkey_s_c k;
764         struct printbuf buf = PRINTBUF;
765         int ret;
766
767         if (bbpos_cmp(pos, start) < 0 ||
768             bbpos_cmp(pos, end) > 0)
769                 return 0;
770
771         k = bch2_backpointer_get_key(trans, &iter, bp.k->p, *bp.v, 0);
772         ret = bkey_err(k);
773         if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
774                 return 0;
775         if (ret)
776                 return ret;
777
778         if (!k.k && !bpos_eq(*last_flushed_pos, bp.k->p)) {
779                 *last_flushed_pos = bp.k->p;
780                 ret = bch2_btree_write_buffer_flush_sync(trans) ?:
781                         -BCH_ERR_transaction_restart_write_buffer_flush;
782                 goto out;
783         }
784
785         if (fsck_err_on(!k.k, c,
786                         backpointer_to_missing_ptr,
787                         "backpointer for missing %s\n  %s",
788                         bp.v->level ? "btree node" : "extent",
789                         (bch2_bkey_val_to_text(&buf, c, bp.s_c), buf.buf))) {
790                 ret = bch2_btree_delete_at_buffered(trans, BTREE_ID_backpointers, bp.k->p);
791                 goto out;
792         }
793 out:
794 fsck_err:
795         bch2_trans_iter_exit(trans, &iter);
796         printbuf_exit(&buf);
797         return ret;
798 }
799
800 static int bch2_check_backpointers_to_extents_pass(struct btree_trans *trans,
801                                                    struct bbpos start,
802                                                    struct bbpos end)
803 {
804         struct btree_iter iter;
805         struct bkey_s_c k;
806         struct bpos last_flushed_pos = SPOS_MAX;
807
808         return for_each_btree_key_commit(trans, iter, BTREE_ID_backpointers,
809                                   POS_MIN, BTREE_ITER_PREFETCH, k,
810                                   NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
811                 check_one_backpointer(trans, start, end,
812                                       bkey_s_c_to_backpointer(k),
813                                       &last_flushed_pos));
814 }
815
816 int bch2_check_backpointers_to_extents(struct bch_fs *c)
817 {
818         struct btree_trans *trans = bch2_trans_get(c);
819         struct bbpos start = (struct bbpos) { .btree = 0, .pos = POS_MIN, }, end;
820         int ret;
821
822         while (1) {
823                 ret = bch2_get_btree_in_memory_pos(trans,
824                                                    (1U << BTREE_ID_extents)|
825                                                    (1U << BTREE_ID_reflink),
826                                                    ~0,
827                                                    start, &end);
828                 if (ret)
829                         break;
830
831                 if (!bbpos_cmp(start, BBPOS_MIN) &&
832                     bbpos_cmp(end, BBPOS_MAX))
833                         bch_verbose(c, "%s(): extents do not fit in ram, running in multiple passes with %zu nodes per pass",
834                                     __func__, btree_nodes_fit_in_ram(c));
835
836                 if (bbpos_cmp(start, BBPOS_MIN) ||
837                     bbpos_cmp(end, BBPOS_MAX)) {
838                         struct printbuf buf = PRINTBUF;
839
840                         prt_str(&buf, "check_backpointers_to_extents(): ");
841                         bch2_bbpos_to_text(&buf, start);
842                         prt_str(&buf, "-");
843                         bch2_bbpos_to_text(&buf, end);
844
845                         bch_verbose(c, "%s", buf.buf);
846                         printbuf_exit(&buf);
847                 }
848
849                 ret = bch2_check_backpointers_to_extents_pass(trans, start, end);
850                 if (ret || !bbpos_cmp(end, BBPOS_MAX))
851                         break;
852
853                 start = bbpos_successor(end);
854         }
855         bch2_trans_put(trans);
856
857         if (ret)
858                 bch_err_fn(c, ret);
859         return ret;
860 }