Received-SPF: pass (google.com: domain of linux-kernel+bounces-30489-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1;
Date: Thu, 18 Jan 2024 13:59:18 -0500
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Christopher Li <chrisl@kernel.org>
Cc: Yosry Ahmed <yosryahmed@google.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        Wei =?utf-8?B?WHXvv7w=?= <weixugc@google.com>,
        Yu Zhao <yuzhao@google.com>, Greg Thelen <gthelen@google.com>,
        Chun-Tse Shao <ctshao@google.com>,
        Suren =?utf-8?B?QmFnaGRhc2FyeWFu77+8?= <surenb@google.com>,
        Brain Geffon <bgeffon@google.com>, Minchan Kim <minchan@kernel.org>,
        Michal Hocko <mhocko@suse.com>,
        Mel Gorman <mgorman@techsingularity.net>,
        Huang Ying <ying.huang@intel.com>, Nhat Pham <nphamcs@gmail.com>,
        Johannes Weiner <hannes@cmpxchg.org>, Kairui Song <kasong@tencent.com>,
        Zhongkun He <hezhongkun.hzk@bytedance.com>,
        Kemeng Shi <shikemeng@huaweicloud.com>,
        Barry Song <v-songbaohua@oppo.com>,
        "Matthew Wilcox (Oracle)" <willy@infradead.org>,
        Joel Fernandes <joel@joelfernandes.org>,
        Chengming Zhou <zhouchengming@bytedance.com>
Subject: Re: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree
Message-ID: <20240118180959.gwqphdgmf7r5sdne@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
	Christopher Li <chrisl@kernel.org>,
	Yosry Ahmed <yosryahmed@google.com>,
	Andrew Morton <akpm@linux-foundation.org>,
	linux-kernel@vger.kernel.org, linux-mm@kvack.org,
	Wei =?utf-8?B?WHXvv7w=?= <weixugc@google.com>,
	Yu Zhao <yuzhao@google.com>, Greg Thelen <gthelen@google.com>,
	Chun-Tse Shao <ctshao@google.com>,
	Suren =?utf-8?B?QmFnaGRhc2FyeWFu77+8?= <surenb@google.com>,
	Brain Geffon <bgeffon@google.com>, Minchan Kim <minchan@kernel.org>,
	Michal Hocko <mhocko@suse.com>,
	Mel Gorman <mgorman@techsingularity.net>,
	Huang Ying <ying.huang@intel.com>, Nhat Pham <nphamcs@gmail.com>,
	Johannes Weiner <hannes@cmpxchg.org>,
	Kairui Song <kasong@tencent.com>,
	Zhongkun He <hezhongkun.hzk@bytedance.com>,
	Kemeng Shi <shikemeng@huaweicloud.com>,
	Barry Song <v-songbaohua@oppo.com>,
	"Matthew Wilcox (Oracle)" <willy@infradead.org>,
	Joel Fernandes <joel@joelfernandes.org>,
	Chengming Zhou <zhouchengming@bytedance.com>
References: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org>
 <CAJD7tkbQb5nAQdhHXELQsUWs8KhwnoOZ7C8Eu2o7tCYSKeY9Ug@mail.gmail.com>
 <CANeU7Q=mphnSfiZRwFhqFTy56d2ifa5Pz-aa1h3O1PXUo_cu=Q@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <CANeU7Q=mphnSfiZRwFhqFTy56d2ifa5Pz-aa1h3O1PXUo_cu=Q@mail.gmail.com>
User-Agent: NeoMutt/20220429
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?utf-8?B?cVB5bi9lUS9aTlI4R3pqMjZIYjRFZ3ZGTW9Mcmk1cmd6MDBnQ0luNTlpcmRY?=
 =?utf-8?B?aTBrazJKaXYwbHR1SlRqT2ZsTFFtMlJmVTFVTTl3d005Q3p2dWgrRU43Vkty?=
 =?utf-8?B?K0ViUzQzNlZMTWpQZjhnbStWTlZrSCt5aWFlSEZqVmZNcEdOcnVzcWdmOWF0?=
 =?utf-8?B?dU5DQ1U4cWJ1TlZSQjVyalRqMVNhendieERPd1d4WWMwRFAvOHNZUDkra2ZQ?=
 =?utf-8?B?WlRUaXUvZFJXRzlvakMyYVd3YnU0KytQSURBT0M0d3lXMklqVW5ud1RNeUp5?=
 =?utf-8?B?UEJ1TXZKTXBZTDVIaUF4Rm1KTDU5VFh3QmltL3NsQ2JCNTRXVnBrY0M2a2xk?=
 =?utf-8?B?UVBmdzU3YmxIVFJpTXpZcHVFNEZzbEcvVm1vcE9raTVJR3hhVXBOZUNpYmtY?=
 =?utf-8?B?VnFIMFBRSERaV0VIb04rQ2Y5aFVDMVFUTFRtNjhqNTVYVm1mV1NRbjlabkhO?=
 =?utf-8?B?NjVLU2thWFFqYnU0UkVqREVPR205MHo2aFhyQkNUMG9hZGw3ek5WSTEyN3lN?=
 =?utf-8?B?OWJBM3NkWUpvK3ZuaWN0NGZHeVE4K2xoYTU1VGxoQ2U0RjNLWjZkWndvaXlp?=
 =?utf-8?B?NWYvMEhoWXNSa3ZQcWljcE00czN2bDBDdDgwMjNPeEtSaFlqN2dyd2hnWklV?=
 =?utf-8?B?eEFabUFodjFSQlZ3R1paRlFOcEw5cDlkbGJpUVVPWno3MHBUdE5ENXBRTlB3?=
 =?utf-8?B?eXl0UXdHaXZHUWs2eWNuK2ZqWElWTHFVQW4zZCtzdkI2dDFUZGphdWh5T1dn?=
 =?utf-8?B?ZGhqOExjRkJJMDA4azlUSjVBNFg3NWU3aEd3RHJ1MFZCOGE4SmNGSWN0VEwx?=
 =?utf-8?B?c2NYMm5hbnNUQWZGeUk4SzBia08ycFRmbEdZSlBYZjdWbjJOWlhSTytmVTVi?=
 =?utf-8?B?Vlo2YUt4NHd1MkVJK1pGcWd4aVlCVEY5ZnBrdmhla3d6Q25Ya1BnQkhKM0Ur?=
 =?utf-8?B?YnlyMFp0SExiQmxSa0NiOEVyRjBXOFF6ZjBDRk1WNWYzRDRGNWxGaTl1TzVR?=
 =?utf-8?B?YmY4VWNCNStnRXZqNWZ2NkFmSHZmNU9HTG9jNjNGclU1c25XYzVUYTFJNTZV?=
 =?utf-8?B?N0w1RTJqT3dzcTdxTGt5cXVWcEdxTDZHSnNUN3hONWxFU1B3aVR2MXFpVXNV?=
 =?utf-8?B?dlVnZ0xobGNsYy80dzNsUGVDS2lCQnkyM1B6U0ZJZmlPd0swUGN0dXlvRVRz?=
 =?utf-8?B?dk1oUnB3ZnRRY2JsNjRtbjVrV2ltZm1LTkVCd01nMnF5a2FpbysweW9KZDZL?=
 =?utf-8?B?OGVUbyt5QUNoRWRiaXB3Yy85Yy9RTkxLekhobmUzTDdjN3hycFV2c0MrekJj?=
 =?utf-8?B?aS9RczlYS0FDbnEwV2hxRTVwa3BYLytZVzByM2pnV2xDWkZ4bVF3eWE3OVlM?=
 =?utf-8?B?cVJzeXQ3WkpHMERHVXk5NUJQbkl2M2puNXpiek1Ld2JwWTBweStwM2hJQk5m?=
 =?utf-8?B?ekZLZUQ5U3lGeFJNL0dFY1RHWmJqUXREOUpoUURJMW9za1VuOUhMUDZ0VTNy?=
 =?utf-8?B?K2w2ODMzOEQyS3FmOFAxamdKNll4a1dXOUhhU1AxNWx5UTI3RXRWZnBmZlFT?=
 =?utf-8?B?TG1lN0dsOUJJU2pJNnFveHFMcXhGaks5MlNEdVZodjBEL2E4QkhObjd6N25F?=
 =?utf-8?B?cXhPZXhuWDdtK3dWMnZoMlg4TnYxNC95T3VwdUF0WTJOdVB1M256TDRTQ3dW?=
 =?utf-8?B?Sm1PQlFhQnJzVGx3SkJDUzRGMDdERzQvS095NTZMYVMrcDJvaldFbEZRVHFr?=
 =?utf-8?B?NS9zUHd3MnlvRWxhSU56djgwejBrME50VXB6SVRlYnEvN25pRlZqbFo5eERk?=
 =?utf-8?B?MW9uZVc1Tk9PSFAxZm5SYzlVNitab0pFby9QSVFwcHlxVmtTRkZQRTVibVVB?=
 =?utf-8?B?VklaVnRqRkp5MjJHTEZtZzVPTEhITlEwdjRNZjdBaEprZUFoTGQvK2pjcnk5?=
 =?utf-8?B?WG04N1BTT3FHNlR3eHhKMFJMb1F1UDJEMVZRWVVQbHNab2JrZktJZFNtVW1J?=
 =?utf-8?B?ZHNlQ0pQZ2Ric3ppSzFQTkFaRjdaRGN5a1FIemNmRkdGVzAyZmNmN1psQXdY?=
 =?utf-8?B?S3dUU0tSSmpoYy90SUNTaGkwZ0tYcEMrNTNTdFFtSWtuWXdVakRscDlINGtW?=
 =?utf-8?Q?8uupax27XO2NWYMj3v+hnet7d?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	rWcrqyVnVGafdl46WS79FLy22d5lcK6KHNgFk97u0PuJjWfpkhyVf/bw1piEvwtdEp9fVYljXzL48VjAoaTX6tprI9UTd9lds0WYIDYcBUGn3btgF2AWkPKJ21XSGi2r78yIW5UWk0opB2Z0mym9uN5xChZ5uWHW1Io4WPWHSRjA9xTmniHdbP2upM27Pn3pbmE5uIRsTb5ah+dQgtD8TZ/9I2wqUi1EvN5l2acNzZxIS8e4ENbZVK1rYL6Y+/IiVTPI0WrQ28+/g7ZQCqyFcn7auMpkiIGanN013s3axkBzVyibO6wna1ZP2gEYxrma1ZYau9N8fXS/fWM1y+iiqY8FMa3gyMh8w/f7EbgK+8/6H/TfXs4iLtf2uAqo6rSuvf0h/bVA5IpFcvLKirS/JOQG9sAH3kCrvLrfZW/JIHvRgRO4NjtCxglPqUs17REWnaftfs5RQt63t07hImRAgQCUnMzlG4xIuvKXt6PWZ7eOQggpweO4p8f4GGoFisUK9uJZcyoYAjmxj0MSZ88IHxk5lYP5agDyaO9KTiOtd4yfcwwDsFELsx8IsrGN75JNHXGFz9l0ep4xqEwR7o/7hgy14J71Eo6gtZSsW4RBouo=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 9d98c5bb-dc14-4fbf-9b63-08dc185793e8
X-MS-Exchange-CrossTenant-AuthSource: DS0PR10MB7933.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 Jan 2024 18:59:20.3952
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 42UJzOq0t7o9fmWkq0Fi9/0snZdWU2/BK0yTq7S0AFx6jNNQczmxYen2QWqmMcJM5hIZrRt3U87VC2CK/5vY8g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA0PR10MB6699
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.997,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2024-01-18_08,2024-01-17_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 adultscore=0 phishscore=0
 suspectscore=0 malwarescore=0 spamscore=0 mlxlogscore=603 mlxscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000
 definitions=main-2401180138
X-Proofpoint-GUID: BUkHo3FvUlIJ-StYWUq_TQFOM47nHTxd
X-Proofpoint-ORIG-GUID: BUkHo3FvUlIJ-StYWUq_TQFOM47nHTxd

* Christopher Li <chrisl@kernel.org> [240118 01:48]:
> On Wed, Jan 17, 2024 at 10:02=E2=80=AFPM Yosry Ahmed <yosryahmed@google.c=
om> wrote:
> >
> > That's a long CC list for sure :)
> >
> > On Wed, Jan 17, 2024 at 7:06=E2=80=AFPM Chris Li <chrisl@kernel.org> wr=
ote:
> > >
> > > 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.
>=20
> 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.
>=20
> > > 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.
>=20
> 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