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