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]
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

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ