Skip to main content

uqa_core/
memory.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Shared byte allowances with reservations that follow allocation ownership.
8//!
9//! Owners reserve requested buffer layouts before allocating and charge any additional reported capacity before moving values. Allocator bookkeeping, borrowed data, and separately owned immutable resources are outside this allowance.
10
11use std::sync::atomic::{AtomicUsize, Ordering};
12use std::sync::Arc;
13
14use triomphe::Arc as StrongArc;
15
16mod deque;
17mod hash_index;
18mod hash_set;
19mod heap;
20mod map;
21mod observation;
22mod production;
23mod small_vec;
24mod string;
25mod vec;
26
27pub use deque::BudgetedDeque;
28pub use hash_index::{BudgetedHashIndex, BudgetedHashIndexIter};
29pub use hash_set::BudgetedHashSet;
30pub use heap::BudgetedBinaryHeap;
31pub use map::{
32    BudgetedMap, BudgetedMapIter, BudgetedSharedMap, BudgetedSharedMapIter,
33    BudgetedSharedMapSnapshot, OwnedMap, OwnedMapIntoIter, OwnedSet, OwnedSetIntoIter,
34    OwnedSetIter, PreparedMapEntry,
35};
36pub use observation::{AllocationObserver, AllocationUsage, ObserveAllocations};
37pub use production::{
38    OwnedProductionControl, Produced, ProductionControl, ProductionMap, ProductionSmallVec,
39    ProductionString, ProductionVec,
40};
41pub use small_vec::BudgetedSmallVec;
42pub use string::BudgetedString;
43pub use vec::BudgetedVec;
44
45#[derive(Debug, thiserror::Error)]
46pub enum MemoryError {
47    #[error("memory requires {required} bytes, exceeding limit {limit}")]
48    Limit { required: usize, limit: usize },
49    #[error("memory allocation size overflow")]
50    SizeOverflow,
51    #[error("memory allocation failed: {0}")]
52    Allocation(#[from] std::collections::TryReserveError),
53}
54
55#[derive(Debug)]
56struct Allowance {
57    limit: usize,
58    used: AtomicUsize,
59    peak: AtomicUsize,
60    parent: Option<MemoryBudget>,
61}
62
63impl Allowance {
64    fn claim(&self, additional: usize) -> Result<(), MemoryError> {
65        let mut used = self.used.load(Ordering::Relaxed);
66        loop {
67            let required = used
68                .checked_add(additional)
69                .ok_or(MemoryError::SizeOverflow)?;
70            if required > self.limit {
71                return Err(MemoryError::Limit {
72                    required,
73                    limit: self.limit,
74                });
75            }
76            match self.used.compare_exchange_weak(
77                used,
78                required,
79                Ordering::Relaxed,
80                Ordering::Relaxed,
81            ) {
82                Ok(_) => {
83                    self.peak.fetch_max(required, Ordering::Relaxed);
84                    return Ok(());
85                }
86                Err(current) => used = current,
87            }
88        }
89    }
90}
91
92impl Drop for Allowance {
93    fn drop(&mut self) {
94        // Destroy an unshared parent chain iteratively, including deeply nested application budgets.
95        let mut parent = self.parent.take();
96        while let Some(budget) = parent {
97            match StrongArc::try_unwrap(budget.0) {
98                Ok(mut allowance) => parent = allowance.parent.take(),
99                Err(_) => break,
100            }
101        }
102    }
103}
104
105/// Clones share one allowance, including reservations retained by completed producers.
106#[derive(Debug, Clone)]
107pub struct MemoryBudget(StrongArc<Allowance>);
108
109impl MemoryBudget {
110    pub fn new(limit: usize) -> Self {
111        Self(StrongArc::new(Allowance {
112            limit,
113            used: AtomicUsize::new(0),
114            peak: AtomicUsize::new(0),
115            parent: None,
116        }))
117    }
118
119    /// Add a component limit without enlarging this allowance. Every descendant reservation also charges each ancestor until its final owner releases it.
120    pub fn child(&self, limit: usize) -> Self {
121        Self(StrongArc::new(Allowance {
122            limit,
123            used: AtomicUsize::new(0),
124            peak: AtomicUsize::new(0),
125            parent: Some(self.clone()),
126        }))
127    }
128
129    fn allowances(&self) -> impl Iterator<Item = &Allowance> {
130        std::iter::successors(Some(self), |budget| budget.0.parent.as_ref())
131            .map(|budget| &*budget.0)
132    }
133
134    pub fn limit(&self) -> usize {
135        self.0.limit
136    }
137
138    pub fn used(&self) -> usize {
139        self.0.used.load(Ordering::Relaxed)
140    }
141
142    /// Currently unreserved bytes under this limit and every ancestor limit. This is a sizing hint; concurrent owners can consume it before a reservation succeeds.
143    pub fn available(&self) -> usize {
144        self.allowances()
145            .map(|allowance| {
146                allowance
147                    .limit
148                    .saturating_sub(allowance.used.load(Ordering::Relaxed))
149            })
150            .min()
151            .expect("a budget has its own allowance")
152    }
153
154    pub fn shares_allowance(&self, other: &Self) -> bool {
155        StrongArc::ptr_eq(&self.0, &other.0)
156    }
157
158    /// Largest simultaneous reservation, including old and replacement buffers.
159    pub fn peak(&self) -> usize {
160        self.0.peak.load(Ordering::Relaxed)
161    }
162
163    pub fn reserve(&self, bytes: usize) -> Result<MemoryReservation, MemoryError> {
164        let mut reservation = self.empty_reservation();
165        reservation.grow(bytes)?;
166        Ok(reservation)
167    }
168
169    pub fn empty_reservation(&self) -> MemoryReservation {
170        MemoryReservation {
171            budget: self.clone(),
172            bytes: 0,
173        }
174    }
175}
176
177/// A unique lease: release it only after the associated allocation has been freed.
178#[derive(Debug)]
179pub struct MemoryReservation {
180    budget: MemoryBudget,
181    bytes: usize,
182}
183
184impl MemoryReservation {
185    pub fn bytes(&self) -> usize {
186        self.bytes
187    }
188
189    pub fn budget(&self) -> &MemoryBudget {
190        &self.budget
191    }
192
193    /// Transfer part of an existing allocation lease without releasing or reserving bytes.
194    ///
195    /// Panics if `bytes` exceeds this lease. The original lease is unchanged on failure.
196    pub fn split(&mut self, bytes: usize) -> Self {
197        self.bytes = self
198            .bytes
199            .checked_sub(bytes)
200            .expect("insufficient reserved bytes");
201        Self {
202            budget: self.budget.clone(),
203            bytes,
204        }
205    }
206
207    /// Reserve additional bytes atomically; a failed request leaves this lease unchanged.
208    pub fn grow(&mut self, additional: usize) -> Result<(), MemoryError> {
209        if additional == 0 {
210            return Ok(());
211        }
212        for (claimed, allowance) in self.budget.allowances().enumerate() {
213            if let Err(error) = allowance.claim(additional) {
214                for previous in self.budget.allowances().take(claimed) {
215                    previous.used.fetch_sub(additional, Ordering::Relaxed);
216                }
217                return Err(error);
218            }
219        }
220        self.bytes += additional;
221        Ok(())
222    }
223
224    /// Transfer ownership without releasing and reacquiring the shared allowance.
225    ///
226    /// Panics if the leases belong to different allowances.
227    pub fn absorb(&mut self, mut other: Self) {
228        assert!(
229            self.budget.shares_allowance(&other.budget),
230            "different memory allowances"
231        );
232        self.bytes += other.bytes;
233        other.bytes = 0;
234    }
235}
236
237impl Drop for MemoryReservation {
238    fn drop(&mut self) {
239        for allowance in self.budget.allowances() {
240            allowance.used.fetch_sub(self.bytes, Ordering::Relaxed);
241        }
242    }
243}
244
245/// An immutable result and its owned allocations. Cloning the value is a separate allocation.
246#[derive(Debug)]
247pub struct Budgeted<T> {
248    // Field order ensures that the value is destroyed before its allowance is returned.
249    value: T,
250    memory: MemoryReservation,
251}
252
253impl<T> Budgeted<T> {
254    /// The caller must associate all owned allocations with this reservation.
255    pub fn new(value: T, memory: MemoryReservation) -> Self {
256        Self { value, memory }
257    }
258
259    pub fn reserved_bytes(&self) -> usize {
260        self.memory.bytes()
261    }
262
263    pub fn budget(&self) -> &MemoryBudget {
264        self.memory.budget()
265    }
266
267    /// Share the immutable value and its lease, reserving the shared payload before allocation. Reference-count bookkeeping is outside the payload allowance.
268    pub fn into_shared(self) -> Result<Arc<Self>, MemoryError> {
269        let mut memory = self.memory.budget().reserve(std::mem::size_of::<Self>())?;
270        let (value, allocations) = self.into_parts();
271        memory.absorb(allocations);
272        Ok(Arc::new(Self::new(value, memory)))
273    }
274
275    /// Move the value and lease together to another allocation owner.
276    pub fn into_parts(self) -> (T, MemoryReservation) {
277        (self.value, self.memory)
278    }
279}
280
281impl<T> std::ops::Deref for Budgeted<T> {
282    type Target = T;
283
284    fn deref(&self) -> &T {
285        &self.value
286    }
287}
288
289impl<T: PartialEq> PartialEq for Budgeted<T> {
290    fn eq(&self, other: &Self) -> bool {
291        self.value == other.value
292    }
293}
294
295impl<T: Eq> Eq for Budgeted<T> {}
296
297impl<T: AsRef<U>, U: ?Sized> AsRef<U> for Budgeted<T> {
298    fn as_ref(&self) -> &U {
299        self.value.as_ref()
300    }
301}
302
303fn buffer_bytes<T>(capacity: usize) -> Result<usize, MemoryError> {
304    capacity
305        .checked_mul(std::mem::size_of::<T>())
306        .filter(|bytes| isize::try_from(*bytes).is_ok())
307        .ok_or(MemoryError::SizeOverflow)
308}
309
310fn reconcile_buffer_capacity<T>(
311    memory: &mut MemoryReservation,
312    capacity: usize,
313) -> Result<(), MemoryError> {
314    memory.grow(buffer_bytes::<T>(capacity)?.saturating_sub(memory.bytes()))
315}
316
317fn replacement<T>(
318    budget: &MemoryBudget,
319    capacity: usize,
320    required: usize,
321) -> Result<(usize, MemoryReservation), MemoryError> {
322    let preferred = capacity.saturating_mul(2).max(required);
323    if let Ok(bytes) = buffer_bytes::<T>(preferred) {
324        if let Ok(memory) = budget.reserve(bytes) {
325            return Ok((preferred, memory));
326        }
327    }
328    Ok((required, budget.reserve(buffer_bytes::<T>(required)?)?))
329}
330
331#[cfg(test)]
332mod tests;