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