Module mlfq_tree 

CART regression tree for next-CPU-burst prediction.

The tree predicts the next burst in nsecs from per-task features and the prediction maps to a queue band (pred < T_INT -> Q1, pred < T_BOUND -> Q2, else Q3). It is trained offline in the daemon on samples emitted by the BPF side and published into a double-buffered two-entry array map in src/bpf/intf.h, which the classification path walks.

The node format, the BFS level-order serialization and the prediction walk are shared with the BPF side: TreeNode is the byte-for-byte mirror of struct mlfq_tree_node (24 bytes under #[repr(C)]), and predict implements the same masked, depth-capped descent as mlfq_tree_walk() in src/bpf/intf.h. serialize_validate() checks a tree against the invariants the walk relies on; the daemon must not commit a tree that fails it.

Growth is classic CART variance reduction: each split minimizes the sum of squared errors of the two child groups, thresholds are exact u64 nsec midpoints between distinct feature values, and growth stops at max_depth, min_samples_leaf, max_nodes or a minimum relative variance reduction.

Structs

FitScratch

Scratch buffers for the CART fit, sized to the maximum window and node budget. The buffers are allocated once with the capacities below and reused across fits by clearing in place, so the training path does not allocate after the first fit. The queue holds owned sample vectors per node; those vectors are still allocated per node, but the major buffers (weights, sorted, left/right) are reused. This keeps the 60s training free of steady-state allocations while preserving the exact CART logic.

NodeSpec 🔒

One node in the BFS queue during fit. The samples are the weighted samples that reached this node. This is an internal detail of the fit and is not part of the published tree.

SerializedTree

A fitted tree in the shared serialized form: BFS level order, index 0 = root, parents before children. The daemon writes these nodes at the front of a map entry’s node buffer (the entry and its tail are zeroed, which is the untrained shape); serialize_validate() must pass before the daemon commits the tree.

TreeFeats

Per-task feature vector, the mirror of struct mlfq_tree_feats.

TreeNode

One tree node, the byte-for-byte mirror of struct mlfq_tree_node.

TreeSample

One training sample, the mirror of struct mlfq_tree_sample.

Constants

DEFAULT_MIN_REL_VAR_REDUCTION

Default minimum relative variance reduction for a split.

MLFQ_TREE_MAX_DEPTH 🔒

Walk depth bound of the shared store entry, from src/bpf/intf.h.

MLFQ_TREE_MAX_NODES 🔒

Node budget of the shared store entry, from src/bpf/intf.h. A power of two, so the walk’s index mask is MAX_NODES - 1.

MLFQ_TREE_META_ACTIVE_SHIFT 🔒

Bit position of the active-buffer flag in the committed-tree meta (bit 1, the value of MLFQ_TREE_META_ACTIVE).

MLFQ_TREE_NR_FEATURES 🔒

Number of populated features; ids 0..8 index the walk’s feat[9] slots, sleep_var_ratio at id 9 is carry-along for the next ABI, gpu_submit at 8 quantised 0..4.

MLFQ_TREE_SAMPLE_VERSION

Record-layout version tag of the emitted training samples, from enum mlfq_consts in src/bpf/intf.h.

Functions

best_split 🔒

Search the best binary split for a node’s samples.

best_split_with_scratch 🔒

Variant of best_split that reuses a caller-provided buffer for sorting. The buffer is cleared and filled from samples for each feature, so the per-feature allocation is avoided after the first call.

feat_value 🔒

Feature value for a feature id, matching the BPF walk’s feat[9] slot layout in src/bpf/intf.h (mlfq_tree_walk). Ids 0..8 are the split features (prev_burst, sleep, ema, io_wait, wake_cnt, wake_lat, queue_wait, sq_ema, gpu_submit), id 9 the cadence ratio (carry-along, split when NR_FEATURES promotes it), and the rest zero.

fit

Grow a CART regression tree over samples.

fit_with_scratch

Fit a tree reusing the caller-provided scratch arena. After the first call the arena retains its capacity, so subsequent fits do not allocate. The logic is identical to fit(), only the temporary buffers are reused.

label_totals 🔒

Sum of weights, weighted sum and weighted sum-of-squares of a node’s labels, in f64 for the variance math. Each sample carries its recency weight alongside it.

leaf_prediction 🔒

Clamp a leaf mean to the u32 prediction field of the shared node.

mae

Mean absolute error between predictions and actuals.

midpoint 🔒

Overflow-safe midpoint between two distinct u64 values.

partition 🔒

Partition a node’s samples by a split, mirroring the walk’s <= routing. feat_value <= threshold goes left. The recency weights ride along with their samples.

pearson

Pearson product-moment correlation of two equally long vectors.

predict

Walk a serialized tree and predict the next burst, the Rust mirror of mlfq_tree_walk() in src/bpf/intf.h (the BPF wrapper adds only the meta gate and the map lookup around this walk).

sample_version_matches

True when a parsed sample carries the current record-layout version.

sample_weights

Recency weight of each training sample, by its age in the window.

sample_weights_into

Fill the provided buffer with recency weights without allocating. The buffer is cleared and filled to length n; capacity is retained so the second call with the same n does not allocate.

serialize_validate

Validate a tree against the walk’s invariants before publishing.

should_publish

The publish quality gate. The tree replaces the previous model only when its holdout MAE beats the exact per-sample EMA baseline on the same holdout slice and the Pearson correlation clears the quality floor and strictly improves on the currently committed model. The holdout MAE is weighted by the recency weights of the window, so recent samples dominate the gate. Correlation is monotonic: once a model at 0.30 is committed, a later fit at 0.30 or below is held out; 0.52 then 0.72 ratchet toward 1.0 on general workloads. A higher correlation must also beat the baseline, so a high but narrow fit on one game cannot regress the tail.

tree_meta

Serialize the committed-tree meta value from its parts.

weighted_holdout_mae

Weighted MAE for the holdout slice. Each holdout sample carries its recency weight w_i = 2^(-age_i / (n/2)) where n is the full window length, so the gate emphasizes the recent regime without dropping the older tail entirely.

Type Aliases

WeightedSample 🔒

A training sample paired with its recency weight, the unit the fit carries through the node partitions.