[RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing

[RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing

[K Prateek Nayak]

Resending the series with the correct Email IDs this time. Sorry for the
noise.

This is the combined successor to the following two series:

https://lore.kernel.org/lkml/20250904041516.3046-1-kprateek.nayak@amd.com/
https://lore.kernel.org/lkml/20250409111539.23791-1-kprateek.nayak@amd.com/

Most bits are same except for more initial cleanups. Changelog is
attached towards the end. This topic will be discussed at LPC'25 in the
"Scheduler and Real-Time MC" - jump to "LPC 2025" to know what will be
discussed.


Problem statement
=================

This series tackles three problems:

1. The busy load balancing always uses the first CPU of
   group_balance_mask() for load balancing which puts all the load
   balancing responsibility on a single CPU.

2. The "nohz.nr_idle" and "nohz.idle_cpus" are global system-wide
   variables that can run into scalability bottlenecks on a large
   core-count system.

3. Periodic balance can take a long time to even out imbalance on
   systems with mostly large and flat sched-domain hierarchy. Preempted
   tasks may wait for a long time behind other runnable tasks increasing
   the tail latencies.

This series aims at addressing the combined problems listed above.


Implementation details
======================

Note: Sections marked EXPERIMENTAL are known to introduce regeressions
for certain benchmarks. These have been discussed in details in the next
section. These patches also may be incomplete from a schedstats
accounting standpoint.


o Busy balancing optimization

The busy balance CPU is always the first cpu of
"sched_group->scg->group_balance_mask". "sgc" object is shared by all
the CPUs on the "group_balance_mask", even for the overlapping domains.

To keep overheads minimal, a simple "busy_balance_cpu" is maintained in
the shared "sgc" object. A CPU is nominated to handle the busy
balancing. Once the CPU is done with its turn, it nominates the next CPU
on the group_balance_mask.

  - Advantages: The responsibility of busy balance is rotated among the
    CPUs on the group_balance_mask. Maintaining the "busy_balance_cpu"
    only requires a READ_ONCE() / WRITE_ONCE() modifications making it
    relatively cheap.

  - Disadvantages: The currently nominated "busy_balance_cpu" can run
    for a long time with bh disabled that can prevent balancing work
    from running however, it is no worse that the current state where
    the first CPU continues running with bh disabled for a prolonged
    period of time.


o Centralized "nohz" accounting optimizations

The centralized "nohz" tracking maintains the number and list of CPUs
that are in nohz idle state. These are done via atomic operations on
variables shared across the system which is less than ideal.

Peter suggested breaking the mask down and embedding it into the
sched_domain hierarchy which would minimize atomic operations on the
global variables.

There are 2 possible ways to implement this:

1. Maintain the idle CPUs mask in sched_domain_shared. Also construct a
   hierarchy of the sched_domain_shared objects which can be used to
   propagate a signal up to the topmost domain.

   - Advantages: Distributed tracking. Less atomic operations on the
     global variables.

   - Disadvantages: Number of atomic ops can scale with the depth of the
     hierarchy with multiple cache lines being possibly shared between
     multiple NUMA domains.

2. [Implemented in this series] Maintain the idle CPUs mask in
   sched_domain_shared. String all the sched_domain_shared objects in a
   global list which is used for traversing all nohz idle CPUs during
   load balancing.

   Maintain a global "nrr_doms" indicator that is only updated when the
   first CPU is added to the LLC local mask / last CPU leaves the LLC
   local mask.

   - Advantages: Distributed tracking. Simpler implementation.

   - Disadvantages: Number of atomic ops to global "nr_doms" can scale
     with the number of LLC domains, however the changes in the boundary
     conditions are still less frequent than the current global scheme.

The nohz_idle_cpus mask is also inherently optimized by retaining a CPU
on the mask until the first tick and is not immediately cleared when the
ticks are enabled again / at idle exit.


o [EXPERIMENTAL] Push-based load balancing

Proactively push tasks to idle CPUs within an LLC domain. Push-based
load balancing is found to be a delicate balancing act where delaying
running the tasks, especially if their runtime is small, can lead to
performance regressions.

There are cases, especially with larger benchmarks where pushing the
tasks more proactively helps with performance however, a number of
microbenchmark suffer as a result of additional work the busy CPU has to
do to to push a preempted task.


o [EXPERIMENTAL] Optimizing Intra-NUMA newidle balancing

On a CONFIG_PREEMPTION enabled kernel, newidle balance only pulls one
task to keep the latency of balancing low. Despite the effort to keep
the latency low, the newidle balance ends up computing a great deal of
stats just to pull a single task at best.

Instead of following the usual path, directly traverse CPUs for newidle
balance in search of CPUs to pull load from.

This too is found to have interesting effects on benchmarks where CPUs
can converge on single target to pull tasks from causing some amount of
lock contention.

More interestingly, a number of benchmarks seem to regress if the
newidle balance yields on spotting (nr_running > 1 || ttwu_pending)
instead of just proceeding to scan the entire domain and bail at the
end.


Benchmark results
=================

Results for some variants are incomplete as a result of setup issues
(and my sheer incompetence to revert some of the changes I made when
analyzing the benchmarks)

I'll update these as and when the runs (and re-runs) complete but as the
moment, this is how the different [EXPERIMENTAL] bits stack up from
benchmarking perspective on a dual socket 3rd Generation EPYC system (2
x 64C/128T)

  ==================================================================
  Test          : hackbench
  Units         : Normalized time in seconds
  Interpretation: Lower is better
  Statistic     : AMean
  ==================================================================
  Case:           tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV) push+newidle[pct imp](CV)
   1-groups     1.00 [ -0.00]( 5.58)     1.01 [ -1.10](14.77)     1.01 [ -0.66]( 8.80)     1.03 [ -2.85]( 6.13)
   2-groups     1.00 [ -0.00]( 9.58)     1.02 [ -2.41]( 3.09)     1.00 [  0.22]( 5.62)     1.02 [ -1.97]( 4.54)
   4-groups     1.00 [ -0.00]( 2.11)     0.99 [  1.48]( 2.30)     1.00 [ -0.21]( 2.60)     1.03 [ -2.54]( 2.82)
   8-groups     1.00 [ -0.00]( 2.07)     1.02 [ -2.31]( 2.98)     1.15 [-14.79]( 2.15)     1.13 [-12.63]( 2.57)
  16-groups     1.00 [ -0.00]( 3.55)     1.09 [ -8.57]( 7.80)     1.04 [ -3.64]( 3.89)     1.04 [ -4.33]( 1.36)


  ==================================================================
  Test          : tbench
  Units         : Normalized throughput
  Interpretation: Higher is better
  Statistic     : AMean
  ==================================================================
  Clients:    tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
      1     1.00 [  0.00]( 0.29)     1.01 [  0.63]( 0.68)     1.00 [ -0.15]( 0.96)       0.99 [ -1.46]( 0.25)
      2     1.00 [  0.00]( 0.55)     1.00 [ -0.09]( 0.21)     1.00 [  0.47]( 0.46)       0.99 [ -1.36]( 0.54)
      4     1.00 [  0.00]( 0.33)     0.99 [ -0.83]( 0.54)     1.01 [  0.76]( 0.36)       0.98 [ -1.51]( 0.20)
      8     1.00 [  0.00]( 0.75)     1.00 [ -0.42]( 1.14)     1.01 [  0.96]( 0.49)       0.99 [ -0.64]( 0.34)
     16     1.00 [  0.00]( 0.98)     0.99 [ -0.70]( 1.23)     0.97 [ -2.55]( 0.73)       0.98 [ -1.80]( 1.62)
     32     1.00 [  0.00]( 0.04)     0.98 [ -2.32]( 1.14)     0.98 [ -1.94]( 0.86)       0.98 [ -2.02]( 0.64)
     64     1.00 [  0.00]( 1.27)     0.94 [ -5.51]( 3.69)     0.97 [ -3.45]( 1.28)       0.99 [ -1.49]( 1.68)
    128     1.00 [  0.00]( 0.69)     1.00 [ -0.05]( 2.34)     1.01 [  0.79]( 0.93)       0.99 [ -1.16]( 0.68)
    256     1.00 [  0.00]( 5.60)     0.97 [ -2.67]( 5.28)     1.00 [  0.34]( 1.23)       0.98 [ -2.16]( 7.10)
    512     1.00 [  0.00]( 0.90)     1.00 [ -0.38]( 0.86)     1.01 [  0.53]( 0.10)       0.98 [ -1.88]( 0.09)
   1024     1.00 [  0.00]( 0.25)     0.99 [ -1.01]( 0.37)     1.01 [  0.91]( 0.53)       0.98 [ -1.58]( 0.32)


  ==================================================================
  Test          : stream-10
  Units         : Normalized Bandwidth, MB/s
  Interpretation: Higher is better
  Statistic     : HMean
  ==================================================================
  Test:       tip[pct imp](CV)      push_only[pct imp](CV)   newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
   Copy     1.00 [  0.00]( 4.37)     0.97 [ -2.82]( 8.57)     0.99 [ -1.31]( 6.75)       0.97 [ -3.34]( 6.18)
  Scale     1.00 [  0.00]( 2.75)     0.99 [ -0.73]( 3.62)     0.99 [ -0.86]( 3.73)       0.99 [ -1.49]( 5.39)
    Add     1.00 [  0.00]( 3.54)     0.98 [ -2.40]( 3.99)     0.98 [ -1.51]( 4.12)       0.97 [ -3.27]( 6.28)
  Triad     1.00 [  0.00]( 4.41)     0.98 [ -1.71]( 7.00)     1.01 [  0.55]( 3.77)       0.96 [ -4.32]( 7.49)


  ==================================================================
  Test          : stream-100
  Units         : Normalized Bandwidth, MB/s
  Interpretation: Higher is better
  Statistic     : HMean
  ==================================================================
  Test:       tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
   Copy     1.00 [  0.00]( 3.25)     0.96 [ -4.08]( 3.07)     0.98 [ -1.56]( 3.45)       0.97 [ -2.74]( 2.00)
  Scale     1.00 [  0.00]( 1.49)     0.98 [ -2.25]( 4.13)     0.98 [ -1.86]( 4.32)       0.99 [ -1.19]( 1.43)
    Add     1.00 [  0.00]( 1.75)     1.00 [ -0.47]( 2.17)     1.00 [ -0.14]( 1.31)       0.99 [ -0.81]( 2.26)
  Triad     1.00 [  0.00]( 1.95)     0.97 [ -2.82]( 4.63)     0.95 [ -4.65]( 6.59)       0.97 [ -2.80]( 4.84)


  ==================================================================
  Test          : netperf
  Units         : Normalized Througput
  Interpretation: Higher is better
  Statistic     : AMean
  ==================================================================
  Clients:         tip[pct imp](CV)       push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
   1-clients     1.00 [  0.00]( 0.25)     0.98 [ -1.51]( 0.56)      0.99 [ -1.37]( 0.32)       0.98 [ -1.91]( 0.38)
   2-clients     1.00 [  0.00]( 0.39)     0.99 [ -1.26]( 1.05)      0.99 [ -0.99]( 0.75)       0.98 [ -2.16]( 0.57)
   4-clients     1.00 [  0.00]( 0.67)     0.99 [ -0.73]( 0.68)      1.00 [ -0.22]( 0.46)       0.98 [ -1.70]( 0.30)
   8-clients     1.00 [  0.00]( 0.46)     0.99 [ -1.09]( 0.50)      1.00 [ -0.27]( 0.44)       0.98 [ -1.84]( 0.59)
  16-clients     1.00 [  0.00]( 0.76)     0.99 [ -0.79]( 0.48)      1.00 [ -0.24]( 1.35)       0.99 [ -1.31]( 0.74)
  32-clients     1.00 [  0.00]( 0.82)     0.99 [ -0.91]( 0.80)      1.00 [ -0.04]( 1.16)       0.99 [ -1.27]( 0.83)
  64-clients     1.00 [  0.00]( 1.63)     0.99 [ -0.97]( 1.37)      1.00 [  0.13]( 1.47)       0.99 [ -1.17]( 1.60)
  128-clients    1.00 [  0.00]( 1.30)     0.99 [ -1.07]( 1.42)      0.99 [ -0.92]( 1.41)       0.98 [ -1.77]( 1.19)
  256-clients    1.00 [  0.00]( 5.43)     1.02 [  1.53]( 6.74)      1.02 [  1.54]( 3.40)       1.00 [  0.25]( 6.01)
  512-clients    1.00 [  0.00](55.62)     1.00 [ -0.25](54.85)      0.98 [ -1.91](52.43)       0.98 [ -1.88](51.45)


  ==================================================================
  Test          : schbench
  Units         : Normalized 99th percentile latency in us
  Interpretation: Lower is better
  Statistic     : Median
  ==================================================================
  #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)    push+newidle[pct imp](CV)
    1     1.00 [ -0.00]( 2.50)     1.00 [ -0.00](35.19)     0.88 [ 12.50](31.97)         0.95 [  5.00](33.07)
    2     1.00 [ -0.00]( 8.58)     1.02 [ -2.44]( 6.45)     1.02 [ -2.44]( 9.52)         1.00 [ -0.00]( 2.44)
    4     1.00 [ -0.00]( 7.36)     1.02 [ -2.22]( 3.30)     0.98 [  2.22]( 8.29)         1.02 [ -2.22](13.95)
    8     1.00 [ -0.00]( 8.73)     1.10 [ -9.62]( 9.02)     1.06 [ -5.77]( 6.68)         1.04 [ -3.85]( 6.46)
   16     1.00 [ -0.00]( 4.34)     1.05 [ -4.84]( 4.01)     1.03 [ -3.23]( 1.82)         1.06 [ -6.45]( 4.07)
   32     1.00 [ -0.00]( 3.27)     1.06 [ -6.19]( 4.01)     0.99 [  1.03]( 2.08)         1.00 [ -0.00]( 2.06)
   64     1.00 [ -0.00]( 2.05)     1.01 [ -1.02]( 1.27)     1.01 [ -1.02]( 5.11)         0.91 [  9.18]( 6.51)
  128     1.00 [ -0.00]( 6.08)     0.95 [  5.49]( 4.91)     1.09 [ -8.59]( 8.22)         1.08 [ -7.88](11.81)
  256     1.00 [ -0.00]( 3.28)     0.94 [  6.24]( 4.22)     1.04 [ -3.72]( 6.18)         1.04 [ -4.10]( 3.62)
  512     1.00 [ -0.00]( 2.23)     0.98 [  2.29]( 1.92)     0.98 [  1.90]( 6.93)         1.02 [ -1.90]( 1.51)


  ==================================================================
  Test          : new-schbench-requests-per-second
  Units         : Normalized Requests per second
  Interpretation: Higher is better
  Statistic     : Median
  ==================================================================
  #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
    1     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.29)     1.00 [  0.00]( 0.14)       0.99 [ -0.56]( 0.91)
    2     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.14)       1.00 [  0.00]( 0.00)
    4     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.14)     1.00 [  0.28]( 0.14)       1.00 [  0.28]( 0.14)
    8     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)       1.00 [  0.00]( 0.00)
   16     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)       1.00 [  0.00]( 0.00)
   32     1.00 [  0.00]( 4.75)     1.01 [  1.13]( 0.29)     1.00 [  0.00]( 3.77)       0.99 [ -0.57]( 0.51)
   64     1.00 [  0.00]( 1.17)     1.01 [  0.69](13.90)     1.00 [  0.00](13.33)       1.01 [  0.69](13.35)
  128     1.00 [  0.00]( 0.00)     1.00 [  0.34]( 0.18)     1.01 [  0.68]( 0.00)       1.00 [  0.34]( 0.18)
  256     1.00 [  0.00]( 0.56)     1.00 [ -0.49]( 1.24)     1.00 [  0.25]( 1.47)       1.01 [  0.99]( 1.20)
  512     1.00 [  0.00]( 0.96)     1.00 [ -0.37]( 0.88)     1.00 [ -0.37]( 1.58)       1.00 [ -0.37]( 0.88)


  ==================================================================
  Test          : new-schbench-wakeup-latency
  Units         : Normalized 99th percentile latency in us
  Interpretation: Lower is better
  Statistic     : Median
  ==================================================================
  #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
    1     1.00 [ -0.00](24.81)     0.75 [ 25.00](24.12)     0.67 [ 33.33]( 6.74)        0.67 [ 33.33](11.18)
    2     1.00 [ -0.00]( 4.08)     0.77 [ 23.08]( 9.68)     0.92 [  7.69](21.56)        0.77 [ 23.08]( 8.94)
    4     1.00 [ -0.00]( 0.00)     1.08 [ -7.69](10.00)     0.85 [ 15.38]( 9.99)        0.85 [ 15.38]( 8.13)
    8     1.00 [ -0.00](12.91)     1.09 [ -9.09]( 4.43)     0.82 [ 18.18](19.99)        0.82 [ 18.18](23.66)
   16     1.00 [ -0.00](12.06)     1.18 [-18.18]( 8.37)     1.18 [-18.18](15.10)        1.18 [-18.18](15.10)
   32     1.00 [ -0.00](22.13)     1.00 [ -0.00]( 5.00)     1.10 [-10.00](19.86)        1.00 [ -0.00]( 5.34)
   64     1.00 [ -0.00](11.07)     1.00 [ -0.00](16.90)     0.92 [  7.69](15.49)        1.00 [ -0.00](13.62)
  128     1.00 [ -0.00]( 9.04)     0.98 [  2.48]( 3.01)     0.99 [  1.49]( 6.96)        0.98 [  1.98]( 5.42)
  256     1.00 [ -0.00]( 0.24)     1.00 [ -0.00]( 0.00)     1.00 [ -0.24]( 0.12)        1.00 [ -0.24]( 0.32)
  512     1.00 [ -0.00]( 0.34)     1.00 [ -0.00]( 0.40)     1.00 [  0.38]( 0.34)        0.99 [  1.15]( 0.20)


  ==================================================================
  Test          : new-schbench-request-latency
  Units         : Normalized 99th percentile latency in us
  Interpretation: Lower is better
  Statistic     : Median
  ==================================================================
  #workers: tip[pct imp](CV)      push_only[pct imp](CV)   newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
    1     1.00 [ -0.00]( 0.90)     0.99 [  0.84]( 1.82)     0.99 [  0.56]( 1.10)        1.03 [ -2.53]( 1.88)
    2     1.00 [ -0.00]( 0.00)     1.01 [ -0.57]( 0.29)     1.01 [ -0.86]( 0.81)        1.02 [ -2.28]( 1.04)
    4     1.00 [ -0.00]( 1.02)     0.98 [  1.69]( 0.15)     0.99 [  0.84]( 1.02)        1.01 [ -0.84]( 1.67)
    8     1.00 [ -0.00]( 0.15)     1.01 [ -0.57]( 0.51)     1.00 [ -0.00]( 0.26)        1.00 [ -0.00]( 0.39)
   16     1.00 [ -0.00]( 0.53)     1.01 [ -0.57]( 0.64)     1.00 [ -0.29]( 0.39)        1.01 [ -0.86]( 0.81)
   32     1.00 [ -0.00](35.40)     0.98 [  1.62]( 0.49)     0.99 [  0.81](10.03)        1.00 [ -0.00]( 0.48)
   64     1.00 [ -0.00]( 5.24)     0.92 [  7.82](26.28)     1.03 [ -2.52]( 6.65)        0.62 [ 38.02](32.78)
  128     1.00 [ -0.00]( 2.02)     0.99 [  0.75]( 1.40)     1.16 [-16.14]( 2.15)        1.17 [-16.89]( 3.16)
  256     1.00 [ -0.00]( 3.41)     0.96 [  4.08]( 3.32)     1.07 [ -7.13]( 2.60)        1.10 [ -9.94]( 4.96)
  512     1.00 [ -0.00]( 1.45)     1.00 [  0.43]( 2.77)     0.99 [  1.06]( 0.73)        0.98 [  1.92]( 0.40)


  ==================================================================
  Test          : Various longer running benchmarks
  Units         : %diff in throughput reported
  Interpretation: Higher is better
  Statistic     : Median
  ==================================================================
  Benchmarks:                push_only    newidle_only  push+newidle
  ycsb-cassandra              -3%             -3%          -1%
  ycsb-mongodb                -2%             -2%          -1%
  deathstarbench-1x           24%             16%
  deathstarbench-2x           12%             14%
  deathstarbench-3x           17%             14%
  deathstarbench-6x


LPC 2025
========

Further experiments carried out will be discussed at LPC'25 in the
"Scheduler and Real-Time MC" between 11:08AM and 11:30AM on 11th
December, 2025 in Hall B4.

Discussion points include:

o "sd->shared" assignment optimization.
o "nohz.idle_cpus" mask optimization
o Busy balance CPU rotation.
o Effective detection of when it is favorable to push tasks.
o The overheads of maintaining masks (even with optimizations).
o The delicate dance of newidle balance.

Please do drop by, or reach out to me directly if this work interests
you.


Changelog
=========

This series is based on tip:sched/core at commit 3eb593560146 ("Merge
tag 'v6.18-rc7' into sched/core, to pick up fixes"). All the comparisons
above are done with the same.

o rfc v1.. rfc v2

- Collected tags on Patch 1 from Srikanth (Thanks a ton for the review)

- Added a for_each_cpu_and_wrap() and cleaned up couple of sites using
  the newly introduced macro.

- Simplified conditions that referenced per-CPU "llc_size" and
  "sd->shared" using the fact that only sd_llc has sd->shared assigned.

- Merged the two series however, the idea is largely the same. Push
  based load balancing is guarded behing CONFIG_NO_HZ_COMMON since a
  bunch of NO_HZ_COMMON specific bits were put behind the config option.

- Idea of overloaded_mask was dropped since the overhead to maintain
  the mask (without any usage) was visible in many benchmark results.

- Idea of shallow_idle_cpus mask was dropped since the overhead to
  maintain the mask (without any usage) was visible in benchmarks like
  tbench that left the CPUs idle for very short duration.

- Added the patch to rotate the "busy_balance_cpu".

- Renamed "idle_cpus_mask" to "nohz_idle_cpus_mask" in anticipation of
  adding the "shallow_idle_cpus" mask which didn't pan out.


Note: Patched marked EXPERIMENTAL may be incomplete from a schedstats
accounting standpoint.

---
K Prateek Nayak (28):
  sched/fair: Simplify set_cpu_sd_state_*() with guards
  sched/fair: Use rq->nohz_tick_stopped in update_nohz_stats()
  sched/topology: Optimize sd->shared allocation and assignment
  sched/fair: Simplify the entry condition for update_idle_cpu_scan()
  sched/fair: Simplity SIS_UTIL handling in select_idle_cpu()
  cpumask: Introduce for_each_cpu_and_wrap() and bitfield helpers
  sched/fair: Use for_each_cpu_and_wrap() in select_idle_capacity()
  sched/fair: Use for_each_cpu_and_wrap() in select_idle_cpu()
  sched/fair: Rotate the CPU resposible for busy load balancing
  sched/fair: Use xchg() to set sd->nohz_idle state
  sched/topology: Attach new hierarchy in rq_attach_root()
  sched/fair: Fixup sd->nohz_idle state during hotplug / cpuset
  sched/fair: Account idle cpus instead of busy cpus in sd->shared
  sched/topology: Introduce fallback sd->shared assignment
  sched/topology: Introduce percpu sd_nohz for nohz state tracking
  sched/topology: Introduce "nohz_idle_cpus_mask" in sd->shared
  sched/topology: Introduce "nohz_shared_list" to keep track of
    sd->shared
  sched/fair: Reorder the barrier in nohz_balance_enter_idle()
  sched/fair: Extract the main _nohz_idle_balance() loop into a helper
  sched/fair: Convert find_new_ilb() to use nohz_shared_list
  sched/fair: Introduce sched_asym_prefer_idle() for ILB kick
  sched/fair: Convert sched_balance_nohz_idle() to use nohz_shared_list
  sched/fair: Remove "nohz.idle_cpus_mask"
  sched/fair: Optimize global "nohz.nr_cpus" tracking
  sched/topology: Add basic debug information for "nohz_shared_list"
  [EXPERIMENTAL] sched/fair: Proactive idle balance using push mechanism
  [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push
  [EXPERIMENTAL] sched/fair: Faster alternate for intra-NUMA newidle
    balance

Vincent Guittot (1):
  [EXPERIMENTAL] sched/fair: Add push task framework

 include/linux/cpumask.h        |  20 +
 include/linux/find.h           |  37 ++
 include/linux/sched/topology.h |  18 +-
 kernel/sched/core.c            |   4 +-
 kernel/sched/fair.c            | 828 ++++++++++++++++++++++++++-------
 kernel/sched/sched.h           |  10 +-
 kernel/sched/topology.c        | 386 +++++++++++++--
 7 files changed, 1076 insertions(+), 227 deletions(-)


base-commit: 3eb59356014674fa1b506a122cc59b57089a4d08
-- 
2.43.0

[RESEND RFC PATCH v2 01/29] sched/fair: Simplify set_cpu_sd_state_*() with guards

[K Prateek Nayak]

Simplify set_cpu_sd_state_{busy,idle}() using guard(rcu).

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Reviewed-by: Shrikanth Hegde <sshegde@linux.ibm.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 20 ++++++++------------
 1 file changed, 8 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 769d7b7990df..8a5168284eaf 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12543,16 +12543,14 @@ static void set_cpu_sd_state_busy(int cpu)
 {
 	struct sched_domain *sd;
 
-	rcu_read_lock();
-	sd = rcu_dereference(per_cpu(sd_llc, cpu));
+	guard(rcu)();
 
+	sd = rcu_dereference(per_cpu(sd_llc, cpu));
 	if (!sd || !sd->nohz_idle)
-		goto unlock;
-	sd->nohz_idle = 0;
+		return;
 
+	sd->nohz_idle = 0;
 	atomic_inc(&sd->shared->nr_busy_cpus);
-unlock:
-	rcu_read_unlock();
 }
 
 void nohz_balance_exit_idle(struct rq *rq)
@@ -12573,16 +12571,14 @@ static void set_cpu_sd_state_idle(int cpu)
 {
 	struct sched_domain *sd;
 
-	rcu_read_lock();
-	sd = rcu_dereference(per_cpu(sd_llc, cpu));
+	guard(rcu)();
 
+	sd = rcu_dereference(per_cpu(sd_llc, cpu));
 	if (!sd || sd->nohz_idle)
-		goto unlock;
-	sd->nohz_idle = 1;
+		return;
 
+	sd->nohz_idle = 1;
 	atomic_dec(&sd->shared->nr_busy_cpus);
-unlock:
-	rcu_read_unlock();
 }
 
 /*
-- 
2.43.0

[RESEND RFC PATCH v2 02/29] sched/fair: Use rq->nohz_tick_stopped in update_nohz_stats()

[K Prateek Nayak]

"rq->nohz_tick_stopped" always follows the state of CPU on
"nohz.idle_cpus_mask". Use the local rq indicator instead of checking
for the CPU on the "idle_cpus_mask".

Use READ_ONCE() and WRITE_ONCE() for "rq->nohz_tick_stopped" to ensure
update_nohz_stats() always sees the latest value.

This cleanup is necessary to avoid the number of references to the
global "nohz.idle_cpus_mask" to ease the transition to a distributed
nohz idle tracking strategy.

No functional changes intended.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 8a5168284eaf..b135c9ce21fe 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12557,10 +12557,10 @@ void nohz_balance_exit_idle(struct rq *rq)
 {
 	WARN_ON_ONCE(rq != this_rq());
 
-	if (likely(!rq->nohz_tick_stopped))
+	if (likely(!READ_ONCE(rq->nohz_tick_stopped)))
 		return;
 
-	rq->nohz_tick_stopped = 0;
+	WRITE_ONCE(rq->nohz_tick_stopped, 0);
 	cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
 	atomic_dec(&nohz.nr_cpus);
 
@@ -12608,14 +12608,14 @@ void nohz_balance_enter_idle(int cpu)
 	 * *_avg. The CPU is already part of nohz.idle_cpus_mask so the clear
 	 * of nohz.has_blocked can only happen after checking the new load
 	 */
-	if (rq->nohz_tick_stopped)
+	if (READ_ONCE(rq->nohz_tick_stopped))
 		goto out;
 
 	/* If we're a completely isolated CPU, we don't play: */
 	if (on_null_domain(rq))
 		return;
 
-	rq->nohz_tick_stopped = 1;
+	WRITE_ONCE(rq->nohz_tick_stopped, 1);
 
 	cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 	atomic_inc(&nohz.nr_cpus);
@@ -12645,7 +12645,7 @@ static bool update_nohz_stats(struct rq *rq)
 	if (!rq->has_blocked_load)
 		return false;
 
-	if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
+	if (!READ_ONCE(rq->nohz_tick_stopped))
 		return false;
 
 	if (!time_after(jiffies, READ_ONCE(rq->last_blocked_load_update_tick)))
-- 
2.43.0

[RESEND RFC PATCH v2 03/29] sched/topology: Optimize sd->shared allocation and assignment

[K Prateek Nayak]

sd->shared is ever only used for sd_llc_shared and the sd->shared of
lower domains are never referenced by the scheduler. Subsequent
optimization will bloat the size of sd->shared and allocation of
redundant "sd->shared" can be expensive.

sd_llc is always a !SD_OVERLAP domain and it's children are always a
subset of the domain, thus the degeneration of a SD_SHARE_LLC  domain
implies that it either contains a single CPU, or its span matches with
that of a its child domain.

Initialize a single level of per-CPU sched_domain_shared objects instead
of doing it for each topology level. Assign sd->shared to the highest
SD_SHARE_LLC domain and rely on the degeneration path to pass it to the
correct topology level.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/sched/topology.h |   1 -
 kernel/sched/topology.c        | 101 +++++++++++++++++++++++----------
 2 files changed, 71 insertions(+), 31 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 45c0022b91ce..fc3d89160513 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -171,7 +171,6 @@ typedef int (*sched_domain_flags_f)(void);
 
 struct sd_data {
 	struct sched_domain *__percpu *sd;
-	struct sched_domain_shared *__percpu *sds;
 	struct sched_group *__percpu *sg;
 	struct sched_group_capacity *__percpu *sgc;
 };
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index cf643a5ddedd..14be90af9761 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -679,6 +679,9 @@ static void update_top_cache_domain(int cpu)
 	if (sd) {
 		id = cpumask_first(sched_domain_span(sd));
 		size = cpumask_weight(sched_domain_span(sd));
+
+		/* If sd_llc exists, sd_llc_shared should exist too. */
+		WARN_ON_ONCE(!sd->shared);
 		sds = sd->shared;
 	}
 
@@ -727,6 +730,13 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
 		if (sd_parent_degenerate(tmp, parent)) {
 			tmp->parent = parent->parent;
 
+			/* Pick reference to parent->shared. */
+			if (parent->shared) {
+				WARN_ON_ONCE(tmp->shared);
+				tmp->shared = parent->shared;
+				parent->shared = NULL;
+			}
+
 			if (parent->parent) {
 				parent->parent->child = tmp;
 				parent->parent->groups->flags = tmp->flags;
@@ -776,6 +786,7 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
 }
 
 struct s_data {
+	struct sched_domain_shared * __percpu *sds;
 	struct sched_domain * __percpu *sd;
 	struct root_domain	*rd;
 };
@@ -783,6 +794,7 @@ struct s_data {
 enum s_alloc {
 	sa_rootdomain,
 	sa_sd,
+	sa_sd_shared,
 	sa_sd_storage,
 	sa_none,
 };
@@ -1529,6 +1541,9 @@ static void set_domain_attribute(struct sched_domain *sd,
 static void __sdt_free(const struct cpumask *cpu_map);
 static int __sdt_alloc(const struct cpumask *cpu_map);
 
+static void __sds_free(struct s_data *d, const struct cpumask *cpu_map);
+static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map);
+
 static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
 				 const struct cpumask *cpu_map)
 {
@@ -1540,6 +1555,9 @@ static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
 	case sa_sd:
 		free_percpu(d->sd);
 		fallthrough;
+	case sa_sd_shared:
+		__sds_free(d, cpu_map);
+		fallthrough;
 	case sa_sd_storage:
 		__sdt_free(cpu_map);
 		fallthrough;
@@ -1555,9 +1573,11 @@ __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map)
 
 	if (__sdt_alloc(cpu_map))
 		return sa_sd_storage;
+	if (__sds_alloc(d, cpu_map))
+		return sa_sd_shared;
 	d->sd = alloc_percpu(struct sched_domain *);
 	if (!d->sd)
-		return sa_sd_storage;
+		return sa_sd_shared;
 	d->rd = alloc_rootdomain();
 	if (!d->rd)
 		return sa_sd;
@@ -1577,9 +1597,6 @@ static void claim_allocations(int cpu, struct sched_domain *sd)
 	WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
 	*per_cpu_ptr(sdd->sd, cpu) = NULL;
 
-	if (atomic_read(&(*per_cpu_ptr(sdd->sds, cpu))->ref))
-		*per_cpu_ptr(sdd->sds, cpu) = NULL;
-
 	if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
 		*per_cpu_ptr(sdd->sg, cpu) = NULL;
 
@@ -1722,16 +1739,6 @@ sd_init(struct sched_domain_topology_level *tl,
 		sd->cache_nice_tries = 1;
 	}
 
-	/*
-	 * For all levels sharing cache; connect a sched_domain_shared
-	 * instance.
-	 */
-	if (sd->flags & SD_SHARE_LLC) {
-		sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
-		atomic_inc(&sd->shared->ref);
-		atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
-	}
-
 	sd->private = sdd;
 
 	return sd;
@@ -2367,10 +2374,6 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 		if (!sdd->sd)
 			return -ENOMEM;
 
-		sdd->sds = alloc_percpu(struct sched_domain_shared *);
-		if (!sdd->sds)
-			return -ENOMEM;
-
 		sdd->sg = alloc_percpu(struct sched_group *);
 		if (!sdd->sg)
 			return -ENOMEM;
@@ -2381,7 +2384,6 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
 		for_each_cpu(j, cpu_map) {
 			struct sched_domain *sd;
-			struct sched_domain_shared *sds;
 			struct sched_group *sg;
 			struct sched_group_capacity *sgc;
 
@@ -2392,13 +2394,6 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
 			*per_cpu_ptr(sdd->sd, j) = sd;
 
-			sds = kzalloc_node(sizeof(struct sched_domain_shared),
-					GFP_KERNEL, cpu_to_node(j));
-			if (!sds)
-				return -ENOMEM;
-
-			*per_cpu_ptr(sdd->sds, j) = sds;
-
 			sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
 					GFP_KERNEL, cpu_to_node(j));
 			if (!sg)
@@ -2440,8 +2435,6 @@ static void __sdt_free(const struct cpumask *cpu_map)
 				kfree(*per_cpu_ptr(sdd->sd, j));
 			}
 
-			if (sdd->sds)
-				kfree(*per_cpu_ptr(sdd->sds, j));
 			if (sdd->sg)
 				kfree(*per_cpu_ptr(sdd->sg, j));
 			if (sdd->sgc)
@@ -2449,8 +2442,6 @@ static void __sdt_free(const struct cpumask *cpu_map)
 		}
 		free_percpu(sdd->sd);
 		sdd->sd = NULL;
-		free_percpu(sdd->sds);
-		sdd->sds = NULL;
 		free_percpu(sdd->sg);
 		sdd->sg = NULL;
 		free_percpu(sdd->sgc);
@@ -2458,6 +2449,42 @@ static void __sdt_free(const struct cpumask *cpu_map)
 	}
 }
 
+static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
+{
+	int j;
+
+	d->sds = alloc_percpu(struct sched_domain_shared *);
+	if (!d->sds)
+		return -ENOMEM;
+
+	for_each_cpu(j, cpu_map) {
+		struct sched_domain_shared *sds;
+
+		sds = kzalloc_node(sizeof(struct sched_domain_shared),
+				GFP_KERNEL, cpu_to_node(j));
+		if (!sds)
+			return -ENOMEM;
+
+		*per_cpu_ptr(d->sds, j) = sds;
+	}
+
+	return 0;
+}
+
+static void __sds_free(struct s_data *d, const struct cpumask *cpu_map)
+{
+	int j;
+
+	if (!d->sds)
+		return;
+
+	for_each_cpu(j, cpu_map)
+		kfree(*per_cpu_ptr(d->sds, j));
+
+	free_percpu(d->sds);
+	d->sds = NULL;
+}
+
 static struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
 		const struct cpumask *cpu_map, struct sched_domain_attr *attr,
 		struct sched_domain *child, int cpu)
@@ -2609,8 +2636,19 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 		unsigned int imb_span = 1;
 
 		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *parent = sd->parent;
 			struct sched_domain *child = sd->child;
 
+			/* Attach sd->shared to the topmost SD_SHARE_LLC domain. */
+			if ((sd->flags & SD_SHARE_LLC) &&
+			    (!parent || !(parent->flags & SD_SHARE_LLC))) {
+				int llc_id = cpumask_first(sched_domain_span(sd));
+
+				sd->shared = *per_cpu_ptr(d.sds, llc_id);
+				atomic_set(&sd->shared->nr_busy_cpus, sd->span_weight);
+				atomic_inc(&sd->shared->ref);
+			}
+
 			if (!(sd->flags & SD_SHARE_LLC) && child &&
 			    (child->flags & SD_SHARE_LLC)) {
 				struct sched_domain __rcu *top_p;
@@ -2663,6 +2701,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 		if (!cpumask_test_cpu(i, cpu_map))
 			continue;
 
+		if (atomic_read(&(*per_cpu_ptr(d.sds, i))->ref))
+			*per_cpu_ptr(d.sds, i) = NULL;
+
 		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
 			claim_allocations(i, sd);
 			init_sched_groups_capacity(i, sd);
-- 
2.43.0

[RESEND RFC PATCH v2 04/29] sched/fair: Simplify the entry condition for update_idle_cpu_scan()

[K Prateek Nayak]

Only the topmost SD_SHARE_LLC domain has the "sd->shared" assigned.
Simply use "sd->shared" as an indicator for load balancing at the highest
SD_SHARE_LLC domain in update_idle_cpu_scan() instead of relying on
llc_size.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b135c9ce21fe..6e1c78142536 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11005,6 +11005,7 @@ static void update_idle_cpu_scan(struct lb_env *env,
 				 unsigned long sum_util)
 {
 	struct sched_domain_shared *sd_share;
+	struct sched_domain *sd = env->sd;
 	int llc_weight, pct;
 	u64 x, y, tmp;
 	/*
@@ -11018,11 +11019,7 @@ static void update_idle_cpu_scan(struct lb_env *env,
 	if (!sched_feat(SIS_UTIL) || env->idle == CPU_NEWLY_IDLE)
 		return;
 
-	llc_weight = per_cpu(sd_llc_size, env->dst_cpu);
-	if (env->sd->span_weight != llc_weight)
-		return;
-
-	sd_share = rcu_dereference(per_cpu(sd_llc_shared, env->dst_cpu));
+	sd_share = sd->shared;
 	if (!sd_share)
 		return;
 
@@ -11056,10 +11053,11 @@ static void update_idle_cpu_scan(struct lb_env *env,
 	 */
 	/* equation [3] */
 	x = sum_util;
+	llc_weight = sd->span_weight;
 	do_div(x, llc_weight);
 
 	/* equation [4] */
-	pct = env->sd->imbalance_pct;
+	pct = sd->imbalance_pct;
 	tmp = x * x * pct * pct;
 	do_div(tmp, 10000 * SCHED_CAPACITY_SCALE);
 	tmp = min_t(long, tmp, SCHED_CAPACITY_SCALE);
-- 
2.43.0

[RESEND RFC PATCH v2 05/29] sched/fair: Simplity SIS_UTIL handling in select_idle_cpu()

[K Prateek Nayak]

Use the "sd_llc" passed to select_idle_cpu() to obtain the
"sd_llc_shared" instead of dereferencing the per-CPU variable.
While at it move the cpumask_and() operation after the SIS_UTIL bailout
check to avoid unnecessarily computing the cpumask.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 19 ++++++++-----------
 1 file changed, 8 insertions(+), 11 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6e1c78142536..20198aa64882 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7636,21 +7636,18 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 {
 	struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
 	int i, cpu, idle_cpu = -1, nr = INT_MAX;
-	struct sched_domain_shared *sd_share;
-
-	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
 
 	if (sched_feat(SIS_UTIL)) {
-		sd_share = rcu_dereference(per_cpu(sd_llc_shared, target));
-		if (sd_share) {
-			/* because !--nr is the condition to stop scan */
-			nr = READ_ONCE(sd_share->nr_idle_scan) + 1;
-			/* overloaded LLC is unlikely to have idle cpu/core */
-			if (nr == 1)
-				return -1;
-		}
+		/* because !--nr is the condition to stop scan */
+		nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
+		/* overloaded LLC is unlikely to have idle cpu/core */
+		if (nr == 1)
+			return -1;
 	}
 
+	if (!cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr))
+		return -1;
+
 	if (static_branch_unlikely(&sched_cluster_active)) {
 		struct sched_group *sg = sd->groups;
 
-- 
2.43.0

[RESEND RFC PATCH v2 06/29] cpumask: Introduce for_each_cpu_and_wrap() and bitfield helpers

[K Prateek Nayak]

There is a developing pattern of using cpumask_and() followed by
for_each_cpu_wrap() in the scheduler.

To avoid a temporary variable and needlessly iterating over the cpumask
twice - once for the cpumask_and() operation and the second in the
for_each_cpu_wrap() loop - introduce a new for_each_cpu_and_wrap()
helper to iterate over the common bits set on two bitfields starting at
a specific position without needing an intermediate cpumask variable.

Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/cpumask.h | 20 ++++++++++++++++++++
 include/linux/find.h    | 37 +++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index ff8f41ab7ce6..b7a984c2a7d5 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -406,6 +406,26 @@ unsigned int cpumask_random(const struct cpumask *src)
 #define for_each_cpu_and(cpu, mask1, mask2)				\
 	for_each_and_bit(cpu, cpumask_bits(mask1), cpumask_bits(mask2), small_cpumask_bits)
 
+/**
+ * for_each_cpu_wrap - iterate over every cpu in both masks, starting at a
+ * specified location.
+ * @cpu: the (optionally unsigned) integer iterator
+ * @mask1: the first cpumask pointer
+ * @mask2: the second cpumask pointer
+ * @start: the start location
+ *
+ * This saves a temporary CPU mask in many places.  It is equivalent to:
+ *	struct cpumask tmp;
+ *	cpumask_and(&tmp, &mask1, &mask2);
+ *	for_each_cpu_wrap(cpu, &tmp, start)
+ *		...
+ *
+ * After the loop, cpu is >= nr_cpu_ids.
+ */
+#define for_each_cpu_and_wrap(cpu, mask1, mask2, start)				\
+	for_each_and_bit_wrap(cpu, cpumask_bits(mask1), cpumask_bits(mask2),	\
+			      small_cpumask_bits, start)
+
 /**
  * for_each_cpu_andnot - iterate over every cpu present in one mask, excluding
  *			 those present in another.
diff --git a/include/linux/find.h b/include/linux/find.h
index 9d720ad92bc1..fff9e2d55e4d 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -487,6 +487,29 @@ unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size,
 	return bit < start ? bit : size;
 }
 
+/* Helper for for_each_and_bit_wrap(). */
+static __always_inline
+unsigned long __for_each_and_wrap(const unsigned long *bitmap1, const unsigned long *bitmap2,
+				  unsigned long size, unsigned long start, unsigned long n)
+{
+	unsigned long bit;
+
+	/* If not wrapped around */
+	if (n > start) {
+		/* and have a bit, just return it. */
+		bit = find_next_and_bit(bitmap1, bitmap2, size, n);
+		if (bit < size)
+			return bit;
+
+		/* Otherwise, wrap around and ... */
+		n = 0;
+	}
+
+	/* Search the other part. */
+	bit = find_next_and_bit(bitmap1, bitmap2, start, n);
+	return bit < start ? bit : size;
+}
+
 /**
  * find_next_clump8 - find next 8-bit clump with set bits in a memory region
  * @clump: location to store copy of found clump
@@ -682,6 +705,20 @@ unsigned long find_next_bit_le(const void *addr, unsigned
 	     (bit) < (size);							\
 	     (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1))
 
+/**
+ * for_each_and_bit_wrap - iterate over all set bits in (*addr1 & *addr2)
+ * starting from @start, and wrapping around the end of bitmap.
+ * @bit: offset for current iteration
+ * @addr1: address of first bitmap
+ * @addr2: address of second bitmask to and with the first
+ * @size: bitmap size in number of bits
+ * @start: Starting bit for bitmap traversing, wrapping around the bitmap end
+ */
+#define for_each_and_bit_wrap(bit, addr1, addr2, size, start) \
+	for ((bit) = find_next_and_bit_wrap((addr1), (addr2), (size), (start));		\
+	     (bit) < (size);								\
+	     (bit) = __for_each_and_wrap((addr1), (addr2), (size), (start), (bit) + 1))
+
 /**
  * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
  * @start: bit offset to start search and to store the current iteration offset
-- 
2.43.0

[RESEND RFC PATCH v2 07/29] sched/fair: Use for_each_cpu_and_wrap() in select_idle_capacity()

[K Prateek Nayak]

select_idle_capacity() does not modify the temporary cpumask used to
find the common CPUs between the domain span and the task's affinity.
Use the for_each_cpu_and_wrap() helper to avoid the temporary cpumask.

No functional changes intended.

Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 20198aa64882..5abe0ccecef3 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7704,16 +7704,12 @@ select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target)
 	unsigned long task_util, util_min, util_max, best_cap = 0;
 	int fits, best_fits = 0;
 	int cpu, best_cpu = -1;
-	struct cpumask *cpus;
-
-	cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
-	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
 
 	task_util = task_util_est(p);
 	util_min = uclamp_eff_value(p, UCLAMP_MIN);
 	util_max = uclamp_eff_value(p, UCLAMP_MAX);
 
-	for_each_cpu_wrap(cpu, cpus, target) {
+	for_each_cpu_and_wrap(cpu, sched_domain_span(sd), p->cpus_ptr, target) {
 		unsigned long cpu_cap = capacity_of(cpu);
 
 		if (!available_idle_cpu(cpu) && !sched_idle_cpu(cpu))
-- 
2.43.0

[RESEND RFC PATCH v2 08/29] sched/fair: Use for_each_cpu_and_wrap() in select_idle_cpu()

[K Prateek Nayak]

Avoid the "cpumask_test() + continue" pattern for cluster cpumask
traversal in select_idle_cpu().

No functional changes intended.

Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5abe0ccecef3..8f5745495974 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7652,10 +7652,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 		struct sched_group *sg = sd->groups;
 
 		if (sg->flags & SD_CLUSTER) {
-			for_each_cpu_wrap(cpu, sched_group_span(sg), target + 1) {
-				if (!cpumask_test_cpu(cpu, cpus))
-					continue;
-
+			for_each_cpu_and_wrap(cpu, sched_group_span(sg), cpus, target + 1) {
 				if (has_idle_core) {
 					i = select_idle_core(p, cpu, cpus, &idle_cpu);
 					if ((unsigned int)i < nr_cpumask_bits)
-- 
2.43.0

[RESEND RFC PATCH v2 09/29] sched/fair: Rotate the CPU resposible for busy load balancing

[K Prateek Nayak]

The group_balance_cpu() currently always returns the fist CPU from the
group_balance_mask(). This puts the burden of busy balancing on the same
set of CPUs when the system is under heavy load.

Rotate the CPU responsilble for busy load balancing across all the CPUs
in group_balance_cpu(). The "busy_balance_cpu" in "sg->scg" shows the
CPU currently responsible for busy balancing in the group. Since
"sg->sgc" is shared by all the CPUs of group_balance_cpu(), all CPUs of
group will see the same "busy_balance_cpu".

The current "busy_balance_cpu" is responsible for updating the shared
variable with the next CPU on the mask once it is done attempting
balancing.

Although there is an unlikely chance of the current "busy_balance_cpu"
being unable to perform load balancing in a timely manner if it is
running with softirqs disabled, it is no worse than current scenario
where the first CPU of group_balance_mask() could also be unavailable
for a long time to perform load balancing.

Any hotplug / cpuset operation will rebuild the sched domain hierarchy
which will reset the "busy_balance_cpu" to the first CPU on the updated
group_balance_mask().

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c     | 24 +++++++++++++++++++++++-
 kernel/sched/sched.h    |  1 +
 kernel/sched/topology.c |  5 ++++-
 3 files changed, 28 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 8f5745495974..e3935903d9c5 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11747,7 +11747,7 @@ static int should_we_balance(struct lb_env *env)
 	if (idle_smt != -1)
 		return idle_smt == env->dst_cpu;
 
-	/* Are we the first CPU of this group ? */
+	/* Are we the busy load balancing CPU of this group ? */
 	return group_balance_cpu(sg) == env->dst_cpu;
 }
 
@@ -11773,6 +11773,22 @@ static void update_lb_imbalance_stat(struct lb_env *env, struct sched_domain *sd
 	}
 }
 
+static void update_busy_balance_cpu(int this_cpu, struct lb_env *env)
+{
+	struct sched_group *group = env->sd->groups;
+	int balance_cpu = group_balance_cpu(group);
+
+	/*
+	 * Only the current CPU responsible for busy load balancing
+	 * should update the "busy_balance_cpu" for next instance.
+	 */
+	if (this_cpu != balance_cpu)
+		return;
+
+	balance_cpu = cpumask_next_wrap(balance_cpu, group_balance_mask(group));
+	WRITE_ONCE(group->sgc->busy_balance_cpu, balance_cpu);
+}
+
 /*
  * This flag serializes load-balancing passes over large domains
  * (above the NODE topology level) - only one load-balancing instance
@@ -12075,6 +12091,12 @@ static int sched_balance_rq(int this_cpu, struct rq *this_rq,
 out:
 	if (need_unlock)
 		atomic_set_release(&sched_balance_running, 0);
+	/*
+	 * If this was a successful busy balancing attempt,
+	 * update the "busy_balance_cpu" of the group.
+	 */
+	if (!idle && continue_balancing)
+		update_busy_balance_cpu(this_cpu, &env);
 
 	return ld_moved;
 }
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b419a4d98461..659e712f348f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2100,6 +2100,7 @@ struct sched_group_capacity {
 	unsigned long		max_capacity;		/* Max per-CPU capacity in group */
 	unsigned long		next_update;
 	int			imbalance;		/* XXX unrelated to capacity but shared group state */
+	int			busy_balance_cpu;
 
 	int			id;
 
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 14be90af9761..8870b38d4072 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -810,7 +810,7 @@ enum s_alloc {
  */
 int group_balance_cpu(struct sched_group *sg)
 {
-	return cpumask_first(group_balance_mask(sg));
+	return READ_ONCE(sg->sgc->busy_balance_cpu);
 }
 
 
@@ -992,6 +992,8 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 	cpu = cpumask_first(mask);
 
 	sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
+	sg->sgc->busy_balance_cpu = cpu;
+
 	if (atomic_inc_return(&sg->sgc->ref) == 1)
 		cpumask_copy(group_balance_mask(sg), mask);
 	else
@@ -1211,6 +1213,7 @@ static struct sched_group *get_group(int cpu, struct sd_data *sdd)
 
 	sg = *per_cpu_ptr(sdd->sg, cpu);
 	sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
+	sg->sgc->busy_balance_cpu = cpu;
 
 	/* Increase refcounts for claim_allocations: */
 	already_visited = atomic_inc_return(&sg->ref) > 1;
-- 
2.43.0

[RESEND RFC PATCH v2 10/29] sched/fair: Use xchg() to set sd->nohz_idle state

[K Prateek Nayak]

"sd->nohz_idle" currently relies on the fact that it is always modified
from the local CPU to keep consistency however, the subsequent commits
will use the rq->online() callback to correct the "sd->nohz_idle" status
from a remote CPU during sched domain rebuild.

Use xchg() instead to prevent double accounting of "nr_busy_cpus" if the
status update on the local CPU races with a correction from a remote
CPU.

No functional changes intended.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e3935903d9c5..3128daf1d5d4 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12559,7 +12559,9 @@ static void set_cpu_sd_state_busy(int cpu)
 	if (!sd || !sd->nohz_idle)
 		return;
 
-	sd->nohz_idle = 0;
+	if (!xchg(&sd->nohz_idle, 0))
+		return;
+
 	atomic_inc(&sd->shared->nr_busy_cpus);
 }
 
@@ -12587,7 +12589,9 @@ static void set_cpu_sd_state_idle(int cpu)
 	if (!sd || sd->nohz_idle)
 		return;
 
-	sd->nohz_idle = 1;
+	if (xchg(&sd->nohz_idle, 1))
+		return;
+
 	atomic_dec(&sd->shared->nr_busy_cpus);
 }
 
-- 
2.43.0

[RESEND RFC PATCH v2 11/29] sched/topology: Attach new hierarchy in rq_attach_root()

[K Prateek Nayak]

Gregory Haskins introduced the concept of root domain in commit
57d885fea0da ("sched: add sched-domain roots") which put
rq_attach_root() before rcu_assign_pointer(rq->sd, sd).

Further development around dynamic sched domain allocation, and
update_top_cache_domain() that came later relied on the new sched
domain hierarchy and was naturaturally done after rq->sd was updated.

Since subsequent changes around nohz idle CPU tracking creates a
dependency for the fair_sched_class->offline() callback to use the old
hierarchy and the fair_sched_class->online() callback to use the
updated hierarchy, update rq->sd and the top cache domains within
rq_attach_root() between the two callbacks.

This modifies the flow as follows:

       old flow                              new flow
       ========                              ========

  rq_attach_root()                   rq_attach_root()
    set_rq_offline();                  set_rq_offline(); /* Operate on old sd_llc */
    set_rq_online();                   rq->sd = sd;
  rq->sd = sd;                         update_top_cache_domain()
  update_top_cache_domain()            set_rq_online(); /* Operate on new sd_llc */

No functional changes intended.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/core.c     |  2 +-
 kernel/sched/sched.h    |  2 +-
 kernel/sched/topology.c | 38 ++++++++++++++++++++++++--------------
 3 files changed, 26 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0c4ff93eeb78..35cb640b7266 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -8666,7 +8666,7 @@ void __init sched_init(void)
 
 		INIT_LIST_HEAD(&rq->cfs_tasks);
 
-		rq_attach_root(rq, &def_root_domain);
+		rq_attach_root(rq, &def_root_domain, NULL);
 #ifdef CONFIG_NO_HZ_COMMON
 		rq->last_blocked_load_update_tick = jiffies;
 		atomic_set(&rq->nohz_flags, 0);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 659e712f348f..7b0f9fbfc65b 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1044,7 +1044,7 @@ struct root_domain {
 
 extern void init_defrootdomain(void);
 extern int sched_init_domains(const struct cpumask *cpu_map);
-extern void rq_attach_root(struct rq *rq, struct root_domain *rd);
+extern void rq_attach_root(struct rq *rq, struct root_domain *rd, struct sched_domain *sd);
 extern void sched_get_rd(struct root_domain *rd);
 extern void sched_put_rd(struct root_domain *rd);
 
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 8870b38d4072..a212ae52cdac 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -469,9 +469,12 @@ static void free_rootdomain(struct rcu_head *rcu)
 	kfree(rd);
 }
 
-void rq_attach_root(struct rq *rq, struct root_domain *rd)
+static void update_top_cache_domain(int cpu);
+
+void rq_attach_root(struct rq *rq, struct root_domain *rd, struct sched_domain *sd)
 {
 	struct root_domain *old_rd = NULL;
+	int cpu = cpu_of(rq);
 	struct rq_flags rf;
 
 	rq_lock_irqsave(rq, &rf);
@@ -494,6 +497,8 @@ void rq_attach_root(struct rq *rq, struct root_domain *rd)
 	}
 
 	atomic_inc(&rd->refcount);
+	rcu_assign_pointer(rq->sd, sd);
+	update_top_cache_domain(cpu);
 	rq->rd = rd;
 
 	cpumask_set_cpu(rq->cpu, rd->span);
@@ -711,16 +716,27 @@ static void update_top_cache_domain(int cpu)
 	rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
 }
 
+struct s_data {
+	struct sched_domain_shared * __percpu *sds;
+	struct sched_domain * __percpu *sd;
+	struct root_domain	*rd;
+};
+
 /*
  * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
  * hold the hotplug lock.
  */
 static void
-cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
+cpu_attach_domain(struct s_data *d, int cpu)
 {
+	struct root_domain *rd = d->rd;
+	struct sched_domain *sd = NULL;
 	struct rq *rq = cpu_rq(cpu);
 	struct sched_domain *tmp;
 
+	if (d->sd)
+		sd = *per_cpu_ptr(d->sd, cpu);
+
 	/* Remove the sched domains which do not contribute to scheduling. */
 	for (tmp = sd; tmp; ) {
 		struct sched_domain *parent = tmp->parent;
@@ -776,21 +792,13 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
 
 	sched_domain_debug(sd, cpu);
 
-	rq_attach_root(rq, rd);
 	tmp = rq->sd;
-	rcu_assign_pointer(rq->sd, sd);
+	rq_attach_root(rq, rd, sd);
 	dirty_sched_domain_sysctl(cpu);
 	destroy_sched_domains(tmp);
 
-	update_top_cache_domain(cpu);
 }
 
-struct s_data {
-	struct sched_domain_shared * __percpu *sds;
-	struct sched_domain * __percpu *sd;
-	struct root_domain	*rd;
-};
-
 enum s_alloc {
 	sa_rootdomain,
 	sa_sd,
@@ -2717,9 +2725,8 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 	rcu_read_lock();
 	for_each_cpu(i, cpu_map) {
 		rq = cpu_rq(i);
-		sd = *per_cpu_ptr(d.sd, i);
 
-		cpu_attach_domain(sd, d.rd, i);
+		cpu_attach_domain(&d, i);
 
 		if (lowest_flag_domain(i, SD_CLUSTER))
 			has_cluster = true;
@@ -2824,6 +2831,9 @@ int __init sched_init_domains(const struct cpumask *cpu_map)
 static void detach_destroy_domains(const struct cpumask *cpu_map)
 {
 	unsigned int cpu = cpumask_any(cpu_map);
+	struct s_data d = {
+		.rd = &def_root_domain,
+	};
 	int i;
 
 	if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity, cpu)))
@@ -2834,7 +2844,7 @@ static void detach_destroy_domains(const struct cpumask *cpu_map)
 
 	rcu_read_lock();
 	for_each_cpu(i, cpu_map)
-		cpu_attach_domain(NULL, &def_root_domain, i);
+		cpu_attach_domain(&d, i);
 	rcu_read_unlock();
 }
 
-- 
2.43.0

[RESEND RFC PATCH v2 12/29] sched/fair: Fixup sd->nohz_idle state during hotplug / cpuset

[K Prateek Nayak]

When CPUs are transitioned offline, set_cpu_sd_state_busy() is called
to exclude the CPU from nohz idle balancing. Currently, it is done
independently via sched_cpu_deactivate() but subsequent transition of
the nohz idle tracking into the sched domain hierarchy would require
each CPU's status to be updated in the new hierarchy generated during
hotplug / cpuset.

Call set_cpu_sd_state_{idle,busy}() from the fair_sched_class' offline()
and online() callback respectively to ensure "sd->nohz_idle" of the
updated hierarchy reflects the same state as "rq->nohz_tick_stopped".

The changes from the prior commit to always update the rq->sd and the
top cache domains from rq_attach_root() ensures that the offline()
callback works on the older hierarchy and the online() callback works on
the updated hierarchy.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 3128daf1d5d4..de9e81eeb93d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12595,6 +12595,18 @@ static void set_cpu_sd_state_idle(int cpu)
 	atomic_dec(&sd->shared->nr_busy_cpus);
 }
 
+static void cpu_sd_exit_nohz_balance(struct rq *rq)
+{
+	if (READ_ONCE(rq->nohz_tick_stopped))
+		set_cpu_sd_state_busy(cpu_of(rq));
+}
+
+static void cpu_sd_reenter_nohz_balance(struct rq *rq)
+{
+	if (READ_ONCE(rq->nohz_tick_stopped))
+		set_cpu_sd_state_idle(cpu_of(rq));
+}
+
 /*
  * This routine will record that the CPU is going idle with tick stopped.
  * This info will be used in performing idle load balancing in the future.
@@ -12845,6 +12857,8 @@ static void nohz_newidle_balance(struct rq *this_rq)
 }
 
 #else /* !CONFIG_NO_HZ_COMMON: */
+static inline void cpu_sd_exit_nohz_balance(struct rq *rq) { }
+static inline void cpu_sd_reenter_nohz_balance(struct rq *rq) { }
 static inline void nohz_balancer_kick(struct rq *rq) { }
 
 static inline bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
@@ -13060,6 +13074,9 @@ static void rq_online_fair(struct rq *rq)
 	update_sysctl();
 
 	update_runtime_enabled(rq);
+
+	/* Fixup nr_busy_cpus and nohz stats. */
+	cpu_sd_reenter_nohz_balance(rq);
 }
 
 static void rq_offline_fair(struct rq *rq)
@@ -13071,6 +13088,9 @@ static void rq_offline_fair(struct rq *rq)
 
 	/* Ensure that we remove rq contribution to group share: */
 	clear_tg_offline_cfs_rqs(rq);
+
+	/* Fixup nr_busy_cpus and nohz stats. */
+	cpu_sd_exit_nohz_balance(rq);
 }
 
 #ifdef CONFIG_SCHED_CORE
-- 
2.43.0

[RESEND RFC PATCH v2 13/29] sched/fair: Account idle cpus instead of busy cpus in sd->shared

[K Prateek Nayak]

Switch to keeping track of "sd->shared->nr_idle_cpus" instead of
"nr_busy_cpus". Since previous commit corrected the "sd->nohz_idle"
state during sched domain rebuild, the nr_idle_cpus will reflect the
correct number of idle CPUs.

The idle CPUs accounting will be used for nohz idle balance in the
subsequent commits.

Races are possible during hotplug / cpuset where "nr_idle_cpus" might
be incorrectly accounted if the CPU enters exits out of nohz idle state
between the read of "rq->nohz_tick_stopped" and the subsequent update of
"sd->nohz_idle" in the hotplug path but these inaccuracies are transient
and will be corrected when the CPU enters idle or receives a tick.

  CPU0 (hotplug)                                    CPU1 (exits nohz idle)
  ==============                                    ======================
  online()
    if (rq->nohz_tick_stopped) /* True */
      ...                                          rq->nohz_tick_stopped = 0
      ...                                          set_cpu_sd_state_busy()
      ...
      set_cpu_sd_state_idle()

These situations are rare and should not have any long-term effect on
the nohz idle balancing since there isn't a case where a nohz idle CPU
is not set on the mask - either the hotplug thread sees that
"rq->nohz_tick_stopped" is set or the CPU going idle sees the updated
sched_domain hierarchy.

After the conversion, all the bits that use "nr_idle_cpus" are already
guarded behind CONFIG_NO_HZ_COMMON which makes it convenient to put the
declaration behind CONFIG_NO_HZ_COMMON as well.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/sched/topology.h |  4 +++-
 kernel/sched/fair.c            | 10 +++++-----
 kernel/sched/topology.c        |  1 -
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index fc3d89160513..15c61aed1b5c 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -65,7 +65,9 @@ struct sched_group;
 
 struct sched_domain_shared {
 	atomic_t	ref;
-	atomic_t	nr_busy_cpus;
+#ifdef CONFIG_NO_HZ_COMMON
+	atomic_t	nr_idle_cpus;
+#endif
 	int		has_idle_cores;
 	int		nr_idle_scan;
 };
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index de9e81eeb93d..fef3826a258f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12533,7 +12533,7 @@ static void nohz_balancer_kick(struct rq *rq)
 		 * the others are - so just get a NOHZ balance going if it looks
 		 * like this LLC domain has tasks we could move.
 		 */
-		nr_busy = atomic_read(&sds->nr_busy_cpus);
+		nr_busy = per_cpu(sd_llc_size, cpu) - atomic_read(&sds->nr_idle_cpus);
 		if (nr_busy > 1) {
 			flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
 			goto unlock;
@@ -12562,7 +12562,7 @@ static void set_cpu_sd_state_busy(int cpu)
 	if (!xchg(&sd->nohz_idle, 0))
 		return;
 
-	atomic_inc(&sd->shared->nr_busy_cpus);
+	atomic_dec(&sd->shared->nr_idle_cpus);
 }
 
 void nohz_balance_exit_idle(struct rq *rq)
@@ -12592,7 +12592,7 @@ static void set_cpu_sd_state_idle(int cpu)
 	if (xchg(&sd->nohz_idle, 1))
 		return;
 
-	atomic_dec(&sd->shared->nr_busy_cpus);
+	atomic_inc(&sd->shared->nr_idle_cpus);
 }
 
 static void cpu_sd_exit_nohz_balance(struct rq *rq)
@@ -13075,7 +13075,7 @@ static void rq_online_fair(struct rq *rq)
 
 	update_runtime_enabled(rq);
 
-	/* Fixup nr_busy_cpus and nohz stats. */
+	/* Fixup nr_idle_cpus and nohz stats. */
 	cpu_sd_reenter_nohz_balance(rq);
 }
 
@@ -13089,7 +13089,7 @@ static void rq_offline_fair(struct rq *rq)
 	/* Ensure that we remove rq contribution to group share: */
 	clear_tg_offline_cfs_rqs(rq);
 
-	/* Fixup nr_busy_cpus and nohz stats. */
+	/* Fixup nr_idle_cpus and nohz stats. */
 	cpu_sd_exit_nohz_balance(rq);
 }
 
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index a212ae52cdac..6b14c7db3e35 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -2656,7 +2656,6 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 				int llc_id = cpumask_first(sched_domain_span(sd));
 
 				sd->shared = *per_cpu_ptr(d.sds, llc_id);
-				atomic_set(&sd->shared->nr_busy_cpus, sd->span_weight);
 				atomic_inc(&sd->shared->ref);
 			}
 
-- 
2.43.0

[RESEND RFC PATCH v2 14/29] sched/topology: Introduce fallback sd->shared assignment

[K Prateek Nayak]

Going forward, tying the nohz balancing to "sd->shared" will require
each CPU's hierarchy to have at least one "sd->shared" object tracking
its idle status.

If the lowest domain of the hierarchy after degeneration does not have
the SD_SHARE_LLC flag set, assign a per-Node fallback shared object to
the lowest domain on CONFIG_NO_HZ_COMMON. !CONFIG_NO_HZ_COMMON kernels
will always have tick enabled on idle CPUs and will not require nohz
idle tracking.

An example scenario where the fallback shared object is used is as
follows - Consider a cpuset with 17CPUs where 16CPUs are from the same
LLC and a singleton CPU from another LLC:

  CPU0:
  domain0: MC {0-15}
    groups: {0} {1} ... {15}
    domain1: PKG {0-16}
      groups: {0-15} {16}
  ...
  CPU15:
  domain0: MC {0-15}
    groups: {15} {0} {1} ... {14}
    domain1: PKG {0-16}
      groups: {0-15} {16}
  CPU16:
  # MC is degenerated since {16} is the only CPU is the domain
  domain0: PKG {0-15}
    groups: {16} {0-15}
  # Assign sd[PKG]->shared = fallback_dhared[cpu_to_node(16)]

If the lowest domain is a SD_OVERLAP domain, "sd->shared" is only shared
by the CPUs on the same node and not the entire domain. This is
acceptable since the fallback shared object is only keeping track of the
CPU's idle status unlike sd_llc_shared which also tracks
"has_idle_cores" and "nr_idle_scan".

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/topology.c | 123 ++++++++++++++++++++++++++++++++++++++--
 1 file changed, 117 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 6b14c7db3e35..3a0740be9fcd 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -455,6 +455,96 @@ static bool build_perf_domains(const struct cpumask *cpu_map)
 static void free_pd(struct perf_domain *pd) { }
 #endif /* !(CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL) */
 
+struct s_data {
+#ifdef CONFIG_NO_HZ_COMMON
+	struct sched_domain_shared **fallback_nohz_sds;
+#endif
+	struct sched_domain_shared * __percpu *sds;
+	struct sched_domain * __percpu *sd;
+	struct root_domain	*rd;
+};
+
+#ifdef CONFIG_NO_HZ_COMMON
+
+static int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
+{
+	int j;
+
+	d->fallback_nohz_sds = kcalloc(nr_node_ids,
+			sizeof(*d->fallback_nohz_sds), GFP_KERNEL);
+	if (!d->fallback_nohz_sds)
+		return -ENOMEM;
+
+	/*
+	 * Allocate a fallback sd->shared object
+	 * for each node covered by the cpu_map.
+	 */
+	for_each_set_bit(j, visited_nodes, nr_node_ids) {
+		struct sched_domain_shared *sds;
+
+		sds = kzalloc_node(sizeof(struct sched_domain_shared),
+				GFP_KERNEL, j);
+		if (!sds)
+			return -ENOMEM;
+
+		d->fallback_nohz_sds[j] = sds;
+	}
+
+	return 0;
+}
+
+static void __fallback_sds_free(struct s_data *d)
+{
+	int j;
+
+	if (!d->fallback_nohz_sds)
+		return;
+
+	for (j = 0; j < nr_node_ids; ++j)
+		kfree(d->fallback_nohz_sds[j]);
+
+	kfree(d->fallback_nohz_sds);
+	d->fallback_nohz_sds = NULL;
+}
+
+static void assign_fallback_sds(struct s_data *d, struct sched_domain *sd, int cpu)
+{
+	struct sched_domain_shared *sds;
+
+	sds = d->fallback_nohz_sds[cpu_to_node(cpu)];
+	sd->shared = sds;
+	atomic_inc(&sd->shared->ref);
+}
+
+static void claim_fallback_sds(struct s_data *d)
+{
+	int j;
+
+	/*
+	 * Claim allocations for the fallback shared objects
+	 * if they were assigned during cpu_attach_domain().
+	 */
+	for (j = 0; j < nr_node_ids; ++j) {
+		struct sched_domain_shared *sds = d->fallback_nohz_sds[j];
+
+		if (sds && atomic_read(&sds->ref))
+			d->fallback_nohz_sds[j] = NULL;
+	}
+}
+
+#else /* !CONFIG_NO_HZ_COMMON */
+
+static inline int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
+{
+	return 0;
+}
+
+static inline void __fallback_sds_free(struct s_data *d) { }
+static inline void assign_fallback_sds(struct s_data *d, struct sched_domain *sd, int cpu) { }
+static inline void claim_fallback_sds(struct s_data *d) { }
+
+#endif /* CONFIG_NO_HZ_COMMON */
+
 static void free_rootdomain(struct rcu_head *rcu)
 {
 	struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
@@ -716,12 +806,6 @@ static void update_top_cache_domain(int cpu)
 	rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
 }
 
-struct s_data {
-	struct sched_domain_shared * __percpu *sds;
-	struct sched_domain * __percpu *sd;
-	struct root_domain	*rd;
-};
-
 /*
  * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
  * hold the hotplug lock.
@@ -790,6 +874,14 @@ cpu_attach_domain(struct s_data *d, int cpu)
 		}
 	}
 
+	/*
+	 * Ensure there is at least one domain in the
+	 * hierarchy with sd->shared attached to
+	 * ensure participation in nohz balancing.
+	 */
+	if (sd && !(sd->flags & SD_SHARE_LLC))
+		assign_fallback_sds(d, sd, cpu);
+
 	sched_domain_debug(sd, cpu);
 
 	tmp = rq->sd;
@@ -2462,12 +2554,19 @@ static void __sdt_free(const struct cpumask *cpu_map)
 
 static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
 {
+	unsigned long *visited_nodes;
 	int j;
 
+	visited_nodes = bitmap_alloc(nr_node_ids, GFP_KERNEL);
+	if (!visited_nodes)
+		return -ENOMEM;
+
 	d->sds = alloc_percpu(struct sched_domain_shared *);
 	if (!d->sds)
 		return -ENOMEM;
 
+	bitmap_zero(visited_nodes, nr_node_ids);
+
 	for_each_cpu(j, cpu_map) {
 		struct sched_domain_shared *sds;
 
@@ -2476,9 +2575,13 @@ static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
 		if (!sds)
 			return -ENOMEM;
 
+		bitmap_set(visited_nodes, cpu_to_node(j), 1);
 		*per_cpu_ptr(d->sds, j) = sds;
 	}
 
+	if (__fallback_sds_alloc(d, visited_nodes))
+		return -ENOMEM;
+
 	return 0;
 }
 
@@ -2492,6 +2595,8 @@ static void __sds_free(struct s_data *d, const struct cpumask *cpu_map)
 	for_each_cpu(j, cpu_map)
 		kfree(*per_cpu_ptr(d->sds, j));
 
+	__fallback_sds_free(d);
+
 	free_percpu(d->sds);
 	d->sds = NULL;
 }
@@ -2730,6 +2835,12 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 		if (lowest_flag_domain(i, SD_CLUSTER))
 			has_cluster = true;
 	}
+
+	/*
+	 * Claim allocations for the fallback shared objects
+	 * if they were assigned during cpu_attach_domain().
+	 */
+	claim_fallback_sds(&d);
 	rcu_read_unlock();
 
 	if (has_asym)
-- 
2.43.0

[RESEND RFC PATCH v2 15/29] sched/topology: Introduce percpu sd_nohz for nohz state tracking

[K Prateek Nayak]

Add a per-CPU "sd_nohz" variable to track domains in the local CPU's
hierarchy that have "sd->shared" set for nohz idle tracking.

Convert cpu_set_sd_state_*() to use "sd_nohz" instead of "sd_llc"
increasing the scope of tracking to all CPUs with non-NULL sd hierarchy
attached as opposed to just those CPUs with a "sd_llc" domain.

"sd_nohz" will be used in a subsequent commit to transition
nohz_balancer_kick() to use the distributed nohz idle tracking.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c     |  4 ++--
 kernel/sched/sched.h    |  2 ++
 kernel/sched/topology.c | 22 ++++++++++++++++++++++
 3 files changed, 26 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fef3826a258f..be7e818687c7 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12555,7 +12555,7 @@ static void set_cpu_sd_state_busy(int cpu)
 
 	guard(rcu)();
 
-	sd = rcu_dereference(per_cpu(sd_llc, cpu));
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
 	if (!sd || !sd->nohz_idle)
 		return;
 
@@ -12585,7 +12585,7 @@ static void set_cpu_sd_state_idle(int cpu)
 
 	guard(rcu)();
 
-	sd = rcu_dereference(per_cpu(sd_llc, cpu));
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
 	if (!sd || sd->nohz_idle)
 		return;
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 7b0f9fbfc65b..be52ebaf0143 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -3263,6 +3263,8 @@ extern void cfs_bandwidth_usage_dec(void);
 
 #define nohz_flags(cpu)		(&cpu_rq(cpu)->nohz_flags)
 
+DECLARE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
+
 extern void nohz_balance_exit_idle(struct rq *rq);
 #else /* !CONFIG_NO_HZ_COMMON: */
 static inline void nohz_balance_exit_idle(struct rq *rq) { }
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 3a0740be9fcd..5c399ca1f4a1 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -466,6 +466,8 @@ struct s_data {
 
 #ifdef CONFIG_NO_HZ_COMMON
 
+DEFINE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
+
 static int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
 {
 	int j;
@@ -532,6 +534,23 @@ static void claim_fallback_sds(struct s_data *d)
 	}
 }
 
+static void update_nohz_domain(int cpu)
+{
+	struct sched_domain *sd = highest_flag_domain(cpu, SD_SHARE_LLC);
+
+	/*
+	 * If sd_llc doesn't exist, use the lowest sd for nohz idle
+	 * tracking. cpu_attach_domain() already ensures sd->shared is
+	 * assigned for the lowest domain if sd_llc doesn't exist after
+	 * degeneration of the hierarchy.
+	 */
+	if (!sd)
+		sd = rcu_dereference(cpu_rq(cpu)->sd);
+
+	WARN_ON_ONCE(sd && !sd->shared);
+	rcu_assign_pointer(per_cpu(sd_nohz, cpu), sd);
+}
+
 #else /* !CONFIG_NO_HZ_COMMON */
 
 static inline int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
@@ -542,6 +561,7 @@ static inline int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_
 static inline void __fallback_sds_free(struct s_data *d) { }
 static inline void assign_fallback_sds(struct s_data *d, struct sched_domain *sd, int cpu) { }
 static inline void claim_fallback_sds(struct s_data *d) { }
+static inline void update_nohz_domain(int cpu) { }
 
 #endif /* CONFIG_NO_HZ_COMMON */
 
@@ -804,6 +824,8 @@ static void update_top_cache_domain(int cpu)
 
 	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY_FULL);
 	rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
+
+	update_nohz_domain(cpu);
 }
 
 /*
-- 
2.43.0

[RESEND RFC PATCH v2 16/29] sched/topology: Introduce "nohz_idle_cpus_mask" in sd->shared

[K Prateek Nayak]

Introduce "nohz_idle_cpus_mask" to track idle CPUs within the sd_nohz
domains. This mask will eventually replace the need for the global
"nohz.idle_cpus" mask for nohz idle balancing.

Convert cpu_set_sd_state_*() to set / clear the CPU from the mask when
transitioning to / out of nohz idle state.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            |  2 ++
 kernel/sched/topology.c        | 48 +++++++++++++++++++++++++++++++---
 3 files changed, 47 insertions(+), 4 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 15c61aed1b5c..280915ff7acf 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -67,6 +67,7 @@ struct sched_domain_shared {
 	atomic_t	ref;
 #ifdef CONFIG_NO_HZ_COMMON
 	atomic_t	nr_idle_cpus;
+	struct cpumask	*nohz_idle_cpus_mask;
 #endif
 	int		has_idle_cores;
 	int		nr_idle_scan;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index be7e818687c7..8f21b655fc40 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12562,6 +12562,7 @@ static void set_cpu_sd_state_busy(int cpu)
 	if (!xchg(&sd->nohz_idle, 0))
 		return;
 
+	cpumask_clear_cpu(cpu, sd->shared->nohz_idle_cpus_mask);
 	atomic_dec(&sd->shared->nr_idle_cpus);
 }
 
@@ -12592,6 +12593,7 @@ static void set_cpu_sd_state_idle(int cpu)
 	if (xchg(&sd->nohz_idle, 1))
 		return;
 
+	cpumask_set_cpu(cpu, sd->shared->nohz_idle_cpus_mask);
 	atomic_inc(&sd->shared->nr_idle_cpus);
 }
 
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 5c399ca1f4a1..59089ed3b840 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -468,6 +468,24 @@ struct s_data {
 
 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
 
+static int __sds_nohz_idle_alloc(struct sched_domain_shared *sds, int node)
+{
+	sds->nohz_idle_cpus_mask = kzalloc_node(cpumask_size(), GFP_KERNEL, node);
+
+	if (!sds->nohz_idle_cpus_mask)
+		return -ENOMEM;
+
+	return 0;
+}
+
+static void __sds_nohz_idle_free(struct sched_domain_shared *sds)
+{
+	if (!sds)
+		return;
+
+	kfree(sds->nohz_idle_cpus_mask);
+}
+
 static int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
 {
 	int j;
@@ -490,6 +508,9 @@ static int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
 			return -ENOMEM;
 
 		d->fallback_nohz_sds[j] = sds;
+
+		if (__sds_nohz_idle_alloc(sds, j))
+			return -ENOMEM;
 	}
 
 	return 0;
@@ -502,8 +523,10 @@ static void __fallback_sds_free(struct s_data *d)
 	if (!d->fallback_nohz_sds)
 		return;
 
-	for (j = 0; j < nr_node_ids; ++j)
+	for (j = 0; j < nr_node_ids; ++j) {
+		__sds_nohz_idle_free(d->fallback_nohz_sds[j]);
 		kfree(d->fallback_nohz_sds[j]);
+	}
 
 	kfree(d->fallback_nohz_sds);
 	d->fallback_nohz_sds = NULL;
@@ -553,6 +576,13 @@ static void update_nohz_domain(int cpu)
 
 #else /* !CONFIG_NO_HZ_COMMON */
 
+static int __sds_nohz_idle_alloc(struct sched_domain_shared *sds, int node)
+{
+	return 0;
+}
+
+static void __sds_nohz_idle_free(struct sched_domain_shared *sds) { }
+
 static inline int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
 {
 	return 0;
@@ -740,8 +770,10 @@ static void destroy_sched_domain(struct sched_domain *sd)
 	 */
 	free_sched_groups(sd->groups, 1);
 
-	if (sd->shared && atomic_dec_and_test(&sd->shared->ref))
+	if (sd->shared && atomic_dec_and_test(&sd->shared->ref)) {
+		__sds_nohz_idle_free(sd->shared);
 		kfree(sd->shared);
+	}
 	kfree(sd);
 }
 
@@ -2599,6 +2631,9 @@ static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
 
 		bitmap_set(visited_nodes, cpu_to_node(j), 1);
 		*per_cpu_ptr(d->sds, j) = sds;
+
+		if (__sds_nohz_idle_alloc(sds, cpu_to_node(j)))
+			return -ENOMEM;
 	}
 
 	if (__fallback_sds_alloc(d, visited_nodes))
@@ -2614,8 +2649,13 @@ static void __sds_free(struct s_data *d, const struct cpumask *cpu_map)
 	if (!d->sds)
 		return;
 
-	for_each_cpu(j, cpu_map)
-		kfree(*per_cpu_ptr(d->sds, j));
+	for_each_cpu(j, cpu_map) {
+		struct sched_domain_shared *sds;
+
+		sds = *per_cpu_ptr(d->sds, j);
+		__sds_nohz_idle_free(sds);
+		kfree(sds);
+	}
 
 	__fallback_sds_free(d);
 
-- 
2.43.0

[RESEND RFC PATCH v2 17/29] sched/topology: Introduce "nohz_shared_list" to keep track of sd->shared

[K Prateek Nayak]

Chain together all the "sd_nohz->shared" objects in a RCU protected
"nohz_shared_list" to get the full view of system for nohz idle
balancing. Since __sds_nohz_idle_alloc() is also responsible for
initializing the list_head, rename it to __sds_nohz_idle_alloc_init() to
fit the bill.

List modifications are protected by the "nohz_shared_list_lock" and
freeing of sd->shared on the list is delayed by one grace period to
ensure all the untracked references to the shared object under RCU are
dropped.

Users of "nohz_shared_list" will be added in subsequent patches where
all the current users of "nohz.idle_cpus" will be converted to use the
distributed tracking.

Reviewed-by: Gautham R. Shenoy <gautham.shenoy@amd.com>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/sched/topology.h | 12 ++++---
 kernel/sched/sched.h           |  1 +
 kernel/sched/topology.c        | 62 +++++++++++++++++++++++++++++++---
 3 files changed, 65 insertions(+), 10 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 280915ff7acf..074ee2980cdf 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -64,13 +64,15 @@ extern int sched_domain_level_max;
 struct sched_group;
 
 struct sched_domain_shared {
-	atomic_t	ref;
+	atomic_t		ref;
 #ifdef CONFIG_NO_HZ_COMMON
-	atomic_t	nr_idle_cpus;
-	struct cpumask	*nohz_idle_cpus_mask;
+	atomic_t		nr_idle_cpus;
+	struct cpumask		*nohz_idle_cpus_mask;
+	struct list_head	nohz_list_node;
+	struct rcu_head		rcu;
 #endif
-	int		has_idle_cores;
-	int		nr_idle_scan;
+	int			has_idle_cores;
+	int			nr_idle_scan;
 };
 
 struct sched_domain {
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index be52ebaf0143..159c24981ead 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -3264,6 +3264,7 @@ extern void cfs_bandwidth_usage_dec(void);
 #define nohz_flags(cpu)		(&cpu_rq(cpu)->nohz_flags)
 
 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
+extern struct list_head nohz_shared_list;
 
 extern void nohz_balance_exit_idle(struct rq *rq);
 #else /* !CONFIG_NO_HZ_COMMON: */
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 59089ed3b840..af4ce9451cd0 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -468,8 +468,12 @@ struct s_data {
 
 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
 
-static int __sds_nohz_idle_alloc(struct sched_domain_shared *sds, int node)
+static DEFINE_RAW_SPINLOCK(nohz_shared_list_lock);
+LIST_HEAD(nohz_shared_list);
+
+static int __sds_nohz_idle_alloc_init(struct sched_domain_shared *sds, int node)
 {
+	sds->nohz_list_node = (struct list_head)LIST_HEAD_INIT(sds->nohz_list_node);
 	sds->nohz_idle_cpus_mask = kzalloc_node(cpumask_size(), GFP_KERNEL, node);
 
 	if (!sds->nohz_idle_cpus_mask)
@@ -483,6 +487,7 @@ static void __sds_nohz_idle_free(struct sched_domain_shared *sds)
 	if (!sds)
 		return;
 
+	WARN_ON_ONCE(!list_empty(&sds->nohz_list_node));
 	kfree(sds->nohz_idle_cpus_mask);
 }
 
@@ -509,7 +514,7 @@ static int __fallback_sds_alloc(struct s_data *d, unsigned long *visited_nodes)
 
 		d->fallback_nohz_sds[j] = sds;
 
-		if (__sds_nohz_idle_alloc(sds, j))
+		if (__sds_nohz_idle_alloc_init(sds, j))
 			return -ENOMEM;
 	}
 
@@ -560,6 +565,7 @@ static void claim_fallback_sds(struct s_data *d)
 static void update_nohz_domain(int cpu)
 {
 	struct sched_domain *sd = highest_flag_domain(cpu, SD_SHARE_LLC);
+	struct sched_domain_shared *sds = NULL;
 
 	/*
 	 * If sd_llc doesn't exist, use the lowest sd for nohz idle
@@ -570,13 +576,52 @@ static void update_nohz_domain(int cpu)
 	if (!sd)
 		sd = rcu_dereference(cpu_rq(cpu)->sd);
 
-	WARN_ON_ONCE(sd && !sd->shared);
+	if (sd)
+		sds = sd->shared;
+
+	if (sds && list_empty(&sds->nohz_list_node)) {
+		/*
+		 * IRQs should be disabled by the caller since they
+		 * hold the rq_lock.
+		 */
+		lockdep_assert_irqs_disabled();
+
+		guard(raw_spinlock)(&nohz_shared_list_lock);
+		list_add(&sds->nohz_list_node, &nohz_shared_list);
+	}
+
+	WARN_ON_ONCE(sd && !sds);
 	rcu_assign_pointer(per_cpu(sd_nohz, cpu), sd);
 }
 
+static void destroy_sched_domain_shared_rcu(struct rcu_head *rcu)
+{
+	struct sched_domain_shared *sds = container_of(rcu, struct sched_domain_shared, rcu);
+
+	kfree(sds->nohz_idle_cpus_mask);
+	kfree(sds);
+}
+
+/*
+ * If sd->shared is on the rcu protected nohz_shared_list,
+ * remove it the list and wait once grace period before
+ * freeing.
+ */
+static int sds_delayed_free(struct sched_domain_shared *sds)
+{
+	if (list_empty(&sds->nohz_list_node))
+		return 0;
+
+	scoped_guard(raw_spinlock_irqsave, &nohz_shared_list_lock)
+		list_del_rcu(&sds->nohz_list_node);
+
+	call_rcu(&sds->rcu, destroy_sched_domain_shared_rcu);
+	return 1;
+}
+
 #else /* !CONFIG_NO_HZ_COMMON */
 
-static int __sds_nohz_idle_alloc(struct sched_domain_shared *sds, int node)
+static int __sds_nohz_idle_alloc_init(struct sched_domain_shared *sds, int node)
 {
 	return 0;
 }
@@ -592,6 +637,7 @@ static inline void __fallback_sds_free(struct s_data *d) { }
 static inline void assign_fallback_sds(struct s_data *d, struct sched_domain *sd, int cpu) { }
 static inline void claim_fallback_sds(struct s_data *d) { }
 static inline void update_nohz_domain(int cpu) { }
+static inline int sds_delayed_free(struct sched_domain_shared *sds) { return 0; }
 
 #endif /* CONFIG_NO_HZ_COMMON */
 
@@ -771,9 +817,15 @@ static void destroy_sched_domain(struct sched_domain *sd)
 	free_sched_groups(sd->groups, 1);
 
 	if (sd->shared && atomic_dec_and_test(&sd->shared->ref)) {
+		if (sds_delayed_free(sd->shared)) {
+			sd->shared = NULL;
+			goto out;
+		}
+
 		__sds_nohz_idle_free(sd->shared);
 		kfree(sd->shared);
 	}
+out:
 	kfree(sd);
 }
 
@@ -2632,7 +2684,7 @@ static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
 		bitmap_set(visited_nodes, cpu_to_node(j), 1);
 		*per_cpu_ptr(d->sds, j) = sds;
 
-		if (__sds_nohz_idle_alloc(sds, cpu_to_node(j)))
+		if (__sds_nohz_idle_alloc_init(sds, cpu_to_node(j)))
 			return -ENOMEM;
 	}
 
-- 
2.43.0

[RESEND RFC PATCH v2 18/29] sched/fair: Reorder the barrier in nohz_balance_enter_idle()

[K Prateek Nayak]

The smp_mb__after_atomic() in nohz_balance_enter_idle() is used to order
the setting of the nohz idle CPU on the "nohz.idle_cpus_mask" with the
write to "nohz.needs_update" as per the comment.

Since set_cpu_sd_state_idle() is now responsible for idle tracking using
"sd_nohz->shared", reorder the call to set_cpu_sd_state_idle() to come
before the barrier ensuring the CPU is tracked on the idle mask before
the update to "nohz.needs_update" is observed.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 8f21b655fc40..5e5db24e1384 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12648,6 +12648,8 @@ void nohz_balance_enter_idle(int cpu)
 	cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 	atomic_inc(&nohz.nr_cpus);
 
+	set_cpu_sd_state_idle(cpu);
+
 	/*
 	 * Ensures that if nohz_idle_balance() fails to observe our
 	 * @idle_cpus_mask store, it must observe the @has_blocked
@@ -12655,8 +12657,6 @@ void nohz_balance_enter_idle(int cpu)
 	 */
 	smp_mb__after_atomic();
 
-	set_cpu_sd_state_idle(cpu);
-
 	WRITE_ONCE(nohz.needs_update, 1);
 out:
 	/*
-- 
2.43.0

[RESEND RFC PATCH v2 19/29] sched/fair: Extract the main _nohz_idle_balance() loop into a helper

[K Prateek Nayak]

With the distributed nohz idle CPU tracking using the
"nohz_shared_list", the trick to do the load balancing for the CPU
in charge of the nohz idle balance at the very end using
for_each_cpu_warp() will no longer work.

Extract the main loop and the loop body doing the load balancing on
behalf of an idle target into two separate helpers -
sched_balance_nohz_idle() and sched_balance_idle_rq() respectively
keeping consistent with the naming convention in fair.c.

This will help transitioning _nohz_idle_balance() to use the
"nohz_shared_list" in the subsequent commit.

No functional changes intended.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 161 ++++++++++++++++++++++++++++----------------
 1 file changed, 102 insertions(+), 59 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5e5db24e1384..5bbd56161838 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12684,6 +12684,97 @@ static bool update_nohz_stats(struct rq *rq)
 	return rq->has_blocked_load;
 }
 
+/*
+ * sched_balance_idle_rq(): Balance a target idle rq.
+ * @rq: rq of the idle CPU that may require stats update or balancing.
+ * @flags: nohz flags of the balancing CPU.
+ * @next_balance: Pointer to variable storing the time in jiffies to
+ *		  trigger the next nohz idle balancing.
+ *
+ * Returns: Update flags for caller to take appropriate actions.
+ * NOHZ_STATS_KICK indicates rq still has blocked load after the update.
+ * NOHZ_NEXT_KICK indicates that *next_balance was updated to rq->next_balance.
+ */
+static unsigned int sched_balance_idle_rq(struct rq *rq,
+					  unsigned int flags,
+					  unsigned long *next_balance)
+{
+	unsigned int update_flags = 0;
+
+	/* If rq has blocked load, indicate via NOHZ_STATS_KICK. */
+	if ((flags & NOHZ_STATS_KICK) && update_nohz_stats(rq))
+		update_flags |= NOHZ_STATS_KICK;
+
+	/* If time for next balance is due, do the balance. */
+	if (time_after_eq(jiffies, rq->next_balance)) {
+		struct rq_flags rf;
+
+		rq_lock_irqsave(rq, &rf);
+		update_rq_clock(rq);
+		rq_unlock_irqrestore(rq, &rf);
+
+		if (flags & NOHZ_BALANCE_KICK)
+			sched_balance_domains(rq, CPU_IDLE);
+	}
+
+	/* Indicate update to next_balance via NOHZ_NEXT_KICK. */
+	if (time_after(*next_balance, rq->next_balance)) {
+		*next_balance = rq->next_balance;
+		update_flags |= NOHZ_NEXT_KICK;
+	}
+
+	return update_flags;
+}
+
+/*
+ * sched_balance_nohz_idle(): Core nohz idle balancing loop.
+ * @balancing_cpu: CPU doing the balancing on behalf of all nohz idle CPUs.
+ * @flags: nohz flags of the balancing CPU.
+ * @start: Time in jiffies when nohz indicators were cleared.
+ *
+ * Returns:
+ * < 0 - The balancing CPU turned busy while balancing.
+ *   0 - All CPUs were balanced; No blocked load if @flags had NOHZ_STATS_KICK.
+ * > 0 - One or more idle CPUs still have blocked load if @flags had
+ *	 NOHZ_STATS_KICK.
+ */
+static int sched_balance_nohz_idle(int balancing_cpu, unsigned int flags, unsigned long start)
+{
+	/* Earliest time when we have to do rebalance again */
+	unsigned long next_balance = start + 60*HZ;
+	unsigned int update_flags = 0;
+	int target_cpu;
+
+	/*
+	 * Start with the next CPU after the balancing CPU so we will end with
+	 * balancing CPU and let a chance for other idle cpu to pull load.
+	 */
+	for_each_cpu_wrap(target_cpu, nohz.idle_cpus_mask, balancing_cpu + 1) {
+		if (!idle_cpu(target_cpu))
+			continue;
+
+		/*
+		 * If balancing CPU gets work to do, stop the load balancing
+		 * work being done for other CPUs. Next load balancing owner
+		 * will pick it up.
+		 */
+		if (!idle_cpu(balancing_cpu) && need_resched())
+			return -EBUSY;
+
+		update_flags |= sched_balance_idle_rq(cpu_rq(target_cpu), flags, &next_balance);
+	}
+
+	/*
+	 * next_balance will be updated only when there is a need.
+	 * When the CPU is attached to null domain for ex, it will not be
+	 * updated.
+	 */
+	if (likely(update_flags & NOHZ_NEXT_KICK))
+		nohz.next_balance = next_balance;
+
+	return update_flags & NOHZ_STATS_KICK;
+}
+
 /*
  * Internal function that runs load balance for all idle CPUs. The load balance
  * can be a simple update of blocked load or a complete load balance with
@@ -12691,14 +12782,8 @@ static bool update_nohz_stats(struct rq *rq)
  */
 static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
 {
-	/* Earliest time when we have to do rebalance again */
 	unsigned long now = jiffies;
-	unsigned long next_balance = now + 60*HZ;
-	bool has_blocked_load = false;
-	int update_next_balance = 0;
-	int this_cpu = this_rq->cpu;
-	int balance_cpu;
-	struct rq *rq;
+	int ret;
 
 	WARN_ON_ONCE((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
@@ -12723,60 +12808,18 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
 	 */
 	smp_mb();
 
-	/*
-	 * Start with the next CPU after this_cpu so we will end with this_cpu and let a
-	 * chance for other idle cpu to pull load.
-	 */
-	for_each_cpu_wrap(balance_cpu,  nohz.idle_cpus_mask, this_cpu+1) {
-		if (!idle_cpu(balance_cpu))
-			continue;
-
-		/*
-		 * If this CPU gets work to do, stop the load balancing
-		 * work being done for other CPUs. Next load
-		 * balancing owner will pick it up.
-		 */
-		if (!idle_cpu(this_cpu) && need_resched()) {
-			if (flags & NOHZ_STATS_KICK)
-				has_blocked_load = true;
-			if (flags & NOHZ_NEXT_KICK)
-				WRITE_ONCE(nohz.needs_update, 1);
-			goto abort;
-		}
-
-		rq = cpu_rq(balance_cpu);
-
-		if (flags & NOHZ_STATS_KICK)
-			has_blocked_load |= update_nohz_stats(rq);
-
-		/*
-		 * If time for next balance is due,
-		 * do the balance.
-		 */
-		if (time_after_eq(jiffies, rq->next_balance)) {
-			struct rq_flags rf;
-
-			rq_lock_irqsave(rq, &rf);
-			update_rq_clock(rq);
-			rq_unlock_irqrestore(rq, &rf);
-
-			if (flags & NOHZ_BALANCE_KICK)
-				sched_balance_domains(rq, CPU_IDLE);
-		}
-
-		if (time_after(next_balance, rq->next_balance)) {
-			next_balance = rq->next_balance;
-			update_next_balance = 1;
-		}
-	}
+	ret = sched_balance_nohz_idle(cpu_of(this_rq), flags, now);
 
 	/*
-	 * next_balance will be updated only when there is a need.
-	 * When the CPU is attached to null domain for ex, it will not be
-	 * updated.
+	 * The balancing CPU turned busy. Set nohz.{needs_update,has_blocked}
+	 * indicators to ensure next CPU observing them triggers nohz idle
+	 * balance again.
 	 */
-	if (likely(update_next_balance))
-		nohz.next_balance = next_balance;
+	if (ret < 0) {
+		if (flags & NOHZ_NEXT_KICK)
+			WRITE_ONCE(nohz.needs_update, 1);
+		goto abort;
+	}
 
 	if (flags & NOHZ_STATS_KICK)
 		WRITE_ONCE(nohz.next_blocked,
@@ -12784,7 +12827,7 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
 
 abort:
 	/* There is still blocked load, enable periodic update */
-	if (has_blocked_load)
+	if (ret)
 		WRITE_ONCE(nohz.has_blocked, 1);
 }
 
-- 
2.43.0

[RESEND RFC PATCH v2 20/29] sched/fair: Convert find_new_ilb() to use nohz_shared_list

[K Prateek Nayak]

Use "nohz_shared_list" in find_new_ilb() instead of the global
"nohz.idle_cpus_mask".

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5bbd56161838..dbbb1f3251d2 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12367,18 +12367,27 @@ static inline int on_null_domain(struct rq *rq)
  */
 static inline int find_new_ilb(void)
 {
+	struct sched_domain_shared *sds;
 	const struct cpumask *hk_mask;
-	int ilb_cpu;
 
 	hk_mask = housekeeping_cpumask(HK_TYPE_KERNEL_NOISE);
 
-	for_each_cpu_and(ilb_cpu, nohz.idle_cpus_mask, hk_mask) {
+	guard(rcu)();
+
+	list_for_each_entry_rcu(sds, &nohz_shared_list, nohz_list_node) {
+		int ilb_cpu;
 
-		if (ilb_cpu == smp_processor_id())
+		/* No idle CPUs in this domain */
+		if (!atomic_read(&sds->nr_idle_cpus))
 			continue;
 
-		if (idle_cpu(ilb_cpu))
-			return ilb_cpu;
+		for_each_cpu_and(ilb_cpu, sds->nohz_idle_cpus_mask, hk_mask) {
+			if (ilb_cpu == smp_processor_id())
+				continue;
+
+			if (idle_cpu(ilb_cpu))
+				return ilb_cpu;
+		}
 	}
 
 	return -1;
-- 
2.43.0

[RESEND RFC PATCH v2 21/29] sched/fair: Introduce sched_asym_prefer_idle() for ILB kick

[K Prateek Nayak]

nohz_balancer_kick() currently depends on "nohz.idle_cpus_maks" to kick
off an idle balance if it finds a more preferred CPU in nohz idle state.

Move the detection logic into sched_asym_prefer_idle() and use the
distributed "sd->shared" based nohz tracking to kick ILB if a more
preferred CPU is found idle.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 70 ++++++++++++++++++++++++++++++++++-----------
 1 file changed, 54 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index dbbb1f3251d2..ca119c57a2a9 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12393,6 +12393,56 @@ static inline int find_new_ilb(void)
 	return -1;
 }
 
+static inline int
+__asym_prefer_idle(int cpu, struct sched_domain *sd_asym, struct cpumask *idle_mask)
+{
+	int i;
+
+	for_each_cpu_and(i, idle_mask, sched_domain_span(sd_asym)) {
+		if (sched_asym(sd_asym, i, cpu))
+			return 1;
+	}
+
+	return 0;
+}
+
+static int sched_asym_prefer_idle(int cpu, struct sched_domain *sd_asym)
+{
+	struct sched_domain *sd = rcu_dereference(per_cpu(sd_nohz, cpu));
+	struct sched_domain_shared *sds;
+
+	if (!sd)
+		return 0;
+
+	/*
+	 * If sd_asym_packing is a subset of sd_llc, don't traverse
+	 * the nohz_shared_list and directly use the mask from
+	 * sd_nohz->shared to find it a preferred CPU is idling.
+	 */
+	if (sd_asym->flags & SD_SHARE_LLC) {
+		sds = sd->shared;
+
+		if (sds &&
+		    atomic_read(&sds->nr_idle_cpus) &&
+		    __asym_prefer_idle(cpu, sd_asym, sds->nohz_idle_cpus_mask))
+			return 1;
+
+		return 0;
+	}
+
+	/* Try the entire list id sd_asym_packing is larger than sd_nohz. */
+	list_for_each_entry_rcu(sds, &nohz_shared_list, nohz_list_node) {
+		/* No idle CPUs in this domain */
+		if (!atomic_read(&sds->nr_idle_cpus))
+			continue;
+
+		if (__asym_prefer_idle(cpu, sd_asym, sds->nohz_idle_cpus_mask))
+			return 1;
+	}
+
+	return 0;
+}
+
 /*
  * Kick a CPU to do the NOHZ balancing, if it is time for it, via a cross-CPU
  * SMP function call (IPI).
@@ -12447,7 +12497,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	unsigned long now = jiffies;
 	struct sched_domain_shared *sds;
 	struct sched_domain *sd;
-	int nr_busy, i, cpu = rq->cpu;
+	int nr_busy, cpu = rq->cpu;
 	unsigned int flags = 0;
 
 	if (unlikely(rq->idle_balance))
@@ -12493,21 +12543,9 @@ static void nohz_balancer_kick(struct rq *rq)
 	}
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
-	if (sd) {
-		/*
-		 * When ASYM_PACKING; see if there's a more preferred CPU
-		 * currently idle; in which case, kick the ILB to move tasks
-		 * around.
-		 *
-		 * When balancing between cores, all the SMT siblings of the
-		 * preferred CPU must be idle.
-		 */
-		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
-			if (sched_asym(sd, i, cpu)) {
-				flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
-				goto unlock;
-			}
-		}
+	if (sd && sched_asym_prefer_idle(cpu, sd)) {
+		flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
+		goto unlock;
 	}
 
 	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
-- 
2.43.0

[RESEND RFC PATCH v2 22/29] sched/fair: Convert sched_balance_nohz_idle() to use nohz_shared_list

[K Prateek Nayak]

Convert the main nohz idle load balancing loop in
sched_balance_nohz_idle() to use the distributed nohz idle tracking
mechanism via "nohz_shared_list".

The nifty trick to balance the nohz owner at the very end using
for_each_cpu_wrap() is lost during this transition. Special care is
taken to ensure nohz.{needs_update,has_blocked} are set correctly for a
reattempt if the balance_cpu turns bust towards the end of nohz
balancing preserving the current behavior.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 62 ++++++++++++++++++++++++++++++++++-----------
 1 file changed, 47 insertions(+), 15 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ca119c57a2a9..b17861bd684f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12789,27 +12789,59 @@ static int sched_balance_nohz_idle(int balancing_cpu, unsigned int flags, unsign
 {
 	/* Earliest time when we have to do rebalance again */
 	unsigned long next_balance = start + 60*HZ;
+	struct sched_domain_shared *sds;
 	unsigned int update_flags = 0;
-	int target_cpu;
 
-	/*
-	 * Start with the next CPU after the balancing CPU so we will end with
-	 * balancing CPU and let a chance for other idle cpu to pull load.
-	 */
-	for_each_cpu_wrap(target_cpu, nohz.idle_cpus_mask, balancing_cpu + 1) {
-		if (!idle_cpu(target_cpu))
+	rcu_read_lock();
+	list_for_each_entry_rcu(sds, &nohz_shared_list, nohz_list_node) {
+		int target_cpu;
+
+		/* No idle CPUs in this domain */
+		if (!atomic_read(&sds->nr_idle_cpus))
 			continue;
 
-		/*
-		 * If balancing CPU gets work to do, stop the load balancing
-		 * work being done for other CPUs. Next load balancing owner
-		 * will pick it up.
-		 */
-		if (!idle_cpu(balancing_cpu) && need_resched())
-			return -EBUSY;
+		for_each_cpu(target_cpu, sds->nohz_idle_cpus_mask) {
+			/* Deal with the balancing CPU at the end. */
+			if (balancing_cpu == target_cpu)
+				continue;
+
+			if (!idle_cpu(target_cpu))
+				continue;
 
-		update_flags |= sched_balance_idle_rq(cpu_rq(target_cpu), flags, &next_balance);
+			/*
+			 * If balancing CPU gets work to do, stop the load balancing
+			 * work being done for other CPUs. Next load balancing owner
+			 * will pick it up.
+			 */
+			if (!idle_cpu(balancing_cpu) && need_resched()) {
+				rcu_read_unlock();
+				return -EBUSY;
+			}
+
+			update_flags |= sched_balance_idle_rq(cpu_rq(target_cpu),
+						flags, &next_balance);
+		}
 	}
+	rcu_read_unlock();
+
+	/*
+	 * If we reach here, all CPUs have been balance and it is time
+	 * to balance the balancing_cpu.
+	 *
+	 * If coincidentally the balancing CPU turns busy at this point
+	 * and is the only nohz idle CPU, we still need to set
+	 * nohz.{needs_update,has_blocked} since the CPU can transition
+	 * back to nohz idle before the tick hits.
+	 *
+	 * In the above case, rq->nohz_tick_stopped is never cleared and
+	 * nohz_balance_enter_idle() skips setting nohz.has_blocked.
+	 * Return -EBUSY instructing the caller to reset the nohz
+	 * signals allowing a reattempt.
+	 */
+	if (!idle_cpu(balancing_cpu) && need_resched())
+		return -EBUSY;
+
+	update_flags |= sched_balance_idle_rq(cpu_rq(balancing_cpu), flags, &next_balance);
 
 	/*
 	 * next_balance will be updated only when there is a need.
-- 
2.43.0

[RESEND RFC PATCH v2 23/29] sched/fair: Remove "nohz.idle_cpus_mask"

[K Prateek Nayak]

All users of "nohz.idle_cpus_mask" have been converted to use the
distributed nohz idle tracking using "nohz_shared_list". Get rid of the
centralized "nohz.idle_cpus_mask" based tracking.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 28 +++++++++++++---------------
 1 file changed, 13 insertions(+), 15 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b17861bd684f..46cb88e88b31 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7143,7 +7143,6 @@ static DEFINE_PER_CPU(cpumask_var_t, should_we_balance_tmpmask);
 #ifdef CONFIG_NO_HZ_COMMON
 
 static struct {
-	cpumask_var_t idle_cpus_mask;
 	atomic_t nr_cpus;
 	int has_blocked;		/* Idle CPUS has blocked load */
 	int needs_update;		/* Newly idle CPUs need their next_balance collated */
@@ -12621,7 +12620,6 @@ void nohz_balance_exit_idle(struct rq *rq)
 		return;
 
 	WRITE_ONCE(rq->nohz_tick_stopped, 0);
-	cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
 	atomic_dec(&nohz.nr_cpus);
 
 	set_cpu_sd_state_busy(rq->cpu);
@@ -12680,8 +12678,9 @@ void nohz_balance_enter_idle(int cpu)
 	/*
 	 * The tick is still stopped but load could have been added in the
 	 * meantime. We set the nohz.has_blocked flag to trig a check of the
-	 * *_avg. The CPU is already part of nohz.idle_cpus_mask so the clear
-	 * of nohz.has_blocked can only happen after checking the new load
+	 * *_avg. The CPU is already part of sd_nohz->idle_cpus_mask so the
+	 * clear of nohz.has_blocked can only happen after checking the new
+	 * load
 	 */
 	if (READ_ONCE(rq->nohz_tick_stopped))
 		goto out;
@@ -12692,7 +12691,6 @@ void nohz_balance_enter_idle(int cpu)
 
 	WRITE_ONCE(rq->nohz_tick_stopped, 1);
 
-	cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 	atomic_inc(&nohz.nr_cpus);
 
 	set_cpu_sd_state_idle(cpu);
@@ -12936,15 +12934,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
  * entering idle state. Here we run ILB directly without issuing IPIs.
  *
  * Note that when this function is called, the tick may not yet be stopped on
- * this CPU yet. nohz.idle_cpus_mask is updated only when tick is stopped and
- * cleared on the next busy tick. In other words, nohz.idle_cpus_mask updates
- * don't align with CPUs enter/exit idle to avoid bottlenecks due to high idle
- * entry/exit rate (usec). So it is possible that _nohz_idle_balance() is
- * called from this function on (this) CPU that's not yet in the mask. That's
- * OK because the goal of nohz_run_idle_balance() is to run ILB only for
- * updating the blocked load of already idle CPUs without waking up one of
- * those idle CPUs and outside the preempt disable / IRQ off phase of the local
- * cpu about to enter idle, because it can take a long time.
+ * this CPU yet. sd_nohz->nohz_idle_cpus_mask is updated only when tick is
+ * stopped and cleared on the next busy tick. In other words,
+ * sd_nohz->nohz_idle_cpus_mask updates don't align with CPUs enter/exit idle
+ * to avoid bottlenecks due to high idle entry/exit rate (usec). So it is
+ * possible that _nohz_idle_balance() is called from this function on (this)
+ * CPU that's not yet in the mask. That's OK because the goal of
+ * nohz_run_idle_balance() is to run ILB only for updating the blocked load of
+ * already idle CPUs without waking up one of those idle CPUs and outside the
+ * preempt disable / IRQ off phase of the local cpu about to enter idle,
+ * because it can take a long time.
  */
 void nohz_run_idle_balance(int cpu)
 {
@@ -14138,6 +14137,5 @@ __init void init_sched_fair_class(void)
 #ifdef CONFIG_NO_HZ_COMMON
 	nohz.next_balance = jiffies;
 	nohz.next_blocked = jiffies;
-	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
 #endif
 }
-- 
2.43.0

[RESEND RFC PATCH v2 24/29] sched/fair: Optimize global "nohz.nr_cpus" tracking

[K Prateek Nayak]

Optimize "nohz.nr_cpus" by tracking number of "sd_nohz->shared" with
non-zero "nr_idle_cpus" count via "nohz.nr_doms" and only updating at
the boundary of "sd_nohz->shared->nr_idle_cpus" going from 0 -> 1 and
back from 1 -> 0.

This also introduces a chance of double accounting when a nohz idle
entry or the tick races with hotplug or cpuset as described in
__nohz_exit_idle_tracking().

__nohz_exit_idle_tracking() called when the sched_domain_shared nodes
tracking idle CPUs are freed is used to correct any potential double
accounting which can unnecessarily trigger nohz idle balances even when
all the CPUs have tick enabled.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c     | 63 ++++++++++++++++++++++++++++++++++++-----
 kernel/sched/sched.h    |  1 +
 kernel/sched/topology.c |  1 +
 3 files changed, 58 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 46cb88e88b31..f622104d54d7 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7143,7 +7143,7 @@ static DEFINE_PER_CPU(cpumask_var_t, should_we_balance_tmpmask);
 #ifdef CONFIG_NO_HZ_COMMON
 
 static struct {
-	atomic_t nr_cpus;
+	atomic_t nr_doms;
 	int has_blocked;		/* Idle CPUS has blocked load */
 	int needs_update;		/* Newly idle CPUs need their next_balance collated */
 	unsigned long next_balance;     /* in jiffy units */
@@ -12512,7 +12512,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	 * None are in tickless mode and hence no need for NOHZ idle load
 	 * balancing:
 	 */
-	if (likely(!atomic_read(&nohz.nr_cpus)))
+	if (likely(!atomic_read(&nohz.nr_doms)))
 		return;
 
 	if (READ_ONCE(nohz.has_blocked) &&
@@ -12609,7 +12609,8 @@ static void set_cpu_sd_state_busy(int cpu)
 		return;
 
 	cpumask_clear_cpu(cpu, sd->shared->nohz_idle_cpus_mask);
-	atomic_dec(&sd->shared->nr_idle_cpus);
+	if (!atomic_dec_return(&sd->shared->nr_idle_cpus))
+		atomic_dec(&nohz.nr_doms);
 }
 
 void nohz_balance_exit_idle(struct rq *rq)
@@ -12620,7 +12621,6 @@ void nohz_balance_exit_idle(struct rq *rq)
 		return;
 
 	WRITE_ONCE(rq->nohz_tick_stopped, 0);
-	atomic_dec(&nohz.nr_cpus);
 
 	set_cpu_sd_state_busy(rq->cpu);
 }
@@ -12639,7 +12639,58 @@ static void set_cpu_sd_state_idle(int cpu)
 		return;
 
 	cpumask_set_cpu(cpu, sd->shared->nohz_idle_cpus_mask);
-	atomic_inc(&sd->shared->nr_idle_cpus);
+	if (!atomic_fetch_inc(&sd->shared->nr_idle_cpus))
+		atomic_inc(&nohz.nr_doms);
+}
+
+/*
+ * Correct nohz.nr_doms if sd_nohz->shared was found to have non-zero
+ * nr_idle_cpus when freeing. No local references to sds remain at
+ * this point and the only reference possible via "nohz_shared_list"
+ * will be dropped after the grace period.
+ */
+void __nohz_exit_idle_tracking(struct sched_domain_shared *sds)
+{
+
+	/*
+	 * It is possible for a idle entry to race with sched domain rebuild like:
+	 *
+	 *  CPU0 (hotplug)			CPU1 (nohz idle)
+	 *
+	 *  rq->offline(CPU1)
+	 *    set_cpu_sd_state_busy()
+	 *    rq->sd = sdd;			# Processes IPI, re-enters nohz idle
+	 *    ...				# For old sd_nohz
+	 *    ...				atomic_fetch_inc(&sd_nohz->shared->nr_idle_cpus);
+	 *    ...				atomic_inc(&nohz.nr_doms); # XXX: Accounted once
+	 *    update_top_cache_domains()
+	 *  rq->online(CPU1)
+	 *  # rq->nohz_tick_stopped is true
+	 *  set_cpu_sd_state_idle()
+	 *    # For new sd_nohz
+	 *    atomic_fetch_inc(&sd_nohz->shared->nr_idle_cpus);
+	 *    atomic_inc(&nohz.nr_doms); # XXX: Accounted twice
+	 *  ...
+	 *
+	 * "nohz.nr_doms" is used as an entry criteria in nohz_balancer_kick()
+	 * and this double accounting can lead to wasted idle balancing
+	 * triggers. Use this path to correct the accounting:
+	 *
+	 *  # In sds_delayed_free()
+	 *  __nohz_exit_idle_tracking(sds)
+	 *    # sd->shared->nr_idle_cpus is != 0
+	 *    atomic_dec(&nohz.nr_doms); # XXX: Fixes nohz.nr_doms
+	 */
+	if (atomic_read(&sds->nr_idle_cpus)) {
+		/*
+		 * Reset the "nr_idle_cpus" indicator to prevent
+		 * existing readers from traversing the idle mask
+		 * to reduce chances of traversing the same CPU
+		 * twice.
+		 */
+		atomic_set(&sds->nr_idle_cpus, 0);
+		atomic_dec(&nohz.nr_doms);
+	}
 }
 
 static void cpu_sd_exit_nohz_balance(struct rq *rq)
@@ -12691,8 +12742,6 @@ void nohz_balance_enter_idle(int cpu)
 
 	WRITE_ONCE(rq->nohz_tick_stopped, 1);
 
-	atomic_inc(&nohz.nr_cpus);
-
 	set_cpu_sd_state_idle(cpu);
 
 	/*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 159c24981ead..3433de20a249 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -3266,6 +3266,7 @@ extern void cfs_bandwidth_usage_dec(void);
 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
 extern struct list_head nohz_shared_list;
 
+extern void __nohz_exit_idle_tracking(struct sched_domain_shared *sds);
 extern void nohz_balance_exit_idle(struct rq *rq);
 #else /* !CONFIG_NO_HZ_COMMON: */
 static inline void nohz_balance_exit_idle(struct rq *rq) { }
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index af4ce9451cd0..ec549fb7d7fc 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -615,6 +615,7 @@ static int sds_delayed_free(struct sched_domain_shared *sds)
 	scoped_guard(raw_spinlock_irqsave, &nohz_shared_list_lock)
 		list_del_rcu(&sds->nohz_list_node);
 
+	__nohz_exit_idle_tracking(sds);
 	call_rcu(&sds->rcu, destroy_sched_domain_shared_rcu);
 	return 1;
 }
-- 
2.43.0

[RESEND RFC PATCH v2 25/29] sched/topology: Add basic debug information for "nohz_shared_list"

[K Prateek Nayak]

Introduce debug_nohz_shared_list_update() to count the number of entries
in "nohz_shared_list" after each list modification.

XXX: There isn't a great way to jump from a sched_domain_shared object
to the sched_domain struct that references it which prevents printing
more information about the sched domain that was linked with the
shared object.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/topology.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index ec549fb7d7fc..738e6084d5be 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -471,6 +471,20 @@ DEFINE_PER_CPU(struct sched_domain __rcu *, sd_nohz);
 static DEFINE_RAW_SPINLOCK(nohz_shared_list_lock);
 LIST_HEAD(nohz_shared_list);
 
+static void debug_nohz_shared_list_update(void)
+{
+	struct sched_domain_shared *sds;
+	int count = 0;
+
+	if (!sched_debug())
+		return;
+
+	list_for_each_entry(sds, &nohz_shared_list, nohz_list_node)
+		count++;
+
+	pr_info("%s: %d nohz_shared_list entries found.\n", __func__, count);
+}
+
 static int __sds_nohz_idle_alloc_init(struct sched_domain_shared *sds, int node)
 {
 	sds->nohz_list_node = (struct list_head)LIST_HEAD_INIT(sds->nohz_list_node);
@@ -588,6 +602,7 @@ static void update_nohz_domain(int cpu)
 
 		guard(raw_spinlock)(&nohz_shared_list_lock);
 		list_add(&sds->nohz_list_node, &nohz_shared_list);
+		debug_nohz_shared_list_update();
 	}
 
 	WARN_ON_ONCE(sd && !sds);
@@ -612,8 +627,10 @@ static int sds_delayed_free(struct sched_domain_shared *sds)
 	if (list_empty(&sds->nohz_list_node))
 		return 0;
 
-	scoped_guard(raw_spinlock_irqsave, &nohz_shared_list_lock)
+	scoped_guard(raw_spinlock_irqsave, &nohz_shared_list_lock) {
 		list_del_rcu(&sds->nohz_list_node);
+		debug_nohz_shared_list_update();
+	}
 
 	__nohz_exit_idle_tracking(sds);
 	call_rcu(&sds->rcu, destroy_sched_domain_shared_rcu);
-- 
2.43.0

[RESEND RFC PATCH v2 26/29] [EXPERIMENTAL] sched/fair: Add push task framework

[K Prateek Nayak]

From: Vincent Guittot <vincent.guittot@linaro.org>

Add the skeleton for push task infrastructure. The empty
push_fair_task() prototype will be used to implement proactive idle
balancing in subsequent commits.

  [ prateek: Broke off relevant bits from [1] ]

Link: https://lore.kernel.org/all/20250302210539.1563190-6-vincent.guittot@linaro.org/ [1]
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
Peter, the plist is still being used since a plist node already exists
in the task_struct which can be reused. Depending on the collective push
effort, we can either settle on the reuse of the plist_node or add a new
list_head for fair tasks.
---
 kernel/sched/fair.c  | 102 +++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |   2 +
 2 files changed, 104 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f622104d54d7..e6ba7bb09a61 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6865,6 +6865,9 @@ requeue_delayed_entity(struct sched_entity *se)
 	clear_delayed(se);
 }
 
+static void fair_remove_pushable_task(struct rq *rq, struct task_struct *p);
+static void fair_add_pushable_task(struct rq *rq, struct task_struct *p);
+
 /*
  * The enqueue_task method is called before nr_running is
  * increased. Here we update the fair scheduling stats and
@@ -7015,6 +7018,7 @@ static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags)
 		h_nr_idle = task_has_idle_policy(p);
 		if (task_sleep || task_delayed || !se->sched_delayed)
 			h_nr_runnable = 1;
+		fair_remove_pushable_task(rq, p);
 	}
 
 	for_each_sched_entity(se) {
@@ -8954,6 +8958,12 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf
 		put_prev_entity(cfs_rq, pse);
 		set_next_entity(cfs_rq, se);
 
+		/*
+		 * The previous task might be eligible for being pushed on
+		 * another cpu if it is still active.
+		 */
+		fair_add_pushable_task(rq, prev);
+
 		__set_next_task_fair(rq, p, true);
 	}
 
@@ -9017,6 +9027,13 @@ static void put_prev_task_fair(struct rq *rq, struct task_struct *prev, struct t
 		cfs_rq = cfs_rq_of(se);
 		put_prev_entity(cfs_rq, se);
 	}
+
+	/*
+	 * The previous task might be eligible for being pushed on another cpu
+	 * if it is still active.
+	 */
+	fair_add_pushable_task(rq, prev);
+
 }
 
 /*
@@ -13028,6 +13045,79 @@ static void nohz_newidle_balance(struct rq *this_rq)
 	atomic_or(NOHZ_NEWILB_KICK, nohz_flags(this_cpu));
 }
 
+/*
+ * Push based load balancing: It may take several ticks before a nohz idle CPU
+ * is selected for load balancing which is less than ideal for latency
+ * sensitive tasks stuck on overloaded CPUs.
+ *
+ * If a fair task is preempted, opportunistically try pushing to an idle CPU if
+ * the indicators say it is favourable. Since a busy CPU is handling the push,
+ * this is a time sensitive operation.
+ */
+static inline bool fair_push_task(struct rq *rq, struct task_struct *p)
+{
+	if (!task_on_rq_queued(p))
+		return false;
+
+	if (p->se.sched_delayed)
+		return false;
+
+	if (p->nr_cpus_allowed == 1)
+		return false;
+
+	if (task_current_donor(rq, p))
+		return false;
+
+	if (task_current(rq, p))
+		return false;
+
+	return true;
+}
+
+static inline int has_pushable_tasks(struct rq *rq)
+{
+	return !plist_head_empty(&rq->cfs.pushable_tasks);
+}
+
+/*
+ * See if the non running fair tasks on this rq can be sent on other CPUs
+ * that fits better with their profile.
+ */
+static bool push_fair_task(struct rq *rq)
+{
+	return false;
+}
+
+static void push_fair_tasks(struct rq *rq)
+{
+	/* push_fair_task() will return true if it moved a fair task */
+	while (push_fair_task(rq))
+		;
+}
+
+static DEFINE_PER_CPU(struct balance_callback, fair_push_head);
+
+static inline void fair_queue_pushable_tasks(struct rq *rq)
+{
+	if (!has_pushable_tasks(rq))
+		return;
+
+	queue_balance_callback(rq, &per_cpu(fair_push_head, rq->cpu), push_fair_tasks);
+}
+static void fair_remove_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+}
+
+static void fair_add_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	if (fair_push_task(rq, p)) {
+		plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+		/* Place the task with greates chance to be pushed first. */
+		plist_node_init(&p->pushable_tasks, p->prio);
+		plist_add(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+	}
+}
 #else /* !CONFIG_NO_HZ_COMMON: */
 static inline void cpu_sd_exit_nohz_balance(struct rq *rq) { }
 static inline void cpu_sd_reenter_nohz_balance(struct rq *rq) { }
@@ -13039,6 +13129,10 @@ static inline bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle
 }
 
 static inline void nohz_newidle_balance(struct rq *this_rq) { }
+
+static inline void fair_remove_pushable_task(struct rq *rq, struct task_struct *p) { }
+static inline void fair_add_pushable_task(struct rq *rq, struct task_struct *p) { }
+static inline void fair_queue_pushable_tasks(struct rq *rq) { }
 #endif /* !CONFIG_NO_HZ_COMMON */
 
 /*
@@ -13738,6 +13832,8 @@ static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool firs
 {
 	struct sched_entity *se = &p->se;
 
+	fair_remove_pushable_task(rq, p);
+
 	if (task_on_rq_queued(p)) {
 		/*
 		 * Move the next running task to the front of the list, so our
@@ -13753,6 +13849,11 @@ static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool firs
 	if (hrtick_enabled_fair(rq))
 		hrtick_start_fair(rq, p);
 
+	/*
+	 * Try to push prev task before checking misfit for next task as
+	 * the migration of prev can make next fitting the CPU
+	 */
+	fair_queue_pushable_tasks(rq);
 	update_misfit_status(p, rq);
 	sched_fair_update_stop_tick(rq, p);
 }
@@ -13782,6 +13883,7 @@ void init_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	cfs_rq->tasks_timeline = RB_ROOT_CACHED;
 	cfs_rq->zero_vruntime = (u64)(-(1LL << 20));
+	plist_head_init(&cfs_rq->pushable_tasks);
 	raw_spin_lock_init(&cfs_rq->removed.lock);
 }
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 3433de20a249..91928a371588 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -743,6 +743,8 @@ struct cfs_rq {
 	struct list_head	leaf_cfs_rq_list;
 	struct task_group	*tg;	/* group that "owns" this runqueue */
 
+	struct plist_head	pushable_tasks;
+
 	/* Locally cached copy of our task_group's idle value */
 	int			idle;
 
-- 
2.43.0

[RESEND RFC PATCH v2 27/29] [EXPERIMENTAL] sched/fair: Proactive idle balance using push mechanism

[K Prateek Nayak]

Proactively try to push tasks to one of the CPUs in the sd_nohz domain
if "nr_idle_cpus" indicator indicates the presence of idle CPUs.

pick_next_pushable_fair_task() is taken from Vincent's series [1] as is
but the locking rules in push_fair_task() has been replaced with an IPI
based __ttwu_queue_wakelist(). Few additional checks have been added to
catch any corner cases with proxy execution where neither the current,
not the donor is pushable.

For the sake of this PoC, the __ttwu_queue_wakelist() based mechanism is
being used as is. If folks are in agreement with wider use of the
wakelist based migration, we can work on making this wakelist based
activation path more generic to be used for migrations too.

Although it is logical to traverse the "sd_nohz->shared->nohz_idle_cpus"
only, in testing, traversing the entire span was found to be more
beneficial.

Link: https://lore.kernel.org/all/20250302210539.1563190-6-vincent.guittot@linaro.org/ [1]
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/core.c  |  2 +-
 kernel/sched/fair.c  | 93 +++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h |  1 +
 3 files changed, 94 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 35cb640b7266..388805c4436c 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3769,7 +3769,7 @@ bool call_function_single_prep_ipi(int cpu)
  * via sched_ttwu_wakeup() for activation so the wakee incurs the cost
  * of the wakeup instead of the waker.
  */
-static void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags)
+void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags)
 {
 	struct rq *rq = cpu_rq(cpu);
 
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e6ba7bb09a61..34aeb8e58e0b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -13079,12 +13079,103 @@ static inline int has_pushable_tasks(struct rq *rq)
 	return !plist_head_empty(&rq->cfs.pushable_tasks);
 }
 
+static struct task_struct *pick_next_pushable_fair_task(struct rq *rq)
+{
+	struct task_struct *p;
+
+	if (!has_pushable_tasks(rq))
+		return NULL;
+
+	p = plist_first_entry(&rq->cfs.pushable_tasks,
+			      struct task_struct, pushable_tasks);
+
+	WARN_ON_ONCE(rq->cpu != task_cpu(p));
+	WARN_ON_ONCE(task_current(rq, p));
+	WARN_ON_ONCE(task_current_donor(rq, p));
+	WARN_ON_ONCE(p->nr_cpus_allowed <= 1);
+	WARN_ON_ONCE(!task_on_rq_queued(p));
+
+	/*
+	 * Remove task from the pushable list as we try only once after that
+	 * the task has been put back in enqueued list.
+	 */
+	plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+
+	return p;
+}
+
+static inline bool should_push_tasks(struct rq *rq)
+{
+	struct sched_domain_shared *sds;
+	struct sched_domain *sd;
+	int cpu = cpu_of(rq);
+
+	/* TODO: Add a CPU local failure counter. */
+
+	/* CPU doesn't have any fair task to push. */
+	if (!has_pushable_tasks(rq))
+		return false;
+
+	/* CPU is overloaded! Do not waste cycles pushing tasks. */
+	if (!fits_capacity(cpu_util_cfs(cpu), capacity_of(cpu)))
+		return false;
+
+	guard(rcu)();
+
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
+	if (!sd)
+		return false;
+
+	/*
+	 * We may not be able to find a push target.
+	 * Skip for this tick and depend on the periodic
+	 * balance to pull the queued tasks.
+	 */
+	sds = sd->shared;
+	if (!sds || !atomic_read(&sds->nr_idle_cpus))
+		return false;
+
+	return true;
+}
+
 /*
  * See if the non running fair tasks on this rq can be sent on other CPUs
  * that fits better with their profile.
  */
 static bool push_fair_task(struct rq *rq)
 {
+	struct task_struct *p = pick_next_pushable_fair_task(rq);
+	struct sched_domain_shared *sds;
+	int cpu, this_cpu = cpu_of(rq);
+	struct sched_domain *sd;
+
+	if (!p)
+		return false;
+
+	guard(rcu)();
+
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
+	if (!sd)
+		return false;
+
+	/*
+	 * It is possble to have idle CPUs with ticks enabled. To maximize the chance
+	 * of pulling a task, traverse the entire sched_domain_span() instead of just
+	 * the sd->shared->nohz_idle_cpus.
+	 */
+	for_each_cpu_and_wrap(cpu, p->cpus_ptr, sched_domain_span(sd), this_cpu + 1) {
+		struct rq *target_rq;
+
+		if (!idle_cpu(cpu))
+			continue;
+
+		target_rq = cpu_rq(cpu);
+		deactivate_task(rq, p, 0);
+		set_task_cpu(p, cpu);
+		__ttwu_queue_wakelist(p, cpu, 0);
+		return true;
+	}
+
 	return false;
 }
 
@@ -13099,7 +13190,7 @@ static DEFINE_PER_CPU(struct balance_callback, fair_push_head);
 
 static inline void fair_queue_pushable_tasks(struct rq *rq)
 {
-	if (!has_pushable_tasks(rq))
+	if (should_push_tasks(rq))
 		return;
 
 	queue_balance_callback(rq, &per_cpu(fair_push_head, rq->cpu), push_fair_tasks);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 91928a371588..451666753c2a 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2939,6 +2939,7 @@ static inline void __block_task(struct rq *rq, struct task_struct *p)
 
 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
+void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags);
 
 extern void wakeup_preempt(struct rq *rq, struct task_struct *p, int flags);
 
-- 
2.43.0

[RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push

[K Prateek Nayak]

Pushing tasks can fail for multitude of reasons - task affinity, the
unavailability of an idle CPUs by the time balance callback is executed,
etc.

Maintain a CPU local counter in sched_domain to rate limit push attempts
if the failures build up. This counter is reset at the time of periodic
balance to the value in "nr_idle_scan".

Since "nr_idle_scan" is only computed for SIS_UTIL, rate limiting has
been guarded behind the same sched_feat().

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 include/linux/sched/topology.h |  4 ++++
 kernel/sched/fair.c            | 23 +++++++++++++++++++++--
 2 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 074ee2980cdf..ebe26ce82c1a 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -122,6 +122,10 @@ struct sched_domain {
 	unsigned int alb_failed;
 	unsigned int alb_pushed;
 
+	/* Push load balancing */
+	unsigned long last_nr_push_update;
+	int nr_push_attempt;
+
 	/* SD_BALANCE_EXEC stats */
 	unsigned int sbe_count;
 	unsigned int sbe_balanced;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 34aeb8e58e0b..46d33ab63336 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12356,6 +12356,16 @@ static void sched_balance_domains(struct rq *rq, enum cpu_idle_type idle)
 		rq->max_idle_balance_cost =
 			max((u64)sysctl_sched_migration_cost, max_cost);
 	}
+	if (sched_feat(SIS_UTIL)) {
+		sd = rcu_dereference(per_cpu(sd_llc, cpu));
+
+		if (sd && sd->shared &&
+		    time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
+			sd->nr_push_attempt = READ_ONCE(sd->shared->nr_idle_scan);
+			sd->last_nr_push_update = jiffies;
+		}
+	}
+
 	rcu_read_unlock();
 
 	/*
@@ -13110,8 +13120,6 @@ static inline bool should_push_tasks(struct rq *rq)
 	struct sched_domain *sd;
 	int cpu = cpu_of(rq);
 
-	/* TODO: Add a CPU local failure counter. */
-
 	/* CPU doesn't have any fair task to push. */
 	if (!has_pushable_tasks(rq))
 		return false;
@@ -13126,6 +13134,10 @@ static inline bool should_push_tasks(struct rq *rq)
 	if (!sd)
 		return false;
 
+	/* We've failed to push task too many times. */
+	if (sched_feat(SIS_UTIL) && sd->nr_push_attempt <= 0)
+		return false;
+
 	/*
 	 * We may not be able to find a push target.
 	 * Skip for this tick and depend on the periodic
@@ -13176,6 +13188,13 @@ static bool push_fair_task(struct rq *rq)
 		return true;
 	}
 
+	/*
+	 * If the push failed after a full search, decrement the
+	 * attempt counter to dicourage further attempts. Periodic
+	 * balancer will reset the "nr_push_attempt" after a while.
+	 */
+	sd->nr_push_attempt--;
+
 	return false;
 }
 
-- 
2.43.0

[RESEND RFC PATCH v2 29/29] [EXPERIMENTAL] sched/fair: Faster alternate for intra-NUMA newidle balance

[K Prateek Nayak]

Kernels that enable CONFIG_PREEMPTION only pull a single task during
newidle balance to keep the latency low. In standard newidle balance
path, the computation of busiest group, busiest rq, and then pulling
a single task from the busy rq adds a lot of overhead.

During the discussions at OSPM around overheads of load balancing, Peter
suggested trying out a different strategy for inter-NUMA newidle balance
with the goal of pulling a task as quickly as possible.

Try out an alternative strategy of newidle balance of directry
traversing the CPUs in the sched domain to pull runnable tasks.

Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/fair.c | 119 ++++++++++++++++++++++++++++++++++----------
 1 file changed, 93 insertions(+), 26 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 46d33ab63336..aa2821a9b800 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11701,6 +11701,11 @@ static int need_active_balance(struct lb_env *env)
 
 static int active_load_balance_cpu_stop(void *data);
 
+static inline bool sched_newidle_stop_balance(struct rq *rq)
+{
+	return (rq->nr_running > 0 || rq->ttwu_pending);
+}
+
 static int should_we_balance(struct lb_env *env)
 {
 	struct cpumask *swb_cpus = this_cpu_cpumask_var_ptr(should_we_balance_tmpmask);
@@ -11722,7 +11727,7 @@ static int should_we_balance(struct lb_env *env)
 	 * to optimize wakeup latency.
 	 */
 	if (env->idle == CPU_NEWLY_IDLE) {
-		if (env->dst_rq->nr_running > 0 || env->dst_rq->ttwu_pending)
+		if (sched_newidle_stop_balance(env->dst_rq))
 			return 0;
 		return 1;
 	}
@@ -13256,6 +13261,7 @@ static inline void fair_queue_pushable_tasks(struct rq *rq) { }
  */
 static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)
 {
+	struct cpumask *cpus = this_cpu_cpumask_var_ptr(load_balance_mask);
 	unsigned long next_balance = jiffies + HZ;
 	int this_cpu = this_rq->cpu;
 	int continue_balancing = 1;
@@ -13315,8 +13321,11 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)
 	t0 = sched_clock_cpu(this_cpu);
 	sched_balance_update_blocked_averages(this_cpu);
 
+	cpumask_clear(cpus);
+
 	rcu_read_lock();
 	for_each_domain(this_cpu, sd) {
+		unsigned int weight = 1;
 		u64 domain_cost;
 
 		update_next_balance(sd, &next_balance);
@@ -13324,40 +13333,98 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)
 		if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
 			break;
 
-		if (sd->flags & SD_BALANCE_NEWIDLE) {
-			unsigned int weight = 1;
+		if (!(sd->flags & SD_BALANCE_NEWIDLE))
+			continue;
 
-			if (sched_feat(NI_RANDOM)) {
-				/*
-				 * Throw a 1k sided dice; and only run
-				 * newidle_balance according to the success
-				 * rate.
-				 */
-				u32 d1k = sched_rng() % 1024;
-				weight = 1 + sd->newidle_ratio;
-				if (d1k > weight) {
-					update_newidle_stats(sd, 0);
-					continue;
-				}
-				weight = (1024 + weight/2) / weight;
+		if (sched_feat(NI_RANDOM)) {
+			/*
+			 * Throw a 1k sided dice; and only run
+			 * newidle_balance according to the success
+			 * rate.
+			 */
+			u32 d1k = sched_rng() % 1024;
+			weight = 1 + sd->newidle_ratio;
+			if (d1k > weight) {
+				update_newidle_stats(sd, 0);
+				continue;
 			}
+			weight = (1024 + weight/2) / weight;
+		}
 
-			pulled_task = sched_balance_rq(this_cpu, this_rq,
-						   sd, CPU_NEWLY_IDLE,
-						   &continue_balancing);
 
-			t1 = sched_clock_cpu(this_cpu);
-			domain_cost = t1 - t0;
-			curr_cost += domain_cost;
-			t0 = t1;
+		/*
+		 * Non-preemptible kernels can pull more than one task during
+		 * newidle balance and NUMA domains may need special
+		 * consideration to preserve tasks on preferred NUMA node.
+		 *
+		 * Only take fast-path on preemptible kernels for intra NUMA
+		 * domains.
+		 */
+		if (!IS_ENABLED(CONFIG_PREEMPTION) || (sd->flags & SD_NUMA)) {
+			pulled_task = sched_balance_rq(this_cpu, this_rq,
+						       sd, CPU_NEWLY_IDLE,
+						       &continue_balancing);
+		} else {
+			struct lb_env env = {
+				.sd		= sd,
+				.dst_cpu	= this_cpu,
+				.dst_rq		= this_rq,
+				.idle		= CPU_NEWLY_IDLE,
+			};
+			int cpu;
 
 			/*
-			 * Track max cost of a domain to make sure to not delay the
-			 * next wakeup on the CPU.
+			 * Clear the CPUs of child domain. They have already
+			 * been visited during last balance. !NUMA domains do
+			 * not overlap so simply excluding the previous
+			 * domain's span should be enough.
 			 */
-			update_newidle_cost(sd, domain_cost, weight * !!pulled_task);
+			cpumask_andnot(cpus, sched_domain_span(sd), cpus);
+
+			/* Commit to searching the sd if we are idle at start. */
+			continue_balancing = sched_newidle_stop_balance(this_rq);
+			if (!continue_balancing)
+				break;
+
+			for_each_cpu_wrap(cpu, cpus, this_cpu + 1) {
+				struct task_struct *p = NULL;
+				struct rq *rq = cpu_rq(cpu);
+
+				/* Not overloaded with runnable tasks. */
+				if (rq->cfs.h_nr_runnable <= 1)
+					continue;
+
+				scoped_guard(rq_lock, rq) {
+					/* Check again with rq lock held. */
+					if (rq->cfs.h_nr_runnable <= 1)
+						break;
+
+					env.src_cpu = cpu;
+					env.src_rq = rq;
+
+					update_rq_clock(rq);
+					p = detach_one_task(&env);
+				}
+
+				if (p) {
+					attach_one_task(this_rq, p);
+					pulled_task = 1;
+					break;
+				}
+			}
 		}
 
+		t1 = sched_clock_cpu(this_cpu);
+		domain_cost = t1 - t0;
+		curr_cost += domain_cost;
+		t0 = t1;
+
+		/*
+		 * Track max cost of a domain to make sure to not delay the
+		 * next wakeup on the CPU.
+		 */
+		update_newidle_cost(sd, domain_cost, weight * !!pulled_task);
+
 		/*
 		 * Stop searching for tasks to pull if there are
 		 * now runnable tasks on this rq.
-- 
2.43.0

Re: [RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push

[Christian Loehle]

On 12/8/25 09:27, K Prateek Nayak wrote:
> Pushing tasks can fail for multitude of reasons - task affinity, the
> unavailability of an idle CPUs by the time balance callback is executed,
> etc.
> 
> Maintain a CPU local counter in sched_domain to rate limit push attempts
> if the failures build up. This counter is reset at the time of periodic
> balance to the value in "nr_idle_scan".
> 
> Since "nr_idle_scan" is only computed for SIS_UTIL, rate limiting has
> been guarded behind the same sched_feat().
> 
> Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
> ---
>  include/linux/sched/topology.h |  4 ++++
>  kernel/sched/fair.c            | 23 +++++++++++++++++++++--
>  2 files changed, 25 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
> index 074ee2980cdf..ebe26ce82c1a 100644
> --- a/include/linux/sched/topology.h
> +++ b/include/linux/sched/topology.h
> @@ -122,6 +122,10 @@ struct sched_domain {
>  	unsigned int alb_failed;
>  	unsigned int alb_pushed;
>  
> +	/* Push load balancing */
> +	unsigned long last_nr_push_update;
> +	int nr_push_attempt;
> +
>  	/* SD_BALANCE_EXEC stats */
>  	unsigned int sbe_count;
>  	unsigned int sbe_balanced;
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 34aeb8e58e0b..46d33ab63336 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -12356,6 +12356,16 @@ static void sched_balance_domains(struct rq *rq, enum cpu_idle_type idle)
>  		rq->max_idle_balance_cost =
>  			max((u64)sysctl_sched_migration_cost, max_cost);
>  	}
> +	if (sched_feat(SIS_UTIL)) {
> +		sd = rcu_dereference(per_cpu(sd_llc, cpu));
> +
> +		if (sd && sd->shared &&
> +		    time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
> +			sd->nr_push_attempt = READ_ONCE(sd->shared->nr_idle_scan);
> +			sd->last_nr_push_update = jiffies;
> +		}
> +	}
> +
>  	rcu_read_unlock();
>  
>  	/*
> @@ -13110,8 +13120,6 @@ static inline bool should_push_tasks(struct rq *rq)
>  	struct sched_domain *sd;
>  	int cpu = cpu_of(rq);
>  
> -	/* TODO: Add a CPU local failure counter. */
> -
>  	/* CPU doesn't have any fair task to push. */
>  	if (!has_pushable_tasks(rq))
>  		return false;
> @@ -13126,6 +13134,10 @@ static inline bool should_push_tasks(struct rq *rq)
>  	if (!sd)
>  		return false;
>  
> +	/* We've failed to push task too many times. */
> +	if (sched_feat(SIS_UTIL) && sd->nr_push_attempt <= 0)
> +		return false;
> +
>  	/*
>  	 * We may not be able to find a push target.
>  	 * Skip for this tick and depend on the periodic
> @@ -13176,6 +13188,13 @@ static bool push_fair_task(struct rq *rq)
>  		return true;
>  	}
>  
> +	/*
> +	 * If the push failed after a full search, decrement the
> +	 * attempt counter to dicourage further attempts. Periodic
> +	 * balancer will reset the "nr_push_attempt" after a while.
> +	 */
> +	sd->nr_push_attempt--;
> +
>  	return false;
>  }
>  

Just to confirm, but this patch is included when the cover letter mentions "push" for the
benchmarks?
Did this help the regressions then?

Re: [RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing

[Shrikanth Hegde]

On 12/8/25 2:56 PM, K Prateek Nayak wrote:
> Resending the series with the correct Email IDs this time. Sorry for the
> noise.
> 
> This is the combined successor to the following two series:
> 
> https://lore.kernel.org/lkml/20250904041516.3046-1-kprateek.nayak@amd.com/
> https://lore.kernel.org/lkml/20250409111539.23791-1-kprateek.nayak@amd.com/
> 
> Most bits are same except for more initial cleanups. Changelog is
> attached towards the end. This topic will be discussed at LPC'25 in the
> "Scheduler and Real-Time MC" - jump to "LPC 2025" to know what will be
> discussed.
> 
> 
> Problem statement
> =================
> 
> This series tackles three problems:
> 
> 1. The busy load balancing always uses the first CPU of
>     group_balance_mask() for load balancing which puts all the load
>     balancing responsibility on a single CPU.
> 
> 2. The "nohz.nr_idle" and "nohz.idle_cpus" are global system-wide
>     variables that can run into scalability bottlenecks on a large
>     core-count system.
> 

I think they are nohz.nr_cpus and nohz.idle_cpus_mask. isn't it?


> 3. Periodic balance can take a long time to even out imbalance on
>     systems with mostly large and flat sched-domain hierarchy. Preempted
>     tasks may wait for a long time behind other runnable tasks increasing
>     the tail latencies.
> 
> This series aims at addressing the combined problems listed above.
> 
> 
> Implementation details
> ======================
> 
> Note: Sections marked EXPERIMENTAL are known to introduce regeressions
> for certain benchmarks. These have been discussed in details in the next
> section. These patches also may be incomplete from a schedstats
> accounting standpoint.
> 
> 
> o Busy balancing optimization
> 
> The busy balance CPU is always the first cpu of
> "sched_group->scg->group_balance_mask". "sgc" object is shared by all
> the CPUs on the "group_balance_mask", even for the overlapping domains.
> 
> To keep overheads minimal, a simple "busy_balance_cpu" is maintained in
> the shared "sgc" object. A CPU is nominated to handle the busy
> balancing. Once the CPU is done with its turn, it nominates the next CPU
> on the group_balance_mask.
> 
>    - Advantages: The responsibility of busy balance is rotated among the
>      CPUs on the group_balance_mask. Maintaining the "busy_balance_cpu"
>      only requires a READ_ONCE() / WRITE_ONCE() modifications making it
>      relatively cheap.
> 
>    - Disadvantages: The currently nominated "busy_balance_cpu" can run
>      for a long time with bh disabled that can prevent balancing work
>      from running however, it is no worse that the current state where
>      the first CPU continues running with bh disabled for a prolonged
>      period of time.
> 
> 
> o Centralized "nohz" accounting optimizations
> 
> The centralized "nohz" tracking maintains the number and list of CPUs
> that are in nohz idle state. These are done via atomic operations on
> variables shared across the system which is less than ideal.
> 
> Peter suggested breaking the mask down and embedding it into the
> sched_domain hierarchy which would minimize atomic operations on the
> global variables.
> 
> There are 2 possible ways to implement this:
> 
> 1. Maintain the idle CPUs mask in sched_domain_shared. Also construct a
>     hierarchy of the sched_domain_shared objects which can be used to
>     propagate a signal up to the topmost domain.
> 
>     - Advantages: Distributed tracking. Less atomic operations on the
>       global variables.
> 
>     - Disadvantages: Number of atomic ops can scale with the depth of the
>       hierarchy with multiple cache lines being possibly shared between
>       multiple NUMA domains.
> 
> 2. [Implemented in this series] Maintain the idle CPUs mask in
>     sched_domain_shared. String all the sched_domain_shared objects in a
>     global list which is used for traversing all nohz idle CPUs during
>     load balancing.
> 
>     Maintain a global "nrr_doms" indicator that is only updated when the
>     first CPU is added to the LLC local mask / last CPU leaves the LLC
>     local mask.
> 
>     - Advantages: Distributed tracking. Simpler implementation.
> 
>     - Disadvantages: Number of atomic ops to global "nr_doms" can scale
>       with the number of LLC domains, however the changes in the boundary
>       conditions are still less frequent than the current global scheme.
> 
> The nohz_idle_cpus mask is also inherently optimized by retaining a CPU
> on the mask until the first tick and is not immediately cleared when the
> ticks are enabled again / at idle exit.
> 
> 
> o [EXPERIMENTAL] Push-based load balancing
> 
> Proactively push tasks to idle CPUs within an LLC domain. Push-based
> load balancing is found to be a delicate balancing act where delaying
> running the tasks, especially if their runtime is small, can lead to
> performance regressions.
> 
> There are cases, especially with larger benchmarks where pushing the
> tasks more proactively helps with performance however, a number of
> microbenchmark suffer as a result of additional work the busy CPU has to
> do to to push a preempted task.
> 
> 
> o [EXPERIMENTAL] Optimizing Intra-NUMA newidle balancing
> 
> On a CONFIG_PREEMPTION enabled kernel, newidle balance only pulls one
> task to keep the latency of balancing low. Despite the effort to keep
> the latency low, the newidle balance ends up computing a great deal of
> stats just to pull a single task at best.
> 
> Instead of following the usual path, directly traverse CPUs for newidle
> balance in search of CPUs to pull load from.
> 
> This too is found to have interesting effects on benchmarks where CPUs
> can converge on single target to pull tasks from causing some amount of
> lock contention.
> 
> More interestingly, a number of benchmarks seem to regress if the
> newidle balance yields on spotting (nr_running > 1 || ttwu_pending)
> instead of just proceeding to scan the entire domain and bail at the
> end.
> 
> 
> Benchmark results
> =================
> 
> Results for some variants are incomplete as a result of setup issues
> (and my sheer incompetence to revert some of the changes I made when
> analyzing the benchmarks)
> 
> I'll update these as and when the runs (and re-runs) complete but as the
> moment, this is how the different [EXPERIMENTAL] bits stack up from
> benchmarking perspective on a dual socket 3rd Generation EPYC system (2
> x 64C/128T)
> 
>    ==================================================================
>    Test          : hackbench
>    Units         : Normalized time in seconds
>    Interpretation: Lower is better
>    Statistic     : AMean
>    ==================================================================
>    Case:           tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV) push+newidle[pct imp](CV)
>     1-groups     1.00 [ -0.00]( 5.58)     1.01 [ -1.10](14.77)     1.01 [ -0.66]( 8.80)     1.03 [ -2.85]( 6.13)
>     2-groups     1.00 [ -0.00]( 9.58)     1.02 [ -2.41]( 3.09)     1.00 [  0.22]( 5.62)     1.02 [ -1.97]( 4.54)
>     4-groups     1.00 [ -0.00]( 2.11)     0.99 [  1.48]( 2.30)     1.00 [ -0.21]( 2.60)     1.03 [ -2.54]( 2.82)
>     8-groups     1.00 [ -0.00]( 2.07)     1.02 [ -2.31]( 2.98)     1.15 [-14.79]( 2.15)     1.13 [-12.63]( 2.57)
>    16-groups     1.00 [ -0.00]( 3.55)     1.09 [ -8.57]( 7.80)     1.04 [ -3.64]( 3.89)     1.04 [ -4.33]( 1.36)
> 
> 
>    ==================================================================
>    Test          : tbench
>    Units         : Normalized throughput
>    Interpretation: Higher is better
>    Statistic     : AMean
>    ==================================================================
>    Clients:    tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
>        1     1.00 [  0.00]( 0.29)     1.01 [  0.63]( 0.68)     1.00 [ -0.15]( 0.96)       0.99 [ -1.46]( 0.25)
>        2     1.00 [  0.00]( 0.55)     1.00 [ -0.09]( 0.21)     1.00 [  0.47]( 0.46)       0.99 [ -1.36]( 0.54)
>        4     1.00 [  0.00]( 0.33)     0.99 [ -0.83]( 0.54)     1.01 [  0.76]( 0.36)       0.98 [ -1.51]( 0.20)
>        8     1.00 [  0.00]( 0.75)     1.00 [ -0.42]( 1.14)     1.01 [  0.96]( 0.49)       0.99 [ -0.64]( 0.34)
>       16     1.00 [  0.00]( 0.98)     0.99 [ -0.70]( 1.23)     0.97 [ -2.55]( 0.73)       0.98 [ -1.80]( 1.62)
>       32     1.00 [  0.00]( 0.04)     0.98 [ -2.32]( 1.14)     0.98 [ -1.94]( 0.86)       0.98 [ -2.02]( 0.64)
>       64     1.00 [  0.00]( 1.27)     0.94 [ -5.51]( 3.69)     0.97 [ -3.45]( 1.28)       0.99 [ -1.49]( 1.68)
>      128     1.00 [  0.00]( 0.69)     1.00 [ -0.05]( 2.34)     1.01 [  0.79]( 0.93)       0.99 [ -1.16]( 0.68)
>      256     1.00 [  0.00]( 5.60)     0.97 [ -2.67]( 5.28)     1.00 [  0.34]( 1.23)       0.98 [ -2.16]( 7.10)
>      512     1.00 [  0.00]( 0.90)     1.00 [ -0.38]( 0.86)     1.01 [  0.53]( 0.10)       0.98 [ -1.88]( 0.09)
>     1024     1.00 [  0.00]( 0.25)     0.99 [ -1.01]( 0.37)     1.01 [  0.91]( 0.53)       0.98 [ -1.58]( 0.32)
> 
> 
>    ==================================================================
>    Test          : stream-10
>    Units         : Normalized Bandwidth, MB/s
>    Interpretation: Higher is better
>    Statistic     : HMean
>    ==================================================================
>    Test:       tip[pct imp](CV)      push_only[pct imp](CV)   newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
>     Copy     1.00 [  0.00]( 4.37)     0.97 [ -2.82]( 8.57)     0.99 [ -1.31]( 6.75)       0.97 [ -3.34]( 6.18)
>    Scale     1.00 [  0.00]( 2.75)     0.99 [ -0.73]( 3.62)     0.99 [ -0.86]( 3.73)       0.99 [ -1.49]( 5.39)
>      Add     1.00 [  0.00]( 3.54)     0.98 [ -2.40]( 3.99)     0.98 [ -1.51]( 4.12)       0.97 [ -3.27]( 6.28)
>    Triad     1.00 [  0.00]( 4.41)     0.98 [ -1.71]( 7.00)     1.01 [  0.55]( 3.77)       0.96 [ -4.32]( 7.49)
> 
> 
>    ==================================================================
>    Test          : stream-100
>    Units         : Normalized Bandwidth, MB/s
>    Interpretation: Higher is better
>    Statistic     : HMean
>    ==================================================================
>    Test:       tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
>     Copy     1.00 [  0.00]( 3.25)     0.96 [ -4.08]( 3.07)     0.98 [ -1.56]( 3.45)       0.97 [ -2.74]( 2.00)
>    Scale     1.00 [  0.00]( 1.49)     0.98 [ -2.25]( 4.13)     0.98 [ -1.86]( 4.32)       0.99 [ -1.19]( 1.43)
>      Add     1.00 [  0.00]( 1.75)     1.00 [ -0.47]( 2.17)     1.00 [ -0.14]( 1.31)       0.99 [ -0.81]( 2.26)
>    Triad     1.00 [  0.00]( 1.95)     0.97 [ -2.82]( 4.63)     0.95 [ -4.65]( 6.59)       0.97 [ -2.80]( 4.84)
> 
> 
>    ==================================================================
>    Test          : netperf
>    Units         : Normalized Througput
>    Interpretation: Higher is better
>    Statistic     : AMean
>    ==================================================================
>    Clients:         tip[pct imp](CV)       push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
>     1-clients     1.00 [  0.00]( 0.25)     0.98 [ -1.51]( 0.56)      0.99 [ -1.37]( 0.32)       0.98 [ -1.91]( 0.38)
>     2-clients     1.00 [  0.00]( 0.39)     0.99 [ -1.26]( 1.05)      0.99 [ -0.99]( 0.75)       0.98 [ -2.16]( 0.57)
>     4-clients     1.00 [  0.00]( 0.67)     0.99 [ -0.73]( 0.68)      1.00 [ -0.22]( 0.46)       0.98 [ -1.70]( 0.30)
>     8-clients     1.00 [  0.00]( 0.46)     0.99 [ -1.09]( 0.50)      1.00 [ -0.27]( 0.44)       0.98 [ -1.84]( 0.59)
>    16-clients     1.00 [  0.00]( 0.76)     0.99 [ -0.79]( 0.48)      1.00 [ -0.24]( 1.35)       0.99 [ -1.31]( 0.74)
>    32-clients     1.00 [  0.00]( 0.82)     0.99 [ -0.91]( 0.80)      1.00 [ -0.04]( 1.16)       0.99 [ -1.27]( 0.83)
>    64-clients     1.00 [  0.00]( 1.63)     0.99 [ -0.97]( 1.37)      1.00 [  0.13]( 1.47)       0.99 [ -1.17]( 1.60)
>    128-clients    1.00 [  0.00]( 1.30)     0.99 [ -1.07]( 1.42)      0.99 [ -0.92]( 1.41)       0.98 [ -1.77]( 1.19)
>    256-clients    1.00 [  0.00]( 5.43)     1.02 [  1.53]( 6.74)      1.02 [  1.54]( 3.40)       1.00 [  0.25]( 6.01)
>    512-clients    1.00 [  0.00](55.62)     1.00 [ -0.25](54.85)      0.98 [ -1.91](52.43)       0.98 [ -1.88](51.45)
> 
> 
>    ==================================================================
>    Test          : schbench
>    Units         : Normalized 99th percentile latency in us
>    Interpretation: Lower is better
>    Statistic     : Median
>    ==================================================================
>    #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)    push+newidle[pct imp](CV)
>      1     1.00 [ -0.00]( 2.50)     1.00 [ -0.00](35.19)     0.88 [ 12.50](31.97)         0.95 [  5.00](33.07)
>      2     1.00 [ -0.00]( 8.58)     1.02 [ -2.44]( 6.45)     1.02 [ -2.44]( 9.52)         1.00 [ -0.00]( 2.44)
>      4     1.00 [ -0.00]( 7.36)     1.02 [ -2.22]( 3.30)     0.98 [  2.22]( 8.29)         1.02 [ -2.22](13.95)
>      8     1.00 [ -0.00]( 8.73)     1.10 [ -9.62]( 9.02)     1.06 [ -5.77]( 6.68)         1.04 [ -3.85]( 6.46)
>     16     1.00 [ -0.00]( 4.34)     1.05 [ -4.84]( 4.01)     1.03 [ -3.23]( 1.82)         1.06 [ -6.45]( 4.07)
>     32     1.00 [ -0.00]( 3.27)     1.06 [ -6.19]( 4.01)     0.99 [  1.03]( 2.08)         1.00 [ -0.00]( 2.06)
>     64     1.00 [ -0.00]( 2.05)     1.01 [ -1.02]( 1.27)     1.01 [ -1.02]( 5.11)         0.91 [  9.18]( 6.51)
>    128     1.00 [ -0.00]( 6.08)     0.95 [  5.49]( 4.91)     1.09 [ -8.59]( 8.22)         1.08 [ -7.88](11.81)
>    256     1.00 [ -0.00]( 3.28)     0.94 [  6.24]( 4.22)     1.04 [ -3.72]( 6.18)         1.04 [ -4.10]( 3.62)
>    512     1.00 [ -0.00]( 2.23)     0.98 [  2.29]( 1.92)     0.98 [  1.90]( 6.93)         1.02 [ -1.90]( 1.51)
> 
> 
>    ==================================================================
>    Test          : new-schbench-requests-per-second
>    Units         : Normalized Requests per second
>    Interpretation: Higher is better
>    Statistic     : Median
>    ==================================================================
>    #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
>      1     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.29)     1.00 [  0.00]( 0.14)       0.99 [ -0.56]( 0.91)
>      2     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.14)       1.00 [  0.00]( 0.00)
>      4     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.14)     1.00 [  0.28]( 0.14)       1.00 [  0.28]( 0.14)
>      8     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)       1.00 [  0.00]( 0.00)
>     16     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)       1.00 [  0.00]( 0.00)
>     32     1.00 [  0.00]( 4.75)     1.01 [  1.13]( 0.29)     1.00 [  0.00]( 3.77)       0.99 [ -0.57]( 0.51)
>     64     1.00 [  0.00]( 1.17)     1.01 [  0.69](13.90)     1.00 [  0.00](13.33)       1.01 [  0.69](13.35)
>    128     1.00 [  0.00]( 0.00)     1.00 [  0.34]( 0.18)     1.01 [  0.68]( 0.00)       1.00 [  0.34]( 0.18)
>    256     1.00 [  0.00]( 0.56)     1.00 [ -0.49]( 1.24)     1.00 [  0.25]( 1.47)       1.01 [  0.99]( 1.20)
>    512     1.00 [  0.00]( 0.96)     1.00 [ -0.37]( 0.88)     1.00 [ -0.37]( 1.58)       1.00 [ -0.37]( 0.88)
> 
> 
>    ==================================================================
>    Test          : new-schbench-wakeup-latency
>    Units         : Normalized 99th percentile latency in us
>    Interpretation: Lower is better
>    Statistic     : Median
>    ==================================================================
>    #workers: tip[pct imp](CV)      push_only[pct imp](CV)  newidle_only[pct imp](CV)   push+newidle[pct imp](CV)
>      1     1.00 [ -0.00](24.81)     0.75 [ 25.00](24.12)     0.67 [ 33.33]( 6.74)        0.67 [ 33.33](11.18)
>      2     1.00 [ -0.00]( 4.08)     0.77 [ 23.08]( 9.68)     0.92 [  7.69](21.56)        0.77 [ 23.08]( 8.94)
>      4     1.00 [ -0.00]( 0.00)     1.08 [ -7.69](10.00)     0.85 [ 15.38]( 9.99)        0.85 [ 15.38]( 8.13)
>      8     1.00 [ -0.00](12.91)     1.09 [ -9.09]( 4.43)     0.82 [ 18.18](19.99)        0.82 [ 18.18](23.66)
>     16     1.00 [ -0.00](12.06)     1.18 [-18.18]( 8.37)     1.18 [-18.18](15.10)        1.18 [-18.18](15.10)
>     32     1.00 [ -0.00](22.13)     1.00 [ -0.00]( 5.00)     1.10 [-10.00](19.86)        1.00 [ -0.00]( 5.34)
>     64     1.00 [ -0.00](11.07)     1.00 [ -0.00](16.90)     0.92 [  7.69](15.49)        1.00 [ -0.00](13.62)
>    128     1.00 [ -0.00]( 9.04)     0.98 [  2.48]( 3.01)     0.99 [  1.49]( 6.96)        0.98 [  1.98]( 5.42)
>    256     1.00 [ -0.00]( 0.24)     1.00 [ -0.00]( 0.00)     1.00 [ -0.24]( 0.12)        1.00 [ -0.24]( 0.32)
>    512     1.00 [ -0.00]( 0.34)     1.00 [ -0.00]( 0.40)     1.00 [  0.38]( 0.34)        0.99 [  1.15]( 0.20)
> 
> 
>    ==================================================================
>    Test          : new-schbench-request-latency
>    Units         : Normalized 99th percentile latency in us
>    Interpretation: Lower is better
>    Statistic     : Median
>    ==================================================================
>    #workers: tip[pct imp](CV)      push_only[pct imp](CV)   newidle_only[pct imp](CV)  push+newidle[pct imp](CV)
>      1     1.00 [ -0.00]( 0.90)     0.99 [  0.84]( 1.82)     0.99 [  0.56]( 1.10)        1.03 [ -2.53]( 1.88)
>      2     1.00 [ -0.00]( 0.00)     1.01 [ -0.57]( 0.29)     1.01 [ -0.86]( 0.81)        1.02 [ -2.28]( 1.04)
>      4     1.00 [ -0.00]( 1.02)     0.98 [  1.69]( 0.15)     0.99 [  0.84]( 1.02)        1.01 [ -0.84]( 1.67)
>      8     1.00 [ -0.00]( 0.15)     1.01 [ -0.57]( 0.51)     1.00 [ -0.00]( 0.26)        1.00 [ -0.00]( 0.39)
>     16     1.00 [ -0.00]( 0.53)     1.01 [ -0.57]( 0.64)     1.00 [ -0.29]( 0.39)        1.01 [ -0.86]( 0.81)
>     32     1.00 [ -0.00](35.40)     0.98 [  1.62]( 0.49)     0.99 [  0.81](10.03)        1.00 [ -0.00]( 0.48)
>     64     1.00 [ -0.00]( 5.24)     0.92 [  7.82](26.28)     1.03 [ -2.52]( 6.65)        0.62 [ 38.02](32.78)
>    128     1.00 [ -0.00]( 2.02)     0.99 [  0.75]( 1.40)     1.16 [-16.14]( 2.15)        1.17 [-16.89]( 3.16)
>    256     1.00 [ -0.00]( 3.41)     0.96 [  4.08]( 3.32)     1.07 [ -7.13]( 2.60)        1.10 [ -9.94]( 4.96)
>    512     1.00 [ -0.00]( 1.45)     1.00 [  0.43]( 2.77)     0.99 [  1.06]( 0.73)        0.98 [  1.92]( 0.40)
> 
> 
>    ==================================================================
>    Test          : Various longer running benchmarks
>    Units         : %diff in throughput reported
>    Interpretation: Higher is better
>    Statistic     : Median
>    ==================================================================
>    Benchmarks:                push_only    newidle_only  push+newidle
>    ycsb-cassandra              -3%             -3%          -1%
>    ycsb-mongodb                -2%             -2%          -1%
>    deathstarbench-1x           24%             16%
>    deathstarbench-2x           12%             14%
>    deathstarbench-3x           17%             14%
>    deathstarbench-6x
> 
> 
> LPC 2025
> ========
> 
> Further experiments carried out will be discussed at LPC'25 in the
> "Scheduler and Real-Time MC" between 11:08AM and 11:30AM on 11th
> December, 2025 in Hall B4.
> 
> Discussion points include:
> 
> o "sd->shared" assignment optimization.
> o "nohz.idle_cpus" mask optimization
> o Busy balance CPU rotation.
> o Effective detection of when it is favorable to push tasks.
> o The overheads of maintaining masks (even with optimizations).
> o The delicate dance of newidle balance.
> 
> Please do drop by, or reach out to me directly if this work interests
> you.
> 
> 
> Changelog
> =========
> 
> This series is based on tip:sched/core at commit 3eb593560146 ("Merge
> tag 'v6.18-rc7' into sched/core, to pick up fixes"). All the comparisons
> above are done with the same.
> 
> o rfc v1.. rfc v2
> 
> - Collected tags on Patch 1 from Srikanth (Thanks a ton for the review)
> 
> - Added a for_each_cpu_and_wrap() and cleaned up couple of sites using
>    the newly introduced macro.
> 
> - Simplified conditions that referenced per-CPU "llc_size" and
>    "sd->shared" using the fact that only sd_llc has sd->shared assigned.
> 
> - Merged the two series however, the idea is largely the same. Push
>    based load balancing is guarded behing CONFIG_NO_HZ_COMMON since a
>    bunch of NO_HZ_COMMON specific bits were put behind the config option.
> 
> - Idea of overloaded_mask was dropped since the overhead to maintain
>    the mask (without any usage) was visible in many benchmark results.
> 
> - Idea of shallow_idle_cpus mask was dropped since the overhead to
>    maintain the mask (without any usage) was visible in benchmarks like
>    tbench that left the CPUs idle for very short duration.
> 
> - Added the patch to rotate the "busy_balance_cpu".
> 
> - Renamed "idle_cpus_mask" to "nohz_idle_cpus_mask" in anticipation of
>    adding the "shallow_idle_cpus" mask which didn't pan out.
> 
> 
> Note: Patched marked EXPERIMENTAL may be incomplete from a schedstats
> accounting standpoint.
> 
> ---
> K Prateek Nayak (28):
>    sched/fair: Simplify set_cpu_sd_state_*() with guards
>    sched/fair: Use rq->nohz_tick_stopped in update_nohz_stats()
>    sched/topology: Optimize sd->shared allocation and assignment
>    sched/fair: Simplify the entry condition for update_idle_cpu_scan()
>    sched/fair: Simplity SIS_UTIL handling in select_idle_cpu()
>    cpumask: Introduce for_each_cpu_and_wrap() and bitfield helpers
>    sched/fair: Use for_each_cpu_and_wrap() in select_idle_capacity()
>    sched/fair: Use for_each_cpu_and_wrap() in select_idle_cpu()
>    sched/fair: Rotate the CPU resposible for busy load balancing
>    sched/fair: Use xchg() to set sd->nohz_idle state
>    sched/topology: Attach new hierarchy in rq_attach_root()
>    sched/fair: Fixup sd->nohz_idle state during hotplug / cpuset
>    sched/fair: Account idle cpus instead of busy cpus in sd->shared
>    sched/topology: Introduce fallback sd->shared assignment
>    sched/topology: Introduce percpu sd_nohz for nohz state tracking
>    sched/topology: Introduce "nohz_idle_cpus_mask" in sd->shared
>    sched/topology: Introduce "nohz_shared_list" to keep track of
>      sd->shared
>    sched/fair: Reorder the barrier in nohz_balance_enter_idle()
>    sched/fair: Extract the main _nohz_idle_balance() loop into a helper
>    sched/fair: Convert find_new_ilb() to use nohz_shared_list
>    sched/fair: Introduce sched_asym_prefer_idle() for ILB kick
>    sched/fair: Convert sched_balance_nohz_idle() to use nohz_shared_list
>    sched/fair: Remove "nohz.idle_cpus_mask"
>    sched/fair: Optimize global "nohz.nr_cpus" tracking
>    sched/topology: Add basic debug information for "nohz_shared_list"
>    [EXPERIMENTAL] sched/fair: Proactive idle balance using push mechanism
>    [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push
>    [EXPERIMENTAL] sched/fair: Faster alternate for intra-NUMA newidle
>      balance
> 
> Vincent Guittot (1):
>    [EXPERIMENTAL] sched/fair: Add push task framework
> 
>   include/linux/cpumask.h        |  20 +
>   include/linux/find.h           |  37 ++
>   include/linux/sched/topology.h |  18 +-
>   kernel/sched/core.c            |   4 +-
>   kernel/sched/fair.c            | 828 ++++++++++++++++++++++++++-------
>   kernel/sched/sched.h           |  10 +-
>   kernel/sched/topology.c        | 386 +++++++++++++--
>   7 files changed, 1076 insertions(+), 227 deletions(-)
> 
> 
> base-commit: 3eb59356014674fa1b506a122cc59b57089a4d08

Re: [RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push

[K Prateek Nayak]

Hello Chris,

On 12/8/2025 6:03 PM, Christian Loehle wrote:
> Just to confirm, but this patch is included when the cover letter mentions "push" for the
> benchmarks?

Yes, this patch is included.

> Did this help the regressions then?

So without this, I was just using tbench as a smoke test - server client
pair sending a very small amount of data and can lead to very short sleep
time.

Up till 64 client there were slight improvements from not rate limiting
but once I hit the fully loaded case, tbench regresses by up to 10%
mostly because of lack of idle targets but also the CPU doesn't hit the
overutilized threshold to cancel push attempts.

CPUs are still considered "nohz" until the first tick hits and at a high
frequency of CPUs going in and out of idle, "sd->shared->nr_idle_cpus"
turned unreliable in my case as a bailout threshold,

With this rate limiting, things are within 2-3% of the baseline.

-- 
Thanks and Regards,
Prateek

Re: [RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing

[K Prateek Nayak]

Hello Shrikanth,

On 12/8/2025 7:34 PM, Shrikanth Hegde wrote:
>> 2. The "nohz.nr_idle" and "nohz.idle_cpus" are global system-wide
>>     variables that can run into scalability bottlenecks on a large
>>     core-count system.
>>
> 
> I think they are nohz.nr_cpus and nohz.idle_cpus_mask. isn't it?

Ack! Sorry my brain is all mush at this point staring at all the new
and old "nohz.*" variable names. Thank you for catching that.

-- 
Thanks and Regards,
Prateek

Re: [RESEND RFC PATCH v2 26/29] [EXPERIMENTAL] sched/fair: Add push task framework

[kernel test robot]

Hi Prateek,

[This is a private test report for your RFC patch.]
kernel test robot noticed the following build errors:

[auto build test ERROR on 3eb59356014674fa1b506a122cc59b57089a4d08]

url:    https://github.com/intel-lab-lkp/linux/commits/K-Prateek-Nayak/sched-fair-Simplify-set_cpu_sd_state_-with-guards/20251208-183121
base:   3eb59356014674fa1b506a122cc59b57089a4d08
patch link:    https://lore.kernel.org/r/20251208092744.32737-26-kprateek.nayak%40amd.com
patch subject: [RESEND RFC PATCH v2 26/29] [EXPERIMENTAL] sched/fair: Add push task framework
config: nios2-randconfig-r072-20251210 (https://download.01.org/0day-ci/archive/20251210/202512101615.0IPukQ21-lkp@intel.com/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251210/202512101615.0IPukQ21-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/202512101615.0IPukQ21-lkp@intel.com/

All errors (new ones prefixed by >>):

   kernel/sched/fair.c: In function 'has_pushable_tasks':
>> kernel/sched/fair.c:13079:42: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13079 |         return !plist_head_empty(&rq->cfs.pushable_tasks);
         |                                          ^
   kernel/sched/fair.c: In function 'fair_remove_pushable_task':
   kernel/sched/fair.c:13109:47: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13109 |         plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
         |                                               ^
   kernel/sched/fair.c: In function 'fair_add_pushable_task':
   kernel/sched/fair.c:13115:55: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13115 |                 plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
         |                                                       ^
   kernel/sched/fair.c:13118:55: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13118 |                 plist_add(&p->pushable_tasks, &rq->cfs.pushable_tasks);
         |                                                       ^
   kernel/sched/fair.c: In function 'init_cfs_rq':
   kernel/sched/fair.c:13886:32: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13886 |         plist_head_init(&cfs_rq->pushable_tasks);
         |                                ^~
   kernel/sched/fair.c: In function 'has_pushable_tasks':
   kernel/sched/fair.c:13080:1: warning: control reaches end of non-void function [-Wreturn-type]
   13080 | }
         | ^


vim +13079 kernel/sched/fair.c

 13076	
 13077	static inline int has_pushable_tasks(struct rq *rq)
 13078	{
 13079		return !plist_head_empty(&rq->cfs.pushable_tasks);
 13080	}
 13081	

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

Re: [RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push

[kernel test robot]

Hi Prateek,

[This is a private test report for your RFC patch.]
kernel test robot noticed the following build errors:

[auto build test ERROR on 3eb59356014674fa1b506a122cc59b57089a4d08]

url:    https://github.com/intel-lab-lkp/linux/commits/K-Prateek-Nayak/sched-fair-Simplify-set_cpu_sd_state_-with-guards/20251208-183121
base:   3eb59356014674fa1b506a122cc59b57089a4d08
patch link:    https://lore.kernel.org/r/20251208092744.32737-28-kprateek.nayak%40amd.com
patch subject: [RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push
config: nios2-randconfig-r072-20251210 (https://download.01.org/0day-ci/archive/20251210/202512101753.617JFKKE-lkp@intel.com/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251210/202512101753.617JFKKE-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/202512101753.617JFKKE-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from include/linux/bitops.h:7,
                    from include/linux/kernel.h:23,
                    from include/linux/cpumask.h:11,
                    from include/linux/energy_model.h:4,
                    from kernel/sched/fair.c:23:
   kernel/sched/fair.c: In function 'sched_balance_domains':
>> kernel/sched/fair.c:12363:46: error: 'struct sched_domain' has no member named 'last_nr_push_update'
   12363 |                     time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
         |                                              ^~
   include/linux/typecheck.h:11:16: note: in definition of macro 'typecheck'
      11 |         typeof(x) __dummy2; \
         |                ^
   kernel/sched/fair.c:12363:21: note: in expansion of macro 'time_after_eq'
   12363 |                     time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
         |                     ^~~~~~~~~~~~~
   include/linux/typecheck.h:12:25: warning: comparison of distinct pointer types lacks a cast
      12 |         (void)(&__dummy == &__dummy2); \
         |                         ^~
   include/linux/jiffies.h:149:10: note: in expansion of macro 'typecheck'
     149 |          typecheck(unsigned long, b) && \
         |          ^~~~~~~~~
   kernel/sched/fair.c:12363:21: note: in expansion of macro 'time_after_eq'
   12363 |                     time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
         |                     ^~~~~~~~~~~~~
   In file included from include/linux/ktime.h:25,
                    from include/linux/timer.h:6,
                    from include/linux/uprobes.h:18,
                    from include/linux/mm_types.h:16,
                    from include/linux/mmzone.h:22,
                    from include/linux/gfp.h:7,
                    from include/linux/xarray.h:16,
                    from include/linux/radix-tree.h:21,
                    from include/linux/idr.h:15,
                    from include/linux/kernfs.h:12,
                    from include/linux/sysfs.h:16,
                    from include/linux/kobject.h:20,
                    from include/linux/device.h:18,
                    from include/linux/energy_model.h:5,
                    from kernel/sched/fair.c:23:
>> kernel/sched/fair.c:12363:46: error: 'struct sched_domain' has no member named 'last_nr_push_update'
   12363 |                     time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
         |                                              ^~
   include/linux/jiffies.h:150:25: note: in definition of macro 'time_after_eq'
     150 |          ((long)((a) - (b)) >= 0))
         |                         ^
>> kernel/sched/fair.c:12364:27: error: 'struct sched_domain' has no member named 'nr_push_attempt'
   12364 |                         sd->nr_push_attempt = READ_ONCE(sd->shared->nr_idle_scan);
         |                           ^~
   kernel/sched/fair.c:12365:27: error: 'struct sched_domain' has no member named 'last_nr_push_update'
   12365 |                         sd->last_nr_push_update = jiffies;
         |                           ^~
   kernel/sched/fair.c: In function 'has_pushable_tasks':
   kernel/sched/fair.c:13089:42: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13089 |         return !plist_head_empty(&rq->cfs.pushable_tasks);
         |                                          ^
   In file included from include/linux/kernel.h:22,
                    from include/linux/cpumask.h:11,
                    from include/linux/energy_model.h:4,
                    from kernel/sched/fair.c:23:
   kernel/sched/fair.c: In function 'pick_next_pushable_fair_task':
   kernel/sched/fair.c:13099:39: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |                                       ^
   include/linux/container_of.h:20:33: note: in definition of macro 'container_of'
      20 |         void *__mptr = (void *)(ptr);                                   \
         |                                 ^~~
   kernel/sched/fair.c:13099:13: note: in expansion of macro 'plist_first_entry'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |             ^~~~~~~~~~~~~~~~~
   In file included from include/linux/container_of.h:5,
                    from include/linux/kernel.h:22,
                    from include/linux/cpumask.h:11,
                    from include/linux/energy_model.h:4,
                    from kernel/sched/fair.c:23:
   kernel/sched/fair.c:13099:39: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |                                       ^
   include/linux/build_bug.h:78:56: note: in definition of macro '__static_assert'
      78 | #define __static_assert(expr, msg, ...) _Static_assert(expr, msg)
         |                                                        ^~~~
   include/linux/container_of.h:21:9: note: in expansion of macro 'static_assert'
      21 |         static_assert(__same_type(*(ptr), ((type *)0)->member) ||       \
         |         ^~~~~~~~~~~~~
   include/linux/container_of.h:21:23: note: in expansion of macro '__same_type'
      21 |         static_assert(__same_type(*(ptr), ((type *)0)->member) ||       \
         |                       ^~~~~~~~~~~
   include/linux/plist.h:233:9: note: in expansion of macro 'container_of'
     233 |         container_of(plist_first(head), type, member)
         |         ^~~~~~~~~~~~
   kernel/sched/fair.c:13099:13: note: in expansion of macro 'plist_first_entry'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |             ^~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:13099:39: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |                                       ^
   include/linux/build_bug.h:78:56: note: in definition of macro '__static_assert'
      78 | #define __static_assert(expr, msg, ...) _Static_assert(expr, msg)
         |                                                        ^~~~
   include/linux/container_of.h:21:9: note: in expansion of macro 'static_assert'
      21 |         static_assert(__same_type(*(ptr), ((type *)0)->member) ||       \
         |         ^~~~~~~~~~~~~
   include/linux/container_of.h:22:23: note: in expansion of macro '__same_type'
      22 |                       __same_type(*(ptr), void),                        \
         |                       ^~~~~~~~~~~
   include/linux/plist.h:233:9: note: in expansion of macro 'container_of'
     233 |         container_of(plist_first(head), type, member)
         |         ^~~~~~~~~~~~
   kernel/sched/fair.c:13099:13: note: in expansion of macro 'plist_first_entry'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |             ^~~~~~~~~~~~~~~~~
   include/linux/compiler_types.h:537:27: error: expression in static assertion is not an integer
     537 | #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
         |                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
   include/linux/build_bug.h:78:56: note: in definition of macro '__static_assert'
      78 | #define __static_assert(expr, msg, ...) _Static_assert(expr, msg)
         |                                                        ^~~~
   include/linux/container_of.h:21:9: note: in expansion of macro 'static_assert'
      21 |         static_assert(__same_type(*(ptr), ((type *)0)->member) ||       \
         |         ^~~~~~~~~~~~~
   include/linux/container_of.h:21:23: note: in expansion of macro '__same_type'
      21 |         static_assert(__same_type(*(ptr), ((type *)0)->member) ||       \
         |                       ^~~~~~~~~~~
   include/linux/plist.h:233:9: note: in expansion of macro 'container_of'
     233 |         container_of(plist_first(head), type, member)
         |         ^~~~~~~~~~~~
   kernel/sched/fair.c:13099:13: note: in expansion of macro 'plist_first_entry'
   13099 |         p = plist_first_entry(&rq->cfs.pushable_tasks,
         |             ^~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:13112:47: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13112 |         plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
         |                                               ^
   kernel/sched/fair.c: In function 'should_push_tasks':
   kernel/sched/fair.c:13138:39: error: 'struct sched_domain' has no member named 'nr_push_attempt'
   13138 |         if (sched_feat(SIS_UTIL) && sd->nr_push_attempt <= 0)
         |                                       ^~
   kernel/sched/fair.c: In function 'push_fair_task':
   kernel/sched/fair.c:13196:11: error: 'struct sched_domain' has no member named 'nr_push_attempt'
   13196 |         sd->nr_push_attempt--;
         |           ^~
   kernel/sched/fair.c:13160:37: warning: unused variable 'sds' [-Wunused-variable]
   13160 |         struct sched_domain_shared *sds;
         |                                     ^~~
   kernel/sched/fair.c: In function 'fair_remove_pushable_task':
   kernel/sched/fair.c:13219:47: error: 'struct cfs_rq' has no member named 'pushable_tasks'
   13219 |         plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
         |                                               ^


vim +12363 kernel/sched/fair.c

 12292	
 12293	/*
 12294	 * It checks each scheduling domain to see if it is due to be balanced,
 12295	 * and initiates a balancing operation if so.
 12296	 *
 12297	 * Balancing parameters are set up in init_sched_domains.
 12298	 */
 12299	static void sched_balance_domains(struct rq *rq, enum cpu_idle_type idle)
 12300	{
 12301		int continue_balancing = 1;
 12302		int cpu = rq->cpu;
 12303		int busy = idle != CPU_IDLE && !sched_idle_cpu(cpu);
 12304		unsigned long interval;
 12305		struct sched_domain *sd;
 12306		/* Earliest time when we have to do rebalance again */
 12307		unsigned long next_balance = jiffies + 60*HZ;
 12308		int update_next_balance = 0;
 12309		int need_decay = 0;
 12310		u64 max_cost = 0;
 12311	
 12312		rcu_read_lock();
 12313		for_each_domain(cpu, sd) {
 12314			/*
 12315			 * Decay the newidle max times here because this is a regular
 12316			 * visit to all the domains.
 12317			 */
 12318			need_decay = update_newidle_cost(sd, 0, 0);
 12319			max_cost += sd->max_newidle_lb_cost;
 12320	
 12321			/*
 12322			 * Stop the load balance at this level. There is another
 12323			 * CPU in our sched group which is doing load balancing more
 12324			 * actively.
 12325			 */
 12326			if (!continue_balancing) {
 12327				if (need_decay)
 12328					continue;
 12329				break;
 12330			}
 12331	
 12332			interval = get_sd_balance_interval(sd, busy);
 12333			if (time_after_eq(jiffies, sd->last_balance + interval)) {
 12334				if (sched_balance_rq(cpu, rq, sd, idle, &continue_balancing)) {
 12335					/*
 12336					 * The LBF_DST_PINNED logic could have changed
 12337					 * env->dst_cpu, so we can't know our idle
 12338					 * state even if we migrated tasks. Update it.
 12339					 */
 12340					idle = idle_cpu(cpu);
 12341					busy = !idle && !sched_idle_cpu(cpu);
 12342				}
 12343				sd->last_balance = jiffies;
 12344				interval = get_sd_balance_interval(sd, busy);
 12345			}
 12346			if (time_after(next_balance, sd->last_balance + interval)) {
 12347				next_balance = sd->last_balance + interval;
 12348				update_next_balance = 1;
 12349			}
 12350		}
 12351		if (need_decay) {
 12352			/*
 12353			 * Ensure the rq-wide value also decays but keep it at a
 12354			 * reasonable floor to avoid funnies with rq->avg_idle.
 12355			 */
 12356			rq->max_idle_balance_cost =
 12357				max((u64)sysctl_sched_migration_cost, max_cost);
 12358		}
 12359		if (sched_feat(SIS_UTIL)) {
 12360			sd = rcu_dereference(per_cpu(sd_llc, cpu));
 12361	
 12362			if (sd && sd->shared &&
 12363			    time_after_eq(jiffies, sd->last_nr_push_update + sd->min_interval)) {
 12364				sd->nr_push_attempt = READ_ONCE(sd->shared->nr_idle_scan);
 12365				sd->last_nr_push_update = jiffies;
 12366			}
 12367		}
 12368	
 12369		rcu_read_unlock();
 12370	
 12371		/*
 12372		 * next_balance will be updated only when there is a need.
 12373		 * When the cpu is attached to null domain for ex, it will not be
 12374		 * updated.
 12375		 */
 12376		if (likely(update_next_balance))
 12377			rq->next_balance = next_balance;
 12378	

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

Re: [RESEND RFC PATCH v2 06/29] cpumask: Introduce for_each_cpu_and_wrap() and bitfield helpers

[Yury Norov]

On Mon, Dec 08, 2025 at 09:26:52AM +0000, K Prateek Nayak wrote:
> There is a developing pattern of using cpumask_and() followed by
> for_each_cpu_wrap() in the scheduler.
> 
> To avoid a temporary variable and needlessly iterating over the cpumask
> twice - once for the cpumask_and() operation and the second in the
> for_each_cpu_wrap() loop - introduce a new for_each_cpu_and_wrap()
> helper to iterate over the common bits set on two bitfields starting at
> a specific position without needing an intermediate cpumask variable.
> 
> Cc: Yury Norov <yury.norov@gmail.com>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
> ---
>  include/linux/cpumask.h | 20 ++++++++++++++++++++
>  include/linux/find.h    | 37 +++++++++++++++++++++++++++++++++++++
>  2 files changed, 57 insertions(+)
> 
> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index ff8f41ab7ce6..b7a984c2a7d5 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h
> @@ -406,6 +406,26 @@ unsigned int cpumask_random(const struct cpumask *src)
>  #define for_each_cpu_and(cpu, mask1, mask2)				\
>  	for_each_and_bit(cpu, cpumask_bits(mask1), cpumask_bits(mask2), small_cpumask_bits)
>  
> +/**
> + * for_each_cpu_wrap - iterate over every cpu in both masks, starting at a

for_each_cpu_and_wrap

With that,

Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

> + * specified location.
> + * @cpu: the (optionally unsigned) integer iterator
> + * @mask1: the first cpumask pointer
> + * @mask2: the second cpumask pointer
> + * @start: the start location
> + *
> + * This saves a temporary CPU mask in many places.  It is equivalent to:
> + *	struct cpumask tmp;
> + *	cpumask_and(&tmp, &mask1, &mask2);
> + *	for_each_cpu_wrap(cpu, &tmp, start)
> + *		...
> + *
> + * After the loop, cpu is >= nr_cpu_ids.
> + */
> +#define for_each_cpu_and_wrap(cpu, mask1, mask2, start)				\
> +	for_each_and_bit_wrap(cpu, cpumask_bits(mask1), cpumask_bits(mask2),	\
> +			      small_cpumask_bits, start)
> +
>  /**
>   * for_each_cpu_andnot - iterate over every cpu present in one mask, excluding
>   *			 those present in another.
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 9d720ad92bc1..fff9e2d55e4d 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -487,6 +487,29 @@ unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size,
>  	return bit < start ? bit : size;
>  }
>  
> +/* Helper for for_each_and_bit_wrap(). */
> +static __always_inline
> +unsigned long __for_each_and_wrap(const unsigned long *bitmap1, const unsigned long *bitmap2,
> +				  unsigned long size, unsigned long start, unsigned long n)
> +{
> +	unsigned long bit;
> +
> +	/* If not wrapped around */
> +	if (n > start) {
> +		/* and have a bit, just return it. */
> +		bit = find_next_and_bit(bitmap1, bitmap2, size, n);
> +		if (bit < size)
> +			return bit;
> +
> +		/* Otherwise, wrap around and ... */
> +		n = 0;
> +	}
> +
> +	/* Search the other part. */
> +	bit = find_next_and_bit(bitmap1, bitmap2, start, n);
> +	return bit < start ? bit : size;
> +}
> +
>  /**
>   * find_next_clump8 - find next 8-bit clump with set bits in a memory region
>   * @clump: location to store copy of found clump
> @@ -682,6 +705,20 @@ unsigned long find_next_bit_le(const void *addr, unsigned
>  	     (bit) < (size);							\
>  	     (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1))
>  
> +/**
> + * for_each_and_bit_wrap - iterate over all set bits in (*addr1 & *addr2)
> + * starting from @start, and wrapping around the end of bitmap.
> + * @bit: offset for current iteration
> + * @addr1: address of first bitmap
> + * @addr2: address of second bitmask to and with the first
> + * @size: bitmap size in number of bits
> + * @start: Starting bit for bitmap traversing, wrapping around the bitmap end
> + */
> +#define for_each_and_bit_wrap(bit, addr1, addr2, size, start) \
> +	for ((bit) = find_next_and_bit_wrap((addr1), (addr2), (size), (start));		\
> +	     (bit) < (size);								\
> +	     (bit) = __for_each_and_wrap((addr1), (addr2), (size), (start), (bit) + 1))
> +
>  /**
>   * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
>   * @start: bit offset to start search and to store the current iteration offset
> -- 
> 2.43.0