use std::hint::spin_loop;
use std::sync::atomic::{AtomicBool, AtomicI64, AtomicU64, Ordering};
use crate::counted::Tally;
const NONE: u64 = u64::MAX;
pub struct Ledger {
cost: fn(u64) -> u64,
busy: AtomicBool,
heap: AtomicI64,
charged: AtomicI64,
allowance: AtomicU64,
events: AtomicU64,
base: AtomicI64,
base_charged: AtomicI64,
peak: AtomicI64,
max_residual: AtomicI64,
max_at: AtomicU64,
first_at: AtomicU64,
first_heap: AtomicI64,
first_charged: AtomicI64,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Observation {
pub events: u64,
pub heap: i64,
pub charged: i64,
pub peak_above_arm: i64,
pub max_residual: i64,
pub max_at: u64,
pub first_violation: Option<Violation>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Violation {
pub event: u64,
pub heap: i64,
pub charged: i64,
}
struct Held<'a>(&'a AtomicBool);
impl Drop for Held<'_> {
fn drop(&mut self) {
self.0.store(false, Ordering::Release);
}
}
fn signed(n: u64) -> i64 {
i64::try_from(n).unwrap_or(i64::MAX)
}
impl Ledger {
#[must_use]
pub const fn new(cost: fn(u64) -> u64) -> Self {
Self {
cost,
busy: AtomicBool::new(false),
heap: AtomicI64::new(0),
charged: AtomicI64::new(0),
allowance: AtomicU64::new(0),
events: AtomicU64::new(0),
base: AtomicI64::new(0),
base_charged: AtomicI64::new(0),
peak: AtomicI64::new(0),
max_residual: AtomicI64::new(0),
max_at: AtomicU64::new(0),
first_at: AtomicU64::new(NONE),
first_heap: AtomicI64::new(0),
first_charged: AtomicI64::new(0),
}
}
fn hold(&self) -> Held<'_> {
let mut tries = 0_u32;
while self
.busy
.compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
.is_err()
{
tries = tries.saturating_add(1);
if tries < 64 {
spin_loop();
} else {
std::thread::yield_now();
}
}
Held(&self.busy)
}
pub fn arm(&self, allowance: u64) -> (i64, i64) {
let _held = self.hold();
let heap = self.heap.load(Ordering::Relaxed);
let charged = self.charged.load(Ordering::Relaxed);
self.allowance.store(allowance, Ordering::Relaxed);
self.events.store(0, Ordering::Relaxed);
self.base.store(heap, Ordering::Relaxed);
self.base_charged.store(charged, Ordering::Relaxed);
self.peak.store(heap, Ordering::Relaxed);
self.max_residual.store(0, Ordering::Relaxed);
self.max_at.store(0, Ordering::Relaxed);
self.first_at.store(NONE, Ordering::Relaxed);
(heap, charged)
}
fn event(&self, heap: i64, charged: i64) {
let _held = self.hold();
let h = self.heap.load(Ordering::Relaxed).saturating_add(heap);
let c = self.charged.load(Ordering::Relaxed).saturating_add(charged);
self.heap.store(h, Ordering::Relaxed);
self.charged.store(c, Ordering::Relaxed);
let n = self.events.load(Ordering::Relaxed).saturating_add(1);
self.events.store(n, Ordering::Relaxed);
if h > self.peak.load(Ordering::Relaxed) {
self.peak.store(h, Ordering::Relaxed);
}
let residual = h
.saturating_sub(self.base.load(Ordering::Relaxed))
.saturating_sub(c.saturating_sub(self.base_charged.load(Ordering::Relaxed)));
if residual > self.max_residual.load(Ordering::Relaxed) {
self.max_residual.store(residual, Ordering::Relaxed);
self.max_at.store(n, Ordering::Relaxed);
}
let allowance = signed(self.allowance.load(Ordering::Relaxed));
if residual > allowance && self.first_at.load(Ordering::Relaxed) == NONE {
self.first_at.store(n, Ordering::Relaxed);
self.first_heap.store(h, Ordering::Relaxed);
self.first_charged.store(c, Ordering::Relaxed);
}
}
pub fn charge(&self, bytes: u64) {
self.event(0, signed(bytes));
}
pub fn release(&self, bytes: u64) {
self.event(0, signed(bytes).saturating_neg());
}
#[must_use]
pub fn observe(&self) -> Observation {
let _held = self.hold();
let first_at = self.first_at.load(Ordering::Relaxed);
Observation {
events: self.events.load(Ordering::Relaxed),
heap: self.heap.load(Ordering::Relaxed),
charged: self.charged.load(Ordering::Relaxed),
peak_above_arm: self
.peak
.load(Ordering::Relaxed)
.saturating_sub(self.base.load(Ordering::Relaxed)),
max_residual: self.max_residual.load(Ordering::Relaxed),
max_at: self.max_at.load(Ordering::Relaxed),
first_violation: (first_at != NONE).then(|| Violation {
event: first_at,
heap: self.first_heap.load(Ordering::Relaxed),
charged: self.first_charged.load(Ordering::Relaxed),
}),
}
}
}
impl Tally for Ledger {
fn shrunk(&self, old: usize, new: usize) {
self.event(
signed((self.cost)(new as u64)).saturating_sub(signed((self.cost)(old as u64))),
0,
);
}
fn growing(&self, size: usize) {
self.event(signed((self.cost)(size as u64)), 0);
}
fn failed(&self, size: usize) {
self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
}
fn grew(&self, _size: usize, _zeroed: bool) {}
fn shrank(&self, size: usize) {
self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
}
}
#[cfg(test)]
mod tests {
use super::{Ledger, Violation};
use crate::counted::Tally;
fn bytes(n: u64) -> u64 {
n
}
#[test]
fn a_charge_before_its_block_and_a_release_after_its_free_never_pass() {
let l = Ledger::new(bytes);
l.arm(0);
l.charge(64);
l.growing(64);
l.shrank(64);
l.release(64);
let o = l.observe();
assert_eq!(o.events, 4);
assert_eq!((o.heap, o.charged), (0, 0));
assert_eq!(o.peak_above_arm, 64);
assert_eq!(o.max_residual, 0);
assert_eq!(o.first_violation, None);
}
#[test]
fn an_allocation_before_its_reservation_is_the_first_violation() {
let l = Ledger::new(bytes);
l.arm(16);
l.growing(64);
l.charge(64);
l.growing(32);
let o = l.observe();
assert_eq!(
o.first_violation,
Some(Violation {
event: 1,
heap: 64,
charged: 0
})
);
assert_eq!((o.max_residual, o.max_at), (64, 1));
l.arm(64);
assert_eq!(l.observe().first_violation, None, "the arm starts again");
assert_eq!(l.observe().heap, 96, "the live heap is not reset");
}
#[test]
fn the_cost_is_the_given_unit() {
let l = Ledger::new(|n| n.div_ceil(16) * 16 + 16);
l.growing(1);
assert_eq!(l.observe().heap, 32);
l.shrank(1);
assert_eq!(l.observe().heap, 0);
}
}