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 "btree_cache.h"
   6 #include "btree_io.h"
   7 #include "btree_key_cache.h"
   8 #include "btree_update.h"
   9 #include "btree_update_interior.h"
  10 #include "btree_gc.h"
  11 #include "buckets.h"
  12 #include "clock.h"
  13 #include "debug.h"
  14 #include "ec.h"
  15 #include "error.h"
  16 #include "recovery.h"
  17
  18 #include <linux/kthread.h>
  19 #include <linux/math64.h>
  20 #include <linux/random.h>
  21 #include <linux/rculist.h>
  22 #include <linux/rcupdate.h>
  23 #include <linux/sched/task.h>
  24 #include <linux/sort.h>
  25 #include <trace/events/bcachefs.h>
  26
  27 static const char * const bch2_alloc_field_names[] = {
  28 #define x(name, bytes) #name,
  29         BCH_ALLOC_FIELDS()
  30 #undef x
  31         NULL
  32 };
  33
  34 static void bch2_recalc_oldest_io(struct bch_fs *, struct bch_dev *, int);
  35
  36 /* Ratelimiting/PD controllers */
  37
  38 static void pd_controllers_update(struct work_struct *work)
  39 {
  40         struct bch_fs *c = container_of(to_delayed_work(work),
  41                                            struct bch_fs,
  42                                            pd_controllers_update);
  43         struct bch_dev *ca;
  44         s64 free = 0, fragmented = 0;
  45         unsigned i;
  46
  47         for_each_member_device(ca, c, i) {
  48                 struct bch_dev_usage stats = bch2_dev_usage_read(ca);
  49
  50                 free += bucket_to_sector(ca,
  51                                 __dev_buckets_free(ca, stats)) << 9;
  52                 /*
  53                  * Bytes of internal fragmentation, which can be
  54                  * reclaimed by copy GC
  55                  */
  56                 fragmented += max_t(s64, 0, (bucket_to_sector(ca,
  57                                         stats.buckets[BCH_DATA_user] +
  58                                         stats.buckets[BCH_DATA_cached]) -
  59                                   (stats.sectors[BCH_DATA_user] +
  60                                    stats.sectors[BCH_DATA_cached])) << 9);
  61         }
  62
  63         bch2_pd_controller_update(&c->copygc_pd, free, fragmented, -1);
  64         schedule_delayed_work(&c->pd_controllers_update,
  65                               c->pd_controllers_update_seconds * HZ);
  66 }
  67
  68 /* Persistent alloc info: */
  69
  70 static inline u64 get_alloc_field(const struct bch_alloc *a,
  71                                   const void **p, unsigned field)
  72 {
  73         unsigned bytes = BCH_ALLOC_FIELD_BYTES[field];
  74         u64 v;
  75
  76         if (!(a->fields & (1 << field)))
  77                 return 0;
  78
  79         switch (bytes) {
  80         case 1:
  81                 v = *((const u8 *) *p);
  82                 break;
  83         case 2:
  84                 v = le16_to_cpup(*p);
  85                 break;
  86         case 4:
  87                 v = le32_to_cpup(*p);
  88                 break;
  89         case 8:
  90                 v = le64_to_cpup(*p);
  91                 break;
  92         default:
  93                 BUG();
  94         }
  95
  96         *p += bytes;
  97         return v;
  98 }
  99
 100 static inline void put_alloc_field(struct bkey_i_alloc *a, void **p,
 101                                    unsigned field, u64 v)
 102 {
 103         unsigned bytes = BCH_ALLOC_FIELD_BYTES[field];
 104
 105         if (!v)
 106                 return;
 107
 108         a->v.fields |= 1 << field;
 109
 110         switch (bytes) {
 111         case 1:
 112                 *((u8 *) *p) = v;
 113                 break;
 114         case 2:
 115                 *((__le16 *) *p) = cpu_to_le16(v);
 116                 break;
 117         case 4:
 118                 *((__le32 *) *p) = cpu_to_le32(v);
 119                 break;
 120         case 8:
 121                 *((__le64 *) *p) = cpu_to_le64(v);
 122                 break;
 123         default:
 124                 BUG();
 125         }
 126
 127         *p += bytes;
 128 }
 129
 130 struct bkey_alloc_unpacked bch2_alloc_unpack(struct bkey_s_c k)
 131 {
 132         struct bkey_alloc_unpacked ret = { .gen = 0 };
 133
 134         if (k.k->type == KEY_TYPE_alloc) {
 135                 const struct bch_alloc *a = bkey_s_c_to_alloc(k).v;
 136                 const void *d = a->data;
 137                 unsigned idx = 0;
 138
 139                 ret.gen = a->gen;
 140
 141 #define x(_name, _bits) ret._name = get_alloc_field(a, &d, idx++);
 142                 BCH_ALLOC_FIELDS()
 143 #undef  x
 144         }
 145         return ret;
 146 }
 147
 148 void bch2_alloc_pack(struct bkey_i_alloc *dst,
 149                      const struct bkey_alloc_unpacked src)
 150 {
 151         unsigned idx = 0;
 152         void *d = dst->v.data;
 153         unsigned bytes;
 154
 155         dst->v.fields   = 0;
 156         dst->v.gen      = src.gen;
 157
 158 #define x(_name, _bits) put_alloc_field(dst, &d, idx++, src._name);
 159         BCH_ALLOC_FIELDS()
 160 #undef  x
 161
 162         bytes = (void *) d - (void *) &dst->v;
 163         set_bkey_val_bytes(&dst->k, bytes);
 164         memset_u64s_tail(&dst->v, 0, bytes);
 165 }
 166
 167 static unsigned bch_alloc_val_u64s(const struct bch_alloc *a)
 168 {
 169         unsigned i, bytes = offsetof(struct bch_alloc, data);
 170
 171         for (i = 0; i < ARRAY_SIZE(BCH_ALLOC_FIELD_BYTES); i++)
 172                 if (a->fields & (1 << i))
 173                         bytes += BCH_ALLOC_FIELD_BYTES[i];
 174
 175         return DIV_ROUND_UP(bytes, sizeof(u64));
 176 }
 177
 178 const char *bch2_alloc_invalid(const struct bch_fs *c, struct bkey_s_c k)
 179 {
 180         struct bkey_s_c_alloc a = bkey_s_c_to_alloc(k);
 181
 182         if (k.k->p.inode >= c->sb.nr_devices ||
 183             !c->devs[k.k->p.inode])
 184                 return "invalid device";
 185
 186         /* allow for unknown fields */
 187         if (bkey_val_u64s(a.k) < bch_alloc_val_u64s(a.v))
 188                 return "incorrect value size";
 189
 190         return NULL;
 191 }
 192
 193 void bch2_alloc_to_text(struct printbuf *out, struct bch_fs *c,
 194                         struct bkey_s_c k)
 195 {
 196         struct bkey_s_c_alloc a = bkey_s_c_to_alloc(k);
 197         const void *d = a.v->data;
 198         unsigned i;
 199
 200         pr_buf(out, "gen %u", a.v->gen);
 201
 202         for (i = 0; i < BCH_ALLOC_FIELD_NR; i++)
 203                 if (a.v->fields & (1 << i))
 204                         pr_buf(out, " %s %llu",
 205                                bch2_alloc_field_names[i],
 206                                get_alloc_field(a.v, &d, i));
 207 }
 208
 209 static int bch2_alloc_read_fn(struct bch_fs *c, enum btree_id id,
 210                               unsigned level, struct bkey_s_c k)
 211 {
 212         struct bch_dev *ca;
 213         struct bucket *g;
 214         struct bkey_alloc_unpacked u;
 215
 216         if (level || k.k->type != KEY_TYPE_alloc)
 217                 return 0;
 218
 219         ca = bch_dev_bkey_exists(c, k.k->p.inode);
 220         g = __bucket(ca, k.k->p.offset, 0);
 221         u = bch2_alloc_unpack(k);
 222
 223         g->_mark.gen            = u.gen;
 224         g->_mark.data_type      = u.data_type;
 225         g->_mark.dirty_sectors  = u.dirty_sectors;
 226         g->_mark.cached_sectors = u.cached_sectors;
 227         g->io_time[READ]        = u.read_time;
 228         g->io_time[WRITE]       = u.write_time;
 229         g->oldest_gen           = u.oldest_gen;
 230         g->gen_valid            = 1;
 231
 232         return 0;
 233 }
 234
 235 int bch2_alloc_read(struct bch_fs *c, struct journal_keys *journal_keys)
 236 {
 237         struct bch_dev *ca;
 238         unsigned i;
 239         int ret = 0;
 240
 241         down_read(&c->gc_lock);
 242         ret = bch2_btree_and_journal_walk(c, journal_keys, BTREE_ID_ALLOC,
 243                                           NULL, bch2_alloc_read_fn);
 244         up_read(&c->gc_lock);
 245
 246         if (ret) {
 247                 bch_err(c, "error reading alloc info: %i", ret);
 248                 return ret;
 249         }
 250
 251         percpu_down_write(&c->mark_lock);
 252         bch2_dev_usage_from_buckets(c);
 253         percpu_up_write(&c->mark_lock);
 254
 255         mutex_lock(&c->bucket_clock[READ].lock);
 256         for_each_member_device(ca, c, i) {
 257                 down_read(&ca->bucket_lock);
 258                 bch2_recalc_oldest_io(c, ca, READ);
 259                 up_read(&ca->bucket_lock);
 260         }
 261         mutex_unlock(&c->bucket_clock[READ].lock);
 262
 263         mutex_lock(&c->bucket_clock[WRITE].lock);
 264         for_each_member_device(ca, c, i) {
 265                 down_read(&ca->bucket_lock);
 266                 bch2_recalc_oldest_io(c, ca, WRITE);
 267                 up_read(&ca->bucket_lock);
 268         }
 269         mutex_unlock(&c->bucket_clock[WRITE].lock);
 270
 271         return 0;
 272 }
 273
 274 static int bch2_alloc_write_key(struct btree_trans *trans,
 275                                 struct btree_iter *iter,
 276                                 unsigned flags)
 277 {
 278         struct bch_fs *c = trans->c;
 279         struct bkey_s_c k;
 280         struct bch_dev *ca;
 281         struct bucket_array *ba;
 282         struct bucket *g;
 283         struct bucket_mark m;
 284         struct bkey_alloc_unpacked old_u, new_u;
 285         __BKEY_PADDED(k, 8) alloc_key; /* hack: */
 286         struct bkey_i_alloc *a;
 287         int ret;
 288 retry:
 289         bch2_trans_begin(trans);
 290
 291         ret = bch2_btree_key_cache_flush(trans,
 292                         BTREE_ID_ALLOC, iter->pos);
 293         if (ret)
 294                 goto err;
 295
 296         k = bch2_btree_iter_peek_slot(iter);
 297         ret = bkey_err(k);
 298         if (ret)
 299                 goto err;
 300
 301         old_u = bch2_alloc_unpack(k);
 302
 303         percpu_down_read(&c->mark_lock);
 304         ca      = bch_dev_bkey_exists(c, iter->pos.inode);
 305         ba      = bucket_array(ca);
 306
 307         g       = &ba->b[iter->pos.offset];
 308         m       = READ_ONCE(g->mark);
 309         new_u   = alloc_mem_to_key(g, m);
 310         percpu_up_read(&c->mark_lock);
 311
 312         if (!bkey_alloc_unpacked_cmp(old_u, new_u))
 313                 return 0;
 314
 315         a = bkey_alloc_init(&alloc_key.k);
 316         a->k.p = iter->pos;
 317         bch2_alloc_pack(a, new_u);
 318
 319         bch2_trans_update(trans, iter, &a->k_i,
 320                           BTREE_TRIGGER_NORUN);
 321         ret = bch2_trans_commit(trans, NULL, NULL,
 322                                 BTREE_INSERT_NOFAIL|
 323                                 BTREE_INSERT_USE_RESERVE|
 324                                 flags);
 325 err:
 326         if (ret == -EINTR)
 327                 goto retry;
 328         return ret;
 329 }
 330
 331 int bch2_dev_alloc_write(struct bch_fs *c, struct bch_dev *ca, unsigned flags)
 332 {
 333         struct btree_trans trans;
 334         struct btree_iter *iter;
 335         u64 first_bucket, nbuckets;
 336         int ret = 0;
 337
 338         percpu_down_read(&c->mark_lock);
 339         first_bucket    = bucket_array(ca)->first_bucket;
 340         nbuckets        = bucket_array(ca)->nbuckets;
 341         percpu_up_read(&c->mark_lock);
 342
 343         BUG_ON(BKEY_ALLOC_VAL_U64s_MAX > 8);
 344
 345         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 346
 347         iter = bch2_trans_get_iter(&trans, BTREE_ID_ALLOC,
 348                                    POS(ca->dev_idx, first_bucket),
 349                                    BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 350
 351         while (iter->pos.offset < nbuckets) {
 352                 bch2_trans_cond_resched(&trans);
 353
 354                 ret = bch2_alloc_write_key(&trans, iter, flags);
 355                 if (ret)
 356                         break;
 357                 bch2_btree_iter_next_slot(iter);
 358         }
 359
 360         bch2_trans_exit(&trans);
 361
 362         return ret;
 363 }
 364
 365 int bch2_alloc_write(struct bch_fs *c, unsigned flags)
 366 {
 367         struct bch_dev *ca;
 368         unsigned i;
 369         int ret = 0;
 370
 371         for_each_rw_member(ca, c, i) {
 372                 bch2_dev_alloc_write(c, ca, flags);
 373                 if (ret) {
 374                         percpu_ref_put(&ca->io_ref);
 375                         break;
 376                 }
 377         }
 378
 379         return ret;
 380 }
 381
 382 /* Bucket IO clocks: */
 383
 384 static void bch2_recalc_oldest_io(struct bch_fs *c, struct bch_dev *ca, int rw)
 385 {
 386         struct bucket_clock *clock = &c->bucket_clock[rw];
 387         struct bucket_array *buckets = bucket_array(ca);
 388         struct bucket *g;
 389         u16 max_last_io = 0;
 390         unsigned i;
 391
 392         lockdep_assert_held(&c->bucket_clock[rw].lock);
 393
 394         /* Recalculate max_last_io for this device: */
 395         for_each_bucket(g, buckets)
 396                 max_last_io = max(max_last_io, bucket_last_io(c, g, rw));
 397
 398         ca->max_last_bucket_io[rw] = max_last_io;
 399
 400         /* Recalculate global max_last_io: */
 401         max_last_io = 0;
 402
 403         for_each_member_device(ca, c, i)
 404                 max_last_io = max(max_last_io, ca->max_last_bucket_io[rw]);
 405
 406         clock->max_last_io = max_last_io;
 407 }
 408
 409 static void bch2_rescale_bucket_io_times(struct bch_fs *c, int rw)
 410 {
 411         struct bucket_clock *clock = &c->bucket_clock[rw];
 412         struct bucket_array *buckets;
 413         struct bch_dev *ca;
 414         struct bucket *g;
 415         unsigned i;
 416
 417         trace_rescale_prios(c);
 418
 419         for_each_member_device(ca, c, i) {
 420                 down_read(&ca->bucket_lock);
 421                 buckets = bucket_array(ca);
 422
 423                 for_each_bucket(g, buckets)
 424                         g->io_time[rw] = clock->hand -
 425                         bucket_last_io(c, g, rw) / 2;
 426
 427                 bch2_recalc_oldest_io(c, ca, rw);
 428
 429                 up_read(&ca->bucket_lock);
 430         }
 431 }
 432
 433 static inline u64 bucket_clock_freq(u64 capacity)
 434 {
 435         return max(capacity >> 10, 2028ULL);
 436 }
 437
 438 static void bch2_inc_clock_hand(struct io_timer *timer)
 439 {
 440         struct bucket_clock *clock = container_of(timer,
 441                                                 struct bucket_clock, rescale);
 442         struct bch_fs *c = container_of(clock,
 443                                         struct bch_fs, bucket_clock[clock->rw]);
 444         struct bch_dev *ca;
 445         u64 capacity;
 446         unsigned i;
 447
 448         mutex_lock(&clock->lock);
 449
 450         /* if clock cannot be advanced more, rescale prio */
 451         if (clock->max_last_io >= U16_MAX - 2)
 452                 bch2_rescale_bucket_io_times(c, clock->rw);
 453
 454         BUG_ON(clock->max_last_io >= U16_MAX - 2);
 455
 456         for_each_member_device(ca, c, i)
 457                 ca->max_last_bucket_io[clock->rw]++;
 458         clock->max_last_io++;
 459         clock->hand++;
 460
 461         mutex_unlock(&clock->lock);
 462
 463         capacity = READ_ONCE(c->capacity);
 464
 465         if (!capacity)
 466                 return;
 467
 468         /*
 469          * we only increment when 0.1% of the filesystem capacity has been read
 470          * or written too, this determines if it's time
 471          *
 472          * XXX: we shouldn't really be going off of the capacity of devices in
 473          * RW mode (that will be 0 when we're RO, yet we can still service
 474          * reads)
 475          */
 476         timer->expire += bucket_clock_freq(capacity);
 477
 478         bch2_io_timer_add(&c->io_clock[clock->rw], timer);
 479 }
 480
 481 static void bch2_bucket_clock_init(struct bch_fs *c, int rw)
 482 {
 483         struct bucket_clock *clock = &c->bucket_clock[rw];
 484
 485         clock->hand             = 1;
 486         clock->rw               = rw;
 487         clock->rescale.fn       = bch2_inc_clock_hand;
 488         clock->rescale.expire   = bucket_clock_freq(c->capacity);
 489         mutex_init(&clock->lock);
 490 }
 491
 492 int bch2_bucket_io_time_reset(struct btree_trans *trans, unsigned dev,
 493                               size_t bucket_nr, int rw)
 494 {
 495         struct bch_fs *c = trans->c;
 496         struct bch_dev *ca = bch_dev_bkey_exists(c, dev);
 497         struct btree_iter *iter;
 498         struct bucket *g;
 499         struct bkey_i_alloc *a;
 500         struct bkey_alloc_unpacked u;
 501         u16 *time;
 502         int ret = 0;
 503
 504         iter = bch2_trans_get_iter(trans, BTREE_ID_ALLOC, POS(dev, bucket_nr),
 505                                    BTREE_ITER_CACHED|
 506                                    BTREE_ITER_CACHED_NOFILL|
 507                                    BTREE_ITER_INTENT);
 508         if (IS_ERR(iter))
 509                 return PTR_ERR(iter);
 510
 511         a = bch2_trans_kmalloc(trans, BKEY_ALLOC_U64s_MAX * 8);
 512         ret = PTR_ERR_OR_ZERO(a);
 513         if (ret)
 514                 goto out;
 515
 516         percpu_down_read(&c->mark_lock);
 517         g = bucket(ca, bucket_nr);
 518         u = alloc_mem_to_key(g, READ_ONCE(g->mark));
 519         percpu_up_read(&c->mark_lock);
 520
 521         bkey_alloc_init(&a->k_i);
 522         a->k.p = iter->pos;
 523
 524         time = rw == READ ? &u.read_time : &u.write_time;
 525         if (*time == c->bucket_clock[rw].hand)
 526                 goto out;
 527
 528         *time = c->bucket_clock[rw].hand;
 529
 530         bch2_alloc_pack(a, u);
 531
 532         ret   = bch2_trans_update(trans, iter, &a->k_i, 0) ?:
 533                 bch2_trans_commit(trans, NULL, NULL, 0);
 534 out:
 535         bch2_trans_iter_put(trans, iter);
 536         return ret;
 537 }
 538
 539 /* Background allocator thread: */
 540
 541 /*
 542  * Scans for buckets to be invalidated, invalidates them, rewrites prios/gens
 543  * (marking them as invalidated on disk), then optionally issues discard
 544  * commands to the newly free buckets, then puts them on the various freelists.
 545  */
 546
 547 /**
 548  * wait_buckets_available - wait on reclaimable buckets
 549  *
 550  * If there aren't enough available buckets to fill up free_inc, wait until
 551  * there are.
 552  */
 553 static int wait_buckets_available(struct bch_fs *c, struct bch_dev *ca)
 554 {
 555         unsigned long gc_count = c->gc_count;
 556         u64 available;
 557         int ret = 0;
 558
 559         ca->allocator_state = ALLOCATOR_BLOCKED;
 560         closure_wake_up(&c->freelist_wait);
 561
 562         while (1) {
 563                 set_current_state(TASK_INTERRUPTIBLE);
 564                 if (kthread_should_stop()) {
 565                         ret = 1;
 566                         break;
 567                 }
 568
 569                 if (gc_count != c->gc_count)
 570                         ca->inc_gen_really_needs_gc = 0;
 571
 572                 available = max_t(s64, 0, dev_buckets_available(ca) -
 573                                   ca->inc_gen_really_needs_gc);
 574
 575                 if (available > fifo_free(&ca->free_inc) ||
 576                     (available &&
 577                      (!fifo_full(&ca->free[RESERVE_BTREE]) ||
 578                       !fifo_full(&ca->free[RESERVE_MOVINGGC]))))
 579                         break;
 580
 581                 up_read(&c->gc_lock);
 582                 schedule();
 583                 try_to_freeze();
 584                 down_read(&c->gc_lock);
 585         }
 586
 587         __set_current_state(TASK_RUNNING);
 588         ca->allocator_state = ALLOCATOR_RUNNING;
 589         closure_wake_up(&c->freelist_wait);
 590
 591         return ret;
 592 }
 593
 594 static bool bch2_can_invalidate_bucket(struct bch_dev *ca,
 595                                        size_t bucket,
 596                                        struct bucket_mark mark)
 597 {
 598         u8 gc_gen;
 599
 600         if (!is_available_bucket(mark))
 601                 return false;
 602
 603         if (ca->buckets_nouse &&
 604             test_bit(bucket, ca->buckets_nouse))
 605                 return false;
 606
 607         gc_gen = bucket_gc_gen(ca, bucket);
 608
 609         if (gc_gen >= BUCKET_GC_GEN_MAX / 2)
 610                 ca->inc_gen_needs_gc++;
 611
 612         if (gc_gen >= BUCKET_GC_GEN_MAX)
 613                 ca->inc_gen_really_needs_gc++;
 614
 615         return gc_gen < BUCKET_GC_GEN_MAX;
 616 }
 617
 618 /*
 619  * Determines what order we're going to reuse buckets, smallest bucket_key()
 620  * first.
 621  *
 622  *
 623  * - We take into account the read prio of the bucket, which gives us an
 624  *   indication of how hot the data is -- we scale the prio so that the prio
 625  *   farthest from the clock is worth 1/8th of the closest.
 626  *
 627  * - The number of sectors of cached data in the bucket, which gives us an
 628  *   indication of the cost in cache misses this eviction will cause.
 629  *
 630  * - If hotness * sectors used compares equal, we pick the bucket with the
 631  *   smallest bucket_gc_gen() - since incrementing the same bucket's generation
 632  *   number repeatedly forces us to run mark and sweep gc to avoid generation
 633  *   number wraparound.
 634  */
 635
 636 static unsigned long bucket_sort_key(struct bch_fs *c, struct bch_dev *ca,
 637                                      size_t b, struct bucket_mark m)
 638 {
 639         unsigned last_io = bucket_last_io(c, bucket(ca, b), READ);
 640         unsigned max_last_io = ca->max_last_bucket_io[READ];
 641
 642         /*
 643          * Time since last read, scaled to [0, 8) where larger value indicates
 644          * more recently read data:
 645          */
 646         unsigned long hotness = (max_last_io - last_io) * 7 / max_last_io;
 647
 648         /* How much we want to keep the data in this bucket: */
 649         unsigned long data_wantness =
 650                 (hotness + 1) * bucket_sectors_used(m);
 651
 652         unsigned long needs_journal_commit =
 653                 bucket_needs_journal_commit(m, c->journal.last_seq_ondisk);
 654
 655         return  (data_wantness << 9) |
 656                 (needs_journal_commit << 8) |
 657                 (bucket_gc_gen(ca, b) / 16);
 658 }
 659
 660 static inline int bucket_alloc_cmp(alloc_heap *h,
 661                                    struct alloc_heap_entry l,
 662                                    struct alloc_heap_entry r)
 663 {
 664         return  cmp_int(l.key, r.key) ?:
 665                 cmp_int(r.nr, l.nr) ?:
 666                 cmp_int(l.bucket, r.bucket);
 667 }
 668
 669 static inline int bucket_idx_cmp(const void *_l, const void *_r)
 670 {
 671         const struct alloc_heap_entry *l = _l, *r = _r;
 672
 673         return cmp_int(l->bucket, r->bucket);
 674 }
 675
 676 static void find_reclaimable_buckets_lru(struct bch_fs *c, struct bch_dev *ca)
 677 {
 678         struct bucket_array *buckets;
 679         struct alloc_heap_entry e = { 0 };
 680         size_t b, i, nr = 0;
 681
 682         ca->alloc_heap.used = 0;
 683
 684         mutex_lock(&c->bucket_clock[READ].lock);
 685         down_read(&ca->bucket_lock);
 686
 687         buckets = bucket_array(ca);
 688
 689         bch2_recalc_oldest_io(c, ca, READ);
 690
 691         /*
 692          * Find buckets with lowest read priority, by building a maxheap sorted
 693          * by read priority and repeatedly replacing the maximum element until
 694          * all buckets have been visited.
 695          */
 696         for (b = ca->mi.first_bucket; b < ca->mi.nbuckets; b++) {
 697                 struct bucket_mark m = READ_ONCE(buckets->b[b].mark);
 698                 unsigned long key = bucket_sort_key(c, ca, b, m);
 699
 700                 if (!bch2_can_invalidate_bucket(ca, b, m))
 701                         continue;
 702
 703                 if (e.nr && e.bucket + e.nr == b && e.key == key) {
 704                         e.nr++;
 705                 } else {
 706                         if (e.nr)
 707                                 heap_add_or_replace(&ca->alloc_heap, e,
 708                                         -bucket_alloc_cmp, NULL);
 709
 710                         e = (struct alloc_heap_entry) {
 711                                 .bucket = b,
 712                                 .nr     = 1,
 713                                 .key    = key,
 714                         };
 715                 }
 716
 717                 cond_resched();
 718         }
 719
 720         if (e.nr)
 721                 heap_add_or_replace(&ca->alloc_heap, e,
 722                                 -bucket_alloc_cmp, NULL);
 723
 724         for (i = 0; i < ca->alloc_heap.used; i++)
 725                 nr += ca->alloc_heap.data[i].nr;
 726
 727         while (nr - ca->alloc_heap.data[0].nr >= ALLOC_SCAN_BATCH(ca)) {
 728                 nr -= ca->alloc_heap.data[0].nr;
 729                 heap_pop(&ca->alloc_heap, e, -bucket_alloc_cmp, NULL);
 730         }
 731
 732         up_read(&ca->bucket_lock);
 733         mutex_unlock(&c->bucket_clock[READ].lock);
 734 }
 735
 736 static void find_reclaimable_buckets_fifo(struct bch_fs *c, struct bch_dev *ca)
 737 {
 738         struct bucket_array *buckets = bucket_array(ca);
 739         struct bucket_mark m;
 740         size_t b, start;
 741
 742         if (ca->fifo_last_bucket <  ca->mi.first_bucket ||
 743             ca->fifo_last_bucket >= ca->mi.nbuckets)
 744                 ca->fifo_last_bucket = ca->mi.first_bucket;
 745
 746         start = ca->fifo_last_bucket;
 747
 748         do {
 749                 ca->fifo_last_bucket++;
 750                 if (ca->fifo_last_bucket == ca->mi.nbuckets)
 751                         ca->fifo_last_bucket = ca->mi.first_bucket;
 752
 753                 b = ca->fifo_last_bucket;
 754                 m = READ_ONCE(buckets->b[b].mark);
 755
 756                 if (bch2_can_invalidate_bucket(ca, b, m)) {
 757                         struct alloc_heap_entry e = { .bucket = b, .nr = 1, };
 758
 759                         heap_add(&ca->alloc_heap, e, bucket_alloc_cmp, NULL);
 760                         if (heap_full(&ca->alloc_heap))
 761                                 break;
 762                 }
 763
 764                 cond_resched();
 765         } while (ca->fifo_last_bucket != start);
 766 }
 767
 768 static void find_reclaimable_buckets_random(struct bch_fs *c, struct bch_dev *ca)
 769 {
 770         struct bucket_array *buckets = bucket_array(ca);
 771         struct bucket_mark m;
 772         size_t checked, i;
 773
 774         for (checked = 0;
 775              checked < ca->mi.nbuckets / 2;
 776              checked++) {
 777                 size_t b = bch2_rand_range(ca->mi.nbuckets -
 778                                            ca->mi.first_bucket) +
 779                         ca->mi.first_bucket;
 780
 781                 m = READ_ONCE(buckets->b[b].mark);
 782
 783                 if (bch2_can_invalidate_bucket(ca, b, m)) {
 784                         struct alloc_heap_entry e = { .bucket = b, .nr = 1, };
 785
 786                         heap_add(&ca->alloc_heap, e, bucket_alloc_cmp, NULL);
 787                         if (heap_full(&ca->alloc_heap))
 788                                 break;
 789                 }
 790
 791                 cond_resched();
 792         }
 793
 794         sort(ca->alloc_heap.data,
 795              ca->alloc_heap.used,
 796              sizeof(ca->alloc_heap.data[0]),
 797              bucket_idx_cmp, NULL);
 798
 799         /* remove duplicates: */
 800         for (i = 0; i + 1 < ca->alloc_heap.used; i++)
 801                 if (ca->alloc_heap.data[i].bucket ==
 802                     ca->alloc_heap.data[i + 1].bucket)
 803                         ca->alloc_heap.data[i].nr = 0;
 804 }
 805
 806 static size_t find_reclaimable_buckets(struct bch_fs *c, struct bch_dev *ca)
 807 {
 808         size_t i, nr = 0;
 809
 810         ca->inc_gen_needs_gc                    = 0;
 811
 812         switch (ca->mi.replacement) {
 813         case CACHE_REPLACEMENT_LRU:
 814                 find_reclaimable_buckets_lru(c, ca);
 815                 break;
 816         case CACHE_REPLACEMENT_FIFO:
 817                 find_reclaimable_buckets_fifo(c, ca);
 818                 break;
 819         case CACHE_REPLACEMENT_RANDOM:
 820                 find_reclaimable_buckets_random(c, ca);
 821                 break;
 822         }
 823
 824         heap_resort(&ca->alloc_heap, bucket_alloc_cmp, NULL);
 825
 826         for (i = 0; i < ca->alloc_heap.used; i++)
 827                 nr += ca->alloc_heap.data[i].nr;
 828
 829         return nr;
 830 }
 831
 832 static inline long next_alloc_bucket(struct bch_dev *ca)
 833 {
 834         struct alloc_heap_entry e, *top = ca->alloc_heap.data;
 835
 836         while (ca->alloc_heap.used) {
 837                 if (top->nr) {
 838                         size_t b = top->bucket;
 839
 840                         top->bucket++;
 841                         top->nr--;
 842                         return b;
 843                 }
 844
 845                 heap_pop(&ca->alloc_heap, e, bucket_alloc_cmp, NULL);
 846         }
 847
 848         return -1;
 849 }
 850
 851 /*
 852  * returns sequence number of most recent journal entry that updated this
 853  * bucket:
 854  */
 855 static u64 bucket_journal_seq(struct bch_fs *c, struct bucket_mark m)
 856 {
 857         if (m.journal_seq_valid) {
 858                 u64 journal_seq = atomic64_read(&c->journal.seq);
 859                 u64 bucket_seq  = journal_seq;
 860
 861                 bucket_seq &= ~((u64) U16_MAX);
 862                 bucket_seq |= m.journal_seq;
 863
 864                 if (bucket_seq > journal_seq)
 865                         bucket_seq -= 1 << 16;
 866
 867                 return bucket_seq;
 868         } else {
 869                 return 0;
 870         }
 871 }
 872
 873 static int bch2_invalidate_one_bucket2(struct btree_trans *trans,
 874                                        struct bch_dev *ca,
 875                                        struct btree_iter *iter,
 876                                        u64 *journal_seq, unsigned flags)
 877 {
 878 #if 0
 879         __BKEY_PADDED(k, BKEY_ALLOC_VAL_U64s_MAX) alloc_key;
 880 #else
 881         /* hack: */
 882         __BKEY_PADDED(k, 8) alloc_key;
 883 #endif
 884         struct bch_fs *c = trans->c;
 885         struct bkey_i_alloc *a;
 886         struct bkey_alloc_unpacked u;
 887         struct bucket *g;
 888         struct bucket_mark m;
 889         bool invalidating_cached_data;
 890         size_t b;
 891         int ret = 0;
 892
 893         BUG_ON(!ca->alloc_heap.used ||
 894                !ca->alloc_heap.data[0].nr);
 895         b = ca->alloc_heap.data[0].bucket;
 896
 897         /* first, put on free_inc and mark as owned by allocator: */
 898         percpu_down_read(&c->mark_lock);
 899         spin_lock(&c->freelist_lock);
 900
 901         verify_not_on_freelist(c, ca, b);
 902
 903         BUG_ON(!fifo_push(&ca->free_inc, b));
 904
 905         g = bucket(ca, b);
 906         m = READ_ONCE(g->mark);
 907
 908         invalidating_cached_data = m.cached_sectors != 0;
 909
 910         /*
 911          * If we're not invalidating cached data, we only increment the bucket
 912          * gen in memory here, the incremented gen will be updated in the btree
 913          * by bch2_trans_mark_pointer():
 914          */
 915
 916         if (!invalidating_cached_data)
 917                 bch2_invalidate_bucket(c, ca, b, &m);
 918         else
 919                 bch2_mark_alloc_bucket(c, ca, b, true, gc_pos_alloc(c, NULL), 0);
 920
 921         spin_unlock(&c->freelist_lock);
 922         percpu_up_read(&c->mark_lock);
 923
 924         if (!invalidating_cached_data)
 925                 goto out;
 926
 927         /*
 928          * If the read-only path is trying to shut down, we can't be generating
 929          * new btree updates:
 930          */
 931         if (test_bit(BCH_FS_ALLOCATOR_STOPPING, &c->flags)) {
 932                 ret = 1;
 933                 goto out;
 934         }
 935
 936         BUG_ON(BKEY_ALLOC_VAL_U64s_MAX > 8);
 937
 938         bch2_btree_iter_set_pos(iter, POS(ca->dev_idx, b));
 939 retry:
 940         ret = bch2_btree_iter_traverse(iter);
 941         if (ret)
 942                 return ret;
 943
 944         percpu_down_read(&c->mark_lock);
 945         g = bucket(ca, iter->pos.offset);
 946         m = READ_ONCE(g->mark);
 947         u = alloc_mem_to_key(g, m);
 948
 949         percpu_up_read(&c->mark_lock);
 950
 951         invalidating_cached_data = u.cached_sectors != 0;
 952
 953         u.gen++;
 954         u.data_type     = 0;
 955         u.dirty_sectors = 0;
 956         u.cached_sectors = 0;
 957         u.read_time     = c->bucket_clock[READ].hand;
 958         u.write_time    = c->bucket_clock[WRITE].hand;
 959
 960         a = bkey_alloc_init(&alloc_key.k);
 961         a->k.p = iter->pos;
 962         bch2_alloc_pack(a, u);
 963
 964         bch2_trans_update(trans, iter, &a->k_i,
 965                           BTREE_TRIGGER_BUCKET_INVALIDATE);
 966
 967         /*
 968          * XXX:
 969          * when using deferred btree updates, we have journal reclaim doing
 970          * btree updates and thus requiring the allocator to make forward
 971          * progress, and here the allocator is requiring space in the journal -
 972          * so we need a journal pre-reservation:
 973          */
 974         ret = bch2_trans_commit(trans, NULL,
 975                                 invalidating_cached_data ? journal_seq : NULL,
 976                                 BTREE_INSERT_NOUNLOCK|
 977                                 BTREE_INSERT_NOCHECK_RW|
 978                                 BTREE_INSERT_NOFAIL|
 979                                 BTREE_INSERT_USE_RESERVE|
 980                                 BTREE_INSERT_USE_ALLOC_RESERVE|
 981                                 flags);
 982         if (ret == -EINTR)
 983                 goto retry;
 984 out:
 985         if (!ret) {
 986                 /* remove from alloc_heap: */
 987                 struct alloc_heap_entry e, *top = ca->alloc_heap.data;
 988
 989                 top->bucket++;
 990                 top->nr--;
 991
 992                 if (!top->nr)
 993                         heap_pop(&ca->alloc_heap, e, bucket_alloc_cmp, NULL);
 994
 995                 /*
 996                  * Make sure we flush the last journal entry that updated this
 997                  * bucket (i.e. deleting the last reference) before writing to
 998                  * this bucket again:
 999                  */
1000                 *journal_seq = max(*journal_seq, bucket_journal_seq(c, m));
1001         } else {
1002                 size_t b2;
1003
1004                 /* remove from free_inc: */
1005                 percpu_down_read(&c->mark_lock);
1006                 spin_lock(&c->freelist_lock);
1007
1008                 bch2_mark_alloc_bucket(c, ca, b, false,
1009                                        gc_pos_alloc(c, NULL), 0);
1010
1011                 BUG_ON(!fifo_pop_back(&ca->free_inc, b2));
1012                 BUG_ON(b != b2);
1013
1014                 spin_unlock(&c->freelist_lock);
1015                 percpu_up_read(&c->mark_lock);
1016         }
1017
1018         return ret < 0 ? ret : 0;
1019 }
1020
1021 /*
1022  * Pull buckets off ca->alloc_heap, invalidate them, move them to ca->free_inc:
1023  */
1024 static int bch2_invalidate_buckets(struct bch_fs *c, struct bch_dev *ca)
1025 {
1026         struct btree_trans trans;
1027         struct btree_iter *iter;
1028         u64 journal_seq = 0;
1029         int ret = 0;
1030
1031         bch2_trans_init(&trans, c, 0, 0);
1032
1033         iter = bch2_trans_get_iter(&trans, BTREE_ID_ALLOC,
1034                                    POS(ca->dev_idx, 0),
1035                                    BTREE_ITER_CACHED|
1036                                    BTREE_ITER_CACHED_NOFILL|
1037                                    BTREE_ITER_INTENT);
1038
1039         /* Only use nowait if we've already invalidated at least one bucket: */
1040         while (!ret &&
1041                !fifo_full(&ca->free_inc) &&
1042                ca->alloc_heap.used)
1043                 ret = bch2_invalidate_one_bucket2(&trans, ca, iter, &journal_seq,
1044                                 BTREE_INSERT_GC_LOCK_HELD|
1045                                 (!fifo_empty(&ca->free_inc)
1046                                  ? BTREE_INSERT_NOWAIT : 0));
1047
1048         bch2_trans_exit(&trans);
1049
1050         /* If we used NOWAIT, don't return the error: */
1051         if (!fifo_empty(&ca->free_inc))
1052                 ret = 0;
1053         if (ret) {
1054                 bch_err(ca, "error invalidating buckets: %i", ret);
1055                 return ret;
1056         }
1057
1058         if (journal_seq)
1059                 ret = bch2_journal_flush_seq(&c->journal, journal_seq);
1060         if (ret) {
1061                 bch_err(ca, "journal error: %i", ret);
1062                 return ret;
1063         }
1064
1065         return 0;
1066 }
1067
1068 static int push_invalidated_bucket(struct bch_fs *c, struct bch_dev *ca, size_t bucket)
1069 {
1070         unsigned i;
1071         int ret = 0;
1072
1073         while (1) {
1074                 set_current_state(TASK_INTERRUPTIBLE);
1075
1076                 spin_lock(&c->freelist_lock);
1077                 for (i = 0; i < RESERVE_NR; i++) {
1078
1079                         /*
1080                          * Don't strand buckets on the copygc freelist until
1081                          * after recovery is finished:
1082                          */
1083                         if (!test_bit(BCH_FS_STARTED, &c->flags) &&
1084                             i == RESERVE_MOVINGGC)
1085                                 continue;
1086
1087                         if (fifo_push(&ca->free[i], bucket)) {
1088                                 fifo_pop(&ca->free_inc, bucket);
1089
1090                                 closure_wake_up(&c->freelist_wait);
1091                                 ca->allocator_state = ALLOCATOR_RUNNING;
1092
1093                                 spin_unlock(&c->freelist_lock);
1094                                 goto out;
1095                         }
1096                 }
1097
1098                 if (ca->allocator_state != ALLOCATOR_BLOCKED_FULL) {
1099                         ca->allocator_state = ALLOCATOR_BLOCKED_FULL;
1100                         closure_wake_up(&c->freelist_wait);
1101                 }
1102
1103                 spin_unlock(&c->freelist_lock);
1104
1105                 if ((current->flags & PF_KTHREAD) &&
1106                     kthread_should_stop()) {
1107                         ret = 1;
1108                         break;
1109                 }
1110
1111                 schedule();
1112                 try_to_freeze();
1113         }
1114 out:
1115         __set_current_state(TASK_RUNNING);
1116         return ret;
1117 }
1118
1119 /*
1120  * Pulls buckets off free_inc, discards them (if enabled), then adds them to
1121  * freelists, waiting until there's room if necessary:
1122  */
1123 static int discard_invalidated_buckets(struct bch_fs *c, struct bch_dev *ca)
1124 {
1125         while (!fifo_empty(&ca->free_inc)) {
1126                 size_t bucket = fifo_peek(&ca->free_inc);
1127
1128                 if (ca->mi.discard &&
1129                     blk_queue_discard(bdev_get_queue(ca->disk_sb.bdev)))
1130                         blkdev_issue_discard(ca->disk_sb.bdev,
1131                                              bucket_to_sector(ca, bucket),
1132                                              ca->mi.bucket_size, GFP_NOIO, 0);
1133
1134                 if (push_invalidated_bucket(c, ca, bucket))
1135                         return 1;
1136         }
1137
1138         return 0;
1139 }
1140
1141 /**
1142  * bch_allocator_thread - move buckets from free_inc to reserves
1143  *
1144  * The free_inc FIFO is populated by find_reclaimable_buckets(), and
1145  * the reserves are depleted by bucket allocation. When we run out
1146  * of free_inc, try to invalidate some buckets and write out
1147  * prios and gens.
1148  */
1149 static int bch2_allocator_thread(void *arg)
1150 {
1151         struct bch_dev *ca = arg;
1152         struct bch_fs *c = ca->fs;
1153         size_t nr;
1154         int ret;
1155
1156         set_freezable();
1157         ca->allocator_state = ALLOCATOR_RUNNING;
1158
1159         while (1) {
1160                 cond_resched();
1161                 if (kthread_should_stop())
1162                         break;
1163
1164                 pr_debug("discarding %zu invalidated buckets",
1165                          fifo_used(&ca->free_inc));
1166
1167                 ret = discard_invalidated_buckets(c, ca);
1168                 if (ret)
1169                         goto stop;
1170
1171                 down_read(&c->gc_lock);
1172
1173                 ret = bch2_invalidate_buckets(c, ca);
1174                 if (ret) {
1175                         up_read(&c->gc_lock);
1176                         goto stop;
1177                 }
1178
1179                 if (!fifo_empty(&ca->free_inc)) {
1180                         up_read(&c->gc_lock);
1181                         continue;
1182                 }
1183
1184                 pr_debug("free_inc now empty");
1185
1186                 do {
1187                         /*
1188                          * Find some buckets that we can invalidate, either
1189                          * they're completely unused, or only contain clean data
1190                          * that's been written back to the backing device or
1191                          * another cache tier
1192                          */
1193
1194                         pr_debug("scanning for reclaimable buckets");
1195
1196                         nr = find_reclaimable_buckets(c, ca);
1197
1198                         pr_debug("found %zu buckets", nr);
1199
1200                         trace_alloc_batch(ca, nr, ca->alloc_heap.size);
1201
1202                         if ((ca->inc_gen_needs_gc >= ALLOC_SCAN_BATCH(ca) ||
1203                              ca->inc_gen_really_needs_gc) &&
1204                             c->gc_thread) {
1205                                 atomic_inc(&c->kick_gc);
1206                                 wake_up_process(c->gc_thread);
1207                         }
1208
1209                         /*
1210                          * If we found any buckets, we have to invalidate them
1211                          * before we scan for more - but if we didn't find very
1212                          * many we may want to wait on more buckets being
1213                          * available so we don't spin:
1214                          */
1215                         if (!nr ||
1216                             (nr < ALLOC_SCAN_BATCH(ca) &&
1217                              !fifo_empty(&ca->free[RESERVE_NONE]))) {
1218                                 ret = wait_buckets_available(c, ca);
1219                                 if (ret) {
1220                                         up_read(&c->gc_lock);
1221                                         goto stop;
1222                                 }
1223                         }
1224                 } while (!nr);
1225
1226                 up_read(&c->gc_lock);
1227
1228                 pr_debug("%zu buckets to invalidate", nr);
1229
1230                 /*
1231                  * alloc_heap is now full of newly-invalidated buckets: next,
1232                  * write out the new bucket gens:
1233                  */
1234         }
1235
1236 stop:
1237         pr_debug("alloc thread stopping (ret %i)", ret);
1238         ca->allocator_state = ALLOCATOR_STOPPED;
1239         closure_wake_up(&c->freelist_wait);
1240         return 0;
1241 }
1242
1243 /* Startup/shutdown (ro/rw): */
1244
1245 void bch2_recalc_capacity(struct bch_fs *c)
1246 {
1247         struct bch_dev *ca;
1248         u64 capacity = 0, reserved_sectors = 0, gc_reserve, copygc_threshold = 0;
1249         unsigned bucket_size_max = 0;
1250         unsigned long ra_pages = 0;
1251         unsigned i, j;
1252
1253         lockdep_assert_held(&c->state_lock);
1254
1255         for_each_online_member(ca, c, i) {
1256                 struct backing_dev_info *bdi = ca->disk_sb.bdev->bd_bdi;
1257
1258                 ra_pages += bdi->ra_pages;
1259         }
1260
1261         bch2_set_ra_pages(c, ra_pages);
1262
1263         for_each_rw_member(ca, c, i) {
1264                 u64 dev_reserve = 0;
1265
1266                 /*
1267                  * We need to reserve buckets (from the number
1268                  * of currently available buckets) against
1269                  * foreground writes so that mainly copygc can
1270                  * make forward progress.
1271                  *
1272                  * We need enough to refill the various reserves
1273                  * from scratch - copygc will use its entire
1274                  * reserve all at once, then run against when
1275                  * its reserve is refilled (from the formerly
1276                  * available buckets).
1277                  *
1278                  * This reserve is just used when considering if
1279                  * allocations for foreground writes must wait -
1280                  * not -ENOSPC calculations.
1281                  */
1282                 for (j = 0; j < RESERVE_NONE; j++)
1283                         dev_reserve += ca->free[j].size;
1284
1285                 dev_reserve += 1;       /* btree write point */
1286                 dev_reserve += 1;       /* copygc write point */
1287                 dev_reserve += 1;       /* rebalance write point */
1288
1289                 dev_reserve *= ca->mi.bucket_size;
1290
1291                 copygc_threshold += dev_reserve;
1292
1293                 capacity += bucket_to_sector(ca, ca->mi.nbuckets -
1294                                              ca->mi.first_bucket);
1295
1296                 reserved_sectors += dev_reserve * 2;
1297
1298                 bucket_size_max = max_t(unsigned, bucket_size_max,
1299                                         ca->mi.bucket_size);
1300         }
1301
1302         gc_reserve = c->opts.gc_reserve_bytes
1303                 ? c->opts.gc_reserve_bytes >> 9
1304                 : div64_u64(capacity * c->opts.gc_reserve_percent, 100);
1305
1306         reserved_sectors = max(gc_reserve, reserved_sectors);
1307
1308         reserved_sectors = min(reserved_sectors, capacity);
1309
1310         c->copygc_threshold = copygc_threshold;
1311         c->capacity = capacity - reserved_sectors;
1312
1313         c->bucket_size_max = bucket_size_max;
1314
1315         /* Wake up case someone was waiting for buckets */
1316         closure_wake_up(&c->freelist_wait);
1317 }
1318
1319 static bool bch2_dev_has_open_write_point(struct bch_fs *c, struct bch_dev *ca)
1320 {
1321         struct open_bucket *ob;
1322         bool ret = false;
1323
1324         for (ob = c->open_buckets;
1325              ob < c->open_buckets + ARRAY_SIZE(c->open_buckets);
1326              ob++) {
1327                 spin_lock(&ob->lock);
1328                 if (ob->valid && !ob->on_partial_list &&
1329                     ob->ptr.dev == ca->dev_idx)
1330                         ret = true;
1331                 spin_unlock(&ob->lock);
1332         }
1333
1334         return ret;
1335 }
1336
1337 /* device goes ro: */
1338 void bch2_dev_allocator_remove(struct bch_fs *c, struct bch_dev *ca)
1339 {
1340         unsigned i;
1341
1342         BUG_ON(ca->alloc_thread);
1343
1344         /* First, remove device from allocation groups: */
1345
1346         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
1347                 clear_bit(ca->dev_idx, c->rw_devs[i].d);
1348
1349         /*
1350          * Capacity is calculated based off of devices in allocation groups:
1351          */
1352         bch2_recalc_capacity(c);
1353
1354         /* Next, close write points that point to this device... */
1355         for (i = 0; i < ARRAY_SIZE(c->write_points); i++)
1356                 bch2_writepoint_stop(c, ca, &c->write_points[i]);
1357
1358         bch2_writepoint_stop(c, ca, &c->copygc_write_point);
1359         bch2_writepoint_stop(c, ca, &c->rebalance_write_point);
1360         bch2_writepoint_stop(c, ca, &c->btree_write_point);
1361
1362         mutex_lock(&c->btree_reserve_cache_lock);
1363         while (c->btree_reserve_cache_nr) {
1364                 struct btree_alloc *a =
1365                         &c->btree_reserve_cache[--c->btree_reserve_cache_nr];
1366
1367                 bch2_open_buckets_put(c, &a->ob);
1368         }
1369         mutex_unlock(&c->btree_reserve_cache_lock);
1370
1371         while (1) {
1372                 struct open_bucket *ob;
1373
1374                 spin_lock(&c->freelist_lock);
1375                 if (!ca->open_buckets_partial_nr) {
1376                         spin_unlock(&c->freelist_lock);
1377                         break;
1378                 }
1379                 ob = c->open_buckets +
1380                         ca->open_buckets_partial[--ca->open_buckets_partial_nr];
1381                 ob->on_partial_list = false;
1382                 spin_unlock(&c->freelist_lock);
1383
1384                 bch2_open_bucket_put(c, ob);
1385         }
1386
1387         bch2_ec_stop_dev(c, ca);
1388
1389         /*
1390          * Wake up threads that were blocked on allocation, so they can notice
1391          * the device can no longer be removed and the capacity has changed:
1392          */
1393         closure_wake_up(&c->freelist_wait);
1394
1395         /*
1396          * journal_res_get() can block waiting for free space in the journal -
1397          * it needs to notice there may not be devices to allocate from anymore:
1398          */
1399         wake_up(&c->journal.wait);
1400
1401         /* Now wait for any in flight writes: */
1402
1403         closure_wait_event(&c->open_buckets_wait,
1404                            !bch2_dev_has_open_write_point(c, ca));
1405 }
1406
1407 /* device goes rw: */
1408 void bch2_dev_allocator_add(struct bch_fs *c, struct bch_dev *ca)
1409 {
1410         unsigned i;
1411
1412         for (i = 0; i < ARRAY_SIZE(c->rw_devs); i++)
1413                 if (ca->mi.data_allowed & (1 << i))
1414                         set_bit(ca->dev_idx, c->rw_devs[i].d);
1415 }
1416
1417 void bch2_dev_allocator_quiesce(struct bch_fs *c, struct bch_dev *ca)
1418 {
1419         if (ca->alloc_thread)
1420                 closure_wait_event(&c->freelist_wait,
1421                                    ca->allocator_state != ALLOCATOR_RUNNING);
1422 }
1423
1424 /* stop allocator thread: */
1425 void bch2_dev_allocator_stop(struct bch_dev *ca)
1426 {
1427         struct task_struct *p;
1428
1429         p = rcu_dereference_protected(ca->alloc_thread, 1);
1430         ca->alloc_thread = NULL;
1431
1432         /*
1433          * We need an rcu barrier between setting ca->alloc_thread = NULL and
1434          * the thread shutting down to avoid bch2_wake_allocator() racing:
1435          *
1436          * XXX: it would be better to have the rcu barrier be asynchronous
1437          * instead of blocking us here
1438          */
1439         synchronize_rcu();
1440
1441         if (p) {
1442                 kthread_stop(p);
1443                 put_task_struct(p);
1444         }
1445 }
1446
1447 /* start allocator thread: */
1448 int bch2_dev_allocator_start(struct bch_dev *ca)
1449 {
1450         struct task_struct *p;
1451
1452         /*
1453          * allocator thread already started?
1454          */
1455         if (ca->alloc_thread)
1456                 return 0;
1457
1458         p = kthread_create(bch2_allocator_thread, ca,
1459                            "bch_alloc[%s]", ca->name);
1460         if (IS_ERR(p))
1461                 return PTR_ERR(p);
1462
1463         get_task_struct(p);
1464         rcu_assign_pointer(ca->alloc_thread, p);
1465         wake_up_process(p);
1466         return 0;
1467 }
1468
1469 void bch2_fs_allocator_background_init(struct bch_fs *c)
1470 {
1471         spin_lock_init(&c->freelist_lock);
1472         bch2_bucket_clock_init(c, READ);
1473         bch2_bucket_clock_init(c, WRITE);
1474
1475         c->pd_controllers_update_seconds = 5;
1476         INIT_DELAYED_WORK(&c->pd_controllers_update, pd_controllers_update);
1477 }