110 lines
2.8 KiB
C
110 lines
2.8 KiB
C
#include <stddef.h>
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
// This allocator lacks critical features such as coalescing
|
|
|
|
#define HEAP_SIZE (1 << 20) // 1 MB
|
|
#define MIN_ORDER 5 // 32 bytes
|
|
#define MAX_ORDER 20 // 1 MB
|
|
|
|
#define ORDER_TO_SZ(order) (1 << order)
|
|
|
|
// Round size up to nearest power-of-two order
|
|
static int size_to_order(size_t size) {
|
|
int order = MIN_ORDER;
|
|
while ((1U << order) < size) order++;
|
|
return order;
|
|
}
|
|
|
|
typedef struct block {
|
|
struct block *next;
|
|
// int order;
|
|
// int is_free;
|
|
} block_t;
|
|
|
|
static char *heap;
|
|
static block_t *free_lists[MAX_ORDER - MIN_ORDER + 1];
|
|
|
|
void buddy_init() {
|
|
block_t *initial = (block_t *)heap;
|
|
initial->next = NULL;
|
|
// initial->order = MAX_ORDER;
|
|
// initial->is_free = 1;
|
|
free_lists[MAX_ORDER - MIN_ORDER] = initial;
|
|
}
|
|
|
|
void *buddy_alloc(size_t size) {
|
|
int order = size_to_order(size);
|
|
int index = order - MIN_ORDER;
|
|
|
|
// Find the first available block of order >= needed
|
|
int i = index; // i is the lowest possible order here
|
|
while (i <= MAX_ORDER - MIN_ORDER && !free_lists[i]) {
|
|
i++;
|
|
}
|
|
|
|
// Check if were still within range, if not there are no free blocks
|
|
if (i > MAX_ORDER - MIN_ORDER)
|
|
return NULL;
|
|
|
|
// Split blocks down to the requested size
|
|
while (i > index) { // Does not run if i == index
|
|
block_t *bigger = free_lists[i];
|
|
free_lists[i] = bigger->next; // This may be null, doesnt matter
|
|
|
|
i--; // i is now equivalent to one order below
|
|
|
|
size_t split_size = ORDER_TO_SZ(i);
|
|
// FIXME: Char???
|
|
char *middle = ((char *)bigger + split_size);
|
|
block_t *buddy = (block_t *)middle;
|
|
// block_t *buddy = (block_t *)((char *)bigger + split_size);
|
|
buddy->next = NULL;
|
|
bigger->next = buddy; // Biggers buddy is of equal size
|
|
free_lists[i] = bigger; // Bigger is no longer bigger here
|
|
}
|
|
|
|
// Allocate from free list
|
|
block_t *block = free_lists[index];
|
|
free_lists[index] = block->next;
|
|
return (void *)block;
|
|
}
|
|
|
|
// Free a block (no coalescing)
|
|
void buddy_free(void *ptr, size_t size) {
|
|
memset(ptr, 0xFFFFFFFF, size);
|
|
|
|
int order = size_to_order(size);
|
|
int index = order - MIN_ORDER;
|
|
|
|
// Push this in front of the orders index
|
|
block_t *block = (block_t *)ptr;
|
|
block->next = free_lists[index];
|
|
free_lists[index] = block;
|
|
}
|
|
|
|
int main(void) {
|
|
heap = malloc(1 << 20);
|
|
|
|
printf("Order: %d\n", size_to_order(100));
|
|
printf("Order: %d\n", size_to_order(1000));
|
|
|
|
buddy_init();
|
|
|
|
void *a = buddy_alloc(100);
|
|
void *b = buddy_alloc(1000);
|
|
|
|
*(int *)a = 10;
|
|
printf("a = %d\n", *(int *)a);
|
|
|
|
buddy_free(a, 100);
|
|
buddy_free(b, 1000);
|
|
|
|
printf("a = %d\n", *(int *)a);
|
|
|
|
free(heap);
|
|
return 0;
|
|
}
|