Buddy System
Data Structure
新增 Buddy 的 data structure，並在 page 的 structure 中新增 linked list，這邊的設計參考 linux 的 list_head
include/mm.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #define MAX_BUDDY_ORDER 9 // 2^0 ~ 2^8 => 4k to 1MB
enum booking_status {
AVAL,
USED,
};
struct buddy_t {
uint32_t nr_free;
struct list_head head;
};
struct page_t {
enum booking_status used;
int order;
struct list_head list;
};
|
src/mm.c
1
2
| struct buddy_t free_area[MAX_BUDDY_ORDER];
struct page_t page[PAGE_FRAMES_NUM];
|
Initialization
用 linked list 維護 buddy 的 order，一開始僅有最高的 order 有超過一個 element，其餘 order 最多只會有一個 element，且必定整除。
src/mm.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| void buddy_init() {
for (int i = 0; i < MAX_BUDDY_ORDER; i++) {
free_area[i].head.next = &free_area[i].head;
free_area[i].head.prev = &free_area[i].head;
free_area[i].nr_free = 0;
}
}
void mm_init() {
buddy_init();
extern uint8_t __kernel_end; // defined in linker
uint8_t* kernel_end = &__kernel_end;
int kernel_end_page = (uint64_t)kernel_end / PAGE_SIZE;
int mmio_base_page = MMIO_PHYSICAL / PAGE_SIZE;
int i = 0;
for (; i <= kernel_end_page; i++) {
page[i].used = USED;
}
int order = MAX_BUDDY_ORDER - 1;
int counter = 0;
for (; i < mmio_base_page; i++) {
// init page counter times
if (counter) {
remain_page++;
page[i].idx = i;
page[i].used = AVAL;
page[i].order = -1;
list_head_init(&(page[i].list));
counter--;
}
// page i can fill current order
else if (i + (1 << order) - 1 < mmio_base_page) {
remain_page++;
page[i].idx = i;
page[i].used = AVAL;
page[i].order = order;
buddy_push(&(free_area[order]), &(page[i].list));
counter = (1 << order) - 1;
}
// reduce order, try again
else {
order--;
i--;
}
}
for (; i < PAGE_FRAMES_NUM; i++) {
page[i].used = USED;
}
first_aval_page = kernel_end_page + 1;
last_aval_page = mmio_base_page - 1;
}
void buddy_push(struct buddy_t* bd, struct list_head* elmt) {
bd->nr_free++;
list_add_tail(elmt, &bd->head);
}
void buddy_remove(struct buddy_t* bd, struct list_head* elmt) {
bd->nr_free--;
list_del(elmt);
}
|
Allocator
src/mm.c
從參數傳進來的 order 開始搜尋是否有可用的 block，將其從 buddy pop 出來，回傳第一個 page 的 virtual address
1
2
3
4
5
6
7
8
9
10
11
| void* buddy_alloc(int order) {
for (int i = order; i < MAX_BUDDY_ORDER; i++) {
if (free_area[i].nr_free > 0) {
struct page_t* p = buddy_pop(&free_area[i], order);
uint64_t page_virt_addr = (p->idx * PAGE_SIZE) | KERNEL_VIRT_BASE;
memzero((void*)page_virt_addr, (1 << order) * PAGE_SIZE);
return (void*)page_virt_addr;
}
}
return NULL;
}
|
從可用的 buddy 中取出一個 block，這個 buddy 的 order 可能超過目標的 order，所以將其遞迴的拆分到目標的 order，以避免浪費
1
2
3
4
5
6
7
8
| struct page_t* buddy_pop(struct buddy_t* bd, int target_order) {
if (list_empty(&(bd->head))) return NULL;
bd->nr_free--;
struct list_head* target = bd->head.next;
list_del(target);
struct page_t* target_page = list_entry(target, struct page_t, list);
return buddy_release_redundant(target_page, target_order);
}
|
若尚未到達目標的 order，就將當前 order 拆成兩半，push bottom 到下一個 order，將 top 繼續遞迴，維護時僅需要將 buddy 中的第一個 page 做標記即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| struct page_t* buddy_release_redundant(struct page_t* p, int target_order) {
uart_printf("release order: %d targer: %d\n", p->order, target_order);
int cur_order = p->order;
// recursive release if not reach to target_order
if (cur_order > target_order) {
int prev_order = cur_order - 1;
struct page_t* bottom = p;
struct page_t* top = p + (1 << prev_order);
bottom->order = prev_order;
top->order = prev_order;
buddy_push(&(free_area[prev_order]), &(bottom->list));
return buddy_release_redundant(top, target_order);
}
// book keeping
p->used = USED;
return p;
}
|
Coalesce the free block
在 free 時，若有兩個同 order 的 buddy 可以合併就將其合併到上一個 order
src/mm.c
由 pfn 與 order 可以取得自己這個 page 的 buddy
The page frame number(PFN) and the block size order can be used to find the page frame’s buddy. For example, if a memory block’s PFN is 8 and the block size is 16KB (order = 2) you can find its buddy by 0b1000 xor 0b100 = 0b1100 = 12.
1
2
3
4
| struct page_t* find_buddy(int pfn, int order) {
int buddy_pfn = pfn ^ (1 << order);
return &page[buddy_pfn];
}
|
若 buddy 正在使用或是 buddy 的 order 與自己不同就不進行 merge，merge 時依照 bottom, top 的順序傳入 buddy_merge，維護時 free 也僅需要維護 buddy 最開頭的 page
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void buddy_free(void* virt_addr) {
int pfn = phy_to_pfn(virtual_to_physical((uint64_t)virt_addr));
struct page_t *p = &page[pfn];
int order = p->order;
struct page_t *buddy = find_buddy(pfn, order);
// can not merge, just free current order's pages
if (buddy->used == USED || buddy->order != order) {
uart_printf("free but no merge\n");
p->used = AVAL;
buddy_push(&(free_area[order]), &(p->list));
}
// merge buddy iteratively
else {
buddy_remove(&free_area[order], &buddy->list);
if (buddy > p)
buddy_merge(p, buddy, order);
else
buddy_merge(buddy, p, order);
}
}
|
若 bottom 的 buddy 又符合 merge 的條件，就繼續遞迴的 merge 下去，直到 coalesce 成一塊更大的 buddy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void buddy_merge(struct page_t *bottom, struct page_t *top, int order) {
uart_printf("merge buddy from order %d to %d (%d %d)\n", order, order+1, bottom->idx, top->idx);
int new_order = order + 1;
struct page_t *buddy = find_buddy(bottom->idx, new_order);
// check buddy exist in new order, if exist => recursively merge
if (buddy->used == AVAL && buddy->order == new_order) {
buddy_remove(&free_area[new_order], &buddy->list);
if (buddy > bottom)
buddy_merge(bottom, buddy, new_order);
else
buddy_merge(buddy, bottom, new_order);
}
// merge bottom and top to same block
else {
bottom->used = AVAL;
bottom->order = new_order;
top->order = -1;
buddy_push(&(free_area[new_order]), &(bottom->list));
}
}
|
Usage
在之前使用 page_alloc 要一塊 page 空間的函式，現在可以使用 buddy_alloc(0) 取代，並改用 buddy_free(addr) 釋放記憶體