1use 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 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#[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 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 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 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#[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 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 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 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#[derive(Debug)]
247pub struct Budgeted<T> {
248 value: T,
250 memory: MemoryReservation,
251}
252
253impl<T> Budgeted<T> {
254 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 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 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;