scx_utils/
ravg.rs

1// Copyright (c) Meta Platforms, Inc. and affiliates.
2//
3// This software may be used and distributed according to the terms of the
4// GNU General Public License version 2.
5
6//! # Running Average Utilities
7//!
8//! Rust userland utilities to access running averages tracked by BPF
9//! ravg_data. See
10//! [ravg.bpf.h](https://github.com/sched-ext/scx/blob/main/scheds/include/common/ravg.bpf.h)
11//! and
12//! [ravg_impl.bpf.h](https://github.com/sched-ext/scx/blob/main/scheds/include/common/ravg_impl.bpf.h)
13//! for details.
14
15/// Read the current running average
16///
17/// Read the running average value at `@now` of ravg_data (`@val`,
18/// `@val_at`, `@old`, `@cur`) given `@half_life` and `@frac_bits`. This is
19/// equivalent to C `ravg_read()`.
20///
21/// There currently is no way to make `bindgen` and `libbpf_cargo` generated
22/// code to use a pre-existing type, so this function takes each field of
23/// struct ravg_data as a separate argument. This works but is ugly and
24/// error-prone. Something to improve in the future.
25pub fn ravg_read(
26    val: u64,
27    val_at: u64,
28    old: u64,
29    cur: u64,
30    now: u64,
31    half_life: u32,
32    frac_bits: u32,
33) -> f64 {
34    let ravg_1: f64 = (1 << frac_bits) as f64;
35    let half_life = half_life as u64;
36    let val = val as f64;
37    let mut old = old as f64 / ravg_1;
38    let mut cur = cur as f64 / ravg_1;
39
40    let now = now.max(val_at);
41    let normalized_dur = |dur| dur as f64 / half_life as f64;
42
43    //
44    // The following is f64 implementation of BPF ravg_accumulate().
45    //
46    let cur_seq = (now / half_life) as i64;
47    let val_seq = (val_at / half_life) as i64;
48    let seq_delta = (cur_seq - val_seq) as i32;
49
50    if seq_delta > 0 {
51        let full_decay = 2f64.powi(seq_delta);
52
53        // Decay $old and fold $cur into it.
54        old /= full_decay;
55        old += cur / full_decay;
56        cur = 0.0;
57
58        // Fold the oldest period whicy may be partial.
59        old += val * normalized_dur(half_life - val_at % half_life) / full_decay;
60
61        // Pre-computed decayed full-period values.
62        const FULL_SUMS: [f64; 20] = [
63            0.5,
64            0.75,
65            0.875,
66            0.9375,
67            0.96875,
68            0.984375,
69            0.9921875,
70            0.99609375,
71            0.998046875,
72            0.9990234375,
73            0.99951171875,
74            0.999755859375,
75            0.9998779296875,
76            0.99993896484375,
77            0.999969482421875,
78            0.9999847412109375,
79            0.9999923706054688,
80            0.9999961853027344,
81            0.9999980926513672,
82            0.9999990463256836,
83            // Use the same value beyond this point.
84        ];
85
86        // Fold the full periods in the middle.
87        if seq_delta >= 2 {
88            let idx = ((seq_delta - 2) as usize).min(FULL_SUMS.len() - 1);
89            old += val * FULL_SUMS[idx];
90        }
91
92        // Accumulate the current period duration into @cur.
93        cur += val * normalized_dur(now % half_life);
94    } else {
95        cur += val * normalized_dur(now - val_at);
96    }
97
98    //
99    // The following is the blending part of BPF ravg_read().
100    //
101    old * (1.0 - normalized_dur(now % half_life) / 2.0) + cur / 2.0
102}
scx_utils/ravg.rs

scx_utils/
ravg.rs
