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.c | 1 + 1 file changed, 1 insertion(+) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index d2ef9ac2a630..4ff42d18a64d 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -704,6 +704,7 @@ static struct { static const struct btrfs_compress_op * const btrfs_compress_op[] = { &btrfs_zlib_compress, &btrfs_lzo_compress, + &btrfs_zstd_compress, }; void __init btrfs_init_compress(void) -- cgit v1.2.3 From 26b28dce50091ae36ebb0bf9cb814a43861f0641 Mon Sep 17 00:00:00 2001 From: Nick Terrell Date: Thu, 29 Jun 2017 10:57:26 -0700 Subject: btrfs: Keep one more workspace around find_workspace() allocates up to num_online_cpus() + 1 workspaces. free_workspace() will only keep num_online_cpus() workspaces. When (de)compressing we will allocate num_online_cpus() + 1 workspaces, then free one, and repeat. Instead, we can just keep num_online_cpus() + 1 workspaces around, and never have to allocate/free another workspace in the common case. I tested on a Ubuntu 14.04 VM with 2 cores and 4 GiB of RAM. I mounted a BtrFS partition with -o compress-force={lzo,zlib,zstd} and logged whenever a workspace was allocated of freed. Then I copied vmlinux (527 MB) to the partition. Before the patch, during the copy it would allocate and free 5-6 workspaces. After, it only allocated the initial 3. This held true for lzo, zlib, and zstd. The time it took to execute cp vmlinux /mnt/btrfs && sync dropped from 1.70s to 1.44s with lzo compression, and from 2.04s to 1.80s for zstd compression. Signed-off-by: Nick Terrell Reviewed-by: Omar Sandoval Signed-off-by: David Sterba --- fs/btrfs/compression.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index d2ef9ac2a630..3896bd0175ec 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -825,7 +825,7 @@ static void free_workspace(int type, struct list_head *workspace) int *free_ws = &btrfs_comp_ws[idx].free_ws; spin_lock(ws_lock); - if (*free_ws < num_online_cpus()) { + if (*free_ws <= num_online_cpus()) { list_add(workspace, idle_ws); (*free_ws)++; spin_unlock(ws_lock); -- 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.c') 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 cf1167d5c1abf3bc42b2a1562bfa7937c05337e2 Mon Sep 17 00:00:00 2001 From: Liu Bo Date: Wed, 20 Sep 2017 17:50:18 -0600 Subject: Btrfs: fix kernel oops while reading compressed data The kernel oops happens at kernel BUG at fs/btrfs/extent_io.c:2104! ... RIP: clean_io_failure+0x263/0x2a0 [btrfs] It's showing that read-repair code is using an improper mirror index. This is due to the fact that compression read's endio hasn't recorded the failed mirror index in %cb->orig_bio. With this, btrfs's read-repair can work properly on reading compressed data. Signed-off-by: Liu Bo Reported-by: Paul Jones Tested-by: Paul Jones Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/compression.c | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 883ecc58fd0d..c6aa53c4c102 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -107,6 +107,7 @@ static void end_compressed_bio_read(struct bio *bio) struct inode *inode; struct page *page; unsigned long index; + unsigned int mirror = btrfs_io_bio(bio)->mirror_num; int ret; if (bio->bi_status) @@ -118,6 +119,14 @@ static void end_compressed_bio_read(struct bio *bio) if (!refcount_dec_and_test(&cb->pending_bios)) goto out; + /* + * Record the correct mirror_num in cb->orig_bio so that + * read-repair can work properly. + */ + ASSERT(btrfs_io_bio(cb->orig_bio)); + btrfs_io_bio(cb->orig_bio)->mirror_num = mirror; + cb->mirror_num = mirror; + inode = cb->inode; ret = check_compressed_csum(BTRFS_I(inode), cb, (u64)bio->bi_iter.bi_sector << 9); -- cgit v1.2.3 From e6311f240c946788131ba2b97e14f37312688072 Mon Sep 17 00:00:00 2001 From: Liu Bo Date: Wed, 20 Sep 2017 17:50:19 -0600 Subject: Btrfs: skip checksum when reading compressed data if some IO have failed Currently even if the underlying disk reports failure on IO, compressed read endio still gets to verify checksum and reports it as a checksum error. In fact, if some IO have failed during reading a compressed data extent , there's no way the checksum could match, therefore, we can skip that in order to return error quickly to the upper layer. Please note that we need to do this after recording the failed mirror index so that read-repair in the upper layer's endio can work properly. Signed-off-by: Liu Bo Tested-by: Paul Jones Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/compression.c | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index c6aa53c4c102..fc31af98a41b 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -108,7 +108,7 @@ static void end_compressed_bio_read(struct bio *bio) struct page *page; unsigned long index; unsigned int mirror = btrfs_io_bio(bio)->mirror_num; - int ret; + int ret = 0; if (bio->bi_status) cb->errors = 1; @@ -127,6 +127,13 @@ static void end_compressed_bio_read(struct bio *bio) btrfs_io_bio(cb->orig_bio)->mirror_num = mirror; cb->mirror_num = mirror; + /* + * Some IO in this cb have failed, just skip checksum as there + * is no way it could be correct. + */ + if (cb->errors == 1) + goto csum_failed; + inode = cb->inode; ret = check_compressed_csum(BTRFS_I(inode), cb, (u64)bio->bi_iter.bi_sector << 9); -- cgit v1.2.3 From 2dbe0c77186c691386b74391039899808a4d3f59 Mon Sep 17 00:00:00 2001 From: Anand Jain Date: Sat, 14 Oct 2017 08:35:56 +0800 Subject: btrfs: use BLK_STS defines where needed At few places we could use BLK_STS_OK and BLK_STS_NOSUPP. Signed-off-by: Anand Jain Reviewed-by: Satoru Taekeuchi Reviewed-by: David Sterba [ dropped first hunk btrfs_endio_direct_read ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 3 ++- fs/btrfs/inode.c | 2 +- fs/btrfs/volumes.c | 2 +- 3 files changed, 4 insertions(+), 3 deletions(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 280384bf34f1..8bdd3dc6c4dc 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -255,7 +255,8 @@ static void end_compressed_bio_write(struct bio *bio) cb->start, cb->start + cb->len - 1, NULL, - bio->bi_status ? 0 : 1); + bio->bi_status ? + BLK_STS_OK : BLK_STS_NOTSUPP); cb->compressed_pages[0]->mapping = NULL; end_compressed_writeback(inode, cb); diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index a11f87fa79d0..f2787cab6f3b 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -8485,7 +8485,7 @@ static void btrfs_end_dio_bio(struct bio *bio) if (dip->errors) { bio_io_error(dip->orig_bio); } else { - dip->dio_bio->bi_status = 0; + dip->dio_bio->bi_status = BLK_STS_OK; bio_endio(dip->orig_bio); } out: diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c index 4931b2df4043..56ed01f8d4df 100644 --- a/fs/btrfs/volumes.c +++ b/fs/btrfs/volumes.c @@ -6029,7 +6029,7 @@ static void btrfs_end_bio(struct bio *bio) * this bio is actually up to date, we didn't * go over the max number of errors */ - bio->bi_status = 0; + bio->bi_status = BLK_STS_OK; } btrfs_end_bbio(bbio, bio); -- 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.c') 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 From fa4d885a482ef52ad3efa12a5799a3f6408b0718 Mon Sep 17 00:00:00 2001 From: Adam Borowski Date: Fri, 15 Sep 2017 17:36:58 +0200 Subject: btrfs: allow setting zlib compression level via :9 This is bikeshedding, but it seems people are drastically more likely to understand "zlib:9" as compression level rather than an algorithm version compared to "zlib9". Based on feedback on the mailinglist, the ":9" will be the only accepted syntax. The level must be a single digit. Unrecognized format will result to the default, for forward compatibility in a similar way the compression algorithm specifier was relaxed in commit a7164fa4e055daf6368c ("btrfs: prepare for extensions in compression options"). Signed-off-by: Adam Borowski Reviewed-by: David Sterba [ tighten the accepted format ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 5 +++-- fs/btrfs/super.c | 2 +- 2 files changed, 4 insertions(+), 3 deletions(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 3e452525f8ad..083f9c485875 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -1111,8 +1111,9 @@ 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'; + /* Accepted form: zlib:1 up to zlib:9 and nothing left after the number */ + if (str[4] == ':' && '1' <= str[5] && str[5] <= '9' && str[6] == 0) + return str[5] - '0'; return 0; } diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c index 57f3f9600e18..65af029559b5 100644 --- a/fs/btrfs/super.c +++ b/fs/btrfs/super.c @@ -1261,7 +1261,7 @@ static int btrfs_show_options(struct seq_file *seq, struct dentry *dentry) else seq_printf(seq, ",compress=%s", compress_type); if (info->compress_level) - seq_printf(seq, "%d", info->compress_level); + seq_printf(seq, ":%d", info->compress_level); } if (btrfs_test_opt(info, NOSSD)) seq_puts(seq, ",nossd"); -- cgit v1.2.3 From 4e439a0b184f014a5833fa468af36cc9f59b8fb1 Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:36 +0300 Subject: Btrfs: compression: separate heuristic/compression workspaces Compression heuristic itself is not a compression type, as current infrastructure provides workspaces for several compression types, it's difficult to just add heuristic workspace. Just refactor the code to support compression/heuristic workspaces with maximum code sharing and minimum changes in it. Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ coding style fixes ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 139 ++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 121 insertions(+), 18 deletions(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 083f9c485875..b155542c5e6b 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -707,7 +707,34 @@ out: return ret; } -static struct { + +struct heuristic_ws { + struct list_head list; +}; + +static void free_heuristic_ws(struct list_head *ws) +{ + struct heuristic_ws *workspace; + + workspace = list_entry(ws, struct heuristic_ws, list); + + kfree(workspace); +} + +static struct list_head *alloc_heuristic_ws(void) +{ + struct heuristic_ws *ws; + + ws = kzalloc(sizeof(*ws), GFP_KERNEL); + if (!ws) + return ERR_PTR(-ENOMEM); + + INIT_LIST_HEAD(&ws->list); + + return &ws->list; +} + +struct workspaces_list { struct list_head idle_ws; spinlock_t ws_lock; /* Number of free workspaces */ @@ -716,7 +743,11 @@ static struct { atomic_t total_ws; /* Waiters for a free workspace */ wait_queue_head_t ws_wait; -} btrfs_comp_ws[BTRFS_COMPRESS_TYPES]; +}; + +static struct workspaces_list btrfs_comp_ws[BTRFS_COMPRESS_TYPES]; + +static struct workspaces_list btrfs_heuristic_ws; static const struct btrfs_compress_op * const btrfs_compress_op[] = { &btrfs_zlib_compress, @@ -726,11 +757,25 @@ static const struct btrfs_compress_op * const btrfs_compress_op[] = { void __init btrfs_init_compress(void) { + struct list_head *workspace; int i; - for (i = 0; i < BTRFS_COMPRESS_TYPES; i++) { - struct list_head *workspace; + INIT_LIST_HEAD(&btrfs_heuristic_ws.idle_ws); + spin_lock_init(&btrfs_heuristic_ws.ws_lock); + atomic_set(&btrfs_heuristic_ws.total_ws, 0); + init_waitqueue_head(&btrfs_heuristic_ws.ws_wait); + workspace = alloc_heuristic_ws(); + if (IS_ERR(workspace)) { + pr_warn( + "BTRFS: cannot preallocate heuristic workspace, will try later\n"); + } else { + atomic_set(&btrfs_heuristic_ws.total_ws, 1); + btrfs_heuristic_ws.free_ws = 1; + list_add(workspace, &btrfs_heuristic_ws.idle_ws); + } + + for (i = 0; i < BTRFS_COMPRESS_TYPES; i++) { INIT_LIST_HEAD(&btrfs_comp_ws[i].idle_ws); spin_lock_init(&btrfs_comp_ws[i].ws_lock); atomic_set(&btrfs_comp_ws[i].total_ws, 0); @@ -757,18 +802,32 @@ void __init btrfs_init_compress(void) * Preallocation makes a forward progress guarantees and we do not return * errors. */ -static struct list_head *find_workspace(int type) +static struct list_head *__find_workspace(int type, bool heuristic) { struct list_head *workspace; int cpus = num_online_cpus(); int idx = type - 1; unsigned nofs_flag; + struct list_head *idle_ws; + spinlock_t *ws_lock; + atomic_t *total_ws; + wait_queue_head_t *ws_wait; + int *free_ws; + + if (heuristic) { + idle_ws = &btrfs_heuristic_ws.idle_ws; + ws_lock = &btrfs_heuristic_ws.ws_lock; + total_ws = &btrfs_heuristic_ws.total_ws; + ws_wait = &btrfs_heuristic_ws.ws_wait; + free_ws = &btrfs_heuristic_ws.free_ws; + } else { + idle_ws = &btrfs_comp_ws[idx].idle_ws; + ws_lock = &btrfs_comp_ws[idx].ws_lock; + total_ws = &btrfs_comp_ws[idx].total_ws; + ws_wait = &btrfs_comp_ws[idx].ws_wait; + free_ws = &btrfs_comp_ws[idx].free_ws; + } - struct list_head *idle_ws = &btrfs_comp_ws[idx].idle_ws; - spinlock_t *ws_lock = &btrfs_comp_ws[idx].ws_lock; - atomic_t *total_ws = &btrfs_comp_ws[idx].total_ws; - wait_queue_head_t *ws_wait = &btrfs_comp_ws[idx].ws_wait; - int *free_ws = &btrfs_comp_ws[idx].free_ws; again: spin_lock(ws_lock); if (!list_empty(idle_ws)) { @@ -798,7 +857,10 @@ again: * context of btrfs_compress_bio/btrfs_compress_pages */ nofs_flag = memalloc_nofs_save(); - workspace = btrfs_compress_op[idx]->alloc_workspace(); + if (heuristic) + workspace = alloc_heuristic_ws(); + else + workspace = btrfs_compress_op[idx]->alloc_workspace(); memalloc_nofs_restore(nofs_flag); if (IS_ERR(workspace)) { @@ -829,18 +891,38 @@ again: return workspace; } +static struct list_head *find_workspace(int type) +{ + return __find_workspace(type, false); +} + /* * put a workspace struct back on the list or free it if we have enough * idle ones sitting around */ -static void free_workspace(int type, struct list_head *workspace) +static void __free_workspace(int type, struct list_head *workspace, + bool heuristic) { int idx = type - 1; - struct list_head *idle_ws = &btrfs_comp_ws[idx].idle_ws; - spinlock_t *ws_lock = &btrfs_comp_ws[idx].ws_lock; - atomic_t *total_ws = &btrfs_comp_ws[idx].total_ws; - wait_queue_head_t *ws_wait = &btrfs_comp_ws[idx].ws_wait; - int *free_ws = &btrfs_comp_ws[idx].free_ws; + struct list_head *idle_ws; + spinlock_t *ws_lock; + atomic_t *total_ws; + wait_queue_head_t *ws_wait; + int *free_ws; + + if (heuristic) { + idle_ws = &btrfs_heuristic_ws.idle_ws; + ws_lock = &btrfs_heuristic_ws.ws_lock; + total_ws = &btrfs_heuristic_ws.total_ws; + ws_wait = &btrfs_heuristic_ws.ws_wait; + free_ws = &btrfs_heuristic_ws.free_ws; + } else { + idle_ws = &btrfs_comp_ws[idx].idle_ws; + ws_lock = &btrfs_comp_ws[idx].ws_lock; + total_ws = &btrfs_comp_ws[idx].total_ws; + ws_wait = &btrfs_comp_ws[idx].ws_wait; + free_ws = &btrfs_comp_ws[idx].free_ws; + } spin_lock(ws_lock); if (*free_ws <= num_online_cpus()) { @@ -851,7 +933,10 @@ static void free_workspace(int type, struct list_head *workspace) } spin_unlock(ws_lock); - btrfs_compress_op[idx]->free_workspace(workspace); + if (heuristic) + free_heuristic_ws(workspace); + else + btrfs_compress_op[idx]->free_workspace(workspace); atomic_dec(total_ws); wake: /* @@ -862,6 +947,11 @@ wake: wake_up(ws_wait); } +static void free_workspace(int type, struct list_head *ws) +{ + return __free_workspace(type, ws, false); +} + /* * cleanup function for module exit */ @@ -870,6 +960,13 @@ static void free_workspaces(void) struct list_head *workspace; int i; + while (!list_empty(&btrfs_heuristic_ws.idle_ws)) { + workspace = btrfs_heuristic_ws.idle_ws.next; + list_del(workspace); + free_heuristic_ws(workspace); + atomic_dec(&btrfs_heuristic_ws.total_ws); + } + for (i = 0; i < BTRFS_COMPRESS_TYPES; i++) { while (!list_empty(&btrfs_comp_ws[i].idle_ws)) { workspace = btrfs_comp_ws[i].idle_ws.next; @@ -1090,11 +1187,15 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, */ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) { + struct list_head *ws_list = __find_workspace(0, true); + struct heuristic_ws *ws; u64 index = start >> PAGE_SHIFT; u64 end_index = end >> PAGE_SHIFT; struct page *page; int ret = 1; + ws = list_entry(ws_list, struct heuristic_ws, list); + while (index <= end_index) { page = find_get_page(inode->i_mapping, index); kmap(page); @@ -1103,6 +1204,8 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) index++; } + __free_workspace(0, ws_list, true); + return ret; } -- cgit v1.2.3 From 17b5a6c17e265ca84fac9c3256ff86c691f04aab Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:37 +0300 Subject: Btrfs: heuristic: add bucket and sample counters and other defines Add basic defines and structures for data sampling. Added macros: - For future sampling algo - For bucket size Heuristic workspace: - Add bucket for storing byte type counters - Add sample array for storing partial copy of input data range - Add counter for store current sample size to workspace Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ minor coding style fixes, comments updated ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 52 insertions(+), 1 deletion(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index b155542c5e6b..4f5d958c71ad 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -707,8 +707,47 @@ out: return ret; } +/* + * Heuristic uses systematic sampling to collect data from the input data + * range, the logic can be tuned by the following constants: + * + * @SAMPLING_READ_SIZE - how many bytes will be copied from for each sample + * @SAMPLING_INTERVAL - range from which the sampled data can be collected + */ +#define SAMPLING_READ_SIZE (16) +#define SAMPLING_INTERVAL (256) + +/* + * For statistical analysis of the input data we consider bytes that form a + * Galois Field of 256 objects. Each object has an attribute count, ie. how + * many times the object appeared in the sample. + */ +#define BUCKET_SIZE (256) + +/* + * The size of the sample is based on a statistical sampling rule of thumb. + * The common way is to perform sampling tests as long as the number of + * elements in each cell is at least 5. + * + * Instead of 5, we choose 32 to obtain more accurate results. + * If the data contain the maximum number of symbols, which is 256, we obtain a + * sample size bound by 8192. + * + * For a sample of at most 8KB of data per data range: 16 consecutive bytes + * from up to 512 locations. + */ +#define MAX_SAMPLE_SIZE (BTRFS_MAX_UNCOMPRESSED * \ + SAMPLING_READ_SIZE / SAMPLING_INTERVAL) + +struct bucket_item { + u32 count; +}; struct heuristic_ws { + /* Partial copy of input data */ + u8 *sample; + /* Buckets store counters for each byte value */ + struct bucket_item *bucket; struct list_head list; }; @@ -718,6 +757,8 @@ static void free_heuristic_ws(struct list_head *ws) workspace = list_entry(ws, struct heuristic_ws, list); + kvfree(workspace->sample); + kfree(workspace->bucket); kfree(workspace); } @@ -729,9 +770,19 @@ static struct list_head *alloc_heuristic_ws(void) if (!ws) return ERR_PTR(-ENOMEM); - INIT_LIST_HEAD(&ws->list); + ws->sample = kvmalloc(MAX_SAMPLE_SIZE, GFP_KERNEL); + if (!ws->sample) + goto fail; + + ws->bucket = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket), GFP_KERNEL); + if (!ws->bucket) + goto fail; + INIT_LIST_HEAD(&ws->list); return &ws->list; +fail: + free_heuristic_ws(&ws->list); + return ERR_PTR(-ENOMEM); } struct workspaces_list { -- cgit v1.2.3 From a440d48c7f93af5bae86af676cc6cd4e9fd6015f Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:38 +0300 Subject: Btrfs: heuristic: implement sampling logic Copy sample data from the input data range to sample buffer then calculate byte value count for that sample into bucket. Signed-off-by: Timofey Titovets [ minor comment updates ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 71 +++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 62 insertions(+), 9 deletions(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 4f5d958c71ad..0e1561cc9578 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -746,6 +746,7 @@ struct bucket_item { struct heuristic_ws { /* Partial copy of input data */ u8 *sample; + u32 sample_size; /* Buckets store counters for each byte value */ struct bucket_item *bucket; struct list_head list; @@ -1221,6 +1222,58 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } +static void heuristic_collect_sample(struct inode *inode, u64 start, u64 end, + struct heuristic_ws *ws) +{ + struct page *page; + u64 index, index_end; + u32 i, curr_sample_pos; + u8 *in_data; + + /* + * Compression handles the input data by chunks of 128KiB + * (defined by BTRFS_MAX_UNCOMPRESSED) + * + * We do the same for the heuristic and loop over the whole range. + * + * MAX_SAMPLE_SIZE - calculated under assumption that heuristic will + * process no more than BTRFS_MAX_UNCOMPRESSED at a time. + */ + if (end - start > BTRFS_MAX_UNCOMPRESSED) + end = start + BTRFS_MAX_UNCOMPRESSED; + + index = start >> PAGE_SHIFT; + index_end = end >> PAGE_SHIFT; + + /* Don't miss unaligned end */ + if (!IS_ALIGNED(end, PAGE_SIZE)) + index_end++; + + curr_sample_pos = 0; + while (index < index_end) { + page = find_get_page(inode->i_mapping, index); + in_data = kmap(page); + /* Handle case where the start is not aligned to PAGE_SIZE */ + i = start % PAGE_SIZE; + while (i < PAGE_SIZE - SAMPLING_READ_SIZE) { + /* Don't sample any garbage from the last page */ + if (start > end - SAMPLING_READ_SIZE) + break; + memcpy(&ws->sample[curr_sample_pos], &in_data[i], + SAMPLING_READ_SIZE); + i += SAMPLING_INTERVAL; + start += SAMPLING_INTERVAL; + curr_sample_pos += SAMPLING_READ_SIZE; + } + kunmap(page); + put_page(page); + + index++; + } + + ws->sample_size = curr_sample_pos; +} + /* * Compression heuristic. * @@ -1240,19 +1293,19 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) { struct list_head *ws_list = __find_workspace(0, true); struct heuristic_ws *ws; - u64 index = start >> PAGE_SHIFT; - u64 end_index = end >> PAGE_SHIFT; - struct page *page; + u32 i; + u8 byte; int ret = 1; ws = list_entry(ws_list, struct heuristic_ws, list); - while (index <= end_index) { - page = find_get_page(inode->i_mapping, index); - kmap(page); - kunmap(page); - put_page(page); - index++; + heuristic_collect_sample(inode, start, end, ws); + + memset(ws->bucket, 0, sizeof(*ws->bucket)*BUCKET_SIZE); + + for (i = 0; i < ws->sample_size; i++) { + byte = ws->sample[i]; + ws->bucket[byte].count++; } __free_workspace(0, ws_list, true); -- cgit v1.2.3 From 1fe4f6fa5ae7dd1e63145e1ced7b9b38854da9f4 Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:39 +0300 Subject: Btrfs: heuristic: add detection of repeated data patterns Walk over data sample and use memcmp to detect repeated patterns, like zeros, but a bit more general. Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ minor coding style fixes ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 0e1561cc9578..0d445c815ca2 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -1222,6 +1222,14 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } +static bool sample_repeated_patterns(struct heuristic_ws *ws) +{ + const u32 half_of_sample = ws->sample_size / 2; + const u8 *data = ws->sample; + + return memcmp(&data[0], &data[half_of_sample], half_of_sample) == 0; +} + static void heuristic_collect_sample(struct inode *inode, u64 start, u64 end, struct heuristic_ws *ws) { @@ -1301,6 +1309,11 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) heuristic_collect_sample(inode, start, end, ws); + if (sample_repeated_patterns(ws)) { + ret = 1; + goto out; + } + memset(ws->bucket, 0, sizeof(*ws->bucket)*BUCKET_SIZE); for (i = 0; i < ws->sample_size; i++) { @@ -1308,8 +1321,8 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) ws->bucket[byte].count++; } +out: __free_workspace(0, ws_list, true); - return ret; } -- cgit v1.2.3 From a288e92cacdc4729ad8f83d018fb0f3f5ded6c37 Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:40 +0300 Subject: Btrfs: heuristic: add byte set calculation Calculate byte set size for data sample: - calculate how many unique bytes have been in the sample - for all bytes count > 0, check if we're still in the low count range (~25%), such data are easily compressible, otherwise furhter analysis is needed Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ update comments ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index 0d445c815ca2..e949f078a81b 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -1222,6 +1222,45 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } +/* + * Count byte values in buckets. + * This heuristic can detect textual data (configs, xml, json, html, etc). + * Because in most text-like data byte set is restricted to limited number of + * possible characters, and that restriction in most cases makes data easy to + * compress. + * + * @BYTE_SET_THRESHOLD - consider all data within this byte set size: + * less - compressible + * more - need additional analysis + */ +#define BYTE_SET_THRESHOLD (64) + +static u32 byte_set_size(const struct heuristic_ws *ws) +{ + u32 i; + u32 byte_set_size = 0; + + for (i = 0; i < BYTE_SET_THRESHOLD; i++) { + if (ws->bucket[i].count > 0) + byte_set_size++; + } + + /* + * Continue collecting count of byte values in buckets. If the byte + * set size is bigger then the threshold, it's pointless to continue, + * the detection technique would fail for this type of data. + */ + for (; i < BUCKET_SIZE; i++) { + if (ws->bucket[i].count > 0) { + byte_set_size++; + if (byte_set_size > BYTE_SET_THRESHOLD) + return byte_set_size; + } + } + + return byte_set_size; +} + static bool sample_repeated_patterns(struct heuristic_ws *ws) { const u32 half_of_sample = ws->sample_size / 2; @@ -1321,6 +1360,12 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) ws->bucket[byte].count++; } + i = byte_set_size(ws); + if (i < BYTE_SET_THRESHOLD) { + ret = 2; + goto out; + } + out: __free_workspace(0, ws_list, true); return ret; -- cgit v1.2.3 From 858177d38d4681dad6efc015b99e4c786a34aca5 Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Thu, 28 Sep 2017 17:33:41 +0300 Subject: Btrfs: heuristic: add byte core set calculation Calculate byte core set for data sample: - sort buckets' numbers in decreasing order - count how many values cover 90% of the sample If the core set size is low (<=25%), data are easily compressible. If the core set size is high (>=80%), data are not compressible. Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ update comments ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index e949f078a81b..c551d8a979f4 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -33,6 +33,7 @@ #include #include #include +#include #include "ctree.h" #include "disk-io.h" #include "transaction.h" @@ -1222,6 +1223,59 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } +/* Compare buckets by size, ascending */ +static int bucket_comp_rev(const void *lv, const void *rv) +{ + const struct bucket_item *l = (const struct bucket_item *)lv; + const struct bucket_item *r = (const struct bucket_item *)rv; + + return r->count - l->count; +} + +/* + * Size of the core byte set - how many bytes cover 90% of the sample + * + * There are several types of structured binary data that use nearly all byte + * values. The distribution can be uniform and counts in all buckets will be + * nearly the same (eg. encrypted data). Unlikely to be compressible. + * + * Other possibility is normal (Gaussian) distribution, where the data could + * be potentially compressible, but we have to take a few more steps to decide + * how much. + * + * @BYTE_CORE_SET_LOW - main part of byte values repeated frequently, + * compression algo can easy fix that + * @BYTE_CORE_SET_HIGH - data have uniform distribution and with high + * probability is not compressible + */ +#define BYTE_CORE_SET_LOW (64) +#define BYTE_CORE_SET_HIGH (200) + +static int byte_core_set_size(struct heuristic_ws *ws) +{ + u32 i; + u32 coreset_sum = 0; + const u32 core_set_threshold = ws->sample_size * 90 / 100; + struct bucket_item *bucket = ws->bucket; + + /* Sort in reverse order */ + sort(bucket, BUCKET_SIZE, sizeof(*bucket), &bucket_comp_rev, NULL); + + for (i = 0; i < BYTE_CORE_SET_LOW; i++) + coreset_sum += bucket[i].count; + + if (coreset_sum > core_set_threshold) + return i; + + for (; i < BYTE_CORE_SET_HIGH && bucket[i].count > 0; i++) { + coreset_sum += bucket[i].count; + if (coreset_sum > core_set_threshold) + break; + } + + return i; +} + /* * Count byte values in buckets. * This heuristic can detect textual data (configs, xml, json, html, etc). @@ -1366,6 +1420,17 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) goto out; } + i = byte_core_set_size(ws); + if (i <= BYTE_CORE_SET_LOW) { + ret = 3; + goto out; + } + + if (i >= BYTE_CORE_SET_HIGH) { + ret = 0; + goto out; + } + out: __free_workspace(0, ws_list, true); return ret; -- cgit v1.2.3 From 19562430c6213925faba3baa9e8cb224ddd47ee6 Mon Sep 17 00:00:00 2001 From: Timofey Titovets Date: Sun, 8 Oct 2017 16:11:59 +0300 Subject: Btrfs: heuristic: add Shannon entropy calculation Byte distribution check in heuristic will filter edge data cases and some time fail to classify input data. Let's fix that by adding Shannon entropy calculation, that will cover classification of most other data types. As Shannon entropy needs log2 with some precision to work, let's use ilog2(N) and for increased precision, by do ilog2(pow(N, 4)). Shannon entropy has been slightly changed to avoid signed numbers and division. The calculation is direct by the formula, successor of precalculated table or chains of if-else. The accuracy errors of ilog2 are compensated by @ENTROPY_LVL_ACEPTABLE 70 -> 65 @ENTROPY_LVL_HIGH 85 -> 80 Signed-off-by: Timofey Titovets Reviewed-by: David Sterba [ update comments ] Signed-off-by: David Sterba --- fs/btrfs/compression.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 84 insertions(+), 1 deletion(-) (limited to 'fs/btrfs/compression.c') diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index c551d8a979f4..b35ce16b3df3 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -34,6 +34,7 @@ #include #include #include +#include #include "ctree.h" #include "disk-io.h" #include "transaction.h" @@ -1223,6 +1224,59 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, return 1; } +/* + * Shannon Entropy calculation + * + * Pure byte distribution analysis fails to determine compressiability of data. + * Try calculating entropy to estimate the average minimum number of bits + * needed to encode the sampled data. + * + * For convenience, return the percentage of needed bits, instead of amount of + * bits directly. + * + * @ENTROPY_LVL_ACEPTABLE - below that threshold, sample has low byte entropy + * and can be compressible with high probability + * + * @ENTROPY_LVL_HIGH - data are not compressible with high probability + * + * Use of ilog2() decreases precision, we lower the LVL to 5 to compensate. + */ +#define ENTROPY_LVL_ACEPTABLE (65) +#define ENTROPY_LVL_HIGH (80) + +/* + * For increasead precision in shannon_entropy calculation, + * let's do pow(n, M) to save more digits after comma: + * + * - maximum int bit length is 64 + * - ilog2(MAX_SAMPLE_SIZE) -> 13 + * - 13 * 4 = 52 < 64 -> M = 4 + * + * So use pow(n, 4). + */ +static inline u32 ilog2_w(u64 n) +{ + return ilog2(n * n * n * n); +} + +static u32 shannon_entropy(struct heuristic_ws *ws) +{ + const u32 entropy_max = 8 * ilog2_w(2); + u32 entropy_sum = 0; + u32 p, p_base, sz_base; + u32 i; + + sz_base = ilog2_w(ws->sample_size); + for (i = 0; i < BUCKET_SIZE && ws->bucket[i].count > 0; i++) { + p = ws->bucket[i].count; + p_base = ilog2_w(p); + entropy_sum += p * (sz_base - p_base); + } + + entropy_sum /= ws->sample_size; + return entropy_sum * 100 / entropy_max; +} + /* Compare buckets by size, ascending */ static int bucket_comp_rev(const void *lv, const void *rv) { @@ -1396,7 +1450,7 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) struct heuristic_ws *ws; u32 i; u8 byte; - int ret = 1; + int ret = 0; ws = list_entry(ws_list, struct heuristic_ws, list); @@ -1431,6 +1485,35 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) goto out; } + i = shannon_entropy(ws); + if (i <= ENTROPY_LVL_ACEPTABLE) { + ret = 4; + goto out; + } + + /* + * For the levels below ENTROPY_LVL_HIGH, additional analysis would be + * needed to give green light to compression. + * + * For now just assume that compression at that level is not worth the + * resources because: + * + * 1. it is possible to defrag the data later + * + * 2. the data would turn out to be hardly compressible, eg. 150 byte + * values, every bucket has counter at level ~54. The heuristic would + * be confused. This can happen when data have some internal repeated + * patterns like "abbacbbc...". This can be detected by analyzing + * pairs of bytes, which is too costly. + */ + if (i < ENTROPY_LVL_HIGH) { + ret = 5; + goto out; + } else { + ret = 0; + goto out; + } + out: __free_workspace(0, ws_list, true); return ret; -- cgit v1.2.3