use std::cell::Cell;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use std::sync::{Arc, Mutex, MutexGuard, OnceLock, PoisonError};
use crate::budget::Reservation;
use crate::error::{Error, LimitKind};
use crate::files::File;
use crate::raw::RawStr;
mod growth;
pub(crate) use growth::Growing;
pub use growth::current_growth;
macro_rules! counter_index {
($index:ident, $count:ident, $ty:ident, $order:ident, [$($v:ident),+ $(,)?]) => {
#[allow(clippy::enum_variant_names)]
#[repr(usize)]
enum $order {
$($v),+
}
const $count: usize = [$($order::$v),+].len();
const fn $index(x: $ty) -> usize {
match x {
$($ty::$v => $order::$v as usize),+
}
}
};
}
counter_index!(
kind_index,
LIMIT_KINDS,
LimitKind,
KindOrder,
[
InputMemory,
InputBytes,
BlockOutput,
DecodeWork,
Inflate,
ContainerDepth,
TreeDepth,
ValueDepth,
ValuesPerObject,
ZeroSizeElements,
Count,
]
);
counter_index!(
reservation_index,
RESERVATIONS,
Reservation,
ReservationOrder,
[Input, Dependency, Provider]
);
pub const NAME_BYTES: usize = 4096;
static LIMITS: [AtomicU64; LIMIT_KINDS] = [const { AtomicU64::new(0) }; LIMIT_KINDS];
static BUDGETS: [AtomicU64; RESERVATIONS] = [const { AtomicU64::new(0) }; RESERVATIONS];
static ALLOCATOR: [AtomicU64; RESERVATIONS] = [const { AtomicU64::new(0) }; RESERVATIONS];
static NEXT_LOAD: AtomicU64 = AtomicU64::new(1);
static RESERVED: AtomicBool = AtomicBool::new(false);
static OVERFLOW: AtomicBool = AtomicBool::new(false);
static TABLES: Mutex<Option<Tables>> = Mutex::new(None);
thread_local! {
static IN_FALLIBLE: Cell<bool> = const { Cell::new(false) };
static VISITING: Cell<bool> = const { Cell::new(false) };
}
fn bump(counters: &[AtomicU64], at: usize) {
if let Some(c) = counters.get(at) {
c.fetch_add(1, Ordering::Relaxed);
}
}
pub(crate) fn limit(kind: LimitKind) {
bump(&LIMITS, kind_index(kind));
}
pub(crate) fn budget(what: Reservation) {
bump(&BUDGETS, reservation_index(what));
}
pub(crate) fn allocator(what: Reservation) {
bump(&ALLOCATOR, reservation_index(what));
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Refusals {
limits: [u64; LIMIT_KINDS],
budgets: [u64; RESERVATIONS],
allocator: [u64; RESERVATIONS],
}
const _: () = crate::send_sync::<Refusals>();
impl Refusals {
#[must_use]
pub fn limit(&self, kind: LimitKind) -> u64 {
self.limits.get(kind_index(kind)).copied().unwrap_or(0)
}
#[must_use]
pub fn budget(&self, what: Reservation) -> u64 {
self.budgets
.get(reservation_index(what))
.copied()
.unwrap_or(0)
}
#[must_use]
pub fn allocator(&self, what: Reservation) -> u64 {
self.allocator
.get(reservation_index(what))
.copied()
.unwrap_or(0)
}
#[must_use]
pub fn total(&self) -> u64 {
self.limits
.iter()
.chain(&self.budgets)
.chain(&self.allocator)
.fold(0, |n, c| n.saturating_add(*c))
}
#[must_use]
pub fn since(&self, earlier: &Self) -> Self {
let diff = |now: &[u64], then: &[u64], out: &mut [u64]| {
for ((o, n), t) in out.iter_mut().zip(now).zip(then) {
*o = n.saturating_sub(*t);
}
};
let mut out = Self::default();
diff(&self.limits, &earlier.limits, &mut out.limits);
diff(&self.budgets, &earlier.budgets, &mut out.budgets);
diff(&self.allocator, &earlier.allocator, &mut out.allocator);
out
}
}
#[must_use]
pub fn refusals() -> Refusals {
let read = |counters: &[AtomicU64], out: &mut [u64]| {
for (o, c) in out.iter_mut().zip(counters) {
*o = c.load(Ordering::Relaxed);
}
};
let mut out = Refusals::default();
read(&LIMITS, &mut out.limits);
read(&BUDGETS, &mut out.budgets);
read(&ALLOCATOR, &mut out.allocator);
out
}
#[must_use]
#[inline]
pub fn in_fallible_reserve() -> bool {
IN_FALLIBLE.try_with(Cell::get).unwrap_or(false)
}
pub(crate) struct Fallible(bool);
impl Fallible {
pub(crate) fn enter() -> Self {
Self(IN_FALLIBLE.try_with(|c| c.replace(true)).unwrap_or(false))
}
}
impl Drop for Fallible {
fn drop(&mut self) {
let _ = IN_FALLIBLE.try_with(|c| c.set(self.0));
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct LoadId(u64);
impl LoadId {
pub(crate) const BARE: Self = Self(0);
pub(crate) fn draw(name: &RawStr) -> Self {
let id = NEXT_LOAD.fetch_add(1, Ordering::Relaxed);
if RESERVED.load(Ordering::Acquire) {
record(|t| t.name(id, name.as_bytes()));
}
Self(id)
}
fn key(self) -> Option<u64> {
(self.0 != 0).then_some(self.0)
}
}
#[derive(Debug)]
pub(crate) struct Ancestry {
up: Option<Arc<Ancestry>>,
row: usize,
}
const _: fn(Ancestry) -> (Option<Arc<Ancestry>>, usize) = |Ancestry { up, row }| (up, row);
const _: fn(&mut Tables, &Key, SpanRow) -> bool = Tables::count;
#[derive(Clone, Debug)]
pub(crate) enum Key {
Untracked,
Top(LoadId),
Nested { load: LoadId, node: Arc<Ancestry> },
}
impl Key {
pub(crate) fn load(load: LoadId) -> Self {
if RESERVED.load(Ordering::Acquire) {
Self::Top(load)
} else {
Self::Untracked
}
}
}
#[derive(Debug)]
pub(crate) struct Origin {
opened: Key,
given: OnceLock<Key>,
}
impl Origin {
pub(crate) fn opened() -> Self {
Self {
opened: Key::load(LoadId::BARE),
given: OnceLock::new(),
}
}
fn key(&self) -> &Key {
self.given.get().unwrap_or(&self.opened)
}
fn give(&self, key: Key) {
let _ = self.given.set(key);
}
pub(crate) fn child(&self, row: usize) -> Key {
if !RESERVED.load(Ordering::Acquire) {
return Key::Untracked;
}
let (load, up) = match self.key() {
Key::Untracked => return Key::Untracked,
Key::Top(load) => (*load, None),
Key::Nested { load, node } => (*load, Some(Arc::clone(node))),
};
Key::Nested {
load,
node: Arc::new(Ancestry { up, row }),
}
}
}
pub(crate) fn adopt(got: &Result<File, Error>, key: impl FnOnce() -> Key) {
if let Ok(File::Bundle(b)) = got {
b.span_origin().give(key());
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum SpanRow {
Row(usize),
Whole,
}
impl SpanRow {
pub(crate) const WHOLE: Self = Self::Whole;
pub(crate) const fn row(i: usize) -> Self {
Self::Row(i)
}
}
pub(crate) fn span_read(origin: &Origin, row: SpanRow) {
if !RESERVED.load(Ordering::Acquire) {
return;
}
let key = origin.key();
if !matches!(key, Key::Untracked) {
record(|t| t.count(key, row));
}
}
#[doc(hidden)]
pub fn hooks_once(name: &RawStr) {
let top = Origin::opened();
let load = LoadId::draw(name);
top.give(Key::load(load));
let inner = Origin::opened();
inner.give(top.child(0));
let deeper = Origin::opened();
deeper.give(inner.child(1));
for o in [&top, &inner, &deeper] {
span_read(o, SpanRow::row(0));
span_read(o, SpanRow::WHOLE);
}
}
fn lock() -> MutexGuard<'static, Option<Tables>> {
TABLES.lock().unwrap_or_else(PoisonError::into_inner)
}
fn visiting() -> bool {
VISITING.try_with(Cell::get).unwrap_or(false)
}
fn record(f: impl FnOnce(&mut Tables) -> bool) {
if visiting() {
OVERFLOW.store(true, Ordering::Release);
return;
}
let mut held = lock();
if let Some(t) = held.as_mut()
&& !f(t)
{
OVERFLOW.store(true, Ordering::Release);
}
}
#[derive(Debug)]
struct Tables {
names: Vec<(u64, usize, usize)>,
arena: Vec<u8>,
slots: Vec<Slot>,
paths: Vec<usize>,
width: usize,
scratch: Vec<usize>,
}
#[derive(Debug)]
struct Slot {
load: LoadId,
whole: bool,
len: usize,
count: u64,
}
impl Tables {
fn with_room(names: usize, slots: usize, width: usize) -> Option<Self> {
let mut t = Self {
names: Vec::new(),
arena: Vec::new(),
slots: Vec::new(),
paths: Vec::new(),
width,
scratch: Vec::new(),
};
t.names.try_reserve_exact(names).ok()?;
t.arena
.try_reserve_exact(names.checked_mul(NAME_BYTES)?)
.ok()?;
t.slots.try_reserve_exact(slots).ok()?;
t.paths.try_reserve_exact(slots.checked_mul(width)?).ok()?;
t.scratch.try_reserve_exact(width).ok()?;
Some(t)
}
fn name(&mut self, id: u64, name: &[u8]) -> bool {
let at = self.arena.len();
let fits = name.len() <= NAME_BYTES
&& self.names.len() < self.names.capacity()
&& at.saturating_add(name.len()) <= self.arena.capacity();
if fits {
self.arena.extend_from_slice(name);
self.names.push((id, at, name.len()));
}
fits
}
fn count(&mut self, key: &Key, row: SpanRow) -> bool {
let (load, mut node) = match key {
Key::Untracked => return true,
Key::Top(load) => (*load, None),
Key::Nested { load, node } => (*load, Some(&**node)),
};
let width = self.width;
let scratch = &mut self.scratch;
scratch.clear();
while let Some(n) = node {
if scratch.len() >= width {
return false;
}
scratch.push(n.row);
node = n.up.as_deref();
}
scratch.reverse();
let whole = match row {
SpanRow::Row(i) if scratch.len() < width => {
scratch.push(i);
false
}
SpanRow::Row(_) => return false,
SpanRow::Whole => true,
};
let path = self.scratch.as_slice();
let len = path.len();
let paths = &self.paths;
let same = |i: usize, s: &Slot| {
let at = i.saturating_mul(width);
let p = paths.get(at..at.saturating_add(s.len)).unwrap_or_default();
s.load == load && s.whole == whole && p == path
};
if let Some(s) = self
.slots
.iter_mut()
.enumerate()
.find_map(|(i, s)| same(i, s).then_some(s))
{
s.count = s.count.saturating_add(1);
return true;
}
let end = self.paths.len().saturating_add(width);
if self.slots.len() >= self.slots.capacity() || end > self.paths.capacity() {
return false;
}
self.paths.extend_from_slice(&self.scratch);
self.paths.resize(end, 0);
self.slots.push(Slot {
load,
whole,
len,
count: 1,
});
true
}
}
pub fn reserve_span_reads(names: usize, slots: usize, width: usize) {
assert!(
!visiting(),
"testing::reserve_span_reads called inside testing::span_reads's reader"
);
let tables = Tables::with_room(names, slots, width);
let mut held = lock();
OVERFLOW.store(tables.is_none(), Ordering::Release);
RESERVED.store(tables.is_some(), Ordering::Release);
let old = std::mem::replace(&mut *held, tables);
drop(held);
drop(old);
}
pub fn span_reads<R>(f: impl FnOnce(&SpanReads<'_>) -> R) -> R {
struct Restore(bool);
impl Drop for Restore {
fn drop(&mut self) {
let _ = VISITING.try_with(|c| c.set(self.0));
}
}
assert!(
!visiting(),
"testing::span_reads called inside its own reader"
);
let held = lock();
let _restore = Restore(VISITING.try_with(|c| c.replace(true)).unwrap_or(false));
f(&SpanReads {
tables: held.as_ref(),
overflowed: OVERFLOW.load(Ordering::Acquire),
})
}
#[derive(Debug)]
pub struct SpanReads<'a> {
tables: Option<&'a Tables>,
overflowed: bool,
}
const _: () = crate::send_sync::<SpanReads<'static>>();
impl<'a> SpanReads<'a> {
#[must_use]
pub fn reserved(&self) -> bool {
self.tables.is_some()
}
#[must_use]
pub fn overflowed(&self) -> bool {
self.overflowed
}
pub fn names(&self) -> impl Iterator<Item = (u64, &'a [u8])> + use<'a> {
let t = self.tables;
t.into_iter().flat_map(|t| {
t.names.iter().map(|&(id, at, len)| {
let name = t.arena.get(at..at.saturating_add(len)).unwrap_or_default();
(id, name)
})
})
}
#[must_use]
pub fn name(&self, id: u64) -> Option<&'a [u8]> {
self.names().find_map(|(i, n)| (i == id).then_some(n))
}
pub fn reads(&self) -> impl Iterator<Item = SpanRead<'a>> + use<'a> {
let t = self.tables;
t.into_iter().flat_map(|t| {
t.slots.iter().enumerate().map(|(i, s)| {
let at = i.saturating_mul(t.width);
SpanRead {
load: s.load.key(),
path: t
.paths
.get(at..at.saturating_add(s.len))
.unwrap_or_default(),
whole: s.whole,
count: s.count,
}
})
})
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct SpanRead<'a> {
pub load: Option<u64>,
pub path: &'a [usize],
pub whole: bool,
pub count: u64,
}
const _: () = crate::send_sync::<SpanRead<'static>>();
#[cfg(test)]
#[path = "testing_tests.rs"]
mod tests;