After sketching a few designs and digging into Rust Atomics and Locks: Low-Level Concurrency in Practice by Mara Bos, I’ve finally locked down the Node component of the allocator.

The Node represents the smallest memory unit the allocator operates on. It holds the pointer to the memory chunk to be handed out.

I’ve benchmarked this at around 200 nanoseconds, compared to 2000+ nanoseconds for Windows’ HeapAlloc. By bypassing a context switch on my machine, the Node allocation logic gives a 10× speed-up, which is huge.

This is the only finalized part so far, but I’ll update benchmarks as other components come together. There’s still more testing to do and more structs to define for broader allocator functionality.

For now, I’m sharing a full screenshot of this section of code. The project is proprietary (not something I intend to police) if someone replicates it, but because of that, I won’t be publishing the complete codebase. Future examples will lean illustrative rather than literal.

That being said this isn’t the code verbatim either but it’s a lot of it and gives the whole mechanics of how a node allocates data and tracks meta. Hope this helps others ❤️

#[derive(Debug)]
pub struct Node<const HEADER_LEN: usize, const DATA_LEN: usize, const BUFFER_LEN: usize> {
    header: [u8; HEADER_LEN],
    data: [u8; DATA_LEN],
}

impl<const HEADER_LEN: usize, const DATA_LEN: usize, const BUFFER_LEN: usize>
    Node<HEADER_LEN, DATA_LEN, BUFFER_LEN>
{
    #[inline]
    pub fn write_header_info_ptr<P>(
        &mut self,
        position_begin_as_usize: usize,
        type_as_ptr: *const P,
    ) -> usize {
        let position_end_as_usize = position_begin_as_usize + SYS_POINTER_WIDTH;
        let type_as_usize = type_as_ptr as usize;
        let type_as_byte_array = type_as_usize.to_ne_bytes();
        let type_as_byte_slice = type_as_byte_array.as_slice();
        let writable_header_section =
            &mut self.header[position_begin_as_usize..position_end_as_usize];

        writable_header_section.copy_from_slice(type_as_byte_slice);
        position_end_as_usize
    }

    #[inline(always)]
    pub fn read_header_info_ptr<P>(&self, position_begin_as_usize: usize) -> (usize, NonNull<P>) {
        let position_end_as_usize = position_begin_as_usize + SYS_POINTER_WIDTH;
        let readable_header_section = &self.header[position_begin_as_usize..position_end_as_usize];
        let mut result_buf = [0u8; SYS_POINTER_WIDTH];

        result_buf.copy_from_slice(readable_header_section);

        let addr = usize::from_ne_bytes(result_buf);
        let type_as_ptr = addr as *const P;

        (position_end_as_usize, unsafe {
            NonNull::new_unchecked(type_as_ptr as *mut P)
        })
    }

    pub fn aligned_addr(&mut self, align: usize) -> Option<NonNull<u8>> {
        let data_as_mut_ptr = self.data.as_mut_ptr();
        let word_offset_as_mut_ptr = unsafe { data_as_mut_ptr.add(SYS_POINTER_WIDTH) };

        let align_offset = word_offset_as_mut_ptr.align_offset(align);
        let align_offset_as_mut_ptr = unsafe { word_offset_as_mut_ptr.add(align_offset) };

        unsafe {
            let header_as_ptr = &self.header as *const [u8; HEADER_LEN];
            let header_as_usize = header_as_ptr as usize;
            let header_as_byte_array = header_as_usize.to_ne_bytes();
            let header_as_byte_slice = header_as_byte_array.as_slice();
            let write_header = align_offset_as_mut_ptr.sub(SYS_POINTER_WIDTH) as *mut u8;
            let write_buf = slice::from_raw_parts_mut(write_header, SYS_POINTER_WIDTH);

            write_buf.copy_from_slice(header_as_byte_slice);
        }

        NonNull::new(align_offset_as_mut_ptr)
    }

    pub fn resolve_addr(
        position_begin_as_usize: usize,
        ptr: *mut u8,
        head: *mut Self,
    ) -> NonNull<Self> {
        let position_end = SYS_POINTER_WIDTH + position_begin_as_usize;
        let header_as_ptr = unsafe { ptr.sub(SYS_POINTER_WIDTH) };
        let header_as_slice = unsafe { slice::from_raw_parts(header_as_ptr, SYS_POINTER_WIDTH) };
        let mut header_as_array = [0u8; SYS_POINTER_WIDTH];

        header_as_array.copy_from_slice(header_as_slice);

        let header_as_usize = usize::from_ne_bytes(header_as_array);
        let header_as_mut_ptr = header_as_usize as *mut [u8; HEADER_LEN];
        let header_as_slice = unsafe { &*header_as_mut_ptr };
        let node_as_slice = &header_as_slice[position_begin_as_usize..position_end];
        let mut node_buf_array = [0u8; SYS_POINTER_WIDTH];

        node_buf_array.copy_from_slice(node_as_slice);

        let node_as_usize = usize::from_ne_bytes(node_buf_array);
        let node_as_ptr = node_as_usize as *const Self;

        unsafe {
            let head_as_usize = head as usize;
            let head_as_byte_array = head_as_usize.to_ne_bytes();
            let head_as_byte_slice = head_as_byte_array.as_slice();
            let header_as_mut_ref = &mut *header_as_mut_ptr;
            let header_first_word_as_mut_slice =
                &mut header_as_mut_ref[SYS_POINTER_WIDTH * 7..SYS_POINTER_WIDTH * 8];

            header_first_word_as_mut_slice.copy_from_slice(head_as_byte_slice);
        }

        unsafe { NonNull::new_unchecked(node_as_ptr as *mut _) }
    }
}

So I've been writing an allocator. A difficult task and in Rust it is currently a dream to write.

The patterns I'm on about are small quick scopes to get a mutable reference and store or read data.

pub fn some_func(&mut self, s: &[u8]) {
    // Mutable borrow 1 and write
    {
        let writable = &mut self.buf[..8];

        writable[..8].copy_from_slice();
    }

    // Mutable borrow 2 and write
    {
        let writable = &mut self.buf[8..16];

        writable[8..16].copy_from_slice();
    }

    // And so on . . .
}

No other language feels like this. No other language is so precise on reads and writes always taking a length or the length can be obtained from the type (such as a slice).

Writing to different parts of a buffer and selecting parts of like this feels amazing. For writing an allocator i can just make array's and then write any bytes to them and just read them back and cast them about.

So much better than just using raw pointers, and safer as sizes are usually know with slices.

Anyway i just love Rust and this was an excuse to share my love of Rust <3