Re: : [PATCH v8 1/2] sched/cache: Reduce the overhead of task_cache_work by only scan the visisted cpus

[Tim Chen]

On Thu, 2026-07-30 at 21:40 +0800, Luo Gengkun wrote:
> 
> On 2026/7/30 10:22, Tim Chen wrote:
> > On Wed, 2026-07-29 at 11:29 -0700, Tim Chen wrote:
> > > On Wed, 2026-07-29 at 17:19 +0800, Luo Gengkun wrote:
> > > > 
> > > > On 2026/7/28 20:08, Chen Yu wrote:
> > > > > On Tue, Jul 28, 2026 at 04:53:59PM +0800, Luo Gengkun wrote:
> > > > > > 
> > > > > > On 2026/7/27 9:09, Chen, Yu C wrote:
> > > > > > > On 7/23/2026 12:04 PM, Luo Gengkun wrote:
> > > > > > > 
> > > > > > > [ ... ]
> > > > > > > 
> > > > > > > >         guard(raw_spinlock_irqsave)(&rq->cpu_epoch_lock);
> > > > > > > >         __update_mm_sched(rq, pcpu_sched);
> > > > > > > > +    /* Skip the rq that has not been hit for a long time */
> > > > > > > > +    if ((rq->cpu_epoch - pcpu_sched->epoch_last_visit) > llc_epoch_affinity_timeout) {
> > > > > > > 
> > > > > > > In v2 there is a check if the cpu has been set before writing:
> > > > > > > cpumask_test_cpu(cpu_of(rq), &mm->sc_stat.visited_cpus)
> > > > > > > https://lore.kernel.org/all/20260414150745.225416-1-luogengkun2@xxxxxxxxxx/
> > > > > > > do we need to bring that back?
> > > > > > > 
> > > > > > I don't think we need it back. Here is why:
> > > > > > 
> > > > > > In v2, for_each_cpu was used instead of for_each_cpu_and in the inner loop,
> > > > > > meaning some CPUs being checked might not have been set. Therefore,
> > > > > > cpumask_test_cpu was necessary to filter out those cases.
> > > > > > 
> > > > > > Now, with for_each_cpu_and(i, sched_domain_span(sd), &mm->sc_stat.visited_cpus),
> > > > > > we can ensure each scanned CPU is set, so the issue no longer exists.
> > > > > > Furthermore, the only place where the visited_cpus bits are cleared is
> > > > > > task_cache_work(), which is only called once per scan period, there is no
> > > > > > risk of the bit being cleared concurrently mid-loop.
> > > > > > 
> > > > > 
> > > > > Make sense.
> > > > >    
> > > > > > However, is there a possibility that the current task_cache_work() execution
> > > > > > hasn't finished yet when the next scan window arrives? For instance, if the
> > > > > > current task work is heavily delayed or preempted by unexpected interrupt,
> > > > > > jiffies could advance past next_scan before the loop completes.
> > > > > > If we move the `work->next = work;` to the very end of task_cache_work(),
> > > > > > would that resolve this issue? By doing so, the existing `work->next == work`
> > > > > > check in task_tick_cache() should fail and no new task work will be submitted.
> > > > > > 
> > > > > > Please let me know if I'm missing something.
> > > > > > 
> > > > > 
> > > > > There are two layers of protection: first a cheap timeout gate (time_before)
> > > > > that skips scanning until the next period, and then a try_cmpxchg that atomically
> > > > > picks a single winner among the threads that pass the timeout — this actually
> > > > > guarantees only one scanner per mm at a time, no?
> > > > 
> > > > What I am worried about is the following scenario:
> > > > 
> > > > Thread A (CPU 0)                             Thread B (CPU 1)
> > > > ================                             ================
> > > > task_cache_work()
> > > >     |
> > > >     +-> try_cmpxchg() == true
> > > >     |   (Sets next_scan = now + 10)
> > > >     |
> > > >     +-> Enters Scanning Loop (jiffies = 100)
> > > >     |   [ Delayed / Preempted ]
> > > >     |   jiffies advances 100 -> 115.
> > > >     |   Thread A STILL in the loop!
> > > >     |                                          task_cache_work() (jiffies = 115)
> > > > 
> > > >     |                                            |
> > > >     |                                            +-> next_scan == 110 (pass timeout check)
> > > > 
> > > >     |                                            |
> > > >     |                                            +-> try_cmpxchg() == true
> > > > 
> > > >     |                                            |   (Sets next_scan = 115 + 10)
> > > >     |                                            |
> > > > 
> > > > In other words, concurrent execution of task_cache_work() from two adjacent periods can
> > > > occur under extreme conditions; do we need to take this scenario into consideration?
> > > > 
> > > > Perhaps we need an explicit state flag (e.g., using test_and_set_bit) to ensure
> > > > that the previous task_cache_work() execution has fully completed before allowing
> > > > a new thread to proceed, regardless of whether the next scan window has arrived.
> > > > What do you think?
> > > 
> > > First, the EPOCH_PERIOD is fairly long (10 msec) so it is unlikely that Thread A
> > > hasn't completed its work.
> > > 
> > > Second, suppose the above scenario happened, the two thread above
> > > are serialized in the work on updating occupancy
> > > and visited cpus under the cpus_read_lock when looping through the cpus
> > > in task_cache_work().
> > > 
> > > So I think we should be okay without an explicit state flag.
> > > 
> > > That said, I think we should use mm->sc_stat.lock instead of cpus_read_lock
> > > in task_cache_work()'s cpu loop. That will improve scalability.
> > 
> > It slipped my mind the cpus_read_lock is read lock, so the two
> > threads could indeed go in parallel.
> > 
> > But the update on each cpu is protected by rq->cpu_epoch_lock, and
> > epochs don't go backwards. So we should still get consistent updates on
> > epochs and occupancy stats.
> > 
> > Tim
> 
> When talking about mm->sc_stat.lock, I found an issue that may be
> worth paying attention. Below is the relevant code snippet:
> 
> task_tick_cache()
> {
> 	...
>          /* avoid moving backwards */
>          if (time_after_eq(mm->sc_stat.epoch, epoch))
>                  return;
> 				
>          guard(raw_spinlock)(&mm->sc_stat.lock);
> 
>          if (work->next == work) {
>                  task_work_add(p, work, TWA_RESUME);
>                  WRITE_ONCE(mm->sc_stat.epoch, epoch);
>          }
> 	..
> }
> Actually, I don't think time_after_eq() can effectively avoid moving
> backwards because this check is performed entirely outside the
> protection of the spinlock. The following sequence diagram describes
> this race condition in detail:
> 
>       Thread A (CPU 0)                             Thread B (CPU 1)
>       ============================                 ============================
>       [ Initial State: mm->sc_stat.epoch = 90 ]
>      
>       task_tick_cache()                            task_tick_cache()
>      
>         |                                            |
>         +-> Read rq->cpu_epoch = 100                 +-> Read rq->cpu_epoch = 101
>      
>         |                                            |
>         +-> Lockless Check (90, 100) -> PASS         +-> Lockless Check (90, 101) -> PASS
>      
>         |                                            |
>         |                                            +-> Acquires lock first
>         |                                            +-> Writes mm->sc_stat.epoch = 101
>         |                                            +-> Releases lock
>         |                                                [ mm->sc_stat.epoch is now 101 ]
>         |
>         +-> Acquires lock
>         |
>         +-> work->next == work (STILL TRUE!
>         |   Because cache_work is per-thread, Thread B's
>         |   submission cannot clear Thread A's local state)
>         |
>         +-> WRITE_ONCE(mm->sc_stat.epoch, 100) !!! <-- BUG: Epoch moves backwards!


That would not happen because in __update_mm_sched(), Thread A will be
reading the updated rq->cpu_epoch and again check
whether time is moving backwards and will skip the update if
that's the case.


>         |
> 
> The solution is straightforward: we should validate the epoch sequence
> under the protection of the lock.
> 

You do not want to acquire the lock before the time check.  As account_mm_sched()
will happen very often and you will to skip those unnecessary lock acquisitions
when rq epoch is not yet due for an update.

Thanks.

Tim

> Furthermore, we should use a trylock here instead of a blocking spinlock
> to eliminate busy-waiting in the sensitive timer tick path. Since the
> lock being held implies that another thread is already submitting the
> cache work, it is safe to skip this tick and return immediately if the
> trylock fails.
> 
> Below is output from lock stat:
> 
> lock_stat version 0.4
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>                                class name    con-bounces    contentions   waittime-min   waittime-max waittime-total   waittime-avg    acq-bounces   acquisitions   holdtime-min   holdtime-max holdtime-total   holdtime-avg
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>                         &mm->sc_stat.lock:        122711         122883           0.12         136.54     1493110.82          12.15         152643         167402           0.12          12.87       99842.76           0.60
> 
> 
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1763,15 +1763,23 @@ static void task_tick_cache(struct rq *rq, struct task_struct *p)
>                  return;
>   
>          epoch = rq->cpu_epoch;
> -       /* avoid moving backwards */
> -       if (time_after_eq(mm->sc_stat.epoch, epoch))
> -               return;
>   
> -       guard(raw_spinlock)(&mm->sc_stat.lock);
> +       /*
> +        * Use trylock instead of a blocking lock to avoid spinning in the
> +        * sensitive timer tick/scheduler path. If the lock is contended,
> +        * which mean another thread is submitting the work. In this case
> +        * skip this tick to reduce redundant cache_work submissions within
> +        * the same epoch.
> +        */
> +       scoped_cond_guard(raw_spinlock_try, return, &mm->sc_stat.lock) {
> +               /* avoid moving backwards */
> +               if (time_after_eq(mm->sc_stat.epoch, epoch))
> +                       return;
>   
> -       if (work->next == work) {
> -               task_work_add(p, work, TWA_RESUME);
> -               WRITE_ONCE(mm->sc_stat.epoch, epoch);
> +               if (work->next == work) {
> +                       task_work_add(p, work, TWA_RESUME);
> +                       WRITE_ONCE(mm->sc_stat.epoch, epoch);
> +               }
>          }
>   }
> 
> The above code prevents the epoch from moving backward and
> reduces lock contention.
> 
> What do you think?
> 
> thanks,
> Gengkun
> 
> >