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 C7884C5475B for ; Mon, 11 Mar 2024 22:52:35 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5B9516B014C; Mon, 11 Mar 2024 18:52:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 568E36B014D; Mon, 11 Mar 2024 18:52:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 430ED6B014E; Mon, 11 Mar 2024 18:52:35 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 33AB96B014C for ; Mon, 11 Mar 2024 18:52:35 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 00A83120854 for ; Mon, 11 Mar 2024 22:52:34 +0000 (UTC) X-FDA: 81886259070.28.A1D1790 Received: from mail-ua1-f43.google.com (mail-ua1-f43.google.com [209.85.222.43]) by imf06.hostedemail.com (Postfix) with ESMTP id 57DD4180007 for ; Mon, 11 Mar 2024 22:52:33 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BHba3xy4; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of 21cnbao@gmail.com designates 209.85.222.43 as permitted sender) smtp.mailfrom=21cnbao@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1710197553; 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=sG6rccbriKueItsKjb2cJTEQoJ9sZCgOF8qwmAyEOIk=; b=uAm7ktKQcroBCbrav4V5yk/+hN8lOcTcvhQVnr2+mVZ6H6msBWkRmoaZM1BEII0h9++AQ5 Tog1czmtjfAEqtuka2hNCFG3XUTCZ5wSZ7dYh9MEg414t/r32AyNV46OYvUQCwkYgls3Tq aNIi3Y5l1mcXiJP8bmnA+vNXQAKdje8= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BHba3xy4; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of 21cnbao@gmail.com designates 209.85.222.43 as permitted sender) smtp.mailfrom=21cnbao@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1710197553; a=rsa-sha256; cv=none; b=GN6lqauod4sbN1DxYHHFzig1R61dJO7yAeMyp8xi5Stdinwzn1Okkq1r/Ciieelqwcp4Fs T8AioRQ15AxfZbBDpiPCvPrXN4Lrir37dm+/XGEq1VCQ6/AjXKGtUZJoyFIi1jV37U2oPq nrUaUGmoAvoHlo4X6qtNfZQOLw3mBBs= Received: by mail-ua1-f43.google.com with SMTP id a1e0cc1a2514c-7db994598cfso1824502241.2 for ; Mon, 11 Mar 2024 15:52:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710197552; x=1710802352; 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=sG6rccbriKueItsKjb2cJTEQoJ9sZCgOF8qwmAyEOIk=; b=BHba3xy4VhRS1HMHBppLWyY/pThwpSTwNJ4v2h2m3N1OkP1Y4F9Bz6Me4L4QuvC+0a Gjwfc/uL3wtoYmjZ9QIGLwn+O6j3Lp2Ie/uoJ7ASGkjmUDgQER077BnIZUk0OItCCggw cYIqoC6mn+DS+1DCM+AqR1ZRk4PliemnZqgak5Tc3EgcnNKApogi5zU5NhTMufQLyNke Q1LpeujvDFOx06hbooNxBVOhsQRHQ3sCwGvnBiI24npDpWQ+hsyU60L3wbGOcunhukeQ U9ps+MKzi57rxyXckcft5AnVXWkKmVIhf9YK7qYvKYgJuGre1U86vNjdSgt8VeeQBbUM phbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710197552; x=1710802352; 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=sG6rccbriKueItsKjb2cJTEQoJ9sZCgOF8qwmAyEOIk=; b=UUAiwhYq7T6QIntHTR75iwXH8vRLAB/vd13IyxWJVyQw/1l4o8H1SCkOpguL9Cow9I hj8NbVdWQ1FJcKKM0BCIJzqEluzHgZutq1ibM/aRzUGsdS5BFdGGcKeHlZvrkGShYVNN Crw/mxxP0UlWtsM14jGYBVoHGVL3HlsEiHPijag1fbraw6Fy399L0JHd8vNzBNCJ+Vyo JpbFdA5N8luPAZra4/Qnyc8Nr198oU+HDAodTJKth6chEB3Rgf06f6i9UNRVVha7vFaY HbDIdTb0KF9d2TC45IQkRD+LQER14M27MlfjwRvF3GfEV5IBrIpwOIWwebXwGLpfQrVx pDsA== X-Forwarded-Encrypted: i=1; AJvYcCUmS612ZG08yIWK9V8M2bWKqlIpzsqBwpBy7YZWzTDn69JMem2Mp6c+2S22CafymELBcL6RndHiHiBf+FT8kjyiY58= X-Gm-Message-State: AOJu0Yynr3nd8IK5QWluByeN7FmCE+YnWxaq7Yzba+3n7L8JxP6Fm/A5 USd+7MkRUX0hPnbvWPmeZ6O5kioBMiZx/OJA6KTprZQblpVnEPtbSNcwSV0iVrN3dKI5OmbnCD/ hAeP1h27QRQkERVyGhKhiRkDioI4= X-Google-Smtp-Source: AGHT+IH7qn/+9W5kdTLPVGt8Aqa7YlqUn9/0gVz+ZYZapZNofZ2SvtCNgguWY9fAufPRjGpcezwjUHJnSF0J2s4EgvU= X-Received: by 2002:a05:6102:419e:b0:473:ed7:fbc with SMTP id cd30-20020a056102419e00b004730ed70fbcmr5238749vsb.5.1710197552386; Mon, 11 Mar 2024 15:52:32 -0700 (PDT) MIME-Version: 1.0 References: <20240311-zswap-xarray-v5-1-a3031feb9c85@kernel.org> In-Reply-To: <20240311-zswap-xarray-v5-1-a3031feb9c85@kernel.org> From: Barry Song <21cnbao@gmail.com> Date: Tue, 12 Mar 2024 06:52:21 +0800 Message-ID: Subject: Re: [PATCH v5] zswap: replace RB tree with xarray To: Chris Li Cc: Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Yosry Ahmed , Nhat Pham , Johannes Weiner , "Matthew Wilcox (Oracle)" , Chengming Zhou , Barry Song Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspamd-Queue-Id: 57DD4180007 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 6ysdir6tprakuzh5md4d5zjbb7uhp7eb X-HE-Tag: 1710197553-273541 X-HE-Meta: U2FsdGVkX1/BSmz6me5HLMhNQiepdfJLNX7+jeLcN6lDgKmlo7056b8p3KYML8PmhGhrOrqSKH8LLNECuOOYmIf5gRZ7ZoXrLdFjWIjjlVNgH3ypc3816z/I7FgaCwgoVgt+QrJS/wAlXGmGx9GRaedVCRHGq66ITM+o204N8CUnogVI2tHaZT9lKE/OCm6m+FzP2I/jiz88TNOJpvL8zN9DNhE3QrwROEzAF2gxiH2BXZ6iA4WFIw2z0RWzcHSGI+DCEEPU710pMGwX09yn9pWCteYmz+NFXVuHnkZZB2h36v/ECnCbpcsNIjmm9Jow07ZvjGVggu4qZkwzL+JSRm+bt7oUuDjZGI0G2J4FBJ3/KvPen7jYVNR6xZJ/sdFSV2w21Pvy5yQWy7tR7LMXqro+MLCXxFED/1hMUFrxdMDUoXZFV6w055o7Htqj35nK3Vxv79gbHCkgcY1MVAVs4A1yL88EGhZE5qLsFMsg4Y5mfhLVZJgk/p764j+XpaHTvxisq7Yc5M7/CeB6GtOZJ30/xHLIc3h8vG0QYHAKKhAvpbcvBez/W1+gNAZ7T1ZpVRJCkIwWlY7iucttxLQhU8+2KOH4WKn9Nb1PoDunfFelBBQx5nA47q5M2g6u6kPd/Zyx+OsHBuqmVltaWCb2ltBvgrzYiJwm19Ls8buHSdvAbmOXIIwC4lyschJ3kGqGfilrCVkCCHNdl/EI90H8kt4uf0cZuHyENSQzQMmKUUttbErDZcsnYaVtBPZSmCovc6ORo3mP+JY96vWoryficol/qOF4KXhXANEJmSP0ZQWefUUcbU0FiXAWKL8M5wtEz3QFsnYNUFMvJbvqym5ypoLrhnIuBqrd1ic1rvWx9FKc+/7otKTxYnZBYVKFpRqKnX3LbmM3J3ou/jN77Qzn9rY0nQrxmjxpzxJ/ZWVJnCqgXvkCvrJ8Qgtz0a/PIt7piDXklrobJuigWAq15Fh g6Yg9w2T Ld0y1GJAdz7NJYYaNMioePNcNfCaU7+E0izt+ 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 12, 2024 at 6:26=E2=80=AFAM 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 and xa_store > directly. 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 swapfile, 24 HT core, 32 jobs) > > mm-9a0181a3710eb xarray v5 > user 3532.385 3535.658 > sys 536.231 530.083 > real 200.431 200.176 > > --- > > > Signed-off-by: Chris Li > --- > Changes in v5: > - Remove zswap_xa_insert(), call xa_store and xa_erase directly. > - Remove zswap_reject_xarray_fail. > - Link to v4: https://lore.kernel.org/r/20240304-zswap-xarray-v4-1-c4b456= 70cc30@kernel.org > > 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-590025= 2f2302@kernel.org > > Changes in v3: > - Use xa_cmpxchg instead of zswap_xa_search_and_delete in zswap_writeback= _entry. > - Use xa_store in zswap_xa_insert directly. Reduce the scope of spinlock. > - Fix xa_store error handling for same page fill case. > - Link to v2: https://lore.kernel.org/r/20240229-zswap-xarray-v2-1-e50284= dfcdb1@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_xa_in= sert(). > - Delete zswap_invalidate_entry(), use zswap_free_entry() instead. > - Link to v1: https://lore.kernel.org/r/20240117-zswap-xarray-v1-0-6daa86= c08fae@kernel.org > --- > mm/zswap.c | 166 +++++++++++++++----------------------------------------= ------ > 1 file changed, 41 insertions(+), 125 deletions(-) It appears to be a suitable figure. And LGTM, Reviewed-by: Barry Song Thanks Barry