Location>code7788 >text

[rCore Study Notes 028] Dynamic Memory Allocation in Rust

Popularity：695 ℃/2024-10-01 13:48:15

introductory

Thinking back to when we were learning C, we always mentioned thatmallocAlways mention that the use ofmallocThe memory applied on-site is part of theheap up, while the memory of directly defined variables belongs to thea wooden or bamboo pen for sheep or cattle.

Remember when you were learning STM32 and CubeIDE had to set up thestack cap (a poem)heapSize.

But let's remember, a feature that works so well, is actuallyThe operating system is carrying the weight..

Then in order to realize the dynamic memory allocation function, the operating system needs to have the following functions.

  • Initially, a large memory space is provided as the initial "heap". In the absence of paging, this space is physical memory, otherwise it is virtual memory.
  • Provides interfaces to functions that allocate and free memory on the heap. This allows function callers to get free blocks of memory with contiguous addresses for reading and writing through the allocate memory function interface, and to reclaim memory for subsequent memory allocation requests through the free memory function interface.
  • A sequential memory allocation algorithm that provides free space management. The associated algorithm dynamically maintains a series of free and allocated memory blocks to efficiently manage free blocks.
  • (Optional) Provides data structures and operations built on the heap. With the above basic memory allocation and freeing

Dynamic Memory Allocation

Implementation methodology

Implementation of dynamic memory allocation:

The application places a separate memory space - the heap - whose size can be dynamically increased or decreased as the application runs. At the same time, the application has to be able to manage the heap, i.e., it has to allocate a block of space for variables at runtime, and at the end of the variable's life cycle, this block of space needs to be reclaimed for later use. If the size of the heap is fixed, then this is really a sequential memory allocation problem, and the students can use theVarious sequential memory allocation algorithms。

memory fragmentation

Disadvantages of Dynamic Memory Allocation - Memory Fragmentation:

After an application performs multiple memory allocation and release operations of different sizes, there is a waste of memory space, i.e., there are free memory fragments that cannot be used by the application.

Memory fragmentation is free memory space that cannot be allocated and used. It can be further subdivided into internal and external fragmentation:

  • Internal fragmentation: Areas of memory that have been allocated (belonging to a running application) that are not used by the occupying application and cannot be utilized by the operating system.
  • External fragmentation: a free area of memory that has not yet been allocated (and does not belong to any running application) and is too small to be allocated to the application making the request for memory space.

Dynamic Memory Allocation in STD Libraries

here areFirstly, reference was made to the fact that inSTDThe heap-related data structures in the library. You can read and understand the diagram below.

But the message this section sends to us is.

  1. dynamic memory management can be elegantly implemented in rust programming.
  2. The std library provides methods for dynamic memory management
  3. However, our operating system kernel can only be implemented using the rust core library, so we need to emphasize and borrow methods from these std libraries.

Support for dynamic memory allocation in the kernel

As stated in the previous section.

All of the above heap-related smart pointers or containers can be found in Rust's ownalloc crate. When we use the Rust standard librarystd You don't need to worry about this crate because the standard library already implements a heap management algorithm and puts thealloc The content of thestd under the namespace for developers to use directly. However, the operating system kernel runs with the standard libraries disabled (i.e., theno_std ) on a bare-metal platform, the core librarycore There is also no dynamic memory allocation, so this is the time to consider utilizing thealloc library-defined interface to the basic dynamic memory allocator.

Specifically implementing thisDynamic Memory Allocator, is to realize for himself thisconstructor, RealizationGlobalAlloc(used form a nominal expression)Trait.

alloc library requires that we provide it with aGlobal dynamic memory allocator , it will utilize this allocator to manage heap space so that smart pointers or container data structures associated with the heap will work properly. Specifically, our dynamic memory allocator will need to implement theGlobalAlloc Trait

GlobalAllocabstract interfaces.

// alloc::alloc::GlobalAlloc

pub unsafe fn alloc(&self, layout: Layout) -> *mut u8;
pub unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

As you can see, they are similar to the Cmalloc/free , which represent the allocation and reclamation of heap space, respectively, and also similarly use a bare pointer (that is, an address) as the return value for allocation and as an argument for reclamation. Both interfaces have aalloc::alloc::Layout parameter, which indicates the allocation requirements, is divided into two parts, namely the amount of space requiredsize and the alignment requirements for the return addressalign This alignment requirement must be a power of 2 in bytes. This alignment requires that it must be a power of 2, in bytes, and restricts the address returned to thealign Multiples of.

Specific Programming Implementation

Introducing an existing memory allocator library

existos/Introduced in.

buddy_system_allocator = "0.6"

pull intoallocstorehouse

existos/src/Introduced in .

// os/src/

extern crate alloc;

Instantiating a Global Dynamic Memory Allocator

establishos/src/mm/heap_allocator.rs.

// os/src/mm/heap_allocator.rs

use buddy_system_allocator::LockedHeap;
use crate::config::KERNEL_HEAP_SIZE;

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

static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];

pub fn init_heap() {
    unsafe {
        HEAP_ALLOCATOR
            .lock()
            .init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
    }
}

can be seeninstantiatedhas a static variableHEAP_ALLOCATOR. . and .instantiatedhas an array ofHEAP_SPACEto serve as itsheap up.

Among them.HEAP_SPACEThe size of theKERNEL_HEAP_SIZE.

So this.KERNEL_HEAP_SIZEis taken fromconfigThis bag's.

This is based onCode in the code repositoryto set upKERNEL_HEAP_SIZESize.

// os/src/
pub const KERNEL_HEAP_SIZE: usize = 0x30_0000;

size3145728.

Semantic items for labeling global dynamic memory allocators

Note the code in the previous paragraph, labeled#[global_allocator]so that the memory allocator here can be recognized as a global dynamic memory allocator.

#[global_allocator]

Handling Dynamic Memory Allocation Failures

needEnable conditional compilation, so it needs to be inLilly declared.

#![feature(alloc_error_handler)]

This is when theos/src/mm/heap_allocator.rsThe handler has been created in.

// os/src/mm/heap_allocator.rs

#[alloc_error_handler]
pub fn handle_alloc_error(layout: core::alloc::Layout) -> ! {
    panic!("Heap allocation error, layout = {:?}", layout);
}

Test the realization of the effect

Creating Test Functions

existos/src/mm/heap_allocator.rsCreate a test function in the

#[allow(unused)]
pub fn heap_test() {
    use alloc::boxed::Box;
    use alloc::vec::Vec;
    extern "C" {
        fn sbss();
        fn ebss();
    }
    let bss_range = sbss as usize..ebss as usize;
    let a = Box::new(5);
    assert_eq!(*a, 5);
    assert!(bss_range.contains(&(a.as_ref() as *const _ as usize)));
    drop(a);
    let mut v: Vec<usize> = Vec::new();
    for i in 0..500 {
        (i);
    }
    for i in 0..500 {
        assert_eq!(v[i], i);
    }
    assert!(bss_range.contains(&(v.as_ptr() as usize)));
    drop(v);
    println!("heap_test passed!");
}

Here.#[allow(unused)]It's fun. It's okay.Prevents the compiler from reporting errors on functions you are not calling because of debugging..

Note here the use of theprintln, add a sentence at the top of the documentuse crate::println.

The test program here first gets thesbssin order toebssScope of the Convention ....

Review the clearing herebssCode for paragraph.

  1. bssThe segment itself is an area of memory that stores uninitialized global variables
  2. sbssbebssbeginning of sth.ebssbebssending

in that casebss_rangeactuallybssScope of the Convention ....

according tohere are, UnderstandingBox::new(5)is trying to store on the heapaand this value is the value of5.

Then the following assertion statement.

assert_eq!(*a, 5);
assert!(bss_range.contains(&(a.as_ref() as *const _ as usize)));

It's easy to understand.

  1. judgementsaIs the value of5
  2. judgementsaIs the pointer to thebsswithin the scope of

The subsequent operation then creates aVeccontainer, which then stores the0..500values, and perform the above mentioned tests of theaThe assertion of the judgment of .

If the assertion doesn't report an error, then it will naturally end up sayingheap_test passed!.

(Final notedropis to free a variable in the heap (dynamic memory))

Make the mm package callable

existos/src/mmCreatefeasiblemmcan be recognized as a package.

In order to useheap_allocatorinnerinit_heapcap (a poem)heap_testIt needs to be publicly stated that thismod:

// os/src/mm/
pub mod heap_allocator;

compilermainFunctions, implementation tests

// os/src/

/// the rust entry-point of os
#[no_mangle]
pub fn rust_main() -> ! {
    clear_bss();
    println!("[kernel] Hello, world!");
    logging::init();
    println!("[kernel] logging init end");
    mm::heap_allocator::init_heap();
    println!("[kernel] heap init end");
    mm::heap_allocator::heap_test();
    println!("heap test passed");
    trap::init();
    println!("[kernel] trap init end");
    loader::load_apps();
    trap::enable_timer_interrupt();
    timer::set_next_trigger();
    task::run_first_task();
    panic!("Unreachable in rust_main!");
}

operational test

cd os
make run

Getting results.

[rustsbi] RustSBI version 0.3.1, adapting to RISC-V SBI v1.0.0
.______       __    __      _______.___________.  _______..______   __
|   _  \     |  |  |  |    /       |           | /       ||   _  \ |  |
|  |_)  |    |  |  |  |   |   (----`---|  |----`|   (----`|  |_)  ||  |
|      /     |  |  |  |    \   \       |  |      \   \    |   _  < |  |
|  |\  \----.|  `--'  |.----)   |      |  |  .----)   |   |  |_)  ||  |
| _| `._____| \______/ |_______/       |__|  |_______/    |______/ |__|
[rustsbi] Implementation     : RustSBI-QEMU Version 0.2.0-alpha.2
[rustsbi] Platform Name      : riscv-virtio,qemu
[rustsbi] Platform SMP       : 1
[rustsbi] Platform Memory    : 0x80000000..0x88000000
[rustsbi] Boot HART          : 0
[rustsbi] Device Tree Region : 0x87000000..0x87000f02
[rustsbi] Firmware Address   : 0x80000000
[rustsbi] Supervisor Address : 0x80200000
[rustsbi] pmp01: 0x00000000..0x80000000 (-wr)
[rustsbi] pmp02: 0x80000000..0x80200000 (---)
[rustsbi] pmp03: 0x80200000..0x88000000 (xwr)
[rustsbi] pmp04: 0x88000000..0x00000000 (-wr)
[kernel] Hello, world!
heap_test passed!
[kernel] IllegalInstruction in application, kernel killed it.
All applications completed!

For the sake of keeping the log short, I'm going to put in theuserThe only apps that need to be compiled are the ones in theuser/src/bin/00hello_world.rs.

Look at the log, here.heap_test passed!, indicating that the test was successful.

<Previous Next>