linux-kernel - Re: [PATCH] zram: add zstd to the supported algorithms list

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <69F9B64F-B138-4D8B-9167-9B91855CFFA9@fb.com>
Date:   Fri, 25 Aug 2017 02:46:04 +0000
From:   Nick Terrell <terrelln@...com>
To:     Sergey Senozhatsky <sergey.senozhatsky.work@...il.com>
CC:     Joonsoo Kim <iamjoonsoo.kim@....com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "minchan@...nel.org" <minchan@...nel.org>,
        Yann Collet <cyan@...com>
Subject: Re: [PATCH] zram: add zstd to the supported algorithms list

On 8/24/17, 7:21 PM, "Sergey Senozhatsky" <sergey.senozhatsky.work@...il.com> wrote:
> not really familiar either... I was thinking about having "zstd" and
> "zstd_dict" crypto_alg structs - one would be !dict, the other one would
> allocate dict and pass it to compress/decompress zstd callbacks. "zstd"
> vecrsion would invoke zstd_params() passing zeros as compress and dict
> sizes to ZSTD_getParams(), while "zstd_dict" would invoke, lets say,
> zstd_params_dict() passing PAGE_SIZE-s. hm... (0, PAGE_SIZE)?  to
> ZSTD_getParams(). just a rough idea...

The way zstd dictionaries work is the user provides some data which gets
"prepended" to the data that is about to be compressed, without actually
writing it to output. That way zstd can find matches in the dictionary and
represent them for "free". That means the user has to pass the same data to
both the compressor and decompressor.

We could build a dictionary, say every 20 minutes, by sampling 512 B chunks
of the RAM and constructing a 16 KB dictionary. Then recompress all the
compressed RAM with the new dictionary. This is just a simple example of a
dictionary construction algorithm. You could imagine grouping pages by
application, and building a dictionary per application, since those pages
would likely be more similar.

Regarding the crypto API, I think it would be possible to experiment by
creating functions like
`zstd_comp_add_dictionary(void *ctx, void *data, size_t size)'
and `zstd_decomp_add_dictionary(void *ctx, void *data, size_t size)'
in the crypto zstd implementation and declare them in `zcomp.c'. If the
experiments prove that using zstd dictionaries (or LZ4 dictionaries) is
worthwhile, then we can figure out how we can make it work for real.