# [2019q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 13 週測驗題
:::info
目的: 檢驗學員對 CS:APP 第 9 章的認知
:::

---

### 測驗 `1`

考慮到以下簡易的記憶體配置器實作 (`alloc.c`):

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HEAP_INIT_SIZE 0x10000
#define HEAP_MAX_SIZE 0xF0000
#define HEAP_MIN_SIZE 0x10000

#define MIN_ALLOC_SZ 4

#define MIN_WILDERNESS 0x2000
#define MAX_WILDERNESS 0x1000000

#define BIN_COUNT 9
#define BIN_MAX_IDX (BIN_COUNT - 1)

typedef unsigned int uint;

typedef struct node_t {
    uint hole, size;
    struct node_t *next, *prev;
} node_t;

typedef struct {
    node_t *header;
} footer_t;

typedef struct {
    node_t *head;
} bin_t;

typedef struct {
    long start, end;
    bin_t *bins[BIN_COUNT];
} heap_t;

static uint overhead = sizeof(footer_t) + sizeof(node_t);

void add_node(bin_t *bin, node_t *node)
{
    node->next = NULL;
    node->prev = NULL;

    node_t *temp = bin->head;

    if (bin->head == NULL) {
        bin->head = node;
        return;
    }

    // we need to save next and prev while we iterate
    node_t *current = bin->head;
    node_t *previous = NULL;
    // iterate until we get the the end of the list or we find a
    // node whose size is
    while (current && current->size <= node->size) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) {  // we reached the end of the list
        previous->next = node;
        node->prev = previous;
    } else {
        if (previous) {  // middle of list, connect all links!
            node->next = current;
            previous->next = node;

            node->prev = previous;
            current->prev = node;
        } else {  // head is the only element
            node->next = bin->head;
            bin->head->prev = node;
            bin->head = node;
        }
    }
}

void remove_node(bin_t *bin, node_t *node)
{
    if (bin->head == NULL)
        return;
    if (bin->head == node) {
        bin->head = bin->head->next;
        return;
    }

    for (node_t *temp = bin->head->next; temp; temp = temp->next) {
        if (temp == node) {            // found the node
            if (temp->next == NULL) {  // last item
                temp->prev->next = NULL;
            } else {  // middle item
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
            }
            // we do not worry about deleting the head here because we already
            // checked that
            return;
        }
    }
}

node_t *get_best_fit(bin_t *bin, size_t size)
{
    if (bin->head == NULL)
        return NULL;  // empty list!

    for (node_t *temp = bin->head; temp; temp = temp->next) {
        if (temp->size >= size)
            return temp;  // found a fit!
    }
    return NULL;  // no fit!
}

node_t *get_last_node(bin_t *bin)
{
    node_t *temp = bin->head;
    while (temp->next)
        temp = temp->next;
    return temp;
}

uint get_bin_index(size_t sz)
{
    uint index = 0;
    sz = sz < 4 ? 4 : sz;

    while (sz >>= 1)
        index++;
    index -= 2;

    if (index > BIN_MAX_IDX)
        index = BIN_MAX_IDX;
    return index;
}

static footer_t *get_foot(node_t *node)
{
    return (footer_t *) ((char *) node + sizeof(node_t) + AAA);
}

static void create_foot(node_t *head)
{
    footer_t *foot = get_foot(head);
    foot->header = head;
}

node_t *get_wilderness(heap_t *heap)
{
    footer_t *wild_foot = (footer_t *) ((char *) heap->end - sizeof(footer_t));
    return wild_foot->header;
}

void init_heap(heap_t *heap, long start)
{
    node_t *init_region = (node_t *) start;
    init_region->hole = BBB;
    init_region->size = (HEAP_INIT_SIZE) - sizeof(node_t) - sizeof(footer_t);

    create_foot(init_region);

    add_node(heap->bins[get_bin_index(init_region->size)], init_region);

    heap->start = (void *) start;
    heap->end = (void *) (start + HEAP_INIT_SIZE);
}

void *heap_alloc(heap_t *heap, size_t size)
{
    uint index = get_bin_index(size);
    bin_t *temp = (bin_t *) heap->bins[index];
    node_t *found = get_best_fit(temp, size);

    while (found == NULL) {
        if (index + 1 >= BIN_COUNT)
            return NULL;

        temp = heap->bins[++index];
        found = get_best_fit(temp, size);
    }

    if ((found->size - size) > (overhead + MIN_ALLOC_SZ)) {
        node_t *split =
            (node_t *) (((char *) found + sizeof(node_t) + sizeof(footer_t)) +
                        size);
        split->size = found->size - size - sizeof(node_t) - sizeof(footer_t);
        split->hole = 1;

        create_foot(split);

        uint new_idx = get_bin_index(split->size);
        add_node(heap->bins[new_idx], split);

        found->size = size;
        create_foot(found);
    }

    found->hole = 0;
    remove_node(heap->bins[index], found);

    node_t *wild = get_wilderness(heap);
    if (wild->size < MIN_WILDERNESS)
        return NULL;

    found->prev = NULL;
    found->next = NULL;
    return &found->next;
}

static int offset = 8;
void heap_free(heap_t *heap, void *p)
{
    footer_t *new_foot, *old_foot;

    node_t *head = (node_t *) ((char *) p - offset);
    if (head == (node_t *) (uintptr_t) heap->start) {
        head->hole = CCC;
        add_node(heap->bins[get_bin_index(head->size)], head);
        return;
    }

    node_t *next = (node_t *) ((char *) get_foot(head) + sizeof(footer_t));
    footer_t *f = (footer_t *) ((char *) head - DDD);
    node_t *prev = f->header;

    if (prev->hole) {
        bin_t *list = heap->bins[get_bin_index(prev->size)];
        remove_node(list, prev);

        prev->size += overhead + head->size;
        new_foot = get_foot(head);
        new_foot->header = prev;

        head = prev;
    }

    if (next->hole) {
        bin_t *list = heap->bins[get_bin_index(next->size)];
        remove_node(list, next);

        head->size += overhead + next->size;

        old_foot = get_foot(next);
        old_foot->header = 0;
        next->size = 0;
        next->hole = 0;

        new_foot = get_foot(head);
        new_foot->header = head;
    }

    head->hole = 1;
    add_node(heap->bins[get_bin_index(head->size)], head);
}

int main(int argc, char **argv)
{
    heap_t *heap = malloc(sizeof(heap_t));
    memset(heap, 0, sizeof(heap_t));

    void *region = malloc(HEAP_INIT_SIZE);
    memset(region, 0, HEAP_INIT_SIZE);

    for (int i = 0; i < BIN_COUNT; i++) {
        heap->bins[i] = malloc(sizeof(bin_t));
        memset(heap->bins[i], 0, sizeof(bin_t));
    }

    init_heap(heap, (long) region);

    printf("overhead = %d \n", overhead);

    void *a = heap_alloc(heap, 8);
    printf("a = %d size: 8 \n", (int) a);
    void *b = heap_alloc(heap, 128);
    printf("b = %d size: 128 \n", (int) b);
    void *c = heap_alloc(heap, 8);
    printf("c = %d size: 8 \n", (int) c);

    printf("\nfreeing b \n");
    heap_free(heap, b);

    void *d = heap_alloc(heap, 8);
    printf("d = %d size: 8 \n", (int) d);

    void *e = heap_alloc(heap, 16);
    printf("e = %d size: 16 \n", (int) e);

    void *f = heap_alloc(heap, 8);
    printf("f = %d size: 8 \n", (int) f);

    void *g = heap_alloc(heap, 8);
    printf("g = %d size: 8 \n", (int) g);

    printf("\nfreeing d & f \n");
    heap_free(heap, d);
    heap_free(heap, f);

    printf("\nfreeing e\n");
    heap_free(heap, e);

    void *h = heap_alloc(heap, 128);
    printf("h = %d size: 128 \n", (int) h);
    printf("\n");

    for (int i = 0; i < BIN_COUNT; i++) {
        free(heap->bins[i]);
    }

    free(heap);
    free(region);
}

在 GNU/Linux 上參考的執行輸出如下:

overhead = 32 
a = -1337560376 size: 8 
b = -1337560336 size: 128 
c = -1337560176 size: 8 

freeing b 
d = -1337560336 size: 8 
e = -1337560296 size: 16 
f = -1337560248 size: 8 
g = -1337560136 size: 8 

freeing d & f 

freeing e
h = -1337560336 size: 128 

請揣摩程式碼及其註解，補完程式碼。

==作答區==

AAA = ?
`(a)` 0
`(b)` `sizeof(footer_t)`
`(c)` 1
`(d)` `node->hole`
`(e)` `node->size`

BBB = ?
`(a)` 0
`(b)` `sizeof(footer_t)`
`(c)` 1
`(d)` `node->hole`
`(e)` `node->size`

CCC = ?
`(a)` 0
`(b)` `sizeof(footer_t)`
`(c)` 1
`(d)` `node->hole`
`(e)` `node->size`

DDD = ?
`(a)` 0
`(b)` `sizeof(footer_t)`
`(c)` 1
`(d)` `node->hole`
`(e)` `node->size`

:::success
延伸問題:
1. 解釋上述程式碼運作機制;
2. 指出實作的缺失並加以改進;
3. 參考 [Two Level Segregated Fit (TLSF) memory allocator implementation](https://github.com/jserv/tlsf-bsd) 實作和對應的論文，分析運作原理;
:::

---