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 B6B66C4332F for ; Tue, 12 Dec 2023 23:27:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 521268D0007; Tue, 12 Dec 2023 18:27:21 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 4D1326B034F; Tue, 12 Dec 2023 18:27:21 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3BFDD8D0007; Tue, 12 Dec 2023 18:27:21 -0500 (EST) 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 2AD776B034D for ; Tue, 12 Dec 2023 18:27:21 -0500 (EST) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 0623A1C13ED for ; Tue, 12 Dec 2023 23:27:21 +0000 (UTC) X-FDA: 81559754682.11.ABCFA82 Received: from mail-ed1-f47.google.com (mail-ed1-f47.google.com [209.85.208.47]) by imf09.hostedemail.com (Postfix) with ESMTP id 42A4D14000D for ; Tue, 12 Dec 2023 23:27:19 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=RIAf2RnC; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf09.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.47 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1702423639; a=rsa-sha256; cv=none; b=MdEphdNYGaL4Sc8ab+POc/s44OMq4alq0Q5RgS6mEIDNu7i0iXumJhnUsD8YtzDL4JmK47 JSxc/NzeJ4K7QE4+jJw3cO1JPYReni7NI+vnJZs3YX3RttMbSBVIXB+9E+8qIbliRATyJJ TQINIZ1D4sJbloprM364QwddppNugkE= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=RIAf2RnC; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf09.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.47 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1702423639; 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=gKLkSlT6twZSU8NwNcfFicELi2XwtFQzSyMdx7RHtng=; b=11g6F6Ju8BXDFQIufOI/97Ys8m8iq+d6UoJW5cvaOcgueXS8COxYG+SxZrj6gBNZnTXoQ5 Xk/WSOwsmNS1Tqbxk6hWbwPWrXeXmoKWTPJTCipqRn8WvuzdLIRGMPDiDHJcEuOahNvT2/ GcWsKPeRCmTIzlblef4H+t3eRe3BcfU= Received: by mail-ed1-f47.google.com with SMTP id 4fb4d7f45d1cf-54cb4fa667bso8868012a12.3 for ; Tue, 12 Dec 2023 15:27:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1702423638; x=1703028438; 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=gKLkSlT6twZSU8NwNcfFicELi2XwtFQzSyMdx7RHtng=; b=RIAf2RnCtvLITrUXxd6rpFyW94NwPZBAEcNEt+9MNoZdwcLeu3BOw38jZSih8fspvN SAOGlO2uRidqK4q+jrwugbOvpVzzbvelLWBzu1w/jZKEZ9CdrGo0I9YnxXKTWBffnUbT tJOE3mcTo+jfgULkq1mHGtm9Meua/1uaeK0AiIZdi6PRAEoIPlEm9t/LokKaj9yU+zks SEtwA6McmMQZG7LMfCepq0k0veRDMoJopCK6N9Sc8q6govYz0mv60jUMoKG7pZXcyhc8 4lQoG3yuPeCuB/PRkCJWkD+2H7M7MDSbGqZCBX77KfDLZbf9x9G8ZPSO2TTjL08BA+99 7hGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1702423638; x=1703028438; 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=gKLkSlT6twZSU8NwNcfFicELi2XwtFQzSyMdx7RHtng=; b=Nhsxxgg0rGFBBt+0qlBYaj0uqUOBWfQRmuCgol0nb6CPhfSr7RZFAIcW6oOwkN2N93 dOIKaOX9TjaGRgFSZAoghrEaVMUNY03dxq1cH072+0Xo+gDj6b+89oXHAlPBAGiqMHPQ Q5Tdo2aTtbDfLNOxB1oXIrXtW6qLnYvUJkhoglV8q9zGaeKoRtYSMEz5wwBs7wC3NT6k e3eBdzenZ43meFnPd4Jzw2aZ+V6baepMV7vbAIG8ZB5vo84Z2b664gS1mt4/4I8fZX2r io98dpB3zcmxTSYrff/6b7Cih78J9b/8EzsVbjrsS+DEJm6YV4hKHMUsPIwmjmah9XTu NSpw== X-Gm-Message-State: AOJu0YxzYF2pD9aUyHWfs96XvmtDFTYi6094T2fAfkTIl0WVNPnnjpuf yWGts8JXovleJFIo748EYgnxd61lhScHWv35QB0ltg== X-Google-Smtp-Source: AGHT+IEcLfbyN3sALFXpOV8inmfq4U78bPkK4T1KZHCYHRdFLvvsTNXJwOIypWMEDP7cNFZj1hDYFe6LyYq/hjCEulI= X-Received: by 2002:a17:906:7c44:b0:a19:a19b:78cc with SMTP id g4-20020a1709067c4400b00a19a19b78ccmr3383860ejp.143.1702423637584; Tue, 12 Dec 2023 15:27:17 -0800 (PST) MIME-Version: 1.0 References: <20231206-zswap-lock-optimize-v1-0-e25b059f9c3a@bytedance.com> <77d628dc-ab8c-4d8c-bc63-7e4518ea92d7@bytedance.com> In-Reply-To: <77d628dc-ab8c-4d8c-bc63-7e4518ea92d7@bytedance.com> From: Yosry Ahmed Date: Tue, 12 Dec 2023 15:26:41 -0800 Message-ID: Subject: Re: [PATCH 0/7] mm/zswap: optimize the scalability of zswap rb-tree To: Chengming Zhou Cc: Chris Li , Nhat Pham , Vitaly Wool , Johannes Weiner , Michal Hocko , Seth Jennings , Dan Streetman , Andrew Morton , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Matthew Wilcox Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 42A4D14000D X-Stat-Signature: 8z34arotpy9wh3taydom94wnotcdc3fp X-HE-Tag: 1702423639-741187 X-HE-Meta: U2FsdGVkX1+Y4AB5NhryqBC6KQPsZ4eY9EzG6UD1cBlsDfcNwhE7VXL5XjGPHkGIyMNMsAYovzGlU0VGR61it7gUnh2CW5s4h6tZFO7E62YLfP7ysk+2lqUaXIKEqpIwJfYJwcFZs58+0Wfvywh7AaYBvxCHQRRaqM0W9Oz2oqwFHBYhfdNeqFhWnoQQraRAMsXxgFBxIT4W0bNY4s4fV7Gl9ntiKfdqKul0Pyje5MVO80HDDgIqqG26xHnMCmiHrVCR/DAs5KZ8ct/mhj/EI50jGF/WFyqrRCQNq5Le2Y2vy6AltVs7uP0pDEUztcT4I/UkE0luyMD03nCXIig1MnVNVL7fxypvfQ/JVtJlV2fGAEAJP0WOFQ2e2DRRZoA73nEG3TwIS75Lv9zcJDnbRMNKf+qaVXf0xEpc8ftllUaBMpsN1/Tp0Vh8DglbzGQ+aoEyctD88hjyWg86oQHKwk/f9yjm+TKjP+nqO2w732tcb9hYbB2J3ctKyG5NnYEeGvAg/G8+3bxOSQkn+3gRiFQxmtxiQ8JzRQBPwCLXVP85AvI4dLdPuGJJIY/4/KtBoKS4ktkKidZTvAZJlXxwSoN50fDzZt0Ry1je3IP1OiKX2Rm2gFioEUh7r5UsN/c1Gr4Mi7bec56lidcnDEsynhwyuszhUIOmAXbY2aK5KAaU2NrJaS7haP02wmgvAv6XOzS2arqM9/j1XcKrTKWHU6jq2q1Dq3FvXF9ZUOL0zX3RG4oy/XOL3mS8tDTta1xhlj2fcDOegFOlfIBVVnPLr1BwRcpwMKsc0mOFwgu7v0OPGPD8/DQGhMhktyXjBqw5VZQE+fDwt4loygd922gWhLLYMPafyZZtOXZyZLKFpwhUke8E5x0cMZF/mc6dhEKq9npT7iShtpnP4CXAc5dauF1zOeiTUT3XP3HxWQN/DKm2kH0X3jreq99yOax+0kGNI58SGTninsKmNkal+iz 5CmY+dp8 rPLOf01MXv5M9SuPlAIqz6QiBKeydRs79/k0W68RST6D9ds9T0LDnwIKO8JIbpJChXoxlXAD4osq8hru7FYv5o4CDXIDegHM+hBi4nDp1Vj0rELEvQ1hcyUzGvWmWAcYdh7PlO4vnNwf9jJP3gjUFRoNOoUnub1GnDkKsq2RN8SKu6KP5Qo4E1TvP1k9HQStX3TfqQJaafIBUAhjiaVhf17ifnKQFYubhExjs1bmbesclMWEVQAvvEYq5jgUQaRc8+ZYnu35V9oKGGKrnOhgtGN2t371Xx5hGGX18n2OV4V9S1cq9EMpHWCLec8TTkO9F8Mp6yec6ul6rqy0= 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, Dec 6, 2023 at 7:25=E2=80=AFPM Chengming Zhou wrote: > > On 2023/12/7 08:43, Chris Li wrote: > > Hi Nhat and Yosry, > > > > On Wed, Dec 6, 2023 at 12:42=E2=80=AFPM Yosry Ahmed wrote: > >> > >> On Wed, Dec 6, 2023 at 9:24=E2=80=AFAM Nhat Pham w= rote: > >>> > >>> + Chris Li > >>> > >>> Chris, I vaguely remember from our last conversation that you have > >>> some concurrent efforts to use xarray here right? > > > > Yes, I do have the zswap xarray for older versions of the kernel. The > > recent mm-unstable tree has a lot of zswap related updates. Give me 2 > > days to refresh and post it. The zswap invalid entry and the reference > > count change is causing a good portion of the code to be updated. That > > is the price to pay keeping out of tree patches. My fault is not > > getting to it sooner. > > > >> > >> If I recall correctly, the xarray already reduces the lock contention > >> as lookups are lockless, but Chris knows more here. As you mentioned > > > > Yes. To be exact, xarray can use spin lock (same as current RB tree) > > or take RCU read lock on the lookup path (depending on how you call > > the xarray API). Not completely lockless but the RCU read lock should > > have less lock contention than normal spinlock. +Matthew > > > > Great! Lockless lookup in zswap_load() should reduce spinlock contention. > And multiple trees (multiple xarrays) can further reduce the contention > on the concurrent zswap_store() side. So it's complementary IMHO. > > >> in a different email, it would be nice to get some data so that we can > >> compare different solutions. > > > > Yes, it is certainly welcome to see more data points. If I recall > > correctly, the zswap xarray array makes the lookup similar to the swap > > cache lookup. It has a noticeable difference in the long tail end. > > > > Right, I post some data from yesterday in another reply. > Will test again and update the data since Nhat's zswap shrinker fix patch > has been merged into mm-unstable today. > > Thanks! Let's split the rbtree breakdown into a separate series. This series has irrelevant (and very nice) cleanups and optimizations, let's get them separately and defer the rbtree breakdown part until we get data about the xarray implementation. Perhaps the tree breakdown is not needed as much with an xarray, or at the very least the implementation would look different on top of an xarray.