Implementing the Allocation API

In this final chapter of the allocation part of the book, we'll cover the AllocRaw trait implementation.

This trait is implemented on the StickyImmixHeap struct:

impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H> {
    type Header = H;

    ...
}

Here the associated header type is provided as the generic type H, leaving it up to the interpreter to define.

Allocating objects

The first function to implement is AllocRaw::alloc<T>(). This function must:

• calculate how much space in bytes is required by the object and header
• allocate that space
• instantiate an object header and write it to the first bytes of the space
• copy the object itself to the remaining bytes of the space
• return a pointer to where the object lives in this space

Let's look at the implementation.

impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H> {
    fn alloc<T>(&self, object: T) -> Result<RawPtr<T>, AllocError>
    where
        T: AllocObject<<Self::Header as AllocHeader>::TypeId>,
    {
        // calculate the total size of the object and it's header
        let header_size = size_of::<Self::Header>();
        let object_size = size_of::<T>();
        let total_size = header_size + object_size;

        // round the size to the next word boundary to keep objects aligned and get the size class
        // TODO BUG? should this be done separately for header and object?
        //  If the base allocation address is where the header gets placed, perhaps
        //  this breaks the double-word alignment object alignment desire?
        let alloc_size = alloc_size_of(total_size);
        let size_class = SizeClass::get_for_size(alloc_size)?;

        // attempt to allocate enough space for the header and the object
        let space = self.find_space(alloc_size, size_class)?;

        // instantiate an object header for type T, setting the mark bit to "allocated"
        let header = Self::Header::new::<T>(object_size as ArraySize, size_class, Mark::Allocated);

        // write the header into the front of the allocated space
        unsafe {
            write(space as *mut Self::Header, header);
        }

        // write the object into the allocated space after the header
        let object_space = unsafe { space.offset(header_size as isize) };
        unsafe {
            write(object_space as *mut T, object);
        }

        // return a pointer to the object in the allocated space
        Ok(RawPtr::new(object_space as *const T))
    }
}

This, hopefully, is easy enough to follow after the previous chapters -

• self.find_space() is the function described in the chapter Allocating into multiple blocks
• Self::Header::new() will be implemented by the interpreter
• write(space as *mut Self::Header, header) calls the std function std::ptr::write

Allocating arrays

We need a similar (but awkwardly different enough) implementation for array allocation. The key differences are that the type is fixed to a u8 pointer and the array is initialized to zero bytes. It is up to the interpreter to write into the array itself.

impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H> {
    fn alloc_array(&self, size_bytes: ArraySize) -> Result<RawPtr<u8>, AllocError> {
        // calculate the total size of the array and it's header
        let header_size = size_of::<Self::Header>();
        let total_size = header_size + size_bytes as usize;

        // round the size to the next word boundary to keep objects aligned and get the size class
        let alloc_size = alloc_size_of(total_size);
        let size_class = SizeClass::get_for_size(alloc_size)?;

        // attempt to allocate enough space for the header and the array
        let space = self.find_space(alloc_size, size_class)?;

        // instantiate an object header for an array, setting the mark bit to "allocated"
        let header = Self::Header::new_array(size_bytes, size_class, Mark::Allocated);

        // write the header into the front of the allocated space
        unsafe {
            write(space as *mut Self::Header, header);
        }

        // calculate where the array will begin after the header
        let array_space = unsafe { space.offset(header_size as isize) };

        // Initialize object_space to zero here.
        // If using the system allocator for any objects (SizeClass::Large, for example),
        // the memory may already be zeroed.
        let array = unsafe { from_raw_parts_mut(array_space as *mut u8, size_bytes as usize) };
        // The compiler should recognize this as optimizable
        for byte in array {
            *byte = 0;
        }

        // return a pointer to the array in the allocated space
        Ok(RawPtr::new(array_space as *const u8))
    }
}

Switching between header and object

As stated in the previous chapter, these functions are essentially pointer operations that do not dereference the pointers. Thus they are not unsafe to call, but the types they operate on should have a suitably unsafe API.

NonNull is the chosen parameter and return type and the pointer arithmetic for obtaining the header from an object pointer of unknown type is shown below.

For our Immix implementation, since headers are placed immediately ahead of an object, we simply subtract the header size from the object pointer.

impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H> {
    fn get_header(object: NonNull<()>) -> NonNull<Self::Header> {
        unsafe { NonNull::new_unchecked(object.cast::<Self::Header>().as_ptr().offset(-1)) }
    }
}

Getting the object from a header is the reverse - adding the header size to the header pointer results in the object pointer:

impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H> {
    fn get_object(header: NonNull<Self::Header>) -> NonNull<()> {
        unsafe { NonNull::new_unchecked(header.as_ptr().offset(1).cast::<()>()) }
    }
}

Conclusion

Thus ends the first part of our Immix implementation. In the next part of the book we will jump over the fence to the interpreter and begin using the interfaces we've defined in this part.