Linux scheduler sync

sched discussion

[PATCH v8 0/2] Cache aware scheduling: Reduce the overhead of task_cache_work

其它重要分析 success2026/07/31 16:3115 封邮件3 个 patch
0/15 已展开

LLM 分析

sched/cache：基于访问记录的 task_cache_work 扫描瘦身

系列概况

  • 标题：[PATCH v8 0/2] Cache aware scheduling: Reduce the overhead of task_cache_work
  • 作者：Luo Gengkun luogengkun2@huawei.com
  • 版本：v8（共 2 个 patch，1/2 为真实改动，2/2 为标注 "-- DO NOT APPLY!!!" 的 debug 扩展）
  • 规模：2 patches；主 patch（1/2）改 3 个文件、+46/-56；debug patch（2/2）改 3 个文件、+91/-5
  • 修改文件：include/linux/mm_types.h、include/linux/sched.h、kernel/sched/fair.c、include/trace/events/sched.h、kernel/sched/features.h
  • 代码统计：主 patch 净 +46/-56；debug patch 净 +91/-5
  • Message-ID：<20260723040429.630176-1-luogengkun2@huawei.com>
  • 完整性：线程包含 cover letter、1/2 主 patch、2/2 debug patch，以及 12 封 reviewer 往返（Chen Yu、Tim Chen 与作者），讨论集中在 visited_cpus 的置位/清位 race、task_cache_work() 跨期重叠、mm->sc_stat.epoch 的 lockless 检查，以及 hackbench 复测结果

补丁目的

task_cache_work() 目前为了找出进程的 preferred LLC，会扫描很大一片 CPU 集合。在多 NUMA 大机器上，这些扫描绝大多数落在"这个 mm 根本没跑过"的 CPU 上，纯属浪费：perf top 中 task_cache_work 占到 0.81% 的内核周期，Redis 多实例场景 p99 延迟相对 baseline 恶化 25.68%。

本系列为每个 mm_struct 维护一张 visited_cpus cpumask，精确记录"近期真正运行过该 mm 的 CPU"，扫描时只遍历这些位，并用 epoch 超时把长期不再访问的位淘汰掉。

效果：扫描 CPU 数从 384 降到 14~16，task_cache_work 开销降到 0.02%，p99 延迟相对 baseline 的劣化从 -25.68% 收敛到 -1.14%（NUMA balancing 关闭时）。

旧流程的问题

旧实现在 task_cache_work() 开头调用 get_scan_cpumasks()：

  1. 在 CONFIG_NUMA_BALANCING 且 static key 打开时，把 task 的 numa_preferred_nid、进程当前 preferred LLC 所在 node、当前运行 node 三者的 node mask 全部 OR 起来。
  2. 否则直接 cpumask_copy(cpus, cpu_online_mask)——整机全扫。

问题在于：

  • 粒度太粗。一个 node 动辄上百个 CPU，其中真正跑过该 mm 的可能只有十几个，其余全是空转的 fraction_mm_sched() 调用，每次还要拿 rq->cpu_epoch_lock。
  • numa_preferred_nid 是 per-task 的，同一进程不同线程可能指向不同 node，导致进程级 preferred LLC 在节点间来回跳；代码里靠"再 OR 一个当前 node"来兜底，注释自己都写着这是 workaround、TBD。

新流程

引入 mm->sc_stat.visited_cpus（cpumask_var_t，随 mm_alloc_sched() 动态分配、mm_destroy_sched() 释放）与 per-CPU 的 epoch_last_visit：

  • 置位路径：account_mm_sched() 在记账时刷新 pcpu_sched->epoch_last_visit = epoch，并在该 CPU 尚未置位时 cpumask_set_cpu()。
  • 清位路径：fraction_mm_sched(cpu, mm) 先 __update_mm_sched()，再判断 rq->cpu_epoch - epoch_last_visit > llc_epoch_affinity_timeout；超时则清掉该位并返回 0，跳过后续占用率计算。
  • 扫描路径：task_cache_work() 用 cpumask_and(cpus, cpu_online_mask, visited_cpus) 得到外层 node 遍历集合，内层改成 for_each_cpu_and(i, sched_domain_span(sd), mm->sc_stat.visited_cpus)，只走"LLC 域 ∩ 最近访问过"的交集。
  • get_scan_cpumasks() 因此整体删除——visited_cpus 本身就是精确答案，不再需要 NUMA node 启发式。

Patch 概览

  • 1/2 sched/cache: Reduce the overhead of task_cache_work by only scan the visisted cpus：核心实现。新增 visited_cpus 与 epoch_last_visit，改造 fraction_mm_sched() 签名为 (int cpu, struct mm_struct *mm)，把扫描循环换成 for_each_cpu_and，删除 get_scan_cpumasks()。
  • 2/2 -- DO NOT APPLY!!! -- sched/cache/debug: ...：仅测试用。把 get_scan_cpumasks() 加回来，新增 SC_VISIT / SC_NODE 两个 sched feature 分别切到新旧路径，并加 sched_cache_scan tracepoint 输出每次扫描的 CPU 数，用于 A/B 对比。

关键实现

/* kernel/sched/fair.c —— 置位与刷新 */
void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
{
    ...
    pcpu_sched->runtime += delta_exec;
    rq->cpu_runtime     += delta_exec;
    epoch = rq->cpu_epoch;

    pcpu_sched->epoch_last_visit = epoch;
    if (!cpumask_test_cpu(cpu_of(rq), mm->sc_stat.visited_cpus))
        cpumask_set_cpu(cpu_of(rq), mm->sc_stat.visited_cpus);
}

/* 清位与超时淘汰 */
static unsigned long fraction_mm_sched(int cpu, struct mm_struct *mm)
{
    struct sched_cache_time *pcpu_sched =
        per_cpu_ptr(mm->sc_stat.pcpu_sched, cpu);
    struct rq *rq = cpu_rq(cpu);

    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) {
        cpumask_clear_cpu(cpu, mm->sc_stat.visited_cpus);
        return 0;
    }
    ...
}

/* 扫描循环 */
static void task_cache_work(struct callback_head *work)
{
    ...
    /* 有意容忍的 race：account_mm_sched() 可能并发置位，
     * 漏掉的贡献下个周期会补回，换取免锁开销 */
    cpumask_and(cpus, cpu_online_mask, mm->sc_stat.visited_cpus);

    for_each_cpu_and(i, sched_domain_span(sd), mm->sc_stat.visited_cpus) {
        cur = rcu_dereference_all(cpu_rq(i)->curr);
        if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) &&
            cur->mm == mm)
            nr_running++;

        occ = fraction_mm_sched(i, mm);
        if (occ == 0)
            continue;
        ...
    }
}

  +--------------------------------------------------+
  | account_mm_sched()   (tick / context switch)     |
  |   epoch_last_visit = rq->cpu_epoch               |
  |   set_bit(cpu, mm->sc_stat.visited_cpus)         |
  +---------------------------+----------------------+
                              | visited_cpus grows
                              v
  +--------------------------------------------------+
  | task_cache_work()    (scan worker, 1 per period) |
  |   cpumask_and(cpus, cpu_online_mask, visited)    |
  |   for_each_cpu_and(i, sd_span, visited):         |
  |       cur->mm == mm ? nr_running++               |
  |       occ = fraction_mm_sched(i, mm)             |
  |            |                                     |
  |            +-- epoch gap > timeout               |
  |                  -> clear_bit(i), return 0       |
  |       track max(occ) -> m_cpu                    |
  +---------------------------+----------------------+
                              v
                   mm->sc_stat.cpu = m_cpu (pref LLC)

  scan width:  384 CPUs (old)  ==>  14..16 CPUs (new)

  Reviewer 关注的两个并发窗口
  ==========================

  (A) task_cache_work 跨期重叠 (Chen Yu)

    Thread A (cpu0)             Thread B (cpu1)
    -----------------           -----------------
    next_scan check OK
    try_cmpxchg WIN
    next_scan = 100+10
    enter scan loop  ......
    [preempted, jiffies->115]
                                next_scan(110) passed
                                try_cmpxchg WIN again
                                enter scan loop  <-- overlap?

  (B) mm->sc_stat.epoch 回退 (Tim Chen / Chen Yu)

    [ mm->sc_stat.epoch = 90 ]
    Thread A                    Thread B
    read cpu_epoch = 100        read cpu_epoch = 101
    time_after_eq(90,100) PASS  time_after_eq(90,101) PASS
                                lock; epoch = 101; unlock
    lock
    work->next == work STILL TRUE   (per-thread state)
    WRITE_ONCE(epoch, 100)      <-- moves backwards?

类比

把 task_cache_work() 想成物业的"快递柜盘点员"。

旧流程：他每轮都要按"整栋楼名册"（cpu_online_mask）或"整个片区名册"（node mask）挨家敲门，问"你最近用过柜子吗"。绝大多数门后没人，敲门声（自旋锁 + per-CPU 读）却一次不少。

新流程：每户人家（mm）自己维护一张"最近有人来取件的柜号清单"（visited_cpus）——取件时顺手在清单上打勾并记下日期（epoch_last_visit）。盘点员只按清单查；查到某个柜号"上次取件已经超过一个月"（llc_epoch_affinity_timeout），就顺手把它从清单上划掉。清单从 384 项瘦成 16 项。

try_cmpxchg 好比门口只有一块"今日盘点员"工牌，谁抢到谁去盘，别人看到工牌被摘走就自动回家。而 time_after_eq 那个锁外的时间检查，则像凭记忆说"我记得刚盘过"——两个人同时凭记忆判断、再先后进屋改台账，就可能把台账日期改回更早的一天，这正是 reviewer 指出的隐患。

Highlight：风险与注意点

  1. mm->sc_stat.epoch 的 lockless time_after_eq() 可能导致 epoch 回退。Tim Chen / Chen Yu 给出时序：A、B 在锁外分别读到 100/101 并都通过检查，B 先拿锁写 101，A 后拿锁时因 work->next 是 per-thread 状态仍为真，于是 WRITE_ONCE(epoch, 100) 把 epoch 写小。作者回复认为 __update_mm_sched() 会让 A 读到最新 epoch 因而不会回退——这一点在线程内尚未达成一致，是最需要跟进的争议。

  2. task_cache_work() 是否可能跨期重叠。Chen Yu 担心 A 在扫描循环里被长时间抢占、jiffies 越过 next_scan 后 B 再次赢得 try_cmpxchg，形成两线程同时扫描同一个 mm；他建议把 work->next = work 挪到函数末尾，让 task_tick_cache() 里的 work->next == work 检查真正起到闸门作用。作者认为 time_before + try_cmpxchg 双层保护已足够，结论待定。

  3. cpumask_test_cpu 守卫是否需要回填。v2 里 fraction_mm_sched() 入口有该检查，v8 删掉了。作者的理由是内层已改用 for_each_cpu_and，只会看到已置位的 CPU；且清位只在 task_cache_work() 内、每周期一次。Chen Yu 接受了这个解释，但这条推理依赖"每周期只有一个扫描者"，与第 2 点是同一个前提——若第 2 点成立，这里的安全性也随之动摇。

  4. 性能结论存在硬件差异。Chen Yu 在 Sapphire Rapids（内存交织）上无明显差异，在 AMD Milan（EPYC 9554P，NUMA balancing 开启）上观察到轻微回归，且怀疑在 run-to-run 抖动范围内。作者自测的 hackbench 里 threads 2 组也有多项 -1% ~ -7% 的 REGRESSED。需要更多硬件/负载复测才能断言"不影响准确性"。

  5. 内存分配与 TOCTOU。zalloc_cpumask_var() 失败时 mm_alloc_sched_noprof() 返回 -ENOMEM，需确认 fork 失败路径不泄漏已分配的 pcpu_sched（patch 里已 free_percpu）。另外 cpumask_and(cpus, cpu_online_mask, visited_cpus) 与并发的 CPU hotplug、account_mm_sched() 置位之间是有意保留的 race，注释已说明"漏掉的 runtime 贡献可忽略，下周期补回"——读者不要误以为这里有锁保护。

版本变化

  • v7 → v8：删除 get_scan_cpumasks()，因为 visited_cpus 已经精确给出需要扫描的 CPU 集合。
  • v6 → v7：在 task_cache_work() 中补充注释，说明 visited_cpus 的置位与读取之间的 race 是有意的取舍。
  • v5 → v6：visited_cpus 从内嵌 cpumask 改为 cpumask_var_t 动态分配，避免 NR_CPUS 很大时每个进程都膨胀；把 LLC sched domain span 直接与 visited_cpus 求交，避免跨 node LLC 拓扑下漏 CPU；epoch_timeout 更名为 epoch_last_visit；__update_mm_sched() 移到 fraction_mm_sched() 的超时检查之前。
  • v4 → v5：恢复 get_scan_cpumasks() 以免违反 NUMA_BALANCING 约束；用 for_each_cpu_and() 在 LLC 域内过滤。
  • v3 → v4：rebase 到 master；引入 epoch_timeout 淘汰过期 CPU（因为 epoch 会被 fraction_mm_sched() 周期性刷新而不可靠）；把 nr_running 自增移到 fraction_mm_sched() 之前；删除 task_cache_work() 末尾多余的 work->next 重置；新增 debug patch 输出扫描 CPU 数。

与其他相关工作的关联

本系列是对已合入主线的 cache-aware scheduling（sched_cache_stat / task_cache_work / llc_epoch_affinity_timeout 这套机制）的开销优化，不改变其选 LLC 的语义。第 2/2 的 debug patch 通过 SC_NODE（旧 NUMA 启发式）与 SC_VISIT（新 visited 路径）两个 sched feature 并存，正是为了在同一内核上对照两条路径。讨论中反复出现的 mm->sc_stat.lock、work->next、next_scan 均属于原 cache-aware 框架，本系列暴露的争议部分实际是原框架的既有问题。

一句话总结

用 per-mm 的 visited_cpus 精确记录近期跑过该进程的 CPU，并以 epoch 超时淘汰冷位，把 task_cache_work() 的扫描面从 384 个 CPU 收缩到十几个，Redis p99 与内核开销显著改善；但 reviewer 对 mm->sc_stat.epoch 锁外检查的回退风险、扫描跨期重叠以及 AMD 平台上的轻微回归仍持保留意见。