From 68149e991454dc880ceb1f7324e118795625d863 Mon Sep 17 00:00:00 2001 From: Christian Cunningham Date: Wed, 24 Aug 2022 19:20:02 -0700 Subject: Use LFIO queue for allocator --- src/mem/alloc.rs | 106 ++++++++++++++++++++++++++++--------------------------- 1 file changed, 54 insertions(+), 52 deletions(-) (limited to 'src') diff --git a/src/mem/alloc.rs b/src/mem/alloc.rs index 1c32a38..307be5c 100644 --- a/src/mem/alloc.rs +++ b/src/mem/alloc.rs @@ -7,8 +7,10 @@ use crate::sync::NullLock; use crate::sync::interface::Mutex; use crate::vprintln; use super::types::*; -use crate::util::{QueueAllocator,QueueItem}; -use crate::init_queue; +use os_pic::util::node::Node; +use os_pic::util::lifo_queue::LifoQueue; +use os_pic::init_lifo_queue; +use os_pic::util::queue::Queue; /// # Grand Allocator /// @@ -18,16 +20,16 @@ pub struct GrandAllocator { } /// # The number of elements of each size 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); -init_queue!(U256_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U256::new()}, U256); -init_queue!(U512_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U512::new()}, U512); -init_queue!(U1024_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U1024::new()}, U1024); -init_queue!(U2048_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U2048::new()}, U2048); -init_queue!(U4096_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U4096::new()}, U4096); +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> { @@ -64,7 +66,7 @@ unsafe impl GlobalAlloc for GrandAllocator { vprintln!("GA: Allocating chunk of size {}!", layout.size()); match layout.size() { 1 => { - match U8_GRAND_ALLOC.alloc() { + match U8_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -74,7 +76,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 2 => { - match U16_GRAND_ALLOC.alloc() { + match U16_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -84,7 +86,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 3..=4 => { - match U32_GRAND_ALLOC.alloc() { + match U32_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -94,7 +96,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 5..=8 => { - match U64_GRAND_ALLOC.alloc() { + match U64_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -104,7 +106,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 9..=16 => { - match U128_GRAND_ALLOC.alloc() { + match U128_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -114,7 +116,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 17..=32 => { - match U256_GRAND_ALLOC.alloc() { + match U256_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -124,7 +126,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 33..=64 => { - match U512_GRAND_ALLOC.alloc() { + match U512_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -134,7 +136,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 65..=128 => { - match U1024_GRAND_ALLOC.alloc() { + match U1024_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -144,7 +146,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 129..=256 => { - match U2048_GRAND_ALLOC.alloc() { + match U2048_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -154,7 +156,7 @@ unsafe impl GlobalAlloc for GrandAllocator { } } 257..=512 => { - match U4096_GRAND_ALLOC.alloc() { + match U4096_GRAND_ALLOC.pop() { None => { panic!("No cells to allocate!"); } @@ -177,111 +179,111 @@ unsafe impl GlobalAlloc for GrandAllocator { match layout.size() { 1 => { U8_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U8_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 2 => { U16_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U16_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 3..=4 => { U32_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U32_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 5..=8 => { U64_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U64_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 9..=16 => { U128_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U128_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 17..=32 => { U256_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U256_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 33..=64 => { U512_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U512_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 65..=128 => { U1024_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U1024_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 129..=256 => { U2048_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U2048_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } 257..=512 => { U4096_GRAND_ALLOC.inner.lock(|pool| { - let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize); - let diff: usize = (ptr as usize) - (pool[2].ptr() as usize); + 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.free(&mut pool[index+2]); + U4096_GRAND_ALLOC.push(&mut pool[index+1]); vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing); }); } -- cgit v1.2.1