1 // SPDX-License-Identifier: GPL-2.0
3 * Moving/copying garbage collector
5 * Copyright 2012 Google, Inc.
9 #include "alloc_background.h"
10 #include "alloc_foreground.h"
11 #include "btree_iter.h"
12 #include "btree_update.h"
15 #include "disk_groups.h"
19 #include "eytzinger.h"
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>
34 static inline int fragmentation_cmp(copygc_heap *heap,
35 struct copygc_heap_entry l,
36 struct copygc_heap_entry r)
38 return cmp_int(l.fragmentation, r.fragmentation);
41 static int find_buckets_to_copygc(struct bch_fs *c)
43 copygc_heap *h = &c->copygc_heap;
44 struct btree_trans trans;
45 struct btree_iter iter;
47 struct bch_alloc_v4 a;
50 bch2_trans_init(&trans, c, 0, 0);
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.
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;
65 bch2_alloc_to_v4(k, &a);
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))
73 e = (struct copygc_heap_entry) {
74 .dev = iter.pos.inode,
76 .replicas = 1 + a.stripe_redundancy,
77 .fragmentation = div_u64((u64) a.dirty_sectors * (1ULL << 31),
79 .sectors = a.dirty_sectors,
80 .bucket = iter.pos.offset,
82 heap_add_or_replace(h, e, -fragmentation_cmp, NULL);
85 bch2_trans_iter_exit(&trans, &iter);
87 bch2_trans_exit(&trans);
91 static int bch2_copygc(struct bch_fs *c)
93 copygc_heap *h = &c->copygc_heap;
94 struct copygc_heap_entry e;
95 struct bch_move_stats move_stats;
99 struct moving_context ctxt;
100 struct data_update_opts data_opts = {
101 .btree_insert_flags = BTREE_INSERT_USE_RESERVE|JOURNAL_WATERMARK_copygc,
105 bch2_move_stats_init(&move_stats, "copygc");
107 for_each_rw_member(ca, c, dev_idx)
108 heap_size += ca->mi.nbuckets >> 7;
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");
118 ret = find_buckets_to_copygc(c);
120 bch2_fs_fatal_error(c, "error walking buckets to copygc!");
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;
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;
136 dev_wait = max(0LL, allowed - fragmented);
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;
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);
150 heap_resort(h, fragmentation_cmp, NULL);
152 bch2_moving_ctxt_init(&ctxt, c, NULL, &move_stats,
153 writepoint_ptr(&c->copygc_write_point),
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,
163 bch2_moving_ctxt_exit(&ctxt);
165 if (ret < 0 && ret != -EROFS)
166 bch_err(c, "error from bch2_move_data() in copygc: %s", bch2_err_str(ret));
168 trace_and_count(c, copygc, c, atomic64_read(&move_stats.sectors_moved), 0, 0, 0);
173 * Copygc runs when the amount of fragmented data is above some arbitrary
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
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.
186 unsigned long bch2_copygc_wait_amount(struct bch_fs *c)
190 s64 wait = S64_MAX, fragmented_allowed, fragmented;
192 for_each_rw_member(ca, c, dev_idx) {
193 struct bch_dev_usage usage = bch2_dev_usage_read(ca);
195 fragmented_allowed = ((__dev_buckets_available(ca, usage, RESERVE_none) *
196 ca->mi.bucket_size) >> 1);
197 fragmented = usage.d[BCH_DATA_user].fragmented;
199 wait = min(wait, max(0LL, fragmented_allowed - fragmented));
205 static int bch2_copygc_thread(void *arg)
207 struct bch_fs *c = arg;
208 struct io_clock *clock = &c->io_clock[WRITE];
214 while (!ret && !kthread_should_stop()) {
217 if (kthread_wait_freezable(c->copy_gc_enabled))
220 last = atomic64_read(&clock->now);
221 wait = bch2_copygc_wait_amount(c);
223 if (wait > clock->max_slop) {
224 trace_and_count(c, 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);
233 c->copygc_running = true;
234 ret = bch2_copygc(c);
235 c->copygc_running = false;
237 wake_up(&c->copygc_running_wq);
243 void bch2_copygc_stop(struct bch_fs *c)
245 if (c->copygc_thread) {
246 kthread_stop(c->copygc_thread);
247 put_task_struct(c->copygc_thread);
249 c->copygc_thread = NULL;
252 int bch2_copygc_start(struct bch_fs *c)
254 struct task_struct *t;
257 if (c->copygc_thread)
260 if (c->opts.nochanges)
263 if (bch2_fs_init_fault("copygc_start"))
266 t = kthread_create(bch2_copygc_thread, c, "bch-copygc/%s", c->name);
267 ret = PTR_ERR_OR_ZERO(t);
269 bch_err(c, "error creating copygc thread: %s", bch2_err_str(ret));
275 c->copygc_thread = t;
276 wake_up_process(c->copygc_thread);
281 void bch2_fs_copygc_init(struct bch_fs *c)
283 init_waitqueue_head(&c->copygc_running_wq);
284 c->copygc_running = false;