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