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 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 static int check_inodes(struct bch_fs *c, bool full)
1012 {
1013         struct btree_trans trans;
1014         struct btree_iter iter;
1015         struct bch_inode_unpacked prev = { 0 };
1016         struct snapshots_seen s;
1017         struct bkey_s_c k;
1018         int ret;
1019
1020         snapshots_seen_init(&s);
1021         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1022
1023         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_inodes,
1024                         POS_MIN,
1025                         BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1026                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
1027                 check_inode(&trans, &iter, k, &prev, &s, full));
1028
1029         bch2_trans_exit(&trans);
1030         snapshots_seen_exit(&s);
1031         if (ret)
1032                 bch_err_fn(c, ret);
1033         return ret;
1034 }
1035
1036 /*
1037  * Checking for overlapping extents needs to be reimplemented
1038  */
1039 #if 0
1040 static int fix_overlapping_extent(struct btree_trans *trans,
1041                                        struct bkey_s_c k, struct bpos cut_at)
1042 {
1043         struct btree_iter iter;
1044         struct bkey_i *u;
1045         int ret;
1046
1047         u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1048         ret = PTR_ERR_OR_ZERO(u);
1049         if (ret)
1050                 return ret;
1051
1052         bkey_reassemble(u, k);
1053         bch2_cut_front(cut_at, u);
1054
1055
1056         /*
1057          * We don't want to go through the extent_handle_overwrites path:
1058          *
1059          * XXX: this is going to screw up disk accounting, extent triggers
1060          * assume things about extent overwrites - we should be running the
1061          * triggers manually here
1062          */
1063         bch2_trans_iter_init(trans, &iter, BTREE_ID_extents, u->k.p,
1064                              BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
1065
1066         BUG_ON(iter.flags & BTREE_ITER_IS_EXTENTS);
1067         ret   = bch2_btree_iter_traverse(&iter) ?:
1068                 bch2_trans_update(trans, &iter, u, BTREE_TRIGGER_NORUN) ?:
1069                 bch2_trans_commit(trans, NULL, NULL,
1070                                   BTREE_INSERT_NOFAIL|
1071                                   BTREE_INSERT_LAZY_RW);
1072         bch2_trans_iter_exit(trans, &iter);
1073         return ret;
1074 }
1075 #endif
1076
1077 static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans,
1078                                                 struct btree_iter *iter,
1079                                                 struct bpos pos)
1080 {
1081         return bch2_bkey_get_iter_typed(trans, iter, BTREE_ID_dirents, pos, 0, dirent);
1082 }
1083
1084 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode,
1085                                    struct bkey_s_c_dirent d)
1086 {
1087         return  inode->bi_dir           == d.k->p.inode &&
1088                 inode->bi_dir_offset    == d.k->p.offset;
1089 }
1090
1091 static bool dirent_points_to_inode(struct bkey_s_c_dirent d,
1092                                    struct bch_inode_unpacked *inode)
1093 {
1094         return d.v->d_type == DT_SUBVOL
1095                 ? le32_to_cpu(d.v->d_child_subvol)      == inode->bi_subvol
1096                 : le64_to_cpu(d.v->d_inum)              == inode->bi_inum;
1097 }
1098
1099 static int inode_backpointer_exists(struct btree_trans *trans,
1100                                     struct bch_inode_unpacked *inode,
1101                                     u32 snapshot)
1102 {
1103         struct btree_iter iter;
1104         struct bkey_s_c_dirent d;
1105         int ret;
1106
1107         d = dirent_get_by_pos(trans, &iter,
1108                         SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot));
1109         ret = bkey_err(d);
1110         if (ret)
1111                 return bch2_err_matches(ret, ENOENT) ? 0 : ret;
1112
1113         ret = dirent_points_to_inode(d, inode);
1114         bch2_trans_iter_exit(trans, &iter);
1115         return ret;
1116 }
1117
1118 static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w)
1119 {
1120         struct bch_fs *c = trans->c;
1121         struct inode_walker_entry *i;
1122         u32 restart_count = trans->restart_count;
1123         int ret = 0;
1124         s64 count2;
1125
1126         darray_for_each(w->inodes, i) {
1127                 if (i->inode.bi_sectors == i->count)
1128                         continue;
1129
1130                 count2 = bch2_count_inode_sectors(trans, w->cur_inum, i->snapshot);
1131
1132                 if (i->count != count2) {
1133                         bch_err(c, "fsck counted i_sectors wrong: got %llu should be %llu",
1134                                 i->count, count2);
1135                         i->count = count2;
1136                         if (i->inode.bi_sectors == i->count)
1137                                 continue;
1138                 }
1139
1140                 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY), c,
1141                             "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu",
1142                             w->cur_inum, i->snapshot,
1143                             i->inode.bi_sectors, i->count)) {
1144                         i->inode.bi_sectors = i->count;
1145                         ret = write_inode(trans, &i->inode, i->snapshot);
1146                         if (ret)
1147                                 break;
1148                 }
1149         }
1150 fsck_err:
1151         if (ret)
1152                 bch_err_fn(c, ret);
1153         if (!ret && trans_was_restarted(trans, restart_count))
1154                 ret = -BCH_ERR_transaction_restart_nested;
1155         return ret;
1156 }
1157
1158 struct extent_end {
1159         u32                     snapshot;
1160         u64                     offset;
1161         struct snapshots_seen   seen;
1162 };
1163
1164 typedef DARRAY(struct extent_end) extent_ends;
1165
1166 static int get_print_extent(struct btree_trans *trans, struct bpos pos, struct printbuf *out)
1167 {
1168         struct btree_iter iter;
1169         struct bkey_s_c k;
1170         int ret;
1171
1172         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_extents, pos,
1173                                BTREE_ITER_SLOTS|
1174                                BTREE_ITER_ALL_SNAPSHOTS|
1175                                BTREE_ITER_NOT_EXTENTS);
1176         ret = bkey_err(k);
1177         if (ret)
1178                 return ret;
1179
1180         bch2_bkey_val_to_text(out, trans->c, k);
1181         bch2_trans_iter_exit(trans, &iter);
1182         return 0;
1183 }
1184
1185 static int check_overlapping_extents(struct btree_trans *trans,
1186                               struct snapshots_seen *seen,
1187                               extent_ends *extent_ends,
1188                               struct bkey_s_c k,
1189                               struct btree_iter *iter)
1190 {
1191         struct bch_fs *c = trans->c;
1192         struct extent_end *i;
1193         struct printbuf buf = PRINTBUF;
1194         int ret = 0;
1195
1196         darray_for_each(*extent_ends, i) {
1197                 /* duplicate, due to transaction restart: */
1198                 if (i->offset   == k.k->p.offset &&
1199                     i->snapshot == k.k->p.snapshot)
1200                         continue;
1201
1202                 if (!ref_visible2(c,
1203                                   k.k->p.snapshot, seen,
1204                                   i->snapshot, &i->seen))
1205                         continue;
1206
1207                 if (i->offset <= bkey_start_offset(k.k))
1208                         continue;
1209
1210                 printbuf_reset(&buf);
1211                 prt_str(&buf, "overlapping extents:\n  ");
1212                 bch2_bkey_val_to_text(&buf, c, k);
1213                 prt_str(&buf, "\n  ");
1214
1215                 ret = get_print_extent(trans, SPOS(k.k->p.inode, i->offset, i->snapshot), &buf);
1216                 if (ret)
1217                         break;
1218
1219                 if (fsck_err(c, "%s", buf.buf)) {
1220                         struct bkey_i *update = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1221                         if ((ret = PTR_ERR_OR_ZERO(update)))
1222                                 goto err;
1223                         bkey_reassemble(update, k);
1224                         ret = bch2_trans_update_extent(trans, iter, update,
1225                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1226                         if (ret)
1227                                 goto err;
1228                 }
1229         }
1230 err:
1231 fsck_err:
1232         printbuf_exit(&buf);
1233         return ret;
1234 }
1235
1236 static int extent_ends_at(extent_ends *extent_ends,
1237                           struct snapshots_seen *seen,
1238                           struct bkey_s_c k)
1239 {
1240         struct extent_end *i, n = (struct extent_end) {
1241                 .snapshot       = k.k->p.snapshot,
1242                 .offset         = k.k->p.offset,
1243                 .seen           = *seen,
1244         };
1245
1246         n.seen.ids.data = kmemdup(seen->ids.data,
1247                               sizeof(seen->ids.data[0]) * seen->ids.size,
1248                               GFP_KERNEL);
1249         if (!n.seen.ids.data)
1250                 return -BCH_ERR_ENOMEM_fsck_extent_ends_at;
1251
1252         darray_for_each(*extent_ends, i) {
1253                 if (i->snapshot == k.k->p.snapshot) {
1254                         snapshots_seen_exit(&i->seen);
1255                         *i = n;
1256                         return 0;
1257                 }
1258
1259                 if (i->snapshot >= k.k->p.snapshot)
1260                         break;
1261         }
1262
1263         return darray_insert_item(extent_ends, i - extent_ends->data, n);
1264 }
1265
1266 static void extent_ends_reset(extent_ends *extent_ends)
1267 {
1268         struct extent_end *i;
1269
1270         darray_for_each(*extent_ends, i)
1271                 snapshots_seen_exit(&i->seen);
1272
1273         extent_ends->nr = 0;
1274 }
1275
1276 static int check_extent(struct btree_trans *trans, struct btree_iter *iter,
1277                         struct bkey_s_c k,
1278                         struct inode_walker *inode,
1279                         struct snapshots_seen *s,
1280                         extent_ends *extent_ends)
1281 {
1282         struct bch_fs *c = trans->c;
1283         struct inode_walker_entry *i;
1284         struct printbuf buf = PRINTBUF;
1285         struct bpos equiv;
1286         int ret = 0;
1287
1288         ret = check_key_has_snapshot(trans, iter, k);
1289         if (ret) {
1290                 ret = ret < 0 ? ret : 0;
1291                 goto out;
1292         }
1293
1294         equiv = k.k->p;
1295         equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot);
1296
1297         ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p);
1298         if (ret)
1299                 goto err;
1300
1301         if (k.k->type == KEY_TYPE_whiteout)
1302                 goto out;
1303
1304         if (inode->cur_inum != k.k->p.inode) {
1305                 ret = check_i_sectors(trans, inode);
1306                 if (ret)
1307                         goto err;
1308
1309                 extent_ends_reset(extent_ends);
1310         }
1311
1312         BUG_ON(!iter->path->should_be_locked);
1313
1314         ret = check_overlapping_extents(trans, s, extent_ends, k, iter);
1315         if (ret)
1316                 goto err;
1317
1318         ret = extent_ends_at(extent_ends, s, k);
1319         if (ret)
1320                 goto err;
1321
1322         i = walk_inode(trans, inode, equiv);
1323         ret = PTR_ERR_OR_ZERO(i);
1324         if (ret)
1325                 goto err;
1326
1327         if (fsck_err_on(!i, c,
1328                         "extent in missing inode:\n  %s",
1329                         (printbuf_reset(&buf),
1330                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1331                 ret = bch2_btree_delete_at(trans, iter,
1332                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1333                 goto out;
1334         }
1335
1336         if (!i)
1337                 goto out;
1338
1339         if (fsck_err_on(!S_ISREG(i->inode.bi_mode) &&
1340                         !S_ISLNK(i->inode.bi_mode), c,
1341                         "extent in non regular inode mode %o:\n  %s",
1342                         i->inode.bi_mode,
1343                         (printbuf_reset(&buf),
1344                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1345                 ret = bch2_btree_delete_at(trans, iter,
1346                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1347                 goto out;
1348         }
1349
1350         /*
1351          * Check inodes in reverse order, from oldest snapshots to newest, so
1352          * that we emit the fewest number of whiteouts necessary:
1353          */
1354         for (i = inode->inodes.data + inode->inodes.nr - 1;
1355              i >= inode->inodes.data;
1356              --i) {
1357                 if (i->snapshot > equiv.snapshot ||
1358                     !key_visible_in_snapshot(c, s, i->snapshot, equiv.snapshot))
1359                         continue;
1360
1361                 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
1362                                 k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9 &&
1363                                 !bkey_extent_is_reservation(k), c,
1364                                 "extent type past end of inode %llu:%u, i_size %llu\n  %s",
1365                                 i->inode.bi_inum, i->snapshot, i->inode.bi_size,
1366                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1367                         struct btree_iter iter2;
1368
1369                         bch2_trans_copy_iter(&iter2, iter);
1370                         bch2_btree_iter_set_snapshot(&iter2, i->snapshot);
1371                         ret =   bch2_btree_iter_traverse(&iter2) ?:
1372                                 bch2_btree_delete_at(trans, &iter2,
1373                                         BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1374                         bch2_trans_iter_exit(trans, &iter2);
1375                         if (ret)
1376                                 goto err;
1377
1378                         if (i->snapshot != equiv.snapshot) {
1379                                 ret = snapshots_seen_add(c, s, i->snapshot);
1380                                 if (ret)
1381                                         goto err;
1382                         }
1383                 }
1384         }
1385
1386         if (bkey_extent_is_allocation(k.k))
1387                 for_each_visible_inode(c, s, inode, equiv.snapshot, i)
1388                         i->count += k.k->size;
1389 #if 0
1390         bch2_bkey_buf_reassemble(&prev, c, k);
1391 #endif
1392
1393 out:
1394 err:
1395 fsck_err:
1396         printbuf_exit(&buf);
1397
1398         if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
1399                 bch_err_fn(c, ret);
1400         return ret;
1401 }
1402
1403 /*
1404  * Walk extents: verify that extents have a corresponding S_ISREG inode, and
1405  * that i_size an i_sectors are consistent
1406  */
1407 noinline_for_stack
1408 static int 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         bch_verbose(c, "checking extents");
1423
1424         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_extents,
1425                         POS(BCACHEFS_ROOT_INO, 0),
1426                         BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1427                         &res, NULL,
1428                         BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, ({
1429                 bch2_disk_reservation_put(c, &res);
1430                 check_extent(&trans, &iter, k, &w, &s, &extent_ends);
1431         }));
1432
1433         bch2_disk_reservation_put(c, &res);
1434         extent_ends_reset(&extent_ends);
1435         darray_exit(&extent_ends);
1436         inode_walker_exit(&w);
1437         bch2_trans_exit(&trans);
1438         snapshots_seen_exit(&s);
1439
1440         if (ret)
1441                 bch_err_fn(c, ret);
1442         return ret;
1443 }
1444
1445 static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w)
1446 {
1447         struct bch_fs *c = trans->c;
1448         struct inode_walker_entry *i;
1449         u32 restart_count = trans->restart_count;
1450         int ret = 0;
1451         s64 count2;
1452
1453         darray_for_each(w->inodes, i) {
1454                 if (i->inode.bi_nlink == i->count)
1455                         continue;
1456
1457                 count2 = bch2_count_subdirs(trans, w->cur_inum, i->snapshot);
1458                 if (count2 < 0)
1459                         return count2;
1460
1461                 if (i->count != count2) {
1462                         bch_err(c, "fsck counted subdirectories wrong: got %llu should be %llu",
1463                                 i->count, count2);
1464                         i->count = count2;
1465                         if (i->inode.bi_nlink == i->count)
1466                                 continue;
1467                 }
1468
1469                 if (fsck_err_on(i->inode.bi_nlink != i->count, c,
1470                                 "directory %llu:%u with wrong i_nlink: got %u, should be %llu",
1471                                 w->cur_inum, i->snapshot, i->inode.bi_nlink, i->count)) {
1472                         i->inode.bi_nlink = i->count;
1473                         ret = write_inode(trans, &i->inode, i->snapshot);
1474                         if (ret)
1475                                 break;
1476                 }
1477         }
1478 fsck_err:
1479         if (ret)
1480                 bch_err_fn(c, ret);
1481         if (!ret && trans_was_restarted(trans, restart_count))
1482                 ret = -BCH_ERR_transaction_restart_nested;
1483         return ret;
1484 }
1485
1486 static int check_dirent_target(struct btree_trans *trans,
1487                                struct btree_iter *iter,
1488                                struct bkey_s_c_dirent d,
1489                                struct bch_inode_unpacked *target,
1490                                u32 target_snapshot)
1491 {
1492         struct bch_fs *c = trans->c;
1493         struct bkey_i_dirent *n;
1494         bool backpointer_exists = true;
1495         struct printbuf buf = PRINTBUF;
1496         int ret = 0;
1497
1498         if (!target->bi_dir &&
1499             !target->bi_dir_offset) {
1500                 target->bi_dir          = d.k->p.inode;
1501                 target->bi_dir_offset   = d.k->p.offset;
1502
1503                 ret = __write_inode(trans, target, target_snapshot);
1504                 if (ret)
1505                         goto err;
1506         }
1507
1508         if (!inode_points_to_dirent(target, d)) {
1509                 ret = inode_backpointer_exists(trans, target, d.k->p.snapshot);
1510                 if (ret < 0)
1511                         goto err;
1512
1513                 backpointer_exists = ret;
1514                 ret = 0;
1515
1516                 if (fsck_err_on(S_ISDIR(target->bi_mode) &&
1517                                 backpointer_exists, c,
1518                                 "directory %llu with multiple links",
1519                                 target->bi_inum)) {
1520                         ret = __remove_dirent(trans, d.k->p);
1521                         goto out;
1522                 }
1523
1524                 if (fsck_err_on(backpointer_exists &&
1525                                 !target->bi_nlink, c,
1526                                 "inode %llu type %s has multiple links but i_nlink 0",
1527                                 target->bi_inum, bch2_d_types[d.v->d_type])) {
1528                         target->bi_nlink++;
1529                         target->bi_flags &= ~BCH_INODE_UNLINKED;
1530
1531                         ret = __write_inode(trans, target, target_snapshot);
1532                         if (ret)
1533                                 goto err;
1534                 }
1535
1536                 if (fsck_err_on(!backpointer_exists, c,
1537                                 "inode %llu:%u has wrong backpointer:\n"
1538                                 "got       %llu:%llu\n"
1539                                 "should be %llu:%llu",
1540                                 target->bi_inum, target_snapshot,
1541                                 target->bi_dir,
1542                                 target->bi_dir_offset,
1543                                 d.k->p.inode,
1544                                 d.k->p.offset)) {
1545                         target->bi_dir          = d.k->p.inode;
1546                         target->bi_dir_offset   = d.k->p.offset;
1547
1548                         ret = __write_inode(trans, target, target_snapshot);
1549                         if (ret)
1550                                 goto err;
1551                 }
1552         }
1553
1554         if (fsck_err_on(d.v->d_type != inode_d_type(target), c,
1555                         "incorrect d_type: got %s, should be %s:\n%s",
1556                         bch2_d_type_str(d.v->d_type),
1557                         bch2_d_type_str(inode_d_type(target)),
1558                         (printbuf_reset(&buf),
1559                          bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf))) {
1560                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1561                 ret = PTR_ERR_OR_ZERO(n);
1562                 if (ret)
1563                         goto err;
1564
1565                 bkey_reassemble(&n->k_i, d.s_c);
1566                 n->v.d_type = inode_d_type(target);
1567
1568                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1569                 if (ret)
1570                         goto err;
1571
1572                 d = dirent_i_to_s_c(n);
1573         }
1574
1575         if (d.v->d_type == DT_SUBVOL &&
1576             target->bi_parent_subvol != le32_to_cpu(d.v->d_parent_subvol) &&
1577             (c->sb.version < bcachefs_metadata_version_subvol_dirent ||
1578              fsck_err(c, "dirent has wrong d_parent_subvol field: got %u, should be %u",
1579                       le32_to_cpu(d.v->d_parent_subvol),
1580                       target->bi_parent_subvol))) {
1581                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1582                 ret = PTR_ERR_OR_ZERO(n);
1583                 if (ret)
1584                         goto err;
1585
1586                 bkey_reassemble(&n->k_i, d.s_c);
1587                 n->v.d_parent_subvol = cpu_to_le32(target->bi_parent_subvol);
1588
1589                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1590                 if (ret)
1591                         goto err;
1592
1593                 d = dirent_i_to_s_c(n);
1594         }
1595 out:
1596 err:
1597 fsck_err:
1598         printbuf_exit(&buf);
1599
1600         if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
1601                 bch_err_fn(c, ret);
1602         return ret;
1603 }
1604
1605 static int check_dirent(struct btree_trans *trans, struct btree_iter *iter,
1606                         struct bkey_s_c k,
1607                         struct bch_hash_info *hash_info,
1608                         struct inode_walker *dir,
1609                         struct inode_walker *target,
1610                         struct snapshots_seen *s)
1611 {
1612         struct bch_fs *c = trans->c;
1613         struct bkey_s_c_dirent d;
1614         struct inode_walker_entry *i;
1615         struct printbuf buf = PRINTBUF;
1616         struct bpos equiv;
1617         int ret = 0;
1618
1619         ret = check_key_has_snapshot(trans, iter, k);
1620         if (ret) {
1621                 ret = ret < 0 ? ret : 0;
1622                 goto out;
1623         }
1624
1625         equiv = k.k->p;
1626         equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot);
1627
1628         ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p);
1629         if (ret)
1630                 goto err;
1631
1632         if (k.k->type == KEY_TYPE_whiteout)
1633                 goto out;
1634
1635         if (dir->cur_inum != k.k->p.inode) {
1636                 ret = check_subdir_count(trans, dir);
1637                 if (ret)
1638                         goto err;
1639         }
1640
1641         BUG_ON(!iter->path->should_be_locked);
1642
1643         i = walk_inode(trans, dir, equiv);
1644         ret = PTR_ERR_OR_ZERO(i);
1645         if (ret < 0)
1646                 goto err;
1647
1648         if (dir->first_this_inode)
1649                 *hash_info = bch2_hash_info_init(c, &dir->inodes.data[0].inode);
1650         dir->first_this_inode = false;
1651
1652         if (fsck_err_on(!i, c,
1653                         "dirent in nonexisting directory:\n%s",
1654                         (printbuf_reset(&buf),
1655                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1656                 ret = bch2_btree_delete_at(trans, iter,
1657                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1658                 goto out;
1659         }
1660
1661         if (!i)
1662                 goto out;
1663
1664         if (fsck_err_on(!S_ISDIR(i->inode.bi_mode), c,
1665                         "dirent in non directory inode type %s:\n%s",
1666                         bch2_d_type_str(inode_d_type(&i->inode)),
1667                         (printbuf_reset(&buf),
1668                          bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1669                 ret = bch2_btree_delete_at(trans, iter, 0);
1670                 goto out;
1671         }
1672
1673         ret = hash_check_key(trans, bch2_dirent_hash_desc, hash_info, iter, k);
1674         if (ret < 0)
1675                 goto err;
1676         if (ret) {
1677                 /* dirent has been deleted */
1678                 ret = 0;
1679                 goto out;
1680         }
1681
1682         if (k.k->type != KEY_TYPE_dirent)
1683                 goto out;
1684
1685         d = bkey_s_c_to_dirent(k);
1686
1687         if (d.v->d_type == DT_SUBVOL) {
1688                 struct bch_inode_unpacked subvol_root;
1689                 u32 target_subvol = le32_to_cpu(d.v->d_child_subvol);
1690                 u32 target_snapshot;
1691                 u64 target_inum;
1692
1693                 ret = __subvol_lookup(trans, target_subvol,
1694                                       &target_snapshot, &target_inum);
1695                 if (ret && !bch2_err_matches(ret, ENOENT))
1696                         goto err;
1697
1698                 if (fsck_err_on(ret, c,
1699                                 "dirent points to missing subvolume %u",
1700                                 le32_to_cpu(d.v->d_child_subvol))) {
1701                         ret = __remove_dirent(trans, d.k->p);
1702                         goto err;
1703                 }
1704
1705                 ret = __lookup_inode(trans, target_inum,
1706                                    &subvol_root, &target_snapshot);
1707                 if (ret && !bch2_err_matches(ret, ENOENT))
1708                         goto err;
1709
1710                 if (fsck_err_on(ret, c,
1711                                 "subvolume %u points to missing subvolume root %llu",
1712                                 target_subvol,
1713                                 target_inum)) {
1714                         bch_err(c, "repair not implemented yet");
1715                         ret = -EINVAL;
1716                         goto err;
1717                 }
1718
1719                 if (fsck_err_on(subvol_root.bi_subvol != target_subvol, c,
1720                                 "subvol root %llu has wrong bi_subvol field: got %u, should be %u",
1721                                 target_inum,
1722                                 subvol_root.bi_subvol, target_subvol)) {
1723                         subvol_root.bi_subvol = target_subvol;
1724                         ret = __write_inode(trans, &subvol_root, target_snapshot);
1725                         if (ret)
1726                                 goto err;
1727                 }
1728
1729                 ret = check_dirent_target(trans, iter, d, &subvol_root,
1730                                           target_snapshot);
1731                 if (ret)
1732                         goto err;
1733         } else {
1734                 ret = __get_visible_inodes(trans, target, s, le64_to_cpu(d.v->d_inum));
1735                 if (ret)
1736                         goto err;
1737
1738                 if (fsck_err_on(!target->inodes.nr, c,
1739                                 "dirent points to missing inode: (equiv %u)\n%s",
1740                                 equiv.snapshot,
1741                                 (printbuf_reset(&buf),
1742                                  bch2_bkey_val_to_text(&buf, c, k),
1743                                  buf.buf))) {
1744                         ret = __remove_dirent(trans, d.k->p);
1745                         if (ret)
1746                                 goto err;
1747                 }
1748
1749                 darray_for_each(target->inodes, i) {
1750                         ret = check_dirent_target(trans, iter, d,
1751                                                   &i->inode, i->snapshot);
1752                         if (ret)
1753                                 goto err;
1754                 }
1755         }
1756
1757         if (d.v->d_type == DT_DIR)
1758                 for_each_visible_inode(c, s, dir, equiv.snapshot, i)
1759                         i->count++;
1760
1761 out:
1762 err:
1763 fsck_err:
1764         printbuf_exit(&buf);
1765
1766         if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
1767                 bch_err_fn(c, ret);
1768         return ret;
1769 }
1770
1771 /*
1772  * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
1773  * validate d_type
1774  */
1775 noinline_for_stack
1776 static int check_dirents(struct bch_fs *c)
1777 {
1778         struct inode_walker dir = inode_walker_init();
1779         struct inode_walker target = inode_walker_init();
1780         struct snapshots_seen s;
1781         struct bch_hash_info hash_info;
1782         struct btree_trans trans;
1783         struct btree_iter iter;
1784         struct bkey_s_c k;
1785         int ret = 0;
1786
1787         bch_verbose(c, "checking dirents");
1788
1789         snapshots_seen_init(&s);
1790         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1791
1792         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_dirents,
1793                         POS(BCACHEFS_ROOT_INO, 0),
1794                         BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS,
1795                         k,
1796                         NULL, NULL,
1797                         BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
1798                 check_dirent(&trans, &iter, k, &hash_info, &dir, &target, &s));
1799
1800         bch2_trans_exit(&trans);
1801         snapshots_seen_exit(&s);
1802         inode_walker_exit(&dir);
1803         inode_walker_exit(&target);
1804
1805         if (ret)
1806                 bch_err_fn(c, ret);
1807         return ret;
1808 }
1809
1810 static int check_xattr(struct btree_trans *trans, struct btree_iter *iter,
1811                        struct bkey_s_c k,
1812                        struct bch_hash_info *hash_info,
1813                        struct inode_walker *inode)
1814 {
1815         struct bch_fs *c = trans->c;
1816         struct inode_walker_entry *i;
1817         int ret;
1818
1819         ret = check_key_has_snapshot(trans, iter, k);
1820         if (ret)
1821                 return ret;
1822
1823         i = walk_inode(trans, inode, k.k->p);
1824         ret = PTR_ERR_OR_ZERO(i);
1825         if (ret)
1826                 return ret;
1827
1828         if (inode->first_this_inode)
1829                 *hash_info = bch2_hash_info_init(c, &inode->inodes.data[0].inode);
1830         inode->first_this_inode = false;
1831
1832         if (fsck_err_on(!i, c,
1833                         "xattr for missing inode %llu",
1834                         k.k->p.inode))
1835                 return bch2_btree_delete_at(trans, iter, 0);
1836
1837         if (!i)
1838                 return 0;
1839
1840         ret = hash_check_key(trans, bch2_xattr_hash_desc, hash_info, iter, k);
1841 fsck_err:
1842         if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
1843                 bch_err_fn(c, ret);
1844         return ret;
1845 }
1846
1847 /*
1848  * Walk xattrs: verify that they all have a corresponding inode
1849  */
1850 noinline_for_stack
1851 static int check_xattrs(struct bch_fs *c)
1852 {
1853         struct inode_walker inode = inode_walker_init();
1854         struct bch_hash_info hash_info;
1855         struct btree_trans trans;
1856         struct btree_iter iter;
1857         struct bkey_s_c k;
1858         int ret = 0;
1859
1860         bch_verbose(c, "checking xattrs");
1861
1862         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1863
1864         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_xattrs,
1865                         POS(BCACHEFS_ROOT_INO, 0),
1866                         BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS,
1867                         k,
1868                         NULL, NULL,
1869                         BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
1870                 check_xattr(&trans, &iter, k, &hash_info, &inode));
1871
1872         bch2_trans_exit(&trans);
1873
1874         if (ret)
1875                 bch_err_fn(c, ret);
1876         return ret;
1877 }
1878
1879 static int check_root_trans(struct btree_trans *trans)
1880 {
1881         struct bch_fs *c = trans->c;
1882         struct bch_inode_unpacked root_inode;
1883         u32 snapshot;
1884         u64 inum;
1885         int ret;
1886
1887         ret = __subvol_lookup(trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum);
1888         if (ret && !bch2_err_matches(ret, ENOENT))
1889                 return ret;
1890
1891         if (mustfix_fsck_err_on(ret, c, "root subvol missing")) {
1892                 struct bkey_i_subvolume root_subvol;
1893
1894                 snapshot        = U32_MAX;
1895                 inum            = BCACHEFS_ROOT_INO;
1896
1897                 bkey_subvolume_init(&root_subvol.k_i);
1898                 root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL;
1899                 root_subvol.v.flags     = 0;
1900                 root_subvol.v.snapshot  = cpu_to_le32(snapshot);
1901                 root_subvol.v.inode     = cpu_to_le64(inum);
1902                 ret = commit_do(trans, NULL, NULL,
1903                                       BTREE_INSERT_NOFAIL|
1904                                       BTREE_INSERT_LAZY_RW,
1905                         __bch2_btree_insert(trans, BTREE_ID_subvolumes,
1906                                             &root_subvol.k_i, 0));
1907                 if (ret) {
1908                         bch_err(c, "error writing root subvol: %s", bch2_err_str(ret));
1909                         goto err;
1910                 }
1911
1912         }
1913
1914         ret = __lookup_inode(trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot);
1915         if (ret && !bch2_err_matches(ret, ENOENT))
1916                 return ret;
1917
1918         if (mustfix_fsck_err_on(ret, c, "root directory missing") ||
1919             mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode), c,
1920                                 "root inode not a directory")) {
1921                 bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755,
1922                                 0, NULL);
1923                 root_inode.bi_inum = inum;
1924
1925                 ret = __write_inode(trans, &root_inode, snapshot);
1926                 if (ret)
1927                         bch_err(c, "error writing root inode: %s", bch2_err_str(ret));
1928         }
1929 err:
1930 fsck_err:
1931         return ret;
1932 }
1933
1934 /* Get root directory, create if it doesn't exist: */
1935 noinline_for_stack
1936 static int check_root(struct bch_fs *c)
1937 {
1938         int ret;
1939
1940         bch_verbose(c, "checking root directory");
1941
1942         ret = bch2_trans_do(c, NULL, NULL,
1943                              BTREE_INSERT_NOFAIL|
1944                              BTREE_INSERT_LAZY_RW,
1945                 check_root_trans(&trans));
1946
1947         if (ret)
1948                 bch_err_fn(c, ret);
1949         return ret;
1950 }
1951
1952 struct pathbuf_entry {
1953         u64     inum;
1954         u32     snapshot;
1955 };
1956
1957 typedef DARRAY(struct pathbuf_entry) pathbuf;
1958
1959 static bool path_is_dup(pathbuf *p, u64 inum, u32 snapshot)
1960 {
1961         struct pathbuf_entry *i;
1962
1963         darray_for_each(*p, i)
1964                 if (i->inum     == inum &&
1965                     i->snapshot == snapshot)
1966                         return true;
1967
1968         return false;
1969 }
1970
1971 static int path_down(struct bch_fs *c, pathbuf *p,
1972                      u64 inum, u32 snapshot)
1973 {
1974         int ret = darray_push(p, ((struct pathbuf_entry) {
1975                 .inum           = inum,
1976                 .snapshot       = snapshot,
1977         }));
1978
1979         if (ret)
1980                 bch_err(c, "fsck: error allocating memory for pathbuf, size %zu",
1981                         p->size);
1982         return ret;
1983 }
1984
1985 /*
1986  * Check that a given inode is reachable from the root:
1987  *
1988  * XXX: we should also be verifying that inodes are in the right subvolumes
1989  */
1990 static int check_path(struct btree_trans *trans,
1991                       pathbuf *p,
1992                       struct bch_inode_unpacked *inode,
1993                       u32 snapshot)
1994 {
1995         struct bch_fs *c = trans->c;
1996         int ret = 0;
1997
1998         snapshot = bch2_snapshot_equiv(c, snapshot);
1999         p->nr = 0;
2000
2001         while (!(inode->bi_inum == BCACHEFS_ROOT_INO &&
2002                  inode->bi_subvol == BCACHEFS_ROOT_SUBVOL)) {
2003                 struct btree_iter dirent_iter;
2004                 struct bkey_s_c_dirent d;
2005                 u32 parent_snapshot = snapshot;
2006
2007                 if (inode->bi_subvol) {
2008                         u64 inum;
2009
2010                         ret = subvol_lookup(trans, inode->bi_parent_subvol,
2011                                             &parent_snapshot, &inum);
2012                         if (ret)
2013                                 break;
2014                 }
2015
2016                 ret = lockrestart_do(trans,
2017                         PTR_ERR_OR_ZERO((d = dirent_get_by_pos(trans, &dirent_iter,
2018                                           SPOS(inode->bi_dir, inode->bi_dir_offset,
2019                                                parent_snapshot))).k));
2020                 if (ret && !bch2_err_matches(ret, ENOENT))
2021                         break;
2022
2023                 if (!ret && !dirent_points_to_inode(d, inode)) {
2024                         bch2_trans_iter_exit(trans, &dirent_iter);
2025                         ret = -BCH_ERR_ENOENT_dirent_doesnt_match_inode;
2026                 }
2027
2028                 if (bch2_err_matches(ret, ENOENT)) {
2029                         if (fsck_err(c,  "unreachable inode %llu:%u, type %s nlink %u backptr %llu:%llu",
2030                                      inode->bi_inum, snapshot,
2031                                      bch2_d_type_str(inode_d_type(inode)),
2032                                      inode->bi_nlink,
2033                                      inode->bi_dir,
2034                                      inode->bi_dir_offset))
2035                                 ret = reattach_inode(trans, inode, snapshot);
2036                         break;
2037                 }
2038
2039                 bch2_trans_iter_exit(trans, &dirent_iter);
2040
2041                 if (!S_ISDIR(inode->bi_mode))
2042                         break;
2043
2044                 ret = path_down(c, p, inode->bi_inum, snapshot);
2045                 if (ret) {
2046                         bch_err(c, "memory allocation failure");
2047                         return ret;
2048                 }
2049
2050                 snapshot = parent_snapshot;
2051
2052                 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot);
2053                 if (ret) {
2054                         /* Should have been caught in dirents pass */
2055                         bch_err(c, "error looking up parent directory: %i", ret);
2056                         break;
2057                 }
2058
2059                 if (path_is_dup(p, inode->bi_inum, snapshot)) {
2060                         struct pathbuf_entry *i;
2061
2062                         /* XXX print path */
2063                         bch_err(c, "directory structure loop");
2064
2065                         darray_for_each(*p, i)
2066                                 pr_err("%llu:%u", i->inum, i->snapshot);
2067                         pr_err("%llu:%u", inode->bi_inum, snapshot);
2068
2069                         if (!fsck_err(c, "directory structure loop"))
2070                                 return 0;
2071
2072                         ret = commit_do(trans, NULL, NULL,
2073                                               BTREE_INSERT_NOFAIL|
2074                                               BTREE_INSERT_LAZY_RW,
2075                                         remove_backpointer(trans, inode));
2076                         if (ret) {
2077                                 bch_err(c, "error removing dirent: %i", ret);
2078                                 break;
2079                         }
2080
2081                         ret = reattach_inode(trans, inode, snapshot);
2082                 }
2083         }
2084 fsck_err:
2085         if (ret)
2086                 bch_err_fn(c, ret);
2087         return ret;
2088 }
2089
2090 /*
2091  * Check for unreachable inodes, as well as loops in the directory structure:
2092  * After check_dirents(), if an inode backpointer doesn't exist that means it's
2093  * unreachable:
2094  */
2095 noinline_for_stack
2096 static int check_directory_structure(struct bch_fs *c)
2097 {
2098         struct btree_trans trans;
2099         struct btree_iter iter;
2100         struct bkey_s_c k;
2101         struct bch_inode_unpacked u;
2102         pathbuf path = { 0, };
2103         int ret;
2104
2105         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2106
2107         for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN,
2108                            BTREE_ITER_INTENT|
2109                            BTREE_ITER_PREFETCH|
2110                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2111                 if (!bkey_is_inode(k.k))
2112                         continue;
2113
2114                 ret = bch2_inode_unpack(k, &u);
2115                 if (ret) {
2116                         /* Should have been caught earlier in fsck: */
2117                         bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
2118                         break;
2119                 }
2120
2121                 if (u.bi_flags & BCH_INODE_UNLINKED)
2122                         continue;
2123
2124                 ret = check_path(&trans, &path, &u, iter.pos.snapshot);
2125                 if (ret)
2126                         break;
2127         }
2128         bch2_trans_iter_exit(&trans, &iter);
2129         bch2_trans_exit(&trans);
2130         darray_exit(&path);
2131
2132         if (ret)
2133                 bch_err_fn(c, ret);
2134         return ret;
2135 }
2136
2137 struct nlink_table {
2138         size_t          nr;
2139         size_t          size;
2140
2141         struct nlink {
2142                 u64     inum;
2143                 u32     snapshot;
2144                 u32     count;
2145         }               *d;
2146 };
2147
2148 static int add_nlink(struct bch_fs *c, struct nlink_table *t,
2149                      u64 inum, u32 snapshot)
2150 {
2151         if (t->nr == t->size) {
2152                 size_t new_size = max_t(size_t, 128UL, t->size * 2);
2153                 void *d = kvmalloc_array(new_size, sizeof(t->d[0]), GFP_KERNEL);
2154
2155                 if (!d) {
2156                         bch_err(c, "fsck: error allocating memory for nlink_table, size %zu",
2157                                 new_size);
2158                         return -BCH_ERR_ENOMEM_fsck_add_nlink;
2159                 }
2160
2161                 if (t->d)
2162                         memcpy(d, t->d, t->size * sizeof(t->d[0]));
2163                 kvfree(t->d);
2164
2165                 t->d = d;
2166                 t->size = new_size;
2167         }
2168
2169
2170         t->d[t->nr++] = (struct nlink) {
2171                 .inum           = inum,
2172                 .snapshot       = snapshot,
2173         };
2174
2175         return 0;
2176 }
2177
2178 static int nlink_cmp(const void *_l, const void *_r)
2179 {
2180         const struct nlink *l = _l;
2181         const struct nlink *r = _r;
2182
2183         return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot);
2184 }
2185
2186 static void inc_link(struct bch_fs *c, struct snapshots_seen *s,
2187                      struct nlink_table *links,
2188                      u64 range_start, u64 range_end, u64 inum, u32 snapshot)
2189 {
2190         struct nlink *link, key = {
2191                 .inum = inum, .snapshot = U32_MAX,
2192         };
2193
2194         if (inum < range_start || inum >= range_end)
2195                 return;
2196
2197         link = __inline_bsearch(&key, links->d, links->nr,
2198                                 sizeof(links->d[0]), nlink_cmp);
2199         if (!link)
2200                 return;
2201
2202         while (link > links->d && link[0].inum == link[-1].inum)
2203                 --link;
2204
2205         for (; link < links->d + links->nr && link->inum == inum; link++)
2206                 if (ref_visible(c, s, snapshot, link->snapshot)) {
2207                         link->count++;
2208                         if (link->snapshot >= snapshot)
2209                                 break;
2210                 }
2211 }
2212
2213 noinline_for_stack
2214 static int check_nlinks_find_hardlinks(struct bch_fs *c,
2215                                        struct nlink_table *t,
2216                                        u64 start, u64 *end)
2217 {
2218         struct btree_trans trans;
2219         struct btree_iter iter;
2220         struct bkey_s_c k;
2221         struct bch_inode_unpacked u;
2222         int ret = 0;
2223
2224         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2225
2226         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
2227                            POS(0, start),
2228                            BTREE_ITER_INTENT|
2229                            BTREE_ITER_PREFETCH|
2230                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2231                 if (!bkey_is_inode(k.k))
2232                         continue;
2233
2234                 /* Should never fail, checked by bch2_inode_invalid: */
2235                 BUG_ON(bch2_inode_unpack(k, &u));
2236
2237                 /*
2238                  * Backpointer and directory structure checks are sufficient for
2239                  * directories, since they can't have hardlinks:
2240                  */
2241                 if (S_ISDIR(u.bi_mode))
2242                         continue;
2243
2244                 if (!u.bi_nlink)
2245                         continue;
2246
2247                 ret = add_nlink(c, t, k.k->p.offset, k.k->p.snapshot);
2248                 if (ret) {
2249                         *end = k.k->p.offset;
2250                         ret = 0;
2251                         break;
2252                 }
2253
2254         }
2255         bch2_trans_iter_exit(&trans, &iter);
2256         bch2_trans_exit(&trans);
2257
2258         if (ret)
2259                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2260
2261         return ret;
2262 }
2263
2264 noinline_for_stack
2265 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
2266                                      u64 range_start, u64 range_end)
2267 {
2268         struct btree_trans trans;
2269         struct snapshots_seen s;
2270         struct btree_iter iter;
2271         struct bkey_s_c k;
2272         struct bkey_s_c_dirent d;
2273         int ret;
2274
2275         snapshots_seen_init(&s);
2276
2277         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2278
2279         for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN,
2280                            BTREE_ITER_INTENT|
2281                            BTREE_ITER_PREFETCH|
2282                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2283                 ret = snapshots_seen_update(c, &s, iter.btree_id, k.k->p);
2284                 if (ret)
2285                         break;
2286
2287                 switch (k.k->type) {
2288                 case KEY_TYPE_dirent:
2289                         d = bkey_s_c_to_dirent(k);
2290
2291                         if (d.v->d_type != DT_DIR &&
2292                             d.v->d_type != DT_SUBVOL)
2293                                 inc_link(c, &s, links, range_start, range_end,
2294                                          le64_to_cpu(d.v->d_inum),
2295                                          bch2_snapshot_equiv(c, d.k->p.snapshot));
2296                         break;
2297                 }
2298         }
2299         bch2_trans_iter_exit(&trans, &iter);
2300
2301         if (ret)
2302                 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
2303
2304         bch2_trans_exit(&trans);
2305         snapshots_seen_exit(&s);
2306         return ret;
2307 }
2308
2309 static int check_nlinks_update_inode(struct btree_trans *trans, struct btree_iter *iter,
2310                                      struct bkey_s_c k,
2311                                      struct nlink_table *links,
2312                                      size_t *idx, u64 range_end)
2313 {
2314         struct bch_fs *c = trans->c;
2315         struct bch_inode_unpacked u;
2316         struct nlink *link = &links->d[*idx];
2317         int ret = 0;
2318
2319         if (k.k->p.offset >= range_end)
2320                 return 1;
2321
2322         if (!bkey_is_inode(k.k))
2323                 return 0;
2324
2325         BUG_ON(bch2_inode_unpack(k, &u));
2326
2327         if (S_ISDIR(u.bi_mode))
2328                 return 0;
2329
2330         if (!u.bi_nlink)
2331                 return 0;
2332
2333         while ((cmp_int(link->inum, k.k->p.offset) ?:
2334                 cmp_int(link->snapshot, k.k->p.snapshot)) < 0) {
2335                 BUG_ON(*idx == links->nr);
2336                 link = &links->d[++*idx];
2337         }
2338
2339         if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c,
2340                         "inode %llu type %s has wrong i_nlink (%u, should be %u)",
2341                         u.bi_inum, bch2_d_types[mode_to_type(u.bi_mode)],
2342                         bch2_inode_nlink_get(&u), link->count)) {
2343                 bch2_inode_nlink_set(&u, link->count);
2344                 ret = __write_inode(trans, &u, k.k->p.snapshot);
2345         }
2346 fsck_err:
2347         return ret;
2348 }
2349
2350 noinline_for_stack
2351 static int check_nlinks_update_hardlinks(struct bch_fs *c,
2352                                struct nlink_table *links,
2353                                u64 range_start, u64 range_end)
2354 {
2355         struct btree_trans trans;
2356         struct btree_iter iter;
2357         struct bkey_s_c k;
2358         size_t idx = 0;
2359         int ret = 0;
2360
2361         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2362
2363         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_inodes,
2364                         POS(0, range_start),
2365                         BTREE_ITER_INTENT|BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
2366                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
2367                 check_nlinks_update_inode(&trans, &iter, k, links, &idx, range_end));
2368
2369         bch2_trans_exit(&trans);
2370
2371         if (ret < 0) {
2372                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2373                 return ret;
2374         }
2375
2376         return 0;
2377 }
2378
2379 noinline_for_stack
2380 static int check_nlinks(struct bch_fs *c)
2381 {
2382         struct nlink_table links = { 0 };
2383         u64 this_iter_range_start, next_iter_range_start = 0;
2384         int ret = 0;
2385
2386         bch_verbose(c, "checking inode nlinks");
2387
2388         do {
2389                 this_iter_range_start = next_iter_range_start;
2390                 next_iter_range_start = U64_MAX;
2391
2392                 ret = check_nlinks_find_hardlinks(c, &links,
2393                                                   this_iter_range_start,
2394                                                   &next_iter_range_start);
2395
2396                 ret = check_nlinks_walk_dirents(c, &links,
2397                                           this_iter_range_start,
2398                                           next_iter_range_start);
2399                 if (ret)
2400                         break;
2401
2402                 ret = check_nlinks_update_hardlinks(c, &links,
2403                                          this_iter_range_start,
2404                                          next_iter_range_start);
2405                 if (ret)
2406                         break;
2407
2408                 links.nr = 0;
2409         } while (next_iter_range_start != U64_MAX);
2410
2411         kvfree(links.d);
2412
2413         if (ret)
2414                 bch_err_fn(c, ret);
2415         return ret;
2416 }
2417
2418 static int fix_reflink_p_key(struct btree_trans *trans, struct btree_iter *iter,
2419                              struct bkey_s_c k)
2420 {
2421         struct bkey_s_c_reflink_p p;
2422         struct bkey_i_reflink_p *u;
2423         int ret;
2424
2425         if (k.k->type != KEY_TYPE_reflink_p)
2426                 return 0;
2427
2428         p = bkey_s_c_to_reflink_p(k);
2429
2430         if (!p.v->front_pad && !p.v->back_pad)
2431                 return 0;
2432
2433         u = bch2_trans_kmalloc(trans, sizeof(*u));
2434         ret = PTR_ERR_OR_ZERO(u);
2435         if (ret)
2436                 return ret;
2437
2438         bkey_reassemble(&u->k_i, k);
2439         u->v.front_pad  = 0;
2440         u->v.back_pad   = 0;
2441
2442         return bch2_trans_update(trans, iter, &u->k_i, BTREE_TRIGGER_NORUN);
2443 }
2444
2445 noinline_for_stack
2446 static int fix_reflink_p(struct bch_fs *c)
2447 {
2448         struct btree_iter iter;
2449         struct bkey_s_c k;
2450         int ret;
2451
2452         if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix)
2453                 return 0;
2454
2455         bch_verbose(c, "fixing reflink_p keys");
2456
2457         ret = bch2_trans_run(c,
2458                 for_each_btree_key_commit(&trans, iter,
2459                                 BTREE_ID_extents, POS_MIN,
2460                                 BTREE_ITER_INTENT|BTREE_ITER_PREFETCH|
2461                                 BTREE_ITER_ALL_SNAPSHOTS, k,
2462                                 NULL, NULL, BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
2463                         fix_reflink_p_key(&trans, &iter, k)));
2464
2465         if (ret)
2466                 bch_err_fn(c, ret);
2467         return ret;
2468 }
2469
2470 /*
2471  * Checks for inconsistencies that shouldn't happen, unless we have a bug.
2472  * Doesn't fix them yet, mainly because they haven't yet been observed:
2473  */
2474 int bch2_fsck_full(struct bch_fs *c)
2475 {
2476         int ret;
2477 again:
2478         ret =   bch2_fs_check_snapshot_trees(c);
2479                 bch2_fs_check_snapshots(c) ?:
2480                 bch2_fs_check_subvols(c) ?:
2481                 bch2_delete_dead_snapshots(c) ?:
2482                 check_inodes(c, true) ?:
2483                 check_extents(c) ?:
2484                 check_dirents(c) ?:
2485                 check_xattrs(c) ?:
2486                 check_root(c) ?:
2487                 check_directory_structure(c) ?:
2488                 check_nlinks(c) ?:
2489                 fix_reflink_p(c);
2490
2491         if (bch2_err_matches(ret, BCH_ERR_need_snapshot_cleanup)) {
2492                 set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
2493                 goto again;
2494         }
2495
2496         return ret;
2497 }
2498
2499 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
2500 {
2501         return  bch2_fs_check_snapshots(c) ?:
2502                 bch2_fs_check_subvols(c) ?:
2503                 bch2_delete_dead_snapshots(c) ?:
2504                 check_inodes(c, false);
2505 }