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