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;
49 bch2_trans_init(&trans, c, 0, 0);
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.
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;
66 a = bch2_alloc_to_v4(k, &a_convert);
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))
74 e = (struct copygc_heap_entry) {
75 .dev = iter.pos.inode,
77 .replicas = 1 + a->stripe_redundancy,
78 .fragmentation = div_u64((u64) a->dirty_sectors * (1ULL << 31),
80 .sectors = a->dirty_sectors,
81 .bucket = iter.pos.offset,
83 heap_add_or_replace(h, e, -fragmentation_cmp, NULL);
86 bch2_trans_iter_exit(&trans, &iter);
88 bch2_trans_exit(&trans);
92 static int bch2_copygc(struct bch_fs *c)
94 copygc_heap *h = &c->copygc_heap;
95 struct copygc_heap_entry e;
96 struct bch_move_stats move_stats;
100 struct moving_context ctxt;
101 struct data_update_opts data_opts = {
102 .btree_insert_flags = BTREE_INSERT_USE_RESERVE|JOURNAL_WATERMARK_copygc,
106 bch2_move_stats_init(&move_stats, "copygc");
108 for_each_rw_member(ca, c, dev_idx)
109 heap_size += ca->mi.nbuckets >> 7;
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");
119 ret = find_buckets_to_copygc(c);
121 bch2_fs_fatal_error(c, "error walking buckets to copygc!");
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;
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;
137 dev_wait = max(0LL, allowed - fragmented);
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;
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);
151 heap_resort(h, fragmentation_cmp, NULL);
153 bch2_moving_ctxt_init(&ctxt, c, NULL, &move_stats,
154 writepoint_ptr(&c->copygc_write_point),
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,
164 bch2_moving_ctxt_exit(&ctxt);
166 if (ret < 0 && ret != -EROFS)
167 bch_err(c, "error from bch2_move_data() in copygc: %s", bch2_err_str(ret));
169 trace_and_count(c, copygc, c, atomic64_read(&move_stats.sectors_moved), 0, 0, 0);
174 * Copygc runs when the amount of fragmented data is above some arbitrary
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
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.
187 unsigned long bch2_copygc_wait_amount(struct bch_fs *c)
191 s64 wait = S64_MAX, fragmented_allowed, fragmented;
193 for_each_rw_member(ca, c, dev_idx) {
194 struct bch_dev_usage usage = bch2_dev_usage_read(ca);
196 fragmented_allowed = ((__dev_buckets_available(ca, usage, RESERVE_none) *
197 ca->mi.bucket_size) >> 1);
198 fragmented = usage.d[BCH_DATA_user].fragmented;
200 wait = min(wait, max(0LL, fragmented_allowed - fragmented));
206 static int bch2_copygc_thread(void *arg)
208 struct bch_fs *c = arg;
209 struct io_clock *clock = &c->io_clock[WRITE];
215 while (!ret && !kthread_should_stop()) {
218 if (kthread_wait_freezable(c->copy_gc_enabled))
221 last = atomic64_read(&clock->now);
222 wait = bch2_copygc_wait_amount(c);
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);
234 c->copygc_running = true;
235 ret = bch2_copygc(c);
236 c->copygc_running = false;
238 wake_up(&c->copygc_running_wq);
244 void bch2_copygc_stop(struct bch_fs *c)
246 if (c->copygc_thread) {
247 kthread_stop(c->copygc_thread);
248 put_task_struct(c->copygc_thread);
250 c->copygc_thread = NULL;
253 int bch2_copygc_start(struct bch_fs *c)
255 struct task_struct *t;
258 if (c->copygc_thread)
261 if (c->opts.nochanges)
264 if (bch2_fs_init_fault("copygc_start"))
267 t = kthread_create(bch2_copygc_thread, c, "bch-copygc/%s", c->name);
268 ret = PTR_ERR_OR_ZERO(t);
270 bch_err(c, "error creating copygc thread: %s", bch2_err_str(ret));
276 c->copygc_thread = t;
277 wake_up_process(c->copygc_thread);
282 void bch2_fs_copygc_init(struct bch_fs *c)
284 init_waitqueue_head(&c->copygc_running_wq);
285 c->copygc_running = false;