tree: 242d878fbf5f05edf3c8417b2ee0259e4d0f8e47 [path history] [tgz]
  1. .gitignore
  2. 0000-cover-letter.patch
  3. 0001-lib-Add-xxhash-module.patch
  4. 0002-lib-Add-zstd-modules.patch
  5. 0003-btrfs-Add-zstd-support.patch
  6. 0004-squashfs-Add-zstd-support.patch
  7. 0005-crypto-Add-zstd-support.patch
  8. 0006-squashfs-tools-Add-zstd-support.patch
  9. COPYING
  10. README.md
  11. btrfs-benchmark.sh
  12. btrfs-extract-benchmark.sh
  13. fs/
  14. include/
  15. kernelize.sh
  16. lib/
  17. squashfs-benchmark.sh
  18. test/
  19. xxhash_test.c
  20. zstd_compress_test.c
  21. zstd_decompress_test.c
contrib/linux-kernel/README.md

Linux Kernel Patch

There are four pieces, the xxhash kernel module, the zstd_compress and zstd_decompress kernel modules, the BtrFS patch, and the SquashFS patch. The patches are based off of the linux kernel master branch.

xxHash kernel module

  • The patch is located in xxhash.diff.
  • The header is in include/linux/xxhash.h.
  • The source is in lib/xxhash.c.
  • test/XXHashUserLandTest.cpp contains tests for the patch in userland by mocking the kernel headers. I tested the tests by commenting a line of of each branch in xxhash.c one line at a time, and made sure the tests failed. It can be run with the following commands:
    cd test && make googletest && make XXHashUserLandTest && ./XXHashUserLandTest
    
  • I also benchmarked the xxhash module against upstream xxHash, and made sure that they ran at the same speed.

Zstd Kernel modules

  • The (large) patch is located in zstd.diff, which depends on xxhash.diff.
  • The header is in include/linux/zstd.h.
  • It is split up into zstd_compress and zstd_decompress, which can be loaded independently.
  • Source files are in lib/zstd/.
  • lib/Kconfig and lib/Makefile need to be modified by applying lib/Kconfig.diff and lib/Makefile.diff respectively. These changes are also included in the zstd.diff.
  • test/UserlandTest.cpp contains tests for the patch in userland by mocking the kernel headers. It can be run with the following commands:
    cd test && make googletest && make UserlandTest && ./UserlandTest
    

BtrFS

  • The patch is located in btrfs.diff.
  • Additionally fs/btrfs/zstd.c is provided as a source for convenience.
  • The patch seems to be working, it doesn't crash the kernel, and compresses at speeds and ratios that are expected. It could still use some more testing for fringe features, like printing options.

Benchmarks

Benchmarks run on a Ubuntu 14.04 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 kernel running was built from the master branch with the patch.

The compression benchmark is copying 10 copies of the unzipped silesia corpus into a BtrFS filesystem mounted with -o compress-force={none, lzo, zlib, zstd}. The decompression benchmark is timing 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 btrfs-benchmark.sh for details.

AlgorithmCompression ratioCompression speedDecompression speed
None0.99504 MB/s686 MB/s
lzo1.66398 MB/s442 MB/s
zlib2.5865 MB/s241 MB/s
zstd 12.57260 MB/s383 MB/s
zstd 32.71174 MB/s408 MB/s
zstd 62.8770 MB/s398 MB/s
zstd 92.9243 MB/s406 MB/s
zstd 122.9321 MB/s408 MB/s
zstd 153.0111 MB/s354 MB/s

SquashFS

  • The patch is located in squashfs.diff
  • Additionally fs/squashfs/zstd_wrapper.c is provided as a source for convenience.
  • The patch has been tested on the master branch of the kernel.

Benchmarks

Benchmarks run on a Ubuntu 14.04 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 kernel running was built from the master branch with the patch.

The compression benchmark is the file tree from the SquashFS archive found in the Ubuntu 16.10 desktop image (ubuntu-16.10-desktop-amd64.iso). The compression benchmark uses mksquashfs with the default block size (128 KB) and various compression algorithms/compression levels. xz and zstd are also benchmarked with 256 KB blocks. The decompression benchmark is timing how long it takes to tar the file tree into /dev/null. See squashfs-benchmark.sh for details.

AlgorithmCompression ratioCompression speedDecompression speed
gzip2.9215 MB/s128 MB/s
lzo2.649.5 MB/s217 MB/s
lz42.1294 MB/s218 MB/s
xz3.435.5 MB/s35 MB/s
xz 256 KB3.535.4 MB/s40 MB/s
zstd 12.7196 MB/s210 MB/s
zstd 52.9369 MB/s198 MB/s
zstd 103.0141 MB/s225 MB/s
zstd 153.1311.4 MB/s224 MB/s
zstd 16 256 KB3.248.1 MB/s210 MB/s