From patchwork Tue Apr 16 07:17:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kairui Song X-Patchwork-Id: 13631450 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 57A7FC04FF6 for ; Tue, 16 Apr 2024 07:17:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 663EC6B0096; Tue, 16 Apr 2024 03:17:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6143D6B0098; Tue, 16 Apr 2024 03:17:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 441126B009B; Tue, 16 Apr 2024 03:17:56 -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 1BDA46B0096 for ; Tue, 16 Apr 2024 03:17:56 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id D401D140912 for ; Tue, 16 Apr 2024 07:17:55 +0000 (UTC) X-FDA: 82014540510.06.9883773 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) by imf20.hostedemail.com (Postfix) with ESMTP id 36A151C0003 for ; Tue, 16 Apr 2024 07:17:54 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GRyxKPZ7; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf20.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.210.174 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=1713251874; 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=MHV2+XE+cugEfsKZfQ4KNnLWAEqkFV7dIjX6To9XLTs=; b=JMyZv0clRv0KQ8XK1PPfqhE6FJSghHxwmIFAiw3kt6rjz64Ssxjuet2ok3xpNv8rOYV7D1 dPjQ4Za3sQwekbuPXgULroc71fFPrhmld9XwPthw1CgXSw2uutNvObwlKDOkNy/KIvi6SL 6HniYioouo5fpZlQeOft9UYxPPN/Hqo= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GRyxKPZ7; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf20.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.210.174 as permitted sender) smtp.mailfrom=ryncsn@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713251874; a=rsa-sha256; cv=none; b=fRjW3zuKym2InMA9PYLsEG7S7lUDS6+EN3Y2eFhVKcPph7Kw8402SM4JlBbFr5iqIEXvuB 3898Sto7spnJm0ikwSJvJmGdpaxxYKl85Qxlb0zTDe1pyqbsaCPPmDQeNtTGKGSQS+glDJ fEg4PFZyYizbmW4SA8Zb4pc9/0jDaiI= Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-6ecf8ebff50so2692782b3a.1 for ; Tue, 16 Apr 2024 00:17:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1713251872; x=1713856672; 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=MHV2+XE+cugEfsKZfQ4KNnLWAEqkFV7dIjX6To9XLTs=; b=GRyxKPZ7oRpt/1LHGMT8pPgYPLzYxsYppYL04HoagE97dPThtQEH1m16ghwgEhHIqo bryteYWNyGOTK2uLytf85UWwFeISDXhusDl1KIyV2UZRE1Dj3XhNNMwkXGHvElFYbzJP Ff6PCBs5Stvm/wnfoc3+d3UWxRp7hYMaufWxQRbZYughlwfzStLR2FTTkBEwRkZ24Xi6 1XcoOSih8mwEJi5+03NaKrhgGESRw677G9toCLubMvokjisWWeWYTunljiAG6+kfj/NL xD1QeWjvFlOWol7H1/52Jd6obP/DjxlwFniWkT0LDcGVz8SaUBvj6vPxcY9mkSt6bBMg A1AA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713251872; x=1713856672; 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=MHV2+XE+cugEfsKZfQ4KNnLWAEqkFV7dIjX6To9XLTs=; b=mXNoJGP8HPdITKkd11mby49aYmTz3Nop2fiVNWgSOvbPrTGJcl/qbjOJHAIanFcGko sUsNRciV69ED11+2T5IYVcb1SXZcZojeaALjHoeUqQG/WRj7+noOgCoZR9pTbQ6BrtXu y3N6lc9GgaDNatoWTGeqfOj48fZHARkabqReSR91lg4H/GZaywuUSHlGa/Ox0Hs3bkZS vALlpUqsQ7auoooFneDFbJRgcfJN4erdR/9JCnHzo8Di3qvFhgmCxoK3qsU/T2noeECD uBkVpaAt19nrp2SJIvlg3BPi+Glo7+Jj6xqHaktcfLufVFP6+D1JBuy++97oPkbW3AG3 VEzA== X-Gm-Message-State: AOJu0YzHDOWLcF3PHnHDmifgB5v7aKR0H/xjQSnwkM8nquQ+7Hsla6gc uySyLR/iYTIYwyun39dWz9w21Lw241IvgCHEsuMbRagOybXpx8aQmODf1daO X-Google-Smtp-Source: AGHT+IESJwVhtcMf3m99N3mRkzrlYgFLHCki4Z3/LDKtQDjTD4+lFVo8Wfkqwv+ogYZO1JOFNTHWzw== X-Received: by 2002:a05:6a00:39a6:b0:6ea:9b37:c288 with SMTP id fi38-20020a056a0039a600b006ea9b37c288mr1644456pfb.15.1713251872585; Tue, 16 Apr 2024 00:17:52 -0700 (PDT) Received: from KASONG-MB2.tencent.com ([43.132.141.21]) by smtp.gmail.com with ESMTPSA id lr48-20020a056a0073b000b006e724ccdc3esm8340029pfb.55.2024.04.16.00.17.50 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 16 Apr 2024 00:17:52 -0700 (PDT) From: Kairui Song To: linux-mm@kvack.org Cc: Andrew Morton , Matthew Wilcox , linux-kernel@vger.kernel.org, Kairui Song Subject: [PATCH v4 3/4] lib/xarray: introduce a new helper xas_get_order Date: Tue, 16 Apr 2024 15:17:21 +0800 Message-ID: <20240416071722.45997-4-ryncsn@gmail.com> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240416071722.45997-1-ryncsn@gmail.com> References: <20240416071722.45997-1-ryncsn@gmail.com> Reply-To: Kairui Song MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 36A151C0003 X-Stat-Signature: hju37yqnohfri7r3d9njy377kp89c5po X-Rspam-User: X-HE-Tag: 1713251874-484457 X-HE-Meta: U2FsdGVkX18gJ3/oTU2Av/k5ZeGBXsztUEg7hRE/XjTzM2AERQlJDWmjRCW71aluWgXDguj4+vHj1ALvEHrf1f6eihuQiZ0DGfxlbxtkEZA7gghJOkX64dBdUOt9SrDkOej4XNgrAS+FbDs+BZicwxv8XDCqQy7FTo78xD3gEmsqqTT25y3MjBLxdrP7FSooWPBpmjsTP//ij1yqXRoDEcuajdbIe9TR7njpbU5luxkwXdJAkJl6OSX3ES9fAhdlJdd0lfJD1o9lCCIzszu4tLq+OqYCwJdg2VNQkseeFCyn2nKdVDPfklXmc8ejtz+5bGbhqMpcHlXTVDZLSgaccLiPrZInS+JuvuoZBgYUbWJX4heP7xvMV/EPHwK7XKeDLHkU+yH+yEFGXPGS+0PcQNyn4B3Fpe02KOLj7aDwWlkNrGP0+T7K6QXGJG6Uklk2U8Y30/oZwJHbE/1Ggg1+v8RuO5A+zexEsTyWTXwHQE7+80IAhj3MTXGPe7XIIAUTZlK7Q2fdFr/fv/dYcJwwb4lhk540OcHcRDS5uZ+LFB0vjtkgc3h2cBO0dXFB3R0B+vGSsVuYbLW6Sxwfil78/egx6D9GWEgHDqHm6cakU+inFplikhN6bxm/x11jXCmZWLxeHTxNh5YLjaf0+AGYAWO4/giZKlclRJ9UKZ5zdxzSdCRRZJj0nfahRwD8SFZY0+b2K40gFSyoe/9/2rQwTAN8UOlLtaALHbcBaGH5J+ZYsRVG/kXvXQLjqXE2S3bC+4Eq7m8I0D2zZZRmgSN0nHd7YXl0bfSwpTj6jV67RNvwuUmjAULEZ4yoSfARtxhiHvJQ70AN3lYLW8OBhUfkr0h5VbFtul2fcT8Ssyaos4HifM8fGCf2MUpYhgvPOoi6hzkFY7Ynke2BAaqNjz0YUokcDubISyJOiErYBtHaclaZhXIha0ghc7dTkevzPo7C+d5885Jxx9wSada7PDo OpP8gNVg RdO6efxVsg07SWpmqr5EAc0stTq4IKLFqMjkOVv+5HlwFpKHtNDBClbCpmPFt9/SeMJIZ6ZVOAgDgzx0r3nIVONx9qkn9RJsApeEnNlJv7LnHlQYxHcGiSWHguZIzpKv7hX3OOJgiJxRPxvQ/3LBRcACwccvNz9/NP6AyCpgw9YXTBL6ccIC0a4OGbUh3eZqc9wncEg0cRNaQtisYuqqpLSxSoQV7PlxTKBKQo5LKptopimxh1kkULAwrnHT7AQerN6FWbLLT9SsC5nDa71NA0gkSgGViBJDHHGkg0gELc1dSvjUYmuFnAYFwkw== 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: 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. Added new test for xas_get_order, to make the test work, we have to export xas_get_order with EXPORT_SYMBOL_GPL. Also fix a sparse warning by checking the slot value with xa_entry instead of accessing it directly, as suggested by Matthew Wilcox. Signed-off-by: Kairui Song --- include/linux/xarray.h | 6 ++++++ lib/test_xarray.c | 34 +++++++++++++++++++++++++++++ lib/xarray.c | 49 ++++++++++++++++++++++++++---------------- 3 files changed, 71 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..0efde8f93490 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1984,6 +1984,39 @@ 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)); + + for (j = i << order; j < (i + 1) << order; j++) { + xas_set_order(&xas, j, 0); + rcu_read_lock(); + xas_load(&xas); + XA_BUG_ON(xa, xas_get_order(&xas) != order); + rcu_read_unlock(); + } + + xas_lock(&xas); + xas_set_order(&xas, i << order, order); + xas_store(&xas, NULL); + xas_unlock(&xas); + } + } +} + static noinline void check_destroy(struct xarray *xa) { unsigned long index; @@ -2035,6 +2068,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..da79128ad754 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 entry. + * @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(xa_entry(xas->xa, xas->xa_node, 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;