From: Nick Terrell <terrelln@fb.com>
To: Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com>
CC: Joonsoo Kim <iamjoonsoo.kim@lge.com>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "minchan@kernel.org" <minchan@kernel.org>, Yann Collet <cyan@fb.com>
Subject: Re: [PATCH] zram: add zstd to the supported algorithms list
Thread-Topic: [PATCH] zram: add zstd to the supported algorithms list
Thread-Index: AQHTHSCvXWqWlMVfbUKYI//VGek9A6KUPdeA//+XcYCAAHo6gP//jzWAgAB4pAD//5GggA==
Date: Fri, 25 Aug 2017 02:46:04 +0000
Message-ID: <69F9B64F-B138-4D8B-9167-9B91855CFFA9@fb.com>
References: <20170824014936.4738-1-sergey.senozhatsky@gmail.com>
 <AA6434F2-6932-436E-B063-B6C0417A553C@contoso.com>
 <20170825004947.GE29701@js1304-P5Q-DELUXE>
 <27EDD68A-61DC-42F1-8422-16B9AB9F0EB3@fb.com>
 <20170825015301.GB743@jagdpanzerIV.localdomain>
 <08620C31-AD6A-4DDB-ACA6-22243920AE1E@fb.com>
 <20170825022106.GC743@jagdpanzerIV.localdomain>
In-Reply-To: <20170825022106.GC743@jagdpanzerIV.localdomain>
Accept-Language: en-US
Content-Language: en-US
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <C1D1BD59C8B47D4EA6B71AF8FED86D35@namprd15.prod.outlook.com>
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Aug 2017 02:46:04.8598
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM5PR15MB1420
X-OriginatorOrg: fb.com
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-08-25_01:,,
 signatures=0
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from base64 to 8bit by nfs id v7P2kIgu021093
Content-Length: 1737
Lines: 31

On 8/24/17, 7:21 PM, "Sergey Senozhatsky" <sergey.senozhatsky.work@gmail.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.