# 2019q1 第 11 週測驗題 (下)
:::info
目的: 檢驗學員對 [Linux 核心記憶體管理](https://hackmd.io/s/rJBXOchtE) 的認知
:::

---

### 測驗 `1`

延伸 [第 11 週測驗題 (上)](https://hackmd.io/s/HypUB7HjV) 和 [第 11 週測驗題 (中)](https://hackmd.io/s/BkFJPHriE)，考慮 [buddy](https://github.com/sysprog21/buddy) 這個 [buddy memory allocator](https://en.wikipedia.org/wiki/Buddy_memory_allocation) 的實作，請補完下列函式:

static void flip_parent_is_split(size_t index) {
    index = (index - 1) / 2;
    A1
}

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;
}

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
    ...
}

void *malloc(size_t request) {
    ...
            if (!lower_bucket_limit(bucket - 1))
                return NULL;
            A4
    ...
}

void free(void *ptr) {
    ...
        A5
        i = (i - 1) / 2;
        bucket--;
    ...
}

==作答區==

A1 = ?
* `(a)` `node_is_split[index / 8] ^= 1 << (index % 8);`
* `(b)` `node_is_split[index / 8] = 1 << (index / 8);`

A2 = ?
* `(a)` `bucket++;`
* `(b)` `size *= 2;`
* `(c)` `bucket--; size *= 2;`
* `(d)` `bucket++; size *= 2;`

A3 = ?
* `(a)` `/* no operation */`
* `(b)` `list_init(&buckets[--bucket_limit]);`
* `(c)` `list_init(&buckets[bucket_limit]);`
* `(d)` `list_init(&buckets[bucket_limit++]);`

A4 = ?
* `(a)` `/* no operation */`
* `(b)` `ptr = (uint8_t *)list_pop(&buckets[--bucket]);`
* `(c)` `ptr = (uint8_t *)list_pop(&buckets[bucket]);`

A5 = ?
* `(a)` `list_remove((list_t *)ptr_for_node(i + 1, bucket));`
* `(b)` `list_remove((list_t *)ptr_for_node(i, bucket));`
* `(c)` `list_remove((list_t *)ptr_for_node(i - 1, bucket));`
* `(d)` `list_remove((list_t *)ptr_for_node(((i - 1) ^ 1) + 1, bucket));`

:::success
延伸問題:
1. 分析程式碼的 `sbrk` 系統呼叫使用，[注意其 alignment 行為](https://stackoverflow.com/questions/27340800/is-the-initial-call-to-sbrk0-in-linux-always-return-a-value-aligned-to-8-bytes)，需要探討到 Linux 核心內部設計
2. 思考能否將 `sbrk` 換為 `mmap` 或者其他系統呼叫，並且該如何設計測試程式，才能涵蓋 `malloc` 和 `free` 的行為？
3. 參照 [rpmalloc 探討](https://hackmd.io/s/H1TP6FV6z) 和 [Malloc 對於多執行緒程式的效能影響](https://hackmd.io/s/SkfLN5j0e)，思考上述 memory allocator 的改進空間;
4. 在 Linux 核心原始程式碼找出 buddy allocator 的實作，並且分析其原理;
:::

---