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