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