An allocator for all sizes & types, backed by UnsafeCell<[u8; 1_000_000_000]>

main.rs

use std::alloc::{GlobalAlloc, Layout};
use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicBool, Ordering};

mod printing {
    use super::get_thread_id;
    use std::alloc::Layout;

    const STDOUT_FILENO: i32 = 1;

    pub fn print_number(mut n: usize) {
        const NUMBERS: &[u8; 10] = &[b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9'];

        let mut numbers = [0; 64];
        let mut digit = 0;
        while n != 0 {
            let this_digit = (n % 10) as usize;
            numbers[digit] = this_digit;

            n /= 10;
            digit += 1;
        }

        while digit != 0 {
            digit -= 1;
            unsafe {
                libc::write(
                    STDOUT_FILENO,
                    (NUMBERS.as_ptr() as *const u8).add(numbers[digit]) as _,
                    1,
                )
            };
        }
    }

    pub fn print_string(s: &str) {
        unsafe {
            libc::write(STDOUT_FILENO, s.as_ptr() as _, s.len() as _);
        }
    }

    pub fn print_allocation(layout: Layout) {
        print_string("Thread #");
        print_number(get_thread_id());

        print_string(" Allocating ");
        print_number(layout.size());
        print_string("-");
        print_number(layout.align());

        print_string(" \n");
    }

    pub fn print_end_of_allocation() {
        print_string("\tThread #");
        print_number(get_thread_id());
        print_string(" finished allocation\n");
    }
}

pub fn get_thread_id() -> usize {
    #[cfg(not(miri))]
    unsafe {
        winapi::um::processthreadsapi::GetCurrentThreadId() as usize
    }
    #[cfg(miri)]
    0
}

#[derive(Copy, Clone, Debug)]
struct Allocation {
    start: *mut u8,
    layout: Layout,
}

impl Allocation {
    ///Returns an inclusive range of the memory used by this allocation
    pub const fn get_range(&self) -> (*mut u8, *mut u8) {
        (self.start, unsafe {
            self.start.add(self.layout.size() - 1)
        })
    }
}

struct Allocator<const MAX_ALLOCS: usize, const MEMORY_SIZE: usize> {
    is_allocating: AtomicBool,
    allocations: UnsafeCell<[Option<Allocation>; MAX_ALLOCS]>,
    memory: UnsafeCell<[u8; MEMORY_SIZE]>,
}

impl<const MAX_ALLOCS: usize, const MEMORY_SIZE: usize> Allocator<MAX_ALLOCS, MEMORY_SIZE> {
    ///SAFETY: must hold onto the `is_allocating` lock before calling
    ///
    ///Finds the next space free for an allocation of given length. NB: does not update
    ///`allocations`
    pub unsafe fn find_next_space(&self, layout: Layout) -> Option<*mut u8> {
        let current_allocations = self.allocations.get().read();
        let end = (self.memory.get() as *mut u8).add(MEMORY_SIZE);

        let length = layout.size();
        let align = layout.align();

        let mut next_space_to_chk = self.memory.get() as *mut u8;
        loop {
            let end_check = next_space_to_chk.add(length - 1);
            if end_check >= end {
                return None;
            }

            let overlapping_block = current_allocations.iter().flatten().find(|allocation| {
                let (start_block, end_block) = allocation.get_range();
                !((next_space_to_chk < start_block && end_check < start_block)
                    || (next_space_to_chk > end_block && end_check > end_block))
            });

            match overlapping_block {
                Some(block) => {
                    let end = block.get_range().1;

                    let delta = end as usize - next_space_to_chk as usize;
                    let aligns = delta / align + 1;
                    next_space_to_chk = next_space_to_chk.add(align * aligns);
                }
                None => return Some(next_space_to_chk),
            }
        }
    }
}

unsafe impl<const MAX_ALLOCS: usize, const MEMORY_SIZE: usize> GlobalAlloc
    for Allocator<MAX_ALLOCS, MEMORY_SIZE>
{
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        //get the lock
        while self
            .is_allocating
            .compare_exchange(false, true, Ordering::SeqCst, Ordering::SeqCst)
            .is_err()
        {}

        //find the position
        let Some(position_to_allocate) = self.find_next_space(layout) else {
            printing::print_string("OOM error");
            return std::ptr::null_mut();
        };

        //add it to our array of allocations
        let allocations_ptr = self.allocations.get() as *mut Option<Allocation>;

        let mut found_spot = false;
        for i in 0..MAX_ALLOCS {
            let this_spot = allocations_ptr.add(i);
            if (*this_spot).is_none() {
                *this_spot = Some(Allocation {
                    start: position_to_allocate,
                    layout,
                });
                found_spot = true;
                break;
            }
        }

        if !found_spot {
            printing::print_string("OOS error");
            return std::ptr::null_mut();
        }

        self.is_allocating.store(false, Ordering::SeqCst);

        position_to_allocate
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        while self
            .is_allocating
            .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
            .is_err()
        { std::thread::yield_now() }

        let allocations_ptr = self.allocations.get() as *mut Option<Allocation>;
        for i in 0..MAX_ALLOCS {
            let this_spot = allocations_ptr.add(i);
            match *this_spot {
                Some(Allocation { start, layout: _ }) if start == ptr => {
                    *this_spot = None;
                    break;
                }
                _ => {}
            }

            if i == (MAX_ALLOCS - 1) {
                printing::print_string("wut?");
            }
        }

        self.is_allocating.store(false, Ordering::Release);
    }
}

unsafe impl<const MAX_ALLOCS: usize, const MEMORY_SIZE: usize> Sync
    for Allocator<MAX_ALLOCS, MEMORY_SIZE>
{
}

#[global_allocator]
static ALLOCATOR: Allocator<1000, 1_000_000_000> = Allocator {
    is_allocating: AtomicBool::new(false),
    allocations: UnsafeCell::new([None; 1000]),
    memory: UnsafeCell::new([0; 1_000_000_000]),
};

fn main() {
    fn factorial(n: u128) -> u128 {
        if n <= 1 {
            return n;
        }

        n + factorial(n - 1)
    }

    let mut threads = Vec::with_capacity(6);

    for block in 0..=5 {
        let t = std::thread::spawn(move || {
            let mut v = Vec::with_capacity(5);
            for n in (1..=5).into_iter().map(|x| block + x * 5) {
                v.push((n, factorial(n)));
            }

            println!("{v:?}");
        });

        threads.push(t);
    }

    for t in threads {
        t.join().unwrap();
    }
}