1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2016-present, Facebook, Inc.
9 #include <linux/bitmap.h>
10 #include <linux/err.h>
11 #include <linux/init.h>
12 #include <linux/kernel.h>
14 #include <linux/sched/mm.h>
15 #include <linux/pagemap.h>
16 #include <linux/refcount.h>
17 #include <linux/sched.h>
18 #include <linux/slab.h>
19 #include <linux/zstd.h>
20 #include "compression.h"
23 #define ZSTD_BTRFS_MAX_WINDOWLOG 17
24 #define ZSTD_BTRFS_MAX_INPUT (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
25 #define ZSTD_BTRFS_DEFAULT_LEVEL 3
26 #define ZSTD_BTRFS_MAX_LEVEL 15
27 /* 307s to avoid pathologically clashing with transaction commit */
28 #define ZSTD_BTRFS_RECLAIM_JIFFIES (307 * HZ)
30 static ZSTD_parameters zstd_get_btrfs_parameters(unsigned int level,
33 ZSTD_parameters params = ZSTD_getParams(level, src_len, 0);
35 if (params.cParams.windowLog > ZSTD_BTRFS_MAX_WINDOWLOG)
36 params.cParams.windowLog = ZSTD_BTRFS_MAX_WINDOWLOG;
37 WARN_ON(src_len > ZSTD_BTRFS_MAX_INPUT);
46 unsigned int req_level;
47 unsigned long last_used; /* jiffies */
48 struct list_head list;
49 struct list_head lru_list;
51 ZSTD_outBuffer out_buf;
55 * Zstd Workspace Management
57 * Zstd workspaces have different memory requirements depending on the level.
58 * The zstd workspaces are managed by having individual lists for each level
59 * and a global lru. Forward progress is maintained by protecting a max level
62 * Getting a workspace is done by using the bitmap to identify the levels that
63 * have available workspaces and scans up. This lets us recycle higher level
64 * workspaces because of the monotonic memory guarantee. A workspace's
65 * last_used is only updated if it is being used by the corresponding memory
66 * level. Putting a workspace involves adding it back to the appropriate places
67 * and adding it back to the lru if necessary.
69 * A timer is used to reclaim workspaces if they have not been used for
70 * ZSTD_BTRFS_RECLAIM_JIFFIES. This helps keep only active workspaces around.
71 * The upper bound is provided by the workqueue limit which is 2 (percpu limit).
74 struct zstd_workspace_manager {
75 const struct btrfs_compress_op *ops;
77 struct list_head lru_list;
78 struct list_head idle_ws[ZSTD_BTRFS_MAX_LEVEL];
79 unsigned long active_map;
80 wait_queue_head_t wait;
81 struct timer_list timer;
84 static struct zstd_workspace_manager wsm;
86 static size_t zstd_ws_mem_sizes[ZSTD_BTRFS_MAX_LEVEL];
88 static inline struct workspace *list_to_workspace(struct list_head *list)
90 return container_of(list, struct workspace, list);
94 * zstd_reclaim_timer_fn - reclaim timer
97 * This scans the lru_list and attempts to reclaim any workspace that hasn't
98 * been used for ZSTD_BTRFS_RECLAIM_JIFFIES.
100 static void zstd_reclaim_timer_fn(struct timer_list *timer)
102 unsigned long reclaim_threshold = jiffies - ZSTD_BTRFS_RECLAIM_JIFFIES;
103 struct list_head *pos, *next;
105 spin_lock(&wsm.lock);
107 if (list_empty(&wsm.lru_list)) {
108 spin_unlock(&wsm.lock);
112 list_for_each_prev_safe(pos, next, &wsm.lru_list) {
113 struct workspace *victim = container_of(pos, struct workspace,
117 if (time_after(victim->last_used, reclaim_threshold))
120 /* workspace is in use */
121 if (victim->req_level)
124 level = victim->level;
125 list_del(&victim->lru_list);
126 list_del(&victim->list);
127 wsm.ops->free_workspace(&victim->list);
129 if (list_empty(&wsm.idle_ws[level - 1]))
130 clear_bit(level - 1, &wsm.active_map);
134 if (!list_empty(&wsm.lru_list))
135 mod_timer(&wsm.timer, jiffies + ZSTD_BTRFS_RECLAIM_JIFFIES);
137 spin_unlock(&wsm.lock);
141 * zstd_calc_ws_mem_sizes - calculate monotonic memory bounds
143 * It is possible based on the level configurations that a higher level
144 * workspace uses less memory than a lower level workspace. In order to reuse
145 * workspaces, this must be made a monotonic relationship. This precomputes
146 * the required memory for each level and enforces the monotonicity between
147 * level and memory required.
149 static void zstd_calc_ws_mem_sizes(void)
154 for (level = 1; level <= ZSTD_BTRFS_MAX_LEVEL; level++) {
155 ZSTD_parameters params =
156 zstd_get_btrfs_parameters(level, ZSTD_BTRFS_MAX_INPUT);
159 ZSTD_CStreamWorkspaceBound(params.cParams),
160 ZSTD_DStreamWorkspaceBound(ZSTD_BTRFS_MAX_INPUT));
162 max_size = max_t(size_t, max_size, level_size);
163 zstd_ws_mem_sizes[level - 1] = max_size;
167 static void zstd_init_workspace_manager(void)
169 struct list_head *ws;
172 zstd_calc_ws_mem_sizes();
174 wsm.ops = &btrfs_zstd_compress;
175 spin_lock_init(&wsm.lock);
176 init_waitqueue_head(&wsm.wait);
177 timer_setup(&wsm.timer, zstd_reclaim_timer_fn, 0);
179 INIT_LIST_HEAD(&wsm.lru_list);
180 for (i = 0; i < ZSTD_BTRFS_MAX_LEVEL; i++)
181 INIT_LIST_HEAD(&wsm.idle_ws[i]);
183 ws = wsm.ops->alloc_workspace(ZSTD_BTRFS_MAX_LEVEL);
186 "BTRFS: cannot preallocate zstd compression workspace\n");
188 set_bit(ZSTD_BTRFS_MAX_LEVEL - 1, &wsm.active_map);
189 list_add(ws, &wsm.idle_ws[ZSTD_BTRFS_MAX_LEVEL - 1]);
193 static void zstd_cleanup_workspace_manager(void)
195 struct workspace *workspace;
198 spin_lock(&wsm.lock);
199 for (i = 0; i < ZSTD_BTRFS_MAX_LEVEL; i++) {
200 while (!list_empty(&wsm.idle_ws[i])) {
201 workspace = container_of(wsm.idle_ws[i].next,
202 struct workspace, list);
203 list_del(&workspace->list);
204 list_del(&workspace->lru_list);
205 wsm.ops->free_workspace(&workspace->list);
208 spin_unlock(&wsm.lock);
210 del_timer_sync(&wsm.timer);
214 * zstd_find_workspace - find workspace
215 * @level: compression level
217 * This iterates over the set bits in the active_map beginning at the requested
218 * compression level. This lets us utilize already allocated workspaces before
219 * allocating a new one. If the workspace is of a larger size, it is used, but
220 * the place in the lru_list and last_used times are not updated. This is to
221 * offer the opportunity to reclaim the workspace in favor of allocating an
222 * appropriately sized one in the future.
224 static struct list_head *zstd_find_workspace(unsigned int level)
226 struct list_head *ws;
227 struct workspace *workspace;
230 spin_lock(&wsm.lock);
231 for_each_set_bit_from(i, &wsm.active_map, ZSTD_BTRFS_MAX_LEVEL) {
232 if (!list_empty(&wsm.idle_ws[i])) {
233 ws = wsm.idle_ws[i].next;
234 workspace = list_to_workspace(ws);
236 /* keep its place if it's a lower level using this */
237 workspace->req_level = level;
238 if (level == workspace->level)
239 list_del(&workspace->lru_list);
240 if (list_empty(&wsm.idle_ws[i]))
241 clear_bit(i, &wsm.active_map);
242 spin_unlock(&wsm.lock);
246 spin_unlock(&wsm.lock);
252 * zstd_get_workspace - zstd's get_workspace
253 * @level: compression level
255 * If @level is 0, then any compression level can be used. Therefore, we begin
256 * scanning from 1. We first scan through possible workspaces and then after
257 * attempt to allocate a new workspace. If we fail to allocate one due to
258 * memory pressure, go to sleep waiting for the max level workspace to free up.
260 static struct list_head *zstd_get_workspace(unsigned int level)
262 struct list_head *ws;
263 unsigned int nofs_flag;
265 /* level == 0 means we can use any workspace */
270 ws = zstd_find_workspace(level);
274 nofs_flag = memalloc_nofs_save();
275 ws = wsm.ops->alloc_workspace(level);
276 memalloc_nofs_restore(nofs_flag);
281 prepare_to_wait(&wsm.wait, &wait, TASK_UNINTERRUPTIBLE);
283 finish_wait(&wsm.wait, &wait);
292 * zstd_put_workspace - zstd put_workspace
293 * @ws: list_head for the workspace
295 * When putting back a workspace, we only need to update the LRU if we are of
296 * the requested compression level. Here is where we continue to protect the
297 * max level workspace or update last_used accordingly. If the reclaim timer
298 * isn't set, it is also set here. Only the max level workspace tries and wakes
299 * up waiting workspaces.
301 static void zstd_put_workspace(struct list_head *ws)
303 struct workspace *workspace = list_to_workspace(ws);
305 spin_lock(&wsm.lock);
307 /* A node is only taken off the lru if we are the corresponding level */
308 if (workspace->req_level == workspace->level) {
309 /* Hide a max level workspace from reclaim */
310 if (list_empty(&wsm.idle_ws[ZSTD_BTRFS_MAX_LEVEL - 1])) {
311 INIT_LIST_HEAD(&workspace->lru_list);
313 workspace->last_used = jiffies;
314 list_add(&workspace->lru_list, &wsm.lru_list);
315 if (!timer_pending(&wsm.timer))
316 mod_timer(&wsm.timer,
317 jiffies + ZSTD_BTRFS_RECLAIM_JIFFIES);
321 set_bit(workspace->level - 1, &wsm.active_map);
322 list_add(&workspace->list, &wsm.idle_ws[workspace->level - 1]);
323 workspace->req_level = 0;
325 spin_unlock(&wsm.lock);
327 if (workspace->level == ZSTD_BTRFS_MAX_LEVEL)
328 cond_wake_up(&wsm.wait);
331 static void zstd_free_workspace(struct list_head *ws)
333 struct workspace *workspace = list_entry(ws, struct workspace, list);
335 kvfree(workspace->mem);
336 kfree(workspace->buf);
340 static struct list_head *zstd_alloc_workspace(unsigned int level)
342 struct workspace *workspace;
344 workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
346 return ERR_PTR(-ENOMEM);
348 workspace->size = zstd_ws_mem_sizes[level - 1];
349 workspace->level = level;
350 workspace->req_level = level;
351 workspace->last_used = jiffies;
352 workspace->mem = kvmalloc(workspace->size, GFP_KERNEL);
353 workspace->buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
354 if (!workspace->mem || !workspace->buf)
357 INIT_LIST_HEAD(&workspace->list);
358 INIT_LIST_HEAD(&workspace->lru_list);
360 return &workspace->list;
362 zstd_free_workspace(&workspace->list);
363 return ERR_PTR(-ENOMEM);
366 static int zstd_compress_pages(struct list_head *ws,
367 struct address_space *mapping,
370 unsigned long *out_pages,
371 unsigned long *total_in,
372 unsigned long *total_out)
374 struct workspace *workspace = list_entry(ws, struct workspace, list);
375 ZSTD_CStream *stream;
378 struct page *in_page = NULL; /* The current page to read */
379 struct page *out_page = NULL; /* The current page to write to */
380 unsigned long tot_in = 0;
381 unsigned long tot_out = 0;
382 unsigned long len = *total_out;
383 const unsigned long nr_dest_pages = *out_pages;
384 unsigned long max_out = nr_dest_pages * PAGE_SIZE;
385 ZSTD_parameters params = zstd_get_btrfs_parameters(workspace->req_level,
392 /* Initialize the stream */
393 stream = ZSTD_initCStream(params, len, workspace->mem,
396 pr_warn("BTRFS: ZSTD_initCStream failed\n");
401 /* map in the first page of input data */
402 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
403 workspace->in_buf.src = kmap(in_page);
404 workspace->in_buf.pos = 0;
405 workspace->in_buf.size = min_t(size_t, len, PAGE_SIZE);
408 /* Allocate and map in the output buffer */
409 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
410 if (out_page == NULL) {
414 pages[nr_pages++] = out_page;
415 workspace->out_buf.dst = kmap(out_page);
416 workspace->out_buf.pos = 0;
417 workspace->out_buf.size = min_t(size_t, max_out, PAGE_SIZE);
422 ret2 = ZSTD_compressStream(stream, &workspace->out_buf,
424 if (ZSTD_isError(ret2)) {
425 pr_debug("BTRFS: ZSTD_compressStream returned %d\n",
426 ZSTD_getErrorCode(ret2));
431 /* Check to see if we are making it bigger */
432 if (tot_in + workspace->in_buf.pos > 8192 &&
433 tot_in + workspace->in_buf.pos <
434 tot_out + workspace->out_buf.pos) {
439 /* We've reached the end of our output range */
440 if (workspace->out_buf.pos >= max_out) {
441 tot_out += workspace->out_buf.pos;
446 /* Check if we need more output space */
447 if (workspace->out_buf.pos == workspace->out_buf.size) {
448 tot_out += PAGE_SIZE;
449 max_out -= PAGE_SIZE;
451 if (nr_pages == nr_dest_pages) {
456 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
457 if (out_page == NULL) {
461 pages[nr_pages++] = out_page;
462 workspace->out_buf.dst = kmap(out_page);
463 workspace->out_buf.pos = 0;
464 workspace->out_buf.size = min_t(size_t, max_out,
468 /* We've reached the end of the input */
469 if (workspace->in_buf.pos >= len) {
470 tot_in += workspace->in_buf.pos;
474 /* Check if we need more input */
475 if (workspace->in_buf.pos == workspace->in_buf.size) {
482 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
483 workspace->in_buf.src = kmap(in_page);
484 workspace->in_buf.pos = 0;
485 workspace->in_buf.size = min_t(size_t, len, PAGE_SIZE);
491 ret2 = ZSTD_endStream(stream, &workspace->out_buf);
492 if (ZSTD_isError(ret2)) {
493 pr_debug("BTRFS: ZSTD_endStream returned %d\n",
494 ZSTD_getErrorCode(ret2));
499 tot_out += workspace->out_buf.pos;
502 if (workspace->out_buf.pos >= max_out) {
503 tot_out += workspace->out_buf.pos;
508 tot_out += PAGE_SIZE;
509 max_out -= PAGE_SIZE;
511 if (nr_pages == nr_dest_pages) {
516 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
517 if (out_page == NULL) {
521 pages[nr_pages++] = out_page;
522 workspace->out_buf.dst = kmap(out_page);
523 workspace->out_buf.pos = 0;
524 workspace->out_buf.size = min_t(size_t, max_out, PAGE_SIZE);
527 if (tot_out >= tot_in) {
534 *total_out = tot_out;
536 *out_pages = nr_pages;
547 static int zstd_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
549 struct workspace *workspace = list_entry(ws, struct workspace, list);
550 struct page **pages_in = cb->compressed_pages;
551 u64 disk_start = cb->start;
552 struct bio *orig_bio = cb->orig_bio;
553 size_t srclen = cb->compressed_len;
554 ZSTD_DStream *stream;
556 unsigned long page_in_index = 0;
557 unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE);
558 unsigned long buf_start;
559 unsigned long total_out = 0;
561 stream = ZSTD_initDStream(
562 ZSTD_BTRFS_MAX_INPUT, workspace->mem, workspace->size);
564 pr_debug("BTRFS: ZSTD_initDStream failed\n");
569 workspace->in_buf.src = kmap(pages_in[page_in_index]);
570 workspace->in_buf.pos = 0;
571 workspace->in_buf.size = min_t(size_t, srclen, PAGE_SIZE);
573 workspace->out_buf.dst = workspace->buf;
574 workspace->out_buf.pos = 0;
575 workspace->out_buf.size = PAGE_SIZE;
580 ret2 = ZSTD_decompressStream(stream, &workspace->out_buf,
582 if (ZSTD_isError(ret2)) {
583 pr_debug("BTRFS: ZSTD_decompressStream returned %d\n",
584 ZSTD_getErrorCode(ret2));
588 buf_start = total_out;
589 total_out += workspace->out_buf.pos;
590 workspace->out_buf.pos = 0;
592 ret = btrfs_decompress_buf2page(workspace->out_buf.dst,
593 buf_start, total_out, disk_start, orig_bio);
597 if (workspace->in_buf.pos >= srclen)
600 /* Check if we've hit the end of a frame */
604 if (workspace->in_buf.pos == workspace->in_buf.size) {
605 kunmap(pages_in[page_in_index++]);
606 if (page_in_index >= total_pages_in) {
607 workspace->in_buf.src = NULL;
612 workspace->in_buf.src = kmap(pages_in[page_in_index]);
613 workspace->in_buf.pos = 0;
614 workspace->in_buf.size = min_t(size_t, srclen, PAGE_SIZE);
618 zero_fill_bio(orig_bio);
620 if (workspace->in_buf.src)
621 kunmap(pages_in[page_in_index]);
625 static int zstd_decompress(struct list_head *ws, unsigned char *data_in,
626 struct page *dest_page,
627 unsigned long start_byte,
628 size_t srclen, size_t destlen)
630 struct workspace *workspace = list_entry(ws, struct workspace, list);
631 ZSTD_DStream *stream;
634 unsigned long total_out = 0;
635 unsigned long pg_offset = 0;
638 stream = ZSTD_initDStream(
639 ZSTD_BTRFS_MAX_INPUT, workspace->mem, workspace->size);
641 pr_warn("BTRFS: ZSTD_initDStream failed\n");
646 destlen = min_t(size_t, destlen, PAGE_SIZE);
648 workspace->in_buf.src = data_in;
649 workspace->in_buf.pos = 0;
650 workspace->in_buf.size = srclen;
652 workspace->out_buf.dst = workspace->buf;
653 workspace->out_buf.pos = 0;
654 workspace->out_buf.size = PAGE_SIZE;
657 while (pg_offset < destlen
658 && workspace->in_buf.pos < workspace->in_buf.size) {
659 unsigned long buf_start;
660 unsigned long buf_offset;
663 /* Check if the frame is over and we still need more input */
665 pr_debug("BTRFS: ZSTD_decompressStream ended early\n");
669 ret2 = ZSTD_decompressStream(stream, &workspace->out_buf,
671 if (ZSTD_isError(ret2)) {
672 pr_debug("BTRFS: ZSTD_decompressStream returned %d\n",
673 ZSTD_getErrorCode(ret2));
678 buf_start = total_out;
679 total_out += workspace->out_buf.pos;
680 workspace->out_buf.pos = 0;
682 if (total_out <= start_byte)
685 if (total_out > start_byte && buf_start < start_byte)
686 buf_offset = start_byte - buf_start;
690 bytes = min_t(unsigned long, destlen - pg_offset,
691 workspace->out_buf.size - buf_offset);
693 kaddr = kmap_atomic(dest_page);
694 memcpy(kaddr + pg_offset, workspace->out_buf.dst + buf_offset,
696 kunmap_atomic(kaddr);
702 if (pg_offset < destlen) {
703 kaddr = kmap_atomic(dest_page);
704 memset(kaddr + pg_offset, 0, destlen - pg_offset);
705 kunmap_atomic(kaddr);
710 static unsigned int zstd_set_level(unsigned int level)
713 return ZSTD_BTRFS_DEFAULT_LEVEL;
715 return min_t(unsigned int, level, ZSTD_BTRFS_MAX_LEVEL);
718 const struct btrfs_compress_op btrfs_zstd_compress = {
719 .init_workspace_manager = zstd_init_workspace_manager,
720 .cleanup_workspace_manager = zstd_cleanup_workspace_manager,
721 .get_workspace = zstd_get_workspace,
722 .put_workspace = zstd_put_workspace,
723 .alloc_workspace = zstd_alloc_workspace,
724 .free_workspace = zstd_free_workspace,
725 .compress_pages = zstd_compress_pages,
726 .decompress_bio = zstd_decompress_bio,
727 .decompress = zstd_decompress,
728 .set_level = zstd_set_level,