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

   1 /*
   2  * Primary bucket allocation code
   3  *
   4  * Copyright 2012 Google, Inc.
   5  *
   6  * Allocation in bcache is done in terms of buckets:
   7  *
   8  * Each bucket has associated an 8 bit gen; this gen corresponds to the gen in
   9  * btree pointers - they must match for the pointer to be considered valid.
  10  *
  11  * Thus (assuming a bucket has no dirty data or metadata in it) we can reuse a
  12  * bucket simply by incrementing its gen.
  13  *
  14  * The gens (along with the priorities; it's really the gens are important but
  15  * the code is named as if it's the priorities) are written in an arbitrary list
  16  * of buckets on disk, with a pointer to them in the journal header.
  17  *
  18  * When we invalidate a bucket, we have to write its new gen to disk and wait
  19  * for that write to complete before we use it - otherwise after a crash we
  20  * could have pointers that appeared to be good but pointed to data that had
  21  * been overwritten.
  22  *
  23  * Since the gens and priorities are all stored contiguously on disk, we can
  24  * batch this up: We fill up the free_inc list with freshly invalidated buckets,
  25  * call prio_write(), and when prio_write() finishes we pull buckets off the
  26  * free_inc list and optionally discard them.
  27  *
  28  * free_inc isn't the only freelist - if it was, we'd often have to sleep while
  29  * priorities and gens were being written before we could allocate. c->free is a
  30  * smaller freelist, and buckets on that list are always ready to be used.
  31  *
  32  * If we've got discards enabled, that happens when a bucket moves from the
  33  * free_inc list to the free list.
  34  *
  35  * It's important to ensure that gens don't wrap around - with respect to
  36  * either the oldest gen in the btree or the gen on disk. This is quite
  37  * difficult to do in practice, but we explicitly guard against it anyways - if
  38  * a bucket is in danger of wrapping around we simply skip invalidating it that
  39  * time around, and we garbage collect or rewrite the priorities sooner than we
  40  * would have otherwise.
  41  *
  42  * bch2_bucket_alloc() allocates a single bucket from a specific device.
  43  *
  44  * bch2_bucket_alloc_set() allocates one or more buckets from different devices
  45  * in a given filesystem.
  46  *
  47  * invalidate_buckets() drives all the processes described above. It's called
  48  * from bch2_bucket_alloc() and a few other places that need to make sure free
  49  * buckets are ready.
  50  *
  51  * invalidate_buckets_(lru|fifo)() find buckets that are available to be
  52  * invalidated, and then invalidate them and stick them on the free_inc list -
  53  * in either lru or fifo order.
  54  */
  55
  56 #include "bcachefs.h"
  57 #include "alloc.h"
  58 #include "btree_cache.h"
  59 #include "btree_io.h"
  60 #include "btree_update.h"
  61 #include "btree_update_interior.h"
  62 #include "btree_gc.h"
  63 #include "buckets.h"
  64 #include "checksum.h"
  65 #include "clock.h"
  66 #include "debug.h"
  67 #include "disk_groups.h"
  68 #include "error.h"
  69 #include "extents.h"
  70 #include "io.h"
  71 #include "journal.h"
  72 #include "super-io.h"
  73
  74 #include <linux/blkdev.h>
  75 #include <linux/kthread.h>
  76 #include <linux/math64.h>
  77 #include <linux/random.h>
  78 #include <linux/rculist.h>
  79 #include <linux/rcupdate.h>
  80 #include <linux/sched/task.h>
  81 #include <linux/sort.h>
  82 #include <trace/events/bcachefs.h>
  83
  84 static void bch2_recalc_oldest_io(struct bch_fs *, struct bch_dev *, int);
  85
  86 /* Ratelimiting/PD controllers */
  87
  88 static void pd_controllers_update(struct work_struct *work)
  89 {
  90         struct bch_fs *c = container_of(to_delayed_work(work),
  91                                            struct bch_fs,
  92                                            pd_controllers_update);
  93         struct bch_dev *ca;
  94         unsigned i;
  95
  96         for_each_member_device(ca, c, i) {
  97                 struct bch_dev_usage stats = bch2_dev_usage_read(c, ca);
  98
  99                 u64 free = bucket_to_sector(ca,
 100                                 __dev_buckets_free(ca, stats)) << 9;
 101                 /*
 102                  * Bytes of internal fragmentation, which can be
 103                  * reclaimed by copy GC
 104                  */
 105                 s64 fragmented = (bucket_to_sector(ca,
 106                                         stats.buckets[BCH_DATA_USER] +
 107                                         stats.buckets[BCH_DATA_CACHED]) -
 108                                   (stats.sectors[BCH_DATA_USER] +
 109                                    stats.sectors[BCH_DATA_CACHED])) << 9;
 110
 111                 fragmented = max(0LL, fragmented);
 112
 113                 bch2_pd_controller_update(&ca->copygc_pd,
 114                                          free, fragmented, -1);
 115         }
 116
 117         schedule_delayed_work(&c->pd_controllers_update,
 118                               c->pd_controllers_update_seconds * HZ);
 119 }
 120
 121 /* Persistent alloc info: */
 122
 123 static unsigned bch_alloc_val_u64s(const struct bch_alloc *a)
 124 {
 125         unsigned bytes = offsetof(struct bch_alloc, data);
 126
 127         if (a->fields & (1 << BCH_ALLOC_FIELD_READ_TIME))
 128                 bytes += 2;
 129         if (a->fields & (1 << BCH_ALLOC_FIELD_WRITE_TIME))
 130                 bytes += 2;
 131
 132         return DIV_ROUND_UP(bytes, sizeof(u64));
 133 }
 134
 135 const char *bch2_alloc_invalid(const struct bch_fs *c, struct bkey_s_c k)
 136 {
 137         if (k.k->p.inode >= c->sb.nr_devices ||
 138             !c->devs[k.k->p.inode])
 139                 return "invalid device";
 140
 141         switch (k.k->type) {
 142         case BCH_ALLOC: {
 143                 struct bkey_s_c_alloc a = bkey_s_c_to_alloc(k);
 144
 145                 if (bch_alloc_val_u64s(a.v) != bkey_val_u64s(a.k))
 146                         return "incorrect value size";
 147                 break;
 148         }
 149         default:
 150                 return "invalid type";
 151         }
 152
 153         return NULL;
 154 }
 155
 156 void bch2_alloc_to_text(struct bch_fs *c, char *buf,
 157                         size_t size, struct bkey_s_c k)
 158 {
 159         buf[0] = '\0';
 160
 161         switch (k.k->type) {
 162         case BCH_ALLOC:
 163                 break;
 164         }
 165 }
 166
 167 static inline unsigned get_alloc_field(const u8 **p, unsigned bytes)
 168 {
 169         unsigned v;
 170
 171         switch (bytes) {
 172         case 1:
 173                 v = **p;
 174                 break;
 175         case 2:
 176                 v = le16_to_cpup((void *) *p);
 177                 break;
 178         case 4:
 179                 v = le32_to_cpup((void *) *p);
 180                 break;
 181         default:
 182                 BUG();
 183         }
 184
 185         *p += bytes;
 186         return v;
 187 }
 188
 189 static inline void put_alloc_field(u8 **p, unsigned bytes, unsigned v)
 190 {
 191         switch (bytes) {
 192         case 1:
 193                 **p = v;
 194                 break;
 195         case 2:
 196                 *((__le16 *) *p) = cpu_to_le16(v);
 197                 break;
 198         case 4:
 199                 *((__le32 *) *p) = cpu_to_le32(v);
 200                 break;
 201         default:
 202                 BUG();
 203         }
 204
 205         *p += bytes;
 206 }
 207
 208 static void bch2_alloc_read_key(struct bch_fs *c, struct bkey_s_c k)
 209 {
 210         struct bch_dev *ca;
 211         struct bkey_s_c_alloc a;
 212         struct bucket_mark new;
 213         struct bucket *g;
 214         const u8 *d;
 215
 216         if (k.k->type != BCH_ALLOC)
 217                 return;
 218
 219         a = bkey_s_c_to_alloc(k);
 220         ca = bch_dev_bkey_exists(c, a.k->p.inode);
 221
 222         if (a.k->p.offset >= ca->mi.nbuckets)
 223                 return;
 224
 225         lg_local_lock(&c->usage_lock);
 226
 227         g = bucket(ca, a.k->p.offset);
 228         bucket_cmpxchg(g, new, ({
 229                 new.gen = a.v->gen;
 230                 new.gen_valid = 1;
 231         }));
 232
 233         d = a.v->data;
 234         if (a.v->fields & (1 << BCH_ALLOC_FIELD_READ_TIME))
 235                 g->io_time[READ] = get_alloc_field(&d, 2);
 236         if (a.v->fields & (1 << BCH_ALLOC_FIELD_WRITE_TIME))
 237                 g->io_time[WRITE] = get_alloc_field(&d, 2);
 238
 239         lg_local_unlock(&c->usage_lock);
 240 }
 241
 242 int bch2_alloc_read(struct bch_fs *c, struct list_head *journal_replay_list)
 243 {
 244         struct journal_replay *r;
 245         struct btree_iter iter;
 246         struct bkey_s_c k;
 247         struct bch_dev *ca;
 248         unsigned i;
 249         int ret;
 250
 251         for_each_btree_key(&iter, c, BTREE_ID_ALLOC, POS_MIN, 0, k) {
 252                 bch2_alloc_read_key(c, k);
 253                 bch2_btree_iter_cond_resched(&iter);
 254         }
 255
 256         ret = bch2_btree_iter_unlock(&iter);
 257         if (ret)
 258                 return ret;
 259
 260         list_for_each_entry(r, journal_replay_list, list) {
 261                 struct bkey_i *k, *n;
 262                 struct jset_entry *entry;
 263
 264                 for_each_jset_key(k, n, entry, &r->j)
 265                         if (entry->btree_id == BTREE_ID_ALLOC)
 266                                 bch2_alloc_read_key(c, bkey_i_to_s_c(k));
 267         }
 268
 269         mutex_lock(&c->bucket_clock[READ].lock);
 270         for_each_member_device(ca, c, i) {
 271                 down_read(&ca->bucket_lock);
 272                 bch2_recalc_oldest_io(c, ca, READ);
 273                 up_read(&ca->bucket_lock);
 274         }
 275         mutex_unlock(&c->bucket_clock[READ].lock);
 276
 277         mutex_lock(&c->bucket_clock[WRITE].lock);
 278         for_each_member_device(ca, c, i) {
 279                 down_read(&ca->bucket_lock);
 280                 bch2_recalc_oldest_io(c, ca, WRITE);
 281                 up_read(&ca->bucket_lock);
 282         }
 283         mutex_unlock(&c->bucket_clock[WRITE].lock);
 284
 285         return 0;
 286 }
 287
 288 static int __bch2_alloc_write_key(struct bch_fs *c, struct bch_dev *ca,
 289                                   size_t b, struct btree_iter *iter,
 290                                   u64 *journal_seq)
 291 {
 292         struct bucket_mark m;
 293         __BKEY_PADDED(k, DIV_ROUND_UP(sizeof(struct bch_alloc), 8)) alloc_key;
 294         struct bucket *g;
 295         struct bkey_i_alloc *a;
 296         u8 *d;
 297         int ret;
 298
 299         bch2_btree_iter_set_pos(iter, POS(ca->dev_idx, b));
 300
 301         do {
 302                 ret = btree_iter_err(bch2_btree_iter_peek_slot(iter));
 303                 if (ret)
 304                         break;
 305
 306                 lg_local_lock(&c->usage_lock);
 307                 g = bucket(ca, b);
 308
 309                 /* read mark under btree node lock: */
 310                 m = READ_ONCE(g->mark);
 311                 a = bkey_alloc_init(&alloc_key.k);
 312                 a->k.p          = iter->pos;
 313                 a->v.fields     = 0;
 314                 a->v.gen        = m.gen;
 315                 set_bkey_val_u64s(&a->k, bch_alloc_val_u64s(&a->v));
 316
 317                 d = a->v.data;
 318                 if (a->v.fields & (1 << BCH_ALLOC_FIELD_READ_TIME))
 319                         put_alloc_field(&d, 2, g->io_time[READ]);
 320                 if (a->v.fields & (1 << BCH_ALLOC_FIELD_WRITE_TIME))
 321                         put_alloc_field(&d, 2, g->io_time[WRITE]);
 322                 lg_local_unlock(&c->usage_lock);
 323
 324                 ret = bch2_btree_insert_at(c, NULL, NULL, journal_seq,
 325                                            BTREE_INSERT_ATOMIC|
 326                                            BTREE_INSERT_NOFAIL|
 327                                            BTREE_INSERT_USE_RESERVE|
 328                                            BTREE_INSERT_USE_ALLOC_RESERVE|
 329                                            BTREE_INSERT_NOWAIT,
 330                                            BTREE_INSERT_ENTRY(iter, &a->k_i));
 331                 bch2_btree_iter_cond_resched(iter);
 332         } while (ret == -EINTR);
 333
 334         return ret;
 335 }
 336
 337 int bch2_alloc_replay_key(struct bch_fs *c, struct bpos pos)
 338 {
 339         struct bch_dev *ca;
 340         struct btree_iter iter;
 341         int ret;
 342
 343         if (pos.inode >= c->sb.nr_devices || !c->devs[pos.inode])
 344                 return 0;
 345
 346         ca = bch_dev_bkey_exists(c, pos.inode);
 347
 348         if (pos.offset >= ca->mi.nbuckets)
 349                 return 0;
 350
 351         bch2_btree_iter_init(&iter, c, BTREE_ID_ALLOC, POS_MIN,
 352                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 353
 354         ret = __bch2_alloc_write_key(c, ca, pos.offset, &iter, NULL);
 355         bch2_btree_iter_unlock(&iter);
 356         return ret;
 357 }
 358
 359 int bch2_alloc_write(struct bch_fs *c)
 360 {
 361         struct bch_dev *ca;
 362         unsigned i;
 363         int ret = 0;
 364
 365         for_each_rw_member(ca, c, i) {
 366                 struct btree_iter iter;
 367                 unsigned long bucket;
 368
 369                 bch2_btree_iter_init(&iter, c, BTREE_ID_ALLOC, POS_MIN,
 370                                      BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 371
 372                 down_read(&ca->bucket_lock);
 373                 for_each_set_bit(bucket, ca->buckets_dirty, ca->mi.nbuckets) {
 374                         ret = __bch2_alloc_write_key(c, ca, bucket, &iter, NULL);
 375                         if (ret)
 376                                 break;
 377
 378                         clear_bit(bucket, ca->buckets_dirty);
 379                 }
 380                 up_read(&ca->bucket_lock);
 381                 bch2_btree_iter_unlock(&iter);
 382
 383                 if (ret) {
 384                         percpu_ref_put(&ca->io_ref);
 385                         break;
 386                 }
 387         }
 388
 389         return ret;
 390 }
 391
 392 /* Bucket IO clocks: */
 393
 394 static void bch2_recalc_oldest_io(struct bch_fs *c, struct bch_dev *ca, int rw)
 395 {
 396         struct bucket_clock *clock = &c->bucket_clock[rw];
 397         struct bucket_array *buckets = bucket_array(ca);
 398         struct bucket *g;
 399         u16 max_last_io = 0;
 400         unsigned i;
 401
 402         lockdep_assert_held(&c->bucket_clock[rw].lock);
 403
 404         /* Recalculate max_last_io for this device: */
 405         for_each_bucket(g, buckets)
 406                 max_last_io = max(max_last_io, bucket_last_io(c, g, rw));
 407
 408         ca->max_last_bucket_io[rw] = max_last_io;
 409
 410         /* Recalculate global max_last_io: */
 411         max_last_io = 0;
 412
 413         for_each_member_device(ca, c, i)
 414                 max_last_io = max(max_last_io, ca->max_last_bucket_io[rw]);
 415
 416         clock->max_last_io = max_last_io;
 417 }
 418
 419 static void bch2_rescale_bucket_io_times(struct bch_fs *c, int rw)
 420 {
 421         struct bucket_clock *clock = &c->bucket_clock[rw];
 422         struct bucket_array *buckets;
 423         struct bch_dev *ca;
 424         struct bucket *g;
 425         unsigned i;
 426
 427         trace_rescale_prios(c);
 428
 429         for_each_member_device(ca, c, i) {
 430                 down_read(&ca->bucket_lock);
 431                 buckets = bucket_array(ca);
 432
 433                 for_each_bucket(g, buckets)
 434                         g->io_time[rw] = clock->hand -
 435                         bucket_last_io(c, g, rw) / 2;
 436
 437                 bch2_recalc_oldest_io(c, ca, rw);
 438
 439                 up_read(&ca->bucket_lock);
 440         }
 441 }
 442
 443 static void bch2_inc_clock_hand(struct io_timer *timer)
 444 {
 445         struct bucket_clock *clock = container_of(timer,
 446                                                 struct bucket_clock, rescale);
 447         struct bch_fs *c = container_of(clock,
 448                                         struct bch_fs, bucket_clock[clock->rw]);
 449         struct bch_dev *ca;
 450         u64 capacity;
 451         unsigned i;
 452
 453         mutex_lock(&clock->lock);
 454
 455         /* if clock cannot be advanced more, rescale prio */
 456         if (clock->max_last_io >= U16_MAX - 2)
 457                 bch2_rescale_bucket_io_times(c, clock->rw);
 458
 459         BUG_ON(clock->max_last_io >= U16_MAX - 2);
 460
 461         for_each_member_device(ca, c, i)
 462                 ca->max_last_bucket_io[clock->rw]++;
 463         clock->max_last_io++;
 464         clock->hand++;
 465
 466         mutex_unlock(&clock->lock);
 467
 468         capacity = READ_ONCE(c->capacity);
 469
 470         if (!capacity)
 471                 return;
 472
 473         /*
 474          * we only increment when 0.1% of the filesystem capacity has been read
 475          * or written too, this determines if it's time
 476          *
 477          * XXX: we shouldn't really be going off of the capacity of devices in
 478          * RW mode (that will be 0 when we're RO, yet we can still service
 479          * reads)
 480          */
 481         timer->expire += capacity >> 10;
 482
 483         bch2_io_timer_add(&c->io_clock[clock->rw], timer);
 484 }
 485
 486 static void bch2_bucket_clock_init(struct bch_fs *c, int rw)
 487 {
 488         struct bucket_clock *clock = &c->bucket_clock[rw];
 489
 490         clock->hand             = 1;
 491         clock->rw               = rw;
 492         clock->rescale.fn       = bch2_inc_clock_hand;
 493         clock->rescale.expire   = c->capacity >> 10;
 494         mutex_init(&clock->lock);
 495 }
 496
 497 /* Background allocator thread: */
 498
 499 /*
 500  * Scans for buckets to be invalidated, invalidates them, rewrites prios/gens
 501  * (marking them as invalidated on disk), then optionally issues discard
 502  * commands to the newly free buckets, then puts them on the various freelists.
 503  */
 504
 505 static void verify_not_on_freelist(struct bch_fs *c, struct bch_dev *ca,
 506                                    size_t bucket)
 507 {
 508         if (expensive_debug_checks(c) &&
 509             test_bit(BCH_FS_ALLOCATOR_STARTED, &c->flags)) {
 510                 size_t iter;
 511                 long i;
 512                 unsigned j;
 513
 514                 for (j = 0; j < RESERVE_NR; j++)
 515                         fifo_for_each_entry(i, &ca->free[j], iter)
 516                                 BUG_ON(i == bucket);
 517                 fifo_for_each_entry(i, &ca->free_inc, iter)
 518                         BUG_ON(i == bucket);
 519         }
 520 }
 521
 522 #define BUCKET_GC_GEN_MAX       96U
 523
 524 /**
 525  * wait_buckets_available - wait on reclaimable buckets
 526  *
 527  * If there aren't enough available buckets to fill up free_inc, wait until
 528  * there are.
 529  */
 530 static int wait_buckets_available(struct bch_fs *c, struct bch_dev *ca)
 531 {
 532         unsigned long gc_count = c->gc_count;
 533         int ret = 0;
 534
 535         while (1) {
 536                 set_current_state(TASK_INTERRUPTIBLE);
 537                 if (kthread_should_stop()) {
 538                         ret = 1;
 539                         break;
 540                 }
 541
 542                 if (gc_count != c->gc_count)
 543                         ca->inc_gen_really_needs_gc = 0;
 544
 545                 if ((ssize_t) (dev_buckets_available(c, ca) -
 546                                ca->inc_gen_really_needs_gc) >=
 547                     (ssize_t) fifo_free(&ca->free_inc))
 548                         break;
 549
 550                 up_read(&c->gc_lock);
 551                 schedule();
 552                 try_to_freeze();
 553                 down_read(&c->gc_lock);
 554         }
 555
 556         __set_current_state(TASK_RUNNING);
 557         return ret;
 558 }
 559
 560 static bool bch2_can_invalidate_bucket(struct bch_dev *ca,
 561                                        size_t bucket,
 562                                        struct bucket_mark mark)
 563 {
 564         u8 gc_gen;
 565
 566         if (!is_available_bucket(mark))
 567                 return false;
 568
 569         gc_gen = bucket_gc_gen(ca, bucket);
 570
 571         if (gc_gen >= BUCKET_GC_GEN_MAX / 2)
 572                 ca->inc_gen_needs_gc++;
 573
 574         if (gc_gen >= BUCKET_GC_GEN_MAX)
 575                 ca->inc_gen_really_needs_gc++;
 576
 577         return gc_gen < BUCKET_GC_GEN_MAX;
 578 }
 579
 580 static void bch2_invalidate_one_bucket(struct bch_fs *c, struct bch_dev *ca,
 581                                        size_t bucket)
 582 {
 583         struct bucket_mark m;
 584
 585         spin_lock(&c->freelist_lock);
 586         if (!bch2_invalidate_bucket(c, ca, bucket, &m)) {
 587                 spin_unlock(&c->freelist_lock);
 588                 return;
 589         }
 590
 591         verify_not_on_freelist(c, ca, bucket);
 592         BUG_ON(!fifo_push(&ca->free_inc, bucket));
 593         spin_unlock(&c->freelist_lock);
 594
 595         /* gc lock held: */
 596         bucket_io_clock_reset(c, ca, bucket, READ);
 597         bucket_io_clock_reset(c, ca, bucket, WRITE);
 598
 599         if (m.cached_sectors) {
 600                 ca->allocator_invalidating_data = true;
 601         } else if (m.journal_seq_valid) {
 602                 u64 journal_seq = atomic64_read(&c->journal.seq);
 603                 u64 bucket_seq  = journal_seq;
 604
 605                 bucket_seq &= ~((u64) U16_MAX);
 606                 bucket_seq |= m.journal_seq;
 607
 608                 if (bucket_seq > journal_seq)
 609                         bucket_seq -= 1 << 16;
 610
 611                 ca->allocator_journal_seq_flush =
 612                         max(ca->allocator_journal_seq_flush, bucket_seq);
 613         }
 614 }
 615
 616 /*
 617  * Determines what order we're going to reuse buckets, smallest bucket_key()
 618  * first.
 619  *
 620  *
 621  * - We take into account the read prio of the bucket, which gives us an
 622  *   indication of how hot the data is -- we scale the prio so that the prio
 623  *   farthest from the clock is worth 1/8th of the closest.
 624  *
 625  * - The number of sectors of cached data in the bucket, which gives us an
 626  *   indication of the cost in cache misses this eviction will cause.
 627  *
 628  * - If hotness * sectors used compares equal, we pick the bucket with the
 629  *   smallest bucket_gc_gen() - since incrementing the same bucket's generation
 630  *   number repeatedly forces us to run mark and sweep gc to avoid generation
 631  *   number wraparound.
 632  */
 633
 634 static unsigned long bucket_sort_key(struct bch_fs *c, struct bch_dev *ca,
 635                                      size_t b, struct bucket_mark m)
 636 {
 637         unsigned last_io = bucket_last_io(c, bucket(ca, b), READ);
 638         unsigned max_last_io = ca->max_last_bucket_io[READ];
 639
 640         /*
 641          * Time since last read, scaled to [0, 8) where larger value indicates
 642          * more recently read data:
 643          */
 644         unsigned long hotness = (max_last_io - last_io) * 7 / max_last_io;
 645
 646         /* How much we want to keep the data in this bucket: */
 647         unsigned long data_wantness =
 648                 (hotness + 1) * bucket_sectors_used(m);
 649
 650         unsigned long needs_journal_commit =
 651                 bucket_needs_journal_commit(m, c->journal.last_seq_ondisk);
 652
 653         return  (data_wantness << 9) |
 654                 (needs_journal_commit << 8) |
 655                 bucket_gc_gen(ca, b);
 656 }
 657
 658 static inline int bucket_alloc_cmp(alloc_heap *h,
 659                                    struct alloc_heap_entry l,
 660                                    struct alloc_heap_entry r)
 661 {
 662         return (l.key > r.key) - (l.key < r.key) ?:
 663                 (l.nr < r.nr)  - (l.nr  > r.nr) ?:
 664                 (l.bucket > r.bucket) - (l.bucket < r.bucket);
 665 }
 666
 667 static void find_reclaimable_buckets_lru(struct bch_fs *c, struct bch_dev *ca)
 668 {
 669         struct bucket_array *buckets;
 670         struct alloc_heap_entry e = { 0 };
 671         size_t b;
 672
 673         ca->alloc_heap.used = 0;
 674
 675         mutex_lock(&c->bucket_clock[READ].lock);
 676         down_read(&ca->bucket_lock);
 677
 678         buckets = bucket_array(ca);
 679
 680         bch2_recalc_oldest_io(c, ca, READ);
 681
 682         /*
 683          * Find buckets with lowest read priority, by building a maxheap sorted
 684          * by read priority and repeatedly replacing the maximum element until
 685          * all buckets have been visited.
 686          */
 687         for (b = ca->mi.first_bucket; b < ca->mi.nbuckets; b++) {
 688                 struct bucket_mark m = READ_ONCE(buckets->b[b].mark);
 689                 unsigned long key = bucket_sort_key(c, ca, b, m);
 690
 691                 if (!bch2_can_invalidate_bucket(ca, b, m))
 692                         continue;
 693
 694                 if (e.nr && e.bucket + e.nr == b && e.key == key) {
 695                         e.nr++;
 696                 } else {
 697                         if (e.nr)
 698                                 heap_add_or_replace(&ca->alloc_heap, e, -bucket_alloc_cmp);
 699
 700                         e = (struct alloc_heap_entry) {
 701                                 .bucket = b,
 702                                 .nr     = 1,
 703                                 .key    = key,
 704                         };
 705                 }
 706
 707                 cond_resched();
 708         }
 709
 710         if (e.nr)
 711                 heap_add_or_replace(&ca->alloc_heap, e, -bucket_alloc_cmp);
 712
 713         up_read(&ca->bucket_lock);
 714         mutex_unlock(&c->bucket_clock[READ].lock);
 715
 716         heap_resort(&ca->alloc_heap, bucket_alloc_cmp);
 717
 718         while (heap_pop(&ca->alloc_heap, e, bucket_alloc_cmp)) {
 719                 for (b = e.bucket;
 720                      b < e.bucket + e.nr;
 721                      b++) {
 722                         if (fifo_full(&ca->free_inc))
 723                                 return;
 724
 725                         bch2_invalidate_one_bucket(c, ca, b);
 726                 }
 727         }
 728 }
 729
 730 static void find_reclaimable_buckets_fifo(struct bch_fs *c, struct bch_dev *ca)
 731 {
 732         struct bucket_array *buckets = bucket_array(ca);
 733         struct bucket_mark m;
 734         size_t b, checked;
 735
 736         for (checked = 0;
 737              checked < ca->mi.nbuckets && !fifo_full(&ca->free_inc);
 738              checked++) {
 739                 if (ca->fifo_last_bucket <  ca->mi.first_bucket ||
 740                     ca->fifo_last_bucket >= ca->mi.nbuckets)
 741                         ca->fifo_last_bucket = ca->mi.first_bucket;
 742
 743                 b = ca->fifo_last_bucket++;
 744
 745                 m = READ_ONCE(buckets->b[b].mark);
 746
 747                 if (bch2_can_invalidate_bucket(ca, b, m))
 748                         bch2_invalidate_one_bucket(c, ca, b);
 749
 750                 cond_resched();
 751         }
 752 }
 753
 754 static void find_reclaimable_buckets_random(struct bch_fs *c, struct bch_dev *ca)
 755 {
 756         struct bucket_array *buckets = bucket_array(ca);
 757         struct bucket_mark m;
 758         size_t checked;
 759
 760         for (checked = 0;
 761              checked < ca->mi.nbuckets / 2 && !fifo_full(&ca->free_inc);
 762              checked++) {
 763                 size_t b = bch2_rand_range(ca->mi.nbuckets -
 764                                            ca->mi.first_bucket) +
 765                         ca->mi.first_bucket;
 766
 767                 m = READ_ONCE(buckets->b[b].mark);
 768
 769                 if (bch2_can_invalidate_bucket(ca, b, m))
 770                         bch2_invalidate_one_bucket(c, ca, b);
 771
 772                 cond_resched();
 773         }
 774 }
 775
 776 static void find_reclaimable_buckets(struct bch_fs *c, struct bch_dev *ca)
 777 {
 778         ca->inc_gen_needs_gc                    = 0;
 779         ca->inc_gen_really_needs_gc             = 0;
 780
 781         switch (ca->mi.replacement) {
 782         case CACHE_REPLACEMENT_LRU:
 783                 find_reclaimable_buckets_lru(c, ca);
 784                 break;
 785         case CACHE_REPLACEMENT_FIFO:
 786                 find_reclaimable_buckets_fifo(c, ca);
 787                 break;
 788         case CACHE_REPLACEMENT_RANDOM:
 789                 find_reclaimable_buckets_random(c, ca);
 790                 break;
 791         }
 792 }
 793
 794 static int size_t_cmp(const void *_l, const void *_r)
 795 {
 796         const size_t *l = _l, *r = _r;
 797
 798         return (*l > *r) - (*l < *r);
 799 }
 800
 801 static void sort_free_inc(struct bch_fs *c, struct bch_dev *ca)
 802 {
 803         BUG_ON(ca->free_inc.front);
 804
 805         spin_lock(&c->freelist_lock);
 806         sort(ca->free_inc.data,
 807              ca->free_inc.back,
 808              sizeof(ca->free_inc.data[0]),
 809              size_t_cmp, NULL);
 810         spin_unlock(&c->freelist_lock);
 811 }
 812
 813 static int bch2_invalidate_free_inc(struct bch_fs *c, struct bch_dev *ca,
 814                                     u64 *journal_seq, size_t nr)
 815 {
 816         struct btree_iter iter;
 817         int ret = 0;
 818
 819         bch2_btree_iter_init(&iter, c, BTREE_ID_ALLOC, POS(ca->dev_idx, 0),
 820                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 821
 822         /*
 823          * XXX: if ca->nr_invalidated != 0, just return if we'd block doing the
 824          * btree update or journal_res_get
 825          */
 826         while (ca->nr_invalidated < min(nr, fifo_used(&ca->free_inc))) {
 827                 size_t b = fifo_idx_entry(&ca->free_inc, ca->nr_invalidated);
 828
 829                 ret = __bch2_alloc_write_key(c, ca, b, &iter, journal_seq);
 830                 if (ret)
 831                         break;
 832
 833                 ca->nr_invalidated++;
 834         }
 835
 836         bch2_btree_iter_unlock(&iter);
 837         return ret;
 838 }
 839
 840 static bool __push_invalidated_bucket(struct bch_fs *c, struct bch_dev *ca, size_t bucket)
 841 {
 842         unsigned i;
 843
 844         /*
 845          * Don't remove from free_inc until after it's added to
 846          * freelist, so gc can find it:
 847          */
 848         spin_lock(&c->freelist_lock);
 849         for (i = 0; i < RESERVE_NR; i++)
 850                 if (fifo_push(&ca->free[i], bucket)) {
 851                         fifo_pop(&ca->free_inc, bucket);
 852                         --ca->nr_invalidated;
 853                         closure_wake_up(&c->freelist_wait);
 854                         spin_unlock(&c->freelist_lock);
 855                         return true;
 856                 }
 857         spin_unlock(&c->freelist_lock);
 858
 859         return false;
 860 }
 861
 862 static int push_invalidated_bucket(struct bch_fs *c, struct bch_dev *ca, size_t bucket)
 863 {
 864         int ret = 0;
 865
 866         while (1) {
 867                 set_current_state(TASK_INTERRUPTIBLE);
 868
 869                 if (__push_invalidated_bucket(c, ca, bucket))
 870                         break;
 871
 872                 if ((current->flags & PF_KTHREAD) &&
 873                     kthread_should_stop()) {
 874                         ret = 1;
 875                         break;
 876                 }
 877
 878                 schedule();
 879                 try_to_freeze();
 880         }
 881
 882         __set_current_state(TASK_RUNNING);
 883         return ret;
 884 }
 885
 886 /*
 887  * Given an invalidated, ready to use bucket: issue a discard to it if enabled,
 888  * then add it to the freelist, waiting until there's room if necessary:
 889  */
 890 static int discard_invalidated_buckets(struct bch_fs *c, struct bch_dev *ca)
 891 {
 892         while (ca->nr_invalidated) {
 893                 size_t bucket = fifo_peek(&ca->free_inc);
 894
 895                 BUG_ON(fifo_empty(&ca->free_inc) || !ca->nr_invalidated);
 896
 897                 if (ca->mi.discard &&
 898                     blk_queue_discard(bdev_get_queue(ca->disk_sb.bdev)))
 899                         blkdev_issue_discard(ca->disk_sb.bdev,
 900                                              bucket_to_sector(ca, bucket),
 901                                              ca->mi.bucket_size, GFP_NOIO, 0);
 902
 903                 if (push_invalidated_bucket(c, ca, bucket))
 904                         return 1;
 905         }
 906
 907         return 0;
 908 }
 909
 910 /**
 911  * bch_allocator_thread - move buckets from free_inc to reserves
 912  *
 913  * The free_inc FIFO is populated by find_reclaimable_buckets(), and
 914  * the reserves are depleted by bucket allocation. When we run out
 915  * of free_inc, try to invalidate some buckets and write out
 916  * prios and gens.
 917  */
 918 static int bch2_allocator_thread(void *arg)
 919 {
 920         struct bch_dev *ca = arg;
 921         struct bch_fs *c = ca->fs;
 922         u64 journal_seq;
 923         int ret;
 924
 925         set_freezable();
 926
 927         while (1) {
 928                 while (1) {
 929                         cond_resched();
 930
 931                         pr_debug("discarding %zu invalidated buckets",
 932                                  ca->nr_invalidated);
 933
 934                         ret = discard_invalidated_buckets(c, ca);
 935                         if (ret)
 936                                 goto stop;
 937
 938                         if (fifo_empty(&ca->free_inc))
 939                                 break;
 940
 941                         pr_debug("invalidating %zu buckets",
 942                                  fifo_used(&ca->free_inc));
 943
 944                         journal_seq = 0;
 945                         ret = bch2_invalidate_free_inc(c, ca, &journal_seq, SIZE_MAX);
 946                         if (ret) {
 947                                 bch_err(ca, "error invalidating buckets: %i", ret);
 948                                 goto stop;
 949                         }
 950
 951                         if (!ca->nr_invalidated) {
 952                                 bch_err(ca, "allocator thread unable to make forward progress!");
 953                                 goto stop;
 954                         }
 955
 956                         if (ca->allocator_invalidating_data)
 957                                 ret = bch2_journal_flush_seq(&c->journal, journal_seq);
 958                         else if (ca->allocator_journal_seq_flush)
 959                                 ret = bch2_journal_flush_seq(&c->journal,
 960                                                        ca->allocator_journal_seq_flush);
 961
 962                         /*
 963                          * journal error - buckets haven't actually been
 964                          * invalidated, can't discard them:
 965                          */
 966                         if (ret) {
 967                                 bch_err(ca, "journal error: %i", ret);
 968                                 goto stop;
 969                         }
 970                 }
 971
 972                 pr_debug("free_inc now empty");
 973
 974                 /* Reset front/back so we can easily sort fifo entries later: */
 975                 ca->free_inc.front = ca->free_inc.back  = 0;
 976                 ca->allocator_journal_seq_flush         = 0;
 977                 ca->allocator_invalidating_data         = false;
 978
 979                 down_read(&c->gc_lock);
 980                 while (1) {
 981                         size_t prev = fifo_used(&ca->free_inc);
 982
 983                         if (test_bit(BCH_FS_GC_FAILURE, &c->flags)) {
 984                                 up_read(&c->gc_lock);
 985                                 bch_err(ca, "gc failure");
 986                                 goto stop;
 987                         }
 988
 989                         /*
 990                          * Find some buckets that we can invalidate, either
 991                          * they're completely unused, or only contain clean data
 992                          * that's been written back to the backing device or
 993                          * another cache tier
 994                          */
 995
 996                         pr_debug("scanning for reclaimable buckets");
 997
 998                         find_reclaimable_buckets(c, ca);
 999
1000                         pr_debug("found %zu buckets (free_inc %zu/%zu)",
1001                                  fifo_used(&ca->free_inc) - prev,
1002                                  fifo_used(&ca->free_inc), ca->free_inc.size);
1003
1004                         trace_alloc_batch(ca, fifo_used(&ca->free_inc),
1005                                           ca->free_inc.size);
1006
1007                         if ((ca->inc_gen_needs_gc >= ca->free_inc.size ||
1008                              (!fifo_full(&ca->free_inc) &&
1009                               ca->inc_gen_really_needs_gc >=
1010                               fifo_free(&ca->free_inc))) &&
1011                             c->gc_thread) {
1012                                 atomic_inc(&c->kick_gc);
1013                                 wake_up_process(c->gc_thread);
1014                         }
1015
1016                         if (fifo_full(&ca->free_inc))
1017                                 break;
1018
1019                         if (!fifo_empty(&ca->free_inc) &&
1020                             !fifo_full(&ca->free[RESERVE_MOVINGGC]))
1021                                 break;
1022
1023                         /*
1024                          * copygc may be waiting until either its reserve fills
1025                          * up, or we can't make forward progress:
1026                          */
1027                         ca->allocator_blocked = true;
1028                         closure_wake_up(&c->freelist_wait);
1029
1030                         ret = wait_buckets_available(c, ca);
1031                         if (ret) {
1032                                 up_read(&c->gc_lock);
1033                                 goto stop;
1034                         }
1035                 }
1036
1037                 ca->allocator_blocked = false;
1038                 up_read(&c->gc_lock);
1039
1040                 pr_debug("free_inc now %zu/%zu",
1041                          fifo_used(&ca->free_inc),
1042                          ca->free_inc.size);
1043
1044                 sort_free_inc(c, ca);
1045
1046                 /*
1047                  * free_inc is now full of newly-invalidated buckets: next,
1048                  * write out the new bucket gens:
1049                  */
1050         }
1051
1052 stop:
1053         pr_debug("alloc thread stopping (ret %i)", ret);
1054         return 0;
1055 }
1056
1057 /* Allocation */
1058
1059 /*
1060  * Open buckets represent a bucket that's currently being allocated from.  They
1061  * serve two purposes:
1062  *
1063  *  - They track buckets that have been partially allocated, allowing for
1064  *    sub-bucket sized allocations - they're used by the sector allocator below
1065  *
1066  *  - They provide a reference to the buckets they own that mark and sweep GC
1067  *    can find, until the new allocation has a pointer to it inserted into the
1068  *    btree
1069  *
1070  * When allocating some space with the sector allocator, the allocation comes
1071  * with a reference to an open bucket - the caller is required to put that
1072  * reference _after_ doing the index update that makes its allocation reachable.
1073  */
1074
1075 void __bch2_open_bucket_put(struct bch_fs *c, struct open_bucket *ob)
1076 {
1077         struct bch_dev *ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1078
1079         spin_lock(&ob->lock);
1080         bch2_mark_alloc_bucket(c, ca, PTR_BUCKET_NR(ca, &ob->ptr),
1081                                false, gc_pos_alloc(c, ob), 0);
1082         ob->valid = false;
1083         spin_unlock(&ob->lock);
1084
1085         spin_lock(&c->freelist_lock);
1086         ob->freelist = c->open_buckets_freelist;
1087         c->open_buckets_freelist = ob - c->open_buckets;
1088         c->open_buckets_nr_free++;
1089         spin_unlock(&c->freelist_lock);
1090
1091         closure_wake_up(&c->open_buckets_wait);
1092 }
1093
1094 static struct open_bucket *bch2_open_bucket_alloc(struct bch_fs *c)
1095 {
1096         struct open_bucket *ob;
1097
1098         BUG_ON(!c->open_buckets_freelist || !c->open_buckets_nr_free);
1099
1100         ob = c->open_buckets + c->open_buckets_freelist;
1101         c->open_buckets_freelist = ob->freelist;
1102         atomic_set(&ob->pin, 1);
1103
1104         c->open_buckets_nr_free--;
1105         return ob;
1106 }
1107
1108 /* _only_ for allocating the journal on a new device: */
1109 long bch2_bucket_alloc_new_fs(struct bch_dev *ca)
1110 {
1111         struct bucket_array *buckets;
1112         ssize_t b;
1113
1114         rcu_read_lock();
1115         buckets = bucket_array(ca);
1116
1117         for (b = ca->mi.first_bucket; b < ca->mi.nbuckets; b++)
1118                 if (is_available_bucket(buckets->b[b].mark))
1119                         goto success;
1120         b = -1;
1121 success:
1122         rcu_read_unlock();
1123         return b;
1124 }
1125
1126 static inline unsigned open_buckets_reserved(enum alloc_reserve reserve)
1127 {
1128         switch (reserve) {
1129         case RESERVE_ALLOC:
1130                 return 0;
1131         case RESERVE_BTREE:
1132                 return BTREE_NODE_RESERVE / 2;
1133         default:
1134                 return BTREE_NODE_RESERVE;
1135         }
1136 }
1137
1138 /**
1139  * bch_bucket_alloc - allocate a single bucket from a specific device
1140  *
1141  * Returns index of bucket on success, 0 on failure
1142  * */
1143 int bch2_bucket_alloc(struct bch_fs *c, struct bch_dev *ca,
1144                       enum alloc_reserve reserve,
1145                       bool may_alloc_partial,
1146                       struct closure *cl)
1147 {
1148         struct bucket_array *buckets;
1149         struct open_bucket *ob;
1150         long bucket;
1151
1152         spin_lock(&c->freelist_lock);
1153         if (may_alloc_partial &&
1154             ca->open_buckets_partial_nr) {
1155                 int ret = ca->open_buckets_partial[--ca->open_buckets_partial_nr];
1156                 c->open_buckets[ret].on_partial_list = false;
1157                 spin_unlock(&c->freelist_lock);
1158                 return ret;
1159         }
1160
1161         if (unlikely(c->open_buckets_nr_free <= open_buckets_reserved(reserve))) {
1162                 if (cl)
1163                         closure_wait(&c->open_buckets_wait, cl);
1164                 spin_unlock(&c->freelist_lock);
1165                 trace_open_bucket_alloc_fail(ca, reserve);
1166                 return OPEN_BUCKETS_EMPTY;
1167         }
1168
1169         if (likely(fifo_pop(&ca->free[RESERVE_NONE], bucket)))
1170                 goto out;
1171
1172         switch (reserve) {
1173         case RESERVE_ALLOC:
1174                 if (fifo_pop(&ca->free[RESERVE_BTREE], bucket))
1175                         goto out;
1176                 break;
1177         case RESERVE_BTREE:
1178                 if (fifo_used(&ca->free[RESERVE_BTREE]) * 2 >=
1179                     ca->free[RESERVE_BTREE].size &&
1180                     fifo_pop(&ca->free[RESERVE_BTREE], bucket))
1181                         goto out;
1182                 break;
1183         case RESERVE_MOVINGGC:
1184                 if (fifo_pop(&ca->free[RESERVE_MOVINGGC], bucket))
1185                         goto out;
1186                 break;
1187         default:
1188                 break;
1189         }
1190
1191         if (cl)
1192                 closure_wait(&c->freelist_wait, cl);
1193
1194         spin_unlock(&c->freelist_lock);
1195
1196         trace_bucket_alloc_fail(ca, reserve);
1197         return FREELIST_EMPTY;
1198 out:
1199         verify_not_on_freelist(c, ca, bucket);
1200
1201         ob = bch2_open_bucket_alloc(c);
1202
1203         spin_lock(&ob->lock);
1204         lg_local_lock(&c->usage_lock);
1205         buckets = bucket_array(ca);
1206
1207         ob->valid       = true;
1208         ob->sectors_free = ca->mi.bucket_size;
1209         ob->ptr         = (struct bch_extent_ptr) {
1210                 .gen    = buckets->b[bucket].mark.gen,
1211                 .offset = bucket_to_sector(ca, bucket),
1212                 .dev    = ca->dev_idx,
1213         };
1214
1215         bucket_io_clock_reset(c, ca, bucket, READ);
1216         bucket_io_clock_reset(c, ca, bucket, WRITE);
1217
1218         lg_local_unlock(&c->usage_lock);
1219         spin_unlock(&ob->lock);
1220
1221         spin_unlock(&c->freelist_lock);
1222
1223         bch2_wake_allocator(ca);
1224
1225         trace_bucket_alloc(ca, reserve);
1226         return ob - c->open_buckets;
1227 }
1228
1229 static int __dev_alloc_cmp(struct write_point *wp,
1230                            unsigned l, unsigned r)
1231 {
1232         return ((wp->next_alloc[l] > wp->next_alloc[r]) -
1233                 (wp->next_alloc[l] < wp->next_alloc[r]));
1234 }
1235
1236 #define dev_alloc_cmp(l, r) __dev_alloc_cmp(wp, l, r)
1237
1238 struct dev_alloc_list bch2_wp_alloc_list(struct bch_fs *c,
1239                                          struct write_point *wp,
1240                                          struct bch_devs_mask *devs)
1241 {
1242         struct dev_alloc_list ret = { .nr = 0 };
1243         struct bch_dev *ca;
1244         unsigned i;
1245
1246         for_each_member_device_rcu(ca, c, i, devs)
1247                 ret.devs[ret.nr++] = i;
1248
1249         bubble_sort(ret.devs, ret.nr, dev_alloc_cmp);
1250         return ret;
1251 }
1252
1253 void bch2_wp_rescale(struct bch_fs *c, struct bch_dev *ca,
1254                      struct write_point *wp)
1255 {
1256         u64 *v = wp->next_alloc + ca->dev_idx;
1257         u64 free_space = dev_buckets_free(c, ca);
1258         u64 free_space_inv = free_space
1259                 ? div64_u64(1ULL << 48, free_space)
1260                 : 1ULL << 48;
1261         u64 scale = *v / 4;
1262
1263         if (*v + free_space_inv >= *v)
1264                 *v += free_space_inv;
1265         else
1266                 *v = U64_MAX;
1267
1268         for (v = wp->next_alloc;
1269              v < wp->next_alloc + ARRAY_SIZE(wp->next_alloc); v++)
1270                 *v = *v < scale ? 0 : *v - scale;
1271 }
1272
1273 static enum bucket_alloc_ret bch2_bucket_alloc_set(struct bch_fs *c,
1274                                         struct write_point *wp,
1275                                         unsigned nr_replicas,
1276                                         enum alloc_reserve reserve,
1277                                         struct bch_devs_mask *devs,
1278                                         struct closure *cl)
1279 {
1280         enum bucket_alloc_ret ret = NO_DEVICES;
1281         struct dev_alloc_list devs_sorted;
1282         struct bch_dev *ca;
1283         unsigned i, nr_ptrs_effective = 0;
1284         bool have_cache_dev = false;
1285
1286         BUG_ON(nr_replicas > ARRAY_SIZE(wp->ptrs));
1287
1288         for (i = wp->first_ptr; i < wp->nr_ptrs; i++) {
1289                 ca = bch_dev_bkey_exists(c, wp->ptrs[i]->ptr.dev);
1290
1291                 nr_ptrs_effective += ca->mi.durability;
1292                 have_cache_dev |= !ca->mi.durability;
1293         }
1294
1295         if (nr_ptrs_effective >= nr_replicas)
1296                 return ALLOC_SUCCESS;
1297
1298         rcu_read_lock();
1299         devs_sorted = bch2_wp_alloc_list(c, wp, devs);
1300
1301         for (i = 0; i < devs_sorted.nr; i++) {
1302                 int ob;
1303
1304                 ca = rcu_dereference(c->devs[devs_sorted.devs[i]]);
1305                 if (!ca)
1306                         continue;
1307
1308                 if (!ca->mi.durability &&
1309                     (have_cache_dev ||
1310                      wp->type != BCH_DATA_USER))
1311                         continue;
1312
1313                 ob = bch2_bucket_alloc(c, ca, reserve,
1314                                        wp->type == BCH_DATA_USER, cl);
1315                 if (ob < 0) {
1316                         ret = ob;
1317                         if (ret == OPEN_BUCKETS_EMPTY)
1318                                 break;
1319                         continue;
1320                 }
1321
1322                 BUG_ON(ob <= 0 || ob > U8_MAX);
1323                 BUG_ON(wp->nr_ptrs >= ARRAY_SIZE(wp->ptrs));
1324
1325                 wp->ptrs[wp->nr_ptrs++] = c->open_buckets + ob;
1326
1327                 bch2_wp_rescale(c, ca, wp);
1328
1329                 nr_ptrs_effective += ca->mi.durability;
1330                 have_cache_dev |= !ca->mi.durability;
1331
1332                 __clear_bit(ca->dev_idx, devs->d);
1333
1334                 if (nr_ptrs_effective >= nr_replicas) {
1335                         ret = ALLOC_SUCCESS;
1336                         break;
1337                 }
1338         }
1339         rcu_read_unlock();
1340
1341         EBUG_ON(reserve == RESERVE_MOVINGGC &&
1342                 ret != ALLOC_SUCCESS &&
1343                 ret != OPEN_BUCKETS_EMPTY);
1344
1345         switch (ret) {
1346         case ALLOC_SUCCESS:
1347                 return 0;
1348         case NO_DEVICES:
1349                 return -EROFS;
1350         case FREELIST_EMPTY:
1351         case OPEN_BUCKETS_EMPTY:
1352                 return cl ? -EAGAIN : -ENOSPC;
1353         default:
1354                 BUG();
1355         }
1356 }
1357
1358 /* Sector allocator */
1359
1360 static void writepoint_drop_ptr(struct bch_fs *c,
1361                                 struct write_point *wp,
1362                                 unsigned i)
1363 {
1364         struct open_bucket *ob = wp->ptrs[i];
1365         struct bch_dev *ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1366
1367         BUG_ON(ca->open_buckets_partial_nr >=
1368                ARRAY_SIZE(ca->open_buckets_partial));
1369
1370         if (wp->type == BCH_DATA_USER) {
1371                 spin_lock(&c->freelist_lock);
1372                 ob->on_partial_list = true;
1373                 ca->open_buckets_partial[ca->open_buckets_partial_nr++] =
1374                         ob - c->open_buckets;
1375                 spin_unlock(&c->freelist_lock);
1376
1377                 closure_wake_up(&c->open_buckets_wait);
1378                 closure_wake_up(&c->freelist_wait);
1379         } else {
1380                 bch2_open_bucket_put(c, ob);
1381         }
1382
1383         array_remove_item(wp->ptrs, wp->nr_ptrs, i);
1384
1385         if (i < wp->first_ptr)
1386                 wp->first_ptr--;
1387 }
1388
1389 static void writepoint_drop_ptrs(struct bch_fs *c,
1390                                  struct write_point *wp,
1391                                  u16 target, bool in_target)
1392 {
1393         int i;
1394
1395         for (i = wp->first_ptr - 1; i >= 0; --i) {
1396                 struct bch_dev *ca = bch_dev_bkey_exists(c, wp->ptrs[i]->ptr.dev);
1397
1398                 if (dev_in_target(ca, target) == in_target)
1399                         writepoint_drop_ptr(c, wp, i);
1400         }
1401 }
1402
1403 static void verify_not_stale(struct bch_fs *c, const struct write_point *wp)
1404 {
1405 #ifdef CONFIG_BCACHEFS_DEBUG
1406         struct open_bucket *ob;
1407         unsigned i;
1408
1409         writepoint_for_each_ptr_all(wp, ob, i) {
1410                 struct bch_dev *ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1411
1412                 BUG_ON(ptr_stale(ca, &ob->ptr));
1413         }
1414 #endif
1415 }
1416
1417 static int open_bucket_add_buckets(struct bch_fs *c,
1418                                    u16 target,
1419                                    struct write_point *wp,
1420                                    struct bch_devs_list *devs_have,
1421                                    unsigned nr_replicas,
1422                                    enum alloc_reserve reserve,
1423                                    struct closure *cl)
1424 {
1425         struct bch_devs_mask devs = c->rw_devs[wp->type];
1426         struct open_bucket *ob;
1427         unsigned i;
1428
1429         /* Don't allocate from devices we already have pointers to: */
1430         for (i = 0; i < devs_have->nr; i++)
1431                 __clear_bit(devs_have->devs[i], devs.d);
1432
1433         writepoint_for_each_ptr_all(wp, ob, i)
1434                 __clear_bit(ob->ptr.dev, devs.d);
1435
1436         if (target) {
1437                 const struct bch_devs_mask *t;
1438
1439                 rcu_read_lock();
1440                 t = bch2_target_to_mask(c, target);
1441                 if (t)
1442                         bitmap_and(devs.d, devs.d, t->d, BCH_SB_MEMBERS_MAX);
1443                 rcu_read_unlock();
1444         }
1445
1446         return bch2_bucket_alloc_set(c, wp, nr_replicas, reserve, &devs, cl);
1447 }
1448
1449 static struct write_point *__writepoint_find(struct hlist_head *head,
1450                                              unsigned long write_point)
1451 {
1452         struct write_point *wp;
1453
1454         hlist_for_each_entry_rcu(wp, head, node)
1455                 if (wp->write_point == write_point)
1456                         return wp;
1457
1458         return NULL;
1459 }
1460
1461 static struct hlist_head *writepoint_hash(struct bch_fs *c,
1462                                           unsigned long write_point)
1463 {
1464         unsigned hash =
1465                 hash_long(write_point, ilog2(ARRAY_SIZE(c->write_points_hash)));
1466
1467         return &c->write_points_hash[hash];
1468 }
1469
1470 static struct write_point *writepoint_find(struct bch_fs *c,
1471                                            unsigned long write_point)
1472 {
1473         struct write_point *wp, *oldest;
1474         struct hlist_head *head;
1475
1476         if (!(write_point & 1UL)) {
1477                 wp = (struct write_point *) write_point;
1478                 mutex_lock(&wp->lock);
1479                 return wp;
1480         }
1481
1482         head = writepoint_hash(c, write_point);
1483 restart_find:
1484         wp = __writepoint_find(head, write_point);
1485         if (wp) {
1486 lock_wp:
1487                 mutex_lock(&wp->lock);
1488                 if (wp->write_point == write_point)
1489                         goto out;
1490                 mutex_unlock(&wp->lock);
1491                 goto restart_find;
1492         }
1493
1494         oldest = NULL;
1495         for (wp = c->write_points;
1496              wp < c->write_points + ARRAY_SIZE(c->write_points);
1497              wp++)
1498                 if (!oldest || time_before64(wp->last_used, oldest->last_used))
1499                         oldest = wp;
1500
1501         mutex_lock(&oldest->lock);
1502         mutex_lock(&c->write_points_hash_lock);
1503         wp = __writepoint_find(head, write_point);
1504         if (wp && wp != oldest) {
1505                 mutex_unlock(&c->write_points_hash_lock);
1506                 mutex_unlock(&oldest->lock);
1507                 goto lock_wp;
1508         }
1509
1510         wp = oldest;
1511         hlist_del_rcu(&wp->node);
1512         wp->write_point = write_point;
1513         hlist_add_head_rcu(&wp->node, head);
1514         mutex_unlock(&c->write_points_hash_lock);
1515 out:
1516         wp->last_used = sched_clock();
1517         return wp;
1518 }
1519
1520 /*
1521  * Get us an open_bucket we can allocate from, return with it locked:
1522  */
1523 struct write_point *bch2_alloc_sectors_start(struct bch_fs *c,
1524                                 unsigned target,
1525                                 struct write_point_specifier write_point,
1526                                 struct bch_devs_list *devs_have,
1527                                 unsigned nr_replicas,
1528                                 unsigned nr_replicas_required,
1529                                 enum alloc_reserve reserve,
1530                                 unsigned flags,
1531                                 struct closure *cl)
1532 {
1533         struct write_point *wp;
1534         struct open_bucket *ob;
1535         struct bch_dev *ca;
1536         unsigned nr_ptrs_have, nr_ptrs_effective;
1537         int ret, i, cache_idx = -1;
1538
1539         BUG_ON(!nr_replicas || !nr_replicas_required);
1540
1541         wp = writepoint_find(c, write_point.v);
1542
1543         wp->first_ptr = 0;
1544
1545         /* does writepoint have ptrs we can't use? */
1546         writepoint_for_each_ptr(wp, ob, i)
1547                 if (bch2_dev_list_has_dev(*devs_have, ob->ptr.dev)) {
1548                         swap(wp->ptrs[i], wp->ptrs[wp->first_ptr]);
1549                         wp->first_ptr++;
1550                 }
1551
1552         nr_ptrs_have = wp->first_ptr;
1553
1554         /* does writepoint have ptrs we don't want to use? */
1555         if (target)
1556                 writepoint_for_each_ptr(wp, ob, i)
1557                         if (!dev_idx_in_target(c, ob->ptr.dev, target)) {
1558                                 swap(wp->ptrs[i], wp->ptrs[wp->first_ptr]);
1559                                 wp->first_ptr++;
1560                         }
1561
1562         if (flags & BCH_WRITE_ONLY_SPECIFIED_DEVS) {
1563                 ret = open_bucket_add_buckets(c, target, wp, devs_have,
1564                                               nr_replicas, reserve, cl);
1565         } else {
1566                 ret = open_bucket_add_buckets(c, target, wp, devs_have,
1567                                               nr_replicas, reserve, NULL);
1568                 if (!ret)
1569                         goto alloc_done;
1570
1571                 wp->first_ptr = nr_ptrs_have;
1572
1573                 ret = open_bucket_add_buckets(c, 0, wp, devs_have,
1574                                               nr_replicas, reserve, cl);
1575         }
1576
1577         if (ret && ret != -EROFS)
1578                 goto err;
1579 alloc_done:
1580         /* check for more than one cache: */
1581         for (i = wp->nr_ptrs - 1; i >= wp->first_ptr; --i) {
1582                 ca = bch_dev_bkey_exists(c, wp->ptrs[i]->ptr.dev);
1583
1584                 if (ca->mi.durability)
1585                         continue;
1586
1587                 /*
1588                  * if we ended up with more than one cache device, prefer the
1589                  * one in the target we want:
1590                  */
1591                 if (cache_idx >= 0) {
1592                         if (!dev_in_target(ca, target)) {
1593                                 writepoint_drop_ptr(c, wp, i);
1594                         } else {
1595                                 writepoint_drop_ptr(c, wp, cache_idx);
1596                                 cache_idx = i;
1597                         }
1598                 } else {
1599                         cache_idx = i;
1600                 }
1601         }
1602
1603         /* we might have more effective replicas than required: */
1604         nr_ptrs_effective = 0;
1605         writepoint_for_each_ptr(wp, ob, i) {
1606                 ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1607                 nr_ptrs_effective += ca->mi.durability;
1608         }
1609
1610         if (ret == -EROFS &&
1611             nr_ptrs_effective >= nr_replicas_required)
1612                 ret = 0;
1613
1614         if (ret)
1615                 goto err;
1616
1617         if (nr_ptrs_effective > nr_replicas) {
1618                 writepoint_for_each_ptr(wp, ob, i) {
1619                         ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1620
1621                         if (ca->mi.durability &&
1622                             ca->mi.durability <= nr_ptrs_effective - nr_replicas &&
1623                             !dev_idx_in_target(c, ob->ptr.dev, target)) {
1624                                 swap(wp->ptrs[i], wp->ptrs[wp->first_ptr]);
1625                                 wp->first_ptr++;
1626                                 nr_ptrs_effective -= ca->mi.durability;
1627                         }
1628                 }
1629         }
1630
1631         if (nr_ptrs_effective > nr_replicas) {
1632                 writepoint_for_each_ptr(wp, ob, i) {
1633                         ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1634
1635                         if (ca->mi.durability &&
1636                             ca->mi.durability <= nr_ptrs_effective - nr_replicas) {
1637                                 swap(wp->ptrs[i], wp->ptrs[wp->first_ptr]);
1638                                 wp->first_ptr++;
1639                                 nr_ptrs_effective -= ca->mi.durability;
1640                         }
1641                 }
1642         }
1643
1644         /* Remove pointers we don't want to use: */
1645         if (target)
1646                 writepoint_drop_ptrs(c, wp, target, false);
1647
1648         BUG_ON(wp->first_ptr >= wp->nr_ptrs);
1649         BUG_ON(nr_ptrs_effective < nr_replicas_required);
1650
1651         wp->sectors_free = UINT_MAX;
1652
1653         writepoint_for_each_ptr(wp, ob, i)
1654                 wp->sectors_free = min(wp->sectors_free, ob->sectors_free);
1655
1656         BUG_ON(!wp->sectors_free || wp->sectors_free == UINT_MAX);
1657
1658         verify_not_stale(c, wp);
1659
1660         return wp;
1661 err:
1662         mutex_unlock(&wp->lock);
1663         return ERR_PTR(ret);
1664 }
1665
1666 /*
1667  * Append pointers to the space we just allocated to @k, and mark @sectors space
1668  * as allocated out of @ob
1669  */
1670 void bch2_alloc_sectors_append_ptrs(struct bch_fs *c, struct write_point *wp,
1671                                     struct bkey_i_extent *e, unsigned sectors)
1672 {
1673         struct open_bucket *ob;
1674         unsigned i;
1675
1676         BUG_ON(sectors > wp->sectors_free);
1677         wp->sectors_free -= sectors;
1678
1679         writepoint_for_each_ptr(wp, ob, i) {
1680                 struct bch_dev *ca = bch_dev_bkey_exists(c, ob->ptr.dev);
1681                 struct bch_extent_ptr tmp = ob->ptr;
1682
1683                 EBUG_ON(bch2_extent_has_device(extent_i_to_s_c(e), ob->ptr.dev));
1684
1685                 tmp.cached = bkey_extent_is_cached(&e->k) ||
1686                         (!ca->mi.durability && wp->type == BCH_DATA_USER);
1687
1688                 tmp.offset += ca->mi.bucket_size - ob->sectors_free;
1689                 extent_ptr_append(e, tmp);
1690
1691                 BUG_ON(sectors > ob->sectors_free);
1692                 ob->sectors_free -= sectors;
1693         }
1694 }
1695
1696 /*
1697  * Append pointers to the space we just allocated to @k, and mark @sectors space
1698  * as allocated out of @ob
1699  */
1700 void bch2_alloc_sectors_done(struct bch_fs *c, struct write_point *wp)
1701 {
1702         int i;
1703
1704         for (i = wp->nr_ptrs - 1; i >= 0; --i) {
1705                 struct open_bucket *ob = wp->ptrs[i];
1706
1707                 if (!ob->sectors_free) {
1708                         array_remove_item(wp->ptrs, wp->nr_ptrs, i);
1709                         bch2_open_bucket_put(c, ob);
1710                 }
1711         }
1712
1713         mutex_unlock(&wp->lock);
1714 }
1715
1716 /* Startup/shutdown (ro/rw): */
1717
1718 void bch2_recalc_capacity(struct bch_fs *c)
1719 {
1720         struct bch_dev *ca;
1721         u64 total_capacity, capacity = 0, reserved_sectors = 0;
1722         unsigned long ra_pages = 0;
1723         unsigned i, j;
1724
1725         lockdep_assert_held(&c->state_lock);
1726
1727         for_each_online_member(ca, c, i) {
1728                 struct backing_dev_info *bdi = ca->disk_sb.bdev->bd_bdi;
1729
1730                 ra_pages += bdi->ra_pages;
1731         }
1732
1733         bch2_set_ra_pages(c, ra_pages);
1734
1735         for_each_rw_member(ca, c, i) {
1736                 size_t reserve = 0;
1737
1738                 /*
1739                  * We need to reserve buckets (from the number
1740                  * of currently available buckets) against
1741                  * foreground writes so that mainly copygc can
1742                  * make forward progress.
1743                  *
1744                  * We need enough to refill the various reserves
1745                  * from scratch - copygc will use its entire
1746                  * reserve all at once, then run against when
1747                  * its reserve is refilled (from the formerly
1748                  * available buckets).
1749                  *
1750                  * This reserve is just used when considering if
1751                  * allocations for foreground writes must wait -
1752                  * not -ENOSPC calculations.
1753                  */
1754                 for (j = 0; j < RESERVE_NONE; j++)
1755                         reserve += ca->free[j].size;
1756
1757                 reserve += ca->free_inc.size;
1758
1759                 reserve += ARRAY_SIZE(c->write_points);
1760
1761                 reserve += 1;   /* btree write point */
1762
1763                 reserved_sectors += bucket_to_sector(ca, reserve);
1764
1765                 capacity += bucket_to_sector(ca, ca->mi.nbuckets -
1766                                              ca->mi.first_bucket);
1767         }
1768
1769         total_capacity = capacity;
1770
1771         capacity *= (100 - c->opts.gc_reserve_percent);
1772         capacity = div64_u64(capacity, 100);
1773
1774         BUG_ON(reserved_sectors > total_capacity);
1775
1776         capacity = min(capacity, total_capacity - reserved_sectors);
1777
1778         c->capacity = capacity;
1779
1780         if (c->capacity) {
1781                 bch2_io_timer_add(&c->io_clock[READ],
1782                                  &c->bucket_clock[READ].rescale);
1783                 bch2_io_timer_add(&c->io_clock[WRITE],
1784                                  &c->bucket_clock[WRITE].rescale);
1785         } else {
1786                 bch2_io_timer_del(&c->io_clock[READ],
1787                                  &c->bucket_clock[READ].rescale);
1788                 bch2_io_timer_del(&c->io_clock[WRITE],
1789                                  &c->bucket_clock[WRITE].rescale);
1790         }
1791
1792         /* Wake up case someone was waiting for buckets */
1793         closure_wake_up(&c->freelist_wait);
1794 }
1795
1796 static void bch2_stop_write_point(struct bch_fs *c, struct bch_dev *ca,
1797                                   struct write_point *wp)
1798 {
1799         struct bch_devs_mask not_self;
1800
1801         bitmap_complement(not_self.d, ca->self.d, BCH_SB_MEMBERS_MAX);
1802
1803         mutex_lock(&wp->lock);
1804         wp->first_ptr = wp->nr_ptrs;
1805         writepoint_drop_ptrs(c, wp, dev_to_target(ca->dev_idx), true);
1806         mutex_unlock(&wp->lock);
1807 }
1808
1809 static bool bch2_dev_has_open_write_point(struct bch_fs *c, struct bch_dev *ca)
1810 {
1811         struct open_bucket *ob;
1812         bool ret = false;
1813
1814         for (ob = c->open_buckets;
1815              ob < c->open_buckets + ARRAY_SIZE(c->open_buckets);
1816              ob++) {
1817                 spin_lock(&ob->lock);
1818                 if (ob->valid && !ob->on_partial_list &&
1819                     ob->ptr.dev == ca->dev_idx)
1820                         ret = true;
1821                 spin_unlock(&ob->lock);
1822         }
1823
1824         return ret;
1825 }
1826
1827 /* device goes ro: */
1828 void bch2_dev_allocator_remove(struct bch_fs *c, struct bch_dev *ca)
1829 {
1830         unsigned i;
1831
1832         BUG_ON(ca->alloc_thread);
1833
1834         /* First, remove device from allocation groups: */
1835
1836         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
1837                 clear_bit(ca->dev_idx, c->rw_devs[i].d);
1838
1839         /*
1840          * Capacity is calculated based off of devices in allocation groups:
1841          */
1842         bch2_recalc_capacity(c);
1843
1844         /* Next, close write points that point to this device... */
1845         for (i = 0; i < ARRAY_SIZE(c->write_points); i++)
1846                 bch2_stop_write_point(c, ca, &c->write_points[i]);
1847
1848         bch2_stop_write_point(c, ca, &ca->copygc_write_point);
1849         bch2_stop_write_point(c, ca, &c->rebalance_write_point);
1850         bch2_stop_write_point(c, ca, &c->btree_write_point);
1851
1852         mutex_lock(&c->btree_reserve_cache_lock);
1853         while (c->btree_reserve_cache_nr) {
1854                 struct btree_alloc *a =
1855                         &c->btree_reserve_cache[--c->btree_reserve_cache_nr];
1856
1857                 bch2_open_bucket_put_refs(c, &a->ob.nr, a->ob.refs);
1858         }
1859         mutex_unlock(&c->btree_reserve_cache_lock);
1860
1861         /*
1862          * Wake up threads that were blocked on allocation, so they can notice
1863          * the device can no longer be removed and the capacity has changed:
1864          */
1865         closure_wake_up(&c->freelist_wait);
1866
1867         /*
1868          * journal_res_get() can block waiting for free space in the journal -
1869          * it needs to notice there may not be devices to allocate from anymore:
1870          */
1871         wake_up(&c->journal.wait);
1872
1873         /* Now wait for any in flight writes: */
1874
1875         closure_wait_event(&c->open_buckets_wait,
1876                            !bch2_dev_has_open_write_point(c, ca));
1877 }
1878
1879 /* device goes rw: */
1880 void bch2_dev_allocator_add(struct bch_fs *c, struct bch_dev *ca)
1881 {
1882         unsigned i;
1883
1884         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
1885                 if (ca->mi.data_allowed & (1 << i))
1886                         set_bit(ca->dev_idx, c->rw_devs[i].d);
1887 }
1888
1889 /* stop allocator thread: */
1890 void bch2_dev_allocator_stop(struct bch_dev *ca)
1891 {
1892         struct task_struct *p = ca->alloc_thread;
1893
1894         ca->alloc_thread = NULL;
1895
1896         /*
1897          * We need an rcu barrier between setting ca->alloc_thread = NULL and
1898          * the thread shutting down to avoid bch2_wake_allocator() racing:
1899          *
1900          * XXX: it would be better to have the rcu barrier be asynchronous
1901          * instead of blocking us here
1902          */
1903         synchronize_rcu();
1904
1905         if (p) {
1906                 kthread_stop(p);
1907                 put_task_struct(p);
1908         }
1909 }
1910
1911 /* start allocator thread: */
1912 int bch2_dev_allocator_start(struct bch_dev *ca)
1913 {
1914         struct task_struct *p;
1915
1916         /*
1917          * allocator thread already started?
1918          */
1919         if (ca->alloc_thread)
1920                 return 0;
1921
1922         p = kthread_create(bch2_allocator_thread, ca,
1923                            "bch_alloc[%s]", ca->name);
1924         if (IS_ERR(p))
1925                 return PTR_ERR(p);
1926
1927         get_task_struct(p);
1928         ca->alloc_thread = p;
1929         wake_up_process(p);
1930         return 0;
1931 }
1932
1933 static void allocator_start_issue_discards(struct bch_fs *c)
1934 {
1935         struct bch_dev *ca;
1936         unsigned dev_iter;
1937         size_t i, bu;
1938
1939         for_each_rw_member(ca, c, dev_iter) {
1940                 unsigned done = 0;
1941
1942                 fifo_for_each_entry(bu, &ca->free_inc, i) {
1943                         if (done == ca->nr_invalidated)
1944                                 break;
1945
1946                         blkdev_issue_discard(ca->disk_sb.bdev,
1947                                              bucket_to_sector(ca, bu),
1948                                              ca->mi.bucket_size, GFP_NOIO, 0);
1949                         done++;
1950                 }
1951         }
1952 }
1953
1954 static int __bch2_fs_allocator_start(struct bch_fs *c)
1955 {
1956         struct bch_dev *ca;
1957         size_t bu, i;
1958         unsigned dev_iter;
1959         u64 journal_seq = 0;
1960         bool invalidating_data = false;
1961         int ret = 0;
1962
1963         if (test_bit(BCH_FS_GC_FAILURE, &c->flags))
1964                 return -1;
1965
1966         /* Scan for buckets that are already invalidated: */
1967         for_each_rw_member(ca, c, dev_iter) {
1968                 struct btree_iter iter;
1969                 struct bucket_mark m;
1970                 struct bkey_s_c k;
1971
1972                 for_each_btree_key(&iter, c, BTREE_ID_ALLOC, POS(ca->dev_idx, 0), 0, k) {
1973                         if (k.k->type != BCH_ALLOC)
1974                                 continue;
1975
1976                         bu = k.k->p.offset;
1977                         m = READ_ONCE(bucket(ca, bu)->mark);
1978
1979                         if (!is_available_bucket(m) || m.cached_sectors)
1980                                 continue;
1981
1982                         bch2_mark_alloc_bucket(c, ca, bu, true,
1983                                         gc_pos_alloc(c, NULL),
1984                                         BCH_BUCKET_MARK_MAY_MAKE_UNAVAILABLE|
1985                                         BCH_BUCKET_MARK_GC_LOCK_HELD);
1986
1987                         fifo_push(&ca->free_inc, bu);
1988                         ca->nr_invalidated++;
1989
1990                         if (fifo_full(&ca->free_inc))
1991                                 break;
1992                 }
1993                 bch2_btree_iter_unlock(&iter);
1994         }
1995
1996         /* did we find enough buckets? */
1997         for_each_rw_member(ca, c, dev_iter)
1998                 if (fifo_used(&ca->free_inc) < ca->free[RESERVE_BTREE].size) {
1999                         percpu_ref_put(&ca->io_ref);
2000                         goto not_enough;
2001                 }
2002
2003         return 0;
2004 not_enough:
2005         pr_debug("did not find enough empty buckets; issuing discards");
2006
2007         /* clear out free_inc - find_reclaimable_buckets() assumes it's empty */
2008         for_each_rw_member(ca, c, dev_iter)
2009                 discard_invalidated_buckets(c, ca);
2010
2011         pr_debug("scanning for reclaimable buckets");
2012
2013         for_each_rw_member(ca, c, dev_iter) {
2014                 BUG_ON(!fifo_empty(&ca->free_inc));
2015                 ca->free_inc.front = ca->free_inc.back  = 0;
2016
2017                 find_reclaimable_buckets(c, ca);
2018                 sort_free_inc(c, ca);
2019
2020                 invalidating_data |= ca->allocator_invalidating_data;
2021
2022                 fifo_for_each_entry(bu, &ca->free_inc, i)
2023                         if (!fifo_push(&ca->free[RESERVE_BTREE], bu))
2024                                 break;
2025         }
2026
2027         pr_debug("done scanning for reclaimable buckets");
2028
2029         /*
2030          * We're moving buckets to freelists _before_ they've been marked as
2031          * invalidated on disk - we have to so that we can allocate new btree
2032          * nodes to mark them as invalidated on disk.
2033          *
2034          * However, we can't _write_ to any of these buckets yet - they might
2035          * have cached data in them, which is live until they're marked as
2036          * invalidated on disk:
2037          */
2038         if (invalidating_data) {
2039                 pr_debug("invalidating existing data");
2040                 set_bit(BCH_FS_HOLD_BTREE_WRITES, &c->flags);
2041         } else {
2042                 pr_debug("issuing discards");
2043                 allocator_start_issue_discards(c);
2044         }
2045
2046         /*
2047          * XXX: it's possible for this to deadlock waiting on journal reclaim,
2048          * since we're holding btree writes. What then?
2049          */
2050
2051         for_each_rw_member(ca, c, dev_iter) {
2052                 ret = bch2_invalidate_free_inc(c, ca, &journal_seq,
2053                                                ca->free[RESERVE_BTREE].size);
2054                 if (ret) {
2055                         percpu_ref_put(&ca->io_ref);
2056                         return ret;
2057                 }
2058         }
2059
2060         if (invalidating_data) {
2061                 pr_debug("flushing journal");
2062
2063                 ret = bch2_journal_flush_seq(&c->journal, journal_seq);
2064                 if (ret)
2065                         return ret;
2066
2067                 pr_debug("issuing discards");
2068                 allocator_start_issue_discards(c);
2069         }
2070
2071         for_each_rw_member(ca, c, dev_iter)
2072                 while (ca->nr_invalidated) {
2073                         BUG_ON(!fifo_pop(&ca->free_inc, bu));
2074                         ca->nr_invalidated--;
2075                 }
2076
2077         set_bit(BCH_FS_ALLOCATOR_STARTED, &c->flags);
2078
2079         /* now flush dirty btree nodes: */
2080         if (invalidating_data) {
2081                 struct bucket_table *tbl;
2082                 struct rhash_head *pos;
2083                 struct btree *b;
2084                 bool flush_updates;
2085                 size_t nr_pending_updates;
2086
2087                 clear_bit(BCH_FS_HOLD_BTREE_WRITES, &c->flags);
2088 again:
2089                 pr_debug("flushing dirty btree nodes");
2090                 cond_resched();
2091
2092                 flush_updates = false;
2093                 nr_pending_updates = bch2_btree_interior_updates_nr_pending(c);
2094
2095
2096                 rcu_read_lock();
2097                 for_each_cached_btree(b, c, tbl, i, pos)
2098                         if (btree_node_dirty(b) && (!b->written || b->level)) {
2099                                 if (btree_node_may_write(b)) {
2100                                         rcu_read_unlock();
2101                                         six_lock_read(&b->lock);
2102                                         bch2_btree_node_write(c, b, SIX_LOCK_read);
2103                                         six_unlock_read(&b->lock);
2104                                         goto again;
2105                                 } else {
2106                                         flush_updates = true;
2107                                 }
2108                         }
2109                 rcu_read_unlock();
2110
2111                 /*
2112                  * This is ugly, but it's needed to flush btree node writes
2113                  * without spinning...
2114                  */
2115                 if (flush_updates) {
2116                         closure_wait_event(&c->btree_interior_update_wait,
2117                                 bch2_btree_interior_updates_nr_pending(c) <
2118                                 nr_pending_updates);
2119                         goto again;
2120                 }
2121         }
2122
2123         return 0;
2124 }
2125
2126 int bch2_fs_allocator_start(struct bch_fs *c)
2127 {
2128         struct bch_dev *ca;
2129         unsigned i;
2130         int ret;
2131
2132         down_read(&c->gc_lock);
2133         ret = __bch2_fs_allocator_start(c);
2134         up_read(&c->gc_lock);
2135
2136         if (ret)
2137                 return ret;
2138
2139         for_each_rw_member(ca, c, i) {
2140                 ret = bch2_dev_allocator_start(ca);
2141                 if (ret) {
2142                         percpu_ref_put(&ca->io_ref);
2143                         return ret;
2144                 }
2145         }
2146
2147         return bch2_alloc_write(c);
2148 }
2149
2150 void bch2_fs_allocator_init(struct bch_fs *c)
2151 {
2152         struct open_bucket *ob;
2153         struct write_point *wp;
2154
2155         mutex_init(&c->write_points_hash_lock);
2156         spin_lock_init(&c->freelist_lock);
2157         bch2_bucket_clock_init(c, READ);
2158         bch2_bucket_clock_init(c, WRITE);
2159
2160         /* open bucket 0 is a sentinal NULL: */
2161         spin_lock_init(&c->open_buckets[0].lock);
2162
2163         for (ob = c->open_buckets + 1;
2164              ob < c->open_buckets + ARRAY_SIZE(c->open_buckets); ob++) {
2165                 spin_lock_init(&ob->lock);
2166                 c->open_buckets_nr_free++;
2167
2168                 ob->freelist = c->open_buckets_freelist;
2169                 c->open_buckets_freelist = ob - c->open_buckets;
2170         }
2171
2172         writepoint_init(&c->btree_write_point, BCH_DATA_BTREE);
2173         writepoint_init(&c->rebalance_write_point, BCH_DATA_USER);
2174
2175         for (wp = c->write_points;
2176              wp < c->write_points + ARRAY_SIZE(c->write_points); wp++) {
2177                 writepoint_init(wp, BCH_DATA_USER);
2178
2179                 wp->last_used   = sched_clock();
2180                 wp->write_point = (unsigned long) wp;
2181                 hlist_add_head_rcu(&wp->node, writepoint_hash(c, wp->write_point));
2182         }
2183
2184         c->pd_controllers_update_seconds = 5;
2185         INIT_DELAYED_WORK(&c->pd_controllers_update, pd_controllers_update);
2186 }