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

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "btree_key_cache.h"
   5 #include "btree_write_buffer.h"
   6 #include "bkey_methods.h"
   7 #include "btree_update.h"
   8 #include "buckets.h"
   9 #include "error.h"
  10 #include "extents.h"
  11 #include "extent_update.h"
  12 #include "inode.h"
  13 #include "str_hash.h"
  14 #include "snapshot.h"
  15 #include "subvolume.h"
  16 #include "varint.h"
  17
  18 #include <linux/random.h>
  19
  20 #include <asm/unaligned.h>
  21
  22 const char * const bch2_inode_opts[] = {
  23 #define x(name, ...)    #name,
  24         BCH_INODE_OPTS()
  25 #undef  x
  26         NULL,
  27 };
  28
  29 static const u8 byte_table[8] = { 1, 2, 3, 4, 6, 8, 10, 13 };
  30
  31 static int inode_decode_field(const u8 *in, const u8 *end,
  32                               u64 out[2], unsigned *out_bits)
  33 {
  34         __be64 be[2] = { 0, 0 };
  35         unsigned bytes, shift;
  36         u8 *p;
  37
  38         if (in >= end)
  39                 return -1;
  40
  41         if (!*in)
  42                 return -1;
  43
  44         /*
  45          * position of highest set bit indicates number of bytes:
  46          * shift = number of bits to remove in high byte:
  47          */
  48         shift   = 8 - __fls(*in); /* 1 <= shift <= 8 */
  49         bytes   = byte_table[shift - 1];
  50
  51         if (in + bytes > end)
  52                 return -1;
  53
  54         p = (u8 *) be + 16 - bytes;
  55         memcpy(p, in, bytes);
  56         *p ^= (1 << 8) >> shift;
  57
  58         out[0] = be64_to_cpu(be[0]);
  59         out[1] = be64_to_cpu(be[1]);
  60         *out_bits = out[0] ? 64 + fls64(out[0]) : fls64(out[1]);
  61
  62         return bytes;
  63 }
  64
  65 static inline void bch2_inode_pack_inlined(struct bkey_inode_buf *packed,
  66                                            const struct bch_inode_unpacked *inode)
  67 {
  68         struct bkey_i_inode_v3 *k = &packed->inode;
  69         u8 *out = k->v.fields;
  70         u8 *end = (void *) &packed[1];
  71         u8 *last_nonzero_field = out;
  72         unsigned nr_fields = 0, last_nonzero_fieldnr = 0;
  73         unsigned bytes;
  74         int ret;
  75
  76         bkey_inode_v3_init(&packed->inode.k_i);
  77         packed->inode.k.p.offset        = inode->bi_inum;
  78         packed->inode.v.bi_journal_seq  = cpu_to_le64(inode->bi_journal_seq);
  79         packed->inode.v.bi_hash_seed    = inode->bi_hash_seed;
  80         packed->inode.v.bi_flags        = cpu_to_le64(inode->bi_flags);
  81         packed->inode.v.bi_sectors      = cpu_to_le64(inode->bi_sectors);
  82         packed->inode.v.bi_size         = cpu_to_le64(inode->bi_size);
  83         packed->inode.v.bi_version      = cpu_to_le64(inode->bi_version);
  84         SET_INODEv3_MODE(&packed->inode.v, inode->bi_mode);
  85         SET_INODEv3_FIELDS_START(&packed->inode.v, INODEv3_FIELDS_START_CUR);
  86
  87
  88 #define x(_name, _bits)                                                 \
  89         nr_fields++;                                                    \
  90                                                                         \
  91         if (inode->_name) {                                             \
  92                 ret = bch2_varint_encode_fast(out, inode->_name);       \
  93                 out += ret;                                             \
  94                                                                         \
  95                 if (_bits > 64)                                         \
  96                         *out++ = 0;                                     \
  97                                                                         \
  98                 last_nonzero_field = out;                               \
  99                 last_nonzero_fieldnr = nr_fields;                       \
 100         } else {                                                        \
 101                 *out++ = 0;                                             \
 102                                                                         \
 103                 if (_bits > 64)                                         \
 104                         *out++ = 0;                                     \
 105         }
 106
 107         BCH_INODE_FIELDS_v3()
 108 #undef  x
 109         BUG_ON(out > end);
 110
 111         out = last_nonzero_field;
 112         nr_fields = last_nonzero_fieldnr;
 113
 114         bytes = out - (u8 *) &packed->inode.v;
 115         set_bkey_val_bytes(&packed->inode.k, bytes);
 116         memset_u64s_tail(&packed->inode.v, 0, bytes);
 117
 118         SET_INODEv3_NR_FIELDS(&k->v, nr_fields);
 119
 120         if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
 121                 struct bch_inode_unpacked unpacked;
 122
 123                 ret = bch2_inode_unpack(bkey_i_to_s_c(&packed->inode.k_i), &unpacked);
 124                 BUG_ON(ret);
 125                 BUG_ON(unpacked.bi_inum         != inode->bi_inum);
 126                 BUG_ON(unpacked.bi_hash_seed    != inode->bi_hash_seed);
 127                 BUG_ON(unpacked.bi_sectors      != inode->bi_sectors);
 128                 BUG_ON(unpacked.bi_size         != inode->bi_size);
 129                 BUG_ON(unpacked.bi_version      != inode->bi_version);
 130                 BUG_ON(unpacked.bi_mode         != inode->bi_mode);
 131
 132 #define x(_name, _bits) if (unpacked._name != inode->_name)             \
 133                         panic("unpacked %llu should be %llu",           \
 134                               (u64) unpacked._name, (u64) inode->_name);
 135                 BCH_INODE_FIELDS_v3()
 136 #undef  x
 137         }
 138 }
 139
 140 void bch2_inode_pack(struct bkey_inode_buf *packed,
 141                      const struct bch_inode_unpacked *inode)
 142 {
 143         bch2_inode_pack_inlined(packed, inode);
 144 }
 145
 146 static noinline int bch2_inode_unpack_v1(struct bkey_s_c_inode inode,
 147                                 struct bch_inode_unpacked *unpacked)
 148 {
 149         const u8 *in = inode.v->fields;
 150         const u8 *end = bkey_val_end(inode);
 151         u64 field[2];
 152         unsigned fieldnr = 0, field_bits;
 153         int ret;
 154
 155 #define x(_name, _bits)                                 \
 156         if (fieldnr++ == INODE_NR_FIELDS(inode.v)) {                    \
 157                 unsigned offset = offsetof(struct bch_inode_unpacked, _name);\
 158                 memset((void *) unpacked + offset, 0,                   \
 159                        sizeof(*unpacked) - offset);                     \
 160                 return 0;                                               \
 161         }                                                               \
 162                                                                         \
 163         ret = inode_decode_field(in, end, field, &field_bits);          \
 164         if (ret < 0)                                                    \
 165                 return ret;                                             \
 166                                                                         \
 167         if (field_bits > sizeof(unpacked->_name) * 8)                   \
 168                 return -1;                                              \
 169                                                                         \
 170         unpacked->_name = field[1];                                     \
 171         in += ret;
 172
 173         BCH_INODE_FIELDS_v2()
 174 #undef  x
 175
 176         /* XXX: signal if there were more fields than expected? */
 177         return 0;
 178 }
 179
 180 static int bch2_inode_unpack_v2(struct bch_inode_unpacked *unpacked,
 181                                 const u8 *in, const u8 *end,
 182                                 unsigned nr_fields)
 183 {
 184         unsigned fieldnr = 0;
 185         int ret;
 186         u64 v[2];
 187
 188 #define x(_name, _bits)                                                 \
 189         if (fieldnr < nr_fields) {                                      \
 190                 ret = bch2_varint_decode_fast(in, end, &v[0]);          \
 191                 if (ret < 0)                                            \
 192                         return ret;                                     \
 193                 in += ret;                                              \
 194                                                                         \
 195                 if (_bits > 64) {                                       \
 196                         ret = bch2_varint_decode_fast(in, end, &v[1]);  \
 197                         if (ret < 0)                                    \
 198                                 return ret;                             \
 199                         in += ret;                                      \
 200                 } else {                                                \
 201                         v[1] = 0;                                       \
 202                 }                                                       \
 203         } else {                                                        \
 204                 v[0] = v[1] = 0;                                        \
 205         }                                                               \
 206                                                                         \
 207         unpacked->_name = v[0];                                         \
 208         if (v[1] || v[0] != unpacked->_name)                            \
 209                 return -1;                                              \
 210         fieldnr++;
 211
 212         BCH_INODE_FIELDS_v2()
 213 #undef  x
 214
 215         /* XXX: signal if there were more fields than expected? */
 216         return 0;
 217 }
 218
 219 static int bch2_inode_unpack_v3(struct bkey_s_c k,
 220                                 struct bch_inode_unpacked *unpacked)
 221 {
 222         struct bkey_s_c_inode_v3 inode = bkey_s_c_to_inode_v3(k);
 223         const u8 *in = inode.v->fields;
 224         const u8 *end = bkey_val_end(inode);
 225         unsigned nr_fields = INODEv3_NR_FIELDS(inode.v);
 226         unsigned fieldnr = 0;
 227         int ret;
 228         u64 v[2];
 229
 230         unpacked->bi_inum       = inode.k->p.offset;
 231         unpacked->bi_journal_seq= le64_to_cpu(inode.v->bi_journal_seq);
 232         unpacked->bi_hash_seed  = inode.v->bi_hash_seed;
 233         unpacked->bi_flags      = le64_to_cpu(inode.v->bi_flags);
 234         unpacked->bi_sectors    = le64_to_cpu(inode.v->bi_sectors);
 235         unpacked->bi_size       = le64_to_cpu(inode.v->bi_size);
 236         unpacked->bi_version    = le64_to_cpu(inode.v->bi_version);
 237         unpacked->bi_mode       = INODEv3_MODE(inode.v);
 238
 239 #define x(_name, _bits)                                                 \
 240         if (fieldnr < nr_fields) {                                      \
 241                 ret = bch2_varint_decode_fast(in, end, &v[0]);          \
 242                 if (ret < 0)                                            \
 243                         return ret;                                     \
 244                 in += ret;                                              \
 245                                                                         \
 246                 if (_bits > 64) {                                       \
 247                         ret = bch2_varint_decode_fast(in, end, &v[1]);  \
 248                         if (ret < 0)                                    \
 249                                 return ret;                             \
 250                         in += ret;                                      \
 251                 } else {                                                \
 252                         v[1] = 0;                                       \
 253                 }                                                       \
 254         } else {                                                        \
 255                 v[0] = v[1] = 0;                                        \
 256         }                                                               \
 257                                                                         \
 258         unpacked->_name = v[0];                                         \
 259         if (v[1] || v[0] != unpacked->_name)                            \
 260                 return -1;                                              \
 261         fieldnr++;
 262
 263         BCH_INODE_FIELDS_v3()
 264 #undef  x
 265
 266         /* XXX: signal if there were more fields than expected? */
 267         return 0;
 268 }
 269
 270 static noinline int bch2_inode_unpack_slowpath(struct bkey_s_c k,
 271                                                struct bch_inode_unpacked *unpacked)
 272 {
 273         memset(unpacked, 0, sizeof(*unpacked));
 274
 275         switch (k.k->type) {
 276         case KEY_TYPE_inode: {
 277                 struct bkey_s_c_inode inode = bkey_s_c_to_inode(k);
 278
 279                 unpacked->bi_inum       = inode.k->p.offset;
 280                 unpacked->bi_journal_seq= 0;
 281                 unpacked->bi_hash_seed  = inode.v->bi_hash_seed;
 282                 unpacked->bi_flags      = le32_to_cpu(inode.v->bi_flags);
 283                 unpacked->bi_mode       = le16_to_cpu(inode.v->bi_mode);
 284
 285                 if (INODE_NEW_VARINT(inode.v)) {
 286                         return bch2_inode_unpack_v2(unpacked, inode.v->fields,
 287                                                     bkey_val_end(inode),
 288                                                     INODE_NR_FIELDS(inode.v));
 289                 } else {
 290                         return bch2_inode_unpack_v1(inode, unpacked);
 291                 }
 292                 break;
 293         }
 294         case KEY_TYPE_inode_v2: {
 295                 struct bkey_s_c_inode_v2 inode = bkey_s_c_to_inode_v2(k);
 296
 297                 unpacked->bi_inum       = inode.k->p.offset;
 298                 unpacked->bi_journal_seq= le64_to_cpu(inode.v->bi_journal_seq);
 299                 unpacked->bi_hash_seed  = inode.v->bi_hash_seed;
 300                 unpacked->bi_flags      = le64_to_cpu(inode.v->bi_flags);
 301                 unpacked->bi_mode       = le16_to_cpu(inode.v->bi_mode);
 302
 303                 return bch2_inode_unpack_v2(unpacked, inode.v->fields,
 304                                             bkey_val_end(inode),
 305                                             INODEv2_NR_FIELDS(inode.v));
 306         }
 307         default:
 308                 BUG();
 309         }
 310 }
 311
 312 int bch2_inode_unpack(struct bkey_s_c k,
 313                       struct bch_inode_unpacked *unpacked)
 314 {
 315         if (likely(k.k->type == KEY_TYPE_inode_v3))
 316                 return bch2_inode_unpack_v3(k, unpacked);
 317         return bch2_inode_unpack_slowpath(k, unpacked);
 318 }
 319
 320 static int bch2_inode_peek_nowarn(struct btree_trans *trans,
 321                     struct btree_iter *iter,
 322                     struct bch_inode_unpacked *inode,
 323                     subvol_inum inum, unsigned flags)
 324 {
 325         struct bkey_s_c k;
 326         u32 snapshot;
 327         int ret;
 328
 329         ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);
 330         if (ret)
 331                 return ret;
 332
 333         k = bch2_bkey_get_iter(trans, iter, BTREE_ID_inodes,
 334                                SPOS(0, inum.inum, snapshot),
 335                                flags|BTREE_ITER_CACHED);
 336         ret = bkey_err(k);
 337         if (ret)
 338                 return ret;
 339
 340         ret = bkey_is_inode(k.k) ? 0 : -BCH_ERR_ENOENT_inode;
 341         if (ret)
 342                 goto err;
 343
 344         ret = bch2_inode_unpack(k, inode);
 345         if (ret)
 346                 goto err;
 347
 348         return 0;
 349 err:
 350         bch2_trans_iter_exit(trans, iter);
 351         return ret;
 352 }
 353
 354 int bch2_inode_peek(struct btree_trans *trans,
 355                     struct btree_iter *iter,
 356                     struct bch_inode_unpacked *inode,
 357                     subvol_inum inum, unsigned flags)
 358 {
 359         int ret = bch2_inode_peek_nowarn(trans, iter, inode, inum, flags);
 360         bch_err_msg(trans->c, ret, "looking up inum %u:%llu:", inum.subvol, inum.inum);
 361         return ret;
 362 }
 363
 364 int bch2_inode_write(struct btree_trans *trans,
 365                      struct btree_iter *iter,
 366                      struct bch_inode_unpacked *inode)
 367 {
 368         struct bkey_inode_buf *inode_p;
 369
 370         inode_p = bch2_trans_kmalloc(trans, sizeof(*inode_p));
 371         if (IS_ERR(inode_p))
 372                 return PTR_ERR(inode_p);
 373
 374         bch2_inode_pack_inlined(inode_p, inode);
 375         inode_p->inode.k.p.snapshot = iter->snapshot;
 376         return bch2_trans_update(trans, iter, &inode_p->inode.k_i, 0);
 377 }
 378
 379 struct bkey_i *bch2_inode_to_v3(struct btree_trans *trans, struct bkey_i *k)
 380 {
 381         struct bch_inode_unpacked u;
 382         struct bkey_inode_buf *inode_p;
 383         int ret;
 384
 385         if (!bkey_is_inode(&k->k))
 386                 return ERR_PTR(-ENOENT);
 387
 388         inode_p = bch2_trans_kmalloc(trans, sizeof(*inode_p));
 389         if (IS_ERR(inode_p))
 390                 return ERR_CAST(inode_p);
 391
 392         ret = bch2_inode_unpack(bkey_i_to_s_c(k), &u);
 393         if (ret)
 394                 return ERR_PTR(ret);
 395
 396         bch2_inode_pack(inode_p, &u);
 397         return &inode_p->inode.k_i;
 398 }
 399
 400 static int __bch2_inode_invalid(struct bkey_s_c k, struct printbuf *err)
 401 {
 402         struct bch_inode_unpacked unpacked;
 403
 404         if (k.k->p.inode) {
 405                 prt_printf(err, "nonzero k.p.inode");
 406                 return -BCH_ERR_invalid_bkey;
 407         }
 408
 409         if (k.k->p.offset < BLOCKDEV_INODE_MAX) {
 410                 prt_printf(err, "fs inode in blockdev range");
 411                 return -BCH_ERR_invalid_bkey;
 412         }
 413
 414         if (bch2_inode_unpack(k, &unpacked)) {
 415                 prt_printf(err, "invalid variable length fields");
 416                 return -BCH_ERR_invalid_bkey;
 417         }
 418
 419         if (unpacked.bi_data_checksum >= BCH_CSUM_OPT_NR + 1) {
 420                 prt_printf(err, "invalid data checksum type (%u >= %u",
 421                         unpacked.bi_data_checksum, BCH_CSUM_OPT_NR + 1);
 422                 return -BCH_ERR_invalid_bkey;
 423         }
 424
 425         if (unpacked.bi_compression >= BCH_COMPRESSION_OPT_NR + 1) {
 426                 prt_printf(err, "invalid data checksum type (%u >= %u)",
 427                        unpacked.bi_compression, BCH_COMPRESSION_OPT_NR + 1);
 428                 return -BCH_ERR_invalid_bkey;
 429         }
 430
 431         if ((unpacked.bi_flags & BCH_INODE_UNLINKED) &&
 432             unpacked.bi_nlink != 0) {
 433                 prt_printf(err, "flagged as unlinked but bi_nlink != 0");
 434                 return -BCH_ERR_invalid_bkey;
 435         }
 436
 437         if (unpacked.bi_subvol && !S_ISDIR(unpacked.bi_mode)) {
 438                 prt_printf(err, "subvolume root but not a directory");
 439                 return -BCH_ERR_invalid_bkey;
 440         }
 441
 442         return 0;
 443 }
 444
 445 int bch2_inode_invalid(const struct bch_fs *c, struct bkey_s_c k,
 446                        enum bkey_invalid_flags flags,
 447                        struct printbuf *err)
 448 {
 449         struct bkey_s_c_inode inode = bkey_s_c_to_inode(k);
 450
 451         if (INODE_STR_HASH(inode.v) >= BCH_STR_HASH_NR) {
 452                 prt_printf(err, "invalid str hash type (%llu >= %u)",
 453                        INODE_STR_HASH(inode.v), BCH_STR_HASH_NR);
 454                 return -BCH_ERR_invalid_bkey;
 455         }
 456
 457         return __bch2_inode_invalid(k, err);
 458 }
 459
 460 int bch2_inode_v2_invalid(const struct bch_fs *c, struct bkey_s_c k,
 461                           enum bkey_invalid_flags flags,
 462                           struct printbuf *err)
 463 {
 464         struct bkey_s_c_inode_v2 inode = bkey_s_c_to_inode_v2(k);
 465
 466         if (INODEv2_STR_HASH(inode.v) >= BCH_STR_HASH_NR) {
 467                 prt_printf(err, "invalid str hash type (%llu >= %u)",
 468                        INODEv2_STR_HASH(inode.v), BCH_STR_HASH_NR);
 469                 return -BCH_ERR_invalid_bkey;
 470         }
 471
 472         return __bch2_inode_invalid(k, err);
 473 }
 474
 475 int bch2_inode_v3_invalid(const struct bch_fs *c, struct bkey_s_c k,
 476                           enum bkey_invalid_flags flags,
 477                           struct printbuf *err)
 478 {
 479         struct bkey_s_c_inode_v3 inode = bkey_s_c_to_inode_v3(k);
 480
 481         if (INODEv3_FIELDS_START(inode.v) < INODEv3_FIELDS_START_INITIAL ||
 482             INODEv3_FIELDS_START(inode.v) > bkey_val_u64s(inode.k)) {
 483                 prt_printf(err, "invalid fields_start (got %llu, min %u max %zu)",
 484                        INODEv3_FIELDS_START(inode.v),
 485                        INODEv3_FIELDS_START_INITIAL,
 486                        bkey_val_u64s(inode.k));
 487                 return -BCH_ERR_invalid_bkey;
 488         }
 489
 490         if (INODEv3_STR_HASH(inode.v) >= BCH_STR_HASH_NR) {
 491                 prt_printf(err, "invalid str hash type (%llu >= %u)",
 492                        INODEv3_STR_HASH(inode.v), BCH_STR_HASH_NR);
 493                 return -BCH_ERR_invalid_bkey;
 494         }
 495
 496         return __bch2_inode_invalid(k, err);
 497 }
 498
 499 static void __bch2_inode_unpacked_to_text(struct printbuf *out,
 500                                           struct bch_inode_unpacked *inode)
 501 {
 502         prt_printf(out, "mode %o flags %x journal_seq %llu bi_size %llu bi_sectors %llu bi_version %llu",
 503                inode->bi_mode, inode->bi_flags,
 504                inode->bi_journal_seq,
 505                inode->bi_size,
 506                inode->bi_sectors,
 507                inode->bi_version);
 508
 509 #define x(_name, _bits)                                         \
 510         prt_printf(out, " "#_name " %llu", (u64) inode->_name);
 511         BCH_INODE_FIELDS_v3()
 512 #undef  x
 513 }
 514
 515 void bch2_inode_unpacked_to_text(struct printbuf *out, struct bch_inode_unpacked *inode)
 516 {
 517         prt_printf(out, "inum: %llu ", inode->bi_inum);
 518         __bch2_inode_unpacked_to_text(out, inode);
 519 }
 520
 521 void bch2_inode_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
 522 {
 523         struct bch_inode_unpacked inode;
 524
 525         if (bch2_inode_unpack(k, &inode)) {
 526                 prt_printf(out, "(unpack error)");
 527                 return;
 528         }
 529
 530         __bch2_inode_unpacked_to_text(out, &inode);
 531 }
 532
 533 static inline u64 bkey_inode_flags(struct bkey_s_c k)
 534 {
 535         switch (k.k->type) {
 536         case KEY_TYPE_inode:
 537                 return le32_to_cpu(bkey_s_c_to_inode(k).v->bi_flags);
 538         case KEY_TYPE_inode_v2:
 539                 return le64_to_cpu(bkey_s_c_to_inode_v2(k).v->bi_flags);
 540         case KEY_TYPE_inode_v3:
 541                 return le64_to_cpu(bkey_s_c_to_inode_v3(k).v->bi_flags);
 542         default:
 543                 return 0;
 544         }
 545 }
 546
 547 static inline bool bkey_is_deleted_inode(struct bkey_s_c k)
 548 {
 549         return bkey_inode_flags(k) & BCH_INODE_UNLINKED;
 550 }
 551
 552 int bch2_trans_mark_inode(struct btree_trans *trans,
 553                           enum btree_id btree_id, unsigned level,
 554                           struct bkey_s_c old,
 555                           struct bkey_i *new,
 556                           unsigned flags)
 557 {
 558         int nr = bkey_is_inode(&new->k) - bkey_is_inode(old.k);
 559         bool old_deleted = bkey_is_deleted_inode(old);
 560         bool new_deleted = bkey_is_deleted_inode(bkey_i_to_s_c(new));
 561
 562         if (nr) {
 563                 int ret = bch2_replicas_deltas_realloc(trans, 0);
 564                 struct replicas_delta_list *d = trans->fs_usage_deltas;
 565
 566                 if (ret)
 567                         return ret;
 568
 569                 d->nr_inodes += nr;
 570         }
 571
 572         if (old_deleted != new_deleted) {
 573                 int ret = bch2_btree_bit_mod(trans, BTREE_ID_deleted_inodes, new->k.p, new_deleted);
 574                 if (ret)
 575                         return ret;
 576         }
 577
 578         return 0;
 579 }
 580
 581 int bch2_mark_inode(struct btree_trans *trans,
 582                     enum btree_id btree_id, unsigned level,
 583                     struct bkey_s_c old, struct bkey_s_c new,
 584                     unsigned flags)
 585 {
 586         struct bch_fs *c = trans->c;
 587         struct bch_fs_usage *fs_usage;
 588         u64 journal_seq = trans->journal_res.seq;
 589
 590         if (flags & BTREE_TRIGGER_INSERT) {
 591                 struct bch_inode_v3 *v = (struct bch_inode_v3 *) new.v;
 592
 593                 BUG_ON(!journal_seq);
 594                 BUG_ON(new.k->type != KEY_TYPE_inode_v3);
 595
 596                 v->bi_journal_seq = cpu_to_le64(journal_seq);
 597         }
 598
 599         if (flags & BTREE_TRIGGER_GC) {
 600                 percpu_down_read(&c->mark_lock);
 601                 preempt_disable();
 602
 603                 fs_usage = fs_usage_ptr(c, journal_seq, flags & BTREE_TRIGGER_GC);
 604                 fs_usage->nr_inodes += bkey_is_inode(new.k);
 605                 fs_usage->nr_inodes -= bkey_is_inode(old.k);
 606
 607                 preempt_enable();
 608                 percpu_up_read(&c->mark_lock);
 609         }
 610         return 0;
 611 }
 612
 613 int bch2_inode_generation_invalid(const struct bch_fs *c, struct bkey_s_c k,
 614                                   enum bkey_invalid_flags flags,
 615                                   struct printbuf *err)
 616 {
 617         if (k.k->p.inode) {
 618                 prt_printf(err, "nonzero k.p.inode");
 619                 return -BCH_ERR_invalid_bkey;
 620         }
 621
 622         return 0;
 623 }
 624
 625 void bch2_inode_generation_to_text(struct printbuf *out, struct bch_fs *c,
 626                                    struct bkey_s_c k)
 627 {
 628         struct bkey_s_c_inode_generation gen = bkey_s_c_to_inode_generation(k);
 629
 630         prt_printf(out, "generation: %u", le32_to_cpu(gen.v->bi_generation));
 631 }
 632
 633 void bch2_inode_init_early(struct bch_fs *c,
 634                            struct bch_inode_unpacked *inode_u)
 635 {
 636         enum bch_str_hash_type str_hash =
 637                 bch2_str_hash_opt_to_type(c, c->opts.str_hash);
 638
 639         memset(inode_u, 0, sizeof(*inode_u));
 640
 641         /* ick */
 642         inode_u->bi_flags |= str_hash << INODE_STR_HASH_OFFSET;
 643         get_random_bytes(&inode_u->bi_hash_seed,
 644                          sizeof(inode_u->bi_hash_seed));
 645 }
 646
 647 void bch2_inode_init_late(struct bch_inode_unpacked *inode_u, u64 now,
 648                           uid_t uid, gid_t gid, umode_t mode, dev_t rdev,
 649                           struct bch_inode_unpacked *parent)
 650 {
 651         inode_u->bi_mode        = mode;
 652         inode_u->bi_uid         = uid;
 653         inode_u->bi_gid         = gid;
 654         inode_u->bi_dev         = rdev;
 655         inode_u->bi_atime       = now;
 656         inode_u->bi_mtime       = now;
 657         inode_u->bi_ctime       = now;
 658         inode_u->bi_otime       = now;
 659
 660         if (parent && parent->bi_mode & S_ISGID) {
 661                 inode_u->bi_gid = parent->bi_gid;
 662                 if (S_ISDIR(mode))
 663                         inode_u->bi_mode |= S_ISGID;
 664         }
 665
 666         if (parent) {
 667 #define x(_name, ...)   inode_u->bi_##_name = parent->bi_##_name;
 668                 BCH_INODE_OPTS()
 669 #undef x
 670         }
 671 }
 672
 673 void bch2_inode_init(struct bch_fs *c, struct bch_inode_unpacked *inode_u,
 674                      uid_t uid, gid_t gid, umode_t mode, dev_t rdev,
 675                      struct bch_inode_unpacked *parent)
 676 {
 677         bch2_inode_init_early(c, inode_u);
 678         bch2_inode_init_late(inode_u, bch2_current_time(c),
 679                              uid, gid, mode, rdev, parent);
 680 }
 681
 682 static inline u32 bkey_generation(struct bkey_s_c k)
 683 {
 684         switch (k.k->type) {
 685         case KEY_TYPE_inode:
 686         case KEY_TYPE_inode_v2:
 687                 BUG();
 688         case KEY_TYPE_inode_generation:
 689                 return le32_to_cpu(bkey_s_c_to_inode_generation(k).v->bi_generation);
 690         default:
 691                 return 0;
 692         }
 693 }
 694
 695 /*
 696  * This just finds an empty slot:
 697  */
 698 int bch2_inode_create(struct btree_trans *trans,
 699                       struct btree_iter *iter,
 700                       struct bch_inode_unpacked *inode_u,
 701                       u32 snapshot, u64 cpu)
 702 {
 703         struct bch_fs *c = trans->c;
 704         struct bkey_s_c k;
 705         u64 min, max, start, pos, *hint;
 706         int ret = 0;
 707         unsigned bits = (c->opts.inodes_32bit ? 31 : 63);
 708
 709         if (c->opts.shard_inode_numbers) {
 710                 bits -= c->inode_shard_bits;
 711
 712                 min = (cpu << bits);
 713                 max = (cpu << bits) | ~(ULLONG_MAX << bits);
 714
 715                 min = max_t(u64, min, BLOCKDEV_INODE_MAX);
 716                 hint = c->unused_inode_hints + cpu;
 717         } else {
 718                 min = BLOCKDEV_INODE_MAX;
 719                 max = ~(ULLONG_MAX << bits);
 720                 hint = c->unused_inode_hints;
 721         }
 722
 723         start = READ_ONCE(*hint);
 724
 725         if (start >= max || start < min)
 726                 start = min;
 727
 728         pos = start;
 729         bch2_trans_iter_init(trans, iter, BTREE_ID_inodes, POS(0, pos),
 730                              BTREE_ITER_ALL_SNAPSHOTS|
 731                              BTREE_ITER_INTENT);
 732 again:
 733         while ((k = bch2_btree_iter_peek(iter)).k &&
 734                !(ret = bkey_err(k)) &&
 735                bkey_lt(k.k->p, POS(0, max))) {
 736                 if (pos < iter->pos.offset)
 737                         goto found_slot;
 738
 739                 /*
 740                  * We don't need to iterate over keys in every snapshot once
 741                  * we've found just one:
 742                  */
 743                 pos = iter->pos.offset + 1;
 744                 bch2_btree_iter_set_pos(iter, POS(0, pos));
 745         }
 746
 747         if (!ret && pos < max)
 748                 goto found_slot;
 749
 750         if (!ret && start == min)
 751                 ret = -BCH_ERR_ENOSPC_inode_create;
 752
 753         if (ret) {
 754                 bch2_trans_iter_exit(trans, iter);
 755                 return ret;
 756         }
 757
 758         /* Retry from start */
 759         pos = start = min;
 760         bch2_btree_iter_set_pos(iter, POS(0, pos));
 761         goto again;
 762 found_slot:
 763         bch2_btree_iter_set_pos(iter, SPOS(0, pos, snapshot));
 764         k = bch2_btree_iter_peek_slot(iter);
 765         ret = bkey_err(k);
 766         if (ret) {
 767                 bch2_trans_iter_exit(trans, iter);
 768                 return ret;
 769         }
 770
 771         *hint                   = k.k->p.offset;
 772         inode_u->bi_inum        = k.k->p.offset;
 773         inode_u->bi_generation  = bkey_generation(k);
 774         return 0;
 775 }
 776
 777 static int bch2_inode_delete_keys(struct btree_trans *trans,
 778                                   subvol_inum inum, enum btree_id id)
 779 {
 780         struct btree_iter iter;
 781         struct bkey_s_c k;
 782         struct bkey_i delete;
 783         u32 snapshot;
 784         int ret = 0;
 785
 786         /*
 787          * We're never going to be deleting partial extents, no need to use an
 788          * extent iterator:
 789          */
 790         bch2_trans_iter_init(trans, &iter, id, POS(inum.inum, 0),
 791                              BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
 792
 793         while (1) {
 794                 bch2_trans_begin(trans);
 795
 796                 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);
 797                 if (ret)
 798                         goto err;
 799
 800                 bch2_btree_iter_set_snapshot(&iter, snapshot);
 801
 802                 k = bch2_btree_iter_peek_upto(&iter, POS(inum.inum, U64_MAX));
 803                 ret = bkey_err(k);
 804                 if (ret)
 805                         goto err;
 806
 807                 if (!k.k)
 808                         break;
 809
 810                 bkey_init(&delete.k);
 811                 delete.k.p = iter.pos;
 812
 813                 ret = bch2_trans_update(trans, &iter, &delete, 0) ?:
 814                       bch2_trans_commit(trans, NULL, NULL,
 815                                         BTREE_INSERT_NOFAIL);
 816 err:
 817                 if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
 818                         break;
 819         }
 820
 821         bch2_trans_iter_exit(trans, &iter);
 822         return ret;
 823 }
 824
 825 int bch2_inode_rm(struct bch_fs *c, subvol_inum inum)
 826 {
 827         struct btree_trans *trans = bch2_trans_get(c);
 828         struct btree_iter iter = { NULL };
 829         struct bkey_i_inode_generation delete;
 830         struct bch_inode_unpacked inode_u;
 831         struct bkey_s_c k;
 832         u32 snapshot;
 833         int ret;
 834
 835         /*
 836          * If this was a directory, there shouldn't be any real dirents left -
 837          * but there could be whiteouts (from hash collisions) that we should
 838          * delete:
 839          *
 840          * XXX: the dirent could ideally would delete whiteouts when they're no
 841          * longer needed
 842          */
 843         ret   = bch2_inode_delete_keys(trans, inum, BTREE_ID_extents) ?:
 844                 bch2_inode_delete_keys(trans, inum, BTREE_ID_xattrs) ?:
 845                 bch2_inode_delete_keys(trans, inum, BTREE_ID_dirents);
 846         if (ret)
 847                 goto err;
 848 retry:
 849         bch2_trans_begin(trans);
 850
 851         ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot);
 852         if (ret)
 853                 goto err;
 854
 855         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
 856                                SPOS(0, inum.inum, snapshot),
 857                                BTREE_ITER_INTENT|BTREE_ITER_CACHED);
 858         ret = bkey_err(k);
 859         if (ret)
 860                 goto err;
 861
 862         if (!bkey_is_inode(k.k)) {
 863                 bch2_fs_inconsistent(c,
 864                                      "inode %llu:%u not found when deleting",
 865                                      inum.inum, snapshot);
 866                 ret = -EIO;
 867                 goto err;
 868         }
 869
 870         bch2_inode_unpack(k, &inode_u);
 871
 872         bkey_inode_generation_init(&delete.k_i);
 873         delete.k.p = iter.pos;
 874         delete.v.bi_generation = cpu_to_le32(inode_u.bi_generation + 1);
 875
 876         ret   = bch2_trans_update(trans, &iter, &delete.k_i, 0) ?:
 877                 bch2_trans_commit(trans, NULL, NULL,
 878                                 BTREE_INSERT_NOFAIL);
 879 err:
 880         bch2_trans_iter_exit(trans, &iter);
 881         if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 882                 goto retry;
 883
 884         bch2_trans_put(trans);
 885         return ret;
 886 }
 887
 888 int bch2_inode_find_by_inum_nowarn_trans(struct btree_trans *trans,
 889                                   subvol_inum inum,
 890                                   struct bch_inode_unpacked *inode)
 891 {
 892         struct btree_iter iter;
 893         int ret;
 894
 895         ret = bch2_inode_peek_nowarn(trans, &iter, inode, inum, 0);
 896         if (!ret)
 897                 bch2_trans_iter_exit(trans, &iter);
 898         return ret;
 899 }
 900
 901 int bch2_inode_find_by_inum_trans(struct btree_trans *trans,
 902                                   subvol_inum inum,
 903                                   struct bch_inode_unpacked *inode)
 904 {
 905         struct btree_iter iter;
 906         int ret;
 907
 908         ret = bch2_inode_peek(trans, &iter, inode, inum, 0);
 909         if (!ret)
 910                 bch2_trans_iter_exit(trans, &iter);
 911         return ret;
 912 }
 913
 914 int bch2_inode_find_by_inum(struct bch_fs *c, subvol_inum inum,
 915                             struct bch_inode_unpacked *inode)
 916 {
 917         return bch2_trans_do(c, NULL, NULL, 0,
 918                 bch2_inode_find_by_inum_trans(trans, inum, inode));
 919 }
 920
 921 int bch2_inode_nlink_inc(struct bch_inode_unpacked *bi)
 922 {
 923         if (bi->bi_flags & BCH_INODE_UNLINKED)
 924                 bi->bi_flags &= ~BCH_INODE_UNLINKED;
 925         else {
 926                 if (bi->bi_nlink == U32_MAX)
 927                         return -EINVAL;
 928
 929                 bi->bi_nlink++;
 930         }
 931
 932         return 0;
 933 }
 934
 935 void bch2_inode_nlink_dec(struct btree_trans *trans, struct bch_inode_unpacked *bi)
 936 {
 937         if (bi->bi_nlink && (bi->bi_flags & BCH_INODE_UNLINKED)) {
 938                 bch2_trans_inconsistent(trans, "inode %llu unlinked but link count nonzero",
 939                                         bi->bi_inum);
 940                 return;
 941         }
 942
 943         if (bi->bi_flags & BCH_INODE_UNLINKED) {
 944                 bch2_trans_inconsistent(trans, "inode %llu link count underflow", bi->bi_inum);
 945                 return;
 946         }
 947
 948         if (bi->bi_nlink)
 949                 bi->bi_nlink--;
 950         else
 951                 bi->bi_flags |= BCH_INODE_UNLINKED;
 952 }
 953
 954 struct bch_opts bch2_inode_opts_to_opts(struct bch_inode_unpacked *inode)
 955 {
 956         struct bch_opts ret = { 0 };
 957 #define x(_name, _bits)                                                 \
 958         if (inode->bi_##_name)                                          \
 959                 opt_set(ret, _name, inode->bi_##_name - 1);
 960         BCH_INODE_OPTS()
 961 #undef x
 962         return ret;
 963 }
 964
 965 void bch2_inode_opts_get(struct bch_io_opts *opts, struct bch_fs *c,
 966                          struct bch_inode_unpacked *inode)
 967 {
 968 #define x(_name, _bits)         opts->_name = inode_opt_get(c, inode, _name);
 969         BCH_INODE_OPTS()
 970 #undef x
 971
 972         if (opts->nocow)
 973                 opts->compression = opts->background_compression = opts->data_checksum = opts->erasure_code = 0;
 974 }
 975
 976 int bch2_inode_rm_snapshot(struct btree_trans *trans, u64 inum, u32 snapshot)
 977 {
 978         struct bch_fs *c = trans->c;
 979         struct btree_iter iter = { NULL };
 980         struct bkey_i_inode_generation delete;
 981         struct bch_inode_unpacked inode_u;
 982         struct bkey_s_c k;
 983         int ret;
 984
 985         do {
 986                 ret   = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
 987                                                       SPOS(inum, 0, snapshot),
 988                                                       SPOS(inum, U64_MAX, snapshot),
 989                                                       0, NULL) ?:
 990                         bch2_btree_delete_range_trans(trans, BTREE_ID_dirents,
 991                                                       SPOS(inum, 0, snapshot),
 992                                                       SPOS(inum, U64_MAX, snapshot),
 993                                                       0, NULL) ?:
 994                         bch2_btree_delete_range_trans(trans, BTREE_ID_xattrs,
 995                                                       SPOS(inum, 0, snapshot),
 996                                                       SPOS(inum, U64_MAX, snapshot),
 997                                                       0, NULL);
 998         } while (ret == -BCH_ERR_transaction_restart_nested);
 999         if (ret)
1000                 goto err;
1001 retry:
1002         bch2_trans_begin(trans);
1003
1004         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
1005                                SPOS(0, inum, snapshot), BTREE_ITER_INTENT);
1006         ret = bkey_err(k);
1007         if (ret)
1008                 goto err;
1009
1010         if (!bkey_is_inode(k.k)) {
1011                 bch2_fs_inconsistent(c,
1012                                      "inode %llu:%u not found when deleting",
1013                                      inum, snapshot);
1014                 ret = -EIO;
1015                 goto err;
1016         }
1017
1018         bch2_inode_unpack(k, &inode_u);
1019
1020         /* Subvolume root? */
1021         if (inode_u.bi_subvol)
1022                 bch_warn(c, "deleting inode %llu marked as unlinked, but also a subvolume root!?", inode_u.bi_inum);
1023
1024         bkey_inode_generation_init(&delete.k_i);
1025         delete.k.p = iter.pos;
1026         delete.v.bi_generation = cpu_to_le32(inode_u.bi_generation + 1);
1027
1028         ret   = bch2_trans_update(trans, &iter, &delete.k_i, 0) ?:
1029                 bch2_trans_commit(trans, NULL, NULL,
1030                                 BTREE_INSERT_NOFAIL);
1031 err:
1032         bch2_trans_iter_exit(trans, &iter);
1033         if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
1034                 goto retry;
1035
1036         return ret ?: -BCH_ERR_transaction_restart_nested;
1037 }
1038
1039 static int may_delete_deleted_inode(struct btree_trans *trans, struct bpos pos)
1040 {
1041         struct bch_fs *c = trans->c;
1042         struct btree_iter iter;
1043         struct bkey_s_c k;
1044         struct bch_inode_unpacked inode;
1045         int ret;
1046
1047         if (bch2_snapshot_is_internal_node(c, pos.snapshot))
1048                 return 0;
1049
1050         if (!fsck_err_on(c->sb.clean, c,
1051                          "filesystem marked as clean but have deleted inode %llu:%u",
1052                          pos.offset, pos.snapshot))
1053                 return 0;
1054
1055         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes, pos, BTREE_ITER_CACHED);
1056         ret = bkey_err(k);
1057         if (ret)
1058                 return ret;
1059
1060         ret = bkey_is_inode(k.k) ? 0 : -BCH_ERR_ENOENT_inode;
1061         if (fsck_err_on(!bkey_is_inode(k.k), c,
1062                         "nonexistent inode %llu:%u in deleted_inodes btree",
1063                         pos.offset, pos.snapshot))
1064                 goto delete;
1065
1066         ret = bch2_inode_unpack(k, &inode);
1067         if (ret)
1068                 goto err;
1069
1070         if (fsck_err_on(S_ISDIR(inode.bi_mode), c,
1071                         "directory %llu:%u in deleted_inodes btree",
1072                         pos.offset, pos.snapshot))
1073                 goto delete;
1074
1075         if (fsck_err_on(!(inode.bi_flags & BCH_INODE_UNLINKED), c,
1076                         "non-deleted inode %llu:%u in deleted_inodes btree",
1077                         pos.offset, pos.snapshot))
1078                 goto delete;
1079
1080         return 1;
1081 err:
1082 fsck_err:
1083         return ret;
1084 delete:
1085         return bch2_btree_bit_mod(trans, BTREE_ID_deleted_inodes, pos, false);
1086 }
1087
1088 int bch2_delete_dead_inodes(struct bch_fs *c)
1089 {
1090         struct btree_trans *trans = bch2_trans_get(c);
1091         struct btree_iter iter;
1092         struct bkey_s_c k;
1093         int ret;
1094
1095         ret = bch2_btree_write_buffer_flush_sync(trans);
1096         if (ret)
1097                 goto err;
1098
1099         /*
1100          * Weird transaction restart handling here because on successful delete,
1101          * bch2_inode_rm_snapshot() will return a nested transaction restart,
1102          * but we can't retry because the btree write buffer won't have been
1103          * flushed and we'd spin:
1104          */
1105         for_each_btree_key(trans, iter, BTREE_ID_deleted_inodes, POS_MIN,
1106                            BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
1107                 ret = lockrestart_do(trans, may_delete_deleted_inode(trans, k.k->p));
1108                 if (ret < 0)
1109                         break;
1110
1111                 if (ret) {
1112                         if (!test_bit(BCH_FS_RW, &c->flags)) {
1113                                 bch2_trans_unlock(trans);
1114                                 bch2_fs_lazy_rw(c);
1115                         }
1116
1117                         ret = bch2_inode_rm_snapshot(trans, k.k->p.offset, k.k->p.snapshot);
1118                         if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
1119                                 break;
1120                 }
1121         }
1122         bch2_trans_iter_exit(trans, &iter);
1123 err:
1124         bch2_trans_put(trans);
1125
1126         return ret;
1127 }