[rCore学习笔记 029] 动态内存分配器实现-以buddy_system_allocator源码为例

在上一部分,我们讲了动态内存分配器的原理是维护一个堆,而且是实现各种连续内存分配方法.
但是上一部分是直接通过引用了buddy_system_allocator来解决的问题.
那么对于内存分配算法有兴趣的我,还是决定看一下源码,总之人是咸鱼但是还是需要有梦想.
人生这么不顺,若是连梦想都没有了,可能当即就找不到活着的意义了吧.
获取buddy_system_allocator的源码

buddy_system_allocator也是rCore这个社区的项目.

1. cd ~/workspace
2. git clone https://github.com/rcore-os/buddy_system_allocator.git

复制代码

从实用的角度开始看源码

为了起一个好头,还是从比较熟悉的部分看代码,思考代码是怎么组织的:

• buddy_system_allocator是怎么作为一个外部包被引用的?
  
• 上一部分我们调用了LockedHeap,那么这个类是怎么实现的,它依赖于什么?
  

LockedHeap

我们在源码中搜索LockedHeap,我们可以在lib.rs里找到它的实现.

1. pub struct LockedHeap<const ORDER: usize>(Mutex<Heap<ORDER>>);

复制代码

在看到这个定义的时候有一种似懂非懂的感觉,只能猜到LockedHeap是一个加了线程锁的大小为ORDER的Heap:

• 因为ORDER放在了中间,应该是和泛型有关系,但是这里又明确标注了usize说明ORDER是一个变量.
  
• 因为在结构体的实现中出现了()有点不知所云
  

元组结构体

查看Rust圣经,发现确实存在这种字段可以没名称的结构体.
这里又产生了一个新的疑问,如果字段可以没名称,那么怎么去访问结构体内容呢?
查阅Rust语言官方参考手册,可以看到:

Tuple structs are similar to regular structs, but its fields have no names. They are used like tuples, with deconstruction possible via let TupleStruct(x, y) = foo; syntax. For accessing individual variables, the same syntax is used as with regular tuples, namely foo.0, foo.1, etc, starting at zero.

通过数字来访问这些结构体内容.

1. // 假如存在TupleStruct这个结构体
3. let foo = TupleStruct(1,2);
5. // 可以通过这种方法来进行析构
7. let TupleStruct(x, y) = foo;
9. // 可以用数字访问
10. let x = foo.0;
11. let y = foo.1;

复制代码

值泛型

那么这里就需要查看参考书目-值泛型的内容尤其是它的示例.
最终得到结论:Rust是允许使用值的泛型的,这代表LockedHeap有一个和值相关的泛型参数.

在某些时候是很像C里边的#define ORDER 0x30000的.
但是事实上在Rust里是灵活了非常多的.

这和LockedHeap提供的两种获取示例的方法是相对应的:

1. impl<const ORDER: usize> LockedHeap<ORDER> {
2.     /// Creates an empty heap
3.     pub const fn new() -> Self {
4.         LockedHeap(Mutex::new(Heap::<ORDER>::new()))
5.     }
7.     /// Creates an empty heap
8.     pub const fn empty() -> Self {
9.         LockedHeap(Mutex::new(Heap::<ORDER>::new()))
10.     }
11. }

复制代码

单看这里还看不出来,因为还套了一层Heap,要看Heap的获取实例的方法.
加互斥锁

理解了上边的语法,只需要理解GlobalAlloc这个trait对于LockedHeap的实现:

1. #[cfg(feature = "use_spin")]
2. unsafe impl<const ORDER: usize> GlobalAlloc for LockedHeap<ORDER> {
3.     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
4.         self.0
5.             .lock()
6.             .alloc(layout)
7.             .ok()
8.             .map_or(core::ptr::null_mut(), |allocation| allocation.as_ptr())
9.     }
11.     unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
12.         self.0.lock().dealloc(NonNull::new_unchecked(ptr), layout)
13.     }
14. }

复制代码

实际上就是在Heap外边加了一个Mutex互斥锁,那么对于alloc和dealloc的实现,只需要经过互斥锁访问里边的Heap,然后访问Heap的alloc和dealloc方法.
Heap

定义

Heap实际上由一个长度为ORDER的list和user,allocated和total几个值组成.

1. pub struct Heap<const ORDER: usize> {
2.     // buddy system with max order of `ORDER - 1`
3.     free_list: [linked_list::LinkedList; ORDER],
5.     // statistics
6.     user: usize,
7.     allocated: usize,
8.     total: usize,
9. }

复制代码

那么ORDER实际上就是const 值泛型了.

为什么在代码里不需要指定ORDER的值?
因为我们设置的包的版本为0.6,这个版本的包没用加入泛型参数,而是固定链表长度为32.

获取实例

查看Heap的new和empty方法:

1. impl<const ORDER: usize> Heap<ORDER> {
2.     /// Create an empty heap
3.     pub const fn new() -> Self {
4.         Heap {
5.             free_list: [linked_list::LinkedList::new(); ORDER],
6.             user: 0,
7.             allocated: 0,
8.             total: 0,
9.         }
10.     }
12.     /// Create an empty heap
13.     pub const fn empty() -> Self {
14.         Self::new()
15.     }
16. }

复制代码

这里注意list是一个LinkedList类型,是一个链表.
设置堆范围

记得上一篇博客内容,我们是使用如下代码初始化的:

1. /// Initialize heap allocator
2. pub fn init_heap() {
3.     unsafe {
4.         HEAP_ALLOCATOR
5.             .lock()
6.             .init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
7.     }
8. }

复制代码

这里且不说HEAP_ALLOCATOR.lock()是怎么获取到Heap实例的.这里这句init确实是调用的Heap的init.
接下来我们看它的实现.
[code]impl Heap {        ... ...    /// Add a range of memory [start, end) to the heap    pub unsafe fn add_to_heap(&mut self, mut start: usize, mut end: usize) {        // avoid unaligned access on some platforms        start = (start + size_of:) - 1) & (!size_of:) + 1);        end &= !size_of:) + 1;        assert!(start