yo_reactor/
budget.rs

1//! What the maintenance slice is allowed to spend.
2//!
3//! `04` section 6 asks for a fixed instruction budget rather than a wall clock
4//! budget, and the difference matters. A wall clock budget reads a timer,
5//! which is a syscall or at best a serialising instruction, and it gives a
6//! different amount of work on a busy machine than on an idle one, so the tail
7//! latency it produces is not reproducible. A unit budget is a subtraction, it
8//! is the same on every machine, and a run that overshoots does so by one item
9//! rather than by however long that item took.
10//!
11//! A unit is whatever the caller says it is. The engine picks a cost per item
12//! it does, keeps the scale consistent between the things it does, and the
13//! budget only has to be monotone: more units means more work.
14
15/// Units a maintenance slice gets by default, per turn of the loop.
16///
17/// Sized so that the slice is a small fraction of a full batch of commands
18/// rather than a competitor to it. Expiry sampling is the usual spender and it
19/// walks twenty keys at a time, so this is tens of samples in the worst case
20/// and nothing at all in the common one, where there is no work waiting.
21pub const MAINTENANCE_UNITS: u32 = 4096;
22
23/// A slice's remaining allowance.
24///
25/// The contract is one call: [`Budget::spend`] returns false when the caller
26/// should stop. It is not an error and it is not something to report. A
27/// maintenance pass that runs out of budget has done part of its work and will
28/// be back on the next turn, which is a hundred nanoseconds away.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub struct Budget {
31    left: u32,
32    spent: u32,
33}
34
35impl Budget {
36    /// A budget of `units`.
37    #[must_use]
38    pub const fn new(units: u32) -> Budget {
39        Budget {
40            left: units,
41            spent: 0,
42        }
43    }
44
45    /// A budget of [`MAINTENANCE_UNITS`].
46    #[must_use]
47    pub const fn standard() -> Budget {
48        Budget::new(MAINTENANCE_UNITS)
49    }
50
51    /// A budget of nothing, which is what a turn hands to an engine that has
52    /// asked not to be given a slice.
53    #[must_use]
54    pub const fn none() -> Budget {
55        Budget::new(0)
56    }
57
58    /// Charge `units` and say whether there is anything left to do after it.
59    ///
60    /// The charge always goes through, even when it takes the budget past the
61    /// end. Refusing it would mean the caller has to ask before every item and
62    /// then do the item anyway, which is two branches for the same answer.
63    #[inline]
64    pub const fn spend(&mut self, units: u32) -> bool {
65        self.spent = self.spent.saturating_add(units);
66        self.left = self.left.saturating_sub(units);
67        self.left > 0
68    }
69
70    /// What is left.
71    #[must_use]
72    #[inline]
73    pub const fn left(&self) -> u32 {
74        self.left
75    }
76
77    /// What has gone, which is what a counter reports rather than what the
78    /// slice decides on.
79    #[must_use]
80    #[inline]
81    pub const fn spent(&self) -> u32 {
82        self.spent
83    }
84
85    /// Whether there is any allowance at all.
86    #[must_use]
87    #[inline]
88    pub const fn is_spent(&self) -> bool {
89        self.left == 0
90    }
91}
92
93impl Default for Budget {
94    fn default() -> Budget {
95        Budget::standard()
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn a_budget_runs_out_and_says_so() {
105        let mut b = Budget::new(10);
106        assert!(b.spend(4));
107        assert!(b.spend(5));
108        assert!(!b.spend(1), "the tenth unit is the last one");
109        assert!(b.is_spent());
110        assert_eq!(b.spent(), 10);
111    }
112
113    #[test]
114    fn overspending_is_allowed_and_recorded() {
115        let mut b = Budget::new(10);
116        assert!(
117            !b.spend(1000),
118            "one item can cost more than the whole slice"
119        );
120        assert_eq!(b.left(), 0);
121        assert_eq!(b.spent(), 1000, "what it cost, not what it was allowed");
122    }
123
124    #[test]
125    fn an_empty_budget_stops_before_the_first_item() {
126        let mut b = Budget::none();
127        assert!(b.is_spent());
128        assert!(!b.spend(1));
129    }
130
131    #[test]
132    fn spending_cannot_wrap() {
133        let mut b = Budget::new(u32::MAX);
134        assert!(b.spend(u32::MAX - 1));
135        assert!(!b.spend(u32::MAX));
136        assert_eq!(b.left(), 0);
137        assert_eq!(b.spent(), u32::MAX);
138    }
139}
yo_reactor/budget.rs

yo_reactor/
budget.rs
