Re: [PATCH v2] btrfs: add zstd compression level support

[Nick Terrell]

> On Nov 13, 2018, at 5:29 AM, Timofey Titovets  wrote:
> 
> вт, 13 нояб. 2018 г. в 04:52, Nick Terrell :
>> 
>> 
>> 
>>> On Nov 12, 2018, at 4:33 PM, David Sterba  wrote:
>>> 
>>> On Wed, Oct 31, 2018 at 11:11:08AM -0700, Nick Terrell wrote:
>>>> From: Jennifer Liu 
>>>> 
>>>> Adds zstd compression level support to btrfs. Zstd requires
>>>> different amounts of memory for each level, so the design had
>>>> to be modified to allow set_level() to allocate memory. We
>>>> preallocate one workspace of the maximum size to guarantee
>>>> forward progress. This feature is expected to be useful for
>>>> read-mostly filesystems, or when creating images.
>>>> 
>>>> Benchmarks run in qemu on Intel x86 with a single core.
>>>> The benchmark measures the time to copy the Silesia corpus [0] to
>>>> a btrfs filesystem 10 times, then read it back.
>>>> 
>>>> The two important things to note are:
>>>> - The decompression speed and memory remains constant.
>>>> The memory required to decompress is the same as level 1.
>>>> - The compression speed and ratio will vary based on the source.
>>>> 
>>>> LevelRatio   Compression Decompression   Compression Memory
>>>> 12.59153 MB/s112 MB/s0.8 MB
>>>> 22.67136 MB/s113 MB/s1.0 MB
>>>> 32.72106 MB/s115 MB/s1.3 MB
>>>> 42.7886  MB/s109 MB/s0.9 MB
>>>> 52.8369  MB/s109 MB/s1.4 MB
>>>> 62.8953  MB/s110 MB/s1.5 MB
>>>> 72.9140  MB/s112 MB/s1.4 MB
>>>> 82.9234  MB/s110 MB/s1.8 MB
>>>> 92.9327  MB/s109 MB/s1.8 MB
>>>> 10   2.9422  MB/s109 MB/s1.8 MB
>>>> 11   2.9517  MB/s114 MB/s1.8 MB
>>>> 12   2.9513  MB/s113 MB/s1.8 MB
>>>> 13   2.9510  MB/s111 MB/s2.3 MB
>>>> 14   2.997   MB/s110 MB/s2.6 MB
>>>> 15   3.036   MB/s110 MB/s2.6 MB
>>>> 
>>>> [0] 
>>>> https://urldefense.proofpoint.com/v2/url?u=http-3A__sun.aei.polsl.pl_-7Esdeor_index.php-3Fpage-3Dsilesia=DwIBAg=5VD0RTtNlTh3ycd41b3MUw=HQM5IQdWOB8WaMoii2dYTw=5LQRTUqZnx_a8dGSa5bGsd0Fm4ejQQOcH50wi7nRewY=gFUm-SA3aeQI7PBe3zmxUuxk4AEEZegB0cRsbjWUToo=
>>>> 
>>>> Signed-off-by: Jennifer Liu 
>>>> Signed-off-by: Nick Terrell 
>>>> Reviewed-by: Omar Sandoval 
>>>> ---
>>>> v1 -> v2:
>>>> - Don't reflow the unchanged line.
>>>> 
>>>> fs/btrfs/compression.c | 169 +
>>>> fs/btrfs/compression.h |  18 +++--
>>>> fs/btrfs/lzo.c |   5 +-
>>>> fs/btrfs/super.c   |   7 +-
>>>> fs/btrfs/zlib.c|  33 
>>>> fs/btrfs/zstd.c|  74 +-
>>>> 6 files changed, 202 insertions(+), 104 deletions(-)
>>>> 
>>>> diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
>>>> index 2955a4ea2fa8..b46652cb653e 100644
>>>> --- a/fs/btrfs/compression.c
>>>> +++ b/fs/btrfs/compression.c
>>>> @@ -822,9 +822,12 @@ void __init btrfs_init_compress(void)
>>>> 
>>>> /*
>>>>  * Preallocate one workspace for each compression type so
>>>> - * we can guarantee forward progress in the worst case
>>>> + * we can guarantee forward progress in the worst case.
>>>> + * Provide the maximum compression level to guarantee large
>>>> + * enough workspace.
>>>>  */
>>>> -workspace = btrfs_compress_op[i]->alloc_workspace();
>>>> +workspace = btrfs_compress_op[i]->alloc_workspace(
>>>> +btrfs_compress_op[i]->max_level);
>> 
>> We provide the max level here, so we have at least one workspace per
>> compression type that is large enough.
>> 
>>>> if (IS_ERR(workspace)) {
>>>> pr_warn("BTRFS: cannot preallocate compression 
>>>> w

Re: [PATCH v2] btrfs: add zstd compression level support

[Nick Terrell]

> On Nov 12, 2018, at 4:33 PM, David Sterba  wrote:
> 
> On Wed, Oct 31, 2018 at 11:11:08AM -0700, Nick Terrell wrote:
>> From: Jennifer Liu 
>> 
>> Adds zstd compression level support to btrfs. Zstd requires
>> different amounts of memory for each level, so the design had
>> to be modified to allow set_level() to allocate memory. We
>> preallocate one workspace of the maximum size to guarantee
>> forward progress. This feature is expected to be useful for
>> read-mostly filesystems, or when creating images.
>> 
>> Benchmarks run in qemu on Intel x86 with a single core.
>> The benchmark measures the time to copy the Silesia corpus [0] to
>> a btrfs filesystem 10 times, then read it back.
>> 
>> The two important things to note are:
>> - The decompression speed and memory remains constant.
>>  The memory required to decompress is the same as level 1.
>> - The compression speed and ratio will vary based on the source.
>> 
>> LevelRatio   Compression Decompression   Compression Memory
>> 12.59153 MB/s112 MB/s0.8 MB
>> 22.67136 MB/s113 MB/s1.0 MB
>> 32.72106 MB/s115 MB/s1.3 MB
>> 42.7886  MB/s109 MB/s0.9 MB
>> 52.8369  MB/s109 MB/s1.4 MB
>> 62.8953  MB/s110 MB/s1.5 MB
>> 72.9140  MB/s112 MB/s1.4 MB
>> 82.9234  MB/s110 MB/s1.8 MB
>> 92.9327  MB/s109 MB/s1.8 MB
>> 10   2.9422  MB/s109 MB/s1.8 MB
>> 11   2.9517  MB/s114 MB/s1.8 MB
>> 12   2.9513  MB/s113 MB/s1.8 MB
>> 13   2.9510  MB/s111 MB/s2.3 MB
>> 14   2.997   MB/s110 MB/s2.6 MB
>> 15   3.036   MB/s110 MB/s2.6 MB
>> 
>> [0] 
>> https://urldefense.proofpoint.com/v2/url?u=http-3A__sun.aei.polsl.pl_-7Esdeor_index.php-3Fpage-3Dsilesia=DwIBAg=5VD0RTtNlTh3ycd41b3MUw=HQM5IQdWOB8WaMoii2dYTw=5LQRTUqZnx_a8dGSa5bGsd0Fm4ejQQOcH50wi7nRewY=gFUm-SA3aeQI7PBe3zmxUuxk4AEEZegB0cRsbjWUToo=
>> 
>> Signed-off-by: Jennifer Liu 
>> Signed-off-by: Nick Terrell 
>> Reviewed-by: Omar Sandoval 
>> ---
>> v1 -> v2:
>> - Don't reflow the unchanged line.
>> 
>> fs/btrfs/compression.c | 169 +
>> fs/btrfs/compression.h |  18 +++--
>> fs/btrfs/lzo.c |   5 +-
>> fs/btrfs/super.c   |   7 +-
>> fs/btrfs/zlib.c|  33 
>> fs/btrfs/zstd.c|  74 +-
>> 6 files changed, 202 insertions(+), 104 deletions(-)
>> 
>> diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
>> index 2955a4ea2fa8..b46652cb653e 100644
>> --- a/fs/btrfs/compression.c
>> +++ b/fs/btrfs/compression.c
>> @@ -822,9 +822,12 @@ void __init btrfs_init_compress(void)
>> 
>>  /*
>>   * Preallocate one workspace for each compression type so
>> - * we can guarantee forward progress in the worst case
>> + * we can guarantee forward progress in the worst case.
>> + * Provide the maximum compression level to guarantee large
>> + * enough workspace.
>>   */
>> -workspace = btrfs_compress_op[i]->alloc_workspace();
>> +workspace = btrfs_compress_op[i]->alloc_workspace(
>> +btrfs_compress_op[i]->max_level);

We provide the max level here, so we have at least one workspace per
compression type that is large enough.

>>  if (IS_ERR(workspace)) {
>>  pr_warn("BTRFS: cannot preallocate compression 
>> workspace, will try later\n");
>>  } else {
>> @@ -835,23 +838,78 @@ void __init btrfs_init_compress(void)
>>  }
>> }
>> 
>> +/*
>> + * 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,
>> + bool heuristic)
>> +{
>> +int idx = type - 1;
>> +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  = _heuristic_ws.idle_ws;
>> + 

Re: [PATCH v2] btrfs: add zstd compression level support

[Nick Terrell]

> On Nov 1, 2018, at 5:57 AM, Timofey Titovets  wrote:
> 
> ср, 31 окт. 2018 г. в 21:12, Nick Terrell :
>> 
>> From: Jennifer Liu 
>> 
>> Adds zstd compression level support to btrfs. Zstd requires
>> different amounts of memory for each level, so the design had
>> to be modified to allow set_level() to allocate memory. We
>> preallocate one workspace of the maximum size to guarantee
>> forward progress. This feature is expected to be useful for
>> read-mostly filesystems, or when creating images.
>> 
>> Benchmarks run in qemu on Intel x86 with a single core.
>> The benchmark measures the time to copy the Silesia corpus [0] to
>> a btrfs filesystem 10 times, then read it back.
>> 
>> The two important things to note are:
>> - The decompression speed and memory remains constant.
>>  The memory required to decompress is the same as level 1.
>> - The compression speed and ratio will vary based on the source.
>> 
>> Level   Ratio   Compression Decompression   Compression Memory
>> 1   2.59153 MB/s112 MB/s0.8 MB
>> 2   2.67136 MB/s113 MB/s1.0 MB
>> 3   2.72106 MB/s115 MB/s1.3 MB
>> 4   2.7886  MB/s109 MB/s0.9 MB
>> 5   2.8369  MB/s109 MB/s1.4 MB
>> 6   2.8953  MB/s110 MB/s1.5 MB
>> 7   2.9140  MB/s112 MB/s1.4 MB
>> 8   2.9234  MB/s110 MB/s1.8 MB
>> 9   2.9327  MB/s109 MB/s1.8 MB
>> 10  2.9422  MB/s109 MB/s1.8 MB
>> 11  2.9517  MB/s114 MB/s1.8 MB
>> 12  2.9513  MB/s113 MB/s1.8 MB
>> 13  2.9510  MB/s111 MB/s2.3 MB
>> 14  2.997   MB/s    110 MB/s2.6 MB
>> 15  3.036   MB/s110 MB/s2.6 MB
>> 
>> [0] http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia
>> 
>> Signed-off-by: Jennifer Liu 
>> Signed-off-by: Nick Terrell 
>> Reviewed-by: Omar Sandoval 



> 
> You didn't mention, so:
> Did you test compression ratio/performance with compress-force or just 
> compress?

I tested with compress-force, since I just reused my script from before [0].

I reran some levels with compress and got these numbers:

Level   Ratio   Compression Decompression
1   2.21158 MB/s113 MB/s
3   2.28117 MB/s113 MB/s
5   2.3281  MB/s112 MB/s
7   2.3747  MB/s116 MB/s
15  2.417   MB/s115 MB/s

Using compress probably makes sense with lower levels, to get higher write 
speeds,
but if you're using higher compression levels, you'll likely want to use 
compress-force,
since you likely don't care too much about write speeds. Obviously this will 
depend on
the data you're compressing.

[0] https://gist.github.com/terrelln/51ed3c9da6f94d613c01fcdae60567e8

-Nick

> 
> Thanks.
> 
> -- 
> Have a nice day,
> Timofey.

[PATCH v2] btrfs: add zstd compression level support

[Nick Terrell]

From: Jennifer Liu 

Adds zstd compression level support to btrfs. Zstd requires
different amounts of memory for each level, so the design had
to be modified to allow set_level() to allocate memory. We
preallocate one workspace of the maximum size to guarantee
forward progress. This feature is expected to be useful for
read-mostly filesystems, or when creating images.

Benchmarks run in qemu on Intel x86 with a single core.
The benchmark measures the time to copy the Silesia corpus [0] to
a btrfs filesystem 10 times, then read it back.

The two important things to note are:
- The decompression speed and memory remains constant.
  The memory required to decompress is the same as level 1.
- The compression speed and ratio will vary based on the source.

Level   Ratio   Compression Decompression   Compression Memory
1   2.59153 MB/s112 MB/s0.8 MB
2   2.67136 MB/s113 MB/s1.0 MB
3   2.72106 MB/s115 MB/s1.3 MB
4   2.7886  MB/s109 MB/s0.9 MB
5   2.8369  MB/s109 MB/s1.4 MB
6   2.8953  MB/s110 MB/s1.5 MB
7   2.9140  MB/s112 MB/s1.4 MB
8   2.9234  MB/s110 MB/s1.8 MB
9   2.9327  MB/s109 MB/s1.8 MB
10  2.9422  MB/s109 MB/s1.8 MB
11  2.9517  MB/s114 MB/s1.8 MB
12  2.9513  MB/s113 MB/s1.8 MB
13  2.9510  MB/s111 MB/s2.3 MB
14  2.997   MB/s110 MB/s2.6 MB
15  3.036   MB/s110 MB/s2.6 MB

[0] http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia

Signed-off-by: Jennifer Liu 
Signed-off-by: Nick Terrell 
Reviewed-by: Omar Sandoval 
---
v1 -> v2:
- Don't reflow the unchanged line.

 fs/btrfs/compression.c | 169 +
 fs/btrfs/compression.h |  18 +++--
 fs/btrfs/lzo.c |   5 +-
 fs/btrfs/super.c   |   7 +-
 fs/btrfs/zlib.c|  33 
 fs/btrfs/zstd.c|  74 +-
 6 files changed, 202 insertions(+), 104 deletions(-)

diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
index 2955a4ea2fa8..b46652cb653e 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -822,9 +822,12 @@ void __init btrfs_init_compress(void)

/*
 * Preallocate one workspace for each compression type so
-* we can guarantee forward progress in the worst case
+* we can guarantee forward progress in the worst case.
+* Provide the maximum compression level to guarantee large
+* enough workspace.
 */
-   workspace = btrfs_compress_op[i]->alloc_workspace();
+   workspace = btrfs_compress_op[i]->alloc_workspace(
+   btrfs_compress_op[i]->max_level);
if (IS_ERR(workspace)) {
pr_warn("BTRFS: cannot preallocate compression 
workspace, will try later\n");
} else {
@@ -835,23 +838,78 @@ void __init btrfs_init_compress(void)
}
 }

+/*
+ * 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,
+bool heuristic)
+{
+   int idx = type - 1;
+   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  = _heuristic_ws.idle_ws;
+   ws_lock  = _heuristic_ws.ws_lock;
+   total_ws = _heuristic_ws.total_ws;
+   ws_wait  = _heuristic_ws.ws_wait;
+   free_ws  = _heuristic_ws.free_ws;
+   } else {
+   idle_ws  = _comp_ws[idx].idle_ws;
+   ws_lock  = _comp_ws[idx].ws_lock;
+   total_ws = _comp_ws[idx].total_ws;
+   ws_wait  = _comp_ws[idx].ws_wait;
+   free_ws  = _comp_ws[idx].free_ws;
+   }
+
+   spin_lock(ws_lock);
+   if (*free_ws <= num_online_cpus()) {
+   list_add(workspace, idle_ws);
+   (*free_ws)++;
+   spin_unlock(ws_lock);
+   goto wake;
+   }
+   spin_unlock(ws_lock);
+
+   if (heuristic)
+   free_heuristic_ws(workspace);
+   else
+   btrfs_compress_op[idx]->free_workspace(workspace);
+   atomic_dec(total_ws);
+wake:
+   cond_wake_up(ws_wait);
+}
+
+static void free_workspace(int type, struct list_head *ws)
+{
+   return __free_workspace(type, ws, false);
+}
+
 /*
  * This finds an available workspace or allocates a new one.
  * If it's not possible to allocate a new one, waits until there's one.
  * Preallocation makes a forward progress guarantees and we do not ret

[PATCH] btrfs: add zstd compression level support

[Nick Terrell]

From: Jennifer Liu 

Adds zstd compression level support to btrfs. Zstd requires
different amounts of memory for each level, so the design had
to be modified to allow set_level() to allocate memory. We
preallocate one workspace of the maximum size to guarantee
forward progress. This feature is expected to be useful for
read-mostly filesystems, or when creating images.

Benchmarks run in qemu on Intel x86 with a single core.
The benchmark measures the time to copy the Silesia corpus [0] to
a btrfs filesystem 10 times, then read it back.

The two important things to note are:
- The decompression speed and memory remains constant.
  The memory required to decompress is the same as level 1.
- The compression speed and ratio will vary based on the source.

Level   Ratio   Compression Decompression   Compression Memory
1   2.59153 MB/s112 MB/s0.8 MB
2   2.67136 MB/s113 MB/s1.0 MB
3   2.72106 MB/s115 MB/s1.3 MB
4   2.7886  MB/s109 MB/s0.9 MB
5   2.8369  MB/s109 MB/s1.4 MB
6   2.8953  MB/s110 MB/s1.5 MB
7   2.9140  MB/s112 MB/s1.4 MB
8   2.9234  MB/s110 MB/s1.8 MB
9   2.9327  MB/s109 MB/s1.8 MB
10  2.9422  MB/s109 MB/s1.8 MB
11  2.9517  MB/s114 MB/s1.8 MB
12  2.9513  MB/s113 MB/s1.8 MB
13  2.9510  MB/s111 MB/s2.3 MB
14  2.997   MB/s110 MB/s2.6 MB
15  3.036   MB/s110 MB/s2.6 MB

[0] http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia

Signed-off-by: Jennifer Liu 
Signed-off-by: Nick Terrell 
---
 fs/btrfs/compression.c | 172 +
 fs/btrfs/compression.h |  18 +++--
 fs/btrfs/lzo.c |   5 +-
 fs/btrfs/super.c   |   7 +-
 fs/btrfs/zlib.c|  33 
 fs/btrfs/zstd.c|  74 ++
 6 files changed, 204 insertions(+), 105 deletions(-)

diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
index 2955a4ea2fa8..bd8e69381dc9 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -822,11 +822,15 @@ void __init btrfs_init_compress(void)
 
/*
 * Preallocate one workspace for each compression type so
-* we can guarantee forward progress in the worst case
+* we can guarantee forward progress in the worst case.
+* Provide the maximum compression level to guarantee large
+* enough workspace.
 */
-   workspace = btrfs_compress_op[i]->alloc_workspace();
+   workspace = btrfs_compress_op[i]->alloc_workspace(
+   btrfs_compress_op[i]->max_level);
if (IS_ERR(workspace)) {
-   pr_warn("BTRFS: cannot preallocate compression 
workspace, will try later\n");
+   pr_warn("BTRFS: cannot preallocate compression "
+   "workspace, will try later\n");
} else {
atomic_set(_comp_ws[i].total_ws, 1);
btrfs_comp_ws[i].free_ws = 1;
@@ -835,23 +839,78 @@ void __init btrfs_init_compress(void)
}
 }
 
+/*
+ * 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,
+bool heuristic)
+{
+   int idx = type - 1;
+   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  = _heuristic_ws.idle_ws;
+   ws_lock  = _heuristic_ws.ws_lock;
+   total_ws = _heuristic_ws.total_ws;
+   ws_wait  = _heuristic_ws.ws_wait;
+   free_ws  = _heuristic_ws.free_ws;
+   } else {
+   idle_ws  = _comp_ws[idx].idle_ws;
+   ws_lock  = _comp_ws[idx].ws_lock;
+   total_ws = _comp_ws[idx].total_ws;
+   ws_wait  = _comp_ws[idx].ws_wait;
+   free_ws  = _comp_ws[idx].free_ws;
+   }
+
+   spin_lock(ws_lock);
+   if (*free_ws <= num_online_cpus()) {
+   list_add(workspace, idle_ws);
+   (*free_ws)++;
+   spin_unlock(ws_lock);
+   goto wake;
+   }
+   spin_unlock(ws_lock);
+
+   if (heuristic)
+   free_heuristic_ws(workspace);
+   else
+   btrfs_compress_op[idx]->free_workspace(workspace);
+   atomic_dec(total_ws);
+wake:
+   cond_wake_up(ws_wait);
+}
+
+static void free_workspace(int type, struct list_head *ws)
+{
+   return __free_workspace(type, ws, false);
+}
+
 /*
  * T

Re: Read before you deploy btrfs + zstd

[Nick Terrell]

> On Dec 5, 2017, at 7:54 AM, David Sterba  wrote:
> 
> I had a different branch with patches from openSUSE, so the diffs apply with
> minimal efforts to the package. The branch btrfs-zstd has been synced up. The
> ENOMEM error was not from the file decompression but from the zstdio.c module,
> that does something different, now disabled.
> 
> I got a bit further, with a few debugging messages, this check fails:
> 
> 957   total_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
> 958   ibuf += sizeof (total_size);
> 959
> 960   if (isize < total_size) {
> 961 grub_error (GRUB_ERR_BAD_FS, "ASSERTION: isize < total_size: %ld < 
> %ld",
> 962 isize, total_size);
> 963 return -1;
> 964   }
> 
> with: "isize < total_size: 61440 < -47205080"
> 
> total_size is u32, but wrngly printed as signed long so it's negative, but
> would be wrong anyway. This looks like the compressed format is not read
> correctly.

The blocks of 4 KB uncompressed data with a u32 containing the compressed
size is part of the btrfs lzo format, so zstd doesn't follow that. The
compressed data is just zstd, with nothing else.

I think I mistook the semantics of grub_btrfs_zstd_decompress() earlier.
If I understand the function correctly, grub_btrfs_zstd_decompress() is
given a compressed block and is asked to read `osize` bytes at offset `off`
of the uncompressed bytes. `osize` may be less than the uncompressed block
size if `off > 0`. Is that correct?

Zstd compressed data is called a "frame", and the frame is made up of
multiple "blocks", each containing up to 128 KB on uncompressed data.
Since btrfs currently passes blocks of up to 128 KB to the compressor,
each frame will contain only one block. Zstd is only able to decompress
at block granularity, so we have to decompress the whole thing.

Since `osize` may be less than the uncompressed size of the zstd frame, we
will need a secondary buffer to decompress into, and then copy the
requested segment into the output buffer.

The code would look something like this:

```
#define BTRFS_ZSTD_WORKSPACE_SIZE_U64 (155984 / sizeof(grub_uint64_t))
static grub_uint64_t zstd_workspace[BTRFS_ZSTD_WORKSPACE_SIZE_U64];

#define ZSTD_BTRFS_MAX_WINDOWLOG 17
#define ZSTD_BTRFS_MAX_INPUT (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
static grub_uint8_t zstd_outbuf[ZSTD_BTRFS_MAX_INPUT];

static grub_ssize_t
grub_btrfs_zstd_decompress(char *ibuf, grub_size_t isize, grub_off_t off,
  char *obuf, grub_size_t osize)
{
 void *ubuf;
 grub_size_t usize;
 void *const wmem = zstd_workspace;
 grub_size_t const wsize = sizeof(zstd_workspace);
 ZSTD_DCtx *ctx;

 if (wsize < ZSTD_DCtxWorkspaceBound())
   {
  /* Unexpected */
  return -1;
   }
 ctx = ZSTD_initDCtx(wmem, wsize);
 if (!ctx)
   {
  /* Unexpected */
  return -1;
   }

 /* Find the end of the zstd frame given a zstd compressed frame possibly
  * followed by extra data. The returned value will always be an error or
  * <= isize.
  *
  * This is only necessary if there is junk after the end of the zstd
  * compressed data in the input buffer. Otherwise the return value
  * should always be exactly isize. If you delete this, and it always works,
  * then there isn't junk data at the end.
  */
 isize = ZSTD_findFrameCompressedSize(ibuf, isize);
 if (ZSTD_isError(isize))
   {
  /* Corruption */
  return -1;
   }

 /* We don't know the original uncompressed size here (osize might be smaller)
  * so we have to fall back to checking that osize >= ZSTD_BTRFS_MAX_INPUT.
  * If we knew the size, we could relax the check.
  *
  * This is only an optimization, not necessary for correctness.
  */
 if (off == 0 && osize >= ZSTD_BTRFS_MAX_INPUT)
   {
  ubuf = obuf;
  usize = osize;
   }
 else
   {
 ubuf = zstd_outbuf;
 usize = sizeof(zstd_outbuf);
   }

 usize = ZSTD_decompressDCtx(ctx, ubuf, usize, ibuf, isize);
 if (ZSTD_isError(usize))
   {
  /* Corruption */
  return -1;
   }
 /* We need to read osize bytes at offset off.
  * Check that we have enough data.
  */
 if (usize < off + osize)
   {
  /* Corruption */
  return -1;
   }
 /* If we decompressed directly to the output buffer, off must be zero. */
 if (ubuf == obuf)
   {
  assert(off == 0);
  return osize;
   }
 assert(ubuf == zstd_outbuf);
 grub_memcpy(obuf, ubuf + off, osize);
 return osize;
}
```--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [btrfs_mount] general protection fault: 0000 [#1] SMP

[Nick Terrell]

> On Nov 29, 2017, at 6:21 PM, Fengguang Wu  wrote:
> 
> Hello,
> 
> FYI this happens in mainline kernel 4.15.0-rc1.
> It looks like a new regression. Bisect is in progress.
> 
> It occurs in 11 out of 11 xfstests run.
> 
> [ 1456.361614]
> [ 1456.918942] BTRFS info (device vdb): disk space caching is enabled
> [ 1456.920760] BTRFS info (device vdb): has skinny extents
> [ 1457.111319] run fstests btrfs/094 at 2017-11-28 09:46:30
> [ 1457.702513] BTRFS: device fsid 5c26b547-822d-4338-be92-b2ec5f6b159d devid 
> 1 transid 5 /dev/vdb
> [ 1457.920372] general protection fault:  [#1] SMP
> [ 1457.921693] Modules linked in: dm_flakey btrfs xor zstd_decompress 
> zstd_compress xxhash raid6_pq dm_mod rpcsec_gss_krb5 auth_rpcgss nfsv4 
> dns_resolver sr_mod cdrom sg ata_generic pata_acpi ppdev snd_pcm snd_timer 
> snd soundcore pcspkr serio_raw ata_piix i2c_piix4 libata parport_pc floppy 
> parport ip_tables
> [ 1457.927395] CPU: 3 PID: 19563 Comm: mount Not tainted 4.15.0-rc1 #1
> [ 1457.928804] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 
> 1.10.2-1 04/01/2014
> [ 1457.930815] task: 880078f8ca00 task.stack: c90004828000
> [ 1457.934242] RIP: 0010:btrfs_compress_str2level+0x17/0x50 [btrfs]

The stack trace looks like the bug fixed by

Qu Wenruo:
btrfs: Fix wild memory access in compression level parser [1]

That fix looks to be included in the pull request for 4.15-rc2 [2].

[1] lkml.kernel.org/r/20171106024319.32584-1-...@suse.com
[2] lkml.kernel.org/r/cover.1511980478.git.dste...@suse.com

> [ 1457.936653] RSP: 0018:c9000482baa8 EFLAGS: 00010202
> [ 1457.938909] RAX: 0001 RBX: a057967f RCX: 
> 0004
> [ 1457.942574] RDX: 192000905763 RSI: 192000905763 RDI: 
> a057bc24
> [ 1457.946221] RBP: c9000482bb40 R08: 0063 R09: 
> 88007e8257a8
> [ 1457.948982] R10: 002c R11: 81a6a340 R12: 
> 8800750b
> [ 1457.952494] R13: 88007e8257a0 R14:  R15: 
> 1000
> [ 1457.956106] FS:  7fb80717d840() GS:88013fd8() 
> knlGS:
> [ 1457.960103] CS:  0010 DS:  ES:  CR0: 80050033
> [ 1457.962466] CR2: 010b6f88 CR3: 750ce000 CR4: 
> 06e0
> [ 1457.966100] Call Trace:
> [ 1457.966851]  btrfs_parse_options+0x96f/0xf20 [btrfs]
> [ 1457.970107]  ? open_ctree+0x1041/0x2410 [btrfs]
> [ 1457.971638]  open_ctree+0x1041/0x2410 [btrfs]
> [ 1457.973780]  btrfs_mount+0xcfa/0xe40 [btrfs]
> [ 1457.975889]  ? pcpu_alloc_area+0xc0/0x130:
>   pcpu_alloc_area at 
> mm/percpu.c:1010
> [ 1457.979028]  ? pcpu_next_unpop+0x37/0x50:
>   pcpu_next_unpop at 
> mm/percpu.c:264
> [ 1457.981051]  ? pcpu_alloc+0x2e1/0x650:
>   pcpu_alloc at mm/percpu.c:1472 
> (discriminator 1)
> [ 1457.983074]  mount_fs+0x36/0x140:
>   mount_fs at fs/super.c:1220
> [ 1457.983941]  vfs_kern_mount+0x62/0x130:
>   vfs_kern_mount at 
> fs/namespace.c:1038
> [ 1457.985951]  btrfs_mount+0x183/0xe40 [btrfs]
> [ 1457.989441]  ? pcpu_alloc_area+0xc0/0x130:
>   pcpu_alloc_area at 
> mm/percpu.c:1010
> [ 1457.991495]  ? pcpu_next_unpop+0x37/0x50:
>   pcpu_next_unpop at 
> mm/percpu.c:264
> [ 1457.993524]  ? pcpu_alloc+0x2e1/0x650:
>   pcpu_alloc at mm/percpu.c:1472 
> (discriminator 1)
> [ 1457.995502]  mount_fs+0x36/0x140:
>   mount_fs at fs/super.c:1220
> [ 1457.997415]  vfs_kern_mount+0x62/0x130:
>   vfs_kern_mount at 
> fs/namespace.c:1038
> [ 1457.999537]  do_mount+0x1d5/0xc90:
>   do_new_mount at 
> fs/namespace.c:2513
>(inlined by) do_mount at 
> fs/namespace.c:2841
> [ 1458.001440]  ? kmem_cache_alloc_trace+0x16d/0x1c0:
>   slab_pre_alloc_hook at 
> mm/slab.h:419
>(inlined by) slab_alloc_node 
> at mm/slub.c:2651
>(inlined by) slab_alloc at 
> mm/slub.c:2733
>(inlined by) 
> kmem_cache_alloc_trace at mm/slub.c:2750
> [ 1458.003603]  ? copy_mount_options+0x28/0x240:
>   copy_mount_options at 
> fs/namespace.c:2722
> [ 1458.005698]  SyS_mount+0x7e/0xd0
> [ 1458.007597]  entry_SYSCALL_64_fastpath+0x1a/0x7d:
>   entry_SYSCALL_64_fastpath at 
> arch/x86/entry/entry_64.S:210
> [ 1458.009808] RIP: 0033:0x7fb80683c98a
> [ 1458.011835] RSP: 

Re: Read before you deploy btrfs + zstd

[Nick Terrell]

> On Nov 28, 2017, at 3:49 PM, David Sterba <dste...@suse.cz> wrote:
> 
> On Tue, Nov 28, 2017 at 09:31:57PM +0000, Nick Terrell wrote:
>> 
>>> On Nov 21, 2017, at 8:22 AM, David Sterba <dste...@suse.cz> wrote:
>>> 
>>> On Wed, Nov 15, 2017 at 08:09:15PM +, Nick Terrell wrote:
>>>> On 11/15/17, 6:41 AM, "David Sterba" <dste...@suse.cz> wrote:
>>>>> The branch is now in a state that can be tested. Turns out the memory
>>>>> requirements are too much for grub, so the boot fails with "not enough
>>>>> memory". The calculated value
>>>>> 
>>>>> ZSTD_BTRFS_MAX_INPUT: 131072
>>>>> ZSTD_DStreamWorkspaceBound with ZSTD_BTRFS_MAX_INPUT: 549424
>>>>> 
>>>>> This is not something I could fix easily, we'd probalby need a tuned
>>>>> version of ZSTD for grub constraints. Adding Nick to CC.
>>>> 
>>>> If I understand the grub code correctly, we only need to read, and we have
>>>> the entire input and output buffer in one segment. In that case you can use
>>>> ZSTD_initDCtx(), and ZSTD_decompressDCtx(). ZSTD_DCtxWorkspaceBound() is
>>>> only 155984. See decompress_single() in
>>>> https://patchwork.kernel.org/patch/9997909/ for an example.
>>> 
>>> Does not help, still ENOMEM.
>> 
>> It looks like XZ had the same issue, and they make the decompression
>> context a static object (grep for GRUB_EMBED_DECOMPRESSOR). We could
>> potentially do the same and statically allocate the workspace:
>> 
>> ```
>> /* Could also be size_t */
>> #define BTRFS_ZSTD_WORKSPACE_SIZE_U64 (155984 / sizeof(uint64_t))
>> static uint64_t workspace[BTRFS_ZSTD_WORKSPACE_SIZE_U64];
>> 
>> /* ... */
>> 
>> assert(sizeof(workspace) >= ZSTD_DCtxWorkspaceBound());
>> ```
> 
> Interesting, thanks for the tip, I'll try it next.
> 
> I've meanwhile tried to tweak the numbers, the maximum block for zstd,
> that squeezed the DCtx somewhere under 48k, with block size 8k. Still
> enomem.

Sadly the block size has to stay 128 KiB, since that is the block size that
is used for compression.

> I've tried to add some debugging prints to see what numbers get actually
> passed to the allocator, but did not see anything printed.  I'm sure
> there is a more intelligent way to test the grub changes.  So far each
> test loop takes quite some time, as I build the rpm package, test it in
> a VM and have to recreate the environmet each time.

Is the code in github.com/kdave/grub in the btrfs-zstd branch up to date?
btrfs.c:1230 looks like it will error for zstd compression, but not with
ENOMEM. btrfs.c:1272 [2] looks like a typo. Maybe the second is causing
the compressed block to be interpreted as uncompressed, and causes a
too-large allocation?

[1] https://github.com/kdave/grub/blob/btrfs-zstd/grub-core/fs/btrfs.c#L1230
[2] https://github.com/kdave/grub/blob/btrfs-zstd/grub-core/fs/btrfs.c#L1272--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Btrfs progs pre-release 4.14-rc1

[Nick Terrell]

> On Nov 17, 2017, at 8:48 AM, Uli Heller  wrote:
> 
> I tried to compile these on ubuntu-14.04 running 4.4.0-98-generic
> - I had to install libzstd-dev
> - I had to disable the zstd tests
> 
> Do you think this ends up in a working binary? Or am I doing something 
> strange?

You'll need to install libzstd-dev to compile with zstd enabled, since you
need the libraries and headers. What version of libzstd do you have? You'll
need a version >= 0.8.1 in order to read the compressed data.

On the zstd side, we're working on getting the version of zstd in Ubuntu
16.04 upgraded from 0.5.1 to a version >= 1.0.0 [1]. zstd-0.5.1 was
released before the format stabilized, and can't read data produced by zstd
>= 0.6.

I would expect the zstd tests to fail if the zstd version is < 0.8.1.
Otherwise, could you tell me which version of zstd you have, and I'll
attempt to reproduce the issue.

[1] https://bugs.launchpad.net/xenial-backports/+bug/1717040

-Nick--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] btrfs: move some zstd work data from stack to workspace

[Nick Terrell]

On 11/15/17, 9:30 AM, "David Sterba" <dste...@suse.com> wrote:
> * ZSTD_inBuffer in_buf
> * ZSTD_outBuffer out_buf
>
> are used in all functions to pass the compression parameters and the
> local variables consume some space. We can move them to the workspace
> and reduce the stack consumption:
>
> zstd.c:zstd_decompress-24 (136 -> 112)
> zstd.c:zstd_decompress_bio-24 (144 -> 120)
> zstd.c:zstd_compress_pages-24 (264 -> 240)

It looks good to me, and I ran my btrfs zstd compression and
decompression test and everything worked.

Is there a case where these 24 bytes matter, or is this just an easy
optimization?

Reviewed-by: Nick Terrell <terre...@fb.com>

Re: Read before you deploy btrfs + zstd

[Nick Terrell]

On 11/15/17, 6:41 AM, "David Sterba"  wrote:
> The branch is now in a state that can be tested. Turns out the memory
> requirements are too much for grub, so the boot fails with "not enough
> memory". The calculated value
>
> ZSTD_BTRFS_MAX_INPUT: 131072
> ZSTD_DStreamWorkspaceBound with ZSTD_BTRFS_MAX_INPUT: 549424
>
> This is not something I could fix easily, we'd probalby need a tuned
> version of ZSTD for grub constraints. Adding Nick to CC.

If I understand the grub code correctly, we only need to read, and we have
the entire input and output buffer in one segment. In that case you can use
ZSTD_initDCtx(), and ZSTD_decompressDCtx(). ZSTD_DCtxWorkspaceBound() is
only 155984. See decompress_single() in
https://patchwork.kernel.org/patch/9997909/ for an example.

This (uncompiled and untested) code should work:

```
static grub_ssize_t
grub_btrfs_zstd_decompress(char *ibuf, grub_size_t isize, grub_off_t off,
   char *obuf, grub_size_t osize)
{
  grub_size_t ret = 0;
  ZSTD_DCtx *ctx;
  void *wmem;
  grub_size_t wsize;

  wsize = ZSTD_DCtxWorkspaceBound();
  wmem = grub_malloc(wsize);
  if (!wmem)
{
   return -1;
}
  ctx = ZSTD_initDCtx(wmem, wsize);
  if (!ctx)
{
   grub_free(wmem);
   return -1;
}

  /* This is only necessary if there is junk after the end of the zstd
   * compressed data in the input buffer. Otherwise the return value
   * should always be exactly isize. If you delete this, and it always works,
   * then there isn't junk data at the end.
   */
  isize = ZSTD_findFrameCompressedSize(in_buf, in_len);
  if (ZSTD_isError(isize))
{
   grub_free(wmem);
   return -1;
}

  ret = ZSTD_decompressDCtx(ctx, obuf, osize, ibuf, isize);
  grub_free(wmem);
  if (ZSTD_isError(ret))
{
   return -1;
}
  return ret;
}
```


N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

Re: [PATCH] btrfs: fix default compression value when set by SETFLAGS ioctl

[Nick Terrell]

On 10/31/17, 9:48 AM, "David Sterba" <dste...@suse.com> wrote:
> The current default for the compression file flag is 'zlib', the zstd
> patch silently changed that to zstd. Though the choice of zlib might not
> be the best one, we should keep the backward compatibility.

Sorry about that, I didn't intentionally change it. I checked over my patch,
and the only other place where an "else" was changed is the other place in
ioctl.c, which looks okay to me.

I'm trying to expose the buggy case in 4.14-rc7. However, since
fs_info->compress_type defaults to ZLIB when -compress is not passed, and
when -compress=no is passed, fs_info->compress_type is not modified, I
don't know how to get fs_info->compress_type to be BTRFS_COMPRESS_NONE.
Is there a way that fs_info->compress_type can be BTRFS_COMPRESS_NONE?

I modified -compress=no to set fs_info->compress_type=BTRFS_COMPRESS_NONE
and the ioctl() call set the compression type to zstd before your patch,
and zlib after, as expected.

Tested-by: Nick Terrell <terre...@fb.com>

> The incompat bit for zstd is not set, so this could lead to a filesystem
> with a zstd compression in the extents but no flag for the filesystem.
>
> Fixes: 5c1aab1dd5445ed8bd ("btrfs: Add zstd support")
> CC: Nick Terrell <terre...@fb.com>
> Signed-off-by: David Sterba <dste...@suse.com>

Re: [PATCH preview] btrfs: allow to set compression level for zlib

[Nick Terrell]

On 9/15/17, 7:53 AM, "David Sterba"  wrote:
> On Sun, Aug 20, 2017 at 06:38:50PM -0600, Chris Murphy wrote:
> > On Fri, Aug 18, 2017 at 10:08 AM, David Sterba  wrote:
> > 
> > > That's quite a lot, in kernel. IIRC zlib and lzo use less than 200kb,
> > > zstd wants 800kb for level 1. And this needs to be contiguous memory, so
> > > if we're lucky and get the memory at the mount time, fine. In general
> > > the memory can be fragmented (in the worst case, there are only 4k
> > > chunks available), so we'd have to vmalloc and consume the virtual,
> > > mappings in great numbers.
> > 
> > Any thoughts on bootloader support, both in general, and as it relates
> > to levels of compression and memory constraints? GRUB switches to
> > protected mode early on but other bootloaders might have more
> > limitations. I guess really it's just GRUB and extlinux right now,
> > there were patches some time ago for Das U-Boot but they still aren't
> > merged.
> 
> I'm not sure if the memory requirements are same for compression and
> decompression. The table is related to compression. I've looked around
> web to find what the decompression requirements are but havne't found
> anything.

In the BtrFS implementation, the same workspaces are used both for
compression and decompression, so they allocate enough memory for
compression. Decompression requires a constant 550 KB with a 128 KB window
size (which BtrFS has). You can find the numbers using the functions
ZSTD_estimateCStreamSize() and ZSTD_estimateDStreamSize().


N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

Re: [GIT PULL] zstd support (lib, btrfs, squashfs)

[Nick Terrell]

On 9/8/17, 6:36 PM, "Herbert Xu"  wrote:
> On Fri, Sep 08, 2017 at 03:33:05PM -0400, Chris Mason wrote:
> >
> >  crypto/Kconfig |9 +
> >  crypto/Makefile|1 +
> >  crypto/testmgr.c   |   10 +
> >  crypto/testmgr.h   |   71 +
> >  crypto/zstd.c  |  265 
> 
> Is there anyone going to use zstd through the crypto API? If not
> then I don't see the point in adding it at this point.  Especially
> as the compression API is still in a state of flux.

There is a patch [1] floating around adding zstd support to compressed RAM
that uses the crypto API.

[1] 
https://lkml.kernel.org/r/20170824014936.4738-1-sergey.senozhatsky%40gmail.com

[PATCH v2] btrfs-progs: Add zstd support

[Nick Terrell]

Adds zstd support to the btrfs program. An optional dependency on libzstd
>= 1.0.0 is added. Autoconf accepts `--enable-zstd' or `--disable-zstd' and
defaults to detecting if libzstd is present using `pkg-config'. Adds tests
for the new features based on a prebuilt btrfs image with a zstd compressed
file.

The patch is also available in my fork of btrfs-progs [1], which passes
Travis-CI with the new tests. The prebuilt binary is available there.

I haven't updated Android.mk.

[1] https://github.com/terrelln/btrfs-progs/tree/devel

Signed-off-by: Nick Terrell <terre...@fb.com>
---
v1 -> v2:
- Allow zstd support to be disabled, defaulting to auto detection
- Print if zstd is enabled/disabled when `./configure' finishes
- Add zstd test to patch with prebuilt image`

 .travis.yml|   9 
 Documentation/btrfs-filesystem.asciidoc|   2 +-
 Documentation/btrfs-man5.asciidoc  |   8 +++-
 Documentation/btrfs-property.asciidoc  |   2 +-
 INSTALL|   1 +
 Makefile   |   1 +
 Makefile.inc.in|   5 +-
 cmds-filesystem.c  |  16 ---
 cmds-inspect-dump-super.c  |   2 +-
 cmds-restore.c |  50 
 configure.ac   |  41 -
 ctree.h|  15 ++
 fsfeatures.h   |   2 +-
 print-tree.c   |   3 ++
 .../022-zstd-compression/compress.raw.xz   | Bin 0 -> 18256 bytes
 tests/misc-tests/022-zstd-compression/test.sh  |  51 +
 16 files changed, 172 insertions(+), 36 deletions(-)
 create mode 100644 tests/misc-tests/022-zstd-compression/compress.raw.xz
 create mode 100755 tests/misc-tests/022-zstd-compression/test.sh

diff --git a/.travis.yml b/.travis.yml
index 2aa44bd..50b3c1c 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -59,6 +59,15 @@ before_install:
  sudo make install;
  cd ../..
 "
+  - "mkdir tmp-zstd;
+ cd tmp-zstd;
+ wget https://github.com/facebook/zstd/archive/v1.3.1.tar.gz;
+ tar xf v1.3.1.tar.gz;
+ cd zstd-1.3.1;
+ make;
+ sudo make install PREFIX=/usr;
+ cd ../..
+"
   - "./autogen.sh && ./configure --disable-documentation && make"
 
 addons:
diff --git a/Documentation/btrfs-filesystem.asciidoc 
b/Documentation/btrfs-filesystem.asciidoc
index b60ef74..41b3032 100644
--- a/Documentation/btrfs-filesystem.asciidoc
+++ b/Documentation/btrfs-filesystem.asciidoc
@@ -112,7 +112,7 @@ KiB, MiB, GiB, TiB, PiB, or EiB, respectively (case does 
not matter).
 be verbose, print file names as they're submitted for defragmentation
 -c[]
 compress file contents while defragmenting. Optional argument selects the 
compression
-algorithm, 'zlib' (default) or 'lzo'. Currently it's not possible to select no
+algorithm, 'zlib' (default), 'lzo' or 'zstd'. Currently it's not possible to 
select no
 compression. See also section 'EXAMPLES'.
 -r
 defragment files recursively in given directories
diff --git a/Documentation/btrfs-man5.asciidoc 
b/Documentation/btrfs-man5.asciidoc
index 8d9031f..3981435 100644
--- a/Documentation/btrfs-man5.asciidoc
+++ b/Documentation/btrfs-man5.asciidoc
@@ -118,7 +118,7 @@ but a warning is printed if it's more than 300 seconds (5 
minutes).
 (default: off)
 +
 Control BTRFS file data compression.  Type may be specified as 'zlib',
-'lzo' or 'no' (for no compression, used for remounting).  If no type
+'lzo', 'zstd' or 'no' (for no compression, used for remounting).  If no type
 is specified, 'zlib' is used.  If 'compress-force' is specified,
 the compression will allways be attempted, but the data may end up uncompressed
 if the compression would make them larger.
@@ -472,6 +472,12 @@ page size
 the 'lzo' compression has been used on the filesystem, either as a mount option
 or via *btrfs filesystem defrag*.
 
+*compress_zstd*::
+(since: 4.14)
++
+the 'zstd' compression has been used on the filesystem, either as a mount 
option
+or via *btrfs filesystem defrag*.
+
 *default_subvol*::
 (since: 2.6.34)
 +
diff --git a/Documentation/btrfs-property.asciidoc 
b/Documentation/btrfs-property.asciidoc
index 05ab0bc..7ed6a7d 100644
--- a/Documentation/btrfs-property.asciidoc
+++ b/Documentation/btrfs-property.asciidoc
@@ -43,7 +43,7 @@ read-only flag of subvolume: true or false
 label
 label of device
 compression
-compression setting for an inode: lzo, zlib, or "" (empty string)
+compression setting for an inode: lzo, zlib, zstd, or "" (empty string)
 
 *list* [-t ] ::
 Lists available properties with their descriptions for the given object.
diff --git a/INSTALL b/INSTALL
index 0465fb0..

Re: [PATCH] btrfs-progs: Add zstd support

[Nick Terrell]

On 9/4/17, 11:03 AM, "linux-btrfs-ow...@vger.kernel.org on behalf of David 
Sterba" <linux-btrfs-ow...@vger.kernel.org on behalf of dste...@suse.cz> wrote:
> On Wed, Aug 30, 2017 at 02:53:22PM -0700, Nick Terrell wrote:
> > Adds zstd support to the btrfs program, and a dependency on libzstd >=
> > 1.0.0.
> 
> I'm afraid we'll have to make the build optional for now, as the distros
> may not provide it and I'd like to give at least some heads-up first. My
> idea is:
> 
> - check if zstd library is found, use it
> - otherwise warn that's it's going to be on by default in near future

I can see a few options, what do you want to see?

1. Require zstd for building `btrfs' but statically link it so users don't
   need to have zstd installed, unless they install from source.
2. Require zstd to build `btrfs', but dynamically link and use `dlopen' and
   `dlsym' to access the decompression function (and check the library
   version).
3. Make zstd optional in the build process, and completely disable it if
   unavailable. Otherwise dynamically link and do the same as (2).
4. Same as (3) but statically link if it is available.

I'm thinking that (3) is the best option for consistency with the other
libraries, at the expense of making the user install zstd if they want to
use it. We can put a nice warning message in `btrfs restore' that says you
need to install zstd.

> 'btrfs restore' would need to be enhanced to dump what's built in (in a
> similar way convert now prints the supported filesystem), and possibly
> warn that there are data compressed by zstd but there's no
> decrompression support.

Sounds good.

> > The patch is also available in my fork of btrfs-progs [1], which passes
> > Travis-CI. I tested each command that is effected in my test script [2].
> 
> The test requires zstd kernel support, which may be not available for
> some time in the testing environments. But as restore is userspace-only,
> we can create and use various images with zstd compressed data.

I'll modify my tests and add them to the test suite.

> > I haven't updated Android.mk since I have no way to test it, and am not
> > certain if it is used.
> 
> The anodroid build verification will work eventually through travis and
> I'm aware it could be out of sync, you don't need to care about that
> right now.

Re: \o/ compsize

[Nick Terrell]

On 9/4/17, 8:12 AM, "Adam Borowski"  wrote:
> Hi!
> Here's an utility to measure used compression type + ratio on a set of files
> or directories: https://github.com/kilobyte/compsize
> 
> It should be of great help for users, and also if you:
> * muck with compression levels
> * add new compression types
> * add heurestics that could err on withholding compression too much

Thanks for writing this tool Adam, I'll try it out with zstd! It looks very
useful for benchmarking compression algorithms, much better than measuring
the filesystem size with du/df.

> (Thanks for Knorrie and his python-btrfs project that made figuring out the
> ioctls much easier.)
> 
> Meow!
> -- 
> ⢀⣴⠾⠻⢶⣦⠀ 
> ⣾⠁⢰⠒⠀⣿⡁ Vat kind uf sufficiently advanced technology iz dis!?
> ⢿⡄⠘⠷⠚⠋⠀ -- Genghis Ht'rok'din
> ⠈⠳⣄ 
> 
 

N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

[PATCH] btrfs-progs: Add zstd support

[Nick Terrell]

Adds zstd support to the btrfs program, and a dependency on libzstd >=
1.0.0.

The patch is also available in my fork of btrfs-progs [1], which passes
Travis-CI. I tested each command that is effected in my test script [2].

I haven't updated Android.mk since I have no way to test it, and am not
certain if it is used.

[1] https://github.com/terrelln/btrfs-progs/tree/devel
[2] https://gist.github.com/terrelln/4136a369c5d10092956781433eed0a23

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 .travis.yml |  9 +++
 Documentation/btrfs-filesystem.asciidoc |  2 +-
 Documentation/btrfs-man5.asciidoc   |  8 +-
 Documentation/btrfs-property.asciidoc   |  2 +-
 INSTALL |  1 +
 Makefile.inc.in |  4 +--
 cmds-filesystem.c   | 16 ++--
 cmds-inspect-dump-super.c   |  2 +-
 cmds-restore.c  | 44 +
 configure.ac|  4 ++-
 ctree.h | 15 ---
 fsfeatures.h|  2 +-
 print-tree.c|  3 +++
 13 files changed, 87 insertions(+), 25 deletions(-)

diff --git a/.travis.yml b/.travis.yml
index 2aa44bd..50b3c1c 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -59,6 +59,15 @@ before_install:
  sudo make install;
  cd ../..
 "
+  - "mkdir tmp-zstd;
+ cd tmp-zstd;
+ wget https://github.com/facebook/zstd/archive/v1.3.1.tar.gz;
+ tar xf v1.3.1.tar.gz;
+ cd zstd-1.3.1;
+ make;
+ sudo make install PREFIX=/usr;
+ cd ../..
+"
   - "./autogen.sh && ./configure --disable-documentation && make"

 addons:
diff --git a/Documentation/btrfs-filesystem.asciidoc 
b/Documentation/btrfs-filesystem.asciidoc
index b60ef74..41b3032 100644
--- a/Documentation/btrfs-filesystem.asciidoc
+++ b/Documentation/btrfs-filesystem.asciidoc
@@ -112,7 +112,7 @@ KiB, MiB, GiB, TiB, PiB, or EiB, respectively (case does 
not matter).
 be verbose, print file names as they're submitted for defragmentation
 -c[]
 compress file contents while defragmenting. Optional argument selects the 
compression
-algorithm, 'zlib' (default) or 'lzo'. Currently it's not possible to select no
+algorithm, 'zlib' (default), 'lzo' or 'zstd'. Currently it's not possible to 
select no
 compression. See also section 'EXAMPLES'.
 -r
 defragment files recursively in given directories
diff --git a/Documentation/btrfs-man5.asciidoc 
b/Documentation/btrfs-man5.asciidoc
index 8d9031f..3981435 100644
--- a/Documentation/btrfs-man5.asciidoc
+++ b/Documentation/btrfs-man5.asciidoc
@@ -118,7 +118,7 @@ but a warning is printed if it's more than 300 seconds (5 
minutes).
 (default: off)
 +
 Control BTRFS file data compression.  Type may be specified as 'zlib',
-'lzo' or 'no' (for no compression, used for remounting).  If no type
+'lzo', 'zstd' or 'no' (for no compression, used for remounting).  If no type
 is specified, 'zlib' is used.  If 'compress-force' is specified,
 the compression will allways be attempted, but the data may end up uncompressed
 if the compression would make them larger.
@@ -472,6 +472,12 @@ page size
 the 'lzo' compression has been used on the filesystem, either as a mount option
 or via *btrfs filesystem defrag*.

+*compress_zstd*::
+(since: 4.14)
++
+the 'zstd' compression has been used on the filesystem, either as a mount 
option
+or via *btrfs filesystem defrag*.
+
 *default_subvol*::
 (since: 2.6.34)
 +
diff --git a/Documentation/btrfs-property.asciidoc 
b/Documentation/btrfs-property.asciidoc
index 05ab0bc..7ed6a7d 100644
--- a/Documentation/btrfs-property.asciidoc
+++ b/Documentation/btrfs-property.asciidoc
@@ -43,7 +43,7 @@ read-only flag of subvolume: true or false
 label
 label of device
 compression
-compression setting for an inode: lzo, zlib, or "" (empty string)
+compression setting for an inode: lzo, zlib, zstd, or "" (empty string)

 *list* [-t ] ::
 Lists available properties with their descriptions for the given object.
diff --git a/INSTALL b/INSTALL
index 0465fb0..686cefb 100644
--- a/INSTALL
+++ b/INSTALL
@@ -7,6 +7,7 @@ The Btrfs utility programs require the following 
libraries/tools to build:
 - libblkid - block device id library
 - liblzo2 - LZO data compression library
 - zlib - ZLIB data compression library
+- libzstd - ZSTD data compression library version >= 1.0.0

 For the btrfs-convert utility:

diff --git a/Makefile.inc.in b/Makefile.inc.in
index 3c7bc03..4076add 100644
--- a/Makefile.inc.in
+++ b/Makefile.inc.in
@@ -18,9 +18,9 @@ SUBST_CFLAGS = @CFLAGS@
 SUBST_LDFLAGS = @LDFLAGS@

 LIBS_BASE = @UUID_LIBS@ @BLKID_LIBS@ -L. -pthread
-LIBS_COMP = @ZLIB_LIBS@ @LZO2_LIBS@
+LIBS_COMP = @ZLIB_LIBS@ @LZO2_LIBS@ @ZSTD_LIBS@
 STATIC_LIBS_BASE = @UUID_LIBS_STATIC@ @BLKID_LIBS_STATIC@ -L. -pthread
-STATIC_LIBS_COMP = @Z

Re: [PATCH v5 3/5] btrfs: Add zstd support

[Nick Terrell]

On 8/10/17, 7:13 PM, "Adam Borowski" <kilob...@angband.pl> wrote:
> On Wed, Aug 09, 2017 at 07:39:02PM -0700, Nick Terrell wrote:
>> Add zstd compression and decompression support to BtrFS.
> 
> Re-tested on arm64, amd64 and i386, this time everything seems fine so far.
> 
> As I'm too lazy to have a separate test setup for the zlib level patch,
> I'm using a dummy implementation:
> 
> --- a/fs/btrfs/zstd.c
> +++ b/fs/btrfs/zstd.c
> @@ -423,10 +423,16 @@ static int zstd_decompress(struct list_head *ws, 
> unsigned char *data_in,
> return ret;
>  }
>  
> +static void zstd_set_level(struct list_head *ws, unsigned int type)
> +{
> +   // TODO
> +}
> +
>  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,
>  };
> 
> 
> It might be worthwhile to do some early testing using different levels,
> though.

I'll run some preliminary tests and make sure nothing blows up and the
compression ratio looks good.

> 
> 
> 喵!
> -- 
> ⢀⣴⠾⠻⢶⣦⠀ 
> ⣾⠁⢠⠒⠀⣿⡁ A dumb species has no way to open a tuna can.
> ⢿⡄⠘⠷⠚⠋⠀ A smart species invents a can opener.
> ⠈⠳⣄ A master species delegates.

Re: [PATCH v5 2/5] lib: Add zstd modules

[Nick Terrell]

On 8/10/17, 10:48 AM, "Austin S. Hemmelgarn" <ahferro...@gmail.com> wrote:
>On 2017-08-10 13:24, Eric Biggers wrote:
>>On Thu, Aug 10, 2017 at 07:32:18AM -0400, Austin S. Hemmelgarn wrote:
>>>On 2017-08-10 04:30, Eric Biggers wrote:
>>>>On Wed, Aug 09, 2017 at 07:35:53PM -0700, Nick Terrell wrote:
>>>>>
>>>>> It can compress at speeds approaching lz4, and quality approaching lzma.
>>>>
>>>> Well, for a very loose definition of "approaching", and certainly not at 
>>>> the
>>>> same time.  I doubt there's a use case for using the highest compression 
>>>> levels
>>>> in kernel mode --- especially the ones using zstd_opt.h.
>>> Large data-sets with WORM access patterns and infrequent writes
>>> immediately come to mind as a use case for the highest compression
>>> level.
>>>
>>> As a more specific example, the company I work for has a very large
>>> amount of documentation, and we keep all old versions.  This is all
>>> stored on a file server which is currently using BTRFS.  Once a
>>> document is written, it's almost never rewritten, so write
>>> performance only matters for the first write.  However, they're read
>>> back pretty frequently, so we need good read performance.  As of
>>> right now, the system is set to use LZO compression by default, and
>>> then when a new document is added, the previous version of that
>>> document gets re-compressed using zlib compression, which actually
>>> results in pretty significant space savings most of the time.  I
>>> would absolutely love to use zstd compression with this system with
>>> the highest compression level, because most people don't care how
>>> long it takes to write the file out, but they do care how long it
>>> takes to read a file (even if it's an older version).
>> 
>> This may be a reasonable use case, but note this cannot just be the regular
>> "zstd" compression setting, since filesystem compression by default must 
>> provide
>> reasonable performance for many different access patterns.  See the patch in
>> this series which actually adds zstd compression to btrfs; it only uses 
>> level 1.
>> I do not see a patch which adds a higher compression mode.  It would need to 
>> be
>> a special setting like "zstdhc" that users could opt-in to on specific
>> directories.  It also would need to be compared to simply compressing in
>> userspace.  In many cases compressing in userspace is probably the better
>> solution for the use case in question because it works on any filesystem, 
>> allows
>> using any compression algorithm, and if random access is not needed it is
>> possible to compress each file as a single stream (like a .xz file), which
>> produces a much better compression ratio than the block-by-block compression
>> that filesystems have to use.
> There has been discussion as well as (I think) initial patches merged 
> for support of specifying the compression level for algorithms which 
> support multiple compression levels in BTRFS.  I was actually under the 
> impression that we had decided to use level 3 as the default for zstd, 
> but that apparently isn't the case, and with the benchmark issues, it 
> may not be once proper benchmarks are run.

There are some initial patches to add compression levels to BtrFS [1]. Once
it's ready, we can add compression levels to zstd. The default compression
level in the current patch is 3.

[1] https://lkml.kernel.org/r/20170724172939.24527-1-dste...@suse.com


N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

Re: [PATCH v5 2/5] lib: Add zstd modules

[Nick Terrell]

On 8/10/17, 1:30 AM, "Eric Biggers" <ebigge...@gmail.com> wrote:
> On Wed, Aug 09, 2017 at 07:35:53PM -0700, Nick Terrell wrote:
>>
>> It can compress at speeds approaching lz4, and quality approaching lzma.
> 
> Well, for a very loose definition of "approaching", and certainly not at the
> same time.  I doubt there's a use case for using the highest compression 
> levels
> in kernel mode --- especially the ones using zstd_opt.h.
> 
>> 
>> The code was ported from the upstream zstd source repository.
> 
> What version?

zstd-1.1.4 with patches applied from upstream. I'll include it in the
next patch version.

>> `linux/zstd.h` header was modified to match linux kernel style.
>> The cross-platform and allocation code was stripped out. Instead zstd
>> requires the caller to pass a preallocated workspace. The source files
>> were clang-formatted [1] to match the Linux Kernel style as much as
>> possible. 
> 
> It would be easier to compare to the upstream version if it was not all
> reformatted.  There is a chance that bugs were introduced by Linux-specific
> changes, and it would be nice if they could be easily reviewed.  (Also I don't
> know what clang-format settings you used, but there are still a lot of
> differences from the Linux coding style.)

The clang-format settings I used are available in the zstd repo [1]. I left
the line length long, since it looked terrible otherwise.I set up a branch
in my zstd GitHub fork called "original-formatted" [2]. I've taken the source
I based the kernel patches off of [3] and ran clang-format without any other
changes. If you have any suggestions to improve the clang-formatting
please let me know.

>> 
>> I benchmarked zstd compression as a special character device. I ran zstd
>> and zlib compression at several levels, as well as performing no
>> compression, which measure the time spent copying the data to kernel space.
>> Data is passed to the compresser 4096 B at a time. The benchmark file is
>> located in the upstream zstd source repository under
>> `contrib/linux-kernel/zstd_compress_test.c` [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. I benchmarked using `silesia.tar` [3], which is
>> 211,988,480 B large. Run the following commands for the benchmark:
>> 
>> sudo modprobe zstd_compress_test
>> sudo mknod zstd_compress_test c 245 0
>> sudo cp silesia.tar zstd_compress_test
>> 
>> The time is reported by the time of the userland `cp`.
>> The MB/s is computed with
>> 
>> 1,536,217,008 B / time(buffer size, hash)
>> 
>> which includes the time to copy from userland.
>> The Adjusted MB/s is computed with
>> 
>> 1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).
>> 
>> The memory reported is the amount of memory the compressor requests.
>> 
>> | Method   | Size (B) | Time (s) | Ratio | MB/s| Adj MB/s | Mem (MB) |
>> |--|--|--|---|-|--|--|
>> | none | 11988480 |0.100 | 1 | 2119.88 |- |- |
>> | zstd -1  | 73645762 |1.044 | 2.878 |  203.05 |   224.56 | 1.23 |
>> | zstd -3  | 66988878 |1.761 | 3.165 |  120.38 |   127.63 | 2.47 |
>> | zstd -5  | 65001259 |2.563 | 3.261 |   82.71 |86.07 | 2.86 |
>> | zstd -10 | 60165346 |   13.242 | 3.523 |   16.01 |16.13 |13.22 |
>> | zstd -15 | 58009756 |   47.601 | 3.654 |4.45 | 4.46 |21.61 |
>> | zstd -19 | 54014593 |  102.835 | 3.925 |2.06 | 2.06 |60.15 |
>> | zlib -1  | 77260026 |2.895 | 2.744 |   73.23 |75.85 | 0.27 |
>> | zlib -3  | 72972206 |4.116 | 2.905 |   51.50 |52.79 | 0.27 |
>> | zlib -6  | 68190360 |9.633 | 3.109 |   22.01 |22.24 | 0.27 |
>> | zlib -9  | 67613382 |   22.554 | 3.135 |9.40 | 9.44 | 0.27 |
>> 
> 
> Theses benchmarks are misleading because they compress the whole file as a
> single stream without resetting the dictionary, which isn't how data will
> typically be compressed in kernel mode.  With filesystem compression the data
> has to be divided into small chunks that can each be decompressed 
> independently.
> That eliminates one of the primary advantages of Zstandard (support for large
> dictionary sizes).

This benchmark isn't meant to be representative of a filesystem scenario. I
wanted to show off zstd without anything else going on. Even in filesystems
where the data is chunked, zstd uses the whole chunk as the wind

[PATCH v5 3/5] btrfs: Add zstd support

[Nick Terrell]

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 <terre...@fb.com>
---
v2 -> v3:
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff
- Change default compression level for BtrFS to 3

v3 -> v4:
- Add missing includes, which fixes the aarch64 build
- Fix minor linter warnings

 fs/btrfs/Kconfig   |   2 +
 fs/btrfs/Makefile  |   2 +-
 fs/btrfs/compression.c |   1 +
 fs/btrfs/compression.h |   6 +-
 fs/btrfs/ctree.h   |   1 +
 fs/btrfs/disk-io.c |   2 +
 fs/btrfs/ioctl.c   |   6 +-
 fs/btrfs/props.c   |   6 +
 fs/btrfs/super.c   |  12 +-
 fs/btrfs/sysfs.c   |   2 +
 fs/btrfs/zstd.c| 432 +
 include/uapi/linux/btrfs.h |   8 +-
 12 files changed, 468 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18..a26c63b 100644
--- a/fs/btrfs/Kconfig
+++ b/fs/btrfs/Kconfig
@@ -6,6 +6,8 @@ config BTRFS_FS
select ZLIB_DEFLATE
select LZO_COMPRESS
select LZO_DECOMPRESS
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
select RAID6_PQ
select XOR_BLOCKS
select SRCU
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 128ce17..962a95a 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o 
root-tree.o dir-item.o \
   transaction.o inode.o file.o tree-defrag.o \
   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
-  export.o tree-log.o free-space-cache.o zlib.o lzo.o \
+  export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
   c

[PATCH v5 1/5] lib: Add xxhash module

[Nick Terrell]

Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
The zstd compression and decompression modules added in the next patch
require xxhash. I extracted it out from zstd since it is useful on its
own. I copied the code from the upstream XXHash source repository and
translated it into kernel style. I ran benchmarks and tests in the kernel
and tests in userland.

I benchmarked xxhash as a special character device. I ran in four modes,
no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to
kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute
hashes on the copied data. I also ran it with four different buffer sizes.
The benchmark file is located in the upstream zstd source repository under
`contrib/linux-kernel/xxhash_test.c` [1].

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. I benchmarked using the file `filesystem.squashfs`
from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large.
Run the following commands for the benchmark:

modprobe xxhash_test
mknod xxhash_test c 245 0
time cp filesystem.squashfs xxhash_test

The time is reported by the time of the userland `cp`.
The GB/s is computed with

1,536,217,008 B / time(buffer size, hash)

which includes the time to copy from userland.
The Normalized GB/s is computed with

1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).


| Buffer Size (B) | Hash  | Time (s) | GB/s | Adjusted GB/s |
|-|---|--|--|---|
|1024 | none  |0.408 | 3.77 | - |
|1024 | xxh32 |0.649 | 2.37 |  6.37 |
|1024 | xxh64 |0.542 | 2.83 | 11.46 |
|1024 | crc32 |1.290 | 1.19 |  1.74 |
|4096 | none  |0.380 | 4.04 | - |
|4096 | xxh32 |0.645 | 2.38 |  5.79 |
|4096 | xxh64 |0.500 | 3.07 | 12.80 |
|4096 | crc32 |1.168 | 1.32 |  1.95 |
|8192 | none  |0.351 | 4.38 | - |
|8192 | xxh32 |0.614 | 2.50 |  5.84 |
|8192 | xxh64 |0.464 | 3.31 | 13.60 |
|8192 | crc32 |1.163 | 1.32 |  1.89 |
|   16384 | none  |0.346 | 4.43 | - |
|   16384 | xxh32 |0.590 | 2.60 |  6.30 |
|   16384 | xxh64 |0.466 | 3.30 | 12.80 |
|   16384 | crc32 |1.183 | 1.30 |  1.84 |

Tested in userland using the test-suite in the zstd repo under
`contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the
kernel functions. A line in each branch of every function in `xxhash.c`
was commented out to ensure that the test-suite fails. Additionally
tested while testing zstd and with SMHasher [3].

[1] https://phabricator.intern.facebook.com/P57526246
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp
[3] https://github.com/aappleby/smhasher

zstd source repository: https://github.com/facebook/zstd
XXHash source repository: https://github.com/cyan4973/xxhash

Signed-off-by: Nick Terrell <terre...@fb.com>
---
v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const

 include/linux/xxhash.h | 236 +++
 lib/Kconfig|   3 +
 lib/Makefile   |   1 +
 lib/xxhash.c   | 500 +
 4 files changed, 740 insertions(+)
 create mode 100644 include/linux/xxhash.h
 create mode 100644 lib/xxhash.c

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000..9e1f42c
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, I

[PATCH v5 0/5] Add xxhash and zstd modules

[Nick Terrell]

Hi all,

This patch set adds xxhash, zstd compression, and zstd decompression
modules. It also adds zstd support to BtrFS and SquashFS.

Each patch has relevant summaries, benchmarks, and tests.

Best,
Nick Terrell

Changelog:

v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const (1/5)
- Use div_u64() for division of u64s (2/5)
- Reduce stack usage of ZSTD_compressSequences(), ZSTD_buildSeqTable(),
  ZSTD_decompressSequencesLong(), FSE_buildDTable(), FSE_decompress_wksp(),
  HUF_writeCTable(), HUF_readStats(), HUF_readCTable(),
  HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/5)
- No zstd function uses more than 400 B of stack space (2/5)

v2 -> v3:
- Work around gcc-7 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388
  (2/5)
- Fix bug in dictionary compression from upstream commit cc1522351f (2/5)
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff (3/5)
- Change default compression level for BtrFS to 3 (3/5)

v3 -> v4:
- Fix compiler warnings (2/5)
- Add missing includes (3/5)
- Fix minor linter warnings (3/5, 4/5)
- Add crypto patch (5/5)

v4 -> v5:
- Fix rare compression bug from upstream commit 308047eb5d (2/5)
- Fix bug introduced in v3 when working around the gcc-7 bug (2/5)
- Fix ZSTD_DStream initialization code in squashfs (4/5)
- Fix patch documentation for patches written by Sean Purcell (4/5)

Nick Terrell (5):
  lib: Add xxhash module
  lib: Add zstd modules
  btrfs: Add zstd support
  squashfs: Add zstd support
  crypto: Add zstd support

 crypto/Kconfig |9 +
 crypto/Makefile|1 +
 crypto/testmgr.c   |   10 +
 crypto/testmgr.h   |   71 +
 crypto/zstd.c  |  265 
 fs/btrfs/Kconfig   |2 +
 fs/btrfs/Makefile  |2 +-
 fs/btrfs/compression.c |1 +
 fs/btrfs/compression.h |6 +-
 fs/btrfs/ctree.h   |1 +
 fs/btrfs/disk-io.c |2 +
 fs/btrfs/ioctl.c   |6 +-
 fs/btrfs/props.c   |6 +
 fs/btrfs/super.c   |   12 +-
 fs/btrfs/sysfs.c   |2 +
 fs/btrfs/zstd.c|  432 ++
 fs/squashfs/Kconfig|   14 +
 fs/squashfs/Makefile   |1 +
 fs/squashfs/decompressor.c |7 +
 fs/squashfs/decompressor.h |4 +
 fs/squashfs/squashfs_fs.h  |1 +
 fs/squashfs/zstd_wrapper.c |  151 ++
 include/linux/xxhash.h |  236 +++
 include/linux/zstd.h   | 1157 +++
 include/uapi/linux/btrfs.h |8 +-
 lib/Kconfig|   11 +
 lib/Makefile   |3 +
 lib/xxhash.c   |  500 +++
 lib/zstd/Makefile  |   18 +
 lib/zstd/bitstream.h   |  374 +
 lib/zstd/compress.c| 3484 
 lib/zstd/decompress.c  | 2528 
 lib/zstd/entropy_common.c  |  243 +++
 lib/zstd/error_private.h   |   53 +
 lib/zstd/fse.h |  575 
 lib/zstd/fse_compress.c|  795 ++
 lib/zstd/fse_decompress.c  |  332 +
 lib/zstd/huf.h |  212 +++
 lib/zstd/huf_compress.c|  770 ++
 lib/zstd/huf_decompress.c  |  960 
 lib/zstd/mem.h |  151 ++
 lib/zstd/zstd_common.c |   75 +
 lib/zstd/zstd_internal.h   |  263 
 lib/zstd/zstd_opt.h| 1014 +
 44 files changed, 14756 insertions(+), 12 deletions(-)
 create mode 100644 crypto/zstd.c
 create mode 100644 fs/btrfs/zstd.c
 create mode 100644 fs/squashfs/zstd_wrapper.c
 create mode 100644 include/linux/xxhash.h
 create mode 100644 include/linux/zstd.h
 create mode 100644 lib/xxhash.c
 create mode 100644 lib/zstd/Makefile
 create mode 100644 lib/zstd/bitstream.h
 create mode 100644 lib/zstd/compress.c
 create mode 100644 lib/zstd/decompress.c
 create mode 100644 lib/zstd/entropy_common.c
 create mode 100644 lib/zstd/error_private.h
 create mode 100644 lib/zstd/fse.h
 create mode 100644 lib/zstd/fse_compress.c
 create mode 100644 lib/zstd/fse_decompress.c
 create mode 100644 lib/zstd/huf.h
 create mode 100644 lib/zstd/huf_compress.c
 create mode 100644 lib/zstd/huf_decompress.c
 create mode 100644 lib/zstd/mem.h
 create mode 100644 lib/zstd/zstd_common.c
 create mode 100644 lib/zstd/zstd_internal.h
 create mode 100644 lib/zstd/zstd_opt.h

--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH preview] btrfs: allow to set compression level for zlib

[Nick Terrell]

On 8/4/17, 6:27 PM, "Adam Borowski" <kilob...@angband.pl> wrote:
> On Fri, Aug 04, 2017 at 09:51:44PM +, Nick Terrell wrote:
> > On 07/25/2017 01:29 AM, David Sterba wrote:
> > > Preliminary support for setting compression level for zlib, the
> > > following works:
> > 
> > Thanks for working on this, I think it is a great feature.
> > I have a few comments relating to how it would work with zstd.
> 
> Like, currently crashing because of ->set_level being 0? :p
> 
> > > --- a/fs/btrfs/compression.c
> > > +++ b/fs/btrfs/compression.c
> > > @@ -866,6 +866,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
> > 
> > zstd has 19 levels, but we can either only allow the first 15 + default, or
> > provide a mapping from zstd-level to BtrFS zstd-level.
> 
> Or give it more bits.  Issues like this are exactly why this patch is marked
> "preview".
> 
> But, does zstd give any gains with high compression level but input data
> capped at 128KB?  I don't see levels above 15 on your benchmark, and certain
> compression algorithms give worse results at highest levels for small
> blocks.

Yeah, I stopped my benchmarks at 15, since without configurable compression
level, high levels didn't seem useful. But level 19 could be interesting if
you are building a base image that is widely distributed. When testing BtrFS
on the Silesia corpus, the compression ratio improved all the way to level
19.

> 
> > > @@ -888,9 +893,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);
> > 
> > zlib uses the same amount of memory independently of the compression level,
> > but zstd uses a different amount of memory for each level. zstd will have
> > to allocate memory here if it doesn't have enough (or has way to much),
> > will that be okay?
> 
> We can instead store workspaces per the encoded type+level, that'd allow
> having different levels on different mounts (then props, once we get there).
> 
> Depends on whether you want highest levels, though (asked above) -- the
> highest ones take drastically more memory, so if they're out, blindly
> reserving space for the highest supported level might be not too wasteful.

Looking at the memory usage of BtrFS zstd, the 128 KB window size keeps the
memory usage very reasonable up to level 19. The zstd compression levels
are computed using a tool that selects the parameters that give the best
compression ratio for a given compression speed target. Since BtrFS has a
fixed window size, the default compression levels might not be optimal. We
could compute our own compression levels for a 128 KB window size.

| Level | Memory |
|---||
| 1 | 0.8 MB |
| 2 | 1.0 MB |
| 3 | 1.3 MB |
| 4 | 0.9 MB |
| 5 | 1.4 MB |
| 6 | 1.5 MB |
| 7 | 1.4 MB |
| 8 | 1.8 MB |
| 9 | 1.8 MB |
| 10| 1.8 MB |
| 11| 1.8 MB |
| 12| 1.8 MB |
| 13| 2.4 MB |
| 14| 2.6 MB |
| 15| 2.6 MB |
| 16| 3.1 MB |
| 17| 3.1 MB |
| 18| 3.1 MB |
| 19| 3.1 MB |

The workspace memory usage for each compression level.

> 
> (I have only briefly looked at memory usage and set_level(), please ignore
> me if I babble incoherently -- in bed on a N900 so I can't test it right
> now.)
> 
> 
> Meow!
> -- 
> ⢀⣴⠾⠻⢶⣦⠀ What Would Jesus Do, MUD/MMORPG edition:
> ⣾⠁⢰⠒⠀⣿⡁ • multiplay with an admin char to benefit your mortal
> ⢿⡄⠘⠷⠚⠋⠀ • abuse item cloning bugs (the five fishes + two breads affair)
> ⠈⠳⣄ • use glitches to walk on water
> 

Re: [PATCH v4 4/5] squashfs: Add zstd support

[Nick Terrell]

On 8/4/17, 3:10 PM, "linus...@gmail.com on behalf of Linus Torvalds" 
<linus...@gmail.com on behalf of torva...@linux-foundation.org> wrote:
> On Fri, Aug 4, 2017 at 1:19 PM, Nick Terrell <terre...@fb.com> wrote:
> >
> > This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
> > taking over the submission process.
> 
> Please, if so, get Sean's sign-off, and also make sure that the patch
> gets submitted with
> 
>From: Sean Purcell <m...@seanp.xyz>
> 
> at the top of the body of the email so that authorship gets properly
> attributed by all the usual tools.
> 
>  Linus
> 

Thanks for the help, I'll fix it for the next version.

Re: [PATCH preview] btrfs: allow to set compression level for zlib

[Nick Terrell]

On 07/25/2017 01:29 AM, David Sterba wrote:
> Preliminary support for setting compression level for zlib, the
> following works:

Thanks for working on this, I think it is a great feature.
I have a few comments relating to how it would work with zstd.

> 
> $ 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 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   |  7 +--
>  fs/btrfs/zlib.c| 12 +++-
>  7 files changed, 50 insertions(+), 6 deletions(-)
> 
> diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
> index 8ba1b86c9b72..142206d68495 100644
> --- a/fs/btrfs/compression.c
> +++ b/fs/btrfs/compression.c
> @@ -866,6 +866,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

zstd has 19 levels, but we can either only allow the first 15 + default, or
provide a mapping from zstd-level to BtrFS zstd-level.

> + *
>   * @out_pages is an in/out parameter, holds maximum number of pages to 
> allocate
>   * and returns number of actually allocated pages
>   *
> @@ -880,7 +885,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,
> @@ -888,9 +893,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);

zlib uses the same amount of memory independently of the compression level,
but zstd uses a different amount of memory for each level. zstd will have
to allocate memory here if it doesn't have enough (or has way to much),
will that be okay?

>   ret = btrfs_compress_op[type-1]->compress_pages(workspace, mapping,
> start, pages,
> out_pages,
> @@ -1047,3 +1054,14 @@ int btrfs_decompress_buf2page(const char *buf, 
> unsigned long buf_start,
>  
>   return 1;
>  }
> +
> +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 89bcf975efb8..8a6db02d8732 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 @@ int btrfs_submit_compressed_write(struct inode *inode, u64 
> start,
>  int 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

[PATCH v4 5/5] crypto: Add zstd support

[Nick Terrell]

Adds zstd support to crypto and scompress. Only supports the default
level.

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 crypto/Kconfig   |   9 ++
 crypto/Makefile  |   1 +
 crypto/testmgr.c |  10 +++
 crypto/testmgr.h |  71 +++
 crypto/zstd.c| 265 +++
 5 files changed, 356 insertions(+)
 create mode 100644 crypto/zstd.c

diff --git a/crypto/Kconfig b/crypto/Kconfig
index caa770e..4fc3936 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1662,6 +1662,15 @@ config CRYPTO_LZ4HC
help
  This is the LZ4 high compression mode algorithm.
 
+config CRYPTO_ZSTD
+   tristate "Zstd compression algorithm"
+   select CRYPTO_ALGAPI
+   select CRYPTO_ACOMP2
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
+   help
+ This is the zstd algorithm.
+
 comment "Random Number Generation"
 
 config CRYPTO_ANSI_CPRNG
diff --git a/crypto/Makefile b/crypto/Makefile
index d41f033..b22e1e8 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -133,6 +133,7 @@ obj-$(CONFIG_CRYPTO_USER_API_HASH) += algif_hash.o
 obj-$(CONFIG_CRYPTO_USER_API_SKCIPHER) += algif_skcipher.o
 obj-$(CONFIG_CRYPTO_USER_API_RNG) += algif_rng.o
 obj-$(CONFIG_CRYPTO_USER_API_AEAD) += algif_aead.o
+obj-$(CONFIG_CRYPTO_ZSTD) += zstd.o
 
 ecdh_generic-y := ecc.o
 ecdh_generic-y += ecdh.o
diff --git a/crypto/testmgr.c b/crypto/testmgr.c
index 7125ba3..8a124d3 100644
--- a/crypto/testmgr.c
+++ b/crypto/testmgr.c
@@ -3603,6 +3603,16 @@ static const struct alg_test_desc alg_test_descs[] = {
.decomp = 
__VECS(zlib_deflate_decomp_tv_template)
}
}
+   }, {
+   .alg = "zstd",
+   .test = alg_test_comp,
+   .fips_allowed = 1,
+   .suite = {
+   .comp = {
+   .comp = __VECS(zstd_comp_tv_template),
+   .decomp = __VECS(zstd_decomp_tv_template)
+   }
+   }
}
 };
 
diff --git a/crypto/testmgr.h b/crypto/testmgr.h
index 6ceb0e2..e6b5920 100644
--- a/crypto/testmgr.h
+++ b/crypto/testmgr.h
@@ -34631,4 +34631,75 @@ static const struct comp_testvec 
lz4hc_decomp_tv_template[] = {
},
 };
 
+static const struct comp_testvec zstd_comp_tv_template[] = {
+   {
+   .inlen  = 68,
+   .outlen = 39,
+   .input  = "The algorithm is zstd. "
+ "The algorithm is zstd. "
+ "The algorithm is zstd.",
+   .output = "\x28\xb5\x2f\xfd\x00\x50\xf5\x00\x00\xb8\x54\x68\x65"
+ "\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x20\x69\x73"
+ "\x20\x7a\x73\x74\x64\x2e\x20\x01\x00\x55\x73\x36\x01"
+ ,
+   },
+   {
+   .inlen  = 244,
+   .outlen = 151,
+   .input  = "zstd, short for Zstandard, is a fast lossless "
+ "compression algorithm, targeting real-time "
+ "compression scenarios at zlib-level and better "
+ "compression ratios. The zstd compression library "
+ "provides in-memory compression and decompression "
+ "functions.",
+   .output = "\x28\xb5\x2f\xfd\x00\x50\x75\x04\x00\x42\x4b\x1e\x17"
+ "\x90\x81\x31\x00\xf2\x2f\xe4\x36\xc9\xef\x92\x88\x32"
+ "\xc9\xf2\x24\x94\xd8\x68\x9a\x0f\x00\x0c\xc4\x31\x6f"
+ "\x0d\x0c\x38\xac\x5c\x48\x03\xcd\x63\x67\xc0\xf3\xad"
+ "\x4e\x90\xaa\x78\xa0\xa4\xc5\x99\xda\x2f\xb6\x24\x60"
+ "\xe2\x79\x4b\xaa\xb6\x6b\x85\x0b\xc9\xc6\x04\x66\x86"
+ "\xe2\xcc\xe2\x25\x3f\x4f\x09\xcd\xb8\x9d\xdb\xc1\x90"
+ "\xa9\x11\xbc\x35\x44\x69\x2d\x9c\x64\x4f\x13\x31\x64"
+ "\xcc\xfb\x4d\x95\x93\x86\x7f\x33\x7f\x1a\xef\xe9\x30"
+ "\xf9\x67\xa1\x94\x0a\x69\x0f\x60\xcd\xc3\xab\x99\xdc"
+ "\x42\xed\x97\x05\x00\x33\xc3\x15\x95\x3a\x06\xa0\x0e"
+ "\x20\xa9\x0e\x82\xb9\x43\x45\x01",
+   },
+};
+
+static const struct comp_testvec zstd_decomp_tv_template[] = {
+   {
+   .inlen  = 43,
+   .outlen = 68,
+   .input  = "\x28\xb5\x2f\xfd\x04\x50\xf5\x00\x00\xb8\x54\x68\x65"
+ "\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x20\x69\x73"
+ "\x20\

[PATCH v4 4/5] squashfs: Add zstd support

[Nick Terrell]

Add zstd compression and decompression support to SquashFS. zstd is a
great fit for SquashFS because it can compress at ratios approaching xz,
while decompressing twice as fast as zlib. For SquashFS in particular,
it can decompress as fast as lzo and lz4. It also has the flexibility
to turn down the compression ratio for faster compression times.

The compression benchmark is run on the file tree from the SquashFS archive
found in ubuntu-16.10-desktop-amd64.iso [1]. It uses `mksquashfs` with the
default block size (128 KB) and and various compression algorithms/levels.
xz and zstd are also benchmarked with 256 KB blocks. The decompression
benchmark times how long it takes to `tar` the file tree into `/dev/null`.
See the benchmark file in the upstream zstd source repository located under
`contrib/linux-kernel/squashfs-benchmark.sh` [2] for details.

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.

| Method | Ratio | Compression MB/s | Decompression MB/s |
||---|--||
| gzip   |  2.92 |   15 |128 |
| lzo|  2.64 |  9.5 |217 |
| lz4|  2.12 |   94 |218 |
| xz |  3.43 |  5.5 | 35 |
| xz 256 KB  |  3.53 |  5.4 | 40 |
| zstd 1 |  2.71 |   96 |210 |
| zstd 5 |  2.93 |   69 |198 |
| zstd 10|  3.01 |   41 |225 |
| zstd 15|  3.13 | 11.4 |224 |
| zstd 16 256 KB |  3.24 |  8.1 |210 |

This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
taking over the submission process.

[1] http://releases.ubuntu.com/16.10/
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh

zstd source repository: https://github.com/facebook/zstd

Cc: Sean Purcell <m...@seanp.xyz>
Signed-off-by: Nick Terrell <terre...@fb.com>
---
v3 -> v4:
- Fix minor linter warnings

 fs/squashfs/Kconfig|  14 +
 fs/squashfs/Makefile   |   1 +
 fs/squashfs/decompressor.c |   7 +++
 fs/squashfs/decompressor.h |   4 ++
 fs/squashfs/squashfs_fs.h  |   1 +
 fs/squashfs/zstd_wrapper.c | 149 +
 6 files changed, 176 insertions(+)
 create mode 100644 fs/squashfs/zstd_wrapper.c

diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
index ffb093e..1adb334 100644
--- a/fs/squashfs/Kconfig
+++ b/fs/squashfs/Kconfig
@@ -165,6 +165,20 @@ config SQUASHFS_XZ

  If unsure, say N.

+config SQUASHFS_ZSTD
+   bool "Include support for ZSTD compressed file systems"
+   depends on SQUASHFS
+   select ZSTD_DECOMPRESS
+   help
+ Saying Y here includes support for reading Squashfs file systems
+ compressed with ZSTD compression.  ZSTD gives better compression than
+ the default ZLIB compression, while using less CPU.
+
+ ZSTD is not the standard compression used in Squashfs and so most
+ file systems will be readable without selecting this option.
+
+ If unsure, say N.
+
 config SQUASHFS_4K_DEVBLK_SIZE
bool "Use 4K device block size?"
depends on SQUASHFS
diff --git a/fs/squashfs/Makefile b/fs/squashfs/Makefile
index 246a6f3..6655631 100644
--- a/fs/squashfs/Makefile
+++ b/fs/squashfs/Makefile
@@ -15,3 +15,4 @@ squashfs-$(CONFIG_SQUASHFS_LZ4) += lz4_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_LZO) += lzo_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_XZ) += xz_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_ZLIB) += zlib_wrapper.o
+squashfs-$(CONFIG_SQUASHFS_ZSTD) += zstd_wrapper.o
diff --git a/fs/squashfs/decompressor.c b/fs/squashfs/decompressor.c
index d2bc136..8366398 100644
--- a/fs/squashfs/decompressor.c
+++ b/fs/squashfs/decompressor.c
@@ -65,6 +65,12 @@ static const struct squashfs_decompressor 
squashfs_zlib_comp_ops = {
 };
 #endif

+#ifndef CONFIG_SQUASHFS_ZSTD
+static const struct squashfs_decompressor squashfs_zstd_comp_ops = {
+   NULL, NULL, NULL, NULL, ZSTD_COMPRESSION, "zstd", 0
+};
+#endif
+
 static const struct squashfs_decompressor squashfs_unknown_comp_ops = {
NULL, NULL, NULL, NULL, 0, "unknown", 0
 };
@@ -75,6 +81,7 @@ static const struct squashfs_decompressor *decompressor[] = {
_lzo_comp_ops,
_xz_comp_ops,
_lzma_unsupported_comp_ops,
+   _zstd_comp_ops,
_unknown_comp_ops
 };

diff --git a/fs/squashfs/decompressor.h b/fs/squashfs/decompressor.h
index a25713c..0f5a8e4 100644
--- a/fs/squashfs/decompressor.h
+++ b/fs/squashfs/decompressor.h
@@ -58,4 +58,8 @@ extern const struct squashfs_decompressor 
squashfs_lzo_comp_ops;
 extern const struct s

[PATCH v4 3/5] btrfs: Add zstd support

[Nick Terrell]

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 <terre...@fb.com>
---
v2 -> v3:
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff
- Change default compression level for BtrFS to 3

v3 -> v4:
- Add missing includes, which fixes the aarch64 build
- Fix minor linter warnings

 fs/btrfs/Kconfig   |   2 +
 fs/btrfs/Makefile  |   2 +-
 fs/btrfs/compression.c |   1 +
 fs/btrfs/compression.h |   6 +-
 fs/btrfs/ctree.h   |   1 +
 fs/btrfs/disk-io.c |   2 +
 fs/btrfs/ioctl.c   |   6 +-
 fs/btrfs/props.c   |   6 +
 fs/btrfs/super.c   |  12 +-
 fs/btrfs/sysfs.c   |   2 +
 fs/btrfs/zstd.c| 432 +
 include/uapi/linux/btrfs.h |   8 +-
 12 files changed, 468 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18..a26c63b 100644
--- a/fs/btrfs/Kconfig
+++ b/fs/btrfs/Kconfig
@@ -6,6 +6,8 @@ config BTRFS_FS
select ZLIB_DEFLATE
select LZO_COMPRESS
select LZO_DECOMPRESS
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
select RAID6_PQ
select XOR_BLOCKS
select SRCU
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 128ce17..962a95a 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o 
root-tree.o dir-item.o \
   transaction.o inode.o file.o tree-defrag.o \
   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
-  export.o tree-log.o free-space-cache.o zlib.o lzo.o \
+  export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
   c

[PATCH v4 1/5] lib: Add xxhash module

[Nick Terrell]

Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
The zstd compression and decompression modules added in the next patch
require xxhash. I extracted it out from zstd since it is useful on its
own. I copied the code from the upstream XXHash source repository and
translated it into kernel style. I ran benchmarks and tests in the kernel
and tests in userland.

I benchmarked xxhash as a special character device. I ran in four modes,
no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to
kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute
hashes on the copied data. I also ran it with four different buffer sizes.
The benchmark file is located in the upstream zstd source repository under
`contrib/linux-kernel/xxhash_test.c` [1].

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. I benchmarked using the file `filesystem.squashfs`
from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large.
Run the following commands for the benchmark:

modprobe xxhash_test
mknod xxhash_test c 245 0
time cp filesystem.squashfs xxhash_test

The time is reported by the time of the userland `cp`.
The GB/s is computed with

1,536,217,008 B / time(buffer size, hash)

which includes the time to copy from userland.
The Normalized GB/s is computed with

1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).


| Buffer Size (B) | Hash  | Time (s) | GB/s | Adjusted GB/s |
|-|---|--|--|---|
|1024 | none  |0.408 | 3.77 | - |
|1024 | xxh32 |0.649 | 2.37 |  6.37 |
|1024 | xxh64 |0.542 | 2.83 | 11.46 |
|1024 | crc32 |1.290 | 1.19 |  1.74 |
|4096 | none  |0.380 | 4.04 | - |
|4096 | xxh32 |0.645 | 2.38 |  5.79 |
|4096 | xxh64 |0.500 | 3.07 | 12.80 |
|4096 | crc32 |1.168 | 1.32 |  1.95 |
|8192 | none  |0.351 | 4.38 | - |
|8192 | xxh32 |0.614 | 2.50 |  5.84 |
|8192 | xxh64 |0.464 | 3.31 | 13.60 |
|8192 | crc32 |1.163 | 1.32 |  1.89 |
|   16384 | none  |0.346 | 4.43 | - |
|   16384 | xxh32 |0.590 | 2.60 |  6.30 |
|   16384 | xxh64 |0.466 | 3.30 | 12.80 |
|   16384 | crc32 |1.183 | 1.30 |  1.84 |

Tested in userland using the test-suite in the zstd repo under
`contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the
kernel functions. A line in each branch of every function in `xxhash.c`
was commented out to ensure that the test-suite fails. Additionally
tested while testing zstd and with SMHasher [3].

[1] https://phabricator.intern.facebook.com/P57526246
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp
[3] https://github.com/aappleby/smhasher

zstd source repository: https://github.com/facebook/zstd
XXHash source repository: https://github.com/cyan4973/xxhash

Signed-off-by: Nick Terrell <terre...@fb.com>
---
v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const

 include/linux/xxhash.h | 236 +++
 lib/Kconfig|   3 +
 lib/Makefile   |   1 +
 lib/xxhash.c   | 500 +
 4 files changed, 740 insertions(+)
 create mode 100644 include/linux/xxhash.h
 create mode 100644 lib/xxhash.c

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000..9e1f42c
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, I

[PATCH v4 0/5] Add xxhash and zstd modules

[Nick Terrell]

Hi all,

This patch set adds xxhash, zstd compression, and zstd decompression
modules. It also adds zstd support to BtrFS and SquashFS.

Each patch has relevant summaries, benchmarks, and tests.

Best,
Nick Terrell

Changelog:

v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const (1/5)
- Use div_u64() for division of u64s (2/5)
- Reduce stack usage of ZSTD_compressSequences(), ZSTD_buildSeqTable(),
  ZSTD_decompressSequencesLong(), FSE_buildDTable(), FSE_decompress_wksp(),
  HUF_writeCTable(), HUF_readStats(), HUF_readCTable(),
  HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/5)
- No zstd function uses more than 400 B of stack space (2/5)

v2 -> v3:
- Work around gcc-7 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388
  (2/5)
- Fix bug in dictionary compression from upstream commit cc1522351f (2/5)
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff (3/5)
- Change default compression level for BtrFS to 3 (3/5)

v3 -> v4:
- Fix compiler warnings (2/5)
- Add missing includes (3/5)
- Fix minor linter warnings (3/5, 4/5)
- Add crypto patch (5/5)

Nick Terrell (5):
  lib: Add xxhash module
  lib: Add zstd modules
  btrfs: Add zstd support
  squashfs: Add zstd support
  crypto: Add zstd support

 crypto/Kconfig |9 +
 crypto/Makefile|1 +
 crypto/testmgr.c   |   10 +
 crypto/testmgr.h   |   71 +
 crypto/zstd.c  |  265 
 fs/btrfs/Kconfig   |2 +
 fs/btrfs/Makefile  |2 +-
 fs/btrfs/compression.c |1 +
 fs/btrfs/compression.h |6 +-
 fs/btrfs/ctree.h   |1 +
 fs/btrfs/disk-io.c |2 +
 fs/btrfs/ioctl.c   |6 +-
 fs/btrfs/props.c   |6 +
 fs/btrfs/super.c   |   12 +-
 fs/btrfs/sysfs.c   |2 +
 fs/btrfs/zstd.c|  432 ++
 fs/squashfs/Kconfig|   14 +
 fs/squashfs/Makefile   |1 +
 fs/squashfs/decompressor.c |7 +
 fs/squashfs/decompressor.h |4 +
 fs/squashfs/squashfs_fs.h  |1 +
 fs/squashfs/zstd_wrapper.c |  149 ++
 include/linux/xxhash.h |  236 +++
 include/linux/zstd.h   | 1157 +++
 include/uapi/linux/btrfs.h |8 +-
 lib/Kconfig|   11 +
 lib/Makefile   |3 +
 lib/xxhash.c   |  500 +++
 lib/zstd/Makefile  |   18 +
 lib/zstd/bitstream.h   |  374 +
 lib/zstd/compress.c| 3479 
 lib/zstd/decompress.c  | 2528 
 lib/zstd/entropy_common.c  |  243 
 lib/zstd/error_private.h   |   53 +
 lib/zstd/fse.h |  575 
 lib/zstd/fse_compress.c|  795 ++
 lib/zstd/fse_decompress.c  |  332 +
 lib/zstd/huf.h |  212 +++
 lib/zstd/huf_compress.c|  770 ++
 lib/zstd/huf_decompress.c  |  960 
 lib/zstd/mem.h |  151 ++
 lib/zstd/zstd_common.c |   75 +
 lib/zstd/zstd_internal.h   |  250 
 lib/zstd/zstd_opt.h| 1014 +
 44 files changed, 14736 insertions(+), 12 deletions(-)
 create mode 100644 crypto/zstd.c
 create mode 100644 fs/btrfs/zstd.c
 create mode 100644 fs/squashfs/zstd_wrapper.c
 create mode 100644 include/linux/xxhash.h
 create mode 100644 include/linux/zstd.h
 create mode 100644 lib/xxhash.c
 create mode 100644 lib/zstd/Makefile
 create mode 100644 lib/zstd/bitstream.h
 create mode 100644 lib/zstd/compress.c
 create mode 100644 lib/zstd/decompress.c
 create mode 100644 lib/zstd/entropy_common.c
 create mode 100644 lib/zstd/error_private.h
 create mode 100644 lib/zstd/fse.h
 create mode 100644 lib/zstd/fse_compress.c
 create mode 100644 lib/zstd/fse_decompress.c
 create mode 100644 lib/zstd/huf.h
 create mode 100644 lib/zstd/huf_compress.c
 create mode 100644 lib/zstd/huf_decompress.c
 create mode 100644 lib/zstd/mem.h
 create mode 100644 lib/zstd/zstd_common.c
 create mode 100644 lib/zstd/zstd_internal.h
 create mode 100644 lib/zstd/zstd_opt.h

--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v3 4/4] squashfs: Add zstd support

[Nick Terrell]

On 7/30/17, 6:50 PM, "Phillip Lougher" <phillip.loug...@gmail.com> wrote:
> On Thu, Jul 20, 2017 at 10:27 PM, Nick Terrell <terre...@fb.com> wrote:
>> Add zstd compression and decompression support to SquashFS. zstd is a
>> great fit for SquashFS because it can compress at ratios approaching xz,
>> while decompressing twice as fast as zlib. For SquashFS in particular,
>> it can decompress as fast as lzo and lz4. It also has the flexibility
>> to turn down the compression ratio for faster compression times.
>
> Hi Nick,
>
> This patch (and none of the previous versions) is showing up on
> squashfs-de...@lists.sourceforge.net.  I also think you should have
> emailed me directly as a courtesy, as I'm the Squashfs author and
> maintainer.

Sorry about that Phillip, it was an oversight on my part. I've added you to
the CC list going forward, and have subscribed to the mailing list.

>> | Method>> | Ratio | Compression MB/s | Decompression MB/s |
>> ||---|--||
>> | gzip>>   |  2.92 |>>>   15 |>>>>128 |
>> | lzo>>>|  2.64 |>>>  9.5 |>>>>217 |
>> | lz4>>>|  2.12 |>>>   94 |>>>>218 |
>> | xz>>> |  3.43 |>>>  5.5 |>>>> 35 |
>> | xz 256 KB>  |  3.53 |>>>  5.4 |>>>> 40 |
>> | zstd 1>> |  2.71 |>>>   96 |>>>>210 |
>> | zstd 5>> |  2.93 |>>>   69 |>>>>198 |
>> | zstd 10>>|  3.01 |>>>   41 |>>>>225 |
>> | zstd 15>>|  3.13 |>>> 11.4 |>>>>224 |
>> | zstd 16 256 KB |  3.24 |>>>  8.1 |>>>>210 |
>
>
> Those numbers look good to me.
>
>>
>> This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
>> taking over the submission process.
>>
>> [1] http://releases.ubuntu.com/16.10/
>> [2] 
>> https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh
>
> I can't find your patch that adds zstd to the user-land
> Squashfs-tools.  That would be handy to do any testing :-)
>
> Phillip

I'll include the squashfs-tools patch that Sean just posted in the next
version.

[PATCH v3 3/4] btrfs: Add zstd support

[Nick Terrell]

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 <terre...@fb.com>
---
v2 -> v3:
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff
- Change default compression level for BtrFS to 3

 fs/btrfs/Kconfig   |   2 +
 fs/btrfs/Makefile  |   2 +-
 fs/btrfs/compression.c |   1 +
 fs/btrfs/compression.h |   6 +-
 fs/btrfs/ctree.h   |   1 +
 fs/btrfs/disk-io.c |   2 +
 fs/btrfs/ioctl.c   |   6 +-
 fs/btrfs/props.c   |   6 +
 fs/btrfs/super.c   |  12 +-
 fs/btrfs/sysfs.c   |   2 +
 fs/btrfs/zstd.c| 435 +
 include/uapi/linux/btrfs.h |   8 +-
 12 files changed, 471 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18..a26c63b 100644
--- a/fs/btrfs/Kconfig
+++ b/fs/btrfs/Kconfig
@@ -6,6 +6,8 @@ config BTRFS_FS
select ZLIB_DEFLATE
select LZO_COMPRESS
select LZO_DECOMPRESS
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
select RAID6_PQ
select XOR_BLOCKS
select SRCU
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 128ce17..962a95a 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o 
root-tree.o dir-item.o \
   transaction.o inode.o file.o tree-defrag.o \
   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
-  export.o tree-log.o free-space-cache.o zlib.o lzo.o \
+  export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
   compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o \
   reada.o backref.

[PATCH v3 4/4] squashfs: Add zstd support

[Nick Terrell]

Add zstd compression and decompression support to SquashFS. zstd is a
great fit for SquashFS because it can compress at ratios approaching xz,
while decompressing twice as fast as zlib. For SquashFS in particular,
it can decompress as fast as lzo and lz4. It also has the flexibility
to turn down the compression ratio for faster compression times.

The compression benchmark is run on the file tree from the SquashFS archive
found in ubuntu-16.10-desktop-amd64.iso [1]. It uses `mksquashfs` with the
default block size (128 KB) and and various compression algorithms/levels.
xz and zstd are also benchmarked with 256 KB blocks. The decompression
benchmark times how long it takes to `tar` the file tree into `/dev/null`.
See the benchmark file in the upstream zstd source repository located under
`contrib/linux-kernel/squashfs-benchmark.sh` [2] for details.

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.

| Method | Ratio | Compression MB/s | Decompression MB/s |
||---|--||
| gzip   |  2.92 |   15 |128 |
| lzo|  2.64 |  9.5 |217 |
| lz4|  2.12 |   94 |218 |
| xz |  3.43 |  5.5 | 35 |
| xz 256 KB  |  3.53 |  5.4 | 40 |
| zstd 1 |  2.71 |   96 |210 |
| zstd 5 |  2.93 |   69 |198 |
| zstd 10|  3.01 |   41 |225 |
| zstd 15|  3.13 | 11.4 |224 |
| zstd 16 256 KB |  3.24 |  8.1 |210 |

This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
taking over the submission process.

[1] http://releases.ubuntu.com/16.10/
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh

zstd source repository: https://github.com/facebook/zstd

Cc: Sean Purcell <m...@seanp.xyz>
Signed-off-by: Nick Terrell <terre...@fb.com>
---
 fs/squashfs/Kconfig|  14 +
 fs/squashfs/Makefile   |   1 +
 fs/squashfs/decompressor.c |   7 +++
 fs/squashfs/decompressor.h |   4 ++
 fs/squashfs/squashfs_fs.h  |   1 +
 fs/squashfs/zstd_wrapper.c | 150 +
 6 files changed, 177 insertions(+)
 create mode 100644 fs/squashfs/zstd_wrapper.c

diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
index ffb093e..1adb334 100644
--- a/fs/squashfs/Kconfig
+++ b/fs/squashfs/Kconfig
@@ -165,6 +165,20 @@ config SQUASHFS_XZ

  If unsure, say N.

+config SQUASHFS_ZSTD
+   bool "Include support for ZSTD compressed file systems"
+   depends on SQUASHFS
+   select ZSTD_DECOMPRESS
+   help
+ Saying Y here includes support for reading Squashfs file systems
+ compressed with ZSTD compression.  ZSTD gives better compression than
+ the default ZLIB compression, while using less CPU.
+
+ ZSTD is not the standard compression used in Squashfs and so most
+ file systems will be readable without selecting this option.
+
+ If unsure, say N.
+
 config SQUASHFS_4K_DEVBLK_SIZE
bool "Use 4K device block size?"
depends on SQUASHFS
diff --git a/fs/squashfs/Makefile b/fs/squashfs/Makefile
index 246a6f3..6655631 100644
--- a/fs/squashfs/Makefile
+++ b/fs/squashfs/Makefile
@@ -15,3 +15,4 @@ squashfs-$(CONFIG_SQUASHFS_LZ4) += lz4_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_LZO) += lzo_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_XZ) += xz_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_ZLIB) += zlib_wrapper.o
+squashfs-$(CONFIG_SQUASHFS_ZSTD) += zstd_wrapper.o
diff --git a/fs/squashfs/decompressor.c b/fs/squashfs/decompressor.c
index d2bc136..8366398 100644
--- a/fs/squashfs/decompressor.c
+++ b/fs/squashfs/decompressor.c
@@ -65,6 +65,12 @@ static const struct squashfs_decompressor 
squashfs_zlib_comp_ops = {
 };
 #endif

+#ifndef CONFIG_SQUASHFS_ZSTD
+static const struct squashfs_decompressor squashfs_zstd_comp_ops = {
+   NULL, NULL, NULL, NULL, ZSTD_COMPRESSION, "zstd", 0
+};
+#endif
+
 static const struct squashfs_decompressor squashfs_unknown_comp_ops = {
NULL, NULL, NULL, NULL, 0, "unknown", 0
 };
@@ -75,6 +81,7 @@ static const struct squashfs_decompressor *decompressor[] = {
_lzo_comp_ops,
_xz_comp_ops,
_lzma_unsupported_comp_ops,
+   _zstd_comp_ops,
_unknown_comp_ops
 };

diff --git a/fs/squashfs/decompressor.h b/fs/squashfs/decompressor.h
index a25713c..0f5a8e4 100644
--- a/fs/squashfs/decompressor.h
+++ b/fs/squashfs/decompressor.h
@@ -58,4 +58,8 @@ extern const struct squashfs_decompressor 
squashfs_lzo_comp_ops;
 extern const struct squashfs_decompressor squashfs_zlib_com

[PATCH v3 1/4] lib: Add xxhash module

[Nick Terrell]

Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
The zstd compression and decompression modules added in the next patch
require xxhash. I extracted it out from zstd since it is useful on its
own. I copied the code from the upstream XXHash source repository and
translated it into kernel style. I ran benchmarks and tests in the kernel
and tests in userland.

I benchmarked xxhash as a special character device. I ran in four modes,
no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to
kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute
hashes on the copied data. I also ran it with four different buffer sizes.
The benchmark file is located in the upstream zstd source repository under
`contrib/linux-kernel/xxhash_test.c` [1].

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. I benchmarked using the file `filesystem.squashfs`
from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large.
Run the following commands for the benchmark:

modprobe xxhash_test
mknod xxhash_test c 245 0
time cp filesystem.squashfs xxhash_test

The time is reported by the time of the userland `cp`.
The GB/s is computed with

1,536,217,008 B / time(buffer size, hash)

which includes the time to copy from userland.
The Normalized GB/s is computed with

1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).


| Buffer Size (B) | Hash  | Time (s) | GB/s | Adjusted GB/s |
|-|---|--|--|---|
|1024 | none  |0.408 | 3.77 | - |
|1024 | xxh32 |0.649 | 2.37 |  6.37 |
|1024 | xxh64 |0.542 | 2.83 | 11.46 |
|1024 | crc32 |1.290 | 1.19 |  1.74 |
|4096 | none  |0.380 | 4.04 | - |
|4096 | xxh32 |0.645 | 2.38 |  5.79 |
|4096 | xxh64 |0.500 | 3.07 | 12.80 |
|4096 | crc32 |1.168 | 1.32 |  1.95 |
|8192 | none  |0.351 | 4.38 | - |
|8192 | xxh32 |0.614 | 2.50 |  5.84 |
|8192 | xxh64 |0.464 | 3.31 | 13.60 |
|8192 | crc32 |1.163 | 1.32 |  1.89 |
|   16384 | none  |0.346 | 4.43 | - |
|   16384 | xxh32 |0.590 | 2.60 |  6.30 |
|   16384 | xxh64 |0.466 | 3.30 | 12.80 |
|   16384 | crc32 |1.183 | 1.30 |  1.84 |

Tested in userland using the test-suite in the zstd repo under
`contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the
kernel functions. A line in each branch of every function in `xxhash.c`
was commented out to ensure that the test-suite fails. Additionally
tested while testing zstd and with SMHasher [3].

[1] https://phabricator.intern.facebook.com/P57526246
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp
[3] https://github.com/aappleby/smhasher

zstd source repository: https://github.com/facebook/zstd
XXHash source repository: https://github.com/cyan4973/xxhash

Signed-off-by: Nick Terrell <terre...@fb.com>
---
v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const

 include/linux/xxhash.h | 236 +++
 lib/Kconfig|   3 +
 lib/Makefile   |   1 +
 lib/xxhash.c   | 500 +
 4 files changed, 740 insertions(+)
 create mode 100644 include/linux/xxhash.h
 create mode 100644 lib/xxhash.c

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000..9e1f42c
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, I

[PATCH v3 0/4] Add xxhash and zstd modules

[Nick Terrell]

Hi all,

This patch set adds xxhash, zstd compression, and zstd decompression
modules. It also adds zstd support to BtrFS and SquashFS.

Each patch has relevant summaries, benchmarks, and tests.

Best,
Nick Terrell

Changelog:

v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const (1/4)
- Use div_u64() for division of u64s (2/4)
- Reduce stack usage of ZSTD_compressSequences(), ZSTD_buildSeqTable(),
  ZSTD_decompressSequencesLong(), FSE_buildDTable(), FSE_decompress_wksp(),
  HUF_writeCTable(), HUF_readStats(), HUF_readCTable(),
  HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/4)
- No zstd function uses more than 400 B of stack space (2/4)

v2 -> v3:
- Work around gcc-7 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388
  (2/4)
- Fix bug in dictionary compression from upstream commit cc1522351f (2/4)
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff (3/4)
- Change default compression level for BtrFS to 3 (3/4)

Nick Terrell (4):
  lib: Add xxhash module
  lib: Add zstd modules
  btrfs: Add zstd support
  squashfs: Add zstd support

 fs/btrfs/Kconfig   |2 +
 fs/btrfs/Makefile  |2 +-
 fs/btrfs/compression.c |1 +
 fs/btrfs/compression.h |6 +-
 fs/btrfs/ctree.h   |1 +
 fs/btrfs/disk-io.c |2 +
 fs/btrfs/ioctl.c   |6 +-
 fs/btrfs/props.c   |6 +
 fs/btrfs/super.c   |   12 +-
 fs/btrfs/sysfs.c   |2 +
 fs/btrfs/zstd.c|  435 ++
 fs/squashfs/Kconfig|   14 +
 fs/squashfs/Makefile   |1 +
 fs/squashfs/decompressor.c |7 +
 fs/squashfs/decompressor.h |4 +
 fs/squashfs/squashfs_fs.h  |1 +
 fs/squashfs/zstd_wrapper.c |  150 ++
 include/linux/xxhash.h |  236 +++
 include/linux/zstd.h   | 1157 +++
 include/uapi/linux/btrfs.h |8 +-
 lib/Kconfig|   11 +
 lib/Makefile   |3 +
 lib/xxhash.c   |  500 +++
 lib/zstd/Makefile  |   18 +
 lib/zstd/bitstream.h   |  374 +
 lib/zstd/compress.c| 3479 
 lib/zstd/decompress.c  | 2526 
 lib/zstd/entropy_common.c  |  243 
 lib/zstd/error_private.h   |   53 +
 lib/zstd/fse.h |  575 
 lib/zstd/fse_compress.c|  795 ++
 lib/zstd/fse_decompress.c  |  332 +
 lib/zstd/huf.h |  212 +++
 lib/zstd/huf_compress.c|  770 ++
 lib/zstd/huf_decompress.c  |  960 
 lib/zstd/mem.h |  151 ++
 lib/zstd/zstd_common.c |   75 +
 lib/zstd/zstd_internal.h   |  250 
 lib/zstd/zstd_opt.h| 1014 +
 39 files changed, 14382 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c
 create mode 100644 fs/squashfs/zstd_wrapper.c
 create mode 100644 include/linux/xxhash.h
 create mode 100644 include/linux/zstd.h
 create mode 100644 lib/xxhash.c
 create mode 100644 lib/zstd/Makefile
 create mode 100644 lib/zstd/bitstream.h
 create mode 100644 lib/zstd/compress.c
 create mode 100644 lib/zstd/decompress.c
 create mode 100644 lib/zstd/entropy_common.c
 create mode 100644 lib/zstd/error_private.h
 create mode 100644 lib/zstd/fse.h
 create mode 100644 lib/zstd/fse_compress.c
 create mode 100644 lib/zstd/fse_decompress.c
 create mode 100644 lib/zstd/huf.h
 create mode 100644 lib/zstd/huf_compress.c
 create mode 100644 lib/zstd/huf_decompress.c
 create mode 100644 lib/zstd/mem.h
 create mode 100644 lib/zstd/zstd_common.c
 create mode 100644 lib/zstd/zstd_internal.h
 create mode 100644 lib/zstd/zstd_opt.h

--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/10/17, 9:57 PM, "Nick Terrell" <terre...@fb.com> wrote:
> The problem is caused by a gcc-7 bug [1]. It miscompiles
> ZSTD_wildcopy(void *dst, void const *src, ptrdiff_t len) when len is 0.
> It only happens when it can't analyze ZSTD_copy8(), which is the case in
> the kernel, because memcpy() is implemented with inline assembly. The
> generated code is slow anyways, so I propose this workaround, which will
> be included in the next patch set. I've confirmed that it fixes the bug for
> me. This alternative implementation is also 10-20x faster, and compiles to
> the same x86 assembly as the original ZSTD_wildcopy() with the userland
> memcpy() implementation [2].
>
> [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388#add_comment
> [2] https://godbolt.org/g/q5YpLx
>
> Signed-off-by: Nick Terrell <terre...@fb.com>
> ---
>  lib/zstd/zstd_internal.h | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
>
> diff --git a/lib/zstd/zstd_internal.h b/lib/zstd/zstd_internal.h
> index 6748719..ade0365 100644
> --- a/lib/zstd/zstd_internal.h
> +++ b/lib/zstd/zstd_internal.h
> @@ -126,7 +126,9 @@ static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
>  /*-***
>  *  Shared functions to include for inlining
>  */
> -static void ZSTD_copy8(void *dst, const void *src) { memcpy(dst, src, 8); }
> +static void ZSTD_copy8(void *dst, const void *src) {
> +   ZSTD_write64(dst, ZSTD_read64(src));
> +}

Sorry, my patch still triggered the gcc bug, I used the wrong compiler.
This patch works, and runs about the same speed as before the patch for
small inputs, and slightly faster for larger inputs (100+ bytes). I'll
look for a faster workaround if benchmarks show it matters.

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 lib/zstd/zstd_internal.h | 8 ++--
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/lib/zstd/zstd_internal.h b/lib/zstd/zstd_internal.h
index 6748719..839014d 100644
--- a/lib/zstd/zstd_internal.h
+++ b/lib/zstd/zstd_internal.h
@@ -139,12 +139,8 @@ static void ZSTD_copy8(void *dst, const void *src) { 
memcpy(dst, src, 8); }
 #define WILDCOPY_OVERLENGTH 8
 ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
 {
-   const BYTE *ip = (const BYTE *)src;
-   BYTE *op = (BYTE *)dst;
-   BYTE *const oend = op + length;
-   do
-   COPY8(op, ip)
-   while (op < oend);
+   if (length > 0)
+   memcpy(dst, src, length);
 }
 
 ZSTD_STATIC void ZSTD_wildcopy_e(void *dst, const void *src, void *dstEnd) /* 
should be faster for decoding, but strangely, not verified on all platform */
-- 
2.9.3



N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/10/17, 5:36 AM, "Austin S. Hemmelgarn" <ahferro...@gmail.com> wrote:
> On 2017-07-07 23:07, Adam Borowski wrote:
>> On Sat, Jul 08, 2017 at 01:40:18AM +0200, Adam Borowski wrote:
>>> On Fri, Jul 07, 2017 at 11:17:49PM +, Nick Terrell wrote:
>>>> On 7/6/17, 9:32 AM, "Adam Borowski" <kilob...@angband.pl> wrote:
>>>>> Got a reproducible crash on amd64:
>>>
>>>> Thanks for the bug report Adam! I'm looking into the failure, and haven't
>>>> been able to reproduce it yet. I've built my kernel from your tree, and
>>>> I ran your script with the kernel.tar tarball 100 times, but haven't gotten
>>>> a failure yet.
>>>
>>>> I have a few questions to guide my debugging.
>>>>
>>>> - How many cores are you running with? I’ve run the script with 1, 2, and 
>>>> 4 cores.
>>>> - Which version of gcc are you using to compile the kernel? I’m using 
>>>> gcc-6.2.0-5ubuntu12.
>>>> - Are the failures always in exactly the same place, and does it fail 100%
>>>>of the time or just regularly?
>>>
>>> 6 cores -- all on bare metal.  gcc-7.1.0-9.
>>> Lemme try with gcc-6, a different config or in a VM.
>>
>> I've tried the following:
>> * gcc-6, defconfig (+btrfs obviously)
>> * gcc-7, defconfig
>> * gcc-6, my regular config
>> * gcc-7, my regular config
>> * gcc-7, debug + UBSAN + etc
>> * gcc-7, defconfig, qemu-kvm with only 1 core
>>
>> Every build with gcc-7 reproduces the crash, every with gcc-6 does not.
>>
> Got a GCC7 tool-chain built, and I can confirm this here too, tested 
> with various numbers of cores ranging from 1-32 in a QEMU+KVM VM, with 
> various combinations of debug options and other config switches.

The problem is caused by a gcc-7 bug [1]. It miscompiles
ZSTD_wildcopy(void *dst, void const *src, ptrdiff_t len) when len is 0.
It only happens when it can't analyze ZSTD_copy8(), which is the case in
the kernel, because memcpy() is implemented with inline assembly. The
generated code is slow anyways, so I propose this workaround, which will
be included in the next patch set. I've confirmed that it fixes the bug for
me. This alternative implementation is also 10-20x faster, and compiles to
the same x86 assembly as the original ZSTD_wildcopy() with the userland
memcpy() implementation [2].

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388#add_comment
[2] https://godbolt.org/g/q5YpLx

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 lib/zstd/zstd_internal.h | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/zstd/zstd_internal.h b/lib/zstd/zstd_internal.h
index 6748719..ade0365 100644
--- a/lib/zstd/zstd_internal.h
+++ b/lib/zstd/zstd_internal.h
@@ -126,7 +126,9 @@ static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
 /*-***
 *  Shared functions to include for inlining
 */
-static void ZSTD_copy8(void *dst, const void *src) { memcpy(dst, src, 8); }
+static void ZSTD_copy8(void *dst, const void *src) {
+   ZSTD_write64(dst, ZSTD_read64(src));
+}
 #define COPY8(d, s)   \
{ \
ZSTD_copy8(d, s); \
--
2.9.3

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/10/17, 5:36 AM, "Austin S. Hemmelgarn" <ahferro...@gmail.com> wrote:
> On 2017-07-07 23:07, Adam Borowski wrote:
>> On Sat, Jul 08, 2017 at 01:40:18AM +0200, Adam Borowski wrote:
>>> On Fri, Jul 07, 2017 at 11:17:49PM +, Nick Terrell wrote:
>>>> On 7/6/17, 9:32 AM, "Adam Borowski" <kilob...@angband.pl> wrote:
>>>>> Got a reproducible crash on amd64:
>>>
>>>> Thanks for the bug report Adam! I'm looking into the failure, and haven't
>>>> been able to reproduce it yet. I've built my kernel from your tree, and
>>>> I ran your script with the kernel.tar tarball 100 times, but haven't gotten
>>>> a failure yet.
>>>
>>>> I have a few questions to guide my debugging.
>>>>
>>>> - How many cores are you running with? I’ve run the script with 1, 2, and 
>>>> 4 cores.
>>>> - Which version of gcc are you using to compile the kernel? I’m using 
>>>> gcc-6.2.0-5ubuntu12.
>>>> - Are the failures always in exactly the same place, and does it fail 100%
>>>>of the time or just regularly?
>>>
>>> 6 cores -- all on bare metal.  gcc-7.1.0-9.
>>> Lemme try with gcc-6, a different config or in a VM.
>> 
>> I've tried the following:
>> * gcc-6, defconfig (+btrfs obviously)
>> * gcc-7, defconfig
>> * gcc-6, my regular config
>> * gcc-7, my regular config
>> * gcc-7, debug + UBSAN + etc
>> * gcc-7, defconfig, qemu-kvm with only 1 core
>>
>> Every build with gcc-7 reproduces the crash, every with gcc-6 does not.
>>
> Got a GCC7 tool-chain built, and I can confirm this here too, tested 
> with various numbers of cores ranging from 1-32 in a QEMU+KVM VM, with 
> various combinations of debug options and other config switches.

I was running in an Ubuntu 16.10 VM on a MacBook Pro. I built with gcc-6.2
with KASAN, and couldn't trigger it, as expected. I built with gcc-7.1.0
built from source, and couldn't reproduce it. However, when I set up
qemu-kvm on another device, and compiled with gcc-7.1.0 built from source,
I was able to reproduce the bug. Now that I can reproduce it, I'll look
into a fix. Thanks Adam and Austin for finding, reproducing, and verifying
the bug.
 

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/6/17, 9:32 AM, "Adam Borowski" <kilob...@angband.pl> wrote:
> On Thu, Jun 29, 2017 at 12:41:07PM -0700, Nick Terrell wrote:
>> 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.
>
> Got a reproducible crash on amd64:
>
> [98235.266511] BUG: unable to handle kernel paging request at c90001251000
> [98235.267485] IP: ZSTD_storeSeq.constprop.24+0x67/0xe0
> [98235.269395] PGD 227034067 
> [98235.269397] P4D 227034067 
> [98235.271587] PUD 227035067 
> [98235.273657] PMD 223323067 
> [98235.275744] PTE 0
>
> [98235.281545] Oops: 0002 [#1] SMP
> [98235.283353] Modules linked in: loop veth tun fuse arc4 rtl8xxxu mac80211 
> cfg80211 cp210x pl2303 rfkill usbserial nouveau video mxm_wmi ttm
> [98235.285203] CPU: 0 PID: 10850 Comm: kworker/u12:9 Not tainted 4.12.0+ #1
> [98235.287070] Hardware name: System manufacturer System Product Name/M4A77T, 
> BIOS 240105/18/2011
> [98235.288964] Workqueue: btrfs-delalloc btrfs_delalloc_helper
> [98235.290934] task: 880224984140 task.stack: c90007e5c000
> [98235.292731] RIP: 0010:ZSTD_storeSeq.constprop.24+0x67/0xe0
> [98235.294579] RSP: 0018:c90007e5fa68 EFLAGS: 00010282
> [98235.296395] RAX: c90001251001 RBX: 0094 RCX: 
> c9000118f930
> [98235.298380] RDX: 0006 RSI: c900011b06b0 RDI: 
> c9000118d1e0
> [98235.300321] RBP: 009f R08: 1fffbe58 R09: 
> 
> [98235.302282] R10: c9000118f970 R11: 0005 R12: 
> c9000118f878
> [98235.304221] R13: 005b R14: c9000118f915 R15: 
> c900011cfe88
> [98235.306147] FS:  () GS:88022fc0() 
> knlGS:
> [98235.308162] CS:  0010 DS:  ES:  CR0: 80050033
> [98235.310129] CR2: c90001251000 CR3: 00021018d000 CR4: 
> 06f0
> [98235.312095] Call Trace:
> [98235.314008]  ? ZSTD_compressBlock_fast+0x94b/0xb30
> [98235.315975]  ? ZSTD_compressContinue_internal+0x1a0/0x580
> [98235.317938]  ? ZSTD_compressStream_generic+0x248/0x2f0
> [98235.319877]  ? ZSTD_compressStream+0x41/0x60
> [98235.321821]  ? zstd_compress_pages+0x236/0x5d0
> [98235.323724]  ? btrfs_compress_pages+0x5e/0x80
> [98235.325684]  ? compress_file_range.constprop.79+0x1eb/0x750
> [98235.327668]  ? async_cow_start+0x2e/0x50
> [98235.329594]  ? btrfs_worker_helper+0x1b9/0x1d0
> [98235.331486]  ? process_one_work+0x158/0x2f0
> [98235.61]  ? worker_thread+0x45/0x3a0
> [98235.335253]  ? process_one_work+0x2f0/0x2f0
> [98235.337189]  ? kthread+0x10e/0x130
> [98235.339020]  ? kthread_park+0x60/0x60
> [98235.340819]  ? ret_from_fork+0x22/0x30
> [98235.342637] Code: 8b 4e d0 4c 89 48 d0 4c 8b 4e d8 4c 89 48 d8 4c 8b 4e e0 
> 4c 89 48 e0 4c 8b 4e e8 4c 89 48 e8 4c 8b 4e f0 4c 89 48 f0 4c 8b 4e f8 <4c> 
> 89 48 f8 48 39 f1 75 a2 4e 8d 04 c0 48 8b 31 48 83 c0 08 48 
> [98235.346773] RIP: ZSTD_storeSeq.constprop.24+0x67/0xe0 RSP: c90007e5fa68
> [98235.348809] CR2: c90001251000
> [98235.363216] ---[ end trace 5fb3ad0f2aec0605 ]---
> [98235.363218] BUG: unable to handle kernel paging request at c9000393a000
> [98235.363239] IP: ZSTD_storeSeq.constprop.24+0x67/0xe0
> [98235.363241] PGD 227034067 
> [98235.363242] P4D 227034067 
> [98235.363243] PUD 227035067 
> [98235.363244] PMD 21edec067 
> [98235.363245] PTE 0
> (More of the above follows.)
>
> My reproducer copies an uncompressed tarball onto a fresh filesystem:
> .
> #!/bin/sh
> set -e
>
> losetup -D; umount /mnt/vol1 ||:
> dd if=/dev/zero of=/tmp/disk bs=2048 seek=1048575 count=1
> mkfs.btrfs -msingle /tmp/disk
> losetup -f /tmp/disk
> sleep 1 # yay udev races
> mount -onoatime,compress=$1 /dev/loop0 /mnt/vol1
> time sh -c 'cp -p ~kilobyte/tmp/kernel.tar /mnt/vol1 && umount /mnt/vol1'
> losetup -D
> `
> (run it with arg of "zstd")
>
> Kernel is 4.12.0 + btrfs-for-4.13 + v4 of Qu's chunk check + some unrelated
> stuff + zstd; in case it matters I've pushed my tree to
> https://github.com/kilobyte/linux/tree/zstd-crash
>
> The payload is a tarball of the above, but, for debugging compression you
> need the exact byte stream.  https://angband.pl/tmp/kernel.tar.xz  --
> without xz, I compressed it for transport.

Thanks for the bug report Adam! I'm looking into the failure, and haven't
been able to reproduce it yet. I've built my kernel from your tree, and
I ran your script with the kernel.tar tarball 100 times, but haven't gotten
a failure yet. I have a few questions to guide my debugging.

- How many cores are you running with? I’ve run the script with 1, 2, and 4 
cores.
- Which version of gcc are you using to compile the kernel? I’m using 
gcc-6.2.0-5ubuntu12.
- Are the failures always in exactly the same place, and does it fail 100%
  of the time or just regularly?

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/5/17, 12:57 PM, "Austin S. Hemmelgarn"  wrote:
> It's the slower compression speed that has me arguing for the 
> possibility of configurable levels on zlib.  11MB/s is painfully slow 
> considering that most decent HDD's these days can get almost 5-10x that 
> speed with no compression.  There are cases (WORM pattern archival 
> storage for example) where slow writes to that degree may be acceptable, 
> but for most users they won't be, and zlib at level 9 would probably be 
> a better choice.  I don't think it can beat zstd at level 15 for 
> compression ratio, but if they're even close, then zlib would still be a 
> better option at that high of a compression level most of the time.

I don't imagine the very high zstd levels would be useful to too many
btrfs users, except in rare cases. However, lower levels of zstd should
outperform zlib level 9 in all aspects except memory usage. I would expect
zstd level 7 would compress as well as or better than zlib 9 with faster
compression and decompression speed. It's worth benchmarking to ensure that
it holds for many different workloads, but I wouldn't expect zlib 9 to
compress better than zstd 7 often. zstd up to level 12 should compress as
fast as or faster than zlib level 9. zstd levels 12 and beyond allow
stronger compression than zlib, at the cost of slow compression and more
memory usage. 

Supporting multiple zlib compression levels could be intersting for older
kernels, lower memory usage, or backwards compatibility with older btrfs
versions. But for every zlib level, zstd has a level that provides better
compression ratio, compression speed, and decompression speed.

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

On 7/5/17, 11:45 AM, "Austin S. Hemmelgarn" <ahferro...@gmail.com> wrote:
>On 2017-07-05 14:18, Adam Borowski wrote:
>> On Wed, Jul 05, 2017 at 07:43:27AM -0400, Austin S. Hemmelgarn
>> wrote:
>>> On 2017-06-30 19:01, Nick Terrell wrote:
>>>>> There is also the fact of deciding what to use for the default
>>>>> when specified without a level.  This is easy for lzo and zlib,
>>>>> where we can just use the existing level, but for zstd we would
>>>>> need to decide how to handle a user just specifying 'zstd'
>>>>> without a level.  I agree with E V that level 3 appears to be
>>>>> the turnover point, and would suggest using that for the
>>>>> default.
>>>> 
>>>> I chose level 1 because I thought if we had to choose one
>>>> speed/compression trade off, faster would be better. However,
>>>> with a configerable compression level, level 3 is a great
>>>> default, and is the default of the zstd CLI.
>>> Actually, even if it's not configurable, I would prefer 3, as that
>>> still performs better in both respects (speed and compression
>>> ratio) than zlib while being sufficiently different from lzo
>>> performance to make it easy to decide on one or the other.  As far
>>> as configurable levels for regular usage on a filesystem, there are
>>> only three levels you benchmarked that I would be interested in,
>>> namely level 1 (highly active data on slow storage with a fast
>>> CPU), 3 (stuff I would use zlib for today), and 15 (stuff I would
>>> use out-of-band compression for today (for example, archival
>>> storage)).
>> 
>> If you guys are going to argue between 1 and 3, just go the cracovian
>> deal and settle at 2. :þ

I'll change the default to level 3 in the next update.

>> 
>> But more seriously: zstd looks so much better than lzo and zlib than
>> I'd suggest making it the default compression in cases where there's
>> no way to choose, such as chattr +c.  But then, changing the default
>> before the previous LTS kernel can mount it would be irresponsible --
>> thus, if you can get it into 4.14, we're looking at 4.19 at soonest
>> (or later if we consider distro kernels).
> To be entirely honest, we probably should have switched to LZO as the
> default a while back to put things more in-line with ZFS (which
> traditionally favors performance for in-line compression) and Windows
> (which uses a custom LZ77 derivative that's wicked fast on most modern
> systems).  I would say that as soon as we get to the point that the last 
> two LTS releases support it, zstd should probably become the default.
>
> Also, slightly OT, but I would love to have the ability to set per 
> volume (not subvolume but volume itself) what to use for compression 
> when no algorithm is specified.
>> 
>> Which means the timing is quite tight: if, per DSterba's request,
>> /lib/ parts are going via a non-btrfs tree, there'll be not enough
>> adequate testing in -next.  Thus, would it be possible to have /lib/
>> patches in btrfs-next but not in for-linus?  That would allow testing
>> so you can catch the LTS train.
>> 
>>>>>> So, I don't see any problem making the level configurable.
>>>>> I would actually love to see this, I regularly make use of
>>>>> varying compression both on BTRFS (with separate filesystems)
>>>>> and on the ZFS-based NAS systems we have at work (where it can
>>>>> be set per-dataset) to allow better compression on less
>>>>> frequently accessed data.
>>>> 
>>>> I would love to see configurable compression level as well. Would
>>>> you want me to add it to my patch set, or should I adapt my patch
>>>> set to work on top of it when it is ready?
>> 
>> Note that as zstd is new, there's no backwards compat to care of,
>> thus you are free to use whatever -o/prop syntax you'd like.  If zstd
>> ends up being configurable while zlib is not -- oh well, there's no
>> reason to use zlib anymore other than for mounting with old kernels,
>> in which case we can't use configurable props anyway.  Unlike zlib,
>> lzo is not strictly worse than configurable zstd, but it has only one
>> level so there's nothing to configure as well.
>> 
>> Thus, I'd suggest skipping the issue and implement levels for zstd
>> only.
> I would mostly agree, with one possible exception.  _If_ zlib at the max
> level gets similar compression ratios to zstd on it's higher levels
> _and_ it also gets better perform

Re: [PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

>> If we're going to make that configurable, there are some things to
>> consider:
>> 
>> * the underlying compressed format -- does not change for different
>>levels

This is true for zlib and zstd. lzo in the kernel only supports one
compression level.

>> * the configuration interface -- mount options, defrag ioctl
>> 
>> * backward compatibility
> There is also the fact of deciding what to use for the default when 
> specified without a level.  This is easy for lzo and zlib, where we can 
> just use the existing level, but for zstd we would need to decide how to 
> handle a user just specifying 'zstd' without a level.  I agree with E V 
> that level 3 appears to be the turnover point, and would suggest using 
> that for the default.

I chose level 1 because I thought if we had to choose one speed/compression
trade off, faster would be better. However, with a configerable compression
level, level 3 is a great default, and is the default of the zstd CLI.

>> So, I don't see any problem making the level configurable.
> I would actually love to see this, I regularly make use of varying 
> compression both on BTRFS (with separate filesystems) and on the 
> ZFS-based NAS systems we have at work (where it can be set per-dataset) 
> to allow better compression on less frequently accessed data.

I would love to see configurable compression level as well. Would you want
me to add it to my patch set, or should I adapt my patch set to work on top
of it when it is ready?

Re: [PATCH v2 0/4] Add xxhash and zstd modules

[Nick Terrell]

> If i understood all correctly,
> zstd can compress (decompress) data in way compatible with gzip (zlib)
> Do that also true for in kernel library?

The zstd command line tool can decompress gzip/zlib compressed data, and
can compress in the gzip format. However, the zstd format is not compatible
with zlib, so gzip/zlib cannot decompress zstd compressed data. The zstd
kernel module can only compress and decompress the zstd format, and can't
decompress zlib/gzip compressed data.

[PATCH v2 4/4] squashfs: Add zstd support

[Nick Terrell]

Add zstd compression and decompression support to SquashFS. zstd is a
great fit for SquashFS because it can compress at ratios approaching xz,
while decompressing twice as fast as zlib. For SquashFS in particular,
it can decompress as fast as lzo and lz4. It also has the flexibility
to turn down the compression ratio for faster compression times.

The compression benchmark is run on the file tree from the SquashFS archive
found in ubuntu-16.10-desktop-amd64.iso [1]. It uses `mksquashfs` with the
default block size (128 KB) and and various compression algorithms/levels.
xz and zstd are also benchmarked with 256 KB blocks. The decompression
benchmark times how long it takes to `tar` the file tree into `/dev/null`.
See the benchmark file in the upstream zstd source repository located under
`contrib/linux-kernel/squashfs-benchmark.sh` [2] for details.

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.

| Method | Ratio | Compression MB/s | Decompression MB/s |
||---|--||
| gzip   |  2.92 |   15 |128 |
| lzo|  2.64 |  9.5 |217 |
| lz4|  2.12 |   94 |218 |
| xz |  3.43 |  5.5 | 35 |
| xz 256 KB  |  3.53 |  5.4 | 40 |
| zstd 1 |  2.71 |   96 |210 |
| zstd 5 |  2.93 |   69 |198 |
| zstd 10|  3.01 |   41 |225 |
| zstd 15|  3.13 | 11.4 |224 |
| zstd 16 256 KB |  3.24 |  8.1 |210 |

This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
taking over the submission process.

[1] http://releases.ubuntu.com/16.10/
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh

zstd source repository: https://github.com/facebook/zstd

Cc: Sean Purcell <m...@seanp.xyz>
Signed-off-by: Nick Terrell <terre...@fb.com>
---
 fs/squashfs/Kconfig|  14 +
 fs/squashfs/Makefile   |   1 +
 fs/squashfs/decompressor.c |   7 +++
 fs/squashfs/decompressor.h |   4 ++
 fs/squashfs/squashfs_fs.h  |   1 +
 fs/squashfs/zstd_wrapper.c | 150 +
 6 files changed, 177 insertions(+)
 create mode 100644 fs/squashfs/zstd_wrapper.c

diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
index ffb093e..1adb334 100644
--- a/fs/squashfs/Kconfig
+++ b/fs/squashfs/Kconfig
@@ -165,6 +165,20 @@ config SQUASHFS_XZ

  If unsure, say N.

+config SQUASHFS_ZSTD
+   bool "Include support for ZSTD compressed file systems"
+   depends on SQUASHFS
+   select ZSTD_DECOMPRESS
+   help
+ Saying Y here includes support for reading Squashfs file systems
+ compressed with ZSTD compression.  ZSTD gives better compression than
+ the default ZLIB compression, while using less CPU.
+
+ ZSTD is not the standard compression used in Squashfs and so most
+ file systems will be readable without selecting this option.
+
+ If unsure, say N.
+
 config SQUASHFS_4K_DEVBLK_SIZE
bool "Use 4K device block size?"
depends on SQUASHFS
diff --git a/fs/squashfs/Makefile b/fs/squashfs/Makefile
index 246a6f3..6655631 100644
--- a/fs/squashfs/Makefile
+++ b/fs/squashfs/Makefile
@@ -15,3 +15,4 @@ squashfs-$(CONFIG_SQUASHFS_LZ4) += lz4_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_LZO) += lzo_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_XZ) += xz_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_ZLIB) += zlib_wrapper.o
+squashfs-$(CONFIG_SQUASHFS_ZSTD) += zstd_wrapper.o
diff --git a/fs/squashfs/decompressor.c b/fs/squashfs/decompressor.c
index d2bc136..8366398 100644
--- a/fs/squashfs/decompressor.c
+++ b/fs/squashfs/decompressor.c
@@ -65,6 +65,12 @@ static const struct squashfs_decompressor 
squashfs_zlib_comp_ops = {
 };
 #endif

+#ifndef CONFIG_SQUASHFS_ZSTD
+static const struct squashfs_decompressor squashfs_zstd_comp_ops = {
+   NULL, NULL, NULL, NULL, ZSTD_COMPRESSION, "zstd", 0
+};
+#endif
+
 static const struct squashfs_decompressor squashfs_unknown_comp_ops = {
NULL, NULL, NULL, NULL, 0, "unknown", 0
 };
@@ -75,6 +81,7 @@ static const struct squashfs_decompressor *decompressor[] = {
_lzo_comp_ops,
_xz_comp_ops,
_lzma_unsupported_comp_ops,
+   _zstd_comp_ops,
_unknown_comp_ops
 };

diff --git a/fs/squashfs/decompressor.h b/fs/squashfs/decompressor.h
index a25713c..0f5a8e4 100644
--- a/fs/squashfs/decompressor.h
+++ b/fs/squashfs/decompressor.h
@@ -58,4 +58,8 @@ extern const struct squashfs_decompressor 
squashfs_lzo_comp_ops;
 extern const struct squashfs_decompressor squashfs_zlib_com

[PATCH v2 3/4] btrfs: Add zstd support

[Nick Terrell]

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 <terre...@fb.com>
---
 fs/btrfs/Kconfig   |   2 +
 fs/btrfs/Makefile  |   2 +-
 fs/btrfs/compression.c |   1 +
 fs/btrfs/compression.h |   6 +-
 fs/btrfs/ctree.h   |   1 +
 fs/btrfs/disk-io.c |   2 +
 fs/btrfs/ioctl.c   |   6 +-
 fs/btrfs/props.c   |   6 +
 fs/btrfs/super.c   |  12 +-
 fs/btrfs/sysfs.c   |   2 +
 fs/btrfs/zstd.c| 433 +
 include/uapi/linux/btrfs.h |   8 +-
 12 files changed, 469 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18..a26c63b 100644
--- a/fs/btrfs/Kconfig
+++ b/fs/btrfs/Kconfig
@@ -6,6 +6,8 @@ config BTRFS_FS
select ZLIB_DEFLATE
select LZO_COMPRESS
select LZO_DECOMPRESS
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
select RAID6_PQ
select XOR_BLOCKS
select SRCU
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 128ce17..962a95a 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o 
root-tree.o dir-item.o \
   transaction.o inode.o file.o tree-defrag.o \
   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
-  export.o tree-log.o free-space-cache.o zlib.o lzo.o \
+  export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
   compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o \
   reada.o backref.o ulist.o qgroup.o send.o dev-replace.o raid56.o \
   uuid-tree.o props.o hash.o free-space-tree.o
diff --git a/fs/btrfs/compressi

[PATCH v2 1/4] lib: Add xxhash module

[Nick Terrell]

Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
The zstd compression and decompression modules added in the next patch
require xxhash. I extracted it out from zstd since it is useful on its
own. I copied the code from the upstream XXHash source repository and
translated it into kernel style. I ran benchmarks and tests in the kernel
and tests in userland.

I benchmarked xxhash as a special character device. I ran in four modes,
no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to
kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute
hashes on the copied data. I also ran it with four different buffer sizes.
The benchmark file is located in the upstream zstd source repository under
`contrib/linux-kernel/xxhash_test.c` [1].

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. I benchmarked using the file `filesystem.squashfs`
from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large.
Run the following commands for the benchmark:

modprobe xxhash_test
mknod xxhash_test c 245 0
time cp filesystem.squashfs xxhash_test

The time is reported by the time of the userland `cp`.
The GB/s is computed with

1,536,217,008 B / time(buffer size, hash)

which includes the time to copy from userland.
The Normalized GB/s is computed with

1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).


| Buffer Size (B) | Hash  | Time (s) | GB/s | Adjusted GB/s |
|-|---|--|--|---|
|1024 | none  |0.408 | 3.77 | - |
|1024 | xxh32 |0.649 | 2.37 |  6.37 |
|1024 | xxh64 |0.542 | 2.83 | 11.46 |
|1024 | crc32 |1.290 | 1.19 |  1.74 |
|4096 | none  |0.380 | 4.04 | - |
|4096 | xxh32 |0.645 | 2.38 |  5.79 |
|4096 | xxh64 |0.500 | 3.07 | 12.80 |
|4096 | crc32 |1.168 | 1.32 |  1.95 |
|8192 | none  |0.351 | 4.38 | - |
|8192 | xxh32 |0.614 | 2.50 |  5.84 |
|8192 | xxh64 |0.464 | 3.31 | 13.60 |
|8192 | crc32 |1.163 | 1.32 |  1.89 |
|   16384 | none  |0.346 | 4.43 | - |
|   16384 | xxh32 |0.590 | 2.60 |  6.30 |
|   16384 | xxh64 |0.466 | 3.30 | 12.80 |
|   16384 | crc32 |1.183 | 1.30 |  1.84 |

Tested in userland using the test-suite in the zstd repo under
`contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the
kernel functions. A line in each branch of every function in `xxhash.c`
was commented out to ensure that the test-suite fails. Additionally
tested while testing zstd and with SMHasher [3].

[1] https://phabricator.intern.facebook.com/P57526246
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp
[3] https://github.com/aappleby/smhasher

zstd source repository: https://github.com/facebook/zstd
XXHash source repository: https://github.com/cyan4973/xxhash

Signed-off-by: Nick Terrell <terre...@fb.com>
---
v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const

 include/linux/xxhash.h | 236 +++
 lib/Kconfig|   3 +
 lib/Makefile   |   1 +
 lib/xxhash.c   | 500 +
 4 files changed, 740 insertions(+)
 create mode 100644 include/linux/xxhash.h
 create mode 100644 lib/xxhash.c

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000..9e1f42c
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, I

[PATCH v2 0/4] Add xxhash and zstd modules

[Nick Terrell]

Hi all,

This patch set adds xxhash, zstd compression, and zstd decompression
modules. It also adds zstd support to BtrFS and SquashFS.

Each patch has relevant summaries, benchmarks, and tests.

Best,
Nick Terrell

Changelog:

v1 -> v2:
- Make pointer in lib/xxhash.c:394 non-const (1/4)
- Use div_u64() for division of u64s (2/4)
- Reduce stack usage of ZSTD_compressSequences(), ZSTD_buildSeqTable(),
  ZSTD_decompressSequencesLong(), FSE_buildDTable(), FSE_decompress_wksp(),
  HUF_writeCTable(), HUF_readStats(), HUF_readCTable(),
  HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/4)
- No zstd function uses more than 400 B of stack space (2/4)

Nick Terrell (4):
  lib: Add xxhash module
  lib: Add zstd modules
  btrfs: Add zstd support
  squashfs: Add zstd support

 fs/btrfs/Kconfig   |2 +
 fs/btrfs/Makefile  |2 +-
 fs/btrfs/compression.c |1 +
 fs/btrfs/compression.h |6 +-
 fs/btrfs/ctree.h   |1 +
 fs/btrfs/disk-io.c |2 +
 fs/btrfs/ioctl.c   |6 +-
 fs/btrfs/props.c   |6 +
 fs/btrfs/super.c   |   12 +-
 fs/btrfs/sysfs.c   |2 +
 fs/btrfs/zstd.c|  433 ++
 fs/squashfs/Kconfig|   14 +
 fs/squashfs/Makefile   |1 +
 fs/squashfs/decompressor.c |7 +
 fs/squashfs/decompressor.h |4 +
 fs/squashfs/squashfs_fs.h  |1 +
 fs/squashfs/zstd_wrapper.c |  150 ++
 include/linux/xxhash.h |  236 +++
 include/linux/zstd.h   | 1157 +++
 include/uapi/linux/btrfs.h |8 +-
 lib/Kconfig|   11 +
 lib/Makefile   |3 +
 lib/xxhash.c   |  500 +++
 lib/zstd/Makefile  |   18 +
 lib/zstd/bitstream.h   |  374 +
 lib/zstd/compress.c| 3479 
 lib/zstd/decompress.c  | 2526 
 lib/zstd/entropy_common.c  |  243 
 lib/zstd/error_private.h   |   53 +
 lib/zstd/fse.h |  575 
 lib/zstd/fse_compress.c|  795 ++
 lib/zstd/fse_decompress.c  |  332 +
 lib/zstd/huf.h |  212 +++
 lib/zstd/huf_compress.c|  771 ++
 lib/zstd/huf_decompress.c  |  960 
 lib/zstd/mem.h |  151 ++
 lib/zstd/zstd_common.c |   75 +
 lib/zstd/zstd_internal.h   |  269 
 lib/zstd/zstd_opt.h| 1014 +
 39 files changed, 14400 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c
 create mode 100644 fs/squashfs/zstd_wrapper.c
 create mode 100644 include/linux/xxhash.h
 create mode 100644 include/linux/zstd.h
 create mode 100644 lib/xxhash.c
 create mode 100644 lib/zstd/Makefile
 create mode 100644 lib/zstd/bitstream.h
 create mode 100644 lib/zstd/compress.c
 create mode 100644 lib/zstd/decompress.c
 create mode 100644 lib/zstd/entropy_common.c
 create mode 100644 lib/zstd/error_private.h
 create mode 100644 lib/zstd/fse.h
 create mode 100644 lib/zstd/fse_compress.c
 create mode 100644 lib/zstd/fse_decompress.c
 create mode 100644 lib/zstd/huf.h
 create mode 100644 lib/zstd/huf_compress.c
 create mode 100644 lib/zstd/huf_decompress.c
 create mode 100644 lib/zstd/mem.h
 create mode 100644 lib/zstd/zstd_common.c
 create mode 100644 lib/zstd/zstd_internal.h
 create mode 100644 lib/zstd/zstd_opt.h

--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH] btrfs: Keep one more workspace around

[Nick Terrell]

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 <terre...@fb.com>
---
 fs/btrfs/compression.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
index 3beb0d0..1a0ef55 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -874,7 +874,7 @@ static void free_workspace(int type, struct list_head 
*workspace)
int *free_ws= _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);
--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH] btrfs: Keep one more workspace around

[Nick Terrell]

> Is there a version I should be testing?

Not yet, I'm working on v2 of the patch set, which will be ready soon.

> I got a bunch of those:
> [10170.448783] kworker/u8:6: page allocation stalls for 60720ms, order:0, 
> mode:0x14000c2(GFP_KERNEL|__GFP_HIGHMEM), nodemask=(null)
> [10170.448819] kworker/u8:6 cpuset=/ mems_allowed=0
> [10170.448842] CPU: 3 PID: 13430 Comm: kworker/u8:6 Not tainted 
> 4.12.0-rc7-00034-gdff47ed160bb #1
> [10170.448846] Hardware name: SAMSUNG EXYNOS (Flattened Device Tree)
> [10170.448872] Workqueue: btrfs-endio btrfs_endio_helper
> [10170.448910] [] (unwind_backtrace) from [] 
> (show_stack+0x10/0x14)
> [10170.448925] [] (show_stack) from [] 
> (dump_stack+0x78/0x8c)
> [10170.448942] [] (dump_stack) from [] 
> (warn_alloc+0xc0/0x170)
> [10170.448952] [] (warn_alloc) from [] 
> (__alloc_pages_nodemask+0x97c/0xe30)
> [10170.448964] [] (__alloc_pages_nodemask) from [] 
> (__vmalloc_node_range+0x144/0x27c)
> [10170.448976] [] (__vmalloc_node_range) from [] 
> (__vmalloc_node.constprop.10+0x48/0x50)
> [10170.448982] [] (__vmalloc_node.constprop.10) from [] 
> (vmalloc+0x2c/0x34)
> [10170.448990] [] (vmalloc) from [] 
> (zstd_alloc_workspace+0x6c/0xb8)
> [10170.448997] [] (zstd_alloc_workspace) from [] 
> (find_workspace+0x120/0x1f4)
> [10170.449002] [] (find_workspace) from [] 
> (end_compressed_bio_read+0x1d4/0x3b0)
> [10170.449016] [] (end_compressed_bio_read) from [] 
> (process_one_work+0x1d8/0x3f0)
> [10170.449026] [] (process_one_work) from [] 
> (worker_thread+0x38/0x558)
> [10170.449035] [] (worker_thread) from [] 
> (kthread+0x124/0x154)
> [10170.449042] [] (kthread) from [] 
> (ret_from_fork+0x14/0x3c)
>
> which never happened with compress=lzo, and a 2GB RAM machine that runs 4
> threads of various builds runs into memory pressure quite often.  On the
> other hand, I used 4.11 for lzo so this needs more testing before I can
> blame the zstd code.

I'm not sure what is causing the symptom of stalls in vmalloc(), but I
think I know what is causing vmalloc() to be called so often. Its probably
showing up for zstd and not lzo because it requires more memory.

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.

> I'm on linus:4.12-rc7 with only a handful of btrfs patches (v3 of Qu's chunk
> check, some misc crap) -- I guess I should use at least btrfs-for-4.13.  Or
> would you prefer full-blown next?

Whatever is convenient for you. The relevant code in BtrFS hasn't changed
for a few months, so it shouldn't matter too much.

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 fs/btrfs/compression.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
index 3beb0d0..1a0ef55 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -874,7 +874,7 @@ static void free_workspace(int type, struct list_head 
*workspace)
int *free_ws= _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);
--
2.9.3
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] lib/zstd: use div_u64() to let it build on 32-bit

[Nick Terrell]

> Please don't top post.

Sorry about that.

> Which function needs 1KB of stack space? That's quite a lot.

FSE_buildCTable_wksp(), FSE_compress_wksp(), and HUF_readDTableX4()
required over 1 KB of stack space.

> I can see in [1] that there are some on-stack buffers replaced by
> pointers to the workspace. That's good, but I would like to know if
> there's any hidden gem that grags the precious stack space.

I've been hunting down functions that use up the most stack trace and
replacing buffers with pointers to the workspace. I compiled the code
with -Wframe-larger-than=512 and reduced the stack usage of all offending
functions. In the next version of the patch, no function uses more than
400 B of stack space. We'll be porting the changes back upstream as well.

> Hm, I'd suggest to create a version optimized for kernel, eg. expecting
> that 4+ GB buffer will never be used and you can use the most fittin in
> type. This should affect only the function signatures, not the
> algorithm implementation, so porting future zstd changes should be
> straightforward.

If the functions were exposed, then I would agree 100%. However, since
these are internal functions, and the rest of zstd uses size_t to represent
buffer sizes, I think it would be awkward to change just FSE/HUF functions.
I also prefer size_t because it is friendlier to the optimizer, especially
the loop optimizer, since the compiler doesn't have to worry about unsigned
overflow.

On a related note, zstd performs automatic optimizations to improve
compression speed and reduce memory usage when given small sources, which
is the common case in the kernel.


N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

Re: [PATCH] lib/zstd: use div_u64() to let it build on 32-bit

[Nick Terrell]

Adam, I’ve applied the same patch in my tree. I’ll send out the update [1]
once it's reviewed, since I also reduced the stack usage of functions
using over 1 KB of stack space.

You’re right that div_u64() will work, since the FSE functions are only
called on blocks of at most 128 KB at a time. Perhaps a u32 would be
clearer, but I would prefer to leave the signatures as is, to stay closer
to upstream. Upstream FSE should work with sizes larger than 4 GB, but
since it can't happen in zstd, it isn't a priority.

I have userland tests set up mocking the linux kernel headers, and tested
32-bit mode there, but neglected to test the kernel on a 32-bit VM, which
I’ve now corrected. Thanks for testing the patch on your ARM machine!

[1] https://github.com/facebook/zstd/pull/738/files

On 6/26/17, 9:18 PM, "Adam Borowski"  wrote:

David Sterba wrote:
> > Thus, you want do_div() instead of /; do check widths and signedness of
> > arguments.
>
> No do_div please, div_u64 or div64_u64.

Good to know, the interface of do_div() is indeed weird.

I guess Nick has found and fixed the offending divisions in his tree
already, but this patch I'm sending is what I'm testing.

One thing to note is that it divides u64 by size_t, so the actual operation
differs on 32 vs 64-bit.  Yet the code fails to handle compressing pieces
bigger than 4GB in other places -- so use of size_t is misleading.  Perhaps
u32 would better convey this limitation?

Anyway, that this code didn't even compile on 32-bit also means it hasn't
been tested.  I just happen to have such an ARM machine doing Debian archive
rebuilds; I've rewritten the chroots with compress=zstd; this should be a
nice non-artificial test.  The load consists of snapshot+dpkg+gcc/etc+
assorted testsuites, two sbuild instances.  Seems to work fine for a whole
hour (yay!) already, let's see if there'll be any explosions.


-- >8  >8  >8  >8  >8  >8  >8  >8  >8 --
Note that "total" is limited to 2³²-1 elsewhere despite being declared
as size_t, so it's ok to use 64/32 -- it's much faster on eg. x86-32
than 64/64.

Signed-off-by: Adam Borowski 
---
 lib/zstd/fse_compress.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/zstd/fse_compress.c b/lib/zstd/fse_compress.c
index e016bb177833..f59f9ebfe9c0 100644
--- a/lib/zstd/fse_compress.c
+++ b/lib/zstd/fse_compress.c
@@ -49,6 +49,7 @@
 #include "fse.h"
 #include 
 #include  /* memcpy, memset */
+#include 
 
 /* **
 *  Error Management
@@ -575,7 +576,7 @@ static size_t FSE_normalizeM2(short *norm, U32 
tableLog, const unsigned *count,
{
U64 const vStepLog = 62 - tableLog;
U64 const mid = (1ULL << (vStepLog - 1)) - 1;
-   U64 const rStep = U64)1 << vStepLog) * ToDistribute) + mid) 
/ total; /* scale on remaining */
+   U64 const rStep = div_u64U64)1 << vStepLog) * ToDistribute) 
+ mid, total); /* scale on remaining */
U64 tmpTotal = mid;
for (s = 0; s <= maxSymbolValue; s++) {
if (norm[s] == NOT_YET_ASSIGNED) {
@@ -609,7 +610,7 @@ size_t FSE_normalizeCount(short *normalizedCounter, 
unsigned tableLog, const uns
{
U32 const rtbTable[] = {0, 473195, 504333, 520860, 55, 
70, 75, 83};
U64 const scale = 62 - tableLog;
-   U64 const step = ((U64)1 << 62) / total; /* <== here, one 
division ! */
+   U64 const step = div_u64((U64)1 << 62, total); /* <== here, one 
division ! */
U64 const vStep = 1ULL << (scale - 20);
int stillToDistribute = 1 << tableLog;
unsigned s;
-- 
2.13.1

Re: [PATCH 3/4] btrfs: Add zstd support

[Nick Terrell]

Thanks for the clarification! I will fix the divisions.

On 6/26/17, 5:12 AM, "David Sterba" <dste...@suse.cz> wrote:

On Sun, Jun 25, 2017 at 11:30:22PM +0200, Adam Borowski wrote:
> On Mon, Jun 26, 2017 at 03:03:17AM +0800, kbuild test robot wrote:
> > Hi Nick,
> > 
> > url:
https://github.com/0day-ci/linux/commits/Nick-Terrell/lib-Add-xxhash-module/20170625-214344
> > config: i386-allmodconfig (attached as .config)
> > compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
> > reproduce:
> > # save the attached .config to linux build tree
> > make ARCH=i386 
> > 
> > All errors (new ones prefixed by >>):
> > 
> > >> ERROR: "__udivdi3" [lib/zstd/zstd_compress.ko] undefined!
> >ERROR: "__udivdi3" [fs/ufs/ufs.ko] undefined!
> 
> Just to save you time to figure it out:
> for division when one or both arguments are longer than the architecture's
> word, gcc uses helper functions that are included when compiling in a 
hosted
> environment -- but not in freestanding.
> 
> Thus, you want do_div() instead of /; do check widths and signedness of
> arguments.

No do_div please, div_u64 or div64_u64.



N�r��yb�X��ǧv�^�)޺{.n�+{�n�߲)w*jg����ݢj/���z�ޖ��2�ޙ&�)ߡ�a�����G���h��j:+v���w��٥

[PATCH 3/4] btrfs: Add zstd support

[Nick Terrell]

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 <terre...@fb.com>
---
 fs/btrfs/Kconfig   |   2 +
 fs/btrfs/Makefile  |   2 +-
 fs/btrfs/compression.c |   1 +
 fs/btrfs/compression.h |   6 +-
 fs/btrfs/ctree.h   |   1 +
 fs/btrfs/disk-io.c |   2 +
 fs/btrfs/ioctl.c   |   6 +-
 fs/btrfs/props.c   |   6 +
 fs/btrfs/super.c   |  12 +-
 fs/btrfs/sysfs.c   |   2 +
 fs/btrfs/zstd.c| 433 +
 include/uapi/linux/btrfs.h |   8 +-
 12 files changed, 469 insertions(+), 12 deletions(-)
 create mode 100644 fs/btrfs/zstd.c

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18..a26c63b 100644
--- a/fs/btrfs/Kconfig
+++ b/fs/btrfs/Kconfig
@@ -6,6 +6,8 @@ config BTRFS_FS
select ZLIB_DEFLATE
select LZO_COMPRESS
select LZO_DECOMPRESS
+   select ZSTD_COMPRESS
+   select ZSTD_DECOMPRESS
select RAID6_PQ
select XOR_BLOCKS
select SRCU
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 128ce17..962a95a 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -6,7 +6,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o 
root-tree.o dir-item.o \
   transaction.o inode.o file.o tree-defrag.o \
   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
-  export.o tree-log.o free-space-cache.o zlib.o lzo.o \
+  export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
   compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o \
   reada.o backref.o ulist.o qgroup.o send.o dev-replace.o raid56.o \
   uuid-tree.o props.o hash.o free-space-tree.o
diff --git a/fs/btrfs/compressi

[PATCH 4/4] squashfs: Add zstd support

[Nick Terrell]

Add zstd compression and decompression support to SquashFS. zstd is a
great fit for SquashFS because it can compress at ratios approaching xz,
while decompressing twice as fast as zlib. For SquashFS in particular,
it can decompress as fast as lzo and lz4. It also has the flexibility
to turn down the compression ratio for faster compression times.

The compression benchmark is run on the file tree from the SquashFS archive
found in ubuntu-16.10-desktop-amd64.iso [1]. It uses `mksquashfs` with the
default block size (128 KB) and and various compression algorithms/levels.
xz and zstd are also benchmarked with 256 KB blocks. The decompression
benchmark times how long it takes to `tar` the file tree into `/dev/null`.
See the benchmark file in the upstream zstd source repository located under
`contrib/linux-kernel/squashfs-benchmark.sh` [2] for details.

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.

| Method | Ratio | Compression MB/s | Decompression MB/s |
||---|--||
| gzip   |  2.92 |   15 |128 |
| lzo|  2.64 |  9.5 |217 |
| lz4|  2.12 |   94 |218 |
| xz |  3.43 |  5.5 | 35 |
| xz 256 KB  |  3.53 |  5.4 | 40 |
| zstd 1 |  2.71 |   96 |210 |
| zstd 5 |  2.93 |   69 |198 |
| zstd 10|  3.01 |   41 |225 |
| zstd 15|  3.13 | 11.4 |224 |
| zstd 16 256 KB |  3.24 |  8.1 |210 |

This patch was written by Sean Purcell <m...@seanp.xyz>, but I will be
taking over the submission process.

[1] http://releases.ubuntu.com/16.10/
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh

zstd source repository: https://github.com/facebook/zstd

Cc: Sean Purcell <m...@seanp.xyz>
Signed-off-by: Nick Terrell <terre...@fb.com>
---
 fs/squashfs/Kconfig|  14 +
 fs/squashfs/Makefile   |   1 +
 fs/squashfs/decompressor.c |   7 +++
 fs/squashfs/decompressor.h |   4 ++
 fs/squashfs/squashfs_fs.h  |   1 +
 fs/squashfs/zstd_wrapper.c | 150 +
 6 files changed, 177 insertions(+)
 create mode 100644 fs/squashfs/zstd_wrapper.c

diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
index ffb093e..1adb334 100644
--- a/fs/squashfs/Kconfig
+++ b/fs/squashfs/Kconfig
@@ -165,6 +165,20 @@ config SQUASHFS_XZ

  If unsure, say N.

+config SQUASHFS_ZSTD
+   bool "Include support for ZSTD compressed file systems"
+   depends on SQUASHFS
+   select ZSTD_DECOMPRESS
+   help
+ Saying Y here includes support for reading Squashfs file systems
+ compressed with ZSTD compression.  ZSTD gives better compression than
+ the default ZLIB compression, while using less CPU.
+
+ ZSTD is not the standard compression used in Squashfs and so most
+ file systems will be readable without selecting this option.
+
+ If unsure, say N.
+
 config SQUASHFS_4K_DEVBLK_SIZE
bool "Use 4K device block size?"
depends on SQUASHFS
diff --git a/fs/squashfs/Makefile b/fs/squashfs/Makefile
index 246a6f3..6655631 100644
--- a/fs/squashfs/Makefile
+++ b/fs/squashfs/Makefile
@@ -15,3 +15,4 @@ squashfs-$(CONFIG_SQUASHFS_LZ4) += lz4_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_LZO) += lzo_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_XZ) += xz_wrapper.o
 squashfs-$(CONFIG_SQUASHFS_ZLIB) += zlib_wrapper.o
+squashfs-$(CONFIG_SQUASHFS_ZSTD) += zstd_wrapper.o
diff --git a/fs/squashfs/decompressor.c b/fs/squashfs/decompressor.c
index d2bc136..8366398 100644
--- a/fs/squashfs/decompressor.c
+++ b/fs/squashfs/decompressor.c
@@ -65,6 +65,12 @@ static const struct squashfs_decompressor 
squashfs_zlib_comp_ops = {
 };
 #endif

+#ifndef CONFIG_SQUASHFS_ZSTD
+static const struct squashfs_decompressor squashfs_zstd_comp_ops = {
+   NULL, NULL, NULL, NULL, ZSTD_COMPRESSION, "zstd", 0
+};
+#endif
+
 static const struct squashfs_decompressor squashfs_unknown_comp_ops = {
NULL, NULL, NULL, NULL, 0, "unknown", 0
 };
@@ -75,6 +81,7 @@ static const struct squashfs_decompressor *decompressor[] = {
_lzo_comp_ops,
_xz_comp_ops,
_lzma_unsupported_comp_ops,
+   _zstd_comp_ops,
_unknown_comp_ops
 };

diff --git a/fs/squashfs/decompressor.h b/fs/squashfs/decompressor.h
index a25713c..0f5a8e4 100644
--- a/fs/squashfs/decompressor.h
+++ b/fs/squashfs/decompressor.h
@@ -58,4 +58,8 @@ extern const struct squashfs_decompressor 
squashfs_lzo_comp_ops;
 extern const struct squashfs_decompressor squashfs_zlib_com

[PATCH 1/4] lib: Add xxhash module

[Nick Terrell]

Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
The zstd compression and decompression modules added in the next patch
require xxhash. I extracted it out from zstd since it is useful on its
own. I copied the code from the upstream XXHash source repository and
translated it into kernel style. I ran benchmarks and tests in the kernel
and tests in userland.

I benchmarked xxhash as a special character device. I ran in four modes,
no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to
kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute
hashes on the copied data. I also ran it with four different buffer sizes.
The benchmark file is located in the upstream zstd source repository under
`contrib/linux-kernel/xxhash_test.c` [1].

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. I benchmarked using the file `filesystem.squashfs`
from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large.
Run the following commands for the benchmark:

modprobe xxhash_test
mknod xxhash_test c 245 0
time cp filesystem.squashfs xxhash_test

The time is reported by the time of the userland `cp`.
The GB/s is computed with

1,536,217,008 B / time(buffer size, hash)

which includes the time to copy from userland.
The Normalized GB/s is computed with

1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)).


| Buffer Size (B) | Hash  | Time (s) | GB/s | Adjusted GB/s |
|-|---|--|--|---|
|1024 | none  |0.408 | 3.77 | - |
|1024 | xxh32 |0.649 | 2.37 |  6.37 |
|1024 | xxh64 |0.542 | 2.83 | 11.46 |
|1024 | crc32 |1.290 | 1.19 |  1.74 |
|4096 | none  |0.380 | 4.04 | - |
|4096 | xxh32 |0.645 | 2.38 |  5.79 |
|4096 | xxh64 |0.500 | 3.07 | 12.80 |
|4096 | crc32 |1.168 | 1.32 |  1.95 |
|8192 | none  |0.351 | 4.38 | - |
|8192 | xxh32 |0.614 | 2.50 |  5.84 |
|8192 | xxh64 |0.464 | 3.31 | 13.60 |
|8192 | crc32 |1.163 | 1.32 |  1.89 |
|   16384 | none  |0.346 | 4.43 | - |
|   16384 | xxh32 |0.590 | 2.60 |  6.30 |
|   16384 | xxh64 |0.466 | 3.30 | 12.80 |
|   16384 | crc32 |1.183 | 1.30 |  1.84 |

Tested in userland using the test-suite in the zstd repo under
`contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the
kernel functions. A line in each branch of every function in `xxhash.c`
was commented out to ensure that the test-suite fails. Additionally
tested while testing zstd and with SMHasher [3].

[1] https://phabricator.intern.facebook.com/P57526246
[2] 
https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp
[3] https://github.com/aappleby/smhasher

zstd source repository: https://github.com/facebook/zstd
XXHash source repository: https://github.com/cyan4973/xxhash

Signed-off-by: Nick Terrell <terre...@fb.com>
---
 include/linux/xxhash.h | 236 +++
 lib/Kconfig|   3 +
 lib/Makefile   |   1 +
 lib/xxhash.c   | 500 +
 4 files changed, 740 insertions(+)
 create mode 100644 include/linux/xxhash.h
 create mode 100644 lib/xxhash.c

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000..9e1f42c
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSE

[PATCH] btrfs: Call kunmap if zlib_inflateInit2 fails

[Nick Terrell]

If zlib_inflateInit2 fails, the input page is never unmapped.
Add a call to kunmap when it fails.

Signed-off-by: Nick Terrell <nickrterr...@gmail.com>
---
 fs/btrfs/zlib.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fs/btrfs/zlib.c b/fs/btrfs/zlib.c
index 88d274e..30e19c9 100644
--- a/fs/btrfs/zlib.c
+++ b/fs/btrfs/zlib.c
@@ -250,6 +250,7 @@ static int zlib_decompress_biovec(struct list_head *ws, 
struct page **pages_in,
 
if (Z_OK != zlib_inflateInit2(>strm, wbits)) {
printk(KERN_WARNING "BTRFS: inflateInit failed\n");
+   kunmap(pages_in[page_in_index]);
return -EIO;
}
while (workspace->strm.total_in < srclen) {
-- 
2.7.4

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html