linux-kernel - Re: [PATCH] z3fold: the 3-fold allocator for compressed pages

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-next>] [day] [month] [year] [list]

Message-ID: <CAC8qmcDHCMCEZ8F+1gEtsgSTzjAH=RETT=WodxkL8RfJpj2dkg@mail.gmail.com>
Date:	Thu, 14 Apr 2016 10:53:50 -0500
From:	Seth Jennings <sjenning@...hat.com>
To:	Vitaly Wool <vitalywool@...il.com>
Cc:	Vlastimil Babka <vbabka@...e.cz>, Linux-MM <linux-mm@...ck.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Dan Streetman <ddstreet@...e.org>
Subject: Re: [PATCH] z3fold: the 3-fold allocator for compressed pages

On Thu, Apr 14, 2016 at 4:06 AM, Vitaly Wool <vitalywool@...il.com> wrote:
>
>
> On Thu, Apr 14, 2016 at 10:48 AM, Vlastimil Babka <vbabka@...e.cz> wrote:
>>
>> On 04/14/2016 10:05 AM, Vitaly Wool wrote:
>>>
>>> This patch introduces z3fold, a special purpose allocator for storing
>>> compressed pages. It is designed to store up to three compressed pages
>>> per
>>> physical page. It is a ZBUD derivative which allows for higher
>>> compression
>>> ratio keeping the simplicity and determinism of its predecessor.
>>
>>
>> So the obvious question is, why a separate allocator and not extend zbud?
>
>
> Well, as far as I recall Seth was very much for keeping zbud as simple as
> possible. I am fine either way but if we have zpool API, why not have
> another zpool API user?
>
>>
>> I didn't study the code, nor notice a design/algorithm overview doc, but
>> it seems z3fold keeps the idea of one compressed page at the beginning, one
>> at the end of page frame, but it adds another one in the middle? Also how is
>> the buddy-matching done?

Yes, as soon as you introduce a 3rd object in the page, zpage
fragmentation becomes an issue.  Having a middle object partitions
that zpage, blocking allocations that are larger than either
partition, even though the combined size of the partitions could have
accommodated the object.

This also means that the unbuddied list is broken in this
implementation.  num_free_chunks() is calculating the _total_ free
space in the page.  But that is not that the _usable_ free space by a
single object, if the middle object has partitioned that free space.

Seth

>
>
> Basically yes. There is 'start_middle' variable which point to the start of
> the middle page, if any. The matching is done basing on the buddy number.
>
> ~vitaly