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 2E421C5475B for ; Mon, 11 Mar 2024 23:31:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 66C116B0072; Mon, 11 Mar 2024 19:31:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 61B306B0078; Mon, 11 Mar 2024 19:31:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 50B6D6B0074; Mon, 11 Mar 2024 19:31:37 -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 3D6086B0156 for ; Mon, 11 Mar 2024 19:31:37 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id D9007C04AD for ; Mon, 11 Mar 2024 23:31:36 +0000 (UTC) X-FDA: 81886357392.19.ABC05A8 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) by imf04.hostedemail.com (Postfix) with ESMTP id 226F940008 for ; Mon, 11 Mar 2024 23:31:34 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=N7x7cZD0; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf04.hostedemail.com: domain of 3VpTvZQoKCHMpfjipRYdVUXffXcV.TfdcZelo-ddbmRTb.fiX@flex--yosryahmed.bounces.google.com designates 209.85.219.201 as permitted sender) smtp.mailfrom=3VpTvZQoKCHMpfjipRYdVUXffXcV.TfdcZelo-ddbmRTb.fiX@flex--yosryahmed.bounces.google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1710199895; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=0P+zg3sC3hxFlZRdvUxH346meH/XQ3eQu3bKmdXAuoI=; b=M3n4PHgzW9KIfjGOI65HzkYqZtCLKfSdBp3G8/53jaX6YxYqStQ7D0ye3Yd5TdAsyy8KNt YmFyCei76GeCg3opzDH/m7DqsoXWV8PDR1Qgqwam8mr5i9dpoLSZ5oyGEAdRX4FkHG/cHn g6y1AjhKuZZ+wPGBc/nkDqXDtpCdL7c= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=N7x7cZD0; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf04.hostedemail.com: domain of 3VpTvZQoKCHMpfjipRYdVUXffXcV.TfdcZelo-ddbmRTb.fiX@flex--yosryahmed.bounces.google.com designates 209.85.219.201 as permitted sender) smtp.mailfrom=3VpTvZQoKCHMpfjipRYdVUXffXcV.TfdcZelo-ddbmRTb.fiX@flex--yosryahmed.bounces.google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1710199895; a=rsa-sha256; cv=none; b=vpRJq31WLFgIx2Z5pnJPPxVfneSAp0AWj2yloY5F6BNYxEr9RILQrtTcu76yktPIFiymcg nL20NnKJWdVTmRjsqMBFbmNUUDlkhEn5sWIineYtQX2O9U4kt2n3g2/e/ILqUXHqTiz5Hw JhYIWridTYYneVi4JLsrGBCJIfSSv2U= Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dcd94cc48a1so8027794276.3 for ; Mon, 11 Mar 2024 16:31:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1710199894; x=1710804694; darn=kvack.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=0P+zg3sC3hxFlZRdvUxH346meH/XQ3eQu3bKmdXAuoI=; b=N7x7cZD0h3hnXZf6G7SpmE8SthwpYXBbEYAWflrCTB7HIm54GVB6ye3dBG/6HXCAwk Rmf9azsDksAJTqlj0TKI6eYzosPpVhpkLA1KKMcta6XFfHTUFjABVJuR7p0ZOUoEm1cX UTocHTXt+Uit+6StMuovMEcIZrS3z+BJUmWrrSpJNIhkrP5bFnF9dNWtZLag2AUfMNsm oudG4qXokTo6FY97QW+vena9TQml7t58VdDlGSfqmTnqMG0+7qqF/XcGfE3QjeE6rfli iGQK9QdgJG3Xsza2+mathIJ9Je6E98U066oRV9fBZfdnZ+qCMgRDMfoRFauavypocHlY lUpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710199894; x=1710804694; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=0P+zg3sC3hxFlZRdvUxH346meH/XQ3eQu3bKmdXAuoI=; b=WNOf4NXuPZoTJrYlanJwWHZPQ8b7AHJWEFXfPPuITx5CCGfdFAUh5rzDSnUmOD4IOE xTEfDMVTa0as2vufzRYtXzI5XQqmD38HyQBDIg12jnajTn9gk5Ovj0tVJUNg2OMI8Guj RgvcH0llriqJl1E2EnsvGLiF3gIzN0KmPYN6S6COY+v0qT7pLP0Vh7BdZXT71yL1CZJH MvwxfQqd2rl4chQLf/xcZMYeiKeXmFkGUyhz7mbHT8YosIqqAUcLmoXW8VVcOb9muqCv qN2w/q3aVTbIBbek8MgFMiihmnHrDkil2W5yLANh9VNpuniJ5xezrvxL412+CHZ9wWbH YQrA== X-Forwarded-Encrypted: i=1; AJvYcCUwEa3oiukBe8oTOfZPEnK6kPFe6HD4cKBtz3r5p8g0E1pvzyRkm6qbGJelJWqs0+nt7C8Ob4bC0jyJ2k8TJ0jI4Zk= X-Gm-Message-State: AOJu0YxVY0nFd1yb+HCywfp1NcuJh6FQcVYgviFZ3hgyPYZ/zG5WpUh4 qSCFPZsT4CEguRhvvkk311TswQw4g8bqYZ5+xwReK8GaXST/hkcoiQncUNqGjRAGFZbyehVOlRG PRYXR4ClSCVJuZgSn6w== X-Google-Smtp-Source: AGHT+IGMBbEsaO5zyl+K2nk3KAYXsMMJMbAJP2dlm1GfJvgnn5ewbSWdzUqwcvsox0d4zRQtSE9tqEa7YRzg451v X-Received: from yosry.c.googlers.com ([fda3:e722:ac3:cc00:20:ed76:c0a8:29b4]) (user=yosryahmed job=sendgmr) by 2002:a05:6902:1004:b0:dc7:48ce:d17f with SMTP id w4-20020a056902100400b00dc748ced17fmr2278245ybt.10.1710199894200; Mon, 11 Mar 2024 16:31:34 -0700 (PDT) Date: Mon, 11 Mar 2024 23:31:32 +0000 In-Reply-To: <20240311-zswap-xarray-v5-1-a3031feb9c85@kernel.org> Mime-Version: 1.0 References: <20240311-zswap-xarray-v5-1-a3031feb9c85@kernel.org> Message-ID: Subject: Re: [PATCH v5] zswap: replace RB tree with xarray From: Yosry Ahmed 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="us-ascii" X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 226F940008 X-Stat-Signature: 1wozacruf3yrfwkga4y9i8kyqoic18o1 X-HE-Tag: 1710199894-377200 X-HE-Meta: U2FsdGVkX19/nTZuvSdLX7cCwPHXOxf1JEjbtGo+/uei4MtUGKx4v15qBZWGS494IyAG6TVJcSzlOT1iEJm2UYX5MAJThbqzRZ9+j78JS5MpHBqZJTuEx67iH0DN3e6VkQRFE5nyrIbTbUhvJn/Bv8sXJ5ONpIXPoSSm+MpKyN98SoSEN8C9C5oQJbCwVJCrDufakIUnZGHuPH6ugXhlFnA0n0T/aaoe3QXieoXKNvz1d4mVeCd3dv98JVjbj1FbB2Y+3HPLQeGwAuXWSXOLCsC1CbYTD4y28AenbvVefO3hhLf2O5/r8rTIvjqXbqdpiFPY1qtf68PgWuO6Htv3iQbL2UU7rPrZ8auXlVnYHNBqLcoMqT8SJeIUuj73ENEglmOApWRgC9GF7z6sNZL7iWLEwl7xUMxxz4nqNnx9zBRKxxUs3G5GNQOXUjaBmXa0CIDx5QSjeCQRDXMs0Pm1rE5RgF0lo2NF6q3ddMlbJ9YjSTExEPIJpEdP/3o4PM7gBtrqQ1jvhYnw4wA2O6XBtoKwo9oU1cvzmASiNkvYWYFl3ieegMqVxNhZHTyDAqBi5ejRkrH+0RuIPil+LUysy8eV6Cuw0pA4YL6CIaQz5uScb+GevIHCjvklermlYTu+hAjto3hPb50pnYtM65Pdb8l7HLRe29dBoaBE/Dt+SbSMWXICLnaEUUCwX5Pz3CuIi+0MOvBF63paLWknzk7tfKk9XMkhK3BNE7nxuhkuEEM2bKE1FbKChwr1UyHMQR6Ewd8//dKIaVKN2goGTFEsmkmY0MlCPZbhvDoA+2q3wque6tYWLhd1MCGqcXBG8OxWP+xQyJcIcztipE69A4YmlJyaUFApg+UZjlSpst9OTyweZW82ZdKqh6hfs5/S6XMqaxoAZsEuync0sg8GiZBBt5EwJ2bgJepA4PVFx68/+L94wlyCuPWTLRTWUjqmGITsRAjdYHRNgTWnwmtCpPI jSQS8Ifz f5cquMXN6jMntBXP3BuaAicTN+CnxbQXOnAQ+moQYiHNnVUHszMLhyI/BHhTCFci/oI1Ci5U504eMaCt3yrd6/1C43FAR+9tS5efSs6qTtqwIzewJscP6jNgFk2Vgv9YHVPxKDx7AkQylUY4I7n5uyDpkdJbILDH5uxlSop+XPJfxpwTB8WmhVNzZPxQOuRF6CDbGaJTDV9E4vrU/k1R+2878YNjbHS/wm2yVUkn/KdL24vhoO7XuUo9N47Sun3PKpl/zTfqvOD4Wp11PrXbkFh3IWWlkOxXATHwQvFKaw2/Tez1AxHX/pWixvffzdNnzaEHx3bTPH2lEZmuCXTYLgSTKBR1fM+7TqXV8plxRDQGUhUwQpe5HkJCszWGft7IWHGiEFJR5zOyST3mcprW2XLSZRxs3vlxHv280wEmE40KT0w2rltEDXAY0cp7DtAKFf0oPffO+v1MZKxGWOS71WhkyTwzgT6PrMsZb9brM7BEAEZFmcuO7sAILBbQHqfu/8r0Gq+nSyJ1NPn9Pzr2Hl3+/J1haYcDfi78ANq37oDfT15RaAFzYkiJgxydP/8nUTHICWFb4fdGpJlIMbEkTa+3GnZaeN0aENyKNMK1NHf6Y0mOtZY+GJrduk5Q3nQriWybUytG3mQOu6hKzozqN/3fT72P5kNKRtLkKodvqKpGyHmy7cEiWqb2rWrThLDcv/7rG 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 Mon, Mar 11, 2024 at 03:26:05PM -0700, 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=2GB, 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 It would be more useful to show figures for the reduction of the tail latency since this is what is advertised as the main benefit. Anyway, there is a small win in the sys build time, and a *lot* of code simplification, so I like this change regardless. > > --- > > > 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-c4b45670cc30@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-5900252f2302@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-e50284dfcdb1@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_insert(). > - Delete zswap_invalidate_entry(), use zswap_free_entry() instead. > - Link to v1: https://lore.kernel.org/r/20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org > --- > mm/zswap.c | 166 +++++++++++++++---------------------------------------------- > 1 file changed, 41 insertions(+), 125 deletions(-) Nice diffstat :) Generally LGTM. With a couple of comments below, feel free to add: Acked-by: Yosry Ahmed [..] > @@ -1555,28 +1473,32 @@ bool zswap_store(struct folio *folio) > insert_entry: > entry->swpentry = swp; > entry->objcg = objcg; > - if (objcg) { > - obj_cgroup_charge_zswap(objcg, entry->length); > - /* Account before objcg ref is moved to tree */ > - count_objcg_event(objcg, ZSWPOUT); > - } > > - /* map */ > - spin_lock(&tree->lock); > /* > * The folio may have been dirtied again, invalidate the > * possibly stale entry before inserting the new entry. > */ > - if (zswap_rb_insert(&tree->rbroot, entry, &dupentry) == -EEXIST) { > - zswap_invalidate_entry(tree, dupentry); > - WARN_ON(zswap_rb_insert(&tree->rbroot, entry, &dupentry)); > + old = xa_store(tree, offset, entry, GFP_KERNEL); > + extra blank line here > + if (xa_is_err(old)) { > + if (xa_err(old) == -ENOMEM) > + zswap_reject_alloc_fail++; I think we want to WARN for any other return codes as they are unexpected?