sched_ext: 基于 Capability 的 CPU 委托机制 — 子调度器 v5 补丁系列分析

系列基线信息

标题: [PATCHSET v5 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers
作者: Tejun Heo (tj@kernel.org)
版本: v5（历经 v1→v2→v3→v4→v5 五轮迭代）
规模: 33 个补丁，覆盖内核核心调度路径 + BPF kfunc + scx_qmap 示例
Message-ID: 20260709225041.1695495-1-tj@kernel.org
来源: sched-ext 频道，基于 sched_ext/for-7.3 (3d1519011e39)
审核人: Andrea Righi 对多个补丁提出评审意见，Tejun 已回复

明确目的

本补丁系列为 sched_ext 的子调度器（sub-scheduler）添加基于 capability 的 CPU 委托机制。

当前子调度支持仅覆盖调度路径的一部分：dispatch 通过 scx_bpf_sub_dispatch() 实现自顶向下的程序化委托，但 enqueue 路径尚未实现——每个调度器可以往任意 local DSQ 插入任务，父调度器无法在 CPU 之间划分资源或保护自身份额。

本系列的核心目标：

在 enqueue 路径启用子调度支持
将同一控制模型扩展到 CPU 占用、kick、抢占和 idle 报告等其他路径
实现"委托是状态而非调用"的设计：capability 以 per-shard cmask 形式记录，热路径只需单次读取 per-cpu effective caps

遍历代码

补丁按逻辑分层，逐步搭建整套委托机制：

基础层（01-09）— 安全加固与基础设施

01: 在 SCX_CALL_OP_TASK() 中添加 WARN_ON_ONCE(sch != scx_task_sched_rcu(task))，确保 per-task op 只在任务所属调度器上运行。两处合法非 owner 调用点改用 __SCX_CALL_OP_TASK()。
02: 将 kick 机制从 rq->scx 共享状态改为 per-sched 的 scx_sched_pcpu 状态，使 preempt kick 可归属到发起调度器。kick irq_work 遍历 per-cpu 的 sched_pcpus_to_kick 链表。
03: 新增 ops.init_cids() 回调，在 ops.init() 之前运行，允许 cid-form 调度器在此调用 scx_bpf_cid_override() 定制 cid 布局。
04: 引入 CID sharding——cid 空间按 LLC 拓扑划分为 shard，每个 shard 是连续 cid 区间，用于可扩展锁粒度。
05: scx_bpf_cid_override() 新增 shard_start 参数，允许 BPF 调度器同时定制 cid 映射和 shard 布局。
06: 将 kobject_init_and_add() 分拆为 kobject_init() + scx_sched_sysfs_add()，后者在 enable workfn 中调用，保证 sysfs 可见时调度器已完全构建。
07: 新增 scx_pshard 按 shard_idx 分配在 shard 的 NUMA node 上，结构体当前为 scaffold（仅 dummy 字段）。
08: 新增 scx_cmask_ref——验证 BPF arena cmask 的安全引用，快照 header 防止并发篡改，提供 shard 读取和回写操作。
09: 将 set_cmask scratch 的构建从读取 BPF-writable header 改为使用 kernel 提供的可信几何参数（scx_cmask_ref_init_kern()），防止 BPF 端篡改引发越界写入。

核心委托层（10-16）— RCU 安全遍历与 cap 机制

10: 子调度器树的 children/sibling 列表改为 RCU 保护，允许 kfunc 在无 scx_sched_lock 下遍历。拒绝在 bypass 状态的祖先下链接子调度器。
11: 提取 scx_skip_subtree_pre() 用于 pre-order 遍历中跳过子树。
12: 新增 scx_sched->dead 标记，在 ops.exit() 之后设置并 synchronize_rcu()，使 scx_prog_sched() 对已死调度器返回 NULL，阻止过期 BPF 程序访问全局状态。
13: 核心补丁——引入 per-shard cap 委托机制。scx_pshard->caps[cap_bit] 是 per-shard cmask，记录调度器在该 shard 上持有哪些 cid 的哪种 cap。根调度器初始持有全部 cap。新增 kfunc scx_bpf_sub_grant() / scx_bpf_sub_revoke() / scx_bpf_sub_caps()，cap 按 shard 加 raw_spinlock 保护。sysfs 导出 caps 属性。
14: 新增 ops.sub_caps_updated() 合并通知器。grant/revoke 批量修改后累积到固定 payload (cmask, caps)，释放 shard lock 后异步投递。每 shard 最多一条 in-flight 通知。
15: 新增 per-cpu effective caps (pcpu->ecaps)。它是 pshard->caps[] 的转置：对每个 cid，记录该调度器在此 cpu 上持有的 cap 位集合。热路径单次 READ_ONCE(ecaps) 即可判断。变更通过 llist 队列在 balance_one() 中同步。

通知与执行层（16-29）

16: ops.sub_ecaps_updated() 通知 per-cpu effective caps 变更生效时机。
17: 将 local-DSQ 处理泛化为 rq-owned DSQ 概念。
18: 添加 per-rq reject DSQ——缺乏 cap 的任务插入被拒绝并打回 ops.enqueue()，标记 SCX_TASK_REENQ_CAP 和缺失 cap。
19: SCX_ENQ_IGNORE_CAPS 标记用于 in-place SAVE/RESTORE requeue，避免已运行任务因只持有 SCX_CAP_ENQ_IMMED 而被误拒。
20-26: 逐步定义 SCX_CAP_ENQ_IMMED（baseline）→ SCX_CAP_ENQ → SCX_CAP_PREEMPT，每层隐含下层，并在对应路径添加执行检查。
22: 每个调度器实例分配唯一 id。
23: 任务 slice 写操作统一经 set_task_slice() 路由。
24: 记录任务 runnable 所在的 cpu。
25: CPU 占用与 SCX_CAP_BASE 绑定——延长 slice 需 baseline cap。
26: 添加 SCX_CAP_ENQ cap。
27: Kick 需要 SCX_CAP_BASE，SCX_KICK_PREEMPT 在无 SCX_CAP_PREEMPT 时降级为普通 reschedule。
28: ops.update_idle() 路由到 cid 的 owner 调度器，所有权变更时重新通知。
29: 在 bypass 结束后 replay 被抑制的 ecaps 通知。

终结与示例（30-33）

30: scx_bpf_sub_kill() 可驱逐行为不当的子调度器。
31: tools/sched_ext 添加三掩码 cmask 交集迭代器。
32: scx_qmap 扩展层级子调度演示——按 cpu.weight 比例分配所拥有的 CPU，时间共享剩余部分。
33: scx_qmap 添加 cap 故障注入，演示内核侧拒绝执行。

ASCII 流程图

CAPABILITY DELEGATION FLOW
==========================

  Root R (owns ALL caps on ALL cids)
  |
  +-- Grant cids 8-15, SCX_CAP_ENQ to Child A
  |     via scx_bpf_sub_grant(A_cgrp, cmask{8..15})
  |
  A (holds SCX_CAP_ENQ on cids 8-15)
  |
  +-- Grant cids 12-15, SCX_CAP_ENQ_IMMED to A1
  |     via scx_bpf_sub_grant(A1_cgrp, cmask{12..15})
  |
  A1 (holds SCX_CAP_ENQ_IMMED on cids 12-15)

REVOKE FLOW (R revokes cid 8 from A):
======================================

  R: scx_bpf_sub_revoke(A_cgrp, cmask{8})
     -> clears cid 8 across A's WHOLE subtree
     -> A1 also loses whatever it held on cid 8

  A's tasks on cid 8:
     -> reject DSQ -> ops.enqueue() w/ SCX_TASK_REENQ_CAP
     -> running task: slice zeroed, evicted

  A receives: ops.sub_caps_updated(cmask{8}, SCX_CAP_ENQ)
  A receives: ops.sub_ecaps_updated(cid=8) once cpu syncs

PER-CPU EFFECTIVE CAPS (ecaps) SYNC:
=====================================

  pshard->caps[cap].cmask          pcpu->ecaps (per-cpu transpose)
  +---+---+---+---+---+---+        cid 8:  SCX_CAP_ENQ_IMMED|ENQ
  | 8 | 9 |10 |11 |12 |13 |   =>  cid 9:  SCX_CAP_ENQ_IMMED|ENQ
  +---+---+---+---+---+---+        cid 12: SCX_CAP_ENQ_IMMED
  (target config, shard-locked)    (effective copy, rq-locked)

  grant/revoke -> queue_sync_ecaps() -> llist -> kick cpu
                -> balance_one() -> scx_process_sync_ecaps()
                -> WRITE_ONCE(pcpu->ecaps, calc_effective_caps())

SHARD LOCKING GRANULARITY:
==========================

  cid space:  [0..7] [8..15] [16..23] [24..31]
  shard 0     shard 1  shard 2   shard 3
  (per LLC)   lock A    lock B    lock C
  => Different shards NEVER contend

概念类比

想象一家大型公司（根调度器 R）拥有多栋办公楼（CPU），将部分楼层委托给子公司 A 使用：

Capability = 租赁合同条款：SCX_CAP_ENQ_IMMED 相当于"可立即入驻"的最低权限；SCX_CAP_ENQ 相当于"可以安排员工到指定楼层办公"；SCX_CAP_PREEMPT 相当于"可以赶走其他公司的人腾出房间"。
Grant/Revoke = 签约/解约：父公司通过 scx_bpf_sub_grant() 签合同给子公司一定楼层和权限范围，scx_bpf_sub_revoke() 解约时立即收回——子公司必须把员工搬到还有合同的楼层。
Shard = 物业管理分区：大楼按楼层段划分物业（shard），每区有自己的管理锁（pshard->lock）。不同区互不影响，签解约只锁自己那个区。
ecaps = 前台门禁系统：每层楼的前台（per-cpu）有一份当前有效权限清单（ecaps），员工刷门禁时只需看这份单子（一次读取），不用每次都打电话到物业总部确认。
Reject DSQ = 暂存区：没权限的员工被拦在门口，送回暂存区等待重新分配到有合同的楼层。
sub_caps_updated = 合同变更通知：物业总部签/解约后发邮件通知子公司，子公司据此更新自己的内部安排，也可以通知自己的下级子公司。

Highlight 窕出问题

两个关键缺失尚未实现：cgroup 跨子调度器迁移不改变任务的调度器归属；任务被亲和到调度器无权限的 CPU 时没有 fallback。Cover letter 明确指出这两块是后续工作，当前设计下这类任务会卡住。
ecaps 与 cap 的时序窗口：ops.sub_caps_updated() 是配置级变更通知，可能在变更生效到具体 cpu 之前就投递。如果子调度器据此立即做调度决策，可能看到一个尚未生效的状态。必须用 ops.sub_ecaps_updated() 确认生效后才做精确判断。
BPF arena cmask header 的并发篡改风险：BPF 程序可以异步修改 arena cmask 的 base/nr_cids/alloc_words。系列中多个补丁（08、09）专门用 scx_cmask_ref 的快照机制防止越界读写，但任何新增的 arena cmask 操作都必须使用 _ref 而非直接访问。
revoke 的级联效应：收回一个 cid 会清除该调度器整个子树的权限，所有后代调度器在该 cid 上的任务也被驱逐。子调度器需要在 ops.enqueue() 中快速重新安置被弹回的任务，否则任务可能反复 bounce。
dead 调度器的 BPF 程序仍可触发：补丁 12 设置 sch->dead 并 synchronize_rcu()，但定时器和追踪程序可在 ops.exit() 之后触发。后续新增 kfunc 必须确保 !sch bailout 覆盖所有新路径。

版本演进

v4→v5 关键改动：
- v4 的 patches 1-9 已被合入 for-7.2-fixes 和 for-7.3，v5 丢弃这些并 rebase。
- 新增 patch 01：per-task op 的 owner 断言（sashiko AI 发现的 placer-vs-owner 隐患）。
- 新增 patch 19：SCX_ENQ_IGNORE_CAPS 防止 in-place requeue 误拒（sashiko AI 发现 SAVE/RESTORE requeue 会重跑 cid admission）。
- patch 12 的 stub 也拒绝 dead root 调度器。
- scx_qmap dispatch 路径改进：高优先级 dispatch 用 shard 的 own cids mask，cgroup_id 只读一次。

与其他相关 patch 系列的关联

本系列是 sched_ext sub-scheduler 支持的延续，与之前已合入的 scx_bpf_sub_dispatch() 和 cgroup subtree attach/detach 机制配套。
依赖 sched_ext/for-7.3 基线（含之前 v4 的 1-9 补丁）。
与 BPF arena 机制紧密耦合：cmask、pshard 等核心数据结构均使用 arena 内存。

一句话总结

本系列为 sched_ext 子调度器添加基于 shard 级 capability 的 CPU 委托机制，使父调度器能通过 grant/revoke 精细控制子调度器的 CPU 访问权限，在 enqueue、kick、抢占和 idle 等所有路径实施一致的安全隔离。

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

LLM 分析