Generic Allocation Scheme

3 files changed, 140 insertions, 61 deletions

diff --git a/Makefile b/Makefile
index 8c202d8..e20e93a 100644
--- a/Makefile
+++ b/Makefile
@@ -20,11 +20,14 @@ COMPILER_ARGS=--target=$(TARGET) $(FEATURES) --release
 RUSTC_CMD=cargo rustc $(COMPILER_ARGS)
 export LINKER_FILE
 
-.PHONY: build clean run
+.PHONY: build doc clean run
 
 build:
 	@RUSTFLAGS="$(RUSTFLAGS_PEDANTIC)" $(RUSTC_CMD)
 
+doc:
+	@RUSTFLAGS="$(RUSTFLAGS_PEDANTIC)" cargo doc $(COMPILER_ARGS)
+
 clean:
 	rm -rf target
 
diff --git a/src/alloc.rs b/src/alloc.rs
index fd22c67..9b77f13 100644
--- a/src/alloc.rs
+++ b/src/alloc.rs
@@ -1,93 +1,153 @@
+//! # 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) => {
+	#[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;
-
-const CHAR_COUNT: usize = 20;
-const CHAR_POOL_SIZE: usize = CHAR_COUNT + 2;
+use core::fmt::{Debug,Formatter,Result};
 
 #[derive(Copy,Clone)]
-pub struct CharCell {
-	pub data: char,
-	next: Option<*mut CharCell>,
+/// # 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 CharCell {
-	pub const fn new() -> Self {
-		Self {
-			data: '\0',
-			next: None,
-		}
+impl<T> 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<T> Send for QueueItem<'_,T> {}
 
-use core::fmt::{Debug,Formatter,Result};
-impl Debug for CharCell {
+impl<T: Debug> Debug for QueueItem<'_,T> {
+	/// # Debug formatter for `QueueItem`
+	///
+	/// Output the encapsulated data
 	fn fmt(&self, f: &mut Formatter<'_>) -> Result {
-		write!(f, "{}", self.data)
+		write!(f, "{:?}", self.data)
 	}
 }
 
-unsafe impl Send for CharCell {}
-
-pub struct CharAllocator(NullLock<[CharCell; CHAR_POOL_SIZE]>);
-
-impl CharAllocator {
-	pub const fn new() -> Self {
-		Self(NullLock::new([CharCell::new(); CHAR_POOL_SIZE]))
-	}
+/// # 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<T,const COUNT: usize> 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.0.lock(|char_pool| {
-			for idx in 2..CHAR_POOL_SIZE {
-				if idx != CHAR_POOL_SIZE - 1 {
-					char_pool[idx].next = Some(&mut char_pool[idx+1] as *mut CharCell);
+		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 {
-					char_pool[idx].next = None;
+					queue[idx].next = None;
 				}
 			}
-			char_pool[0].next = Some(&mut char_pool[2] as *mut CharCell);
-			char_pool[1].next = Some(&mut char_pool[CHAR_POOL_SIZE-1] as *mut CharCell);
+			queue[0].next = Some(&mut queue[2] as *mut QueueItem<'_, T>);
+			queue[1].next = Some(&mut queue[queue.len()-1] as *mut QueueItem<'_, T>);
 		});
 	}
 
-	pub fn alloc(&self) -> Option<&mut CharCell> {
-		return self.0.lock(|char_pool| {
-			if let Some(char_cell) = char_pool[0].next {
-				char_pool[0].next = unsafe{(*char_cell).next};
+	/// # 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 {
-					(*char_cell).next = None;
+					(*entry).next = None;
 				}
-				return Some(unsafe{&mut *char_cell as &mut CharCell});
+				match pool[0].next {
+					None => {
+						pool[1].next = None
+					}
+					_ => {}
+				}
+				return Some(unsafe{&mut *entry as &mut QueueItem<'a,T>});
 			} else {
 				return None;
 			}
 		});
 	}
 
-	pub fn free(&self, cell: &mut CharCell) {
-		self.0.lock(|char_pool| {
-			cell.next = None;
-			match char_pool[1].next {
+	/// # 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 => {
-					char_pool[0].next = Some(cell as *mut CharCell);
+					pool[0].next = Some(freed_item as *mut QueueItem<'a,T>);
 				}
-				Some(ocell) => {
+				Some(entry) => {
 					unsafe {
-						(*ocell).next = Some(cell as *mut CharCell);
+						if (entry as u32) == (freed_item as *mut QueueItem<'a,T> as u32) {
+							(*entry).next = Some(freed_item as *mut QueueItem<'a,T>);
+						}
 					}
 				}
 			}
-			char_pool[1].next = Some(cell as *mut CharCell);
+			pool[1].next = Some(freed_item as *mut QueueItem<'a,T>);
 		});
 	}
 }
 
-impl Debug for CharAllocator {
+impl<T: Debug,const COUNT: usize> 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.0.lock(|pool| {
-			write!(f, "{:?}", pool)
+		self.inner.lock(|queue| {
+			write!(f, "{:?}", queue)
 		})
 	}
 }
 
-#[link_section = ".data.alloc"]
-pub static CHAR_ALLOCATOR: CharAllocator = CharAllocator::new();
+/// 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 9377eb5..3f10849 100644
--- a/src/kernel.rs
+++ b/src/kernel.rs
@@ -1,4 +1,10 @@
-//! Kernel Code
+//! # Kernel Code
+//!
+//! ## Initializes the peripherals
+//!  - UART
+//!  - Allocators
+
+#![doc(html_logo_url = "https://raw.githubusercontent.com/rust-embedded/wg/master/assets/logo/ewg-logo-blue-white-on-transparent.png")]
 
 #![allow(non_snake_case)]
 #![allow(clippy::upper_case_acronyms,dead_code)]
@@ -17,24 +23,34 @@ mod print;
 mod sync;
 mod uart;
 use crate::console::console;
-use crate::alloc::CHAR_ALLOCATOR;
+use crate::alloc::*;
 
-/// Initialization Code
+/// # Initialization Code
+///
+/// Initializes
+///  - Allocators
+///  - UART
+///
+/// After initialization, jump to
+/// the regular main.
 unsafe fn kernel_init() -> ! {
 	console().init().unwrap();
-	CHAR_ALLOCATOR.init();
+	U64_QUEUE_ALLOCATOR.init();
 	kernel_main()
 }
 
-/// Post init
+/// # Post-initialization
+///
+/// TODO: Figure out what to do here
 fn kernel_main() -> ! {
 	for idx in 0..30 {
-		if let Some(cell) = CHAR_ALLOCATOR.alloc() {
-			cell.data = ('0' as u8 + idx as u8) as char;
-			println!("SUCCESS: Allocated a char! {:?} {:?}", cell, CHAR_ALLOCATOR);
-			CHAR_ALLOCATOR.free(cell);
+		if let Some(cell) = U64_QUEUE_ALLOCATOR.alloc() {
+			let inner = cell.inner();
+			*inner = idx;
+			println!("SUCCESS: Allocated a char! {:?}", cell);
+			U64_QUEUE_ALLOCATOR.free(cell);
 		} else {
-			println!("ERROR: No more chars remaining! {:?}", CHAR_ALLOCATOR);
+			println!("ERROR: No more chars remaining!");
 		}
 	}
 	println!("I should be able to print {} here!", 5);