use std::fmt;
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use bytes::Bytes;
use crate::error::{LimitError, LimitKind};
use crate::limits::{
Charge, ChargeError, Meter, grow_charged, grow_counted, heap_cost, shrink_charged,
};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Reservation {
Input,
Dependency,
Provider,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
#[error("allocator refused {requested} bytes for {what:?}")]
pub struct AllocError {
pub requested: u64,
pub what: Reservation,
}
const _: () = crate::send_sync::<AllocError>();
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("memory budget refused {requested} bytes for {what:?}")]
pub struct BudgetExceeded {
pub requested: u64,
pub what: Reservation,
}
pub trait MemoryBudget: Send + Sync + fmt::Debug {
fn try_reserve(&self, bytes: u64, what: Reservation) -> Result<Permit, BudgetExceeded>;
fn allocator_refused(&self, _error: AllocError) {}
}
pub trait PermitHome: Send + Sync {
fn release(&self, bytes: u64);
}
#[must_use = "a permit returns its bytes when dropped"]
pub struct Permit {
primary: PermitRecord,
more: PermitRecords,
}
enum PermitRecords {
Empty,
Inline(PermitRecord),
Heap(Vec<PermitRecord>),
}
impl PermitRecords {
fn as_slice(&self) -> &[PermitRecord] {
match self {
Self::Empty => &[],
Self::Inline(record) => std::slice::from_ref(record),
Self::Heap(records) => records,
}
}
fn as_mut_slice(&mut self) -> &mut [PermitRecord] {
match self {
Self::Empty => &mut [],
Self::Inline(record) => std::slice::from_mut(record),
Self::Heap(records) => records,
}
}
}
struct PermitRecord {
bytes: u64,
home: Option<Arc<dyn PermitHome>>,
}
impl PermitRecord {
fn release(&mut self, n: u64) {
let n = n.min(self.bytes);
if let Some(home) = &self.home {
home.release(n);
}
self.bytes -= n;
}
}
impl Drop for PermitRecord {
fn drop(&mut self) {
self.release(self.bytes);
}
}
fn same_home(a: Option<&Arc<dyn PermitHome>>, b: Option<&Arc<dyn PermitHome>>) -> bool {
match (a, b) {
(None, None) => true,
(Some(a), Some(b)) => std::ptr::addr_eq(Arc::as_ptr(a), Arc::as_ptr(b)),
_ => false,
}
}
impl Permit {
pub fn detached(bytes: u64) -> Self {
Self {
primary: PermitRecord { bytes, home: None },
more: PermitRecords::Empty,
}
}
pub fn new(bytes: u64, home: Arc<dyn PermitHome>) -> Self {
Self {
primary: PermitRecord {
bytes,
home: Some(home),
},
more: PermitRecords::Empty,
}
}
#[must_use]
pub fn bytes(&self) -> u64 {
self.more
.as_slice()
.iter()
.fold(self.primary.bytes, |n, p| n.saturating_add(p.bytes))
}
pub fn absorb(&mut self, other: Permit) {
match other.more {
PermitRecords::Empty => (),
PermitRecords::Inline(record) => self.absorb_record(record),
PermitRecords::Heap(records) => {
for record in records {
self.absorb_record(record);
}
}
}
self.absorb_record(other.primary);
}
fn absorb_record(&mut self, mut other: PermitRecord) {
if other.bytes == 0 {
other.home = None;
return;
}
if let Some(kept) = std::iter::once(&mut self.primary)
.chain(self.more.as_mut_slice())
.find(|p| same_home(p.home.as_ref(), other.home.as_ref()))
{
kept.bytes = kept.bytes.saturating_add(other.bytes);
other.bytes = 0;
other.home = None;
} else if self.primary.bytes == 0 {
self.primary = other;
} else {
match &mut self.more {
PermitRecords::Empty => self.more = PermitRecords::Inline(other),
PermitRecords::Heap(records) => records.push(other),
PermitRecords::Inline(_) => {
let previous = std::mem::replace(&mut self.more, PermitRecords::Empty);
if let PermitRecords::Inline(record) = previous {
self.more = PermitRecords::Heap(vec![record, other]);
}
}
}
}
}
#[must_use]
pub fn records(&self) -> usize {
self.more.as_slice().len()
}
pub fn shrink_to(&mut self, keep: u64) {
let mut excess = self.bytes().saturating_sub(keep);
match &mut self.more {
PermitRecords::Empty => (),
PermitRecords::Inline(record) => {
let n = excess.min(record.bytes);
record.release(n);
excess -= n;
if record.bytes == 0 {
self.more = PermitRecords::Empty;
}
}
PermitRecords::Heap(records) => {
while excess > 0 {
let Some(last) = records.last_mut() else {
break;
};
let n = excess.min(last.bytes);
last.release(n);
excess -= n;
if last.bytes == 0 {
records.pop();
}
}
}
}
self.primary.release(excess);
}
}
impl fmt::Debug for Permit {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Permit")
.field("bytes", &self.bytes())
.field("attached", &self.primary.home.is_some())
.field("more", &self.records())
.finish_non_exhaustive()
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct Unbounded;
impl MemoryBudget for Unbounded {
fn try_reserve(&self, bytes: u64, _what: Reservation) -> Result<Permit, BudgetExceeded> {
Ok(Permit::detached(bytes))
}
}
#[derive(Debug)]
pub struct Counting {
limit: u64,
used: Arc<CountingHome>,
}
#[derive(Debug, Default)]
struct CountingHome {
used: AtomicU64,
}
impl PermitHome for CountingHome {
fn release(&self, bytes: u64) {
self.used.fetch_sub(bytes, Ordering::AcqRel);
}
}
impl Counting {
#[must_use]
pub fn new(limit: u64) -> Self {
Self {
limit,
used: Arc::new(CountingHome::default()),
}
}
#[must_use]
pub fn used(&self) -> u64 {
self.used.used.load(Ordering::Acquire)
}
}
impl MemoryBudget for Counting {
fn try_reserve(&self, bytes: u64, what: Reservation) -> Result<Permit, BudgetExceeded> {
let refused = BudgetExceeded {
requested: bytes,
what,
};
self.used
.used
.try_update(Ordering::AcqRel, Ordering::Acquire, |used| {
used.checked_add(bytes).filter(|n| *n <= self.limit)
})
.map_err(|_| refused)?;
Ok(Permit::new(bytes, self.used.clone()))
}
}
struct Charged {
buf: Vec<u8>,
_charge: Charge,
}
impl AsRef<[u8]> for Charged {
fn as_ref(&self) -> &[u8] {
&self.buf
}
}
pub const OWNER_COST: u64 = heap_cost(256);
pub fn charged_bytes(buf: Vec<u8>, mut charge: Charge) -> Result<Bytes, ChargeError> {
charge.grow(OWNER_COST)?;
Ok(Bytes::from_owner(Charged {
buf,
_charge: charge,
}))
}
pub struct DecodeBuf {
buf: Vec<u8>,
charge: Charge,
seg_start: usize,
seg_cap: u64,
seg_kind: LimitKind,
seg_declared: u64,
ahead: u64,
seg_epoch: u64,
prepaid: u64,
count_writes: bool,
}
impl fmt::Debug for DecodeBuf {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("DecodeBuf")
.field("len", &self.buf.len())
.field("capacity", &self.buf.capacity())
.field("charged", &self.charge.bytes())
.field("seg_start", &self.seg_start)
.field("seg_cap", &self.seg_cap)
.finish_non_exhaustive()
}
}
impl DecodeBuf {
pub fn new(
meter: &Arc<Meter>,
initial: u64,
cap: u64,
cap_kind: LimitKind,
) -> Result<Self, ChargeError> {
let mut out = Self {
buf: Vec::new(),
charge: Charge::zero(meter),
seg_start: 0,
seg_cap: cap,
seg_kind: cap_kind,
seg_declared: cap,
ahead: 0,
seg_epoch: 0,
prepaid: 0,
count_writes: cap_kind == LimitKind::BlockOutput,
};
let initial = usize::try_from(initial.min(cap)).unwrap_or(usize::MAX);
grow_charged(&mut out.buf, &mut out.charge, initial, initial)?;
Ok(out)
}
pub(crate) fn inflated(meter: &Arc<Meter>, cap: u64) -> Result<Self, ChargeError> {
Self::counted(meter, cap, LimitKind::Inflate)
}
pub(crate) fn counted(
meter: &Arc<Meter>,
cap: u64,
cap_kind: LimitKind,
) -> Result<Self, ChargeError> {
let mut out = Self::new(meter, 0, cap, cap_kind)?;
out.count_writes = true;
Ok(out)
}
pub fn begin_block(&mut self, cap: u64, cap_kind: LimitKind, declared: u64) {
self.seg_start = self.buf.len();
self.seg_cap = cap;
self.seg_kind = cap_kind;
self.count_writes = cap_kind == LimitKind::BlockOutput;
self.seg_declared = declared;
self.seg_epoch = self.seg_epoch.wrapping_add(1);
}
pub(crate) fn set_ahead(&mut self, bytes: u64) {
self.ahead = bytes;
}
pub(crate) fn prepay(&mut self, n: u64) -> Result<(), ChargeError> {
self.charge.meter().count_decode(n)?;
self.prepaid = self.prepaid.saturating_add(n);
Ok(())
}
pub(crate) fn end_prepaid(&mut self) -> u64 {
std::mem::take(&mut self.prepaid)
}
#[must_use]
pub fn meter(&self) -> &Arc<Meter> {
self.charge.meter()
}
#[must_use]
pub fn segment_cap(&self) -> u64 {
self.seg_cap
}
pub(crate) fn segment_epoch(&self) -> u64 {
self.seg_epoch
}
#[must_use]
pub fn len(&self) -> usize {
self.buf.len()
}
#[must_use]
pub fn segment_len(&self) -> usize {
self.buf.len().saturating_sub(self.seg_start)
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.buf.is_empty()
}
#[must_use]
pub fn capacity(&self) -> usize {
self.buf.capacity()
}
#[must_use]
pub fn charged(&self) -> u64 {
self.charge.bytes()
}
#[must_use]
pub fn as_slice(&self) -> &[u8] {
&self.buf
}
fn seg_end(&self) -> usize {
let cap = usize::try_from(self.seg_cap).unwrap_or(usize::MAX);
self.seg_start.saturating_add(cap)
}
pub fn reserve(&mut self, additional: usize) -> Result<(), ChargeError> {
self.make_room(additional, 0)
}
fn room_to_write(&mut self, n: usize) -> Result<(), ChargeError> {
let work = if self.count_writes {
u64::try_from(n).unwrap_or(u64::MAX)
} else {
0
};
let credit = work.min(self.prepaid);
self.make_room(n, work - credit)?;
self.prepaid -= credit;
Ok(())
}
fn make_room(&mut self, additional: usize, work: u64) -> Result<(), ChargeError> {
let need = self.buf.len().saturating_add(additional);
let end = self.seg_end();
if need > end {
return Err(ChargeError::Limit(LimitError::refused(
self.seg_kind,
u64::try_from(need - self.seg_start).unwrap_or(u64::MAX),
self.seg_cap,
)));
}
let declared = self.seg_declared.saturating_add(self.ahead);
let declared = usize::try_from(declared).unwrap_or(usize::MAX);
let hint = self.seg_start.saturating_add(declared).min(end);
let most = if need <= hint { hint } else { end };
grow_counted(&mut self.buf, &mut self.charge, need, most, work)
}
pub fn extend_from_slice(&mut self, data: &[u8]) -> Result<(), ChargeError> {
self.room_to_write(data.len())?;
self.buf.extend_from_slice(data);
Ok(())
}
pub(crate) fn write_at(&mut self, offset: usize, data: &[u8]) -> Result<(), ChargeError> {
if data.is_empty() {
return Ok(());
}
let refused =
|| ChargeError::Limit(LimitError::refused(self.seg_kind, u64::MAX, self.seg_cap));
let end = offset.checked_add(data.len()).ok_or_else(refused)?;
let old = self.buf.len();
let overlap = old.saturating_sub(offset).min(data.len());
let (prefix, suffix) = data.split_at_checked(overlap).ok_or_else(refused)?;
let gap = offset.saturating_sub(old);
let work = if self.count_writes {
u64::try_from(gap.saturating_add(data.len())).unwrap_or(u64::MAX)
} else {
0
};
let credit = work.min(self.prepaid);
self.make_room(end.saturating_sub(old), work - credit)?;
self.prepaid -= credit;
if gap > 0 {
self.buf.resize(offset, 0);
}
if let Some(target) = self.buf.get_mut(offset..offset.saturating_add(overlap)) {
target.copy_from_slice(prefix);
}
self.buf.extend_from_slice(suffix);
Ok(())
}
pub fn grow_zeroed(&mut self, n: usize) -> Result<&mut [u8], ChargeError> {
self.room_to_write(n)?;
let start = self.buf.len();
self.buf.resize(start + n, 0);
Ok(self.buf.get_mut(start..).unwrap_or_default())
}
pub(crate) fn write_zeroes_at(
&mut self,
offset: usize,
count: usize,
) -> Result<(), ChargeError> {
if count == 0 {
return Ok(());
}
let end = offset.checked_add(count).ok_or_else(|| {
ChargeError::Limit(LimitError::refused(self.seg_kind, u64::MAX, self.seg_cap))
})?;
let old = self.buf.len();
let work = if self.count_writes {
u64::try_from(offset.saturating_sub(old).saturating_add(count)).unwrap_or(u64::MAX)
} else {
0
};
let credit = work.min(self.prepaid);
self.make_room(end.saturating_sub(old), work - credit)?;
self.prepaid -= credit;
self.buf.resize(old.max(end), 0);
if let Some(target) = self.buf.get_mut(offset..end) {
target.fill(0);
}
Ok(())
}
pub fn truncate(&mut self, len: usize) {
self.buf.truncate(len);
if self.buf.len() < self.seg_start {
self.seg_start = self.buf.len();
self.seg_epoch = self.seg_epoch.wrapping_add(1);
}
}
pub fn into_bytes(mut self) -> Result<Bytes, ChargeError> {
let _ = shrink_charged(&mut self.buf, &mut self.charge);
charged_bytes(self.buf, self.charge)
}
}
#[cfg(test)]
mod tests;