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