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