Demilade Sonuga's blog

All posts

Box III

2023-04-02 · 32 min read

In this post, we're going to test the Box.

What Exactly Are We Testing

The aim of testing the Box is to see if it behaves the way it ought to behave under certain conditions. We need to check if our trait implementations, PartialEq, Deref, DerefMut, Drop, are working as expected. We need to check if panics occur when they're supposed to, like when an allocation fails, and when they're not supposed to.

The same thing goes for our into_raw and from_raw functions. The into_raw function must return a valid pointer to the underlying data in the Box and the from_raw function when given a valid pointer and allocator, must return a perfectly valid Box managing the data behind that pointer.

An Allocator Trait

Before we start testing, we need to make one thing clear: we are testing the Box, not the allocator. To make sure that we're doing this, we need to ensure that we use only dummy allocators that predictably behave exactly how we want them to behave. For example, when testing the Box under normal conditions, we need to have an allocator that will reliably succeed no matter what. And when we're testing failure conditions, we need to have an allocator that will reliably fail no matter what.

This implies that we shouldn't use our LinkedListAllocator to test the Box. We need another allocator. The problem that arises here is that our Box has been hardcoded to use only LinkedListAllocator:

impl<T> Box<T> {
    pub fn new(val: T, allocator: *mut LinkedListAllocator) -> Box<T> {
        /* ...Others */
    }
}

When, instead, what we want is anything that can behave like an allocator. This calls for a form of polymorphism: the ability to use multiple types in a single context. We need to be able to accept not just LinkedListAllocator as allocator but any other allocator of our making, as long as it has the alloc and dealloc functions.

There are different ways we could achieve this, but the approach we'll be using here is to let allocator be a trait object, instead of a pointer to a concrete type. If you're not familiar with trait objects, check the references.

Instead of having just one LinkedListAllocator, we'll have an Allocator trait which will be implemented for anything that we want to use as an allocator. It will be implemented for the LinkedListAllocator and for structs that we'll use as dummy allocators.

To effect this change, we'll start by creating an Allocator trait. Open allocator.rs and throw this in:

// The trait for structs that can be used as heap allocators
pub unsafe trait Allocator {
    // Allocate memory of `size` bytes with an alignment of `alignment`
    unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8>;
    // Deallocate memory of size `size_to_dealloc` pointed at by `ptr`
    unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize);
}

The trait and all the functions in it are unsafe because this heap allocation business is all very unsafe. There is really no way the compiler can verify the correctness of any of the implementations (I mean, just take a look at the allocator.rs code; we might have well written in C (it's just so unsafe)).

Then refactor the LinkedListAllocator's alloc and dealloc functions into an Allocator implementation:

impl LinkedListAllocator {
    /* DELETED:
    pub fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> { /* ...Others */}
    */

    /* DELETED:
    pub fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {/* ...Others */}
    */
}

// NEW:
unsafe impl Allocator for LinkedListAllocator {
    unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> {
        self.find_free_region(size, alignment)
    }

    unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {
        self.add_free_region(MemChunk {
            start_addr: ptr as usize,
            size: size_to_dealloc
        });
    }
}

Run the tests again:

cargo test

And they should still pass. This is one of the benefits of automated testing: you can make changes like these and verify, to an extent, that the code still works as expected.

Making changes to Box:

// DELETED: use crate::allocator::LinkedListAllocator;
use crate::allocator::Allocator; // NEW
pub struct Box<T> {
    ptr: *mut T,
    // DELETED: allocator: *mut LinkedListAllocator
    allocator: *mut dyn Allocator // NEW
}
impl<T> Box<T> {
    // DELETED: pub fn new(val: T, allocator: *mut LinkedListAllocator) -> Box<T> {
    pub fn new(val: T, allocator: *mut dyn Allocator) -> Box<T> { // NEW
        /* ...Others */
    }

    // DELETED: pub unsafe fn from_raw<U>(ptr: *mut U, allocator: *mut LinkedListAllocator) -> Box<U> {
    pub unsafe fn from_raw<U>(ptr: *mut U, allocator: *mut dyn Allocator) -> Box<U> { // NEW
        /* ...Others */
    }
}

Dummy Allocators

With the new Allocator trait, we can now create dummy allocators that will behave predictably whenever we use them. One to predictably succeed, to test normal scenarios. And another to predictably fail, to test scenarios where there isn't space for data on the heap.

To create an allocator that will predictably be successful:

In boxed.rs

#[cfg(test)]
mod tests {
    use crate::allocator::Allocator;

    // Dummy allocator that we can depend on to always succeed
    struct SuccessfulAllocator;

    
    use std::alloc::Global as PlatformAllocator;
    use std::alloc::Layout;
    use std::ptr::NonNull;
    use std::alloc::Allocator as StdAllocator;
    
    // Use your computer's allocator to allocate and deallocate memory
    // Much more reliable than using our own custom allocator,
    // so we can depend on it succeeding (under normal circumstances)
    unsafe impl Allocator for SuccessfulAllocator {
        unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> {
            let mem_layout = Layout::from_size_align(size, alignment).unwrap();
            let mem = PlatformAllocator.allocate(mem_layout).unwrap();
            let ptr = mem.as_ptr() as *mut u8;
            Some(ptr)
        }
        unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {
            // Using an alignment of 1 here because I think the alignment no
            // longer matters here. We're deallocating memory because we're
            // done using it
            let mem_layout = Layout::from_size_align(size_to_dealloc, 1).unwrap();
            PlatformAllocator.deallocate(NonNull::new(ptr).unwrap(), mem_layout);
        }
    }
}

For the alloc function, a Layout struct is first instantiated. This struct's purpose is to tell your platform's allocator the size and required alignment of memory to allocate (or deallocate).

The platform allocator which we make use of is the global memory allocator: Global. It's a unit tuple that implements the Allocator trait provided by the std crate.

You'll notice that the unit struct didn't need to be instantiated before we could start using it like so: PlatformAllocator.allocate. This is normal with unit structs: they don't need to be instantiated.

To dive deeper into the structs used in this code, you can check the references.

For the code to work, we need to let the compiler know that we're using an experimental feature.

In main.rs

#![cfg_attr(not(test), no_std)]
#![cfg_attr(not(test), no_main)]
#![feature(abi_efiapi, abi_x86_interrupt)]
#![feature(panic_info_message)]
#![cfg_attr(test, feature(allocator_api))] // NEW

And for the testing tool to find our tests:

// ...Others
mod boxed; // NEW
mod allocator;
// ...Others

Invoking cargo test should result in a successful compilation and run of the allocator tests.

As for our always-failing allocator:

In boxed.rs

#[cfg(test)]
mod tests {
    // ...Others

    // Dummy allocator we can depend on to always fail
    struct FailingAllocator;

    unsafe impl Allocator for FailingAllocator {
        unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> {
            None
        }
        unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {}
    }
}

Testing

Let's start with the PartialEq implementations.

Out first implementation:

impl<T: PartialEq> PartialEq<Box<T>> for Box<T> {
    fn eq(&self, other: &Box<T>) -> bool {
        unsafe { *self.ptr == *other.ptr }
    }
}

is for comparing Box<T> and Box<T>. To test it, we check if the comparisons result in true or false as expected.

#[cfg(test)]
mod tests {
    use super::*; // NEW
    use crate::allocator::Allocator;

    // NEW:
    #[test]
    fn test_partial_eq1() {
        let box1 = Box::new(32, successful_allocator());
        let box2 = Box::new(32, successful_allocator());
        let box3 = Box::new(1984, successful_allocator());
        assert_eq!(box1, box2);
        assert_ne!(box1, box3);
    }

    // NEW:
    // Convenience function for getting the always successful allocator
    fn successful_allocator() -> *mut SuccessfulAllocator {
        &mut SuccessfulAllocator as *mut _
    }

    // ...Others
}

If you run the tests now, you'll see an error telling us that the Box<T> must implement Debug for the assert macros to be used. We can't just #[derive(Debug)] in this situation because we don't want to be printing out the pointer to the allocator. We only want to print the data.

To implement Debug for Box:

use crate::allocator::Allocator;
use core::mem;
use core::cmp::PartialEq;
use core::fmt; // NEW
impl<T: core::fmt::Debug> core::fmt::Debug for Box<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_struct("Box")
            .field("val", unsafe { &*self.ptr })
            .finish()
    }
}

This implementation of Debug ensures that only the value pointed to is printed out. It makes use of some utility functions provided by the Formatter struct in core::fmt. If you would like to take a good look at those functions, check the references. Let's just say that printing Box::new(32, allocator) with the Debug formatting will look like this: "Box { val: 32 }" (if we have '{' and '}' in our font).

Invoking cargo test again will result in a successful execution of all the tests, including the one we just wrote.

But, as I said mentioned in an earlier post, you really should not be trusting tests that have never failed. You should mess around with the test and the code to make sure it passes and fails as expected.

The other implementation of PartialEq:

impl<T: PartialEq> PartialEq<T> for Box<T> {
    fn eq(&self, other: &T) -> bool {
        unsafe { *self.ptr == *other }
    }
}

is for comparing Box<T> and T. To test it:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn test_partial_eq2() {
        let box1 = Box::new(32, successful_allocator());
        let n1 = 32;
        let n2 = 1984;
        assert_eq!(box1, n1);
        assert_ne!(box1, n2);
    }

    // ...Others
}

Run the tests and you should have success. Again, experiment. Mess around and verify that the test is working.

To test our implementations of Deref and DerefMut, we need to ensure that the dereference operator (*), when used with the Box properly dereferences to the underlying data.

To test this:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn test_deref() {
        let box1 = Box::new(45, successful_allocator());
        let mut n = 1_000;
        n = *box1;
        assert_eq!(n, 45);
    }

    // ...Others
}

This test checks to see if the Box, when dereferenced, really returns the data behind the pointer.

Running the tests should not result in failure.

To test the DerefMut:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn test_deref_mut() {
        let mut b: Box<i32> = Box::new(45, successful_allocator());
        *b = 999_999;
        assert_eq!(b, 999_999);
    }

    // ...Others
}

When allocation fails while trying to create a new Box, a panic should occur:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    #[should_panic]
    fn test_failed_allocation() {
        let box1 = Box::new(32, failing_allocator());
    }

    // Convenience function for getting the always fail allocator
    fn failing_allocator() -> *mut FailingAllocator {
        &mut FailingAllocator as *mut _
    }

    // ...Others
}

Running the tests should result in success.

The into_raw retrieves the pointer from the Box:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn box_into_raw() {
        let b: Box<usize> = Box::new(1984, successful_allocator());
        let b_ptr = Box::into_raw(b);
        unsafe { assert_eq!(*b_ptr, 1984) }
    }

    // ...Others
}

And from_raw creates a Box from a valid pointer and allocator:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn box_from_raw() {
        let allocator = successful_allocator();
        let ptr = unsafe {
            let ptr = (*allocator).alloc(mem::size_of::<i32>(), mem::align_of::<i32>())
                .unwrap() as *mut i32;
            *ptr = 100_000_000;
            ptr
        };
        let b = unsafe { Box::<i32>::from_raw(ptr, allocator) };
        assert_eq!(*b, 100_000_000);
    }

    // ...Others
}

And that's where we stop Box testing. There are a lot of things our tests don't cover like the Drop implementation. The essence of our tests is to demonstrate that the basic stuff is in place and is working as expected.

Remember that tests can only show the presence of bugs, but not the absence.

You should figure out how to test the things left untested here.

Our list, before we get on with event handling, looks like this now:

  1. Create a heap (without the heap, there can be no allocator).
  2. Create an allocator (without the allocator, there can be no Box or Vec).
  3. Create a Box.
  4. Create a Vec.
  5. Get on with the event handling scheme.

Just to create a Vec, then we can get on with what we're doing. But even before that, there are some things I think it will be wise to mention first, about concurrency and some potential safety problems with our allocator and Boxes, and that will be the subject of the next post.

Take Away

For the full code, go to the repo

In The Next Post

We'll look at a few potential problems with our allocator and Box related to concurrency and safety

References

← Previous Post

Box II

Next Post →

Interlude A: Some Potential Problems In The Project