README.md
1# Linux Kernel Patch
2
3There are four pieces, the `xxhash` kernel module, the `zstd_compress` and `zstd_decompress` kernel modules, the BtrFS patch, and the SquashFS patch.
4The patches are based off of the linux kernel master branch.
5
6## xxHash kernel module
7
8* The patch is located in `xxhash.diff`.
9* The header is in `include/linux/xxhash.h`.
10* The source is in `lib/xxhash.c`.
11* `test/XXHashUserLandTest.cpp` contains tests for the patch in userland by mocking the kernel headers.
12 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.
13 It can be run with the following commands:
14 ```
15 cd test && make googletest && make XXHashUserLandTest && ./XXHashUserLandTest
16 ```
17* I also benchmarked the `xxhash` module against upstream xxHash, and made sure that they ran at the same speed.
18
19## Zstd Kernel modules
20
21* The (large) patch is located in `zstd.diff`, which depends on `xxhash.diff`.
22* The header is in `include/linux/zstd.h`.
23* It is split up into `zstd_compress` and `zstd_decompress`, which can be loaded independently.
24* Source files are in `lib/zstd/`.
25* `lib/Kconfig` and `lib/Makefile` need to be modified by applying `lib/Kconfig.diff` and `lib/Makefile.diff` respectively.
26 These changes are also included in the `zstd.diff`.
27* `test/UserlandTest.cpp` contains tests for the patch in userland by mocking the kernel headers.
28 It can be run with the following commands:
29 ```
30 cd test && make googletest && make UserlandTest && ./UserlandTest
31 ```
32
33## BtrFS
34
35* The patch is located in `btrfs.diff`.
36* Additionally `fs/btrfs/zstd.c` is provided as a source for convenience.
37* The patch seems to be working, it doesn't crash the kernel, and compresses at speeds and ratios that are expected.
38 It could still use some more testing for fringe features, like printing options.
39
40### Benchmarks
41
42Benchmarks run on a Ubuntu 14.04 with 2 cores and 4 GiB of RAM.
43The VM is running on a Macbook Pro with a 3.1 GHz Intel Core i7 processor,
4416 GB of ram, and a SSD.
45The kernel running was built from the master branch with the patch.
46
47The compression benchmark is copying 10 copies of the
48unzipped [silesia corpus](http://mattmahoney.net/dc/silesia.html) into a BtrFS
49filesystem mounted with `-o compress-force={none, lzo, zlib, zstd}`.
50The decompression benchmark is timing how long it takes to `tar` all 10 copies
51into `/dev/null`.
52The compression ratio is measured by comparing the output of `df` and `du`.
53See `btrfs-benchmark.sh` for details.
54
55| Algorithm | Compression ratio | Compression speed | Decompression speed |
56|-----------|-------------------|-------------------|---------------------|
57| None | 0.99 | 504 MB/s | 686 MB/s |
58| lzo | 1.66 | 398 MB/s | 442 MB/s |
59| zlib | 2.58 | 65 MB/s | 241 MB/s |
60| zstd 1 | 2.57 | 260 MB/s | 383 MB/s |
61| zstd 3 | 2.71 | 174 MB/s | 408 MB/s |
62| zstd 6 | 2.87 | 70 MB/s | 398 MB/s |
63| zstd 9 | 2.92 | 43 MB/s | 406 MB/s |
64| zstd 12 | 2.93 | 21 MB/s | 408 MB/s |
65| zstd 15 | 3.01 | 11 MB/s | 354 MB/s |
66
67
68## SquashFS
69
70* The patch is located in `squashfs.diff`
71* Additionally `fs/squashfs/zstd_wrapper.c` is provided as a source for convenience.
72* The patch has been tested on the master branch of the kernel.
73
74### Benchmarks
75
76Benchmarks run on a Ubuntu 14.04 with 2 cores and 4 GiB of RAM.
77The VM is running on a Macbook Pro with a 3.1 GHz Intel Core i7 processor,
7816 GB of ram, and a SSD.
79The kernel running was built from the master branch with the patch.
80
81The compression benchmark is the file tree from the SquashFS archive found in the
82Ubuntu 16.10 desktop image (ubuntu-16.10-desktop-amd64.iso).
83The compression benchmark uses mksquashfs with the default block size (128 KB)
84and various compression algorithms/compression levels.
85`xz` and `zstd` are also benchmarked with 256 KB blocks.
86The decompression benchmark is timing how long it takes to `tar` the file tree
87into `/dev/null`.
88See `squashfs-benchmark.sh` for details.
89
90| Algorithm | Compression ratio | Compression speed | Decompression speed |
91|----------------|-------------------|-------------------|---------------------|
92| gzip | 2.92 | 15 MB/s | 128 MB/s |
93| lzo | 2.64 | 9.5 MB/s | 217 MB/s |
94| lz4 | 2.12 | 94 MB/s | 218 MB/s |
95| xz | 3.43 | 5.5 MB/s | 35 MB/s |
96| xz 256 KB | 3.53 | 5.4 MB/s | 40 MB/s |
97| zstd 1 | 2.71 | 96 MB/s | 210 MB/s |
98| zstd 5 | 2.93 | 69 MB/s | 198 MB/s |
99| zstd 10 | 3.01 | 41 MB/s | 225 MB/s |
100| zstd 15 | 3.13 | 11.4 MB/s | 224 MB/s |
101| zstd 16 256 KB | 3.24 | 8.1 MB/s | 210 MB/s |
102