# 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) 的實作,請補完下列函式: ```cpp 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 的實作,並且分析其原理; ::: ---