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，且必定整除。

Memory Layout After Initialization

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) 釋放記憶體