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 "dirent.h"
   7 #include "error.h"
   8 #include "fs-common.h"
   9 #include "fsck.h"
  10 #include "inode.h"
  11 #include "keylist.h"
  12 #include "super.h"
  13 #include "xattr.h"
  14
  15 #include <linux/bsearch.h>
  16 #include <linux/dcache.h> /* struct qstr */
  17
  18 #define QSTR(n) { { { .len = strlen(n) } }, .name = n }
  19
  20 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum)
  21 {
  22         struct btree_iter *iter;
  23         struct bkey_s_c k;
  24         u64 sectors = 0;
  25         int ret;
  26
  27         for_each_btree_key(trans, iter, BTREE_ID_extents,
  28                            POS(inum, 0), 0, k, ret) {
  29                 if (k.k->p.inode != inum)
  30                         break;
  31
  32                 if (bkey_extent_is_allocation(k.k))
  33                         sectors += k.k->size;
  34         }
  35
  36         bch2_trans_iter_free(trans, iter);
  37
  38         return ret ?: sectors;
  39 }
  40
  41 static int __lookup_inode(struct btree_trans *trans, u64 inode_nr,
  42                           struct bch_inode_unpacked *inode,
  43                           u32 *snapshot)
  44 {
  45         struct btree_iter *iter;
  46         struct bkey_s_c k;
  47         int ret;
  48
  49         iter = bch2_trans_get_iter(trans, BTREE_ID_inodes,
  50                         POS(0, inode_nr), 0);
  51         k = bch2_btree_iter_peek_slot(iter);
  52         ret = bkey_err(k);
  53         if (ret)
  54                 goto err;
  55
  56         if (snapshot)
  57                 *snapshot = iter->pos.snapshot;
  58         ret = k.k->type == KEY_TYPE_inode
  59                 ? bch2_inode_unpack(bkey_s_c_to_inode(k), inode)
  60                 : -ENOENT;
  61 err:
  62         bch2_trans_iter_free(trans, iter);
  63         return ret;
  64 }
  65
  66 static int lookup_inode(struct btree_trans *trans, u64 inode_nr,
  67                         struct bch_inode_unpacked *inode,
  68                         u32 *snapshot)
  69 {
  70         return lockrestart_do(trans, __lookup_inode(trans, inode_nr, inode, snapshot));
  71 }
  72
  73 static int __write_inode(struct btree_trans *trans,
  74                          struct bch_inode_unpacked *inode,
  75                          u32 snapshot)
  76 {
  77         struct btree_iter *inode_iter =
  78                 bch2_trans_get_iter(trans, BTREE_ID_inodes,
  79                                     SPOS(0, inode->bi_inum, snapshot),
  80                                     BTREE_ITER_INTENT);
  81         int ret = bch2_btree_iter_traverse(inode_iter) ?:
  82                 bch2_inode_write(trans, inode_iter, inode);
  83         bch2_trans_iter_put(trans, inode_iter);
  84         return ret;
  85 }
  86
  87 static int write_inode(struct btree_trans *trans,
  88                        struct bch_inode_unpacked *inode,
  89                        u32 snapshot)
  90 {
  91         int ret = __bch2_trans_do(trans, NULL, NULL,
  92                                   BTREE_INSERT_NOFAIL|
  93                                   BTREE_INSERT_LAZY_RW,
  94                                   __write_inode(trans, inode, snapshot));
  95         if (ret)
  96                 bch_err(trans->c, "error in fsck: error %i updating inode", ret);
  97         return ret;
  98 }
  99
 100 static int __remove_dirent(struct btree_trans *trans, struct bpos pos)
 101 {
 102         struct bch_fs *c = trans->c;
 103         struct btree_iter *iter;
 104         struct bch_inode_unpacked dir_inode;
 105         struct bch_hash_info dir_hash_info;
 106         int ret;
 107
 108         ret = lookup_inode(trans, pos.inode, &dir_inode, NULL);
 109         if (ret)
 110                 return ret;
 111
 112         dir_hash_info = bch2_hash_info_init(c, &dir_inode);
 113
 114         iter = bch2_trans_get_iter(trans, BTREE_ID_dirents, pos, BTREE_ITER_INTENT);
 115
 116         ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc,
 117                                   &dir_hash_info, iter);
 118         bch2_trans_iter_put(trans, iter);
 119         return ret;
 120 }
 121
 122 static int remove_dirent(struct btree_trans *trans, struct bpos pos)
 123 {
 124         int ret = __bch2_trans_do(trans, NULL, NULL,
 125                                   BTREE_INSERT_NOFAIL|
 126                                   BTREE_INSERT_LAZY_RW,
 127                                   __remove_dirent(trans, pos));
 128         if (ret)
 129                 bch_err(trans->c, "remove_dirent: err %i deleting dirent", ret);
 130         return ret;
 131 }
 132
 133 /* Get lost+found, create if it doesn't exist: */
 134 static int lookup_lostfound(struct btree_trans *trans,
 135                             struct bch_inode_unpacked *lostfound)
 136 {
 137         struct bch_fs *c = trans->c;
 138         struct bch_inode_unpacked root;
 139         struct bch_hash_info root_hash_info;
 140         struct qstr lostfound_str = QSTR("lost+found");
 141         u64 inum;
 142         u32 snapshot;
 143         int ret;
 144
 145         ret = lookup_inode(trans, BCACHEFS_ROOT_INO, &root, &snapshot);
 146         if (ret && ret != -ENOENT)
 147                 return ret;
 148
 149         root_hash_info = bch2_hash_info_init(c, &root);
 150         inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info,
 151                                   &lostfound_str);
 152         if (!inum) {
 153                 bch_notice(c, "creating lost+found");
 154                 goto create_lostfound;
 155         }
 156
 157         ret = lookup_inode(trans, inum, lostfound, &snapshot);
 158         if (ret && ret != -ENOENT) {
 159                 /*
 160                  * The check_dirents pass has already run, dangling dirents
 161                  * shouldn't exist here:
 162                  */
 163                 bch_err(c, "error looking up lost+found: %i", ret);
 164                 return ret;
 165         }
 166
 167         if (ret == -ENOENT) {
 168 create_lostfound:
 169                 bch2_inode_init_early(c, lostfound);
 170
 171                 ret = __bch2_trans_do(trans, NULL, NULL,
 172                                       BTREE_INSERT_NOFAIL|
 173                                       BTREE_INSERT_LAZY_RW,
 174                         bch2_create_trans(trans,
 175                                           BCACHEFS_ROOT_INO, &root,
 176                                           lostfound,
 177                                           &lostfound_str,
 178                                           0, 0, S_IFDIR|0700, 0, NULL, NULL));
 179                 if (ret)
 180                         bch_err(c, "error creating lost+found: %i", ret);
 181         }
 182
 183         return 0;
 184 }
 185
 186 static int reattach_inode(struct btree_trans *trans,
 187                           struct bch_inode_unpacked *inode)
 188 {
 189         struct bch_hash_info dir_hash;
 190         struct bch_inode_unpacked lostfound;
 191         char name_buf[20];
 192         struct qstr name;
 193         u64 dir_offset = 0;
 194         int ret;
 195
 196         ret = lookup_lostfound(trans, &lostfound);
 197         if (ret)
 198                 return ret;
 199
 200         if (S_ISDIR(inode->bi_mode)) {
 201                 lostfound.bi_nlink++;
 202
 203                 ret = write_inode(trans, &lostfound, U32_MAX);
 204                 if (ret)
 205                         return ret;
 206         }
 207
 208         dir_hash = bch2_hash_info_init(trans->c, &lostfound);
 209
 210         snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum);
 211         name = (struct qstr) QSTR(name_buf);
 212
 213         ret = __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW,
 214                 bch2_dirent_create(trans, lostfound.bi_inum, &dir_hash,
 215                                    mode_to_type(inode->bi_mode),
 216                                    &name, inode->bi_inum, &dir_offset,
 217                                    BCH_HASH_SET_MUST_CREATE));
 218         if (ret) {
 219                 bch_err(trans->c, "error %i reattaching inode %llu",
 220                         ret, inode->bi_inum);
 221                 return ret;
 222         }
 223
 224         inode->bi_dir           = lostfound.bi_inum;
 225         inode->bi_dir_offset    = dir_offset;
 226
 227         return write_inode(trans, inode, U32_MAX);
 228 }
 229
 230 static int remove_backpointer(struct btree_trans *trans,
 231                               struct bch_inode_unpacked *inode)
 232 {
 233         struct btree_iter *iter;
 234         struct bkey_s_c k;
 235         int ret;
 236
 237         iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
 238                                    POS(inode->bi_dir, inode->bi_dir_offset), 0);
 239         k = bch2_btree_iter_peek_slot(iter);
 240         ret = bkey_err(k);
 241         if (ret)
 242                 goto out;
 243         if (k.k->type != KEY_TYPE_dirent) {
 244                 ret = -ENOENT;
 245                 goto out;
 246         }
 247
 248         ret = remove_dirent(trans, k.k->p);
 249 out:
 250         bch2_trans_iter_put(trans, iter);
 251         return ret;
 252 }
 253
 254 struct inode_walker {
 255         bool                    first_this_inode;
 256         bool                    have_inode;
 257         u64                     cur_inum;
 258         u32                     snapshot;
 259         struct bch_inode_unpacked inode;
 260 };
 261
 262 static struct inode_walker inode_walker_init(void)
 263 {
 264         return (struct inode_walker) {
 265                 .cur_inum       = -1,
 266                 .have_inode     = false,
 267         };
 268 }
 269
 270 static int walk_inode(struct btree_trans *trans,
 271                       struct inode_walker *w, u64 inum)
 272 {
 273         if (inum != w->cur_inum) {
 274                 int ret = lookup_inode(trans, inum, &w->inode, &w->snapshot);
 275
 276                 if (ret && ret != -ENOENT)
 277                         return ret;
 278
 279                 w->have_inode   = !ret;
 280                 w->cur_inum     = inum;
 281                 w->first_this_inode = true;
 282         } else {
 283                 w->first_this_inode = false;
 284         }
 285
 286         return 0;
 287 }
 288
 289 static int hash_redo_key(struct btree_trans *trans,
 290                          const struct bch_hash_desc desc,
 291                          struct bch_hash_info *hash_info,
 292                          struct btree_iter *k_iter, struct bkey_s_c k)
 293 {
 294         struct bkey_i *delete;
 295         struct bkey_i *tmp;
 296
 297         delete = bch2_trans_kmalloc(trans, sizeof(*delete));
 298         if (IS_ERR(delete))
 299                 return PTR_ERR(delete);
 300
 301         tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
 302         if (IS_ERR(tmp))
 303                 return PTR_ERR(tmp);
 304
 305         bkey_reassemble(tmp, k);
 306
 307         bkey_init(&delete->k);
 308         delete->k.p = k_iter->pos;
 309         return  bch2_btree_iter_traverse(k_iter) ?:
 310                 bch2_trans_update(trans, k_iter, delete, 0) ?:
 311                 bch2_hash_set(trans, desc, hash_info, k_iter->pos.inode, tmp, 0);
 312 }
 313
 314 static int fsck_hash_delete_at(struct btree_trans *trans,
 315                                const struct bch_hash_desc desc,
 316                                struct bch_hash_info *info,
 317                                struct btree_iter *iter)
 318 {
 319         int ret;
 320 retry:
 321         ret   = bch2_hash_delete_at(trans, desc, info, iter) ?:
 322                 bch2_trans_commit(trans, NULL, NULL,
 323                                   BTREE_INSERT_NOFAIL|
 324                                   BTREE_INSERT_LAZY_RW);
 325         if (ret == -EINTR) {
 326                 ret = bch2_btree_iter_traverse(iter);
 327                 if (!ret)
 328                         goto retry;
 329         }
 330
 331         return ret;
 332 }
 333
 334 static int hash_check_key(struct btree_trans *trans,
 335                           const struct bch_hash_desc desc,
 336                           struct bch_hash_info *hash_info,
 337                           struct btree_iter *k_iter, struct bkey_s_c hash_k)
 338 {
 339         struct bch_fs *c = trans->c;
 340         struct btree_iter *iter = NULL;
 341         char buf[200];
 342         struct bkey_s_c k;
 343         u64 hash;
 344         int ret = 0;
 345
 346         if (hash_k.k->type != desc.key_type)
 347                 return 0;
 348
 349         hash = desc.hash_bkey(hash_info, hash_k);
 350
 351         if (likely(hash == hash_k.k->p.offset))
 352                 return 0;
 353
 354         if (hash_k.k->p.offset < hash)
 355                 goto bad_hash;
 356
 357         for_each_btree_key(trans, iter, desc.btree_id, POS(hash_k.k->p.inode, hash),
 358                            BTREE_ITER_SLOTS, k, ret) {
 359                 if (!bkey_cmp(k.k->p, hash_k.k->p))
 360                         break;
 361
 362                 if (fsck_err_on(k.k->type == desc.key_type &&
 363                                 !desc.cmp_bkey(k, hash_k), c,
 364                                 "duplicate hash table keys:\n%s",
 365                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 366                                                        hash_k), buf))) {
 367                         ret = fsck_hash_delete_at(trans, desc, hash_info, k_iter);
 368                         if (ret)
 369                                 return ret;
 370                         ret = 1;
 371                         break;
 372                 }
 373
 374                 if (bkey_deleted(k.k)) {
 375                         bch2_trans_iter_free(trans, iter);
 376                         goto bad_hash;
 377                 }
 378
 379         }
 380         bch2_trans_iter_free(trans, iter);
 381         return ret;
 382 bad_hash:
 383         if (fsck_err(c, "hash table key at wrong offset: btree %u inode %llu offset %llu, "
 384                      "hashed to %llu\n%s",
 385                      desc.btree_id, hash_k.k->p.inode, hash_k.k->p.offset, hash,
 386                      (bch2_bkey_val_to_text(&PBUF(buf), c, hash_k), buf)) == FSCK_ERR_IGNORE)
 387                 return 0;
 388
 389         ret = __bch2_trans_do(trans, NULL, NULL,
 390                               BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
 391                 hash_redo_key(trans, desc, hash_info, k_iter, hash_k));
 392         if (ret) {
 393                 bch_err(c, "hash_redo_key err %i", ret);
 394                 return ret;
 395         }
 396         return -EINTR;
 397 fsck_err:
 398         return ret;
 399 }
 400
 401 static int check_inode(struct btree_trans *trans,
 402                        struct btree_iter *iter,
 403                        struct bkey_s_c_inode inode)
 404 {
 405         struct bch_fs *c = trans->c;
 406         struct bch_inode_unpacked u;
 407         bool do_update = false;
 408         int ret = 0;
 409
 410         ret = bch2_inode_unpack(inode, &u);
 411
 412         if (bch2_fs_inconsistent_on(ret, c,
 413                          "error unpacking inode %llu in fsck",
 414                          inode.k->p.inode))
 415                 return ret;
 416
 417         if (u.bi_flags & BCH_INODE_UNLINKED &&
 418             (!c->sb.clean ||
 419              fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
 420                       u.bi_inum))) {
 421                 bch_verbose(c, "deleting inode %llu", u.bi_inum);
 422
 423                 bch2_trans_unlock(trans);
 424                 bch2_fs_lazy_rw(c);
 425
 426                 ret = bch2_inode_rm(c, u.bi_inum, false);
 427                 if (ret)
 428                         bch_err(c, "error in fsck: error %i while deleting inode", ret);
 429                 return ret;
 430         }
 431
 432         if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
 433             (!c->sb.clean ||
 434              fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
 435                       u.bi_inum))) {
 436                 bch_verbose(c, "truncating inode %llu", u.bi_inum);
 437
 438                 bch2_trans_unlock(trans);
 439                 bch2_fs_lazy_rw(c);
 440
 441                 /*
 442                  * XXX: need to truncate partial blocks too here - or ideally
 443                  * just switch units to bytes and that issue goes away
 444                  */
 445                 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
 446                                 POS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9),
 447                                 POS(u.bi_inum, U64_MAX),
 448                                 NULL);
 449                 if (ret) {
 450                         bch_err(c, "error in fsck: error %i truncating inode", ret);
 451                         return ret;
 452                 }
 453
 454                 /*
 455                  * We truncated without our normal sector accounting hook, just
 456                  * make sure we recalculate it:
 457                  */
 458                 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
 459
 460                 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
 461                 do_update = true;
 462         }
 463
 464         if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
 465             (!c->sb.clean ||
 466              fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
 467                       u.bi_inum))) {
 468                 s64 sectors;
 469
 470                 bch_verbose(c, "recounting sectors for inode %llu",
 471                             u.bi_inum);
 472
 473                 sectors = bch2_count_inode_sectors(trans, u.bi_inum);
 474                 if (sectors < 0) {
 475                         bch_err(c, "error in fsck: error %i recounting inode sectors",
 476                                 (int) sectors);
 477                         return sectors;
 478                 }
 479
 480                 u.bi_sectors = sectors;
 481                 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
 482                 do_update = true;
 483         }
 484
 485         if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) {
 486                 u.bi_dir = 0;
 487                 u.bi_dir_offset = 0;
 488                 u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED;
 489                 do_update = true;
 490         }
 491
 492         if (do_update) {
 493                 ret = __bch2_trans_do(trans, NULL, NULL,
 494                                       BTREE_INSERT_NOFAIL|
 495                                       BTREE_INSERT_LAZY_RW,
 496                                 bch2_btree_iter_traverse(iter) ?:
 497                                 bch2_inode_write(trans, iter, &u));
 498                 if (ret)
 499                         bch_err(c, "error in fsck: error %i "
 500                                 "updating inode", ret);
 501         }
 502 fsck_err:
 503         return ret;
 504 }
 505
 506 noinline_for_stack
 507 static int check_inodes(struct bch_fs *c, bool full)
 508 {
 509         struct btree_trans trans;
 510         struct btree_iter *iter;
 511         struct bkey_s_c k;
 512         struct bkey_s_c_inode inode;
 513         int ret;
 514
 515         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 516
 517         for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN,
 518                            BTREE_ITER_INTENT|
 519                            BTREE_ITER_PREFETCH, k, ret) {
 520                 if (k.k->type != KEY_TYPE_inode)
 521                         continue;
 522
 523                 inode = bkey_s_c_to_inode(k);
 524
 525                 if (full ||
 526                     (inode.v->bi_flags & (BCH_INODE_I_SIZE_DIRTY|
 527                                           BCH_INODE_I_SECTORS_DIRTY|
 528                                           BCH_INODE_UNLINKED))) {
 529                         ret = check_inode(&trans, iter, inode);
 530                         if (ret)
 531                                 break;
 532                 }
 533         }
 534         bch2_trans_iter_put(&trans, iter);
 535
 536         BUG_ON(ret == -EINTR);
 537
 538         return bch2_trans_exit(&trans) ?: ret;
 539 }
 540
 541 static int fix_overlapping_extent(struct btree_trans *trans,
 542                                        struct bkey_s_c k, struct bpos cut_at)
 543 {
 544         struct btree_iter *iter;
 545         struct bkey_i *u;
 546         int ret;
 547
 548         u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
 549         ret = PTR_ERR_OR_ZERO(u);
 550         if (ret)
 551                 return ret;
 552
 553         bkey_reassemble(u, k);
 554         bch2_cut_front(cut_at, u);
 555
 556
 557         /*
 558          * We don't want to go through the extent_handle_overwrites path:
 559          *
 560          * XXX: this is going to screw up disk accounting, extent triggers
 561          * assume things about extent overwrites - we should be running the
 562          * triggers manually here
 563          */
 564         iter = bch2_trans_get_iter(trans, BTREE_ID_extents, u->k.p,
 565                                    BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
 566
 567         BUG_ON(iter->flags & BTREE_ITER_IS_EXTENTS);
 568         ret   = bch2_btree_iter_traverse(iter) ?:
 569                 bch2_trans_update(trans, iter, u, BTREE_TRIGGER_NORUN) ?:
 570                 bch2_trans_commit(trans, NULL, NULL,
 571                                   BTREE_INSERT_NOFAIL|
 572                                   BTREE_INSERT_LAZY_RW);
 573         bch2_trans_iter_put(trans, iter);
 574         return ret;
 575 }
 576
 577 static int inode_backpointer_exists(struct btree_trans *trans,
 578                                     struct bch_inode_unpacked *inode)
 579 {
 580         struct btree_iter *iter;
 581         struct bkey_s_c k;
 582         int ret;
 583
 584         iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
 585                                    POS(inode->bi_dir, inode->bi_dir_offset), 0);
 586         k = bch2_btree_iter_peek_slot(iter);
 587         ret = bkey_err(k);
 588         if (ret)
 589                 goto out;
 590         if (k.k->type != KEY_TYPE_dirent)
 591                 goto out;
 592
 593         ret = le64_to_cpu(bkey_s_c_to_dirent(k).v->d_inum) == inode->bi_inum;
 594 out:
 595         bch2_trans_iter_free(trans, iter);
 596         return ret;
 597 }
 598
 599 static bool inode_backpointer_matches(struct bkey_s_c_dirent d,
 600                                       struct bch_inode_unpacked *inode)
 601 {
 602         return d.k->p.inode == inode->bi_dir &&
 603                 d.k->p.offset == inode->bi_dir_offset;
 604 }
 605
 606 /*
 607  * Walk extents: verify that extents have a corresponding S_ISREG inode, and
 608  * that i_size an i_sectors are consistent
 609  */
 610 noinline_for_stack
 611 static int check_extents(struct bch_fs *c)
 612 {
 613         struct inode_walker w = inode_walker_init();
 614         struct btree_trans trans;
 615         struct btree_iter *iter;
 616         struct bkey_s_c k;
 617         struct bkey_buf prev;
 618         u64 i_sectors = 0;
 619         int ret = 0;
 620
 621         bch2_bkey_buf_init(&prev);
 622         prev.k->k = KEY(0, 0, 0);
 623         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 624
 625         bch_verbose(c, "checking extents");
 626
 627         iter = bch2_trans_get_iter(&trans, BTREE_ID_extents,
 628                                    POS(BCACHEFS_ROOT_INO, 0),
 629                                    BTREE_ITER_INTENT|
 630                                    BTREE_ITER_PREFETCH);
 631 retry:
 632         while ((k = bch2_btree_iter_peek(iter)).k &&
 633                !(ret = bkey_err(k))) {
 634                 if (w.have_inode &&
 635                     w.cur_inum != k.k->p.inode &&
 636                     !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) &&
 637                     fsck_err_on(w.inode.bi_sectors != i_sectors, c,
 638                                 "inode %llu has incorrect i_sectors: got %llu, should be %llu",
 639                                 w.inode.bi_inum,
 640                                 w.inode.bi_sectors, i_sectors)) {
 641                         w.inode.bi_sectors = i_sectors;
 642
 643                         ret = write_inode(&trans, &w.inode, w.snapshot);
 644                         if (ret)
 645                                 break;
 646                 }
 647
 648                 if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) {
 649                         char buf1[200];
 650                         char buf2[200];
 651
 652                         bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k));
 653                         bch2_bkey_val_to_text(&PBUF(buf2), c, k);
 654
 655                         if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2))
 656                                 return fix_overlapping_extent(&trans, k, prev.k->k.p) ?: -EINTR;
 657                 }
 658
 659                 ret = walk_inode(&trans, &w, k.k->p.inode);
 660                 if (ret)
 661                         break;
 662
 663                 if (w.first_this_inode)
 664                         i_sectors = 0;
 665
 666                 if (fsck_err_on(!w.have_inode, c,
 667                                 "extent type %u for missing inode %llu",
 668                                 k.k->type, k.k->p.inode) ||
 669                     fsck_err_on(w.have_inode &&
 670                                 !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c,
 671                                 "extent type %u for non regular file, inode %llu mode %o",
 672                                 k.k->type, k.k->p.inode, w.inode.bi_mode)) {
 673                         bch2_fs_lazy_rw(c);
 674                         return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
 675                                                        POS(k.k->p.inode, 0),
 676                                                        POS(k.k->p.inode, U64_MAX),
 677                                                        NULL) ?: -EINTR;
 678                 }
 679
 680                 if (fsck_err_on(w.have_inode &&
 681                                 !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
 682                                 k.k->type != KEY_TYPE_reservation &&
 683                                 k.k->p.offset > round_up(w.inode.bi_size, block_bytes(c)) >> 9, c,
 684                                 "extent type %u offset %llu past end of inode %llu, i_size %llu",
 685                                 k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) {
 686                         bch2_fs_lazy_rw(c);
 687                         return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
 688                                         POS(k.k->p.inode, round_up(w.inode.bi_size, block_bytes(c)) >> 9),
 689                                         POS(k.k->p.inode, U64_MAX),
 690                                         NULL) ?: -EINTR;
 691                 }
 692
 693                 if (bkey_extent_is_allocation(k.k))
 694                         i_sectors += k.k->size;
 695                 bch2_bkey_buf_reassemble(&prev, c, k);
 696
 697                 bch2_btree_iter_advance(iter);
 698         }
 699 fsck_err:
 700         if (ret == -EINTR)
 701                 goto retry;
 702         bch2_trans_iter_put(&trans, iter);
 703         bch2_bkey_buf_exit(&prev, c);
 704         return bch2_trans_exit(&trans) ?: ret;
 705 }
 706
 707 /*
 708  * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
 709  * validate d_type
 710  */
 711 noinline_for_stack
 712 static int check_dirents(struct bch_fs *c)
 713 {
 714         struct inode_walker w = inode_walker_init();
 715         struct bch_hash_info hash_info;
 716         struct btree_trans trans;
 717         struct btree_iter *iter;
 718         struct bkey_s_c k;
 719         char buf[200];
 720         unsigned nr_subdirs = 0;
 721         int ret = 0;
 722
 723         bch_verbose(c, "checking dirents");
 724
 725         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 726
 727         iter = bch2_trans_get_iter(&trans, BTREE_ID_dirents,
 728                                    POS(BCACHEFS_ROOT_INO, 0),
 729                                    BTREE_ITER_INTENT|
 730                                    BTREE_ITER_PREFETCH);
 731 retry:
 732         while ((k = bch2_btree_iter_peek(iter)).k &&
 733                !(ret = bkey_err(k))) {
 734                 struct bkey_s_c_dirent d;
 735                 struct bch_inode_unpacked target;
 736                 u32 target_snapshot;
 737                 bool have_target;
 738                 bool backpointer_exists = true;
 739                 u64 d_inum;
 740
 741                 if (w.have_inode &&
 742                     w.cur_inum != k.k->p.inode &&
 743                     fsck_err_on(w.inode.bi_nlink != nr_subdirs, c,
 744                                 "directory %llu with wrong i_nlink: got %u, should be %u",
 745                                 w.inode.bi_inum, w.inode.bi_nlink, nr_subdirs)) {
 746                         w.inode.bi_nlink = nr_subdirs;
 747                         ret = write_inode(&trans, &w.inode, w.snapshot);
 748                         if (ret)
 749                                 break;
 750                 }
 751
 752                 ret = walk_inode(&trans, &w, k.k->p.inode);
 753                 if (ret)
 754                         break;
 755
 756                 if (w.first_this_inode)
 757                         nr_subdirs = 0;
 758
 759                 if (fsck_err_on(!w.have_inode, c,
 760                                 "dirent in nonexisting directory:\n%s",
 761                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 762                                                        k), buf)) ||
 763                     fsck_err_on(!S_ISDIR(w.inode.bi_mode), c,
 764                                 "dirent in non directory inode type %u:\n%s",
 765                                 mode_to_type(w.inode.bi_mode),
 766                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 767                                                        k), buf))) {
 768                         ret = __bch2_trans_do(&trans, NULL, NULL, 0,
 769                                         bch2_btree_delete_at(&trans, iter, 0));
 770                         if (ret)
 771                                 goto err;
 772                         goto next;
 773                 }
 774
 775                 if (!w.have_inode)
 776                         goto next;
 777
 778                 if (w.first_this_inode)
 779                         hash_info = bch2_hash_info_init(c, &w.inode);
 780
 781                 ret = hash_check_key(&trans, bch2_dirent_hash_desc,
 782                                      &hash_info, iter, k);
 783                 if (ret > 0) {
 784                         ret = 0;
 785                         goto next;
 786                 }
 787                 if (ret)
 788                         goto fsck_err;
 789
 790                 if (k.k->type != KEY_TYPE_dirent)
 791                         goto next;
 792
 793                 d = bkey_s_c_to_dirent(k);
 794                 d_inum = le64_to_cpu(d.v->d_inum);
 795
 796                 ret = lookup_inode(&trans, d_inum, &target, &target_snapshot);
 797                 if (ret && ret != -ENOENT)
 798                         break;
 799
 800                 have_target = !ret;
 801                 ret = 0;
 802
 803                 if (fsck_err_on(!have_target, c,
 804                                 "dirent points to missing inode:\n%s",
 805                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 806                                                        k), buf))) {
 807                         ret = remove_dirent(&trans, d.k->p);
 808                         if (ret)
 809                                 goto err;
 810                         goto next;
 811                 }
 812
 813                 if (!have_target)
 814                         goto next;
 815
 816                 if (!target.bi_dir &&
 817                     !target.bi_dir_offset) {
 818                         target.bi_dir           = k.k->p.inode;
 819                         target.bi_dir_offset    = k.k->p.offset;
 820
 821                         ret = write_inode(&trans, &target, target_snapshot);
 822                         if (ret)
 823                                 goto err;
 824                 }
 825
 826                 if (!inode_backpointer_matches(d, &target)) {
 827                         ret = inode_backpointer_exists(&trans, &target);
 828                         if (ret < 0)
 829                                 goto err;
 830
 831                         backpointer_exists = ret;
 832                         ret = 0;
 833
 834                         if (fsck_err_on(S_ISDIR(target.bi_mode) &&
 835                                         backpointer_exists, c,
 836                                         "directory %llu with multiple links",
 837                                         target.bi_inum)) {
 838                                 ret = remove_dirent(&trans, d.k->p);
 839                                 if (ret)
 840                                         goto err;
 841                                 continue;
 842                         }
 843
 844                         if (fsck_err_on(backpointer_exists &&
 845                                         !target.bi_nlink, c,
 846                                         "inode %llu has multiple links but i_nlink 0",
 847                                         d_inum)) {
 848                                 target.bi_nlink++;
 849                                 target.bi_flags &= ~BCH_INODE_UNLINKED;
 850
 851                                 ret = write_inode(&trans, &target, target_snapshot);
 852                                 if (ret)
 853                                         goto err;
 854                         }
 855
 856                         if (fsck_err_on(!backpointer_exists, c,
 857                                         "inode %llu has wrong backpointer:\n"
 858                                         "got       %llu:%llu\n"
 859                                         "should be %llu:%llu",
 860                                         d_inum,
 861                                         target.bi_dir,
 862                                         target.bi_dir_offset,
 863                                         k.k->p.inode,
 864                                         k.k->p.offset)) {
 865                                 target.bi_dir           = k.k->p.inode;
 866                                 target.bi_dir_offset    = k.k->p.offset;
 867
 868                                 ret = write_inode(&trans, &target, target_snapshot);
 869                                 if (ret)
 870                                         goto err;
 871                         }
 872                 }
 873
 874                 if (fsck_err_on(d.v->d_type != mode_to_type(target.bi_mode), c,
 875                                 "incorrect d_type: should be %u:\n%s",
 876                                 mode_to_type(target.bi_mode),
 877                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 878                                                        k), buf))) {
 879                         struct bkey_i_dirent *n;
 880
 881                         n = kmalloc(bkey_bytes(d.k), GFP_KERNEL);
 882                         if (!n) {
 883                                 ret = -ENOMEM;
 884                                 goto err;
 885                         }
 886
 887                         bkey_reassemble(&n->k_i, d.s_c);
 888                         n->v.d_type = mode_to_type(target.bi_mode);
 889
 890                         ret = __bch2_trans_do(&trans, NULL, NULL,
 891                                               BTREE_INSERT_NOFAIL|
 892                                               BTREE_INSERT_LAZY_RW,
 893                                 bch2_btree_iter_traverse(iter) ?:
 894                                 bch2_trans_update(&trans, iter, &n->k_i, 0));
 895                         kfree(n);
 896                         if (ret)
 897                                 goto err;
 898
 899                 }
 900
 901                 nr_subdirs += d.v->d_type == DT_DIR;
 902 next:
 903                 bch2_btree_iter_advance(iter);
 904         }
 905 err:
 906 fsck_err:
 907         if (ret == -EINTR)
 908                 goto retry;
 909
 910         bch2_trans_iter_put(&trans, iter);
 911         return bch2_trans_exit(&trans) ?: ret;
 912 }
 913
 914 /*
 915  * Walk xattrs: verify that they all have a corresponding inode
 916  */
 917 noinline_for_stack
 918 static int check_xattrs(struct bch_fs *c)
 919 {
 920         struct inode_walker w = inode_walker_init();
 921         struct bch_hash_info hash_info;
 922         struct btree_trans trans;
 923         struct btree_iter *iter;
 924         struct bkey_s_c k;
 925         int ret = 0;
 926
 927         bch_verbose(c, "checking xattrs");
 928
 929         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 930
 931         iter = bch2_trans_get_iter(&trans, BTREE_ID_xattrs,
 932                                    POS(BCACHEFS_ROOT_INO, 0),
 933                                    BTREE_ITER_INTENT|
 934                                    BTREE_ITER_PREFETCH);
 935 retry:
 936         while ((k = bch2_btree_iter_peek(iter)).k &&
 937                !(ret = bkey_err(k))) {
 938                 ret = walk_inode(&trans, &w, k.k->p.inode);
 939                 if (ret)
 940                         break;
 941
 942                 if (fsck_err_on(!w.have_inode, c,
 943                                 "xattr for missing inode %llu",
 944                                 k.k->p.inode)) {
 945                         ret = bch2_btree_delete_at(&trans, iter, 0);
 946                         if (ret)
 947                                 break;
 948                         continue;
 949                 }
 950
 951                 if (w.first_this_inode && w.have_inode)
 952                         hash_info = bch2_hash_info_init(c, &w.inode);
 953
 954                 ret = hash_check_key(&trans, bch2_xattr_hash_desc,
 955                                      &hash_info, iter, k);
 956                 if (ret)
 957                         break;
 958
 959                 bch2_btree_iter_advance(iter);
 960         }
 961 fsck_err:
 962         if (ret == -EINTR)
 963                 goto retry;
 964
 965         bch2_trans_iter_put(&trans, iter);
 966         return bch2_trans_exit(&trans) ?: ret;
 967 }
 968
 969 /* Get root directory, create if it doesn't exist: */
 970 static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode)
 971 {
 972         struct bkey_inode_buf packed;
 973         u32 snapshot;
 974         int ret;
 975
 976         bch_verbose(c, "checking root directory");
 977
 978         ret = bch2_trans_do(c, NULL, NULL, 0,
 979                 lookup_inode(&trans, BCACHEFS_ROOT_INO, root_inode, &snapshot));
 980         if (ret && ret != -ENOENT)
 981                 return ret;
 982
 983         if (fsck_err_on(ret, c, "root directory missing"))
 984                 goto create_root;
 985
 986         if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c,
 987                         "root inode not a directory"))
 988                 goto create_root;
 989
 990         return 0;
 991 fsck_err:
 992         return ret;
 993 create_root:
 994         bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|0755,
 995                         0, NULL);
 996         root_inode->bi_inum = BCACHEFS_ROOT_INO;
 997
 998         bch2_inode_pack(c, &packed, root_inode);
 999
1000         return bch2_btree_insert(c, BTREE_ID_inodes, &packed.inode.k_i,
1001                                  NULL, NULL,
1002                                  BTREE_INSERT_NOFAIL|
1003                                  BTREE_INSERT_LAZY_RW);
1004 }
1005
1006 struct pathbuf {
1007         size_t          nr;
1008         size_t          size;
1009
1010         struct pathbuf_entry {
1011                 u64     inum;
1012         }               *entries;
1013 };
1014
1015 static int path_down(struct pathbuf *p, u64 inum)
1016 {
1017         if (p->nr == p->size) {
1018                 size_t new_size = max_t(size_t, 256UL, p->size * 2);
1019                 void *n = krealloc(p->entries,
1020                                    new_size * sizeof(p->entries[0]),
1021                                    GFP_KERNEL);
1022                 if (!n) {
1023                         return -ENOMEM;
1024                 }
1025
1026                 p->entries = n;
1027                 p->size = new_size;
1028         };
1029
1030         p->entries[p->nr++] = (struct pathbuf_entry) {
1031                 .inum = inum,
1032         };
1033         return 0;
1034 }
1035
1036 static int check_path(struct btree_trans *trans,
1037                       struct pathbuf *p,
1038                       struct bch_inode_unpacked *inode)
1039 {
1040         struct bch_fs *c = trans->c;
1041         u32 snapshot;
1042         size_t i;
1043         int ret = 0;
1044
1045         p->nr = 0;
1046
1047         while (inode->bi_inum != BCACHEFS_ROOT_INO) {
1048                 ret = lockrestart_do(trans,
1049                         inode_backpointer_exists(trans, inode));
1050                 if (ret < 0)
1051                         break;
1052
1053                 if (!ret) {
1054                         if (fsck_err(c,  "unreachable inode %llu, type %u nlink %u backptr %llu:%llu",
1055                                      inode->bi_inum,
1056                                      mode_to_type(inode->bi_mode),
1057                                      inode->bi_nlink,
1058                                      inode->bi_dir,
1059                                      inode->bi_dir_offset))
1060                                 ret = reattach_inode(trans, inode);
1061                         break;
1062                 }
1063                 ret = 0;
1064
1065                 if (!S_ISDIR(inode->bi_mode))
1066                         break;
1067
1068                 ret = path_down(p, inode->bi_inum);
1069                 if (ret) {
1070                         bch_err(c, "memory allocation failure");
1071                         return ret;
1072                 }
1073
1074                 for (i = 0; i < p->nr; i++) {
1075                         if (inode->bi_dir != p->entries[i].inum)
1076                                 continue;
1077
1078                         /* XXX print path */
1079                         if (!fsck_err(c, "directory structure loop"))
1080                                 return 0;
1081
1082                         ret = lockrestart_do(trans,
1083                                          remove_backpointer(trans, inode));
1084                         if (ret) {
1085                                 bch_err(c, "error removing dirent: %i", ret);
1086                                 break;
1087                         }
1088
1089                         ret = reattach_inode(trans, inode);
1090                         break;
1091                 }
1092
1093                 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot);
1094                 if (ret) {
1095                         /* Should have been caught in dirents pass */
1096                         bch_err(c, "error looking up parent directory: %i", ret);
1097                         break;
1098                 }
1099         }
1100 fsck_err:
1101         if (ret)
1102                 bch_err(c, "%s: err %i", __func__, ret);
1103         return ret;
1104 }
1105
1106 /*
1107  * Check for unreachable inodes, as well as loops in the directory structure:
1108  * After check_dirents(), if an inode backpointer doesn't exist that means it's
1109  * unreachable:
1110  */
1111 static int check_directory_structure(struct bch_fs *c)
1112 {
1113         struct btree_trans trans;
1114         struct btree_iter *iter;
1115         struct bkey_s_c k;
1116         struct bch_inode_unpacked u;
1117         struct pathbuf path = { 0, 0, NULL };
1118         int ret;
1119
1120         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1121
1122         for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN,
1123                            BTREE_ITER_INTENT|
1124                            BTREE_ITER_PREFETCH, k, ret) {
1125                 if (k.k->type != KEY_TYPE_inode)
1126                         continue;
1127
1128                 ret = bch2_inode_unpack(bkey_s_c_to_inode(k), &u);
1129                 if (ret) {
1130                         /* Should have been caught earlier in fsck: */
1131                         bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
1132                         break;
1133                 }
1134
1135                 ret = check_path(&trans, &path, &u);
1136                 if (ret)
1137                         break;
1138         }
1139         bch2_trans_iter_put(&trans, iter);
1140
1141         BUG_ON(ret == -EINTR);
1142
1143         kfree(path.entries);
1144
1145         return bch2_trans_exit(&trans) ?: ret;
1146 }
1147
1148 struct nlink_table {
1149         size_t          nr;
1150         size_t          size;
1151
1152         struct nlink {
1153                 u64     inum;
1154                 u32     snapshot;
1155                 u32     count;
1156         }               *d;
1157 };
1158
1159 static int add_nlink(struct nlink_table *t, u64 inum, u32 snapshot)
1160 {
1161         if (t->nr == t->size) {
1162                 size_t new_size = max_t(size_t, 128UL, t->size * 2);
1163                 void *d = kvmalloc(new_size * sizeof(t->d[0]), GFP_KERNEL);
1164                 if (!d) {
1165                         return -ENOMEM;
1166                 }
1167
1168                 if (t->d)
1169                         memcpy(d, t->d, t->size * sizeof(t->d[0]));
1170                 kvfree(t->d);
1171
1172                 t->d = d;
1173                 t->size = new_size;
1174         }
1175
1176
1177         t->d[t->nr++] = (struct nlink) {
1178                 .inum           = inum,
1179                 .snapshot       = snapshot,
1180         };
1181
1182         return 0;
1183 }
1184
1185 static int nlink_cmp(const void *_l, const void *_r)
1186 {
1187         const struct nlink *l = _l;
1188         const struct nlink *r = _r;
1189
1190         return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot);
1191 }
1192
1193 static void inc_link(struct bch_fs *c, struct nlink_table *links,
1194                      u64 range_start, u64 range_end, u64 inum)
1195 {
1196         struct nlink *link, key = {
1197                 .inum = inum, .snapshot = U32_MAX,
1198         };
1199
1200         if (inum < range_start || inum >= range_end)
1201                 return;
1202
1203         link = __inline_bsearch(&key, links->d, links->nr,
1204                                 sizeof(links->d[0]), nlink_cmp);
1205         if (link)
1206                 link->count++;
1207 }
1208
1209 noinline_for_stack
1210 static int check_nlinks_find_hardlinks(struct bch_fs *c,
1211                                        struct nlink_table *t,
1212                                        u64 start, u64 *end)
1213 {
1214         struct btree_trans trans;
1215         struct btree_iter *iter;
1216         struct bkey_s_c k;
1217         struct bkey_s_c_inode inode;
1218         struct bch_inode_unpacked u;
1219         int ret = 0;
1220
1221         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1222
1223         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
1224                            POS(0, start),
1225                            BTREE_ITER_INTENT|
1226                            BTREE_ITER_PREFETCH, k, ret) {
1227                 if (k.k->type != KEY_TYPE_inode)
1228                         continue;
1229
1230                 inode = bkey_s_c_to_inode(k);
1231
1232                 /*
1233                  * Backpointer and directory structure checks are sufficient for
1234                  * directories, since they can't have hardlinks:
1235                  */
1236                 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
1237                         continue;
1238
1239                 /* Should never fail, checked by bch2_inode_invalid: */
1240                 BUG_ON(bch2_inode_unpack(inode, &u));
1241
1242                 if (!u.bi_nlink)
1243                         continue;
1244
1245                 ret = add_nlink(t, k.k->p.offset, k.k->p.snapshot);
1246                 if (ret) {
1247                         *end = k.k->p.offset;
1248                         ret = 0;
1249                         break;
1250                 }
1251
1252         }
1253         bch2_trans_iter_put(&trans, iter);
1254         bch2_trans_exit(&trans);
1255
1256         if (ret)
1257                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
1258
1259         return ret;
1260 }
1261
1262 noinline_for_stack
1263 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
1264                                      u64 range_start, u64 range_end)
1265 {
1266         struct btree_trans trans;
1267         struct btree_iter *iter;
1268         struct bkey_s_c k;
1269         struct bkey_s_c_dirent d;
1270         int ret;
1271
1272         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1273
1274         for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN,
1275                            BTREE_ITER_INTENT|
1276                            BTREE_ITER_PREFETCH, k, ret) {
1277                 switch (k.k->type) {
1278                 case KEY_TYPE_dirent:
1279                         d = bkey_s_c_to_dirent(k);
1280
1281                         if (d.v->d_type != DT_DIR)
1282                                 inc_link(c, links, range_start, range_end,
1283                                          le64_to_cpu(d.v->d_inum));
1284                         break;
1285                 }
1286
1287                 bch2_trans_cond_resched(&trans);
1288         }
1289         bch2_trans_iter_put(&trans, iter);
1290
1291         ret = bch2_trans_exit(&trans) ?: ret;
1292         if (ret)
1293                 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
1294
1295         return ret;
1296 }
1297
1298 noinline_for_stack
1299 static int check_nlinks_update_hardlinks(struct bch_fs *c,
1300                                struct nlink_table *links,
1301                                u64 range_start, u64 range_end)
1302 {
1303         struct btree_trans trans;
1304         struct btree_iter *iter;
1305         struct bkey_s_c k;
1306         struct bkey_s_c_inode inode;
1307         struct bch_inode_unpacked u;
1308         struct nlink *link = links->d;
1309         int ret = 0;
1310
1311         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1312
1313         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
1314                            POS(0, range_start),
1315                            BTREE_ITER_INTENT|
1316                            BTREE_ITER_PREFETCH, k, ret) {
1317                 if (k.k->p.offset >= range_end)
1318                         break;
1319
1320                 if (k.k->type != KEY_TYPE_inode)
1321                         continue;
1322
1323                 inode = bkey_s_c_to_inode(k);
1324                 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
1325                         continue;
1326
1327                 BUG_ON(bch2_inode_unpack(inode, &u));
1328
1329                 if (!u.bi_nlink)
1330                         continue;
1331
1332                 while (link->inum < k.k->p.offset) {
1333                         link++;
1334                         BUG_ON(link >= links->d + links->nr);
1335                 }
1336
1337                 if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c,
1338                                 "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)",
1339                                 u.bi_inum, mode_to_type(u.bi_mode),
1340                                 bch2_inode_nlink_get(&u), link->count)) {
1341                         bch2_inode_nlink_set(&u, link->count);
1342
1343                         ret = __bch2_trans_do(&trans, NULL, NULL,
1344                                               BTREE_INSERT_NOFAIL|
1345                                               BTREE_INSERT_LAZY_RW,
1346                                               bch2_btree_iter_traverse(iter) ?:
1347                                         bch2_inode_write(&trans, iter, &u));
1348                         if (ret)
1349                                 bch_err(c, "error in fsck: error %i updating inode", ret);
1350                 }
1351         }
1352 fsck_err:
1353         bch2_trans_iter_put(&trans, iter);
1354         bch2_trans_exit(&trans);
1355
1356         if (ret)
1357                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
1358
1359         return ret;
1360 }
1361
1362 noinline_for_stack
1363 static int check_nlinks(struct bch_fs *c)
1364 {
1365         struct nlink_table links = { 0 };
1366         u64 this_iter_range_start, next_iter_range_start = 0;
1367         int ret = 0;
1368
1369         bch_verbose(c, "checking inode nlinks");
1370
1371         do {
1372                 this_iter_range_start = next_iter_range_start;
1373                 next_iter_range_start = U64_MAX;
1374
1375                 ret = check_nlinks_find_hardlinks(c, &links,
1376                                                   this_iter_range_start,
1377                                                   &next_iter_range_start);
1378
1379                 ret = check_nlinks_walk_dirents(c, &links,
1380                                           this_iter_range_start,
1381                                           next_iter_range_start);
1382                 if (ret)
1383                         break;
1384
1385                 ret = check_nlinks_update_hardlinks(c, &links,
1386                                          this_iter_range_start,
1387                                          next_iter_range_start);
1388                 if (ret)
1389                         break;
1390
1391                 links.nr = 0;
1392         } while (next_iter_range_start != U64_MAX);
1393
1394         kvfree(links.d);
1395
1396         return ret;
1397 }
1398
1399 /*
1400  * Checks for inconsistencies that shouldn't happen, unless we have a bug.
1401  * Doesn't fix them yet, mainly because they haven't yet been observed:
1402  */
1403 int bch2_fsck_full(struct bch_fs *c)
1404 {
1405         struct bch_inode_unpacked root_inode;
1406
1407         return  check_inodes(c, true) ?:
1408                 check_extents(c) ?:
1409                 check_dirents(c) ?:
1410                 check_xattrs(c) ?:
1411                 check_root(c, &root_inode) ?:
1412                 check_directory_structure(c) ?:
1413                 check_nlinks(c);
1414 }
1415
1416 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
1417 {
1418         return check_inodes(c, false);
1419 }