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