BratSinot June 13, 2013 at 20:12

As I wrote LZ4 compression plugin for Reiser4

From the sandbox

I will not explain what Reiser4 is and what it is eaten with, because there is enough information on this [ 1 , 2 ] and I see no reason to repeat it. Therefore, I’ll probably start with the fact that I decided to try Reiser4 in 2010, but due to problems using transparent compression together with tail packaging (as it turned out there were problems in the flush procedure that were currently solved [ 3 ]), I switched back to ReiserFS. In 2013, I found out that this problem was resolved [ 4] and I returned to Reiser4 (LZO1 on a stationary system, on a laptop without compression). After some time, I remembered the news about the “Extremely Fast Compression Algorithm” LZ4, as well as the fact that the Illumos community added support for it in ZFS. Then I was visited by the thought: “But it would be great if Reiser4 had LZ4 support!” So I started to “attach” it to Reiser4.

First I looked at the ccreg40 plugin code (as you know Reiser4 has a plugin structure). It all starts with the file fs / reiser4 / plugin / compress / compress.h which has the reiser4_compression_id enumeration:

typedef enum {
	LZO1_COMPRESSION_ID,
	GZIP1_COMPRESSION_ID,
	LAST_COMPRESSION_ID,
} reiser4_compression_id;

It identifies the identification numbers of a compression algorithm (LZO1 and GZIP1 are available by default). The last in the list is LAST_COMPRESSION_ID, which is needed to determine the sizes of various tables containing information about the algorithms and related functions.

We continue in the file fs / reiser4 / plugin / compress / compress.c , in which we already directly describe the functions. Only 7 main functions:

init () - Needed if the algorithm requires preliminary initialization of something. Neither GZIP1, nor LZO1, nor LZ4 require this, so they simply return 0.
overrun () - Returns the maximum size of the "tail" that can be formed during compression. For example, if you do not take into account the “tail”, then with incompressible input data, the output buffer will go beyond the limits. For example, for GZIP1 this value is 0, for LZO1 “src_len / 64 + 19”, and for LZ4 “src_len / 255 + 16”.
alloc () - Allocates memory for algorithm needs.
free () - Releases the memory allocated for the needs of the algorithm.
min_size_deflate () - Returns the minimum block size that it still makes sense to compress.
compress () - Compresses data.
decompress () - Unpacks data.

I will dwell on the alloc () / free () functions. One of the arguments that they accept is an argument of type tfm_action. tfm_action is an enumeration described in the header file fs / reiser4 / plugin / compress / compress.h (has the same structure as reiser4_compression_id), in which there are two elements TFMA_READ and TFMA_WRITE.

typedef enum {
	TFMA_READ,   /* decrypt, decompress */
	TFMA_WRITE,  /* encrypt, compress */
	TFMA_LAST
} tfm_action;

Thus, it is possible to determine the moment, function calls, when reading or writing. Some algorithms require additional memory for decompression, and thus we correctly allocate the right amount of memory. For example, the GZIP1 algorithm requires additional memory and we allocate it for it, but the LZO1 / LZ4 algorithms do not require it and we do not allocate it.

Everything ends in the same compress.c file, a description of the compression_plugins array , in which we indicate the type of the plug-in, its identification number, header, functions, etc.

	[LZ4_COMPRESSION_ID] = {
		.h = {
			.type_id = REISER4_COMPRESSION_PLUGIN_TYPE,
			.id = LZ4_COMPRESSION_ID,
			.pops = &compression_plugin_ops,
			.label = "lz4",
			.desc = "lz4 compression transform",
			.linkage = {NULL, NULL}
		},
		.init = lz4_init,
		.overrun = lz4_overrun,
		.alloc = lz4_alloc,
		.free = lz4_free,
		.min_size_deflate = lz4_min_size_deflate,
		.checksum = reiser4_adler32,
		.compress = lz4_compress,
		.decompress = lz4_decompress
 	}

Now about what I changed in the LZ4 code. To start, I removed all the code associated with Microsoft Visual Studio (maybe someday they will build the Linux kernel using the MS VS compiler, but obviously this will not be in the near future) and C ++ (one extern “C”). Then he removed the code related to optimization for BigEndian systems, which made the output information incompatible with LittleEndian systems and the code that allows using stack memory instead of usual (it will turn out faster, but we are in the kernel, such liberties will not be in vain). Finally, I removed the malloc () / free () functions from the code, adding a pointer to the memory allocated for the needs of LZ4 in the list of function arguments (remember alloc ()).

Well, now the most important thing is how it all worked ... frankly, badly. The LZ4 plugin was slower and compressed worse than the LZO1 plugin. Measurements were carried out on a live system, in single-user mode. The measurement included the operation of unmounting the partition (so that the sync / flush procedures worked and the files were completely written to disk). Three tests were performed: linear writing / reading to disk of a file zipped with zeros (from / dev / zero), linear reading / writing of an incompressible file (previously taken from / dev / urandom and written to tmpfs memory) and unpacking / compression of Linux kernel sources version 3.9.5. Of all the tests, the plugin with LZ4 showed an advantage only when writing / reading a file with zeros. In all other tests, LZO1 outperformed LZ4 both in compression / decompression speed and in the final file size.

In further studies (fullbench from LZ4 and lz4c vs lzop), it was found that LZ4 loses all its properties with small blocks, and shows the declared properties [ 5 ] only on large blocks, for example, in default fullbench 4MiB, in lz4c 8MiB. As Eduard Shishkin put it: “4MiB is a bit much. LZO1 compresses the pieces and is much smaller .. ”[ 6 ]

Thus, I found out that for Reiser4 LZO1 is more preferable than LZ4. By the way, something tells me that the support of LZ4, which was added by the community, in ZFS will not always manifest itself (although in comparison with LZJB always), and unsuccessful attempts to push LZ4 in Linux [ 7] (as a possibility of use for kernel compression or initram) confirmation of this. As for LZ4 in btrfs ... Eduard Shishkin clearly told what btrfs [ 8 ] is and how it is being developed.

Patch Reiser4 for Linux 3.9
Patch LZ4 for Reiser4
PS The LZ4_decompress_safe () function needs a little redoing, but it makes no sense, so I did not.
Patch for reiser4progs
[1] habrahabr.ru/post/45873
[2] http://theoks.net/~onekopaka/Reiser4Site/v4.html
[3] marc.info/?l=reiserfs-devel&m=135146138331012&w=2
[ 4] sourceforge.net/p/reiser4/discussion/general/thread/2bca4f8e
[5] code.google.com/p/lz4
[6] sourceforge.net/p/reiser4/discussion/general/thread/780facb4
[7] lwn.net/Articles/534168
[8] habrahabr.ru/post/108629

Tags:

As I wrote LZ4 compression plugin for Reiser4

Also popular now: