sched: 在 LLC 粒度上扩展 cache-aware 聚合

系列概况

标题：[RFC PATCH v2 00/23] sched: Scale cache-aware aggregation at LLC granularity
作者：Jianyong Wu（Hygon）
版本：v2（RFC，征求早期反馈）
规模：23 个 patch，覆盖拓扑基础设施、NUMA 偏好统计、迁移决策、NUMA balancing 协同、利用率估算与调试打印
修改文件：include/linux/topology.h、include/linux/sched/topology.h、include/linux/mm_types.h、include/linux/sched/sysctl.h、include/linux/sched.h、kernel/sched/topology.c、kernel/sched/fair.c、kernel/sched/core.c、mm/memory.c
代码统计：合计约 +800 / -200 行（各 patch stat 行累加）
Message-ID：20260827122816.756234-1-wujianyong@hygon.cn
完整性：包含 cover letter + 22 个具体 patch + 多轮回复；多数 reply 在 lore 抓取的 body 为空，仅保留主题与发件人

补丁目的

当前 cache-aware 调度（CAS）以"一个 LLC"为中心聚合线程。该模型在单 LLC 域内有效，但工作负载超出单个 LLC 后无法扩展。Peter Zijlstra 提议改为按 LLC 粒度扩展资源。

本系列回答两个核心问题：LLC 应该按什么顺序被选用？线程组需要沿该顺序扩展多远？

调度器先估算线程组总利用率，从 preferred LLC 沿 affinity sequence 向外扩展；目标 LLC 在估算范围内且有容量即可迁移，超出范围仍走 saturation check 以维持聚合。同时尝试拆解 CAS 与 NUMA balancing 的迁移冲突。

旧流程的问题

LLC-centric 聚合无法跨 LLC，工作负载超出一个 LLC 域后无扩展手段。
用 LLC mask 记录线程组资源范围：mask 在 task_cache_work() 中更新，在 load balance 中读取，负载快速变化时 mask 易暂时失真。
mask 绑定到具体线程组，但 load balance 在选择 source sched_group / runqueue 时没有 task 上下文，无法获取对应 mask。
NUMA balancing 启用时 preferred LLC 不稳定，因为扫描范围被限制在当前 task 的 preferred node。
CAS 与 NUMA balancing 的 task migration 路径冲突，难以独立控制。

新流程

构造 affinity sequence：preferred LLC 所在节点的 NUMA 距离行决定其它节点的先后顺序；preferred LLC 所在节点内的 LLC 由合成的 intra-node LLC 距离决定；其它节点按 LLC id 升序。
用估算的线程组利用率推出所需 LLC 深度 llc_range，范围内允许迁移。
迁移决策走 can_migrate_node()：先在 NUMA 节点粒度找第一个能容纳任务的节点，再在节点内按 intra-node LLC 顺序找第一个有容量的 LLC。
选 src rq / sched_group 时使用 affinity score：score = sum_i Rt_i * (src_dist - dst_dist)。
NUMA balancing 拆成 task migration 和 page migration，可通过 sysctl numa_balancing_mode 独立开关。
引入不对称 EWMA（上升 1/2，下降 1/8）估算 mm 整体利用率。

Patch 概览

拓扑基础设施（01–06）：llc_to_node()、去重 NUMA 距离矩阵、节点遍历宏、intra-node LLC 距离公式、LLC 遍历宏、sd_node per-CPU 句柄。
偏好统计（07–10）：task_cache_work 中先选 NUMA 节点再选 LLC、sd->numa_counts、account_llc_enqueue/dequeue 更新 NUMA 计数、sd->affi_ids/affi_weights scratch。
迁移决策（11–16）：can_migrate_node() 两阶段、cal_affinity_score()、get_affi_llcs/get_affi_numas、源 rq/组按 affinity score 选取、解除 prefer_sibling 限制、用 if_to_prefer() 替代 cpus_share_cache 判定、llc_spread_active_balance() 解除 spread 方向对 nr_balance_failed 的等待。
NUMA balancing 协同（17–19）：numa_balancing_mode 独立开关 task/page migration、扫描线程组所有 preferred node、删除过时的 preferred LLC/node 检查。
利用率与 walk（20–22）：update_mm_util_avg()、llc_range 范围内允许 spread、从 preferred LLC 沿 preferred node 走。
调试（23）：sched/debug 打印 task preferred LLC。

关键实现

Intra-node LLC 距离公式

// 给定同一节点内的两个 LLC，rank 为节点内 LLC id 升序排名
dist(LLC1, LLC2) = (rank1 + rank2) % k + 1   // k = 该节点 LLC 数
// LLC1 == LLC2 时硬编码为 0

保证从一个 reference LLC 看出去，所有兄弟 LLC 的距离互不相同；但不保证任意两个 LLC 对之间的全局唯一性。

去重 NUMA 距离矩阵

// 对每个 tier，用贪心 edge-color 把同 tier 节点对打散到不同 color
// 编码：(tier, color) -> 最终值 = tier_dist[t] * scale + color
// scale 自适应，使每个 tier 的 color span 严格小于下一 tier 间距

性质：对称、保留 node_distance() 的相对顺序、行内距离互不相同。

Affinity 评分

Di = node_distance(src_node, NUMAi) - node_distance(dst_node, NUMAi)
Wi = Rt_i * clamp(Di, lo, hi)
score = sum_i Wi

NUMA 域 balance 用 sched_cache_node_distance()；NODE 域 balance 在同节点内用 llc_intra_node_distance()，跨节点使用假设公式 llc_dist = node_dist + m + n。

迁移两阶段（can_migrate_node）

for_each_sched_node(target_cpu, node) { // 从 src 节点开始
    for_each_llc_node_span(node, span) {          // 按 intra-node 距离
        get_span_stats(span, &u, &c);
        if (dst 在此 span) {
            if (fits_llc_capacity(u + tsk_util, c)) return mig_llc;
            // 兜底：源比目的大 2 个 task 且仍能装下时也放行
            return mig_forbid;
        }
        // 更近的 LLC 只有在能装下时才否决此次迁移
    }
}

类比

把调度器想象成会议室分配员。一间大会议室只能装 12 人（一个 LLC）。当一个 20 人项目组要开会，原系统只能让他们挤在小会议室里。改造后：分配员手里有一本"会议室手册"（去重 NUMA 距离 + intra-node LLC 距离），告诉他哪个会议室最近（affinity sequence）以及每个会议室能装多少人。他还实时估计项目规模（group_util）：当主会议室坐满时，就顺着手册里"下一个最近的"会议室把人挪过去，每次只挪一个，并且只往还有空位的地方挪。llc_spread_active_balance 类似"反向分配员"：当某个会议室塞得太满而隔壁还空着时，他可以主动把人挪走，不需要等多次失败重试。

          [preferred LLC]
                |
                v
   +-----------------------------+
   |  for_each_sched_node walk   |
   +-----------------------------+
        |        |        |
        v        v        v
     node N1   node N0   node N2 ...
        |
        +---> for_each_llc_node_span
                  |
                  v
         +-------------------+
         |  llc intra dist   |
         |  sort by anchor   |
         +-------------------+
                  |
                  v
          can_migrate_node()
                  |
                  v
   cal_affinity_score() -> src rq / group
                  |
                  v
           spread / pull / keep

Highlight：风险与注意点

去重矩阵的 scale 自适应有上限保护 scale > 1000，极端拓扑下距离值可能远离 BIOS 原始数值；不参与 sched domain 构造，但所有 CAS 决策都基于它。
跨节点 LLC 距离用假设公式 llc_dist = node_dist + m + n，与真实拓扑偏差未知；affinity score 可能因此把任务引导到非最优节点。
不对称 EWMA（上升 1/2，下降 1/8）扩张快、收缩慢，负载波动大时线程组可能长时间跨过多 LLC。
双向迁移不对称：pull 走 migrate_llc_task 直接走 active balance，spread 走 migrate_task 必须等 nr_balance_failed；新加的 llc_spread_active_balance 只在 LLC 已超 cap 且 dst 仍有空间时放行，回归风险较高。
alb_break_llc 改为只处理单任务 rq，多任务路径移到 can_migrate_task；NUMA 亲和检查提前到 active balance 之前。任一边漏改都会让任务驻留在错误节点。
大量 reply 的 body 在 lore 抓取为空，主题多为具体 patch 编号，作者与 Peter Zijlstra 在邮件线程中反复来回但看不到具体技术意见原文。

版本变化（v1 → v2）

不再按 sched domain 边界扩展资源。
引入行内距离互不相同的 NUMA 距离矩阵。
引入 intra-node LLC 距离矩阵（(rank1+rank2)%k+1）。
重写 affinity gain 计算。
重写 migration 权限判定（if_to_prefer）。
修复 schbench 等测试的 saturation 问题。
把线程组所有 preferred node 都纳入扫描范围。
新增 numa_balancing_mode sysctl 独立开关 task/page migration。
引入线程组整体利用率估算。
允许估算范围内即使前一 LLC 未饱和也迁移。
从 preferred LLC 沿 preferred node 走。
修复 debug print 的 bug（XIAO WU 建议）。

一句话总结

本系列把 cache-aware 调度的聚合范围从一个 LLC 扩展到多个 LLC，通过去重 NUMA/intra-node LLC 距离矩阵构造 affinity sequence，用 affinity score + 线程组利用率估算决定扩展深度，并拆解 NUMA balancing 以解除 CAS 与之的冲突。

[RFC PATCH v2 00/23] sched: Scale cache-aware aggregation at LLC granularity

LLM 分析