sched_ext 子调度器的能力化 CPU 委托（v4）

系列基线信息

标题：[PATCHSET v4 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers
作者：Tejun Heo tj@kernel.org
版本：v4（4th iteration，v1→v2→v3→v4 全部发布）
规模：40 个 patch
Message-ID 起点：20260708212429.3405787-1-tj@kernel.org
来源频道：lore.kernel.org / sched-ext
基础分支：sched_ext/for-7.3 (daf8…)
线程长度：83 封邮件（41 封 patch + 15 封 sashiko-bot 自动审阅回复 + 27 封作者/审阅者交互）
当前状态：v4 已发，等待 maintainer 上树或继续迭代

明确目的（Purpose）

让 sched_ext 的子调度器（sub-scheduler）分层从「只能在 dispatch 路径上以程序化调用形式委托」，扩展为包含 enqueue、occupancy、kick、preempt、idle reporting 在内的全路径能力（capability）式委托。核心是把 CPU 访问变成显式的能力令牌（cap token），父调度器按 (scheduler, cid) 粒度向下授予、收回，子调度器只能在持有的能力范围内操作 CPU。子调度器只有在 cgroup 边界且亲和性未逃逸的前提下才能工作；cgroup 跨迁、不可达 cpu 上的 fallback 是已知遗留问题，未来通过为根调度器预留一个「无 cpu 通道」slice 来解决。

遍历代码（Walkthrough）

整条 40 patch 大致可分为五段：

段一：清理与基础设施（patches 01–09）

01/40 scx_sub_enable_workfn()：在 err_disable 落点记录错误，避免仅返回 -ENOMEM 这类 errno-only 失败路径走不到 scx_flush_disable_work()，导致子调度器半初始化态被挂在树里。Fixes: ebeca1f930ea。
02/40 scx_alloc_and_add_sched()：把 rcu_assign_pointer(ops->priv, sch) 推迟到 cgroup 路径分配之后，使任何此后的失败都通过 kobject_put() 走 RCU 延迟释放，杜绝并发 scx_prog_sched() 读者 use-after-free。
03/40 工具链 BPF 头 cid.bpf.h：cmask_equal / cmask_weight / cmask_subset 用 CMASK_NR_WORDS 限制字游走，本来比实际活跃 range 多走一个 slack word，重写时改用「range 实际跨度的字」+ 空 range 早返回；cmask_subset 改成与内核 scx_cmask_subset() 语义一致（用 cmask_next_set 检查外部位、遍历交集字）。
04/40 cmask 字操作：把 data_race() 风格的 _RACY 变体换成 READ_ONCE/WRITE_ONCE，让所有双 cmask op 都能 lockless 读源 cmask。
05/40 引入 SCX_CALL_CID_OP_TASK()：原 scx_call_op_set_cpumask() 手写 kf_tasks[] 与 locked_rq 包裹，且退出时把 locked_rq 复位成 NULL（覆盖了外层）。参数化调度宏并通过 __SCX_CALL_OP_TASK(sch, ops_cid, op, …) 走 ops_cid，行为修复后 locked_rq 正确保存/恢复。
06/40 extra_enq_flags → remote_activate_enq_flags：纯改名，澄清这个字段只在跨 rq 任务迁移里走 activate_task() 边界时携带 scx 标志，并修掉一段指向旧函数名的过期注释。
07/40 scx_qmap 工具：把 __u64/__u32/__s32 全部换成 u64/u32/s32 保持风格一致；stats printf 用 (unsigned long long) 转换。
08/40 给 cid-form struct_ops 单独的 BPF verifier ops：拒绝 BPF 程序直接写 p->scx.slice 与 p->scx.dsq_vtime，强制走 scx_bpf_task_set_slice/dsq_vtime() kfunc（这两个 kfunc 才带 cap 校验）。cpu-form 保留直接写并去掉 deprecation warning。
09/40 scx_bpf_kick_cid() 返回值改 void：旧返回值无实际意义（kick 是异步的），非法 cid 由 scx_cid_to_cpu() 经 scx_error() 自行 abort；ABI 安全（cid-form 还未实际使用）。

段二：per-sched kick 与 CID 布局（patches 10–15）

10/40 把 kick 状态从 rq->scx（所有调度器共享）下放到 scx_sched_pcpu：每个 (sched, cpu) 持有自己的 cpus_to_kick / _if_idle / _preempt / _wait 与 to_kick_node，cpu 的 kick_cpus_irq_workfn() 走 sched_pcpus_to_kick 链表处理。scx_kick_cpu() 加 NMI 检测（仅 local_irq_save 不能屏蔽 NMI）并告警；free_kick_syncs() 现在 irq_work_sync 之后再清 pcpu 状态。
11/40 新增 ops.init_cids()：在 root 调度器的默认 CID 布局建好之后、正式 init() 之前调用，cid-form 调度器可在这里调 scx_bpf_cid_override() 改写布局；scx_bpf_cid_override 从原来「仅 init 阶段可调」改到「init_cids 阶段可调」并相应增加 SCX_KF_ALLOW_INIT_CIDS。scx_qmap 同步加 qmap_init_cids()。
12/40 引入 CID sharding：把 CID 空间按 LLC 对齐切成 shard（scx_nr_cid_shards + scx_cid_to_shard + scx_shard_node + scx_cid_shard_ranges），每 shard 至少 1 核、最多 SCX_CID_SHARD_MAX_CPUS；新增 ops.cid_shard_size 字段。无拓扑 cid 也按相同 max 打包。
13/40 scx_bpf_cid_override() 新增 shard_start 参数：BPF 程序显式声明每个 shard 的起始 cid；kfunc 严格校验（必须 0 起、严格递增、范围合法、跨度 ≤ max），无效输入直接 abort 调度器；scx_shard_node 通过「每个 shard 内 cid 所属 node 的多数表决」推断。
14/40 把 kobject_init_and_add 拆成 kobject_init() + 新的 scx_sched_sysfs_add()，sysfs add 移到 enable workfn 里执行——这样未来 caps 属性能假定 sch 已完全建立。scx_root_disable / scx_sub_disable 跳过未加入 sysfs 的 kobj。
15/40 为 scx_sched 引入 pshard[]（按 shard_idx 索引，每条目在 scx_shard_node[si] 的 NUMA 节点上分配）。本 patch 中 struct scx_pshard 还是空壳，数组完整分配后通过 smp_wmb() + WRITE_ONCE 发布，避免读者看到半填状态。scx_nr_cid_shards 在异步 RCU 释放时可能已被后启调度器覆写，所以 sch->nr_pshards 单独记录。

段三：cmask 引用与子树遍历（patches 16–20）

16/40 scx_cmask_ref —— 来自 BPF arena 的 cmask 引用要面对两个问题：BPF 可以传任意指针、并且 arena header（base/nr_cids/alloc_words）可被并发改写。_init() 把 BPF 指针 normalize 到 arena 的 kern_vm 并快照 header；_shard() 按快照读某个 shard；_or/_copy() 按快照写回。顺便去掉 bits[] 上的 __counted_by(alloc_words)（BPF 可改 alloc_words，注释帮不上忙反而误导）。
17/40 scx_cmask_ref_init_kern() 与 _from_cpumask()：给内核侧 cmask scratch 用可信几何信息（base/nr_cids 由调用方给，arena header 不读），再把 cpumask 写进 arena；scx_call_op_set_cpumask() 走这条路径，杜绝 BPF 篡改 header 导致越界。
18/40 RCU 化 children / sibling 链表：子调度器的子树 walker 允许在 rcu_read_lock 下进行（除了写者仍持 scx_sched_lock）。scx_link_sched 在 scx_bypass_lock 持锁下检查父级是否在 bypass（bypass 状态 = per-cpu flag + depth count，不能原子继承），若父级正在 bypass 直接 -EBUSY 拒绝挂接。
19/40 scx_skip_subtree_pre()：把 scx_next_descendant_pre() 末尾的 sibling/ancestor 提升逻辑抽出来，未来用于驱逐子树等场景。
20/40 scx_prog_sched() 不再解析已被 disable 的调度器：避免 BPF 程序（timer、tracing）跨生成访问已被拆掉的 pshard[]，关闭一类跨代越界。

段四：能力机制主体（patches 21–33）

21/40 每 shard cap 委托：定义 SCX_CAP_ENQ_IMMED / SCX_CAP_ENQ / SCX_CAP_PREEMPT 三种能力，per-shard cmask 记录「父持有 ∩ 子持有」的交集；scx_bpf_sub_grant() / scx_bpf_sub_revoke() 修改 cmask；SCX_CAP_ENQ 蕴含 SCX_CAP_ENQ_IMMED，SCX_CAP_PREEMPT 蕴含 SCX_CAP_ENQ。grant 必须是父字面持有的能力，不能授予蕴含得到的。
22/40 ops.sub_caps_updated(s32 shard_idx, …) 通知：shard 级配置变更带合并/去抖。
23/40 每个 (sched, cpu) 维护 effective-cap 副本：把 shard 内的 cmask 折进 per-cpu 数组，热路径单读就拿到本 cpu 上该调度器的能力。grant/revoke 触发 doorbell，本 cpu 在 balance() 顶端 fold 进来。
24/40 ops.sub_ecaps_updated(cid, new_ecaps)：effective-cap 真正生效时通知；通过 doorbell 路径解耦「配置变化」与「生效时机」。
25/40 把 local-DSQ 概念泛化成 rq-owned DSQ：cid-form 调度器对每个授权 cid 都有一组 per-cpu DSQ，统一抽象便于拒绝路径使用。
26/40 拒绝 DSQ（reject DSQ）：cap 校验失败的 insert 改放到 per-rq 的内核私有拒绝 DSQ，重新入队到 BPF 调度器的 ops.enqueue()，并打上 SCX_TASK_REENQ_CAP 与缺失 cap 列表。
27/40 SCX_CAP_ENQ_IMMED：只允许 insert IMMED 任务，是 SCX_CAP_BASE（任何 CPU 访问的基线）。
28/40 给每个调度器实例分配唯一 id（用于 kill、stats、sysfs 等）。
29/40 slice 写改走 set_task_slice()：避免 BPF 直接写 p->scx.slice 绕过 cap。
30/40 跟踪任务在哪个 cpu 上 runnable（p->scx.runnable_cpu），rq lock 下盖章；slice 写路径用它校验 rq 归属，杜绝「缓存的 task_rq() 在远端唤醒时与已迁移的睡眠任务 stale-match」的 TOCTOU。
31/40 CPU 占用与 slice 绑定：扩 slice 等同于在该 cpu 上有 baseline 访问。
32/40 SCX_CAP_ENQ：允许 insert 任意任务。
33/40 kick 必须有目标 cid 的 baseline 访问；SCX_KICK_PREEMPT 在 victim 不在 kicker 子树且 kicker 没有 SCX_CAP_PREEMPT 时降级为普通 reschedule。

段五：通知、kill、demo（patches 34–40）

34/40 远端 move insert：以「放置任务的调度器」为准做授权。
35/40 ops.update_idle() 路由到 cid owner；owner 变更时给新 owner 重发通知（如果 cpu 当前正 idle）。
36/40 被 bypass 抑制的 ecaps 通知在 bypass 退出时回放。
37/40 scx_bpf_sub_kill()：父调度器驱逐不听话的子调度器。
38/40 工具链 tools/sched_ext：把三 mask 交集迭代器抽成独立 patch。
39/40 scx_qmap 分层 demo 扩展：qmap 实例把自己完全持有的 cpus 按 cpu.weight 比例在自己与子 qmap 之间分配，余数 round-robin 池分时复用。
40/40 scx_qmap 给未持有 cid 的 dispatch 加 fault injection，演示内核侧的强制路径。

ASCII 流程图

1. 三层能力委托（R → A → A1）

                 +-----------+
                 |  Root R   |  持有全部 cap、所有 cid
                 |  ops.init |
                 +-----+-----+
                       | scx_bpf_sub_grant(cid 8-15, BASE|ENQ|PREEMPT)
                       v
                 +-----------+         scx_bpf_sub_grant(cid 12-15, BASE|ENQ)
                 |  Sub  A   |
                 | (ops.sub_caps_updated)
                 +-----+-----+
                       v
                 +-----------+
                 |  Sub A1   |  持有的 cap  ⊆  A  ⊆  R
                 +-----------+  不能授予通过蕴含得到的 cap


### 2. 撤销 cid 8 后任务回收流

R revoke(cid 8)
|
v
sub_caps_updated(A, shard=…) <-- 整棵子树一起清
|
v
A: ecaps 在各 cpu fold 进 effective_cap
|
+--> queued task -> reject DSQ -> ops.enqueue() 重入, 标 SCX_TASK_REENQ_CAP
+--> running task -> slice 清零 -> 强制切出 -> 同样回 A.enqueue()
+--> new insert -> 直接 reject -> 回 A.enqueue()
|
v
A 把 bounce 出来的任务放到还持有的 cpu 上继续调度


### 3. 能力检查热路径


### 4. shard + per-cpu effective cap 结构

         grant / revoke
             |
             v
    +------------------+         doorbell
    | shard[0].cmask   |  <----------------  per-cpu effective_cap
    | shard[1].cmask   |                      (fold on balance() entry)
    |   ...            |
    | shard[N-1].cmask |                      热路径单读
    +------------------+


## 概念类比（Analogy）

**「酒店房卡分层」**：root 调度器是酒店业主，握着所有房间的总控卡；子调度器 A 是租下一层楼的客户，A 再把其中几间转给子客户 A1。每张「房卡」就是 cap（BASE/ENQ/PREEMPT）——有 BASE 卡才能进门，ENQ 卡能带人入住，PREEMPT 卡能在别人占用时强制换锁。业主可以随时在总控台把某间房的卡远程作废（revoke），此时 A 与 A1 持有的该房间的卡**同步失效**（子集语义），已入住的客人被请出（slice 清零）并在前台重新办登记（reject DSQ → re-enqueue）。整层楼的物理房间（CPU 资源）通过 shard 切成若干门厅（lock 域），每层各办各的入住登记，互不打架。

## Highlight 突出问题（Pitfalls / 待跟进）

- **跨代 pshard[] 越界**（patch 20 关闭的口子）：disable 后仍存活的 BPF 程序（timer、tracing）可能在新生成上做 `pshard[]` 索引。读者应复查所有「outlive disable」的程序路径。
- **NMI 上下文踢人**：patch 10 把踢人改成 `local_irq_save` 保护的链表，**NMI 仍未屏蔽**，从 NMI 调 `scx_bpf_kick_cpu()` 会破坏链表——仅打 warning 拒绝，未来要么换 `local_irq_save_nmi` 要么限制 NMI 内 BPF 调用点。
- **scx_cmask_ref header 快照 vs live cmask**：patch 16 用快照做 sizing，但实际写入路径仍要对齐 live layout；如果 BPF 在两次 `_shard()` 之间把 range 缩小到比 `_init` 快照还窄，写入会落到原本合法的位置（设计选择，但要在文档中明示）。
- **bypass 期间链接**：patch 18 改成「拒绝」而不是「继承 bypass_depth」。未来若有合法跨 bypass 链接需求，要重新评估；现在只是简化正确性。
- **ecaps 通知回放窗口**（patch 36）：bypass 退出时回放被抑制的 ecaps 通知，回放期间状态可能再次变化；需要复查回放代码是否对重入/并发有界。
- **「无 cpu 通道」fallback 仍未实现**：把任务交给根调度器预留 slice 是 forward-looking，目前只写在 cover letter 的「Known limitations」里。
- **cgroup 跨迁不携带调度器归属**：跨 cgroup 移动的任务保留原 sched，对分层结构是已知局限。
- **BPF-side 直接写 slice/dsq_vtime 的旧路径**仍然存在于 cpu-form：cid-form 已堵；混用两种 struct_ops 的旧 demo 仍可能误用，需要在示例仓库中 grep 一遍。
- **per-cpu effective-cap 副本的内存成本**：随 (sched × shard × cpu) 增长，配置阶段要测算极端拓扑下的占用（典型没问题但要在 v5 之前的 cover letter 中给一个上限数）。
- **scx_qmap 三 mask 迭代器**（patch 38）目前只在 demo 路径调用；如未来有 production 使用，需要补 unit test。
- **API 表面**：cid-form 已经 8+ 新增 kfunc/struct_op（`init_cids, sub_grant, sub_revoke, sub_kill, sub_caps_updated, sub_ecaps_updated, update_idle 路由`），未来 API review 时需要 list ABI 兼容性。

## 版本演进（v1 → v4）

v4 在 cover letter 列出的关键改动：

| 类别 | v4 新增/调整 |
|---|---|
| 修复 | 新增 01/40：errno-only 失败路径漏 record error |
| 修复 | 新增 20/40：scx_prog_sched() 不再解析被 disable 的调度器（关跨代 pshard 越界） |
| 修复 | 10/40 `free_kick_syncs()` 在清 per-cpu kick state 之前 flush pending irq_work |
| 重构 | 新增 30/40 prep：`p->scx.runnable_cpu` 解决远端唤醒 TOCTOU |
| 演示 | 39/40 scx_qmap 跟踪每个 cid 的 idle，按 node 自己的 cid 集合做 mask，去 reseed race |
| 演示 | 38/40 把三 mask cmask 迭代器独立成 patch |
| 基础 | 15/40 的 pshard[] 以「先建后发」形式引入，避免后续 patch 二次重写 |
| 文档 | cover letter 列出剩余两个 limitation（cgroup 跨迁、无 cpu fallback） |

## 与其他相关 patch 系列的关联

- **sched_ext/for-7.3 base (daf8…)**：本系列基础分支，包含 EBECA1F930EA（cgroup sub-sched 引入，patch 01 Fixes 标签）以及 105dcd005be2（scx_prog_sched 引入，patch 02 Fixes 标签）。
- **scx_qmap demo** 持续作为分层的可视化与压测来源；本系列 patch 38–40 都与 demo 紧密相关，scx_qmap 的 hierarchical 演示是真实负载下验证 cap 行为的主要工具。
- **sub-sched 概念本身**（EBECA1F930EA）由 Tejun 早期提交，本系列是其「全路径委托」补完。
- 与上游 LKML 的 `sashiko AI` 工具互动：cover letter 中多个 patch 标注 `(sashiko AI)`，说明这是 Tejun 与 AI 协作审计过的结果；lore 上同时间的 sashiko-bot 回复也是同一工具的体现。

## 一句话总结

v4 把 sched_ext 的子调度器从「dispatch-only 委托」升级为「全路径能力化 CPU 委托」：每 (sched, cid) 持三档 cap，per-shard cmask 跟踪 + per-cpu effective-cap 单读热路径，cap 缺失走 reject DSQ 回 BPF 重排，并修掉了 5+ 个并发的 pre-existing 漏洞。

[PATCHSET v4 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers

LLM 分析