From patchwork Mon Mar 25 17:14:04 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kairui Song X-Patchwork-Id: 13602534 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 8392EC6FD1F for ; Mon, 25 Mar 2024 17:14:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 181986B0098; Mon, 25 Mar 2024 13:14:22 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 095A26B0099; Mon, 25 Mar 2024 13:14:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DDC166B009A; Mon, 25 Mar 2024 13:14:21 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id CE8166B0098 for ; Mon, 25 Mar 2024 13:14:21 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id A2CB1A07B5 for ; Mon, 25 Mar 2024 17:14:21 +0000 (UTC) X-FDA: 81936209922.14.ACD8E3D Received: from mail-oo1-f52.google.com (mail-oo1-f52.google.com [209.85.161.52]) by imf01.hostedemail.com (Postfix) with ESMTP id CD3354001B for ; Mon, 25 Mar 2024 17:14:19 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DjnEwVbg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf01.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.161.52 as permitted sender) smtp.mailfrom=ryncsn@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1711386859; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=6sDmtk9HBtK4D63m2Orr58T2syAmM3af2Tjjpj9AWXM=; b=P5qtfPeA6/hsAvy62JyDbwbQ7b8/ezBCqqbNEX1MA8LqvH/gnvs58hHVzpqO31aNKAZBRH vpIiG0RejfgnFNl3KOz0fzxvgeXvShyosBsdRvWzeWJLuPydrXXYJzr2FK71pTlCy40NOi QyqNdTQg6xxRgm2gIkgtWzw3Gtjhy8s= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DjnEwVbg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf01.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.161.52 as permitted sender) smtp.mailfrom=ryncsn@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1711386859; a=rsa-sha256; cv=none; b=hDOr5P5h/P51cgrglCQ0L6atkH6sMU8ullqTsmlRKnfqNhaXlkl0RlYLn7+ZyeuTJSVq74 Fk3A83yaaNiFVRENCst0QWYlTHsAwcZ9Zw8/H/BzZPBxxA0nZQD6jach7gkX35LWBlwi1k hbRbm3gYtriTVCpT5LAxishVWy1eL40= Received: by mail-oo1-f52.google.com with SMTP id 006d021491bc7-5a5508007fcso572520eaf.2 for ; Mon, 25 Mar 2024 10:14:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1711386858; x=1711991658; darn=kvack.org; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:from:to:cc:subject :date:message-id:reply-to; bh=6sDmtk9HBtK4D63m2Orr58T2syAmM3af2Tjjpj9AWXM=; b=DjnEwVbgvak9k6M/KigCvaZM/pdDc6O6WV8hS9mIxODItWzcUvWl2AQwFDVjpCjwD5 ukaxd+10DSDlqPU9OqxZVO49csDgrceB+xjea08XwCcpS6JETeuPPnf87npzDLMJb7bi oSV3r2qtqzh72CbgjC2dnOL/jGdljcop67UfM8vLRQnKTnqmEuM6Khq8Rnj+wZRqDvij dQfv89N3ByxWpRpCRTMmsZrYz/+rhB0mYmfjD3jPT1zM1dP3Y7JQM9vc+nx1+JoA5OGb WENm2XK2sOyYbj7Uv3LM+UjWk7fzBlWBgeeORCdfknp/xrr5QX7ej/H9pUCBwboCIAY0 Tx1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1711386858; x=1711991658; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=6sDmtk9HBtK4D63m2Orr58T2syAmM3af2Tjjpj9AWXM=; b=dsvAFUYvUAgfHBTuWOCNy/YgeOPwetiInoYyJfxjhiYDRcReFOmtDlMjnKkdjKOLC4 mSSeVCQeH9r9jSd9S8gOqulTJ877pnkONCzv9BwSp6FivEniWGS+7IJpa0a6yXwJpEf/ NNVg+9R8TveOfn2Nov3ZbryY4lW8bI4u/170mN53ssevTPWyqDqMj1D6kIgAD7rlv9c9 gc7cBE4J3x1bZJiJ5Y3M6+6WuMlxAGKseSOC9mxOpvBy3Jkan7bR/IktfGo8wvnm+Dfb IHAaevcG8HUniIfj15YNihyBMXL3I3WH+/9Zk5b98ZT9tCdscfYu31yPUtjH/yVwzHJl /TTg== X-Gm-Message-State: AOJu0YzkIjNm89UXb8EztZEhHTYypgFPwYyPKrYYhRFqldka2sUTSstc sp+hnchPwq4gL3B0XLjRjroxYvyhqHn/XNuXye9hefnoROoFElTq98tEooMbdKuQfgV6 X-Google-Smtp-Source: AGHT+IH812g8lEhOIH3UUXbXCSKLPkSjpe82QohMIQkOyOH031CL/t5qi83Q7yr/40ax5hVVYS2Ijg== X-Received: by 2002:a05:6358:3996:b0:17e:9ca7:c3a2 with SMTP id b22-20020a056358399600b0017e9ca7c3a2mr9245069rwe.21.1711386857956; Mon, 25 Mar 2024 10:14:17 -0700 (PDT) Received: from KASONG-MB2.tencent.com ([115.171.40.106]) by smtp.gmail.com with ESMTPSA id r16-20020a63d910000000b005dc5129ba9dsm6001812pgg.72.2024.03.25.10.14.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 25 Mar 2024 10:14:17 -0700 (PDT) From: Kairui Song To: linux-mm@kvack.org Cc: Matthew Wilcox , Andrew Morton , linux-kernel@vger.kernel.org, Kairui Song Subject: [PATCH v2 3/4] lib/xarray: introduce a new helper xas_get_order Date: Tue, 26 Mar 2024 01:14:04 +0800 Message-ID: <20240325171405.99971-4-ryncsn@gmail.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240325171405.99971-1-ryncsn@gmail.com> References: <20240325171405.99971-1-ryncsn@gmail.com> Reply-To: Kairui Song MIME-Version: 1.0 X-Rspamd-Queue-Id: CD3354001B X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: naoxczh7tnjo9ztxdnhqcpmu1zsucrci X-HE-Tag: 1711386859-978621 X-HE-Meta: U2FsdGVkX1/Za2VtcPCbdFtpU/FE4Og2opc1PAVw7vXwnHe+vjIeEnhTy+Luc25TLNJgjbBE2qvLFl8YrfAQdgcSoORK+0QBx7+qVJsHRI0QZh8b+HvxyqRHLm6bEGb8E+L0VY69dXMMnt78x/y6K7y1CmTT1BoB1J39gsPeipMK1cEiIIg8vvzfXA4AujybB+rxUu04dARlMZp4n7BP28DZeT9wsLlhJIY8lFKqDMpFZDM2QPMvUhh0cvX4oMghRtSubZmtuTRg3QZCRCE3AntyIIuT2f5GviDZfTkjKSCIP2bUAkC8NkWrJEDDXOuDPVLVqwdIdZyxy2hB7q6AsZqb05r0wkNcgRwBm+8/lD9NuLMTkaEKDK4uiFr3lLxf1OcIAJbCqOeKWHCUeh0bdLrXiWPsNeUT/KnaC+S8vuLxWo85x822M113oEX/ukSv5mK2mgtUbE2ts1UOBkSnXNCt7qgjKfTx0FsSSgM17deZqy4+4UiDKDl9b1goXPgMAazaD35UJr/SgsHiUfMVW91EoVrbNj5YTbU8lPnVAaDg8+BOm3koF22vyAgJPbAxylGvHBVsGD0khtqisfKe2RX8f4qg3OUpZdqB+epBksWq59hfsbsRkG7WGXcecXThcpN77QH+Elch3TGce6Nl7yWWKWHtMbpWOiqxt8woRVRlpsPamCH6fLRdFo3/r7yHcWxylxOrwToM7izs+JMGGnp5Yml44GqIZ0rIMWeBxktP65gGXmGXoNPdM4pyM/T61CYtJosM64louwsY6+92b1jeKr4aVvWO0+7IVM5auOTfXXvXWdEnaAGWmHUym/pXbLj+uwHCTH3YtNz3eohQW5+7sANug4cmvwBkealZIQy1YeRjYH1ISovDZboaTiwzwmq6ctb31YaGFjXNcx/QtCpr8Qx56bYdqz1Vd4wzv8bpu5hFlL/nVPnB1TK1wscMlqIV2hgATFSpJ4IjaTl fZeyUFMm ktmcMx+C7wb+K9HAGYlPrvW++4+bJC2U38ejMFcexB7m1U2wb9hEZiVQmEXgyaHDg0XKj7/2+LS+fS9sibcG9yUoqDySvqmv/ifN6Yh2ZOETQmLd062DOx7XiKzAUyyaJflPpOILh1j8iM+uN4Y/84AqqR2cPgVzGAPYB2B5453z60RvaXXMy0fXRwaHFn0Ito+9GNLvSgvY0WOmoXVD2H3LEGdmT5+4vSaSBBOJoWwzmVykdy8hUqVZTsUBow0zqCqY7vEtf90Jm2OmIN4IG2G+pfKNFnJgZzNNwucPH+wquXtud0iX69sCv7xzgBrGfNOKC4M120jZ8muLMwQT8Gb6Ebi5URoWcAAtjGD+W2fj1YlDpkR3bB8Sig9t5dNcOoQRfHeTFdMr5XHlohdTXzi2HUSmkZWiXLoF6mW+XxEAJBuVKcD7jcP/ckxN1W0qlG571ljP1POcJI1/N0lY15kljPt9utFtzlbGow6fIZTs40PloqeYuMHYieiksWiSApNM8AZ2H+llcLzl+5MduUPBJLCQX9z0/QOHLbh14iAyOTad9dxPPdotf4ldxpAVLIx6cwMoqDf89Q1p6ekaR6bIGTy2Sk8Q0ZNzLHokEDBY2zsWj65a51WuLiDkNQpG4UdIl6FTRq8QtzlBCGdcsjqMjsxcLSBZt6aI4u3imQxSuanE= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000015, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Kairui Song It can be used after xas_load to check the order of loaded entries. Compared to xa_get_order, it saves an XA_STATE and avoid a rewalk. Also add new test for xas_get_order, to make the test work we have to export xas_get_order with EXPORT_SYMBOL_GPL. Signed-off-by: Kairui Song --- include/linux/xarray.h | 6 ++++++ lib/test_xarray.c | 32 +++++++++++++++++++++++++++ lib/xarray.c | 49 ++++++++++++++++++++++++++---------------- 3 files changed, 69 insertions(+), 18 deletions(-) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index cb571dfcf4b1..d9d479334c9e 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -1548,6 +1548,7 @@ void xas_create_range(struct xa_state *); #ifdef CONFIG_XARRAY_MULTI int xa_get_order(struct xarray *, unsigned long index); +int xas_get_order(struct xa_state *xas); void xas_split(struct xa_state *, void *entry, unsigned int order); void xas_split_alloc(struct xa_state *, void *entry, unsigned int order, gfp_t); #else @@ -1556,6 +1557,11 @@ static inline int xa_get_order(struct xarray *xa, unsigned long index) return 0; } +static inline int xas_get_order(struct xa_state *xas) +{ + return 0; +} + static inline void xas_split(struct xa_state *xas, void *entry, unsigned int order) { diff --git a/lib/test_xarray.c b/lib/test_xarray.c index ebe2af2e072d..26e28b65d60a 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1984,6 +1984,37 @@ static noinline void check_get_order(struct xarray *xa) } } +static noinline void check_xas_get_order(struct xarray *xa) +{ + XA_STATE(xas, xa, 0); + + unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; + unsigned int order; + unsigned long i, j; + + for (order = 0; order < max_order; order++) { + for (i = 0; i < 10; i++) { + xas_set_order(&xas, i << order, order); + do { + xas_lock(&xas); + xas_store(&xas, xa_mk_value(i)); + xas_unlock(&xas); + } while (xas_nomem(&xas, GFP_KERNEL)); + + xas_lock(&xas); + for (j = i << order; j < (i + 1) << order; j++) { + xas_set_order(&xas, j, 0); + xas_load(&xas); + XA_BUG_ON(xa, xas_get_order(&xas) != order); + } + xas_unlock(&xas); + + xas_set_order(&xas, i << order, order); + xas_store(&xas, NULL); + } + } +} + static noinline void check_destroy(struct xarray *xa) { unsigned long index; @@ -2035,6 +2066,7 @@ static int xarray_checks(void) check_multi_store(&array); check_multi_store_advanced(&array); check_get_order(&array); + check_xas_get_order(&array); check_xa_alloc(); check_find(&array); check_find_entry(&array); diff --git a/lib/xarray.c b/lib/xarray.c index 39f07bfc4dcc..fbf1d1dd83bc 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1750,39 +1750,52 @@ void *xa_store_range(struct xarray *xa, unsigned long first, EXPORT_SYMBOL(xa_store_range); /** - * xa_get_order() - Get the order of an entry. - * @xa: XArray. - * @index: Index of the entry. + * xas_get_order() - Get the order of an loaded entry after xas_load. + * @xas: XArray operation state. + * + * Called after xas_load, the xas should not be in an error state. * * Return: A number between 0 and 63 indicating the order of the entry. */ -int xa_get_order(struct xarray *xa, unsigned long index) +int xas_get_order(struct xa_state *xas) { - XA_STATE(xas, xa, index); - void *entry; int order = 0; - rcu_read_lock(); - entry = xas_load(&xas); - - if (!entry) - goto unlock; - - if (!xas.xa_node) - goto unlock; + if (!xas->xa_node) + return 0; for (;;) { - unsigned int slot = xas.xa_offset + (1 << order); + unsigned int slot = xas->xa_offset + (1 << order); if (slot >= XA_CHUNK_SIZE) break; - if (!xa_is_sibling(xas.xa_node->slots[slot])) + if (!xa_is_sibling(xas->xa_node->slots[slot])) break; order++; } - order += xas.xa_node->shift; -unlock: + order += xas->xa_node->shift; + return order; +} +EXPORT_SYMBOL_GPL(xas_get_order); + +/** + * xa_get_order() - Get the order of an entry. + * @xa: XArray. + * @index: Index of the entry. + * + * Return: A number between 0 and 63 indicating the order of the entry. + */ +int xa_get_order(struct xarray *xa, unsigned long index) +{ + XA_STATE(xas, xa, index); + int order = 0; + void *entry; + + rcu_read_lock(); + entry = xas_load(&xas); + if (entry) + order = xas_get_order(&xas); rcu_read_unlock(); return order;