Arena's and alignment

Hi rustaceans!
I wanted to build an arena allocator as a little exercise for myself and I came up with this:

use std::{alloc::{Layout, alloc, dealloc, handle_alloc_error}, ptr::NonNull};
use std::cell::Cell;
pub struct Arena {
    ptr: Cell<NonNull<u8>>,
    ptr_pos: Cell<usize>,
    capacity: usize,
}
impl Arena {
    pub fn new(capacity: usize) -> Self {
        if capacity > isize::MAX as usize {
            panic!("cannot alloc more than isize::MAX bytes");
        }
        if capacity == 0 {
            panic!("capacity cannot be 0");
        }
        let layout = Layout::array::<u8>(capacity).expect("we checked if the capacity was less than isize::MAX byes");
        // SAFETY: we checked if the capacity was 0
        let ptr = unsafe {
            alloc(layout)
        };
        if ptr.is_null() {
            handle_alloc_error(layout);
        }
        let ptr = Cell::new(NonNull::new(ptr).expect("we checked if ptr was null"));
        Self {
            ptr,
            ptr_pos: Cell::new(0),
            capacity,
        }
    }
    pub fn alloc<T>(&self, data: T) -> Option<&mut T> {
        self.ptr_pos.update(|pos| pos + size_of::<T>());
        if self.ptr_pos.get() > self.capacity - 1 {
            return None;
        }
        let ptr = self.ptr.get().as_ptr() as *mut T;
        unsafe {
            ptr.write(data);
        }
        self.ptr.update(|ptr| unsafe { ptr.add(size_of::<T>()) });
        // SAFETY: the pointer is valid non-null
        unsafe {
            Some(ptr.as_mut().expect("the pointer isn't null"))
        }
    }
}
impl Drop for Arena {
    fn drop(&mut self) {
        self.ptr.update(|ptr| unsafe {ptr.sub(self.ptr_pos.get())});
        let layout = Layout::array::<u8>(self.capacity).expect("capacity isn't 0");
        unsafe {
            dealloc(self.ptr.get().as_ptr(), layout);
        }
    }
}

but the problem with this Arena is that it doesn't align items properly and reading/writing from unaligned pointers is UB, so my question is: how can I make sure that my pointer is properly aligned for a type while still allowing many different types within one Arena.

This is quite easy. Just allocate necessary padding before new element. For example if your arena state is:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x|x|x|x|x| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1
                    0 1 2 3 4 5 6

          ^ptr_pos 

And you want to allocate u16, then add one byte of padding and then ptr_pos will be properly aligned to 2 bytes:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x|x|x|x|x|p|x|x| | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1
                    0 1 2 3 4 5 6

                ^ptr_pos 

In order to know how much padding bytes you need, you can use NonNull::align_offset. At the beginning of alloc compute

let padding = self.ptr.get().align_offset(align_of::<T>);

And then move ptr_pos by size_of::<T> + padding.

Side note

I didn't review all of your code, so there might be other problems hiding, but one bug you have for sure is that in alloc if new ptr_pos exceeds capacity, then you return without decrementing ptr_pos. This will cause UB in Drop, because you are subtracting wrong offset from self.ptr.

Thanks for the quick answer (and the bug)! This is what I love about the rust community :slight_smile:

I do still have one question, you do need to add the padding to the pointer before writing, right?

Yes. The point of padding is to ensure that arena pointer is properly aligned. In total you need to do five things:

  1. Check how many bytes of padding you need to add.
  2. Move self.ptr by that amount.
  3. Write through properly aligned pointer (and create a reference).
  4. Advance self.ptr by the size of T.
  5. Advance self.ptr_pos by the sum of padding from point 1 and size of T.

The 5th point can be moved earlier, if you are careful enough. But there is a strict order dependency of 1 -> 2 -> 3 -> 4.