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 6B082C47DB7 for ; Thu, 18 Jan 2024 19:36:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BA4E16B0072; Thu, 18 Jan 2024 14:36:20 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B2D976B0087; Thu, 18 Jan 2024 14:36:20 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9CE226B0089; Thu, 18 Jan 2024 14:36:20 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 89B996B0072 for ; Thu, 18 Jan 2024 14:36:20 -0500 (EST) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id C356CC0311 for ; Thu, 18 Jan 2024 19:36:19 +0000 (UTC) X-FDA: 81693438078.02.8CD2080 Received: from mail-ej1-f44.google.com (mail-ej1-f44.google.com [209.85.218.44]) by imf26.hostedemail.com (Postfix) with ESMTP id 0100B140004 for ; Thu, 18 Jan 2024 19:36:17 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=4IvKAHkH; spf=pass (imf26.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.44 as permitted sender) smtp.mailfrom=yosryahmed@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1705606578; a=rsa-sha256; cv=none; b=DgM9z42xq6neN7qdTx2AFcsL8+GWkzUeqdqv6TpeJEIueUx8dnOA2my7sNAtnZ0rnXwLYc L0cQdE0OGglx2UQjyB7KXIB2h19jvHh1NwsXq1mxmjGPNEZeUO35X7noP7qd7gaal4/Y7L n9obF52rwFScfwxIV8MfwUvV+p9EmNA= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=4IvKAHkH; spf=pass (imf26.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.44 as permitted sender) smtp.mailfrom=yosryahmed@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1705606578; 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=cZDkcKK8uyhcMNTfFp6ML8LXI1RuetKqYpSVVoE584Q=; b=TRbFKO89NC7RIwZ/2MlKrAWY3IpRbEiYEB2nZ3gIU3D4776sIS3ub1w5D1DLRZZ2qPwDIt V+u22kv4V7fTgy54hByEcBQll3Wx1a1m0UJC5kFYAtIqBdiRVwUrsQ3d9p6YViFRTiQFOp KJxLXxoQttNein3hrhZsxXOwFwdKR6g= Received: by mail-ej1-f44.google.com with SMTP id a640c23a62f3a-a2d7e2e7fe0so9274366b.1 for ; Thu, 18 Jan 2024 11:36:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1705606576; x=1706211376; 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=cZDkcKK8uyhcMNTfFp6ML8LXI1RuetKqYpSVVoE584Q=; b=4IvKAHkH9D2fVCp7ypnCQcbdwrrvqAy2IpP2pcdQGuAH/jUlwhzNAcV2LoqOkNvgx9 nklhKORQ6XGCCfvGcHwA2OQP/n1RVo10toWidOcKrmzWaNMglP37NK9YpcE00MoSL2rx 52W5g/VNlhFZz3ZmOUZ9cruRexW8dH+bDxtFms+5xLRqR6sxXpW/AgwT5M4iYOzQiER4 iJmrSVQ8kaG7HCthKX+4RkdcfeN3Buqik04vFLZoQzzSIzbmWCsZQd34nQLE6jEUXyX5 jCYw22RAnHpbShCK5ZfSUZuPFUzfFBGF7JJNJQzebCSc39F/Mg96DomZHR+PtSc8dwro lq8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705606576; x=1706211376; 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=cZDkcKK8uyhcMNTfFp6ML8LXI1RuetKqYpSVVoE584Q=; b=dGZHFCH8rk2476KrobwKmpHpnSHIV+yxUa/aO5G7KVveLuDi40CA2SmSdKxCwQX0W7 OVBCb0e6FtqRY2eKEeLVycgwu/K9fTwFyam4ctP6gL0N7KGq1CqAxNQ1wNg0pIi0CbiS XHfqonWa8kjtzlPdofojIehwbEeHMOAAbzV4LUdn3ximjXYkRZvsFHbSeWmAyUWteAmj IGI/OI2BUPzclR17KOly7cnugKzTTJyNCDT+sa4vWL9xLQKM7FFvy6BEfYMXZpy8jKtx t4ZbrfUT4xXHzRthD+Foec9/RHfbEUOG5vH7iG0BFHNZRJ/TdGTRCMs3141IjOuwjLcb kmJg== X-Gm-Message-State: AOJu0YxchJnNxmxB09ULK9/MAvt1gIBZ+2TSYPLvT3Bl7jYr9qlk2IpW TT92JpAclQnBdSILtuALlFcbv8x8LyHZjUIS9TxbXgr2rc6EYUll2o4Opxdc8sXVP4XgaLlEnCc bhhgO+/OwaNrQfmQ6k6r+qTOdjw+n+ETGMe8h X-Google-Smtp-Source: AGHT+IHNARndcPkevbhESph8uzGKHb3QILXTpJfID+26UjpTZwh9rl0SKaz5Jxqu1azSrdHtE0kbuTG6/SSnWwwcCms= X-Received: by 2002:a17:907:da8:b0:a2e:98d2:9c29 with SMTP id go40-20020a1709070da800b00a2e98d29c29mr2257202ejc.70.1705606576334; Thu, 18 Jan 2024 11:36:16 -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: Yosry Ahmed Date: Thu, 18 Jan 2024 11:35:38 -0800 Message-ID: Subject: Re: [PATCH 2/2] mm: zswap.c: remove 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-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 0100B140004 X-Stat-Signature: 577wyrwps8sp4b51dpn4s83rkspugstd X-Rspam-User: X-HE-Tag: 1705606577-931743 X-HE-Meta: U2FsdGVkX1+5dtYw1U1jP1FkW/zI78U79qZ/UdI+66UD+5bcSmOMQv41z33NVm8q2Wa4sZV8MjkViDOlRQfTt6AUk9FzjX2npTsSXBiCympZzSbwJ9T27lyKH1oRhe+XGizhuchDSVqz4Mpvsz6z2Cpc40CEz6QA0ilOYTFHlPnXKakJJWWXbdy5RXWyDMYTVd/NGlpUW6xddz9Fcil2jRjMXq5PfoQhh4gYsDSe5mdOJ4vkbj28IVDqF48bEOUFzjSvmhtrKy8U2/1T2XG9RvWYsa25hoMjOUBEntyjqy6DZN8raupwwvsAUH5YgETjq1QeEAEN/jsM8fchKLygjlRKmYVSJ5gOa2T185Fvje0qUNO1mPNvyo8XtLqgmQYa+8Swuai1tqx0eSJ5jD1F2hsUJUoOeIZ8yqbLX4nImTsEPuz2mDucKn38EhqXR0yLtSjEB2o2ttPKgBRZTiXP50tnm85Qe1o4jR3UrSIfQg12FhxCXg+5qtkPTWUbAVyDEQAl1avkFJ8rVVamh3cLro3AX65InBdWPe4q2iHRWeV55AFqjEpGBwcQGSQA7wXXH2nM+o7Hy1DzHBouphkB84NNIkiS/hmZ+shiLbSp6XMFaJ48Ky20IRqrRPtX5E0qfC3ZLiNNqP3m/c3K7wWd6X3t2JboHuZVbifWeFjJSQPTwE+IYa0IC4sI9KljLKF5ssqokc0vV7KJPgJLS1ZWQ3GnNppLSR1ee8IUL71yG+w0DouKhmQXB2nUTtgpUl2G95VWB3L0KfKRrTUueGwVtkCUyvdm4u7x4pi6dRWqElIBcnkJzGPvBy92Ey5fua0WFMj8wDoY4v2+pThHsH9z/n+fc03bFfgeWufpthp9YqKTftD92nkUFd1K7JvT84cB/JVGB9+/C2MM/fnqo9DBopapX8+XX6O3h7UjLTbPR73amQl+1Zj+sW05IlJGyWbCdr/4GOdfjmG7xRB7kTh PWi6D1TD QsMTRm6xyrcZNdc99fZEEZ4g5ZXS3dU2r7pdCOVSmnfp+qgRdGmRJSHjqEaDpF4gAM7kJaRmg82+lpMx3+L/ANCItDPydiOp23lPu3hDZTVZ/iiwq+0lf/fw9wP2gN4JqBEsUUPuP1C9jyOoT997vgkNXBReFgZwgtd2ebRNOBdPFvtAIprQbeJwLMa023eVVdvxyC4X5i9arCvfnHlCPATS7P8ukr0PnQeGh/zMhgAoJp2ok/WSj8bMt8g== 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:35=E2=80=AFPM Yosry Ahmed wrote: > > > @@ -493,45 +471,47 @@ static struct zswap_entry *zswap_search(struct zs= wap_tree *tree, pgoff_t offset) > > static int zswap_insert(struct zswap_tree *tree, struct zswap_entry *e= ntry, > > 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->swpe= ntry); > > - > > - > > - while (*link) { > > - parent =3D *link; > > - myentry =3D rb_entry(parent, struct zswap_entry, rbnode= ); > > - 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_KERNEL= ); > > - 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.