# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 14 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 mmap 系統呼叫和 [Linux 核心記憶體管理](https://hackmd.io/s/rJBXOchtE) 的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLScwO7UTvMkaw3LJ5XBoHg0XBMH_bO_MOiONuz8bwmbBecDAhQ/viewform)==

---

## 測驗 `1`

考慮以下一個以 mmap 實作的記憶體管理實作，針對 x86_64 平台的 GNU/Linux:

#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>

struct page_header {
    size_t pages, page_size;
    char page_data[];  // the rest of the page(s) of memory
};

static unsigned long get_page_size(void)
{
    static unsigned long page_size = 0;
    if (page_size == 0) {
        long tmp = sysconf(_SC_PAGESIZE);
        page_size = tmp < 0 ? 4096 : (unsigned long) tmp;
    }
    return page_size;
}

/* Takes a void * pointer as returned by malloc and returns the corresponding
 * page_header. Fails if the initial pointer was not returned by malloc
 */
static inline struct page_header *any_to_page_header(void *ptr)
{
    return (struct page_header *) ((char *) ptr - sizeof(struct page_header));
}

static void naive_free_internal(struct page_header *header)
{
    if (!header) return;

    if (munmap(header, header->pages * header->page_size) == -1)
        perror("Error freeing!");
}

void naive_free(void *ptr)
{
    if (ptr) naive_free_internal(any_to_page_header(ptr));
}

/*  Allocates the required number of pages of memory, places some header
 *  information at the start of the first page, then returns a pointer to the
 *  first byte after the header
 *  Allocates at least one page of memory for each call to simplify the logic
 *  Very inefficient for many small mallocs, but effective for one big malloc
 *  returns
 *   ________ _______ _______ ____     Page boundary
 *  | number |       |       |    |    |
 *  |   of   |data[0]|data[1]|... |    |
 *  | pages  |       |       |    |    |
 *   -------- ------- ------- ----
 *
 *  |--------|-------|
 *   size_t   sizeof(char)
 *           |--------------------|
 *            sizeof(char) * bytes
 */
static struct page_header *naive_malloc_internal(size_t size)
{
    if (size == 0) return NULL;

    /* size in bytes of a page of memory */
    size_t page_size = get_page_size();
    /* number of pages to allocate */
    size_t pages = AAA;
    size_t mmap_size = pages * page_size;
    void *ptr = mmap(0, mmap_size, BBB,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (ptr == MAP_FAILED) return NULL;

    struct page_header *page = ptr;
    /* copy values to page header */
    page->pages = pages;
    page->page_size = page_size;
    return page;
}

void *naive_malloc(size_t size)
{
    struct page_header *result = naive_malloc_internal(size);
    return !result ? NULL : result->page_data;
}

enum test_result {
    TEST_SUCCESS = 0,
    ALLOC_LARGE = 1,   // Allocation was larger than expected
    ALLOC_SMALL = 2,   // Allocation was smaller than expected
    NOT_FREED = 4,     // Call to free didn't work
    ALLOC_FAILED = 8,  // Allocation failed
    NOT_ZEROED = 16,   // Allocated memory is not zeroed (calloc only)
};

static void print_result(const char *const test_name, enum test_result result)
{
    if (result == TEST_SUCCESS) return;

    printf("%s failed.\n", test_name);
    if (result & ALLOC_LARGE) puts("Allocation was larger than expected\n");
    if (result & ALLOC_SMALL) puts("Allocation was smaller than expected\n");
    if (result & NOT_FREED) puts("Free failed\n");
    if (result & ALLOC_FAILED) puts("Allocation failed\n");
    fflush(stdout);
}

/** number of pages of memory used
 *  used to determine if call to free() worked */
static unsigned long get_used_memory(void)
{
    FILE *mem_info = fopen("/proc/self/statm", "r");
    if (!mem_info) {
        perror("Failed to open /proc/self/statm in get_used_memory()");
        assert(0);
    }

    unsigned long size, resident, shared, text, lib, data, dt;
    // each field has a maximum length of 19 = log_10(2^(64-1)) and there are
    // 7 fields in /proc/self/statm
    // With space delimiters and a trailing \0 this comes out to (19+1)*7 + 1 =
    // 141 Round to 150 just to be safe
    char buf[150];
    /* Provides information about memory usage, measured in pages.
     *   size        (1) total program size
     *               (same as VmSize in /proc/[pid]/status)
     *   resident    (2) resident set size
     *               (same as VmRSS in /proc/[pid]/status)
     *   shared	     (3) number of resident shared pages (i.e., backed by a
     *                   file) (same as RssFile+RssShmem in /proc/[pid]/status)
     *   text        (4) text (code)
     *   lib         (5) library (unused since Linux 2.6; always 0)
     *   data        (6) data + stack
     *   dt          (7) dirty pages (unused since Linux 2.6; always 0)
     */
    fgets(buf, sizeof(buf), mem_info);
    sscanf(buf, "%lu %lu %lu %lu %lu %lu %lu", &size, &resident, &shared, &text,
           &lib, &data, &dt);
    fclose(mem_info);
    return size;
}

static enum test_result test_variable_malloc(size_t size)
{
    unsigned ret = TEST_SUCCESS;
    unsigned long page_size = get_page_size();
    // size rounded down to the nearest multiple of page_size
    size_t min_expected_page_alloc =
        (size + sizeof(struct page_header)) / page_size;
    // size rounded up to the nearest multiple of page_size
    // TODO: deal with overflow
    size_t max_expected_page_alloc =
        (size + sizeof(struct page_header)) / page_size + 1;

    unsigned long before_malloc = get_used_memory();
    void *ptr = naive_malloc(size);
    if (!ptr && size != 0) return ALLOC_FAILED;

    unsigned long after_malloc = get_used_memory();
    unsigned long allocated = after_malloc - before_malloc;
    if (allocated < min_expected_page_alloc) ret |= ALLOC_SMALL;
    if (allocated > max_expected_page_alloc) ret |= ALLOC_LARGE;
    naive_free(ptr);

    unsigned long after_free = get_used_memory();
    if (before_malloc != after_free) ret |= NOT_FREED;
    return ret;
}

static int test_alloc_zero(void)
{
    unsigned int result = test_variable_malloc(0);
    if (result != TEST_SUCCESS) {
        print_result("test_malloc_zero", result);
        assert(result == TEST_SUCCESS);
    }
    return 0;
}

// allocations of less than one page of memory
static int test_alloc_small(void)
{
    for (size_t i = 1; i < get_page_size() - sizeof(struct page_header); i++) {
        unsigned int result = test_variable_malloc(i);
        if (result != TEST_SUCCESS) {
            print_result("test_malloc_small", result);
            assert(result == TEST_SUCCESS);
        }
    }
    return 0;
}

static int test_alloc_large(void)
{
    const unsigned long long _2pow64 = 18446744073709551615ull;
    const unsigned long long _2pow64div10 = _2pow64 / 10;
    unsigned long long size = get_page_size() - sizeof(struct page_header);
    unsigned increment = 2;  // multiply by this number each time
    for (; size < _2pow64div10; size *= increment) {
        unsigned int result = test_variable_malloc((size_t) size);
        if (result & ALLOC_FAILED) break;
        if (result != TEST_SUCCESS) {
            print_result("test_malloc_large", result);
            assert(result == TEST_SUCCESS);
        }
    }
    const unsigned long long largest_sucessful_alloc = size / increment;
    const unsigned long long billion = 1000ull * 1000ull * 1000ull;
    const unsigned long long million = 1000ull * 1000ull;
    if (largest_sucessful_alloc > billion) {
        printf("largest successfull alloc: %llu GB\n",
               largest_sucessful_alloc / billion);
    } else if (largest_sucessful_alloc > million) {
        printf("largest successfull alloc: %llu MB\n",
               largest_sucessful_alloc / million);
    } else if (largest_sucessful_alloc > 1000ull) {
        printf("largest successfull alloc: %llu KB\n",
               largest_sucessful_alloc / 1000ull);
    } else {
        printf("largest successfull alloc: %llu B\n", largest_sucessful_alloc);
    }
    return 0;
}

int main(void)
{
    test_alloc_zero();
    test_alloc_small();
    test_alloc_large();
    return 0;
}

參考執行輸出為:

largest successfull alloc: 136 GB

請補完程式碼。

==作答區==

AAA = ?
* `(a)` `size / page_size`
* `(b)` `size / page_size + 1`
* `(c)` `(size + sizeof(struct page_header)) / page_size`
* `(d)` `(size + sizeof(struct page_header)) / page_size + 1`
* `(e)` `(size - sizeof(struct page_header)) / page_size`

BBB = ?
* `(a)` `PROT_READ`
* `(b)` `PROT_READ | PROT_WRITE`
* `(c)` `PROT_READ | PROT_EXEC`

:::success
延伸問題:
1. 解釋上述程式運作原理，並探討 `/proc/self/statm` 的使用方式
2. 指出上述實作的缺失並予以改進
:::

---

### 測驗 `2`

在 [sbrk 的 Linux Man Page](https://linux.die.net/man/2/sbrk) 提到：
> `brk()` and `sbrk()` change the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory.
>
> 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.
>> `void *sbrk(intptr_t increment);`

sbrk() 用以變更 program break 的位置，改變 data segment size ，實現 virtual memory 到 physical memory 的 mapping
- 當 `increment > 0` 時， program break 的位置向後移動 increment 個位元組，同時 return 移動之前的位置，相當於配置新的記憶億
- 當 `increment < 0` 時，program break 的位置向前移動 increment 個位元組，相當於釋放記憶體
- 當` increment = 0` 時，program break 的位置不移動，只 return 目前的位置


考慮一個針對 GNU/Linux 的 [buddy memory allocator](https://en.wikipedia.org/wiki/Buddy_memory_allocation) 的實作，程式碼列表如下：

/* This file implements a buddy memory allocator, which is an allocator that
 * allocates memory within a fixed linear address range. It spans the address
 * range with a binary tree that tracks free space. Both "malloc" and "free"
 * are O(log N) time where N is the maximum possible number of allocations.
 *
 * The "buddy" term comes from how the tree is used. When memory is allocated,
 * nodes in the tree are split recursively until a node of the appropriate size
 * is reached. Every split results in two child nodes, each of which is the
 * buddy of the other. When a node is freed, the node and its buddy can be
 * merged again if the buddy is also free. This makes the memory available
 * for larger allocations again.
 */
#include <stdint.h>
#include <unistd.h>

/* Every allocation needs an 8-byte header to store the allocation size while
 * staying 8-byte aligned. The address returned by "malloc" is the address
 * right after this header (i.e. the size occupies the 8 bytes before the
 * returned address).
 */
#define HEADER_SIZE 8

/* The minimum allocation size is 16 bytes because we have an 8-byte header and
 * we need to stay 8-byte aligned.
 */
#define MIN_ALLOC_LOG2 4
#define MIN_ALLOC ((size_t) 1 << MIN_ALLOC_LOG2)

/* The maximum allocation size is currently set to 2gb. This is the total size
 * of the heap. It's technically also the maximum allocation size because the
 * heap could consist of a single allocation of this size. But of course real
 * heaps will have multiple allocations, so the real maximum allocation limit
 * is at most 1gb.
 */
#define MAX_ALLOC_LOG2 31
#define MAX_ALLOC ((size_t) 1 << MAX_ALLOC_LOG2)

/* Allocations are done in powers of two starting from MIN_ALLOC and ending at
 * MAX_ALLOC inclusive. Each allocation size has a bucket that stores the free
 * list for that allocation size.
 *
 * Given a bucket index, the size of the allocations in that bucket can be
 * found with "(size_t)1 << (MAX_ALLOC_LOG2 - bucket)".
 */
#define BUCKET_COUNT (MAX_ALLOC_LOG2 - MIN_ALLOC_LOG2 + 1)

/* Free lists are stored as circular doubly-linked lists. Every possible
 * allocation size has an associated free list that is threaded through all
 * currently free blocks of that size. That means MIN_ALLOC must be at least
 * "sizeof(list_t)". MIN_ALLOC is currently 16 bytes, so this will be true for
 * both 32-bit and 64-bit.
 */
typedef struct list_t {
    struct list_t *prev, *next;
} list_t;

/* Each bucket corresponds to a certain allocation size and stores a free list
 * for that size. The bucket at index 0 corresponds to an allocation size of
 * MAX_ALLOC (i.e. the whole address space).
 */
static list_t buckets[BUCKET_COUNT];

/* We could initialize the allocator by giving it one free block the size of
 * the entire address space. However, this would cause us to instantly reserve
 * half of the entire address space on the first allocation, since the first
 * split would store a free list entry at the start of the right child of the
 * root. Instead, we have the tree start out small and grow the size of the
 * tree as we use more memory. The size of the tree is tracked by this value.
 */
static size_t bucket_limit;

/* This array represents a linearized binary tree of bits. Every possible
 * allocation larger than MIN_ALLOC has a node in this tree (and therefore a
 * bit in this array).
 *
 * Given the index for a node, lineraized binary trees allow you to traverse to
 * the parent node or the child nodes just by doing simple arithmetic on the
 * index:
 *
 * - 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;
 *
 * Each node in this tree can be in one of several states:
 *
 * - UNUSED (both children are UNUSED)
 * - SPLIT (one child is UNUSED and the other child isn't)
 * - USED (neither children are UNUSED)
 *
 * These states take two bits to store. However, it turns out we have enough
 * information to distinguish between UNUSED and USED from context, so we only
 * need to store SPLIT or not, which only takes a single bit.
 *
 * Note that we don't need to store any nodes for allocations of size MIN_ALLOC
 * since we only ever care about parent nodes.
 */
static uint8_t node_is_split[(1 << (BUCKET_COUNT - 1)) / 8];

/* This is the starting address of the address range for this allocator. Every
 * returned allocation will be an offset of this pointer from 0 to MAX_ALLOC.
 */
static uint8_t *base_ptr;

/* This is the maximum address that has ever been used by the allocator. It's
 * used to know when to call "brk" to request more memory from the kernel.
 */
static uint8_t *max_ptr;

/* Make sure all addresses before "new_value" are valid and can be used. Memory
 * is allocated in a 2gb address range but that memory is not reserved up
 * front. It's only reserved when it's needed by calling this function. This
 * will return false if the memory could not be reserved.
 */
static int update_max_ptr(uint8_t *new_value)
{
    if (new_value > max_ptr) {
        if (brk(new_value)) return 0;
        max_ptr = new_value;
    }
    return 1;
}

/* Initialize a list to empty. Because these are circular lists, an "empty"
 * list is an entry where both links point to itself. This makes insertion
 * and removal simpler because they don't need any branches.
 */
static void list_init(list_t *list)
{
    list->prev = list;
    list->next = list;
}

/* Append the provided entry to the end of the list. This assumes the entry
 * isn't in a list already because it overwrites the linked list pointers.
 */
static void list_push(list_t *list, list_t *entry)
{
    list_t *prev = list->prev;
    entry->prev = prev;
    entry->next = list;
    prev->next = entry;
    list->prev = entry;
}

/* Remove the provided entry from whichever list it's currently in. This
 * assumes that the entry is in a list. You don't need to provide the list
 * because the lists are circular, so the list's pointers will automatically
 * be updated if the first or last entries are removed.
 */
static void list_remove(list_t *entry)
{
    list_t *prev = entry->prev;
    list_t *next = entry->next;
    prev->next = next;
    next->prev = prev;
}

/* Remove and return the first entry in the list or NULL if the list is empty.
 */
static list_t *list_pop(list_t *list)
{
    list_t *back = list->prev;
    if (back == list) return NULL;
    list_remove(back);
    return back;
}

/* This maps from the index of a node to the address of memory that node
 * represents. The bucket can be derived from the index using a loop but is
 * required to be provided here since having them means we can avoid the loop
 * and have this function return in constant time.
 */
static uint8_t *ptr_for_node(size_t index, size_t bucket)
{
    return base_ptr +
           ((index - (1 << bucket) + 1) << (MAX_ALLOC_LOG2 - bucket));
}

/* This maps from an address of memory to the node that represents that
 * address. There are often many nodes that all map to the same address, so
 * the bucket is needed to uniquely identify a node.
 */
static size_t node_for_ptr(uint8_t *ptr, size_t bucket)
{
    return ((ptr - base_ptr) >> (MAX_ALLOC_LOG2 - bucket)) + (1 << bucket) - 1;
}

/* Given the index of a node, this returns the "is split" flag of the parent.
 */
static int parent_is_split(size_t index)
{
    index = (index - 1) / 2;
    return (node_is_split[index / 8] >> (index % 8)) & 1;
}

/*
 * Given the index of a node, this flips the "is split" flag of the parent.
 */
static void flip_parent_is_split(size_t index)
{
    index = (index - 1) / 2;
    A1
}

/*
 * Given the requested size passed to "malloc", this function returns the index
 * of the smallest bucket that can fit that size.
 */
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;
}

/*
 * The tree is always rooted at the current bucket limit. This call grows the
 * tree by repeatedly doubling it in size until the root lies at the provided
 * bucket index. Each doubling lowers the bucket limit by 1.
 */
static int lower_bucket_limit(size_t bucket)
{
    while (bucket < bucket_limit) {
        size_t root = node_for_ptr(base_ptr, bucket_limit);
        uint8_t *right_child;

        /*
         * If the parent isn't SPLIT, that means the node at the current bucket
         * limit is UNUSED and our address space is entirely free. In that case,
         * clear the root free list, increase the bucket limit, and add a single
         * block with the newly-expanded address space to the new root free
         * list.
         */
        if (!parent_is_split(root)) {
            list_remove((list_t *) base_ptr);
            list_init(&buckets[--bucket_limit]);
            list_push(&buckets[bucket_limit], (list_t *) base_ptr);
            continue;
        }

        /*
         * Otherwise, the tree is currently in use. Create a parent node for the
         * current root node in the SPLIT state with a right child on the free
         * list. Make sure to reserve the memory for the free list entry before
         * writing to it. Note that we do not need to flip the "is split" flag
         * for our current parent because it's already on (we know because we
         * just checked it above).
         */
        right_child = ptr_for_node(root + 1, bucket_limit);
        if (!update_max_ptr(right_child + sizeof(list_t))) return 0;
        list_push(&buckets[bucket_limit], (list_t *) right_child);
        A3

        /*
         * Set the grandparent's SPLIT flag so if we need to lower the bucket
         * limit again, we'll know that the new root node we just added is in
         * use.
         */
        root = (root - 1) / 2;
        if (root != 0) flip_parent_is_split(root);
    }

    return 1;
}

void *malloc(size_t request)
{
    size_t original_bucket, bucket;

    /*
     * Make sure it's possible for an allocation of this size to succeed.
     * There's a hard-coded limit on the maximum allocation size because of the
     * way this allocator works.
     */
    if (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 == NULL) {
        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);
    }

    /*
     * Find the smallest bucket that will fit this request. This doesn't check
     * that there's space for the request yet.
     */
    bucket = bucket_for_request(request + HEADER_SIZE);
    original_bucket = bucket;

    /*
     * Search for a bucket with a non-empty free list that's as large or larger
     * than what we need. If there isn't an exact match, we'll need to split a
     * larger one to get a match.
     */
    while (bucket + 1 != 0) {
        size_t size, bytes_needed, i;
        uint8_t *ptr;

        /*
         * We may need to grow the tree to be able to fit an allocation of this
         * size. Try to grow the tree and stop here if we can't.
         */
        if (!lower_bucket_limit(bucket)) return NULL;

        /*
         * Try to pop a block off the free list for this bucket. If the free
         * list is empty, we're going to have to split a larger block instead.
         */
        ptr = (uint8_t *) list_pop(&buckets[bucket]);
        if (!ptr) {
            /*
             * If we're not at the root of the tree or it's impossible to grow
             * the tree any more, continue on to the next bucket.
             */
            if (bucket != bucket_limit || bucket == 0) {
                bucket--;
                continue;
            }

            /*
             * Otherwise, grow the tree one more level and then pop a block off
             * the free list again. Since we know the root of the tree is used
             * (because the free list was empty), this will add a parent above
             * this node in the SPLIT state and then add the new right child
             * node to the free list for this bucket. Popping the free list will
             * give us this right child.
             */
            if (!lower_bucket_limit(bucket - 1)) return NULL;
            A4
        }

        /*
         * Try to expand the address space first before going any further. If we
         * have run out of space, put this block back on the free list and fail.
         */
        size = (size_t) 1 << (MAX_ALLOC_LOG2 - bucket);
        bytes_needed =
            bucket < original_bucket ? size / 2 + sizeof(list_t) : size;
        if (!update_max_ptr(ptr + bytes_needed)) {
            list_push(&buckets[bucket], (list_t *) ptr);
            return NULL;
        }

        /*
         * If we got a node off the free list, change the node from UNUSED to
         * USED. This involves flipping our parent's "is split" bit because that
         * bit is the exclusive-or of the UNUSED flags of both children, and our
         * UNUSED flag (which isn't ever stored explicitly) has just changed.
         *
         * Note that we shouldn't ever need to flip the "is split" bit of our
         * grandparent because we know our buddy is USED so it's impossible for
         * our grandparent to be UNUSED (if our buddy chunk was UNUSED, our
         * parent wouldn't ever have been split in the first place).
         */
        i = node_for_ptr(ptr, bucket);
        if (i != 0) flip_parent_is_split(i);

        /*
         * If the node we got is larger than we need, split it down to the
         * correct size and put the new unused child nodes on the free list in
         * the corresponding bucket. This is done by repeatedly moving to the
         * left child, splitting the parent, and then adding the right child to
         * the free list.
         */
        while (bucket < original_bucket) {
            i = i * 2 + 1;
            bucket++;
            flip_parent_is_split(i);
            list_push(&buckets[bucket], (list_t *) ptr_for_node(i + 1, bucket));
        }

        /*
         * Now that we have a memory address, write the block header (just the
         * size of the allocation) and return the address immediately after the
         * header.
         */
        *(size_t *) ptr = request;
        return ptr + HEADER_SIZE;
    }

    return NULL;
}

void free(void *ptr)
{
    size_t bucket, i;

    /* Ignore any attempts to free a NULL pointer */
    if (!ptr) return;

    /*
     * We were given the address returned by "malloc" so get back to the actual
     * address of the node by subtracting off the size of the block header. Then
     * look up the index of the node corresponding to this address.
     */
    ptr = (uint8_t *) ptr - HEADER_SIZE;
    bucket = bucket_for_request(*(size_t *) ptr + HEADER_SIZE);
    i = node_for_ptr((uint8_t *) ptr, bucket);

    /*
     * Traverse up to the root node, flipping USED blocks to UNUSED and merging
     * UNUSED buddies together into a single UNUSED parent.
     */
    while (i != 0) {
        /*
         * Change this node from UNUSED to USED. This involves flipping our
         * parent's "is split" bit because that bit is the exclusive-or of the
         * UNUSED flags of both children, and our UNUSED flag (which isn't ever
         * stored explicitly) has just changed.
         */
        flip_parent_is_split(i);

        /*
         * If the parent is now SPLIT, that means our buddy is USED, so don't
         * merge with it. Instead, stop the iteration here and add ourselves to
         * the free list for our bucket.
         *
         * Also stop here if we're at the current root node, even if that root
         * node is now UNUSED. Root nodes don't have a buddy so we can't merge
         * with one.
         */
        if (parent_is_split(i) || bucket == bucket_limit) break;

        /*
         * If we get here, we know our buddy is UNUSED. In this case we should
         * merge with that buddy and continue traversing up to the root node. We
         * need to remove the buddy from its free list here but we don't need to
         * add the merged parent to its free list yet. That will be done once
         * after this loop is finished.
         */
        A5
        i = (i - 1) / 2;
        bucket--;
    }

    /*
     * Add ourselves to the free list for our bucket. We add to the back of the
     * list because "malloc" takes from the back of the list and we want a
     * "free" followed by a "malloc" of the same size to ideally use the same
     * address for better memory locality.
     */
    list_push(&buckets[bucket], (list_t *) ptr_for_node(i, bucket));
}

#include <assert.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    printf("Allocate 64\n");
    void *a = malloc(64);
    assert(a);

    printf("Allocate 100\n");
    a = malloc(100);
    assert(a);

    printf("Allocate 10000\n");
    a = malloc(10000);
    assert(a);
}

請補完下列函式:

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 int 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 0;
        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. 參照 [Malloc 對於多執行緒程式的效能影響](https://hackmd.io/s/SkfLN5j0e)，思考上述 memory allocator 的改進空間;
4. 在 Linux 核心原始程式碼找出 buddy allocator 的實作，並且分析其原理;
:::