                  fcg_dispatch() true-up on slice boundary
                  ========================================

   slice boundary event
          |
          v
   +-------------------+
   | cgrp_slice_ns     |  (budget)
   | cur_at            |  (slice start)
   | now               |  (dispatch cb time)
   +---------+---------+
             |
             v
        delta = now - cur_at - slice_ns          (s64, signed)
             |
    +--------+--------+
    |                 |
    v (delta >= 0)    v (delta < 0)
  EXPIRE path        EMPTY path
  (overrun)           (unused quota)
    |                 |
    v                 v
  fetch_and_add       fetch_and_sub
  (u64)delta / hw     (u64)-delta / hw
    |                 |
    +--------+--------+
             |
             v
      cgc->cvtime_delta       (weighted virtual time)

sched_ext/scx_flatcg：修复切片到期 cvtime true-up 符号与 u64 回卷

系列概况

标题：[PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry
作者：Tao Cui cuitao@kylinos.cn
版本：单封 patch（v1）
规模：1 文件，+11/-3
修改文件：tools/sched_ext/scx_flatcg.bpf.c
代码统计：仅改 fcg_dispatch() 中 cvtime true-up 表达式
Message-ID：20260815045905.3431991-1-cui.tao@linux.dev
完整性：完整；后续 Sashiko 提示 pre-existing RB-tree 风险；Tejun Heo Applied to sched_ext/for-7.3

补丁目的

scx_flatcg 是 tools/sched_ext/ 下的示例 BPF scheduler，用扁平化 cgroup 层级 + CFS 风格虚拟时间（cvtime）做公平调度。它把每个 cgroup 一段 slice 的实际虚拟时间消耗，按权重 hweight 累加进 cvtime_delta。

本 patch 修复 fcg_dispatch() 中切片到期（CNS_EXPIRE）或 DSQ 空但 slice 还在期内（CNS_EMPTY）时的 true-up 计算。原式同时存在「符号反向」与「u64 下溢 + BPF 无符号除法丢失符号位」两个 bug，导致每次过期往 cvtime_delta 加接近 2^64/hweight 的垃圾值。

旧流程的问题

__sync_fetch_and_add(&cgc->cvtime_delta,
    (cpuc->cur_at + cgrp_slice_ns - now) * FCG_HWEIGHT_ONE / (cgc->hweight ?: 1));

两条隐性缺陷：

符号反了：true-up 语义是「实际花掉的虚拟时间 − 已经记账的 slice」。
- CNS_EXPIRE：overrun = now - cur_at - slice，应当加。
- CNS_EMPTY：unused = slice - (now - cur_at)，应当减。
  原式 (cur_at + slice - now) 是「应减」量取负，方向颠倒。
u64 回卷 + 无符号除法：CNS_EXPIRE 下 cur_at + slice - now 下溢成 ~2^64 - overrun；乘法保留补码，但随后的 u64 / hweight 把符号位当数据除掉，结果接近 2^64 / hweight。作者在 3 叶子 cgroup 树 + 4 CPU VM 上实测每次过期约加 5e15。

cgrp_cap_budget() 的 hweight 预算钳制掩盖了大部分垃圾，所以权重分布「看起来还凑合」，但账从根本上就是错的。

新流程

s64 delta = now - cpuc->cur_at - cgrp_slice_ns;

/* keep the dividends positive, BPF division is unsigned */
if (delta >= 0)
    __sync_fetch_and_add(&cgc->cvtime_delta,
        (u64)delta * FCG_HWEIGHT_ONE / (cgc->hweight ?: 1));
else
    __sync_fetch_and_sub(&cgc->cvtime_delta,
        (u64)-delta * FCG_HWEIGHT_ONE / (cgc->hweight ?: 1));

要点：

显式 s64 delta = now - cur_at - slice，得到正确的有符号差。
进入 / 前取 -delta 强制被除数 ≥ 0，因为 BPF 除法是 u64 / u64，符号位会被吃掉。
按 delta 正负分流到 fetch_and_add / fetch_and_sub，分别处理 EXPIRE 加 overrun、EMPTY 减 unused。
作者实测：修正后量级回到 slice 级别，方向正确。

Patch 概览

单 hunk，只动 fcg_dispatch() 中 __sync_fetch_and_add(&cgc->cvtime_delta, ...) 块。
引入局部 s64 delta，加 if/else 显式分支。
注释「BPF division is unsigned」明确说明保正动机。
提交带 Fixes: a4103eacc2ab、Suggested-by: Tejun Heo、Signed-off-by: Tao Cui。

关键实现

1. 把"账"算对

true-up 类似月底对账：cgroup 已按 slice 预算预扣 CPU 虚拟时间，但实际跑片可能长于或短于预算；这段差额在 slice 边界修正一次。原版把"长多少"和"短多少"两件事都搞反了。

2. BPF 除法是 `u64`

即使 delta 是 s64，在被除数进入 / 之前必须保正。这与用户态内核 div_s64() / div64_s64() 思路一致，但 BPF 子集没有这些 helper，所以只能手工 if (delta >= 0) 分流并先取 -delta。

3. `fetch_and_add` vs `fetch_and_sub`

__sync_fetch_and_sub(&x, n) 在语义上等价于 x += -n，但读 patch 时意图更清晰：减法路径明确表达"少记这么多"。多核并发累加 cvtime_delta 时两种原语都正确。

4. 验证场景

作者给出实测对比：修复前每次过期 cvtime_delta 加约 5e15（接近 2^64/hweight），修复后量级回到 slice 级别。commit body 把"症状—根因—实测"三件事串起来，可读性强——光看代码很难判断 u64 回卷是否真触发。

类比

把 cgroup 的 slice 想成火车票印的"座位时段"：

cur_at = 你坐下的真实时刻；cgrp_slice_ns = 票面时长；now = 你站起来让位的时刻。
坐过站（now > cur_at + slice）：票务系统按"超坐"时长补一笔占用 → delta += 超时部分。
提前下车（now < cur_at + slice）：票务系统应归还没跑完的那一段 → delta -= 闲置部分。

旧代码把"补票"算成"退款"，等于谁迟到谁反而得奖励；更糟的是，u64 时间戳回卷后，超坐 1 秒的差值会算成 ~2^64——把"超时 1 秒"算成"超时几百年"，除以权重后仍是天文数字。账面上谁都不欠费，但预算都以"几百年"为单位算，与正常的纳秒到微秒量级完全脱节。

新代码先 s64 delta 求差，再分两路：正的就 add，负的就 sub（并先取 -delta 保正）—— 先看清是"补票"还是"退款"，再走对应窗口。

Highlight：风险与注意点

pre-existing RB-tree 风险（Sashiko High）：cgv_node_less() 是红黑树 cvtime 排序的比较函数；cvtime 长期累加逼近 u64 上限后比较会回卷，触发优先级反转——本应最该跑的 cgroup 被认为最大。本 patch 未修，可能因为：跑满 2^64 需极久、scx_flatcg 是 tools/ 示例、改比较函数涉及 RB-tree 排序不变量需更谨慎 fix。建议后续单独发保护性 patch。
测试覆盖不足：patch 没附 selftest。新 if/else 分支应补 unit test：构造 cur_at + slice - now 跨越 0 的场景，断言 cvtime_delta 方向与量级。
示例代码的传染性：scx_flatcg 是用户跑 sched_ext 时常选的模板。账错会掩盖"为什么我设的权重不起作用"的问题，修复教学价值高。
教学价值：本 patch 是 "BPF u64 除法吃掉符号位" 的典型案例，可考虑放进 tools/testing/selftests/bpf 注释或 BPF 文档，提醒后续 scheduler 编写者。
SoB 链路：SoB 只来自作者个人邮箱 cuitao@kylinos.cn，无公司 From 头；lore 接收正常，但企业内部审计链可能需要补 kylinos 维护者。

版本变化

仅 v1。后续：

Sashiko 提示 pre-existing RB-tree 优先级反转，未修。
Tejun Heo：Applied to sched_ext/for-7.3。

与其他相关 patch 系列的关联

Fixes: a4103eacc2ab ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy") —— scx_flatcg 最初被合入的提交。
本 patch 只动 tools/sched_ext/scx_flatcg.bpf.c，与 kernel/sched/ext.c 的核心调度路径无关；预期跟随 sched_ext/for-7.3 周期 ship。

一句话总结

scx_flatcg 在切片到期/DSQ 空时给 cgroup cvtime_delta 做 true-up，原表达式符号反了且 u64 减法下溢、BPF 无符号除法吃掉符号位，导致每次过期加接近 2^64/hweight 的垃圾值；patch 改成先求带符号 delta 再按正负分流到 fetch_and_add / fetch_and_sub，并把被除数保正以适配 BPF 的无符号除法。

[PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

LLM 分析