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