[PATCH 0/3] bitmap: introduce find_random_bit() and use in clocksource

[PATCH 0/3] bitmap: introduce find_random_bit() and use in clocksource

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

nodemasks implement node_random(), which may also be useful for other
subsystems. Generalize the function, and propagate to cpumask API.

Yury Norov (3):
  bitmap: generalize node_random()
  cpumask: introduce cpumask_random()
  clocksource: improve randomness in clocksource_verify_choose_cpus()

 include/linux/cpumask.h   | 12 ++++++++++++
 include/linux/find.h      |  2 ++
 include/linux/nodemask.h  | 16 +---------------
 kernel/time/clocksource.c |  5 +----
 lib/find_bit.c            | 17 ++++++++++++++++-
 5 files changed, 32 insertions(+), 20 deletions(-)

-- 
2.43.0

[PATCH 1/3] bitmap: generalize node_random()

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

Generalize node_random and make it available to general bitmaps and
cpumasks users.

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/find.h     |  2 ++
 include/linux/nodemask.h | 16 +---------------
 lib/find_bit.c           | 17 ++++++++++++++++-
 3 files changed, 19 insertions(+), 16 deletions(-)

diff --git a/include/linux/find.h b/include/linux/find.h
index 5a2c267ea7f9..98c61838002c 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -44,6 +44,8 @@ unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
 				long size, unsigned long offset);
 #endif
 
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index f08ae71585fa..1cedc7132b76 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -492,21 +492,7 @@ static __always_inline int num_node_state(enum node_states state)
 static __always_inline int node_random(const nodemask_t *maskp)
 {
 #if defined(CONFIG_NUMA) && (MAX_NUMNODES > 1)
-	int w, bit;
-
-	w = nodes_weight(*maskp);
-	switch (w) {
-	case 0:
-		bit = NUMA_NO_NODE;
-		break;
-	case 1:
-		bit = first_node(*maskp);
-		break;
-	default:
-		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_u32_below(w));
-		break;
-	}
-	return bit;
+	return find_random_bit(maskp->bits, MAX_NUMNODES);
 #else
 	return 0;
 #endif
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 06b6342aa3ae..2118ea23bed8 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -18,6 +18,7 @@
 #include <linux/math.h>
 #include <linux/minmax.h>
 #include <linux/swab.h>
+#include <linux/random.h>
 
 /*
  * Common helper for find_bit() function family
@@ -287,7 +288,21 @@ unsigned long _find_next_bit_le(const unsigned long *addr,
 	return FIND_NEXT_BIT(addr[idx], swab, size, offset);
 }
 EXPORT_SYMBOL(_find_next_bit_le);
-
 #endif
 
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
+{
+	int w = bitmap_weight(addr, size);
+
+	switch (w) {
+	case 0:
+		return size;
+	case 1:
+		return find_first_bit(addr, size);
+	default:
+		return find_nth_bit(addr, size, get_random_u32_below(w));
+	}
+}
+EXPORT_SYMBOL(find_random_bit);
+
 #endif /* __BIG_ENDIAN */
-- 
2.43.0

[PATCH 2/3] cpumask: introduce cpumask_random()

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

Propagate find_random_bit() to cpumask API.

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index ede95bbe8b80..4d3505acb5e0 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -354,6 +354,18 @@ unsigned int cpumask_next_wrap(int n, const struct cpumask *src)
 	return find_next_bit_wrap(cpumask_bits(src), small_cpumask_bits, n + 1);
 }
 
+/**
+ * cpumask_random - get random cpu in *src.
+ * @src: cpumask pointer
+ *
+ * Return: random set bit, or >= nr_cpu_ids if @src is empty.
+ */
+static __always_inline
+unsigned int cpumask_random(const struct cpumask *src)
+{
+	return find_random_bit(cpumask_bits(src), nr_cpu_ids);
+}
+
 /**
  * for_each_cpu - iterate over every cpu in a mask
  * @cpu: the (optionally unsigned) integer iterator
-- 
2.43.0

[PATCH 3/3] clocksource: improve randomness in clocksource_verify_choose_cpus()

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

The current algorithm of picking a random CPU works OK for dence online
cpumask, but if cpumask is non-dence, the distribution of picked CPUs
is skewed.

For example, on 8-CPU board with CPUs 4-7 offlined, the probability of
selecting CPU 0 is 5/8. Accordingly, cpus 1, 2 and 3 are chosen with
probability 1/8 each. The proper algorithm should pick each CPU with
probability 1/4.

Switch it to cpumask_random(), which has better statistical
characteristics.

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 kernel/time/clocksource.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c
index e400fe150f9d..0aef0e349e49 100644
--- a/kernel/time/clocksource.c
+++ b/kernel/time/clocksource.c
@@ -340,10 +340,7 @@ static void clocksource_verify_choose_cpus(void)
 	 * CPUs that are currently online.
 	 */
 	for (i = 1; i < n; i++) {
-		cpu = get_random_u32_below(nr_cpu_ids);
-		cpu = cpumask_next(cpu - 1, cpu_online_mask);
-		if (cpu >= nr_cpu_ids)
-			cpu = cpumask_first(cpu_online_mask);
+		cpu = cpumask_random(cpu_online_mask);
 		if (!WARN_ON_ONCE(cpu >= nr_cpu_ids))
 			cpumask_set_cpu(cpu, &cpus_chosen);
 	}
-- 
2.43.0

Re: [PATCH 1/3] bitmap: generalize node_random()

[Andrew Morton]

On Wed,  4 Jun 2025 17:21:21 -0400 Yury Norov <yury.norov@gmail.com> wrote:

> Generalize node_random and make it available to general bitmaps and
> cpumasks users.

Seems sensible.

> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
>  
> +unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
> +{
> +	int w = bitmap_weight(addr, size);
> +
> +	switch (w) {
> +	case 0:
> +		return size;
> +	case 1:
> +		return find_first_bit(addr, size);

Is the `1' special case useful?  The `default' case should still work OK?

> +	default:
> +		return find_nth_bit(addr, size, get_random_u32_below(w));
> +	}
> +}
> +EXPORT_SYMBOL(find_random_bit);

Some kerneldoc, please?

Of course, the hard-coding of get_random_u32_below() might be
unsuitable for some future potential callers but we can deal with that
if it ever occurs.

Re: [PATCH 1/3] bitmap: generalize node_random()

[Yury Norov]

On Wed, Jun 04, 2025 at 02:34:42PM -0700, Andrew Morton wrote:
> On Wed,  4 Jun 2025 17:21:21 -0400 Yury Norov <yury.norov@gmail.com> wrote:
> 
> > Generalize node_random and make it available to general bitmaps and
> > cpumasks users.
> 
> Seems sensible.
> 
> > --- a/lib/find_bit.c
> > +++ b/lib/find_bit.c
> >  
> > +unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
> > +{
> > +	int w = bitmap_weight(addr, size);
> > +
> > +	switch (w) {
> > +	case 0:
> > +		return size;
> > +	case 1:
> > +		return find_first_bit(addr, size);
> 
> Is the `1' special case useful?  The `default' case should still work OK?

find_first_bit() is faster that find_nth_bit(), so this is a
performance optimization. See 3e061d924fe9c7b4 ("lib/nodemask: optimize
node_random for nodemask with single NUMA node").
 
> > +	default:
> > +		return find_nth_bit(addr, size, get_random_u32_below(w));
> > +	}
> > +}
> > +EXPORT_SYMBOL(find_random_bit);
> 
> Some kerneldoc, please?

Indeed, will send v2.

> Of course, the hard-coding of get_random_u32_below() might be
> unsuitable for some future potential callers but we can deal with that
> if it ever occurs.

Can you please elaborate?

Thanks,
Yury

Re: [PATCH 1/3] bitmap: generalize node_random()

[Andrew Morton]

On Wed, 4 Jun 2025 17:46:59 -0400 Yury Norov <yury.norov@gmail.com> wrote:

> > Of course, the hard-coding of get_random_u32_below() might be
> > unsuitable for some future potential callers but we can deal with that
> > if it ever occurs.
> 
> Can you please elaborate?

Some callers might want to use a different random number generator. 
Seems unlikely, I know.

Re: [PATCH 3/3] clocksource: improve randomness in clocksource_verify_choose_cpus()

[John Stultz]

On Wed, Jun 4, 2025 at 2:21 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
>
> The current algorithm of picking a random CPU works OK for dence online

spelling nit: dence -> dense

> cpumask, but if cpumask is non-dence, the distribution of picked CPUs

same: non-dence -> non-dense


> is skewed.
>
> For example, on 8-CPU board with CPUs 4-7 offlined, the probability of
> selecting CPU 0 is 5/8. Accordingly, cpus 1, 2 and 3 are chosen with
> probability 1/8 each. The proper algorithm should pick each CPU with
> probability 1/4.
>
> Switch it to cpumask_random(), which has better statistical
> characteristics.
> Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> ---
>  kernel/time/clocksource.c | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)
>
> diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c
> index e400fe150f9d..0aef0e349e49 100644
> --- a/kernel/time/clocksource.c
> +++ b/kernel/time/clocksource.c
> @@ -340,10 +340,7 @@ static void clocksource_verify_choose_cpus(void)
>          * CPUs that are currently online.
>          */
>         for (i = 1; i < n; i++) {
> -               cpu = get_random_u32_below(nr_cpu_ids);
> -               cpu = cpumask_next(cpu - 1, cpu_online_mask);
> -               if (cpu >= nr_cpu_ids)
> -                       cpu = cpumask_first(cpu_online_mask);
> +               cpu = cpumask_random(cpu_online_mask);
>                 if (!WARN_ON_ONCE(cpu >= nr_cpu_ids))
>                         cpumask_set_cpu(cpu, &cpus_chosen);
>         }

This looks ok to me.   Again, just the smallest nit about the subject
line capitalization.

Acked-by: John Stultz <jstultz@google.com>

thanks
-john

[PATCH 1/3] bitmap: generalize node_random()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

Generalize node_random() and make it available to general bitmaps and
cpumasks users.

Notice, find_first_bit() is generally faster than find_nth_bit(), and we
employ it when there's a single set bit in the bitmap.

See commit 3e061d924fe9c7b4 ("lib/nodemask: optimize node_random for
nodemask with single NUMA node").

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/find.h     |  2 ++
 include/linux/nodemask.h | 17 +----------------
 lib/find_bit.c           | 24 ++++++++++++++++++++++++
 3 files changed, 27 insertions(+), 16 deletions(-)

diff --git a/include/linux/find.h b/include/linux/find.h
index 5a2c267ea7f9..98c61838002c 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -44,6 +44,8 @@ unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
 				long size, unsigned long offset);
 #endif
 
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index f08ae71585fa..d49f3bd3e20b 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -91,7 +91,6 @@
 #include <linux/bitmap.h>
 #include <linux/minmax.h>
 #include <linux/nodemask_types.h>
-#include <linux/random.h>
 
 extern nodemask_t _unused_nodemask_arg_;
 
@@ -492,21 +491,7 @@ static __always_inline int num_node_state(enum node_states state)
 static __always_inline int node_random(const nodemask_t *maskp)
 {
 #if defined(CONFIG_NUMA) && (MAX_NUMNODES > 1)
-	int w, bit;
-
-	w = nodes_weight(*maskp);
-	switch (w) {
-	case 0:
-		bit = NUMA_NO_NODE;
-		break;
-	case 1:
-		bit = first_node(*maskp);
-		break;
-	default:
-		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_u32_below(w));
-		break;
-	}
-	return bit;
+	return find_random_bit(maskp->bits, MAX_NUMNODES);
 #else
 	return 0;
 #endif
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 06b6342aa3ae..d4b5a29e3e72 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -18,6 +18,7 @@
 #include <linux/math.h>
 #include <linux/minmax.h>
 #include <linux/swab.h>
+#include <linux/random.h>
 
 /*
  * Common helper for find_bit() function family
@@ -291,3 +292,26 @@ EXPORT_SYMBOL(_find_next_bit_le);
 #endif
 
 #endif /* __BIG_ENDIAN */
+
+/**
+ * find_random_bit - find a set bit at random position
+ * @addr: The address to base the search on
+ * @size: The bitmap size in bits
+ *
+ * Returns: a position of a random set bit; >= @size otherwise
+ */
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
+{
+	int w = bitmap_weight(addr, size);
+
+	switch (w) {
+	case 0:
+		return size;
+	case 1:
+		/* Performance trick for single-bit bitmaps */
+		return find_first_bit(addr, size);
+	default:
+		return find_nth_bit(addr, size, get_random_u32_below(w));
+	}
+}
+EXPORT_SYMBOL(find_random_bit);
-- 
2.43.0

Re: [PATCH 1/3] bitmap: generalize node_random()

[kernel test robot]

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on akpm-mm/mm-nonmm-unstable]
[also build test ERROR on tip/timers/core akpm-mm/mm-everything linus/master v6.15 next-20250606]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-generalize-node_random/20250609-034657
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20250608194536.28130-2-yury.norov%40gmail.com
patch subject: [PATCH 1/3] bitmap: generalize node_random()
config: arm-randconfig-002-20250609 (https://download.01.org/0day-ci/archive/20250609/202506090550.y3ypu2EO-lkp@intel.com/config)
compiler: clang version 17.0.6 (https://github.com/llvm/llvm-project 6009708b4367171ccdbf4b5905cb6a803753fe18)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250609/202506090550.y3ypu2EO-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202506090550.y3ypu2EO-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from ./arch/arm/include/generated/asm/preempt.h:1:
   In file included from include/asm-generic/preempt.h:5:
   In file included from include/linux/thread_info.h:27:
   In file included from include/linux/bitops.h:29:
   include/asm-generic/bitops/generic-non-atomic.h:140:16: warning: attribute 'error' is already applied with different arguments [-Wignored-attributes]
     140 |         return 1UL & (smp_load_acquire(p) >> (nr & (BITS_PER_LONG-1)));
         |                       ^
   include/asm-generic/barrier.h:204:37: note: expanded from macro 'smp_load_acquire'
     204 |         __unqual_scalar_typeof(*p) ___p1 = READ_ONCE(*p);               \
         |                                            ^
   include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
      49 |         compiletime_assert_rwonce_type(x);                              \
         |         ^
   include/asm-generic/rwonce.h:36:2: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^
   include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
     565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^
   include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
     547 |                         __compiletime_error(msg);                       \
         |                         ^
   include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
     138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
         |                                                        ^
   include/linux/mm.h:2618:9: note: previous attribute is here
    2618 |         return max(mm->hiwater_rss, get_mm_rss(mm));
         |                ^
   include/linux/minmax.h:112:19: note: expanded from macro 'max'
     112 | #define max(x, y)       __careful_cmp(max, x, y)
         |                         ^
   include/linux/minmax.h:98:2: note: expanded from macro '__careful_cmp'
      98 |         __careful_cmp_once(op, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))
         |         ^
   include/linux/minmax.h:93:2: note: expanded from macro '__careful_cmp_once'
      93 |         BUILD_BUG_ON_MSG(!__types_ok(ux, uy),           \
         |         ^
   note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
   include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
     565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^
   include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
     547 |                         __compiletime_error(msg);                       \
         |                         ^
   include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
     138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
         |                                                        ^
   In file included from crypto/krb5/rfc8009_aes2.c:10:
   In file included from include/linux/slab.h:16:
   In file included from include/linux/gfp.h:7:
   In file included from include/linux/mmzone.h:8:
   In file included from include/linux/spinlock.h:56:
   In file included from include/linux/preempt.h:79:
   In file included from ./arch/arm/include/generated/asm/preempt.h:1:
   In file included from include/asm-generic/preempt.h:5:
   In file included from include/linux/thread_info.h:27:
   In file included from include/linux/bitops.h:29:
   include/asm-generic/bitops/generic-non-atomic.h:140:16: warning: attribute 'error' is already applied with different arguments [-Wignored-attributes]
     140 |         return 1UL & (smp_load_acquire(p) >> (nr & (BITS_PER_LONG-1)));
         |                       ^
   include/asm-generic/barrier.h:204:37: note: expanded from macro 'smp_load_acquire'
     204 |         __unqual_scalar_typeof(*p) ___p1 = READ_ONCE(*p);               \
         |                                            ^
   include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
      49 |         compiletime_assert_rwonce_type(x);                              \
         |         ^
   include/asm-generic/rwonce.h:36:2: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^
   include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
     565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^
   include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
     547 |                         __compiletime_error(msg);                       \
         |                         ^
   include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
     138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
         |                                                        ^
   include/linux/mm.h:2623:9: note: previous attribute is here
    2623 |         return max(mm->hiwater_vm, mm->total_vm);
         |                ^
   include/linux/minmax.h:112:19: note: expanded from macro 'max'
     112 | #define max(x, y)       __careful_cmp(max, x, y)
         |                         ^
   include/linux/minmax.h:98:2: note: expanded from macro '__careful_cmp'
      98 |         __careful_cmp_once(op, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))
         |         ^
   include/linux/minmax.h:93:2: note: expanded from macro '__careful_cmp_once'
      93 |         BUILD_BUG_ON_MSG(!__types_ok(ux, uy),           \
         |         ^
   note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
   include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
     565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^
   include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
     547 |                         __compiletime_error(msg);                       \
         |                         ^
   include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
     138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
         |                                                        ^
>> crypto/krb5/rfc8009_aes2.c:209:3: error: call to undeclared function 'get_random_bytes'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     209 |                 get_random_bytes(buffer, krb5->conf_len);
         |                 ^
   27 warnings and 1 error generated.


vim +/get_random_bytes +209 crypto/krb5/rfc8009_aes2.c

6c3c0e86c2acf5 David Howells 2025-02-03  167  
6c3c0e86c2acf5 David Howells 2025-02-03  168  /*
6c3c0e86c2acf5 David Howells 2025-02-03  169   * Apply encryption and checksumming functions to a message.  Unlike for
6c3c0e86c2acf5 David Howells 2025-02-03  170   * RFC3961, for RFC8009, we have to chuck the starting IV into the hash first.
6c3c0e86c2acf5 David Howells 2025-02-03  171   */
6c3c0e86c2acf5 David Howells 2025-02-03  172  static ssize_t rfc8009_encrypt(const struct krb5_enctype *krb5,
6c3c0e86c2acf5 David Howells 2025-02-03  173  			       struct crypto_aead *aead,
6c3c0e86c2acf5 David Howells 2025-02-03  174  			       struct scatterlist *sg, unsigned int nr_sg, size_t sg_len,
6c3c0e86c2acf5 David Howells 2025-02-03  175  			       size_t data_offset, size_t data_len,
6c3c0e86c2acf5 David Howells 2025-02-03  176  			       bool preconfounded)
6c3c0e86c2acf5 David Howells 2025-02-03  177  {
6c3c0e86c2acf5 David Howells 2025-02-03  178  	struct aead_request *req;
6c3c0e86c2acf5 David Howells 2025-02-03  179  	struct scatterlist bsg[2];
6c3c0e86c2acf5 David Howells 2025-02-03  180  	ssize_t ret, done;
6c3c0e86c2acf5 David Howells 2025-02-03  181  	size_t bsize, base_len, secure_offset, secure_len, pad_len, cksum_offset;
6c3c0e86c2acf5 David Howells 2025-02-03  182  	void *buffer;
6c3c0e86c2acf5 David Howells 2025-02-03  183  	u8 *iv, *ad;
6c3c0e86c2acf5 David Howells 2025-02-03  184  
6c3c0e86c2acf5 David Howells 2025-02-03  185  	if (WARN_ON(data_offset != krb5->conf_len))
6c3c0e86c2acf5 David Howells 2025-02-03  186  		return -EINVAL; /* Data is in wrong place */
6c3c0e86c2acf5 David Howells 2025-02-03  187  
6c3c0e86c2acf5 David Howells 2025-02-03  188  	secure_offset	= 0;
6c3c0e86c2acf5 David Howells 2025-02-03  189  	base_len	= krb5->conf_len + data_len;
6c3c0e86c2acf5 David Howells 2025-02-03  190  	pad_len		= 0;
6c3c0e86c2acf5 David Howells 2025-02-03  191  	secure_len	= base_len + pad_len;
6c3c0e86c2acf5 David Howells 2025-02-03  192  	cksum_offset	= secure_len;
6c3c0e86c2acf5 David Howells 2025-02-03  193  	if (WARN_ON(cksum_offset + krb5->cksum_len > sg_len))
6c3c0e86c2acf5 David Howells 2025-02-03  194  		return -EFAULT;
6c3c0e86c2acf5 David Howells 2025-02-03  195  
6c3c0e86c2acf5 David Howells 2025-02-03  196  	bsize = krb5_aead_size(aead) +
6c3c0e86c2acf5 David Howells 2025-02-03  197  		krb5_aead_ivsize(aead) * 2;
6c3c0e86c2acf5 David Howells 2025-02-03  198  	buffer = kzalloc(bsize, GFP_NOFS);
6c3c0e86c2acf5 David Howells 2025-02-03  199  	if (!buffer)
6c3c0e86c2acf5 David Howells 2025-02-03  200  		return -ENOMEM;
6c3c0e86c2acf5 David Howells 2025-02-03  201  
6c3c0e86c2acf5 David Howells 2025-02-03  202  	req = buffer;
6c3c0e86c2acf5 David Howells 2025-02-03  203  	iv = buffer + krb5_aead_size(aead);
6c3c0e86c2acf5 David Howells 2025-02-03  204  	ad = buffer + krb5_aead_size(aead) + krb5_aead_ivsize(aead);
6c3c0e86c2acf5 David Howells 2025-02-03  205  
6c3c0e86c2acf5 David Howells 2025-02-03  206  	/* Insert the confounder into the buffer */
6c3c0e86c2acf5 David Howells 2025-02-03  207  	ret = -EFAULT;
6c3c0e86c2acf5 David Howells 2025-02-03  208  	if (!preconfounded) {
6c3c0e86c2acf5 David Howells 2025-02-03 @209  		get_random_bytes(buffer, krb5->conf_len);
6c3c0e86c2acf5 David Howells 2025-02-03  210  		done = sg_pcopy_from_buffer(sg, nr_sg, buffer, krb5->conf_len,
6c3c0e86c2acf5 David Howells 2025-02-03  211  					    secure_offset);
6c3c0e86c2acf5 David Howells 2025-02-03  212  		if (done != krb5->conf_len)
6c3c0e86c2acf5 David Howells 2025-02-03  213  			goto error;
6c3c0e86c2acf5 David Howells 2025-02-03  214  	}
6c3c0e86c2acf5 David Howells 2025-02-03  215  
6c3c0e86c2acf5 David Howells 2025-02-03  216  	/* We may need to pad out to the crypto blocksize. */
6c3c0e86c2acf5 David Howells 2025-02-03  217  	if (pad_len) {
6c3c0e86c2acf5 David Howells 2025-02-03  218  		done = sg_zero_buffer(sg, nr_sg, pad_len, data_offset + data_len);
6c3c0e86c2acf5 David Howells 2025-02-03  219  		if (done != pad_len)
6c3c0e86c2acf5 David Howells 2025-02-03  220  			goto error;
6c3c0e86c2acf5 David Howells 2025-02-03  221  	}
6c3c0e86c2acf5 David Howells 2025-02-03  222  
6c3c0e86c2acf5 David Howells 2025-02-03  223  	/* We need to include the starting IV in the hash. */
6c3c0e86c2acf5 David Howells 2025-02-03  224  	sg_init_table(bsg, 2);
6c3c0e86c2acf5 David Howells 2025-02-03  225  	sg_set_buf(&bsg[0], ad, krb5_aead_ivsize(aead));
6c3c0e86c2acf5 David Howells 2025-02-03  226  	sg_chain(bsg, 2, sg);
6c3c0e86c2acf5 David Howells 2025-02-03  227  
6c3c0e86c2acf5 David Howells 2025-02-03  228  	/* Hash and encrypt the message. */
6c3c0e86c2acf5 David Howells 2025-02-03  229  	aead_request_set_tfm(req, aead);
6c3c0e86c2acf5 David Howells 2025-02-03  230  	aead_request_set_callback(req, 0, NULL, NULL);
6c3c0e86c2acf5 David Howells 2025-02-03  231  	aead_request_set_ad(req, krb5_aead_ivsize(aead));
6c3c0e86c2acf5 David Howells 2025-02-03  232  	aead_request_set_crypt(req, bsg, bsg, secure_len, iv);
6c3c0e86c2acf5 David Howells 2025-02-03  233  	ret = crypto_aead_encrypt(req);
6c3c0e86c2acf5 David Howells 2025-02-03  234  	if (ret < 0)
6c3c0e86c2acf5 David Howells 2025-02-03  235  		goto error;
6c3c0e86c2acf5 David Howells 2025-02-03  236  
6c3c0e86c2acf5 David Howells 2025-02-03  237  	ret = secure_len + krb5->cksum_len;
6c3c0e86c2acf5 David Howells 2025-02-03  238  
6c3c0e86c2acf5 David Howells 2025-02-03  239  error:
6c3c0e86c2acf5 David Howells 2025-02-03  240  	kfree_sensitive(buffer);
6c3c0e86c2acf5 David Howells 2025-02-03  241  	return ret;
6c3c0e86c2acf5 David Howells 2025-02-03  242  }
6c3c0e86c2acf5 David Howells 2025-02-03  243  

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 1/3] bitmap: generalize node_random()

[Yury Norov]

On Mon, Jun 09, 2025 at 05:44:47AM +0800, kernel test robot wrote:
> Hi Yury,
> 
> kernel test robot noticed the following build errors:
> 
> [auto build test ERROR on akpm-mm/mm-nonmm-unstable]
> [also build test ERROR on tip/timers/core akpm-mm/mm-everything linus/master v6.15 next-20250606]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch#_base_tree_information]
> 
> url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-generalize-node_random/20250609-034657
> base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
> patch link:    https://lore.kernel.org/r/20250608194536.28130-2-yury.norov%40gmail.com
> patch subject: [PATCH 1/3] bitmap: generalize node_random()
> config: arm-randconfig-002-20250609 (https://download.01.org/0day-ci/archive/20250609/202506090550.y3ypu2EO-lkp@intel.com/config)
> compiler: clang version 17.0.6 (https://github.com/llvm/llvm-project 6009708b4367171ccdbf4b5905cb6a803753fe18)
> reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250609/202506090550.y3ypu2EO-lkp@intel.com/reproduce)
> 
> If you fix the issue in a separate patch/commit (i.e. not just a new version of
> the same patch/commit), kindly add following tags
> | Reported-by: kernel test robot <lkp@intel.com>
> | Closes: https://lore.kernel.org/oe-kbuild-all/202506090550.y3ypu2EO-lkp@intel.com/
> 
> All errors (new ones prefixed by >>):
> 
>    In file included from ./arch/arm/include/generated/asm/preempt.h:1:
>    In file included from include/asm-generic/preempt.h:5:
>    In file included from include/linux/thread_info.h:27:
>    In file included from include/linux/bitops.h:29:
>    include/asm-generic/bitops/generic-non-atomic.h:140:16: warning: attribute 'error' is already applied with different arguments [-Wignored-attributes]
>      140 |         return 1UL & (smp_load_acquire(p) >> (nr & (BITS_PER_LONG-1)));
>          |                       ^
>    include/asm-generic/barrier.h:204:37: note: expanded from macro 'smp_load_acquire'
>      204 |         __unqual_scalar_typeof(*p) ___p1 = READ_ONCE(*p);               \
>          |                                            ^
>    include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
>       49 |         compiletime_assert_rwonce_type(x);                              \
>          |         ^
>    include/asm-generic/rwonce.h:36:2: note: expanded from macro 'compiletime_assert_rwonce_type'
>       36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
>          |         ^
>    include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
>      565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
>          |         ^
>    include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
>      547 |                         __compiletime_error(msg);                       \
>          |                         ^
>    include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
>      138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
>          |                                                        ^
>    include/linux/mm.h:2618:9: note: previous attribute is here
>     2618 |         return max(mm->hiwater_rss, get_mm_rss(mm));
>          |                ^
>    include/linux/minmax.h:112:19: note: expanded from macro 'max'
>      112 | #define max(x, y)       __careful_cmp(max, x, y)
>          |                         ^
>    include/linux/minmax.h:98:2: note: expanded from macro '__careful_cmp'
>       98 |         __careful_cmp_once(op, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))
>          |         ^
>    include/linux/minmax.h:93:2: note: expanded from macro '__careful_cmp_once'
>       93 |         BUILD_BUG_ON_MSG(!__types_ok(ux, uy),           \
>          |         ^
>    note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
>    include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
>      565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
>          |         ^
>    include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
>      547 |                         __compiletime_error(msg);                       \
>          |                         ^
>    include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
>      138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
>          |                                                        ^
>    In file included from crypto/krb5/rfc8009_aes2.c:10:
>    In file included from include/linux/slab.h:16:
>    In file included from include/linux/gfp.h:7:
>    In file included from include/linux/mmzone.h:8:
>    In file included from include/linux/spinlock.h:56:
>    In file included from include/linux/preempt.h:79:
>    In file included from ./arch/arm/include/generated/asm/preempt.h:1:
>    In file included from include/asm-generic/preempt.h:5:
>    In file included from include/linux/thread_info.h:27:
>    In file included from include/linux/bitops.h:29:
>    include/asm-generic/bitops/generic-non-atomic.h:140:16: warning: attribute 'error' is already applied with different arguments [-Wignored-attributes]
>      140 |         return 1UL & (smp_load_acquire(p) >> (nr & (BITS_PER_LONG-1)));
>          |                       ^
>    include/asm-generic/barrier.h:204:37: note: expanded from macro 'smp_load_acquire'
>      204 |         __unqual_scalar_typeof(*p) ___p1 = READ_ONCE(*p);               \
>          |                                            ^
>    include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
>       49 |         compiletime_assert_rwonce_type(x);                              \
>          |         ^
>    include/asm-generic/rwonce.h:36:2: note: expanded from macro 'compiletime_assert_rwonce_type'
>       36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
>          |         ^
>    include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
>      565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
>          |         ^
>    include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
>      547 |                         __compiletime_error(msg);                       \
>          |                         ^
>    include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
>      138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
>          |                                                        ^
>    include/linux/mm.h:2623:9: note: previous attribute is here
>     2623 |         return max(mm->hiwater_vm, mm->total_vm);
>          |                ^
>    include/linux/minmax.h:112:19: note: expanded from macro 'max'
>      112 | #define max(x, y)       __careful_cmp(max, x, y)
>          |                         ^
>    include/linux/minmax.h:98:2: note: expanded from macro '__careful_cmp'
>       98 |         __careful_cmp_once(op, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))
>          |         ^
>    include/linux/minmax.h:93:2: note: expanded from macro '__careful_cmp_once'
>       93 |         BUILD_BUG_ON_MSG(!__types_ok(ux, uy),           \
>          |         ^
>    note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
>    include/linux/compiler_types.h:565:2: note: expanded from macro 'compiletime_assert'
>      565 |         __compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
>          |         ^
>    include/linux/compiler_types.h:547:4: note: expanded from macro '__compiletime_assert'
>      547 |                         __compiletime_error(msg);                       \
>          |                         ^
>    include/linux/compiler_attributes.h:138:56: note: expanded from macro '__compiletime_error'
>      138 | # define __compiletime_error(msg)       __attribute__((__error__(msg)))
>          |                                                        ^
> >> crypto/krb5/rfc8009_aes2.c:209:3: error: call to undeclared function 'get_random_bytes'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
>      209 |                 get_random_bytes(buffer, krb5->conf_len);
>          |                 ^
>    27 warnings and 1 error generated.

OK, I'll enable those locally, buld-test and send a v3.