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 800F4C4707B for ; Thu, 18 Jan 2024 06:40:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BC1976B0083; Thu, 18 Jan 2024 01:40:24 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B720D6B0085; Thu, 18 Jan 2024 01:40:24 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A14506B0087; Thu, 18 Jan 2024 01:40:24 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 8EEAA6B0083 for ; Thu, 18 Jan 2024 01:40:24 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 5DFD740542 for ; Thu, 18 Jan 2024 06:40:24 +0000 (UTC) X-FDA: 81691482768.19.F823240 Received: from mail-ej1-f43.google.com (mail-ej1-f43.google.com [209.85.218.43]) by imf07.hostedemail.com (Postfix) with ESMTP id 79A9240003 for ; Thu, 18 Jan 2024 06:40:22 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=KwOPrnYY; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf07.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.43 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1705560022; a=rsa-sha256; cv=none; b=EsxTBUkzZYACdS5wBObHxvagRZomZ94opTE/f4/iTvmQV/Q5nDGJbc/yCPcOqq4xvH852Q tpkb7DSZlkTzXzACuMoT11Bc+yKqYbJLfwppsQ2lDWEN2+g5dJ+ITWpnP5aKuJHuefjeis wvgCFuMkxUmUrIUWhWn6DmbXzF8utlQ= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=KwOPrnYY; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf07.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.43 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=1705560022; 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=Fo8gKI5wcPqBhTE9n7Z17rjeWkfglngA29Ql06ELL7w=; b=5BMxEqCuJ06jNjp0Q7p1kJsCC2MNUlevmUjlWxMbGUqGNjsfX6HB/S7my2XcLpDFgqhJFW jExLTbKgCONv+3HHVGdKoag8zjv2MPiXA0LCw9/nmRBGKF6bumcLjNUSyx/U8tJ60+WtzR BsHLY/6Frbx1hHgTDJD5GTshCinyw3Q= Received: by mail-ej1-f43.google.com with SMTP id a640c23a62f3a-a2d348d213dso540542066b.0 for ; Wed, 17 Jan 2024 22:40:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1705560021; x=1706164821; 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=Fo8gKI5wcPqBhTE9n7Z17rjeWkfglngA29Ql06ELL7w=; b=KwOPrnYYNPo1pSCs6v9fqWwBLwAsId3++pX1MoTohj4cP3esHwEevBt+lk5ETfJKC0 hbP4rZtYKvBORFZe2d9OK8fUS1OJsDhsBg5VX3zA2CJ/J4ft+iXUUNBbP+CChr24ab/e 59gqfhzgP2eRN4pnUY3KE/8NlQV6bt0c+WJCGAg8OqQzMsjd6/2hZ0v2o3VX4hWy3kYF io7AwhHtuNRkjEanc0DmPWB26pxjNgs8UknwUmsiPnSkBQr20fzk01fww9IZq1bEwfz5 nnhcBEaRv/pm1OpkoIgDhNR51rUn9dGLXsi+PGNpRjL3xOJlpL56RCt/ZyYIysEGy3gU 3ncA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705560021; x=1706164821; 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=Fo8gKI5wcPqBhTE9n7Z17rjeWkfglngA29Ql06ELL7w=; b=ZfdHNCkzYpPYlJ/o23Xxf0TfDgyyHMaTRx+kLe0v2nMUBtiDjn25DE/UtlkBdXJwfG MW1LkCJws55D2tyxGSZ23+BWJLXYV43r9ha0INrE8VhvgX8z/uyGz9HfTjZzkqTNEDSe KxEGHwdiXY2eP2qjeMpug5nRLZIwxCzcN1HuRZPwbpg6gpPeGLT7OQXDeTHTu4VYjNha 8jeccEGapeFtW+Joug0oXGdWI4dPeLd7zQTxNY5DxMLclYnEL0ARQWEhBrYsyaOHep94 RJFCVXDqEqqflI6CirEfsSShwcXzJ1/UHRFP15V0P1fr5UN4j99SeH7ZmKCMORk7luIc g1FQ== X-Gm-Message-State: AOJu0Yw/UpXQwzj8umRBuRqdfZ4JC+Sao/7Umi4SktQK0KhNRqov4O2a iGmU8P3aPTmByDV4MWqoD2rE4mTNzwjD4wVGVV5uGsSupTQzUegG8HMXVAwETcbOnsbmHF/sqt4 P26ejiibZeDnXM0tcsTmGl/JtawzITkrI8qzR X-Google-Smtp-Source: AGHT+IGw5du6D82TNqrknpI8JySufWW6DPtTDJUIBduFgdYHIqWd8umiN+b4qNoeZ9g61oVtNH4GmHa39joy5nNJF38= X-Received: by 2002:a17:906:5916:b0:a28:f6a1:f0c0 with SMTP id h22-20020a170906591600b00a28f6a1f0c0mr173495ejq.103.1705560020964; Wed, 17 Jan 2024 22:40:20 -0800 (PST) MIME-Version: 1.0 References: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org> In-Reply-To: From: Yosry Ahmed Date: Wed, 17 Jan 2024 22:39:45 -0800 Message-ID: Subject: Re: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree To: Chris Li Cc: 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 , Chengming Zhou Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 79A9240003 X-Stat-Signature: u8jjetgdbdjwto15m4k9zu7hn8uuog5j X-HE-Tag: 1705560022-464592 X-HE-Meta: U2FsdGVkX1/g7552snA9iulkYS6NJO+gAWyu1zdD+VmxnImRoEfTqlBEefgw9/xpTkJmxs5EjRxngL8wg881PWrSkhm+4VJCHO/z7I/0F4D04nQDCfoVv5RU3e6eLzm9WwrBXuDSvhQpRJvXzj+3d84D0DpNyvl7EwulgM9lsCO3BJsWq13mYMkGT6bxm0awZ9+VBAmzK+jDe0I9p9AcQ/s9MRyJFc7ytC5jLDejNON6WmXj/rtyvjAxoWbEhfcjCpuffNkIXpxefw2VkA46Qm5hgePQ7j6bYRQ5Uvg40xhrUN0wnNuy+Oqqi4M+SYCZNE/5KYaqoYb1bwTN/Gy8FJ0hKvOpXfc4EtScieAOftvwGzWcnrBaS5uYL2Rgts1Qp9mB0lzcKAH3p1zBBYxDdAr0aojJVlXtUrywDHS/QssL5X98vxKrBSg7vQgJHwb4CZuWE8P9RQ4pXodPCtmeH6UmeMxkL1+m4GcXW5tqs1S5odOphOnoBfcnqyeN9fcG5z0ZYTjKj+UKP9XV0PDWHhDRJ9zbnKvwvOi6hMpOeC925kzg1aeEmhmHOCGeVuA+uNDo/Jw2u73vKIwl4rTNhvkO21zJWFxP2/YBlBj+bj+yYR7imx4CpDfSplhUXIFyY7szLv4t4nt0537CgS8DY3/rPHohXTMxNM3o6Lyz2EJsEqObqHQZQFKrQ2KBz56R2gVqiBseFuMco6M1Aoan1m13Unj2vP2F4Lf63xGnqRN4Yv2JoIbDLtNLUEUsfCp1QvlH/UHV1u7vmqFnmGzg1e9FxYFgQJK4+UUTg3AZBQrmUxcqu6gQQAuvOQI/liUns9snfGNqcnfOxuJyrdKWrKg3vis89QXXbAGGvuyARBDWfqnyD3Usn7ORtII9d79giSHrcFTniaGGIlfUhqW6enFbBRfrZNbqfXqkJxwO+l4E+ENKhEApgZ9xJyWS24ZplK4j4CQzfIkG94m+5/U Cgrizb2R 8uY3ZohU9zkEP1ONTZ2iNcTgeu9DXTpXB1NoqbzdDhe507QAw/M30nCL3DPd2xeaIJWhSCFZ5O0F6yMPHQVHV1/iZeFJIOXmOynRnSNZYiaJrfuqxgKle+mBXiCGdx1eUVbmYUFKmTC0KbmXoWz35cj51+f57CNUza0CEq4GoXkEQwkvfkrjwFxJuREnht57P/URSQyrG2+kxhqVq3GW24GNOnPem0czySCFxMmBFqHCRRQeSMsR0b8FGLV512ZwBqNweXCutFYJZEFCvzJmX7KOPTG19HMJg6JUl6diyazTpXDASozDsFDg4XA== 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: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 wrot= e: > > > > 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).