2019q1 第 11 週測驗題 (下)

目的: 檢驗學員對 Linux 核心記憶體管理 的認知

---

測驗 1

延伸 第 11 週測驗題 (上) 和 第 11 週測驗題 (中)，考慮 buddy 這個 buddy memory allocator 的實作，請補完下列函式:

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

延伸問題:

1. 分析程式碼的 sbrk 系統呼叫使用，注意其 alignment 行為，需要探討到 Linux 核心內部設計
2. 思考能否將 sbrk 換為 mmap 或者其他系統呼叫，並且該如何設計測試程式，才能涵蓋 malloc 和 free 的行為？
3. 參照 rpmalloc 探討 和 Malloc 對於多執行緒程式的效能影響，思考上述 memory allocator 的改進空間;
4. 在 Linux 核心原始程式碼找出 buddy allocator 的實作，並且分析其原理;

---