From nobody Sat Apr 18 21:01:27 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 86DF2C43334 for ; Mon, 11 Jul 2022 04:47:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229716AbiGKErW (ORCPT ); Mon, 11 Jul 2022 00:47:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41580 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229542AbiGKErR (ORCPT ); Mon, 11 Jul 2022 00:47:17 -0400 Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 216C460CF for ; Sun, 10 Jul 2022 21:47:16 -0700 (PDT) Received: by mail-qt1-x82c.google.com with SMTP id l2so2534980qtp.11 for ; Sun, 10 Jul 2022 21:47:16 -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=hZljeIHUIZz/AYIvotC3sgnaLGYxeJANre/U+XxdNdA=; b=P23YvmhWiMAPTJw+rKMkN2HA8Cesa0rn1BCnKhKzrDbh31j1Rf5QyHkjd711eEoK2o wRSZtUO/traXd1NgZ88DZmVpSsQwR0InKbTROHq4VdzAHyyEk6JD6EBGb6n/pUFLFlLD gONHelEW+PwrMmY1bDub5nLKSpBPTp7R4fr0y8AAftjjkcN/VeyqASAEMzaGojETax1X l3zXza+FC6KwebxLef3v2R7jMwGoZDtCW/CFGiePrt/MnMQ0CiG/4iGYK5ZcV2y1QkUR ZDzRVORYddWZzQpy3tpwfcoIcW3jcwSR1daipZlrNp5t59JCPGFxJDYckkJM21Qr+JNu 5y+A== 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=hZljeIHUIZz/AYIvotC3sgnaLGYxeJANre/U+XxdNdA=; b=WMiEqFPSc2xK3J/Zwi8mptjhRFLlbirv777Vw/XqA/Tl/LMaDEnOlW7zcdrHmSKEar EOHN61Vcc0g+7pI7umN1JqmGql/7WkKcCwM3fI3ewjJbsiqfNRAPMa8FawIFqJHdkL6I PhJn5toJ4sooofMfZq24+qjwI4r/qDZQZ1exyIYb8d/ivVPMqEuukVdI7FA5eMwlK4za 4/H1lNykZ7NxyXM2Yi4ofWHo06AgBdIhos2ZKgxkKVXBvbeuP8eOOBaXplkNldaTIX3h Ii0wyu4YrNNlBZFu+TL2TJM6tkLAy5x4v7JwH9Cdz9+7OQXJzDRaw+KuASux6/HFxhoK Weqw== X-Gm-Message-State: AJIora/OOWMNAzsuncN9+A/rgWbAenXxGhp/vh/CBYlzNI7esTNXtLFK k64Xb+f1S+c3QaCLtYQ+criljAfpCIRdAw== X-Google-Smtp-Source: AGRyM1sbgh3+9R+FabG7KyjNcVKDAoyQ0uthQPfVRjBogNTUJl4rQUZUIXtJ3RTvfC7WpcobPdskRA== X-Received: by 2002:ac8:7e8d:0:b0:31e:b5cd:4cf2 with SMTP id w13-20020ac87e8d000000b0031eb5cd4cf2mr2006603qtj.37.1657514835006; Sun, 10 Jul 2022 21:47:15 -0700 (PDT) Received: from localhost ([2601:4c1:c100:1230:a22e:180:f963:1eff]) by smtp.gmail.com with ESMTPSA id f1-20020a05620a280100b006b58b806745sm1477941qkp.43.2022.07.10.21.47.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Jul 2022 21:47:14 -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: Sun, 10 Jul 2022 21:47:07 -0700 Message-Id: <20220711044711.466822-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220711044711.466822-1-yury.norov@gmail.com> References: <20220711044711.466822-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: find_nth_bit: 7154190 ns, 16411 iterations for_each_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 | 83 ++++++++++++++++++++++++++++++++++++++++++ lib/find_bit.c | 20 ++++++++++ 3 files changed, 122 insertions(+) diff --git a/include/linux/bitops.h b/include/linux/bitops.h index cf9bf65039f2..8b2189878afa 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -246,6 +246,25 @@ static inline unsigned long __ffs64(u64 word) return __ffs((unsigned long)word); } =20 +/** + * fns - find N'th set bit in a word + * @word: The word to search + * @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..4c7f82dcc38a 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, unsigned long invert); 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,87 @@ 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, counting from 0 + * + * The following is semantically equivalent: + * idx =3D find_nth_bit(addr, size, 0); + * idx =3D find_first_bit(addr, size); + * + * 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 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, 0UL); +} + +/** + * 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, counting from 0 + * + * 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 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, 0UL); +} + +/** + * 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, counting from 0 + * + * 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 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, ~0UL); +} + #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..43cb1f781056 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, unsigned long invert) +{ + 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 addr2[idx] ^ invert; + + w =3D hweight_long(val); + if (w > 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 Sat Apr 18 21:01:27 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 657FCC43334 for ; Mon, 11 Jul 2022 04:47:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229732AbiGKEr2 (ORCPT ); Mon, 11 Jul 2022 00:47:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41586 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229674AbiGKErS (ORCPT ); Mon, 11 Jul 2022 00:47:18 -0400 Received: from mail-qk1-x732.google.com (mail-qk1-x732.google.com [IPv6:2607:f8b0:4864:20::732]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2404C5FB6 for ; Sun, 10 Jul 2022 21:47:17 -0700 (PDT) Received: by mail-qk1-x732.google.com with SMTP id x17so3078130qkh.11 for ; Sun, 10 Jul 2022 21:47:17 -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=lhvBjfQP4mIrveuhzJyEIDkKa/zzrboSQCfWcClOI6U=; b=A/8fxM2nCGbY7JBMHxvERs5r4l1RPJNkSK3jdC786MNoXyiR3sJGAtsDxdAdW+eMoX PUzTQh4qd9/YdDJfhi0ykQDOyqFDE+SwPAjaVrz0io+rJC9FEFBJVZ7I2kWA6fST40tL g6R0jLamktLvsk2XmgczwNqO5BL+lZc/6bYH/LXbfsPxN1HJDnKPtFOeAuj7ZQTYkVfc ZeZLT2U4Gb8KMdX5ZGkh9wR4SIzBPSa9sBiyDfl9kkhfVbMiWMB7heJCEzJCeljBEI9l +XcydROy6XBPS1FUb0srxxM2nv2vmKu8o/1hElsA0XXtJH80q0fNC+vt6zMW8fqBCIO7 4aeQ== 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=lhvBjfQP4mIrveuhzJyEIDkKa/zzrboSQCfWcClOI6U=; b=ORQTU1IG+KbU0EOzHtzcT/N+AXLNpnBaUTjmEhSJ2m73yLBuoM0ebmpZSJVW1pnuse Mf2AlldX8ikZwj3edrrLhEdrGnrBRvTNOKKjJnYhPDBfkg9TgDUzvELAS/+jWEPUgMKQ ZrX8n+7piSqxN4970KgLGawkfWpdvzCjfjV6+hMoUkGpaBvEYoDzPYES9fpmzp98oMgd fP28pkxG7apNF76zM7RzLzSuXHuxQ4dyVx9apDCt1th7yoPMmIkEHuab6DccMG7CZQp2 vTtRHMURVUbXXYgWY7qHxQsGF6BWEaZQQcsi2atkIZzRPbQqva8ZNr3DCZoS5xDaGph7 Ne3Q== X-Gm-Message-State: AJIora/4Z868U+USDWGZoiYVVXRifJ2qz4pA4vdFxQ3O/cvD1sxKjq/T pEAGKuAUG0Rpa1uL9w0ELDzJs9mwfBEEaw== X-Google-Smtp-Source: AGRyM1sTy72NmKAxhvRREqoybgvhQqJb8QIu1doICBGTbvFvCKX9nQ8JzgNgjE9M60R0WV/Piw+nwg== X-Received: by 2002:a37:a003:0:b0:6b5:7c77:d937 with SMTP id j3-20020a37a003000000b006b57c77d937mr3460461qke.263.1657514836055; Sun, 10 Jul 2022 21:47:16 -0700 (PDT) Received: from localhost ([2601:4c1:c100:1230:a22e:180:f963:1eff]) by smtp.gmail.com with ESMTPSA id k8-20020ac84788000000b0031bf484079esm4482223qtq.18.2022.07.10.21.47.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Jul 2022 21:47:15 -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: Sun, 10 Jul 2022 21:47:08 -0700 Message-Id: <20220711044711.466822-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220711044711.466822-1-yury.norov@gmail.com> References: <20220711044711.466822-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..a17a0ad0f783 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 0; n < 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 25967cfa4ab2..8ac8c1df818c 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, 0)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7)); + + 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; @@ -946,6 +976,8 @@ static void __init selftest(void) test_bitmap_cut(); test_bitmap_print_buf(); test_bitmap_const_eval(); + + test_find_nth_bit(); } =20 KSTM_MODULE_LOADERS(test_bitmap); --=20 2.34.1 From nobody Sat Apr 18 21:01:27 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 76F1FC433EF for ; Mon, 11 Jul 2022 04:47:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229755AbiGKErd (ORCPT ); Mon, 11 Jul 2022 00:47:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41606 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229687AbiGKErT (ORCPT ); Mon, 11 Jul 2022 00:47:19 -0400 Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3000260CF for ; Sun, 10 Jul 2022 21:47:18 -0700 (PDT) Received: by mail-qk1-x72b.google.com with SMTP id f12so3014869qka.12 for ; Sun, 10 Jul 2022 21:47:18 -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=A6q5z8s18QRfHFAJrndvZI9vXCYXjK+FWxgchg+J6RI=; b=QBLvVko+rS1FTRCtsf8vYGAy3nf88w3gkkF8Q6lJ4404r2d6ucehKkAsSxdZTlDrJN 2pUb0w/ZNLfWKoV4hMSenj84fR8fbAkByJK+izpYCcYmSoKXJdYn/I7UMDtX8zVvxjPy +fcOJSDoVp+JIfnFpHlM5gNfBGdf/kVhF+DUWvoNP+Jw1pE5yLBMGxfKlhxkbnxbH9zW woWPX6MRG8VWKSr5Gw1JueW0KsxNBk5D/3JQRTdRjlPpYt3y+5gACNvHDQUMggy1U/Mu PBs1b1FO5Hl0pyz9+ImqpzBvXjW1oP1Sibb7/pjUgGo0k88vOsDm4Vv1aswEUmmhOtFw V0pA== 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=A6q5z8s18QRfHFAJrndvZI9vXCYXjK+FWxgchg+J6RI=; b=LwaZkJIIXAajkHyEI1XpauvtZm8nuF0afGVvnPw0CU+bYIXMToooRR+z5eU4+KWuaz 8nMcq1APDyuEGgceYZfLhqjx18WN4sJxF+5QZAfc4X2/4wLEp7cbkdfvr5nllOM32ATD hgnEsQWCJdgB6g2aLhMrAdVYNPiosYuBjK+tt2Gkld58K+g/q3kZu5DzjLcIuXDaMv85 PzHWeOTMIiq9ZptfUfzI4ble3zKa7ulO1Jcwn4MhFhbyRP0M31WQ+GMAFNBHfqAMjkOa EprIX4w6d6LZ7SI4mHgGrAx91FIGUi3YW2WQ/wPhconFHFK64GdxkzJ6KxQHqbdbJ+RF J0yA== X-Gm-Message-State: AJIora8Ea4jEJZ6SKaDRdXMIw+VesGzcDzowTREodWxIJF6u/7ppne+L lg2cuiNRENl8FEX+wEfbPEniT7YUAQLeKg== X-Google-Smtp-Source: AGRyM1t0kd3jZCCquGJH9OtMac+nJ5b3c9DI68BHZKN/BAfLOUcyRZM4IrHddpmG4NB4S2tCbsdhrw== X-Received: by 2002:a37:a695:0:b0:6b5:8c47:ab0 with SMTP id p143-20020a37a695000000b006b58c470ab0mr1252213qke.579.1657514837051; Sun, 10 Jul 2022 21:47:17 -0700 (PDT) Received: from localhost ([2601:4c1:c100:1230:a22e:180:f963:1eff]) by smtp.gmail.com with ESMTPSA id s12-20020a05620a29cc00b006b28349678dsm5975138qkp.80.2022.07.10.21.47.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Jul 2022 21:47:16 -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: Sun, 10 Jul 2022 21:47:09 -0700 Message-Id: <20220711044711.466822-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220711044711.466822-1-yury.norov@gmail.com> References: <20220711044711.466822-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 035d4ac66641..0de6f6a101a9 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), 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); } 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); * 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); return bit; } #endif --=20 2.34.1 From nobody Sat Apr 18 21:01:27 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 C35B2C43334 for ; Mon, 11 Jul 2022 04:47:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229763AbiGKErk (ORCPT ); Mon, 11 Jul 2022 00:47:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41624 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229708AbiGKErU (ORCPT ); Mon, 11 Jul 2022 00:47:20 -0400 Received: from mail-qk1-x72c.google.com (mail-qk1-x72c.google.com [IPv6:2607:f8b0:4864:20::72c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4C24660CF for ; Sun, 10 Jul 2022 21:47:19 -0700 (PDT) Received: by mail-qk1-x72c.google.com with SMTP id f12so3014886qka.12 for ; Sun, 10 Jul 2022 21:47:19 -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=B/+c9EiF9/emkxKF8PsBaxLM8SipI/6o4W1rL+EK1gU=; b=iVll2f8cJnDQrGa2Adcc428xEcVhjWAHcHz4MptpjtUXN7lnsvBHVwYUVrBL+lVxLp ioI+6DQiSLkhH7bxizmPtsxWX7bvNq831jjdTTXwQIVp3Gu0DUlB9T2vROndZgAKoXL5 KWbHUK7jZwULl4dCf4FKU73XgOCwp+O+R3oyUtqlR3/gDoJHO7dO1Ltrt9xNNnsdkEBB fSc1GvTvvOMUsm8GbZQoYn84G5kFElABalMDwTMQ7fbodhc0Fw0FvKM33tZPXslgciQh 6ImKhDSs51frYo79Nhj+NWrFBTTnRkKMRfSRxnjPI6Zshs/KYkUXPMKbUBwubKSejp6G bxDg== 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=B/+c9EiF9/emkxKF8PsBaxLM8SipI/6o4W1rL+EK1gU=; b=GMzV5YGdZiFV/f6gIhPfymvhBeaIbuM6NCyBxUNSN7PXqZpcEs+cAgZUu8wN42ScOl /ZK7WlsTUv5X/r+4QzGGiPrtNUtRr6VMM4BZsFe09Gti9lddanoBhzX43//HUxTivPwt YAVm5ZEs0mVbdVEiCYpeuFc4OR/fF4TVUfK3HIdkS28IxsgmsWxaGvKp6o47qyKIz1KS 8UHAJiz59uHQ53VPPvXCiMM5UuTvzWgd5S+oeZ8Rk1hUet8GRuIvi5TDbVe1Qx38TXZ0 lLI/m1sYax5DAbTl8DOS7/JSvIIzvjQG5oQBftPe4l43LeFMxQifu6S0V3Vi7JEB97M9 T//w== X-Gm-Message-State: AJIora+JJf71jEcwgpiAXPrR3y2H6WVdI7mr0fiq0UhEmw9aryZRqt2y UKEPbY9y9BEOChluyquHmu+JmbtlFhV9MA== X-Google-Smtp-Source: AGRyM1vy5C+3k70AnLvG6MY8AfNBJisfqJNqFquWqUWry5GwuGQPhe1VcOtAB3dWWWo5lY1U5QWQ5g== X-Received: by 2002:a05:620a:8018:b0:6af:1fee:41ac with SMTP id ee24-20020a05620a801800b006af1fee41acmr10105424qkb.476.1657514838130; Sun, 10 Jul 2022 21:47:18 -0700 (PDT) Received: from localhost ([2601:4c1:c100:1230:a22e:180:f963:1eff]) by smtp.gmail.com with ESMTPSA id i14-20020a05620a248e00b006b555509398sm5455586qkn.136.2022.07.10.21.47.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Jul 2022 21:47:17 -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: Sun, 10 Jul 2022 21:47:10 -0700 Message-Id: <20220711044711.466822-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220711044711.466822-1-yury.norov@gmail.com> References: <20220711044711.466822-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 80627362c774..86c7e6c6e473 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 0 + * + * 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 0 + * + * 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 0 + * + * 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..062821dbf65f 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, 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, 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, cpu_online_mask, cpumask_of_node(node)); + if (cpu < nr_cpu_ids) + return cpu; } BUG(); } --=20 2.34.1 From nobody Sat Apr 18 21:01:27 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 7C5A0C43334 for ; Mon, 11 Jul 2022 04:47:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229754AbiGKErq (ORCPT ); Mon, 11 Jul 2022 00:47:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41656 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229724AbiGKErV (ORCPT ); Mon, 11 Jul 2022 00:47:21 -0400 Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 49D5760CF for ; Sun, 10 Jul 2022 21:47:20 -0700 (PDT) Received: by mail-qk1-x72b.google.com with SMTP id b2so523872qkk.3 for ; Sun, 10 Jul 2022 21:47:20 -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=INvUTYu9dairWJ/J98PrS85b9AuqfQWZLIuDZmgdIug=; b=YaKowwfmmEcDAw8khKC4VVPEog0/+uU4H8CAy1j0FgHqSR9O2QCzFFd5uEf13z5XIo 3m2TviDjmax/vb/ztAi1FDg4qTC9UlSaU0JCb+1vwxCBCHttWpfh2xCsgiRlMHywfw2j DWQrvlrQ151l7EhmHKdqTjPwSh6xCBm7C0S2cSX7aXY/nHMEFPB68ry2YhV0QhYXsq38 hdyBAduJHpfO0SpgX7Ro53uItDqvLACOrCGWAjmH1EmgPSo9g1afCaNTqbzleXBUqqjQ VL0nEIsG36DdajEO67uDK6aKGLYfDENjGJGR3tyUC0laHGfzYc+0pJ1IiKmHCCNb3skV KYtg== 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=INvUTYu9dairWJ/J98PrS85b9AuqfQWZLIuDZmgdIug=; b=feER4AHfHTNCEtLzg02VzEIejk4fT35ezjitp+RyJZCM3VU80W3tdB61hPX2hoOYMK nuw+cbg88Ygh1znyr+2eqgPseKG+ZsIJTl2+nWhDxmuKYmMUS0h0wqE3/yMvh4pTmVl1 at2ITSpSjuSVmBo6ulzXyl5t4Ycha7HpvgXGsrSJzewEiWbfJ/jjphx65vKNkEiAME4b gJANak1pCVMTT0Jr0URUgPYQ3GzmQdlaiWi2uV7dhY8xtTziVaFGIuG4Go8GcARrx00M MhJwCe4qIfWQDe0ch9mZKtT6qWmfr6kgzRGZl5Mjn3N43boUmLxiPsLAFd23hKP46oif Z5HQ== X-Gm-Message-State: AJIora/UyBBBqQy/GCVULBeABuwyrNQDEh49WAIImzNLC3810LuxPjmP 8vKRKwEP4Fjw+q2GQoA+uEMm8LofbQvq3A== X-Google-Smtp-Source: AGRyM1uhBWsCKUmq9aDc1F1otrdss8jIzZiRjquWwL0Ewzd4Viza65MG7AjCdPZ5uUgUUBzgQluFxA== X-Received: by 2002:a05:620a:1e5:b0:6b5:55d5:5ce3 with SMTP id x5-20020a05620a01e500b006b555d55ce3mr10018006qkn.640.1657514839230; Sun, 10 Jul 2022 21:47:19 -0700 (PDT) Received: from localhost ([2601:4c1:c100:1230:a22e:180:f963:1eff]) by smtp.gmail.com with ESMTPSA id f20-20020a05620a409400b006b5840f3eefsm2475579qko.130.2022.07.10.21.47.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Jul 2022 21:47:18 -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: Sun, 10 Jul 2022 21:47:11 -0700 Message-Id: <20220711044711.466822-6-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220711044711.466822-1-yury.norov@gmail.com> References: <20220711044711.466822-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 7c0b8f28aa25..19c8d0ef1177 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); + 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); - return bit; -} -#endif --=20 2.34.1