How to implement a single linked list in os/bare metal?

help
1

TLDR; May read the example first.
Condition: no_std, no heap
I want to implement a linked list in my kernel to maintain the raw memory, which ranges from 0x80020000 to 0x88000000. More specifically, when booting, the kernel first spilts the raw memory into a bunch of fix-sized(4KB) frames and then use a linked list to record the frames.
The kernel use this list to alloc and dealloc the frames and it only records the free frames, i.e., the linked list is a free list. Since the number of frames is large, I would like to reuse the memory of the free frames.

C code illustration:

struct frame {
    struct frame *next;
}
static struct frame *freelist;
void *alloc() {/* pop a frame in the head of the freelist */}
void free(void *) {/* push the frame in the head of the freelist */}

In terms of Rust code, I first intend to use:

struct Frame {
    next: Option<&mut Frame>
}

but then with this struct, I don't know how to somehow generate a new ownership of Frame from raw pointers. So I use this:

struct Frame {
    next: Option<*mut Frame>
}
impl Frame {
    fn from(addr: usize) -> *mut Frame {
        let frame_ptr = addr as *mut Frame;
        unsafe { frame_ptr.write(Frame { next: None }); }
        frame_ptr
    }

    fn set(&mut self, value: Option<*mut Frame>) {
        self.next = value;
    }

    fn take_next(&mut self) -> Option<*mut Frame> {
        self.next.take()
    }
}

What the kernel does here is it uses Frame::new to convert from usize(like 0x80020000, 0x80021000, 0x80022000, ...) to *mut Frame and push it into the freelist.
But with this implementation, something weird happens when the kernel is initializing the free list. Aftering some debugging, I find that the kernel can just push a little frame into the freelist successfully. I don't know what happens exactly here, but it seems that something weird happens on variable with type *mut Frame in the free function.

/* simplified, originally wrapped in mutex in my kernel */
static mut free_list: Frame = Frame{ next: None };

pub fn free(addr: usize) {
    let frame: *mut Frame = Frame::from(addr);
    unsafe {
        let next = free_list.take_next();
        (*frame).set(next);
        free_list.set(Some(frame));
    }
}
2

If you haven't already, I'd highly recommend reading Learn Rust With Entirely Too Many Linked Lists.

While you say you aren't using the heap, the way your kernel has split memory sounds a lot like what an allocator would do internally. You may want to check out the Heap Allocation chapter from Philipp Oppermann's excellent Writing an OS in Rust series.

You may also want to google something like "intrusive linked lists in Rust". Safe Intrusive Collections with Pinning by @RalfJung and the intrusive_collections crate may also be useful resources.

It doesn't directly answer your question about why your free() function isn't working correctly, but those links might give you a better high-level understanding of what you're trying to do.

5 Likes
3

Thanks your recommendation, I am currently struggling with some of these solutions to find my solutions. :rofl: :rofl:

4

If you don't mind you may also check my simple and lightweight allocator implementation for a RaspberryPi bare-metal OS. This also uses a single linked list to refer the diffferent allocated and free memory buckets... Checkout here: ruspiro-allocator
This might give further ideas to help you getting to your solution :wink:

3 Likes
5

Here is a prototype of how you'd be doing it:

#![feature(untagged_unions)]

mod lib {    
    use ::core::{
        cell::Cell,
        mem,
        ptr,
    };
    
    const START: usize = 0x80_02_00_00;
    const END: usize = 0x88_00_00_00;

    pub
    const FRAME_SIZE: usize = 0x10_00; // 4KB
    
    pub
    const FRAME_COUNT: usize = (END - START) / FRAME_SIZE;
    type FrameChunk = [Cell<u8>; FRAME_SIZE];
    
    #[repr(C)]
    struct FrameNode {
        next: Cell<Option<ptr::NonNull<FrameNode>>>,
    }
    
    #[repr(C)]
    union Frame {
        node: FrameNode,
        chunk: FrameChunk,
    }
    
    /// Safety: can only be called once
    unsafe
    fn initial_free_list () -> FrameNode
    {
        let frames_array: &'static [Frame; FRAME_COUNT] =
            &*(START as *const _)
        ;
        frames_array
            .windows(2)
            .for_each(|window| {
                window[0]
                    .node
                    .next
                    .set(Some(ptr::NonNull::from(
                        &window[1].node
                    )))
                ;
            })
        ;
        FrameNode {
            next: Cell::new(Some(ptr::NonNull::from(
                &frames_array[0].node
            ))),
        }
    }
    
    pub
    struct Kernel {
        free_list: FrameNode,
    }
    
    impl Kernel {
        /// Safety: can only be called once
        pub
        unsafe
        fn new () -> Self
        {
            Self {
                free_list: initial_free_list(),
            }
        }
        
        pub
        fn alloc (self: &'_ Kernel)
          -> Option<KernelChunk<'_>>
        {
            unsafe {
                let first: &FrameNode = &*
                    self.free_list
                        .next
                        .replace(None)?
                        .as_ptr()
                ;
                self.free_list
                    .next
                    .set(first.next.replace(None))
                ;
                let frame_chunk: *mut [u8; FRAME_SIZE] =
                    first as *const _ as _
                ;
                frame_chunk
                    .write([0; FRAME_SIZE])
                ;
                Some(KernelChunk(&mut *frame_chunk))
            }
        }
        
        pub
        fn free (
            self: &'_ Kernel,
            chunk: KernelChunk<'_>,
        )
        {
            unsafe {
                let frame: &'_ Frame = mem::transmute(chunk);
                frame.node.next.set(
                    self.free_list
                        .next
                        .replace(None)
                );
                self.free_list
                    .next
                    .set(Some(ptr::NonNull::from(
                        &frame.node
                    )))
                ;
            }
        }
    }
    
    #[repr(transparent)]
    pub
    struct KernelChunk<'kernel> /* = */ (
        &'kernel mut [u8; FRAME_SIZE],
    );
    
    impl ::core::ops::Deref for KernelChunk<'_> {
        type Target = [u8; FRAME_SIZE];
        
        #[inline]
        fn deref (self: &'_ Self)
          -> &'_ [u8; FRAME_SIZE]
        {
            self.0
        }
    }
    
    impl ::core::ops::DerefMut for KernelChunk<'_> {
        #[inline]
        fn deref_mut (self: &'_ mut Self)
          -> &'_ mut [u8; FRAME_SIZE]
        {
            self.0
        }
    }
}
use lib::*;

fn main ()
{
    let kernel = unsafe { Kernel::new() };
    for _ in 0 .. 10 {
        let mut chunks = vec![];
        while let Some(chunk) = kernel.alloc() {
            chunks.push(chunk);
        }
        assert_eq!(
            dbg!(FRAME_COUNT),
            dbg!(chunks.len()),
        );
        assert_eq!(
            ::core::mem::replace(
                &mut chunks[0][42],
                ::rand::random(),
            ),
            0,
        );
        for chunk in chunks {
            kernel.free(chunk);
        }
    }
}

Doing something so low-level is very easy to mess up; it's already hard to do right in C, but it is actually worse in Rust! Indeed, you'll be tempted to use &mut references instead of all that Cell verbiage, and that very easily leads to unsound code, given the uniqueness (no aliasing) invariant of &mut references, and how such invariant does not play well with the linked lists pattern (c.f., the .windows(2) initialization of the list; that pattern cannot be using &muts since the window[0] frame is aliased by the window[0].next of the previous iteration).

4 Likes
6

Thanks for your allocator, I will take a look.

7

Thanks your detailed reply, I will try it out.

1 Like
8

May I ask you a question?
We explicitly use 'kernel here to constrain that these two references have same lifetime, so that we can to some extent verify that this chunk is previously allocated by the kernel.
Is my understanding correct?

mod lib {    
    /* omitted */
    impl Kernel {
        /* omitted */
        pub
        fn free<'kernel> (
            self: &'kernel Kernel,
            chunk: KernelChunk<'kernel>,
        )
        {
            /* omitted */
        }
    }
}
9

That was my intent, yes, but it's actually counter-productive in that it is actually not the case and thus gives a false sense of security. That's why I edited and removed those lifetime annotations in the post here (but forgot to update the playground).

Why is it not the case? Well, Rust happily shrinks a &'long [mut] reference into a &'short [mut] one, and also recursively so (it can shrink a KernelChunk<'long> into a KernelChunk<'short>; the fancy / savy way of saying this is "KernelChunk is covariant w.r.t its lifetime parameter")

So if we had:

// this is the `free` from your example
fn free_strict<'common> (
    this: &'common Kernel,
    chunk: KernelChunk<'common>,
)
// and a
fn free_apparently_loose<'kernel, 'chunk> (
    this: &'kernel Kernel,
    chunk: KernelChunk<'chunk>,
)
// (<=> `free_apparently_loose(this: &'_ Kernel, chunk: KernelChunk<'_>`)

then it turns out it is legal for free_apparently_loose to call free_strict:

fn free_apparently_loose<'kernel, 'chunk> (
    this: &'kernel Kernel,
    chunk: KernelChunk<'chunk>,
)
{
    // Rust will use `'common = intersection('kernel, 'chunk)`
    free_strict(this, chunk)
}
10

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.