1use crate::error::{LinalgError, LinalgResult};
17use std::collections::{BTreeMap, HashMap, VecDeque};
18use std::fmt::Debug;
19use std::sync::{Arc, Mutex, RwLock};
20use std::time::{Duration, Instant};
21
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub enum AllocationStrategy {
25 BestFit,
27 FirstFit,
29 NextFit,
31 Buddy,
33}
34
35#[derive(Debug, Clone)]
37pub struct MemoryPoolConfig {
38 pub pool_size: usize,
40 pub min_block_size: usize,
42 pub max_block_size: usize,
44 pub alignment: usize,
46 pub strategy: AllocationStrategy,
48 pub enable_defrag: bool,
50 pub defrag_threshold: f64,
52 pub pressure_threshold: f64,
54 pub max_cache_age: Duration,
56}
57
58impl Default for MemoryPoolConfig {
59 fn default() -> Self {
60 #[cfg(target_pointer_width = "32")]
61 let pool_size = 256 * 1024 * 1024; #[cfg(target_pointer_width = "64")]
63 let pool_size = 1024 * 1024 * 1024; Self {
66 pool_size,
67 min_block_size: 256,
68 max_block_size: 64 * 1024 * 1024, alignment: 256, strategy: AllocationStrategy::BestFit,
71 enable_defrag: true,
72 defrag_threshold: 0.3,
73 pressure_threshold: 0.9,
74 max_cache_age: Duration::from_secs(60),
75 }
76 }
77}
78
79#[derive(Debug, Clone)]
81struct MemoryBlock {
82 offset: usize,
84 size: usize,
86 in_use: bool,
88 allocation_id: Option<usize>,
90 last_access: Instant,
92}
93
94#[derive(Debug, Clone)]
96pub struct AllocationHandle {
97 pub id: usize,
99 pub offset: usize,
101 pub size: usize,
103 created_at: Instant,
105}
106
107#[derive(Debug, Clone, Default)]
109pub struct MemoryStats {
110 pub total_size: usize,
112 pub allocated_bytes: usize,
114 pub free_bytes: usize,
116 pub active_allocations: usize,
118 pub total_allocations: usize,
120 pub total_deallocations: usize,
122 pub peak_usage: usize,
124 pub fragmented_blocks: usize,
126 pub fragmentation_ratio: f64,
128 pub cache_hit_rate: f64,
130 pub cache_hits: usize,
132 pub cache_misses: usize,
134}
135
136pub struct GpuMemoryPool {
138 config: MemoryPoolConfig,
139 free_blocks: RwLock<BTreeMap<usize, Vec<usize>>>,
141 blocks: RwLock<HashMap<usize, MemoryBlock>>,
143 allocations: RwLock<HashMap<usize, AllocationHandle>>,
145 block_cache: Mutex<HashMap<usize, VecDeque<usize>>>,
147 next_id: Mutex<usize>,
149 stats: RwLock<MemoryStats>,
151 last_offset: Mutex<usize>,
153}
154
155impl GpuMemoryPool {
156 pub fn new() -> Self {
158 Self::with_config(MemoryPoolConfig::default())
159 }
160
161 pub fn with_config(config: MemoryPoolConfig) -> Self {
163 let pool_size = config.pool_size;
164
165 let mut blocks = HashMap::new();
166 blocks.insert(
167 0,
168 MemoryBlock {
169 offset: 0,
170 size: pool_size,
171 in_use: false,
172 allocation_id: None,
173 last_access: Instant::now(),
174 },
175 );
176
177 let mut free_blocks = BTreeMap::new();
178 free_blocks.insert(pool_size, vec![0]);
179
180 let stats = MemoryStats {
181 total_size: pool_size,
182 free_bytes: pool_size,
183 ..Default::default()
184 };
185
186 Self {
187 config,
188 free_blocks: RwLock::new(free_blocks),
189 blocks: RwLock::new(blocks),
190 allocations: RwLock::new(HashMap::new()),
191 block_cache: Mutex::new(HashMap::new()),
192 next_id: Mutex::new(1),
193 stats: RwLock::new(stats),
194 last_offset: Mutex::new(0),
195 }
196 }
197
198 pub fn allocate(&self, size: usize) -> LinalgResult<AllocationHandle> {
200 let aligned_size = self.align_size(size);
202
203 if aligned_size > self.config.max_block_size {
205 return Err(LinalgError::ComputationError(format!(
206 "Allocation size {} exceeds maximum block size {}",
207 aligned_size, self.config.max_block_size
208 )));
209 }
210
211 if let Some(offset) = self.try_cache(aligned_size) {
213 return self.complete_allocation(offset, aligned_size);
214 }
215
216 let block_offset = match self.config.strategy {
218 AllocationStrategy::BestFit => self.find_best_fit(aligned_size)?,
219 AllocationStrategy::FirstFit => self.find_first_fit(aligned_size)?,
220 AllocationStrategy::NextFit => self.find_next_fit(aligned_size)?,
221 AllocationStrategy::Buddy => self.find_buddy_block(aligned_size)?,
222 };
223
224 if let Ok(mut stats) = self.stats.write() {
226 stats.cache_misses += 1;
227 self.update_cache_hit_rate(&mut stats);
228 }
229
230 self.complete_allocation(block_offset, aligned_size)
231 }
232
233 fn try_cache(&self, size: usize) -> Option<usize> {
235 if let Ok(mut cache) = self.block_cache.lock() {
236 if let Some(offsets) = cache.get_mut(&size) {
237 if let Some(offset) = offsets.pop_front() {
238 if let Ok(mut stats) = self.stats.write() {
239 stats.cache_hits += 1;
240 self.update_cache_hit_rate(&mut stats);
241 }
242 return Some(offset);
243 }
244 }
245 }
246 None
247 }
248
249 fn complete_allocation(&self, offset: usize, size: usize) -> LinalgResult<AllocationHandle> {
251 let id = {
253 let mut id_guard = self
254 .next_id
255 .lock()
256 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
257 let id = *id_guard;
258 *id_guard += 1;
259 id
260 };
261
262 {
264 let mut blocks = self
265 .blocks
266 .write()
267 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
268 let mut free_blocks = self
269 .free_blocks
270 .write()
271 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
272
273 if let Some(original_size) = blocks.get(&offset).map(|b| b.size) {
274 if original_size > size {
276 let remaining_offset = offset + size;
277 let remaining_size = original_size - size;
278
279 blocks.insert(
280 remaining_offset,
281 MemoryBlock {
282 offset: remaining_offset,
283 size: remaining_size,
284 in_use: false,
285 allocation_id: None,
286 last_access: Instant::now(),
287 },
288 );
289
290 free_blocks
292 .entry(remaining_size)
293 .or_default()
294 .push(remaining_offset);
295 }
296
297 if let Some(block) = blocks.get_mut(&offset) {
299 block.size = size;
300 block.in_use = true;
301 block.allocation_id = Some(id);
302 block.last_access = Instant::now();
303 }
304
305 if let Some(offsets) = free_blocks.get_mut(&original_size) {
307 offsets.retain(|&o| o != offset);
308 if offsets.is_empty() {
309 free_blocks.remove(&original_size);
310 }
311 }
312 }
313 }
314
315 let handle = AllocationHandle {
316 id,
317 offset,
318 size,
319 created_at: Instant::now(),
320 };
321
322 if let Ok(mut allocs) = self.allocations.write() {
324 allocs.insert(id, handle.clone());
325 }
326
327 if let Ok(mut stats) = self.stats.write() {
329 stats.allocated_bytes += size;
330 stats.free_bytes = stats.free_bytes.saturating_sub(size);
331 stats.active_allocations += 1;
332 stats.total_allocations += 1;
333 stats.peak_usage = stats.peak_usage.max(stats.allocated_bytes);
334 }
335
336 Ok(handle)
337 }
338
339 fn find_best_fit(&self, size: usize) -> LinalgResult<usize> {
341 let free_blocks = self
342 .free_blocks
343 .read()
344 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
345
346 for (&block_size, offsets) in free_blocks.range(size..) {
348 if let Some(&offset) = offsets.first() {
349 return Ok(offset);
350 }
351 }
352
353 Err(LinalgError::ComputationError(
354 "No suitable free block found".to_string(),
355 ))
356 }
357
358 fn find_first_fit(&self, size: usize) -> LinalgResult<usize> {
360 let blocks = self
361 .blocks
362 .read()
363 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
364
365 let mut offsets: Vec<_> = blocks
367 .iter()
368 .filter(|(_, b)| !b.in_use && b.size >= size)
369 .map(|(&o, _)| o)
370 .collect();
371 offsets.sort();
372
373 offsets.into_iter().next().ok_or_else(|| {
374 LinalgError::ComputationError("No suitable free block found".to_string())
375 })
376 }
377
378 fn find_next_fit(&self, size: usize) -> LinalgResult<usize> {
380 let last_offset = *self
381 .last_offset
382 .lock()
383 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
384
385 let blocks = self
386 .blocks
387 .read()
388 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
389
390 let mut offsets: Vec<_> = blocks
392 .iter()
393 .filter(|(_, b)| !b.in_use && b.size >= size)
394 .map(|(&o, _)| o)
395 .collect();
396 offsets.sort();
397
398 for &offset in &offsets {
400 if offset >= last_offset {
401 if let Ok(mut last) = self.last_offset.lock() {
402 *last = offset;
403 }
404 return Ok(offset);
405 }
406 }
407
408 if let Some(&offset) = offsets.first() {
410 if let Ok(mut last) = self.last_offset.lock() {
411 *last = offset;
412 }
413 return Ok(offset);
414 }
415
416 Err(LinalgError::ComputationError(
417 "No suitable free block found".to_string(),
418 ))
419 }
420
421 fn find_buddy_block(&self, size: usize) -> LinalgResult<usize> {
423 let buddy_size = size.next_power_of_two();
425 self.find_best_fit(buddy_size)
426 }
427
428 pub fn deallocate(&self, handle: &AllocationHandle) -> LinalgResult<()> {
430 let offset = handle.offset;
431 let size = handle.size;
432
433 if let Ok(mut allocs) = self.allocations.write() {
435 allocs.remove(&handle.id);
436 }
437
438 {
440 let mut blocks = self
441 .blocks
442 .write()
443 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
444 let mut free_blocks = self
445 .free_blocks
446 .write()
447 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
448
449 if let Some(block) = blocks.get_mut(&offset) {
450 block.in_use = false;
451 block.allocation_id = None;
452 block.last_access = Instant::now();
453
454 free_blocks.entry(size).or_default().push(offset);
456 }
457 }
458
459 self.try_coalesce(offset)?;
461
462 if let Ok(mut cache) = self.block_cache.lock() {
464 let offsets = cache.entry(size).or_default();
465 if offsets.len() < 16 {
466 offsets.push_back(offset);
468 }
469 }
470
471 if let Ok(mut stats) = self.stats.write() {
473 stats.allocated_bytes = stats.allocated_bytes.saturating_sub(size);
474 stats.free_bytes += size;
475 stats.active_allocations = stats.active_allocations.saturating_sub(1);
476 stats.total_deallocations += 1;
477 }
478
479 Ok(())
480 }
481
482 fn try_coalesce(&self, offset: usize) -> LinalgResult<()> {
484 let mut blocks = self
485 .blocks
486 .write()
487 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
488 let mut free_blocks = self
489 .free_blocks
490 .write()
491 .map_err(|_| LinalgError::ComputationError("Lock poisoned".to_string()))?;
492
493 let (current_size, current_end) = {
495 if let Some(block) = blocks.get(&offset) {
496 if block.in_use {
497 return Ok(()); }
499 (block.size, offset + block.size)
500 } else {
501 return Ok(());
502 }
503 };
504
505 if let Some(next_block) = blocks.get(¤t_end).cloned() {
507 if !next_block.in_use {
508 blocks.remove(¤t_end);
510
511 if let Some(offsets) = free_blocks.get_mut(&next_block.size) {
513 offsets.retain(|&o| o != current_end);
514 if offsets.is_empty() {
515 free_blocks.remove(&next_block.size);
516 }
517 }
518
519 if let Some(block) = blocks.get_mut(&offset) {
521 if let Some(offsets) = free_blocks.get_mut(&block.size) {
523 offsets.retain(|&o| o != offset);
524 if offsets.is_empty() {
525 free_blocks.remove(&block.size);
526 }
527 }
528
529 block.size += next_block.size;
530
531 free_blocks.entry(block.size).or_default().push(offset);
533 }
534 }
535 }
536
537 let prev_info: Option<(usize, usize)> = blocks
539 .iter()
540 .filter(|(_, b)| !b.in_use && b.offset + b.size == offset)
541 .map(|(&o, b)| (o, b.size))
542 .next();
543
544 if let Some((prev_offset, prev_size)) = prev_info {
545 let current_size_now = blocks.get(&offset).map(|b| b.size).unwrap_or(0);
547 blocks.remove(&offset);
548
549 if let Some(offsets) = free_blocks.get_mut(¤t_size_now) {
551 offsets.retain(|&o| o != offset);
552 if offsets.is_empty() {
553 free_blocks.remove(¤t_size_now);
554 }
555 }
556
557 if let Some(offsets) = free_blocks.get_mut(&prev_size) {
558 offsets.retain(|&o| o != prev_offset);
559 if offsets.is_empty() {
560 free_blocks.remove(&prev_size);
561 }
562 }
563
564 if let Some(prev_block) = blocks.get_mut(&prev_offset) {
566 prev_block.size += current_size_now;
567
568 free_blocks
570 .entry(prev_block.size)
571 .or_default()
572 .push(prev_offset);
573 }
574 }
575
576 Ok(())
577 }
578
579 pub fn stats(&self) -> MemoryStats {
581 self.stats.read().map(|s| s.clone()).unwrap_or_default()
582 }
583
584 pub fn fragmentation_ratio(&self) -> f64 {
586 if let Ok(blocks) = self.blocks.read() {
587 let free_blocks: Vec<_> = blocks.values().filter(|b| !b.in_use).collect();
588
589 if free_blocks.is_empty() {
590 return 0.0;
591 }
592
593 let total_free: usize = free_blocks.iter().map(|b| b.size).sum();
594 let largest_free = free_blocks.iter().map(|b| b.size).max().unwrap_or(0);
595
596 if total_free == 0 {
597 return 0.0;
598 }
599
600 1.0 - (largest_free as f64 / total_free as f64)
601 } else {
602 0.0
603 }
604 }
605
606 pub fn maybe_defragment(&self) -> LinalgResult<bool> {
608 let frag_ratio = self.fragmentation_ratio();
609
610 if frag_ratio > self.config.defrag_threshold && self.config.enable_defrag {
611 self.defragment()?;
612 return Ok(true);
613 }
614
615 Ok(false)
616 }
617
618 pub fn defragment(&self) -> LinalgResult<()> {
620 if let Ok(mut stats) = self.stats.write() {
623 stats.fragmentation_ratio = self.fragmentation_ratio();
624 stats.fragmented_blocks = self.count_fragmented_blocks();
625 }
626 Ok(())
627 }
628
629 fn count_fragmented_blocks(&self) -> usize {
631 self.blocks
632 .read()
633 .map(|blocks| blocks.values().filter(|b| !b.in_use).count())
634 .unwrap_or(0)
635 }
636
637 pub fn evict_old_caches(&self) -> LinalgResult<usize> {
639 let now = Instant::now();
640 let mut evicted = 0;
641
642 if let Ok(mut cache) = self.block_cache.lock() {
643 for offsets in cache.values_mut() {
644 let initial_len = offsets.len();
645 while offsets.len() > 8 {
647 offsets.pop_front();
648 evicted += 1;
649 }
650 evicted += initial_len.saturating_sub(offsets.len());
651 }
652 }
653
654 Ok(evicted)
655 }
656
657 pub fn reset(&self) -> LinalgResult<()> {
659 let pool_size = self.config.pool_size;
660
661 if let Ok(mut blocks) = self.blocks.write() {
663 blocks.clear();
664 blocks.insert(
665 0,
666 MemoryBlock {
667 offset: 0,
668 size: pool_size,
669 in_use: false,
670 allocation_id: None,
671 last_access: Instant::now(),
672 },
673 );
674 }
675
676 if let Ok(mut free_blocks) = self.free_blocks.write() {
677 free_blocks.clear();
678 free_blocks.insert(pool_size, vec![0]);
679 }
680
681 if let Ok(mut allocs) = self.allocations.write() {
682 allocs.clear();
683 }
684
685 if let Ok(mut cache) = self.block_cache.lock() {
686 cache.clear();
687 }
688
689 if let Ok(mut stats) = self.stats.write() {
690 *stats = MemoryStats {
691 total_size: pool_size,
692 free_bytes: pool_size,
693 ..Default::default()
694 };
695 }
696
697 Ok(())
698 }
699
700 fn align_size(&self, size: usize) -> usize {
702 let alignment = self.config.alignment;
703 size.div_ceil(alignment) * alignment
704 }
705
706 fn update_cache_hit_rate(&self, stats: &mut MemoryStats) {
708 let total = stats.cache_hits + stats.cache_misses;
709 if total > 0 {
710 stats.cache_hit_rate = stats.cache_hits as f64 / total as f64;
711 }
712 }
713}
714
715impl Default for GpuMemoryPool {
716 fn default() -> Self {
717 Self::new()
718 }
719}
720
721pub struct SharedMemoryPool {
723 pool: Arc<GpuMemoryPool>,
724}
725
726impl SharedMemoryPool {
727 pub fn new() -> Self {
729 Self {
730 pool: Arc::new(GpuMemoryPool::new()),
731 }
732 }
733
734 pub fn with_config(config: MemoryPoolConfig) -> Self {
736 Self {
737 pool: Arc::new(GpuMemoryPool::with_config(config)),
738 }
739 }
740
741 pub fn allocate(&self, size: usize) -> LinalgResult<AllocationHandle> {
743 self.pool.allocate(size)
744 }
745
746 pub fn deallocate(&self, handle: &AllocationHandle) -> LinalgResult<()> {
748 self.pool.deallocate(handle)
749 }
750
751 pub fn stats(&self) -> MemoryStats {
753 self.pool.stats()
754 }
755
756 pub fn clone_ref(&self) -> Self {
758 Self {
759 pool: Arc::clone(&self.pool),
760 }
761 }
762}
763
764impl Default for SharedMemoryPool {
765 fn default() -> Self {
766 Self::new()
767 }
768}
769
770impl Clone for SharedMemoryPool {
771 fn clone(&self) -> Self {
772 self.clone_ref()
773 }
774}
775
776#[cfg(test)]
777mod tests {
778 use super::*;
779
780 #[test]
781 fn test_basic_allocation() {
782 let pool = GpuMemoryPool::new();
783
784 let handle1 = pool.allocate(1024).expect("Allocation failed");
785 assert_eq!(handle1.size, 1024);
786
787 let stats = pool.stats();
788 assert_eq!(stats.active_allocations, 1);
789 assert!(stats.allocated_bytes >= 1024);
790 }
791
792 #[test]
793 fn test_multiple_allocations() {
794 let pool = GpuMemoryPool::new();
795
796 let handles: Vec<_> = (0..10)
797 .map(|_| pool.allocate(1024).expect("Allocation failed"))
798 .collect();
799
800 assert_eq!(handles.len(), 10);
801
802 let stats = pool.stats();
803 assert_eq!(stats.active_allocations, 10);
804 }
805
806 #[test]
807 fn test_allocation_and_deallocation() {
808 let pool = GpuMemoryPool::new();
809
810 let handle = pool.allocate(1024).expect("Allocation failed");
811 assert_eq!(pool.stats().active_allocations, 1);
812
813 pool.deallocate(&handle).expect("Deallocation failed");
814 assert_eq!(pool.stats().active_allocations, 0);
815 }
816
817 #[test]
818 fn test_reuse_after_deallocation() {
819 let pool = GpuMemoryPool::new();
820
821 let handle1 = pool.allocate(1024).expect("Allocation failed");
822 let offset1 = handle1.offset;
823
824 pool.deallocate(&handle1).expect("Deallocation failed");
825
826 let handle2 = pool.allocate(1024).expect("Allocation failed");
827 assert!(handle2.offset == offset1 || pool.stats().cache_hits > 0);
829 }
830
831 #[test]
832 fn test_fragmentation_calculation() {
833 let config = MemoryPoolConfig {
834 pool_size: 10240,
835 min_block_size: 256,
836 ..Default::default()
837 };
838 let pool = GpuMemoryPool::with_config(config);
839
840 let handles: Vec<_> = (0..5)
842 .map(|_| pool.allocate(1024).expect("Allocation failed"))
843 .collect();
844
845 for (i, handle) in handles.iter().enumerate() {
847 if i % 2 == 0 {
848 pool.deallocate(handle).expect("Deallocation failed");
849 }
850 }
851
852 let frag_ratio = pool.fragmentation_ratio();
853 assert!((0.0..=1.0).contains(&frag_ratio));
854 }
855
856 #[test]
857 fn test_reset() {
858 let pool = GpuMemoryPool::new();
859
860 for _ in 0..10 {
862 let _ = pool.allocate(1024);
863 }
864
865 assert!(pool.stats().active_allocations > 0);
866
867 pool.reset().expect("Reset failed");
869
870 let stats = pool.stats();
871 assert_eq!(stats.active_allocations, 0);
872 assert_eq!(stats.allocated_bytes, 0);
873 }
874
875 #[test]
876 fn test_shared_pool() {
877 let pool = SharedMemoryPool::new();
878 let pool2 = pool.clone_ref();
879
880 let handle = pool.allocate(1024).expect("Allocation failed");
881 assert_eq!(pool2.stats().active_allocations, 1);
882
883 pool2.deallocate(&handle).expect("Deallocation failed");
884 assert_eq!(pool.stats().active_allocations, 0);
885 }
886
887 #[test]
888 fn test_alignment() {
889 let config = MemoryPoolConfig {
890 alignment: 256,
891 ..Default::default()
892 };
893 let pool = GpuMemoryPool::with_config(config);
894
895 let handle = pool.allocate(100).expect("Allocation failed");
896 assert!(handle.size >= 100);
897 assert!(handle.size % 256 == 0 || handle.size == 256);
898 }
899}