From a04cf2dbb8d2e890405fbf0a1022aaad3015b1e8 Mon Sep 17 00:00:00 2001 From: Christian Cunningham Date: Fri, 26 Aug 2022 17:25:34 -0700 Subject: Modularize --- src/util/mem/alloc.rs | 289 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 289 insertions(+) create mode 100644 src/util/mem/alloc.rs (limited to 'src/util/mem/alloc.rs') diff --git a/src/util/mem/alloc.rs b/src/util/mem/alloc.rs new file mode 100644 index 0000000..dfe8c60 --- /dev/null +++ b/src/util/mem/alloc.rs @@ -0,0 +1,289 @@ +//! # Allocate crate +//! +//! Provides the Global allocator and methods +//! to create special purpose allocators. +use super::types::*; +use crate::lib::lifo_queue::init_lifo_queue; +use crate::lib::lifo_queue::LifoQueue; +use crate::lib::node::Node; +use crate::lib::queue::Queue; +use crate::lib::sync::interface::Mutex; +use crate::lib::sync::NullLock; +use crate::serial_vprintln; +use crate::util::mem::{GlobalAlloc, Layout}; + +/// # Grand Allocator +/// +/// The structure that uses different sized pools and allocates memory chunks +pub struct GrandAllocator {} + +/// # The number of elements of each size +const GRAND_ALLOC_SIZE: usize = 64; + +init_lifo_queue!(U8_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u8); +init_lifo_queue!(U16_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u16); +init_lifo_queue!(U32_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u32); +init_lifo_queue!(U64_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u64); +init_lifo_queue!(U128_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u128); +init_lifo_queue!(U256_GRAND_ALLOC, GRAND_ALLOC_SIZE, { U256::new() }, U256); +init_lifo_queue!(U512_GRAND_ALLOC, GRAND_ALLOC_SIZE, { U512::new() }, U512); +init_lifo_queue!(U1024_GRAND_ALLOC, GRAND_ALLOC_SIZE, { U1024::new() }, U1024); +init_lifo_queue!(U2048_GRAND_ALLOC, GRAND_ALLOC_SIZE, { U2048::new() }, U2048); +init_lifo_queue!(U4096_GRAND_ALLOC, GRAND_ALLOC_SIZE, { U4096::new() }, U4096); + +impl GrandAllocator { + pub fn init(&self) -> Result<(), &'static str> { + serial_vprintln!("GA: \x1b[93mInit U8 Pool\x1b[0m"); + U8_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U16 Pool\x1b[0m"); + U16_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U32 Pool\x1b[0m"); + U32_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U64 Pool\x1b[0m"); + U64_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U128 Pool\x1b[0m"); + U128_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U256 Pool\x1b[0m"); + U256_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U512 Pool\x1b[0m"); + U512_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U1024 Pool\x1b[0m"); + U1024_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U2048 Pool\x1b[0m"); + U2048_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[93mInit U4096 Pool\x1b[0m"); + U4096_GRAND_ALLOC.init(); + serial_vprintln!("GA: \x1b[94mPools Initialized!\x1b[0m"); + Ok(()) + } +} + +unsafe impl GlobalAlloc for GrandAllocator { + /// # Allocator + /// + /// Allocate the fixed size chunks + unsafe fn alloc(&self, layout: Layout) -> *mut u8 { + serial_vprintln!("GA: Allocating chunk of size {}!", layout.size()); + match layout.size() { + 1 => match U8_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 2 => match U16_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 3..=4 => match U32_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 5..=8 => match U64_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 9..=16 => match U128_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 17..=32 => match U256_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 33..=64 => match U512_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 65..=128 => match U1024_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 129..=256 => match U2048_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + 257..=512 => match U4096_GRAND_ALLOC.pop() { + None => { + panic!("No cells to allocate!"); + } + Some(elem) => { + return (*elem).ptr(); + } + }, + _ => { + panic!("No allocators for size {}!", layout.size()); + } + } + } + + /// # Deallocate + /// + /// Deallocate the fixed size chunks by searching for them + unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) { + serial_vprintln!("GA: Deallocating chunk of size {}!", layout.size()); + match layout.size() { + 1 => { + U8_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U8_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 2 => { + U16_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U16_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 3..=4 => { + U32_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U32_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 5..=8 => { + U64_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U64_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 9..=16 => { + U128_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U128_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 17..=32 => { + U256_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U256_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 33..=64 => { + U512_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U512_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 65..=128 => { + U1024_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U1024_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 129..=256 => { + U2048_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U2048_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + 257..=512 => { + U4096_GRAND_ALLOC.inner.lock(|pool| { + let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize); + let diff: usize = (ptr as usize) - (pool[1].ptr() as usize); + let index: usize = diff/spacing; + assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE); + assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing); + U4096_GRAND_ALLOC.push(&mut pool[index+1]); + serial_vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); + }); + } + _ => { + panic!("No deallocators for size {}!", layout.size()); + } + } + } +} + +/// # Grand Allocator +/// +/// The allocator of allocators. It hands out fixed sized memory chunks. +#[global_allocator] +pub static ALLOCATOR: GrandAllocator = GrandAllocator {}; + +/// # Global Allocator +/// +/// Returns a borrow for the Global Allocator +pub fn allocator() -> &'static crate::util::mem::alloc::GrandAllocator { + serial_vprintln!("AL: Getting global allocator!"); + &crate::util::mem::alloc::ALLOCATOR +} -- cgit v1.2.1