Understanding Memory Allocation in Rust Through Building a Custom Vector

Hey there, welcome aboard! Today, we're going on a thrilling journey into the heart of Rust, diving deep into the realm of manual memory management, a territory often associated with the likes of C/C++. Now, don't get me wrong, Rust's safety and ownership model is pretty awesome, but let's be honest, sometimes it feels like we're driving with the handbrake on.

We're going to toss the rulebook out the window and get our hands dirty with manual memory management in Rust. And what's a good adventure without a practical project? We'll put our newfound knowledge to the test by crafting a simple vector from scratch. It's going to be a wild ride, so buckle up (or don't, we're rule-breakers after all) and let's dive right in!

alloc and Layout in action

Alright, folks, we're stepping into the wild side, where alloc, dealloc, and Layout rule the roost. These bad boys are part of the std::alloc module and they're our ticket to memory management freedom.

Now, let's dive into some code. Here's a little taster of how we can harness the power of alloc, dealloc, and Layout to take control of our memory destiny.

use std::alloc::{alloc, dealloc, Layout};

fn main() {
    let layout = Layout::new::<i32>();
    let ptr = unsafe { alloc(layout) } as *mut i32;

    unsafe {
        *ptr = 42;
    }

    let value = unsafe { *ptr };
    println!("value: {}", value);

    unsafe {
        dealloc(ptr as *mut u8, layout);
    }
}

Let's break down this code and see what's really going on.

First up, let layout = Layout::new::<i32>();.

This line is like ordering a new storage unit for our data. We're telling Rust we need a chunk of memory big enough to hold an i32. You can swap out i32 with any type or struct you fancy, and Rust will size up the memory just right.

Next, we've got let ptr = unsafe { alloc(layout) } as *mut i32;.

Here, we're calling in the movers with the alloc function. We hand them our layout, and they set aside a block of memory that fits the bill, handing us back a raw pointer. We then cast that raw pointer to a mutable i32 pointer, giving us the power to change or read the value it's pointing to.

You might notice we're throwing around the unsafe keyword quite a bit. That's us telling the compiler, 'Hey, we're living on the edge here, no need for the safety net. We got this.' And just like that, the compiler backs off on the errors.

Moving on, let value = unsafe { *ptr };

This is us peeking inside the storage unit. We're accessing the value that the pointer is pointing to in memory. But remember, this is unsafe territory. There's no guarantee that the pointer is pointing to a valid memory. It could be null, or it could be misused, leading to undefined behavior. So tread carefully.

Finally, unsafe { dealloc(ptr as *mut u8, layout); }

Here, we're being good citizens and cleaning up after ourselves. We're deallocating the memory we allocated earlier. Don't get tripped up by the *mut u8 here versus the *mut i32 we used earlier. The value this pointer is pointing to is of type i32, but the type of ptr that we're using here is u8.

Custom Vector

Let's talk vectors. Picture an array, but it's been hitting the gym, flexing its muscles, and now it can dynamically change its size depending on how many elements we throw into it. Arrays, on the other hand, are like that old pair of jeans - they ain't gonna stretch no matter how much you wish they would. Now, let's dive into the code.

use std::alloc::{alloc, dealloc, Layout};
use std::ptr;

#[derive(Debug)]
pub struct Vec<T> {
    ptr: *mut T,
    len: usize,
    capacity: usize,
}

impl<T> Vec<T> {
    pub fn new() -> Self {
        Self {
            ptr: ptr::null_mut(),
            len: 0,
            capacity: 0,
        }
    }

    pub fn push(&mut self, item: T) {
        if self.len == self.capacity {
            let new_capacity = self.capacity.max(1) + (99); // increment in 100
            let new_layout = Layout::array::<T>(new_capacity).unwrap();
            let new_ptr = unsafe { alloc(new_layout) as *mut T };

            if !self.ptr.is_null() {
                unsafe {
                    ptr::copy_nonoverlapping(self.ptr, new_ptr, self.len);
                    let old_layout = Layout::array::<T>(self.capacity).unwrap();
                    dealloc(self.ptr as *mut u8, old_layout);
                }
            }

            self.ptr = new_ptr;
            self.capacity = new_capacity;
        }

        unsafe {
            ptr::write(self.ptr.add(self.len), item);
        }

        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            unsafe { Some(ptr::read(self.ptr.add(self.len))) }
        }
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.len {
            unsafe { Some(&*self.ptr.add(index)) }
        } else {
            None
        }
    }
}
impl<T> Drop for Vec<T> {
    fn drop(&mut self) {
        if !self.ptr.is_null() {
            unsafe {
                for i in 0..self.len {
                    ptr::drop_in_place(self.ptr.add(i));
                }
                let layout = Layout::array::<T>(self.capacity).unwrap();
                dealloc(self.ptr as *mut u8, layout);
            }
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_vector() {
        let mut list = Vec::new();
        println!("list capacity {:?}", list.capacity);

        println!("adding items to list");
        for i in 0..10 {
            list.push(i);
        }
        println!("list capacity after adding items: {:?}", list.capacity);

        println!("printing out list items");
        for i in 0..list.len {
            println!("{:?}", list.get(i));
        }
    }
}

I've kept it simple, just like a good burger - no unnecessary toppings, just pure, juicy code. You can take it for a spin with cargo test -- --nocapture.

Let's break it down, shall we?

I will be going to dive deep into the push method together, and then I'll guide you through some other juicy bits of code that I think are worth your attention. I won't be covering every single line - we ain't got all day for this.

#[derive(Debug)]
pub struct Vec<T> {
    ptr: *mut T,
    len: usize,
    capacity: usize,
}

Here's our vector struct, all dressed up and ready to go. We've got a mutable pointer of the generic type, a len to keep track of our elements, and a capacity to know how big our vector is.

pub fn push(&mut self, item: T) {
    if self.len == self.capacity {
        let new_capacity = self.capacity.max(1) + (99); // increment in 100
        let new_layout = Layout::array::<T>(new_capacity).unwrap();
        let new_ptr = unsafe { alloc(new_layout) as *mut T 
    };

First up, we're checking if we've hit our capacity. If we have, we're cranking it up by 100. Then, we're allocating space for our new, beefed-up vector.

if !self.ptr.is_null() {
    unsafe {
        ptr::copy_nonoverlapping(self.ptr, new_ptr, self.len);
        let old_layout = Layout::array::<T>(self.capacity).unwrap();
        dealloc(self.ptr as *mut u8, old_layout);
    }
}

If our pointer isn't null, we're copying over the contents from the old vector to the new one, then saying goodbye to the old vector.

self.ptr = new_ptr;
self.capacity = new_capacity;

We're updating our pointer and capacity to the new ones.

unsafe {
    ptr::write(self.ptr.add(self.len), item);
}

self.len += 1;

Then, we're adding the new item to the end of the vector and bumping up the length.

The rest of the code is pretty straightforward like the pop and get method, but let's touch on a few key points.

• self.ptr.add(self.len): This is us getting a pointer to the memory location right after the last element in the vector.

• ptr::write(self.ptr.add(self.len), item);: Here, we're writing our new item right at the end of the vector.

• ptr::drop_in_place(self.ptr.add(i));: And here, we're dropping the i-th element in the vector, making sure we're not leaving any resources hanging around.

That's how we roll with a custom vector in Rust. If you have any questions dont hesitate to hit me up! Also, if you made something cooler, feel free to share.