bitmap patches for v6.1-rc1

bitmap patches for v6.1-rc1

[Yury Norov]

The following changes since commit 7e18e42e4b280c85b76967a9106a13ca61c16179:

  Linux 6.0-rc4 (2022-09-04 13:10:01 -0700)

are available in the Git repository at:

  https://github.com/norov/linux.git tags/bitmap-6.1-rc1

for you to fetch changes up to 585463f0d58aa4d29b744c7c53b222b8028de87f:

  sched/core: Merge cpumask_andnot()+for_each_cpu() into for_each_cpu_andnot() (2022-10-06 05:57:36 -0700)

----------------------------------------------------------------
bitmap patches for v6.1-rc1

Hi Linus,

Please pull this patches. They spent more than a week in -next without
major problems.

The only problem with warnings generated by cpumask_check(), when robots
do bisection, is fixed by moving the patch "cpumask: fix checking valid
cpu range" to the very end of the sub-series.

I decided to include Valentin's series because it matches with the rest
of the work very well.

The patch "lib/bitmap: remove bitmap_ord_to_pos" conflicts with 
"lib/nodemask: optimize node_random for nodemask with single NUMA node"
from Aneesh Kumar K.V. The patch is in Andrew Morton's tree, and as of
today is not merged in mainline. Correct merge of the chunk that conflicts
should look like this:

  static 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_int() % w);
                  break;
          }
          return bit;
  #else
          return 0;
  #endif
  }

Also, it looks like Phil's patch is already in master, merged through
Greg's tree.

Thanks,
Yury


From Phil Auld:
drivers/base: Fix unsigned comparison to -1 in CPUMAP_FILE_MAX_BYTES

From me:
cpumask: cleanup nr_cpu_ids vs nr_cpumask_bits mess

This series cleans that mess and adds new config FORCE_NR_CPUS that
allows to optimize cpumask subsystem if the number of CPUs is known
at compile-time.

From me:
lib: optimize find_bit() functions

Reworks find_bit() functions based on new FIND_{FIRST,NEXT}_BIT() macros.

From me:
lib/find: add find_nth_bit()

Adds find_nth_bit(), which is ~70 times faster than bitcounting with
for_each() loop:
        for_each_set_bit(bit, mask, size)
                if (n-- == 0)
                        return bit;

Also adds bitmap_weight_and() to let people replace this pattern:
	tmp = bitmap_alloc(nbits);
	bitmap_and(tmp, map1, map2, nbits);
	weight = bitmap_weight(tmp, nbits);
	bitmap_free(tmp);
with a single bitmap_weight_and() call.

From me:
cpumask: repair cpumask_check()

After switching cpumask to use nr_cpu_ids, cpumask_check() started
generating many false-positive warnings. This series fixes it.

From Valentin Schneider:
bitmap,cpumask: Add for_each_cpu_andnot() and for_each_cpu_andnot()

Extends the API with one more function and applies it in sched/core.

----------------------------------------------------------------
Phil Auld (1):
      drivers/base: Fix unsigned comparison to -1 in CPUMAP_FILE_MAX_BYTES

Valentin Schneider (4):
      lib/find_bit: Introduce find_next_andnot_bit()
      cpumask: Introduce for_each_cpu_andnot()
      lib/test_cpumask: Add for_each_cpu_and(not) tests
      sched/core: Merge cpumask_andnot()+for_each_cpu() into for_each_cpu_andnot()

Yury Norov (23):
      smp: don't declare nr_cpu_ids if NR_CPUS == 1
      smp: add set_nr_cpu_ids()
      lib/cpumask: delete misleading comment
      lib/cpumask: deprecate nr_cpumask_bits
      powerpc/64: don't refer nr_cpu_ids in asm code when it's undefined
      lib/cpumask: add FORCE_NR_CPUS config option
      lib/find_bit: introduce FIND_FIRST_BIT() macro
      lib/find_bit: create find_first_zero_bit_le()
      lib/find_bit: optimize find_next_bit() functions
      tools: sync find_bit() implementation
      lib/bitmap: don't call __bitmap_weight() in kernel code
      lib/bitmap: add bitmap_weight_and()
      lib: add find_nth{,_and,_andnot}_bit()
      lib/bitmap: add tests for find_nth_bit()
      lib/bitmap: remove bitmap_ord_to_pos
      cpumask: add cpumask_nth_{,and,andnot}
      net: fix cpu_max_bits_warn() usage in netif_attrmask_next{,_and}
      cpumask: switch for_each_cpu{,_not} to use for_each_bit()
      lib/find_bit: add find_next{,_and}_bit_wrap
      lib/bitmap: introduce for_each_set_bit_wrap() macro
      lib/find: optimize for_each() macros
      lib/bitmap: add tests for for_each() loops
      cpumask: fix checking valid cpu range

 arch/loongarch/kernel/setup.c |   2 +-
 arch/mips/kernel/setup.c      |   2 +-
 arch/powerpc/kernel/head_64.S |   4 +
 arch/x86/kernel/smpboot.c     |   4 +-
 arch/x86/xen/smp_pv.c         |   2 +-
 fs/ntfs3/bitmap.c             |   4 +-
 include/linux/bitmap.h        |  13 +-
 include/linux/bitops.h        |  19 +++
 include/linux/cpumask.h       | 137 ++++++++++++++-----
 include/linux/find.h          | 310 ++++++++++++++++++++++++++++++++++++------
 include/linux/netdevice.h     |  10 +-
 include/linux/nodemask.h      |   3 +-
 kernel/sched/core.c           |   5 +-
 kernel/smp.c                  |   6 +-
 lib/Kconfig                   |   9 ++
 lib/bitmap.c                  |  68 ++++-----
 lib/cpumask.c                 |  40 +++---
 lib/cpumask_kunit.c           |  19 +++
 lib/find_bit.c                | 233 +++++++++++++++++++++----------
 lib/find_bit_benchmark.c      |  18 +++
 lib/test_bitmap.c             | 291 ++++++++++++++++++++++++++++++++++++++-
 tools/include/linux/find.h    |  61 ++-------
 tools/lib/find_bit.c          | 149 ++++++++++----------
 23 files changed, 1038 insertions(+), 371 deletions(-)