linux-kernel - Re: [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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20240118180959.gwqphdgmf7r5sdne@revolver>
Date: Thu, 18 Jan 2024 13:59:18 -0500
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Christopher Li <chrisl@...nel.org>
Cc: Yosry Ahmed <yosryahmed@...gle.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        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>,
        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>,
        Joel Fernandes <joel@...lfernandes.org>,
        Chengming Zhou <zhouchengming@...edance.com>
Subject: Re: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree

* Christopher Li <chrisl@...nel.org> [240118 01:48]:
> On Wed, Jan 17, 2024 at 10:02 PM Yosry Ahmed <yosryahmed@...gle.com> wrote:
> >
> > That's a long CC list for sure :)
> >
> > On Wed, Jan 17, 2024 at 7:06 PM Chris Li <chrisl@...nel.org> wrote:
> > >
> > > 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.
> >
> > I think the comparison to the swap cache may not be valid as the swap
> > cache has many trees per swapfile, while zswap has a single tree.
> 
> Yes, good point. I think we can bench mark the xarray zswap vs the RB
> tree zswap, that would be more of a direct comparison.
> 
> > > Moving the zswap entry to xarray enable read side
> > > take read RCU lock only.
> >
> > Nice.
> >
> > >
> > > 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.
> >
> > The breakdown looks like something that would be a development step,
> > but for patch submission I think it makes more sense to have a single
> > patch replacing the rbtree with an xarray.
> 
> I think it makes the review easier. The code adding and removing does
> not have much overlap. Combining it to a single patch does not save
> patch size. Having the assert check would be useful for some bisecting
> to narrow down which step causing the problem. I am fine with squash
> it to one patch as well.

I had thought similar when I replaced the rbtree with the maple tree in
the VMA space.  That conversion was more involved and I wanted to detect
if there was ever any difference, and where I had made the error in the
multiple patch conversion.

This became rather painful once an issue was found, as then anyone
bisecting other issues could hit this difference and either blamed the
commit pointing at the BUG_ON() or gave up (I don't blame them for
giving up, I would).  With only two commits, it may be easier for people
to see a fixed tag pointing to the same commit that bisect found (if
they check), but it proved an issue with my multiple patch conversion.

You may not experience this issue with the users of the zswap, but I
plan to avoid doing this again in the future.  At least a WARN_ON_ONCE()
and a comment might help?

Thanks,
Liam