1
2
3#include <linux/jiffies.h>
4#include <linux/kernel.h>
5#include <linux/ktime.h>
6#include <linux/list.h>
7#include <linux/math64.h>
8#include <linux/sizes.h>
9#include <linux/workqueue.h>
10#include "ctree.h"
11#include "block-group.h"
12#include "discard.h"
13#include "free-space-cache.h"
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#define BTRFS_DISCARD_DELAY (120ULL * NSEC_PER_SEC)
56#define BTRFS_DISCARD_UNUSED_DELAY (10ULL * NSEC_PER_SEC)
57
58
59#define BTRFS_DISCARD_TARGET_MSEC (6 * 60 * 60UL * MSEC_PER_SEC)
60#define BTRFS_DISCARD_MIN_DELAY_MSEC (1UL)
61#define BTRFS_DISCARD_MAX_DELAY_MSEC (1000UL)
62#define BTRFS_DISCARD_MAX_IOPS (10U)
63
64
65static int discard_minlen[BTRFS_NR_DISCARD_LISTS] = {
66 0,
67 BTRFS_ASYNC_DISCARD_MAX_FILTER,
68 BTRFS_ASYNC_DISCARD_MIN_FILTER
69};
70
71static struct list_head *get_discard_list(struct btrfs_discard_ctl *discard_ctl,
72 struct btrfs_block_group *block_group)
73{
74 return &discard_ctl->discard_list[block_group->discard_index];
75}
76
77static void __add_to_discard_list(struct btrfs_discard_ctl *discard_ctl,
78 struct btrfs_block_group *block_group)
79{
80 if (!btrfs_run_discard_work(discard_ctl))
81 return;
82
83 if (list_empty(&block_group->discard_list) ||
84 block_group->discard_index == BTRFS_DISCARD_INDEX_UNUSED) {
85 if (block_group->discard_index == BTRFS_DISCARD_INDEX_UNUSED)
86 block_group->discard_index = BTRFS_DISCARD_INDEX_START;
87 block_group->discard_eligible_time = (ktime_get_ns() +
88 BTRFS_DISCARD_DELAY);
89 block_group->discard_state = BTRFS_DISCARD_RESET_CURSOR;
90 }
91
92 list_move_tail(&block_group->discard_list,
93 get_discard_list(discard_ctl, block_group));
94}
95
96static void add_to_discard_list(struct btrfs_discard_ctl *discard_ctl,
97 struct btrfs_block_group *block_group)
98{
99 if (!btrfs_is_block_group_data_only(block_group))
100 return;
101
102 spin_lock(&discard_ctl->lock);
103 __add_to_discard_list(discard_ctl, block_group);
104 spin_unlock(&discard_ctl->lock);
105}
106
107static void add_to_discard_unused_list(struct btrfs_discard_ctl *discard_ctl,
108 struct btrfs_block_group *block_group)
109{
110 spin_lock(&discard_ctl->lock);
111
112 if (!btrfs_run_discard_work(discard_ctl)) {
113 spin_unlock(&discard_ctl->lock);
114 return;
115 }
116
117 list_del_init(&block_group->discard_list);
118
119 block_group->discard_index = BTRFS_DISCARD_INDEX_UNUSED;
120 block_group->discard_eligible_time = (ktime_get_ns() +
121 BTRFS_DISCARD_UNUSED_DELAY);
122 block_group->discard_state = BTRFS_DISCARD_RESET_CURSOR;
123 list_add_tail(&block_group->discard_list,
124 &discard_ctl->discard_list[BTRFS_DISCARD_INDEX_UNUSED]);
125
126 spin_unlock(&discard_ctl->lock);
127}
128
129static bool remove_from_discard_list(struct btrfs_discard_ctl *discard_ctl,
130 struct btrfs_block_group *block_group)
131{
132 bool running = false;
133
134 spin_lock(&discard_ctl->lock);
135
136 if (block_group == discard_ctl->block_group) {
137 running = true;
138 discard_ctl->block_group = NULL;
139 }
140
141 block_group->discard_eligible_time = 0;
142 list_del_init(&block_group->discard_list);
143
144 spin_unlock(&discard_ctl->lock);
145
146 return running;
147}
148
149
150
151
152
153
154
155
156
157static struct btrfs_block_group *find_next_block_group(
158 struct btrfs_discard_ctl *discard_ctl,
159 u64 now)
160{
161 struct btrfs_block_group *ret_block_group = NULL, *block_group;
162 int i;
163
164 for (i = 0; i < BTRFS_NR_DISCARD_LISTS; i++) {
165 struct list_head *discard_list = &discard_ctl->discard_list[i];
166
167 if (!list_empty(discard_list)) {
168 block_group = list_first_entry(discard_list,
169 struct btrfs_block_group,
170 discard_list);
171
172 if (!ret_block_group)
173 ret_block_group = block_group;
174
175 if (ret_block_group->discard_eligible_time < now)
176 break;
177
178 if (ret_block_group->discard_eligible_time >
179 block_group->discard_eligible_time)
180 ret_block_group = block_group;
181 }
182 }
183
184 return ret_block_group;
185}
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201static struct btrfs_block_group *peek_discard_list(
202 struct btrfs_discard_ctl *discard_ctl,
203 enum btrfs_discard_state *discard_state,
204 int *discard_index, u64 now)
205{
206 struct btrfs_block_group *block_group;
207
208 spin_lock(&discard_ctl->lock);
209again:
210 block_group = find_next_block_group(discard_ctl, now);
211
212 if (block_group && now >= block_group->discard_eligible_time) {
213 if (block_group->discard_index == BTRFS_DISCARD_INDEX_UNUSED &&
214 block_group->used != 0) {
215 if (btrfs_is_block_group_data_only(block_group))
216 __add_to_discard_list(discard_ctl, block_group);
217 else
218 list_del_init(&block_group->discard_list);
219 goto again;
220 }
221 if (block_group->discard_state == BTRFS_DISCARD_RESET_CURSOR) {
222 block_group->discard_cursor = block_group->start;
223 block_group->discard_state = BTRFS_DISCARD_EXTENTS;
224 }
225 discard_ctl->block_group = block_group;
226 }
227 if (block_group) {
228 *discard_state = block_group->discard_state;
229 *discard_index = block_group->discard_index;
230 }
231 spin_unlock(&discard_ctl->lock);
232
233 return block_group;
234}
235
236
237
238
239
240
241
242
243
244
245
246void btrfs_discard_check_filter(struct btrfs_block_group *block_group,
247 u64 bytes)
248{
249 struct btrfs_discard_ctl *discard_ctl;
250
251 if (!block_group ||
252 !btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC))
253 return;
254
255 discard_ctl = &block_group->fs_info->discard_ctl;
256
257 if (block_group->discard_index > BTRFS_DISCARD_INDEX_START &&
258 bytes >= discard_minlen[block_group->discard_index - 1]) {
259 int i;
260
261 remove_from_discard_list(discard_ctl, block_group);
262
263 for (i = BTRFS_DISCARD_INDEX_START; i < BTRFS_NR_DISCARD_LISTS;
264 i++) {
265 if (bytes >= discard_minlen[i]) {
266 block_group->discard_index = i;
267 add_to_discard_list(discard_ctl, block_group);
268 break;
269 }
270 }
271 }
272}
273
274
275
276
277
278
279
280
281
282static void btrfs_update_discard_index(struct btrfs_discard_ctl *discard_ctl,
283 struct btrfs_block_group *block_group)
284{
285 block_group->discard_index++;
286 if (block_group->discard_index == BTRFS_NR_DISCARD_LISTS) {
287 block_group->discard_index = 1;
288 return;
289 }
290
291 add_to_discard_list(discard_ctl, block_group);
292}
293
294
295
296
297
298
299
300
301
302void btrfs_discard_cancel_work(struct btrfs_discard_ctl *discard_ctl,
303 struct btrfs_block_group *block_group)
304{
305 if (remove_from_discard_list(discard_ctl, block_group)) {
306 cancel_delayed_work_sync(&discard_ctl->work);
307 btrfs_discard_schedule_work(discard_ctl, true);
308 }
309}
310
311
312
313
314
315
316
317
318void btrfs_discard_queue_work(struct btrfs_discard_ctl *discard_ctl,
319 struct btrfs_block_group *block_group)
320{
321 if (!block_group || !btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC))
322 return;
323
324 if (block_group->used == 0)
325 add_to_discard_unused_list(discard_ctl, block_group);
326 else
327 add_to_discard_list(discard_ctl, block_group);
328
329 if (!delayed_work_pending(&discard_ctl->work))
330 btrfs_discard_schedule_work(discard_ctl, false);
331}
332
333static void __btrfs_discard_schedule_work(struct btrfs_discard_ctl *discard_ctl,
334 u64 now, bool override)
335{
336 struct btrfs_block_group *block_group;
337
338 if (!btrfs_run_discard_work(discard_ctl))
339 return;
340 if (!override && delayed_work_pending(&discard_ctl->work))
341 return;
342
343 block_group = find_next_block_group(discard_ctl, now);
344 if (block_group) {
345 u64 delay = discard_ctl->delay_ms * NSEC_PER_MSEC;
346 u32 kbps_limit = READ_ONCE(discard_ctl->kbps_limit);
347
348
349
350
351
352
353 if (kbps_limit && discard_ctl->prev_discard) {
354 u64 bps_limit = ((u64)kbps_limit) * SZ_1K;
355 u64 bps_delay = div64_u64(discard_ctl->prev_discard *
356 NSEC_PER_SEC, bps_limit);
357
358 delay = max(delay, bps_delay);
359 }
360
361
362
363
364
365 if (now < block_group->discard_eligible_time) {
366 u64 bg_timeout = block_group->discard_eligible_time - now;
367
368 delay = max(delay, bg_timeout);
369 }
370
371 if (override && discard_ctl->prev_discard) {
372 u64 elapsed = now - discard_ctl->prev_discard_time;
373
374 if (delay > elapsed)
375 delay -= elapsed;
376 else
377 delay = 0;
378 }
379
380 mod_delayed_work(discard_ctl->discard_workers,
381 &discard_ctl->work, nsecs_to_jiffies(delay));
382 }
383}
384
385
386
387
388
389
390
391
392
393
394void btrfs_discard_schedule_work(struct btrfs_discard_ctl *discard_ctl,
395 bool override)
396{
397 const u64 now = ktime_get_ns();
398
399 spin_lock(&discard_ctl->lock);
400 __btrfs_discard_schedule_work(discard_ctl, now, override);
401 spin_unlock(&discard_ctl->lock);
402}
403
404
405
406
407
408
409
410
411
412
413
414static void btrfs_finish_discard_pass(struct btrfs_discard_ctl *discard_ctl,
415 struct btrfs_block_group *block_group)
416{
417 remove_from_discard_list(discard_ctl, block_group);
418
419 if (block_group->used == 0) {
420 if (btrfs_is_free_space_trimmed(block_group))
421 btrfs_mark_bg_unused(block_group);
422 else
423 add_to_discard_unused_list(discard_ctl, block_group);
424 } else {
425 btrfs_update_discard_index(discard_ctl, block_group);
426 }
427}
428
429
430
431
432
433
434
435
436
437static void btrfs_discard_workfn(struct work_struct *work)
438{
439 struct btrfs_discard_ctl *discard_ctl;
440 struct btrfs_block_group *block_group;
441 enum btrfs_discard_state discard_state;
442 int discard_index = 0;
443 u64 trimmed = 0;
444 u64 minlen = 0;
445 u64 now = ktime_get_ns();
446
447 discard_ctl = container_of(work, struct btrfs_discard_ctl, work.work);
448
449 block_group = peek_discard_list(discard_ctl, &discard_state,
450 &discard_index, now);
451 if (!block_group || !btrfs_run_discard_work(discard_ctl))
452 return;
453 if (now < block_group->discard_eligible_time) {
454 btrfs_discard_schedule_work(discard_ctl, false);
455 return;
456 }
457
458
459 minlen = discard_minlen[discard_index];
460
461 if (discard_state == BTRFS_DISCARD_BITMAPS) {
462 u64 maxlen = 0;
463
464
465
466
467
468
469
470 if (discard_index != BTRFS_DISCARD_INDEX_UNUSED)
471 maxlen = discard_minlen[discard_index - 1];
472
473 btrfs_trim_block_group_bitmaps(block_group, &trimmed,
474 block_group->discard_cursor,
475 btrfs_block_group_end(block_group),
476 minlen, maxlen, true);
477 discard_ctl->discard_bitmap_bytes += trimmed;
478 } else {
479 btrfs_trim_block_group_extents(block_group, &trimmed,
480 block_group->discard_cursor,
481 btrfs_block_group_end(block_group),
482 minlen, true);
483 discard_ctl->discard_extent_bytes += trimmed;
484 }
485
486
487 if (block_group->discard_cursor >= btrfs_block_group_end(block_group)) {
488 if (discard_state == BTRFS_DISCARD_BITMAPS) {
489 btrfs_finish_discard_pass(discard_ctl, block_group);
490 } else {
491 block_group->discard_cursor = block_group->start;
492 spin_lock(&discard_ctl->lock);
493 if (block_group->discard_state !=
494 BTRFS_DISCARD_RESET_CURSOR)
495 block_group->discard_state =
496 BTRFS_DISCARD_BITMAPS;
497 spin_unlock(&discard_ctl->lock);
498 }
499 }
500
501 now = ktime_get_ns();
502 spin_lock(&discard_ctl->lock);
503 discard_ctl->prev_discard = trimmed;
504 discard_ctl->prev_discard_time = now;
505 discard_ctl->block_group = NULL;
506 __btrfs_discard_schedule_work(discard_ctl, now, false);
507 spin_unlock(&discard_ctl->lock);
508}
509
510
511
512
513
514
515
516bool btrfs_run_discard_work(struct btrfs_discard_ctl *discard_ctl)
517{
518 struct btrfs_fs_info *fs_info = container_of(discard_ctl,
519 struct btrfs_fs_info,
520 discard_ctl);
521
522 return (!(fs_info->sb->s_flags & SB_RDONLY) &&
523 test_bit(BTRFS_FS_DISCARD_RUNNING, &fs_info->flags));
524}
525
526
527
528
529
530
531
532
533
534void btrfs_discard_calc_delay(struct btrfs_discard_ctl *discard_ctl)
535{
536 s32 discardable_extents;
537 s64 discardable_bytes;
538 u32 iops_limit;
539 unsigned long delay;
540
541 discardable_extents = atomic_read(&discard_ctl->discardable_extents);
542 if (!discardable_extents)
543 return;
544
545 spin_lock(&discard_ctl->lock);
546
547
548
549
550
551
552
553
554 if (discardable_extents < 0)
555 atomic_add(-discardable_extents,
556 &discard_ctl->discardable_extents);
557
558 discardable_bytes = atomic64_read(&discard_ctl->discardable_bytes);
559 if (discardable_bytes < 0)
560 atomic64_add(-discardable_bytes,
561 &discard_ctl->discardable_bytes);
562
563 if (discardable_extents <= 0) {
564 spin_unlock(&discard_ctl->lock);
565 return;
566 }
567
568 iops_limit = READ_ONCE(discard_ctl->iops_limit);
569 if (iops_limit)
570 delay = MSEC_PER_SEC / iops_limit;
571 else
572 delay = BTRFS_DISCARD_TARGET_MSEC / discardable_extents;
573
574 delay = clamp(delay, BTRFS_DISCARD_MIN_DELAY_MSEC,
575 BTRFS_DISCARD_MAX_DELAY_MSEC);
576 discard_ctl->delay_ms = delay;
577
578 spin_unlock(&discard_ctl->lock);
579}
580
581
582
583
584
585
586
587
588
589void btrfs_discard_update_discardable(struct btrfs_block_group *block_group)
590{
591 struct btrfs_free_space_ctl *ctl;
592 struct btrfs_discard_ctl *discard_ctl;
593 s32 extents_delta;
594 s64 bytes_delta;
595
596 if (!block_group ||
597 !btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC) ||
598 !btrfs_is_block_group_data_only(block_group))
599 return;
600
601 ctl = block_group->free_space_ctl;
602 discard_ctl = &block_group->fs_info->discard_ctl;
603
604 lockdep_assert_held(&ctl->tree_lock);
605 extents_delta = ctl->discardable_extents[BTRFS_STAT_CURR] -
606 ctl->discardable_extents[BTRFS_STAT_PREV];
607 if (extents_delta) {
608 atomic_add(extents_delta, &discard_ctl->discardable_extents);
609 ctl->discardable_extents[BTRFS_STAT_PREV] =
610 ctl->discardable_extents[BTRFS_STAT_CURR];
611 }
612
613 bytes_delta = ctl->discardable_bytes[BTRFS_STAT_CURR] -
614 ctl->discardable_bytes[BTRFS_STAT_PREV];
615 if (bytes_delta) {
616 atomic64_add(bytes_delta, &discard_ctl->discardable_bytes);
617 ctl->discardable_bytes[BTRFS_STAT_PREV] =
618 ctl->discardable_bytes[BTRFS_STAT_CURR];
619 }
620}
621
622
623
624
625
626
627
628
629
630
631
632void btrfs_discard_punt_unused_bgs_list(struct btrfs_fs_info *fs_info)
633{
634 struct btrfs_block_group *block_group, *next;
635
636 spin_lock(&fs_info->unused_bgs_lock);
637
638 list_for_each_entry_safe(block_group, next, &fs_info->unused_bgs,
639 bg_list) {
640 list_del_init(&block_group->bg_list);
641 btrfs_put_block_group(block_group);
642 btrfs_discard_queue_work(&fs_info->discard_ctl, block_group);
643 }
644 spin_unlock(&fs_info->unused_bgs_lock);
645}
646
647
648
649
650
651
652
653
654
655
656
657static void btrfs_discard_purge_list(struct btrfs_discard_ctl *discard_ctl)
658{
659 struct btrfs_block_group *block_group, *next;
660 int i;
661
662 spin_lock(&discard_ctl->lock);
663 for (i = 0; i < BTRFS_NR_DISCARD_LISTS; i++) {
664 list_for_each_entry_safe(block_group, next,
665 &discard_ctl->discard_list[i],
666 discard_list) {
667 list_del_init(&block_group->discard_list);
668 spin_unlock(&discard_ctl->lock);
669 if (block_group->used == 0)
670 btrfs_mark_bg_unused(block_group);
671 spin_lock(&discard_ctl->lock);
672 }
673 }
674 spin_unlock(&discard_ctl->lock);
675}
676
677void btrfs_discard_resume(struct btrfs_fs_info *fs_info)
678{
679 if (!btrfs_test_opt(fs_info, DISCARD_ASYNC)) {
680 btrfs_discard_cleanup(fs_info);
681 return;
682 }
683
684 btrfs_discard_punt_unused_bgs_list(fs_info);
685
686 set_bit(BTRFS_FS_DISCARD_RUNNING, &fs_info->flags);
687}
688
689void btrfs_discard_stop(struct btrfs_fs_info *fs_info)
690{
691 clear_bit(BTRFS_FS_DISCARD_RUNNING, &fs_info->flags);
692}
693
694void btrfs_discard_init(struct btrfs_fs_info *fs_info)
695{
696 struct btrfs_discard_ctl *discard_ctl = &fs_info->discard_ctl;
697 int i;
698
699 spin_lock_init(&discard_ctl->lock);
700 INIT_DELAYED_WORK(&discard_ctl->work, btrfs_discard_workfn);
701
702 for (i = 0; i < BTRFS_NR_DISCARD_LISTS; i++)
703 INIT_LIST_HEAD(&discard_ctl->discard_list[i]);
704
705 discard_ctl->prev_discard = 0;
706 discard_ctl->prev_discard_time = 0;
707 atomic_set(&discard_ctl->discardable_extents, 0);
708 atomic64_set(&discard_ctl->discardable_bytes, 0);
709 discard_ctl->max_discard_size = BTRFS_ASYNC_DISCARD_DEFAULT_MAX_SIZE;
710 discard_ctl->delay_ms = BTRFS_DISCARD_MAX_DELAY_MSEC;
711 discard_ctl->iops_limit = BTRFS_DISCARD_MAX_IOPS;
712 discard_ctl->kbps_limit = 0;
713 discard_ctl->discard_extent_bytes = 0;
714 discard_ctl->discard_bitmap_bytes = 0;
715 atomic64_set(&discard_ctl->discard_bytes_saved, 0);
716}
717
718void btrfs_discard_cleanup(struct btrfs_fs_info *fs_info)
719{
720 btrfs_discard_stop(fs_info);
721 cancel_delayed_work_sync(&fs_info->discard_ctl.work);
722 btrfs_discard_purge_list(&fs_info->discard_ctl);
723}
724