linux-kernel - Re: [PATCH v2] zswap: replace RB tree with xarray

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: <CAF8kJuP1=n_U4VsPh9eezmta1gYKEt0vqAJSLFnxBFBV1DzHcA@mail.gmail.com>
Date: Fri, 1 Mar 2024 14:33:37 -0800
From: Chris Li <chrisl@...nel.org>
To: David Laight <David.Laight@...lab.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>, 
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, "linux-mm@...ck.org" <linux-mm@...ck.org>, 
	Yosry Ahmed <yosryahmed@...gle.com>, Nhat Pham <nphamcs@...il.com>, 
	Johannes Weiner <hannes@...xchg.org>, "Matthew Wilcox (Oracle)" <willy@...radead.org>, 
	Chengming Zhou <zhouchengming@...edance.com>, Barry Song <v-songbaohua@...o.com>
Subject: Re: [PATCH v2] zswap: replace RB tree with xarray

On Fri, Mar 1, 2024 at 1:58 PM David Laight <David.Laight@...lab.com> wrote:
>
> From: Chris Li
> > Sent: 29 February 2024 08:46
> >
> > Very deep RB tree requires rebalance at times. That
> > contributes to the zswap fault latencies. Xarray does not
> > need to perform tree rebalance. Replacing RB tree to xarray
> > can have some small performance gain.
> >
> > One small difference is that xarray insert might fail with
> > ENOMEM, while RB tree insert does not allocate additional
> > memory.
>
> What is the difference in kernel memory use?
> IIRC someone pointed out (in the rosebush thread) that xarray
> uses a lot of kernel memory if the items are randomly distributed.

Do you have any suggestions on what script I can run to collect that
information for you?

If the swapfile is fully utilized, then every 1G of swapfile space
will save about 4M of memory using xarray compared to RB tree. Every
swap entry saves about 2 pointers (ignoring the intermedia xarray
node)
Every 1G of swapfile, fully populated xarray pointer uses about 2M of
memory. The RB tree node (left pointer, right pointer, color) will use
about 6M of memory.
In the worst case, you are wasting at most 2M of memory on xarray for
every 1G of swapfile.
Hope that calculation helps.

Keep in mind that the swap cache is already using xarray, using the
same swap entry offset as index. So whatever memory waste caused by
the sparse distribution of the swap entry, you are already getting
that in the current swap cache.

Chris