linux-kernel - [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree

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]

Date: Wed, 17 Jan 2024 19:05:40 -0800
From: Chris Li <chrisl@...nel.org>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: linux-kernel@...r.kernel.org, linux-mm@...ck.org, 
 Wei Xu <weixugc@...gle.com>, 
 Yu Zhao <yuzhao@...gle.com>, Greg Thelen <gthelen@...gle.com>, 
 Chun-Tse Shao <ctshao@...gle.com>, 
 Suren Baghdasaryan <surenb@...gle.com>, 
 Yosry Ahmed <yosryahmed@...gle.com>, Brain Geffon <bgeffon@...gle.com>, 
 Minchan Kim <minchan@...nel.org>, Michal Hocko <mhocko@...e.com>, 
 Mel Gorman <mgorman@...hsingularity.net>, Huang Ying <ying.huang@...el.com>, 
 Nhat Pham <nphamcs@...il.com>, Johannes Weiner <hannes@...xchg.org>, 
 Kairui Song <kasong@...cent.com>, 
 Zhongkun He <hezhongkun.hzk@...edance.com>, 
 Kemeng Shi <shikemeng@...weicloud.com>, Barry Song <v-songbaohua@...o.com>, 
 "Matthew Wilcox (Oracle)" <willy@...radead.org>, 
 "Liam R. Howlett" <Liam.Howlett@...cle.com>, 
 Joel Fernandes <joel@...lfernandes.org>, 
 Chengming Zhou <zhouchengming@...edance.com>, Chris Li <chrisl@...nel.org>
Subject: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree

The RB tree shows some contribution to the swap fault
long tail latency due to two factors:
1) RB tree requires re-balance from time to time.
2) The zswap RB tree has a tree level spin lock protecting
the tree access.

The swap cache is using xarray. The break down the swap
cache access does not have the similar long time as zswap
RB tree.

Moving the zswap entry to xarray enable read side
take read RCU lock only.

The first patch adds the xarray alongside the RB tree.
There is some debug check asserting the xarray agrees with
the RB tree results.

The second patch removes the zwap RB tree.

I expect to merge the zswap rb tree spin lock with the xarray
lock in the follow up changes.

I can surely use some help in reviewing and testing.

Signed-off-by: Chris Li <chrisl@...nel.org>
---
Chris Li (2):
      mm: zswap.c: add xarray tree to zswap
      mm: zswap.c: remove RB tree

 mm/zswap.c | 120 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 59 insertions(+), 61 deletions(-)
---
base-commit: d7ba3d7c3bf13e2faf419cce9e9bdfc3a1a50905
change-id: 20240104-zswap-xarray-716260e541e3

Best regards,
-- 
Chris Li <chrisl@...nel.org>