用 per-ctx 无锁 PRNG 取代 damon_rand

背景

DAMON 用一个叫 kdamond 的内核线程监控进程的内存访问，方法是在被监控区域的地址空间里随机取一个地址（sampling_addr），检查它对应 PTE 的 accessed 位，以此估计访问模式。取这个随机地址发生在采样的热路径上。

┌────────────────────────────────────┐
│ kdamond 在采样热路径反复取随机地址 │
└─────────────────┬──────────────────┘
                  ▼
┌────────────────────────────────────┐
│    每次都走带锁的加密随机数生成    │  取本地锁、访问 per-CPU 熵池、周期性 ChaCha
└─────────────────┬──────────────────┘  重填
                  ▼
┌────────────────────────────────────┐
│   区域数升高时锁开销主导 kdamond   │  区域多时占满大半个核的 CPU
└────────────────────────────────────┘

damon_rand 取随机地址，背后调的是 get_random_u32_below，一个加密级的随机数接口：它用 local_lock_irqsave 保护一个 per-CPU 的批量熵池，还周期性用 ChaCha20 重填。在监控区域数量小的时候这点锁开销不算什么，但当 nr_regions 升到 2 万以上，lock_acquire/local_lock 这对加上 __get_random_u32_below 本身，就成了 kdamond 性能 profile 的主角，把 kdamond 推到吃掉约 72% 单核。

问题

• kdamond 采样热路径用加密级随机数接口
• 该接口取本地锁、访问 per-CPU 熵池、周期性 ChaCha 重填
• 区域数升高时锁开销主导 kdamond CPU
• 把 kdamond 推到约 72% 单核

方案

核心是看清"这个随机数不必是加密级的"，从而换掉那把锁。

DAMON 的 sampling_addr 只是选一个地址去看 PTE 的 accessed 位，不暴露给用户态、也不做任何安全决策，完全不需要加密强度的随机性。

旧：每次取随机都过加密随机数锁
┌──────────────────────────┐
│ 采样地址走带锁加密随机数 │
└────────────┬─────────────┘
             ▼
┌──────────────────────────┐
│   锁与熵池开销主导 CPU   │
└──────────────────────────┘

新：每上下文一个无锁 PRNG
┌──────────────────────────────────┐
│  kdamond 是某上下文的唯一消费者  │
└────────────────┬─────────────────┘
                 ▼
┌──────────────────────────────────┐
│ 用无锁 PRNG 产采样地址，无需同步 │  采样地址非加密用途，仅作页表访问位探针
└──────────────────────────────────┘

于是把 damon_rand 换成一个 lockless 的 lfsr113 伪随机数生成器（struct rnd_state），每个 damon_ctx 持有一个，在 damon_new_ctx 里用 get_random_u64 播种。关键在于 kdamond 是一个 ctx 的唯一消费者，只有它读这个 PRNG，所以连同步都不需要。

范围映射（把 PRNG 输出投到监控区间里）用传统的 reciprocal multiplication，和原 get_random_u32_below 同路；区间跨度超过 U32_MAX（只有 64-bit 才够得到）时走 slow path，拼两个 u32 输出、用 mul_u64_u64_shr 做 64 位宽运算；32-bit 上这段 slow path 是死代码，被编译器消掉。

收益

作者用 paddr 监控、max_nr_regions=20000 实测：

锁开销移除后，kdamond 在区域数高时少吃了约五分之一核，留给系统其它用途；这也让 DAMON 在大区域数监控（如 proactive reclaim）场景下更便宜，更适合长期常驻。