git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/fsck.c

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