git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/fsck.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "bkey_buf.h"
   5 #include "btree_cache.h"
   6 #include "btree_update.h"
   7 #include "buckets.h"
   8 #include "dirent.h"
   9 #include "error.h"
  10 #include "fs-common.h"
  11 #include "fsck.h"
  12 #include "inode.h"
  13 #include "keylist.h"
  14 #include "recovery.h"
  15 #include "snapshot.h"
  16 #include "super.h"
  17 #include "xattr.h"
  18
  19 #include <linux/bsearch.h>
  20 #include <linux/darray.h>
  21 #include <linux/dcache.h> /* struct qstr */
  22
  23 /*
  24  * XXX: this is handling transaction restarts without returning
  25  * -BCH_ERR_transaction_restart_nested, this is not how we do things anymore:
  26  */
  27 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum,
  28                                     u32 snapshot)
  29 {
  30         u64 sectors = 0;
  31
  32         int ret = for_each_btree_key_upto(trans, iter, BTREE_ID_extents,
  33                                 SPOS(inum, 0, snapshot),
  34                                 POS(inum, U64_MAX),
  35                                 0, k, ({
  36                 if (bkey_extent_is_allocation(k.k))
  37                         sectors += k.k->size;
  38                 0;
  39         }));
  40
  41         return ret ?: sectors;
  42 }
  43
  44 static s64 bch2_count_subdirs(struct btree_trans *trans, u64 inum,
  45                                     u32 snapshot)
  46 {
  47         u64 subdirs = 0;
  48
  49         int ret = for_each_btree_key_upto(trans, iter, BTREE_ID_dirents,
  50                                     SPOS(inum, 0, snapshot),
  51                                     POS(inum, U64_MAX),
  52                                     0, k, ({
  53                 if (k.k->type == KEY_TYPE_dirent &&
  54                     bkey_s_c_to_dirent(k).v->d_type == DT_DIR)
  55                         subdirs++;
  56                 0;
  57         }));
  58
  59         return ret ?: subdirs;
  60 }
  61
  62 static int subvol_lookup(struct btree_trans *trans, u32 subvol,
  63                          u32 *snapshot, u64 *inum)
  64 {
  65         struct bch_subvolume s;
  66         int ret;
  67
  68         ret = bch2_subvolume_get(trans, subvol, false, 0, &s);
  69
  70         *snapshot = le32_to_cpu(s.snapshot);
  71         *inum = le64_to_cpu(s.inode);
  72         return ret;
  73 }
  74
  75 static int lookup_first_inode(struct btree_trans *trans, u64 inode_nr,
  76                               struct bch_inode_unpacked *inode)
  77 {
  78         struct btree_iter iter;
  79         struct bkey_s_c k;
  80         int ret;
  81
  82         bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
  83                              POS(0, inode_nr),
  84                              BTREE_ITER_ALL_SNAPSHOTS);
  85         k = bch2_btree_iter_peek(&iter);
  86         ret = bkey_err(k);
  87         if (ret)
  88                 goto err;
  89
  90         if (!k.k || !bkey_eq(k.k->p, POS(0, inode_nr))) {
  91                 ret = -BCH_ERR_ENOENT_inode;
  92                 goto err;
  93         }
  94
  95         ret = bch2_inode_unpack(k, inode);
  96 err:
  97         bch_err_msg(trans->c, ret, "fetching inode %llu", inode_nr);
  98         bch2_trans_iter_exit(trans, &iter);
  99         return ret;
 100 }
 101
 102 static int lookup_inode(struct btree_trans *trans, u64 inode_nr,
 103                         struct bch_inode_unpacked *inode,
 104                         u32 *snapshot)
 105 {
 106         struct btree_iter iter;
 107         struct bkey_s_c k;
 108         int ret;
 109
 110         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
 111                                SPOS(0, inode_nr, *snapshot), 0);
 112         ret = bkey_err(k);
 113         if (ret)
 114                 goto err;
 115
 116         ret = bkey_is_inode(k.k)
 117                 ? bch2_inode_unpack(k, inode)
 118                 : -BCH_ERR_ENOENT_inode;
 119         if (!ret)
 120                 *snapshot = iter.pos.snapshot;
 121 err:
 122         bch2_trans_iter_exit(trans, &iter);
 123         return ret;
 124 }
 125
 126 static int lookup_dirent_in_snapshot(struct btree_trans *trans,
 127                            struct bch_hash_info hash_info,
 128                            subvol_inum dir, struct qstr *name,
 129                            u64 *target, unsigned *type, u32 snapshot)
 130 {
 131         struct btree_iter iter;
 132         struct bkey_s_c_dirent d;
 133         int ret = bch2_hash_lookup_in_snapshot(trans, &iter, bch2_dirent_hash_desc,
 134                                &hash_info, dir, name, 0, snapshot);
 135         if (ret)
 136                 return ret;
 137
 138         d = bkey_s_c_to_dirent(bch2_btree_iter_peek_slot(&iter));
 139         *target = le64_to_cpu(d.v->d_inum);
 140         *type = d.v->d_type;
 141         bch2_trans_iter_exit(trans, &iter);
 142         return 0;
 143 }
 144
 145 static int __remove_dirent(struct btree_trans *trans, struct bpos pos)
 146 {
 147         struct bch_fs *c = trans->c;
 148         struct btree_iter iter;
 149         struct bch_inode_unpacked dir_inode;
 150         struct bch_hash_info dir_hash_info;
 151         int ret;
 152
 153         ret = lookup_first_inode(trans, pos.inode, &dir_inode);
 154         if (ret)
 155                 goto err;
 156
 157         dir_hash_info = bch2_hash_info_init(c, &dir_inode);
 158
 159         bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, pos, BTREE_ITER_INTENT);
 160
 161         ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc,
 162                                   &dir_hash_info, &iter,
 163                                   BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
 164         bch2_trans_iter_exit(trans, &iter);
 165 err:
 166         bch_err_fn(c, ret);
 167         return ret;
 168 }
 169
 170 /* Get lost+found, create if it doesn't exist: */
 171 static int lookup_lostfound(struct btree_trans *trans, u32 snapshot,
 172                             struct bch_inode_unpacked *lostfound)
 173 {
 174         struct bch_fs *c = trans->c;
 175         struct qstr lostfound_str = QSTR("lost+found");
 176         u64 inum = 0;
 177         unsigned d_type = 0;
 178         int ret;
 179
 180         struct bch_snapshot_tree st;
 181         ret = bch2_snapshot_tree_lookup(trans,
 182                         bch2_snapshot_tree(c, snapshot), &st);
 183         if (ret)
 184                 return ret;
 185
 186         subvol_inum root_inum = { .subvol = le32_to_cpu(st.master_subvol) };
 187         u32 subvol_snapshot;
 188
 189         ret = subvol_lookup(trans, le32_to_cpu(st.master_subvol),
 190                             &subvol_snapshot, &root_inum.inum);
 191         bch_err_msg(c, ret, "looking up root subvol");
 192         if (ret)
 193                 return ret;
 194
 195         struct bch_inode_unpacked root_inode;
 196         struct bch_hash_info root_hash_info;
 197         u32 root_inode_snapshot = snapshot;
 198         ret = lookup_inode(trans, root_inum.inum, &root_inode, &root_inode_snapshot);
 199         bch_err_msg(c, ret, "looking up root inode");
 200         if (ret)
 201                 return ret;
 202
 203         root_hash_info = bch2_hash_info_init(c, &root_inode);
 204
 205         ret = lookup_dirent_in_snapshot(trans, root_hash_info, root_inum,
 206                               &lostfound_str, &inum, &d_type, snapshot);
 207         if (bch2_err_matches(ret, ENOENT))
 208                 goto create_lostfound;
 209
 210         bch_err_fn(c, ret);
 211         if (ret)
 212                 return ret;
 213
 214         if (d_type != DT_DIR) {
 215                 bch_err(c, "error looking up lost+found: not a directory");
 216                 return -BCH_ERR_ENOENT_not_directory;
 217         }
 218
 219         /*
 220          * The bch2_check_dirents pass has already run, dangling dirents
 221          * shouldn't exist here:
 222          */
 223         ret = lookup_inode(trans, inum, lostfound, &snapshot);
 224         bch_err_msg(c, ret, "looking up lost+found %llu:%u in (root inode %llu, snapshot root %u)",
 225                     inum, snapshot, root_inum.inum, bch2_snapshot_root(c, snapshot));
 226         return ret;
 227
 228 create_lostfound:
 229         /*
 230          * XXX: we could have a nicer log message here  if we had a nice way to
 231          * walk backpointers to print a path
 232          */
 233         bch_notice(c, "creating lost+found in snapshot %u", le32_to_cpu(st.root_snapshot));
 234
 235         u64 now = bch2_current_time(c);
 236         struct btree_iter lostfound_iter = { NULL };
 237         u64 cpu = raw_smp_processor_id();
 238
 239         bch2_inode_init_early(c, lostfound);
 240         bch2_inode_init_late(lostfound, now, 0, 0, S_IFDIR|0700, 0, &root_inode);
 241         lostfound->bi_dir = root_inode.bi_inum;
 242
 243         root_inode.bi_nlink++;
 244
 245         ret = bch2_inode_create(trans, &lostfound_iter, lostfound, snapshot, cpu);
 246         if (ret)
 247                 goto err;
 248
 249         bch2_btree_iter_set_snapshot(&lostfound_iter, snapshot);
 250         ret = bch2_btree_iter_traverse(&lostfound_iter);
 251         if (ret)
 252                 goto err;
 253
 254         ret =   bch2_dirent_create_snapshot(trans,
 255                                 0, root_inode.bi_inum, snapshot, &root_hash_info,
 256                                 mode_to_type(lostfound->bi_mode),
 257                                 &lostfound_str,
 258                                 lostfound->bi_inum,
 259                                 &lostfound->bi_dir_offset,
 260                                 BCH_HASH_SET_MUST_CREATE) ?:
 261                 bch2_inode_write_flags(trans, &lostfound_iter, lostfound,
 262                                        BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
 263 err:
 264         bch_err_msg(c, ret, "creating lost+found");
 265         bch2_trans_iter_exit(trans, &lostfound_iter);
 266         return ret;
 267 }
 268
 269 static int reattach_inode(struct btree_trans *trans,
 270                           struct bch_inode_unpacked *inode,
 271                           u32 inode_snapshot)
 272 {
 273         struct bch_hash_info dir_hash;
 274         struct bch_inode_unpacked lostfound;
 275         char name_buf[20];
 276         struct qstr name;
 277         u64 dir_offset = 0;
 278         u32 dirent_snapshot = inode_snapshot;
 279         int ret;
 280
 281         if (inode->bi_subvol) {
 282                 inode->bi_parent_subvol = BCACHEFS_ROOT_SUBVOL;
 283
 284                 u64 root_inum;
 285                 ret = subvol_lookup(trans, inode->bi_parent_subvol,
 286                                     &dirent_snapshot, &root_inum);
 287                 if (ret)
 288                         return ret;
 289
 290                 snprintf(name_buf, sizeof(name_buf), "subvol-%u", inode->bi_subvol);
 291         } else {
 292                 snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum);
 293         }
 294
 295         ret = lookup_lostfound(trans, dirent_snapshot, &lostfound);
 296         if (ret)
 297                 return ret;
 298
 299         if (S_ISDIR(inode->bi_mode)) {
 300                 lostfound.bi_nlink++;
 301
 302                 ret = __bch2_fsck_write_inode(trans, &lostfound, U32_MAX);
 303                 if (ret)
 304                         return ret;
 305         }
 306
 307         dir_hash = bch2_hash_info_init(trans->c, &lostfound);
 308
 309         name = (struct qstr) QSTR(name_buf);
 310
 311         ret = bch2_dirent_create_snapshot(trans,
 312                                 inode->bi_parent_subvol, lostfound.bi_inum,
 313                                 dirent_snapshot,
 314                                 &dir_hash,
 315                                 inode_d_type(inode),
 316                                 &name,
 317                                 inode->bi_subvol ?: inode->bi_inum,
 318                                 &dir_offset,
 319                                 BCH_HASH_SET_MUST_CREATE);
 320         if (ret)
 321                 return ret;
 322
 323         inode->bi_dir           = lostfound.bi_inum;
 324         inode->bi_dir_offset    = dir_offset;
 325
 326         return __bch2_fsck_write_inode(trans, inode, inode_snapshot);
 327 }
 328
 329 static int remove_backpointer(struct btree_trans *trans,
 330                               struct bch_inode_unpacked *inode)
 331 {
 332         struct btree_iter iter;
 333         struct bkey_s_c_dirent d;
 334         int ret;
 335
 336         d = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_dirents,
 337                                      POS(inode->bi_dir, inode->bi_dir_offset), 0,
 338                                      dirent);
 339         ret =   bkey_err(d) ?:
 340                 __remove_dirent(trans, d.k->p);
 341         bch2_trans_iter_exit(trans, &iter);
 342         return ret;
 343 }
 344
 345 static int reattach_subvol(struct btree_trans *trans, struct bkey_s_c_subvolume s)
 346 {
 347         struct bch_fs *c = trans->c;
 348
 349         struct bch_inode_unpacked inode;
 350         int ret = bch2_inode_find_by_inum_trans(trans,
 351                                 (subvol_inum) { s.k->p.offset, le64_to_cpu(s.v->inode) },
 352                                 &inode);
 353         if (ret)
 354                 return ret;
 355
 356         ret = remove_backpointer(trans, &inode);
 357         bch_err_msg(c, ret, "removing dirent");
 358         if (ret)
 359                 return ret;
 360
 361         ret = reattach_inode(trans, &inode, le32_to_cpu(s.v->snapshot));
 362         bch_err_msg(c, ret, "reattaching inode %llu", inode.bi_inum);
 363         return ret;
 364 }
 365
 366 struct snapshots_seen_entry {
 367         u32                             id;
 368         u32                             equiv;
 369 };
 370
 371 struct snapshots_seen {
 372         struct bpos                     pos;
 373         DARRAY(struct snapshots_seen_entry) ids;
 374 };
 375
 376 static inline void snapshots_seen_exit(struct snapshots_seen *s)
 377 {
 378         darray_exit(&s->ids);
 379 }
 380
 381 static inline void snapshots_seen_init(struct snapshots_seen *s)
 382 {
 383         memset(s, 0, sizeof(*s));
 384 }
 385
 386 static int snapshots_seen_add_inorder(struct bch_fs *c, struct snapshots_seen *s, u32 id)
 387 {
 388         struct snapshots_seen_entry *i, n = {
 389                 .id     = id,
 390                 .equiv  = bch2_snapshot_equiv(c, id),
 391         };
 392         int ret = 0;
 393
 394         __darray_for_each(s->ids, i) {
 395                 if (i->id == id)
 396                         return 0;
 397                 if (i->id > id)
 398                         break;
 399         }
 400
 401         ret = darray_insert_item(&s->ids, i - s->ids.data, n);
 402         if (ret)
 403                 bch_err(c, "error reallocating snapshots_seen table (size %zu)",
 404                         s->ids.size);
 405         return ret;
 406 }
 407
 408 static int snapshots_seen_update(struct bch_fs *c, struct snapshots_seen *s,
 409                                  enum btree_id btree_id, struct bpos pos)
 410 {
 411         struct snapshots_seen_entry n = {
 412                 .id     = pos.snapshot,
 413                 .equiv  = bch2_snapshot_equiv(c, pos.snapshot),
 414         };
 415         int ret = 0;
 416
 417         if (!bkey_eq(s->pos, pos))
 418                 s->ids.nr = 0;
 419
 420         s->pos = pos;
 421         s->pos.snapshot = n.equiv;
 422
 423         darray_for_each(s->ids, i) {
 424                 if (i->id == n.id)
 425                         return 0;
 426
 427                 /*
 428                  * We currently don't rigorously track for snapshot cleanup
 429                  * needing to be run, so it shouldn't be a fsck error yet:
 430                  */
 431                 if (i->equiv == n.equiv) {
 432                         bch_err(c, "snapshot deletion did not finish:\n"
 433                                 "  duplicate keys in btree %s at %llu:%llu snapshots %u, %u (equiv %u)\n",
 434                                 bch2_btree_id_str(btree_id),
 435                                 pos.inode, pos.offset,
 436                                 i->id, n.id, n.equiv);
 437                         set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
 438                         return bch2_run_explicit_recovery_pass(c, BCH_RECOVERY_PASS_delete_dead_snapshots);
 439                 }
 440         }
 441
 442         ret = darray_push(&s->ids, n);
 443         if (ret)
 444                 bch_err(c, "error reallocating snapshots_seen table (size %zu)",
 445                         s->ids.size);
 446         return ret;
 447 }
 448
 449 /**
 450  * key_visible_in_snapshot - returns true if @id is a descendent of @ancestor,
 451  * and @ancestor hasn't been overwritten in @seen
 452  *
 453  * @c:          filesystem handle
 454  * @seen:       list of snapshot ids already seen at current position
 455  * @id:         descendent snapshot id
 456  * @ancestor:   ancestor snapshot id
 457  *
 458  * Returns:     whether key in @ancestor snapshot is visible in @id snapshot
 459  */
 460 static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *seen,
 461                                     u32 id, u32 ancestor)
 462 {
 463         ssize_t i;
 464
 465         EBUG_ON(id > ancestor);
 466         EBUG_ON(!bch2_snapshot_is_equiv(c, id));
 467         EBUG_ON(!bch2_snapshot_is_equiv(c, ancestor));
 468
 469         /* @ancestor should be the snapshot most recently added to @seen */
 470         EBUG_ON(ancestor != seen->pos.snapshot);
 471         EBUG_ON(ancestor != seen->ids.data[seen->ids.nr - 1].equiv);
 472
 473         if (id == ancestor)
 474                 return true;
 475
 476         if (!bch2_snapshot_is_ancestor(c, id, ancestor))
 477                 return false;
 478
 479         /*
 480          * We know that @id is a descendant of @ancestor, we're checking if
 481          * we've seen a key that overwrote @ancestor - i.e. also a descendent of
 482          * @ascestor and with @id as a descendent.
 483          *
 484          * But we already know that we're scanning IDs between @id and @ancestor
 485          * numerically, since snapshot ID lists are kept sorted, so if we find
 486          * an id that's an ancestor of @id we're done:
 487          */
 488
 489         for (i = seen->ids.nr - 2;
 490              i >= 0 && seen->ids.data[i].equiv >= id;
 491              --i)
 492                 if (bch2_snapshot_is_ancestor(c, id, seen->ids.data[i].equiv))
 493                         return false;
 494
 495         return true;
 496 }
 497
 498 /**
 499  * ref_visible - given a key with snapshot id @src that points to a key with
 500  * snapshot id @dst, test whether there is some snapshot in which @dst is
 501  * visible.
 502  *
 503  * @c:          filesystem handle
 504  * @s:          list of snapshot IDs already seen at @src
 505  * @src:        snapshot ID of src key
 506  * @dst:        snapshot ID of dst key
 507  * Returns:     true if there is some snapshot in which @dst is visible
 508  *
 509  * Assumes we're visiting @src keys in natural key order
 510  */
 511 static bool ref_visible(struct bch_fs *c, struct snapshots_seen *s,
 512                         u32 src, u32 dst)
 513 {
 514         return dst <= src
 515                 ? key_visible_in_snapshot(c, s, dst, src)
 516                 : bch2_snapshot_is_ancestor(c, src, dst);
 517 }
 518
 519 static int ref_visible2(struct bch_fs *c,
 520                         u32 src, struct snapshots_seen *src_seen,
 521                         u32 dst, struct snapshots_seen *dst_seen)
 522 {
 523         src = bch2_snapshot_equiv(c, src);
 524         dst = bch2_snapshot_equiv(c, dst);
 525
 526         if (dst > src) {
 527                 swap(dst, src);
 528                 swap(dst_seen, src_seen);
 529         }
 530         return key_visible_in_snapshot(c, src_seen, dst, src);
 531 }
 532
 533 #define for_each_visible_inode(_c, _s, _w, _snapshot, _i)                               \
 534         for (_i = (_w)->inodes.data; _i < (_w)->inodes.data + (_w)->inodes.nr &&        \
 535              (_i)->snapshot <= (_snapshot); _i++)                                       \
 536                 if (key_visible_in_snapshot(_c, _s, _i->snapshot, _snapshot))
 537
 538 struct inode_walker_entry {
 539         struct bch_inode_unpacked inode;
 540         u32                     snapshot;
 541         bool                    seen_this_pos;
 542         u64                     count;
 543 };
 544
 545 struct inode_walker {
 546         bool                            first_this_inode;
 547         bool                            recalculate_sums;
 548         struct bpos                     last_pos;
 549
 550         DARRAY(struct inode_walker_entry) inodes;
 551 };
 552
 553 static void inode_walker_exit(struct inode_walker *w)
 554 {
 555         darray_exit(&w->inodes);
 556 }
 557
 558 static struct inode_walker inode_walker_init(void)
 559 {
 560         return (struct inode_walker) { 0, };
 561 }
 562
 563 static int add_inode(struct bch_fs *c, struct inode_walker *w,
 564                      struct bkey_s_c inode)
 565 {
 566         struct bch_inode_unpacked u;
 567
 568         BUG_ON(bch2_inode_unpack(inode, &u));
 569
 570         return darray_push(&w->inodes, ((struct inode_walker_entry) {
 571                 .inode          = u,
 572                 .snapshot       = bch2_snapshot_equiv(c, inode.k->p.snapshot),
 573         }));
 574 }
 575
 576 static int get_inodes_all_snapshots(struct btree_trans *trans,
 577                                     struct inode_walker *w, u64 inum)
 578 {
 579         struct bch_fs *c = trans->c;
 580         struct btree_iter iter;
 581         struct bkey_s_c k;
 582         int ret;
 583
 584         w->recalculate_sums = false;
 585         w->inodes.nr = 0;
 586
 587         for_each_btree_key_norestart(trans, iter, BTREE_ID_inodes, POS(0, inum),
 588                                      BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
 589                 if (k.k->p.offset != inum)
 590                         break;
 591
 592                 if (bkey_is_inode(k.k))
 593                         add_inode(c, w, k);
 594         }
 595         bch2_trans_iter_exit(trans, &iter);
 596
 597         if (ret)
 598                 return ret;
 599
 600         w->first_this_inode = true;
 601         return 0;
 602 }
 603
 604 static struct inode_walker_entry *
 605 lookup_inode_for_snapshot(struct bch_fs *c, struct inode_walker *w, struct bkey_s_c k)
 606 {
 607         bool is_whiteout = k.k->type == KEY_TYPE_whiteout;
 608         u32 snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot);
 609
 610         struct inode_walker_entry *i;
 611         __darray_for_each(w->inodes, i)
 612                 if (bch2_snapshot_is_ancestor(c, snapshot, i->snapshot))
 613                         goto found;
 614
 615         return NULL;
 616 found:
 617         BUG_ON(snapshot > i->snapshot);
 618
 619         if (snapshot != i->snapshot && !is_whiteout) {
 620                 struct inode_walker_entry new = *i;
 621
 622                 new.snapshot = snapshot;
 623                 new.count = 0;
 624
 625                 struct printbuf buf = PRINTBUF;
 626                 bch2_bkey_val_to_text(&buf, c, k);
 627
 628                 bch_info(c, "have key for inode %llu:%u but have inode in ancestor snapshot %u\n"
 629                          "unexpected because we should always update the inode when we update a key in that inode\n"
 630                          "%s",
 631                          w->last_pos.inode, snapshot, i->snapshot, buf.buf);
 632                 printbuf_exit(&buf);
 633
 634                 while (i > w->inodes.data && i[-1].snapshot > snapshot)
 635                         --i;
 636
 637                 size_t pos = i - w->inodes.data;
 638                 int ret = darray_insert_item(&w->inodes, pos, new);
 639                 if (ret)
 640                         return ERR_PTR(ret);
 641
 642                 i = w->inodes.data + pos;
 643         }
 644
 645         return i;
 646 }
 647
 648 static struct inode_walker_entry *walk_inode(struct btree_trans *trans,
 649                                              struct inode_walker *w,
 650                                              struct bkey_s_c k)
 651 {
 652         if (w->last_pos.inode != k.k->p.inode) {
 653                 int ret = get_inodes_all_snapshots(trans, w, k.k->p.inode);
 654                 if (ret)
 655                         return ERR_PTR(ret);
 656         } else if (bkey_cmp(w->last_pos, k.k->p)) {
 657                 darray_for_each(w->inodes, i)
 658                         i->seen_this_pos = false;
 659         }
 660
 661         w->last_pos = k.k->p;
 662
 663         return lookup_inode_for_snapshot(trans->c, w, k);
 664 }
 665
 666 static int __get_visible_inodes(struct btree_trans *trans,
 667                                 struct inode_walker *w,
 668                                 struct snapshots_seen *s,
 669                                 u64 inum)
 670 {
 671         struct bch_fs *c = trans->c;
 672         struct btree_iter iter;
 673         struct bkey_s_c k;
 674         int ret;
 675
 676         w->inodes.nr = 0;
 677
 678         for_each_btree_key_norestart(trans, iter, BTREE_ID_inodes, POS(0, inum),
 679                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
 680                 u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot);
 681
 682                 if (k.k->p.offset != inum)
 683                         break;
 684
 685                 if (!ref_visible(c, s, s->pos.snapshot, equiv))
 686                         continue;
 687
 688                 if (bkey_is_inode(k.k))
 689                         add_inode(c, w, k);
 690
 691                 if (equiv >= s->pos.snapshot)
 692                         break;
 693         }
 694         bch2_trans_iter_exit(trans, &iter);
 695
 696         return ret;
 697 }
 698
 699 static int check_key_has_snapshot(struct btree_trans *trans,
 700                                   struct btree_iter *iter,
 701                                   struct bkey_s_c k)
 702 {
 703         struct bch_fs *c = trans->c;
 704         struct printbuf buf = PRINTBUF;
 705         int ret = 0;
 706
 707         if (mustfix_fsck_err_on(!bch2_snapshot_equiv(c, k.k->p.snapshot), c,
 708                                 bkey_in_missing_snapshot,
 709                                 "key in missing snapshot: %s",
 710                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
 711                 ret = bch2_btree_delete_at(trans, iter,
 712                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?: 1;
 713 fsck_err:
 714         printbuf_exit(&buf);
 715         return ret;
 716 }
 717
 718 static int hash_redo_key(struct btree_trans *trans,
 719                          const struct bch_hash_desc desc,
 720                          struct bch_hash_info *hash_info,
 721                          struct btree_iter *k_iter, struct bkey_s_c k)
 722 {
 723         struct bkey_i *delete;
 724         struct bkey_i *tmp;
 725
 726         delete = bch2_trans_kmalloc(trans, sizeof(*delete));
 727         if (IS_ERR(delete))
 728                 return PTR_ERR(delete);
 729
 730         tmp = bch2_bkey_make_mut_noupdate(trans, k);
 731         if (IS_ERR(tmp))
 732                 return PTR_ERR(tmp);
 733
 734         bkey_init(&delete->k);
 735         delete->k.p = k_iter->pos;
 736         return  bch2_btree_iter_traverse(k_iter) ?:
 737                 bch2_trans_update(trans, k_iter, delete, 0) ?:
 738                 bch2_hash_set_in_snapshot(trans, desc, hash_info,
 739                                        (subvol_inum) { 0, k.k->p.inode },
 740                                        k.k->p.snapshot, tmp,
 741                                        BCH_HASH_SET_MUST_CREATE,
 742                                        BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?:
 743                 bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);
 744 }
 745
 746 static int hash_check_key(struct btree_trans *trans,
 747                           const struct bch_hash_desc desc,
 748                           struct bch_hash_info *hash_info,
 749                           struct btree_iter *k_iter, struct bkey_s_c hash_k)
 750 {
 751         struct bch_fs *c = trans->c;
 752         struct btree_iter iter = { NULL };
 753         struct printbuf buf = PRINTBUF;
 754         struct bkey_s_c k;
 755         u64 hash;
 756         int ret = 0;
 757
 758         if (hash_k.k->type != desc.key_type)
 759                 return 0;
 760
 761         hash = desc.hash_bkey(hash_info, hash_k);
 762
 763         if (likely(hash == hash_k.k->p.offset))
 764                 return 0;
 765
 766         if (hash_k.k->p.offset < hash)
 767                 goto bad_hash;
 768
 769         for_each_btree_key_norestart(trans, iter, desc.btree_id,
 770                                      SPOS(hash_k.k->p.inode, hash, hash_k.k->p.snapshot),
 771                                      BTREE_ITER_SLOTS, k, ret) {
 772                 if (bkey_eq(k.k->p, hash_k.k->p))
 773                         break;
 774
 775                 if (fsck_err_on(k.k->type == desc.key_type &&
 776                                 !desc.cmp_bkey(k, hash_k), c,
 777                                 hash_table_key_duplicate,
 778                                 "duplicate hash table keys:\n%s",
 779                                 (printbuf_reset(&buf),
 780                                  bch2_bkey_val_to_text(&buf, c, hash_k),
 781                                  buf.buf))) {
 782                         ret = bch2_hash_delete_at(trans, desc, hash_info, k_iter, 0) ?: 1;
 783                         break;
 784                 }
 785
 786                 if (bkey_deleted(k.k)) {
 787                         bch2_trans_iter_exit(trans, &iter);
 788                         goto bad_hash;
 789                 }
 790         }
 791 out:
 792         bch2_trans_iter_exit(trans, &iter);
 793         printbuf_exit(&buf);
 794         return ret;
 795 bad_hash:
 796         if (fsck_err(c, hash_table_key_wrong_offset,
 797                      "hash table key at wrong offset: btree %s inode %llu offset %llu, hashed to %llu\n%s",
 798                      bch2_btree_id_str(desc.btree_id), hash_k.k->p.inode, hash_k.k->p.offset, hash,
 799                      (printbuf_reset(&buf),
 800                       bch2_bkey_val_to_text(&buf, c, hash_k), buf.buf))) {
 801                 ret = hash_redo_key(trans, desc, hash_info, k_iter, hash_k);
 802                 bch_err_fn(c, ret);
 803                 if (ret)
 804                         return ret;
 805                 ret = -BCH_ERR_transaction_restart_nested;
 806         }
 807 fsck_err:
 808         goto out;
 809 }
 810
 811 static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans,
 812                                                 struct btree_iter *iter,
 813                                                 struct bpos pos)
 814 {
 815         return bch2_bkey_get_iter_typed(trans, iter, BTREE_ID_dirents, pos, 0, dirent);
 816 }
 817
 818 static struct bkey_s_c_dirent inode_get_dirent(struct btree_trans *trans,
 819                                                struct btree_iter *iter,
 820                                                struct bch_inode_unpacked *inode,
 821                                                u32 *snapshot)
 822 {
 823         if (inode->bi_subvol) {
 824                 u64 inum;
 825                 int ret = subvol_lookup(trans, inode->bi_parent_subvol, snapshot, &inum);
 826                 if (ret)
 827                         return ((struct bkey_s_c_dirent) { .k = ERR_PTR(ret) });
 828         }
 829
 830         return dirent_get_by_pos(trans, iter, SPOS(inode->bi_dir, inode->bi_dir_offset, *snapshot));
 831 }
 832
 833 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode,
 834                                    struct bkey_s_c_dirent d)
 835 {
 836         return  inode->bi_dir           == d.k->p.inode &&
 837                 inode->bi_dir_offset    == d.k->p.offset;
 838 }
 839
 840 static bool dirent_points_to_inode(struct bkey_s_c_dirent d,
 841                                    struct bch_inode_unpacked *inode)
 842 {
 843         return d.v->d_type == DT_SUBVOL
 844                 ? le32_to_cpu(d.v->d_child_subvol)      == inode->bi_subvol
 845                 : le64_to_cpu(d.v->d_inum)              == inode->bi_inum;
 846 }
 847
 848 static int check_inode_deleted_list(struct btree_trans *trans, struct bpos p)
 849 {
 850         struct btree_iter iter;
 851         struct bkey_s_c k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_deleted_inodes, p, 0);
 852         int ret = bkey_err(k);
 853         if (ret)
 854                 return ret;
 855
 856         bch2_trans_iter_exit(trans, &iter);
 857         return k.k->type == KEY_TYPE_set;
 858 }
 859
 860 static int check_inode_dirent_inode(struct btree_trans *trans, struct bkey_s_c inode_k,
 861                                     struct bch_inode_unpacked *inode,
 862                                     u32 inode_snapshot, bool *write_inode)
 863 {
 864         struct bch_fs *c = trans->c;
 865         struct printbuf buf = PRINTBUF;
 866
 867         struct btree_iter dirent_iter = {};
 868         struct bkey_s_c_dirent d = inode_get_dirent(trans, &dirent_iter, inode, &inode_snapshot);
 869         int ret = bkey_err(d);
 870         if (ret && !bch2_err_matches(ret, ENOENT))
 871                 return ret;
 872
 873         if (fsck_err_on(ret,
 874                         c, inode_points_to_missing_dirent,
 875                         "inode points to missing dirent\n%s",
 876                         (bch2_bkey_val_to_text(&buf, c, inode_k), buf.buf)) ||
 877             fsck_err_on(!ret && !dirent_points_to_inode(d, inode),
 878                         c, inode_points_to_wrong_dirent,
 879                         "inode points to dirent that does not point back:\n%s",
 880                         (bch2_bkey_val_to_text(&buf, c, inode_k),
 881                          prt_newline(&buf),
 882                          bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf))) {
 883                 /*
 884                  * We just clear the backpointer fields for now. If we find a
 885                  * dirent that points to this inode in check_dirents(), we'll
 886                  * update it then; then when we get to check_path() if the
 887                  * backpointer is still 0 we'll reattach it.
 888                  */
 889                 inode->bi_dir = 0;
 890                 inode->bi_dir_offset = 0;
 891                 inode->bi_flags &= ~BCH_INODE_backptr_untrusted;
 892                 *write_inode = true;
 893         }
 894
 895         ret = 0;
 896 fsck_err:
 897         bch2_trans_iter_exit(trans, &dirent_iter);
 898         printbuf_exit(&buf);
 899         bch_err_fn(c, ret);
 900         return ret;
 901 }
 902
 903 static int check_inode(struct btree_trans *trans,
 904                        struct btree_iter *iter,
 905                        struct bkey_s_c k,
 906                        struct bch_inode_unpacked *prev,
 907                        struct snapshots_seen *s,
 908                        bool full)
 909 {
 910         struct bch_fs *c = trans->c;
 911         struct bch_inode_unpacked u;
 912         bool do_update = false;
 913         int ret;
 914
 915         ret = check_key_has_snapshot(trans, iter, k);
 916         if (ret < 0)
 917                 goto err;
 918         if (ret)
 919                 return 0;
 920
 921         ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p);
 922         if (ret)
 923                 goto err;
 924
 925         if (!bkey_is_inode(k.k))
 926                 return 0;
 927
 928         BUG_ON(bch2_inode_unpack(k, &u));
 929
 930         if (!full &&
 931             !(u.bi_flags & (BCH_INODE_i_size_dirty|
 932                             BCH_INODE_i_sectors_dirty|
 933                             BCH_INODE_unlinked)))
 934                 return 0;
 935
 936         if (prev->bi_inum != u.bi_inum)
 937                 *prev = u;
 938
 939         if (fsck_err_on(prev->bi_hash_seed      != u.bi_hash_seed ||
 940                         inode_d_type(prev)      != inode_d_type(&u),
 941                         c, inode_snapshot_mismatch,
 942                         "inodes in different snapshots don't match")) {
 943                 bch_err(c, "repair not implemented yet");
 944                 return -BCH_ERR_fsck_repair_unimplemented;
 945         }
 946
 947         if ((u.bi_flags & (BCH_INODE_i_size_dirty|BCH_INODE_unlinked)) &&
 948             bch2_key_has_snapshot_overwrites(trans, BTREE_ID_inodes, k.k->p)) {
 949                 struct bpos new_min_pos;
 950
 951                 ret = bch2_propagate_key_to_snapshot_leaves(trans, iter->btree_id, k, &new_min_pos);
 952                 if (ret)
 953                         goto err;
 954
 955                 u.bi_flags &= ~BCH_INODE_i_size_dirty|BCH_INODE_unlinked;
 956
 957                 ret = __bch2_fsck_write_inode(trans, &u, iter->pos.snapshot);
 958
 959                 bch_err_msg(c, ret, "in fsck updating inode");
 960                 if (ret)
 961                         return ret;
 962
 963                 if (!bpos_eq(new_min_pos, POS_MIN))
 964                         bch2_btree_iter_set_pos(iter, bpos_predecessor(new_min_pos));
 965                 return 0;
 966         }
 967
 968         if (u.bi_flags & BCH_INODE_unlinked) {
 969                 ret = check_inode_deleted_list(trans, k.k->p);
 970                 if (ret < 0)
 971                         return ret;
 972
 973                 fsck_err_on(ret, c, unlinked_inode_not_on_deleted_list,
 974                             "inode %llu:%u unlinked, but not on deleted list",
 975                             u.bi_inum, k.k->p.snapshot);
 976                 ret = 0;
 977         }
 978
 979         if (u.bi_flags & BCH_INODE_unlinked &&
 980             (!c->sb.clean ||
 981              fsck_err(c, inode_unlinked_but_clean,
 982                       "filesystem marked clean, but inode %llu unlinked",
 983                       u.bi_inum))) {
 984                 ret = bch2_inode_rm_snapshot(trans, u.bi_inum, iter->pos.snapshot);
 985                 bch_err_msg(c, ret, "in fsck deleting inode");
 986                 return ret;
 987         }
 988
 989         if (u.bi_flags & BCH_INODE_i_size_dirty &&
 990             (!c->sb.clean ||
 991              fsck_err(c, inode_i_size_dirty_but_clean,
 992                       "filesystem marked clean, but inode %llu has i_size dirty",
 993                       u.bi_inum))) {
 994                 bch_verbose(c, "truncating inode %llu", u.bi_inum);
 995
 996                 /*
 997                  * XXX: need to truncate partial blocks too here - or ideally
 998                  * just switch units to bytes and that issue goes away
 999                  */
1000                 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
1001                                 SPOS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9,
1002                                      iter->pos.snapshot),
1003                                 POS(u.bi_inum, U64_MAX),
1004                                 0, NULL);
1005                 bch_err_msg(c, ret, "in fsck truncating inode");
1006                 if (ret)
1007                         return ret;
1008
1009                 /*
1010                  * We truncated without our normal sector accounting hook, just
1011                  * make sure we recalculate it:
1012                  */
1013                 u.bi_flags |= BCH_INODE_i_sectors_dirty;
1014
1015                 u.bi_flags &= ~BCH_INODE_i_size_dirty;
1016                 do_update = true;
1017         }
1018
1019         if (u.bi_flags & BCH_INODE_i_sectors_dirty &&
1020             (!c->sb.clean ||
1021              fsck_err(c, inode_i_sectors_dirty_but_clean,
1022                       "filesystem marked clean, but inode %llu has i_sectors dirty",
1023                       u.bi_inum))) {
1024                 s64 sectors;
1025
1026                 bch_verbose(c, "recounting sectors for inode %llu",
1027                             u.bi_inum);
1028
1029                 sectors = bch2_count_inode_sectors(trans, u.bi_inum, iter->pos.snapshot);
1030                 if (sectors < 0) {
1031                         bch_err_msg(c, sectors, "in fsck recounting inode sectors");
1032                         return sectors;
1033                 }
1034
1035                 u.bi_sectors = sectors;
1036                 u.bi_flags &= ~BCH_INODE_i_sectors_dirty;
1037                 do_update = true;
1038         }
1039
1040         if (u.bi_flags & BCH_INODE_backptr_untrusted) {
1041                 u.bi_dir = 0;
1042                 u.bi_dir_offset = 0;
1043                 u.bi_flags &= ~BCH_INODE_backptr_untrusted;
1044                 do_update = true;
1045         }
1046
1047         if (u.bi_dir || u.bi_dir_offset) {
1048                 ret = check_inode_dirent_inode(trans, k, &u, k.k->p.snapshot, &do_update);
1049                 if (ret)
1050                         goto err;
1051         }
1052
1053         if (fsck_err_on(u.bi_parent_subvol &&
1054                         (u.bi_subvol == 0 ||
1055                          u.bi_subvol == BCACHEFS_ROOT_SUBVOL),
1056                         c, inode_bi_parent_nonzero,
1057                         "inode %llu:%u has subvol %u but nonzero parent subvol %u",
1058                         u.bi_inum, k.k->p.snapshot, u.bi_subvol, u.bi_parent_subvol)) {
1059                 u.bi_parent_subvol = 0;
1060                 do_update = true;
1061         }
1062
1063         if (u.bi_subvol) {
1064                 struct bch_subvolume s;
1065
1066                 ret = bch2_subvolume_get(trans, u.bi_subvol, false, 0, &s);
1067                 if (ret && !bch2_err_matches(ret, ENOENT))
1068                         goto err;
1069
1070                 if (fsck_err_on(ret,
1071                                 c, inode_bi_subvol_missing,
1072                                 "inode %llu:%u bi_subvol points to missing subvolume %u",
1073                                 u.bi_inum, k.k->p.snapshot, u.bi_subvol) ||
1074                     fsck_err_on(le64_to_cpu(s.inode) != u.bi_inum ||
1075                                 !bch2_snapshot_is_ancestor(c, le32_to_cpu(s.snapshot),
1076                                                            k.k->p.snapshot),
1077                                 c, inode_bi_subvol_wrong,
1078                                 "inode %llu:%u points to subvol %u, but subvol points to %llu:%u",
1079                                 u.bi_inum, k.k->p.snapshot, u.bi_subvol,
1080                                 le64_to_cpu(s.inode),
1081                                 le32_to_cpu(s.snapshot))) {
1082                         u.bi_subvol = 0;
1083                         u.bi_parent_subvol = 0;
1084                         do_update = true;
1085                 }
1086         }
1087
1088         if (do_update) {
1089                 ret = __bch2_fsck_write_inode(trans, &u, iter->pos.snapshot);
1090                 bch_err_msg(c, ret, "in fsck updating inode");
1091                 if (ret)
1092                         return ret;
1093         }
1094 err:
1095 fsck_err:
1096         bch_err_fn(c, ret);
1097         return ret;
1098 }
1099
1100 int bch2_check_inodes(struct bch_fs *c)
1101 {
1102         bool full = c->opts.fsck;
1103         struct bch_inode_unpacked prev = { 0 };
1104         struct snapshots_seen s;
1105
1106         snapshots_seen_init(&s);
1107
1108         int ret = bch2_trans_run(c,
1109                 for_each_btree_key_commit(trans, iter, BTREE_ID_inodes,
1110                                 POS_MIN,
1111                                 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1112                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
1113                         check_inode(trans, &iter, k, &prev, &s, full)));
1114
1115         snapshots_seen_exit(&s);
1116         bch_err_fn(c, ret);
1117         return ret;
1118 }
1119
1120 static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w)
1121 {
1122         struct bch_fs *c = trans->c;
1123         u32 restart_count = trans->restart_count;
1124         int ret = 0;
1125         s64 count2;
1126
1127         darray_for_each(w->inodes, i) {
1128                 if (i->inode.bi_sectors == i->count)
1129                         continue;
1130
1131                 count2 = bch2_count_inode_sectors(trans, w->last_pos.inode, i->snapshot);
1132
1133                 if (w->recalculate_sums)
1134                         i->count = count2;
1135
1136                 if (i->count != count2) {
1137                         bch_err(c, "fsck counted i_sectors wrong for inode %llu:%u: got %llu should be %llu",
1138                                 w->last_pos.inode, i->snapshot, i->count, count2);
1139                         return -BCH_ERR_internal_fsck_err;
1140                 }
1141
1142                 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_i_sectors_dirty),
1143                                 c, inode_i_sectors_wrong,
1144                                 "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu",
1145                                 w->last_pos.inode, i->snapshot,
1146                                 i->inode.bi_sectors, i->count)) {
1147                         i->inode.bi_sectors = i->count;
1148                         ret = bch2_fsck_write_inode(trans, &i->inode, i->snapshot);
1149                         if (ret)
1150                                 break;
1151                 }
1152         }
1153 fsck_err:
1154         bch_err_fn(c, ret);
1155         return ret ?: trans_was_restarted(trans, restart_count);
1156 }
1157
1158 struct extent_end {
1159         u32                     snapshot;
1160         u64                     offset;
1161         struct snapshots_seen   seen;
1162 };
1163
1164 struct extent_ends {
1165         struct bpos                     last_pos;
1166         DARRAY(struct extent_end)       e;
1167 };
1168
1169 static void extent_ends_reset(struct extent_ends *extent_ends)
1170 {
1171         darray_for_each(extent_ends->e, i)
1172                 snapshots_seen_exit(&i->seen);
1173         extent_ends->e.nr = 0;
1174 }
1175
1176 static void extent_ends_exit(struct extent_ends *extent_ends)
1177 {
1178         extent_ends_reset(extent_ends);
1179         darray_exit(&extent_ends->e);
1180 }
1181
1182 static void extent_ends_init(struct extent_ends *extent_ends)
1183 {
1184         memset(extent_ends, 0, sizeof(*extent_ends));
1185 }
1186
1187 static int extent_ends_at(struct bch_fs *c,
1188                           struct extent_ends *extent_ends,
1189                           struct snapshots_seen *seen,
1190                           struct bkey_s_c k)
1191 {
1192         struct extent_end *i, n = (struct extent_end) {
1193                 .offset         = k.k->p.offset,
1194                 .snapshot       = k.k->p.snapshot,
1195                 .seen           = *seen,
1196         };
1197
1198         n.seen.ids.data = kmemdup(seen->ids.data,
1199                               sizeof(seen->ids.data[0]) * seen->ids.size,
1200                               GFP_KERNEL);
1201         if (!n.seen.ids.data)
1202                 return -BCH_ERR_ENOMEM_fsck_extent_ends_at;
1203
1204         __darray_for_each(extent_ends->e, i) {
1205                 if (i->snapshot == k.k->p.snapshot) {
1206                         snapshots_seen_exit(&i->seen);
1207                         *i = n;
1208                         return 0;
1209                 }
1210
1211                 if (i->snapshot >= k.k->p.snapshot)
1212                         break;
1213         }
1214
1215         return darray_insert_item(&extent_ends->e, i - extent_ends->e.data, n);
1216 }
1217
1218 static int overlapping_extents_found(struct btree_trans *trans,
1219                                      enum btree_id btree,
1220                                      struct bpos pos1, struct snapshots_seen *pos1_seen,
1221                                      struct bkey pos2,
1222                                      bool *fixed,
1223                                      struct extent_end *extent_end)
1224 {
1225         struct bch_fs *c = trans->c;
1226         struct printbuf buf = PRINTBUF;
1227         struct btree_iter iter1, iter2 = { NULL };
1228         struct bkey_s_c k1, k2;
1229         int ret;
1230
1231         BUG_ON(bkey_le(pos1, bkey_start_pos(&pos2)));
1232
1233         bch2_trans_iter_init(trans, &iter1, btree, pos1,
1234                              BTREE_ITER_ALL_SNAPSHOTS|
1235                              BTREE_ITER_NOT_EXTENTS);
1236         k1 = bch2_btree_iter_peek_upto(&iter1, POS(pos1.inode, U64_MAX));
1237         ret = bkey_err(k1);
1238         if (ret)
1239                 goto err;
1240
1241         prt_str(&buf, "\n  ");
1242         bch2_bkey_val_to_text(&buf, c, k1);
1243
1244         if (!bpos_eq(pos1, k1.k->p)) {
1245                 prt_str(&buf, "\n  wanted\n  ");
1246                 bch2_bpos_to_text(&buf, pos1);
1247                 prt_str(&buf, "\n  ");
1248                 bch2_bkey_to_text(&buf, &pos2);
1249
1250                 bch_err(c, "%s: error finding first overlapping extent when repairing, got%s",
1251                         __func__, buf.buf);
1252                 ret = -BCH_ERR_internal_fsck_err;
1253                 goto err;
1254         }
1255
1256         bch2_trans_copy_iter(&iter2, &iter1);
1257
1258         while (1) {
1259                 bch2_btree_iter_advance(&iter2);
1260
1261                 k2 = bch2_btree_iter_peek_upto(&iter2, POS(pos1.inode, U64_MAX));
1262                 ret = bkey_err(k2);
1263                 if (ret)
1264                         goto err;
1265
1266                 if (bpos_ge(k2.k->p, pos2.p))
1267                         break;
1268         }
1269
1270         prt_str(&buf, "\n  ");
1271         bch2_bkey_val_to_text(&buf, c, k2);
1272
1273         if (bpos_gt(k2.k->p, pos2.p) ||
1274             pos2.size != k2.k->size) {
1275                 bch_err(c, "%s: error finding seconding overlapping extent when repairing%s",
1276                         __func__, buf.buf);
1277                 ret = -BCH_ERR_internal_fsck_err;
1278                 goto err;
1279         }
1280
1281         prt_printf(&buf, "\n  overwriting %s extent",
1282                    pos1.snapshot >= pos2.p.snapshot ? "first" : "second");
1283
1284         if (fsck_err(c, extent_overlapping,
1285                      "overlapping extents%s", buf.buf)) {
1286                 struct btree_iter *old_iter = &iter1;
1287                 struct disk_reservation res = { 0 };
1288
1289                 if (pos1.snapshot < pos2.p.snapshot) {
1290                         old_iter = &iter2;
1291                         swap(k1, k2);
1292                 }
1293
1294                 trans->extra_disk_res += bch2_bkey_sectors_compressed(k2);
1295
1296                 ret =   bch2_trans_update_extent_overwrite(trans, old_iter,
1297                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE,
1298                                 k1, k2) ?:
1299                         bch2_trans_commit(trans, &res, NULL, BCH_TRANS_COMMIT_no_enospc);
1300                 bch2_disk_reservation_put(c, &res);
1301
1302                 if (ret)
1303                         goto err;
1304
1305                 *fixed = true;
1306
1307                 if (pos1.snapshot == pos2.p.snapshot) {
1308                         /*
1309                          * We overwrote the first extent, and did the overwrite
1310                          * in the same snapshot:
1311                          */
1312                         extent_end->offset = bkey_start_offset(&pos2);
1313                 } else if (pos1.snapshot > pos2.p.snapshot) {
1314                         /*
1315                          * We overwrote the first extent in pos2's snapshot:
1316                          */
1317                         ret = snapshots_seen_add_inorder(c, pos1_seen, pos2.p.snapshot);
1318                 } else {
1319                         /*
1320                          * We overwrote the second extent - restart
1321                          * check_extent() from the top:
1322                          */
1323                         ret = -BCH_ERR_transaction_restart_nested;
1324                 }
1325         }
1326 fsck_err:
1327 err:
1328         bch2_trans_iter_exit(trans, &iter2);
1329         bch2_trans_iter_exit(trans, &iter1);
1330         printbuf_exit(&buf);
1331         return ret;
1332 }
1333
1334 static int check_overlapping_extents(struct btree_trans *trans,
1335                               struct snapshots_seen *seen,
1336                               struct extent_ends *extent_ends,
1337                               struct bkey_s_c k,
1338                               u32 equiv,
1339                               struct btree_iter *iter,
1340                               bool *fixed)
1341 {
1342         struct bch_fs *c = trans->c;
1343         int ret = 0;
1344
1345         /* transaction restart, running again */
1346         if (bpos_eq(extent_ends->last_pos, k.k->p))
1347                 return 0;
1348
1349         if (extent_ends->last_pos.inode != k.k->p.inode)
1350                 extent_ends_reset(extent_ends);
1351
1352         darray_for_each(extent_ends->e, i) {
1353                 if (i->offset <= bkey_start_offset(k.k))
1354                         continue;
1355
1356                 if (!ref_visible2(c,
1357                                   k.k->p.snapshot, seen,
1358                                   i->snapshot, &i->seen))
1359                         continue;
1360
1361                 ret = overlapping_extents_found(trans, iter->btree_id,
1362                                                 SPOS(iter->pos.inode,
1363                                                      i->offset,
1364                                                      i->snapshot),
1365                                                 &i->seen,
1366                                                 *k.k, fixed, i);
1367                 if (ret)
1368                         goto err;
1369         }
1370
1371         ret = extent_ends_at(c, extent_ends, seen, k);
1372         if (ret)
1373                 goto err;
1374
1375         extent_ends->last_pos = k.k->p;
1376 err:
1377         return ret;
1378 }
1379
1380 static int check_extent_overbig(struct btree_trans *trans, struct btree_iter *iter,
1381                                 struct bkey_s_c k)
1382 {
1383         struct bch_fs *c = trans->c;
1384         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
1385         struct bch_extent_crc_unpacked crc;
1386         const union bch_extent_entry *i;
1387         unsigned encoded_extent_max_sectors = c->opts.encoded_extent_max >> 9;
1388
1389         bkey_for_each_crc(k.k, ptrs, crc, i)
1390                 if (crc_is_encoded(crc) &&
1391                     crc.uncompressed_size > encoded_extent_max_sectors) {
1392                         struct printbuf buf = PRINTBUF;
1393
1394                         bch2_bkey_val_to_text(&buf, c, k);
1395                         bch_err(c, "overbig encoded extent, please report this:\n  %s", buf.buf);
1396                         printbuf_exit(&buf);
1397                 }
1398
1399         return 0;
1400 }
1401
1402 static int check_extent(struct btree_trans *trans, struct btree_iter *iter,
1403                         struct bkey_s_c k,
1404                         struct inode_walker *inode,
1405                         struct snapshots_seen *s,
1406                         struct extent_ends *extent_ends)
1407 {
1408         struct bch_fs *c = trans->c;
1409         struct inode_walker_entry *i;
1410         struct printbuf buf = PRINTBUF;
1411         struct bpos equiv = k.k->p;
1412         int ret = 0;
1413
1414         equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot);
1415
1416         ret = check_key_has_snapshot(trans, iter, k);
1417         if (ret) {
1418                 ret = ret < 0 ? ret : 0;
1419                 goto out;
1420         }
1421
1422         if (inode->last_pos.inode != k.k->p.inode) {
1423                 ret = check_i_sectors(trans, inode);
1424                 if (ret)
1425                         goto err;
1426         }
1427
1428         i = walk_inode(trans, inode, k);
1429         ret = PTR_ERR_OR_ZERO(i);
1430         if (ret)
1431                 goto err;
1432
1433         ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p);
1434         if (ret)
1435                 goto err;
1436
1437         if (k.k->type != KEY_TYPE_whiteout) {
1438                 if (fsck_err_on(!i, c, extent_in_missing_inode,
1439                                 "extent in missing inode:\n  %s",
1440                                 (printbuf_reset(&buf),
1441                                  bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
1442                         goto delete;
1443
1444                 if (fsck_err_on(i &&
1445                                 !S_ISREG(i->inode.bi_mode) &&
1446                                 !S_ISLNK(i->inode.bi_mode),
1447                                 c, extent_in_non_reg_inode,
1448                                 "extent in non regular inode mode %o:\n  %s",
1449                                 i->inode.bi_mode,
1450                                 (printbuf_reset(&buf),
1451                                  bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
1452                         goto delete;
1453
1454                 ret = check_overlapping_extents(trans, s, extent_ends, k,
1455                                                 equiv.snapshot, iter,
1456                                                 &inode->recalculate_sums);
1457                 if (ret)
1458                         goto err;
1459         }
1460
1461         /*
1462          * Check inodes in reverse order, from oldest snapshots to newest,
1463          * starting from the inode that matches this extent's snapshot. If we
1464          * didn't have one, iterate over all inodes:
1465          */
1466         if (!i)
1467                 i = inode->inodes.data + inode->inodes.nr - 1;
1468
1469         for (;
1470              inode->inodes.data && i >= inode->inodes.data;
1471              --i) {
1472                 if (i->snapshot > equiv.snapshot ||
1473                     !key_visible_in_snapshot(c, s, i->snapshot, equiv.snapshot))
1474                         continue;
1475
1476                 if (k.k->type != KEY_TYPE_whiteout) {
1477                         if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_i_size_dirty) &&
1478                                         k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9 &&
1479                                         !bkey_extent_is_reservation(k),
1480                                         c, extent_past_end_of_inode,
1481                                         "extent type past end of inode %llu:%u, i_size %llu\n  %s",
1482                                         i->inode.bi_inum, i->snapshot, i->inode.bi_size,
1483                                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1484                                 struct btree_iter iter2;
1485
1486                                 bch2_trans_copy_iter(&iter2, iter);
1487                                 bch2_btree_iter_set_snapshot(&iter2, i->snapshot);
1488                                 ret =   bch2_btree_iter_traverse(&iter2) ?:
1489                                         bch2_btree_delete_at(trans, &iter2,
1490                                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1491                                 bch2_trans_iter_exit(trans, &iter2);
1492                                 if (ret)
1493                                         goto err;
1494
1495                                 iter->k.type = KEY_TYPE_whiteout;
1496                         }
1497
1498                         if (bkey_extent_is_allocation(k.k))
1499                                 i->count += k.k->size;
1500                 }
1501
1502                 i->seen_this_pos = true;
1503         }
1504 out:
1505 err:
1506 fsck_err:
1507         printbuf_exit(&buf);
1508         bch_err_fn(c, ret);
1509         return ret;
1510 delete:
1511         ret = bch2_btree_delete_at(trans, iter, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1512         goto out;
1513 }
1514
1515 /*
1516  * Walk extents: verify that extents have a corresponding S_ISREG inode, and
1517  * that i_size an i_sectors are consistent
1518  */
1519 int bch2_check_extents(struct bch_fs *c)
1520 {
1521         struct inode_walker w = inode_walker_init();
1522         struct snapshots_seen s;
1523         struct extent_ends extent_ends;
1524         struct disk_reservation res = { 0 };
1525
1526         snapshots_seen_init(&s);
1527         extent_ends_init(&extent_ends);
1528
1529         int ret = bch2_trans_run(c,
1530                 for_each_btree_key_commit(trans, iter, BTREE_ID_extents,
1531                                 POS(BCACHEFS_ROOT_INO, 0),
1532                                 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1533                                 &res, NULL,
1534                                 BCH_TRANS_COMMIT_no_enospc, ({
1535                         bch2_disk_reservation_put(c, &res);
1536                         check_extent(trans, &iter, k, &w, &s, &extent_ends) ?:
1537                         check_extent_overbig(trans, &iter, k);
1538                 })) ?:
1539                 check_i_sectors(trans, &w));
1540
1541         bch2_disk_reservation_put(c, &res);
1542         extent_ends_exit(&extent_ends);
1543         inode_walker_exit(&w);
1544         snapshots_seen_exit(&s);
1545
1546         bch_err_fn(c, ret);
1547         return ret;
1548 }
1549
1550 int bch2_check_indirect_extents(struct bch_fs *c)
1551 {
1552         struct disk_reservation res = { 0 };
1553
1554         int ret = bch2_trans_run(c,
1555                 for_each_btree_key_commit(trans, iter, BTREE_ID_reflink,
1556                                 POS_MIN,
1557                                 BTREE_ITER_PREFETCH, k,
1558                                 &res, NULL,
1559                                 BCH_TRANS_COMMIT_no_enospc, ({
1560                         bch2_disk_reservation_put(c, &res);
1561                         check_extent_overbig(trans, &iter, k);
1562                 })));
1563
1564         bch2_disk_reservation_put(c, &res);
1565         bch_err_fn(c, ret);
1566         return ret;
1567 }
1568
1569 static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w)
1570 {
1571         struct bch_fs *c = trans->c;
1572         u32 restart_count = trans->restart_count;
1573         int ret = 0;
1574         s64 count2;
1575
1576         darray_for_each(w->inodes, i) {
1577                 if (i->inode.bi_nlink == i->count)
1578                         continue;
1579
1580                 count2 = bch2_count_subdirs(trans, w->last_pos.inode, i->snapshot);
1581                 if (count2 < 0)
1582                         return count2;
1583
1584                 if (i->count != count2) {
1585                         bch_err(c, "fsck counted subdirectories wrong: got %llu should be %llu",
1586                                 i->count, count2);
1587                         i->count = count2;
1588                         if (i->inode.bi_nlink == i->count)
1589                                 continue;
1590                 }
1591
1592                 if (fsck_err_on(i->inode.bi_nlink != i->count,
1593                                 c, inode_dir_wrong_nlink,
1594                                 "directory %llu:%u with wrong i_nlink: got %u, should be %llu",
1595                                 w->last_pos.inode, i->snapshot, i->inode.bi_nlink, i->count)) {
1596                         i->inode.bi_nlink = i->count;
1597                         ret = bch2_fsck_write_inode(trans, &i->inode, i->snapshot);
1598                         if (ret)
1599                                 break;
1600                 }
1601         }
1602 fsck_err:
1603         bch_err_fn(c, ret);
1604         return ret ?: trans_was_restarted(trans, restart_count);
1605 }
1606
1607 static int check_dirent_inode_dirent(struct btree_trans *trans,
1608                                    struct btree_iter *iter,
1609                                    struct bkey_s_c_dirent d,
1610                                    struct bch_inode_unpacked *target,
1611                                    u32 target_snapshot)
1612 {
1613         struct bch_fs *c = trans->c;
1614         struct printbuf buf = PRINTBUF;
1615         int ret = 0;
1616
1617         if (inode_points_to_dirent(target, d))
1618                 return 0;
1619
1620         if (!target->bi_dir &&
1621             !target->bi_dir_offset) {
1622                 target->bi_dir          = d.k->p.inode;
1623                 target->bi_dir_offset   = d.k->p.offset;
1624                 return __bch2_fsck_write_inode(trans, target, target_snapshot);
1625         }
1626
1627         struct btree_iter bp_iter = { NULL };
1628         struct bkey_s_c_dirent bp_dirent = dirent_get_by_pos(trans, &bp_iter,
1629                               SPOS(target->bi_dir, target->bi_dir_offset, target_snapshot));
1630         ret = bkey_err(bp_dirent);
1631         if (ret && !bch2_err_matches(ret, ENOENT))
1632                 goto err;
1633
1634         bool backpointer_exists = !ret;
1635         ret = 0;
1636
1637         if (fsck_err_on(!backpointer_exists,
1638                         c, inode_wrong_backpointer,
1639                         "inode %llu:%u has wrong backpointer:\n"
1640                         "got       %llu:%llu\n"
1641                         "should be %llu:%llu",
1642                         target->bi_inum, target_snapshot,
1643                         target->bi_dir,
1644                         target->bi_dir_offset,
1645                         d.k->p.inode,
1646                         d.k->p.offset)) {
1647                 target->bi_dir          = d.k->p.inode;
1648                 target->bi_dir_offset   = d.k->p.offset;
1649                 ret = __bch2_fsck_write_inode(trans, target, target_snapshot);
1650                 goto out;
1651         }
1652
1653         bch2_bkey_val_to_text(&buf, c, d.s_c);
1654         prt_newline(&buf);
1655         if (backpointer_exists)
1656                 bch2_bkey_val_to_text(&buf, c, bp_dirent.s_c);
1657
1658         if (fsck_err_on(backpointer_exists &&
1659                         (S_ISDIR(target->bi_mode) ||
1660                          target->bi_subvol),
1661                         c, inode_dir_multiple_links,
1662                         "%s %llu:%u with multiple links\n%s",
1663                         S_ISDIR(target->bi_mode) ? "directory" : "subvolume",
1664                         target->bi_inum, target_snapshot, buf.buf)) {
1665                 ret = __remove_dirent(trans, d.k->p);
1666                 goto out;
1667         }
1668
1669         /*
1670          * hardlinked file with nlink 0:
1671          * We're just adjusting nlink here so check_nlinks() will pick
1672          * it up, it ignores inodes with nlink 0
1673          */
1674         if (fsck_err_on(backpointer_exists && !target->bi_nlink,
1675                         c, inode_multiple_links_but_nlink_0,
1676                         "inode %llu:%u type %s has multiple links but i_nlink 0\n%s",
1677                         target->bi_inum, target_snapshot, bch2_d_types[d.v->d_type], buf.buf)) {
1678                 target->bi_nlink++;
1679                 target->bi_flags &= ~BCH_INODE_unlinked;
1680                 ret = __bch2_fsck_write_inode(trans, target, target_snapshot);
1681                 if (ret)
1682                         goto err;
1683         }
1684 out:
1685 err:
1686 fsck_err:
1687         bch2_trans_iter_exit(trans, &bp_iter);
1688         printbuf_exit(&buf);
1689         bch_err_fn(c, ret);
1690         return ret;
1691 }
1692
1693 static int check_dirent_target(struct btree_trans *trans,
1694                                struct btree_iter *iter,
1695                                struct bkey_s_c_dirent d,
1696                                struct bch_inode_unpacked *target,
1697                                u32 target_snapshot)
1698 {
1699         struct bch_fs *c = trans->c;
1700         struct bkey_i_dirent *n;
1701         struct printbuf buf = PRINTBUF;
1702         int ret = 0;
1703
1704         ret = check_dirent_inode_dirent(trans, iter, d, target, target_snapshot);
1705         if (ret)
1706                 goto err;
1707
1708         if (fsck_err_on(d.v->d_type != inode_d_type(target),
1709                         c, dirent_d_type_wrong,
1710                         "incorrect d_type: got %s, should be %s:\n%s",
1711                         bch2_d_type_str(d.v->d_type),
1712                         bch2_d_type_str(inode_d_type(target)),
1713                         (printbuf_reset(&buf),
1714                          bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf))) {
1715                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1716                 ret = PTR_ERR_OR_ZERO(n);
1717                 if (ret)
1718                         goto err;
1719
1720                 bkey_reassemble(&n->k_i, d.s_c);
1721                 n->v.d_type = inode_d_type(target);
1722                 if (n->v.d_type == DT_SUBVOL) {
1723                         n->v.d_parent_subvol = cpu_to_le32(target->bi_parent_subvol);
1724                         n->v.d_child_subvol = cpu_to_le32(target->bi_subvol);
1725                 } else {
1726                         n->v.d_inum = cpu_to_le64(target->bi_inum);
1727                 }
1728
1729                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1730                 if (ret)
1731                         goto err;
1732
1733                 d = dirent_i_to_s_c(n);
1734         }
1735 err:
1736 fsck_err:
1737         printbuf_exit(&buf);
1738         bch_err_fn(c, ret);
1739         return ret;
1740 }
1741
1742 /* find a subvolume that's a descendent of @snapshot: */
1743 static int find_snapshot_subvol(struct btree_trans *trans, u32 snapshot, u32 *subvolid)
1744 {
1745         struct btree_iter iter;
1746         struct bkey_s_c k;
1747         int ret;
1748
1749         for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN, 0, k, ret) {
1750                 if (k.k->type != KEY_TYPE_subvolume)
1751                         continue;
1752
1753                 struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
1754                 if (bch2_snapshot_is_ancestor(trans->c, le32_to_cpu(s.v->snapshot), snapshot)) {
1755                         bch2_trans_iter_exit(trans, &iter);
1756                         *subvolid = k.k->p.offset;
1757                         goto found;
1758                 }
1759         }
1760         if (!ret)
1761                 ret = -ENOENT;
1762 found:
1763         bch2_trans_iter_exit(trans, &iter);
1764         return ret;
1765 }
1766
1767 static int check_dirent_to_subvol(struct btree_trans *trans, struct btree_iter *iter,
1768                                   struct bkey_s_c_dirent d)
1769 {
1770         struct bch_fs *c = trans->c;
1771         struct btree_iter subvol_iter = {};
1772         struct bch_inode_unpacked subvol_root;
1773         u32 parent_subvol = le32_to_cpu(d.v->d_parent_subvol);
1774         u32 target_subvol = le32_to_cpu(d.v->d_child_subvol);
1775         u32 parent_snapshot;
1776         u64 parent_inum;
1777         struct printbuf buf = PRINTBUF;
1778         int ret = 0;
1779
1780         ret = subvol_lookup(trans, parent_subvol, &parent_snapshot, &parent_inum);
1781         if (ret && !bch2_err_matches(ret, ENOENT))
1782                 return ret;
1783
1784         if (fsck_err_on(ret, c, dirent_to_missing_parent_subvol,
1785                         "dirent parent_subvol points to missing subvolume\n%s",
1786                         (bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf)) ||
1787             fsck_err_on(!ret && !bch2_snapshot_is_ancestor(c, parent_snapshot, d.k->p.snapshot),
1788                         c, dirent_not_visible_in_parent_subvol,
1789                         "dirent not visible in parent_subvol (not an ancestor of subvol snap %u)\n%s",
1790                         parent_snapshot,
1791                         (bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf))) {
1792                 u32 new_parent_subvol;
1793                 ret = find_snapshot_subvol(trans, d.k->p.snapshot, &new_parent_subvol);
1794                 if (ret)
1795                         goto err;
1796
1797                 struct bkey_i_dirent *new_dirent = bch2_bkey_make_mut_typed(trans, iter, &d.s_c, 0, dirent);
1798                 ret = PTR_ERR_OR_ZERO(new_dirent);
1799                 if (ret)
1800                         goto err;
1801
1802                 new_dirent->v.d_parent_subvol = cpu_to_le32(new_parent_subvol);
1803         }
1804
1805         struct bkey_s_c_subvolume s =
1806                 bch2_bkey_get_iter_typed(trans, &subvol_iter,
1807                                          BTREE_ID_subvolumes, POS(0, target_subvol),
1808                                          0, subvolume);
1809         ret = bkey_err(s.s_c);
1810         if (ret && !bch2_err_matches(ret, ENOENT))
1811                 return ret;
1812
1813         if (ret) {
1814                 if (fsck_err(c, dirent_to_missing_subvol,
1815                              "dirent points to missing subvolume\n%s",
1816                              (bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf)))
1817                         return __remove_dirent(trans, d.k->p);
1818                 ret = 0;
1819                 goto out;
1820         }
1821
1822         if (fsck_err_on(le32_to_cpu(s.v->fs_path_parent) != parent_subvol,
1823                         c, subvol_fs_path_parent_wrong,
1824                         "subvol with wrong fs_path_parent, should be be %u\n%s",
1825                         parent_subvol,
1826                         (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
1827                 struct bkey_i_subvolume *n =
1828                         bch2_bkey_make_mut_typed(trans, &subvol_iter, &s.s_c, 0, subvolume);
1829                 ret = PTR_ERR_OR_ZERO(n);
1830                 if (ret)
1831                         goto err;
1832
1833                 n->v.fs_path_parent = cpu_to_le32(parent_subvol);
1834         }
1835
1836         u64 target_inum = le64_to_cpu(s.v->inode);
1837         u32 target_snapshot = le32_to_cpu(s.v->snapshot);
1838
1839         ret = lookup_inode(trans, target_inum, &subvol_root, &target_snapshot);
1840         if (ret && !bch2_err_matches(ret, ENOENT))
1841                 return ret;
1842
1843         if (fsck_err_on(parent_subvol != subvol_root.bi_parent_subvol,
1844                         c, inode_bi_parent_wrong,
1845                         "subvol root %llu has wrong bi_parent_subvol: got %u, should be %u",
1846                         target_inum,
1847                         subvol_root.bi_parent_subvol, parent_subvol)) {
1848                 subvol_root.bi_parent_subvol = parent_subvol;
1849                 ret = __bch2_fsck_write_inode(trans, &subvol_root, target_snapshot);
1850                 if (ret)
1851                         return ret;
1852         }
1853
1854         ret = check_dirent_target(trans, iter, d, &subvol_root,
1855                                   target_snapshot);
1856         if (ret)
1857                 return ret;
1858 out:
1859 err:
1860 fsck_err:
1861         bch2_trans_iter_exit(trans, &subvol_iter);
1862         printbuf_exit(&buf);
1863         return ret;
1864 }
1865
1866 static int check_dirent(struct btree_trans *trans, struct btree_iter *iter,
1867                         struct bkey_s_c k,
1868                         struct bch_hash_info *hash_info,
1869                         struct inode_walker *dir,
1870                         struct inode_walker *target,
1871                         struct snapshots_seen *s)
1872 {
1873         struct bch_fs *c = trans->c;
1874         struct bkey_s_c_dirent d;
1875         struct inode_walker_entry *i;
1876         struct printbuf buf = PRINTBUF;
1877         struct bpos equiv;
1878         int ret = 0;
1879
1880         ret = check_key_has_snapshot(trans, iter, k);
1881         if (ret) {
1882                 ret = ret < 0 ? ret : 0;
1883                 goto out;
1884         }
1885
1886         equiv = k.k->p;
1887         equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot);
1888
1889         ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p);
1890         if (ret)
1891                 goto err;
1892
1893         if (k.k->type == KEY_TYPE_whiteout)
1894                 goto out;
1895
1896         if (dir->last_pos.inode != k.k->p.inode) {
1897                 ret = check_subdir_count(trans, dir);
1898                 if (ret)
1899                         goto err;
1900         }
1901
1902         BUG_ON(!btree_iter_path(trans, iter)->should_be_locked);
1903
1904         i = walk_inode(trans, dir, k);
1905         ret = PTR_ERR_OR_ZERO(i);
1906         if (ret < 0)
1907                 goto err;
1908
1909         if (dir->first_this_inode && dir->inodes.nr)
1910                 *hash_info = bch2_hash_info_init(c, &dir->inodes.data[0].inode);
1911         dir->first_this_inode = false;
1912
1913         if (fsck_err_on(!i, c, dirent_in_missing_dir_inode,
1914                         "dirent in nonexisting directory:\n%s",
1915                         (printbuf_reset(&buf),
1916                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1917                 ret = bch2_btree_delete_at(trans, iter,
1918                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1919                 goto out;
1920         }
1921
1922         if (!i)
1923                 goto out;
1924
1925         if (fsck_err_on(!S_ISDIR(i->inode.bi_mode),
1926                         c, dirent_in_non_dir_inode,
1927                         "dirent in non directory inode type %s:\n%s",
1928                         bch2_d_type_str(inode_d_type(&i->inode)),
1929                         (printbuf_reset(&buf),
1930                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1931                 ret = bch2_btree_delete_at(trans, iter, 0);
1932                 goto out;
1933         }
1934
1935         ret = hash_check_key(trans, bch2_dirent_hash_desc, hash_info, iter, k);
1936         if (ret < 0)
1937                 goto err;
1938         if (ret) {
1939                 /* dirent has been deleted */
1940                 ret = 0;
1941                 goto out;
1942         }
1943
1944         if (k.k->type != KEY_TYPE_dirent)
1945                 goto out;
1946
1947         d = bkey_s_c_to_dirent(k);
1948
1949         if (d.v->d_type == DT_SUBVOL) {
1950                 ret = check_dirent_to_subvol(trans, iter, d);
1951                 if (ret)
1952                         goto err;
1953         } else {
1954                 ret = __get_visible_inodes(trans, target, s, le64_to_cpu(d.v->d_inum));
1955                 if (ret)
1956                         goto err;
1957
1958                 if (fsck_err_on(!target->inodes.nr,
1959                                 c, dirent_to_missing_inode,
1960                                 "dirent points to missing inode: (equiv %u)\n%s",
1961                                 equiv.snapshot,
1962                                 (printbuf_reset(&buf),
1963                                  bch2_bkey_val_to_text(&buf, c, k),
1964                                  buf.buf))) {
1965                         ret = __remove_dirent(trans, d.k->p);
1966                         if (ret)
1967                                 goto err;
1968                 }
1969
1970                 darray_for_each(target->inodes, i) {
1971                         ret = check_dirent_target(trans, iter, d,
1972                                                   &i->inode, i->snapshot);
1973                         if (ret)
1974                                 goto err;
1975                 }
1976
1977                 if (d.v->d_type == DT_DIR)
1978                         for_each_visible_inode(c, s, dir, equiv.snapshot, i)
1979                                 i->count++;
1980         }
1981 out:
1982 err:
1983 fsck_err:
1984         printbuf_exit(&buf);
1985         bch_err_fn(c, ret);
1986         return ret;
1987 }
1988
1989 /*
1990  * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
1991  * validate d_type
1992  */
1993 int bch2_check_dirents(struct bch_fs *c)
1994 {
1995         struct inode_walker dir = inode_walker_init();
1996         struct inode_walker target = inode_walker_init();
1997         struct snapshots_seen s;
1998         struct bch_hash_info hash_info;
1999
2000         snapshots_seen_init(&s);
2001
2002         int ret = bch2_trans_run(c,
2003                 for_each_btree_key_commit(trans, iter, BTREE_ID_dirents,
2004                                 POS(BCACHEFS_ROOT_INO, 0),
2005                                 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS,
2006                                 k,
2007                                 NULL, NULL,
2008                                 BCH_TRANS_COMMIT_no_enospc,
2009                         check_dirent(trans, &iter, k, &hash_info, &dir, &target, &s)));
2010
2011         snapshots_seen_exit(&s);
2012         inode_walker_exit(&dir);
2013         inode_walker_exit(&target);
2014         bch_err_fn(c, ret);
2015         return ret;
2016 }
2017
2018 static int check_xattr(struct btree_trans *trans, struct btree_iter *iter,
2019                        struct bkey_s_c k,
2020                        struct bch_hash_info *hash_info,
2021                        struct inode_walker *inode)
2022 {
2023         struct bch_fs *c = trans->c;
2024         struct inode_walker_entry *i;
2025         int ret;
2026
2027         ret = check_key_has_snapshot(trans, iter, k);
2028         if (ret)
2029                 return ret;
2030
2031         i = walk_inode(trans, inode, k);
2032         ret = PTR_ERR_OR_ZERO(i);
2033         if (ret)
2034                 return ret;
2035
2036         if (inode->first_this_inode && inode->inodes.nr)
2037                 *hash_info = bch2_hash_info_init(c, &inode->inodes.data[0].inode);
2038         inode->first_this_inode = false;
2039
2040         if (fsck_err_on(!i, c, xattr_in_missing_inode,
2041                         "xattr for missing inode %llu",
2042                         k.k->p.inode))
2043                 return bch2_btree_delete_at(trans, iter, 0);
2044
2045         if (!i)
2046                 return 0;
2047
2048         ret = hash_check_key(trans, bch2_xattr_hash_desc, hash_info, iter, k);
2049 fsck_err:
2050         bch_err_fn(c, ret);
2051         return ret;
2052 }
2053
2054 /*
2055  * Walk xattrs: verify that they all have a corresponding inode
2056  */
2057 int bch2_check_xattrs(struct bch_fs *c)
2058 {
2059         struct inode_walker inode = inode_walker_init();
2060         struct bch_hash_info hash_info;
2061         int ret = 0;
2062
2063         ret = bch2_trans_run(c,
2064                 for_each_btree_key_commit(trans, iter, BTREE_ID_xattrs,
2065                         POS(BCACHEFS_ROOT_INO, 0),
2066                         BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS,
2067                         k,
2068                         NULL, NULL,
2069                         BCH_TRANS_COMMIT_no_enospc,
2070                 check_xattr(trans, &iter, k, &hash_info, &inode)));
2071         bch_err_fn(c, ret);
2072         return ret;
2073 }
2074
2075 static int check_root_trans(struct btree_trans *trans)
2076 {
2077         struct bch_fs *c = trans->c;
2078         struct bch_inode_unpacked root_inode;
2079         u32 snapshot;
2080         u64 inum;
2081         int ret;
2082
2083         ret = subvol_lookup(trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum);
2084         if (ret && !bch2_err_matches(ret, ENOENT))
2085                 return ret;
2086
2087         if (mustfix_fsck_err_on(ret, c, root_subvol_missing,
2088                                 "root subvol missing")) {
2089                 struct bkey_i_subvolume root_subvol;
2090
2091                 snapshot        = U32_MAX;
2092                 inum            = BCACHEFS_ROOT_INO;
2093
2094                 bkey_subvolume_init(&root_subvol.k_i);
2095                 root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL;
2096                 root_subvol.v.flags     = 0;
2097                 root_subvol.v.snapshot  = cpu_to_le32(snapshot);
2098                 root_subvol.v.inode     = cpu_to_le64(inum);
2099                 ret = bch2_btree_insert_trans(trans, BTREE_ID_subvolumes, &root_subvol.k_i, 0);
2100                 bch_err_msg(c, ret, "writing root subvol");
2101                 if (ret)
2102                         goto err;
2103         }
2104
2105         ret = lookup_inode(trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot);
2106         if (ret && !bch2_err_matches(ret, ENOENT))
2107                 return ret;
2108
2109         if (mustfix_fsck_err_on(ret, c, root_dir_missing,
2110                                 "root directory missing") ||
2111             mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode),
2112                                 c, root_inode_not_dir,
2113                                 "root inode not a directory")) {
2114                 bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755,
2115                                 0, NULL);
2116                 root_inode.bi_inum = inum;
2117
2118                 ret = __bch2_fsck_write_inode(trans, &root_inode, snapshot);
2119                 bch_err_msg(c, ret, "writing root inode");
2120         }
2121 err:
2122 fsck_err:
2123         return ret;
2124 }
2125
2126 /* Get root directory, create if it doesn't exist: */
2127 int bch2_check_root(struct bch_fs *c)
2128 {
2129         int ret = bch2_trans_do(c, NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
2130                 check_root_trans(trans));
2131         bch_err_fn(c, ret);
2132         return ret;
2133 }
2134
2135 typedef DARRAY(u32) darray_u32;
2136
2137 static bool darray_u32_has(darray_u32 *d, u32 v)
2138 {
2139         darray_for_each(*d, i)
2140                 if (*i == v)
2141                         return true;
2142         return false;
2143 }
2144
2145 /*
2146  * We've checked that inode backpointers point to valid dirents; here, it's
2147  * sufficient to check that the subvolume root has a dirent:
2148  */
2149 static int subvol_has_dirent(struct btree_trans *trans, struct bkey_s_c_subvolume s)
2150 {
2151         struct bch_inode_unpacked inode;
2152         int ret = bch2_inode_find_by_inum_trans(trans,
2153                                 (subvol_inum) { s.k->p.offset, le64_to_cpu(s.v->inode) },
2154                                 &inode);
2155         if (ret)
2156                 return ret;
2157
2158         return inode.bi_dir != 0;
2159 }
2160
2161 static int check_subvol_path(struct btree_trans *trans, struct btree_iter *iter, struct bkey_s_c k)
2162 {
2163         struct bch_fs *c = trans->c;
2164         struct btree_iter parent_iter = {};
2165         darray_u32 subvol_path = {};
2166         struct printbuf buf = PRINTBUF;
2167         int ret = 0;
2168
2169         if (k.k->type != KEY_TYPE_subvolume)
2170                 return 0;
2171
2172         while (k.k->p.offset != BCACHEFS_ROOT_SUBVOL) {
2173                 ret = darray_push(&subvol_path, k.k->p.offset);
2174                 if (ret)
2175                         goto err;
2176
2177                 struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
2178
2179                 ret = subvol_has_dirent(trans, s);
2180                 if (ret < 0)
2181                         break;
2182
2183                 if (fsck_err_on(!ret,
2184                                 c, subvol_unreachable,
2185                                 "unreachable subvolume %s",
2186                                 (bch2_bkey_val_to_text(&buf, c, s.s_c),
2187                                  buf.buf))) {
2188                         ret = reattach_subvol(trans, s);
2189                         break;
2190                 }
2191
2192                 u32 parent = le32_to_cpu(s.v->fs_path_parent);
2193
2194                 if (darray_u32_has(&subvol_path, parent)) {
2195                         if (fsck_err(c, subvol_loop, "subvolume loop"))
2196                                 ret = reattach_subvol(trans, s);
2197                         break;
2198                 }
2199
2200                 bch2_trans_iter_exit(trans, &parent_iter);
2201                 bch2_trans_iter_init(trans, &parent_iter,
2202                                      BTREE_ID_subvolumes, POS(0, parent), 0);
2203                 k = bch2_btree_iter_peek_slot(&parent_iter);
2204                 ret = bkey_err(k);
2205                 if (ret)
2206                         goto err;
2207
2208                 if (fsck_err_on(k.k->type != KEY_TYPE_subvolume,
2209                                 c, subvol_unreachable,
2210                                 "unreachable subvolume %s",
2211                                 (bch2_bkey_val_to_text(&buf, c, s.s_c),
2212                                  buf.buf))) {
2213                         ret = reattach_subvol(trans, s);
2214                         break;
2215                 }
2216         }
2217 fsck_err:
2218 err:
2219         printbuf_exit(&buf);
2220         darray_exit(&subvol_path);
2221         bch2_trans_iter_exit(trans, &parent_iter);
2222         return ret;
2223 }
2224
2225 int bch2_check_subvolume_structure(struct bch_fs *c)
2226 {
2227         int ret = bch2_trans_run(c,
2228                 for_each_btree_key_commit(trans, iter,
2229                                 BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
2230                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
2231                         check_subvol_path(trans, &iter, k)));
2232         bch_err_fn(c, ret);
2233         return ret;
2234 }
2235
2236 struct pathbuf_entry {
2237         u64     inum;
2238         u32     snapshot;
2239 };
2240
2241 typedef DARRAY(struct pathbuf_entry) pathbuf;
2242
2243 static bool path_is_dup(pathbuf *p, u64 inum, u32 snapshot)
2244 {
2245         darray_for_each(*p, i)
2246                 if (i->inum     == inum &&
2247                     i->snapshot == snapshot)
2248                         return true;
2249         return false;
2250 }
2251
2252 /*
2253  * Check that a given inode is reachable from its subvolume root - we already
2254  * verified subvolume connectivity:
2255  *
2256  * XXX: we should also be verifying that inodes are in the right subvolumes
2257  */
2258 static int check_path(struct btree_trans *trans, pathbuf *p, struct bkey_s_c inode_k)
2259 {
2260         struct bch_fs *c = trans->c;
2261         struct btree_iter inode_iter = {};
2262         struct bch_inode_unpacked inode;
2263         struct printbuf buf = PRINTBUF;
2264         u32 snapshot = bch2_snapshot_equiv(c, inode_k.k->p.snapshot);
2265         int ret = 0;
2266
2267         p->nr = 0;
2268
2269         BUG_ON(bch2_inode_unpack(inode_k, &inode));
2270
2271         while (!inode.bi_subvol) {
2272                 struct btree_iter dirent_iter;
2273                 struct bkey_s_c_dirent d;
2274                 u32 parent_snapshot = snapshot;
2275
2276                 d = inode_get_dirent(trans, &dirent_iter, &inode, &parent_snapshot);
2277                 ret = bkey_err(d.s_c);
2278                 if (ret && !bch2_err_matches(ret, ENOENT))
2279                         break;
2280
2281                 if (!ret && !dirent_points_to_inode(d, &inode)) {
2282                         bch2_trans_iter_exit(trans, &dirent_iter);
2283                         ret = -BCH_ERR_ENOENT_dirent_doesnt_match_inode;
2284                 }
2285
2286                 if (bch2_err_matches(ret, ENOENT)) {
2287                         ret = 0;
2288                         if (fsck_err(c, inode_unreachable,
2289                                      "unreachable inode\n%s",
2290                                      (printbuf_reset(&buf),
2291                                       bch2_bkey_val_to_text(&buf, c, inode_k),
2292                                       buf.buf)))
2293                                 ret = reattach_inode(trans, &inode, snapshot);
2294                         goto out;
2295                 }
2296
2297                 bch2_trans_iter_exit(trans, &dirent_iter);
2298
2299                 if (!S_ISDIR(inode.bi_mode))
2300                         break;
2301
2302                 ret = darray_push(p, ((struct pathbuf_entry) {
2303                         .inum           = inode.bi_inum,
2304                         .snapshot       = snapshot,
2305                 }));
2306                 if (ret)
2307                         return ret;
2308
2309                 snapshot = parent_snapshot;
2310
2311                 bch2_trans_iter_exit(trans, &inode_iter);
2312                 inode_k = bch2_bkey_get_iter(trans, &inode_iter, BTREE_ID_inodes,
2313                                              SPOS(0, inode.bi_dir, snapshot), 0);
2314                 ret = bkey_err(inode_k) ?:
2315                         !bkey_is_inode(inode_k.k) ? -BCH_ERR_ENOENT_inode
2316                         : bch2_inode_unpack(inode_k, &inode);
2317                 if (ret) {
2318                         /* Should have been caught in dirents pass */
2319                         if (!bch2_err_matches(ret, BCH_ERR_transaction_restart))
2320                                 bch_err(c, "error looking up parent directory: %i", ret);
2321                         break;
2322                 }
2323
2324                 snapshot = inode_k.k->p.snapshot;
2325
2326                 if (path_is_dup(p, inode.bi_inum, snapshot)) {
2327                         /* XXX print path */
2328                         bch_err(c, "directory structure loop");
2329
2330                         darray_for_each(*p, i)
2331                                 pr_err("%llu:%u", i->inum, i->snapshot);
2332                         pr_err("%llu:%u", inode.bi_inum, snapshot);
2333
2334                         if (fsck_err(c, dir_loop, "directory structure loop")) {
2335                                 ret = remove_backpointer(trans, &inode);
2336                                 bch_err_msg(c, ret, "removing dirent");
2337                                 if (ret)
2338                                         break;
2339
2340                                 ret = reattach_inode(trans, &inode, snapshot);
2341                                 bch_err_msg(c, ret, "reattaching inode %llu", inode.bi_inum);
2342                         }
2343                         break;
2344                 }
2345         }
2346 out:
2347 fsck_err:
2348         bch2_trans_iter_exit(trans, &inode_iter);
2349         printbuf_exit(&buf);
2350         bch_err_fn(c, ret);
2351         return ret;
2352 }
2353
2354 /*
2355  * Check for unreachable inodes, as well as loops in the directory structure:
2356  * After bch2_check_dirents(), if an inode backpointer doesn't exist that means it's
2357  * unreachable:
2358  */
2359 int bch2_check_directory_structure(struct bch_fs *c)
2360 {
2361         pathbuf path = { 0, };
2362         int ret;
2363
2364         ret = bch2_trans_run(c,
2365                 for_each_btree_key_commit(trans, iter, BTREE_ID_inodes, POS_MIN,
2366                                           BTREE_ITER_INTENT|
2367                                           BTREE_ITER_PREFETCH|
2368                                           BTREE_ITER_ALL_SNAPSHOTS, k,
2369                                           NULL, NULL, BCH_TRANS_COMMIT_no_enospc, ({
2370                         if (!bkey_is_inode(k.k))
2371                                 continue;
2372
2373                         if (bch2_inode_flags(k) & BCH_INODE_unlinked)
2374                                 continue;
2375
2376                         check_path(trans, &path, k);
2377                 })));
2378         darray_exit(&path);
2379
2380         bch_err_fn(c, ret);
2381         return ret;
2382 }
2383
2384 struct nlink_table {
2385         size_t          nr;
2386         size_t          size;
2387
2388         struct nlink {
2389                 u64     inum;
2390                 u32     snapshot;
2391                 u32     count;
2392         }               *d;
2393 };
2394
2395 static int add_nlink(struct bch_fs *c, struct nlink_table *t,
2396                      u64 inum, u32 snapshot)
2397 {
2398         if (t->nr == t->size) {
2399                 size_t new_size = max_t(size_t, 128UL, t->size * 2);
2400                 void *d = kvmalloc_array(new_size, sizeof(t->d[0]), GFP_KERNEL);
2401
2402                 if (!d) {
2403                         bch_err(c, "fsck: error allocating memory for nlink_table, size %zu",
2404                                 new_size);
2405                         return -BCH_ERR_ENOMEM_fsck_add_nlink;
2406                 }
2407
2408                 if (t->d)
2409                         memcpy(d, t->d, t->size * sizeof(t->d[0]));
2410                 kvfree(t->d);
2411
2412                 t->d = d;
2413                 t->size = new_size;
2414         }
2415
2416
2417         t->d[t->nr++] = (struct nlink) {
2418                 .inum           = inum,
2419                 .snapshot       = snapshot,
2420         };
2421
2422         return 0;
2423 }
2424
2425 static int nlink_cmp(const void *_l, const void *_r)
2426 {
2427         const struct nlink *l = _l;
2428         const struct nlink *r = _r;
2429
2430         return cmp_int(l->inum, r->inum);
2431 }
2432
2433 static void inc_link(struct bch_fs *c, struct snapshots_seen *s,
2434                      struct nlink_table *links,
2435                      u64 range_start, u64 range_end, u64 inum, u32 snapshot)
2436 {
2437         struct nlink *link, key = {
2438                 .inum = inum, .snapshot = U32_MAX,
2439         };
2440
2441         if (inum < range_start || inum >= range_end)
2442                 return;
2443
2444         link = __inline_bsearch(&key, links->d, links->nr,
2445                                 sizeof(links->d[0]), nlink_cmp);
2446         if (!link)
2447                 return;
2448
2449         while (link > links->d && link[0].inum == link[-1].inum)
2450                 --link;
2451
2452         for (; link < links->d + links->nr && link->inum == inum; link++)
2453                 if (ref_visible(c, s, snapshot, link->snapshot)) {
2454                         link->count++;
2455                         if (link->snapshot >= snapshot)
2456                                 break;
2457                 }
2458 }
2459
2460 noinline_for_stack
2461 static int check_nlinks_find_hardlinks(struct bch_fs *c,
2462                                        struct nlink_table *t,
2463                                        u64 start, u64 *end)
2464 {
2465         int ret = bch2_trans_run(c,
2466                 for_each_btree_key(trans, iter, BTREE_ID_inodes,
2467                                    POS(0, start),
2468                                    BTREE_ITER_INTENT|
2469                                    BTREE_ITER_PREFETCH|
2470                                    BTREE_ITER_ALL_SNAPSHOTS, k, ({
2471                         if (!bkey_is_inode(k.k))
2472                                 continue;
2473
2474                         /* Should never fail, checked by bch2_inode_invalid: */
2475                         struct bch_inode_unpacked u;
2476                         BUG_ON(bch2_inode_unpack(k, &u));
2477
2478                         /*
2479                          * Backpointer and directory structure checks are sufficient for
2480                          * directories, since they can't have hardlinks:
2481                          */
2482                         if (S_ISDIR(u.bi_mode))
2483                                 continue;
2484
2485                         if (!u.bi_nlink)
2486                                 continue;
2487
2488                         ret = add_nlink(c, t, k.k->p.offset, k.k->p.snapshot);
2489                         if (ret) {
2490                                 *end = k.k->p.offset;
2491                                 ret = 0;
2492                                 break;
2493                         }
2494                         0;
2495                 })));
2496
2497         bch_err_fn(c, ret);
2498         return ret;
2499 }
2500
2501 noinline_for_stack
2502 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
2503                                      u64 range_start, u64 range_end)
2504 {
2505         struct snapshots_seen s;
2506
2507         snapshots_seen_init(&s);
2508
2509         int ret = bch2_trans_run(c,
2510                 for_each_btree_key(trans, iter, BTREE_ID_dirents, POS_MIN,
2511                                    BTREE_ITER_INTENT|
2512                                    BTREE_ITER_PREFETCH|
2513                                    BTREE_ITER_ALL_SNAPSHOTS, k, ({
2514                         ret = snapshots_seen_update(c, &s, iter.btree_id, k.k->p);
2515                         if (ret)
2516                                 break;
2517
2518                         if (k.k->type == KEY_TYPE_dirent) {
2519                                 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);
2520
2521                                 if (d.v->d_type != DT_DIR &&
2522                                     d.v->d_type != DT_SUBVOL)
2523                                         inc_link(c, &s, links, range_start, range_end,
2524                                                  le64_to_cpu(d.v->d_inum),
2525                                                  bch2_snapshot_equiv(c, d.k->p.snapshot));
2526                         }
2527                         0;
2528                 })));
2529
2530         snapshots_seen_exit(&s);
2531
2532         bch_err_fn(c, ret);
2533         return ret;
2534 }
2535
2536 static int check_nlinks_update_inode(struct btree_trans *trans, struct btree_iter *iter,
2537                                      struct bkey_s_c k,
2538                                      struct nlink_table *links,
2539                                      size_t *idx, u64 range_end)
2540 {
2541         struct bch_fs *c = trans->c;
2542         struct bch_inode_unpacked u;
2543         struct nlink *link = &links->d[*idx];
2544         int ret = 0;
2545
2546         if (k.k->p.offset >= range_end)
2547                 return 1;
2548
2549         if (!bkey_is_inode(k.k))
2550                 return 0;
2551
2552         BUG_ON(bch2_inode_unpack(k, &u));
2553
2554         if (S_ISDIR(u.bi_mode))
2555                 return 0;
2556
2557         if (!u.bi_nlink)
2558                 return 0;
2559
2560         while ((cmp_int(link->inum, k.k->p.offset) ?:
2561                 cmp_int(link->snapshot, k.k->p.snapshot)) < 0) {
2562                 BUG_ON(*idx == links->nr);
2563                 link = &links->d[++*idx];
2564         }
2565
2566         if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count,
2567                         c, inode_wrong_nlink,
2568                         "inode %llu type %s has wrong i_nlink (%u, should be %u)",
2569                         u.bi_inum, bch2_d_types[mode_to_type(u.bi_mode)],
2570                         bch2_inode_nlink_get(&u), link->count)) {
2571                 bch2_inode_nlink_set(&u, link->count);
2572                 ret = __bch2_fsck_write_inode(trans, &u, k.k->p.snapshot);
2573         }
2574 fsck_err:
2575         return ret;
2576 }
2577
2578 noinline_for_stack
2579 static int check_nlinks_update_hardlinks(struct bch_fs *c,
2580                                struct nlink_table *links,
2581                                u64 range_start, u64 range_end)
2582 {
2583         size_t idx = 0;
2584
2585         int ret = bch2_trans_run(c,
2586                 for_each_btree_key_commit(trans, iter, BTREE_ID_inodes,
2587                                 POS(0, range_start),
2588                                 BTREE_ITER_INTENT|BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
2589                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
2590                         check_nlinks_update_inode(trans, &iter, k, links, &idx, range_end)));
2591         if (ret < 0) {
2592                 bch_err(c, "error in fsck walking inodes: %s", bch2_err_str(ret));
2593                 return ret;
2594         }
2595
2596         return 0;
2597 }
2598
2599 int bch2_check_nlinks(struct bch_fs *c)
2600 {
2601         struct nlink_table links = { 0 };
2602         u64 this_iter_range_start, next_iter_range_start = 0;
2603         int ret = 0;
2604
2605         do {
2606                 this_iter_range_start = next_iter_range_start;
2607                 next_iter_range_start = U64_MAX;
2608
2609                 ret = check_nlinks_find_hardlinks(c, &links,
2610                                                   this_iter_range_start,
2611                                                   &next_iter_range_start);
2612
2613                 ret = check_nlinks_walk_dirents(c, &links,
2614                                           this_iter_range_start,
2615                                           next_iter_range_start);
2616                 if (ret)
2617                         break;
2618
2619                 ret = check_nlinks_update_hardlinks(c, &links,
2620                                          this_iter_range_start,
2621                                          next_iter_range_start);
2622                 if (ret)
2623                         break;
2624
2625                 links.nr = 0;
2626         } while (next_iter_range_start != U64_MAX);
2627
2628         kvfree(links.d);
2629         bch_err_fn(c, ret);
2630         return ret;
2631 }
2632
2633 static int fix_reflink_p_key(struct btree_trans *trans, struct btree_iter *iter,
2634                              struct bkey_s_c k)
2635 {
2636         struct bkey_s_c_reflink_p p;
2637         struct bkey_i_reflink_p *u;
2638
2639         if (k.k->type != KEY_TYPE_reflink_p)
2640                 return 0;
2641
2642         p = bkey_s_c_to_reflink_p(k);
2643
2644         if (!p.v->front_pad && !p.v->back_pad)
2645                 return 0;
2646
2647         u = bch2_trans_kmalloc(trans, sizeof(*u));
2648         int ret = PTR_ERR_OR_ZERO(u);
2649         if (ret)
2650                 return ret;
2651
2652         bkey_reassemble(&u->k_i, k);
2653         u->v.front_pad  = 0;
2654         u->v.back_pad   = 0;
2655
2656         return bch2_trans_update(trans, iter, &u->k_i, BTREE_TRIGGER_NORUN);
2657 }
2658
2659 int bch2_fix_reflink_p(struct bch_fs *c)
2660 {
2661         if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix)
2662                 return 0;
2663
2664         int ret = bch2_trans_run(c,
2665                 for_each_btree_key_commit(trans, iter,
2666                                 BTREE_ID_extents, POS_MIN,
2667                                 BTREE_ITER_INTENT|BTREE_ITER_PREFETCH|
2668                                 BTREE_ITER_ALL_SNAPSHOTS, k,
2669                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
2670                         fix_reflink_p_key(trans, &iter, k)));
2671         bch_err_fn(c, ret);
2672         return ret;
2673 }