From 5c1aab1dd5445ed8bdcdbb575abc1b0d7ee5b2e7 Mon Sep 17 00:00:00 2001 From: Nick Terrell Date: Wed, 9 Aug 2017 19:39:02 -0700 Subject: btrfs: Add zstd support Add zstd compression and decompression support to BtrFS. zstd at its fastest level compresses almost as well as zlib, while offering much faster compression and decompression, approaching lzo speeds. I benchmarked btrfs with zstd compression against no compression, lzo compression, and zlib compression. I benchmarked two scenarios. Copying a set of files to btrfs, and then reading the files. Copying a tarball to btrfs, extracting it to btrfs, and then reading the extracted files. After every operation, I call `sync` and include the sync time. Between every pair of operations I unmount and remount the filesystem to avoid caching. The benchmark files can be found in the upstream zstd source repository under `contrib/linux-kernel/{btrfs-benchmark.sh,btrfs-extract-benchmark.sh}` [1] [2]. I ran the benchmarks on a Ubuntu 14.04 VM with 2 cores and 4 GiB of RAM. The VM is running on a MacBook Pro with a 3.1 GHz Intel Core i7 processor, 16 GB of RAM, and a SSD. The first compression benchmark is copying 10 copies of the unzipped Silesia corpus [3] into a BtrFS filesystem mounted with `-o compress-force=Method`. The decompression benchmark times how long it takes to `tar` all 10 copies into `/dev/null`. The compression ratio is measured by comparing the output of `df` and `du`. See the benchmark file [1] for details. I benchmarked multiple zstd compression levels, although the patch uses zstd level 1. | Method | Ratio | Compression MB/s | Decompression speed | |---------|-------|------------------|---------------------| | None | 0.99 | 504 | 686 | | lzo | 1.66 | 398 | 442 | | zlib | 2.58 | 65 | 241 | | zstd 1 | 2.57 | 260 | 383 | | zstd 3 | 2.71 | 174 | 408 | | zstd 6 | 2.87 | 70 | 398 | | zstd 9 | 2.92 | 43 | 406 | | zstd 12 | 2.93 | 21 | 408 | | zstd 15 | 3.01 | 11 | 354 | The next benchmark first copies `linux-4.11.6.tar` [4] to btrfs. Then it measures the compression ratio, extracts the tar, and deletes the tar. Then it measures the compression ratio again, and `tar`s the extracted files into `/dev/null`. See the benchmark file [2] for details. | Method | Tar Ratio | Extract Ratio | Copy (s) | Extract (s)| Read (s) | |--------|-----------|---------------|----------|------------|----------| | None | 0.97 | 0.78 | 0.981 | 5.501 | 8.807 | | lzo | 2.06 | 1.38 | 1.631 | 8.458 | 8.585 | | zlib | 3.40 | 1.86 | 7.750 | 21.544 | 11.744 | | zstd 1 | 3.57 | 1.85 | 2.579 | 11.479 | 9.389 | [1] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/btrfs-benchmark.sh [2] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/btrfs-extract-benchmark.sh [3] http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia [4] https://cdn.kernel.org/pub/linux/kernel/v4.x/linux-4.11.6.tar.xz zstd source repository: https://github.com/facebook/zstd Signed-off-by: Nick Terrell Signed-off-by: Chris Mason --- fs/btrfs/compression.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'fs/btrfs/compression.h') diff --git a/fs/btrfs/compression.h b/fs/btrfs/compression.h index 87f6d3332163..2269e00854d8 100644 --- a/fs/btrfs/compression.h +++ b/fs/btrfs/compression.h @@ -99,8 +99,9 @@ enum btrfs_compression_type { BTRFS_COMPRESS_NONE = 0, BTRFS_COMPRESS_ZLIB = 1, BTRFS_COMPRESS_LZO = 2, - BTRFS_COMPRESS_TYPES = 2, - BTRFS_COMPRESS_LAST = 3, + BTRFS_COMPRESS_ZSTD = 3, + BTRFS_COMPRESS_TYPES = 3, + BTRFS_COMPRESS_LAST = 4, }; struct btrfs_compress_op { @@ -128,5 +129,6 @@ struct btrfs_compress_op { extern const struct btrfs_compress_op btrfs_zlib_compress; extern const struct btrfs_compress_op btrfs_lzo_compress; +extern const struct btrfs_compress_op btrfs_zstd_compress; #endif -- cgit v1.2.3 From c2fcdcdf36bba08c5d2fbf4f17c2d8a944bfd4df Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Mon, 17 Jul 2017 16:52:58 +0300 Subject: Btrfs: add skeleton code for compression heuristic Add skeleton code for compresison heuristics. Now it iterates over all the pages, but in the end always says "yes, compress please", ie it does not change the current behaviour. In the future we're going to add various heuristics to analyze the data. This patch can be used as a baseline for measuring if the effectivness and performance. Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ enhanced changelog, modified comments ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 33 +++++++++++++++++++++++++++++++++ fs/btrfs/compression.h | 2 ++ fs/btrfs/inode.c | 8 ++++---- 3 files changed, 39 insertions(+), 4 deletions(-) (limited to 'fs/btrfs/compression.h') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 3896bd0175ec..883ecc58fd0d 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -1047,3 +1047,36 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } + +/* + * Compression heuristic. + * + * For now is's a naive and optimistic 'return true', we'll extend the logic to + * quickly (compared to direct compression) detect data characteristics + * (compressible/uncompressible) to avoid wasting CPU time on uncompressible + * data. + * + * The following types of analysis can be performed: + * - detect mostly zero data + * - detect data with low "byte set" size (text, etc) + * - detect data with low/high "core byte" set + * + * Return non-zero if the compression should be done, 0 otherwise. + */ +int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) +{ + u64 index = start >> PAGE_SHIFT; + u64 end_index = end >> PAGE_SHIFT; + struct page *page; + int ret = 1; + + while (index <= end_index) { + page = find_get_page(inode->i_mapping, index); + kmap(page); + kunmap(page); + put_page(page); + index++; + } + + return ret; +} diff --git a/fs/btrfs/compression.h b/fs/btrfs/compression.h index 87f6d3332163..8508ba6b9aef 100644 --- a/fs/btrfs/compression.h +++ b/fs/btrfs/compression.h @@ -129,4 +129,6 @@ struct btrfs_compress_op { extern const struct btrfs_compress_op btrfs_zlib_compress; extern const struct btrfs_compress_op btrfs_lzo_compress; +int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end); + #endif diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index 467b9477dac4..0bd008b9e0d1 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -392,7 +392,7 @@ static noinline int add_async_extent(struct async_cow *cow, return 0; } -static inline int inode_need_compress(struct inode *inode) +static inline int inode_need_compress(struct inode *inode, u64 start, u64 end) { struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); @@ -405,7 +405,7 @@ static inline int inode_need_compress(struct inode *inode) if (btrfs_test_opt(fs_info, COMPRESS) || BTRFS_I(inode)->flags & BTRFS_INODE_COMPRESS || BTRFS_I(inode)->force_compress) - return 1; + return btrfs_compress_heuristic(inode, start, end); return 0; } @@ -503,7 +503,7 @@ again: * inode has not been flagged as nocompress. This flag can * change at any time if we discover bad compression ratios. */ - if (inode_need_compress(inode)) { + if (inode_need_compress(inode, start, end)) { WARN_ON(pages); pages = kcalloc(nr_pages, sizeof(struct page *), GFP_NOFS); if (!pages) { @@ -1576,7 +1576,7 @@ static int run_delalloc_range(void *private_data, struct page *locked_page, } else if (BTRFS_I(inode)->flags & BTRFS_INODE_PREALLOC && !force_cow) { ret = run_delalloc_nocow(inode, locked_page, start, end, page_started, 0, nr_written); - } else if (!inode_need_compress(inode)) { + } else if (!inode_need_compress(inode, start, end)) { ret = cow_file_range(inode, locked_page, start, end, end, page_started, nr_written, 1, NULL); } else { -- cgit v1.2.3 From dc2f29212a2648164b054016dc5b948bf0fc92d5 Mon Sep 17 00:00:00 2001 From: Anand Jain Date: Sun, 13 Aug 2017 12:02:41 +0800 Subject: btrfs: remove unused BTRFS_COMPRESS_LAST We aren't using this define, so removing it. Signed-off-by: Anand Jain Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/compression.h | 1 - 1 file changed, 1 deletion(-) (limited to 'fs/btrfs/compression.h') diff --git a/fs/btrfs/compression.h b/fs/btrfs/compression.h index 8508ba6b9aef..3b1b0ac15fdc 100644 --- a/fs/btrfs/compression.h +++ b/fs/btrfs/compression.h @@ -100,7 +100,6 @@ enum btrfs_compression_type { BTRFS_COMPRESS_ZLIB = 1, BTRFS_COMPRESS_LZO = 2, BTRFS_COMPRESS_TYPES = 2, - BTRFS_COMPRESS_LAST = 3, }; struct btrfs_compress_op { -- cgit v1.2.3 From f51d2b59120ff364a5e612a594ed358767e1cd09 Mon Sep 17 00:00:00 2001 From: David Sterba Date: Fri, 15 Sep 2017 17:36:57 +0200 Subject: btrfs: allow to set compression level for zlib Preliminary support for setting compression level for zlib, the following works: $ mount -o compess=zlib # default $ mount -o compess=zlib0 # same $ mount -o compess=zlib9 # level 9, slower sync, less data $ mount -o compess=zlib1 # level 1, faster sync, more data $ mount -o remount,compress=zlib3 # level set by remount The compress-force works the same as compress'. The level is visible in the same format in /proc/mounts. Level set via file property does not work yet. Required patch: "btrfs: prepare for extensions in compression options" Signed-off-by: David Sterba --- fs/btrfs/compression.c | 20 +++++++++++++++++++- fs/btrfs/compression.h | 6 +++++- fs/btrfs/ctree.h | 1 + fs/btrfs/inode.c | 5 ++++- fs/btrfs/lzo.c | 5 +++++ fs/btrfs/super.c | 8 ++++++-- fs/btrfs/zlib.c | 15 ++++++++++++++- fs/btrfs/zstd.c | 5 +++++ 8 files changed, 59 insertions(+), 6 deletions(-) (limited to 'fs/btrfs/compression.h') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 8bdd3dc6c4dc..3e452525f8ad 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -884,6 +884,11 @@ static void free_workspaces(void) * Given an address space and start and length, compress the bytes into @pages * that are allocated on demand. * + * @type_level is encoded algorithm and level, where level 0 means whatever + * default the algorithm chooses and is opaque here; + * - compression algo are 0-3 + * - the level are bits 4-7 + * * @out_pages is an in/out parameter, holds maximum number of pages to allocate * and returns number of actually allocated pages * @@ -898,7 +903,7 @@ static void free_workspaces(void) * @max_out tells us the max number of bytes that we're allowed to * stuff into pages */ -int btrfs_compress_pages(int type, struct address_space *mapping, +int btrfs_compress_pages(unsigned int type_level, struct address_space *mapping, u64 start, struct page **pages, unsigned long *out_pages, unsigned long *total_in, @@ -906,9 +911,11 @@ int btrfs_compress_pages(int type, struct address_space *mapping, { struct list_head *workspace; int ret; + int type = type_level & 0xF; workspace = find_workspace(type); + btrfs_compress_op[type - 1]->set_level(workspace, type_level); ret = btrfs_compress_op[type-1]->compress_pages(workspace, mapping, start, pages, out_pages, @@ -1098,3 +1105,14 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) return ret; } + +unsigned int btrfs_compress_str2level(const char *str) +{ + if (strncmp(str, "zlib", 4) != 0) + return 0; + + if ('1' <= str[4] && str[4] <= '9' ) + return str[4] - '0'; + + return 0; +} diff --git a/fs/btrfs/compression.h b/fs/btrfs/compression.h index d2781ff8f994..da20755ebf21 100644 --- a/fs/btrfs/compression.h +++ b/fs/btrfs/compression.h @@ -76,7 +76,7 @@ struct compressed_bio { void btrfs_init_compress(void); void btrfs_exit_compress(void); -int btrfs_compress_pages(int type, struct address_space *mapping, +int btrfs_compress_pages(unsigned int type_level, struct address_space *mapping, u64 start, struct page **pages, unsigned long *out_pages, unsigned long *total_in, @@ -95,6 +95,8 @@ blk_status_t btrfs_submit_compressed_write(struct inode *inode, u64 start, blk_status_t btrfs_submit_compressed_read(struct inode *inode, struct bio *bio, int mirror_num, unsigned long bio_flags); +unsigned btrfs_compress_str2level(const char *str); + enum btrfs_compression_type { BTRFS_COMPRESS_NONE = 0, BTRFS_COMPRESS_ZLIB = 1, @@ -124,6 +126,8 @@ struct btrfs_compress_op { struct page *dest_page, unsigned long start_byte, size_t srclen, size_t destlen); + + void (*set_level)(struct list_head *ws, unsigned int type); }; extern const struct btrfs_compress_op btrfs_zlib_compress; diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 7bda8429e93f..2c02d9524055 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -790,6 +790,7 @@ struct btrfs_fs_info { */ unsigned long pending_changes; unsigned long compress_type:4; + unsigned int compress_level; int commit_interval; /* * It is a suggestive number, the read side is safe even it gets a diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index f2787cab6f3b..3f1b53f85735 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -539,7 +539,10 @@ again: */ extent_range_clear_dirty_for_io(inode, start, end); redirty = 1; - ret = btrfs_compress_pages(compress_type, + + /* Compression level is applied here and only here */ + ret = btrfs_compress_pages( + compress_type | (fs_info->compress_level << 4), inode->i_mapping, start, pages, &nr_pages, diff --git a/fs/btrfs/lzo.c b/fs/btrfs/lzo.c index d433e75d489a..6c7f18cd3b61 100644 --- a/fs/btrfs/lzo.c +++ b/fs/btrfs/lzo.c @@ -430,10 +430,15 @@ out: return ret; } +static void lzo_set_level(struct list_head *ws, unsigned int type) +{ +} + const struct btrfs_compress_op btrfs_lzo_compress = { .alloc_workspace = lzo_alloc_workspace, .free_workspace = lzo_free_workspace, .compress_pages = lzo_compress_pages, .decompress_bio = lzo_decompress_bio, .decompress = lzo_decompress, + .set_level = lzo_set_level, }; diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c index 4fb7eefb80ae..57f3f9600e18 100644 --- a/fs/btrfs/super.c +++ b/fs/btrfs/super.c @@ -508,6 +508,8 @@ int btrfs_parse_options(struct btrfs_fs_info *info, char *options, strncmp(args[0].from, "zlib", 4) == 0) { compress_type = "zlib"; info->compress_type = BTRFS_COMPRESS_ZLIB; + info->compress_level = + btrfs_compress_str2level(args[0].from); btrfs_set_opt(info->mount_opt, COMPRESS); btrfs_clear_opt(info->mount_opt, NODATACOW); btrfs_clear_opt(info->mount_opt, NODATASUM); @@ -555,9 +557,9 @@ int btrfs_parse_options(struct btrfs_fs_info *info, char *options, compress_force != saved_compress_force)) || (!btrfs_test_opt(info, COMPRESS) && no_compress == 1)) { - btrfs_info(info, "%s %s compression", + btrfs_info(info, "%s %s compression, level %d", (compress_force) ? "force" : "use", - compress_type); + compress_type, info->compress_level); } compress_force = false; break; @@ -1258,6 +1260,8 @@ static int btrfs_show_options(struct seq_file *seq, struct dentry *dentry) seq_printf(seq, ",compress-force=%s", compress_type); else seq_printf(seq, ",compress=%s", compress_type); + if (info->compress_level) + seq_printf(seq, "%d", info->compress_level); } if (btrfs_test_opt(info, NOSSD)) seq_puts(seq, ",nossd"); diff --git a/fs/btrfs/zlib.c b/fs/btrfs/zlib.c index c248f9286366..2b52950dc2c6 100644 --- a/fs/btrfs/zlib.c +++ b/fs/btrfs/zlib.c @@ -37,6 +37,7 @@ struct workspace { z_stream strm; char *buf; struct list_head list; + int level; }; static void zlib_free_workspace(struct list_head *ws) @@ -96,7 +97,7 @@ static int zlib_compress_pages(struct list_head *ws, *total_out = 0; *total_in = 0; - if (Z_OK != zlib_deflateInit(&workspace->strm, 3)) { + if (Z_OK != zlib_deflateInit(&workspace->strm, workspace->level)) { pr_warn("BTRFS: deflateInit failed\n"); ret = -EIO; goto out; @@ -402,10 +403,22 @@ next: return ret; } +static void zlib_set_level(struct list_head *ws, unsigned int type) +{ + struct workspace *workspace = list_entry(ws, struct workspace, list); + unsigned level = (type & 0xF0) >> 4; + + if (level > 9) + level = 9; + + workspace->level = level > 0 ? level : 3; +} + const struct btrfs_compress_op btrfs_zlib_compress = { .alloc_workspace = zlib_alloc_workspace, .free_workspace = zlib_free_workspace, .compress_pages = zlib_compress_pages, .decompress_bio = zlib_decompress_bio, .decompress = zlib_decompress, + .set_level = zlib_set_level, }; diff --git a/fs/btrfs/zstd.c b/fs/btrfs/zstd.c index 607ce47b483a..17f2dd8fddb8 100644 --- a/fs/btrfs/zstd.c +++ b/fs/btrfs/zstd.c @@ -423,10 +423,15 @@ finish: return ret; } +static void zstd_set_level(struct list_head *ws, unsigned int type) +{ +} + const struct btrfs_compress_op btrfs_zstd_compress = { .alloc_workspace = zstd_alloc_workspace, .free_workspace = zstd_free_workspace, .compress_pages = zstd_compress_pages, .decompress_bio = zstd_decompress_bio, .decompress = zstd_decompress, + .set_level = zstd_set_level, }; -- cgit v1.2.3