From patchwork Mon Apr 15 17:18:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kairui Song X-Patchwork-Id: 13630434 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 5DBAEC4345F for ; Mon, 15 Apr 2024 17:19:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 51B936B00A3; Mon, 15 Apr 2024 13:19:22 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4A3D46B00A5; Mon, 15 Apr 2024 13:19:22 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2D1BF6B00A6; Mon, 15 Apr 2024 13:19:22 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id F0C3E6B00A3 for ; Mon, 15 Apr 2024 13:19:21 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id B8670A1777 for ; Mon, 15 Apr 2024 17:19:21 +0000 (UTC) X-FDA: 82012427322.13.FC3797B Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) by imf11.hostedemail.com (Postfix) with ESMTP id D565C40019 for ; Mon, 15 Apr 2024 17:19:19 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=WKL+jyOg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.216.49 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=1713201559; 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=cEjwwoQAn8m3grSTrvNR4sEkOR0nGA3RJ0TZjOfUHm4=; b=AOY0e9hf9Quo4Wm5fKMbV19NdY/EeikBedk4O9A/NqhhJNuvHseGC7In8G9s4pDlgbMtBP IRJ5s+YcVCb0CJWFFssXdtQryq3OayMMLvim4dTrZzadimvXGCwpq1nYhdrtg7mDeRbBuB nwKL8/w+C0bNirjzm8PBxtgUPS+OERs= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=WKL+jyOg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.216.49 as permitted sender) smtp.mailfrom=ryncsn@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713201559; a=rsa-sha256; cv=none; b=Zb4DSlanpN3Xr1AJV4qslJlTtDz8V6hZCHRYfUMgqOjc8ElSMY5rW/ZMcZ4EFpve4yu8v6 SGHYoOnBCGiyb9+pg1o6Ew/o8hTPptrrQdgdgP9HS55LEODs1WS8SwDK8tYY1l1lupLZ5h CKXCiDlWJaVmQT/+N/X8vp38hjPvtpE= Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2a475bdd4a6so1933846a91.2 for ; Mon, 15 Apr 2024 10:19:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1713201558; x=1713806358; 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=cEjwwoQAn8m3grSTrvNR4sEkOR0nGA3RJ0TZjOfUHm4=; b=WKL+jyOgVyNgz4Sp6bAk2juwaTtu8Wu8ppKjKuvondPAgGrBV15tXFwMFD2eZPffhA snVJlUB6w9ymf1lQmrEox9vXhB4g8seJF2sQTw83aNjPRIIUwooEj9Ji9fcH+9zysRZH bcPFCX4D0CIvKNehYUGGUbDnrXJnpltGnGRxOyWLcbYHPV/5Fx6m05s91ZXYPUM3UOzU sKpZ7pT54CBi8DF2zMWBax9ro8vQoL3rqP+axQX4VEOxQ1LlHGDKMGmC4XAs9aDJEXCs lOMBzcxfhH9udGTRXlYQslTrIMUlzvX4X5O/vL6jmYl811/LpJUnvXk3kaW1UAFdN2AI ryfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713201558; x=1713806358; 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=cEjwwoQAn8m3grSTrvNR4sEkOR0nGA3RJ0TZjOfUHm4=; b=KjwVu+rGns/fVgshMtApb1HaKEvkSUwotgLv88lFk4sQD6Mo57QD2bVUuV4XTSxxAB P2DCfyJ0I8iZQ1Micakzow3LK0Bua05RWpfGZ1jybH84rRLEw47ES4bEoqSf89kz4mWR XP5aOYCsrOZYgTBNzxNGm5jsqBR6qunLnyPa9aox6ymzZZm0U/LYQWXOND0MihzwzOt5 xSZZCJZLwVSuYYc548H+83gQne13pQlq1cWeH76U9gyyWrM2w33ojzGsd7orVb9DdGkP bLbI5RUIYLv9nGrh0ljmZ52PrJuVYDjsssQ/n9C4U6WKD64/05/0EdkmUVsg7p98hj7c GoVA== X-Gm-Message-State: AOJu0Yzp27E5s3lXFL9X/sylHdg/6OqNICHnsD+4lRmt/nSIh9SZcrfk e46+MrySegc89KSxAUkmAYsgLYrHP4yiLwGI6gFze/ha24EeRjtv75tFS2x4 X-Google-Smtp-Source: AGHT+IFva3FT+6Qo1iTE2UIbKwGFak0JgfA5Q5ANtjD68Wt1gDflM7XbEgZEqtWRZbI/FtzxK97aFQ== X-Received: by 2002:a17:90b:3d3:b0:2a5:ba9d:a06b with SMTP id go19-20020a17090b03d300b002a5ba9da06bmr10332693pjb.5.1713201558299; Mon, 15 Apr 2024 10:19:18 -0700 (PDT) Received: from localhost.localdomain ([101.32.222.185]) by smtp.gmail.com with ESMTPSA id o19-20020a17090aac1300b002a537abb536sm8751648pjq.57.2024.04.15.10.19.16 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 Apr 2024 10:19: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 v3 3/4] lib/xarray: introduce a new helper xas_get_order Date: Tue, 16 Apr 2024 01:18:55 +0800 Message-ID: <20240415171857.19244-4-ryncsn@gmail.com> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415171857.19244-1-ryncsn@gmail.com> References: <20240415171857.19244-1-ryncsn@gmail.com> Reply-To: Kairui Song MIME-Version: 1.0 X-Rspamd-Queue-Id: D565C40019 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: hum15b3qwmy1jud3bdgm9j3sckq13f7f X-HE-Tag: 1713201559-194207 X-HE-Meta: U2FsdGVkX1+2krcRx7wr0jnM/Dp0okAMboZ2LC/RbM5cekjlNyYh3TaHPPbZ8/Jgi5VehD/+9a9mdpYpY+HGlgtiRzcujVyEJYTlYvm74mHdRRffVlIJnXo+AObZSYjyxU4bRGkfclmmiGBqprHIdeGZTS7EFtd6sibXMCpA91/+wwLcgBoUxxTnLzX8AgMePgO3V+JBpbPuMuPWua+fzjNcQ0kTRk4dHSh2A12aXMwAc5DvixgxxzQkU9wdNeo3yRTN0Ph/zv72PaFa0Dgv4M5STJ9FDl5JQ/DlKC8I7SNX5dneBSpQPtGe+AfOl+ibhhTHPaosLFL2f+CJ/d8JuT0eYzV1BMhWRYGa8BXfgbXroS1O4nhib1/uqjmjhWZFbttmeQ03DSfLMZ0fTBsMUDwvZsPsAdYYpzh5WV6Wydhcd2/G/zAZRoNMKULRzBqYcGaawvzO9pwWkMgV8v/LldwcLOlevc7XyWdE2BcC4PNAmKROcSQlsHkgw4mjgtllcuUoxOZ2ilPJgTMeMjZWKuVzNRVlMi42sEgrMqnbWcfRkztALiBqJHkOJeGHZPA/sMFTpgAYkBxzYgl/fSWTHq7wmn1jvTGDB+H0Vp9mR4Snm5ES5d0cQGGdWvlg2Ut1flffTagXzH76Y98h/Ybzt5cYzxKNH8HKSHpfwt/wkjWIT8OevDgafdvWFaJviE2Mwb5pSdtu9dcl/5ClL15OV5RY0nX1nYwM5Kj1QX1QtC0fkvVsbJWITyyoAp5nCDBaTgECMZuSPLBj1fM4GTnL9qBYw49i+GgKwZk1meGUSpfN6AURBDQrxEouhmLYH9tGH2QH5jbKqEJRM1D/VoqDWrJP9WYdV77VcyKKSJrXp+CdpoRUwePEFt3n3vHVNinf3fa+e//cwDsScMy9Lv2z+dwKtWJC/d9V7Lr1WlwC8sTIIR12FYdcZYxAXKsl8H2XAXaawHhaojC6lejvR26 TgAXtYgw A1b9OEedcIapTnhaG3svD0Ve3W94NTBoFdJeatZcEnAdeIRHS/EVgDVNW2Oe4wZyk3aQoYHb4hU/eN4D4OOS36ko2yf7Bb6PXNeYc0VWO8bzR+7cI1M1q/CRwFm69CAutqOxh/8TN2M60AgeEb1amQ+7yVaY5mVmhxqArUokROKXmOlWupH8IQC8dd/ovF2Otiv/PDJLg7tifvV6STmiT/rfZW5rYwYeUYEgHzAZoNf5KdlRDYs610RntZTcPj3FItzpxAsL+bBFlvT7zJvV7mTuvqCmGSIRdmUbAlEnzaicwSSRShkUCEgFJ71N0grJIGjgnB0h+7UnlqtoHfec5+kyL8YbdH3bGMRl3zMBPw5+LvJTj4lHZKibgNIbqnEFOTLcxkT8FxzEE3a/4lMyiX5BshjTxmDBtE0oikUq4ul8qWBDV+tY5o45itAFCFnjcvpBMK1dG9QmsbQ3T2d9L0h6YJ+6G0Xbl6AhoG/mKjxGA8wu6CBsjvA/ejOYJT6kgiClVhpEJpPSnmYDO1HaY8wXcb9bgmExBJl08tpVNT7hRJI6qinBLqRKug8U5uEi3NArU6W8hpm0eR0883p6tN8xMyeBlfADtoCoGE/skGf3v5v9XjcIy0wXaalYSknTdgp9zxAETVu4y2HKV4tkAEa/bu230kWY4x9JS6xioTSnFKN8DTfGY81r7uEka/CeAUBF0rxv5gzUgicvJVr+6aDyn2PGyq5GxzBRS+3yYsogolc8= 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. 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 | 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..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;