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