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 20B46C54798 for ; Thu, 7 Mar 2024 18:45:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5F9C06B00AA; Thu, 7 Mar 2024 13:45:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 5AA3B6B0266; Thu, 7 Mar 2024 13:45:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 421E56B0269; Thu, 7 Mar 2024 13:45:32 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 2DD6A6B0261 for ; Thu, 7 Mar 2024 13:45:32 -0500 (EST) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id CF9941A120E for ; Thu, 7 Mar 2024 18:45:31 +0000 (UTC) X-FDA: 81871121262.21.3443487 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf21.hostedemail.com (Postfix) with ESMTP id 5416A1C001B for ; Thu, 7 Mar 2024 18:45:26 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=mG9cnX7g; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf21.hostedemail.com: domain of chrisl@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=chrisl@kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1709837128; 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=Ih+Usdxw233dJi1r6/WBHXbgTpv6vjnktz2XUBea5Jo=; b=ZACawbs5Ixjxn3PLGQP925803nzvfTRMpDf1qWu6W5Tplc/5ClQS+DzuRjU0HGaTdlhkUe OybWNVYDN7EWz7dw2X6UAuzTsMoT6zUTG8+njQaJ9IAeiuD/vIhQmnB/RqKuQBd7US8hhl hCY5jpmQdV1JeTUKyMCC3kP3DCuDvZs= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=mG9cnX7g; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf21.hostedemail.com: domain of chrisl@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=chrisl@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1709837128; a=rsa-sha256; cv=none; b=AGykpgk6Kyw3c0jklI49m9eWW1BwZscsaCKwg8odrPtRZaOy2CFOOzkoPJqh8k/8jeCU37 oFZAkFk3dXWuC7B7VKBb0SelrI7imo2Ck6oowHHyWUHkAWkG5q6w8p4gK2NxZjMQQU5VZA mqOVZNdJivWsI6bpUv96p094YTe6ELQ= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 3CFA1CE1CAE for ; Thu, 7 Mar 2024 18:45:24 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 64AB6C43394 for ; Thu, 7 Mar 2024 18:45:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1709837123; bh=s5GdOzHE//uEnkMCcYz0ORml5ihxX9d3bq9ysI/X7CM=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=mG9cnX7g0LpB1wKyQ7LpE8B90W/SJUIGqBHVFLDUg7G4hrRLQ2KdlHG5l9PZfrxlo r1vLMHB5LmpQ3UhfRkFld+iq6bpluCfJ+k82JSOl6MR6lhA4ACjTYkNgJ2mlFgT0Kk A/DW2gxPLfpz8GjsCQ63rpxabMzgyrmamt58LDgb6QNZPCMLEsDInGV9sIwKJgRgof 8xmCU38gWbp1G1yt/YpRYZHfz6bUsLjkuMTnZKlfSE1S+hTVZVjouTSUp06YDofrU4 iJdEM2BNvfmxylNligMx1TQgulkavvQzvp9l4nloA1EQhqXAMdymQFHX3Dnpy6JdS7 UXbXuYYCYP13A== Received: by mail-lj1-f170.google.com with SMTP id 38308e7fff4ca-2d2509c66daso18634921fa.3 for ; Thu, 07 Mar 2024 10:45:23 -0800 (PST) X-Forwarded-Encrypted: i=1; AJvYcCWg78HO/EAiNkcaHAJS7yBRzm/WvZZaYaPXAo/h7DyEThFJP8U/9CCBERFiCd/f77BAfi/6WM9rio3BZ6cOnUjYvDM= X-Gm-Message-State: AOJu0YzrKiHPJNyKxWeHwlxizrDn5S5RyJLDu4NwFhAWkVOsjx6hqhSJ W6SNnsdmzQeVPyhquTRvwLN7RZokT0o1AwrQCNX1wzAkUdPDcKDxuyrmNnVb4fXxQvjI8x+z2q2 SL5zzIeNEUkIJYgkSGEKyYyh2Eg== X-Google-Smtp-Source: AGHT+IHrRYoaJT2bSsvCQm0KgzHTC+9vou3Twrb27dGAnsPRq6p/smDpxqBOXVH2KQKixc6awU0RqmL5lR4dZ5spFTE= X-Received: by 2002:a05:651c:2db:b0:2d3:1c52:7ae5 with SMTP id f27-20020a05651c02db00b002d31c527ae5mr1689653ljo.46.1709837121756; Thu, 07 Mar 2024 10:45:21 -0800 (PST) MIME-Version: 1.0 References: <20240304-zswap-xarray-v4-1-c4b45670cc30@kernel.org> <05cbfe34-bac1-4c16-92fa-f38b09160458@bytedance.com> <000b8cee-79cc-4f28-b180-105f2abe6b82@bytedance.com> In-Reply-To: <000b8cee-79cc-4f28-b180-105f2abe6b82@bytedance.com> From: Chris Li Date: Thu, 7 Mar 2024 10:45:09 -0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH v4] zswap: replace RB tree with xarray To: Chengming Zhou Cc: Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Yosry Ahmed , Nhat Pham , Johannes Weiner , "Matthew Wilcox (Oracle)" , Barry Song Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspamd-Queue-Id: 5416A1C001B X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: t3p6t7gx71un9ky5qd1ot7oouidm781k X-HE-Tag: 1709837126-973772 X-HE-Meta: U2FsdGVkX19RnHXcgyYFMQBIzXsx44ooAOBwlX0QBaC4ECg7lBzehK9THiuW5qM2pXYpSeGkc12ueMCxihNPGdECkRIQmdZ+UmHCG0E/Qs8qX6ga0knyQ0GOmhXKawXXFHLpDKMACOF9Map+j2ngXcO4rLwx4Zr/DkGKt+yiVcpBYVrPNNEN7yX+MClCZSJib5LL2jMDRi7OhTqOrLAjlrj4rUqUN4fCG75e4xIrYHM3wO1HSJrDsI5fl1/dbc0Wr4wMVMX9tNJyKsiHZDlPuAKOuXxNwKAXsadOAggL+7qyy+Fyi/OvGwn2tqHdWcOle/LC5ZeCAiFtehvAi5Fa6Dm54D86VGQAL50tcrLVRIbV3OxG+w9MhI5cGxHhsk76bI8MrZ0KSc0QC+Wv8FA9EP22IFX+bjviWsbtX9Qz70qKfk6cK6UM2NJF/OWpH0/i5tIYn4k+DlLyXbpeqtRGJId/YzZ05Y4FhulkI/9EqWuQEtTUt1Br7IskWOY/SUm8UIlg3Uh6TMg53++5C1Pp2K6qBZWedEUQy2bmzTUh6leWZpx/YN76vDwSRjmkd06cyQHDkabHF/JFUcBzPVdVFfaH4fabhn2w4LwYM2gK46Y0Z64fbP++B2cNacguevJrd3Z255Y14z4wUPNgLzvOvKWXXiitbWNxMzFdDKbJ6BLGkjmTAHSyCUuP0DIksuJWOsy6UEkWJEwRX6AEytbLEhXyNR8+bq+7I11/jZ4y6qhro3iBHBj9y1KT1LA+5FIqLJ8GMZ9Tb3TlG7YNmSdo22Vtn5yZufpxd5Y3/QrqpbkrrCQgevBTteaN5J9Xq3rvAyzjo9/Xc6yxxtIUPN7zkUm1mcvnuKfU02uc8upZG5FsEORmR4ZsbllacfgtJOIIvizfQfe1TVJYsfseLMdq7EET8x/6bhe9OdqSd9Obdz9SpYOTNP6nzrUGFNBOO+ApJ7ALZUSOYzzD0dxMvNR E3D00uxR u7Zd3tTL6SL1bLwQxzh3MwqMoqwAdN5e8Hkcj6uf0Mr76L/sOkLzKo9tg27NwolRknc8JPQ6e0vzlILr/9UAyJlIE6OKUY0RIWIM/+w12Hp8Ch9zczsg2eZPmuPQY5mU9ubTP8NeJFdDEK/qUf2qBGfSrM2oPWvk77TMhNoAjhJvZnsIR5+E59d9AOjxxfJvift36f0HXEn+EntK6iOT9jN034hjry3ZZZ9sV7EqXGtFx2DFynnKqiqXTk5ZUy/iXh2FLYLHvHsM6b75VQ5LEH/67v7Q4RthB9cgwQzZiWe+tHDdksH7rrisA6w1wUye//nshTeH5fgmNdrE= 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, Mar 6, 2024 at 6:17=E2=80=AFPM Chengming Zhou wrote: > > On 2024/3/7 05:12, Chris Li wrote: > > Hi Chengming, > > > > On Mon, Mar 4, 2024 at 6:52=E2=80=AFPM Chengming Zhou > > wrote: > >> > >> Hi Chris, > >> > >> On 2024/3/5 05:32, Chris Li wrote: > >>> Very deep RB tree requires rebalance at times. That > >>> contributes to the zswap fault latencies. Xarray does not > >>> need to perform tree rebalance. Replacing RB tree to xarray > >>> can have some small performance gain. > >>> > >>> One small difference is that xarray insert might fail with > >>> ENOMEM, while RB tree insert does not allocate additional > >>> memory. > >>> > >>> The zswap_entry size will reduce a bit due to removing the > >>> RB node, which has two pointers and a color field. Xarray > >>> store the pointer in the xarray tree rather than the > >>> zswap_entry. Every entry has one pointer from the xarray > >>> tree. Overall, switching to xarray should save some memory, > >>> if the swap entries are densely packed. > >>> > >>> Notice the zswap_rb_search and zswap_rb_insert always > >>> followed by zswap_rb_erase. Use xa_erase directly. The entry > >>> erase into zswap_xa_insert as well. That saves one tree > >>> lookup as well. > >>> > >>> Remove zswap_invalidate_entry due to no need to call > >>> zswap_rb_erase any more. Use zswap_free_entry instead. > >>> > >>> The "struct zswap_tree" has been replaced by "struct xarray". > >>> The tree spin lock has transferred to the xarray lock. > >>> > >>> Run the kernel build testing 10 times for each version, averages: > >>> (memory.max=3D2GB, zswap shrinker and writeback enabled, one 50GB swa= pfile.) > >>> > >>> mm-9a0181a3710eb xarray v4 > >>> user 3526.829 3526.930 > >>> sys 532.754 526.525 > >>> real 198.748 198.850 > >>> > >>> --- > >>> > >>> > >>> Signed-off-by: Chris Li > >>> --- > >>> Changes in v4: > >>> - Remove zswap_xa_search_and_earse, use xa_erase directly. > >>> - Move charge of objcg after zswap_xa_insert. > >>> - Avoid erase old entry on insert fail error path. > >>> - Remove not needed swap_zswap_tree change > >>> - Link to v3: https://lore.kernel.org/r/20240302-zswap-xarray-v3-1-59= 00252f2302@kernel.org > >>> > >>> Changes in v3: > >>> - Use xa_cmpxchg instead of zswap_xa_search_and_delete in zswap_write= back_entry. > >>> - Use xa_store in zswap_xa_insert directly. Reduce the scope of spinl= ock. > >>> - Fix xa_store error handling for same page fill case. > >>> - Link to v2: https://lore.kernel.org/r/20240229-zswap-xarray-v2-1-e5= 0284dfcdb1@kernel.org > >>> > >>> Changes in v2: > >>> - Replace struct zswap_tree with struct xarray. > >>> - Remove zswap_tree spinlock, use xarray lock instead. > >>> - Fold zswap_rb_erase() into zswap_xa_search_and_delete() and zswap_x= a_insert(). > >>> - Delete zswap_invalidate_entry(), use zswap_free_entry() instead. > >>> - Link to v1: https://lore.kernel.org/r/20240117-zswap-xarray-v1-0-6d= aa86c08fae@kernel.org > >>> --- > >>> mm/zswap.c | 186 ++++++++++++++++++++++++---------------------------= ---------- > >>> 1 file changed, 72 insertions(+), 114 deletions(-) > >>> > >>> diff --git a/mm/zswap.c b/mm/zswap.c > >>> index 011e068eb355..4f4a3f452b76 100644 > >>> --- a/mm/zswap.c > >>> +++ b/mm/zswap.c > >>> @@ -20,7 +20,6 @@ > >>> #include > >>> #include > >>> #include > >>> -#include > >>> #include > >>> #include > >>> #include > >>> @@ -71,6 +70,8 @@ static u64 zswap_reject_compress_poor; > >>> static u64 zswap_reject_alloc_fail; > >>> /* Store failed because the entry metadata could not be allocated (r= are) */ > >>> static u64 zswap_reject_kmemcache_fail; > >>> +/* Store failed because xarray can't insert the entry*/ > >>> +static u64 zswap_reject_xarray_fail; > >>> > >>> /* Shrinker work queue */ > >>> static struct workqueue_struct *shrink_wq; > >>> @@ -196,7 +197,6 @@ static struct { > >>> * This structure contains the metadata for tracking a single compre= ssed > >>> * page within zswap. > >>> * > >>> - * rbnode - links the entry into red-black tree for the appropriate = swap type > >>> * swpentry - associated swap entry, the offset indexes into the red= -black tree > >>> * length - the length in bytes of the compressed page data. Needed= during > >>> * decompression. For a same value filled page length is 0,= and both > >>> @@ -208,7 +208,6 @@ static struct { > >>> * lru - handle to the pool's lru used to evict pages. > >>> */ > >>> struct zswap_entry { > >>> - struct rb_node rbnode; > >>> swp_entry_t swpentry; > >>> unsigned int length; > >>> struct zswap_pool *pool; > >>> @@ -220,12 +219,7 @@ struct zswap_entry { > >>> struct list_head lru; > >>> }; > >>> > >>> -struct zswap_tree { > >>> - struct rb_root rbroot; > >>> - spinlock_t lock; > >>> -}; > >>> - > >>> -static struct zswap_tree *zswap_trees[MAX_SWAPFILES]; > >>> +static struct xarray *zswap_trees[MAX_SWAPFILES]; > >>> static unsigned int nr_zswap_trees[MAX_SWAPFILES]; > >>> > >>> /* RCU-protected iteration */ > >>> @@ -253,7 +247,7 @@ static bool zswap_has_pool; > >>> * helpers and fwd declarations > >>> **********************************/ > >>> > >>> -static inline struct zswap_tree *swap_zswap_tree(swp_entry_t swp) > >>> +static inline struct xarray *swap_zswap_tree(swp_entry_t swp) > >>> { > >>> return &zswap_trees[swp_type(swp)][swp_offset(swp) > >>> >> SWAP_ADDRESS_SPACE_SHIFT]; > >>> @@ -805,60 +799,33 @@ void zswap_memcg_offline_cleanup(struct mem_cgr= oup *memcg) > >>> } > >>> > >>> /********************************* > >>> -* rbtree functions > >>> +* xarray functions > >>> **********************************/ > >>> -static struct zswap_entry *zswap_rb_search(struct rb_root *root, pgo= ff_t offset) > >>> -{ > >>> - struct rb_node *node =3D root->rb_node; > >>> - struct zswap_entry *entry; > >>> - pgoff_t entry_offset; > >>> - > >>> - while (node) { > >>> - entry =3D rb_entry(node, struct zswap_entry, rbnode); > >>> - entry_offset =3D swp_offset(entry->swpentry); > >>> - if (entry_offset > offset) > >>> - node =3D node->rb_left; > >>> - else if (entry_offset < offset) > >>> - node =3D node->rb_right; > >>> - else > >>> - return entry; > >>> - } > >>> - return NULL; > >>> -} > >>> > >>> /* > >>> * In the case that a entry with the same offset is found, a pointer= to > >>> - * the existing entry is stored in dupentry and the function returns= -EEXIST > >>> + * the existing entry is stored in old and erased from the tree. > >>> + * Function return error on insert. > >>> */ > >>> -static int zswap_rb_insert(struct rb_root *root, struct zswap_entry = *entry, > >>> - struct zswap_entry **dupentry) > >>> +static int zswap_xa_insert(struct xarray *tree, struct zswap_entry *= entry, > >>> + struct zswap_entry **old) > >>> { > >>> - struct rb_node **link =3D &root->rb_node, *parent =3D NULL; > >>> - struct zswap_entry *myentry; > >>> - 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 { > >>> - *dupentry =3D myentry; > >>> - return -EEXIST; > >>> - } > >>> - } > >>> - rb_link_node(&entry->rbnode, parent, link); > >>> - rb_insert_color(&entry->rbnode, root); > >>> - return 0; > >>> -} > >>> + int err; > >>> + struct zswap_entry *e; > >>> + pgoff_t offset =3D swp_offset(entry->swpentry); > >>> > >>> -static void zswap_rb_erase(struct rb_root *root, struct zswap_entry = *entry) > >>> -{ > >>> - rb_erase(&entry->rbnode, root); > >>> - RB_CLEAR_NODE(&entry->rbnode); > >>> + e =3D xa_store(tree, offset, entry, GFP_KERNEL); > >>> + err =3D xa_err(e); > >>> + > >>> + if (err) { > >>> + e =3D xa_erase(tree, offset); > >>> + if (err =3D=3D -ENOMEM) > >>> + zswap_reject_alloc_fail++; > >>> + else > >>> + zswap_reject_xarray_fail++; > >>> + } > >>> + *old =3D e; > >>> + return err; > >>> } > >>> > >>> /********************************* > >>> @@ -872,7 +839,6 @@ static struct zswap_entry *zswap_entry_cache_allo= c(gfp_t gfp, int nid) > >>> entry =3D kmem_cache_alloc_node(zswap_entry_cache, gfp, nid); > >>> if (!entry) > >>> return NULL; > >>> - RB_CLEAR_NODE(&entry->rbnode); > >>> return entry; > >>> } > >>> > >>> @@ -914,17 +880,6 @@ static void zswap_entry_free(struct zswap_entry = *entry) > >>> zswap_update_total_size(); > >>> } > >>> > >>> -/* > >>> - * The caller hold the tree lock and search the entry from the tree, > >>> - * so it must be on the tree, remove it from the tree and free it. > >>> - */ > >>> -static void zswap_invalidate_entry(struct zswap_tree *tree, > >>> - struct zswap_entry *entry) > >>> -{ > >>> - zswap_rb_erase(&tree->rbroot, entry); > >>> - zswap_entry_free(entry); > >>> -} > >>> - > >>> /********************************* > >>> * compressed storage functions > >>> **********************************/ > >>> @@ -1113,7 +1068,9 @@ static void zswap_decompress(struct zswap_entry= *entry, struct page *page) > >>> static int zswap_writeback_entry(struct zswap_entry *entry, > >>> swp_entry_t swpentry) > >>> { > >>> - struct zswap_tree *tree; > >>> + struct xarray *tree; > >>> + pgoff_t offset =3D swp_offset(swpentry); > >>> + struct zswap_entry *e; > >>> struct folio *folio; > >>> struct mempolicy *mpol; > >>> bool folio_was_allocated; > >>> @@ -1150,19 +1107,14 @@ static int zswap_writeback_entry(struct zswap= _entry *entry, > >>> * be dereferenced. > >>> */ > >>> tree =3D swap_zswap_tree(swpentry); > >>> - spin_lock(&tree->lock); > >>> - if (zswap_rb_search(&tree->rbroot, swp_offset(swpentry)) !=3D e= ntry) { > >>> - spin_unlock(&tree->lock); > >>> + e =3D xa_cmpxchg(tree, offset, entry, NULL, GFP_KERNEL); > >>> + if (e !=3D entry) { > >> > >> Maybe "if (xa_cmpxchg() !=3D entry)" look better, so "e" variable can = be removed, > >> since we don't use it. > > > > I thought about that. The main reason "if (xa_cmpxchg(tree, offset, > > entry, NULL, GFP_KERNEL) !=3D entry)" is a long expression. Having > > !=3D entry at the end of the expression makes it harder to read. Have > > the temporary variable IMHO help reading the comparison. > > > > Not sure I understand the motivation to save a temporary variable. The > > compiler always generates temporary variables internally. Having one > > here does not affect the compiling result at all. It is just there to > > help reading. If you still think it has the reverse effect on reading > > I can of course remove it. It generates the same code anyway. > You are right, just a minor type suggestion, no much difference if you ke= ep it. Thanks for the understanding and flexibility. I agree this is more a personal flavor kind of thing, Doesn't have a big enough impact on readability which has to flip one way or the other. Chris