From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 66C01C47077 for ; Thu, 18 Jan 2024 07:02:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 01D746B0093; Thu, 18 Jan 2024 02:02:53 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F0C226B0095; Thu, 18 Jan 2024 02:02:52 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DD3726B0096; Thu, 18 Jan 2024 02:02:52 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id CEE376B0093 for ; Thu, 18 Jan 2024 02:02:52 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 9E4E014064E for ; Thu, 18 Jan 2024 07:02:52 +0000 (UTC) X-FDA: 81691539384.14.61EB32E Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf15.hostedemail.com (Postfix) with ESMTP id CA23DA0023 for ; Thu, 18 Jan 2024 07:02:50 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=prqO5TJm; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf15.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1705561370; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Nbjh7lj3LaK3dDhh9thIiUGNa0deGp3ufaKLo6GVy8c=; b=Y2wZ+JhR5BCn7irHgBiQpM1lhyuTlI0AQOrBEq7Sfckd/rwrPWXHpMIZrhYXHi9hodDEEi jWP8/tdyngYKBZ5TgZk7JwNtu+3Q0pMU+W3mBPdYP12cemZsE0QdvbaVf39ijTYpbbYnl7 +zSq4Z0uJECnJqf6H9NLN8Z9GsaFCfE= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=prqO5TJm; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf15.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1705561370; a=rsa-sha256; cv=none; b=SstQCZRV+VioMsVYubgRZEqQO7NuQBNRxHn0dJ7qUrjh9XDLJqRN93AklrbUNaYsQ6pDwk z5Vyx0QDkxNxqFoZyzeUHtyYI2gPADtMOG8z1uNCZjO6/4GgUtA/cD3jyswoIzrJwoK6ba ISaQ7PilKa4xy0Ik0MD+BJZH2zHgMtc= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-559d3fbed6bso1783194a12.1 for ; Wed, 17 Jan 2024 23:02:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1705561369; x=1706166169; darn=kvack.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=Nbjh7lj3LaK3dDhh9thIiUGNa0deGp3ufaKLo6GVy8c=; b=prqO5TJmXIglsw4WnAgC+oChcQTj9Kqo9SJpGqv9VkulLoCH1jiOqqNfKTUwOdAYx5 qjP4mx2ula0VeqYdorBnL7Rdr/oVMwzhErMYnrUN8fVnbok3t0lOerEmN6pJRGejwJ8w T3OKLfh3GaSRFH1BqpGu0lASOJvjlhKtcUky4GtGkTiMly5dnQ8meCjGTKHjVjVMHs5/ mWKnjuURy+GphzYCJK05vjWFZ+EzDcvjjLL+WFQcvPglv2sb74fOGVAtnIto1Hr7WmaQ ZySymYLruXy/cIVv45OIv1swxF4u7zA64PvHtklFJJ5mfd1qp0MhixQigK415GCJdqL3 tWQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705561369; x=1706166169; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Nbjh7lj3LaK3dDhh9thIiUGNa0deGp3ufaKLo6GVy8c=; b=DbVMXvrkMWfdlsspC2Z7vTRM5TVPQgxhwAQCqy7TYdJLhtlIeP53qTIKVR6RU0L0T/ P4CxQal9BmMXTCpo/9NAuhAVL2jJdD4z9lHR3wwnV1WL8CMuu3CcBBLrwO0YmEjX0c7m FI/s4ubKVAGxL7LebZgEb+TGoQnmEmU1OAg44PWKjoEiNSmCCL81DBft7SCS25ZIJ973 +ohLjgFtGW/l5K8Ihjq3eYcmt0YRlP3wCQlMHRvxm9hymDbWVPVOF81XRMv4zsMtZZcR +3QFQ4Pib5JAHxB0xXZXH4wZCaPfizPk9+2ppIS8Rt4H3mV5YFarSB8sN4fnY2H8FGs2 fBXQ== X-Gm-Message-State: AOJu0Yw7ZM7Ff+iVldfvzscKP6UlkHgToUB+del8FPThJp7b1rCzyrN2 19w9qqXgGBj3RT8OXuzjfkQlibM98bJIJ6NnuN4EStL5U5Kw6kUSIdfYDn8NPfsg5eBVH6UoRFQ lELXwDl174l9cVryloMWfhayuhZjWmacznjMV X-Google-Smtp-Source: AGHT+IFXOCrsKZFskYsH/UIu/PL4WgJ1hIa7+Er8K1Ylf7x/E0yJYgJ9ghoUUYiH9SJjC/yJ/eXvEQ1HEE65wc1z/Ec= X-Received: by 2002:a17:907:7890:b0:a28:fcbd:cabc with SMTP id ku16-20020a170907789000b00a28fcbdcabcmr129710ejc.41.1705561369103; Wed, 17 Jan 2024 23:02:49 -0800 (PST) MIME-Version: 1.0 References: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org> <7f52ad78-e10b-438a-b380-49451bf6f64f@bytedance.com> In-Reply-To: <7f52ad78-e10b-438a-b380-49451bf6f64f@bytedance.com> From: Yosry Ahmed Date: Wed, 17 Jan 2024 23:02:11 -0800 Message-ID: Subject: Re: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree To: Chengming Zhou Cc: Chris Li , Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, =?UTF-8?B?V2VpIFh177+8?= , Yu Zhao , Greg Thelen , Chun-Tse Shao , =?UTF-8?Q?Suren_Baghdasaryan=EF=BF=BC?= , Brain Geffon , Minchan Kim , Michal Hocko , Mel Gorman , Huang Ying , Nhat Pham , Johannes Weiner , Kairui Song , Zhongkun He , Kemeng Shi , Barry Song , "Matthew Wilcox (Oracle)" , "Liam R. Howlett" , Joel Fernandes Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspamd-Queue-Id: CA23DA0023 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 4rmtfj8cms4a77w7midhgrtcdw5qfryt X-HE-Tag: 1705561370-211635 X-HE-Meta: U2FsdGVkX19+fNPae50TAz2hLWCPDihlfZdWnn8u9fapk+ia/oYOHE6xXqgJR2y+AcxXaD4RUxWDQMS5UFf517OgNfUTQB4dBdle8pq8Yrkux+YC6SxnYesmt3KrgYjcR7dYBFra2kZrQ4qwJOFnQiSF2OkCGvau71xZ53oHlchGFdlDiIdo+JH9uK5hTQZg4x3PDUdyTB1TA3ku7gOSecC+vAixDpZgsVow2y4aa1Yt9/0My+Up07RC2IKNfuTPzh+qi0imUTTL203YTwy299vrKiS7k2+mB4wsm9avBLUu6R7Xs+dAmIc2EjZB68M2Utt5l07j8xATDWOsETIu3c0fcve/zbeXrzGhkSbznTX5ndvsaTSiez4LSelUziCCyKjnphUqgGyXa08oR7WwTHDraPWE60tDL9tAElLEB5Tcd1OlY5ClgUw0z3WMnFetvwqErBbPypBg8byI/8aVt5ORdkvHsrZyebFOqxL+BgyqxrlOmXVpq3cw3z9VqFbZ87p/mloPSm9nNcL7VefcpASH9NWHf2W20LExKq0eCZUrF5CDIotAvlmPOiUHRy6RDo7sjdBNLIplOVvYTlx5jHyOTgVFJnANt8b4z5/+a+/ofb7mA8TIiOZf0XXm7UeCM6/s0F2oKnqAN0qcUq+2oVkN+aWzmAdLG/XUxjmrXahhabwCy8nABbccsANb3iOIjhgEtNW1Uv4QW0fn92BEBHCtWWnOWADjnywSZvXUil82hCroxUBohJEnwmzpFC6Aq/4pbxyY2geSYsNkNKYCMxg0Q/v/aCK8yFqP5lkVnN6cDFFgVmeIKb7PFKEDME8Y4PFPyuW1VSE4c4yTCqtFo4P68zliJ+0IiFP3xK57La+jWnTGhlaygvRbwIqJCAT1oM0hAsvAk24vxmanGL6CGO3jtgcVTgRpUCcs9wZw7Z1mHvLJE73Dej8W3GUwzVepN9fdTaW3aI3Zp269oYa XZ9kjuKR 2LO5gXa5LiHyKKixceoPBCjDw9LKiPSV6CTmZVt17L6FGKtd62hFQkbGbAvw5WxuRLhgqOGEMOC5U/4BHAUZ0KtpdhvLuD6vg0oQ1nCVNuSE3Ch1GhgGOOOYoYQR6+8EK30h8tWPPoYsBguEU87eg/oAXIQEaHN9ap5D6iaHhfFeMgHhw6xE/e6fjCSmL80zeVoQPidY543eWHmN6rliRGOZjapAfawuZ24miUi/q4kgWtRk7Qw+qVAX/dmp6oB/b16mw2vJN0fqKbuoT1hH8faJeH0ak3GKD0tA0er/uhX37xcARm/UGMJ/+BR9T4l3EwpviQobiBJnxsTRtFGfpP5DYLIKgz8/XxAVZd2AifjaPLh04cxqfSTKkKQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Wed, Jan 17, 2024 at 10:57=E2=80=AFPM Chengming Zhou wrote: > > Hi Yosry and Chris, > > On 2024/1/18 14:39, Yosry Ahmed wrote: > > On Wed, Jan 17, 2024 at 10:01=E2=80=AFPM Yosry Ahmed wrote: > >> > >> That's a long CC list for sure :) > >> > >> On Wed, Jan 17, 2024 at 7:06=E2=80=AFPM Chris Li w= rote: > >>> > >>> 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. > >> > >>> > >>> 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 expect to merge the zswap rb tree spin lock with the xarray > >>> lock in the follow up changes. > >> > >> Shouldn't this simply be changing uses of tree->lock to use > >> xa_{lock/unlock}? We also need to make sure we don't try to lock the > >> tree when operating on the xarray if the caller is already holding the > >> lock, but this seems to be straightforward enough to be done as part > >> of this patch or this series at least. > >> > >> Am I missing something? > > > > Also, I assume we will only see performance improvements after the > > tree lock in its current form is removed so that we get loads > > protected only by RCU. Can we get some performance numbers to see how > > the latency improves with the xarray under contention (unless > > Chengming is already planning on testing this for his multi-tree > > patches). > > I just give it a try, the same test of kernel build in tmpfs with zswap > shrinker enabled, all based on the latest mm/mm-stable branch. > > mm-stable zswap-split-tree zswap-xarray > real 1m10.442s 1m4.157s 1m9.962s > user 17m48.232s 17m41.477s 17m45.887s > sys 8m13.517s 5m2.226s 7m59.305s > > Looks like the contention of concurrency is still there, I haven't > look into the code yet, will review it later. I think that's expected with the current version because the tree spin_lock is still there and we are still doing lookups with a spinlock.