From fe157268a376f5b945f1d64629e051340b06e6f2 Mon Sep 17 00:00:00 2001 From: Christian Cunningham Date: Fri, 19 Aug 2022 23:13:53 -0700 Subject: New allocation --- src/alloc.rs | 157 ---------------------------- src/kernel.rs | 31 +++++- src/mem.rs | 1 + src/mem/alloc.rs | 301 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/panic_wait.rs | 26 ++++- 5 files changed, 352 insertions(+), 164 deletions(-) delete mode 100644 src/alloc.rs create mode 100644 src/mem.rs create mode 100644 src/mem/alloc.rs (limited to 'src') diff --git a/src/alloc.rs b/src/alloc.rs deleted file mode 100644 index 0c0df56..0000000 --- a/src/alloc.rs +++ /dev/null @@ -1,157 +0,0 @@ -//! # 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 - } -} -/// # 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 { - if (entry as u32) == (freed_item as *mut QueueItem<'a,T> as u32) { - (*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); diff --git a/src/kernel.rs b/src/kernel.rs index 3f10849..19c4e5f 100644 --- a/src/kernel.rs +++ b/src/kernel.rs @@ -12,10 +12,14 @@ #![feature(panic_info_message)] #![feature(trait_alias)] #![feature(exclusive_range_pattern)] +#![feature(default_alloc_error_handler)] #![no_main] #![no_std] -mod alloc; +extern crate alloc; +use alloc::boxed::Box; + +mod mem; mod console; mod cpu; mod panic_wait; @@ -23,7 +27,8 @@ mod print; mod sync; mod uart; use crate::console::console; -use crate::alloc::*; +use crate::mem::alloc::*; +//use crate::sync::interface::Mutex; /// # Initialization Code /// @@ -36,6 +41,10 @@ use crate::alloc::*; unsafe fn kernel_init() -> ! { console().init().unwrap(); U64_QUEUE_ALLOCATOR.init(); + ALLOCATOR.init(); + //ALLOCATOR.lock(|qa| { + // qa.init(); + //}); kernel_main() } @@ -43,16 +52,28 @@ unsafe fn kernel_init() -> ! { /// /// TODO: Figure out what to do here fn kernel_main() -> ! { - for idx in 0..30 { + for idx in 0..5 { if let Some(cell) = U64_QUEUE_ALLOCATOR.alloc() { let inner = cell.inner(); *inner = idx; - println!("SUCCESS: Allocated a char! {:?}", cell); + println!("SUCCESS: Allocated a char! {:?} {:?}", cell, U64_QUEUE_ALLOCATOR); U64_QUEUE_ALLOCATOR.free(cell); } else { - println!("ERROR: No more chars remaining!"); + println!("ERROR: No more chars remaining! {:?}", U64_QUEUE_ALLOCATOR); } } println!("I should be able to print {} here!", 5); + { + let a: Box = Box::new(5); + println!("{:?}", a); + let b: Box = Box::new(7); + println!("{:?}", b); + } + { + let a: Box = Box::new(8); + println!("{:?}", a); + let b: Box = Box::new(9); + println!("{:?}", b); + } loop { } } diff --git a/src/mem.rs b/src/mem.rs new file mode 100644 index 0000000..920965d --- /dev/null +++ b/src/mem.rs @@ -0,0 +1 @@ +pub mod alloc; diff --git a/src/mem/alloc.rs b/src/mem/alloc.rs new file mode 100644 index 0000000..0b02fbd --- /dev/null +++ b/src/mem/alloc.rs @@ -0,0 +1,301 @@ +//! # 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 + } +} +/// # 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).inner() as *mut u8; + } + } + } + /* + 2 => { + U16_GRAND_ALLOC.inner.lock(|pool| { + match pool.alloc() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + (*elem).inner() as *mut u8; + } + } + }) + } + 4 => { + U32_GRAND_ALLOC.inner.lock(|pool| { + match pool.alloc() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + (*elem).inner() as *mut u8; + } + } + }) + } + 8 => { + U64_GRAND_ALLOC.inner.lock(|pool| { + match pool.alloc() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + (*elem).inner() as *mut u8; + } + } + }) + } + */ + _ => { + 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!("No deallocators for size {}!", layout.size()); + } + } + } +} + +#[global_allocator] +pub static ALLOCATOR: GrandAllocator = GrandAllocator{}; +/* +unsafe impl GlobalAlloc for NullLock> { + unsafe fn alloc(&self, layout: Layout) -> *mut u8 { + match layout.size() { + 1 => { + self.lock(|qa| { + match qa.alloc() { + None => { + panic!("No data to allocate!"); + } + Some(elem) => { + return (*elem).inner() as *mut u8; + } + } + }) + } + _ => { + panic!("No allocators for size {}!", layout.size()); + } + } + } + + unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) { + self.lock(|qa| { + qa.inner.lock(|pool| { + for idx in 2..COUNT { + if pool[idx].inner() as *mut u8 == _ptr { + qa.free(&mut pool[idx]); + return; + } + } + }); + }); + } +} + +const GLOBAL_ALLOCATOR_SIZE: usize = 100; + +// TODO: Add other allocation sizes +#[global_allocator] +pub static ALLOCATOR: NullLock> = NullLock::new(QueueAllocator::{inner: NullLock::new([QueueItem{data: 0, next: None}; {GLOBAL_ALLOCATOR_SIZE+2}])}); +*/ diff --git a/src/panic_wait.rs b/src/panic_wait.rs index 1136e54..2181869 100644 --- a/src/panic_wait.rs +++ b/src/panic_wait.rs @@ -2,10 +2,32 @@ //! //! A panic handler that infinitely waits +use crate::{cpu,println}; use core::panic::PanicInfo; +fn panic_prevent_reenter() { + use core::sync::atomic::{AtomicBool, Ordering}; + + static PANIC_IN_PROGRESS: AtomicBool = AtomicBool::new(false); + + if !PANIC_IN_PROGRESS.load(Ordering::Relaxed) { + PANIC_IN_PROGRESS.store(true, Ordering::Relaxed); + return; + } + + cpu::wait_forever() +} + /// # Panic handler #[panic_handler] -fn panic(_info: &PanicInfo) -> ! { - unimplemented!() +fn panic(info: &PanicInfo) -> ! { + panic_prevent_reenter(); + + let (location, line, column) = match info.location() { + Some(loc) => (loc.file(), loc.line(), loc.column()), + _ => ("???",0,0), + }; + + println!("Kernel panic!\n\nPanic Location:\n\tFile: '{}', line {}, column {}\n\n{}", location, line, column, info.message().unwrap_or(&format_args!("")),); + cpu::wait_forever() } -- cgit v1.2.1