sched_ext：vtime 排序环绕不安全修复（含 maintainer 异议）

系列概况

标题：[PATCH 0/2] sched_ext: fix wraparound-unsafe vtime orderings
作者：Tao Cui cuitao@kylinos.cn
版本：v1（无 vN 编号，本次提交即为初版）
规模：2 个补丁 + cover letter
修改文件：kernel/sched/ext/ext.c、tools/sched_ext/scx_flatcg.bpf.c
代码统计：2 个文件，4 行新增，2 行删除
Message-ID（首封）：20260901024038.730424-1-cui.tao@linux.dev
完整性：完整；含 Sashiko AI 评审、bpf-ci bot 对 Fixes tag 的核对、Andrea Righi 与 Tejun Heo 的审阅，以及作者本人在第 9 封中对自身 Patch 1 方向的自我反驳

补丁目的

该系列针对 sched_ext 中两处用 64 位 vtime 做红黑树排序的比较器，纠正它们在 u64 边界（2^64 环绕）附近的错误。两处表面同源，但 spread 不变量不同，需要方向相反的修复：

scx_dsq_priq_less()（内核）：spread 没有上限，循环比较在 spread 大于 2^63 时会反转。
cgv_node_less()（scx_flatcg BPF）：spread 被 cgrp_cap_budget() 钳制，但用的是绝对 <，环绕瞬间就乱序。

补丁目的是让两处比较器分别匹配自己的不变量，避免饿死 /失序。

旧流程的问题

Patch 1 位置（内核）：scx_dsq_priq_less() 用 time_before64()，等价于 (s64)(a-b) < 0。它只在所有节点差距小于 2^63 时等价于真序。CFS 靠 min_vruntime 钳制维护这个不变量；sched_ext 把 dsq_vtime 直接交给 BPF 写，没有任何钳制。作者用「一半 vtime 接近 0、一半 vtime 大于 2^63」的 probe scheduler 复现：8 个繁忙任务里 4 个独占 CPU，另外 4 个饿死。

Patch 2 位置（scx_flatcg）：cgv_node_less() 用绝对 <。weight=1、层级总和=10000 时，cvtime 按 10000 倍墙钟速率推进，几周连续饱和就可能撞到 2^64 边界。一旦环绕，被环绕节点永远落在队尾。

新流程

两处采用相反修复，判定依据是「spread 不变量是否被维护」：

scx_dsq_priq_less() 改为绝对 a->scx.dsq_vtime < b->scx.dsq_vtime（全序）。代价：自然 2^64 环绕瞬间有极短错序。
cgv_node_less() 改为 (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0（循环序）。前提是 cgrp_cap_budget() 把每个节点钳到 cvtime_now - max_budget 之后。

作者刻意说明：天真地「到处都用 time_before64」并不成立——没有 spread 不变量时，循环比较就是 Patch 1 修复的那个反转。

关键实现

/* kernel/sched/ext/ext.c -- Patch 1 */
static bool scx_dsq_priq_less(struct rb_node *node_a,
                              struct rb_node *node_b) {
    ...
    /* dsq_vtime is arbitrary BPF input: keep a total order */
    return a->scx.dsq_vtime < b->scx.dsq_vtime;
}

/* tools/sched_ext/scx_flatcg.bpf.c -- Patch 2 */
static bool cgv_node_less(const struct bpf_rb_node *a,
                          const struct bpf_rb_node *b) {
    ...
    /* wrap-safe: cap_budget keeps nodes within 2^63 of each other */
    return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;
}

两处 diff 都是「比较运算符 + 一行注释说明不变量前提」。真正的修复点不在行数，而在解释为什么这条比较是这台 rbtree 该用的那种。

类比

Patch 1 像「钟表店按进货号排队」：钟表店不保证所有进货号落在 12 点钟面（u64 半圈）之内，硬要用 12 小时循环表比对，半数订单就会排反；只能改成按绝对号排。
Patch 2 像「银行窗口排队号」：每天从 1 开始重新发号，号码始终在 0–999 内，「下一号」用循环语义没问题；但若某天跳号到 10000 后又归零，绝对 < 会让刚发的号被永久压到队尾。
一句话版本：循环比较和绝对序都「正确」，前提是台子够小、不变量被维护。区别不在代码行，而在不变量是否在场。

Highlight：风险与注意点

maintainer 直接否定 Patch 1：Tejun Heo 回复「This doesn't make any practical sense. dsq_vtime is by (implicit) definition a rolling cursor.」——按 BPF kfunc 文档，dsq_vtime 排序语义就是循环序，Patch 1 切换为绝对序破坏合约。
作者本人在 message 9 自我反驳：Tao Cui 引用 scx_bpf_dsq_insert_vtime() 文档明确以 time_before64() 定义顺序，并举 a = U64_MAX - 5、b = 3 的例子，说明切换为绝对 < 后 b 会被错误地排到前面。这条线索强烈暗示 Patch 1 将在 v2 被撤回或反转方向。
Fixes: tag 错位：bot+bpf-ci 指出 Patch 2 引用的 7b742aa2c2c9 在仓库中不存在，真正引入该 bug 的是 a4103eacc2ab4，v2 必须修订。
Sashiko AI 评审 High 风险：Patch 1 标「破坏循环 vtime 合约，环绕时永久饿死」；Patch 2 标「预先存在的 __sync_fetch_and_sub 自引用导致并发时间双计数」，与本次改动无关但建议单独修复。
Andrea Righi 评审被截断（message 7 body 不完整），公开邮件原文可能有补充论点，需要到 lore.kernel.org 核对完整正文。
隐藏测试覆盖风险：若内核已有针对 DSQ vtime 顺序的 selftest，Patch 1 的方向很可能让现有测试失败——这是 v2 必须先跑 kselftest 再发的原因。

+-------------------+
| vtime comparator  |
+-------------------+
         |
         v
+---------------------------+
| spread invariant kept?   |
+---------------------------+
    |               |
   no              yes
    |               |
    v               v
+----------+    +-------------+
| absolute |    | cyclic |
|  a <  b |    | (s64)(a-b)  |
| (total   |    |    < 0      |
|  order)  |    | (CFS-style) |
+----------+    +-------------+
  Patch 1         Patch 2
  (likely         (expected
 withdrawn       to merge
   in v2)          after
 Fixes: tag is fixed)

版本变化

本系列仅 v1，无 vN→vN+1 对照。依据 maintainer 与作者本人回复，预期 v2 至少：

撤回或反转 Patch 1（回到循环比较，并补充文档强化 dsq_vtime 是 rolling cursor 的语义）；
修正 Patch 2 的 Fixes: tag 为 a4103eacc2ab4；
把 Sashiko 提到的 __sync_fetch_and_sub 自引用问题拆出为独立修复。

一句话总结

同一族 vtime 排序错误，spread 不变量不同就要相反修复——而 maintainer 已明确 dsq_vtime 是循环 cursor，作者的 Patch 1 方向大概率在 v2 被撤回，整条线索本身就是「不变量决定比较器」的活教材。

[PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

LLM 分析