Merge branch 'zstd-minimal' of git://git.kernel.org/pub/scm/linux/kernel/git/mason/linux-btrfs

Pull zstd support from Chris Mason:
 "Nick Terrell's patch series to add zstd support to the kernel has been
  floating around for a while. After talking with Dave Sterba, Herbert
  and Phillip, we decided to send the whole thing in as one pull
  request.

  zstd is a big win in speed over zlib and in compression ratio over
  lzo, and the compression team here at FB has gotten great results
  using it in production. Nick will continue to update the kernel side
  with new improvements from the open source zstd userland code.

  Nick has a number of benchmarks for the main zstd code in his lib/zstd
  commit:

      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 |

      I benchmarked zstd decompression using the same method on the same
      machine. The benchmark file is located in the upstream zstd repo
      under `contrib/linux-kernel/zstd_decompress_test.c` [4]. The
      memory reported is the amount of memory required to decompress
      data compressed with the given compression level. If you know the
      maximum size of your input, you can reduce the memory usage of
      decompression irrespective of the compression level.

        | Method   | Time (s) | MB/s    | Adjusted MB/s | Memory (MB) |
        |----------|----------|---------|---------------|-------------|
        | none     |    0.025 | 8479.54 |             - |           - |
        | zstd -1  |    0.358 |  592.15 |        636.60 |        0.84 |
        | zstd -3  |    0.396 |  535.32 |        571.40 |        1.46 |
        | zstd -5  |    0.396 |  535.32 |        571.40 |        1.46 |
        | zstd -10 |    0.374 |  566.81 |        607.42 |        2.51 |
        | zstd -15 |    0.379 |  559.34 |        598.84 |        4.61 |
        | zstd -19 |    0.412 |  514.54 |        547.77 |        8.80 |
        | zlib -1  |    0.940 |  225.52 |        231.68 |        0.04 |
        | zlib -3  |    0.883 |  240.08 |        247.07 |        0.04 |
        | zlib -6  |    0.844 |  251.17 |        258.84 |        0.04 |
        | zlib -9  |    0.837 |  253.27 |        287.64 |        0.04 |

  I ran a long series of tests and benchmarks on the btrfs side and the
  gains are very similar to the core benchmarks Nick ran"

* 'zstd-minimal' of git://git.kernel.org/pub/scm/linux/kernel/git/mason/linux-btrfs:
  squashfs: Add zstd support
  btrfs: Add zstd support
  lib: Add zstd modules
  lib: Add xxhash module

39 files changed, 14399 insertions, 11 deletions

diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
index 80e9c18ea64f..a26c63b4ad68 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 128ce17a80b0..962a95aefb81 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/compression.c b/fs/btrfs/compression.c
index 883ecc58fd0d..b51d23f5cafa 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -704,6 +704,7 @@ static struct {
 static const struct btrfs_compress_op * const btrfs_compress_op[] = {
         &btrfs_zlib_compress,
         &btrfs_lzo_compress,
+        &btrfs_zstd_compress,
 };
 
 void __init btrfs_init_compress(void)
diff --git a/fs/btrfs/compression.h b/fs/btrfs/compression.h
index 3b1b0ac15fdc..d2781ff8f994 100644
--- a/fs/btrfs/compression.h
+++ b/fs/btrfs/compression.h
@@ -99,7 +99,8 @@ enum btrfs_compression_type {
         BTRFS_COMPRESS_NONE  = 0,
         BTRFS_COMPRESS_ZLIB  = 1,
         BTRFS_COMPRESS_LZO   = 2,
-        BTRFS_COMPRESS_TYPES = 2,
+        BTRFS_COMPRESS_ZSTD  = 3,
+        BTRFS_COMPRESS_TYPES = 3,
 };
 
 struct btrfs_compress_op {
@@ -127,6 +128,7 @@ struct btrfs_compress_op {
 
 extern const struct btrfs_compress_op btrfs_zlib_compress;
 extern const struct btrfs_compress_op btrfs_lzo_compress;
+extern const struct btrfs_compress_op btrfs_zstd_compress;
 
 int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end);
 
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 2add002662f4..5a8933da39a7 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -270,6 +270,7 @@ struct btrfs_super_block {
          BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS |          \
          BTRFS_FEATURE_INCOMPAT_BIG_METADATA |          \
          BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO |          \
+         BTRFS_FEATURE_INCOMPAT_COMPRESS_ZSTD |         \
          BTRFS_FEATURE_INCOMPAT_RAID56 |                \
          BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF |         \
          BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA |       \
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 46329524dd5f..b6dc1d179d23 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -2828,6 +2828,8 @@ int open_ctree(struct super_block *sb,
         features |= BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF;
         if (fs_info->compress_type == BTRFS_COMPRESS_LZO)
                 features |= BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO;
+        else if (fs_info->compress_type == BTRFS_COMPRESS_ZSTD)
+                features |= BTRFS_FEATURE_INCOMPAT_COMPRESS_ZSTD;
 
         if (features & BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA)
                 btrfs_info(fs_info, "has skinny extents");
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index ae8fbf9d3de2..0ebaf5d116bc 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -296,8 +296,10 @@ static int btrfs_ioctl_setflags(struct file *file, void __user *arg)
 
                 if (fs_info->compress_type == BTRFS_COMPRESS_LZO)
                         comp = "lzo";
-                else
+                else if (fs_info->compress_type == BTRFS_COMPRESS_ZLIB)
                         comp = "zlib";
+                else
+                        comp = "zstd";
                 ret = btrfs_set_prop(inode, "btrfs.compression",
                                      comp, strlen(comp), 0);
                 if (ret)
@@ -1435,6 +1437,8 @@ int btrfs_defrag_file(struct inode *inode, struct file *file,
 
         if (range->compress_type == BTRFS_COMPRESS_LZO) {
                 btrfs_set_fs_incompat(fs_info, COMPRESS_LZO);
+        } else if (range->compress_type == BTRFS_COMPRESS_ZSTD) {
+                btrfs_set_fs_incompat(fs_info, COMPRESS_ZSTD);
         }
 
         ret = defrag_count;
diff --git a/fs/btrfs/props.c b/fs/btrfs/props.c
index 09c0266f248d..f6a05f836629 100644
--- a/fs/btrfs/props.c
+++ b/fs/btrfs/props.c
@@ -390,6 +390,8 @@ static int prop_compression_validate(const char *value, size_t len)
                 return 0;
         else if (!strncmp("zlib", value, len))
                 return 0;
+        else if (!strncmp("zstd", value, len))
+                return 0;
 
         return -EINVAL;
 }
@@ -412,6 +414,8 @@ static int prop_compression_apply(struct inode *inode,
                 type = BTRFS_COMPRESS_LZO;