Skip to main content

tpt_gpu_runtime/memory/
allocator.rs

1//! GPU Memory Allocators: Slab, Buddy, and Fallback strategies.
2use 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    /// Release the bookkeeping for an allocation by its handle alone, without
35    /// re-matching the device pointer (used when the real device pointer has
36    /// been substituted for the allocator's fake address).
37    fn free_handle(&mut self, handle: u64) -> TptrResult<()>;
38    fn stats(&self) -> AllocatorStats;
39    fn reset(&mut self) -> TptrResult<()>;
40}
41
42// Slab Allocator
43#[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// Buddy Allocator
136#[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// Fallback Allocator
275#[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}