1use crate::error::{ErrorCode, TptrError, TptrResult};
3use crate::memory::types::{Alignment, MemAccess, MemType, MemoryAllocation, MemoryRegion};
4use std::collections::HashMap;
5use std::sync::atomic::{AtomicU64, Ordering};
6
7#[derive(Debug, Clone, Default)]
8pub struct AllocatorStats {
9 pub total_allocations: u64,
10 pub total_frees: u64,
11 pub bytes_allocated: u64,
12 pub bytes_freed: u64,
13 pub current_usage: u64,
14 pub peak_usage: u64,
15 pub allocation_failures: u64,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum AllocationStrategy {
20 Slab,
21 Buddy,
22 Fallback,
23}
24
25pub trait GpuAllocator: Send + Sync {
26 fn allocate(
27 &mut self,
28 size: u64,
29 region: MemoryRegion,
30 mem_type: MemType,
31 access: MemAccess,
32 ) -> TptrResult<MemoryAllocation>;
33 fn free(&mut self, allocation: &MemoryAllocation) -> TptrResult<()>;
34 fn free_handle(&mut self, handle: u64) -> TptrResult<()>;
38 fn stats(&self) -> AllocatorStats;
39 fn reset(&mut self) -> TptrResult<()>;
40}
41
42#[derive(Debug)]
44struct Slab {
45 base_addr: u64,
46 free_list: Vec<u64>,
47 block_size: u64,
48}
49
50#[derive(Debug)]
51pub struct SlabAllocator {
52 slab_size: u64,
53 slabs: Vec<Slab>,
54 next_handle: AtomicU64,
55 stats: AllocatorStats,
56}
57
58impl SlabAllocator {
59 pub fn new(base_addr: u64, total_size: u64, block_size: u64) -> Self {
60 let bs = block_size.max(256);
61 let num = total_size / bs;
62 let free: Vec<u64> = (0..num).map(|i| base_addr + i * bs).collect();
63 Self {
64 slab_size: total_size,
65 slabs: vec![Slab {
66 base_addr,
67 free_list: free,
68 block_size: bs,
69 }],
70 next_handle: AtomicU64::new(1),
71 stats: AllocatorStats::default(),
72 }
73 }
74}
75
76impl GpuAllocator for SlabAllocator {
77 fn allocate(
78 &mut self,
79 size: u64,
80 region: MemoryRegion,
81 mem_type: MemType,
82 access: MemAccess,
83 ) -> TptrResult<MemoryAllocation> {
84 let bs = self.slabs[0].block_size;
85 let needed = size.div_ceil(bs);
86 for slab in &mut self.slabs {
87 if slab.free_list.len() >= needed as usize {
88 let dp = slab.free_list.pop().unwrap_or(0);
89 let h = self.next_handle.fetch_add(1, Ordering::SeqCst);
90 let asize = needed * bs;
91 self.stats.total_allocations += 1;
92 self.stats.bytes_allocated += asize;
93 self.stats.current_usage += asize;
94 self.stats.peak_usage = self.stats.peak_usage.max(self.stats.current_usage);
95 return Ok(MemoryAllocation::new(
96 h,
97 asize,
98 region,
99 mem_type,
100 access,
101 dp,
102 Alignment::DEFAULT,
103 ));
104 }
105 }
106 self.stats.allocation_failures += 1;
107 Err(TptrError::new(
108 ErrorCode::OutOfMemory,
109 format!("SlabAllocator: no free block for size {}", size),
110 ))
111 }
112 fn free(&mut self, allocation: &MemoryAllocation) -> TptrResult<()> {
113 allocation.mark_freed();
114 self.slabs[0].free_list.push(allocation.device_ptr());
115 self.stats.bytes_freed += allocation.size();
116 self.stats.current_usage = self.stats.current_usage.saturating_sub(allocation.size());
117 self.stats.total_frees += 1;
118 Ok(())
119 }
120 fn free_handle(&mut self, _handle: u64) -> TptrResult<()> {
121 Ok(())
122 }
123 fn stats(&self) -> AllocatorStats {
124 self.stats.clone()
125 }
126 fn reset(&mut self) -> TptrResult<()> {
127 let bs = self.slabs[0].block_size;
128 let num = self.slab_size / bs;
129 self.slabs[0].free_list = (0..num).map(|i| self.slabs[0].base_addr + i * bs).collect();
130 self.stats = AllocatorStats::default();
131 Ok(())
132 }
133}
134
135#[derive(Debug, Clone)]
137struct BuddyBlock {
138 addr: u64,
139 order: usize,
140}
141
142#[derive(Debug)]
143pub struct BuddyAllocator {
144 base_addr: u64,
145 min_block: u64,
146 free_lists: Vec<Vec<u64>>,
147 allocations: HashMap<u64, BuddyBlock>,
148 next_handle: AtomicU64,
149 stats: AllocatorStats,
150}
151
152impl BuddyAllocator {
153 pub fn new(base_addr: u64, total_size: u64, min_block: u64) -> Self {
154 let mb = min_block.next_power_of_two().max(256);
155 let ts = total_size.next_power_of_two().max(mb);
156 let mo = (ts / mb).trailing_zeros() as usize;
157 let mut fl = vec![Vec::new(); mo + 1];
158 fl[mo].push(base_addr);
159 Self {
160 base_addr,
161 min_block: mb,
162 free_lists: fl,
163 allocations: HashMap::new(),
164 next_handle: AtomicU64::new(1),
165 stats: AllocatorStats::default(),
166 }
167 }
168 fn order_for(&self, size: u64) -> usize {
169 let a = size.next_power_of_two().max(self.min_block);
170 ((a / self.min_block) as f64).log2().ceil() as usize
171 }
172 fn block_size(&self, order: usize) -> u64 {
173 self.min_block * (1 << order)
174 }
175 fn buddy(&self, addr: u64, size: u64) -> u64 {
176 addr ^ size
177 }
178}
179
180impl GpuAllocator for BuddyAllocator {
181 fn allocate(
182 &mut self,
183 size: u64,
184 region: MemoryRegion,
185 mem_type: MemType,
186 access: MemAccess,
187 ) -> TptrResult<MemoryAllocation> {
188 let order = self.order_for(size);
189 let asize = self.block_size(order);
190 let mut found = false;
191 let mut addr = 0u64;
192 let mut ao = order;
193 for o in order..self.free_lists.len() {
194 if let Some(b) = self.free_lists[o].pop() {
195 addr = b;
196 ao = o;
197 found = true;
198 break;
199 }
200 }
201 if !found {
202 self.stats.allocation_failures += 1;
203 return Err(TptrError::new(
204 ErrorCode::OutOfMemory,
205 format!("BuddyAllocator: no free block for size {}", size),
206 ));
207 }
208 while ao > order {
209 ao -= 1;
210 let half = self.block_size(ao);
211 self.free_lists[ao].push(addr + half);
212 }
213 let h = self.next_handle.fetch_add(1, Ordering::SeqCst);
214 self.allocations.insert(addr, BuddyBlock { addr, order });
215 self.stats.total_allocations += 1;
216 self.stats.bytes_allocated += asize;
217 self.stats.current_usage += asize;
218 self.stats.peak_usage = self.stats.peak_usage.max(self.stats.current_usage);
219 Ok(MemoryAllocation::new(
220 h,
221 asize,
222 region,
223 mem_type,
224 access,
225 addr,
226 Alignment::DEFAULT,
227 ))
228 }
229 fn free(&mut self, allocation: &MemoryAllocation) -> TptrResult<()> {
230 allocation.mark_freed();
231 let addr = allocation.device_ptr();
232 let block = self.allocations.remove(&addr).ok_or_else(|| {
233 TptrError::new(
234 ErrorCode::InvalidAddress,
235 format!("double free at {:x}", addr),
236 )
237 })?;
238 let mut fa = block.addr;
239 let mut fo = block.order;
240 while fo < self.free_lists.len() - 1 {
241 let b = self.buddy(fa, self.block_size(fo));
242 if let Some(pos) = self.free_lists[fo].iter().position(|&x| x == b) {
243 self.free_lists[fo].swap_remove(pos);
244 fa = fa.min(b);
245 fo += 1;
246 } else {
247 break;
248 }
249 }
250 self.free_lists[fo].push(fa);
251 self.stats.bytes_freed += allocation.size();
252 self.stats.current_usage = self.stats.current_usage.saturating_sub(allocation.size());
253 self.stats.total_frees += 1;
254 Ok(())
255 }
256 fn free_handle(&mut self, _handle: u64) -> TptrResult<()> {
257 Ok(())
258 }
259 fn stats(&self) -> AllocatorStats {
260 self.stats.clone()
261 }
262 fn reset(&mut self) -> TptrResult<()> {
263 let mo = self.free_lists.len() - 1;
264 for list in &mut self.free_lists {
265 list.clear();
266 }
267 self.free_lists[mo].push(self.base_addr);
268 self.allocations.clear();
269 self.stats = AllocatorStats::default();
270 Ok(())
271 }
272}
273
274#[derive(Debug)]
276pub struct FallbackAllocator {
277 base_addr: u64,
278 total_size: u64,
279 next_free: u64,
280 next_handle: AtomicU64,
281 stats: AllocatorStats,
282}
283
284impl FallbackAllocator {
285 pub fn new(base_addr: u64, total_size: u64) -> Self {
286 Self {
287 base_addr,
288 total_size,
289 next_free: base_addr,
290 next_handle: AtomicU64::new(1),
291 stats: AllocatorStats::default(),
292 }
293 }
294}
295
296impl GpuAllocator for FallbackAllocator {
297 fn allocate(
298 &mut self,
299 size: u64,
300 region: MemoryRegion,
301 mem_type: MemType,
302 access: MemAccess,
303 ) -> TptrResult<MemoryAllocation> {
304 let aligned = Alignment(256).align_up(size);
305 let end = self
306 .next_free
307 .checked_add(aligned)
308 .ok_or_else(|| TptrError::new(ErrorCode::OutOfMemory, "overflow"))?;
309 if end > self.base_addr + self.total_size {
310 self.stats.allocation_failures += 1;
311 return Err(TptrError::new(ErrorCode::OutOfMemory, "OOM"));
312 }
313 let addr = self.next_free;
314 self.next_free = end;
315 let h = self.next_handle.fetch_add(1, Ordering::SeqCst);
316 self.stats.total_allocations += 1;
317 self.stats.bytes_allocated += aligned;
318 self.stats.current_usage += aligned;
319 self.stats.peak_usage = self.stats.peak_usage.max(self.stats.current_usage);
320 Ok(MemoryAllocation::new(
321 h,
322 aligned,
323 region,
324 mem_type,
325 access,
326 addr,
327 Alignment::DEFAULT,
328 ))
329 }
330 fn free(&mut self, allocation: &MemoryAllocation) -> TptrResult<()> {
331 allocation.mark_freed();
332 self.stats.bytes_freed += allocation.size();
333 self.stats.current_usage = self.stats.current_usage.saturating_sub(allocation.size());
334 self.stats.total_frees += 1;
335 Ok(())
336 }
337 fn free_handle(&mut self, _handle: u64) -> TptrResult<()> {
338 Ok(())
339 }
340 fn stats(&self) -> AllocatorStats {
341 self.stats.clone()
342 }
343 fn reset(&mut self) -> TptrResult<()> {
344 self.next_free = self.base_addr;
345 self.stats = AllocatorStats::default();
346 Ok(())
347 }
348}
349
350#[cfg(test)]
351mod tests {
352 use super::*;
353 #[test]
354 fn test_slab() {
355 let mut a = SlabAllocator::new(0x1000_0000, 1 << 20, 4096);
356 let m = a
357 .allocate(
358 1024,
359 MemoryRegion::Global,
360 MemType::Device,
361 MemAccess::ReadWrite,
362 )
363 .unwrap();
364 assert!(m.device_ptr() >= 0x1000_0000);
365 a.free(&m).unwrap();
366 assert!(m.is_freed());
367 }
368 #[test]
369 fn test_buddy() {
370 let mut a = BuddyAllocator::new(0x2000_0000, 1 << 24, 4096);
371 let m1 = a
372 .allocate(
373 4096,
374 MemoryRegion::Global,
375 MemType::Device,
376 MemAccess::ReadWrite,
377 )
378 .unwrap();
379 assert_eq!(m1.device_ptr(), 0x2000_0000);
380 let m2 = a
381 .allocate(
382 4096,
383 MemoryRegion::Global,
384 MemType::Device,
385 MemAccess::ReadWrite,
386 )
387 .unwrap();
388 assert_eq!(m2.device_ptr(), 0x2000_1000);
389 a.free(&m1).unwrap();
390 a.free(&m2).unwrap();
391 let m3 = a
392 .allocate(
393 8192,
394 MemoryRegion::Global,
395 MemType::Device,
396 MemAccess::ReadWrite,
397 )
398 .unwrap();
399 assert_eq!(m3.device_ptr(), 0x2000_0000);
400 }
401 #[test]
402 fn test_fallback() {
403 let mut a = FallbackAllocator::new(0x3000_0000, 1 << 20);
404 let m = a
405 .allocate(
406 65536,
407 MemoryRegion::Global,
408 MemType::Device,
409 MemAccess::ReadWrite,
410 )
411 .unwrap();
412 assert_eq!(m.device_ptr(), 0x3000_0000);
413 }
414 #[test]
415 fn test_oom() {
416 let mut a = FallbackAllocator::new(0x4000_0000, 4096);
417 let _ = a
418 .allocate(
419 4096,
420 MemoryRegion::Global,
421 MemType::Device,
422 MemAccess::ReadWrite,
423 )
424 .unwrap();
425 assert!(a
426 .allocate(
427 1,
428 MemoryRegion::Global,
429 MemType::Device,
430 MemAccess::ReadWrite
431 )
432 .is_err());
433 }
434 #[test]
435 fn test_reset() {
436 let mut a = BuddyAllocator::new(0x5000_0000, 1 << 20, 4096);
437 let m = a
438 .allocate(
439 4096,
440 MemoryRegion::Global,
441 MemType::Device,
442 MemAccess::ReadWrite,
443 )
444 .unwrap();
445 a.free(&m).unwrap();
446 a.reset().unwrap();
447 let m2 = a
448 .allocate(
449 4096,
450 MemoryRegion::Global,
451 MemType::Device,
452 MemAccess::ReadWrite,
453 )
454 .unwrap();
455 assert_eq!(m2.device_ptr(), 0x5000_0000);
456 }
457}