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

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "bkey_buf.h"
   5 #include "btree_update.h"
   6 #include "dirent.h"
   7 #include "error.h"
   8 #include "fs-common.h"
   9 #include "fsck.h"
  10 #include "inode.h"
  11 #include "keylist.h"
  12 #include "subvolume.h"
  13 #include "super.h"
  14 #include "xattr.h"
  15
  16 #include <linux/bsearch.h>
  17 #include <linux/dcache.h> /* struct qstr */
  18
  19 #define QSTR(n) { { { .len = strlen(n) } }, .name = n }
  20
  21 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum,
  22                                     u32 snapshot)
  23 {
  24         struct btree_iter iter;
  25         struct bkey_s_c k;
  26         u64 sectors = 0;
  27         int ret;
  28
  29         for_each_btree_key(trans, iter, BTREE_ID_extents,
  30                            SPOS(inum, 0, snapshot), 0, k, ret) {
  31                 if (k.k->p.inode != inum)
  32                         break;
  33
  34                 if (bkey_extent_is_allocation(k.k))
  35                         sectors += k.k->size;
  36         }
  37
  38         bch2_trans_iter_exit(trans, &iter);
  39
  40         return ret ?: sectors;
  41 }
  42
  43 static s64 bch2_count_subdirs(struct btree_trans *trans, u64 inum,
  44                                     u32 snapshot)
  45 {
  46         struct btree_iter iter;
  47         struct bkey_s_c k;
  48         struct bkey_s_c_dirent d;
  49         u64 subdirs = 0;
  50         int ret;
  51
  52         for_each_btree_key(trans, iter, BTREE_ID_dirents,
  53                            SPOS(inum, 0, snapshot), 0, k, ret) {
  54                 if (k.k->p.inode != inum)
  55                         break;
  56
  57                 if (k.k->type != KEY_TYPE_dirent)
  58                         continue;
  59
  60                 d = bkey_s_c_to_dirent(k);
  61                 if (d.v->d_type == DT_DIR)
  62                         subdirs++;
  63         }
  64
  65         bch2_trans_iter_exit(trans, &iter);
  66
  67         return ret ?: subdirs;
  68 }
  69
  70 static int __snapshot_lookup_subvol(struct btree_trans *trans, u32 snapshot,
  71                                     u32 *subvol)
  72 {
  73         struct btree_iter iter;
  74         struct bkey_s_c k;
  75         int ret;
  76
  77         bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
  78                              POS(0, snapshot), 0);
  79         k = bch2_btree_iter_peek_slot(&iter);
  80         ret = bkey_err(k);
  81         if (ret)
  82                 goto err;
  83
  84         if (k.k->type != KEY_TYPE_snapshot) {
  85                 bch_err(trans->c, "snapshot %u not fonud", snapshot);
  86                 ret = -ENOENT;
  87                 goto err;
  88         }
  89
  90         *subvol = le32_to_cpu(bkey_s_c_to_snapshot(k).v->subvol);
  91 err:
  92         bch2_trans_iter_exit(trans, &iter);
  93         return ret;
  94
  95 }
  96
  97 static int __subvol_lookup(struct btree_trans *trans, u32 subvol,
  98                            u32 *snapshot, u64 *inum)
  99 {
 100         struct bch_subvolume s;
 101         int ret;
 102
 103         ret = bch2_subvolume_get(trans, subvol, false, 0, &s);
 104
 105         *snapshot = le32_to_cpu(s.snapshot);
 106         *inum = le64_to_cpu(s.inode);
 107         return ret;
 108 }
 109
 110 static int subvol_lookup(struct btree_trans *trans, u32 subvol,
 111                          u32 *snapshot, u64 *inum)
 112 {
 113         return lockrestart_do(trans, __subvol_lookup(trans, subvol, snapshot, inum));
 114 }
 115
 116 static int lookup_first_inode(struct btree_trans *trans, u64 inode_nr,
 117                               struct bch_inode_unpacked *inode)
 118 {
 119         struct btree_iter iter;
 120         struct bkey_s_c k;
 121         int ret;
 122
 123         bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
 124                              POS(0, inode_nr),
 125                              BTREE_ITER_ALL_SNAPSHOTS);
 126         k = bch2_btree_iter_peek(&iter);
 127         ret = bkey_err(k);
 128         if (ret)
 129                 goto err;
 130
 131         if (!k.k || bkey_cmp(k.k->p, POS(0, inode_nr))) {
 132                 ret = -ENOENT;
 133                 goto err;
 134         }
 135
 136         ret = bch2_inode_unpack(bkey_s_c_to_inode(k), inode);
 137 err:
 138         if (ret && ret != -EINTR)
 139                 bch_err(trans->c, "error %i fetching inode %llu",
 140                         ret, inode_nr);
 141         bch2_trans_iter_exit(trans, &iter);
 142         return ret;
 143 }
 144
 145 static int __lookup_inode(struct btree_trans *trans, u64 inode_nr,
 146                           struct bch_inode_unpacked *inode,
 147                           u32 *snapshot)
 148 {
 149         struct btree_iter iter;
 150         struct bkey_s_c k;
 151         int ret;
 152
 153         bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
 154                              SPOS(0, inode_nr, *snapshot), 0);
 155         k = bch2_btree_iter_peek_slot(&iter);
 156         ret = bkey_err(k);
 157         if (ret)
 158                 goto err;
 159
 160         ret = k.k->type == KEY_TYPE_inode
 161                 ? bch2_inode_unpack(bkey_s_c_to_inode(k), inode)
 162                 : -ENOENT;
 163         if (!ret)
 164                 *snapshot = iter.pos.snapshot;
 165 err:
 166         if (ret && ret != -EINTR)
 167                 bch_err(trans->c, "error %i fetching inode %llu:%u",
 168                         ret, inode_nr, *snapshot);
 169         bch2_trans_iter_exit(trans, &iter);
 170         return ret;
 171 }
 172
 173 static int lookup_inode(struct btree_trans *trans, u64 inode_nr,
 174                         struct bch_inode_unpacked *inode,
 175                         u32 *snapshot)
 176 {
 177         return lockrestart_do(trans, __lookup_inode(trans, inode_nr, inode, snapshot));
 178 }
 179
 180 static int __lookup_dirent(struct btree_trans *trans,
 181                            struct bch_hash_info hash_info,
 182                            subvol_inum dir, struct qstr *name,
 183                            u64 *target, unsigned *type)
 184 {
 185         struct btree_iter iter;
 186         struct bkey_s_c_dirent d;
 187         int ret;
 188
 189         ret = bch2_hash_lookup(trans, &iter, bch2_dirent_hash_desc,
 190                                &hash_info, dir, name, 0);
 191         if (ret)
 192                 return ret;
 193
 194         d = bkey_s_c_to_dirent(bch2_btree_iter_peek_slot(&iter));
 195         *target = le64_to_cpu(d.v->d_inum);
 196         *type = d.v->d_type;
 197         bch2_trans_iter_exit(trans, &iter);
 198         return 0;
 199 }
 200
 201 static int __write_inode(struct btree_trans *trans,
 202                          struct bch_inode_unpacked *inode,
 203                          u32 snapshot)
 204 {
 205         struct btree_iter iter;
 206         int ret;
 207
 208         bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
 209                             SPOS(0, inode->bi_inum, snapshot),
 210                             BTREE_ITER_INTENT);
 211
 212         ret   = bch2_btree_iter_traverse(&iter) ?:
 213                 bch2_inode_write(trans, &iter, inode);
 214         bch2_trans_iter_exit(trans, &iter);
 215         return ret;
 216 }
 217
 218 static int write_inode(struct btree_trans *trans,
 219                        struct bch_inode_unpacked *inode,
 220                        u32 snapshot)
 221 {
 222         int ret = __bch2_trans_do(trans, NULL, NULL,
 223                                   BTREE_INSERT_NOFAIL|
 224                                   BTREE_INSERT_LAZY_RW,
 225                                   __write_inode(trans, inode, snapshot));
 226         if (ret)
 227                 bch_err(trans->c, "error in fsck: error %i updating inode", ret);
 228         return ret;
 229 }
 230
 231 static int fsck_inode_rm(struct btree_trans *trans, u64 inum, u32 snapshot)
 232 {
 233         struct btree_iter iter = { NULL };
 234         struct bkey_i_inode_generation delete;
 235         struct bch_inode_unpacked inode_u;
 236         struct bkey_s_c k;
 237         int ret;
 238
 239         ret   = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
 240                                               SPOS(inum, 0, snapshot),
 241                                               SPOS(inum, U64_MAX, snapshot),
 242                                               0, NULL) ?:
 243                 bch2_btree_delete_range_trans(trans, BTREE_ID_dirents,
 244                                               SPOS(inum, 0, snapshot),
 245                                               SPOS(inum, U64_MAX, snapshot),
 246                                               0, NULL) ?:
 247                 bch2_btree_delete_range_trans(trans, BTREE_ID_xattrs,
 248                                               SPOS(inum, 0, snapshot),
 249                                               SPOS(inum, U64_MAX, snapshot),
 250                                               0, NULL);
 251         if (ret)
 252                 goto err;
 253 retry:
 254         bch2_trans_begin(trans);
 255
 256         bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
 257                              SPOS(0, inum, snapshot), BTREE_ITER_INTENT);
 258         k = bch2_btree_iter_peek_slot(&iter);
 259
 260         ret = bkey_err(k);
 261         if (ret)
 262                 goto err;
 263
 264         if (k.k->type != KEY_TYPE_inode) {
 265                 bch2_fs_inconsistent(trans->c,
 266                                      "inode %llu:%u not found when deleting",
 267                                      inum, snapshot);
 268                 ret = -EIO;
 269                 goto err;
 270         }
 271
 272         bch2_inode_unpack(bkey_s_c_to_inode(k), &inode_u);
 273
 274         /* Subvolume root? */
 275         if (inode_u.bi_subvol) {
 276                 ret = bch2_subvolume_delete(trans, inode_u.bi_subvol);
 277                 if (ret)
 278                         goto err;
 279         }
 280
 281         bkey_inode_generation_init(&delete.k_i);
 282         delete.k.p = iter.pos;
 283         delete.v.bi_generation = cpu_to_le32(inode_u.bi_generation + 1);
 284
 285         ret   = bch2_trans_update(trans, &iter, &delete.k_i, 0) ?:
 286                 bch2_trans_commit(trans, NULL, NULL,
 287                                 BTREE_INSERT_NOFAIL);
 288 err:
 289         bch2_trans_iter_exit(trans, &iter);
 290         if (ret == -EINTR)
 291                 goto retry;
 292
 293         return ret;
 294 }
 295
 296 static int __remove_dirent(struct btree_trans *trans, struct bpos pos)
 297 {
 298         struct bch_fs *c = trans->c;
 299         struct btree_iter iter;
 300         struct bch_inode_unpacked dir_inode;
 301         struct bch_hash_info dir_hash_info;
 302         int ret;
 303
 304         ret = lookup_first_inode(trans, pos.inode, &dir_inode);
 305         if (ret)
 306                 return ret;
 307
 308         dir_hash_info = bch2_hash_info_init(c, &dir_inode);
 309
 310         bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, pos, BTREE_ITER_INTENT);
 311
 312         ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc,
 313                                   &dir_hash_info, &iter, 0);
 314         bch2_trans_iter_exit(trans, &iter);
 315         return ret;
 316 }
 317
 318 /* Get lost+found, create if it doesn't exist: */
 319 static int lookup_lostfound(struct btree_trans *trans, u32 subvol,
 320                             struct bch_inode_unpacked *lostfound)
 321 {
 322         struct bch_fs *c = trans->c;
 323         struct bch_inode_unpacked root;
 324         struct bch_hash_info root_hash_info;
 325         struct qstr lostfound_str = QSTR("lost+found");
 326         subvol_inum root_inum = { .subvol = subvol };
 327         u64 inum = 0;
 328         unsigned d_type = 0;
 329         u32 snapshot;
 330         int ret;
 331
 332         ret = __subvol_lookup(trans, subvol, &snapshot, &root_inum.inum);
 333         if (ret)
 334                 return ret;
 335
 336         ret = __lookup_inode(trans, root_inum.inum, &root, &snapshot);
 337         if (ret)
 338                 return ret;
 339
 340         root_hash_info = bch2_hash_info_init(c, &root);
 341
 342         ret = __lookup_dirent(trans, root_hash_info, root_inum,
 343                             &lostfound_str, &inum, &d_type);
 344         if (ret == -ENOENT) {
 345                 bch_notice(c, "creating lost+found");
 346                 goto create_lostfound;
 347         }
 348
 349         if (ret && ret != -EINTR)
 350                 bch_err(c, "error looking up lost+found: %i", ret);
 351         if (ret)
 352                 return ret;
 353
 354         if (d_type != DT_DIR) {
 355                 bch_err(c, "error looking up lost+found: not a directory");
 356                 return ret;
 357         }
 358
 359         /*
 360          * The check_dirents pass has already run, dangling dirents
 361          * shouldn't exist here:
 362          */
 363         return __lookup_inode(trans, inum, lostfound, &snapshot);
 364
 365 create_lostfound:
 366         bch2_inode_init_early(c, lostfound);
 367
 368         ret = bch2_create_trans(trans, root_inum, &root,
 369                                 lostfound, &lostfound_str,
 370                                 0, 0, S_IFDIR|0700, 0, NULL, NULL,
 371                                 (subvol_inum) { }, 0);
 372         if (ret && ret != -EINTR)
 373                 bch_err(c, "error creating lost+found: %i", ret);
 374         return ret;
 375 }
 376
 377 static int __reattach_inode(struct btree_trans *trans,
 378                           struct bch_inode_unpacked *inode,
 379                           u32 inode_snapshot)
 380 {
 381         struct bch_hash_info dir_hash;
 382         struct bch_inode_unpacked lostfound;
 383         char name_buf[20];
 384         struct qstr name;
 385         u64 dir_offset = 0;
 386         u32 subvol;
 387         int ret;
 388
 389         ret = __snapshot_lookup_subvol(trans, inode_snapshot, &subvol);
 390         if (ret)
 391                 return ret;
 392
 393         ret = lookup_lostfound(trans, subvol, &lostfound);
 394         if (ret)
 395                 return ret;
 396
 397         if (S_ISDIR(inode->bi_mode)) {
 398                 lostfound.bi_nlink++;
 399
 400                 ret = __write_inode(trans, &lostfound, U32_MAX);
 401                 if (ret)
 402                         return ret;
 403         }
 404
 405         dir_hash = bch2_hash_info_init(trans->c, &lostfound);
 406
 407         snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum);
 408         name = (struct qstr) QSTR(name_buf);
 409
 410         ret = bch2_dirent_create(trans,
 411                                  (subvol_inum) {
 412                                         .subvol = subvol,
 413                                         .inum = lostfound.bi_inum,
 414                                  },
 415                                  &dir_hash,
 416                                  inode_d_type(inode),
 417                                  &name, inode->bi_inum, &dir_offset,
 418                                  BCH_HASH_SET_MUST_CREATE);
 419         if (ret)
 420                 return ret;
 421
 422         inode->bi_dir           = lostfound.bi_inum;
 423         inode->bi_dir_offset    = dir_offset;
 424
 425         return __write_inode(trans, inode, inode_snapshot);
 426 }
 427
 428 static int reattach_inode(struct btree_trans *trans,
 429                           struct bch_inode_unpacked *inode,
 430                           u32 inode_snapshot)
 431 {
 432         int ret = __bch2_trans_do(trans, NULL, NULL,
 433                                   BTREE_INSERT_LAZY_RW|
 434                                   BTREE_INSERT_NOFAIL,
 435                         __reattach_inode(trans, inode, inode_snapshot));
 436         if (ret) {
 437                 bch_err(trans->c, "error %i reattaching inode %llu",
 438                         ret, inode->bi_inum);
 439                 return ret;
 440         }
 441
 442         return ret;
 443 }
 444
 445 static int remove_backpointer(struct btree_trans *trans,
 446                               struct bch_inode_unpacked *inode)
 447 {
 448         struct btree_iter iter;
 449         struct bkey_s_c k;
 450         int ret;
 451
 452         bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents,
 453                              POS(inode->bi_dir, inode->bi_dir_offset), 0);
 454         k = bch2_btree_iter_peek_slot(&iter);
 455         ret = bkey_err(k);
 456         if (ret)
 457                 goto out;
 458         if (k.k->type != KEY_TYPE_dirent) {
 459                 ret = -ENOENT;
 460                 goto out;
 461         }
 462
 463         ret = __remove_dirent(trans, k.k->p);
 464 out:
 465         bch2_trans_iter_exit(trans, &iter);
 466         return ret;
 467 }
 468
 469 static int snapshots_seen_update(struct bch_fs *c, struct snapshots_seen *s, struct bpos pos)
 470 {
 471         pos.snapshot = snapshot_t(c, pos.snapshot)->equiv;
 472
 473         if (bkey_cmp(s->pos, pos))
 474                 s->nr = 0;
 475         s->pos = pos;
 476
 477         /* Might get called multiple times due to lock restarts */
 478         if (s->nr && s->d[s->nr - 1] == pos.snapshot)
 479                 return 0;
 480
 481         return snapshots_seen_add(c, s, pos.snapshot);
 482 }
 483
 484 /**
 485  * key_visible_in_snapshot - returns true if @id is a descendent of @ancestor,
 486  * and @ancestor hasn't been overwritten in @seen
 487  *
 488  * That is, returns whether key in @ancestor snapshot is visible in @id snapshot
 489  */
 490 static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *seen,
 491                                     u32 id, u32 ancestor)
 492 {
 493         ssize_t i;
 494
 495         BUG_ON(id > ancestor);
 496
 497         id              = snapshot_t(c, id)->equiv;
 498         ancestor        = snapshot_t(c, ancestor)->equiv;
 499
 500         /* @ancestor should be the snapshot most recently added to @seen */
 501         BUG_ON(!seen->nr || seen->d[seen->nr - 1] != ancestor);
 502         BUG_ON(seen->pos.snapshot != ancestor);
 503
 504         if (id == ancestor)
 505                 return true;
 506
 507         if (!bch2_snapshot_is_ancestor(c, id, ancestor))
 508                 return false;
 509
 510         for (i = seen->nr - 2;
 511              i >= 0 && seen->d[i] >= id;
 512              --i)
 513                 if (bch2_snapshot_is_ancestor(c, id, seen->d[i]) &&
 514                     bch2_snapshot_is_ancestor(c, seen->d[i], ancestor))
 515                         return false;
 516
 517         return true;
 518 }
 519
 520 /**
 521  * ref_visible - given a key with snapshot id @src that points to a key with
 522  * snapshot id @dst, test whether there is some snapshot in which @dst is
 523  * visible.
 524  *
 525  * This assumes we're visiting @src keys in natural key order.
 526  *
 527  * @s   - list of snapshot IDs already seen at @src
 528  * @src - snapshot ID of src key
 529  * @dst - snapshot ID of dst key
 530  */
 531 static int ref_visible(struct bch_fs *c, struct snapshots_seen *s,
 532                        u32 src, u32 dst)
 533 {
 534         return dst <= src
 535                 ? key_visible_in_snapshot(c, s, dst, src)
 536                 : bch2_snapshot_is_ancestor(c, src, dst);
 537 }
 538
 539 #define for_each_visible_inode(_c, _s, _w, _snapshot, _i)       \
 540         for (_i = (_w)->d; _i < (_w)->d + (_w)->nr && (_i)->snapshot <= (_snapshot); _i++)\
 541                 if (key_visible_in_snapshot(_c, _s, _i->snapshot, _snapshot))
 542
 543 struct inode_walker {
 544         bool                            first_this_inode;
 545         u64                             cur_inum;
 546
 547         size_t                          nr;
 548         size_t                          size;
 549         struct inode_walker_entry {
 550                 struct bch_inode_unpacked inode;
 551                 u32                     snapshot;
 552                 u64                     count;
 553         } *d;
 554 };
 555
 556 static void inode_walker_exit(struct inode_walker *w)
 557 {
 558         kfree(w->d);
 559         w->d = NULL;
 560 }
 561
 562 static struct inode_walker inode_walker_init(void)
 563 {
 564         return (struct inode_walker) { 0, };
 565 }
 566
 567 static int inode_walker_realloc(struct inode_walker *w)
 568 {
 569         if (w->nr == w->size) {
 570                 size_t new_size = max_t(size_t, 8UL, w->size * 2);
 571                 void *d = krealloc(w->d, new_size * sizeof(w->d[0]),
 572                                    GFP_KERNEL);
 573                 if (!d)
 574                         return -ENOMEM;
 575
 576                 w->d = d;
 577                 w->size = new_size;
 578         }
 579
 580         return 0;
 581 }
 582
 583 static int add_inode(struct bch_fs *c, struct inode_walker *w,
 584                      struct bkey_s_c_inode inode)
 585 {
 586         struct bch_inode_unpacked u;
 587         int ret;
 588
 589         ret = inode_walker_realloc(w);
 590         if (ret)
 591                 return ret;
 592
 593         BUG_ON(bch2_inode_unpack(inode, &u));
 594
 595         w->d[w->nr++] = (struct inode_walker_entry) {
 596                 .inode          = u,
 597                 .snapshot       = snapshot_t(c, inode.k->p.snapshot)->equiv,
 598         };
 599
 600         return 0;
 601 }
 602
 603 static int __walk_inode(struct btree_trans *trans,
 604                         struct inode_walker *w, struct bpos pos)
 605 {
 606         struct bch_fs *c = trans->c;
 607         struct btree_iter iter;
 608         struct bkey_s_c k;
 609         unsigned i, ancestor_pos;
 610         int ret;
 611
 612         pos.snapshot = snapshot_t(c, pos.snapshot)->equiv;
 613
 614         if (pos.inode == w->cur_inum) {
 615                 w->first_this_inode = false;
 616                 goto lookup_snapshot;
 617         }
 618
 619         w->nr = 0;
 620
 621         for_each_btree_key(trans, iter, BTREE_ID_inodes, POS(0, pos.inode),
 622                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
 623                 if (k.k->p.offset != pos.inode)
 624                         break;
 625
 626                 if (k.k->type == KEY_TYPE_inode)
 627                         add_inode(c, w, bkey_s_c_to_inode(k));
 628         }
 629         bch2_trans_iter_exit(trans, &iter);
 630
 631         if (ret)
 632                 return ret;
 633
 634         w->cur_inum             = pos.inode;
 635         w->first_this_inode     = true;
 636 lookup_snapshot:
 637         for (i = 0; i < w->nr; i++)
 638                 if (bch2_snapshot_is_ancestor(c, pos.snapshot, w->d[i].snapshot))
 639                         goto found;
 640         return INT_MAX;
 641 found:
 642         BUG_ON(pos.snapshot > w->d[i].snapshot);
 643
 644         if (pos.snapshot != w->d[i].snapshot) {
 645                 ancestor_pos = i;
 646
 647                 while (i && w->d[i - 1].snapshot > pos.snapshot)
 648                         --i;
 649
 650                 ret = inode_walker_realloc(w);
 651                 if (ret)
 652                         return ret;
 653
 654                 array_insert_item(w->d, w->nr, i, w->d[ancestor_pos]);
 655                 w->d[i].snapshot = pos.snapshot;
 656                 w->d[i].count   = 0;
 657         }
 658
 659         return i;
 660 }
 661
 662 static int __get_visible_inodes(struct btree_trans *trans,
 663                                 struct inode_walker *w,
 664                                 struct snapshots_seen *s,
 665                                 u64 inum)
 666 {
 667         struct bch_fs *c = trans->c;
 668         struct btree_iter iter;
 669         struct bkey_s_c k;
 670         int ret;
 671
 672         w->nr = 0;
 673
 674         for_each_btree_key(trans, iter, BTREE_ID_inodes, POS(0, inum),
 675                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
 676                 if (k.k->p.offset != inum)
 677                         break;
 678
 679                 if (k.k->type != KEY_TYPE_inode)
 680                         continue;
 681
 682                 if (ref_visible(c, s, s->pos.snapshot, k.k->p.snapshot)) {
 683                         add_inode(c, w, bkey_s_c_to_inode(k));
 684                         if (k.k->p.snapshot >= s->pos.snapshot)
 685                                 break;
 686                 }
 687         }
 688         bch2_trans_iter_exit(trans, &iter);
 689
 690         return ret;
 691 }
 692
 693 static int check_key_has_snapshot(struct btree_trans *trans,
 694                                   struct btree_iter *iter,
 695                                   struct bkey_s_c k)
 696 {
 697         struct bch_fs *c = trans->c;
 698         char buf[200];
 699         int ret = 0;
 700
 701         if (mustfix_fsck_err_on(!snapshot_t(c, k.k->p.snapshot)->equiv, c,
 702                         "key in missing snapshot: %s",
 703                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
 704                 return bch2_btree_delete_at(trans, iter,
 705                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?: 1;
 706 fsck_err:
 707         return ret;
 708 }
 709
 710 static int hash_redo_key(struct btree_trans *trans,
 711                          const struct bch_hash_desc desc,
 712                          struct bch_hash_info *hash_info,
 713                          struct btree_iter *k_iter, struct bkey_s_c k)
 714 {
 715         bch_err(trans->c, "hash_redo_key() not implemented yet");
 716         return -EINVAL;
 717 #if 0
 718         struct bkey_i *delete;
 719         struct bkey_i *tmp;
 720
 721         delete = bch2_trans_kmalloc(trans, sizeof(*delete));
 722         if (IS_ERR(delete))
 723                 return PTR_ERR(delete);
 724
 725         tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
 726         if (IS_ERR(tmp))
 727                 return PTR_ERR(tmp);
 728
 729         bkey_reassemble(tmp, k);
 730
 731         bkey_init(&delete->k);
 732         delete->k.p = k_iter->pos;
 733         return  bch2_btree_iter_traverse(k_iter) ?:
 734                 bch2_trans_update(trans, k_iter, delete, 0) ?:
 735                 bch2_hash_set(trans, desc, hash_info, k_iter->pos.inode, tmp, 0);
 736 #endif
 737 }
 738
 739 static int hash_check_key(struct btree_trans *trans,
 740                           const struct bch_hash_desc desc,
 741                           struct bch_hash_info *hash_info,
 742                           struct btree_iter *k_iter, struct bkey_s_c hash_k)
 743 {
 744         struct bch_fs *c = trans->c;
 745         struct btree_iter iter = { NULL };
 746         char buf[200];
 747         struct bkey_s_c k;
 748         u64 hash;
 749         int ret = 0;
 750
 751         if (hash_k.k->type != desc.key_type)
 752                 return 0;
 753
 754         hash = desc.hash_bkey(hash_info, hash_k);
 755
 756         if (likely(hash == hash_k.k->p.offset))
 757                 return 0;
 758
 759         if (hash_k.k->p.offset < hash)
 760                 goto bad_hash;
 761
 762         for_each_btree_key(trans, iter, desc.btree_id, POS(hash_k.k->p.inode, hash),
 763                            BTREE_ITER_SLOTS, k, ret) {
 764                 if (!bkey_cmp(k.k->p, hash_k.k->p))
 765                         break;
 766
 767                 if (fsck_err_on(k.k->type == desc.key_type &&
 768                                 !desc.cmp_bkey(k, hash_k), c,
 769                                 "duplicate hash table keys:\n%s",
 770                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
 771                                                        hash_k), buf))) {
 772                         ret = bch2_hash_delete_at(trans, desc, hash_info, k_iter, 0) ?: 1;
 773                         break;
 774                 }
 775
 776                 if (bkey_deleted(k.k)) {
 777                         bch2_trans_iter_exit(trans, &iter);
 778                         goto bad_hash;
 779                 }
 780
 781         }
 782         bch2_trans_iter_exit(trans, &iter);
 783         return ret;
 784 bad_hash:
 785         if (fsck_err(c, "hash table key at wrong offset: btree %u inode %llu offset %llu, "
 786                      "hashed to %llu\n%s",
 787                      desc.btree_id, hash_k.k->p.inode, hash_k.k->p.offset, hash,
 788                      (bch2_bkey_val_to_text(&PBUF(buf), c, hash_k), buf)) == FSCK_ERR_IGNORE)
 789                 return 0;
 790
 791         ret = hash_redo_key(trans, desc, hash_info, k_iter, hash_k);
 792         if (ret) {
 793                 bch_err(c, "hash_redo_key err %i", ret);
 794                 return ret;
 795         }
 796         return -EINTR;
 797 fsck_err:
 798         return ret;
 799 }
 800
 801 static int check_inode(struct btree_trans *trans,
 802                        struct btree_iter *iter,
 803                        struct bch_inode_unpacked *prev,
 804                        bool full)
 805 {
 806         struct bch_fs *c = trans->c;
 807         struct bkey_s_c k;
 808         struct bkey_s_c_inode inode;
 809         struct bch_inode_unpacked u;
 810         bool do_update = false;
 811         int ret;
 812
 813         k = bch2_btree_iter_peek(iter);
 814         if (!k.k)
 815                 return 0;
 816
 817         ret = bkey_err(k);
 818         if (ret)
 819                 return ret;
 820
 821         ret = check_key_has_snapshot(trans, iter, k);
 822         if (ret)
 823                 return ret < 0 ? ret : 0;
 824
 825         /*
 826          * if snapshot id isn't a leaf node, skip it - deletion in
 827          * particular is not atomic, so on the internal snapshot nodes
 828          * we can see inodes marked for deletion after a clean shutdown
 829          */
 830         if (bch2_snapshot_internal_node(c, k.k->p.snapshot))
 831                 return 0;
 832
 833         if (k.k->type != KEY_TYPE_inode)
 834                 return 0;
 835
 836         inode = bkey_s_c_to_inode(k);
 837
 838         if (!full &&
 839             !(inode.v->bi_flags & (BCH_INODE_I_SIZE_DIRTY|
 840                                    BCH_INODE_I_SECTORS_DIRTY|
 841                                    BCH_INODE_UNLINKED)))
 842                 return 0;
 843
 844         BUG_ON(bch2_inode_unpack(inode, &u));
 845
 846         if (prev->bi_inum != u.bi_inum)
 847                 *prev = u;
 848
 849         if (fsck_err_on(prev->bi_hash_seed      != u.bi_hash_seed ||
 850                         inode_d_type(prev)      != inode_d_type(&u), c,
 851                         "inodes in different snapshots don't match")) {
 852                 bch_err(c, "repair not implemented yet");
 853                 return -EINVAL;
 854         }
 855
 856         if (u.bi_flags & BCH_INODE_UNLINKED &&
 857             (!c->sb.clean ||
 858              fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
 859                       u.bi_inum))) {
 860                 bch2_trans_unlock(trans);
 861                 bch2_fs_lazy_rw(c);
 862
 863                 ret = fsck_inode_rm(trans, u.bi_inum, iter->pos.snapshot);
 864                 if (ret)
 865                         bch_err(c, "error in fsck: error %i while deleting inode", ret);
 866                 return ret;
 867         }
 868
 869         if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
 870             (!c->sb.clean ||
 871              fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
 872                       u.bi_inum))) {
 873                 bch_verbose(c, "truncating inode %llu", u.bi_inum);
 874
 875                 bch2_trans_unlock(trans);
 876                 bch2_fs_lazy_rw(c);
 877
 878                 /*
 879                  * XXX: need to truncate partial blocks too here - or ideally
 880                  * just switch units to bytes and that issue goes away
 881                  */
 882                 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
 883                                 SPOS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9,
 884                                      iter->pos.snapshot),
 885                                 POS(u.bi_inum, U64_MAX),
 886                                 0, NULL);
 887                 if (ret) {
 888                         bch_err(c, "error in fsck: error %i truncating inode", ret);
 889                         return ret;
 890                 }
 891
 892                 /*
 893                  * We truncated without our normal sector accounting hook, just
 894                  * make sure we recalculate it:
 895                  */
 896                 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
 897
 898                 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
 899                 do_update = true;
 900         }
 901
 902         if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
 903             (!c->sb.clean ||
 904              fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
 905                       u.bi_inum))) {
 906                 s64 sectors;
 907
 908                 bch_verbose(c, "recounting sectors for inode %llu",
 909                             u.bi_inum);
 910
 911                 sectors = bch2_count_inode_sectors(trans, u.bi_inum, iter->pos.snapshot);
 912                 if (sectors < 0) {
 913                         bch_err(c, "error in fsck: error %i recounting inode sectors",
 914                                 (int) sectors);
 915                         return sectors;
 916                 }
 917
 918                 u.bi_sectors = sectors;
 919                 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
 920                 do_update = true;
 921         }
 922
 923         if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) {
 924                 u.bi_dir = 0;
 925                 u.bi_dir_offset = 0;
 926                 u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED;
 927                 do_update = true;
 928         }
 929
 930         if (do_update) {
 931                 ret = write_inode(trans, &u, iter->pos.snapshot);
 932                 if (ret)
 933                         bch_err(c, "error in fsck: error %i "
 934                                 "updating inode", ret);
 935         }
 936 fsck_err:
 937         return ret;
 938 }
 939
 940 noinline_for_stack
 941 static int check_inodes(struct bch_fs *c, bool full)
 942 {
 943         struct btree_trans trans;
 944         struct btree_iter iter;
 945         struct bch_inode_unpacked prev = { 0 };
 946         int ret;
 947
 948         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 949
 950         bch2_trans_iter_init(&trans, &iter, BTREE_ID_inodes, POS_MIN,
 951                              BTREE_ITER_INTENT|
 952                              BTREE_ITER_PREFETCH|
 953                              BTREE_ITER_ALL_SNAPSHOTS);
 954
 955         do {
 956                 ret = __bch2_trans_do(&trans, NULL, NULL,
 957                                       BTREE_INSERT_LAZY_RW|
 958                                       BTREE_INSERT_NOFAIL,
 959                         check_inode(&trans, &iter, &prev, full));
 960                 if (ret)
 961                         break;
 962         } while (bch2_btree_iter_advance(&iter));
 963         bch2_trans_iter_exit(&trans, &iter);
 964
 965         bch2_trans_exit(&trans);
 966         return ret;
 967 }
 968
 969 static int check_subvol(struct btree_trans *trans,
 970                         struct btree_iter *iter)
 971 {
 972         struct bkey_s_c k;
 973         struct bkey_s_c_subvolume subvol;
 974         int ret;
 975
 976         k = bch2_btree_iter_peek(iter);
 977         if (!k.k)
 978                 return 0;
 979
 980         ret = bkey_err(k);
 981         if (ret)
 982                 return ret;
 983
 984         if (k.k->type != KEY_TYPE_subvolume)
 985                 return 0;
 986
 987         subvol = bkey_s_c_to_subvolume(k);
 988
 989         if (BCH_SUBVOLUME_UNLINKED(subvol.v)) {
 990                 ret = bch2_subvolume_delete(trans, iter->pos.offset);
 991                 if (ret && ret != -EINTR)
 992                         bch_err(trans->c, "error deleting subvolume %llu: %i",
 993                                 iter->pos.offset, ret);
 994                 if (ret)
 995                         return ret;
 996         }
 997
 998         return 0;
 999 }
1000
1001 noinline_for_stack
1002 static int check_subvols(struct bch_fs *c)
1003 {
1004         struct btree_trans trans;
1005         struct btree_iter iter;
1006         int ret;
1007
1008         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1009
1010         bch2_trans_iter_init(&trans, &iter, BTREE_ID_subvolumes,
1011                              POS_MIN,
1012                              BTREE_ITER_INTENT|
1013                              BTREE_ITER_PREFETCH);
1014
1015         do {
1016                 ret = __bch2_trans_do(&trans, NULL, NULL,
1017                                       BTREE_INSERT_LAZY_RW|
1018                                       BTREE_INSERT_NOFAIL,
1019                                       check_subvol(&trans, &iter));
1020                 if (ret)
1021                         break;
1022         } while (bch2_btree_iter_advance(&iter));
1023         bch2_trans_iter_exit(&trans, &iter);
1024
1025         bch2_trans_exit(&trans);
1026         return ret;
1027 }
1028
1029 /*
1030  * Checking for overlapping extents needs to be reimplemented
1031  */
1032 #if 0
1033 static int fix_overlapping_extent(struct btree_trans *trans,
1034                                        struct bkey_s_c k, struct bpos cut_at)
1035 {
1036         struct btree_iter iter;
1037         struct bkey_i *u;
1038         int ret;
1039
1040         u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1041         ret = PTR_ERR_OR_ZERO(u);
1042         if (ret)
1043                 return ret;
1044
1045         bkey_reassemble(u, k);
1046         bch2_cut_front(cut_at, u);
1047
1048
1049         /*
1050          * We don't want to go through the extent_handle_overwrites path:
1051          *
1052          * XXX: this is going to screw up disk accounting, extent triggers
1053          * assume things about extent overwrites - we should be running the
1054          * triggers manually here
1055          */
1056         bch2_trans_iter_init(trans, &iter, BTREE_ID_extents, u->k.p,
1057                              BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
1058
1059         BUG_ON(iter.flags & BTREE_ITER_IS_EXTENTS);
1060         ret   = bch2_btree_iter_traverse(&iter) ?:
1061                 bch2_trans_update(trans, &iter, u, BTREE_TRIGGER_NORUN) ?:
1062                 bch2_trans_commit(trans, NULL, NULL,
1063                                   BTREE_INSERT_NOFAIL|
1064                                   BTREE_INSERT_LAZY_RW);
1065         bch2_trans_iter_exit(trans, &iter);
1066         return ret;
1067 }
1068 #endif
1069
1070 static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans,
1071                                                 struct btree_iter *iter,
1072                                                 struct bpos pos)
1073 {
1074         struct bkey_s_c k;
1075         int ret;
1076
1077         bch2_trans_iter_init(trans, iter, BTREE_ID_dirents, pos, 0);
1078         k = bch2_btree_iter_peek_slot(iter);
1079         ret = bkey_err(k);
1080         if (!ret && k.k->type != KEY_TYPE_dirent)
1081                 ret = -ENOENT;
1082         if (ret) {
1083                 bch2_trans_iter_exit(trans, iter);
1084                 return (struct bkey_s_c_dirent) { .k = ERR_PTR(ret) };
1085         }
1086
1087         return bkey_s_c_to_dirent(k);
1088 }
1089
1090 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode,
1091                                    struct bkey_s_c_dirent d)
1092 {
1093         return  inode->bi_dir           == d.k->p.inode &&
1094                 inode->bi_dir_offset    == d.k->p.offset;
1095 }
1096
1097 static bool dirent_points_to_inode(struct bkey_s_c_dirent d,
1098                                    struct bch_inode_unpacked *inode)
1099 {
1100         return d.v->d_type == DT_SUBVOL
1101                 ? le32_to_cpu(d.v->d_child_subvol)      == inode->bi_subvol
1102                 : le64_to_cpu(d.v->d_inum)              == inode->bi_inum;
1103 }
1104
1105 static int inode_backpointer_exists(struct btree_trans *trans,
1106                                     struct bch_inode_unpacked *inode,
1107                                     u32 snapshot)
1108 {
1109         struct btree_iter iter;
1110         struct bkey_s_c_dirent d;
1111         int ret;
1112
1113         d = dirent_get_by_pos(trans, &iter,
1114                         SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot));
1115         ret = bkey_err(d.s_c);
1116         if (ret)
1117                 return ret;
1118
1119         ret = dirent_points_to_inode(d, inode);
1120         bch2_trans_iter_exit(trans, &iter);
1121         return ret;
1122 }
1123
1124 static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w)
1125 {
1126         struct bch_fs *c = trans->c;
1127         struct inode_walker_entry *i;
1128         int ret = 0, ret2 = 0;
1129         s64 count2;
1130
1131         for (i = w->d; i < w->d + w->nr; i++) {
1132                 if (i->inode.bi_sectors == i->count)
1133                         continue;
1134
1135                 count2 = lockrestart_do(trans,
1136                         bch2_count_inode_sectors(trans, w->cur_inum, i->snapshot));
1137
1138                 if (i->count != count2) {
1139                         bch_err(c, "fsck counted i_sectors wrong: got %llu should be %llu",
1140                                 i->count, count2);
1141                         i->count = count2;
1142                         if (i->inode.bi_sectors == i->count)
1143                                 continue;
1144                 }
1145
1146                 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY), c,
1147                             "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu",
1148                             w->cur_inum, i->snapshot,
1149                             i->inode.bi_sectors, i->count) == FSCK_ERR_IGNORE)
1150                         continue;
1151
1152                 i->inode.bi_sectors = i->count;
1153                 ret = write_inode(trans, &i->inode, i->snapshot);
1154                 if (ret)
1155                         break;
1156                 ret2 = -EINTR;
1157         }
1158 fsck_err:
1159         return ret ?: ret2;
1160 }
1161
1162 static int check_extent(struct btree_trans *trans, struct btree_iter *iter,
1163                         struct inode_walker *inode,
1164                         struct snapshots_seen *s)
1165 {
1166         struct bch_fs *c = trans->c;
1167         struct bkey_s_c k;
1168         struct inode_walker_entry *i;
1169         char buf[200];
1170         int ret = 0;
1171
1172         k = bch2_btree_iter_peek(iter);
1173         if (!k.k)
1174                 return 0;
1175
1176         ret = bkey_err(k);
1177         if (ret)
1178                 return ret;
1179
1180         ret = check_key_has_snapshot(trans, iter, k);
1181         if (ret)
1182                 return ret < 0 ? ret : 0;
1183
1184         ret = snapshots_seen_update(c, s, k.k->p);
1185         if (ret)
1186                 return ret;
1187
1188         if (k.k->type == KEY_TYPE_whiteout)
1189                 return 0;
1190
1191         if (inode->cur_inum != k.k->p.inode) {
1192                 ret = check_i_sectors(trans, inode);
1193                 if (ret)
1194                         return ret;
1195         }
1196 #if 0
1197         if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) {
1198                 char buf1[200];
1199                 char buf2[200];
1200
1201                 bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k));
1202                 bch2_bkey_val_to_text(&PBUF(buf2), c, k);
1203
1204                 if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2))
1205                         return fix_overlapping_extent(trans, k, prev.k->k.p) ?: -EINTR;
1206         }
1207 #endif
1208         ret = __walk_inode(trans, inode, k.k->p);
1209         if (ret < 0)
1210                 return ret;
1211
1212         if (fsck_err_on(ret == INT_MAX, c,
1213                         "extent in missing inode:\n  %s",
1214                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1215                 return bch2_btree_delete_at(trans, iter,
1216                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1217
1218         if (ret == INT_MAX)
1219                 return 0;
1220
1221         i = inode->d + ret;
1222         ret = 0;
1223
1224         if (fsck_err_on(!S_ISREG(i->inode.bi_mode) &&
1225                         !S_ISLNK(i->inode.bi_mode), c,
1226                         "extent in non regular inode mode %o:\n  %s",
1227                         i->inode.bi_mode,
1228                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1229                 return bch2_btree_delete_at(trans, iter,
1230                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1231
1232         if (!bch2_snapshot_internal_node(c, k.k->p.snapshot)) {
1233                 for_each_visible_inode(c, s, inode, k.k->p.snapshot, i) {
1234                         if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
1235                                         k.k->type != KEY_TYPE_reservation &&
1236                                         k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9, c,
1237                                         "extent type %u offset %llu past end of inode %llu, i_size %llu",
1238                                         k.k->type, k.k->p.offset, k.k->p.inode, i->inode.bi_size)) {
1239                                 bch2_fs_lazy_rw(c);
1240                                 return bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
1241                                                 SPOS(k.k->p.inode, round_up(i->inode.bi_size, block_bytes(c)) >> 9,
1242                                                      k.k->p.snapshot),
1243                                                 POS(k.k->p.inode, U64_MAX),
1244                                                 0, NULL) ?: -EINTR;
1245                         }
1246                 }
1247         }
1248
1249         if (bkey_extent_is_allocation(k.k))
1250                 for_each_visible_inode(c, s, inode, k.k->p.snapshot, i)
1251                         i->count += k.k->size;
1252 #if 0
1253         bch2_bkey_buf_reassemble(&prev, c, k);
1254 #endif
1255
1256 fsck_err:
1257         return ret;
1258 }
1259
1260 /*
1261  * Walk extents: verify that extents have a corresponding S_ISREG inode, and
1262  * that i_size an i_sectors are consistent
1263  */
1264 noinline_for_stack
1265 static int check_extents(struct bch_fs *c)
1266 {
1267         struct inode_walker w = inode_walker_init();
1268         struct snapshots_seen s;
1269         struct btree_trans trans;
1270         struct btree_iter iter;
1271         int ret = 0;
1272
1273 #if 0
1274         struct bkey_buf prev;
1275         bch2_bkey_buf_init(&prev);
1276         prev.k->k = KEY(0, 0, 0);
1277 #endif
1278         snapshots_seen_init(&s);
1279         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1280
1281         bch_verbose(c, "checking extents");
1282
1283         bch2_trans_iter_init(&trans, &iter, BTREE_ID_extents,
1284                              POS(BCACHEFS_ROOT_INO, 0),
1285                              BTREE_ITER_INTENT|
1286                              BTREE_ITER_PREFETCH|
1287                              BTREE_ITER_ALL_SNAPSHOTS);
1288
1289         do {
1290                 ret = __bch2_trans_do(&trans, NULL, NULL,
1291                                       BTREE_INSERT_LAZY_RW|
1292                                       BTREE_INSERT_NOFAIL,
1293                         check_extent(&trans, &iter, &w, &s));
1294                 if (ret)
1295                         break;
1296         } while (bch2_btree_iter_advance(&iter));
1297         bch2_trans_iter_exit(&trans, &iter);
1298 #if 0
1299         bch2_bkey_buf_exit(&prev, c);
1300 #endif
1301         inode_walker_exit(&w);
1302         bch2_trans_exit(&trans);
1303         snapshots_seen_exit(&s);
1304
1305         return ret;
1306 }
1307
1308 static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w)
1309 {
1310         struct bch_fs *c = trans->c;
1311         struct inode_walker_entry *i;
1312         int ret = 0, ret2 = 0;
1313         s64 count2;
1314
1315         for (i = w->d; i < w->d + w->nr; i++) {
1316                 if (i->inode.bi_nlink == i->count)
1317                         continue;
1318
1319                 count2 = lockrestart_do(trans,
1320                                 bch2_count_subdirs(trans, w->cur_inum, i->snapshot));
1321
1322                 if (i->count != count2) {
1323                         bch_err(c, "fsck counted subdirectories wrong: got %llu should be %llu",
1324                                 i->count, count2);
1325                         i->count = count2;
1326                         if (i->inode.bi_nlink == i->count)
1327                                 continue;
1328                 }
1329
1330                 if (fsck_err_on(i->inode.bi_nlink != i->count, c,
1331                                 "directory %llu:%u with wrong i_nlink: got %u, should be %llu",
1332                                 w->cur_inum, i->snapshot, i->inode.bi_nlink, i->count)) {
1333                         i->inode.bi_nlink = i->count;
1334                         ret = write_inode(trans, &i->inode, i->snapshot);
1335                         if (ret)
1336                                 break;
1337                         ret2 = -EINTR;
1338                 }
1339         }
1340 fsck_err:
1341         return ret ?: ret2;
1342 }
1343
1344 static int check_dirent_target(struct btree_trans *trans,
1345                                struct btree_iter *iter,
1346                                struct bkey_s_c_dirent d,
1347                                struct bch_inode_unpacked *target,
1348                                u32 target_snapshot)
1349 {
1350         struct bch_fs *c = trans->c;
1351         struct bkey_i_dirent *n;
1352         bool backpointer_exists = true;
1353         char buf[200];
1354         int ret = 0;
1355
1356         if (!target->bi_dir &&
1357             !target->bi_dir_offset) {
1358                 target->bi_dir          = d.k->p.inode;
1359                 target->bi_dir_offset   = d.k->p.offset;
1360
1361                 ret = __write_inode(trans, target, target_snapshot);
1362                 if (ret)
1363                         goto err;
1364         }
1365
1366         if (!inode_points_to_dirent(target, d)) {
1367                 ret = inode_backpointer_exists(trans, target, d.k->p.snapshot);
1368                 if (ret < 0)
1369                         goto err;
1370
1371                 backpointer_exists = ret;
1372                 ret = 0;
1373
1374                 if (fsck_err_on(S_ISDIR(target->bi_mode) &&
1375                                 backpointer_exists, c,
1376                                 "directory %llu with multiple links",
1377                                 target->bi_inum)) {
1378                         ret = __remove_dirent(trans, d.k->p);
1379                         if (ret)
1380                                 goto err;
1381                         return 0;
1382                 }
1383
1384                 if (fsck_err_on(backpointer_exists &&
1385                                 !target->bi_nlink, c,
1386                                 "inode %llu has multiple links but i_nlink 0",
1387                                 target->bi_inum)) {
1388                         target->bi_nlink++;
1389                         target->bi_flags &= ~BCH_INODE_UNLINKED;
1390
1391                         ret = __write_inode(trans, target, target_snapshot);
1392                         if (ret)
1393                                 goto err;
1394                 }
1395
1396                 if (fsck_err_on(!backpointer_exists, c,
1397                                 "inode %llu:%u has wrong backpointer:\n"
1398                                 "got       %llu:%llu\n"
1399                                 "should be %llu:%llu",
1400                                 target->bi_inum, target_snapshot,
1401                                 target->bi_dir,
1402                                 target->bi_dir_offset,
1403                                 d.k->p.inode,
1404                                 d.k->p.offset)) {
1405                         target->bi_dir          = d.k->p.inode;
1406                         target->bi_dir_offset   = d.k->p.offset;
1407
1408                         ret = __write_inode(trans, target, target_snapshot);
1409                         if (ret)
1410                                 goto err;
1411                 }
1412         }
1413
1414         if (fsck_err_on(d.v->d_type != inode_d_type(target), c,
1415                         "incorrect d_type: got %s, should be %s:\n%s",
1416                         bch2_d_type_str(d.v->d_type),
1417                         bch2_d_type_str(inode_d_type(target)),
1418                         (bch2_bkey_val_to_text(&PBUF(buf), c, d.s_c), buf))) {
1419                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1420                 ret = PTR_ERR_OR_ZERO(n);
1421                 if (ret)
1422                         return ret;
1423
1424                 bkey_reassemble(&n->k_i, d.s_c);
1425                 n->v.d_type = inode_d_type(target);
1426
1427                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1428                 if (ret)
1429                         return ret;
1430
1431                 d = dirent_i_to_s_c(n);
1432         }
1433
1434         if (d.v->d_type == DT_SUBVOL &&
1435             target->bi_parent_subvol != le32_to_cpu(d.v->d_parent_subvol) &&
1436             (c->sb.version < bcachefs_metadata_version_subvol_dirent ||
1437              fsck_err(c, "dirent has wrong d_parent_subvol field: got %u, should be %u",
1438                       le32_to_cpu(d.v->d_parent_subvol),
1439                       target->bi_parent_subvol))) {
1440                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1441                 ret = PTR_ERR_OR_ZERO(n);
1442                 if (ret)
1443                         return ret;
1444
1445                 bkey_reassemble(&n->k_i, d.s_c);
1446                 n->v.d_parent_subvol = cpu_to_le32(target->bi_parent_subvol);
1447
1448                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1449                 if (ret)
1450                         return ret;
1451
1452                 d = dirent_i_to_s_c(n);
1453         }
1454 err:
1455 fsck_err:
1456         return ret;
1457 }
1458
1459 static int check_dirent(struct btree_trans *trans, struct btree_iter *iter,
1460                         struct bch_hash_info *hash_info,
1461                         struct inode_walker *dir,
1462                         struct inode_walker *target,
1463                         struct snapshots_seen *s)
1464 {
1465         struct bch_fs *c = trans->c;
1466         struct bkey_s_c k;
1467         struct bkey_s_c_dirent d;
1468         struct inode_walker_entry *i;
1469         char buf[200];
1470         int ret;
1471
1472         k = bch2_btree_iter_peek(iter);
1473         if (!k.k)
1474                 return 0;
1475
1476         ret = bkey_err(k);
1477         if (ret)
1478                 return ret;
1479
1480         ret = check_key_has_snapshot(trans, iter, k);
1481         if (ret)
1482                 return ret < 0 ? ret : 0;
1483
1484         ret = snapshots_seen_update(c, s, k.k->p);
1485         if (ret)
1486                 return ret;
1487
1488         if (k.k->type == KEY_TYPE_whiteout)
1489                 return 0;
1490
1491         if (dir->cur_inum != k.k->p.inode) {
1492                 ret = check_subdir_count(trans, dir);
1493                 if (ret)
1494                         return ret;
1495         }
1496
1497         ret = __walk_inode(trans, dir, k.k->p);
1498         if (ret < 0)
1499                 return ret;
1500
1501         if (fsck_err_on(ret == INT_MAX, c,
1502                         "dirent in nonexisting directory:\n%s",
1503                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1504                 return bch2_btree_delete_at(trans, iter,
1505                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1506
1507         if (ret == INT_MAX)
1508                 return 0;
1509
1510         i = dir->d + ret;
1511         ret = 0;
1512
1513         if (fsck_err_on(!S_ISDIR(i->inode.bi_mode), c,
1514                         "dirent in non directory inode type %s:\n%s",
1515                         bch2_d_type_str(inode_d_type(&i->inode)),
1516                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1517                 return bch2_btree_delete_at(trans, iter, 0);
1518
1519         if (dir->first_this_inode)
1520                 *hash_info = bch2_hash_info_init(c, &dir->d[0].inode);
1521
1522         ret = hash_check_key(trans, bch2_dirent_hash_desc,
1523                              hash_info, iter, k);
1524         if (ret < 0)
1525                 return ret;
1526         if (ret) /* dirent has been deleted */
1527                 return 0;
1528
1529         if (k.k->type != KEY_TYPE_dirent)
1530                 return 0;
1531
1532         d = bkey_s_c_to_dirent(k);
1533
1534         if (d.v->d_type == DT_SUBVOL) {
1535                 struct bch_inode_unpacked subvol_root;
1536                 u32 target_subvol = le32_to_cpu(d.v->d_child_subvol);
1537                 u32 target_snapshot;
1538                 u64 target_inum;
1539
1540                 ret = __subvol_lookup(trans, target_subvol,
1541                                       &target_snapshot, &target_inum);
1542                 if (ret && ret != -ENOENT)
1543                         return ret;
1544
1545                 if (fsck_err_on(ret, c,
1546                                 "dirent points to missing subvolume %llu",
1547                                 le64_to_cpu(d.v->d_child_subvol)))
1548                         return __remove_dirent(trans, d.k->p);
1549
1550                 ret = __lookup_inode(trans, target_inum,
1551                                    &subvol_root, &target_snapshot);
1552                 if (ret && ret != -ENOENT)
1553                         return ret;
1554
1555                 if (fsck_err_on(ret, c,
1556                                 "subvolume %u points to missing subvolume root %llu",
1557                                 target_subvol,
1558                                 target_inum)) {
1559                         bch_err(c, "repair not implemented yet");
1560                         return -EINVAL;
1561                 }
1562
1563                 if (fsck_err_on(subvol_root.bi_subvol != target_subvol, c,
1564                                 "subvol root %llu has wrong bi_subvol field: got %u, should be %u",
1565                                 target_inum,
1566                                 subvol_root.bi_subvol, target_subvol)) {
1567                         subvol_root.bi_subvol = target_subvol;
1568                         ret = __write_inode(trans, &subvol_root, target_snapshot);
1569                         if (ret)
1570                                 return ret;
1571                 }
1572
1573                 ret = check_dirent_target(trans, iter, d, &subvol_root,
1574                                           target_snapshot);
1575                 if (ret)
1576                         return ret;
1577         } else {
1578                 ret = __get_visible_inodes(trans, target, s, le64_to_cpu(d.v->d_inum));
1579                 if (ret)
1580                         return ret;
1581
1582                 if (fsck_err_on(!target->nr, c,
1583                                 "dirent points to missing inode:\n%s",
1584                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
1585                                                        k), buf))) {
1586                         ret = __remove_dirent(trans, d.k->p);
1587                         if (ret)
1588                                 return ret;
1589                 }
1590
1591                 for (i = target->d; i < target->d + target->nr; i++) {
1592                         ret = check_dirent_target(trans, iter, d,
1593                                                   &i->inode, i->snapshot);
1594                         if (ret)
1595                                 return ret;
1596                 }
1597         }
1598
1599         if (d.v->d_type == DT_DIR)
1600                 for_each_visible_inode(c, s, dir, d.k->p.snapshot, i)
1601                         i->count++;
1602
1603 fsck_err:
1604         return ret;
1605 }
1606
1607 /*
1608  * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
1609  * validate d_type
1610  */
1611 noinline_for_stack
1612 static int check_dirents(struct bch_fs *c)
1613 {
1614         struct inode_walker dir = inode_walker_init();
1615         struct inode_walker target = inode_walker_init();
1616         struct snapshots_seen s;
1617         struct bch_hash_info hash_info;
1618         struct btree_trans trans;
1619         struct btree_iter iter;
1620         int ret = 0;
1621
1622         bch_verbose(c, "checking dirents");
1623
1624         snapshots_seen_init(&s);
1625         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1626
1627         bch2_trans_iter_init(&trans, &iter, BTREE_ID_dirents,
1628                              POS(BCACHEFS_ROOT_INO, 0),
1629                              BTREE_ITER_INTENT|
1630                              BTREE_ITER_PREFETCH|
1631                              BTREE_ITER_ALL_SNAPSHOTS);
1632
1633         do {
1634                 ret = __bch2_trans_do(&trans, NULL, NULL,
1635                                       BTREE_INSERT_LAZY_RW|
1636                                       BTREE_INSERT_NOFAIL,
1637                         check_dirent(&trans, &iter, &hash_info,
1638                                      &dir, &target, &s));
1639                 if (ret)
1640                         break;
1641         } while (bch2_btree_iter_advance(&iter));
1642         bch2_trans_iter_exit(&trans, &iter);
1643
1644         bch2_trans_exit(&trans);
1645         snapshots_seen_exit(&s);
1646         inode_walker_exit(&dir);
1647         inode_walker_exit(&target);
1648         return ret;
1649 }
1650
1651 static int check_xattr(struct btree_trans *trans, struct btree_iter *iter,
1652                        struct bch_hash_info *hash_info,
1653                        struct inode_walker *inode)
1654 {
1655         struct bch_fs *c = trans->c;
1656         struct bkey_s_c k;
1657         int ret;
1658
1659         k = bch2_btree_iter_peek(iter);
1660         if (!k.k)
1661                 return 0;
1662
1663         ret = bkey_err(k);
1664         if (ret)
1665                 return ret;
1666
1667         ret = check_key_has_snapshot(trans, iter, k);
1668         if (ret)
1669                 return ret;
1670
1671         ret = __walk_inode(trans, inode, k.k->p);
1672         if (ret < 0)
1673                 return ret;
1674
1675         if (fsck_err_on(ret == INT_MAX, c,
1676                         "xattr for missing inode %llu",
1677                         k.k->p.inode))
1678                 return bch2_btree_delete_at(trans, iter, 0);
1679
1680         if (ret == INT_MAX)
1681                 return 0;
1682
1683         ret = 0;
1684
1685         if (inode->first_this_inode)
1686                 *hash_info = bch2_hash_info_init(c, &inode->d[0].inode);
1687
1688         ret = hash_check_key(trans, bch2_xattr_hash_desc, hash_info, iter, k);
1689 fsck_err:
1690         return ret;
1691 }
1692
1693 /*
1694  * Walk xattrs: verify that they all have a corresponding inode
1695  */
1696 noinline_for_stack
1697 static int check_xattrs(struct bch_fs *c)
1698 {
1699         struct inode_walker inode = inode_walker_init();
1700         struct bch_hash_info hash_info;
1701         struct btree_trans trans;
1702         struct btree_iter iter;
1703         int ret = 0;
1704
1705         bch_verbose(c, "checking xattrs");
1706
1707         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1708
1709         bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
1710                              POS(BCACHEFS_ROOT_INO, 0),
1711                              BTREE_ITER_INTENT|
1712                              BTREE_ITER_PREFETCH|
1713                              BTREE_ITER_ALL_SNAPSHOTS);
1714
1715         do {
1716                 ret = __bch2_trans_do(&trans, NULL, NULL,
1717                                       BTREE_INSERT_LAZY_RW|
1718                                       BTREE_INSERT_NOFAIL,
1719                                       check_xattr(&trans, &iter, &hash_info,
1720                                                   &inode));
1721                 if (ret)
1722                         break;
1723         } while (bch2_btree_iter_advance(&iter));
1724         bch2_trans_iter_exit(&trans, &iter);
1725
1726         bch2_trans_exit(&trans);
1727         return ret;
1728 }
1729
1730 static int check_root_trans(struct btree_trans *trans)
1731 {
1732         struct bch_fs *c = trans->c;
1733         struct bch_inode_unpacked root_inode;
1734         u32 snapshot;
1735         u64 inum;
1736         int ret;
1737
1738         ret = __subvol_lookup(trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum);
1739         if (ret && ret != -ENOENT)
1740                 return ret;
1741
1742         if (mustfix_fsck_err_on(ret, c, "root subvol missing")) {
1743                 struct bkey_i_subvolume root_subvol;
1744
1745                 snapshot        = U32_MAX;
1746                 inum            = BCACHEFS_ROOT_INO;
1747
1748                 bkey_subvolume_init(&root_subvol.k_i);
1749                 root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL;
1750                 root_subvol.v.flags     = 0;
1751                 root_subvol.v.snapshot  = cpu_to_le32(snapshot);
1752                 root_subvol.v.inode     = cpu_to_le64(inum);
1753                 ret = __bch2_trans_do(trans, NULL, NULL,
1754                                       BTREE_INSERT_NOFAIL|
1755                                       BTREE_INSERT_LAZY_RW,
1756                         __bch2_btree_insert(trans, BTREE_ID_subvolumes, &root_subvol.k_i));
1757                 if (ret) {
1758                         bch_err(c, "error writing root subvol: %i", ret);
1759                         goto err;
1760                 }
1761
1762         }
1763
1764         ret = __lookup_inode(trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot);
1765         if (ret && ret != -ENOENT)
1766                 return ret;
1767
1768         if (mustfix_fsck_err_on(ret, c, "root directory missing") ||
1769             mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode), c,
1770                                 "root inode not a directory")) {
1771                 bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755,
1772                                 0, NULL);
1773                 root_inode.bi_inum = inum;
1774
1775                 ret = __write_inode(trans, &root_inode, snapshot);
1776                 if (ret)
1777                         bch_err(c, "error writing root inode: %i", ret);
1778         }
1779 err:
1780 fsck_err:
1781         return ret;
1782 }
1783
1784 /* Get root directory, create if it doesn't exist: */
1785 noinline_for_stack
1786 static int check_root(struct bch_fs *c)
1787 {
1788         bch_verbose(c, "checking root directory");
1789
1790         return bch2_trans_do(c, NULL, NULL,
1791                              BTREE_INSERT_NOFAIL|
1792                              BTREE_INSERT_LAZY_RW,
1793                 check_root_trans(&trans));
1794 }
1795
1796 struct pathbuf {
1797         size_t          nr;
1798         size_t          size;
1799
1800         struct pathbuf_entry {
1801                 u64     inum;
1802                 u32     snapshot;
1803         }               *entries;
1804 };
1805
1806 static bool path_is_dup(struct pathbuf *p, u64 inum, u32 snapshot)
1807 {
1808         struct pathbuf_entry *i;
1809
1810         for (i = p->entries; i < p->entries + p->nr; i++)
1811                 if (i->inum     == inum &&
1812                     i->snapshot == snapshot)
1813                         return true;
1814
1815         return false;
1816 }
1817
1818 static int path_down(struct pathbuf *p, u64 inum, u32 snapshot)
1819 {
1820         if (p->nr == p->size) {
1821                 size_t new_size = max_t(size_t, 256UL, p->size * 2);
1822                 void *n = krealloc(p->entries,
1823                                    new_size * sizeof(p->entries[0]),
1824                                    GFP_KERNEL);
1825                 if (!n) {
1826                         return -ENOMEM;
1827                 }
1828
1829                 p->entries = n;
1830                 p->size = new_size;
1831         };
1832
1833         p->entries[p->nr++] = (struct pathbuf_entry) {
1834                 .inum           = inum,
1835                 .snapshot       = snapshot,
1836         };
1837         return 0;
1838 }
1839
1840 /*
1841  * Check that a given inode is reachable from the root:
1842  *
1843  * XXX: we should also be verifying that inodes are in the right subvolumes
1844  */
1845 static int check_path(struct btree_trans *trans,
1846                       struct pathbuf *p,
1847                       struct bch_inode_unpacked *inode,
1848                       u32 snapshot)
1849 {
1850         struct bch_fs *c = trans->c;
1851         int ret = 0;
1852
1853         snapshot = snapshot_t(c, snapshot)->equiv;
1854         p->nr = 0;
1855
1856         while (!(inode->bi_inum == BCACHEFS_ROOT_INO &&
1857                  inode->bi_subvol == BCACHEFS_ROOT_SUBVOL)) {
1858                 struct btree_iter dirent_iter;
1859                 struct bkey_s_c_dirent d;
1860                 u32 parent_snapshot = snapshot;
1861
1862                 if (inode->bi_subvol) {
1863                         u64 inum;
1864
1865                         ret = subvol_lookup(trans, inode->bi_parent_subvol,
1866                                             &parent_snapshot, &inum);
1867                         if (ret)
1868                                 break;
1869                 }
1870
1871                 ret = lockrestart_do(trans,
1872                         PTR_ERR_OR_ZERO((d = dirent_get_by_pos(trans, &dirent_iter,
1873                                           SPOS(inode->bi_dir, inode->bi_dir_offset,
1874                                                parent_snapshot))).k));
1875                 if (ret && ret != -ENOENT)
1876                         break;
1877
1878                 if (!ret && !dirent_points_to_inode(d, inode)) {
1879                         bch2_trans_iter_exit(trans, &dirent_iter);
1880                         ret = -ENOENT;
1881                 }
1882
1883                 if (ret == -ENOENT) {
1884                         if (fsck_err(c,  "unreachable inode %llu:%u, type %s nlink %u backptr %llu:%llu",
1885                                      inode->bi_inum, snapshot,
1886                                      bch2_d_type_str(inode_d_type(inode)),
1887                                      inode->bi_nlink,
1888                                      inode->bi_dir,
1889                                      inode->bi_dir_offset))
1890                                 ret = reattach_inode(trans, inode, snapshot);
1891                         break;
1892                 }
1893
1894                 bch2_trans_iter_exit(trans, &dirent_iter);
1895
1896                 if (!S_ISDIR(inode->bi_mode))
1897                         break;
1898
1899                 ret = path_down(p, inode->bi_inum, snapshot);
1900                 if (ret) {
1901                         bch_err(c, "memory allocation failure");
1902                         return ret;
1903                 }
1904
1905                 snapshot = parent_snapshot;
1906
1907                 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot);
1908                 if (ret) {
1909                         /* Should have been caught in dirents pass */
1910                         bch_err(c, "error looking up parent directory: %i", ret);
1911                         break;
1912                 }
1913
1914                 if (path_is_dup(p, inode->bi_inum, snapshot)) {
1915                         struct pathbuf_entry *i;
1916
1917                         /* XXX print path */
1918                         bch_err(c, "directory structure loop");
1919
1920                         for (i = p->entries; i < p->entries + p->nr; i++)
1921                                 pr_err("%llu:%u", i->inum, i->snapshot);
1922                         pr_err("%llu:%u", inode->bi_inum, snapshot);
1923
1924                         if (!fsck_err(c, "directory structure loop"))
1925                                 return 0;
1926
1927                         ret = __bch2_trans_do(trans, NULL, NULL,
1928                                               BTREE_INSERT_NOFAIL|
1929                                               BTREE_INSERT_LAZY_RW,
1930                                         remove_backpointer(trans, inode));
1931                         if (ret) {
1932                                 bch_err(c, "error removing dirent: %i", ret);
1933                                 break;
1934                         }
1935
1936                         ret = reattach_inode(trans, inode, snapshot);
1937                 }
1938         }
1939 fsck_err:
1940         if (ret)
1941                 bch_err(c, "%s: err %i", __func__, ret);
1942         return ret;
1943 }
1944
1945 /*
1946  * Check for unreachable inodes, as well as loops in the directory structure:
1947  * After check_dirents(), if an inode backpointer doesn't exist that means it's
1948  * unreachable:
1949  */
1950 noinline_for_stack
1951 static int check_directory_structure(struct bch_fs *c)
1952 {
1953         struct btree_trans trans;
1954         struct btree_iter iter;
1955         struct bkey_s_c k;
1956         struct bch_inode_unpacked u;
1957         struct pathbuf path = { 0, 0, NULL };
1958         int ret;
1959
1960         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1961
1962         for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN,
1963                            BTREE_ITER_INTENT|
1964                            BTREE_ITER_PREFETCH|
1965                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
1966                 if (k.k->type != KEY_TYPE_inode)
1967                         continue;
1968
1969                 ret = bch2_inode_unpack(bkey_s_c_to_inode(k), &u);
1970                 if (ret) {
1971                         /* Should have been caught earlier in fsck: */
1972                         bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
1973                         break;
1974                 }
1975
1976                 if (u.bi_flags & BCH_INODE_UNLINKED)
1977                         continue;
1978
1979                 ret = check_path(&trans, &path, &u, iter.pos.snapshot);
1980                 if (ret)
1981                         break;
1982         }
1983         bch2_trans_iter_exit(&trans, &iter);
1984
1985         BUG_ON(ret == -EINTR);
1986
1987         kfree(path.entries);
1988
1989         bch2_trans_exit(&trans);
1990         return ret;
1991 }
1992
1993 struct nlink_table {
1994         size_t          nr;
1995         size_t          size;
1996
1997         struct nlink {
1998                 u64     inum;
1999                 u32     snapshot;
2000                 u32     count;
2001         }               *d;
2002 };
2003
2004 static int add_nlink(struct nlink_table *t, u64 inum, u32 snapshot)
2005 {
2006         if (t->nr == t->size) {
2007                 size_t new_size = max_t(size_t, 128UL, t->size * 2);
2008                 void *d = kvmalloc(new_size * sizeof(t->d[0]), GFP_KERNEL);
2009                 if (!d) {
2010                         return -ENOMEM;
2011                 }
2012
2013                 if (t->d)
2014                         memcpy(d, t->d, t->size * sizeof(t->d[0]));
2015                 kvfree(t->d);
2016
2017                 t->d = d;
2018                 t->size = new_size;
2019         }
2020
2021
2022         t->d[t->nr++] = (struct nlink) {
2023                 .inum           = inum,
2024                 .snapshot       = snapshot,
2025         };
2026
2027         return 0;
2028 }
2029
2030 static int nlink_cmp(const void *_l, const void *_r)
2031 {
2032         const struct nlink *l = _l;
2033         const struct nlink *r = _r;
2034
2035         return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot);
2036 }
2037
2038 static void inc_link(struct bch_fs *c, struct snapshots_seen *s,
2039                      struct nlink_table *links,
2040                      u64 range_start, u64 range_end, u64 inum, u32 snapshot)
2041 {
2042         struct nlink *link, key = {
2043                 .inum = inum, .snapshot = U32_MAX,
2044         };
2045
2046         if (inum < range_start || inum >= range_end)
2047                 return;
2048
2049         link = __inline_bsearch(&key, links->d, links->nr,
2050                                 sizeof(links->d[0]), nlink_cmp);
2051         if (!link)
2052                 return;
2053
2054         while (link > links->d && link[0].inum == link[-1].inum)
2055                 --link;
2056
2057         for (; link < links->d + links->nr && link->inum == inum; link++)
2058                 if (ref_visible(c, s, snapshot, link->snapshot)) {
2059                         link->count++;
2060                         if (link->snapshot >= snapshot)
2061                                 break;
2062                 }
2063 }
2064
2065 noinline_for_stack
2066 static int check_nlinks_find_hardlinks(struct bch_fs *c,
2067                                        struct nlink_table *t,
2068                                        u64 start, u64 *end)
2069 {
2070         struct btree_trans trans;
2071         struct btree_iter iter;
2072         struct bkey_s_c k;
2073         struct bkey_s_c_inode inode;
2074         struct bch_inode_unpacked u;
2075         int ret = 0;
2076
2077         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2078
2079         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
2080                            POS(0, start),
2081                            BTREE_ITER_INTENT|
2082                            BTREE_ITER_PREFETCH|
2083                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2084                 if (k.k->type != KEY_TYPE_inode)
2085                         continue;
2086
2087                 inode = bkey_s_c_to_inode(k);
2088
2089                 /*
2090                  * Backpointer and directory structure checks are sufficient for
2091                  * directories, since they can't have hardlinks:
2092                  */
2093                 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
2094                         continue;
2095
2096                 /* Should never fail, checked by bch2_inode_invalid: */
2097                 BUG_ON(bch2_inode_unpack(inode, &u));
2098
2099                 if (!u.bi_nlink)
2100                         continue;
2101
2102                 ret = add_nlink(t, k.k->p.offset, k.k->p.snapshot);
2103                 if (ret) {
2104                         *end = k.k->p.offset;
2105                         ret = 0;
2106                         break;
2107                 }
2108
2109         }
2110         bch2_trans_iter_exit(&trans, &iter);
2111         bch2_trans_exit(&trans);
2112
2113         if (ret)
2114                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2115
2116         return ret;
2117 }
2118
2119 noinline_for_stack
2120 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
2121                                      u64 range_start, u64 range_end)
2122 {
2123         struct btree_trans trans;
2124         struct snapshots_seen s;
2125         struct btree_iter iter;
2126         struct bkey_s_c k;
2127         struct bkey_s_c_dirent d;
2128         int ret;
2129
2130         snapshots_seen_init(&s);
2131
2132         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2133
2134         for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN,
2135                            BTREE_ITER_INTENT|
2136                            BTREE_ITER_PREFETCH|
2137                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2138                 ret = snapshots_seen_update(c, &s, k.k->p);
2139                 if (ret)
2140                         break;
2141
2142                 switch (k.k->type) {
2143                 case KEY_TYPE_dirent:
2144                         d = bkey_s_c_to_dirent(k);
2145
2146                         if (d.v->d_type != DT_DIR &&
2147                             d.v->d_type != DT_SUBVOL)
2148                                 inc_link(c, &s, links, range_start, range_end,
2149                                          le64_to_cpu(d.v->d_inum),
2150                                          d.k->p.snapshot);
2151                         break;
2152                 }
2153         }
2154         bch2_trans_iter_exit(&trans, &iter);
2155
2156         if (ret)
2157                 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
2158
2159         bch2_trans_exit(&trans);
2160         snapshots_seen_exit(&s);
2161         return ret;
2162 }
2163
2164 noinline_for_stack
2165 static int check_nlinks_update_hardlinks(struct bch_fs *c,
2166                                struct nlink_table *links,
2167                                u64 range_start, u64 range_end)
2168 {
2169         struct btree_trans trans;
2170         struct btree_iter iter;
2171         struct bkey_s_c k;
2172         struct bkey_s_c_inode inode;
2173         struct bch_inode_unpacked u;
2174         struct nlink *link = links->d;
2175         int ret = 0;
2176
2177         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2178
2179         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
2180                            POS(0, range_start),
2181                            BTREE_ITER_INTENT|
2182                            BTREE_ITER_PREFETCH|
2183                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2184                 if (k.k->p.offset >= range_end)
2185                         break;
2186
2187                 if (k.k->type != KEY_TYPE_inode)
2188                         continue;
2189
2190                 inode = bkey_s_c_to_inode(k);
2191                 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
2192                         continue;
2193
2194                 BUG_ON(bch2_inode_unpack(inode, &u));
2195
2196                 if (!u.bi_nlink)
2197                         continue;
2198
2199                 while ((cmp_int(link->inum, k.k->p.offset) ?:
2200                         cmp_int(link->snapshot, k.k->p.snapshot)) < 0) {
2201                         link++;
2202                         BUG_ON(link >= links->d + links->nr);
2203                 }
2204
2205                 if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c,
2206                                 "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)",
2207                                 u.bi_inum, mode_to_type(u.bi_mode),
2208                                 bch2_inode_nlink_get(&u), link->count)) {
2209                         bch2_inode_nlink_set(&u, link->count);
2210
2211                         ret = write_inode(&trans, &u, k.k->p.snapshot);
2212                         if (ret)
2213                                 bch_err(c, "error in fsck: error %i updating inode", ret);
2214                 }
2215         }
2216 fsck_err:
2217         bch2_trans_iter_exit(&trans, &iter);
2218         bch2_trans_exit(&trans);
2219
2220         if (ret)
2221                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2222
2223         return ret;
2224 }
2225
2226 noinline_for_stack
2227 static int check_nlinks(struct bch_fs *c)
2228 {
2229         struct nlink_table links = { 0 };
2230         u64 this_iter_range_start, next_iter_range_start = 0;
2231         int ret = 0;
2232
2233         bch_verbose(c, "checking inode nlinks");
2234
2235         do {
2236                 this_iter_range_start = next_iter_range_start;
2237                 next_iter_range_start = U64_MAX;
2238
2239                 ret = check_nlinks_find_hardlinks(c, &links,
2240                                                   this_iter_range_start,
2241                                                   &next_iter_range_start);
2242
2243                 ret = check_nlinks_walk_dirents(c, &links,
2244                                           this_iter_range_start,
2245                                           next_iter_range_start);
2246                 if (ret)
2247                         break;
2248
2249                 ret = check_nlinks_update_hardlinks(c, &links,
2250                                          this_iter_range_start,
2251                                          next_iter_range_start);
2252                 if (ret)
2253                         break;
2254
2255                 links.nr = 0;
2256         } while (next_iter_range_start != U64_MAX);
2257
2258         kvfree(links.d);
2259
2260         return ret;
2261 }
2262
2263 static int fix_reflink_p_key(struct btree_trans *trans, struct btree_iter *iter)
2264 {
2265         struct bkey_s_c k;
2266         struct bkey_s_c_reflink_p p;
2267         struct bkey_i_reflink_p *u;
2268         int ret;
2269
2270         k = bch2_btree_iter_peek(iter);
2271         if (!k.k)
2272                 return 0;
2273
2274         ret = bkey_err(k);
2275         if (ret)
2276                 return ret;
2277
2278         if (k.k->type != KEY_TYPE_reflink_p)
2279                 return 0;
2280
2281         p = bkey_s_c_to_reflink_p(k);
2282
2283         if (!p.v->front_pad && !p.v->back_pad)
2284                 return 0;
2285
2286         u = bch2_trans_kmalloc(trans, sizeof(*u));
2287         ret = PTR_ERR_OR_ZERO(u);
2288         if (ret)
2289                 return ret;
2290
2291         bkey_reassemble(&u->k_i, k);
2292         u->v.front_pad  = 0;
2293         u->v.back_pad   = 0;
2294
2295         return bch2_trans_update(trans, iter, &u->k_i, BTREE_TRIGGER_NORUN);
2296 }
2297
2298 noinline_for_stack
2299 static int fix_reflink_p(struct bch_fs *c)
2300 {
2301         struct btree_trans trans;
2302         struct btree_iter iter;
2303         struct bkey_s_c k;
2304         int ret;
2305
2306         if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix)
2307                 return 0;
2308
2309         bch_verbose(c, "fixing reflink_p keys");
2310
2311         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2312
2313         for_each_btree_key(&trans, iter, BTREE_ID_extents, POS_MIN,
2314                            BTREE_ITER_INTENT|
2315                            BTREE_ITER_PREFETCH|
2316                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2317                 if (k.k->type == KEY_TYPE_reflink_p) {
2318                         ret = __bch2_trans_do(&trans, NULL, NULL,
2319                                               BTREE_INSERT_NOFAIL|
2320                                               BTREE_INSERT_LAZY_RW,
2321                                               fix_reflink_p_key(&trans, &iter));
2322                         if (ret)
2323                                 break;
2324                 }
2325         }
2326         bch2_trans_iter_exit(&trans, &iter);
2327
2328         bch2_trans_exit(&trans);
2329         return ret;
2330 }
2331
2332 /*
2333  * Checks for inconsistencies that shouldn't happen, unless we have a bug.
2334  * Doesn't fix them yet, mainly because they haven't yet been observed:
2335  */
2336 int bch2_fsck_full(struct bch_fs *c)
2337 {
2338         return  bch2_fs_snapshots_check(c) ?:
2339                 check_inodes(c, true) ?:
2340                 check_subvols(c) ?:
2341                 check_extents(c) ?:
2342                 check_dirents(c) ?:
2343                 check_xattrs(c) ?:
2344                 check_root(c) ?:
2345                 check_directory_structure(c) ?:
2346                 check_nlinks(c) ?:
2347                 fix_reflink_p(c);
2348 }
2349
2350 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
2351 {
2352         return check_inodes(c, false);
2353 }