Allocator

OS in Rust

Update

This is a lab.

The last homework would be assigned Friday, 24 April.
Homeworks are due one week after being assigned, which would be Friday, 1 May.
Study Days run 30 April to 1 May.
So no homework may be assigned that day.

There is no more homework, so this week we only have this lab.

Cheating Using an Allocator Crate

Since implementing an allocator is somewhat complex, we start by using an external allocator crate.

A simple allocator crate for no_std applications is the linked_list_allocator crate. Its name comes from the fact that it uses a linked list data structure to keep track of deallocated memory regions.

Q: When will you used linked lists?

A: Always.

To use the crate, we first need to add a dependency on it in our Cargo.toml:

Cargo.toml

[dependencies]
linked_list_allocator = "0.9.0"

Then we can replace our dummy allocator with the allocator provided by the crate:

src/allocator.rs

#[global_allocator]
static ALLOCATOR: linked_list_allocator::LockedHeap = linked_list_allocator::LockedHeap::empty();

The struct is named LockedHeap because it uses the spinning_top::Spinlock type for synchronization. This is required because multiple threads could access the ALLOCATOR static at the same time. As always, when using a spinlock or a mutex, we need to be careful to not accidentally cause a deadlock. This means that we shouldn’t perform any allocations in interrupt handlers, since they can run at an arbitrary time and might interrupt an in-progress allocation.

Setting the LockedHeap as global allocator is not enough. The reason is that we use the empty constructor function, which creates an allocator without any backing memory. Like our dummy allocator, it always returns an error on alloc. To fix this, we need to initialize the allocator after creating the heap:

src/allocator.rs

pub fn init_heap(
    mapper: &mut impl x86_64::structures::paging::Mapper<x86_64::structures::paging::Size4KiB>,
    frame_allocator: &mut impl x86_64::structures::paging::FrameAllocator<
        x86_64::structures::paging::Size4KiB,
    >,
) -> Option<()> {

    // All the stuff we did already

    unsafe {
        ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE);
    }

    return Some(());
}

We use the lock method on the inner spinlock of the LockedHeap type to get an exclusive reference to the wrapped [Heap] instance, on which we then call the init method with the heap bounds as arguments. Because the init function already tries to write to the heap memory, we must initialize the heap only after mapping the heap pages.

After initializing the heap, we can now use all allocation and collection types of the built-in [alloc] crate without error:

src/main.rs

    // Do all the initialization stuff

    println!("Hello world{}", "!");
    let b = alloc::boxed::Box::new(371);
    println!("Hello box containing {}!", *b);
    println!("Hello box at {:p}!", b);
    
    // All the other main nonsense.

I see the following:

Hello world!
Hello box containing 371!
Hello box at 0xc3710010!

I note that this is the 371 we enboxified and the 0x_c371_0000 used as a memory location during initialization (which mean it is out on the heap).

Of course, there are many more allocation and collection types in the alloc crate that we can now all use in our kernel, including:

the thread-safe reference counted pointer Arc
the owned string type String and the format! macro
LinkedList
the growable ring buffer VecDeque
the BinaryHeap priority queue
BTreeMap and BTreeSet

Recall

I, an actual real life Rust developer (honest!) have used BTreeMap.

These types will become very useful to implement thread lists, scheduling queues, or support for async/await.

Adding a Test

To ensure that we don’t accidentally break our new allocation code, we should add an integration test for it. We start by creating a new tests/heap_allocation.rs file with the following content:

tests/heap_allocation.rs

#![no_std]
#![no_main]
#![feature(custom_test_frameworks)]
#![test_runner(osirs::_test_runner)]

extern crate alloc;

#[panic_handler]
fn panic(info: &core::panic::PanicInfo) -> ! {
    osirs::test_panic_handler(info)
}

#[unsafe(no_mangle)]
pub extern "C" fn _start() -> ! {
    osirs::init();
    osirs::qemu_quit(osirs::QEMU_PASS);
    osirs::halt();
}

Best Practice

Around this point, I would refactor all the initialization code back into the src/lib.rs function init() to avoid copying around (and maintaining!) reams of code.

Now we’re ready to add a few test cases. First, we add a test that performs some simple allocations using [Box] and checks the allocated values to ensure that basic allocations work:

tests/heap_allocation.rs

fn simple_allocation() {
    let heap_value_1 = alloc::boxed::Box::new(41);
    let heap_value_2 = alloc::boxed::Box::new(13);
    assert_eq!(*heap_value_1, 41);
    assert_eq!(*heap_value_2, 13);
}

Most importantly, this test verifies that no allocation error occurs.

Next, we iteratively build a large vector, to test both large allocations and multiple allocations (due to reallocations):

tests/heap_allocation.rs

fn large_vec() {
    let n = 1000;
    let mut vec = alloc::vec::Vec::new();
    for i in 0..n {
        vec.push(i);
    }
    assert_eq!(vec.iter().sum::<u64>(), (n - 1) * n / 2);
}

We verify the sum by comparing it with the formula for the n-th partial sum. This gives us some confidence that the allocated values are all correct.

\[ \sum_{k=1}^n k = \frac{n(n + 1)}{2} \]

As a third test, we create ten thousand allocations after each other:

tests/heap_allocation.rs

fn many_boxes() {
    for i in 0..osirs::allocator::HEAP_SIZE {
        let x = Box::new(i);
        assert_eq!(*x, i);
    }
}

Timeout

I couldn’t finish this test during my timeout window, but you can make a smaller heap size, especially just for now, and may need to change the vector test accordingly.

This test ensures that the allocator reuses freed memory for subsequent allocations since it would run out of memory otherwise. This might seem like an obvious requirement for an allocator, but there are allocator designs that don’t do this.

Let’s run our new integration test:

> cargo test --test heap_allocation
[…]
Initiating test 0x00... [Pass]
Initiating test 0x01... [Pass]
Initiating test 0x02... [Pass]

All three tests succeeded! You can also invoke cargo t (without the --test argument) to run all unit and integration tests.

Fin

--- title: Allocator format: html --- # Update This is a lab. - The last homework would be assigned Friday, 24 April. - Homeworks are due one week after being assigned, which would be Friday, 1 May. - Study Days run 30 April to 1 May. - So no homework may be assigned that day. **There is no more homework, so this week we only have this lab.** ## <s>Cheating</s> Using an Allocator Crate Since implementing an allocator is somewhat complex, we start by using an external allocator crate. A simple allocator crate for `no_std` applications is the [`linked_list_allocator`] crate. Its name comes from the fact that it uses a linked list data structure to keep track of deallocated memory regions. ::: {.callout-note} ## Q: When will you used linked lists? **A**: Always. ::: To use the crate, we first need to add a dependency on it in our `Cargo.toml`: [`linked_list_allocator`]: https://github.com/phil-opp/linked-list-allocator/ ```{.toml filename="Cargo.toml"} [dependencies] linked_list_allocator = "0.9.0" ``` Then we can replace our dummy allocator with the allocator provided by the crate: ```{.rs filename="src/allocator.rs"} #[global_allocator] static ALLOCATOR: linked_list_allocator::LockedHeap = linked_list_allocator::LockedHeap::empty(); ``` The struct is named `LockedHeap` because it uses the [`spinning_top::Spinlock`](https://docs.rs/spinning_top/0.1.0/spinning_top/type.Spinlock.html) type for synchronization. This is required because multiple threads could access the `ALLOCATOR` static at the same time. As always, when using a spinlock or a mutex, we need to be careful to not accidentally cause a deadlock. This means that we shouldn't perform any allocations in interrupt handlers, since they can run at an arbitrary time and might interrupt an in-progress allocation. Setting the `LockedHeap` as global allocator is not enough. The reason is that we use the [`empty`](https://docs.rs/linked_list_allocator/0.9.0/linked_list_allocator/struct.LockedHeap.html#method.empty) constructor function, which creates an allocator without any backing memory. Like our dummy allocator, it always returns an error on `alloc`. To fix this, we need to initialize the allocator after creating the heap: ```{.rs filename="src/allocator.rs"} pub fn init_heap( mapper: &mut impl x86_64::structures::paging::Mapper<x86_64::structures::paging::Size4KiB>, frame_allocator: &mut impl x86_64::structures::paging::FrameAllocator< x86_64::structures::paging::Size4KiB, >, ) -> Option<()> { // All the stuff we did already unsafe { ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE); } return Some(()); } ``` We use the [`lock`](https://docs.rs/lock_api/0.3.3/lock_api/struct.Mutex.html#method.lock) method on the inner spinlock of the `LockedHeap` type to get an exclusive reference to the wrapped [`Heap`] instance, on which we then call the [`init`](https://docs.rs/linked_list_allocator/0.9.0/linked_list_allocator/struct.Heap.html#method.init) method with the heap bounds as arguments. Because the [`init`](https://docs.rs/linked_list_allocator/0.9.0/linked_list_allocator/struct.Heap.html#method.init) function already tries to write to the heap memory, we must initialize the heap only _after_ mapping the heap pages. After initializing the heap, we can now use all allocation and collection types of the built-in [`alloc`] crate without error: ```{.rs filename="src/main.rs"} // Do all the initialization stuff println!("Hello world{}", "!"); let b = alloc::boxed::Box::new(371); println!("Hello box containing {}!", *b); println!("Hello box at {:p}!", b); // All the other main nonsense. ``` I see the following: ```{.email} Hello world! Hello box containing 371! Hello box at 0xc3710010! ``` I note that this is the `371` we enboxified and the `0x_c371_0000` used as a memory location during initialization (which mean it is out on the heap). Of course, there are many more allocation and collection types in the `alloc` crate that we can now all use in our kernel, including: - the thread-safe reference counted pointer [`Arc`](https://doc.rust-lang.org/alloc/sync/struct.Arc.html) - the owned string type [`String`](https://doc.rust-lang.org/alloc/string/struct.String.html) and the [`format!`](https://doc.rust-lang.org/alloc/macro.format.html) macro - [`LinkedList`](https://doc.rust-lang.org/alloc/collections/linked_list/struct.LinkedList.html) - the growable ring buffer [`VecDeque`](https://doc.rust-lang.org/alloc/collections/vec_deque/struct.VecDeque.html) - the [`BinaryHeap`](https://doc.rust-lang.org/alloc/collections/binary_heap/struct.BinaryHeap.html) priority queue - [`BTreeMap`](https://doc.rust-lang.org/alloc/collections/btree_map/struct.BTreeMap.html) and [`BTreeSet`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html) ::: {.callout-note appearance="simple"} ## Recall I, an actual real life Rust developer (honest!) have used `BTreeMap`. ::: These types will become very useful to implement thread lists, scheduling queues, or support for async/await. ## Adding a Test To ensure that we don't accidentally break our new allocation code, we should add an integration test for it. We start by creating a new `tests/heap_allocation.rs` file with the following content: ```{.rs filename="tests/heap_allocation.rs"} #![no_std] #![no_main] #![feature(custom_test_frameworks)] #![test_runner(osirs::_test_runner)] extern crate alloc; #[panic_handler] fn panic(info: &core::panic::PanicInfo) -> ! { osirs::test_panic_handler(info) } #[unsafe(no_mangle)] pub extern "C" fn _start() -> ! { osirs::init(); osirs::qemu_quit(osirs::QEMU_PASS); osirs::halt(); } ``` ::: {.callout-note} ## Best Practice Around this point, I would refactor all the initialization code back into the `src/lib.rs` function `init()` to avoid copying around (and maintaining!) reams of code. ::: Now we're ready to add a few test cases. First, we add a test that performs some simple allocations using [`Box`] and checks the allocated values to ensure that basic allocations work: ```{.rs filename="tests/heap_allocation.rs"} fn simple_allocation() { let heap_value_1 = alloc::boxed::Box::new(41); let heap_value_2 = alloc::boxed::Box::new(13); assert_eq!(*heap_value_1, 41); assert_eq!(*heap_value_2, 13); } ``` Most importantly, this test verifies that no allocation error occurs. Next, we iteratively build a large vector, to test both large allocations and multiple allocations (due to reallocations): ```{.rs filename="tests/heap_allocation.rs"} fn large_vec() { let n = 1000; let mut vec = alloc::vec::Vec::new(); for i in 0..n { vec.push(i); } assert_eq!(vec.iter().sum::<u64>(), (n - 1) * n / 2); } ``` We verify the sum by comparing it with the formula for the [n-th partial sum](https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF#Partial_sums). This gives us some confidence that the allocated values are all correct. $$ \sum_{k=1}^n k = \frac{n(n + 1)}{2} $$ As a third test, we create ten thousand allocations after each other: ```{.rs filename="tests/heap_allocation.rs"} fn many_boxes() { for i in 0..osirs::allocator::HEAP_SIZE { let x = Box::new(i); assert_eq!(*x, i); } } ``` ::: {.callout-note} ## Timeout I couldn't finish this test during my timeout window, but you can make a smaller heap size, especially just for now, and may need to change the vector test accordingly. ::: This test ensures that the allocator reuses freed memory for subsequent allocations since it would run out of memory otherwise. This might seem like an obvious requirement for an allocator, but there are allocator designs that don't do this. Let's run our new integration test: ``` > cargo test --test heap_allocation […] Initiating test 0x00... [Pass] Initiating test 0x01... [Pass] Initiating test 0x02... [Pass] ``` All three tests succeeded! You can also invoke `cargo t` (without the `--test` argument) to run all unit and integration tests. # Fin