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 8ABDEC6FD1F for ; Tue, 26 Mar 2024 18:49:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 038456B0092; Tue, 26 Mar 2024 14:49:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F2A786B0093; Tue, 26 Mar 2024 14:49:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DFD196B0095; Tue, 26 Mar 2024 14:49:39 -0400 (EDT) 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 CFC136B0092 for ; Tue, 26 Mar 2024 14:49:39 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 9FC3AA11D5 for ; Tue, 26 Mar 2024 18:49:39 +0000 (UTC) X-FDA: 81940078878.21.31BFCCD Received: from mail-lf1-f52.google.com (mail-lf1-f52.google.com [209.85.167.52]) by imf02.hostedemail.com (Postfix) with ESMTP id A6EDF80007 for ; Tue, 26 Mar 2024 18:49:37 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=KNseh3yK; spf=pass (imf02.hostedemail.com: domain of yosryahmed@google.com designates 209.85.167.52 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=1711478977; 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=7mynrQyLYQKIvyzb5pPjoeLmjvmkiY75j1id5hI0x/A=; b=5LlJyxDgaKPeQOfx37Qf68BBvlJgvYLFvDzS4WNvpbeoB4JblNKf93xWy1DAv7g0WFJKVi ducqp+193lBxkVssUSIFDXu22bZhHjsnTrGbu2qZkRD5cL/TLaAkkNrWD2+S2cXnTIBfWN 0ZPdQ3TbThOJq2ShAl/J7ktBeRUnPY0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1711478977; a=rsa-sha256; cv=none; b=QlWeUkYesjBqOlLpCox+tkY46WqlPTlHIHJzdfJddOIthIKbhXW7hqEeAXng6AOC3CFua5 8DET/AKvtp5676TsOZ4vwXVUMwj61nbA+axWMpjpLtRuVmhHqiOqw/Q11UpMnkke/EcG96 ZLdD1lc65cEVYWFanWzWfwCZooDqCIE= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=KNseh3yK; spf=pass (imf02.hostedemail.com: domain of yosryahmed@google.com designates 209.85.167.52 as permitted sender) smtp.mailfrom=yosryahmed@google.com; dmarc=pass (policy=reject) header.from=google.com Received: by mail-lf1-f52.google.com with SMTP id 2adb3069b0e04-515a81928a1so4584186e87.3 for ; Tue, 26 Mar 2024 11:49:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1711478976; x=1712083776; 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=7mynrQyLYQKIvyzb5pPjoeLmjvmkiY75j1id5hI0x/A=; b=KNseh3yK+jLBb6ajbNZJxXzr4FCtgsrPOqqZP4ekCpb7eiMrdhi752gvNlR63l740p emPfKj2Vu5T4JA3R0WUaN4pm3BKD9qPgAE/qB0xFP6n9/dOUQ5cHW8phQGl/ZefFAjqj +bMx83r83wzVo4CG8rrgv63Y3W3rf4qMfjDdtsRc2lTE+X+N3r6EjwV8aubG2Jp8pEJC vKvzUTFD1fMn2istEKDlUxyyC1nl0egWSxVyI6dTNuUm7az5k/YWYIcHv/5J54XdZ/NQ vXOE27O/hfaX5cZXkgSvLVTLzEUm/KiLZXJl1jQvMOKRpMffs6OOB4Y2x3PDoARQ0kZh DpEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1711478976; x=1712083776; 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=7mynrQyLYQKIvyzb5pPjoeLmjvmkiY75j1id5hI0x/A=; b=ICA/JoA5rnx7gayq8JLHQcDo9jSTiVNg0a6o6UsSTUV/GynjHCyV2euPQZC9Hrhftt 19q79V8rN6iiq5g1cWWpKOOCsUfVxLCjAV1LifiLYHYuo44E38tLwxWPgVJYtTzelYdJ FtRJL/nx6HtPgthVKATeH8+KTyMenhCs+i4HF+yHp2K6+AGJdg9+Vcpvq+2rLsN9LHvv WuxNem0Z0GvNwUZBaMjepMwAja7wVZW0OLX6x4o1P5lVItebhF4tq0vUOG4fU6OiMZSO laB8Ya9kgvgj2vANcmgivcCBYbPSg9a0ZIAphDL3xQqCPJrxrH/n01Ckhv9yae2CVghw r8VQ== X-Forwarded-Encrypted: i=1; AJvYcCV7/ojjmCK7ix0hIbJ/dqiIAjaI6fxv+b0z1PY/pdpLCiVFJfJqsI3sopvd/LmHwYjIVXCklBMXh/s8SvrL9qwdVgM= X-Gm-Message-State: AOJu0Yz+UQMC5b4CpNnOvWHZy9ZY3l45xxehArN0EzgXGiq96aAfBKzT vb84fP1Ox0JRVjfy4qgNNyx5/FXDlekbF1/LN0TXGmqDrQqbwAQ3cZcBrcUs9NA5idCAwtiiO9j XjJTsliceBy5gIo04N19/2oVZ/7DOFGLZkazi X-Google-Smtp-Source: AGHT+IGadDByxC5Y8jsYw2G3ELZW4f5s1LwSvVhbepIXimyXtqmvP0RJWH5b0K5i33DD9xw9b2Q8/zpYp0ntt35t/Qg= X-Received: by 2002:a19:5e47:0:b0:513:c2e3:226e with SMTP id z7-20020a195e47000000b00513c2e3226emr341221lfi.8.1711478975472; Tue, 26 Mar 2024 11:49:35 -0700 (PDT) MIME-Version: 1.0 References: <20240326-zswap-xarray-v9-1-d2891a65dfc7@kernel.org> In-Reply-To: From: Yosry Ahmed Date: Tue, 26 Mar 2024 11:48:57 -0700 Message-ID: Subject: Re: [PATCH v9] zswap: replace RB tree with xarray To: Chris Li Cc: Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Nhat Pham , Johannes Weiner , "Matthew Wilcox (Oracle)" , Chengming Zhou , Barry Song Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Stat-Signature: 53t8abad5rag1ozhhtt6hynseaa19i4f X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: A6EDF80007 X-Rspam-User: X-HE-Tag: 1711478977-54870 X-HE-Meta: U2FsdGVkX1/k8y9La0AGqEYHB5jWC4QOAOEAwz9c8VbPCibo3vOptEmCWfsjmalel3zIvzk34v28tGLjQDDoFF/2AZhgKKtCxXdtbDD7Z5vvegr4IYDkveiOtm1wDRX46M/4XUF12hXkL2Ne1of8H5eU9cce/1/R2WPo98z06z2ILE6uF/LVY6rIi7XEloaZqeY+lcuZ/jdp1e18YsZU/JKans23AuanBDMbtT/4PmAc1ulGJFTyxEDxfJVjyG3dt266qOK5HO5IIj9HJFuNhx8hPl0Q16ZIZJqcFvJFuBMSx7/aDB9C16l9Szzfx23556kiRWstMethWS9dIBNHO+COK6bKClTL7oin47asy/UiJerfwQRgECAWXrOmjfV11tDC9pAMOCbUwrOYY8NaFebnP69t7UWaKIs7oKQ6Ab+8L5CT/VR82UU17+ppEo0WPLoM9eqNudldaSzipTd0aMwmBrOHFC6KTOXyF8IawGZt2XDTgV7QI2fSrufA1XDn+eBS7+bjTzewvj7Q1rIvAbCADfstyS0Lm+ZkFSjmc1NJUKpLJnbcLr90hTuMt+uhXnJMr4k021U45h7LZR0GM1UyIYjLWPK2Vn1YawFPzxMdVlFZtk491LwBDfNTo+sgQG9s9F7DEsdfjYrJqhgGfvBL88V3ezBXsWnXrXEZUPDykN0zpBp9mqQyakxONGF8SOK0OkOhY4ViJjBMqgp2zZYqqARjviRrrehCiM/yYt13/dnYHUuKGRE9Kxizx4S1OYQq1XDuOGMs8LiZdET6WoIlXIP8XKl95sT0JjP0cBaXsdGJfBZfEp39jnzZzHd6mH6Bdi4zolVxtVILLXKi9xaVDShRm0S8AppOn3G9q2uu+sBt6WXBKwXUPeLwsnSl4HVI3rK7iTazUV26ycatAdYJVgXN5Uyf3UITYHQjVLg0Tcs1Bzma8vbPecHN2Prm4AL+9FXp5xQN5xxE4F8 FOVxop4c wE/zSTX4fIlOl2velr9VVSwEoXX4gMba7TRaAIgNueCYR+LgEAdGrsU2DcKuLDWOc6TpCrHpHM79NTSWFdBiPWXJJvq+4YZwzoX4MwG6p8ZjUC8aa1gKmnHJmd8L1qtJUWo6JEn0dWVuuY1xd7BZoLLEysZGeDm2Ach9e+zESBHHWprfm8mLE93CqZz2a8SlDXLy5MmX9NYBhRLOTydQzlLGIu/200FFWPn8zuEHsd6Vy67i+GTzpJYQpMIhaLCtSpSbKf1oybZo3GzF8NtXbKJGLwv5zuUPJcSQ5+Sm0QVXEp7poQBGQM0Nh/w== 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 Tue, Mar 26, 2024 at 11:42=E2=80=AFAM Chris Li wrote= : > > On Tue, Mar 26, 2024 at 11:35=E2=80=AFAM Chris Li wro= te: > > > > 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, whil= e > > RB tree insert does not allocate additional memory. > > > > The zswap_entry size will reduce a bit due to removing the RB node, whi= ch > > 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 f= rom > > 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 often followed by > > zswap_rb_erase. Use xa_erase and xa_store directly. That saves one tr= ee > > 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 5 times for each version, averages: > > (memory.max=3D2GB, zswap shrinker and writeback enabled, one 50GB swapf= ile, > > 24 HT core, 32 jobs) > > > > mm-unstable-4aaccadb5c04 xarray v9 > > user 3548.902 3534.375 > > sys 522.232 520.976 > > real 202.796 200.864 > > > > Signed-off-by: Chris Li > > I remove the previous review tags because I like to get some review of > the conflict resolution as well. [..] > > @@ -1624,20 +1562,14 @@ bool zswap_load(struct folio *folio) > > pgoff_t offset =3D swp_offset(swp); > > struct page *page =3D &folio->page; > > bool swapcache =3D folio_test_swapcache(folio); > > - struct zswap_tree *tree =3D swap_zswap_tree(swp); > > + struct xarray *tree =3D swap_zswap_tree(swp); > > struct zswap_entry *entry; > > u8 *dst; > > > > VM_WARN_ON_ONCE(!folio_test_locked(folio)); > > > > - spin_lock(&tree->lock); > > - entry =3D zswap_rb_search(&tree->rbroot, offset); > > - if (!entry) { > > - spin_unlock(&tree->lock); > > - return false; > > - } > > /* > > - * When reading into the swapcache, invalidate our entry. The > > + * When reading into the swapcache, erase our entry. The > > * swapcache can be the authoritative owner of the page and > > * its mappings, and the pressure that results from having two > > * in-memory copies outweighs any benefits of caching the > > @@ -1649,8 +1581,12 @@ bool zswap_load(struct folio *folio) > > * the fault fails. We remain the primary owner of the entry.) > > */ > > if (swapcache) > > - zswap_rb_erase(&tree->rbroot, entry); > > - spin_unlock(&tree->lock); > > + entry =3D xa_erase(tree, offset); > > + else > > + entry =3D xa_load(tree, offset); > > This is the place I make the modification for the conflict resolution. > It depends on the swapcache to execute xa_erase() or xa_load(). > Obviously, the xa_load() will not delete the entry from the tree. The conflict resolution LGTM. If this is the only change from v8 then: Acked-by: Yosry Ahmed