Ehsan's Blog

Let’s get deep into std::alloc!

Memory allocator 101

The very basic need for any program to compile and execute is having access to either physical memory or virtual memory. An allocator is responsible for providing such an access. You can think of an allocator as a service, taking some sort of requests and either giving back a (pointer) to block of memory or some errors. In Rust, a request is a Layout i.e. some meta-data about how the memory we want is supposed to take up the space.

A memory layout is made up of

• size (in bytes)
• alignment (in bytes and must be power of two): the CPU always reads memory at its word size (4 bytes on 32-bit system or 8 bytes on 64-bit system). See what’s the purpose of memory alignment.

std::alloc::Layout

#[lang = "alloc_layout"]
pub struct Layout {
    // size of the requested block of memory, measured in bytes.
    size_: usize,

    // alignment of the requested block of memory, measured in bytes.
    // we ensure that this is always a power-of-two ...
    align_: NonZeroUsize,
}

For example, to check the size and alignment of a type vs a value, we can do (playpen)

println!("type alignment of i32 {}", mem::align_of::<i32>()); // --> 4 bytes
println!("val alignment 1i32 {}", mem::align_of_val(&1i32)); // --> 4 bytes
println!("type size i32 {}", mem::size_of::<i32>()); // --> 4 bytes
println!("val size 1i32 {}", mem::size_of_val(&1i32)); // --> 4 bytes

// empty struct
struct A;
let val = A;
println!("type alignment {}", mem::align_of::<A>()); // --> 1 byte
println!("val alignment {}", mem::align_of_val(&val)); // --> 1 byte
println!("type size {}", mem::size_of::<A>()); // --> 0 bytes
println!("val size {}", mem::size_of_val(&val)); // --> 0 bytes

// also with
println!("Layout of A: {:?}", Layout::new::<A>()); // --> Layout { size_: 0, align_: 1 }

Are there any relations between size and align?

Looking into std::alloc::from_size_align indicates three requirements (invariants) that must be held when constructing a layout given size and alignment:

• align must be non-zero
• align must be a power of two
• size when rounded up to the nearest multiple of align, must not overflow (i.e., the rounded value must be less than usize::MAX) i.e. .

We can compute the the round up size with For example, if we want to create a layout with size bytes and alignment bytes, then the round up size will be , but for size of bytes and the same alignment, the round up size will be bytes. The difference between the rounded up size and the given size is the amount of padding needed for that alignment which are and respectively. (playpen)

We saw in the earlier example that we can create a layout for a type T using Layout::new::<T>(). Moreover, given a reference &T, we can create the desirable layout with std::alloc::for_value. Basically, they are

impl<T> Layout<T> {
    pub fn new<T>() -> Self {
        let (size, align) = (mem::size_of::<T>(), mem::align_of::<T>());
        // Note that the align is guaranteed by rustc to be a power of two and
        // the size+align combo is guaranteed to fit in our address space. As a
        // result use the unchecked constructor here to avoid inserting code
        // that panics if it isn't optimized well enough.
        debug_assert!(Layout::from_size_align(size, align).is_ok());
        unsafe {
            Layout::from_size_align_unchecked(size, align)
        }
    }

    pub fn for_value<T: ?Sized>(t: &T) -> Self {
        let (size, align) = (mem::size_of_val(t), mem::align_of_val(t));
        // See rationale in `new` for why this us using an unsafe variant below
        debug_assert!(Layout::from_size_align(size, align).is_ok());
        unsafe {
            Layout::from_size_align_unchecked(size, align)
        }
    }
}

So far we have covered the layout (request part of the allocator service). Let’s look closer into the main constituent of the service.

std::alloc::GlobalAlloc

pub unsafe trait GlobalAlloc {
    // required methods
    unsafe fn alloc(&self, layout: Layout) -> *mut u8;
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
    // provided methods
    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { ... }
    unsafe fn realloc(
        &self, 
        ptr: *mut u8, 
        layout: Layout, 
        new_size: usize
    ) -> *mut u8 { ... }
}

Implementing this trait for a type, must be followed by using the attribute #[global_allocator] so that we can register it as the global std allocator. For a given layout, the alloc method returns a pointer to a block memory or a null pointer in case of Out-Of-Memory (OOM) or invalid layout. The allocated block of memory may or may not be initialized.

Up to writing these notes, the experimental variant of GlobalAlloc trait is std::alloc::Alloc with more functionalities. Note that the default allocator provided by the OS is std::alloc::System which in case of alloc provides either a non-null pointer (to some block of memory) or some AllocErr. This is configured as

pub struct System;

// The Alloc impl just forwards to the GlobalAlloc impl, which is in `std::sys::*::alloc`.
#[unstable(feature = "allocator_api", issue = "32838")]
unsafe impl Alloc for System {
    #[inline]
    unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        NonNull::new(GlobalAlloc::alloc(self, layout)).ok_or(AllocErr)
    }

    #[inline]
    unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        NonNull::new(GlobalAlloc::alloc_zeroed(self, layout)).ok_or(AllocErr)
    }

    #[inline]
    unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
        GlobalAlloc::dealloc(self, ptr.as_ptr(), layout)
    }

    #[inline]
    unsafe fn realloc(&mut self,
                      ptr: NonNull<u8>,
                      layout: Layout,
                      new_size: usize) -> Result<NonNull<u8>, AllocErr> {
        NonNull::new(GlobalAlloc::realloc(self, ptr.as_ptr(), layout, new_size)).ok_or(AllocErr)
    }
}

And for example on unix, the System allocator is defined using libc::malloc satisfying the condition below

unsafe impl GlobalAlloc for System {
    #[inline]
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
            libc::malloc(layout.size()) as *mut u8
        } else {
            #[cfg(target_os = "macos")]
            {
                if layout.align() > (1 << 31) {
                    return ptr::null_mut()
                }
            }
            aligned_malloc(&layout) // --> more or less is: libc::memalign(layout.align(), layout.size()) as *mut u8
        }
    }
    ...

That’s it for now! we have covered most of the basics and important aspects of std::alloc.