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