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 "buckets.h"
  14 #include "clock.h"
  15 #include "disk_groups.h"
  16 #include "error.h"
  17 #include "extents.h"
  18 #include "eytzinger.h"
  19 #include "io.h"
  20 #include "keylist.h"
  21 #include "move.h"
  22 #include "movinggc.h"
  23 #include "super-io.h"
  24
  25 #include <trace/events/bcachefs.h>
  26 #include <linux/freezer.h>
  27 #include <linux/kthread.h>
  28 #include <linux/math64.h>
  29 #include <linux/sched/task.h>
  30 #include <linux/sort.h>
  31 #include <linux/wait.h>
  32
  33 static inline int fragmentation_cmp(copygc_heap *heap,
  34                                    struct copygc_heap_entry l,
  35                                    struct copygc_heap_entry r)
  36 {
  37         return cmp_int(l.fragmentation, r.fragmentation);
  38 }
  39
  40 static int find_buckets_to_copygc(struct bch_fs *c)
  41 {
  42         copygc_heap *h = &c->copygc_heap;
  43         struct btree_trans trans;
  44         struct btree_iter iter;
  45         struct bkey_s_c k;
  46         struct bch_alloc_v4 a;
  47         int ret;
  48
  49         bch2_trans_init(&trans, c, 0, 0);
  50
  51         /*
  52          * Find buckets with lowest sector counts, skipping completely
  53          * empty buckets, by building a maxheap sorted by sector count,
  54          * and repeatedly replacing the maximum element until all
  55          * buckets have been visited.
  56          */
  57         h->used = 0;
  58
  59         for_each_btree_key(&trans, iter, BTREE_ID_alloc, POS_MIN,
  60                            BTREE_ITER_PREFETCH, k, ret) {
  61                 struct bch_dev *ca = bch_dev_bkey_exists(c, iter.pos.inode);
  62                 struct copygc_heap_entry e;
  63
  64                 bch2_alloc_to_v4(k, &a);
  65
  66                 if ((a.data_type != BCH_DATA_btree &&
  67                      a.data_type != BCH_DATA_user) ||
  68                     a.dirty_sectors >= ca->mi.bucket_size ||
  69                     bch2_bucket_is_open(c, iter.pos.inode, iter.pos.offset))
  70                         continue;
  71
  72                 e = (struct copygc_heap_entry) {
  73                         .dev            = iter.pos.inode,
  74                         .gen            = a.gen,
  75                         .replicas       = 1 + a.stripe_redundancy,
  76                         .fragmentation  = div_u64((u64) a.dirty_sectors * (1ULL << 31),
  77                                                   ca->mi.bucket_size),
  78                         .sectors        = a.dirty_sectors,
  79                         .bucket         = iter.pos.offset,
  80                 };
  81                 heap_add_or_replace(h, e, -fragmentation_cmp, NULL);
  82
  83         }
  84         bch2_trans_iter_exit(&trans, &iter);
  85
  86         bch2_trans_exit(&trans);
  87         return ret;
  88 }
  89
  90 static int bch2_copygc(struct bch_fs *c)
  91 {
  92         copygc_heap *h = &c->copygc_heap;
  93         struct copygc_heap_entry e;
  94         struct bch_move_stats move_stats;
  95         struct bch_dev *ca;
  96         unsigned dev_idx;
  97         size_t heap_size = 0;
  98         struct data_opts data_opts = {
  99                 .nr_replicas            = 1,
 100                 .btree_insert_flags     = BTREE_INSERT_USE_RESERVE|JOURNAL_WATERMARK_copygc,
 101         };
 102         int ret;
 103
 104         bch_move_stats_init(&move_stats, "copygc");
 105
 106         for_each_rw_member(ca, c, dev_idx)
 107                 heap_size += ca->mi.nbuckets >> 7;
 108
 109         if (h->size < heap_size) {
 110                 free_heap(&c->copygc_heap);
 111                 if (!init_heap(&c->copygc_heap, heap_size, GFP_KERNEL)) {
 112                         bch_err(c, "error allocating copygc heap");
 113                         return 0;
 114                 }
 115         }
 116
 117         ret = find_buckets_to_copygc(c);
 118         if (ret) {
 119                 bch2_fs_fatal_error(c, "error walking buckets to copygc!");
 120                 return ret;
 121         }
 122
 123         if (!h->used) {
 124                 bch_err_ratelimited(c, "copygc requested to run but found no buckets to move!");
 125                 return 0;
 126         }
 127
 128         heap_resort(h, fragmentation_cmp, NULL);
 129
 130         while (h->used) {
 131                 BUG_ON(!heap_pop(h, e, -fragmentation_cmp, NULL));
 132                 /* not correct w.r.t. device removal */
 133
 134                 ret = bch2_evacuate_bucket(c, POS(e.dev, e.bucket), e.gen, NULL,
 135                                            writepoint_ptr(&c->copygc_write_point),
 136                                            DATA_REWRITE, &data_opts,
 137                                            &move_stats);
 138                 if (ret < 0)
 139                         bch_err(c, "error %i from bch2_move_data() in copygc", ret);
 140                 if (ret)
 141                         return ret;
 142         }
 143
 144         trace_copygc(c, atomic64_read(&move_stats.sectors_moved), 0, 0, 0);
 145         return ret;
 146 }
 147
 148 /*
 149  * Copygc runs when the amount of fragmented data is above some arbitrary
 150  * threshold:
 151  *
 152  * The threshold at the limit - when the device is full - is the amount of space
 153  * we reserved in bch2_recalc_capacity; we can't have more than that amount of
 154  * disk space stranded due to fragmentation and store everything we have
 155  * promised to store.
 156  *
 157  * But we don't want to be running copygc unnecessarily when the device still
 158  * has plenty of free space - rather, we want copygc to smoothly run every so
 159  * often and continually reduce the amount of fragmented space as the device
 160  * fills up. So, we increase the threshold by half the current free space.
 161  */
 162 unsigned long bch2_copygc_wait_amount(struct bch_fs *c)
 163 {
 164         struct bch_dev *ca;
 165         unsigned dev_idx;
 166         s64 wait = S64_MAX, fragmented_allowed, fragmented;
 167
 168         for_each_rw_member(ca, c, dev_idx) {
 169                 struct bch_dev_usage usage = bch2_dev_usage_read(ca);
 170
 171                 fragmented_allowed = ((__dev_buckets_available(ca, usage, RESERVE_none) *
 172                                        ca->mi.bucket_size) >> 1);
 173                 fragmented = usage.d[BCH_DATA_user].fragmented;
 174
 175                 wait = min(wait, max(0LL, fragmented_allowed - fragmented));
 176         }
 177
 178         return wait;
 179 }
 180
 181 static int bch2_copygc_thread(void *arg)
 182 {
 183         struct bch_fs *c = arg;
 184         struct io_clock *clock = &c->io_clock[WRITE];
 185         u64 last, wait;
 186
 187         set_freezable();
 188
 189         while (!kthread_should_stop()) {
 190                 cond_resched();
 191
 192                 if (kthread_wait_freezable(c->copy_gc_enabled))
 193                         break;
 194
 195                 last = atomic64_read(&clock->now);
 196                 wait = bch2_copygc_wait_amount(c);
 197
 198                 if (wait > clock->max_slop) {
 199                         trace_copygc_wait(c, wait, last + wait);
 200                         c->copygc_wait = last + wait;
 201                         bch2_kthread_io_clock_wait(clock, last + wait,
 202                                         MAX_SCHEDULE_TIMEOUT);
 203                         continue;
 204                 }
 205
 206                 c->copygc_wait = 0;
 207
 208                 if (bch2_copygc(c))
 209                         break;
 210         }
 211
 212         return 0;
 213 }
 214
 215 void bch2_copygc_stop(struct bch_fs *c)
 216 {
 217         if (c->copygc_thread) {
 218                 kthread_stop(c->copygc_thread);
 219                 put_task_struct(c->copygc_thread);
 220         }
 221         c->copygc_thread = NULL;
 222 }
 223
 224 int bch2_copygc_start(struct bch_fs *c)
 225 {
 226         struct task_struct *t;
 227
 228         if (c->copygc_thread)
 229                 return 0;
 230
 231         if (c->opts.nochanges)
 232                 return 0;
 233
 234         if (bch2_fs_init_fault("copygc_start"))
 235                 return -ENOMEM;
 236
 237         t = kthread_create(bch2_copygc_thread, c, "bch-copygc/%s", c->name);
 238         if (IS_ERR(t)) {
 239                 bch_err(c, "error creating copygc thread: %li", PTR_ERR(t));
 240                 return PTR_ERR(t);
 241         }
 242
 243         get_task_struct(t);
 244
 245         c->copygc_thread = t;
 246         wake_up_process(c->copygc_thread);
 247
 248         return 0;
 249 }
 250
 251 void bch2_fs_copygc_init(struct bch_fs *c)
 252 {
 253 }