1use std::hint::spin_loop;
35use std::sync::atomic::{AtomicBool, AtomicI64, AtomicU64, Ordering};
36
37use crate::counted::Tally;
38
39const NONE: u64 = u64::MAX;
41
42pub struct Ledger {
46 cost: fn(u64) -> u64,
47 busy: AtomicBool,
48 heap: AtomicI64,
49 charged: AtomicI64,
50 allowance: AtomicU64,
51 events: AtomicU64,
52 base: AtomicI64,
53 base_charged: AtomicI64,
54 peak: AtomicI64,
55 max_residual: AtomicI64,
56 max_at: AtomicU64,
57 first_at: AtomicU64,
58 first_heap: AtomicI64,
59 first_charged: AtomicI64,
60}
61
62#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
64pub struct Observation {
65 pub events: u64,
67 pub heap: i64,
69 pub charged: i64,
71 pub peak_above_arm: i64,
73 pub max_residual: i64,
76 pub max_at: u64,
78 pub first_violation: Option<Violation>,
80}
81
82#[derive(Clone, Copy, Debug, PartialEq, Eq)]
84pub struct Violation {
85 pub event: u64,
87 pub heap: i64,
89 pub charged: i64,
91}
92
93struct Held<'a>(&'a AtomicBool);
95
96impl Drop for Held<'_> {
97 fn drop(&mut self) {
98 self.0.store(false, Ordering::Release);
99 }
100}
101
102fn signed(n: u64) -> i64 {
103 i64::try_from(n).unwrap_or(i64::MAX)
104}
105
106impl Ledger {
107 #[must_use]
109 pub const fn new(cost: fn(u64) -> u64) -> Self {
110 Self {
111 cost,
112 busy: AtomicBool::new(false),
113 heap: AtomicI64::new(0),
114 charged: AtomicI64::new(0),
115 allowance: AtomicU64::new(0),
116 events: AtomicU64::new(0),
117 base: AtomicI64::new(0),
118 base_charged: AtomicI64::new(0),
119 peak: AtomicI64::new(0),
120 max_residual: AtomicI64::new(0),
121 max_at: AtomicU64::new(0),
122 first_at: AtomicU64::new(NONE),
123 first_heap: AtomicI64::new(0),
124 first_charged: AtomicI64::new(0),
125 }
126 }
127
128 fn hold(&self) -> Held<'_> {
133 let mut tries = 0_u32;
134 while self
135 .busy
136 .compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
137 .is_err()
138 {
139 tries = tries.saturating_add(1);
140 if tries < 64 {
141 spin_loop();
142 } else {
143 std::thread::yield_now();
144 }
145 }
146 Held(&self.busy)
147 }
148
149 pub fn arm(&self, allowance: u64) -> (i64, i64) {
156 let _held = self.hold();
157 let heap = self.heap.load(Ordering::Relaxed);
158 let charged = self.charged.load(Ordering::Relaxed);
159 self.allowance.store(allowance, Ordering::Relaxed);
160 self.events.store(0, Ordering::Relaxed);
161 self.base.store(heap, Ordering::Relaxed);
162 self.base_charged.store(charged, Ordering::Relaxed);
163 self.peak.store(heap, Ordering::Relaxed);
164 self.max_residual.store(0, Ordering::Relaxed);
165 self.max_at.store(0, Ordering::Relaxed);
166 self.first_at.store(NONE, Ordering::Relaxed);
167 (heap, charged)
168 }
169
170 fn event(&self, heap: i64, charged: i64) {
173 let _held = self.hold();
174 let h = self.heap.load(Ordering::Relaxed).saturating_add(heap);
175 let c = self.charged.load(Ordering::Relaxed).saturating_add(charged);
176 self.heap.store(h, Ordering::Relaxed);
177 self.charged.store(c, Ordering::Relaxed);
178 let n = self.events.load(Ordering::Relaxed).saturating_add(1);
179 self.events.store(n, Ordering::Relaxed);
180 if h > self.peak.load(Ordering::Relaxed) {
181 self.peak.store(h, Ordering::Relaxed);
182 }
183 let residual = h
184 .saturating_sub(self.base.load(Ordering::Relaxed))
185 .saturating_sub(c.saturating_sub(self.base_charged.load(Ordering::Relaxed)));
186 if residual > self.max_residual.load(Ordering::Relaxed) {
187 self.max_residual.store(residual, Ordering::Relaxed);
188 self.max_at.store(n, Ordering::Relaxed);
189 }
190 let allowance = signed(self.allowance.load(Ordering::Relaxed));
191 if residual > allowance && self.first_at.load(Ordering::Relaxed) == NONE {
192 self.first_at.store(n, Ordering::Relaxed);
193 self.first_heap.store(h, Ordering::Relaxed);
194 self.first_charged.store(c, Ordering::Relaxed);
195 }
196 }
197
198 pub fn charge(&self, bytes: u64) {
200 self.event(0, signed(bytes));
201 }
202
203 pub fn release(&self, bytes: u64) {
205 self.event(0, signed(bytes).saturating_neg());
206 }
207
208 #[must_use]
210 pub fn observe(&self) -> Observation {
211 let _held = self.hold();
212 let first_at = self.first_at.load(Ordering::Relaxed);
213 Observation {
214 events: self.events.load(Ordering::Relaxed),
215 heap: self.heap.load(Ordering::Relaxed),
216 charged: self.charged.load(Ordering::Relaxed),
217 peak_above_arm: self
218 .peak
219 .load(Ordering::Relaxed)
220 .saturating_sub(self.base.load(Ordering::Relaxed)),
221 max_residual: self.max_residual.load(Ordering::Relaxed),
222 max_at: self.max_at.load(Ordering::Relaxed),
223 first_violation: (first_at != NONE).then(|| Violation {
224 event: first_at,
225 heap: self.first_heap.load(Ordering::Relaxed),
226 charged: self.first_charged.load(Ordering::Relaxed),
227 }),
228 }
229 }
230}
231
232impl Tally for Ledger {
239 fn shrunk(&self, old: usize, new: usize) {
240 self.event(
241 signed((self.cost)(new as u64)).saturating_sub(signed((self.cost)(old as u64))),
242 0,
243 );
244 }
245 fn growing(&self, size: usize) {
246 self.event(signed((self.cost)(size as u64)), 0);
247 }
248
249 fn failed(&self, size: usize) {
250 self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
251 }
252
253 fn grew(&self, _size: usize, _zeroed: bool) {}
255
256 fn shrank(&self, size: usize) {
257 self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
258 }
259}
260
261#[cfg(test)]
262mod tests {
263 use super::{Ledger, Violation};
264 use crate::counted::Tally;
265
266 fn bytes(n: u64) -> u64 {
267 n
268 }
269
270 #[test]
271 fn a_charge_before_its_block_and_a_release_after_its_free_never_pass() {
272 let l = Ledger::new(bytes);
273 l.arm(0);
274 l.charge(64);
275 l.growing(64);
276 l.shrank(64);
277 l.release(64);
278 let o = l.observe();
279 assert_eq!(o.events, 4);
280 assert_eq!((o.heap, o.charged), (0, 0));
281 assert_eq!(o.peak_above_arm, 64);
282 assert_eq!(o.max_residual, 0);
283 assert_eq!(o.first_violation, None);
284 }
285
286 #[test]
289 fn an_allocation_before_its_reservation_is_the_first_violation() {
290 let l = Ledger::new(bytes);
291 l.arm(16);
292 l.growing(64);
293 l.charge(64);
294 l.growing(32);
295 let o = l.observe();
296 assert_eq!(
297 o.first_violation,
298 Some(Violation {
299 event: 1,
300 heap: 64,
301 charged: 0
302 })
303 );
304 assert_eq!((o.max_residual, o.max_at), (64, 1));
305 l.arm(64);
306 assert_eq!(l.observe().first_violation, None, "the arm starts again");
307 assert_eq!(l.observe().heap, 96, "the live heap is not reset");
308 }
309
310 #[test]
311 fn the_cost_is_the_given_unit() {
312 let l = Ledger::new(|n| n.div_ceil(16) * 16 + 16);
313 l.growing(1);
314 assert_eq!(l.observe().heap, 32);
315 l.shrank(1);
316 assert_eq!(l.observe().heap, 0);
317 }
318}