From nobody Sun Apr 19 04:23:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 45003C43334 for ; Wed, 6 Jul 2022 18:23:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233721AbiGFSXJ (ORCPT ); Wed, 6 Jul 2022 14:23:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35824 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230496AbiGFSXF (ORCPT ); Wed, 6 Jul 2022 14:23:05 -0400 Received: from mail-qt1-x833.google.com (mail-qt1-x833.google.com [IPv6:2607:f8b0:4864:20::833]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 51927275DF for ; Wed, 6 Jul 2022 11:23:04 -0700 (PDT) Received: by mail-qt1-x833.google.com with SMTP id ck6so19426498qtb.7 for ; Wed, 06 Jul 2022 11:23:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=YcIiYRUAkK4hThsiTUmcop0uj0NkU+EnxuUcvjeiwcw=; b=PfDnBaOf9rzqGm8iXPrycR1x+cGtlYAYfxRqPqbkAACdi8hIvPUpaak9PRr3rtVpjt xiVVI5XpP1c+k7HKpSE1Ly079Dw5r4Z6MXuQ3FtGCOjtGzrKSZwYqJMDAoct76RQVyRR QsTyNK2RSXrnhSL4qPhI4P7M8ltqtOVar4UKYcxFkq69E1iMOe7wN5TIbOVdm3fuh+Si t1TAj++2+VfHxN3xoQXIK4o8Dah8jxheRulwm4bRXhUUfWA3wPLFnB+o7VU3AgP060gY LvjFxCpVzAwII+FV/G2obR3QZpeWQhv5PnyPtchaD63oCvH5u3yfFIKklHN1bHjftHlu fivw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=YcIiYRUAkK4hThsiTUmcop0uj0NkU+EnxuUcvjeiwcw=; b=buZO0cIEAVB+0SDXvIeqlB6H/BL4/pBvg+ApEoba+kYaV4Re0hAr9ZO2hLydCVJfPe hr7iORO59BKbO0S+C7yOb3W4L6I04LsPeofyr/D1cxwcQquoBSxj1GpVFNK2BbwZ7gt9 tT92SZ1tDKf7ZYOS1vlymZSsfDp53NjEC30mFnuYfkNM/DQCtVO57FKzcSHnG8lWTIrQ CMmy+dwv5eZQfVuL3h93HUtCmID6nhcoPnkSjij0qxs+450l9BoKBb/zv68IxNn6yPJN 9SFeIA/QgsI03ydvU3O9m6QRBDpachD1MifDEl0wcAtJlDFe+cdns9PJUSI4ONLlvNvp wcyg== X-Gm-Message-State: AJIora/KJ14kWyHz+NMh1pz1ld8BAeLoL54hCCk3Qq3FGDrf3HF0iFaD neJ8tr3Qs2T6PvvvVvMABhBibTOWfk2trQ== X-Google-Smtp-Source: AGRyM1s4/Oompt0Y1loOAPg2Pry4nWKDsKMkqnqHtOmUpMzV0ZX2xJrG/qavihtlYy7V4KYIDq7D2w== X-Received: by 2002:a05:622a:386:b0:31d:4c75:6f63 with SMTP id j6-20020a05622a038600b0031d4c756f63mr14466710qtx.404.1657131783280; Wed, 06 Jul 2022 11:23:03 -0700 (PDT) Received: from localhost (c-69-254-185-160.hsd1.fl.comcast.net. [69.254.185.160]) by smtp.gmail.com with ESMTPSA id b14-20020ac84f0e000000b00317c3ce1f4esm24299121qte.45.2022.07.06.11.23.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 Jul 2022 11:23:03 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= Cc: Yury Norov Subject: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit() Date: Wed, 6 Jul 2022 11:22:56 -0700 Message-Id: <20220706182300.70862-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706182300.70862-1-yury.norov@gmail.com> References: <20220706182300.70862-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Kernel lacks for a function that searches for Nth bit in a bitmap. Usually people do it like this: for_each_set_bit(bit, mask, size) if (--n =3D=3D 0) return bit; We can do it more efficiently, if we: 1. find a word containing Nth bit, using hweight(); and 2. find the bit, using a helper fns(), that works similarly to __ffs() and ffz(). fns() is implemented as a simple loop. For x86_64, there's PDEP instruction to do that: ret =3D clz(pdep(1 << idx, num)). However, for large bitmaps the most of improvement comes from using hweight(), so I kept fns() simple. New find_nth_bit() is ~70 times faster on x86_64/kvm: for_each_bit: 7154190 ns, 16411 iterations find_nth_bit: 505493126 ns, 16315 iterations With all that, a family of 3 new functions is added, and used where appropriate in the following patches. Signed-off-by: Yury Norov --- include/linux/bitops.h | 19 ++++++++++ include/linux/find.h | 79 ++++++++++++++++++++++++++++++++++++++++++ lib/find_bit.c | 20 +++++++++++ 3 files changed, 118 insertions(+) diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 7aaed501f768..86072cfcbe17 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word) return __ffs((unsigned long)word); } =20 +/** + * fns - find N'th set bit in a 64 bit word + * @word: The 64 bit word + * @n: Bit to find + */ +static inline unsigned long fns(unsigned long word, unsigned int n) +{ + unsigned int bit; + + while (word) { + bit =3D __ffs(word); + if (--n =3D=3D 0) + return bit; + __clear_bit(bit, &word); + } + + return BITS_PER_LONG; +} + /** * assign_bit - Assign value to a bit in memory * @nr: the bit to set diff --git a/include/linux/find.h b/include/linux/find.h index 424ef67d4a42..00a24bc596d0 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -12,6 +12,8 @@ extern unsigned long _find_next_bit(const unsigned long *= addr1, const unsigned long *addr2, unsigned long nbits, unsigned long start, unsigned long invert, unsigned long le); extern unsigned long _find_first_bit(const unsigned long *addr, unsigned l= ong size); +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned lon= g *addr2, + unsigned long size, unsigned long n, bool not); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsig= ned long size); @@ -125,6 +127,83 @@ unsigned long find_first_bit(const unsigned long *addr= , unsigned long size) } #endif =20 +/** + * find_nth_bit - find N'th set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, = unsigned long n) +{ + if (n =3D=3D 0 || n > size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return _find_nth_bit(addr, NULL, size, n, false); +} + +/** + * find_nth_and_bit - find N'th set bit in 2 memory regions + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned = long *addr2, + unsigned long size, unsigned long n) +{ + if (n =3D=3D 0 || n > size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr1 & *addr2 & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return _find_nth_bit(addr1, addr2, size, n, false); +} + +/** + * find_nth_andnot_bit - find N'th set bit in 2 memory regions, + * flipping bits in 2nd region + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsign= ed long *addr2, + unsigned long size, unsigned long n) +{ + if (n =3D=3D 0 || n > size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr1 & (~*addr2) & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return _find_nth_bit(addr1, addr2, size, n, true); +} + #ifndef find_first_and_bit /** * find_first_and_bit - find the first set bit in both memory regions diff --git a/lib/find_bit.c b/lib/find_bit.c index 1b8e4b2a9cba..7b8ad12c8cc7 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr,= unsigned long size) EXPORT_SYMBOL(_find_first_bit); #endif =20 +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned lon= g *addr2, + unsigned long size, unsigned long n, bool not) +{ + unsigned long val, idx, w; + + for (idx =3D 0; idx * BITS_PER_LONG < size; idx++, n -=3D w) { + val =3D addr1[idx]; + if (addr2) + val &=3D not ? ~addr2[idx] : addr2[idx]; + + w =3D hweight_long(val); + if (w >=3D n) + return min(idx * BITS_PER_LONG + fns(val, n), size); + } + + return size; + +} +EXPORT_SYMBOL(_find_nth_bit); + #ifndef find_first_and_bit /* * Find the first set bit in two memory regions. --=20 2.34.1 From nobody Sun Apr 19 04:23:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id E0DD9C433EF for ; Wed, 6 Jul 2022 18:23:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233865AbiGFSXO (ORCPT ); Wed, 6 Jul 2022 14:23:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35832 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232010AbiGFSXF (ORCPT ); Wed, 6 Jul 2022 14:23:05 -0400 Received: from mail-qk1-x734.google.com (mail-qk1-x734.google.com [IPv6:2607:f8b0:4864:20::734]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 25DFD28E33 for ; Wed, 6 Jul 2022 11:23:05 -0700 (PDT) Received: by mail-qk1-x734.google.com with SMTP id z7so11662139qko.8 for ; Wed, 06 Jul 2022 11:23:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=6QLssyCPgTwVHYtmN9nUGGfabZPbS3KXlULG75HB9Jo=; b=mL8HIkzYN4g3cRiyyVzzxpeuOXI14Sqnatn1QJ4dEH0JuXJ43HOa8gWZoFdveOyrLO u+t3prHckc0JBC/F06XNPlzZdsW4uaNbV3tYA+Ah2tcRIhGkk+/MRUldytBdfQVAr1C4 QlqcE3lQkJ8aaSfaZnGSYel3GmBmCBCbO2BQThR4T3b8CJWEhZald0/2lqPVx77aaNeo cToqpxyRpy5h8oVP4K4weqGMpHOfZHjPp3hfUQXzODg40BfLjYrBG2b8/KEjTt9bmf7t bTFUzJD9r2uIo7rtLkfDvkun+AU3ycreyX3BqqOBNcy8wpNjCJjKoolgRKiH7hPg89f4 g95Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=6QLssyCPgTwVHYtmN9nUGGfabZPbS3KXlULG75HB9Jo=; b=LfbY+O1eSQVNQqXuX51TTVwM1WD0hbRVhTt+xRazw3Mx7l44BVe/QcYEWjv4N4choK jTVyYRPG5qfts2MKVT50EvUq2ed8cpiUK7UEdqOZNnOou2w30IKoSuTjL98z9dtg0CSi V1AUITFmQd3c4ATCkBlFYkzHHlF6OxLsMnlUTbD//ySsmarFfPJNnoyhu9WqSKJZFa6/ 0niT8khdyWStMp5eEf490NBwk+zp6TWiI9+mTfgEwhzlPctqyVS0NKOIg6D0hV4fe5du sD+0vr661FdJ6+q0JvFTKjYzcAoyTbyQ6xtFGFuvdl8hgWLFsJFY7Qn12f7kSxwKkkUm Guxw== X-Gm-Message-State: AJIora+EhXxvA7OajBD7nt8pd94K5u42YR7jURmJb1P9v3fGRW+cuzNh Oj4JNqYb9Oj0I4LNlUs4SUyj3drbgavdfA== X-Google-Smtp-Source: AGRyM1sgGM1He2HakssDW7NQLjfHwUcwTLNmAlSSIKkpO6F4atqLGRBjELlHqmuSKtZjWzrHPNGfPA== X-Received: by 2002:a05:620a:1710:b0:6b2:583b:c0ce with SMTP id az16-20020a05620a171000b006b2583bc0cemr19966884qkb.471.1657131784116; Wed, 06 Jul 2022 11:23:04 -0700 (PDT) Received: from localhost (c-69-254-185-160.hsd1.fl.comcast.net. [69.254.185.160]) by smtp.gmail.com with ESMTPSA id r18-20020ac87ef2000000b00304e33f21f7sm24192517qtc.68.2022.07.06.11.23.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 Jul 2022 11:23:03 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= Cc: Yury Norov Subject: [PATCH 2/5] lib/bitmap: add tests for find_nth_bit() Date: Wed, 6 Jul 2022 11:22:57 -0700 Message-Id: <20220706182300.70862-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706182300.70862-1-yury.norov@gmail.com> References: <20220706182300.70862-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Add functional and performance tests for find_nth_bit(). Signed-off-by: Yury Norov --- lib/find_bit_benchmark.c | 17 +++++++++++++++++ lib/test_bitmap.c | 36 ++++++++++++++++++++++++++++++++++-- 2 files changed, 51 insertions(+), 2 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index db904b57d4b8..aad769c6ca84 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -115,6 +115,22 @@ static int __init test_find_last_bit(const void *bitma= p, unsigned long len) return 0; } =20 +static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned = long len) +{ + unsigned long l, n, w =3D bitmap_weight(bitmap, len); + ktime_t time; + + time =3D ktime_get(); + for (n =3D 1; n <=3D w; n++) { + l =3D find_nth_bit(bitmap, len, n); + WARN_ON(l >=3D len); + } + time =3D ktime_get() - time; + pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + + return 0; +} + static int __init test_find_next_and_bit(const void *bitmap, const void *bitmap2, unsigned long len) { @@ -142,6 +158,7 @@ static int __init find_bit_test(void) test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); + test_find_nth_bit(bitmap, BITMAP_LEN/10); =20 /* * test_find_first_bit() may take some time, so diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index d5923a640457..b4b53d8c66ae 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -16,6 +16,8 @@ =20 #include "../tools/testing/selftests/kselftest_module.h" =20 +#define EXP1_IN_BITS (sizeof(exp1) * 8) + KSTM_MODULE_GLOBALS(); =20 static char pbl_buffer[PAGE_SIZE] __initdata; @@ -219,6 +221,36 @@ static void __init test_zero_clear(void) expect_eq_pbl("", bmap, 1024); } =20 +static void __init test_find_nth_bit(void) +{ + unsigned long b, bit, cnt =3D 0; + DECLARE_BITMAP(bmap, 64 * 3); + + bitmap_zero(bmap, 64 * 3); + __set_bit(10, bmap); + __set_bit(20, bmap); + __set_bit(30, bmap); + __set_bit(40, bmap); + __set_bit(50, bmap); + __set_bit(60, bmap); + __set_bit(80, bmap); + __set_bit(123, bmap); + + expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 1)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 2)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 3)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 4)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 5)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 6)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 7)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 8)); + + for_each_set_bit(bit, exp1, EXP1_IN_BITS) { + b =3D find_nth_bit(exp1, EXP1_IN_BITS, ++cnt); + expect_eq_uint(b, bit); + } +} + static void __init test_fill_set(void) { DECLARE_BITMAP(bmap, 1024); @@ -557,8 +589,6 @@ static void __init test_bitmap_parse(void) } } =20 -#define EXP1_IN_BITS (sizeof(exp1) * 8) - static void __init test_bitmap_arr32(void) { unsigned int nbits, next_bit; @@ -884,6 +914,8 @@ static void __init selftest(void) test_for_each_set_clump8(); test_bitmap_cut(); test_bitmap_print_buf(); + + test_find_nth_bit(); } =20 KSTM_MODULE_LOADERS(test_bitmap); --=20 2.34.1 From nobody Sun Apr 19 04:23:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6B029C433EF for ; Wed, 6 Jul 2022 18:23:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233896AbiGFSXR (ORCPT ); Wed, 6 Jul 2022 14:23:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35852 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229901AbiGFSXH (ORCPT ); Wed, 6 Jul 2022 14:23:07 -0400 Received: from mail-qt1-x82f.google.com (mail-qt1-x82f.google.com [IPv6:2607:f8b0:4864:20::82f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3A82C20193 for ; Wed, 6 Jul 2022 11:23:06 -0700 (PDT) Received: by mail-qt1-x82f.google.com with SMTP id h19so19451728qtp.6 for ; Wed, 06 Jul 2022 11:23:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=hy1Cll65BZP8JO4Jpuyg4IGmFUmacl9SpleS3IvscpM=; b=nmgqjfLsvKj1hpB3WD2dAqde/v8ZbkHNCp1gle0xYqg8ojb8HqI9laswQ7QP6n78MP iwZ4P07GtZEGMy/B0qmlyxfpuxVWjrsvKBKzHahnRKhUn1IIoTB2P9Wi0LAdc3Fx+Lnb KvnRuITTi8Fmx2oWrleoCsC3oiqE69JX1s1mCuTxvPESO3ziUVn1oRWOmlKVZTVx/0Ir sjH6zW0yMTFBz3032wkKCAE/HA28GCX7SSVJWK/zuuYl217pgC+VKeX9SqqdkFZkzRR2 zAZVtflmXkAF/gdVYwBoqusSwLtunXiHYjQZDivGuVtuIu3V0AVAg/hb096zHtPG+GQa puhw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=hy1Cll65BZP8JO4Jpuyg4IGmFUmacl9SpleS3IvscpM=; b=6HniR9JQbSnVDzYIPMQfydmPGuPl4n/+0XhSuuJRErwjT5iivcLIOlewmPnWYGBlAB Cvh0QdHuFgO/NXEPfIGhKjDMyRG3X7k2fWjRNHoTcbltT4xrbcOZ+aYHK5Y2m7k8dzKy wWffZcZHyueMLGiqOC2hHKFaCaGQxheddHplLebtoWDtuCQXyAgqLNMoNLUDQXiNcdlx PpDNh2a2HjvBKUfdiv7i2lmURIJ0dpGt/ckmM5E+pwNoB8QSzl9VJIcraaEw8UFWiM2E kWEYp44TvtkLlmBPIxeRoB1vpL15xsCLnfrnYTGWG7au6c4b7KVEfi0rj7UaIrAqeTWm qgyQ== X-Gm-Message-State: AJIora/xB5RDBtFwWV+UY2nuTXTaYgg8IULw+QL8k9p3xh4xY3OKJ9eu P0O325d8pcAZFKzB6KbqglzHZqcDRX1Ijg== X-Google-Smtp-Source: AGRyM1sXwH/92sewGs9iSo+ylW6KFna6nLt4ZI+flx/x9kz+/TNp6ZoAEKE+iD2jAbfLqbhU0FKAQQ== X-Received: by 2002:a05:622a:1305:b0:31d:3d10:fd88 with SMTP id v5-20020a05622a130500b0031d3d10fd88mr20986122qtk.168.1657131785197; Wed, 06 Jul 2022 11:23:05 -0700 (PDT) Received: from localhost (c-69-254-185-160.hsd1.fl.comcast.net. [69.254.185.160]) by smtp.gmail.com with ESMTPSA id ey14-20020a05622a4c0e00b002fcb0d95f65sm24639528qtb.90.2022.07.06.11.23.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 Jul 2022 11:23:05 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= Cc: Yury Norov Subject: [PATCH 3/5] lib/bitmap: remove bitmap_ord_to_pos Date: Wed, 6 Jul 2022 11:22:58 -0700 Message-Id: <20220706182300.70862-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706182300.70862-1-yury.norov@gmail.com> References: <20220706182300.70862-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Now that we have find_nth_bit(), we can drop bitmap_ord_to_pos(). Signed-off-by: Yury Norov --- include/linux/bitmap.h | 1 - lib/bitmap.c | 36 +++--------------------------------- lib/nodemask.c | 3 +-- 3 files changed, 4 insertions(+), 36 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index b2198665a064..91506057b240 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -222,7 +222,6 @@ void bitmap_copy_le(unsigned long *dst, const unsigned = long *src, unsigned int n #else #define bitmap_copy_le bitmap_copy #endif -unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int o= rd, unsigned int nbits); int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, int nmaskbits); =20 diff --git a/lib/bitmap.c b/lib/bitmap.c index b580b381eca1..0b1082aa0b2c 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -956,36 +956,6 @@ static int bitmap_pos_to_ord(const unsigned long *buf,= unsigned int pos, unsigne return __bitmap_weight(buf, pos); } =20 -/** - * bitmap_ord_to_pos - find position of n-th set bit in bitmap - * @buf: pointer to bitmap - * @ord: ordinal bit position (n-th set bit, n >=3D 0) - * @nbits: number of valid bit positions in @buf - * - * Map the ordinal offset of bit @ord in @buf to its position in @buf. - * Value of @ord should be in range 0 <=3D @ord < weight(buf). If @ord - * >=3D weight(buf), returns @nbits. - * - * If for example, just bits 4 through 7 are set in @buf, then @ord - * values 0 through 3 will get mapped to 4 through 7, respectively, - * and all other @ord values returns @nbits. When @ord value 3 - * gets mapped to (returns) @pos value 7 in this example, that means - * that the 3rd set bit (starting with 0th) is at position 7 in @buf. - * - * The bit positions 0 through @nbits-1 are valid positions in @buf. - */ -unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord,= unsigned int nbits) -{ - unsigned int pos; - - for (pos =3D find_first_bit(buf, nbits); - pos < nbits && ord; - pos =3D find_next_bit(buf, nbits, pos + 1)) - ord--; - - return pos; -} - /** * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap * @dst: remapped result @@ -1035,7 +1005,7 @@ void bitmap_remap(unsigned long *dst, const unsigned = long *src, if (n < 0 || w =3D=3D 0) set_bit(oldbit, dst); /* identity map */ else - set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst); + set_bit(find_nth_bit(new, nbits, n % w + 1), dst); } } EXPORT_SYMBOL(bitmap_remap); @@ -1074,7 +1044,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *= old, if (n < 0 || w =3D=3D 0) return oldbit; else - return bitmap_ord_to_pos(new, n % w, bits); + return find_nth_bit(new, bits, n % w + 1); } EXPORT_SYMBOL(bitmap_bitremap); =20 @@ -1198,7 +1168,7 @@ void bitmap_onto(unsigned long *dst, const unsigned l= ong *orig, * The following code is a more efficient, but less * obvious, equivalent to the loop: * for (m =3D 0; m < bitmap_weight(relmap, bits); m++) { - * n =3D bitmap_ord_to_pos(orig, m, bits); + * n =3D find_nth_bit(orig, bits, m + 1); * if (test_bit(m, orig)) * set_bit(n, dst); * } diff --git a/lib/nodemask.c b/lib/nodemask.c index e22647f5181b..7dad4ce8ff59 100644 --- a/lib/nodemask.c +++ b/lib/nodemask.c @@ -24,8 +24,7 @@ int node_random(const nodemask_t *maskp) =20 w =3D nodes_weight(*maskp); if (w) - bit =3D bitmap_ord_to_pos(maskp->bits, - get_random_int() % w, MAX_NUMNODES); + bit =3D find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1= ); return bit; } #endif --=20 2.34.1 From nobody Sun Apr 19 04:23:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 259C8C433EF for ; Wed, 6 Jul 2022 18:23:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233940AbiGFSXU (ORCPT ); Wed, 6 Jul 2022 14:23:20 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35878 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233306AbiGFSXH (ORCPT ); Wed, 6 Jul 2022 14:23:07 -0400 Received: from mail-qk1-x730.google.com (mail-qk1-x730.google.com [IPv6:2607:f8b0:4864:20::730]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F087929C89 for ; Wed, 6 Jul 2022 11:23:06 -0700 (PDT) Received: by mail-qk1-x730.google.com with SMTP id r138so11653237qke.13 for ; Wed, 06 Jul 2022 11:23:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=pai9znSdO+fwy4aj7J/mMLYj56s01kumpPyW+l50h6M=; b=ELJYXJ/V7ZHpOqKh9DKvzDBB//zFWkfsQlSz2x6A4lbIPATB+g8WQbNx21wAXqFptx +pWZOrA8a7c6NEIaKcfVgwqPvsmIsz+nch4BbsI3i2mdulvUYtfb0FqIuR5tdi0ZP1cc Ptb/bWg+KM/1EtR2x90ZTMhJy4yqG5k/y8X5FRDPtp6ed/nZtMBMgh/uCdoYjs1J9d6/ CB3bXdmqoZHuDoN9h2PFrqFQTV4i9GbrNPEOcsEYuTTBi4aaDcmygaO0Z9Rc1ZB7fY1H z1ZTaEWxj2dWhaTkIM6n0lDpsmhKfvCH0nNI2o5xyhw+Lu+/A842bAqxCFl17OKwqJep n4lA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=pai9znSdO+fwy4aj7J/mMLYj56s01kumpPyW+l50h6M=; b=BuXcrm/ak+rik62pTZT42hZ7LKUmsFxqW518QcAWpc1izRmap6VtNLkWOjBD74IaE0 2RgLDrEBMMWwTF3Cw49fC4uYU/YCtT7+5CkVNTZU2z5+QQUmE1+b3tEsW12qMdDgENHF jeRHAoj0Dj/n78IFia/MlkIpax2NizuHkooQSMYFlQEtSLzoUAzlwlKxnf9vlCF4FAk5 dnZdBK6ImfDhTR149OuadNwNgbu+eUfPicXhZv3CuoaCRCzgTYt2NEYopFsNgcYxuify 8vFRhAledRWdMFwKFvu0Eq8HbvoYrfW5TzQlI2YTOSRd02v92YwaqFcqTMX+WmJXvut6 N3bg== X-Gm-Message-State: AJIora+mtTUHkUfW+jxSdFivHtrciOZDD0jSLqTpbzhJoqfl+ByiQKA3 qmq1+RgankR2LLVAIrUvMXupIRnAENaZ1g== X-Google-Smtp-Source: AGRyM1tOPXpgnvuNb3qc1kcKGwUSQiO9Xfku/hquZpKix0xs64NrKVUjMPXrJB7H1GnHP2AzMAXVHg== X-Received: by 2002:a05:620a:8018:b0:6af:1fee:41ac with SMTP id ee24-20020a05620a801800b006af1fee41acmr27768228qkb.476.1657131785889; Wed, 06 Jul 2022 11:23:05 -0700 (PDT) Received: from localhost (c-69-254-185-160.hsd1.ar.comcast.net. [69.254.185.160]) by smtp.gmail.com with ESMTPSA id c190-20020ae9edc7000000b006a743b360bcsm28998990qkg.136.2022.07.06.11.23.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 Jul 2022 11:23:05 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= Cc: Yury Norov Subject: [PATCH 4/5] cpumask: add cpumask_nth_{,and,andnot} Date: Wed, 6 Jul 2022 11:22:59 -0700 Message-Id: <20220706182300.70862-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706182300.70862-1-yury.norov@gmail.com> References: <20220706182300.70862-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Add cpumask_nth_{,and,andnot} as wrappers around corresponding find functions, and use it in cpumask_local_spread(). Signed-off-by: Yury Norov --- include/linux/cpumask.h | 44 +++++++++++++++++++++++++++++++++++++++++ lib/cpumask.c | 26 +++++++++++------------- 2 files changed, 55 insertions(+), 15 deletions(-) diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index 0738a6c9be40..8cf460368fca 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -379,6 +379,50 @@ unsigned int cpumask_any_but(const struct cpumask *mas= k, unsigned int cpu) } #endif /* SMP */ =20 +/** + * cpumask_nth - get the first cpu in a cpumask + * @srcp: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 1 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpum= ask *srcp) +{ + return find_nth_bit(cpumask_bits(srcp), nr_cpumask_bits, cpumask_check(cp= u)); +} + +/** + * cpumask_nth_and - get the first cpu in 2 cpumasks + * @srcp1: the cpumask pointer + * @srcp2: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 1 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline +unsigned int cpumask_nth_and(unsigned int cpu, const struct cpumask *srcp1, + const struct cpumask *srcp2) +{ + return find_nth_and_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), + nr_cpumask_bits, cpumask_check(cpu)); +} + +/** + * cpumask_nth_andnot - get the first cpu set in 1st cpumask, and clear in= 2nd. + * @srcp1: the cpumask pointer + * @srcp2: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 1 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline +unsigned int cpumask_nth_andnot(unsigned int cpu, const struct cpumask *sr= cp1, + const struct cpumask *srcp2) +{ + return find_nth_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), + nr_cpumask_bits, cpumask_check(cpu)); +} + #define CPU_BITS_NONE \ { \ [0 ... BITS_TO_LONGS(NR_CPUS)-1] =3D 0UL \ diff --git a/lib/cpumask.c b/lib/cpumask.c index f0ae119be8c4..56aeb9c9d702 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -128,23 +128,19 @@ unsigned int cpumask_local_spread(unsigned int i, int= node) i %=3D num_online_cpus(); =20 if (node =3D=3D NUMA_NO_NODE) { - for_each_cpu(cpu, cpu_online_mask) - if (i-- =3D=3D 0) - return cpu; + cpu =3D cpumask_nth(i + 1, cpu_online_mask); + if (cpu < nr_cpu_ids) + return cpu; } else { /* NUMA first. */ - for_each_cpu_and(cpu, cpumask_of_node(node), cpu_online_mask) - if (i-- =3D=3D 0) - return cpu; - - for_each_cpu(cpu, cpu_online_mask) { - /* Skip NUMA nodes, done above. */ - if (cpumask_test_cpu(cpu, cpumask_of_node(node))) - continue; - - if (i-- =3D=3D 0) - return cpu; - } + cpu =3D cpumask_nth_and(i + 1, cpu_online_mask, cpumask_of_node(node)); + if (cpu < nr_cpu_ids) + return cpu; + + /* Skip NUMA nodes, done above. */ + cpu =3D cpumask_nth_andnot(i + 1, cpu_online_mask, cpumask_of_node(node)= ); + if (cpu < nr_cpu_ids) + return cpu; } BUG(); } --=20 2.34.1 From nobody Sun Apr 19 04:23:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 839D7C433EF for ; Wed, 6 Jul 2022 18:23:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234097AbiGFSXZ (ORCPT ); Wed, 6 Jul 2022 14:23:25 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35916 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233519AbiGFSXJ (ORCPT ); Wed, 6 Jul 2022 14:23:09 -0400 Received: from mail-qt1-x82a.google.com (mail-qt1-x82a.google.com [IPv6:2607:f8b0:4864:20::82a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CC9A62A428 for ; Wed, 6 Jul 2022 11:23:07 -0700 (PDT) Received: by mail-qt1-x82a.google.com with SMTP id l14so19446401qtx.2 for ; Wed, 06 Jul 2022 11:23:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=1hhqdc2x+kkGFSuuHDeERWD84qOn+LrQwMR/CrzMYCA=; b=ncJa0bbsY+ADs51/B7IPMBI5jZWHnw1auM0/zB0TVloBNSAhkr+fEWFFYikqeSmgJS 5STn7hps64Hfd8wMGa2yVr0H8MOUMs/lePVZx9gaXvgN8YKgP4rMFqOjN5bEUrX2xRYD p+7aDMLStNe/af2b4loTfOCSYfQH+i9l3xQUj3PDb73qQqoAbh7LHYrIEbL8wYkIBXuf 9UGhQUCdjLimslM/24w24qs4ONlci3+PpnQB9oX0a1AGpQtGU9BYZXExgwjUzGat3IFn W+ydV+JCcWKndye8Ie2Yxb6csdupMh6OJ+Dm50tynm/1iqplz9ljRpkVTZmBoo/O1tH4 pHIA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=1hhqdc2x+kkGFSuuHDeERWD84qOn+LrQwMR/CrzMYCA=; b=ASJdiIWYxwZqlIZFjz0GBddWwu9BeoNiZTXI2NK6pqEdBiG/46VRB6HgDzYgBe1c7r iFHXq1ExQagyltya1MR8uMZ0YtcayO64upwXGMsx58q8RrXnHEmjLMhr18pMi187QBJV 3s+I1v4pomDzHB2N9gEMl78gdA5X9dVrOPktIbjE3kOb+1ZZmL1cDd3Dl4VeTrxY781J ZNXceeIH0r7BRCGNnapAnhQixuDjz87pInLGUYa/bTPaJRRmqRy+yk8WwYPcfEhBnUXW 7CkpGtBgvoGScrD/LvOFXJ9epaPtex1WYRsaavEUUmtiixXmgCBrUvoN++NfjaCMNtof +NOw== X-Gm-Message-State: AJIora/DO7+6eiYFF+GQ5FWWuRrfs8en/7cY3ns0POb0FegjOgeIccNt 8MiqBSud0oAOnOK2xT1X8O6za/f+ixXROg== X-Google-Smtp-Source: AGRyM1v6owxWrcp9XaQYZwsUgPkipgCazU6XPpChMM/D/s0UTByGci2ze0poMpZmFKcFgOHaGy8iRQ== X-Received: by 2002:ac8:5bd4:0:b0:31a:faa2:f639 with SMTP id b20-20020ac85bd4000000b0031afaa2f639mr33715592qtb.487.1657131786757; Wed, 06 Jul 2022 11:23:06 -0700 (PDT) Received: from localhost (c-69-254-185-160.hsd1.ar.comcast.net. [69.254.185.160]) by smtp.gmail.com with ESMTPSA id y17-20020a05620a25d100b006a6a5d1e240sm33304238qko.34.2022.07.06.11.23.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 06 Jul 2022 11:23:06 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= Cc: Yury Norov Subject: [PATCH 5/5] lib/nodemask: inline next_node_in() and node_random() Date: Wed, 6 Jul 2022 11:23:00 -0700 Message-Id: <20220706182300.70862-6-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706182300.70862-1-yury.norov@gmail.com> References: <20220706182300.70862-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" The functions are pretty thin wrappers around find_bit engine, and keeping them in c-file prevents compiler from small_const_nbits() optimization, which must take place for all systems with MAX_NUMNODES less than BITS_PER_LONG (default is 16 for me). Moving them in header file doesn't blow up the kernel size: add/remove: 1/2 grow/shrink: 9/5 up/down: 968/-88 (880) Signed-off-by: Yury Norov --- MAINTAINERS | 1 - include/linux/nodemask.h | 27 ++++++++++++++++++++++----- lib/Makefile | 2 +- lib/nodemask.c | 30 ------------------------------ 4 files changed, 23 insertions(+), 37 deletions(-) delete mode 100644 lib/nodemask.c diff --git a/MAINTAINERS b/MAINTAINERS index f808826509e5..314dd1054246 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -3540,7 +3540,6 @@ F: lib/bitmap.c F: lib/cpumask.c F: lib/find_bit.c F: lib/find_bit_benchmark.c -F: lib/nodemask.c F: lib/test_bitmap.c F: tools/include/linux/bitmap.h F: tools/include/linux/find.h diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h index 0f233b76c9ce..48ebe4007955 100644 --- a/include/linux/nodemask.h +++ b/include/linux/nodemask.h @@ -94,6 +94,7 @@ #include #include #include +#include =20 typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t; extern nodemask_t _unused_nodemask_arg_; @@ -276,7 +277,14 @@ static inline unsigned int __next_node(int n, const no= demask_t *srcp) * the first node in src if needed. Returns MAX_NUMNODES if src is empty. */ #define next_node_in(n, src) __next_node_in((n), &(src)) -unsigned int __next_node_in(int node, const nodemask_t *srcp); +static inline unsigned int __next_node_in(int node, const nodemask_t *srcp) +{ + unsigned int ret =3D __next_node(node, srcp); + + if (ret =3D=3D MAX_NUMNODES) + ret =3D __first_node(srcp); + return ret; +} =20 static inline void init_nodemask_of_node(nodemask_t *mask, int node) { @@ -493,14 +501,23 @@ static inline int num_node_state(enum node_states sta= te) =20 #endif =20 +/* + * Return the bit number of a random bit set in the nodemask. + * (returns NUMA_NO_NODE if nodemask is empty) + */ +static inline int node_random(const nodemask_t *maskp) +{ #if defined(CONFIG_NUMA) && (MAX_NUMNODES > 1) -extern int node_random(const nodemask_t *maskp); + int w, bit =3D NUMA_NO_NODE; + + w =3D nodes_weight(*maskp); + if (w) + bit =3D find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1= ); + return bit; #else -static inline int node_random(const nodemask_t *mask) -{ return 0; -} #endif +} =20 #define node_online_map node_states[N_ONLINE] #define node_possible_map node_states[N_POSSIBLE] diff --git a/lib/Makefile b/lib/Makefile index f99bf61f8bbc..731cea0342d1 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -33,7 +33,7 @@ lib-y :=3D ctype.o string.o vsprintf.o cmdline.o \ flex_proportions.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ - nmi_backtrace.o nodemask.o win_minmax.o memcat_p.o \ + nmi_backtrace.o win_minmax.o memcat_p.o \ buildid.o =20 lib-$(CONFIG_PRINTK) +=3D dump_stack.o diff --git a/lib/nodemask.c b/lib/nodemask.c deleted file mode 100644 index 7dad4ce8ff59..000000000000 --- a/lib/nodemask.c +++ /dev/null @@ -1,30 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 -#include -#include -#include - -unsigned int __next_node_in(int node, const nodemask_t *srcp) -{ - unsigned int ret =3D __next_node(node, srcp); - - if (ret =3D=3D MAX_NUMNODES) - ret =3D __first_node(srcp); - return ret; -} -EXPORT_SYMBOL(__next_node_in); - -#ifdef CONFIG_NUMA -/* - * Return the bit number of a random bit set in the nodemask. - * (returns NUMA_NO_NODE if nodemask is empty) - */ -int node_random(const nodemask_t *maskp) -{ - int w, bit =3D NUMA_NO_NODE; - - w =3D nodes_weight(*maskp); - if (w) - bit =3D find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1= ); - return bit; -} -#endif --=20 2.34.1