sched_ext: dsq_vtime 滚动游标约束文档化与 flatcg 比较器修复

系列概况

标题: [PATCH v2 0/2] sched_ext: document and enforce vtime ordering constraints
作者: Tao Cui cuitao@kylinos.cn
版本: v2，共 2 个 patch
规模: 2 个文件，+7 / -1
修改文件: kernel/sched/ext/ext.c、tools/sched_ext/scx_flatcg.bpf.c
代码统计: ext.c +5；scx_flatcg.bpf.c +2 / -1
Message-ID: 20260901140343.764080-1-cui.tao@linux.dev
完整性: 0/2 + 1/2 + 2/2 + sashiko-bot 复审 + Tejun ×2 + Tao 致谢，闭环

补丁目的

scx_bpf_dsq_insert_vtime() 通过 time_before64() 对同一 DSQ 内任务排序，但 u64 循环比较所依赖的 half-range（差值 < 2^63）这条隐式约束从未写进文档。同时示例调度器 scx_flatcg 的 rbtree comparator 用裸 u64 <，一旦 cvtime 绕回就会破坏 strict weak ordering，导致 cgroup 永久饥饿或调度错乱。

本系列做两件事：

把"vtime 是滚动游标、同一 DSQ 内任意两值差值 < 2^63"写进 ext.c 的 kdoc。
把 scx_flatcg 的 cgv_node_less() 换成 wrap-safe 循环比较。

旧流程的问题

static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
{
    ...
    return cgc_a->cvtime < cgc_b->cvtime;
}

裸 u64 < 没有循环语义，wrap 后原本最久的节点 u64 值反而最小，rbtree 把它推到最左抢调度。
文档里完全没写"DSQ 内 vtime 差值必须 < 2^63"，BPF 调度器作者无从知道这条硬约束。
在 hierarchy 总和 10000 的环境下，weight=1 的 cgroup 以 10000x wall time 推进 cvtime，加上每 CPU 选取 cgroup 时按 slice 全量 charge，wrap 实际比 commit 描述的"数周连续饱和"更近。

新流程

在 ext.c 的 scx_bpf_dsq_insert_vtime() kdoc 中新增一段说明 rolling-cursor 与 half-range 要求。
把 cgv_node_less() 改成 (s64)(a - b) < 0（v3 进一步收敛为 time_before()）。在 cgrp_cap_budget() 把节点钳到 cvtime_now - max_budget 之后、且每 CPU slice charge + 待结算 cvtime_delta 也限制了 lead 的条件下，循环比较与真实序一致。

Patch 概览

patch	文件	改动
1/2	kernel/sched/ext/ext.c	kdoc +5 行
2/2	tools/sched_ext/scx_flatcg.bpf.c	比较器 +2 / -1

关键实现

1/2 文档化 half-range

在 BPF 入口注释里点出 vtime 单调滚动 + DSQ 内差值 < 2^63，让 BPF 调度器作者写 comparator 时知道这条硬约束。v3 须改写为 "less than 2^63 apart" 并折进上一段。

2/2 wrap-safe comparator

return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;

或 v3 改为 time_before()。在 cgrp_cap_budget 保证差值 < 半范围的条件下与真实序一致；wrap 时不再破坏 strict weak ordering。

评审闭环

Tao v2 cover (0/2)
   |
   +-- 1/2 kdoc: dsq_vtime half-range doc
   +-- 2/2 flatcg: wrap-safe comparator
   |
   v
Reviewers
   |
   +-- sashiko-bot: 2 pre-existing [High]
   |     - cap_budget RMW race
   |     - early yield penalizes cvtime
   |
   +-- Tejun on 1/2:
   |     - say "less than 2^63 apart"
   |     - fold into above paragraph
   |
   +-- Tejun on 2/2:
   |     - plain < puts wrapped node at FRONT
   |     - wrap happens sooner than "weeks"
   |     - cap_budget bounds lag only
   |     - lead bounded by slice + cvtime_delta
   |     - Fixes tag -> a4103eacc2ab
   |     - use time_before(), drop comment
   |
   v
Tao v3 plan: accept all, send v3 soon

cvtime 绕回时的比较行为

cvtime values        plain u64 <     cyclic (s64)(a-b)<0
---------------      ------------    --------------------
a = 10               false           false (a after b)
b = MAX - 5

   --- after wrap ---

a = 0 (newest,       true  WRONG     depends on whether
  actually oldest)   a goes left     cap_budget pulls a
b = MAX - 5          a steals        back near cvtime_now
                     scheduling      then: false (correct)

plain < breaks strict weak ordering at the wrap instant.
cyclic < is correct iff all nodes stay within 2^63 of each other.

类比

把 vtime 想成一条 u64 模 2^64 的圆形跑道，调度器按"谁跑得最少就先跑"调度。

裸 u64 < 像用尺子量跑道长度 0..2^64：选手跑过一圈后看起来在起点附近，尺子上"几乎不动"，被排到队首抢调度——典型的饥饿错乱。
(s64)(a - b) < 0 取两点最短弧方向，CFS 对 vruntime 正是这样做的。只要所有选手都在同一圈（差 < 半周），最短弧就和真实顺序一致。
cgrp_cap_budget 就像在跑道边放一个裁判，把落后太多的选手拉回大部队附近；外加每 CPU 选 cgroup 时按 slice 全量 charge 与待结算 cvtime_delta 共同把 lead 也限住——只有这样循环比较才能作为 rbtree comparator 使用。

Highlight：风险与注意点

half-range 措辞：必须写 "less than 2^63 apart"，差值恰好 2^63 时 time_before64 双向都成立，违反 strict weak ordering，rbtree 会拒收节点。
wrap 比 commit 描述更近：每个 CPU 选 cgroup 都按 slice 全量 charge，多 CPU 累加后触发条件比"数周连续饱和"更容易到达。
Fixes 标签错：原 7b742aa2c2c9 不在 mainline，upstream 是 a4103eacc2ab。
lead也不止 lag 受限：作者只写 lag 受 cgrp_cap_budget 限制，Tejun 提醒 lead 由 slice charge + 待结算 cvtime_delta 共同钳制。
裸 < 的真实效果：作者在 commit 里写"wrapped 节点落到队尾"，实际 u64 裸 < 把 wrap 后更小的节点推到最左，反抢调度——v3 描述需纠错。
sashiko-bot 报告的另两条 pre-existing 问题（cgrp_cap_budget 的 RMW 竞态、提前 yield 不 refund 而惩罚 cvtime）属于独立 bug，本系列不动，但需要后续单独 patch。
v3 验证：复跑确认 pre-existing 问题未被 2/2 改动放大；同时观察 cap_budget 是否需要补一段 lead-bound 注释，让 BPF 作者更清楚 lead 的限制。

版本变化

v1 → v2：
- 删除原 1/2（改 kernel priq 比较器为循环比较）——Andrea、Tejun 指出循环排序是文档化契约，kernel priq 没有 half-range 保证，裸改会在自然 wrap 处引入不可控饥饿。
- 新 1/2 改为只补文档，写 rolling-cursor 要求。
- 2/2（flatcg 改 wrap-safe）保持不变。

一句话总结

v2 把 sched_ext dsq_vtime 的 half-range 隐式约束写进文档，并把示例 scx_flatcg 的 rbtree 比较器改成 wrap-safe 循环比较；Tejun 复审指出措辞应为 "less than 2^63 apart"、wrap 实际更近、lag 与 lead 都需受限、Fixes 应指向 upstream a4103eacc2ab 并改用 time_before()；作者承诺发 v3。

[PATCH v2 0/2] sched_ext: document and enforce vtime ordering constraints

LLM 分析