# 2019q1 Homework7 (buddy)
contributed by < `tony2037` >
# F13: buddy
* https://hackmd.io/@sysprog/SyPmY90jV?type=view
## 測驗解析
### 第一題
#### `static void flip_parent_is_split`
```clike=
static void flip_parent_is_split(size_t index) {
index = (index - 1) / 2;
A1
}
```
* 先看看 binary tree
* - Move to parent: index = (index - 1) / 2;
* - Move to left child: index = index * 2 + 1;
* - Move to right child: index = index * 2 + 2;
* - Move to sibling: index = ((index - 1) ^ 1) + 1;
* 所以 index 目前移動到 parent node
* 答案是 `(a) node_is_split[index / 8] ^= 1 << (index % 8);`
* `node_is_split`
* $\because$ 只需要 1 個 bit 來 store state (split or not)
* $\therefore$ `static uint8_t node_is_split[(1 << (BUCKET_COUNT - 1)) / 8];`
### 第二題
#### `static size_t bucket_for_request(size_t request)`
```clike=
static size_t bucket_for_request(size_t request) {
size_t bucket = BUCKET_COUNT - 1;
size_t size = MIN_ALLOC;
while (size < request) {
A2
}
return bucket;
}
```
* 呼叫 malloc() 之後要找到對應的 size (最小且大於 request) 並且要把 allocated area 加入 doubly-linked list
* 答案是 `(c) bucket--; size *= 2;`
* bucket 從最大開始遞減
* 每次 size 不夠大, 就 times 2, 直到 size > request(包括 header 大小)
### 第三題
#### `static bool lower_bucket_limit(size_t bucket)`
```clike=
static bool lower_bucket_limit(size_t bucket) {
...
uint8_t *right_child = ptr_for_node(root + 1, bucket_limit);
if (!update_max_ptr(right_child + sizeof(list_t)))
return false;
list_push(&buckets[bucket_limit], (list_t *) right_child);
A3
...
}
```
* 當 **bucket_limit** 比 **bucket** 大的時候, 此函式 `double the size` & `makes bucket_limit lower by 1`
* 題目中做的事情是: 在確認過 **parent point slips** 後, 把 **right chlid** 加入 free list, 並且 `initialize &buckets[--bucket_limit]` 因為已經 split 出去了
* 答案是 `(b) list_init(&buckets[--bucket_limit]);`
### 第四題
#### `void *malloc(size_t request)`
```clike=
void *malloc(size_t request) {
...
if (!lower_bucket_limit(bucket - 1))
return NULL;
A4
...
}
```
* 答案是 `(c) ptr = (uint8_t *)list_pop(&buckets[bucket]);`
* 透過 `bucket_for_request()` 找到我們的 bucket 之後, 嘗試從 `free list` 尋找, 如果太大就 split
### 第五題
#### `void free(void *ptr)`
```clike=
void free(void *ptr) {
...
A5
i = (i - 1) / 2;
bucket--;
...
}
```
* 必須把 buddy 從 **free list** remove
* Move to sibling: index = ((index - 1) ^ 1) + 1;
* 答案是: `(d) list_remove((list_t *)ptr_for_node(((i - 1) ^ 1) + 1, bucket));`
## 延伸問題
**1. 分析程式碼的 sbrk 系統呼叫使用，注意其 alignment 行為，需要探討到 Linux 核心內部設計**
首先來看看 `man-pages` 怎麼解釋 `sbrk` 系統呼叫
>sbrk() increments the program's data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current location of the program break.
>
從這裡可以知道 `sbark()` 以 `byte` 為單位增加 `data space` 的大小，若給定參數 `0` 則會回傳 `program break` 的位址
在 `buddy` 內 `alloc.c` 裡的 `malloc` 函式用到了 `sbrk` 系統呼叫，以下是 `malloc` 的部份程式碼
```cpp=
void *malloc(size_t request)
{
if (!request || request + HEADER_SIZE > MAX_ALLOC)
return NULL;
/*
* Initialize our global state if this is the first call to "malloc". At the
* beginning, the tree has a single node that represents the smallest
* possible allocation size. More memory will be reserved later as needed.
*/
if (!base_ptr) {
/* FIXME: sbrk is deprecated on some platforms where mmap is suggested
* as a better replacement (macOS, FreeBSD). sbrk is generally
* onsidered quite archaic.
*/
base_ptr = max_ptr = (uint8_t *) sbrk(0);
bucket_limit = BUCKET_COUNT - 1;
update_max_ptr(base_ptr + sizeof(list_t));
list_init(&buckets[BUCKET_COUNT - 1]);
list_push(&buckets[BUCKET_COUNT - 1], (list_t *) base_ptr);
}
...
...
...
}
```
第 16 行使用 `sbrk(0)` 取得當前的 `program break` ，存到 `base_ptr` 當作之後新建 `bucket` 得初始位址
**2.思考能否將 sbrk 換為 mmap 或者其他系統呼叫，並且該如何設計測試程式，才能涵蓋 malloc 和 free 的行為？**
* 關於 mmap 這邊有個小範例, 如何透過 mmap 寫檔案?
* 根據 [认真分析mmap：是什么 为什么 怎么用
](https://www.cnblogs.com/huxiao-tee/p/4660352.html)
* 根據 [系统调用与内存管理](https://blog.csdn.net/Apollon_krj/article/details/54565768)
* 一般的文件操作使用 **page cache**:disk -> page cache -> main memory: 需要 2 次 數據拷貝
* 使用 **mmap** 建立 **disk** & **memory** 的映射關係: 需要 1 次 數據拷貝
```clike
1 #include <sys/mman.h>
2 #include <sys/types.h>
3 #include <sys/stat.h>
4 #include <fcntl.h>
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <unistd.h>
8 #include <string.h>
9
10 #define handle_error(msg) \
11 do { perror(msg); exit(EXIT_FAILURE); } while (0)
12
13 int main(int argc, char **argv) {
14 int fd = open("map.map", O_RDWR);
15 if (fd < 0) handle_error("open");
16
17 void *ptr1, *ptr2;
18 ptr1 = mmap(NULL, 64, PROT_WRITE | PROT_READ, MAP_SHARED, fd, 0);
19 ptr2 = malloc(64);
20
21 strcpy(ptr1, "Hello world");
22 //msync(ptr1, 64, MS_SYNC);
23 munmap(ptr1, 64);
24 close(fd);
25 }
```
上述程式先與 `map.map` 文件地址建立映射關係, 之後呼叫 `strcpy` 達成寫入動作, 要注意到的是: 呼叫 `msync` 或者 `munmap` 之前, 改動是不會寫回檔案的
### simple memory allocator
這是上學期修資工系作業系統的功課, 實作 buddy allocator, 如果超過上限, 則以 `mmap()` mapping
* https://github.com/oslab-csie-ncku/hw4-simple-memory-allocator-tony2037
* `hw_malloc(size_t size)`
```clike=
if(required_size <= (1 << 15)){
// Use heap to mallocate
int power = 0;
while((1 << (power)) < required_size){++power;};
printf("power required: %d\n", power);
...
// if Bin accessable give it, if not split
while(Bin[power]->next == NULL){
// no accessable, split
split(power + 1);
}
...
}
else{
// use mmap to distribute
void *ptr;
ptr = mmap(NULL, (bytes + sizeof(struct Header)), PROT_WRITE|PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
...
return ptr;
}
}
```
## Experience
* https://github.com/tony2037/buddy_allocator
## Reference
* http://students.mimuw.edu.pl/ZSO/Wyklady/05_pamiec/5_pamiec_en.html#wolne_ramki
* https://github.com/evanw/buddy-malloc/blob/master/buddy-malloc.c
* https://blog.csdn.net/juS3Ve/article/details/78441239
Sign in with Wallet
Connect another wallet