buddy_alloc.c

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

#define MIN_ORDER   4           /* minimum block: 2^4  =   16 bytes */
#define MAX_ORDER   12          /* maximum block: 2^12 = 4096 bytes */
#define ORDERS      (MAX_ORDER - MIN_ORDER + 1)
#define ARENA_SIZE  (1 << MAX_ORDER)

typedef struct block { struct block *next; } block_t;

static char    arena[ARENA_SIZE] __attribute__((aligned(4096)));
static block_t *free_list[ORDERS];   /* free_list[0] = order MIN_ORDER */

static int fl_idx(int order) { return order - MIN_ORDER; }

/* Return the minimum order whose block size >= n, or -1 if too large. */
static int order_for(size_t n)
{
    if (n == 0) n = 1;
    int o = MIN_ORDER;
    while ((size_t)(1 << o) < n) o++;
    return o > MAX_ORDER ? -1 : o;
}

void buddy_init(void)
{
    memset(free_list, 0, sizeof(free_list));
    free_list[fl_idx(MAX_ORDER)] = (block_t *)arena;
}

void *buddy_alloc(size_t size)
{
    int o = order_for(size);
    if (o < 0) return NULL;

    /* find the smallest free list at order >= o */
    int found = -1;
    for (int i = o; i <= MAX_ORDER; i++) {
        if (free_list[fl_idx(i)]) { found = i; break; }
    }
    if (found < 0) return NULL;

    /* take one block from 'found', split down to order o */
    block_t *blk = free_list[fl_idx(found)];
    free_list[fl_idx(found)] = blk->next;

    for (int i = found; i > o; i--) {
        /* right half becomes a free buddy at order i-1 */
        block_t *buddy = (block_t *)((char *)blk + (1 << (i - 1)));
        buddy->next = free_list[fl_idx(i - 1)];
        free_list[fl_idx(i - 1)] = buddy;
        /* blk is the left half; keep splitting it */
    }

    return blk;
}

void buddy_free(void *ptr, size_t size)
{
    if (!ptr) return;
    int o = order_for(size);
    if (o < 0) return;

    for (;;) {
        /* buddy address: flip the bit at position o */
        uintptr_t off   = (uintptr_t)((char *)ptr - arena);
        uintptr_t boff  = off ^ (uintptr_t)(1 << o);
        block_t  *buddy = (block_t *)(arena + boff);

        if (o == MAX_ORDER) break; /* already at the top */

        /* search for buddy in the free list at this order */
        block_t **p = &free_list[fl_idx(o)];
        while (*p && *p != buddy) p = &(*p)->next;
        if (!*p) break; /* buddy is not free — stop here */

        /* remove buddy, merge: use the lower-address half */
        *p = buddy->next;
        if (buddy < (block_t *)ptr) ptr = buddy;
        o++;
    }

    block_t *blk = (block_t *)ptr;
    blk->next = free_list[fl_idx(o)];
    free_list[fl_idx(o)] = blk;
}

int main(void)
{
    buddy_init();

    void *a = buddy_alloc(100);   /* → 128-byte block (order 7) */
    void *b = buddy_alloc(200);   /* → 256-byte block (order 8) */
    void *c = buddy_alloc(50);    /* →  64-byte block (order 6) */
    printf("a=%p  b=%p  c=%p\n", a, b, c);

    buddy_free(b, 200);
    void *d = buddy_alloc(180);   /* should reuse b's region */
    printf("d=%p  (reused b's slot: %s)\n", d, d == b ? "yes" : "no");

    buddy_free(a, 100);
    buddy_free(c, 50);
    buddy_free(d, 180);

    /* with all blocks freed the whole arena should coalesce back */
    int coalesced = (free_list[fl_idx(MAX_ORDER)] == (block_t *)arena &&
                     free_list[fl_idx(MAX_ORDER)]->next == NULL);
    printf("fully coalesced: %s\n", coalesced ? "yes" : "no");

    return 0;
}