sched_ext：vtime 排序约束的文档化与强制

系列概况

标题: [PATCH v3 0/2] sched_ext: document and enforce vtime ordering constraints
作者: Tao Cui cuitao@kylinos.cn
版本: v3，共 2 个 patch
规模: 2 个文件，4 行新增 / 2 行删除
修改文件:
- kernel/sched/ext/ext.c（+3/-1）
- tools/sched_ext/scx_flatcg.bpf.c（+1/-1）
代码统计: 合计 +4/-2
Message-ID（系列首页）: 20260902024812.794879-1-cui.tao@linux.dev
完整性: 闭环。Tejun Heo 已将 1-2 合入 sched_ext/for-7.4（仅规范主题大小写），同时 Sashiko bot 附上 AI review 提示两条预存隐患。

补丁目的

sched_ext 在 BPF 侧通过 scx_bpf_dsq_insert_vtime() 按 time_before64() 把任务排进 DSQ。该比较函数按 循环序号 解释 u64 vtime（相差必须落在 2^63 窗口内，"早"才有定义），但这条隐式约束一直没人写下来。

系列两件事：

1/2：在 ext.c 注释里把"rolling-cursor"约束显式写出来。
2/2：修 scx_flatcg 的 cgv_node_less()。它原本用裸 <，一旦 cvtime 回卷就把刚回卷的 cgroup 节点顶到 rbtree 最前端，使其他 cgroup 长期饥饿。

旧流程的问题

cgv_node_less() 的比较器：

return cgc_a->cvtime < cgc_b->cvtime;

cvtime 由 cgrp_cap_budget() 充电，是 u64 单调递增；每 CPU 选中一个 cgroup 即整段扣一个 slice，回卷比直觉更早到来。
一旦 cvtime 翻过 2^63，刚回卷的数反而最小，rbtree 把它判成最小节点 → 该 cgroup 立刻冲到树头。
后续 未回卷 的节点被卡在它后面，反复拿不到切片，造成事实上的调度错位与饥饿。

新流程

比较器换成 time_before(cgc_a->cvtime, cgc_b->cvtime)：按循环序号解释 u64，回卷/未回卷的节点仍能维持正确先后。
文档侧明确写出 "values ... should stay less than 2^63 apart for time_before64() ordering to remain well-defined"。
同时给出双向边界论证：cgrp_cap_budget() 把 lag 锁在调度节奏内，lead 由 slice + 重入时的 cvtime_delta 锁住，窗口总小于 2^63，循环比较前提成立。

关键实现

static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
{
        struct cgv_node *cgc_a = container_of(a, struct cgv_node, rb_node);
        struct cgv_node *cgc_b = container_of(b, struct cgv_node, rb_node);

-       return cgc_a->cvtime < cgc_b->cvtime;
+       return time_before(cgc_a->cvtime, cgc_b->cvtime);
}

time_before() 在 sched_ext 工具目录中定义为循环 u64 比较：等价于 (s64)(a - b) < 0，也即 delta 在 [-2^63, 0) 区间算"早"。

文档补丁只动注释：

- * ordering and vice-versa.
+ * ordering and vice-versa. vtime is a rolling cursor and values used for
+ * ordering within a given DSQ should stay less than 2^63 apart for
+ * time_before64() ordering to remain well-defined.

类比

把 cvtime 想成一条 永远向前走的手表，但表盘只有 12 小时，秒针绕一圈回到 0——原来的"大值"反而成了"刚刚发生"。

裸 <：戴一块 24 小时制机械表，每次走过午夜都得出错（刚翻 0 点的值 < 还没翻的 23:59，于是被当成最早）。
time_before()：把表盘视为环形，"短弧最短"才算早晚。

调度器使用者也要被告知：你 不能在表盘上写太长的记录——同一队列里任意两个任务的 vtime 距离必须永远 < 半圈，否则"近"的方向本身就含糊了。

+---------------------------+        +---------------------------+
|   cvtime ring (u64 wrap)  |        |   scx_flatcg rbtree view  |
|                           |        |                           |
| 0 -- 2^31 ---- 2^63 ----- | -----> | before fix:               |
|        |                  |        |   wrap node -> tree head  |
|        v                  |        |   others     -> starved   |
|     cvtime wraps back to 0|        +---------------------------+
+---------------------------+                  |
                                               v after fix (time_before)
+---------------------------+        +---------------------------+
| < 2^63 apart window rule  |        | order follows cyclic gap  |
|   a and b must stay within|        |   wrap vs unwrap: correct |
|   half-ring difference    |        |   starvation: gone        |
+---------------------------+        +---------------------------+

Highlight：风险与注意点

Sashiko bot 提示另外两条预存问题（不在本系列范围）：
- High：在 cvtime 已回卷的情况下做无符号差除法，会让过期 cgroup 的虚拟时间被人为放大大数倍，需后续单独修。
- Medium：cvtime_delta 用 __sync_fetch_and_sub(ptr, *ptr) 提取存在竞态，可能造成重复记账。
v3 相对 v2 收紧措辞（"less than 2^63 apart"，非 "within"），补全 lag/lead 双向边界；Fixes tag 校正为上游 a4103eacc2ab（Tejun 原作）。
v3 相对 v1 删掉了 kernel priq 比较器改动：循环排序是 BPF scheduler 文档契约，普通比较会在自然回卷点制造无界饥饿（Andrea/Tejun 反馈）。

版本变化

v1：包含 kernel priq 改用循环比较器；flatcg fix 雏形。
v2：收到 Andrea/Tejun 反馈后，删除 priq 改动、新增文档 patch；措辞改为 "within"。
v3：文档措辞收紧为 "less than 2^63 apart"；flatcg patch 用 time_before()、去冗余注释、Fixes tag 校准到 a4103eacc2ab。

一句话总结

把 sched_ext DSQ vtime 的"必须落在 2^63 窗口内"这条隐式规则写进注释，同时把 scx_flatcg 的裸 < 比较换成 time_before()，防止 cvtime 回卷后早回卷 cgroup 抢占、未回卷的饥饿。

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

LLM 分析