//! # Allocate /// # Initialize Queue /// - Name: Symbol name /// - Size: Number of elements /// - Default: Default value /// - Type: Data Type macro_rules! init_queue { ($name:tt,$size:tt,$default:tt,$type:ty) => { init_queue!{@gen [$name,$size,$default,$type,concat!("# ", stringify!($type), " Queue Allocator")]} }; (@gen [$name:tt,$size:tt,$default:tt,$type:ty,$doc:expr]) => { #[doc = $doc] #[link_section = ".data.alloc"] pub static $name: QueueAllocator<'static, $type, {$size+2}> = QueueAllocator::<$type, {$size+2}>{inner: NullLock::new([QueueItem{data: $default, next: None}; {$size+2}])}; }; } use crate::sync::NullLock; use crate::sync::interface::Mutex; use core::fmt::{Debug,Formatter,Result}; #[derive(Copy,Clone)] /// # Queue Item /// /// Encapsulates a data element and a pointer to /// the next `Queue` item pub struct QueueItem<'a, T: Sized> { /// # Data /// /// The encapsulated data data: T, /// # Pointer to the next item /// /// Stores either `None` or points /// to the next item. next: Option<*mut QueueItem<'a, T>>, } impl QueueItem<'_,T> { /// # Get the inner data /// /// Returns a borrow of the underlying data. pub fn inner(&mut self) -> &mut T { &mut self.data } /// # Get pointer to inner data pub fn ptr(&mut self) -> *mut u8 { self.inner() as *mut T as *mut u8 } } /// # Sharing Thread Safety for QueueItem unsafe impl Send for QueueItem<'_,T> {} impl Debug for QueueItem<'_,T> { /// # Debug formatter for `QueueItem` /// /// Output the encapsulated data fn fmt(&self, f: &mut Formatter<'_>) -> Result { write!(f, "{:?}", self.data) } } /// # Queue Allocator /// /// Structure to store a pool of allocated data structures. pub struct QueueAllocator<'a, T: Sized, const COUNT: usize> { /// # Synchronized Pool of items /// /// Stores synchronization wrapper around the data pool pub inner: NullLock<[QueueItem<'a, T>;COUNT]>, } /// # Sharing Thread Safety for QueueAllocator unsafe impl Send for QueueAllocator<'_,T,COUNT> {} impl<'a, T: Sized,const COUNT: usize> QueueAllocator<'a, T, COUNT> { /// # Initialization of Fixed-Size Pool /// /// Establishes the header and footer of the queue /// as the first and second elements respectively. /// All of the internal elements point to the next /// one and the final element points to `None` pub fn init(&self) { self.inner.lock(|queue| { for idx in 2..queue.len() { if idx != queue.len()-1 { queue[idx].next = Some(&mut queue[idx+1] as *mut QueueItem<'_, T>); } else { queue[idx].next = None; } } queue[0].next = Some(&mut queue[2] as *mut QueueItem<'_, T>); queue[1].next = Some(&mut queue[queue.len()-1] as *mut QueueItem<'_, T>); }); } /// # Allocate Data /// /// If there is a data chunk available, /// return it, otherwise return `None` #[allow(dead_code)] pub fn alloc(&self) -> Option<&mut QueueItem<'a,T>> { return self.inner.lock(|pool| { if let Some(entry) = pool[0].next { pool[0].next = unsafe { (*entry).next }; unsafe { (*entry).next = None; } match pool[0].next { None => { pool[1].next = None } _ => {} } return Some(unsafe{&mut *entry as &mut QueueItem<'a,T>}); } else { return None; } }); } /// # Free /// /// Add the item to the end of the queue. /// If there were no items, set it as the head. #[allow(dead_code)] pub fn free(&self, freed_item: &mut QueueItem<'a,T>) { self.inner.lock(|pool| { freed_item.next = None; match pool[1].next { None => { pool[0].next = Some(freed_item as *mut QueueItem<'a,T>); } Some(entry) => { unsafe { (*entry).next = Some(freed_item as *mut QueueItem<'a,T>); } } } pool[1].next = Some(freed_item as *mut QueueItem<'a,T>); }); } } impl Debug for QueueAllocator<'_,T,COUNT> { /// # Debug Formatted Output /// /// Output each data point in the array with /// its debug formatter. fn fmt(&self, f: &mut Formatter<'_>) -> Result { self.inner.lock(|queue| { write!(f, "{:?}", queue) }) } } /// Number of U64s to hand out const U64_POOL_SIZE: usize = 2; init_queue!(U64_QUEUE_ALLOCATOR, U64_POOL_SIZE, 0, u64); extern crate alloc; use alloc::alloc::{GlobalAlloc,Layout}; pub struct GrandAllocator { } const GRAND_ALLOC_SIZE: usize = 64; init_queue!(U8_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u8); init_queue!(U16_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u16); init_queue!(U32_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u32); init_queue!(U64_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u64); init_queue!(U128_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u128); impl GrandAllocator { pub fn init(&self) { U8_GRAND_ALLOC.init(); U16_GRAND_ALLOC.init(); U32_GRAND_ALLOC.init(); U64_GRAND_ALLOC.init(); U128_GRAND_ALLOC.init(); } } unsafe impl GlobalAlloc for GrandAllocator { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { match layout.size() { 1 => { match U8_GRAND_ALLOC.alloc() { None => { panic!("No cells to allocate!"); } Some(elem) => { return (*elem).ptr(); } } } 2 => { match U16_GRAND_ALLOC.alloc() { None => { panic!("No cells to allocate!"); } Some(elem) => { return (*elem).ptr(); } } } 4 => { match U32_GRAND_ALLOC.alloc() { None => { panic!("No cells to allocate!"); } Some(elem) => { return (*elem).ptr(); } } } 8 => { match U64_GRAND_ALLOC.alloc() { None => { panic!("No cells to allocate!"); } Some(elem) => { return (*elem).ptr(); } } } 16 => { match U128_GRAND_ALLOC.alloc() { None => { panic!("No cells to allocate!"); } Some(elem) => { return (*elem).ptr(); } } } _ => { panic!("No allocators for size {}!", layout.size()); } } } unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) { match layout.size() { 1 => { U8_GRAND_ALLOC.inner.lock(|pool| { for idx in 2..pool.len() { if pool[idx].inner() as *mut u8 == ptr { U8_GRAND_ALLOC.free(&mut pool[idx]); return; } } panic!("Didn't deallocate!"); }); } 2 => { U16_GRAND_ALLOC.inner.lock(|pool| { for idx in 2..pool.len() { if pool[idx].ptr() == ptr { U16_GRAND_ALLOC.free(&mut pool[idx]); return; } } panic!("Didn't deallocate!"); }); } 4 => { U32_GRAND_ALLOC.inner.lock(|pool| { for idx in 2..pool.len() { if pool[idx].ptr() == ptr { U32_GRAND_ALLOC.free(&mut pool[idx]); return; } } panic!("Didn't deallocate!"); }); } 8 => { U64_GRAND_ALLOC.inner.lock(|pool| { for idx in 2..pool.len() { if pool[idx].ptr() == ptr { U64_GRAND_ALLOC.free(&mut pool[idx]); return; } } panic!("Didn't deallocate!"); }); } 16 => { U128_GRAND_ALLOC.inner.lock(|pool| { for idx in 2..pool.len() { if pool[idx].ptr() == ptr { U128_GRAND_ALLOC.free(&mut pool[idx]); return; } } panic!("Didn't deallocate!"); }); } _ => { panic!("No deallocators for size {}!", layout.size()); } } } } #[global_allocator] pub static ALLOCATOR: GrandAllocator = GrandAllocator{};