Project 5: Building a Memory Allocator

Goals of Projects

Build a Heap Allocator to demonstrate functions malloc()

.
├── heap.c
├── heap_test
├── include
│   ├── heap.h
│   └── llist.h
├── llist.c
└── main.c

Where heap_test is the exectuable file to run. The include folder contains header files for the heap and linked lists C code programs.

In this Project we will use a Doubly-Linked Lists to implement and we will work on the heap.c file below to see how it allocates memory. The main.c file will run our program for us.

Doubly-Linked List Implementated

Doubly-Linked List Header File (llist.h)

#ifndef LLIST_H
#define LLIST_H

#include "heap.h"
#include <stdint.h>

void add_node(bin_t *bin, node_t *node);

void remove_node(bin_t *bin, node_t *node);

node_t *get_best_fit(bin_t *list, size_t size);
node_t *get_last_node(bin_t *list);

node_t *next(node_t *current);
node_t *prev(node_t *current);

#endif

Doubly-Linked List File (llist.c)

#include "include/llist.h"

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 != NULL && 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 != NULL) { // 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;
    }
    
    node_t *temp = bin->head->next;
    while (temp != NULL) {
        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 dont worry about deleting the head here because we already checked that
            return;
        }
        temp = temp->next;
    }
}

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

    node_t *temp = bin->head;

    while (temp != NULL) {
        if (temp->size >= size) {
            return temp; // found a fit!
        }
        temp = temp->next;
    }
    return NULL; // no fit!
}

node_t *get_last_node(bin_t *bin) {
    node_t *temp = bin->head;

    while (temp->next != NULL) {
        temp = temp->next;
    }
    return temp;
}

Heap Code

Heap Header File (heap.h)

• The Header file contain functions

#ifndef HEAP_H
#define HEAP_H

#include <stdint.h>
#include <stddef.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;
    uint size;
    struct node_t* next;
    struct node_t* prev;
} node_t;

typedef struct { 
    node_t *header;
} footer_t;

typedef struct {
    node_t* head;
} bin_t;

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

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

void init_heap(heap_t *heap, long start);

void *heap_alloc(heap_t *heap, size_t size);
void heap_free(heap_t *heap, void *p);
uint expand(heap_t *heap, size_t sz);
void contract(heap_t *heap, size_t sz);

uint get_bin_index(size_t sz);
void create_foot(node_t *head);
footer_t *get_foot(node_t *head);

node_t *get_wilderness(heap_t *heap);

#endif

Heap File (heap.c)

#include "include/heap.h"
#include "include/llist.h"

uint offset = 8;

void init_heap(heap_t *heap, long start) {
    node_t *init_region = (node_t *) start;
    init_region->hole = 1;
    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) {
        uint success = expand(heap, 0x1000);
        if (success == 0) {
            return NULL;
        }
    }
    else if (wild->size > MAX_WILDERNESS) {
        contract(heap, 0x1000);
    }

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

void heap_free(heap_t *heap, void *p) {
    bin_t *list;
    footer_t *new_foot, *old_foot;

    node_t *head = (node_t *) ((char *) p - offset);
    if (head == (node_t *) (uintptr_t) heap->start) {
        head->hole = 1; 
        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 - sizeof(footer_t));
    node_t *prev = f->header;
    
    if (prev->hole) {
        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) {
        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);
}

uint expand(heap_t *heap, size_t sz) {
    return 0;
}

void contract(heap_t *heap, size_t sz) {
    return;
}

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

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

footer_t *get_foot(node_t *node) {
    return (footer_t *) ((char *) node + sizeof(node_t) + node->size);
}

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

Main File (main.c)

#include "include/heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv) {
    int i;

    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 (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 (i = 1; i <= 2048; i += i) printf("size: %d -> bin: %d \n", i, get_bin_index(i));

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

    // Remove Memory
    free(heap);
    free(region);

}

Makefile

clang-test:
	clang -O3 llist.c heap.c main.c -o heap_test
	./heap_test	

gcc-test:
	gcc -O3 llist.c heap.c main.c -o heap_test
	./heap_test

clean:
	rm heap_test

Run the Executable

Compile Code:

Can just run make

make

Run heap_test

./heap_test

Output:

overhead = 32 
a = 671121416 size: 8 
b = 671121456 size: 128 
c = 671121616 size: 8 

freeing b 
d = 671121456 size: 8 
e = 671121496 size: 16 
f = 671121544 size: 8 
g = 671121656 size: 8 

freeing d & f 

freeing e
h = 671121456 size: 128 

size: 1 -> bin: 0 
size: 2 -> bin: 0 
size: 4 -> bin: 0 
size: 8 -> bin: 1 
size: 16 -> bin: 2 
size: 32 -> bin: 3 
size: 64 -> bin: 4 
size: 128 -> bin: 5 
size: 256 -> bin: 6 
size: 512 -> bin: 7 
size: 1024 -> bin: 8 
size: 2048 -> bin: 8