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

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include "bcachefs.h"
   3 #include "alloc_background.h"
   4 #include "alloc_foreground.h"
   5 #include "backpointers.h"
   6 #include "btree_cache.h"
   7 #include "btree_io.h"
   8 #include "btree_key_cache.h"
   9 #include "btree_update.h"
  10 #include "btree_update_interior.h"
  11 #include "btree_gc.h"
  12 #include "btree_write_buffer.h"
  13 #include "buckets.h"
  14 #include "buckets_waiting_for_journal.h"
  15 #include "clock.h"
  16 #include "debug.h"
  17 #include "ec.h"
  18 #include "error.h"
  19 #include "lru.h"
  20 #include "recovery.h"
  21 #include "trace.h"
  22 #include "varint.h"
  23
  24 #include <linux/kthread.h>
  25 #include <linux/math64.h>
  26 #include <linux/random.h>
  27 #include <linux/rculist.h>
  28 #include <linux/rcupdate.h>
  29 #include <linux/sched/task.h>
  30 #include <linux/sort.h>
  31
  32 /* Persistent alloc info: */
  33
  34 static const unsigned BCH_ALLOC_V1_FIELD_BYTES[] = {
  35 #define x(name, bits) [BCH_ALLOC_FIELD_V1_##name] = bits / 8,
  36         BCH_ALLOC_FIELDS_V1()
  37 #undef x
  38 };
  39
  40 struct bkey_alloc_unpacked {
  41         u64             journal_seq;
  42         u8              gen;
  43         u8              oldest_gen;
  44         u8              data_type;
  45         bool            need_discard:1;
  46         bool            need_inc_gen:1;
  47 #define x(_name, _bits) u##_bits _name;
  48         BCH_ALLOC_FIELDS_V2()
  49 #undef  x
  50 };
  51
  52 static inline u64 alloc_field_v1_get(const struct bch_alloc *a,
  53                                      const void **p, unsigned field)
  54 {
  55         unsigned bytes = BCH_ALLOC_V1_FIELD_BYTES[field];
  56         u64 v;
  57
  58         if (!(a->fields & (1 << field)))
  59                 return 0;
  60
  61         switch (bytes) {
  62         case 1:
  63                 v = *((const u8 *) *p);
  64                 break;
  65         case 2:
  66                 v = le16_to_cpup(*p);
  67                 break;
  68         case 4:
  69                 v = le32_to_cpup(*p);
  70                 break;
  71         case 8:
  72                 v = le64_to_cpup(*p);
  73                 break;
  74         default:
  75                 BUG();
  76         }
  77
  78         *p += bytes;
  79         return v;
  80 }
  81
  82 static inline void alloc_field_v1_put(struct bkey_i_alloc *a, void **p,
  83                                       unsigned field, u64 v)
  84 {
  85         unsigned bytes = BCH_ALLOC_V1_FIELD_BYTES[field];
  86
  87         if (!v)
  88                 return;
  89
  90         a->v.fields |= 1 << field;
  91
  92         switch (bytes) {
  93         case 1:
  94                 *((u8 *) *p) = v;
  95                 break;
  96         case 2:
  97                 *((__le16 *) *p) = cpu_to_le16(v);
  98                 break;
  99         case 4:
 100                 *((__le32 *) *p) = cpu_to_le32(v);
 101                 break;
 102         case 8:
 103                 *((__le64 *) *p) = cpu_to_le64(v);
 104                 break;
 105         default:
 106                 BUG();
 107         }
 108
 109         *p += bytes;
 110 }
 111
 112 static void bch2_alloc_unpack_v1(struct bkey_alloc_unpacked *out,
 113                                  struct bkey_s_c k)
 114 {
 115         const struct bch_alloc *in = bkey_s_c_to_alloc(k).v;
 116         const void *d = in->data;
 117         unsigned idx = 0;
 118
 119         out->gen = in->gen;
 120
 121 #define x(_name, _bits) out->_name = alloc_field_v1_get(in, &d, idx++);
 122         BCH_ALLOC_FIELDS_V1()
 123 #undef  x
 124 }
 125
 126 static int bch2_alloc_unpack_v2(struct bkey_alloc_unpacked *out,
 127                                 struct bkey_s_c k)
 128 {
 129         struct bkey_s_c_alloc_v2 a = bkey_s_c_to_alloc_v2(k);
 130         const u8 *in = a.v->data;
 131         const u8 *end = bkey_val_end(a);
 132         unsigned fieldnr = 0;
 133         int ret;
 134         u64 v;
 135
 136         out->gen        = a.v->gen;
 137         out->oldest_gen = a.v->oldest_gen;
 138         out->data_type  = a.v->data_type;
 139
 140 #define x(_name, _bits)                                                 \
 141         if (fieldnr < a.v->nr_fields) {                                 \
 142                 ret = bch2_varint_decode_fast(in, end, &v);             \
 143                 if (ret < 0)                                            \
 144                         return ret;                                     \
 145                 in += ret;                                              \
 146         } else {                                                        \
 147                 v = 0;                                                  \
 148         }                                                               \
 149         out->_name = v;                                                 \
 150         if (v != out->_name)                                            \
 151                 return -1;                                              \
 152         fieldnr++;
 153
 154         BCH_ALLOC_FIELDS_V2()
 155 #undef  x
 156         return 0;
 157 }
 158
 159 static int bch2_alloc_unpack_v3(struct bkey_alloc_unpacked *out,
 160                                 struct bkey_s_c k)
 161 {
 162         struct bkey_s_c_alloc_v3 a = bkey_s_c_to_alloc_v3(k);
 163         const u8 *in = a.v->data;
 164         const u8 *end = bkey_val_end(a);
 165         unsigned fieldnr = 0;
 166         int ret;
 167         u64 v;
 168
 169         out->gen        = a.v->gen;
 170         out->oldest_gen = a.v->oldest_gen;
 171         out->data_type  = a.v->data_type;
 172         out->need_discard = BCH_ALLOC_V3_NEED_DISCARD(a.v);
 173         out->need_inc_gen = BCH_ALLOC_V3_NEED_INC_GEN(a.v);
 174         out->journal_seq = le64_to_cpu(a.v->journal_seq);
 175
 176 #define x(_name, _bits)                                                 \
 177         if (fieldnr < a.v->nr_fields) {                                 \
 178                 ret = bch2_varint_decode_fast(in, end, &v);             \
 179                 if (ret < 0)                                            \
 180                         return ret;                                     \
 181                 in += ret;                                              \
 182         } else {                                                        \
 183                 v = 0;                                                  \
 184         }                                                               \
 185         out->_name = v;                                                 \
 186         if (v != out->_name)                                            \
 187                 return -1;                                              \
 188         fieldnr++;
 189
 190         BCH_ALLOC_FIELDS_V2()
 191 #undef  x
 192         return 0;
 193 }
 194
 195 static struct bkey_alloc_unpacked bch2_alloc_unpack(struct bkey_s_c k)
 196 {
 197         struct bkey_alloc_unpacked ret = { .gen = 0 };
 198
 199         switch (k.k->type) {
 200         case KEY_TYPE_alloc:
 201                 bch2_alloc_unpack_v1(&ret, k);
 202                 break;
 203         case KEY_TYPE_alloc_v2:
 204                 bch2_alloc_unpack_v2(&ret, k);
 205                 break;
 206         case KEY_TYPE_alloc_v3:
 207                 bch2_alloc_unpack_v3(&ret, k);
 208                 break;
 209         }
 210
 211         return ret;
 212 }
 213
 214 static unsigned bch_alloc_v1_val_u64s(const struct bch_alloc *a)
 215 {
 216         unsigned i, bytes = offsetof(struct bch_alloc, data);
 217
 218         for (i = 0; i < ARRAY_SIZE(BCH_ALLOC_V1_FIELD_BYTES); i++)
 219                 if (a->fields & (1 << i))
 220                         bytes += BCH_ALLOC_V1_FIELD_BYTES[i];
 221
 222         return DIV_ROUND_UP(bytes, sizeof(u64));
 223 }
 224
 225 int bch2_alloc_v1_invalid(const struct bch_fs *c, struct bkey_s_c k,
 226                           enum bkey_invalid_flags flags,
 227                           struct printbuf *err)
 228 {
 229         struct bkey_s_c_alloc a = bkey_s_c_to_alloc(k);
 230
 231         /* allow for unknown fields */
 232         if (bkey_val_u64s(a.k) < bch_alloc_v1_val_u64s(a.v)) {
 233                 prt_printf(err, "incorrect value size (%zu < %u)",
 234                        bkey_val_u64s(a.k), bch_alloc_v1_val_u64s(a.v));
 235                 return -BCH_ERR_invalid_bkey;
 236         }
 237
 238         return 0;
 239 }
 240
 241 int bch2_alloc_v2_invalid(const struct bch_fs *c, struct bkey_s_c k,
 242                           enum bkey_invalid_flags flags,
 243                           struct printbuf *err)
 244 {
 245         struct bkey_alloc_unpacked u;
 246
 247         if (bch2_alloc_unpack_v2(&u, k)) {
 248                 prt_printf(err, "unpack error");
 249                 return -BCH_ERR_invalid_bkey;
 250         }
 251
 252         return 0;
 253 }
 254
 255 int bch2_alloc_v3_invalid(const struct bch_fs *c, struct bkey_s_c k,
 256                           enum bkey_invalid_flags flags,
 257                           struct printbuf *err)
 258 {
 259         struct bkey_alloc_unpacked u;
 260
 261         if (bch2_alloc_unpack_v3(&u, k)) {
 262                 prt_printf(err, "unpack error");
 263                 return -BCH_ERR_invalid_bkey;
 264         }
 265
 266         return 0;
 267 }
 268
 269 int bch2_alloc_v4_invalid(const struct bch_fs *c, struct bkey_s_c k,
 270                           unsigned flags, struct printbuf *err)
 271 {
 272         struct bkey_s_c_alloc_v4 a = bkey_s_c_to_alloc_v4(k);
 273         int rw = flags & WRITE;
 274
 275         if (alloc_v4_u64s(a.v) > bkey_val_u64s(k.k)) {
 276                 prt_printf(err, "bad val size (%u > %lu)",
 277                        alloc_v4_u64s(a.v), bkey_val_u64s(k.k));
 278                 return -BCH_ERR_invalid_bkey;
 279         }
 280
 281         if (!BCH_ALLOC_V4_BACKPOINTERS_START(a.v) &&
 282             BCH_ALLOC_V4_NR_BACKPOINTERS(a.v)) {
 283                 prt_printf(err, "invalid backpointers_start");
 284                 return -BCH_ERR_invalid_bkey;
 285         }
 286
 287         if (rw == WRITE &&
 288             !(flags & BKEY_INVALID_JOURNAL) &&
 289             test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags)) {
 290                 unsigned i, bp_len = 0;
 291
 292                 for (i = 0; i < BCH_ALLOC_V4_NR_BACKPOINTERS(a.v); i++)
 293                         bp_len += alloc_v4_backpointers_c(a.v)[i].bucket_len;
 294
 295                 if (bp_len > a.v->dirty_sectors) {
 296                         prt_printf(err, "too many backpointers");
 297                         return -BCH_ERR_invalid_bkey;
 298                 }
 299         }
 300
 301         if (rw == WRITE) {
 302                 if (alloc_data_type(*a.v, a.v->data_type) != a.v->data_type) {
 303                         prt_printf(err, "invalid data type (got %u should be %u)",
 304                                a.v->data_type, alloc_data_type(*a.v, a.v->data_type));
 305                         return -BCH_ERR_invalid_bkey;
 306                 }
 307
 308                 switch (a.v->data_type) {
 309                 case BCH_DATA_free:
 310                 case BCH_DATA_need_gc_gens:
 311                 case BCH_DATA_need_discard:
 312                         if (a.v->dirty_sectors ||
 313                             a.v->cached_sectors ||
 314                             a.v->stripe) {
 315                                 prt_printf(err, "empty data type free but have data");
 316                                 return -BCH_ERR_invalid_bkey;
 317                         }
 318                         break;
 319                 case BCH_DATA_sb:
 320                 case BCH_DATA_journal:
 321                 case BCH_DATA_btree:
 322                 case BCH_DATA_user:
 323                 case BCH_DATA_parity:
 324                         if (!a.v->dirty_sectors) {
 325                                 prt_printf(err, "data_type %s but dirty_sectors==0",
 326                                        bch2_data_types[a.v->data_type]);
 327                                 return -BCH_ERR_invalid_bkey;
 328                         }
 329                         break;
 330                 case BCH_DATA_cached:
 331                         if (!a.v->cached_sectors ||
 332                             a.v->dirty_sectors ||
 333                             a.v->stripe) {
 334                                 prt_printf(err, "data type inconsistency");
 335                                 return -BCH_ERR_invalid_bkey;
 336                         }
 337
 338                         if (!a.v->io_time[READ] &&
 339                             test_bit(BCH_FS_CHECK_ALLOC_TO_LRU_REFS_DONE, &c->flags)) {
 340                                 prt_printf(err, "cached bucket with read_time == 0");
 341                                 return -BCH_ERR_invalid_bkey;
 342                         }
 343                         break;
 344                 case BCH_DATA_stripe:
 345                         if (!a.v->stripe) {
 346                                 prt_printf(err, "data_type %s but stripe==0",
 347                                        bch2_data_types[a.v->data_type]);
 348                                 return -BCH_ERR_invalid_bkey;
 349                         }
 350                         break;
 351                 }
 352         }
 353
 354         return 0;
 355 }
 356
 357 static inline u64 swab40(u64 x)
 358 {
 359         return (((x & 0x00000000ffULL) << 32)|
 360                 ((x & 0x000000ff00ULL) << 16)|
 361                 ((x & 0x0000ff0000ULL) >>  0)|
 362                 ((x & 0x00ff000000ULL) >> 16)|
 363                 ((x & 0xff00000000ULL) >> 32));
 364 }
 365
 366 void bch2_alloc_v4_swab(struct bkey_s k)
 367 {
 368         struct bch_alloc_v4 *a = bkey_s_to_alloc_v4(k).v;
 369         struct bch_backpointer *bp, *bps;
 370
 371         a->journal_seq          = swab64(a->journal_seq);
 372         a->flags                = swab32(a->flags);
 373         a->dirty_sectors        = swab32(a->dirty_sectors);
 374         a->cached_sectors       = swab32(a->cached_sectors);
 375         a->io_time[0]           = swab64(a->io_time[0]);
 376         a->io_time[1]           = swab64(a->io_time[1]);
 377         a->stripe               = swab32(a->stripe);
 378         a->nr_external_backpointers = swab32(a->nr_external_backpointers);
 379
 380         bps = alloc_v4_backpointers(a);
 381         for (bp = bps; bp < bps + BCH_ALLOC_V4_NR_BACKPOINTERS(a); bp++) {
 382                 bp->bucket_offset       = swab40(bp->bucket_offset);
 383                 bp->bucket_len          = swab32(bp->bucket_len);
 384                 bch2_bpos_swab(&bp->pos);
 385         }
 386 }
 387
 388 void bch2_alloc_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
 389 {
 390         struct bch_alloc_v4 _a;
 391         const struct bch_alloc_v4 *a = bch2_alloc_to_v4(k, &_a);
 392         unsigned i;
 393
 394         prt_newline(out);
 395         printbuf_indent_add(out, 2);
 396
 397         prt_printf(out, "gen %u oldest_gen %u data_type %s",
 398                a->gen, a->oldest_gen,
 399                a->data_type < BCH_DATA_NR
 400                ? bch2_data_types[a->data_type]
 401                : "(invalid data type)");
 402         prt_newline(out);
 403         prt_printf(out, "journal_seq       %llu",       a->journal_seq);
 404         prt_newline(out);
 405         prt_printf(out, "need_discard      %llu",       BCH_ALLOC_V4_NEED_DISCARD(a));
 406         prt_newline(out);
 407         prt_printf(out, "need_inc_gen      %llu",       BCH_ALLOC_V4_NEED_INC_GEN(a));
 408         prt_newline(out);
 409         prt_printf(out, "dirty_sectors     %u", a->dirty_sectors);
 410         prt_newline(out);
 411         prt_printf(out, "cached_sectors    %u", a->cached_sectors);
 412         prt_newline(out);
 413         prt_printf(out, "stripe            %u", a->stripe);
 414         prt_newline(out);
 415         prt_printf(out, "stripe_redundancy %u", a->stripe_redundancy);
 416         prt_newline(out);
 417         prt_printf(out, "io_time[READ]     %llu",       a->io_time[READ]);
 418         prt_newline(out);
 419         prt_printf(out, "io_time[WRITE]    %llu",       a->io_time[WRITE]);
 420         prt_newline(out);
 421         prt_printf(out, "fragmentation     %llu",       a->fragmentation_lru);
 422         prt_newline(out);
 423         prt_printf(out, "bp_start          %llu", BCH_ALLOC_V4_BACKPOINTERS_START(a));
 424         prt_newline(out);
 425
 426         if (BCH_ALLOC_V4_NR_BACKPOINTERS(a)) {
 427                 struct bkey_s_c_alloc_v4 a_raw = bkey_s_c_to_alloc_v4(k);
 428                 const struct bch_backpointer *bps = alloc_v4_backpointers_c(a_raw.v);
 429
 430                 prt_printf(out, "backpointers:     %llu", BCH_ALLOC_V4_NR_BACKPOINTERS(a_raw.v));
 431                 printbuf_indent_add(out, 2);
 432
 433                 for (i = 0; i < BCH_ALLOC_V4_NR_BACKPOINTERS(a_raw.v); i++) {
 434                         prt_newline(out);
 435                         bch2_backpointer_to_text(out, &bps[i]);
 436                 }
 437
 438                 printbuf_indent_sub(out, 2);
 439         }
 440
 441         printbuf_indent_sub(out, 2);
 442 }
 443
 444 void __bch2_alloc_to_v4(struct bkey_s_c k, struct bch_alloc_v4 *out)
 445 {
 446         if (k.k->type == KEY_TYPE_alloc_v4) {
 447                 void *src, *dst;
 448
 449                 *out = *bkey_s_c_to_alloc_v4(k).v;
 450
 451                 src = alloc_v4_backpointers(out);
 452                 SET_BCH_ALLOC_V4_BACKPOINTERS_START(out, BCH_ALLOC_V4_U64s);
 453                 dst = alloc_v4_backpointers(out);
 454
 455                 if (src < dst)
 456                         memset(src, 0, dst - src);
 457
 458                 SET_BCH_ALLOC_V4_NR_BACKPOINTERS(out, 0);
 459         } else {
 460                 struct bkey_alloc_unpacked u = bch2_alloc_unpack(k);
 461
 462                 *out = (struct bch_alloc_v4) {
 463                         .journal_seq            = u.journal_seq,
 464                         .flags                  = u.need_discard,
 465                         .gen                    = u.gen,
 466                         .oldest_gen             = u.oldest_gen,
 467                         .data_type              = u.data_type,
 468                         .stripe_redundancy      = u.stripe_redundancy,
 469                         .dirty_sectors          = u.dirty_sectors,
 470                         .cached_sectors         = u.cached_sectors,
 471                         .io_time[READ]          = u.read_time,
 472                         .io_time[WRITE]         = u.write_time,
 473                         .stripe                 = u.stripe,
 474                 };
 475
 476                 SET_BCH_ALLOC_V4_BACKPOINTERS_START(out, BCH_ALLOC_V4_U64s);
 477         }
 478 }
 479
 480 static noinline struct bkey_i_alloc_v4 *
 481 __bch2_alloc_to_v4_mut(struct btree_trans *trans, struct bkey_s_c k)
 482 {
 483         struct bkey_i_alloc_v4 *ret;
 484
 485         ret = bch2_trans_kmalloc(trans, max(bkey_bytes(k.k), sizeof(struct bkey_i_alloc_v4)));
 486         if (IS_ERR(ret))
 487                 return ret;
 488
 489         if (k.k->type == KEY_TYPE_alloc_v4) {
 490                 void *src, *dst;
 491
 492                 bkey_reassemble(&ret->k_i, k);
 493
 494                 src = alloc_v4_backpointers(&ret->v);
 495                 SET_BCH_ALLOC_V4_BACKPOINTERS_START(&ret->v, BCH_ALLOC_V4_U64s);
 496                 dst = alloc_v4_backpointers(&ret->v);
 497
 498                 if (src < dst)
 499                         memset(src, 0, dst - src);
 500
 501                 SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&ret->v, 0);
 502                 set_alloc_v4_u64s(ret);
 503         } else {
 504                 bkey_alloc_v4_init(&ret->k_i);
 505                 ret->k.p = k.k->p;
 506                 bch2_alloc_to_v4(k, &ret->v);
 507         }
 508         return ret;
 509 }
 510
 511 static inline struct bkey_i_alloc_v4 *bch2_alloc_to_v4_mut_inlined(struct btree_trans *trans, struct bkey_s_c k)
 512 {
 513         struct bkey_s_c_alloc_v4 a;
 514
 515         if (likely(k.k->type == KEY_TYPE_alloc_v4) &&
 516             ((a = bkey_s_c_to_alloc_v4(k), true) &&
 517              BCH_ALLOC_V4_NR_BACKPOINTERS(a.v) == 0))
 518                 return bch2_bkey_make_mut_noupdate_typed(trans, k, alloc_v4);
 519
 520         return __bch2_alloc_to_v4_mut(trans, k);
 521 }
 522
 523 struct bkey_i_alloc_v4 *bch2_alloc_to_v4_mut(struct btree_trans *trans, struct bkey_s_c k)
 524 {
 525         return bch2_alloc_to_v4_mut_inlined(trans, k);
 526 }
 527
 528 struct bkey_i_alloc_v4 *
 529 bch2_trans_start_alloc_update(struct btree_trans *trans, struct btree_iter *iter,
 530                               struct bpos pos)
 531 {
 532         struct bkey_s_c k;
 533         struct bkey_i_alloc_v4 *a;
 534         int ret;
 535
 536         k = bch2_bkey_get_iter(trans, iter, BTREE_ID_alloc, pos,
 537                              BTREE_ITER_WITH_UPDATES|
 538                              BTREE_ITER_CACHED|
 539                              BTREE_ITER_INTENT);
 540         ret = bkey_err(k);
 541         if (unlikely(ret))
 542                 return ERR_PTR(ret);
 543
 544         a = bch2_alloc_to_v4_mut_inlined(trans, k);
 545         ret = PTR_ERR_OR_ZERO(a);
 546         if (unlikely(ret))
 547                 goto err;
 548         return a;
 549 err:
 550         bch2_trans_iter_exit(trans, iter);
 551         return ERR_PTR(ret);
 552 }
 553
 554 int bch2_alloc_read(struct bch_fs *c)
 555 {
 556         struct btree_trans trans;
 557         struct btree_iter iter;
 558         struct bkey_s_c k;
 559         struct bch_alloc_v4 a;
 560         struct bch_dev *ca;
 561         int ret;
 562
 563         bch2_trans_init(&trans, c, 0, 0);
 564
 565         for_each_btree_key(&trans, iter, BTREE_ID_alloc, POS_MIN,
 566                            BTREE_ITER_PREFETCH, k, ret) {
 567                 /*
 568                  * Not a fsck error because this is checked/repaired by
 569                  * bch2_check_alloc_key() which runs later:
 570                  */
 571                 if (!bch2_dev_bucket_exists(c, k.k->p))
 572                         continue;
 573
 574                 ca = bch_dev_bkey_exists(c, k.k->p.inode);
 575
 576                 *bucket_gen(ca, k.k->p.offset) = bch2_alloc_to_v4(k, &a)->gen;
 577         }
 578         bch2_trans_iter_exit(&trans, &iter);
 579
 580         bch2_trans_exit(&trans);
 581
 582         if (ret)
 583                 bch_err_fn(c, ret);
 584
 585         return ret;
 586 }
 587
 588 static struct bpos alloc_gens_pos(struct bpos pos, unsigned *offset)
 589 {
 590         *offset = pos.offset & KEY_TYPE_BUCKET_GENS_MASK;
 591
 592         pos.offset >>= KEY_TYPE_BUCKET_GENS_BITS;
 593         return pos;
 594 }
 595
 596 static struct bpos bucket_gens_pos_to_alloc(struct bpos pos, unsigned offset)
 597 {
 598         pos.offset <<= KEY_TYPE_BUCKET_GENS_BITS;
 599         pos.offset += offset;
 600         return pos;
 601 }
 602
 603 static unsigned alloc_gen(struct bkey_s_c k, unsigned offset)
 604 {
 605         return k.k->type == KEY_TYPE_bucket_gens
 606                 ? bkey_s_c_to_bucket_gens(k).v->gens[offset]
 607                 : 0;
 608 }
 609
 610 int bch2_bucket_gens_invalid(const struct bch_fs *c, struct bkey_s_c k,
 611                              enum bkey_invalid_flags flags,
 612                              struct printbuf *err)
 613 {
 614         if (bkey_val_bytes(k.k) != sizeof(struct bch_bucket_gens)) {
 615                 prt_printf(err, "bad val size (%lu != %zu)",
 616                        bkey_val_bytes(k.k), sizeof(struct bch_bucket_gens));
 617                 return -BCH_ERR_invalid_bkey;
 618         }
 619
 620         return 0;
 621 }
 622
 623 void bch2_bucket_gens_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
 624 {
 625         struct bkey_s_c_bucket_gens g = bkey_s_c_to_bucket_gens(k);
 626         unsigned i;
 627
 628         for (i = 0; i < ARRAY_SIZE(g.v->gens); i++) {
 629                 if (i)
 630                         prt_char(out, ' ');
 631                 prt_printf(out, "%u", g.v->gens[i]);
 632         }
 633 }
 634
 635 int bch2_bucket_gens_init(struct bch_fs *c)
 636 {
 637         struct btree_trans trans;
 638         struct btree_iter iter;
 639         struct bkey_s_c k;
 640         struct bch_alloc_v4 a;
 641         struct bkey_i_bucket_gens g;
 642         bool have_bucket_gens_key = false;
 643         unsigned offset;
 644         struct bpos pos;
 645         u8 gen;
 646         int ret;
 647
 648         bch2_trans_init(&trans, c, 0, 0);
 649
 650         for_each_btree_key(&trans, iter, BTREE_ID_alloc, POS_MIN,
 651                            BTREE_ITER_PREFETCH, k, ret) {
 652                 /*
 653                  * Not a fsck error because this is checked/repaired by
 654                  * bch2_check_alloc_key() which runs later:
 655                  */
 656                 if (!bch2_dev_bucket_exists(c, k.k->p))
 657                         continue;
 658
 659                 gen = bch2_alloc_to_v4(k, &a)->gen;
 660                 pos = alloc_gens_pos(iter.pos, &offset);
 661
 662                 if (have_bucket_gens_key && bkey_cmp(iter.pos, pos)) {
 663                         ret = commit_do(&trans, NULL, NULL,
 664                                         BTREE_INSERT_NOFAIL|
 665                                         BTREE_INSERT_LAZY_RW,
 666                                 __bch2_btree_insert(&trans, BTREE_ID_bucket_gens, &g.k_i, 0));
 667                         if (ret)
 668                                 break;
 669                         have_bucket_gens_key = false;
 670                 }
 671
 672                 if (!have_bucket_gens_key) {
 673                         bkey_bucket_gens_init(&g.k_i);
 674                         g.k.p = pos;
 675                         have_bucket_gens_key = true;
 676                 }
 677
 678                 g.v.gens[offset] = gen;
 679         }
 680         bch2_trans_iter_exit(&trans, &iter);
 681
 682         if (have_bucket_gens_key && !ret)
 683                 ret = commit_do(&trans, NULL, NULL,
 684                                 BTREE_INSERT_NOFAIL|
 685                                 BTREE_INSERT_LAZY_RW,
 686                         __bch2_btree_insert(&trans, BTREE_ID_bucket_gens, &g.k_i, 0));
 687
 688         bch2_trans_exit(&trans);
 689
 690         if (ret)
 691                 bch_err_fn(c, ret);
 692         return ret;
 693 }
 694
 695 int bch2_bucket_gens_read(struct bch_fs *c)
 696 {
 697         struct btree_trans trans;
 698         struct btree_iter iter;
 699         struct bkey_s_c k;
 700         const struct bch_bucket_gens *g;
 701         struct bch_dev *ca;
 702         u64 b;
 703         int ret;
 704
 705         bch2_trans_init(&trans, c, 0, 0);
 706
 707         for_each_btree_key(&trans, iter, BTREE_ID_bucket_gens, POS_MIN,
 708                            BTREE_ITER_PREFETCH, k, ret) {
 709                 u64 start = bucket_gens_pos_to_alloc(k.k->p, 0).offset;
 710                 u64 end = bucket_gens_pos_to_alloc(bpos_nosnap_successor(k.k->p), 0).offset;
 711
 712                 if (k.k->type != KEY_TYPE_bucket_gens)
 713                         continue;
 714
 715                 g = bkey_s_c_to_bucket_gens(k).v;
 716
 717                 /*
 718                  * Not a fsck error because this is checked/repaired by
 719                  * bch2_check_alloc_key() which runs later:
 720                  */
 721                 if (!bch2_dev_exists2(c, k.k->p.inode))
 722                         continue;
 723
 724                 ca = bch_dev_bkey_exists(c, k.k->p.inode);
 725
 726                 for (b = max_t(u64, ca->mi.first_bucket, start);
 727                      b < min_t(u64, ca->mi.nbuckets, end);
 728                      b++)
 729                         *bucket_gen(ca, b) = g->gens[b & KEY_TYPE_BUCKET_GENS_MASK];
 730         }
 731         bch2_trans_iter_exit(&trans, &iter);
 732
 733         bch2_trans_exit(&trans);
 734
 735         if (ret)
 736                 bch_err_fn(c, ret);
 737
 738         return ret;
 739 }
 740
 741 /* Free space/discard btree: */
 742
 743 static int bch2_bucket_do_index(struct btree_trans *trans,
 744                                 struct bkey_s_c alloc_k,
 745                                 const struct bch_alloc_v4 *a,
 746                                 bool set)
 747 {
 748         struct bch_fs *c = trans->c;
 749         struct bch_dev *ca = bch_dev_bkey_exists(c, alloc_k.k->p.inode);
 750         struct btree_iter iter;
 751         struct bkey_s_c old;
 752         struct bkey_i *k;
 753         enum btree_id btree;
 754         enum bch_bkey_type old_type = !set ? KEY_TYPE_set : KEY_TYPE_deleted;
 755         enum bch_bkey_type new_type =  set ? KEY_TYPE_set : KEY_TYPE_deleted;
 756         struct printbuf buf = PRINTBUF;
 757         int ret;
 758
 759         if (a->data_type != BCH_DATA_free &&
 760             a->data_type != BCH_DATA_need_discard)
 761                 return 0;
 762
 763         k = bch2_trans_kmalloc_nomemzero(trans, sizeof(*k));
 764         if (IS_ERR(k))
 765                 return PTR_ERR(k);
 766
 767         bkey_init(&k->k);
 768         k->k.type = new_type;
 769
 770         switch (a->data_type) {
 771         case BCH_DATA_free:
 772                 btree = BTREE_ID_freespace;
 773                 k->k.p = alloc_freespace_pos(alloc_k.k->p, *a);
 774                 bch2_key_resize(&k->k, 1);
 775                 break;
 776         case BCH_DATA_need_discard:
 777                 btree = BTREE_ID_need_discard;
 778                 k->k.p = alloc_k.k->p;
 779                 break;
 780         default:
 781                 return 0;
 782         }
 783
 784         old = bch2_bkey_get_iter(trans, &iter, btree,
 785                              bkey_start_pos(&k->k),
 786                              BTREE_ITER_INTENT);
 787         ret = bkey_err(old);
 788         if (ret)
 789                 return ret;
 790
 791         if (ca->mi.freespace_initialized &&
 792             test_bit(BCH_FS_CHECK_ALLOC_DONE, &c->flags) &&
 793             bch2_trans_inconsistent_on(old.k->type != old_type, trans,
 794                         "incorrect key when %s %s:%llu:%llu:0 (got %s should be %s)\n"
 795                         "  for %s",
 796                         set ? "setting" : "clearing",
 797                         bch2_btree_ids[btree],
 798                         iter.pos.inode,
 799                         iter.pos.offset,
 800                         bch2_bkey_types[old.k->type],
 801                         bch2_bkey_types[old_type],
 802                         (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) {
 803                 ret = -EIO;
 804                 goto err;
 805         }
 806
 807         ret = bch2_trans_update(trans, &iter, k, 0);
 808 err:
 809         bch2_trans_iter_exit(trans, &iter);
 810         printbuf_exit(&buf);
 811         return ret;
 812 }
 813
 814 static noinline int bch2_bucket_gen_update(struct btree_trans *trans,
 815                                            struct bpos bucket, u8 gen)
 816 {
 817         struct btree_iter iter;
 818         unsigned offset;
 819         struct bpos pos = alloc_gens_pos(bucket, &offset);
 820         struct bkey_i_bucket_gens *g;
 821         struct bkey_s_c k;
 822         int ret;
 823
 824         g = bch2_trans_kmalloc(trans, sizeof(*g));
 825         ret = PTR_ERR_OR_ZERO(g);
 826         if (ret)
 827                 return ret;
 828
 829         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_bucket_gens, pos,
 830                                BTREE_ITER_INTENT|
 831                                BTREE_ITER_WITH_UPDATES);
 832         ret = bkey_err(k);
 833         if (ret)
 834                 return ret;
 835
 836         if (k.k->type != KEY_TYPE_bucket_gens) {
 837                 bkey_bucket_gens_init(&g->k_i);
 838                 g->k.p = iter.pos;
 839         } else {
 840                 bkey_reassemble(&g->k_i, k);
 841         }
 842
 843         g->v.gens[offset] = gen;
 844
 845         ret = bch2_trans_update(trans, &iter, &g->k_i, 0);
 846         bch2_trans_iter_exit(trans, &iter);
 847         return ret;
 848 }
 849
 850 int bch2_trans_mark_alloc(struct btree_trans *trans,
 851                           enum btree_id btree_id, unsigned level,
 852                           struct bkey_s_c old, struct bkey_i *new,
 853                           unsigned flags)
 854 {
 855         struct bch_fs *c = trans->c;
 856         struct bch_alloc_v4 old_a_convert, *new_a;
 857         const struct bch_alloc_v4 *old_a;
 858         u64 old_lru, new_lru;
 859         int ret = 0;
 860
 861         /*
 862          * Deletion only happens in the device removal path, with
 863          * BTREE_TRIGGER_NORUN:
 864          */
 865         BUG_ON(new->k.type != KEY_TYPE_alloc_v4);
 866
 867         old_a = bch2_alloc_to_v4(old, &old_a_convert);
 868         new_a = &bkey_i_to_alloc_v4(new)->v;
 869
 870         new_a->data_type = alloc_data_type(*new_a, new_a->data_type);
 871
 872         if (new_a->dirty_sectors > old_a->dirty_sectors ||
 873             new_a->cached_sectors > old_a->cached_sectors) {
 874                 new_a->io_time[READ] = max_t(u64, 1, atomic64_read(&c->io_clock[READ].now));
 875                 new_a->io_time[WRITE]= max_t(u64, 1, atomic64_read(&c->io_clock[WRITE].now));
 876                 SET_BCH_ALLOC_V4_NEED_INC_GEN(new_a, true);
 877                 SET_BCH_ALLOC_V4_NEED_DISCARD(new_a, true);
 878         }
 879
 880         if (data_type_is_empty(new_a->data_type) &&
 881             BCH_ALLOC_V4_NEED_INC_GEN(new_a) &&
 882             !bch2_bucket_is_open_safe(c, new->k.p.inode, new->k.p.offset)) {
 883                 new_a->gen++;
 884                 SET_BCH_ALLOC_V4_NEED_INC_GEN(new_a, false);
 885         }
 886
 887         if (old_a->data_type != new_a->data_type ||
 888             (new_a->data_type == BCH_DATA_free &&
 889              alloc_freespace_genbits(*old_a) != alloc_freespace_genbits(*new_a))) {
 890                 ret =   bch2_bucket_do_index(trans, old, old_a, false) ?:
 891                         bch2_bucket_do_index(trans, bkey_i_to_s_c(new), new_a, true);
 892                 if (ret)
 893                         return ret;
 894         }
 895
 896         if (new_a->data_type == BCH_DATA_cached &&
 897             !new_a->io_time[READ])
 898                 new_a->io_time[READ] = max_t(u64, 1, atomic64_read(&c->io_clock[READ].now));
 899
 900         old_lru = alloc_lru_idx_read(*old_a);
 901         new_lru = alloc_lru_idx_read(*new_a);
 902
 903         if (old_lru != new_lru) {
 904                 ret = bch2_lru_change(trans, new->k.p.inode,
 905                                       bucket_to_u64(new->k.p),
 906                                       old_lru, new_lru);
 907                 if (ret)
 908                         return ret;
 909         }
 910
 911         new_a->fragmentation_lru = alloc_lru_idx_fragmentation(*new_a,
 912                                         bch_dev_bkey_exists(c, new->k.p.inode));
 913
 914         if (old_a->fragmentation_lru != new_a->fragmentation_lru) {
 915                 ret = bch2_lru_change(trans,
 916                                 BCH_LRU_FRAGMENTATION_START,
 917                                 bucket_to_u64(new->k.p),
 918                                 old_a->fragmentation_lru, new_a->fragmentation_lru);
 919                 if (ret)
 920                         return ret;
 921         }
 922
 923         if (old_a->gen != new_a->gen) {
 924                 ret = bch2_bucket_gen_update(trans, new->k.p, new_a->gen);
 925                 if (ret)
 926                         return ret;
 927         }
 928
 929         return 0;
 930 }
 931
 932 /*
 933  * This synthesizes deleted extents for holes, similar to BTREE_ITER_SLOTS for
 934  * extents style btrees, but works on non-extents btrees:
 935  */
 936 static struct bkey_s_c bch2_get_key_or_hole(struct btree_iter *iter, struct bpos end, struct bkey *hole)
 937 {
 938         struct bkey_s_c k = bch2_btree_iter_peek_slot(iter);
 939
 940         if (bkey_err(k))
 941                 return k;
 942
 943         if (k.k->type) {
 944                 return k;
 945         } else {
 946                 struct btree_iter iter2;
 947                 struct bpos next;
 948
 949                 bch2_trans_copy_iter(&iter2, iter);
 950
 951                 if (!bpos_eq(iter->path->l[0].b->key.k.p, SPOS_MAX))
 952                         end = bkey_min(end, bpos_nosnap_successor(iter->path->l[0].b->key.k.p));
 953
 954                 end = bkey_min(end, POS(iter->pos.inode, iter->pos.offset + U32_MAX - 1));
 955
 956                 /*
 957                  * btree node min/max is a closed interval, upto takes a half
 958                  * open interval:
 959                  */
 960                 k = bch2_btree_iter_peek_upto(&iter2, end);
 961                 next = iter2.pos;
 962                 bch2_trans_iter_exit(iter->trans, &iter2);
 963
 964                 BUG_ON(next.offset >= iter->pos.offset + U32_MAX);
 965
 966                 if (bkey_err(k))
 967                         return k;
 968
 969                 bkey_init(hole);
 970                 hole->p = iter->pos;
 971
 972                 bch2_key_resize(hole, next.offset - iter->pos.offset);
 973                 return (struct bkey_s_c) { hole, NULL };
 974         }
 975 }
 976
 977 static bool next_bucket(struct bch_fs *c, struct bpos *bucket)
 978 {
 979         struct bch_dev *ca;
 980         unsigned iter;
 981
 982         if (bch2_dev_bucket_exists(c, *bucket))
 983                 return true;
 984
 985         if (bch2_dev_exists2(c, bucket->inode)) {
 986                 ca = bch_dev_bkey_exists(c, bucket->inode);
 987
 988                 if (bucket->offset < ca->mi.first_bucket) {
 989                         bucket->offset = ca->mi.first_bucket;
 990                         return true;
 991                 }
 992
 993                 bucket->inode++;
 994                 bucket->offset = 0;
 995         }
 996
 997         rcu_read_lock();
 998         iter = bucket->inode;
 999         ca = __bch2_next_dev(c, &iter, NULL);
1000         if (ca)
1001                 *bucket = POS(ca->dev_idx, ca->mi.first_bucket);
1002         rcu_read_unlock();
1003
1004         return ca != NULL;
1005 }
1006
1007 static struct bkey_s_c bch2_get_key_or_real_bucket_hole(struct btree_iter *iter, struct bkey *hole)
1008 {
1009         struct bch_fs *c = iter->trans->c;
1010         struct bkey_s_c k;
1011 again:
1012         k = bch2_get_key_or_hole(iter, POS_MAX, hole);
1013         if (bkey_err(k))
1014                 return k;
1015
1016         if (!k.k->type) {
1017                 struct bpos bucket = bkey_start_pos(k.k);
1018
1019                 if (!bch2_dev_bucket_exists(c, bucket)) {
1020                         if (!next_bucket(c, &bucket))
1021                                 return bkey_s_c_null;
1022
1023                         bch2_btree_iter_set_pos(iter, bucket);
1024                         goto again;
1025                 }
1026
1027                 if (!bch2_dev_bucket_exists(c, k.k->p)) {
1028                         struct bch_dev *ca = bch_dev_bkey_exists(c, bucket.inode);
1029
1030                         bch2_key_resize(hole, ca->mi.nbuckets - bucket.offset);
1031                 }
1032         }
1033
1034         return k;
1035 }
1036
1037 static noinline_for_stack
1038 int bch2_check_alloc_key(struct btree_trans *trans,
1039                          struct bkey_s_c alloc_k,
1040                          struct btree_iter *alloc_iter,
1041                          struct btree_iter *discard_iter,
1042                          struct btree_iter *freespace_iter,
1043                          struct btree_iter *bucket_gens_iter)
1044 {
1045         struct bch_fs *c = trans->c;
1046         struct bch_dev *ca;
1047         struct bch_alloc_v4 a_convert;
1048         const struct bch_alloc_v4 *a;
1049         unsigned discard_key_type, freespace_key_type;
1050         unsigned gens_offset;
1051         struct bkey_s_c k;
1052         struct printbuf buf = PRINTBUF;
1053         int ret;
1054
1055         if (fsck_err_on(!bch2_dev_bucket_exists(c, alloc_k.k->p), c,
1056                         "alloc key for invalid device:bucket %llu:%llu",
1057                         alloc_k.k->p.inode, alloc_k.k->p.offset))
1058                 return bch2_btree_delete_at(trans, alloc_iter, 0);
1059
1060         ca = bch_dev_bkey_exists(c, alloc_k.k->p.inode);
1061         if (!ca->mi.freespace_initialized)
1062                 return 0;
1063
1064         a = bch2_alloc_to_v4(alloc_k, &a_convert);
1065
1066         discard_key_type = a->data_type == BCH_DATA_need_discard ? KEY_TYPE_set : 0;
1067         bch2_btree_iter_set_pos(discard_iter, alloc_k.k->p);
1068         k = bch2_btree_iter_peek_slot(discard_iter);
1069         ret = bkey_err(k);
1070         if (ret)
1071                 goto err;
1072
1073         if (k.k->type != discard_key_type &&
1074             (c->opts.reconstruct_alloc ||
1075              fsck_err(c, "incorrect key in need_discard btree (got %s should be %s)\n"
1076                       "  %s",
1077                       bch2_bkey_types[k.k->type],
1078                       bch2_bkey_types[discard_key_type],
1079                       (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf)))) {
1080                 struct bkey_i *update =
1081                         bch2_trans_kmalloc(trans, sizeof(*update));
1082
1083                 ret = PTR_ERR_OR_ZERO(update);
1084                 if (ret)
1085                         goto err;
1086
1087                 bkey_init(&update->k);
1088                 update->k.type  = discard_key_type;
1089                 update->k.p     = discard_iter->pos;
1090
1091                 ret = bch2_trans_update(trans, discard_iter, update, 0);
1092                 if (ret)
1093                         goto err;
1094         }
1095
1096         freespace_key_type = a->data_type == BCH_DATA_free ? KEY_TYPE_set : 0;
1097         bch2_btree_iter_set_pos(freespace_iter, alloc_freespace_pos(alloc_k.k->p, *a));
1098         k = bch2_btree_iter_peek_slot(freespace_iter);
1099         ret = bkey_err(k);
1100         if (ret)
1101                 goto err;
1102
1103         if (k.k->type != freespace_key_type &&
1104             (c->opts.reconstruct_alloc ||
1105              fsck_err(c, "incorrect key in freespace btree (got %s should be %s)\n"
1106                       "  %s",
1107                       bch2_bkey_types[k.k->type],
1108                       bch2_bkey_types[freespace_key_type],
1109                       (printbuf_reset(&buf),
1110                        bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf)))) {
1111                 struct bkey_i *update =
1112                         bch2_trans_kmalloc(trans, sizeof(*update));
1113
1114                 ret = PTR_ERR_OR_ZERO(update);
1115                 if (ret)
1116                         goto err;
1117
1118                 bkey_init(&update->k);
1119                 update->k.type  = freespace_key_type;
1120                 update->k.p     = freespace_iter->pos;
1121                 bch2_key_resize(&update->k, 1);
1122
1123                 ret = bch2_trans_update(trans, freespace_iter, update, 0);
1124                 if (ret)
1125                         goto err;
1126         }
1127
1128         bch2_btree_iter_set_pos(bucket_gens_iter, alloc_gens_pos(alloc_k.k->p, &gens_offset));
1129         k = bch2_btree_iter_peek_slot(bucket_gens_iter);
1130         ret = bkey_err(k);
1131         if (ret)
1132                 goto err;
1133
1134         if (a->gen != alloc_gen(k, gens_offset) &&
1135             (c->opts.reconstruct_alloc ||
1136              fsck_err(c, "incorrect gen in bucket_gens btree (got %u should be %u)\n"
1137                       "  %s",
1138                       alloc_gen(k, gens_offset), a->gen,
1139                       (printbuf_reset(&buf),
1140                        bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf)))) {
1141                 struct bkey_i_bucket_gens *g =
1142                         bch2_trans_kmalloc(trans, sizeof(*g));
1143
1144                 ret = PTR_ERR_OR_ZERO(g);
1145                 if (ret)
1146                         goto err;
1147
1148                 if (k.k->type == KEY_TYPE_bucket_gens) {
1149                         bkey_reassemble(&g->k_i, k);
1150                 } else {
1151                         bkey_bucket_gens_init(&g->k_i);
1152                         g->k.p = alloc_gens_pos(alloc_k.k->p, &gens_offset);
1153                 }
1154
1155                 g->v.gens[gens_offset] = a->gen;
1156
1157                 ret = bch2_trans_update(trans, bucket_gens_iter, &g->k_i, 0);
1158                 if (ret)
1159                         goto err;
1160         }
1161 err:
1162 fsck_err:
1163         printbuf_exit(&buf);
1164         return ret;
1165 }
1166
1167 static noinline_for_stack
1168 int bch2_check_alloc_hole_freespace(struct btree_trans *trans,
1169                                     struct bpos start,
1170                                     struct bpos *end,
1171                                     struct btree_iter *freespace_iter)
1172 {
1173         struct bch_fs *c = trans->c;
1174         struct bch_dev *ca;
1175         struct bkey_s_c k;
1176         struct printbuf buf = PRINTBUF;
1177         int ret;
1178
1179         ca = bch_dev_bkey_exists(c, start.inode);
1180         if (!ca->mi.freespace_initialized)
1181                 return 0;
1182
1183         bch2_btree_iter_set_pos(freespace_iter, start);
1184
1185         k = bch2_btree_iter_peek_slot(freespace_iter);
1186         ret = bkey_err(k);
1187         if (ret)
1188                 goto err;
1189
1190         *end = bkey_min(k.k->p, *end);
1191
1192         if (k.k->type != KEY_TYPE_set &&
1193             (c->opts.reconstruct_alloc ||
1194              fsck_err(c, "hole in alloc btree missing in freespace btree\n"
1195                       "  device %llu buckets %llu-%llu",
1196                       freespace_iter->pos.inode,
1197                       freespace_iter->pos.offset,
1198                       end->offset))) {
1199                 struct bkey_i *update =
1200                         bch2_trans_kmalloc(trans, sizeof(*update));
1201
1202                 ret = PTR_ERR_OR_ZERO(update);
1203                 if (ret)
1204                         goto err;
1205
1206                 bkey_init(&update->k);
1207                 update->k.type  = KEY_TYPE_set;
1208                 update->k.p     = freespace_iter->pos;
1209                 bch2_key_resize(&update->k,
1210                                 min_t(u64, U32_MAX, end->offset -
1211                                       freespace_iter->pos.offset));
1212
1213                 ret = bch2_trans_update(trans, freespace_iter, update, 0);
1214                 if (ret)
1215                         goto err;
1216         }
1217 err:
1218 fsck_err:
1219         printbuf_exit(&buf);
1220         return ret;
1221 }
1222
1223 static noinline_for_stack
1224 int bch2_check_alloc_hole_bucket_gens(struct btree_trans *trans,
1225                                       struct bpos start,
1226                                       struct bpos *end,
1227                                       struct btree_iter *bucket_gens_iter)
1228 {
1229         struct bch_fs *c = trans->c;
1230         struct bkey_s_c k;
1231         struct printbuf buf = PRINTBUF;
1232         unsigned i, gens_offset, gens_end_offset;
1233         int ret;
1234
1235         if (c->sb.version < bcachefs_metadata_version_bucket_gens &&
1236             !c->opts.version_upgrade)
1237                 return 0;
1238
1239         bch2_btree_iter_set_pos(bucket_gens_iter, alloc_gens_pos(start, &gens_offset));
1240
1241         k = bch2_btree_iter_peek_slot(bucket_gens_iter);
1242         ret = bkey_err(k);
1243         if (ret)
1244                 goto err;
1245
1246         if (bkey_cmp(alloc_gens_pos(start, &gens_offset),
1247                      alloc_gens_pos(*end,  &gens_end_offset)))
1248                 gens_end_offset = KEY_TYPE_BUCKET_GENS_NR;
1249
1250         if (k.k->type == KEY_TYPE_bucket_gens) {
1251                 struct bkey_i_bucket_gens g;
1252                 bool need_update = false;
1253
1254                 bkey_reassemble(&g.k_i, k);
1255
1256                 for (i = gens_offset; i < gens_end_offset; i++) {
1257                         if (fsck_err_on(g.v.gens[i], c,
1258                                         "hole in alloc btree at %llu:%llu with nonzero gen in bucket_gens btree (%u)",
1259                                         bucket_gens_pos_to_alloc(k.k->p, i).inode,
1260                                         bucket_gens_pos_to_alloc(k.k->p, i).offset,
1261                                         g.v.gens[i])) {
1262                                 g.v.gens[i] = 0;
1263                                 need_update = true;
1264                         }
1265                 }
1266
1267                 if (need_update) {
1268                         struct bkey_i *k = bch2_trans_kmalloc(trans, sizeof(g));
1269
1270                         ret = PTR_ERR_OR_ZERO(k);
1271                         if (ret)
1272                                 goto err;
1273
1274                         memcpy(k, &g, sizeof(g));
1275
1276                         ret = bch2_trans_update(trans, bucket_gens_iter, k, 0);
1277                         if (ret)
1278                                 goto err;
1279                 }
1280         }
1281
1282         *end = bkey_min(*end, bucket_gens_pos_to_alloc(bpos_nosnap_successor(k.k->p), 0));
1283 err:
1284 fsck_err:
1285         printbuf_exit(&buf);
1286         return ret;
1287 }
1288
1289 static noinline_for_stack int __bch2_check_discard_freespace_key(struct btree_trans *trans,
1290                                               struct btree_iter *iter)
1291 {
1292         struct bch_fs *c = trans->c;
1293         struct btree_iter alloc_iter;
1294         struct bkey_s_c alloc_k;
1295         struct bch_alloc_v4 a_convert;
1296         const struct bch_alloc_v4 *a;
1297         u64 genbits;
1298         struct bpos pos;
1299         enum bch_data_type state = iter->btree_id == BTREE_ID_need_discard
1300                 ? BCH_DATA_need_discard
1301                 : BCH_DATA_free;
1302         struct printbuf buf = PRINTBUF;
1303         int ret;
1304
1305         pos = iter->pos;
1306         pos.offset &= ~(~0ULL << 56);
1307         genbits = iter->pos.offset & (~0ULL << 56);
1308
1309         alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, pos, 0);
1310         ret = bkey_err(alloc_k);
1311         if (ret)
1312                 return ret;
1313
1314         if (fsck_err_on(!bch2_dev_bucket_exists(c, pos), c,
1315                         "entry in %s btree for nonexistant dev:bucket %llu:%llu",
1316                         bch2_btree_ids[iter->btree_id], pos.inode, pos.offset))
1317                 goto delete;
1318
1319         a = bch2_alloc_to_v4(alloc_k, &a_convert);
1320
1321         if (fsck_err_on(a->data_type != state ||
1322                         (state == BCH_DATA_free &&
1323                          genbits != alloc_freespace_genbits(*a)), c,
1324                         "%s\n  incorrectly set at %s:%llu:%llu:0 (free %u, genbits %llu should be %llu)",
1325                         (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf),
1326                         bch2_btree_ids[iter->btree_id],
1327                         iter->pos.inode,
1328                         iter->pos.offset,
1329                         a->data_type == state,
1330                         genbits >> 56, alloc_freespace_genbits(*a) >> 56))
1331                 goto delete;
1332 out:
1333 fsck_err:
1334         set_btree_iter_dontneed(&alloc_iter);
1335         bch2_trans_iter_exit(trans, &alloc_iter);
1336         printbuf_exit(&buf);
1337         return ret;
1338 delete:
1339         ret =   bch2_btree_delete_extent_at(trans, iter,
1340                         iter->btree_id == BTREE_ID_freespace ? 1 : 0, 0) ?:
1341                 bch2_trans_commit(trans, NULL, NULL,
1342                         BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW);
1343         goto out;
1344 }
1345
1346 static int bch2_check_discard_freespace_key(struct btree_trans *trans,
1347                                             struct btree_iter *iter,
1348                                             struct bpos end)
1349 {
1350         if (!btree_node_type_is_extents(iter->btree_id)) {
1351                 return __bch2_check_discard_freespace_key(trans, iter);
1352         } else {
1353                 int ret;
1354
1355                 while (!bkey_eq(iter->pos, end) &&
1356                        !(ret = btree_trans_too_many_iters(trans) ?:
1357                                __bch2_check_discard_freespace_key(trans, iter)))
1358                         bch2_btree_iter_set_pos(iter, bpos_nosnap_successor(iter->pos));
1359
1360                 return ret;
1361         }
1362 }
1363
1364 /*
1365  * We've already checked that generation numbers in the bucket_gens btree are
1366  * valid for buckets that exist; this just checks for keys for nonexistent
1367  * buckets.
1368  */
1369 static noinline_for_stack
1370 int bch2_check_bucket_gens_key(struct btree_trans *trans,
1371                                struct btree_iter *iter,
1372                                struct bkey_s_c k)
1373 {
1374         struct bch_fs *c = trans->c;
1375         struct bkey_i_bucket_gens g;
1376         struct bch_dev *ca;
1377         u64 start = bucket_gens_pos_to_alloc(k.k->p, 0).offset;
1378         u64 end = bucket_gens_pos_to_alloc(bpos_nosnap_successor(k.k->p), 0).offset;
1379         u64 b;
1380         bool need_update = false, dev_exists;
1381         struct printbuf buf = PRINTBUF;
1382         int ret = 0;
1383
1384         BUG_ON(k.k->type != KEY_TYPE_bucket_gens);
1385         bkey_reassemble(&g.k_i, k);
1386
1387         /* if no bch_dev, skip out whether we repair or not */
1388         dev_exists = bch2_dev_exists2(c, k.k->p.inode);
1389         if (!dev_exists) {
1390                 if (fsck_err_on(!dev_exists, c,
1391                                 "bucket_gens key for invalid device:\n  %s",
1392                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1393                         ret = bch2_btree_delete_at(trans, iter, 0);
1394                 }
1395                 goto out;
1396         }
1397
1398         ca = bch_dev_bkey_exists(c, k.k->p.inode);
1399         if (fsck_err_on(end <= ca->mi.first_bucket ||
1400                         start >= ca->mi.nbuckets, c,
1401                         "bucket_gens key for invalid buckets:\n  %s",
1402                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
1403                 ret = bch2_btree_delete_at(trans, iter, 0);
1404                 goto out;
1405         }
1406
1407         for (b = start; b < ca->mi.first_bucket; b++)
1408                 if (fsck_err_on(g.v.gens[b & KEY_TYPE_BUCKET_GENS_MASK], c,
1409                                 "bucket_gens key has nonzero gen for invalid bucket")) {
1410                         g.v.gens[b & KEY_TYPE_BUCKET_GENS_MASK] = 0;
1411                         need_update = true;
1412                 }
1413
1414         for (b = ca->mi.nbuckets; b < end; b++)
1415                 if (fsck_err_on(g.v.gens[b & KEY_TYPE_BUCKET_GENS_MASK], c,
1416                                 "bucket_gens key has nonzero gen for invalid bucket")) {
1417                         g.v.gens[b & KEY_TYPE_BUCKET_GENS_MASK] = 0;
1418                         need_update = true;
1419                 }
1420
1421         if (need_update) {
1422                 struct bkey_i *k;
1423
1424                 k = bch2_trans_kmalloc(trans, sizeof(g));
1425                 ret = PTR_ERR_OR_ZERO(k);
1426                 if (ret)
1427                         goto out;
1428
1429                 memcpy(k, &g, sizeof(g));
1430                 ret = bch2_trans_update(trans, iter, k, 0);
1431         }
1432 out:
1433 fsck_err:
1434         printbuf_exit(&buf);
1435         return ret;
1436 }
1437
1438 int bch2_check_alloc_info(struct bch_fs *c)
1439 {
1440         struct btree_trans trans;
1441         struct btree_iter iter, discard_iter, freespace_iter, bucket_gens_iter;
1442         struct bkey hole;
1443         struct bkey_s_c k;
1444         int ret = 0;
1445
1446         bch2_trans_init(&trans, c, 0, 0);
1447
1448         bch2_trans_iter_init(&trans, &iter, BTREE_ID_alloc, POS_MIN,
1449                              BTREE_ITER_PREFETCH);
1450         bch2_trans_iter_init(&trans, &discard_iter, BTREE_ID_need_discard, POS_MIN,
1451                              BTREE_ITER_PREFETCH);
1452         bch2_trans_iter_init(&trans, &freespace_iter, BTREE_ID_freespace, POS_MIN,
1453                              BTREE_ITER_PREFETCH);
1454         bch2_trans_iter_init(&trans, &bucket_gens_iter, BTREE_ID_bucket_gens, POS_MIN,
1455                              BTREE_ITER_PREFETCH);
1456
1457         while (1) {
1458                 struct bpos next;
1459
1460                 bch2_trans_begin(&trans);
1461
1462                 k = bch2_get_key_or_real_bucket_hole(&iter, &hole);
1463                 ret = bkey_err(k);
1464                 if (ret)
1465                         goto bkey_err;
1466
1467                 if (!k.k)
1468                         break;
1469
1470                 if (k.k->type) {
1471                         next = bpos_nosnap_successor(k.k->p);
1472
1473                         ret = bch2_check_alloc_key(&trans,
1474                                                    k, &iter,
1475                                                    &discard_iter,
1476                                                    &freespace_iter,
1477                                                    &bucket_gens_iter);
1478                         if (ret)
1479                                 goto bkey_err;
1480                 } else {
1481                         next = k.k->p;
1482
1483                         ret = bch2_check_alloc_hole_freespace(&trans,
1484                                                     bkey_start_pos(k.k),
1485                                                     &next,
1486                                                     &freespace_iter) ?:
1487                                 bch2_check_alloc_hole_bucket_gens(&trans,
1488                                                     bkey_start_pos(k.k),
1489                                                     &next,
1490                                                     &bucket_gens_iter);
1491                         if (ret)
1492                                 goto bkey_err;
1493                 }
1494
1495                 ret = bch2_trans_commit(&trans, NULL, NULL,
1496                                         BTREE_INSERT_NOFAIL|
1497                                         BTREE_INSERT_LAZY_RW);
1498                 if (ret)
1499                         goto bkey_err;
1500
1501                 bch2_btree_iter_set_pos(&iter, next);
1502 bkey_err:
1503                 if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
1504                         continue;
1505                 if (ret)
1506                         break;
1507         }
1508         bch2_trans_iter_exit(&trans, &bucket_gens_iter);
1509         bch2_trans_iter_exit(&trans, &freespace_iter);
1510         bch2_trans_iter_exit(&trans, &discard_iter);
1511         bch2_trans_iter_exit(&trans, &iter);
1512
1513         if (ret < 0)
1514                 goto err;
1515
1516         ret = for_each_btree_key2(&trans, iter,
1517                         BTREE_ID_need_discard, POS_MIN,
1518                         BTREE_ITER_PREFETCH, k,
1519                 bch2_check_discard_freespace_key(&trans, &iter, k.k->p)) ?:
1520               for_each_btree_key2(&trans, iter,
1521                         BTREE_ID_freespace, POS_MIN,
1522                         BTREE_ITER_PREFETCH, k,
1523                 bch2_check_discard_freespace_key(&trans, &iter, k.k->p)) ?:
1524               for_each_btree_key_commit(&trans, iter,
1525                         BTREE_ID_bucket_gens, POS_MIN,
1526                         BTREE_ITER_PREFETCH, k,
1527                         NULL, NULL, BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
1528                 bch2_check_bucket_gens_key(&trans, &iter, k));
1529 err:
1530         bch2_trans_exit(&trans);
1531         if (ret)
1532                 bch_err_fn(c, ret);
1533         return ret;
1534 }
1535
1536 static int bch2_check_alloc_to_lru_ref(struct btree_trans *trans,
1537                                        struct btree_iter *alloc_iter)
1538 {
1539         struct bch_fs *c = trans->c;
1540         struct btree_iter lru_iter;
1541         struct bch_alloc_v4 a_convert;
1542         const struct bch_alloc_v4 *a;
1543         struct bkey_s_c alloc_k, lru_k;
1544         struct printbuf buf = PRINTBUF;
1545         int ret;
1546
1547         alloc_k = bch2_btree_iter_peek(alloc_iter);
1548         if (!alloc_k.k)
1549                 return 0;
1550
1551         ret = bkey_err(alloc_k);
1552         if (ret)
1553                 return ret;
1554
1555         a = bch2_alloc_to_v4(alloc_k, &a_convert);
1556
1557         if (a->data_type != BCH_DATA_cached)
1558                 return 0;
1559
1560         lru_k = bch2_bkey_get_iter(trans, &lru_iter, BTREE_ID_lru,
1561                              lru_pos(alloc_k.k->p.inode,
1562                                      bucket_to_u64(alloc_k.k->p),
1563                                      a->io_time[READ]), 0);
1564         ret = bkey_err(lru_k);
1565         if (ret)
1566                 return ret;
1567
1568         if (fsck_err_on(!a->io_time[READ], c,
1569                         "cached bucket with read_time 0\n"
1570                         "  %s",
1571                 (printbuf_reset(&buf),
1572                  bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf)) ||
1573             fsck_err_on(lru_k.k->type != KEY_TYPE_set, c,
1574                         "missing lru entry\n"
1575                         "  %s",
1576                         (printbuf_reset(&buf),
1577                          bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) {
1578                 u64 read_time = a->io_time[READ] ?:
1579                         atomic64_read(&c->io_clock[READ].now);
1580
1581                 ret = bch2_lru_set(trans,
1582                                    alloc_k.k->p.inode,
1583                                    bucket_to_u64(alloc_k.k->p),
1584                                    read_time);
1585                 if (ret)
1586                         goto err;
1587
1588                 if (a->io_time[READ] != read_time) {
1589                         struct bkey_i_alloc_v4 *a_mut =
1590                                 bch2_alloc_to_v4_mut(trans, alloc_k);
1591                         ret = PTR_ERR_OR_ZERO(a_mut);
1592                         if (ret)
1593                                 goto err;
1594
1595                         a_mut->v.io_time[READ] = read_time;
1596                         ret = bch2_trans_update(trans, alloc_iter,
1597                                                 &a_mut->k_i, BTREE_TRIGGER_NORUN);
1598                         if (ret)
1599                                 goto err;
1600                 }
1601         }
1602 err:
1603 fsck_err:
1604         bch2_trans_iter_exit(trans, &lru_iter);
1605         printbuf_exit(&buf);
1606         return ret;
1607 }
1608
1609 int bch2_check_alloc_to_lru_refs(struct bch_fs *c)
1610 {
1611         struct btree_iter iter;
1612         struct bkey_s_c k;
1613         int ret = 0;
1614
1615         ret = bch2_trans_run(c,
1616                 for_each_btree_key_commit(&trans, iter, BTREE_ID_alloc,
1617                                 POS_MIN, BTREE_ITER_PREFETCH, k,
1618                                 NULL, NULL, BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
1619                         bch2_check_alloc_to_lru_ref(&trans, &iter)));
1620         if (ret)
1621                 bch_err_fn(c, ret);
1622         return ret;
1623 }
1624
1625 static int bch2_discard_one_bucket(struct btree_trans *trans,
1626                                    struct btree_iter *need_discard_iter,
1627                                    struct bpos *discard_pos_done,
1628                                    u64 *seen,
1629                                    u64 *open,
1630                                    u64 *need_journal_commit,
1631                                    u64 *discarded)
1632 {
1633         struct bch_fs *c = trans->c;
1634         struct bpos pos = need_discard_iter->pos;
1635         struct btree_iter iter = { NULL };
1636         struct bkey_s_c k;
1637         struct bch_dev *ca;
1638         struct bkey_i_alloc_v4 *a;
1639         struct printbuf buf = PRINTBUF;
1640         int ret = 0;
1641
1642         ca = bch_dev_bkey_exists(c, pos.inode);
1643         if (!percpu_ref_tryget(&ca->io_ref)) {
1644                 bch2_btree_iter_set_pos(need_discard_iter, POS(pos.inode + 1, 0));
1645                 return 0;
1646         }
1647
1648         if (bch2_bucket_is_open_safe(c, pos.inode, pos.offset)) {
1649                 (*open)++;
1650                 goto out;
1651         }
1652
1653         if (bch2_bucket_needs_journal_commit(&c->buckets_waiting_for_journal,
1654                         c->journal.flushed_seq_ondisk,
1655                         pos.inode, pos.offset)) {
1656                 (*need_journal_commit)++;
1657                 goto out;
1658         }
1659
1660         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_alloc,
1661                                need_discard_iter->pos,
1662                                BTREE_ITER_CACHED);
1663         ret = bkey_err(k);
1664         if (ret)
1665                 goto out;
1666
1667         a = bch2_alloc_to_v4_mut(trans, k);
1668         ret = PTR_ERR_OR_ZERO(a);
1669         if (ret)
1670                 goto out;
1671
1672         if (BCH_ALLOC_V4_NEED_INC_GEN(&a->v)) {
1673                 a->v.gen++;
1674                 SET_BCH_ALLOC_V4_NEED_INC_GEN(&a->v, false);
1675                 goto write;
1676         }
1677
1678         if (a->v.journal_seq > c->journal.flushed_seq_ondisk) {
1679                 if (test_bit(BCH_FS_CHECK_ALLOC_DONE, &c->flags)) {
1680                         bch2_trans_inconsistent(trans,
1681                                 "clearing need_discard but journal_seq %llu > flushed_seq %llu\n"
1682                                 "%s",
1683                                 a->v.journal_seq,
1684                                 c->journal.flushed_seq_ondisk,
1685                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
1686                         ret = -EIO;
1687                 }
1688                 goto out;
1689         }
1690
1691         if (a->v.data_type != BCH_DATA_need_discard) {
1692                 if (test_bit(BCH_FS_CHECK_ALLOC_DONE, &c->flags)) {
1693                         bch2_trans_inconsistent(trans,
1694                                 "bucket incorrectly set in need_discard btree\n"
1695                                 "%s",
1696                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
1697                         ret = -EIO;
1698                 }
1699
1700                 goto out;
1701         }
1702
1703         if (!bkey_eq(*discard_pos_done, iter.pos) &&
1704             ca->mi.discard && !c->opts.nochanges) {
1705                 /*
1706                  * This works without any other locks because this is the only
1707                  * thread that removes items from the need_discard tree
1708                  */
1709                 bch2_trans_unlock(trans);
1710                 blkdev_issue_discard(ca->disk_sb.bdev,
1711                                      k.k->p.offset * ca->mi.bucket_size,
1712                                      ca->mi.bucket_size,
1713                                      GFP_KERNEL);
1714                 *discard_pos_done = iter.pos;
1715
1716                 ret = bch2_trans_relock_notrace(trans);
1717                 if (ret)
1718                         goto out;
1719         }
1720
1721         SET_BCH_ALLOC_V4_NEED_DISCARD(&a->v, false);
1722         a->v.data_type = alloc_data_type(a->v, a->v.data_type);
1723 write:
1724         ret =   bch2_trans_update(trans, &iter, &a->k_i, 0) ?:
1725                 bch2_trans_commit(trans, NULL, NULL,
1726                                   BCH_WATERMARK_btree|
1727                                   BTREE_INSERT_NOFAIL);
1728         if (ret)
1729                 goto out;
1730
1731         this_cpu_inc(c->counters[BCH_COUNTER_bucket_discard]);
1732         (*discarded)++;
1733 out:
1734         (*seen)++;
1735         bch2_trans_iter_exit(trans, &iter);
1736         percpu_ref_put(&ca->io_ref);
1737         printbuf_exit(&buf);
1738         return ret;
1739 }
1740
1741 static void bch2_do_discards_work(struct work_struct *work)
1742 {
1743         struct bch_fs *c = container_of(work, struct bch_fs, discard_work);
1744         struct btree_trans trans;
1745         struct btree_iter iter;
1746         struct bkey_s_c k;
1747         u64 seen = 0, open = 0, need_journal_commit = 0, discarded = 0;
1748         struct bpos discard_pos_done = POS_MAX;
1749         int ret;
1750
1751         bch2_trans_init(&trans, c, 0, 0);
1752
1753         /*
1754          * We're doing the commit in bch2_discard_one_bucket instead of using
1755          * for_each_btree_key_commit() so that we can increment counters after
1756          * successful commit:
1757          */
1758         ret = for_each_btree_key2(&trans, iter,
1759                         BTREE_ID_need_discard, POS_MIN, 0, k,
1760                 bch2_discard_one_bucket(&trans, &iter, &discard_pos_done,
1761                                         &seen,
1762                                         &open,
1763                                         &need_journal_commit,
1764                                         &discarded));
1765
1766         bch2_trans_exit(&trans);
1767
1768         if (need_journal_commit * 2 > seen)
1769                 bch2_journal_flush_async(&c->journal, NULL);
1770
1771         bch2_write_ref_put(c, BCH_WRITE_REF_discard);
1772
1773         trace_discard_buckets(c, seen, open, need_journal_commit, discarded,
1774                               bch2_err_str(ret));
1775 }
1776
1777 void bch2_do_discards(struct bch_fs *c)
1778 {
1779         if (bch2_write_ref_tryget(c, BCH_WRITE_REF_discard) &&
1780             !queue_work(c->write_ref_wq, &c->discard_work))
1781                 bch2_write_ref_put(c, BCH_WRITE_REF_discard);
1782 }
1783
1784 static int invalidate_one_bucket(struct btree_trans *trans,
1785                                  struct btree_iter *lru_iter,
1786                                  struct bkey_s_c lru_k,
1787                                  s64 *nr_to_invalidate)
1788 {
1789         struct bch_fs *c = trans->c;
1790         struct btree_iter alloc_iter = { NULL };
1791         struct bkey_i_alloc_v4 *a = NULL;
1792         struct printbuf buf = PRINTBUF;
1793         struct bpos bucket = u64_to_bucket(lru_k.k->p.offset);
1794         unsigned cached_sectors;
1795         int ret = 0;
1796
1797         if (*nr_to_invalidate <= 0)
1798                 return 1;
1799
1800         if (!bch2_dev_bucket_exists(c, bucket)) {
1801                 prt_str(&buf, "lru entry points to invalid bucket");
1802                 goto err;
1803         }
1804
1805         if (bch2_bucket_is_open_safe(c, bucket.inode, bucket.offset))
1806                 return 0;
1807
1808         a = bch2_trans_start_alloc_update(trans, &alloc_iter, bucket);
1809         ret = PTR_ERR_OR_ZERO(a);
1810         if (ret)
1811                 goto out;
1812
1813         /* We expect harmless races here due to the btree write buffer: */
1814         if (lru_pos_time(lru_iter->pos) != alloc_lru_idx_read(a->v))
1815                 goto out;
1816
1817         BUG_ON(a->v.data_type != BCH_DATA_cached);
1818
1819         if (!a->v.cached_sectors)
1820                 bch_err(c, "invalidating empty bucket, confused");
1821
1822         cached_sectors = a->v.cached_sectors;
1823
1824         SET_BCH_ALLOC_V4_NEED_INC_GEN(&a->v, false);
1825         a->v.gen++;
1826         a->v.data_type          = 0;
1827         a->v.dirty_sectors      = 0;
1828         a->v.cached_sectors     = 0;
1829         a->v.io_time[READ]      = atomic64_read(&c->io_clock[READ].now);
1830         a->v.io_time[WRITE]     = atomic64_read(&c->io_clock[WRITE].now);
1831
1832         ret =   bch2_trans_update(trans, &alloc_iter, &a->k_i,
1833                                 BTREE_TRIGGER_BUCKET_INVALIDATE) ?:
1834                 bch2_trans_commit(trans, NULL, NULL,
1835                                   BCH_WATERMARK_btree|
1836                                   BTREE_INSERT_NOFAIL);
1837         if (ret)
1838                 goto out;
1839
1840         trace_and_count(c, bucket_invalidate, c, bucket.inode, bucket.offset, cached_sectors);
1841         --*nr_to_invalidate;
1842 out:
1843         bch2_trans_iter_exit(trans, &alloc_iter);
1844         printbuf_exit(&buf);
1845         return ret;
1846 err:
1847         prt_str(&buf, "\n  lru key: ");
1848         bch2_bkey_val_to_text(&buf, c, lru_k);
1849
1850         prt_str(&buf, "\n  lru entry: ");
1851         bch2_lru_pos_to_text(&buf, lru_iter->pos);
1852
1853         prt_str(&buf, "\n  alloc key: ");
1854         if (!a)
1855                 bch2_bpos_to_text(&buf, bucket);
1856         else
1857                 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&a->k_i));
1858
1859         bch_err(c, "%s", buf.buf);
1860         if (test_bit(BCH_FS_CHECK_LRUS_DONE, &c->flags)) {
1861                 bch2_inconsistent_error(c);
1862                 ret = -EINVAL;
1863         }
1864
1865         goto out;
1866 }
1867
1868 static void bch2_do_invalidates_work(struct work_struct *work)
1869 {
1870         struct bch_fs *c = container_of(work, struct bch_fs, invalidate_work);
1871         struct bch_dev *ca;
1872         struct btree_trans trans;
1873         struct btree_iter iter;
1874         struct bkey_s_c k;
1875         unsigned i;
1876         int ret = 0;
1877
1878         bch2_trans_init(&trans, c, 0, 0);
1879
1880         ret = bch2_btree_write_buffer_flush(&trans);
1881         if (ret)
1882                 goto err;
1883
1884         for_each_member_device(ca, c, i) {
1885                 s64 nr_to_invalidate =
1886                         should_invalidate_buckets(ca, bch2_dev_usage_read(ca));
1887
1888                 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_lru,
1889                                 lru_pos(ca->dev_idx, 0, 0),
1890                                 lru_pos(ca->dev_idx, U64_MAX, LRU_TIME_MAX),
1891                                 BTREE_ITER_INTENT, k,
1892                         invalidate_one_bucket(&trans, &iter, k, &nr_to_invalidate));
1893
1894                 if (ret < 0) {
1895                         percpu_ref_put(&ca->ref);
1896                         break;
1897                 }
1898         }
1899 err:
1900         bch2_trans_exit(&trans);
1901         bch2_write_ref_put(c, BCH_WRITE_REF_invalidate);
1902 }
1903
1904 void bch2_do_invalidates(struct bch_fs *c)
1905 {
1906         if (bch2_write_ref_tryget(c, BCH_WRITE_REF_invalidate) &&
1907             !queue_work(c->write_ref_wq, &c->invalidate_work))
1908                 bch2_write_ref_put(c, BCH_WRITE_REF_invalidate);
1909 }
1910
1911 static int bch2_dev_freespace_init(struct bch_fs *c, struct bch_dev *ca,
1912                                    unsigned long *last_updated)
1913 {
1914         struct btree_trans trans;
1915         struct btree_iter iter;
1916         struct bkey_s_c k;
1917         struct bkey hole;
1918         struct bpos end = POS(ca->dev_idx, ca->mi.nbuckets);
1919         struct bch_member *m;
1920         int ret;
1921
1922         bch2_trans_init(&trans, c, 0, 0);
1923
1924         bch2_trans_iter_init(&trans, &iter, BTREE_ID_alloc,
1925                              POS(ca->dev_idx, ca->mi.first_bucket),
1926                              BTREE_ITER_PREFETCH);
1927         /*
1928          * Scan the alloc btree for every bucket on @ca, and add buckets to the
1929          * freespace/need_discard/need_gc_gens btrees as needed:
1930          */
1931         while (1) {
1932                 if (*last_updated + HZ * 10 < jiffies) {
1933                         bch_info(ca, "%s: currently at %llu/%llu",
1934                                  __func__, iter.pos.offset, ca->mi.nbuckets);
1935                         *last_updated = jiffies;
1936                 }
1937
1938                 bch2_trans_begin(&trans);
1939
1940                 if (bkey_ge(iter.pos, end)) {
1941                         ret = 0;
1942                         break;
1943                 }
1944
1945                 k = bch2_get_key_or_hole(&iter, end, &hole);
1946                 ret = bkey_err(k);
1947                 if (ret)
1948                         goto bkey_err;
1949
1950                 if (k.k->type) {
1951                         /*
1952                          * We process live keys in the alloc btree one at a
1953                          * time:
1954                          */
1955                         struct bch_alloc_v4 a_convert;
1956                         const struct bch_alloc_v4 *a = bch2_alloc_to_v4(k, &a_convert);
1957
1958                         ret =   bch2_bucket_do_index(&trans, k, a, true) ?:
1959                                 bch2_trans_commit(&trans, NULL, NULL,
1960                                                   BTREE_INSERT_LAZY_RW|
1961                                                   BTREE_INSERT_NOFAIL);
1962                         if (ret)
1963                                 goto bkey_err;
1964
1965                         bch2_btree_iter_advance(&iter);
1966                 } else {
1967                         struct bkey_i *freespace;
1968
1969                         freespace = bch2_trans_kmalloc(&trans, sizeof(*freespace));
1970                         ret = PTR_ERR_OR_ZERO(freespace);
1971                         if (ret)
1972                                 goto bkey_err;
1973
1974                         bkey_init(&freespace->k);
1975                         freespace->k.type       = KEY_TYPE_set;
1976                         freespace->k.p          = k.k->p;
1977                         freespace->k.size       = k.k->size;
1978
1979                         ret = __bch2_btree_insert(&trans, BTREE_ID_freespace, freespace, 0) ?:
1980                                 bch2_trans_commit(&trans, NULL, NULL,
1981                                                   BTREE_INSERT_LAZY_RW|
1982                                                   BTREE_INSERT_NOFAIL);
1983                         if (ret)
1984                                 goto bkey_err;
1985
1986                         bch2_btree_iter_set_pos(&iter, k.k->p);
1987                 }
1988 bkey_err:
1989                 if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
1990                         continue;
1991                 if (ret)
1992                         break;
1993         }
1994
1995         bch2_trans_iter_exit(&trans, &iter);
1996         bch2_trans_exit(&trans);
1997
1998         if (ret < 0) {
1999                 bch_err(ca, "error initializing free space: %s", bch2_err_str(ret));
2000                 return ret;
2001         }
2002
2003         mutex_lock(&c->sb_lock);
2004         m = bch2_sb_get_members(c->disk_sb.sb)->members + ca->dev_idx;
2005         SET_BCH_MEMBER_FREESPACE_INITIALIZED(m, true);
2006         mutex_unlock(&c->sb_lock);
2007
2008         return 0;
2009 }
2010
2011 int bch2_fs_freespace_init(struct bch_fs *c)
2012 {
2013         struct bch_dev *ca;
2014         unsigned i;
2015         int ret = 0;
2016         bool doing_init = false;
2017         unsigned long last_updated = jiffies;
2018
2019         /*
2020          * We can crash during the device add path, so we need to check this on
2021          * every mount:
2022          */
2023
2024         for_each_member_device(ca, c, i) {
2025                 if (ca->mi.freespace_initialized)
2026                         continue;
2027
2028                 if (!doing_init) {
2029                         bch_info(c, "initializing freespace");
2030                         doing_init = true;
2031                 }
2032
2033                 ret = bch2_dev_freespace_init(c, ca, &last_updated);
2034                 if (ret) {
2035                         percpu_ref_put(&ca->ref);
2036                         bch_err_fn(c, ret);
2037                         return ret;
2038                 }
2039         }
2040
2041         if (doing_init) {
2042                 mutex_lock(&c->sb_lock);
2043                 bch2_write_super(c);
2044                 mutex_unlock(&c->sb_lock);
2045                 bch_verbose(c, "done initializing freespace");
2046         }
2047
2048         return 0;
2049 }
2050
2051 /* Bucket IO clocks: */
2052
2053 int bch2_bucket_io_time_reset(struct btree_trans *trans, unsigned dev,
2054                               size_t bucket_nr, int rw)
2055 {
2056         struct bch_fs *c = trans->c;
2057         struct btree_iter iter;
2058         struct bkey_i_alloc_v4 *a;
2059         u64 now;
2060         int ret = 0;
2061
2062         a = bch2_trans_start_alloc_update(trans, &iter,  POS(dev, bucket_nr));
2063         ret = PTR_ERR_OR_ZERO(a);
2064         if (ret)
2065                 return ret;
2066
2067         now = atomic64_read(&c->io_clock[rw].now);
2068         if (a->v.io_time[rw] == now)
2069                 goto out;
2070
2071         a->v.io_time[rw] = now;
2072
2073         ret   = bch2_trans_update(trans, &iter, &a->k_i, 0) ?:
2074                 bch2_trans_commit(trans, NULL, NULL, 0);
2075 out:
2076         bch2_trans_iter_exit(trans, &iter);
2077         return ret;
2078 }
2079
2080 /* Startup/shutdown (ro/rw): */
2081
2082 void bch2_recalc_capacity(struct bch_fs *c)
2083 {
2084         struct bch_dev *ca;
2085         u64 capacity = 0, reserved_sectors = 0, gc_reserve;
2086         unsigned bucket_size_max = 0;
2087         unsigned long ra_pages = 0;
2088         unsigned i;
2089
2090         lockdep_assert_held(&c->state_lock);
2091
2092         for_each_online_member(ca, c, i) {
2093                 struct backing_dev_info *bdi = ca->disk_sb.bdev->bd_disk->bdi;
2094
2095                 ra_pages += bdi->ra_pages;
2096         }
2097
2098         bch2_set_ra_pages(c, ra_pages);
2099
2100         for_each_rw_member(ca, c, i) {
2101                 u64 dev_reserve = 0;
2102
2103                 /*
2104                  * We need to reserve buckets (from the number
2105                  * of currently available buckets) against
2106                  * foreground writes so that mainly copygc can
2107                  * make forward progress.
2108                  *
2109                  * We need enough to refill the various reserves
2110                  * from scratch - copygc will use its entire
2111                  * reserve all at once, then run against when
2112                  * its reserve is refilled (from the formerly
2113                  * available buckets).
2114                  *
2115                  * This reserve is just used when considering if
2116                  * allocations for foreground writes must wait -
2117                  * not -ENOSPC calculations.
2118                  */
2119
2120                 dev_reserve += ca->nr_btree_reserve * 2;
2121                 dev_reserve += ca->mi.nbuckets >> 6; /* copygc reserve */
2122
2123                 dev_reserve += 1;       /* btree write point */
2124                 dev_reserve += 1;       /* copygc write point */
2125                 dev_reserve += 1;       /* rebalance write point */
2126
2127                 dev_reserve *= ca->mi.bucket_size;
2128
2129                 capacity += bucket_to_sector(ca, ca->mi.nbuckets -
2130                                              ca->mi.first_bucket);
2131
2132                 reserved_sectors += dev_reserve * 2;
2133
2134                 bucket_size_max = max_t(unsigned, bucket_size_max,
2135                                         ca->mi.bucket_size);
2136         }
2137
2138         gc_reserve = c->opts.gc_reserve_bytes
2139                 ? c->opts.gc_reserve_bytes >> 9
2140                 : div64_u64(capacity * c->opts.gc_reserve_percent, 100);
2141
2142         reserved_sectors = max(gc_reserve, reserved_sectors);
2143
2144         reserved_sectors = min(reserved_sectors, capacity);
2145
2146         c->capacity = capacity - reserved_sectors;
2147
2148         c->bucket_size_max = bucket_size_max;
2149
2150         /* Wake up case someone was waiting for buckets */
2151         closure_wake_up(&c->freelist_wait);
2152 }
2153
2154 static bool bch2_dev_has_open_write_point(struct bch_fs *c, struct bch_dev *ca)
2155 {
2156         struct open_bucket *ob;
2157         bool ret = false;
2158
2159         for (ob = c->open_buckets;
2160              ob < c->open_buckets + ARRAY_SIZE(c->open_buckets);
2161              ob++) {
2162                 spin_lock(&ob->lock);
2163                 if (ob->valid && !ob->on_partial_list &&
2164                     ob->dev == ca->dev_idx)
2165                         ret = true;
2166                 spin_unlock(&ob->lock);
2167         }
2168
2169         return ret;
2170 }
2171
2172 /* device goes ro: */
2173 void bch2_dev_allocator_remove(struct bch_fs *c, struct bch_dev *ca)
2174 {
2175         unsigned i;
2176
2177         /* First, remove device from allocation groups: */
2178
2179         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
2180                 clear_bit(ca->dev_idx, c->rw_devs[i].d);
2181
2182         /*
2183          * Capacity is calculated based off of devices in allocation groups:
2184          */
2185         bch2_recalc_capacity(c);
2186
2187         bch2_open_buckets_stop(c, ca, false);
2188
2189         /*
2190          * Wake up threads that were blocked on allocation, so they can notice
2191          * the device can no longer be removed and the capacity has changed:
2192          */
2193         closure_wake_up(&c->freelist_wait);
2194
2195         /*
2196          * journal_res_get() can block waiting for free space in the journal -
2197          * it needs to notice there may not be devices to allocate from anymore:
2198          */
2199         wake_up(&c->journal.wait);
2200
2201         /* Now wait for any in flight writes: */
2202
2203         closure_wait_event(&c->open_buckets_wait,
2204                            !bch2_dev_has_open_write_point(c, ca));
2205 }
2206
2207 /* device goes rw: */
2208 void bch2_dev_allocator_add(struct bch_fs *c, struct bch_dev *ca)
2209 {
2210         unsigned i;
2211
2212         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
2213                 if (ca->mi.data_allowed & (1 << i))
2214                         set_bit(ca->dev_idx, c->rw_devs[i].d);
2215 }
2216
2217 void bch2_fs_allocator_background_init(struct bch_fs *c)
2218 {
2219         spin_lock_init(&c->freelist_lock);
2220         INIT_WORK(&c->discard_work, bch2_do_discards_work);
2221         INIT_WORK(&c->invalidate_work, bch2_do_invalidates_work);
2222 }