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

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Moving/copying garbage collector
   4  *
   5  * Copyright 2012 Google, Inc.
   6  */
   7
   8 #include "bcachefs.h"
   9 #include "alloc_background.h"
  10 #include "alloc_foreground.h"
  11 #include "btree_iter.h"
  12 #include "btree_update.h"
  13 #include "btree_write_buffer.h"
  14 #include "buckets.h"
  15 #include "clock.h"
  16 #include "disk_groups.h"
  17 #include "errcode.h"
  18 #include "error.h"
  19 #include "extents.h"
  20 #include "eytzinger.h"
  21 #include "io.h"
  22 #include "keylist.h"
  23 #include "lru.h"
  24 #include "move.h"
  25 #include "movinggc.h"
  26 #include "super-io.h"
  27
  28 #include <trace/events/bcachefs.h>
  29 #include <linux/bsearch.h>
  30 #include <linux/freezer.h>
  31 #include <linux/kthread.h>
  32 #include <linux/math64.h>
  33 #include <linux/sched/task.h>
  34 #include <linux/sort.h>
  35 #include <linux/wait.h>
  36
  37 static int bch2_bucket_is_movable(struct btree_trans *trans,
  38                                   struct bpos bucket, u64 time, u8 *gen)
  39 {
  40         struct btree_iter iter;
  41         struct bkey_s_c k;
  42         struct bch_alloc_v4 _a;
  43         const struct bch_alloc_v4 *a;
  44         int ret;
  45
  46         if (bch2_bucket_is_open(trans->c, bucket.inode, bucket.offset))
  47                 return 0;
  48
  49         bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc, bucket, BTREE_ITER_CACHED);
  50         k = bch2_btree_iter_peek_slot(&iter);
  51         ret = bkey_err(k);
  52         bch2_trans_iter_exit(trans, &iter);
  53
  54         if (ret)
  55                 return ret;
  56
  57         a = bch2_alloc_to_v4(k, &_a);
  58         *gen = a->gen;
  59         ret = data_type_movable(a->data_type) &&
  60                 a->fragmentation_lru &&
  61                 a->fragmentation_lru <= time;
  62
  63         if (ret) {
  64                 struct printbuf buf = PRINTBUF;
  65
  66                 bch2_bkey_val_to_text(&buf, trans->c, k);
  67                 pr_debug("%s", buf.buf);
  68                 printbuf_exit(&buf);
  69         }
  70
  71         return ret;
  72 }
  73
  74 typedef FIFO(struct move_bucket_in_flight) move_buckets_in_flight;
  75
  76 struct move_bucket {
  77         struct bpos             bucket;
  78         u8                      gen;
  79 };
  80
  81 typedef DARRAY(struct move_bucket) move_buckets;
  82
  83 static int move_bucket_cmp(const void *_l, const void *_r)
  84 {
  85         const struct move_bucket *l = _l;
  86         const struct move_bucket *r = _r;
  87
  88         return bkey_cmp(l->bucket, r->bucket);
  89 }
  90
  91 static bool bucket_in_flight(move_buckets *buckets_sorted, struct move_bucket b)
  92 {
  93         return bsearch(&b,
  94                        buckets_sorted->data,
  95                        buckets_sorted->nr,
  96                        sizeof(buckets_sorted->data[0]),
  97                        move_bucket_cmp) != NULL;
  98 }
  99
 100 static void move_buckets_wait(struct btree_trans *trans,
 101                               struct moving_context *ctxt,
 102                               move_buckets_in_flight *buckets_in_flight,
 103                               size_t nr, bool verify_evacuated)
 104 {
 105         while (!fifo_empty(buckets_in_flight)) {
 106                 struct move_bucket_in_flight *i = &fifo_peek_front(buckets_in_flight);
 107
 108                 if (fifo_used(buckets_in_flight) > nr)
 109                         move_ctxt_wait_event(ctxt, trans, !atomic_read(&i->count));
 110
 111                 if (atomic_read(&i->count))
 112                         break;
 113
 114                 /*
 115                  * moving_ctxt_exit calls bch2_write as it flushes pending
 116                  * reads, which inits another btree_trans; this one must be
 117                  * unlocked:
 118                  */
 119                 if (verify_evacuated)
 120                         bch2_verify_bucket_evacuated(trans, i->bucket, i->gen);
 121                 buckets_in_flight->front++;
 122         }
 123
 124         bch2_trans_unlock(trans);
 125 }
 126
 127 static int bch2_copygc_get_buckets(struct btree_trans *trans,
 128                         struct moving_context *ctxt,
 129                         move_buckets_in_flight *buckets_in_flight,
 130                         move_buckets *buckets)
 131 {
 132         struct btree_iter iter;
 133         move_buckets buckets_sorted = { 0 };
 134         struct move_bucket_in_flight *i;
 135         struct bkey_s_c k;
 136         size_t fifo_iter, nr_to_get;
 137         int ret;
 138
 139         move_buckets_wait(trans, ctxt, buckets_in_flight, buckets_in_flight->size / 2, true);
 140
 141         nr_to_get = max(16UL, fifo_used(buckets_in_flight) / 4);
 142
 143         fifo_for_each_entry_ptr(i, buckets_in_flight, fifo_iter) {
 144                 ret = darray_push(&buckets_sorted, ((struct move_bucket) {i->bucket, i->gen}));
 145                 if (ret) {
 146                         bch_err(trans->c, "error allocating move_buckets_sorted");
 147                         goto err;
 148                 }
 149         }
 150
 151         sort(buckets_sorted.data,
 152              buckets_sorted.nr,
 153              sizeof(buckets_sorted.data[0]),
 154              move_bucket_cmp,
 155              NULL);
 156
 157         ret = for_each_btree_key2_upto(trans, iter, BTREE_ID_lru,
 158                                   lru_pos(BCH_LRU_FRAGMENTATION_START, 0, 0),
 159                                   lru_pos(BCH_LRU_FRAGMENTATION_START, U64_MAX, LRU_TIME_MAX),
 160                                   0, k, ({
 161                 struct move_bucket b = { .bucket = u64_to_bucket(k.k->p.offset) };
 162                 int ret = 0;
 163
 164                 if (!bucket_in_flight(&buckets_sorted, b) &&
 165                     bch2_bucket_is_movable(trans, b.bucket, lru_pos_time(k.k->p), &b.gen))
 166                         ret = darray_push(buckets, b) ?: buckets->nr >= nr_to_get;
 167
 168                 ret;
 169         }));
 170 err:
 171         darray_exit(&buckets_sorted);
 172
 173         return ret < 0 ? ret : 0;
 174 }
 175
 176 static int bch2_copygc(struct btree_trans *trans,
 177                        struct moving_context *ctxt,
 178                        move_buckets_in_flight *buckets_in_flight)
 179 {
 180         struct bch_fs *c = trans->c;
 181         struct data_update_opts data_opts = {
 182                 .btree_insert_flags = BTREE_INSERT_USE_RESERVE|JOURNAL_WATERMARK_copygc,
 183         };
 184         move_buckets buckets = { 0 };
 185         struct move_bucket_in_flight *f;
 186         struct move_bucket *i;
 187         u64 moved = atomic64_read(&ctxt->stats->sectors_moved);
 188         int ret = 0;
 189
 190         ret = bch2_btree_write_buffer_flush(trans);
 191         if (bch2_fs_fatal_err_on(ret, c, "%s: error %s from bch2_btree_write_buffer_flush()",
 192                                  __func__, bch2_err_str(ret)))
 193                 return ret;
 194
 195         ret = bch2_copygc_get_buckets(trans, ctxt, buckets_in_flight, &buckets);
 196         if (ret)
 197                 goto err;
 198
 199         darray_for_each(buckets, i) {
 200                 if (unlikely(freezing(current)))
 201                         break;
 202
 203                 f = fifo_push_ref(buckets_in_flight);
 204                 f->bucket       = i->bucket;
 205                 f->gen          = i->gen;
 206                 atomic_set(&f->count, 0);
 207
 208                 ret = __bch2_evacuate_bucket(trans, ctxt, f, f->bucket, f->gen, data_opts);
 209                 if (ret)
 210                         goto err;
 211         }
 212 err:
 213         darray_exit(&buckets);
 214
 215         /* no entries in LRU btree found, or got to end: */
 216         if (ret == -ENOENT)
 217                 ret = 0;
 218
 219         if (ret < 0 && !bch2_err_matches(ret, EROFS))
 220                 bch_err(c, "error from bch2_move_data() in copygc: %s", bch2_err_str(ret));
 221
 222         moved = atomic64_read(&ctxt->stats->sectors_moved) - moved;
 223         trace_and_count(c, copygc, c, moved, 0, 0, 0);
 224         return ret;
 225 }
 226
 227 /*
 228  * Copygc runs when the amount of fragmented data is above some arbitrary
 229  * threshold:
 230  *
 231  * The threshold at the limit - when the device is full - is the amount of space
 232  * we reserved in bch2_recalc_capacity; we can't have more than that amount of
 233  * disk space stranded due to fragmentation and store everything we have
 234  * promised to store.
 235  *
 236  * But we don't want to be running copygc unnecessarily when the device still
 237  * has plenty of free space - rather, we want copygc to smoothly run every so
 238  * often and continually reduce the amount of fragmented space as the device
 239  * fills up. So, we increase the threshold by half the current free space.
 240  */
 241 unsigned long bch2_copygc_wait_amount(struct bch_fs *c)
 242 {
 243         struct bch_dev *ca;
 244         unsigned dev_idx;
 245         s64 wait = S64_MAX, fragmented_allowed, fragmented;
 246         unsigned i;
 247
 248         for_each_rw_member(ca, c, dev_idx) {
 249                 struct bch_dev_usage usage = bch2_dev_usage_read(ca);
 250
 251                 fragmented_allowed = ((__dev_buckets_available(ca, usage, RESERVE_stripe) *
 252                                        ca->mi.bucket_size) >> 1);
 253                 fragmented = 0;
 254
 255                 for (i = 0; i < BCH_DATA_NR; i++)
 256                         if (data_type_movable(i))
 257                                 fragmented += usage.d[i].fragmented;
 258
 259                 wait = min(wait, max(0LL, fragmented_allowed - fragmented));
 260         }
 261
 262         return wait;
 263 }
 264
 265 void bch2_copygc_wait_to_text(struct printbuf *out, struct bch_fs *c)
 266 {
 267         prt_printf(out, "Currently waiting for:     ");
 268         prt_human_readable_u64(out, max(0LL, c->copygc_wait -
 269                                         atomic64_read(&c->io_clock[WRITE].now)) << 9);
 270         prt_newline(out);
 271
 272         prt_printf(out, "Currently calculated wait: ");
 273         prt_human_readable_u64(out, bch2_copygc_wait_amount(c));
 274         prt_newline(out);
 275 }
 276
 277 static int bch2_copygc_thread(void *arg)
 278 {
 279         struct bch_fs *c = arg;
 280         struct btree_trans trans;
 281         struct moving_context ctxt;
 282         struct bch_move_stats move_stats;
 283         struct io_clock *clock = &c->io_clock[WRITE];
 284         move_buckets_in_flight move_buckets;
 285         u64 last, wait;
 286         int ret = 0;
 287
 288         if (!init_fifo(&move_buckets, 1 << 14, GFP_KERNEL)) {
 289                 bch_err(c, "error allocating copygc buckets in flight");
 290                 return -ENOMEM;
 291         }
 292
 293         set_freezable();
 294         bch2_trans_init(&trans, c, 0, 0);
 295
 296         bch2_move_stats_init(&move_stats, "copygc");
 297         bch2_moving_ctxt_init(&ctxt, c, NULL, &move_stats,
 298                               writepoint_ptr(&c->copygc_write_point),
 299                               false);
 300
 301         while (!ret && !kthread_should_stop()) {
 302                 bch2_trans_unlock(&trans);
 303                 cond_resched();
 304
 305                 if (!c->copy_gc_enabled) {
 306                         move_buckets_wait(&trans, &ctxt, &move_buckets, 0, true);
 307                         kthread_wait_freezable(c->copy_gc_enabled);
 308                 }
 309
 310                 if (unlikely(freezing(current))) {
 311                         move_buckets_wait(&trans, &ctxt, &move_buckets, 0, true);
 312                         __refrigerator(false);
 313                         continue;
 314                 }
 315
 316                 last = atomic64_read(&clock->now);
 317                 wait = bch2_copygc_wait_amount(c);
 318
 319                 if (wait > clock->max_slop) {
 320                         move_buckets_wait(&trans, &ctxt, &move_buckets, 0, true);
 321                         trace_and_count(c, copygc_wait, c, wait, last + wait);
 322                         c->copygc_wait = last + wait;
 323                         bch2_kthread_io_clock_wait(clock, last + wait,
 324                                         MAX_SCHEDULE_TIMEOUT);
 325                         continue;
 326                 }
 327
 328                 c->copygc_wait = 0;
 329
 330                 c->copygc_running = true;
 331                 ret = bch2_copygc(&trans, &ctxt, &move_buckets);
 332                 c->copygc_running = false;
 333
 334                 wake_up(&c->copygc_running_wq);
 335         }
 336
 337         bch2_trans_exit(&trans);
 338         bch2_moving_ctxt_exit(&ctxt);
 339         free_fifo(&move_buckets);
 340
 341         return 0;
 342 }
 343
 344 void bch2_copygc_stop(struct bch_fs *c)
 345 {
 346         if (c->copygc_thread) {
 347                 kthread_stop(c->copygc_thread);
 348                 put_task_struct(c->copygc_thread);
 349         }
 350         c->copygc_thread = NULL;
 351 }
 352
 353 int bch2_copygc_start(struct bch_fs *c)
 354 {
 355         struct task_struct *t;
 356         int ret;
 357
 358         if (c->copygc_thread)
 359                 return 0;
 360
 361         if (c->opts.nochanges)
 362                 return 0;
 363
 364         if (bch2_fs_init_fault("copygc_start"))
 365                 return -ENOMEM;
 366
 367         t = kthread_create(bch2_copygc_thread, c, "bch-copygc/%s", c->name);
 368         ret = PTR_ERR_OR_ZERO(t);
 369         if (ret) {
 370                 bch_err(c, "error creating copygc thread: %s", bch2_err_str(ret));
 371                 return ret;
 372         }
 373
 374         get_task_struct(t);
 375
 376         c->copygc_thread = t;
 377         wake_up_process(c->copygc_thread);
 378
 379         return 0;
 380 }
 381
 382 void bch2_fs_copygc_init(struct bch_fs *c)
 383 {
 384         init_waitqueue_head(&c->copygc_running_wq);
 385         c->copygc_running = false;
 386 }