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(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 = bkey_is_inode(k.k)
 161                 ? bch2_inode_unpack(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 (!bkey_is_inode(k.k)) {
 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(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)
 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 (bkey_is_inode(k.k))
 627                         add_inode(c, w, 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 (!bkey_is_inode(k.k))
 680                         continue;
 681
 682                 if (ref_visible(c, s, s->pos.snapshot, k.k->p.snapshot)) {
 683                         add_inode(c, w, 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 bch_inode_unpacked u;
 809         bool do_update = false;
 810         int ret;
 811
 812         k = bch2_btree_iter_peek(iter);
 813         if (!k.k)
 814                 return 0;
 815
 816         ret = bkey_err(k);
 817         if (ret)
 818                 return ret;
 819
 820         ret = check_key_has_snapshot(trans, iter, k);
 821         if (ret)
 822                 return ret < 0 ? ret : 0;
 823
 824         /*
 825          * if snapshot id isn't a leaf node, skip it - deletion in
 826          * particular is not atomic, so on the internal snapshot nodes
 827          * we can see inodes marked for deletion after a clean shutdown
 828          */
 829         if (bch2_snapshot_internal_node(c, k.k->p.snapshot))
 830                 return 0;
 831
 832         if (!bkey_is_inode(k.k))
 833                 return 0;
 834
 835         BUG_ON(bch2_inode_unpack(k, &u));
 836
 837         if (!full &&
 838             !(u.bi_flags & (BCH_INODE_I_SIZE_DIRTY|
 839                             BCH_INODE_I_SECTORS_DIRTY|
 840                             BCH_INODE_UNLINKED)))
 841                 return 0;
 842
 843         if (prev->bi_inum != u.bi_inum)
 844                 *prev = u;
 845
 846         if (fsck_err_on(prev->bi_hash_seed      != u.bi_hash_seed ||
 847                         inode_d_type(prev)      != inode_d_type(&u), c,
 848                         "inodes in different snapshots don't match")) {
 849                 bch_err(c, "repair not implemented yet");
 850                 return -EINVAL;
 851         }
 852
 853         if (u.bi_flags & BCH_INODE_UNLINKED &&
 854             (!c->sb.clean ||
 855              fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
 856                       u.bi_inum))) {
 857                 bch2_trans_unlock(trans);
 858                 bch2_fs_lazy_rw(c);
 859
 860                 ret = fsck_inode_rm(trans, u.bi_inum, iter->pos.snapshot);
 861                 if (ret)
 862                         bch_err(c, "error in fsck: error %i while deleting inode", ret);
 863                 return ret;
 864         }
 865
 866         if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
 867             (!c->sb.clean ||
 868              fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
 869                       u.bi_inum))) {
 870                 bch_verbose(c, "truncating inode %llu", u.bi_inum);
 871
 872                 bch2_trans_unlock(trans);
 873                 bch2_fs_lazy_rw(c);
 874
 875                 /*
 876                  * XXX: need to truncate partial blocks too here - or ideally
 877                  * just switch units to bytes and that issue goes away
 878                  */
 879                 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
 880                                 SPOS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9,
 881                                      iter->pos.snapshot),
 882                                 POS(u.bi_inum, U64_MAX),
 883                                 0, NULL);
 884                 if (ret) {
 885                         bch_err(c, "error in fsck: error %i truncating inode", ret);
 886                         return ret;
 887                 }
 888
 889                 /*
 890                  * We truncated without our normal sector accounting hook, just
 891                  * make sure we recalculate it:
 892                  */
 893                 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
 894
 895                 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
 896                 do_update = true;
 897         }
 898
 899         if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
 900             (!c->sb.clean ||
 901              fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
 902                       u.bi_inum))) {
 903                 s64 sectors;
 904
 905                 bch_verbose(c, "recounting sectors for inode %llu",
 906                             u.bi_inum);
 907
 908                 sectors = bch2_count_inode_sectors(trans, u.bi_inum, iter->pos.snapshot);
 909                 if (sectors < 0) {
 910                         bch_err(c, "error in fsck: error %i recounting inode sectors",
 911                                 (int) sectors);
 912                         return sectors;
 913                 }
 914
 915                 u.bi_sectors = sectors;
 916                 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
 917                 do_update = true;
 918         }
 919
 920         if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) {
 921                 u.bi_dir = 0;
 922                 u.bi_dir_offset = 0;
 923                 u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED;
 924                 do_update = true;
 925         }
 926
 927         if (do_update) {
 928                 ret = write_inode(trans, &u, iter->pos.snapshot);
 929                 if (ret)
 930                         bch_err(c, "error in fsck: error %i "
 931                                 "updating inode", ret);
 932         }
 933 fsck_err:
 934         return ret;
 935 }
 936
 937 noinline_for_stack
 938 static int check_inodes(struct bch_fs *c, bool full)
 939 {
 940         struct btree_trans trans;
 941         struct btree_iter iter;
 942         struct bch_inode_unpacked prev = { 0 };
 943         int ret;
 944
 945         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 946
 947         bch2_trans_iter_init(&trans, &iter, BTREE_ID_inodes, POS_MIN,
 948                              BTREE_ITER_INTENT|
 949                              BTREE_ITER_PREFETCH|
 950                              BTREE_ITER_ALL_SNAPSHOTS);
 951
 952         do {
 953                 ret = __bch2_trans_do(&trans, NULL, NULL,
 954                                       BTREE_INSERT_LAZY_RW|
 955                                       BTREE_INSERT_NOFAIL,
 956                         check_inode(&trans, &iter, &prev, full));
 957                 if (ret)
 958                         break;
 959         } while (bch2_btree_iter_advance(&iter));
 960         bch2_trans_iter_exit(&trans, &iter);
 961
 962         bch2_trans_exit(&trans);
 963         return ret;
 964 }
 965
 966 static int check_subvol(struct btree_trans *trans,
 967                         struct btree_iter *iter)
 968 {
 969         struct bkey_s_c k;
 970         struct bkey_s_c_subvolume subvol;
 971         int ret;
 972
 973         k = bch2_btree_iter_peek(iter);
 974         if (!k.k)
 975                 return 0;
 976
 977         ret = bkey_err(k);
 978         if (ret)
 979                 return ret;
 980
 981         if (k.k->type != KEY_TYPE_subvolume)
 982                 return 0;
 983
 984         subvol = bkey_s_c_to_subvolume(k);
 985
 986         if (BCH_SUBVOLUME_UNLINKED(subvol.v)) {
 987                 ret = bch2_subvolume_delete(trans, iter->pos.offset);
 988                 if (ret && ret != -EINTR)
 989                         bch_err(trans->c, "error deleting subvolume %llu: %i",
 990                                 iter->pos.offset, ret);
 991                 if (ret)
 992                         return ret;
 993         }
 994
 995         return 0;
 996 }
 997
 998 noinline_for_stack
 999 static int check_subvols(struct bch_fs *c)
1000 {
1001         struct btree_trans trans;
1002         struct btree_iter iter;
1003         int ret;
1004
1005         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1006
1007         bch2_trans_iter_init(&trans, &iter, BTREE_ID_subvolumes,
1008                              POS_MIN,
1009                              BTREE_ITER_INTENT|
1010                              BTREE_ITER_PREFETCH);
1011
1012         do {
1013                 ret = __bch2_trans_do(&trans, NULL, NULL,
1014                                       BTREE_INSERT_LAZY_RW|
1015                                       BTREE_INSERT_NOFAIL,
1016                                       check_subvol(&trans, &iter));
1017                 if (ret)
1018                         break;
1019         } while (bch2_btree_iter_advance(&iter));
1020         bch2_trans_iter_exit(&trans, &iter);
1021
1022         bch2_trans_exit(&trans);
1023         return ret;
1024 }
1025
1026 /*
1027  * Checking for overlapping extents needs to be reimplemented
1028  */
1029 #if 0
1030 static int fix_overlapping_extent(struct btree_trans *trans,
1031                                        struct bkey_s_c k, struct bpos cut_at)
1032 {
1033         struct btree_iter iter;
1034         struct bkey_i *u;
1035         int ret;
1036
1037         u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
1038         ret = PTR_ERR_OR_ZERO(u);
1039         if (ret)
1040                 return ret;
1041
1042         bkey_reassemble(u, k);
1043         bch2_cut_front(cut_at, u);
1044
1045
1046         /*
1047          * We don't want to go through the extent_handle_overwrites path:
1048          *
1049          * XXX: this is going to screw up disk accounting, extent triggers
1050          * assume things about extent overwrites - we should be running the
1051          * triggers manually here
1052          */
1053         bch2_trans_iter_init(trans, &iter, BTREE_ID_extents, u->k.p,
1054                              BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
1055
1056         BUG_ON(iter.flags & BTREE_ITER_IS_EXTENTS);
1057         ret   = bch2_btree_iter_traverse(&iter) ?:
1058                 bch2_trans_update(trans, &iter, u, BTREE_TRIGGER_NORUN) ?:
1059                 bch2_trans_commit(trans, NULL, NULL,
1060                                   BTREE_INSERT_NOFAIL|
1061                                   BTREE_INSERT_LAZY_RW);
1062         bch2_trans_iter_exit(trans, &iter);
1063         return ret;
1064 }
1065 #endif
1066
1067 static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans,
1068                                                 struct btree_iter *iter,
1069                                                 struct bpos pos)
1070 {
1071         struct bkey_s_c k;
1072         int ret;
1073
1074         bch2_trans_iter_init(trans, iter, BTREE_ID_dirents, pos, 0);
1075         k = bch2_btree_iter_peek_slot(iter);
1076         ret = bkey_err(k);
1077         if (!ret && k.k->type != KEY_TYPE_dirent)
1078                 ret = -ENOENT;
1079         if (ret) {
1080                 bch2_trans_iter_exit(trans, iter);
1081                 return (struct bkey_s_c_dirent) { .k = ERR_PTR(ret) };
1082         }
1083
1084         return bkey_s_c_to_dirent(k);
1085 }
1086
1087 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode,
1088                                    struct bkey_s_c_dirent d)
1089 {
1090         return  inode->bi_dir           == d.k->p.inode &&
1091                 inode->bi_dir_offset    == d.k->p.offset;
1092 }
1093
1094 static bool dirent_points_to_inode(struct bkey_s_c_dirent d,
1095                                    struct bch_inode_unpacked *inode)
1096 {
1097         return d.v->d_type == DT_SUBVOL
1098                 ? le32_to_cpu(d.v->d_child_subvol)      == inode->bi_subvol
1099                 : le64_to_cpu(d.v->d_inum)              == inode->bi_inum;
1100 }
1101
1102 static int inode_backpointer_exists(struct btree_trans *trans,
1103                                     struct bch_inode_unpacked *inode,
1104                                     u32 snapshot)
1105 {
1106         struct btree_iter iter;
1107         struct bkey_s_c_dirent d;
1108         int ret;
1109
1110         d = dirent_get_by_pos(trans, &iter,
1111                         SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot));
1112         ret = bkey_err(d.s_c);
1113         if (ret)
1114                 return ret;
1115
1116         ret = dirent_points_to_inode(d, inode);
1117         bch2_trans_iter_exit(trans, &iter);
1118         return ret;
1119 }
1120
1121 static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w)
1122 {
1123         struct bch_fs *c = trans->c;
1124         struct inode_walker_entry *i;
1125         int ret = 0, ret2 = 0;
1126         s64 count2;
1127
1128         for (i = w->d; i < w->d + w->nr; i++) {
1129                 if (i->inode.bi_sectors == i->count)
1130                         continue;
1131
1132                 count2 = lockrestart_do(trans,
1133                         bch2_count_inode_sectors(trans, w->cur_inum, i->snapshot));
1134
1135                 if (fsck_err_on(i->count != count2, c,
1136                                 "fsck counted i_sectors wrong: got %llu should be %llu",
1137                                 i->count, count2)) {
1138                         i->count = count2;
1139                         if (i->inode.bi_sectors == i->count)
1140                                 continue;
1141                 }
1142
1143                 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY), c,
1144                             "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu",
1145                             w->cur_inum, i->snapshot,
1146                             i->inode.bi_sectors, i->count) == FSCK_ERR_IGNORE)
1147                         continue;
1148
1149                 i->inode.bi_sectors = i->count;
1150                 ret = write_inode(trans, &i->inode, i->snapshot);
1151                 if (ret)
1152                         break;
1153                 ret2 = -EINTR;
1154         }
1155 fsck_err:
1156         return ret ?: ret2;
1157 }
1158
1159 static int check_extent(struct btree_trans *trans, struct btree_iter *iter,
1160                         struct inode_walker *inode,
1161                         struct snapshots_seen *s)
1162 {
1163         struct bch_fs *c = trans->c;
1164         struct bkey_s_c k;
1165         struct inode_walker_entry *i;
1166         char buf[200];
1167         int ret = 0;
1168
1169         k = bch2_btree_iter_peek(iter);
1170         if (!k.k)
1171                 return 0;
1172
1173         ret = bkey_err(k);
1174         if (ret)
1175                 return ret;
1176
1177         ret = check_key_has_snapshot(trans, iter, k);
1178         if (ret)
1179                 return ret < 0 ? ret : 0;
1180
1181         ret = snapshots_seen_update(c, s, k.k->p);
1182         if (ret)
1183                 return ret;
1184
1185         if (k.k->type == KEY_TYPE_whiteout)
1186                 return 0;
1187
1188         if (inode->cur_inum != k.k->p.inode) {
1189                 ret = check_i_sectors(trans, inode);
1190                 if (ret)
1191                         return ret;
1192         }
1193 #if 0
1194         if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) {
1195                 char buf1[200];
1196                 char buf2[200];
1197
1198                 bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k));
1199                 bch2_bkey_val_to_text(&PBUF(buf2), c, k);
1200
1201                 if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2))
1202                         return fix_overlapping_extent(trans, k, prev.k->k.p) ?: -EINTR;
1203         }
1204 #endif
1205         ret = __walk_inode(trans, inode, k.k->p);
1206         if (ret < 0)
1207                 return ret;
1208
1209         if (fsck_err_on(ret == INT_MAX, c,
1210                         "extent in missing inode:\n  %s",
1211                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1212                 return bch2_btree_delete_at(trans, iter,
1213                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1214
1215         if (ret == INT_MAX)
1216                 return 0;
1217
1218         i = inode->d + ret;
1219         ret = 0;
1220
1221         if (fsck_err_on(!S_ISREG(i->inode.bi_mode) &&
1222                         !S_ISLNK(i->inode.bi_mode), c,
1223                         "extent in non regular inode mode %o:\n  %s",
1224                         i->inode.bi_mode,
1225                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1226                 return bch2_btree_delete_at(trans, iter,
1227                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1228
1229         if (!bch2_snapshot_internal_node(c, k.k->p.snapshot)) {
1230                 for_each_visible_inode(c, s, inode, k.k->p.snapshot, i) {
1231                         if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
1232                                         k.k->type != KEY_TYPE_reservation &&
1233                                         k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9, c,
1234                                         "extent type %u offset %llu past end of inode %llu, i_size %llu",
1235                                         k.k->type, k.k->p.offset, k.k->p.inode, i->inode.bi_size)) {
1236                                 bch2_fs_lazy_rw(c);
1237                                 return bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
1238                                                 SPOS(k.k->p.inode, round_up(i->inode.bi_size, block_bytes(c)) >> 9,
1239                                                      k.k->p.snapshot),
1240                                                 POS(k.k->p.inode, U64_MAX),
1241                                                 0, NULL) ?: -EINTR;
1242                         }
1243                 }
1244         }
1245
1246         if (bkey_extent_is_allocation(k.k))
1247                 for_each_visible_inode(c, s, inode, k.k->p.snapshot, i)
1248                         i->count += k.k->size;
1249 #if 0
1250         bch2_bkey_buf_reassemble(&prev, c, k);
1251 #endif
1252
1253 fsck_err:
1254         return ret;
1255 }
1256
1257 /*
1258  * Walk extents: verify that extents have a corresponding S_ISREG inode, and
1259  * that i_size an i_sectors are consistent
1260  */
1261 noinline_for_stack
1262 static int check_extents(struct bch_fs *c)
1263 {
1264         struct inode_walker w = inode_walker_init();
1265         struct snapshots_seen s;
1266         struct btree_trans trans;
1267         struct btree_iter iter;
1268         int ret = 0;
1269
1270 #if 0
1271         struct bkey_buf prev;
1272         bch2_bkey_buf_init(&prev);
1273         prev.k->k = KEY(0, 0, 0);
1274 #endif
1275         snapshots_seen_init(&s);
1276         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1277
1278         bch_verbose(c, "checking extents");
1279
1280         bch2_trans_iter_init(&trans, &iter, BTREE_ID_extents,
1281                              POS(BCACHEFS_ROOT_INO, 0),
1282                              BTREE_ITER_INTENT|
1283                              BTREE_ITER_PREFETCH|
1284                              BTREE_ITER_ALL_SNAPSHOTS);
1285
1286         do {
1287                 ret = __bch2_trans_do(&trans, NULL, NULL,
1288                                       BTREE_INSERT_LAZY_RW|
1289                                       BTREE_INSERT_NOFAIL,
1290                         check_extent(&trans, &iter, &w, &s));
1291                 if (ret)
1292                         break;
1293         } while (bch2_btree_iter_advance(&iter));
1294         bch2_trans_iter_exit(&trans, &iter);
1295 #if 0
1296         bch2_bkey_buf_exit(&prev, c);
1297 #endif
1298         inode_walker_exit(&w);
1299         bch2_trans_exit(&trans);
1300         snapshots_seen_exit(&s);
1301
1302         return ret;
1303 }
1304
1305 static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w)
1306 {
1307         struct bch_fs *c = trans->c;
1308         struct inode_walker_entry *i;
1309         int ret = 0, ret2 = 0;
1310         s64 count2;
1311
1312         for (i = w->d; i < w->d + w->nr; i++) {
1313                 if (i->inode.bi_nlink == i->count)
1314                         continue;
1315
1316                 count2 = lockrestart_do(trans,
1317                                 bch2_count_subdirs(trans, w->cur_inum, i->snapshot));
1318
1319                 if (fsck_err_on(i->count != count2, c,
1320                                 "directory %llu:%u: fsck counted subdirectories wrong, got %llu should be %llu",
1321                                 w->cur_inum, i->snapshot, i->count, count2)) {
1322                         i->count = count2;
1323                         if (i->inode.bi_nlink == i->count)
1324                                 continue;
1325                 }
1326
1327                 if (fsck_err_on(i->inode.bi_nlink != i->count, c,
1328                                 "directory %llu:%u with wrong i_nlink: got %u, should be %llu",
1329                                 w->cur_inum, i->snapshot, i->inode.bi_nlink, i->count)) {
1330                         i->inode.bi_nlink = i->count;
1331                         ret = write_inode(trans, &i->inode, i->snapshot);
1332                         if (ret)
1333                                 break;
1334                         ret2 = -EINTR;
1335                 }
1336         }
1337 fsck_err:
1338         return ret ?: ret2;
1339 }
1340
1341 static int check_dirent_target(struct btree_trans *trans,
1342                                struct btree_iter *iter,
1343                                struct bkey_s_c_dirent d,
1344                                struct bch_inode_unpacked *target,
1345                                u32 target_snapshot)
1346 {
1347         struct bch_fs *c = trans->c;
1348         struct bkey_i_dirent *n;
1349         bool backpointer_exists = true;
1350         char buf[200];
1351         int ret = 0;
1352
1353         if (!target->bi_dir &&
1354             !target->bi_dir_offset) {
1355                 target->bi_dir          = d.k->p.inode;
1356                 target->bi_dir_offset   = d.k->p.offset;
1357
1358                 ret = __write_inode(trans, target, target_snapshot);
1359                 if (ret)
1360                         goto err;
1361         }
1362
1363         if (!inode_points_to_dirent(target, d)) {
1364                 ret = inode_backpointer_exists(trans, target, d.k->p.snapshot);
1365                 if (ret < 0)
1366                         goto err;
1367
1368                 backpointer_exists = ret;
1369                 ret = 0;
1370
1371                 if (fsck_err_on(S_ISDIR(target->bi_mode) &&
1372                                 backpointer_exists, c,
1373                                 "directory %llu with multiple links",
1374                                 target->bi_inum)) {
1375                         ret = __remove_dirent(trans, d.k->p);
1376                         if (ret)
1377                                 goto err;
1378                         return 0;
1379                 }
1380
1381                 if (fsck_err_on(backpointer_exists &&
1382                                 !target->bi_nlink, c,
1383                                 "inode %llu has multiple links but i_nlink 0",
1384                                 target->bi_inum)) {
1385                         target->bi_nlink++;
1386                         target->bi_flags &= ~BCH_INODE_UNLINKED;
1387
1388                         ret = __write_inode(trans, target, target_snapshot);
1389                         if (ret)
1390                                 goto err;
1391                 }
1392
1393                 if (fsck_err_on(!backpointer_exists, c,
1394                                 "inode %llu:%u has wrong backpointer:\n"
1395                                 "got       %llu:%llu\n"
1396                                 "should be %llu:%llu",
1397                                 target->bi_inum, target_snapshot,
1398                                 target->bi_dir,
1399                                 target->bi_dir_offset,
1400                                 d.k->p.inode,
1401                                 d.k->p.offset)) {
1402                         target->bi_dir          = d.k->p.inode;
1403                         target->bi_dir_offset   = d.k->p.offset;
1404
1405                         ret = __write_inode(trans, target, target_snapshot);
1406                         if (ret)
1407                                 goto err;
1408                 }
1409         }
1410
1411         if (fsck_err_on(d.v->d_type != inode_d_type(target), c,
1412                         "incorrect d_type: got %s, should be %s:\n%s",
1413                         bch2_d_type_str(d.v->d_type),
1414                         bch2_d_type_str(inode_d_type(target)),
1415                         (bch2_bkey_val_to_text(&PBUF(buf), c, d.s_c), buf))) {
1416                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1417                 ret = PTR_ERR_OR_ZERO(n);
1418                 if (ret)
1419                         return ret;
1420
1421                 bkey_reassemble(&n->k_i, d.s_c);
1422                 n->v.d_type = inode_d_type(target);
1423
1424                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1425                 if (ret)
1426                         return ret;
1427
1428                 d = dirent_i_to_s_c(n);
1429         }
1430
1431         if (d.v->d_type == DT_SUBVOL &&
1432             target->bi_parent_subvol != le32_to_cpu(d.v->d_parent_subvol) &&
1433             (c->sb.version < bcachefs_metadata_version_subvol_dirent ||
1434              fsck_err(c, "dirent has wrong d_parent_subvol field: got %u, should be %u",
1435                       le32_to_cpu(d.v->d_parent_subvol),
1436                       target->bi_parent_subvol))) {
1437                 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k));
1438                 ret = PTR_ERR_OR_ZERO(n);
1439                 if (ret)
1440                         return ret;
1441
1442                 bkey_reassemble(&n->k_i, d.s_c);
1443                 n->v.d_parent_subvol = cpu_to_le32(target->bi_parent_subvol);
1444
1445                 ret = bch2_trans_update(trans, iter, &n->k_i, 0);
1446                 if (ret)
1447                         return ret;
1448
1449                 d = dirent_i_to_s_c(n);
1450         }
1451 err:
1452 fsck_err:
1453         return ret;
1454 }
1455
1456 static int check_dirent(struct btree_trans *trans, struct btree_iter *iter,
1457                         struct bch_hash_info *hash_info,
1458                         struct inode_walker *dir,
1459                         struct inode_walker *target,
1460                         struct snapshots_seen *s)
1461 {
1462         struct bch_fs *c = trans->c;
1463         struct bkey_s_c k;
1464         struct bkey_s_c_dirent d;
1465         struct inode_walker_entry *i;
1466         char buf[200];
1467         int ret;
1468
1469         k = bch2_btree_iter_peek(iter);
1470         if (!k.k)
1471                 return 0;
1472
1473         ret = bkey_err(k);
1474         if (ret)
1475                 return ret;
1476
1477         ret = check_key_has_snapshot(trans, iter, k);
1478         if (ret)
1479                 return ret < 0 ? ret : 0;
1480
1481         ret = snapshots_seen_update(c, s, k.k->p);
1482         if (ret)
1483                 return ret;
1484
1485         if (k.k->type == KEY_TYPE_whiteout)
1486                 return 0;
1487
1488         if (dir->cur_inum != k.k->p.inode) {
1489                 ret = check_subdir_count(trans, dir);
1490                 if (ret)
1491                         return ret;
1492         }
1493
1494         ret = __walk_inode(trans, dir, k.k->p);
1495         if (ret < 0)
1496                 return ret;
1497
1498         if (fsck_err_on(ret == INT_MAX, c,
1499                         "dirent in nonexisting directory:\n%s",
1500                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1501                 return bch2_btree_delete_at(trans, iter,
1502                                 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
1503
1504         if (ret == INT_MAX)
1505                 return 0;
1506
1507         i = dir->d + ret;
1508         ret = 0;
1509
1510         if (fsck_err_on(!S_ISDIR(i->inode.bi_mode), c,
1511                         "dirent in non directory inode type %s:\n%s",
1512                         bch2_d_type_str(inode_d_type(&i->inode)),
1513                         (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf)))
1514                 return bch2_btree_delete_at(trans, iter, 0);
1515
1516         if (dir->first_this_inode)
1517                 *hash_info = bch2_hash_info_init(c, &dir->d[0].inode);
1518
1519         ret = hash_check_key(trans, bch2_dirent_hash_desc,
1520                              hash_info, iter, k);
1521         if (ret < 0)
1522                 return ret;
1523         if (ret) /* dirent has been deleted */
1524                 return 0;
1525
1526         if (k.k->type != KEY_TYPE_dirent)
1527                 return 0;
1528
1529         d = bkey_s_c_to_dirent(k);
1530
1531         if (d.v->d_type == DT_SUBVOL) {
1532                 struct bch_inode_unpacked subvol_root;
1533                 u32 target_subvol = le32_to_cpu(d.v->d_child_subvol);
1534                 u32 target_snapshot;
1535                 u64 target_inum;
1536
1537                 ret = __subvol_lookup(trans, target_subvol,
1538                                       &target_snapshot, &target_inum);
1539                 if (ret && ret != -ENOENT)
1540                         return ret;
1541
1542                 if (fsck_err_on(ret, c,
1543                                 "dirent points to missing subvolume %llu",
1544                                 le64_to_cpu(d.v->d_child_subvol)))
1545                         return __remove_dirent(trans, d.k->p);
1546
1547                 ret = __lookup_inode(trans, target_inum,
1548                                    &subvol_root, &target_snapshot);
1549                 if (ret && ret != -ENOENT)
1550                         return ret;
1551
1552                 if (fsck_err_on(ret, c,
1553                                 "subvolume %u points to missing subvolume root %llu",
1554                                 target_subvol,
1555                                 target_inum)) {
1556                         bch_err(c, "repair not implemented yet");
1557                         return -EINVAL;
1558                 }
1559
1560                 if (fsck_err_on(subvol_root.bi_subvol != target_subvol, c,
1561                                 "subvol root %llu has wrong bi_subvol field: got %u, should be %u",
1562                                 target_inum,
1563                                 subvol_root.bi_subvol, target_subvol)) {
1564                         subvol_root.bi_subvol = target_subvol;
1565                         ret = __write_inode(trans, &subvol_root, target_snapshot);
1566                         if (ret)
1567                                 return ret;
1568                 }
1569
1570                 ret = check_dirent_target(trans, iter, d, &subvol_root,
1571                                           target_snapshot);
1572                 if (ret)
1573                         return ret;
1574         } else {
1575                 ret = __get_visible_inodes(trans, target, s, le64_to_cpu(d.v->d_inum));
1576                 if (ret)
1577                         return ret;
1578
1579                 if (fsck_err_on(!target->nr, c,
1580                                 "dirent points to missing inode:\n%s",
1581                                 (bch2_bkey_val_to_text(&PBUF(buf), c,
1582                                                        k), buf))) {
1583                         ret = __remove_dirent(trans, d.k->p);
1584                         if (ret)
1585                                 return ret;
1586                 }
1587
1588                 for (i = target->d; i < target->d + target->nr; i++) {
1589                         ret = check_dirent_target(trans, iter, d,
1590                                                   &i->inode, i->snapshot);
1591                         if (ret)
1592                                 return ret;
1593                 }
1594         }
1595
1596         if (d.v->d_type == DT_DIR)
1597                 for_each_visible_inode(c, s, dir, d.k->p.snapshot, i)
1598                         i->count++;
1599
1600 fsck_err:
1601         return ret;
1602 }
1603
1604 /*
1605  * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
1606  * validate d_type
1607  */
1608 noinline_for_stack
1609 static int check_dirents(struct bch_fs *c)
1610 {
1611         struct inode_walker dir = inode_walker_init();
1612         struct inode_walker target = inode_walker_init();
1613         struct snapshots_seen s;
1614         struct bch_hash_info hash_info;
1615         struct btree_trans trans;
1616         struct btree_iter iter;
1617         int ret = 0;
1618
1619         bch_verbose(c, "checking dirents");
1620
1621         snapshots_seen_init(&s);
1622         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1623
1624         bch2_trans_iter_init(&trans, &iter, BTREE_ID_dirents,
1625                              POS(BCACHEFS_ROOT_INO, 0),
1626                              BTREE_ITER_INTENT|
1627                              BTREE_ITER_PREFETCH|
1628                              BTREE_ITER_ALL_SNAPSHOTS);
1629
1630         do {
1631                 ret = __bch2_trans_do(&trans, NULL, NULL,
1632                                       BTREE_INSERT_LAZY_RW|
1633                                       BTREE_INSERT_NOFAIL,
1634                         check_dirent(&trans, &iter, &hash_info,
1635                                      &dir, &target, &s));
1636                 if (ret)
1637                         break;
1638         } while (bch2_btree_iter_advance(&iter));
1639         bch2_trans_iter_exit(&trans, &iter);
1640
1641         bch2_trans_exit(&trans);
1642         snapshots_seen_exit(&s);
1643         inode_walker_exit(&dir);
1644         inode_walker_exit(&target);
1645         return ret;
1646 }
1647
1648 static int check_xattr(struct btree_trans *trans, struct btree_iter *iter,
1649                        struct bch_hash_info *hash_info,
1650                        struct inode_walker *inode)
1651 {
1652         struct bch_fs *c = trans->c;
1653         struct bkey_s_c k;
1654         int ret;
1655
1656         k = bch2_btree_iter_peek(iter);
1657         if (!k.k)
1658                 return 0;
1659
1660         ret = bkey_err(k);
1661         if (ret)
1662                 return ret;
1663
1664         ret = check_key_has_snapshot(trans, iter, k);
1665         if (ret)
1666                 return ret;
1667
1668         ret = __walk_inode(trans, inode, k.k->p);
1669         if (ret < 0)
1670                 return ret;
1671
1672         if (fsck_err_on(ret == INT_MAX, c,
1673                         "xattr for missing inode %llu",
1674                         k.k->p.inode))
1675                 return bch2_btree_delete_at(trans, iter, 0);
1676
1677         if (ret == INT_MAX)
1678                 return 0;
1679
1680         ret = 0;
1681
1682         if (inode->first_this_inode)
1683                 *hash_info = bch2_hash_info_init(c, &inode->d[0].inode);
1684
1685         ret = hash_check_key(trans, bch2_xattr_hash_desc, hash_info, iter, k);
1686 fsck_err:
1687         return ret;
1688 }
1689
1690 /*
1691  * Walk xattrs: verify that they all have a corresponding inode
1692  */
1693 noinline_for_stack
1694 static int check_xattrs(struct bch_fs *c)
1695 {
1696         struct inode_walker inode = inode_walker_init();
1697         struct bch_hash_info hash_info;
1698         struct btree_trans trans;
1699         struct btree_iter iter;
1700         int ret = 0;
1701
1702         bch_verbose(c, "checking xattrs");
1703
1704         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1705
1706         bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
1707                              POS(BCACHEFS_ROOT_INO, 0),
1708                              BTREE_ITER_INTENT|
1709                              BTREE_ITER_PREFETCH|
1710                              BTREE_ITER_ALL_SNAPSHOTS);
1711
1712         do {
1713                 ret = __bch2_trans_do(&trans, NULL, NULL,
1714                                       BTREE_INSERT_LAZY_RW|
1715                                       BTREE_INSERT_NOFAIL,
1716                                       check_xattr(&trans, &iter, &hash_info,
1717                                                   &inode));
1718                 if (ret)
1719                         break;
1720         } while (bch2_btree_iter_advance(&iter));
1721         bch2_trans_iter_exit(&trans, &iter);
1722
1723         bch2_trans_exit(&trans);
1724         return ret;
1725 }
1726
1727 static int check_root_trans(struct btree_trans *trans)
1728 {
1729         struct bch_fs *c = trans->c;
1730         struct bch_inode_unpacked root_inode;
1731         u32 snapshot;
1732         u64 inum;
1733         int ret;
1734
1735         ret = __subvol_lookup(trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum);
1736         if (ret && ret != -ENOENT)
1737                 return ret;
1738
1739         if (mustfix_fsck_err_on(ret, c, "root subvol missing")) {
1740                 struct bkey_i_subvolume root_subvol;
1741
1742                 snapshot        = U32_MAX;
1743                 inum            = BCACHEFS_ROOT_INO;
1744
1745                 bkey_subvolume_init(&root_subvol.k_i);
1746                 root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL;
1747                 root_subvol.v.flags     = 0;
1748                 root_subvol.v.snapshot  = cpu_to_le32(snapshot);
1749                 root_subvol.v.inode     = cpu_to_le64(inum);
1750                 ret = __bch2_trans_do(trans, NULL, NULL,
1751                                       BTREE_INSERT_NOFAIL|
1752                                       BTREE_INSERT_LAZY_RW,
1753                         __bch2_btree_insert(trans, BTREE_ID_subvolumes, &root_subvol.k_i));
1754                 if (ret) {
1755                         bch_err(c, "error writing root subvol: %i", ret);
1756                         goto err;
1757                 }
1758
1759         }
1760
1761         ret = __lookup_inode(trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot);
1762         if (ret && ret != -ENOENT)
1763                 return ret;
1764
1765         if (mustfix_fsck_err_on(ret, c, "root directory missing") ||
1766             mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode), c,
1767                                 "root inode not a directory")) {
1768                 bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755,
1769                                 0, NULL);
1770                 root_inode.bi_inum = inum;
1771
1772                 ret = __write_inode(trans, &root_inode, snapshot);
1773                 if (ret)
1774                         bch_err(c, "error writing root inode: %i", ret);
1775         }
1776 err:
1777 fsck_err:
1778         return ret;
1779 }
1780
1781 /* Get root directory, create if it doesn't exist: */
1782 noinline_for_stack
1783 static int check_root(struct bch_fs *c)
1784 {
1785         bch_verbose(c, "checking root directory");
1786
1787         return bch2_trans_do(c, NULL, NULL,
1788                              BTREE_INSERT_NOFAIL|
1789                              BTREE_INSERT_LAZY_RW,
1790                 check_root_trans(&trans));
1791 }
1792
1793 struct pathbuf {
1794         size_t          nr;
1795         size_t          size;
1796
1797         struct pathbuf_entry {
1798                 u64     inum;
1799                 u32     snapshot;
1800         }               *entries;
1801 };
1802
1803 static bool path_is_dup(struct pathbuf *p, u64 inum, u32 snapshot)
1804 {
1805         struct pathbuf_entry *i;
1806
1807         for (i = p->entries; i < p->entries + p->nr; i++)
1808                 if (i->inum     == inum &&
1809                     i->snapshot == snapshot)
1810                         return true;
1811
1812         return false;
1813 }
1814
1815 static int path_down(struct pathbuf *p, u64 inum, u32 snapshot)
1816 {
1817         if (p->nr == p->size) {
1818                 size_t new_size = max_t(size_t, 256UL, p->size * 2);
1819                 void *n = krealloc(p->entries,
1820                                    new_size * sizeof(p->entries[0]),
1821                                    GFP_KERNEL);
1822                 if (!n) {
1823                         return -ENOMEM;
1824                 }
1825
1826                 p->entries = n;
1827                 p->size = new_size;
1828         };
1829
1830         p->entries[p->nr++] = (struct pathbuf_entry) {
1831                 .inum           = inum,
1832                 .snapshot       = snapshot,
1833         };
1834         return 0;
1835 }
1836
1837 /*
1838  * Check that a given inode is reachable from the root:
1839  *
1840  * XXX: we should also be verifying that inodes are in the right subvolumes
1841  */
1842 static int check_path(struct btree_trans *trans,
1843                       struct pathbuf *p,
1844                       struct bch_inode_unpacked *inode,
1845                       u32 snapshot)
1846 {
1847         struct bch_fs *c = trans->c;
1848         int ret = 0;
1849
1850         snapshot = snapshot_t(c, snapshot)->equiv;
1851         p->nr = 0;
1852
1853         while (!(inode->bi_inum == BCACHEFS_ROOT_INO &&
1854                  inode->bi_subvol == BCACHEFS_ROOT_SUBVOL)) {
1855                 struct btree_iter dirent_iter;
1856                 struct bkey_s_c_dirent d;
1857                 u32 parent_snapshot = snapshot;
1858
1859                 if (inode->bi_subvol) {
1860                         u64 inum;
1861
1862                         ret = subvol_lookup(trans, inode->bi_parent_subvol,
1863                                             &parent_snapshot, &inum);
1864                         if (ret)
1865                                 break;
1866                 }
1867
1868                 ret = lockrestart_do(trans,
1869                         PTR_ERR_OR_ZERO((d = dirent_get_by_pos(trans, &dirent_iter,
1870                                           SPOS(inode->bi_dir, inode->bi_dir_offset,
1871                                                parent_snapshot))).k));
1872                 if (ret && ret != -ENOENT)
1873                         break;
1874
1875                 if (!ret && !dirent_points_to_inode(d, inode)) {
1876                         bch2_trans_iter_exit(trans, &dirent_iter);
1877                         ret = -ENOENT;
1878                 }
1879
1880                 if (ret == -ENOENT) {
1881                         if (fsck_err(c,  "unreachable inode %llu:%u, type %s nlink %u backptr %llu:%llu",
1882                                      inode->bi_inum, snapshot,
1883                                      bch2_d_type_str(inode_d_type(inode)),
1884                                      inode->bi_nlink,
1885                                      inode->bi_dir,
1886                                      inode->bi_dir_offset))
1887                                 ret = reattach_inode(trans, inode, snapshot);
1888                         break;
1889                 }
1890
1891                 bch2_trans_iter_exit(trans, &dirent_iter);
1892
1893                 if (!S_ISDIR(inode->bi_mode))
1894                         break;
1895
1896                 ret = path_down(p, inode->bi_inum, snapshot);
1897                 if (ret) {
1898                         bch_err(c, "memory allocation failure");
1899                         return ret;
1900                 }
1901
1902                 snapshot = parent_snapshot;
1903
1904                 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot);
1905                 if (ret) {
1906                         /* Should have been caught in dirents pass */
1907                         bch_err(c, "error looking up parent directory: %i", ret);
1908                         break;
1909                 }
1910
1911                 if (path_is_dup(p, inode->bi_inum, snapshot)) {
1912                         struct pathbuf_entry *i;
1913
1914                         /* XXX print path */
1915                         bch_err(c, "directory structure loop");
1916
1917                         for (i = p->entries; i < p->entries + p->nr; i++)
1918                                 pr_err("%llu:%u", i->inum, i->snapshot);
1919                         pr_err("%llu:%u", inode->bi_inum, snapshot);
1920
1921                         if (!fsck_err(c, "directory structure loop"))
1922                                 return 0;
1923
1924                         ret = __bch2_trans_do(trans, NULL, NULL,
1925                                               BTREE_INSERT_NOFAIL|
1926                                               BTREE_INSERT_LAZY_RW,
1927                                         remove_backpointer(trans, inode));
1928                         if (ret) {
1929                                 bch_err(c, "error removing dirent: %i", ret);
1930                                 break;
1931                         }
1932
1933                         ret = reattach_inode(trans, inode, snapshot);
1934                 }
1935         }
1936 fsck_err:
1937         if (ret)
1938                 bch_err(c, "%s: err %i", __func__, ret);
1939         return ret;
1940 }
1941
1942 /*
1943  * Check for unreachable inodes, as well as loops in the directory structure:
1944  * After check_dirents(), if an inode backpointer doesn't exist that means it's
1945  * unreachable:
1946  */
1947 noinline_for_stack
1948 static int check_directory_structure(struct bch_fs *c)
1949 {
1950         struct btree_trans trans;
1951         struct btree_iter iter;
1952         struct bkey_s_c k;
1953         struct bch_inode_unpacked u;
1954         struct pathbuf path = { 0, 0, NULL };
1955         int ret;
1956
1957         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1958
1959         for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN,
1960                            BTREE_ITER_INTENT|
1961                            BTREE_ITER_PREFETCH|
1962                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
1963                 if (!bkey_is_inode(k.k))
1964                         continue;
1965
1966                 ret = bch2_inode_unpack(k, &u);
1967                 if (ret) {
1968                         /* Should have been caught earlier in fsck: */
1969                         bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
1970                         break;
1971                 }
1972
1973                 if (u.bi_flags & BCH_INODE_UNLINKED)
1974                         continue;
1975
1976                 ret = check_path(&trans, &path, &u, iter.pos.snapshot);
1977                 if (ret)
1978                         break;
1979         }
1980         bch2_trans_iter_exit(&trans, &iter);
1981
1982         BUG_ON(ret == -EINTR);
1983
1984         kfree(path.entries);
1985
1986         bch2_trans_exit(&trans);
1987         return ret;
1988 }
1989
1990 struct nlink_table {
1991         size_t          nr;
1992         size_t          size;
1993
1994         struct nlink {
1995                 u64     inum;
1996                 u32     snapshot;
1997                 u32     count;
1998         }               *d;
1999 };
2000
2001 static int add_nlink(struct nlink_table *t, u64 inum, u32 snapshot)
2002 {
2003         if (t->nr == t->size) {
2004                 size_t new_size = max_t(size_t, 128UL, t->size * 2);
2005                 void *d = kvmalloc(new_size * sizeof(t->d[0]), GFP_KERNEL);
2006                 if (!d) {
2007                         return -ENOMEM;
2008                 }
2009
2010                 if (t->d)
2011                         memcpy(d, t->d, t->size * sizeof(t->d[0]));
2012                 kvfree(t->d);
2013
2014                 t->d = d;
2015                 t->size = new_size;
2016         }
2017
2018
2019         t->d[t->nr++] = (struct nlink) {
2020                 .inum           = inum,
2021                 .snapshot       = snapshot,
2022         };
2023
2024         return 0;
2025 }
2026
2027 static int nlink_cmp(const void *_l, const void *_r)
2028 {
2029         const struct nlink *l = _l;
2030         const struct nlink *r = _r;
2031
2032         return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot);
2033 }
2034
2035 static void inc_link(struct bch_fs *c, struct snapshots_seen *s,
2036                      struct nlink_table *links,
2037                      u64 range_start, u64 range_end, u64 inum, u32 snapshot)
2038 {
2039         struct nlink *link, key = {
2040                 .inum = inum, .snapshot = U32_MAX,
2041         };
2042
2043         if (inum < range_start || inum >= range_end)
2044                 return;
2045
2046         link = __inline_bsearch(&key, links->d, links->nr,
2047                                 sizeof(links->d[0]), nlink_cmp);
2048         if (!link)
2049                 return;
2050
2051         while (link > links->d && link[0].inum == link[-1].inum)
2052                 --link;
2053
2054         for (; link < links->d + links->nr && link->inum == inum; link++)
2055                 if (ref_visible(c, s, snapshot, link->snapshot)) {
2056                         link->count++;
2057                         if (link->snapshot >= snapshot)
2058                                 break;
2059                 }
2060 }
2061
2062 noinline_for_stack
2063 static int check_nlinks_find_hardlinks(struct bch_fs *c,
2064                                        struct nlink_table *t,
2065                                        u64 start, u64 *end)
2066 {
2067         struct btree_trans trans;
2068         struct btree_iter iter;
2069         struct bkey_s_c k;
2070         struct bch_inode_unpacked u;
2071         int ret = 0;
2072
2073         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2074
2075         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
2076                            POS(0, start),
2077                            BTREE_ITER_INTENT|
2078                            BTREE_ITER_PREFETCH|
2079                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2080                 if (!bkey_is_inode(k.k))
2081                         continue;
2082
2083                 /* Should never fail, checked by bch2_inode_invalid: */
2084                 BUG_ON(bch2_inode_unpack(k, &u));
2085
2086                 /*
2087                  * Backpointer and directory structure checks are sufficient for
2088                  * directories, since they can't have hardlinks:
2089                  */
2090                 if (S_ISDIR(le16_to_cpu(u.bi_mode)))
2091                         continue;
2092
2093                 if (!u.bi_nlink)
2094                         continue;
2095
2096                 ret = add_nlink(t, k.k->p.offset, k.k->p.snapshot);
2097                 if (ret) {
2098                         *end = k.k->p.offset;
2099                         ret = 0;
2100                         break;
2101                 }
2102
2103         }
2104         bch2_trans_iter_exit(&trans, &iter);
2105         bch2_trans_exit(&trans);
2106
2107         if (ret)
2108                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2109
2110         return ret;
2111 }
2112
2113 noinline_for_stack
2114 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
2115                                      u64 range_start, u64 range_end)
2116 {
2117         struct btree_trans trans;
2118         struct snapshots_seen s;
2119         struct btree_iter iter;
2120         struct bkey_s_c k;
2121         struct bkey_s_c_dirent d;
2122         int ret;
2123
2124         snapshots_seen_init(&s);
2125
2126         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2127
2128         for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN,
2129                            BTREE_ITER_INTENT|
2130                            BTREE_ITER_PREFETCH|
2131                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2132                 ret = snapshots_seen_update(c, &s, k.k->p);
2133                 if (ret)
2134                         break;
2135
2136                 switch (k.k->type) {
2137                 case KEY_TYPE_dirent:
2138                         d = bkey_s_c_to_dirent(k);
2139
2140                         if (d.v->d_type != DT_DIR &&
2141                             d.v->d_type != DT_SUBVOL)
2142                                 inc_link(c, &s, links, range_start, range_end,
2143                                          le64_to_cpu(d.v->d_inum),
2144                                          d.k->p.snapshot);
2145                         break;
2146                 }
2147         }
2148         bch2_trans_iter_exit(&trans, &iter);
2149
2150         if (ret)
2151                 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
2152
2153         bch2_trans_exit(&trans);
2154         snapshots_seen_exit(&s);
2155         return ret;
2156 }
2157
2158 noinline_for_stack
2159 static int check_nlinks_update_hardlinks(struct bch_fs *c,
2160                                struct nlink_table *links,
2161                                u64 range_start, u64 range_end)
2162 {
2163         struct btree_trans trans;
2164         struct btree_iter iter;
2165         struct bkey_s_c k;
2166         struct bch_inode_unpacked u;
2167         struct nlink *link = links->d;
2168         int ret = 0;
2169
2170         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2171
2172         for_each_btree_key(&trans, iter, BTREE_ID_inodes,
2173                            POS(0, range_start),
2174                            BTREE_ITER_INTENT|
2175                            BTREE_ITER_PREFETCH|
2176                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2177                 if (k.k->p.offset >= range_end)
2178                         break;
2179
2180                 if (!bkey_is_inode(k.k))
2181                         continue;
2182
2183                 BUG_ON(bch2_inode_unpack(k, &u));
2184
2185                 if (S_ISDIR(le16_to_cpu(u.bi_mode)))
2186                         continue;
2187
2188                 if (!u.bi_nlink)
2189                         continue;
2190
2191                 while ((cmp_int(link->inum, k.k->p.offset) ?:
2192                         cmp_int(link->snapshot, k.k->p.snapshot)) < 0) {
2193                         link++;
2194                         BUG_ON(link >= links->d + links->nr);
2195                 }
2196
2197                 if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c,
2198                                 "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)",
2199                                 u.bi_inum, mode_to_type(u.bi_mode),
2200                                 bch2_inode_nlink_get(&u), link->count)) {
2201                         bch2_inode_nlink_set(&u, link->count);
2202
2203                         ret = write_inode(&trans, &u, k.k->p.snapshot);
2204                         if (ret)
2205                                 bch_err(c, "error in fsck: error %i updating inode", ret);
2206                 }
2207         }
2208 fsck_err:
2209         bch2_trans_iter_exit(&trans, &iter);
2210         bch2_trans_exit(&trans);
2211
2212         if (ret)
2213                 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
2214
2215         return ret;
2216 }
2217
2218 noinline_for_stack
2219 static int check_nlinks(struct bch_fs *c)
2220 {
2221         struct nlink_table links = { 0 };
2222         u64 this_iter_range_start, next_iter_range_start = 0;
2223         int ret = 0;
2224
2225         bch_verbose(c, "checking inode nlinks");
2226
2227         do {
2228                 this_iter_range_start = next_iter_range_start;
2229                 next_iter_range_start = U64_MAX;
2230
2231                 ret = check_nlinks_find_hardlinks(c, &links,
2232                                                   this_iter_range_start,
2233                                                   &next_iter_range_start);
2234
2235                 ret = check_nlinks_walk_dirents(c, &links,
2236                                           this_iter_range_start,
2237                                           next_iter_range_start);
2238                 if (ret)
2239                         break;
2240
2241                 ret = check_nlinks_update_hardlinks(c, &links,
2242                                          this_iter_range_start,
2243                                          next_iter_range_start);
2244                 if (ret)
2245                         break;
2246
2247                 links.nr = 0;
2248         } while (next_iter_range_start != U64_MAX);
2249
2250         kvfree(links.d);
2251
2252         return ret;
2253 }
2254
2255 static int fix_reflink_p_key(struct btree_trans *trans, struct btree_iter *iter)
2256 {
2257         struct bkey_s_c k;
2258         struct bkey_s_c_reflink_p p;
2259         struct bkey_i_reflink_p *u;
2260         int ret;
2261
2262         k = bch2_btree_iter_peek(iter);
2263         if (!k.k)
2264                 return 0;
2265
2266         ret = bkey_err(k);
2267         if (ret)
2268                 return ret;
2269
2270         if (k.k->type != KEY_TYPE_reflink_p)
2271                 return 0;
2272
2273         p = bkey_s_c_to_reflink_p(k);
2274
2275         if (!p.v->front_pad && !p.v->back_pad)
2276                 return 0;
2277
2278         u = bch2_trans_kmalloc(trans, sizeof(*u));
2279         ret = PTR_ERR_OR_ZERO(u);
2280         if (ret)
2281                 return ret;
2282
2283         bkey_reassemble(&u->k_i, k);
2284         u->v.front_pad  = 0;
2285         u->v.back_pad   = 0;
2286
2287         return bch2_trans_update(trans, iter, &u->k_i, BTREE_TRIGGER_NORUN);
2288 }
2289
2290 noinline_for_stack
2291 static int fix_reflink_p(struct bch_fs *c)
2292 {
2293         struct btree_trans trans;
2294         struct btree_iter iter;
2295         struct bkey_s_c k;
2296         int ret;
2297
2298         if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix)
2299                 return 0;
2300
2301         bch_verbose(c, "fixing reflink_p keys");
2302
2303         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
2304
2305         for_each_btree_key(&trans, iter, BTREE_ID_extents, POS_MIN,
2306                            BTREE_ITER_INTENT|
2307                            BTREE_ITER_PREFETCH|
2308                            BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
2309                 if (k.k->type == KEY_TYPE_reflink_p) {
2310                         ret = __bch2_trans_do(&trans, NULL, NULL,
2311                                               BTREE_INSERT_NOFAIL|
2312                                               BTREE_INSERT_LAZY_RW,
2313                                               fix_reflink_p_key(&trans, &iter));
2314                         if (ret)
2315                                 break;
2316                 }
2317         }
2318         bch2_trans_iter_exit(&trans, &iter);
2319
2320         bch2_trans_exit(&trans);
2321         return ret;
2322 }
2323
2324 /*
2325  * Checks for inconsistencies that shouldn't happen, unless we have a bug.
2326  * Doesn't fix them yet, mainly because they haven't yet been observed:
2327  */
2328 int bch2_fsck_full(struct bch_fs *c)
2329 {
2330         return  bch2_fs_snapshots_check(c) ?:
2331                 check_inodes(c, true) ?:
2332                 check_subvols(c) ?:
2333                 check_extents(c) ?:
2334                 check_dirents(c) ?:
2335                 check_xattrs(c) ?:
2336                 check_root(c) ?:
2337                 check_directory_structure(c) ?:
2338                 check_nlinks(c) ?:
2339                 fix_reflink_p(c);
2340 }
2341
2342 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
2343 {
2344         return check_inodes(c, false);
2345 }