#[cfg(test)]
mod tests;
use std::collections::BTreeMap;
use std::mem::size_of;
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use bytes::Bytes;
use super::counts::RunBytes;
use crate::limits::{Charge, ChargeError, Meter, MeteredVec, heap_cost};
pub(super) const STEP: u64 = 8;
pub(super) fn search_steps(n: usize) -> u64 {
n.checked_sub(1).map_or(0, |m| u64::from(m.bit_width()) + 1)
}
pub(crate) struct Ends {
ends: Box<[AtomicU64]>,
known: AtomicUsize,
}
impl Ends {
pub(crate) fn new(blocks: usize, meter: &Arc<Meter>) -> Result<(Self, Charge), ChargeError> {
let mut rows = MeteredVec::with_capacity(meter, blocks)?;
for _ in 0..blocks {
rows.push(AtomicU64::new(0))?;
}
let (ends, charge) = rows.into_boxed_slice()?;
let ends = Self {
ends,
known: AtomicUsize::new(0),
};
Ok((ends, charge))
}
pub(super) fn known(&self) -> usize {
self.known.load(Ordering::Acquire)
}
pub(super) fn start(&self, k: usize) -> u64 {
k.checked_sub(1).map_or(0, |j| self.end(j))
}
pub(super) fn end(&self, k: usize) -> u64 {
self.ends.get(k).map_or(0, |e| e.load(Ordering::Relaxed))
}
pub(super) fn first_ending_past(&self, from: usize, known: usize, at: u64) -> (usize, u64) {
self.search(from, known, |end| end <= at)
}
pub(super) fn first_ending_at(&self, from: usize, known: usize, at: u64) -> (usize, u64) {
self.search(from, known, |end| end < at)
}
fn search(&self, from: usize, known: usize, before: impl Fn(u64) -> bool) -> (usize, u64) {
let rows = self.ends.get(from..known).unwrap_or_default();
let mut probes = 0u64;
let at = rows.partition_point(|e| {
probes += 1;
before(e.load(Ordering::Relaxed))
});
(from + at, probes)
}
pub(super) fn learn(&self, k: usize, len: u64) {
if k > self.known() {
return;
}
let Some(row) = self.ends.get(k) else {
return;
};
row.store(self.start(k).saturating_add(len), Ordering::Relaxed);
self.known.fetch_max(k + 1, Ordering::Release);
}
}
struct Run {
end: usize,
bytes: Bytes,
}
const RUN_ELEMENT: usize = size_of::<usize>() + size_of::<Run>();
const RUN_LEAF: u64 = heap_cost((16 + 11 * RUN_ELEMENT) as u64);
const RUN_INTERNAL: u64 = heap_cost((16 + 11 * RUN_ELEMENT + 12 * size_of::<usize>()) as u64);
pub(super) const RUN_SHARE: u64 = RUN_LEAF / 5 + 1 + RUN_INTERNAL / 30 + 1;
pub(crate) struct RunIndex {
runs: BTreeMap<usize, Run>,
charge: Charge,
rooted: bool,
bytes: RunBytes,
}
pub(super) enum Published {
Cached,
Covered(usize, Bytes),
Refused,
}
impl RunIndex {
#[cfg_attr(
not(target_vendor = "apple"),
expect(
clippy::unnecessary_wraps,
reason = "only Darwin's lazily boxed mutex is charged here"
)
)]
pub(super) fn mutex(charge: &mut Charge) -> Result<Mutex<Self>, ChargeError> {
let runs = Mutex::new(Self::new(charge.meter()));
#[cfg(target_vendor = "apple")]
{
charge.grow(heap_cost(64))?;
drop(
runs.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner),
);
}
Ok(runs)
}
pub(crate) fn new(meter: &Arc<Meter>) -> Self {
Self {
runs: BTreeMap::new(),
charge: Charge::zero(meter),
rooted: false,
bytes: RunBytes::default(),
}
}
pub(super) fn len(&self) -> usize {
self.runs.len()
}
pub(super) fn bytes(&self) -> &RunBytes {
&self.bytes
}
pub(super) fn covering(&self, first: usize, end: usize) -> Option<(usize, Bytes)> {
self.runs
.range(..=first)
.next_back()
.filter(|(_, r)| r.end >= end)
.map(|(f, r)| (*f, r.bytes.clone()))
}
pub(super) fn inside(&self, first: usize, end: usize) -> impl Iterator<Item = usize> + '_ {
self.runs
.range(first..)
.take_while(move |(_, r)| r.end <= end)
.map(|(f, _)| *f)
}
pub(super) fn covered(&self, first: usize, end: usize) -> usize {
self.inside(first, end).count()
}
pub(super) fn publish(
&mut self,
first: usize,
end: usize,
bytes: &Bytes,
dropped: &mut MeteredVec<Bytes>,
) -> Published {
if let Some((f, b)) = self.covering(first, end) {
return Published::Covered(f, b);
}
let covered = self.covered(first, end);
if covered > 0 && dropped.reserve_exact(covered).is_err() {
return Published::Refused;
}
let share = if self.rooted {
RUN_SHARE
} else {
RUN_SHARE + RUN_LEAF
};
if self.charge.grow(share).is_err() {
return Published::Refused;
}
self.rooted = true;
let mut gone = 0u64;
for _ in 0..covered {
let Some(f) = self.runs.range(first..).next().map(|(f, _)| *f) else {
break;
};
if let Some(run) = self.runs.remove(&f) {
gone = gone.saturating_add(len64(&run.bytes));
let _ = dropped.push(run.bytes);
}
}
self.bytes.publish(len64(bytes), gone);
self.runs.insert(
first,
Run {
end,
bytes: bytes.clone(),
},
);
self.charge
.release(RUN_SHARE.saturating_mul(u64::try_from(covered).unwrap_or(u64::MAX)));
Published::Cached
}
}
fn len64(bytes: &Bytes) -> u64 {
u64::try_from(bytes.len()).unwrap_or(u64::MAX)
}