Our own vector: Rust

Apr 26, 2024

Every programming language today has some sort of array which can be allocated on the heap. In Rust, this is called a vector. A vector can grow in memory. When it grows, the previously allocated data is copied to another place or even the same place if the memory is available. It can grow in size, allowing us to dynamically add data.

A vector has three fields:

Capacity, which is how much max data can be entered before we need to allocate more memory using malloc
Length, which is the number of fields in the vector
The pointer in the memory on the heap where it lives

Libc Library provides us with a malloc call. malloc is not a system call; it just doesn’t allocate a new page on the key pages that are already available. It allocates the given object.

Lets implement our own vec

struct OwnVec<T> {
    data: *mut T, // address
    cap: usize,
    len: usize,
}

impl<T> OwnVec<T> {
    fn alloc(cap: usize) -> Option<*mut T> {
        let p = unsafe { libc::malloc(size_of::<T>() * cap) as *mut T };
        if p.is_null() {
            return None;
        }
        Some(p)
    }

    pub fn new(cap: usize) -> Self {
        OwnVec {
            data: Self::alloc(cap).unwrap(),
            cap: cap,
            len: 0,
        }
    }
    pub fn push(&mut self, n: T) {
        if self.len >= self.cap {
            panic!("");
        }
        unsafe {
            let addr = (self.data as usize) + self.len * size_of::<T>();
            *addr = n; // calls the drop if the type implements Drop trait
            // even if it is uninitialized.
        };
        self.len += 1;
    }
    pub fn nth(&self, n: usize) -> Option<T>
    where
        T: Copy,
    {
        if n >= self.len {
            return None;
        }
        let addr = (self.data as usize) + (n) * size_of::<T>();
        return Some(unsafe { *(addr as *const T) });
    }
}

The above implementation is a simple array where we can index the element, push a new element, and get a new slice of heap allocated array. The malloc call can return a NULL pointer in case the malloc call fails, so we have to check whether it is pointing to null. The few problems it has are:

If the length reaches capacity, we need to allocate more pages.
We are doing pointer increments manually.
In the push method, we are assigning directly to the address pointer the value of n, but if the address points to even if it’s uninitialized, has a dropped implementation, the drop will be called, which can lead to undefined behavior.
We also don’t have a drop implementation on the vector. As a result, when the vector is gone, the memory is leaked.

Lets fix them

    // Newly added function to allocate new memory with double the capacity. 
    // It also checks if the previous capacity is zero. 
    fn inc(&mut self) {
        let cap = if self.cap == 0 { 1 } else { self.cap * 2 };
        self.cap = cap;
        unsafe {
        // malloc, then copy, then delete
            let np = libc::malloc(size_of::<T>() * cap) as *mut T;
            if np.is_null() {
                panic!("failed to relloc");
            }
            std::ptr::copy(self.data as *const T, np, self.len);
            libc::free(self.data as *mut c_void);
            self.data = np;
        };
    }
    pub fn push(&mut self, n: T) {
        if self.len >= self.cap {
            self.inc();
        }
        unsafe {
            let addr = self.data.add(self.len);
            // let addr = (self.data as usize) + self.len * size_of::<T>();
            // write to pointer using write api
            std::ptr::write(addr, n)
        };
        
        self.len += 1;
    }
    pub fn nth(&self, n: usize) -> Option<T>
    where
        T: Copy,
    {
        if n >= self.len {
            return None;
        }
        let addr = unsafe { self.data.add(n) };
        // let addr = (self.data as usize) + (n) * size_of::<T>();
        // read using read api
        return Some(unsafe { std::ptr::read(addr) });
    }
}
...
impl<T> Drop for OwnVec<T> {
    fn drop(&mut self) {
    // dropping heap allocated object
       unsafe { libc::free(self.data as *mut c_void)};
    }
}

In the above snippet, we have introduced:

inc function to allocate new capacity when the previously allocated space is filled. We copy the previous space to the new allocated space and then free the previous space.
Another thing we have done is that we have used the write and read API to write to the address.
For calculating the address, we are not using manual calculations. Now we are using the pointer arithmetic add method.
Apart from that, we have also added the drop implementation.

Polishing implementation

There are still a few things missing:

When we call the drop on the vector, we are not calling the individual drop of the array elements. It can happen that the own vec has a string that, only the main data structure in the heap will be deallocated in a single call, but we also want the data string pointers to be deallocated.
Another problem we have is that we are manually doing new allocation and then copying and then deallocating. Instead, libc has the libc:realloc function for this exact flow.

    fn inc(&mut self) {
        let cap = if self.cap == 0 { 1 } else { self.cap * 2 };
        self.cap = cap;
        // using libc::realloc
        let x = unsafe { libc::realloc(self.data as *mut c_void, cap * size_of::<T>()) as *mut T };
        if x.is_null() {
            panic!("failed to relloc");
        }
        self.data = x;
    }
    ...
    impl<T> Drop for OwnVec<T> {
    fn drop(&mut self) {
        unsafe {
        // calling drop on individual objects.
            for i in 0..self.len {
                std::ptr::drop_in_place(self.data.add(i));
            }
            libc::free(self.data as *mut c_void);
        }
    }
}

Tasks

We have a basic working implementation of VAC. Now we want to further improve it by, instead of directly having a pointer, we can use an unsafecell which internally references the pointer, or we can use NonNull. The usage of notnull needs to be paired with phantomData<* mut T> because not null is covariant with t

Lets implement our own vec

Lets fix them

Polishing implementation

Tasks

Links: