From patchwork Thu Jan 18 03:05:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Chris Li X-Patchwork-Id: 19130 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2bc4:b0:101:a8e8:374 with SMTP id hx4csp97575dyb; Wed, 17 Jan 2024 19:07:31 -0800 (PST) X-Google-Smtp-Source: AGHT+IEus0lg1A5XvynQAqNYlVNckKR0TvCidab3k4cErmFZrkvz7ZwNYXAb3ajhZyxOjom+u4xv X-Received: by 2002:a05:6a21:7883:b0:19a:f4a6:b492 with SMTP id bf3-20020a056a21788300b0019af4a6b492mr257047pzc.6.1705547250841; Wed, 17 Jan 2024 19:07:30 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1705547250; cv=pass; d=google.com; s=arc-20160816; b=D4fEkALSsinWfGt3Qsf6JBx4foXurPKxqsrE+MneObUJ4hToLboJ1Y8tl8M74h5ITa WNo3wfseX8emjfUa1ExhppaVe+dVctxABggPvOhUugPrTZAkiNnfcnGYY4mMMpwIg1m9 9diYfFXVO86ZYoXboAMlMcRWmUSoYIBKUgwLZNQlgM0gghgq86/bsLVUSm6gRY8n+rlk bjWZf35oQDqwTprOPFTVNeNSRw+HT3dbAlJiIWE9CfHzO8sVTMkhJMiDcws49enmlrEy ukuchMOKXvwH+L56sLygQFHvF1NYmVzFkjtUTX4p3lBX/2Y1IRC/hUSJmXiIvQ5//evV w3HQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=cc:to:content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:date:subject:from :dkim-signature; bh=5t8WW2a5QmKlOvStagneE3RmRwukLHdm3rfjomiYQlA=; fh=Fm7oGaoSyaoSNy5CKYtJzzqJj4aq0AwbdWSgVNWLSu4=; b=X5KGlv+rxzZv2x+GkmNgzyOS9dpXwkdGW4r/L1u9kQlBblX2HOnUXJxL3fxwSN+Lto fK5hvPyQR1l8JJ7ZsSgHUaq5zCfUhF+hj+9841tqfaN+iOa0caxumlhyMPGLkz5rjBbX 1Az/Gly4aiWnpLlxrkxVsSdN1n63rKuXs6giNQQfVyKRoierzWhwMZrwG+hjAjJH6QVa CaWdpzf+sYWLlGr9SiGAwvwlSAfCR9hE3HJ8vz04VqoFdpoKYJlsIaIUjn1ZaXcJO/q0 PP1fINX+IGv0Lwdpyb0qHZcz9XMC5UrjKn4rIBRt8jU01A9Nuci8CZ0URyEiyjdMEj9N 0KaA== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=Fvm0Zspz; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-29678-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-29678-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [139.178.88.99]) by mx.google.com with ESMTPS id a12-20020a17090ad80c00b0028fef30ef35si675345pjv.80.2024.01.17.19.07.30 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 17 Jan 2024 19:07:30 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-29678-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=Fvm0Zspz; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-29678-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-29678-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id 58D02284813 for ; Thu, 18 Jan 2024 03:06:16 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 2DEE679D4; Thu, 18 Jan 2024 03:06:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="Fvm0Zspz" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 512F433D3 for ; Thu, 18 Jan 2024 03:05:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705547160; cv=none; b=uvOP186jsuq3Oe5xAoTSzAq5jRSI5qnBBZDsoJOde+92Xf/xp9mWbm5FUeBwAkF+qXzHri6RIUhYldHQPzd1QaZksi2cjyJLgB3oH4zfJLAdqhwF1l+3bVGLVYyxAXCvuK3OQu2f9sRL+ZroLdhKXc6CYTXzzjlbihQkPxtV2qg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705547160; c=relaxed/simple; bh=OKgJl85PBzkDLOECRXoBFZ9nSFWwN6N+G8E0iFDjg2w=; h=Received:DKIM-Signature:From:Subject:Date:Message-Id:MIME-Version: Content-Type:Content-Transfer-Encoding:X-B4-Tracking:To:Cc: X-Mailer; b=my8pc5nSg/9xbLzk5SqNgDyZwIF0DmbXB3i4Lw0oKedvX6gGvwcRIi8CzLhpzwPWlfA8E9yfItn/bV02j9hBmjHU5bcQzWXBzcYWaIhVNIKCKd8AKlhkVhbqrsfwZ0NUQHFzd5SMUC57f+MowRllVVwumROkqOWS5dsgdez8xeY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=Fvm0Zspz; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 80460C433C7; Thu, 18 Jan 2024 03:05:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1705547159; bh=OKgJl85PBzkDLOECRXoBFZ9nSFWwN6N+G8E0iFDjg2w=; h=From:Subject:Date:To:Cc:From; b=Fvm0Zspz/CNN5KQ3c3PT8DPP7tlnCcuqAG6lVMLeHgcYHdXPeaRYafbaM/Pzef+/8 xp40ZaUpHNnFQ64XyvwdFxQTxYv06XkirXjv1wIP3xzceM5JeJvnPzsJxcILCgDQdK 5A35efQm7HP3sbTsfzPNzXUWuXLbs01LJwU9cbrHvM+WEDtZc3B1XKqGUnL7kp3TIv kUrL8+dVI52kKeUSWHpc+zOINfEWIrsKvSc+44O+tuxjfu30lIDCGh22daQAxhyLS2 XIAhV78mkrVxgPzR5OMIFBpu32N2pO8rDmMds48kRbY4LRjyUTfqFBtCMy5QIa8rU4 AGn97B1AvF4sw== From: Chris Li Subject: [PATCH 0/2] RFC: zswap tree use xarray instead of RB tree Date: Wed, 17 Jan 2024 19:05:40 -0800 Message-Id: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-B4-Tracking: v=1; b=H4sIAISVqGUC/x3MQQqAIBBA0avIrBPUzKCrRAupqWZjMkJZ0t2Tl m/xf4GETJhgEAUYT0p0hArdCJh3HzaUtFSDUcYqrax80uWjzJ7Z37LXzjiFndXYQk0i40r5343 T+36OfBucXgAAAA== To: Andrew Morton Cc: 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?= , Yosry Ahmed , 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 , Chris Li X-Mailer: b4 0.12.3 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1788395914307128079 X-GMAIL-MSGID: 1788395914307128079 The RB tree shows some contribution to the swap fault long tail latency due to two factors: 1) RB tree requires re-balance from time to time. 2) The zswap RB tree has a tree level spin lock protecting the tree access. The swap cache is using xarray. The break down the swap cache access does not have the similar long time as zswap RB tree. Moving the zswap entry to xarray enable read side take read RCU lock only. The first patch adds the xarray alongside the RB tree. There is some debug check asserting the xarray agrees with the RB tree results. The second patch removes the zwap RB tree. I expect to merge the zswap rb tree spin lock with the xarray lock in the follow up changes. I can surely use some help in reviewing and testing. Signed-off-by: Chris Li --- Chris Li (2): mm: zswap.c: add xarray tree to zswap mm: zswap.c: remove RB tree mm/zswap.c | 120 ++++++++++++++++++++++++++++++------------------------------- 1 file changed, 59 insertions(+), 61 deletions(-) --- base-commit: d7ba3d7c3bf13e2faf419cce9e9bdfc3a1a50905 change-id: 20240104-zswap-xarray-716260e541e3 Best regards,