1use std::{
2 collections::BTreeMap,
3 mem::size_of,
4 sync::{Arc, Condvar, Mutex, MutexGuard},
5};
6
7use rusttorch_core::Tensor;
8
9use crate::Bytes;
10
11#[derive(Clone, Copy, Debug, Default)]
13pub struct MemoryDisabled;
14
15#[derive(Clone, Copy, Debug, Default)]
17pub struct MemoryEnabled;
18
19pub trait MemoryFootprint {
26 fn resident_bytes(&self) -> usize;
28}
29
30impl MemoryFootprint for Tensor {
31 fn resident_bytes(&self) -> usize {
32 let Some(bytes) = self.numel().checked_mul(self.kind().elt_size_in_bytes()) else {
33 return usize::MAX;
34 };
35 bytes
36 }
37}
38
39macro_rules! impl_scalar_footprint {
40 ($($type:ty),+ $(,)?) => {
41 $(
42 impl MemoryFootprint for $type {
43 fn resident_bytes(&self) -> usize {
44 size_of::<Self>()
45 }
46 }
47 )+
48 };
49}
50
51impl_scalar_footprint!(u8, i8, i16, i32, i64, f32, f64, bool);
52
53impl MemoryFootprint for String {
54 fn resident_bytes(&self) -> usize {
55 self.capacity()
56 }
57}
58
59impl MemoryFootprint for Bytes {
60 fn resident_bytes(&self) -> usize {
61 self.0.capacity()
62 }
63}
64
65impl<T> MemoryFootprint for Vec<T>
66where
67 T: MemoryFootprint,
68{
69 fn resident_bytes(&self) -> usize {
70 saturating_sum(self.iter().map(MemoryFootprint::resident_bytes))
71 }
72}
73
74impl<T> MemoryFootprint for Option<T>
75where
76 T: MemoryFootprint,
77{
78 fn resident_bytes(&self) -> usize {
79 self.as_ref().map_or(0, MemoryFootprint::resident_bytes)
80 }
81}
82
83impl<K, V> MemoryFootprint for BTreeMap<K, V>
84where
85 K: MemoryFootprint,
86 V: MemoryFootprint,
87{
88 fn resident_bytes(&self) -> usize {
89 saturating_sum(
90 self.iter()
91 .flat_map(|(key, value)| [key.resident_bytes(), value.resident_bytes()]),
92 )
93 }
94}
95
96macro_rules! impl_tuple_footprint {
97 ($(($type:ident, $index:tt)),+ $(,)?) => {
98 impl<$($type),+> MemoryFootprint for ($($type,)+)
99 where
100 $($type: MemoryFootprint),+
101 {
102 fn resident_bytes(&self) -> usize {
103 saturating_sum([$((self.$index).resident_bytes()),+])
104 }
105 }
106 };
107}
108
109impl_tuple_footprint!((A, 0), (B, 1));
110impl_tuple_footprint!((A, 0), (B, 1), (C, 2));
111impl_tuple_footprint!((A, 0), (B, 1), (C, 2), (D, 3));
112impl_tuple_footprint!((A, 0), (B, 1), (C, 2), (D, 3), (E, 4));
113impl_tuple_footprint!((A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5));
114impl_tuple_footprint!((A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6));
115impl_tuple_footprint!(
116 (A, 0),
117 (B, 1),
118 (C, 2),
119 (D, 3),
120 (E, 4),
121 (F, 5),
122 (G, 6),
123 (H, 7)
124);
125
126fn saturating_sum(values: impl IntoIterator<Item = usize>) -> usize {
127 let mut total = 0usize;
128 for value in values {
129 let Some(next) = total.checked_add(value) else {
130 return usize::MAX;
131 };
132 total = next;
133 }
134 total
135}
136
137#[derive(Debug)]
138pub(crate) enum BudgetError {
139 Oversize { limit: usize, actual: usize },
140 Cancelled,
141 SequenceAlreadyAdmitted,
142}
143
144#[derive(Default)]
145struct BudgetState {
146 used: usize,
147 next_ordered: u64,
148 waiters: usize,
149 cancelled: bool,
150}
151
152pub(crate) struct ByteBudget {
153 limit: usize,
154 state: Mutex<BudgetState>,
155 changed: Condvar,
156}
157
158impl ByteBudget {
159 pub(crate) fn new(limit: usize) -> Arc<Self> {
160 Arc::new(Self {
161 limit,
162 state: Mutex::new(BudgetState::default()),
163 changed: Condvar::new(),
164 })
165 }
166
167 pub(crate) fn acquire(self: &Arc<Self>, bytes: usize) -> Result<BytePermit, BudgetError> {
168 self.acquire_inner(None, bytes)
169 }
170
171 pub(crate) fn acquire_ordered(
172 self: &Arc<Self>,
173 sequence: u64,
174 bytes: usize,
175 ) -> Result<BytePermit, BudgetError> {
176 self.acquire_inner(Some(sequence), bytes)
177 }
178
179 fn acquire_inner(
180 self: &Arc<Self>,
181 sequence: Option<u64>,
182 bytes: usize,
183 ) -> Result<BytePermit, BudgetError> {
184 let mut state = lock_recover(&self.state);
185 loop {
186 if state.cancelled {
187 return Err(BudgetError::Cancelled);
188 }
189 if bytes > self.limit {
190 return Err(BudgetError::Oversize {
191 limit: self.limit,
192 actual: bytes,
193 });
194 }
195 if sequence.is_some_and(|sequence| sequence < state.next_ordered) {
196 return Err(BudgetError::SequenceAlreadyAdmitted);
197 }
198 let sequence_ready = sequence.is_none_or(|sequence| sequence == state.next_ordered);
199 if sequence_ready && bytes <= self.limit - state.used {
200 state.used = state.used.saturating_add(bytes);
201 if sequence.is_some() {
202 state.next_ordered = state
203 .next_ordered
204 .checked_add(1)
205 .ok_or(BudgetError::SequenceAlreadyAdmitted)?;
206 self.changed.notify_all();
207 }
208 return Ok(BytePermit {
209 budget: Arc::clone(self),
210 bytes,
211 });
212 }
213 state.waiters = state.waiters.saturating_add(1);
214 self.changed.notify_all();
215 state = match self.changed.wait(state) {
216 Ok(state) => state,
217 Err(poisoned) => poisoned.into_inner(),
218 };
219 state.waiters = state.waiters.saturating_sub(1);
220 }
221 }
222
223 pub(crate) fn cancel(&self) {
224 let mut state = lock_recover(&self.state);
225 state.cancelled = true;
226 self.changed.notify_all();
227 }
228}
229
230fn lock_recover<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
231 match mutex.lock() {
232 Ok(guard) => guard,
233 Err(poisoned) => poisoned.into_inner(),
234 }
235}
236
237pub(crate) struct BytePermit {
238 budget: Arc<ByteBudget>,
239 bytes: usize,
240}
241
242pub(crate) trait MemoryPolicy {
243 type Permit: Send + 'static;
244
245 fn permit(acquired: Option<BytePermit>) -> Self::Permit;
246}
247
248impl MemoryPolicy for MemoryDisabled {
249 type Permit = ();
250
251 fn permit(acquired: Option<BytePermit>) -> Self::Permit {
252 debug_assert!(acquired.is_none());
253 }
254}
255
256impl MemoryPolicy for MemoryEnabled {
257 type Permit = BytePermit;
258
259 fn permit(acquired: Option<BytePermit>) -> Self::Permit {
260 acquired.expect("enabled byte accounting acquires a permit before publication")
261 }
262}
263
264impl Drop for BytePermit {
265 fn drop(&mut self) {
266 let mut state = lock_recover(&self.budget.state);
267 state.used = state.used.saturating_sub(self.bytes);
268 self.budget.changed.notify_all();
269 }
270}
271
272#[cfg(test)]
273mod tests {
274 use std::sync::mpsc;
275 use std::thread;
276
277 use super::*;
278
279 #[test]
280 fn permit_release_and_cancellation_wake_waiters() {
281 let budget = ByteBudget::new(4);
282 let first = budget.acquire(4).unwrap();
283 let waiting = Arc::clone(&budget);
284 let (sender, receiver) = mpsc::sync_channel(0);
285 let handle = thread::spawn(move || {
286 sender.send(waiting.acquire(1).is_ok()).unwrap();
287 });
288 drop(first);
289 assert!(receiver.recv().unwrap());
290 handle.join().unwrap();
291
292 let held = budget.acquire(4).unwrap();
293 let waiting = Arc::clone(&budget);
294 let (sender, receiver) = mpsc::sync_channel(0);
295 let handle = thread::spawn(move || {
296 sender.send(waiting.acquire(1).is_err()).unwrap();
297 });
298 budget.cancel();
299 assert!(receiver.recv().unwrap());
300 drop(held);
301 handle.join().unwrap();
302 }
303
304 #[test]
305 fn exact_limit_never_overgrants_and_release_wakes_the_blocked_acquire() {
306 let budget = ByteBudget::new(5);
307 let first = budget.acquire(3).unwrap();
308 let second = budget.acquire(2).unwrap();
309 let waiting = Arc::clone(&budget);
310 let (admitted_sender, admitted_receiver) = mpsc::sync_channel(0);
311 let handle = thread::spawn(move || {
312 let permit = waiting.acquire(1).unwrap();
313 admitted_sender.send(()).unwrap();
314 drop(permit);
315 });
316
317 let mut state = lock_recover(&budget.state);
318 while state.waiters == 0 {
319 state = match budget.changed.wait(state) {
320 Ok(state) => state,
321 Err(poisoned) => poisoned.into_inner(),
322 };
323 }
324 assert_eq!(state.used, 5);
325 drop(state);
326 assert!(matches!(
327 admitted_receiver.try_recv(),
328 Err(mpsc::TryRecvError::Empty)
329 ));
330 drop(first);
331 admitted_receiver.recv().unwrap();
332 drop(second);
333 handle.join().unwrap();
334 }
335}