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 160C3C4725D for ; Fri, 19 Jan 2024 05:49:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 86CA46B0085; Fri, 19 Jan 2024 00:49:21 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 81C706B0087; Fri, 19 Jan 2024 00:49:21 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6E3816B0088; Fri, 19 Jan 2024 00:49:21 -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 5C1896B0085 for ; Fri, 19 Jan 2024 00:49:21 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id F11DF14032C for ; Fri, 19 Jan 2024 05:49:20 +0000 (UTC) X-FDA: 81694982880.06.D27C58D Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by imf02.hostedemail.com (Postfix) with ESMTP id DDFE980007 for ; Fri, 19 Jan 2024 05:49:18 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=aWovuuas; spf=pass (imf02.hostedemail.com: domain of chrisl@kernel.org designates 145.40.68.75 as permitted sender) smtp.mailfrom=chrisl@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1705643359; a=rsa-sha256; cv=none; b=GfYgxLBTySOTVe8/RpTK1grKY6U2W5Fp057C7exy4oOQlOHg206EFZS/apVPrAF6UCR4W8 S1gb8txi5RCtu1kCSTZ3j5SiUzIvSHohKHg312C3UW78lSlgjztsOjFKVk5k3mmqLjRY2C hztri19nIlaMEAb8XKMqvxmYCvZa6tM= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=aWovuuas; spf=pass (imf02.hostedemail.com: domain of chrisl@kernel.org designates 145.40.68.75 as permitted sender) smtp.mailfrom=chrisl@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1705643359; 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=W4+vuLtpjFuzZZSsQ7+j0wMlZoDWStDlcw372yDvlZw=; b=u2xOxOKMoGhgBaPZV1RkFsKn0Kf3eq475Afh3Sg8/DcyQ2h+HHS9ej+4aZ7mzShDaEo1XF +mZr1QUMeuU+nSNyfARDw9gegTYmRGqV4ZqvZL5uquyNYqpE0QMZWmBPg3Yob2B+xnZYmO vR2x2vhqkdraw6PD+K4QT0WfU+46NGU= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by ams.source.kernel.org (Postfix) with ESMTP id 67278B81AA7 for ; Fri, 19 Jan 2024 05:49:15 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 37F39C43143 for ; Fri, 19 Jan 2024 05:49:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1705643354; bh=gFaoz5Lad+xTGdXdZ7SAqJDCdLlZZMjHIoUjSxAe/Ws=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=aWovuuasc8Tpi4aH/pOrg3P/qleuej3K3IkcZESn4DVHrl4Vy22+h9dEQzW9iZ43o kct+ZC7d6E34BomSXrbWzFWKitb2nSTDYIOxX+94gpeMcA4UfkfZr7bY8tt24utwLX U77wnbP2a1dk8OzMK6M1y1M1KbL7kcNb/SrkuzCKSU9MtESGbCLizMkvKVg0C0FGqf slhBIpSWxyuulR8zaXQdt2scBoCFPKf70rwdXeGzF7uTyCpRyWHJFGBEqM6nQoF4Jq jmNWKTkG1SnXh9fwMTANUQtrbFAmsskslpT/p/lnioIeKdUwREWZZaOjxoItrXdqac 8M7id9xokopkA== Received: by mail-oo1-f49.google.com with SMTP id 006d021491bc7-59960d26f65so8943eaf.0 for ; Thu, 18 Jan 2024 21:49:14 -0800 (PST) X-Gm-Message-State: AOJu0YwjBLiuSG+0xhQeIfiaoXjI/wMSgM7vjp0/01zGLDV40wcoGqkp wq7UpDTpV4/s4VDc4iLqAv73BRdm8l+pdXqOOqeCb/rPousnTVMsd5PHYYwxrb3X4e3fIu1j/Yr 2CntWZ01ByJXC5egs9ix6jX1nB/sfLWJuSKdo X-Google-Smtp-Source: AGHT+IF0zUxYWNPabx8vxbpRQ8Nx587jedet0oDo6CRg6ecDT2wFKoHxB4IWqV1gAwVBFcfxSv6C3uxGcuX+1llkUqs= X-Received: by 2002:a05:6359:320c:b0:175:67e3:cb28 with SMTP id rj12-20020a056359320c00b0017567e3cb28mr1756236rwb.12.1705643353344; Thu, 18 Jan 2024 21:49:13 -0800 (PST) MIME-Version: 1.0 References: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org> <20240117-zswap-xarray-v1-2-6daa86c08fae@kernel.org> In-Reply-To: From: Chris Li Date: Thu, 18 Jan 2024 21:49:02 -0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH 2/2] mm: zswap.c: remove RB tree To: Yosry Ahmed 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-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: DDFE980007 X-Stat-Signature: 9iydxt7zbtsjikywusiokryi5xu9doyz X-Rspam-User: X-HE-Tag: 1705643358-817907 X-HE-Meta: U2FsdGVkX18+1bEWND+3lHjF6gPHueDE36Y1EB79TcsSHOZATEsiYJM2PqiW98BdaV8onSQfNdvsbUZBF2YdE3gsCzyob82ugI6Ne8hukuShW4i0F9TRq3kbawOTy6BpmV8miDZzbw3EMc6SfZqqYtQ92CL5DlZ2M/BFeSl7n6YSmcdQFKcmMU/BYYws0eVyEw0z5ORDp8xTpqb/M8P9oPFNKZNZ67Tg6YrooqJS0oVdyPssJMEpVY9KjyW+jF3izYgC45dqdmphyb95JEtHJ15mA0AoYdFJgJRRUigOhMvoGR7XAHsFUd8homGrE3Nm66zRaZrbOQNfnXqH9+zLZbplkpG9H1gaKkXtWILgOoLIod21bAeInbiWCCrqBkAE64Z5RbVnfL1Eo2EMug8SVfvK5yBaupXg3wAZva7TYrJ4IKjuGVU4IWbZjaQwFjySJ8hJO6EV6wtLbynaUhha8lCeBjnsYU4NgL0TrIzMEqp6kjQ2xYWbcU8RuvVvJpKI/jB5MHsp9/TjpXbw37QN0LRg/YmAnS2WAimvaNwywOEGHsPoIuZAVoVW/evNAQ6gWMB6JZqY2ltbnUEXkB0jwQ2UPO0bGwzdcR6cFjlVCGjBhdM6ZaZgmx0R8EMP9Rjmrh2aWkCUDLo5jhCVZexTyJggonu/ls7vNIra+8uV2QahHNAWsTAej2Sutcp2xr+CiqkYkbJa8DJTBVjsDhtLvntP7cM9CTQNpSn80hUFyNZbzPsC4pk5UGB+cj0fOCyFm5hq7SWEWufoMZkkqOFa9ivE/2/pXc3WkW+6Vgcmgnhcr6ZYuxkKmAP1oe20PFb6H2tTfZp0KgEJTl7ExQigEInNGETDc/neN1iIoq736JVz0hHEhUzF2YWwF56xROfcGYe/t/x3NTt8giJaOqH8w8OhDF3FnkPtzmrGVIwLLSmAPH5QxkN1qGKl131KSOJF7PGXTv8sgn/bucD6/Ad Yzfim2Wq Jpd7DlRodz0DPxedplZcvJ/MxuIuFa57qC3yuuS6rhIlXthpD3CIu7KZaaYdtxJ6iaGo6COu2OGYvpY7SnDLz4PxdXYfpOBBvmZMh3gbwqEMjdTpXVOrx/3FOG3EHZaSiTsl02vsklIQRUN9QUMPkcd6Z10XARXhIS5Ky/7DHQpkuqyZJZEpnfoyO7tpifbOVj9yCvXuPvk6F7131VFaKU27F+SyWj6LXxzIH8Mioc2KEQCE= 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 Thu, Jan 18, 2024 at 11:36=E2=80=AFAM Yosry Ahmed wrote: > > On Wed, Jan 17, 2024 at 10:35=E2=80=AFPM Yosry Ahmed wrote: > > > > > @@ -493,45 +471,47 @@ static struct zswap_entry *zswap_search(struct = zswap_tree *tree, pgoff_t offset) > > > static int zswap_insert(struct zswap_tree *tree, struct zswap_entry = *entry, > > > struct zswap_entry **dupentry) > > > { > > > - struct rb_root *root =3D &tree->rbroot; > > > - struct rb_node **link =3D &root->rb_node, *parent =3D NULL; > > > - struct zswap_entry *myentry, *old; > > > - pgoff_t myentry_offset, entry_offset =3D swp_offset(entry->sw= pentry); > > > - > > > - > > > - while (*link) { > > > - parent =3D *link; > > > - myentry =3D rb_entry(parent, struct zswap_entry, rbno= de); > > > - myentry_offset =3D swp_offset(myentry->swpentry); > > > - if (myentry_offset > entry_offset) > > > - link =3D &(*link)->rb_left; > > > - else if (myentry_offset < entry_offset) > > > - link =3D &(*link)->rb_right; > > > - else { > > > - old =3D xa_load(&tree->xarray, entry_offset); > > > - BUG_ON(old !=3D myentry); > > > - *dupentry =3D myentry; > > > + struct zswap_entry *e; > > > + pgoff_t offset =3D swp_offset(entry->swpentry); > > > + XA_STATE(xas, &tree->xarray, offset); > > > + > > > + do { > > > + xas_lock_irq(&xas); > > > + do { > > > + e =3D xas_load(&xas); > > > + if (xa_is_zero(e)) > > > + e =3D NULL; > > > + } while (xas_retry(&xas, e)); > > > + if (xas_valid(&xas) && e) { > > > + xas_unlock_irq(&xas); > > > + *dupentry =3D e; > > > return -EEXIST; > > > } > > > - } > > > - rb_link_node(&entry->rbnode, parent, link); > > > - rb_insert_color(&entry->rbnode, root); > > > - old =3D xa_store(&tree->xarray, entry_offset, entry, GFP_KERN= EL); > > > - return 0; > > > + xas_store(&xas, entry); > > > + xas_unlock_irq(&xas); > > > + } while (xas_nomem(&xas, GFP_KERNEL)); > > > + return xas_error(&xas); > > > > I think using the xas_* APIs can be avoided here. The only reason we > > need it is that we want to check if there's an existing entry first, > > and return -EEXIST. However, in that case, the caller will replace it > > anyway (and do some operations on the dupentry): > > > > while (zswap_rb_insert(&tree->rbroot, entry, &dupentry) =3D=3D -EEXIST)= { > > WARN_ON(1); > > zswap_duplicate_entry++; > > zswap_invalidate_entry(tree, dupentry); > > } > > > > So I think we can do something like this in zswap_insert() instead: > > > > dupentry =3D xa_store(..); > > if (WARN_ON(dupentry)) { > > zswap_duplicate_entry++; > > zswap_invalidate_entry(tree, dupentry); > > } > > If this is doable, I think we can return xa_store(..) and keep the > logic in the caller. I think there's a chance > zswap_{search/insert/erase} may end up being very thin wrappers around > xa_{load/store/erase}, and we may be able to remove them completely. > Let's see how it goes. > See my other email about erasing an entry raced into a new entry. That is the part I am not certain. Anyway, when zswap adopte folio, then it might need to handle multi entry, we will be back to using the XAS API. Chris