It was at this point that I discovered the Embedded Rust Manual while searching for information about memory allocation. In particular, I became much more aware of the difference between the core crate and the std crate. Specifically, most of the hard work is done in the core crate and the main things that are missing are memory allocation and automated loading of libraries. Collections such as Vec are also excluded, but can be included separately by importing them from the collections crate. Macros such as println! also seem to be a problem, but it's one I've seen other people work around and will come back to.
Explicit memory allocation is covered in Chapter 7 of the Embedded Rust Manual and it seems at first glance to be really complicated. Now that I think I've understood it (having read numerous other references as well), let's test that by seeing if I can explain it while writing some code.
Let's start by writing the line of code that we really want, replacing the code that allocates a message buffer on the stack with one that allocates a 35-byte message on the heap and returns an array.
let mut buf: &mut [u32] = allocate_message_buffer(35);To implement this function we need to allocate a block of memory using the "global allocator" and then "turn that" into an array slice.
In order to use alloc directly, we need to add the following declaration at the top of our file:
extern crate alloc;The documentation says that it is also necessary to specify #![feature(alloc)], but the compiler contradicts this, saying that this is only necessary for unstable features, and the alloc feature has been stable for a while, so the feature declaration is no longer needed.
The function to allocate the memory we need for our message buffer is then fairly easy to write, with the caveat that it involves some arcane Rust magic:
fn allocate_message_buffer(nwords: usize) -> &'static mut [u32] {Starting in the middle, the normal way of referencing alloc would be std::alloc::alloc, that is, the alloc function in the alloc module of the std crate, but because we aren't using std but the alloc crate direcly, it becomes alloc::alloc::alloc. Likewise, the Layout class would normally be referenced as std::alloc::Layout but becomes alloc::alloc::Layout.
unsafe {
let ptr = alloc::alloc::alloc(alloc::alloc::Layout::from_size_align_unchecked(nwords * 4, 16)) as *mut u32;
alloc::slice::from_raw_parts_mut(ptr, nwords)
}
}
The key thing we want to achieve is 16-byte alignment, so we specify a Layout with a size of nwords words and an alignment of 16. It's my impression that both of these values are expected to be in bytes, but I can't claim that I have read anything which makes this absolutely clear. We then pass the resultant Layout object to the alloc method which returns a *mut u8 pointer, which we then cast to a *mut u32 pointer.
However, what we really want to do is to return an array slice, which is a "regular", stack-allocated object which wraps this pointer together with other meta-information (specifically, the size of each element and the number of elements that can be referenced without overflow) which can be used "safely", that is, with full compiler checks and no need for the unsafe keyword.
To effect this transition, we call the slice::from_raw_parts_mut function, passing in the pointer and the available number of words (I think it deduces the size of each entry from the type of the pointer). This constructs and returns an array slice, which we then return to the caller.
Most of the return type - &mut [u32] - makes perfect sense to me, but the compiler forced me to add the 'static lifetime. I'm still a Rust newbie, so I can't claim to understand this, but if it's what the compiler requires, it "must be" right - at least until it isn't or until I know more. My instinct is that we want to copy what we have created on the stack into the parent, not return something with the static lifecycle, but since I don't understand what I am doing, I will follow the compiler's advice until I run into trouble.
There are a couple more changes that I need to make in order for all the code to be consistent. Obviously, I want to remove the copy into the Message struct, and we need to then convert the array slice address to a raw pointer using the as_mut_ptr.
mbox_send(8, &mut buf);We need to change the signature of the mbox_send to remove the explicit array length, and likewise change the code to extract the pointer.
let volbuf: *mut u32 = buf.as_mut_ptr();
fn mbox_send(ch: u8, buf: &mut[u32]) {So now we can try building this. As you might expect, we get linking errors:
while mmio_read(MBOX_STATUS) & MBOX_BUSY != 0 {
}
// obtain the address of buf as a raw pointer
let volbuf = buf.as_mut_ptr();
Compiling homer_rust v0.1.0 (/home/gareth/Projects/IgnoranceBlog/homer_rust)Having said I was expecting linking errors, I don't think I was expecting these linking errors: I don't know what rust_no_alloc_shim_is_unstable even is, and I was thinking the rust_alloc would be defined and have some internal logic to handle the actual allocation process.
Finished release [optimized] target(s) in 0.20s
aarch64-linux-gnu-ld -nostdlib boot.o ../target/aarch64-unknown-linux-gnu/release/libhomer_rust.rlib -T linker.ld -o kernel8.elf
aarch64-linux-gnu-ld: ../target/aarch64-unknown-linux-gnu/release/libhomer_rust.rlib(homer_rust-2e5114238dd615aa.homer_rust.f56f16d2546ffac4-cgu.0.rcgu.o): in function `kernel_main':
homer_rust.f56f16d2546ffac4-cgu.0:(.text.kernel_main+0xb8): undefined reference to `__rust_no_alloc_shim_is_unstable'
aarch64-linux-gnu-ld: homer_rust.f56f16d2546ffac4-cgu.0:(.text.kernel_main+0xbc): undefined reference to `__rust_no_alloc_shim_is_unstable'
aarch64-linux-gnu-ld: homer_rust.f56f16d2546ffac4-cgu.0:(.text.kernel_main+0xcc): undefined reference to `__rust_alloc'
make: *** [Makefile:14: kernel8.img] Error 1
Anyway, I'm now going to go ahead and implement an allocator as laid out in the Embedded Rust Book chapter on alloc and see what happens.
I'm going to put the allocator in a new module, so in lib.rs, I added the following line toward the top of the file:
mod allocator;and created a file allocator.rs.
The first thing I want to do is build enough code that the program links again, and then worry about whether it works or not - once it builds, I can always connect a debugger if I need to in order to see what is happening inside.
Following the instructions in the guide, the first thing we are going to do is use the global_allocator attribute to declare an allocator called HEAP.
use core::alloc::GlobalAlloc;In order to be able to fulfill the role of global_allocator, it is necessary to implement the GlobalAlloc trait. This has two methods, alloc and dealloc. For now, while we are just trying to get something to link, we are going to just return 0 in alloc. We don't need to implment dealloc at all yet.
#[global_allocator]
static HEAP: HeapAllocator = HeapAllocator {
};
struct HeapAllocator {
}
unsafe impl GlobalAlloc for HeapAllocator {Excellent. That links and we can try running it. Unsurprisingly, it doesn't resize the screen and doesn't display Homer. OK, I can live with that for now.
unsafe fn alloc(&self, _layout: core::alloc::Layout) -> *mut u8 {
// simply return 0 - won't work but will link
0x0 as *mut u8
}
unsafe fn dealloc(&self, _ptr: *mut u8, _layout: core::alloc::Layout) {
// we don't support deallocation yet
}
}
Moving on, let's try and allocate a heap and then have our allocator return the block at the beginning of that area.
It seems to me that the right way to do this is to allocate a .heap section in the linker script, linker.ld. I'm going to put it at the end, after the .bss section and before the .end (obviously):
. = ALIGN(4096); /* align to page size */This declares a .heap section and three symbols: __heap_start, which marks the start of the block, immediately after the end of the .bss section, aligned to a 4096-byte page boundary; __heap_end, at the end of the heap, which I have explicitly forced to be at 0x100000; and __heap_size, the size of the heap, which the linker calculates as the difference between these two.
__bss_end = .;
__bss_size = __bss_end - __bss_start;
__heap_start = .;
.heap :
{
}
. = 0x100000;
__heap_end = .;
__heap_size = __heap_end - __heap_start;
__end = .;
Now we can update the allocator to include __heap_start:
extern {and return it from the alloc function:
pub static __heap_start : *mut u8;
}
unsafe fn alloc(&self, _layout: core::alloc::Layout) -> *mut u8 {Strangely, this now goes back to issuing some linker errors:
// just return the top of heap
__heap_start
}
Compiling homer_rust v0.1.0 (/home/gareth/Projects/IgnoranceBlog/homer_rust)It's that symbol __rust_no_alloc_shim_is_unstable again. I suspect that this is something to do with unstable Rust builds; let's track that down.
Finished dev [unoptimized + debuginfo] target(s) in 0.06s
aarch64-linux-gnu-ld -nostdlib boot.o ../target/aarch64-unknown-linux-gnu/debug/libhomer_rust.rlib -T linker.ld -o kernel8.elf
aarch64-linux-gnu-ld: ../target/aarch64-unknown-linux-gnu/debug/libhomer_rust.rlib(homer_rust-c9f0f32593953886.1y1lhhvr9vp1xcdg.rcgu.o): in function `alloc::alloc::alloc':
/rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/alloc/src/alloc.rs:92: undefined reference to `__rust_no_alloc_shim_is_unstable'
aarch64-linux-gnu-ld: /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/alloc/src/alloc.rs:92: undefined reference to `__rust_no_alloc_shim_is_unstable'
This thread explains that it is there as a hint to remind implementors that some aspects of the API may change in the future. I'm not quite sure what that means, but it sounds a bit like signing a legal contract. I don't see how it will actually help me in the future, unless it is going to be replaced by _is_stable or something when the API changes, which will stop the program linking again until I make the necessary changes.
Anyway, it seems to be declared in the allocator API and we just need to define and export it:
#[allow(non_upper_case_globals)]This feels more wrangling than actual code: the first simply suppresses the warning associated with having to declare a C style variable: Rust expects static variables to be declared in upper snake case. The second stops the name (which has already been mangled) being mangled again.
#[no_mangle]
pub static __rust_no_alloc_shim_is_unstable: u8 = 0;
Running the application with this allocator in place, we now see Homer again.
Adding in a trace statement to check on the address that is returned from our allocator, I'm staggered to see it returning 00000000. How can that be? And if so, why did it not work when I returned 0 explicitly?
I suspect that there is something funky going on between declaring the variable __heap_start in the linker and using it here. So let's attach the debugger again. Remember that we have scripts scripts/debug.sh to compile and start the program, and scripts/gdb.sh to run the debugger. When we do this, we can put a breakpoint in the allocate function:
(gdb) b allocator.rs:21So it seems that what is happening here is that it is treating __heap_start not as a pointer itself, but as the location where the desired value can be found. Consequently, it is dereferencing it and returning the value in memory at that location - which could be anything but happens to be 0. So we need to take the address of __heap_start and then work through all the insanity of casting it to the value it needs to be:
Breakpoint 1 at 0x83364: file src/allocator.rs, line 21.
(gdb) c
Continuing.
Thread 1 hit Breakpoint 1, homer_rust::allocator::{impl#0}::alloc (self=0x8a163, _layout=...) at src/allocator.rs:21
21 __heap_start
(gdb) x/5i $pc
=> 0x83364 <_ZN89_LThomer_rust..allocator..HeapAllocatoru20asu20core..alloc..global..GlobalAllocGT5alloc17h5b531fd15c42200cE+16>: adrp x8, 0x8b000
0x83368 <_ZN89_LThomer_rust..allocator..HeapAllocatoru20asu20core..alloc..global..GlobalAllocGT5alloc17h5b531fd15c42200cE+20>: ldr x8, [x8, #16]
0x8336c <_ZN89_LThomer_rust..allocator..HeapAllocatoru20asu20core..alloc..global..GlobalAllocGT5alloc17h5b531fd15c42200cE+24>: ldr x0, [x8]
0x83370 <_ZN89_LThomer_rust..allocator..HeapAllocatoru20asu20core..alloc..global..GlobalAllocGT5alloc17h5b531fd15c42200cE+28>: add sp, sp, #0x20
0x83374 <_ZN89_LThomer_rust..allocator..HeapAllocatoru20asu20core..alloc..global..GlobalAllocGT5alloc17h5b531fd15c42200cE+32>: ret
unsafe fn alloc(&self, _layout: core::alloc::Layout) -> *mut u8 {In this context, *const _ refers to a "raw" pointer which is what we need to move from the pointer we have to the pointer we want. I think in the fullness of time the correct solution to declare the value of __heap_start not as a pointer but as an array or object or something from which we can more reasonably take the address. But this works, and the value shown by the debugger is now 00090000 which matches the value we can see using nm:
// just return the top of heap
(&__heap_start as *const _) as *mut u8
}
$ nm asm/kernel8.elfThis is checked in and tagged as RUST_BARE_METAL_MESSAGE_ALLOCATOR.
...
0000000000090000 B __heap_start
...
A Simple, Page-Based Allocator
So, the actual process of incorporating an allocator wasn't too bad. On the other hand, I haven't actually written an allocator yet - I have just implemented the API and it won't so much as handle two calls, let alone complexities such as reallocation or multi-threading.Not surprisingly, the alloc documentation in the Embedded Rust Book suggests that you don't write your own allocator, but use a battle-hardened one. But that's not why we're here. We are here (as JFK would say) to "play Texas": these are precisely the things we want to do in order to see how they work and how we can deal with the problems that arise.
For now, at least, I want to write something very simple, which can handle both allocation and deallocation and can handle different sizes of memory, along with alignment.
One of the challenges of memory management is fragmentation, and knowing where the most suitable chunk of memory can be found. What I'm going to do to reduce this complexity is only offer three possible chunk sizes: 16, 256 and 4096 bytes. Each of these will be aligned to the same boundary as its size. If you want less memory than one of these, I'll give you the next size up. If you want more than 4096 bytes in a single allocation, you will see receive a series of pages, fresh from the heap, but at least they will be guaranteed to be consecutive.
Memory is often (generally?) issued in 4096-byte "pages". This is certainly the case in the ARM v8 MMU. So if we handle memory internally in pages, we will probably find life easier than if we do something else.
The struct associated with the global_allocator can hold arbitrary data items, although obviously this is all allocated in the data segment, not on the heap. We can use this to hold references to our currently available pages.
My basic strategy is to divide up the memory between __heap_start and __heap_end into pages, and to allocate one of these each time we have run out of free memory. We will call this next_page. We can either allocate the new page as a whole page, as 15 256-byte blocks, or as 255 16-byte blocks. If a new page is requested and the pointer is already at __heap_end, we will return nulll (indicating out of memory, which apparently causes a panic in _rust_alloc). There is no garbage collection here, we are only going to reuse memory which has been deallocated.
We also need pointers to the free lists, which we will call free_16, free_256 and free_4096. Note that even when someone requests a whole page, we may have pages on hand which have been previously allocated and then deallocated which we can hand them. We will initialize each of these pointers to 0, indicating that there are no free entries available for that size.
When an alloc request is received, if a suitable block is on the free list, we want to return that, and update the pointer to point to the next free block. If the pointer is 0, then we need to allocate a whole new page, and then initialize it. What is meant by initialization? For a whole page, nothing is required, but for the other cases, we need to do two things:
- The first entry (somewhat wastefully) contains an integer which is the size of the entries in that block, i.e. either 16 or 256. We will use this in dealloc to determine how big the block was that we issued.
- We need to set up a linked list through the remaining entries in the block, so that when we return one of the entries in the block, we know where the next one is.
This is a non-trivial piece of code, and it is made more complicated by the fact that I am abusing Rust without really knowing what I'm doing. I am going to press on regardless, and get something to work which is in about the shape that we want. I'm then going to double back and use automated tests (now that I know how) to flesh out the implementation.
First off, I'm going to change __heap_start to be a u32, since we're only taking its address anyway. I'm also going to introduce __heap_end as a u32, so that we can detect when we run out of memory.
extern {I'm going to rename HeapAllocator to PageAllocator, since that more accurately reflects what it is doing, rather than the role that it is playing. And I am going to add four members: one to track where the next unassigned page is, and the other three to track where the heads of the three free lists are.
pub static __heap_start : u32;
pub static __heap_end : u32;
}
struct PageAllocator {I spent a lot of time trying to figure out how to store these values, but I ended up settling for the same UnsafeCell<usize> that is used in BumpPointerAlloc in the embedded Rust book. But doing this causes an error to appear:
next_page: UnsafeCell<usize>,
free_16: UnsafeCell<usize>,
free_256: UnsafeCell<usize>,
free_4096: UnsafeCell<usize>
}
error[E0277]: `UnsafeCell<usize>` cannot be shared between threads safelyI spent some time looking into this, and trying to understand how the BumpPointerAlloc class worked, until I spotted this line in the example:
--> src/allocator.rs:14:14
|
14 | static HEAP: PageAllocator = PageAllocator {
| ^^^^^^^^^^^^^ `UnsafeCell<usize>` cannot be shared between threads safely
|
= help: within `PageAllocator`, the trait `Sync` is not implemented for `UnsafeCell<usize>`
note: required because it appears within the type `PageAllocator`
--> src/allocator.rs:21:8
|
21 | struct PageAllocator {
| ^^^^^^^^^^^^^
= note: shared static variables must have a type that implements `Sync`
unsafe impl Sync for BumpPointerAlloc {}Basically, just wish it to be true! The code explicitly says that the memory allocator is only valid in a single-threaded environment. Presumably it would be possible to make the allocator thread-safe by appropriate use of thread-aware constructs, but since we are (currently) also in a single-threaded environment, I'm not going to worry about this too much, and just copy it.
// OK to hack this because we are single threaded for nowHaving declared the allocator, we need to initialize it. I again spent a non-trivial amount of time trying to figure out how to pass __heap_start into the initializer before finally giving up and saying "that is just a case I will need to handle in alloc". So we initialize all the fields to zero instead:
unsafe impl Sync for PageAllocator {}
#[global_allocator]Now it's just a question of writing the actual allocation function. This has four cases, which are:
static HEAP: PageAllocator = PageAllocator {
next_page: UnsafeCell::new(0),
free_16: UnsafeCell::new(0),
free_256: UnsafeCell::new(0),
free_4096: UnsafeCell::new(0)
};
- allocate a small block (16 bytes or less)
- allocate a middling block (17-256 byres)
- allocate a page (for requests from 257-4096 bytes)
- fail for now (for larger requests)
unsafe fn alloc(&self, layout: core::alloc::Layout) -> *mut u8 {So, yes, this does just delegate all of the hard work to a function called next. The reason for this is that the three cases where we do allocate memory are all very similar and we just need to consider which list to use (we also need to know the sizes of the block, but that code isn't written yet).
if layout.size() <= 16 && layout.align() <= 16 {
self.next(&self.free_16)
} else if layout.size() <= 256 && layout.align() <= 256 {
self.next(&self.free_256)
} else if layout.size() <= 4096 && layout.align() <= 4096 {
self.next(&self.free_4096)
} else {
core::ptr::null_mut() // this is allegedly what will cause OOM exceptions
}
}
That function does all the hard work. I think I'm going to present it first, then talk about it.
impl PageAllocator {First, note that this is not in the same impl block as alloc. That's because that block is exclusively for implementing the methods of the GlobalAlloc trait. This is a new method exclusive to PageAllocator and so goes in its own block.
unsafe fn next(&self, list: &UnsafeCell<usize>) -> *mut u8 {
let lp = list.get();
if *lp == 0 {
let np = self.next_page.get();
// we don't have any free memory, allocate next page
if *np == 0 {
*np = (&__heap_start as *const _) as usize;
}
if *np >= (&__heap_end as *const _) as usize {
return core::ptr::null_mut(); // we are out of memory
}
// TODO: still need to initialize inside of block if not 4096
*lp = *np;
*np = *np + 4096;
}
let curr = *lp;
*lp = *(curr as *const usize);
curr as *mut u8
}
}
An UnsafeCell is an object which can hold a value and return a pointer to it when desired. We are using these here to store the head of a linked list inside our heap. In next, we start by obtaining and dereferencing this pointer to obtain the usize value. If it is the value 0, then we know we don't have any available items on this free list and we need to allocate some. Leaving aside that block, when we have an entry on the free list, we assign it to curr, the current value we will return, and then assign the contents of that memory address to the "head" pointer. This assumes that we have stored the next free pointer (if any) in this location previously, or 0 if there are no more free locations.
Now let's return to the base case, in which there are no entries on the free list. Here, we look at the next_page pointer, which is where we are storing the pages that haven't been used yet. If this is 0, then this is the first call to alloc, and we need to assign the address of __heap_start to the next_page pointer before continuing.
The next check ensures that the value in the next_page pointer is not past the address of __heap_end. If it is, then we have completely run out of heap and cannot allocate the requested memory. Following the example we are basing our code on, we return core::ptr::null_mut() to indicate that we could not perform the allocation, and it would seem that the parent code deals with the rest of the issues.
We have two final steps to complete: first, we need to initialize this block to make sure that it contains all the right values in all the right places (just a comment right now); and then we need to update the current free list to point to the page just allocated, and move the next_page pointer on by 4096 to point to the next page (which must either be the next free page or __heap_end).
For all that complexity, this code does exactly the same thing as our prior code in the sample we are using: it just returns the address of __heap_start. So, unsurprisingly, the code still works.
I have checked this in as RUST_BARE_METAL_PAGE_ALLOCATOR_1.
Completing the Implementation
So up to this point, I have been mainly fiddling in the dark without really knowing what I was doing and mainly just trying to abuse Rust to the point where it let me compile something. But now I have something working, I want to switch gears and complete the implementation in the canonical way - by writing unit tests.So let's write a test, which we will place in its own module and file, tests.rs:
#[cfg(test)]The problem with this is that when I go to run the test, the linker gives me errors. Why? Well, I can't say it's entirely unexpected. We have written code that depends on __heap_start and that is a symbol we bind in during our explicit linking process in linker.ld. The cargo script doesn't know how to find it. However, the error message is as impressive as usual for Rust, and in addition to reporting the entire command line which is passed to ld through cc, it gives these errors and suggestions:
mod tests {
use crate::allocator::PageAllocator;
use core::{cell::UnsafeCell, alloc::GlobalAlloc};
#[test]
fn test_allocate_first_page() {
let pa = simple_allocator();
unsafe {
let addr = pa.alloc(alloc::alloc::Layout::fromsizealign(4096, 16).unwrap()) as usize;
assert_eq!(addr, 4096);
}
}
fn simple_allocator() -> PageAllocator {
return PageAllocator{
next_page: UnsafeCell::new(4096),
free_16: UnsafeCell::new(0),
free_256: UnsafeCell::new(0),
free_4096: UnsafeCell::new(0)
}
}
}
/usr/bin/ld: /home/gareth/Projects/IgnoranceBlog/homerrust/target/debug/deps/homerrust-6186d6a57da04f90.3ti03rv249xsljw4.rcgu.o: in function `homer_rust::allocator::PageAllocator::next':I have checked the current state of the code in as RUST_BARE_METAL_PAGE_ALLOCATOR_TESTS_BROKEN, in large part so I can try different strategies and come back to a known state.
/home/gareth/Projects/IgnoranceBlog/homer_rust/src/allocator.rs:58: undefined reference to `__heap_start'
/usr/bin/ld: /home/gareth/Projects/IgnoranceBlog/homer_rust/src/allocator.rs:60: undefined reference to `__heap_end'
collect2: error: ld returned 1 exit status
= note: some `extern` functions couldn't be found; some native libraries may need to be installed or have their path specified
= note: use the `-l` flag to specify native libraries to link
= note: use the `cargo:rustc-link-lib` directive to specify the native libraries to link with Cargo (see https://doc.rust-lang.org/cargo/reference/build-scripts.html#cargorustc-link-libkindname)
Interestingly, what my research reveals is that the solution to the whole problem is a lot simpler than seems to be indicated by the messages above. What I hadn't realized, but is clearly documented is that the #[cfg(test)] attribute is in fact a directive for conditional compilation comparable to using #ifdef in C. So we can put any code we want inside the #[cfg(test)] and it will be defined there and not in the live application. And, in contrast, we can define a block with #[cfg(not(test))] which will include code that is only defined when compiling not for tests.
So, I can add this directly into tests.rs:
#[no_mangle]And we can add yet one more attribute to the existing definition of the unstable shim variable in allocator.rs:
pub static __heap_start :u32 = 0;
#[no_mangle]
pub static __heap_end :u32 = 0;
#[cfg(not(test))]This stops it being defined more than once in the test scenario.
#[allow(non_upper_case_globals)]
#[no_mangle]
pub static __rust_no_alloc_shim_is_unstable: u8 = 0;
The tests still fail:
$ cargo testThis is not actually that surprising, because we have defined a #[global-allocator] and so the code we are trying to test is being used to allocate memory for the test. This was never going to end well.
Finished test [unoptimized + debuginfo] target(s) in 0.00s
Running unittests src/lib.rs (target/debug/deps/homer_rust-6186d6a57da04f90)
memory allocation of 48 bytes failed
error: test failed, to rerun pass `--lib`
But surely our new "get out of jail free" card can be played here as well:
#[cfg(not(test))]Now it goes a little further, but still no joy:
#[global_allocator]
static HEAP: PageAllocator = PageAllocator {
...
};
$ cargo testSIGSEGV is never good. And it suggests that we have done something wrong with memory and pointers and all that unsafe stuff we've been messing around with. Basically, our code doesn't work. But at least it is compiling and running now.
Compiling homer_rust v0.1.0 (/home/gareth/Projects/IgnoranceBlog/homer_rust)
Finished test [unoptimized + debuginfo] target(s) in 0.21s
Running unittests src/lib.rs (target/debug/deps/homer_rust-6186d6a57da04f90)
running 2 tests
test tests::test_set_4_in_1_from_0 ... ok
error: test failed, to rerun pass `--lib`
Caused by:
process didn't exit successfully: `/home/gareth/Projects/IgnoranceBlog/homer_rust/target/debug/deps/homer_rust-6186d6a57da04f90` (signal: 11, SIGSEGV: invalid memory reference)
Removing all the code from the test case gets the test to pass:
running 2 testsSo at least we have a baseline that compiles and links we can work from. I'm going to put the code back, and then check this in as RUST_BARE_METAL_PAGE_ALLOCATOR_TESTS_SEGV.
test tests::test_set_4_in_1_from_0 ... ok
test allocator::tests::tests::test_allocate_first_page ... ok
I don't know how to attach a debugger to cargo test, and, rather than find out right now, I've decided to fall back on the old tactic of commenting out code until I find the line that fails. It's this one:
*lp = *(curr as *const usize);But it's not obvious to me why. Presumably the variable curr is not correctly defined. Looking through my code, I see that in the test definition of the allocator, I set it to 4096 which is clearly not a valid address. I'd done that without thinking about the fact that I would be wanting to write to that address. So let's instead set it to zero, and then, now that we have __heap_start defined in the test, that should work.
Sadly, it still fails, but at least it's now an assertion failure:
assertion `left == right` failedSo, now that we have reached this point, I think it's time to ask if we are going the way we want to go or not. So, again, I'm going to check in broken code as RUST_BARE_METAL_PAGE_ALLOCATOR_TESTS_FAILING.
left: 94405430325248
right: 4096
I'm not really ready for how complicated this is becoming. But having floundered my way through it, I hope I can explain it in words of one syllable. It occurs to me that what I need to do (in the tests) is to use the standard allocator to allocate a block of (test) heap which I can then treat as if it were the entire heap available to the allocator under test.
So it seems to me that the right thing to do is to extract the section of code that handles initialisation when the initial value of next_page is 0. We can then wrap this up in a closure and pass it to the PageAllocator constructor.
So, in the test, this looks something like this:
let blk = alloc::alloc::alloc(alloc::alloc::Layout::from_size_align(4096, 16).unwrap());The first line here allocates a block of memory on the heap which is exactly the size of a page. The second line converts the pointer to a usize value, and the third defines a closure which returns the start and end of the block.
let start = (blk as *const _) as usize;
let f = || { (start, start+4096) };
Meanwhile, in the non-test case, we can extract the values of __heap_start and __heap_end as defined by the linker in a function:
fn init_from_heap() -> (usize, usize) {We need to update the PageAllocator struct to store this field, as well as a field to hold the end value.
unsafe { ((&__heap_start as *const _) as usize, (&__heap_end as *const _) as usize) }
}
struct PageAllocator {What could possibly go wrong?
next_page: UnsafeCell<usize>,
end: UnsafeCell<usize>,
free_16: UnsafeCell<usize>,
free_256: UnsafeCell<usize>,
free_4096: UnsafeCell<usize>,
init: fn() -> (usize, usize)
}
Well, quite a bit.
First, we have declared init to have a function type, but Rust views a closure as something different because it references (or "captures") the value of start.
error[E0308]: mismatched typesThis now sends us down a chain of corrections. OK, it's a closure, so we need to declare it as such. To declare a closure, you need to use a Rust trait, which, as I understand it, is similar to an interface in Java. But you can't just declare the closure type, as you can with a function, because each closure is different and requires the compiler to generate a different enclosing type (in this case PageAllocator) for each actual closure instance. So, we need to provide the type with a type attribute, and then express the constraint that it is a closure trait.
--> src/allocator/tests.rs:27:23
|
20 | let f = || { (start, start+4096) };
| -- the found closure
...
27 | init: f
| ^ expected fn pointer, found closure
|
= note: expected fn pointer `fn() -> (usize, usize)`
found closure `[closure@src/allocator/tests.rs:20:21: 20:23]`
note: closures can only be coerced to `fn` types if they do not capture any variables
--> src/allocator/tests.rs:20:27
|
20 | let f = || { (start, start+4096) };
| ^^^^^ `start` captured here
struct PageAllocator<F> where F: Fn() -> (usize,usize) {So far, so good. The problem is that we need to add a similar attribute everywhere we use PageAllocator.
...
init: F
}
In the actual initialization of the global_allocator:
static HEAP: PageAllocator<fn()->(usize,usize)> = PageAllocator {In the test initialization:
...
};
fn simple_allocator() -> (usize, PageAllocator<Fn() -> (usize,usize)>) {And then in each of the impl blocks for PageAllocator. Interestingly, in these cases, we need to declare the parameter all over again - it isn't automatically inherited from the struct declaration. I'm sure there are reasons for this, but I don't understand them.
...
}
impl<F> PageAllocator<F> where F: Fn() -> (usize,usize) {OK, now does it work? Well, sadly not. The closure type cannot be used directly in the test initialization because the compiler cannot figure out what size it is. I think what it means is that it cannot figure out how to generate the code for the PageAllocator to store or invoke the closure, because I can't see how it doesn't know it when generating the code to call the constructor.
...
}
unsafe impl<F> Sync for PageAllocator<F> where F: Fn() -> (usize,usize) {}
unsafe impl<F> GlobalAlloc for PageAllocator<F> where F: Fn() -> (usize,usize) {
...
}
error[E0782]: trait objects must include the `dyn` keywordOK, so let's try adding a dyn as shown. This leads to another message:
--> src/allocator/tests.rs:16:52
|
16 | fn simple_allocator() -> (usize, PageAllocator<Fn() -> (usize,usize)>) {
| ^^^^^^^^^^^^^^^^^^^^^
|
help: add `dyn` keyword before this trait
|
16 | fn simple_allocator() -> (usize, PageAllocator<dyn Fn() -> (usize,usize)>) {
| +++
error[E0277]: the size for values of type `(dyn Fn() -> (usize, usize) + 'static)` cannot be known at compilation timeAll of these suggestions can be followed, and I did try a couple of them, but the Box seemed the simplest to get working:
--> src/allocator/tests.rs:16:30
|
16 | fn simple_allocator() -> (usize, PageAllocator<dyn Fn() -> (usize,usize)>) {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ doesn't have a size known at compile-time
|
= help: the trait `Sized` is not implemented for `(dyn Fn() -> (usize, usize) + 'static)`
note: required by a bound in `PageAllocator`
--> src/allocator.rs:7:22
|
7 | struct PageAllocator<F> where F: Fn() -> (usize,usize) {
| ^ required by this bound in `PageAllocator`
help: you could relax the implicit `Sized` bound on `F` if it were used through indirection like `&F` or `Box<F>`
--> src/allocator.rs:7:22
|
7 | struct PageAllocator<F> where F: Fn() -> (usize,usize) {
| ^ this could be changed to `F: ?Sized`...
...
13 | init: F
| - ...if indirection were used here: `Box<F>`
fn simple_allocator() -> (usize, PageAllocator<Box<dyn Fn() -> (usize,usize)>>) {So, now it works, right? Almost, but not quite.
unsafe {
...
let f = || { (start, start+4096) };
(start, PageAllocator{
...
init: Box::new(f)
})
}
}
Quite understandably, the compiler thinks that start will go out of scope before it is used in the closure:
error[E0373]: closure may outlive the current function, but it borrows `start`, which is owned by the current functionBut at least the suggested solution is quite simple: add the move keyword to the definition of the closure.
--> src/allocator/tests.rs:20:21
|
20 | let f = || { (start, start+4096) };
| ^^ ----- `start` is borrowed here
| |
| may outlive borrowed value `start`
|
note: closure is returned here
--> src/allocator/tests.rs:21:13
|
21 | / (start, PageAllocator{
22 | | next_page: UnsafeCell::new(0),
23 | | end: UnsafeCell::new(0),
24 | | free_16: UnsafeCell::new(0),
... |
27 | | init: Box::new(f)
28 | | })
| |_______^
help: to force the closure to take ownership of `start` (and any other referenced variables), use the `move` keyword
|
20 | let f = move || { (start, start+4096) };
| ++++
And, yes, now everything works. And the test passes while the code keeps on running.
That's all checked in as RUST_BASE_METAL_PAGE_ALLOCATOR_FIRST_TEST. Before checking it in, I did a couple of quick refactorings to put all the non-test code in its own module, all neatly wrapped up in a single #[not(cfg(test))].
Tidying up
OK, I think everything from here on is straightforward TDD of a fairly normal piece of code - the fact that it will be used as a memory allocator can be safely ignored. Some refactoring happened as well, and I've replaced all the static memory allocation with dynamic allocation. I don't think any interesting issues came up.The final version is checked in as RUST_BARE_METAL_PAGE_ALLOCATOR_COMPLETE.
