
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-zeroalign
must be a power of twosize
when rounded up to the nearest multiple ofalign
, must not overflow (i.e., the rounded value must be less thanusize::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
.