]> git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/backpointers.c
Update bcachefs sources to cbccc6d869 bcachefs: Ratelimit ec error message
[bcachefs-tools-debian] / libbcachefs / backpointers.c
1 // SPDX-License-Identifier: GPL-2.0
2 #include "bcachefs.h"
3 #include "alloc_background.h"
4 #include "backpointers.h"
5 #include "btree_cache.h"
6 #include "btree_update.h"
7 #include "error.h"
8
9 #define MAX_EXTENT_COMPRESS_RATIO_SHIFT         10
10
11 /*
12  * Convert from pos in backpointer btree to pos of corresponding bucket in alloc
13  * btree:
14  */
15 static inline struct bpos bp_pos_to_bucket(const struct bch_fs *c,
16                                            struct bpos bp_pos)
17 {
18         struct bch_dev *ca = bch_dev_bkey_exists(c, bp_pos.inode);
19         u64 bucket_sector = bp_pos.offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT;
20
21         return POS(bp_pos.inode, sector_to_bucket(ca, bucket_sector));
22 }
23
24 /*
25  * Convert from pos in alloc btree + bucket offset to pos in backpointer btree:
26  */
27 static inline struct bpos bucket_pos_to_bp(const struct bch_fs *c,
28                                            struct bpos bucket,
29                                            u64 bucket_offset)
30 {
31         struct bch_dev *ca = bch_dev_bkey_exists(c, bucket.inode);
32         struct bpos ret;
33
34         ret = POS(bucket.inode,
35                   (bucket_to_sector(ca, bucket.offset) <<
36                    MAX_EXTENT_COMPRESS_RATIO_SHIFT) + bucket_offset);
37
38         BUG_ON(bpos_cmp(bucket, bp_pos_to_bucket(c, ret)));
39
40         return ret;
41 }
42
43 void bch2_extent_ptr_to_bp(struct bch_fs *c,
44                            enum btree_id btree_id, unsigned level,
45                            struct bkey_s_c k, struct extent_ptr_decoded p,
46                            struct bpos *bucket_pos, struct bch_backpointer *bp)
47 {
48         enum bch_data_type data_type = level ? BCH_DATA_btree : BCH_DATA_user;
49         s64 sectors = level ? btree_sectors(c) : k.k->size;
50         u32 bucket_offset;
51
52         *bucket_pos = PTR_BUCKET_POS_OFFSET(c, &p.ptr, &bucket_offset);
53         *bp = (struct bch_backpointer) {
54                 .btree_id       = btree_id,
55                 .level          = level,
56                 .data_type      = data_type,
57                 .bucket_offset  = ((u64) bucket_offset << MAX_EXTENT_COMPRESS_RATIO_SHIFT) +
58                         p.crc.offset,
59                 .bucket_len     = ptr_disk_sectors(sectors, p),
60                 .pos            = k.k->p,
61         };
62 }
63
64 static bool extent_matches_bp(struct bch_fs *c,
65                               enum btree_id btree_id, unsigned level,
66                               struct bkey_s_c k,
67                               struct bpos bucket,
68                               struct bch_backpointer bp)
69 {
70         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
71         const union bch_extent_entry *entry;
72         struct extent_ptr_decoded p;
73
74         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
75                 struct bpos bucket2;
76                 struct bch_backpointer bp2;
77
78                 if (p.ptr.cached)
79                         continue;
80
81                 bch2_extent_ptr_to_bp(c, btree_id, level, k, p,
82                                       &bucket2, &bp2);
83                 if (!bpos_cmp(bucket, bucket2) &&
84                     !memcmp(&bp, &bp2, sizeof(bp)))
85                         return true;
86         }
87
88         return false;
89 }
90
91 int bch2_backpointer_invalid(const struct bch_fs *c, struct bkey_s_c k,
92                              int rw, struct printbuf *err)
93 {
94         struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);
95         struct bpos bucket = bp_pos_to_bucket(c, bp.k->p);
96
97         if (bkey_val_bytes(bp.k) < sizeof(*bp.v)) {
98                 prt_str(err, "incorrect value size");
99                 return -EINVAL;
100         }
101
102         if (bpos_cmp(bp.k->p, bucket_pos_to_bp(c, bucket, bp.v->bucket_offset))) {
103                 prt_str(err, "backpointer at wrong pos");
104                 return -EINVAL;
105         }
106
107         return 0;
108 }
109
110 void bch2_backpointer_to_text(struct printbuf *out, const struct bch_backpointer *bp)
111 {
112         prt_printf(out, "btree=%s l=%u offset=%llu:%u len=%u pos=",
113                bch2_btree_ids[bp->btree_id],
114                bp->level,
115                (u64) (bp->bucket_offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT),
116                (u32) bp->bucket_offset & ~(~0U << MAX_EXTENT_COMPRESS_RATIO_SHIFT),
117                bp->bucket_len);
118         bch2_bpos_to_text(out, bp->pos);
119 }
120
121 void bch2_backpointer_k_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
122 {
123         bch2_backpointer_to_text(out, bkey_s_c_to_backpointer(k).v);
124 }
125
126 void bch2_backpointer_swab(struct bkey_s k)
127 {
128         struct bkey_s_backpointer bp = bkey_s_to_backpointer(k);
129
130         bp.v->bucket_offset     = swab32(bp.v->bucket_offset);
131         bp.v->bucket_len        = swab32(bp.v->bucket_len);
132         bch2_bpos_swab(&bp.v->pos);
133 }
134
135 #define BACKPOINTER_OFFSET_MAX  ((1ULL << 40) - 1)
136
137 static inline int backpointer_cmp(struct bch_backpointer l, struct bch_backpointer r)
138 {
139         return cmp_int(l.bucket_offset, r.bucket_offset);
140 }
141
142 static int bch2_backpointer_del_by_offset(struct btree_trans *trans,
143                                           struct bpos bucket,
144                                           u64 bp_offset,
145                                           struct bch_backpointer bp)
146 {
147         struct bch_fs *c = trans->c;
148         struct btree_iter iter;
149         struct bkey_s_c k;
150         int ret;
151
152         if (bp_offset < BACKPOINTER_OFFSET_MAX) {
153                 struct bch_backpointer *bps;
154                 struct bkey_i_alloc_v4 *a;
155                 unsigned i, nr;
156
157                 bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc,
158                                      bucket,
159                                      BTREE_ITER_INTENT|
160                                      BTREE_ITER_SLOTS|
161                                      BTREE_ITER_WITH_UPDATES);
162                 k = bch2_btree_iter_peek_slot(&iter);
163                 ret = bkey_err(k);
164                 if (ret)
165                         goto err;
166
167                 if (k.k->type != KEY_TYPE_alloc_v4) {
168                         ret = -ENOENT;
169                         goto err;
170                 }
171
172                 a = bch2_alloc_to_v4_mut(trans, k);
173                 ret = PTR_ERR_OR_ZERO(a);
174                 if (ret)
175                         goto err;
176                 bps = alloc_v4_backpointers(&a->v);
177                 nr = BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v);
178
179                 for (i = 0; i < nr; i++) {
180                         if (bps[i].bucket_offset == bp_offset)
181                                 goto found;
182                         if (bps[i].bucket_offset > bp_offset)
183                                 break;
184                 }
185
186                 ret = -ENOENT;
187                 goto err;
188 found:
189                 if (memcmp(&bps[i], &bp, sizeof(bp))) {
190                         ret = -ENOENT;
191                         goto err;
192                 }
193                 array_remove_item(bps, nr, i);
194                 SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v, nr);
195                 set_alloc_v4_u64s(a);
196                 ret = bch2_trans_update(trans, &iter, &a->k_i, 0);
197         } else {
198                 bp_offset -= BACKPOINTER_OFFSET_MAX;
199
200                 bch2_trans_iter_init(trans, &iter, BTREE_ID_backpointers,
201                                      bucket_pos_to_bp(c, bucket, bp_offset),
202                                      BTREE_ITER_INTENT|
203                                      BTREE_ITER_SLOTS|
204                                      BTREE_ITER_WITH_UPDATES);
205                 k = bch2_btree_iter_peek_slot(&iter);
206                 ret = bkey_err(k);
207                 if (ret)
208                         goto err;
209
210                 if (k.k->type != KEY_TYPE_backpointer ||
211                     memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp))) {
212                         ret = -ENOENT;
213                         goto err;
214                 }
215
216                 ret = bch2_btree_delete_at(trans, &iter, 0);
217         }
218 err:
219         bch2_trans_iter_exit(trans, &iter);
220         return ret;
221 }
222
223 int bch2_bucket_backpointer_del(struct btree_trans *trans,
224                                 struct bkey_i_alloc_v4 *a,
225                                 struct bch_backpointer bp,
226                                 struct bkey_s_c orig_k)
227 {
228         struct bch_fs *c = trans->c;
229         struct bch_backpointer *bps = alloc_v4_backpointers(&a->v);
230         unsigned i, nr = BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v);
231         struct btree_iter bp_iter;
232         struct bkey_s_c k;
233         int ret;
234
235         for (i = 0; i < nr; i++) {
236                 int cmp = backpointer_cmp(bps[i], bp) ?:
237                         memcmp(&bps[i], &bp, sizeof(bp));
238                 if (!cmp)
239                         goto found;
240                 if (cmp >= 0)
241                         break;
242         }
243
244         goto btree;
245 found:
246         array_remove_item(bps, nr, i);
247         SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v, nr);
248         set_alloc_v4_u64s(a);
249         return 0;
250 btree:
251         bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
252                              bucket_pos_to_bp(c, a->k.p, bp.bucket_offset),
253                              BTREE_ITER_INTENT|
254                              BTREE_ITER_SLOTS|
255                              BTREE_ITER_WITH_UPDATES);
256         k = bch2_btree_iter_peek_slot(&bp_iter);
257         ret = bkey_err(k);
258         if (ret)
259                 goto err;
260
261         if (k.k->type != KEY_TYPE_backpointer ||
262             memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp))) {
263                 struct printbuf buf = PRINTBUF;
264
265                 prt_printf(&buf, "backpointer not found when deleting");
266                 prt_newline(&buf);
267                 printbuf_indent_add(&buf, 2);
268
269                 prt_printf(&buf, "searching for ");
270                 bch2_backpointer_to_text(&buf, &bp);
271                 prt_newline(&buf);
272
273                 prt_printf(&buf, "got ");
274                 bch2_bkey_val_to_text(&buf, c, k);
275                 prt_newline(&buf);
276
277                 prt_str(&buf, "alloc ");
278                 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&a->k_i));
279                 prt_newline(&buf);
280
281                 prt_printf(&buf, "for ");
282                 bch2_bkey_val_to_text(&buf, c, orig_k);
283
284                 if (!test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags)) {
285                         bch_err(c, "%s", buf.buf);
286                 } else {
287                         ret = -EIO;
288                         bch2_trans_inconsistent(trans, "%s", buf.buf);
289                 }
290                 printbuf_exit(&buf);
291                 goto err;
292         }
293
294         ret = bch2_btree_delete_at(trans, &bp_iter, 0);
295 err:
296         bch2_trans_iter_exit(trans, &bp_iter);
297         return ret;
298 }
299
300 int bch2_bucket_backpointer_add(struct btree_trans *trans,
301                                 struct bkey_i_alloc_v4 *a,
302                                 struct bch_backpointer bp,
303                                 struct bkey_s_c orig_k)
304 {
305         struct bch_fs *c = trans->c;
306         struct bch_dev *ca;
307         struct bch_backpointer *bps = alloc_v4_backpointers(&a->v);
308         unsigned i, nr = BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v);
309         struct bkey_i_backpointer *bp_k;
310         struct btree_iter bp_iter;
311         struct bkey_s_c k;
312         int ret;
313
314         /* Check for duplicates: */
315         for (i = 0; i < nr; i++) {
316                 int cmp = backpointer_cmp(bps[i], bp);
317                 if (cmp >= 0)
318                         break;
319         }
320
321         if ((i &&
322              (bps[i - 1].bucket_offset +
323               bps[i - 1].bucket_len > bp.bucket_offset)) ||
324             (i < nr &&
325              (bp.bucket_offset + bp.bucket_len > bps[i].bucket_offset))) {
326                 struct printbuf buf = PRINTBUF;
327
328                 prt_printf(&buf, "overlapping backpointer found when inserting ");
329                 bch2_backpointer_to_text(&buf, &bp);
330                 prt_newline(&buf);
331                 printbuf_indent_add(&buf, 2);
332
333                 prt_printf(&buf, "into ");
334                 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&a->k_i));
335                 prt_newline(&buf);
336
337                 prt_printf(&buf, "for ");
338                 bch2_bkey_val_to_text(&buf, c, orig_k);
339
340                 if (!test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags))
341                         bch_err(c, "%s", buf.buf);
342                 else {
343                         bch2_trans_inconsistent(trans, "%s", buf.buf);
344                         printbuf_exit(&buf);
345                         return -EIO;
346                 }
347         }
348
349         if (nr < BCH_ALLOC_V4_NR_BACKPOINTERS_MAX) {
350                 array_insert_item(bps, nr, i, bp);
351                 SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v, nr);
352                 set_alloc_v4_u64s(a);
353                 return 0;
354         }
355
356         /* Overflow: use backpointer btree */
357         bp_k = bch2_trans_kmalloc(trans, sizeof(*bp_k));
358         ret = PTR_ERR_OR_ZERO(bp_k);
359         if (ret)
360                 return ret;
361
362         ca = bch_dev_bkey_exists(c, a->k.p.inode);
363
364         bkey_backpointer_init(&bp_k->k_i);
365         bp_k->k.p = bucket_pos_to_bp(c, a->k.p, bp.bucket_offset);
366         bp_k->v = bp;
367
368         bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers, bp_k->k.p,
369                              BTREE_ITER_INTENT|
370                              BTREE_ITER_SLOTS|
371                              BTREE_ITER_WITH_UPDATES);
372         k = bch2_btree_iter_peek_slot(&bp_iter);
373         ret = bkey_err(k);
374         if (ret)
375                 goto err;
376
377         if (k.k->type) {
378                 struct printbuf buf = PRINTBUF;
379
380                 prt_printf(&buf, "existing btree backpointer key found when inserting ");
381                 bch2_backpointer_to_text(&buf, &bp);
382                 prt_newline(&buf);
383                 printbuf_indent_add(&buf, 2);
384
385                 prt_printf(&buf, "found ");
386                 bch2_bkey_val_to_text(&buf, c, k);
387                 prt_newline(&buf);
388
389                 prt_printf(&buf, "for ");
390                 bch2_bkey_val_to_text(&buf, c, orig_k);
391
392                 if (!test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags))
393                         bch_err(c, "%s", buf.buf);
394                 else {
395                         bch2_trans_inconsistent(trans, "%s", buf.buf);
396                         printbuf_exit(&buf);
397                         ret = -EIO;
398                         goto err;
399                 }
400         }
401
402         ret = bch2_trans_update(trans, &bp_iter, &bp_k->k_i, 0);
403 err:
404         bch2_trans_iter_exit(trans, &bp_iter);
405         return ret;
406 }
407
408 /*
409  * Find the next backpointer >= *bp_offset:
410  */
411 int bch2_get_next_backpointer(struct btree_trans *trans,
412                               struct bpos bucket, int gen,
413                               u64 *bp_offset,
414                               struct bch_backpointer *dst)
415 {
416         struct bch_fs *c = trans->c;
417         struct bpos bp_pos, bp_end_pos;
418         struct btree_iter alloc_iter, bp_iter = { NULL };
419         struct bkey_s_c k;
420         struct bkey_s_c_alloc_v4 a;
421         size_t i;
422         int ret;
423
424         if (*bp_offset == U64_MAX)
425                 return 0;
426
427         bp_pos = bucket_pos_to_bp(c, bucket,
428                                   max(*bp_offset, BACKPOINTER_OFFSET_MAX) - BACKPOINTER_OFFSET_MAX);
429         bp_end_pos = bucket_pos_to_bp(c, bpos_nosnap_successor(bucket), 0);
430
431         bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
432                              bucket, BTREE_ITER_CACHED);
433         k = bch2_btree_iter_peek_slot(&alloc_iter);
434         ret = bkey_err(k);
435         if (ret)
436                 goto out;
437
438         if (k.k->type != KEY_TYPE_alloc_v4)
439                 goto done;
440
441         a = bkey_s_c_to_alloc_v4(k);
442         if (gen >= 0 && a.v->gen != gen)
443                 goto done;
444
445         for (i = 0; i < BCH_ALLOC_V4_NR_BACKPOINTERS(a.v); i++) {
446                 if (alloc_v4_backpointers_c(a.v)[i].bucket_offset < *bp_offset)
447                         continue;
448
449                 *dst = alloc_v4_backpointers_c(a.v)[i];
450                 *bp_offset = dst->bucket_offset;
451                 goto out;
452         }
453
454         for_each_btree_key_norestart(trans, bp_iter, BTREE_ID_backpointers,
455                                      bp_pos, 0, k, ret) {
456                 if (bpos_cmp(k.k->p, bp_end_pos) >= 0)
457                         break;
458
459                 if (k.k->type != KEY_TYPE_backpointer)
460                         continue;
461
462                 *dst = *bkey_s_c_to_backpointer(k).v;
463                 *bp_offset = dst->bucket_offset + BACKPOINTER_OFFSET_MAX;
464                 goto out;
465         }
466 done:
467         *bp_offset = U64_MAX;
468 out:
469         bch2_trans_iter_exit(trans, &bp_iter);
470         bch2_trans_iter_exit(trans, &alloc_iter);
471         return ret;
472 }
473
474 static void backpointer_not_found(struct btree_trans *trans,
475                                   struct bpos bucket,
476                                   u64 bp_offset,
477                                   struct bch_backpointer bp,
478                                   struct bkey_s_c k,
479                                   const char *thing_it_points_to)
480 {
481         struct bch_fs *c = trans->c;
482         struct printbuf buf = PRINTBUF;
483
484         prt_printf(&buf, "backpointer doesn't match %s it points to:\n  ",
485                    thing_it_points_to);
486         prt_printf(&buf, "bucket: ");
487         bch2_bpos_to_text(&buf, bucket);
488         prt_printf(&buf, "\n  ");
489
490         if (bp_offset >= BACKPOINTER_OFFSET_MAX) {
491                 struct bpos bp_pos =
492                         bucket_pos_to_bp(c, bucket,
493                                         bp_offset - BACKPOINTER_OFFSET_MAX);
494                 prt_printf(&buf, "backpointer pos: ");
495                 bch2_bpos_to_text(&buf, bp_pos);
496                 prt_printf(&buf, "\n  ");
497         }
498
499         bch2_backpointer_to_text(&buf, &bp);
500         prt_printf(&buf, "\n  ");
501         bch2_bkey_val_to_text(&buf, c, k);
502         if (!test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags))
503                 bch_err_ratelimited(c, "%s", buf.buf);
504         else
505                 bch2_trans_inconsistent(trans, "%s", buf.buf);
506
507         printbuf_exit(&buf);
508 }
509
510 struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
511                                          struct btree_iter *iter,
512                                          struct bpos bucket,
513                                          u64 bp_offset,
514                                          struct bch_backpointer bp)
515 {
516         struct bch_fs *c = trans->c;
517         struct bkey_s_c k;
518
519         bch2_trans_node_iter_init(trans, iter,
520                                   bp.btree_id,
521                                   bp.pos,
522                                   0,
523                                   min(bp.level, c->btree_roots[bp.btree_id].level),
524                                   0);
525         k = bch2_btree_iter_peek_slot(iter);
526         if (bkey_err(k)) {
527                 bch2_trans_iter_exit(trans, iter);
528                 return k;
529         }
530
531         if (bp.level == c->btree_roots[bp.btree_id].level + 1)
532                 k = bkey_i_to_s_c(&c->btree_roots[bp.btree_id].key);
533
534         if (extent_matches_bp(c, bp.btree_id, bp.level, k, bucket, bp))
535                 return k;
536
537         bch2_trans_iter_exit(trans, iter);
538
539         if (bp.level) {
540                 struct btree *b;
541
542                 /*
543                  * If a backpointer for a btree node wasn't found, it may be
544                  * because it was overwritten by a new btree node that hasn't
545                  * been written out yet - backpointer_get_node() checks for
546                  * this:
547                  */
548                 b = bch2_backpointer_get_node(trans, iter, bucket, bp_offset, bp);
549                 if (!IS_ERR_OR_NULL(b))
550                         return bkey_i_to_s_c(&b->key);
551
552                 bch2_trans_iter_exit(trans, iter);
553
554                 if (IS_ERR(b))
555                         return bkey_s_c_err(PTR_ERR(b));
556                 return bkey_s_c_null;
557         }
558
559         backpointer_not_found(trans, bucket, bp_offset, bp, k, "extent");
560         return bkey_s_c_null;
561 }
562
563 struct btree *bch2_backpointer_get_node(struct btree_trans *trans,
564                                         struct btree_iter *iter,
565                                         struct bpos bucket,
566                                         u64 bp_offset,
567                                         struct bch_backpointer bp)
568 {
569         struct bch_fs *c = trans->c;
570         struct btree *b;
571
572         BUG_ON(!bp.level);
573
574         bch2_trans_node_iter_init(trans, iter,
575                                   bp.btree_id,
576                                   bp.pos,
577                                   0,
578                                   bp.level - 1,
579                                   0);
580         b = bch2_btree_iter_peek_node(iter);
581         if (IS_ERR(b))
582                 goto err;
583
584         if (extent_matches_bp(c, bp.btree_id, bp.level,
585                               bkey_i_to_s_c(&b->key),
586                               bucket, bp))
587                 return b;
588
589         if (btree_node_will_make_reachable(b)) {
590                 b = ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node);
591         } else {
592                 backpointer_not_found(trans, bucket, bp_offset, bp,
593                                       bkey_i_to_s_c(&b->key), "btree node");
594                 b = NULL;
595         }
596 err:
597         bch2_trans_iter_exit(trans, iter);
598         return b;
599 }
600
601 static int bch2_check_btree_backpointer(struct btree_trans *trans, struct btree_iter *bp_iter,
602                                         struct bkey_s_c k)
603 {
604         struct bch_fs *c = trans->c;
605         struct btree_iter alloc_iter = { NULL };
606         struct bch_dev *ca;
607         struct bkey_s_c alloc_k;
608         struct printbuf buf = PRINTBUF;
609         int ret = 0;
610
611         if (fsck_err_on(!bch2_dev_exists2(c, k.k->p.inode), c,
612                         "backpointer for mising device:\n%s",
613                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
614                 ret = bch2_btree_delete_at(trans, bp_iter, 0);
615                 goto out;
616         }
617
618         ca = bch_dev_bkey_exists(c, k.k->p.inode);
619
620         bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
621                              bp_pos_to_bucket(c, k.k->p), 0);
622
623         alloc_k = bch2_btree_iter_peek_slot(&alloc_iter);
624         ret = bkey_err(alloc_k);
625         if (ret)
626                 goto out;
627
628         if (fsck_err_on(alloc_k.k->type != KEY_TYPE_alloc_v4, c,
629                         "backpointer for nonexistent alloc key: %llu:%llu:0\n%s",
630                         alloc_iter.pos.inode, alloc_iter.pos.offset,
631                         (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) {
632                 ret = bch2_btree_delete_at(trans, bp_iter, 0);
633                 goto out;
634         }
635 out:
636 fsck_err:
637         bch2_trans_iter_exit(trans, &alloc_iter);
638         printbuf_exit(&buf);
639         return ret;
640 }
641
642 /* verify that every backpointer has a corresponding alloc key */
643 int bch2_check_btree_backpointers(struct bch_fs *c)
644 {
645         struct btree_iter iter;
646         struct bkey_s_c k;
647
648         return bch2_trans_run(c,
649                 for_each_btree_key_commit(&trans, iter,
650                         BTREE_ID_backpointers, POS_MIN, 0, k,
651                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
652                   bch2_check_btree_backpointer(&trans, &iter, k)));
653 }
654
655 static int check_bp_exists(struct btree_trans *trans,
656                            struct bpos bucket_pos,
657                            struct bch_backpointer bp,
658                            struct bkey_s_c orig_k)
659 {
660         struct bch_fs *c = trans->c;
661         struct btree_iter alloc_iter, bp_iter = { NULL };
662         struct printbuf buf = PRINTBUF;
663         struct bkey_s_c alloc_k, bp_k;
664         int ret;
665
666         bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc, bucket_pos, 0);
667         alloc_k = bch2_btree_iter_peek_slot(&alloc_iter);
668         ret = bkey_err(alloc_k);
669         if (ret)
670                 goto err;
671
672         if (alloc_k.k->type == KEY_TYPE_alloc_v4) {
673                 struct bkey_s_c_alloc_v4 a = bkey_s_c_to_alloc_v4(alloc_k);
674                 const struct bch_backpointer *bps = alloc_v4_backpointers_c(a.v);
675                 unsigned i, nr = BCH_ALLOC_V4_NR_BACKPOINTERS(a.v);
676
677                 for (i = 0; i < nr; i++) {
678                         int cmp = backpointer_cmp(bps[i], bp) ?:
679                                 memcmp(&bps[i], &bp, sizeof(bp));
680                         if (!cmp)
681                                 goto out;
682                         if (cmp >= 0)
683                                 break;
684                 }
685         } else {
686                 goto missing;
687         }
688
689         bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
690                              bucket_pos_to_bp(c, bucket_pos, bp.bucket_offset),
691                              0);
692         bp_k = bch2_btree_iter_peek_slot(&bp_iter);
693         ret = bkey_err(bp_k);
694         if (ret)
695                 goto err;
696
697         if (bp_k.k->type != KEY_TYPE_backpointer ||
698             memcmp(bkey_s_c_to_backpointer(bp_k).v, &bp, sizeof(bp)))
699                 goto missing;
700 out:
701 err:
702 fsck_err:
703         bch2_trans_iter_exit(trans, &bp_iter);
704         bch2_trans_iter_exit(trans, &alloc_iter);
705         printbuf_exit(&buf);
706         return ret;
707 missing:
708         prt_printf(&buf, "missing backpointer for btree=%s l=%u ",
709                bch2_btree_ids[bp.btree_id], bp.level);
710         bch2_bkey_val_to_text(&buf, c, orig_k);
711         prt_printf(&buf, "\nin alloc key ");
712         bch2_bkey_val_to_text(&buf, c, alloc_k);
713
714         if (c->sb.version < bcachefs_metadata_version_backpointers ||
715             c->opts.reconstruct_alloc ||
716             fsck_err(c, "%s", buf.buf)) {
717                 struct bkey_i_alloc_v4 *a = bch2_alloc_to_v4_mut(trans, alloc_k);
718
719                 ret   = PTR_ERR_OR_ZERO(a) ?:
720                         bch2_bucket_backpointer_add(trans, a, bp, orig_k) ?:
721                         bch2_trans_update(trans, &alloc_iter, &a->k_i, 0);
722         }
723
724         goto out;
725 }
726
727 static int check_extent_to_backpointers(struct btree_trans *trans,
728                                         struct btree_iter *iter)
729 {
730         struct bch_fs *c = trans->c;
731         struct bkey_ptrs_c ptrs;
732         const union bch_extent_entry *entry;
733         struct extent_ptr_decoded p;
734         struct bkey_s_c k;
735         int ret;
736
737         k = bch2_btree_iter_peek_all_levels(iter);
738         ret = bkey_err(k);
739         if (ret)
740                 return ret;
741         if (!k.k)
742                 return 0;
743
744         ptrs = bch2_bkey_ptrs_c(k);
745         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
746                 struct bpos bucket_pos;
747                 struct bch_backpointer bp;
748
749                 if (p.ptr.cached)
750                         continue;
751
752                 bch2_extent_ptr_to_bp(c, iter->btree_id, iter->path->level,
753                                       k, p, &bucket_pos, &bp);
754
755                 ret = check_bp_exists(trans, bucket_pos, bp, k);
756                 if (ret)
757                         return ret;
758         }
759
760         return 0;
761 }
762
763 static int check_btree_root_to_backpointers(struct btree_trans *trans,
764                                             enum btree_id btree_id)
765 {
766         struct bch_fs *c = trans->c;
767         struct btree_iter iter;
768         struct btree *b;
769         struct bkey_s_c k;
770         struct bkey_ptrs_c ptrs;
771         struct extent_ptr_decoded p;
772         const union bch_extent_entry *entry;
773         int ret;
774
775         bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0,
776                                   c->btree_roots[btree_id].level, 0);
777         b = bch2_btree_iter_peek_node(&iter);
778         ret = PTR_ERR_OR_ZERO(b);
779         if (ret)
780                 goto err;
781
782         BUG_ON(b != btree_node_root(c, b));
783
784         k = bkey_i_to_s_c(&b->key);
785         ptrs = bch2_bkey_ptrs_c(k);
786         bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
787                 struct bpos bucket_pos;
788                 struct bch_backpointer bp;
789
790                 if (p.ptr.cached)
791                         continue;
792
793                 bch2_extent_ptr_to_bp(c, iter.btree_id, iter.path->level + 1,
794                                       k, p, &bucket_pos, &bp);
795
796                 ret = check_bp_exists(trans, bucket_pos, bp, k);
797                 if (ret)
798                         goto err;
799         }
800 err:
801         bch2_trans_iter_exit(trans, &iter);
802         return ret;
803 }
804
805 int bch2_check_extents_to_backpointers(struct bch_fs *c)
806 {
807         struct btree_trans trans;
808         struct btree_iter iter;
809         enum btree_id btree_id;
810         int ret = 0;
811
812         bch2_trans_init(&trans, c, 0, 0);
813         for (btree_id = 0; btree_id < BTREE_ID_NR; btree_id++) {
814                 unsigned depth = btree_type_has_ptrs(btree_id) ? 0 : 1;
815
816                 bch2_trans_node_iter_init(&trans, &iter, btree_id, POS_MIN, 0,
817                                           depth,
818                                           BTREE_ITER_ALL_LEVELS|
819                                           BTREE_ITER_PREFETCH);
820
821                 do {
822                         ret = commit_do(&trans, NULL, NULL,
823                                               BTREE_INSERT_LAZY_RW|
824                                               BTREE_INSERT_NOFAIL,
825                                               check_extent_to_backpointers(&trans, &iter));
826                         if (ret)
827                                 break;
828                 } while (!bch2_btree_iter_advance(&iter));
829
830                 bch2_trans_iter_exit(&trans, &iter);
831
832                 if (ret)
833                         break;
834
835                 ret = commit_do(&trans, NULL, NULL,
836                                       BTREE_INSERT_LAZY_RW|
837                                       BTREE_INSERT_NOFAIL,
838                                       check_btree_root_to_backpointers(&trans, btree_id));
839                 if (ret)
840                         break;
841         }
842         bch2_trans_exit(&trans);
843         return ret;
844 }
845
846 static int check_one_backpointer(struct btree_trans *trans,
847                                  struct bpos bucket,
848                                  u64 *bp_offset)
849 {
850         struct btree_iter iter;
851         struct bch_backpointer bp;
852         struct bkey_s_c k;
853         struct printbuf buf = PRINTBUF;
854         int ret;
855
856         ret = bch2_get_next_backpointer(trans, bucket, -1,
857                                         bp_offset, &bp);
858         if (ret || *bp_offset == U64_MAX)
859                 return ret;
860
861         k = bch2_backpointer_get_key(trans, &iter, bucket, *bp_offset, bp);
862         ret = bkey_err(k);
863         if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
864                 return 0;
865         if (ret)
866                 return ret;
867
868         if (fsck_err_on(!k.k, trans->c,
869                         "%s backpointer points to missing extent\n%s",
870                         *bp_offset < BACKPOINTER_OFFSET_MAX ? "alloc" : "btree",
871                         (bch2_backpointer_to_text(&buf, &bp), buf.buf))) {
872                 ret = bch2_backpointer_del_by_offset(trans, bucket, *bp_offset, bp);
873                 if (ret == -ENOENT)
874                         bch_err(trans->c, "backpointer at %llu not found", *bp_offset);
875         }
876
877         bch2_trans_iter_exit(trans, &iter);
878 fsck_err:
879         printbuf_exit(&buf);
880         return ret;
881 }
882
883 int bch2_check_backpointers_to_extents(struct bch_fs *c)
884 {
885         struct btree_trans trans;
886         struct btree_iter iter;
887         struct bkey_s_c k;
888         int ret = 0;
889
890         bch2_trans_init(&trans, c, 0, 0);
891         for_each_btree_key(&trans, iter, BTREE_ID_alloc, POS_MIN,
892                            BTREE_ITER_PREFETCH, k, ret) {
893                 u64 bp_offset = 0;
894
895                 while (!(ret = commit_do(&trans, NULL, NULL,
896                                                BTREE_INSERT_LAZY_RW|
897                                                BTREE_INSERT_NOFAIL,
898                                 check_one_backpointer(&trans, iter.pos, &bp_offset))) &&
899                        bp_offset < U64_MAX)
900                         bp_offset++;
901
902                 if (ret)
903                         break;
904         }
905         bch2_trans_iter_exit(&trans, &iter);
906         bch2_trans_exit(&trans);
907         return ret < 0 ? ret : 0;
908 }