Saturday, March 21, 2009

C Code - Bucket Based Allocator

In realtime systems, malloc/free/garbage collection can take a very long time.

For a real-time system I'm doing, I want to have very fast response time, I call malloc/free often.
Traditional malloc/free will fragment memory quickly, and garbage collection will just take
forever.

The solution I've used many times is a bucket allocator, setting pre-defined sizes of memory, and putting them in a queue, or in this case a "bucket". The idea being find the bucket, pull out a entry and return it.

Also something I've found useful is to keep track of busy memory elements as well. That way if I suspect that memory is getting corrupted, I can easily add a tag at the end of the allocation, and run thru the busy memory looking for the corruption. Very useful in debug.

#include <stdio.h>
#include <stdlib.h>
#include "include/queue.h"



struct bucket_struct {
struct entry_struct entry;
struct queue_struct free_q;
struct queue_struct busy_q;
int size;
};

struct alloc_struct {
struct entry_struct entry;
struct bucket_struct *bucket;
};

struct queue_struct buckets;

int gkmalloc_init_needed = 1;

void gkmalloc_newbucket(thesize)
int thesize;
{
struct bucket_struct *mybucket;

mybucket = malloc(sizeof(struct bucket_struct));
mybucket->free_q.head = NULL;
mybucket->free_q.tail = NULL;
mybucket->busy_q.head = NULL;
mybucket->busy_q.tail = NULL;
mybucket->entry.next = NULL;
mybucket->entry.prev = NULL;
mybucket->size = thesize;
queue(&buckets, &mybucket->entry);
return;
}


void gkmalloc_init(void)
{
gkmalloc_init_needed = 0;
buckets.head = NULL;
buckets.tail = NULL;
gkmalloc_newbucket(32);
gkmalloc_newbucket(64);
gkmalloc_newbucket(128);
gkmalloc_newbucket(256);
gkmalloc_newbucket(512);
gkmalloc_newbucket(1024);
gkmalloc_newbucket(2048);
gkmalloc_newbucket(4096);
gkmalloc_newbucket(8192);
gkmalloc_newbucket(32768);
gkmalloc_newbucket(12000000); // Big Buf for jpegs
return;
}

char *gkmalloc(thesize)
int thesize;
{
struct bucket_struct *mybucket;
struct alloc_struct *myalloc;
void *ptr;

if (thesize == 0)
return(NULL);
if (gkmalloc_init_needed){
gkmalloc_init();
gkmalloc_init_needed = 0;
}
mybucket = (struct bucket_struct *)buckets.head;
while(mybucket->size < thesize){
if (mybucket == NULL){ // Should never happen
gkfatal("gkmalloc: Allocation bigger than max bucket");
return(NULL);
}
mybucket = (struct bucket_struct *)mybucket->entry.next;
}
myalloc = (struct alloc_struct *)unqueue(&mybucket->free_q);
if (myalloc == NULL){ // The allocation queue is empty
// Dynamically allocate from the system
myalloc = malloc(sizeof(struct alloc_struct) + mybucket->size);
if (myalloc == NULL){
gkfatal("gkmalloc: Cannot malloc new buffer");
return(NULL);
}
myalloc->bucket = mybucket;
}

queue(&mybucket->busy_q, &myalloc->entry);
ptr = (void *)(myalloc + 1); // Add the size of the header to get Memory After
return(ptr);
}

void gkfree(ptr)
void *ptr;
{
struct bucket_struct *mybucket;
struct alloc_struct *myalloc;

if (ptr == NULL){
gkfatal("gkfree: Bad Free - Null Ptr Passed");
return;
}
myalloc = (struct alloc_struct *)ptr;
myalloc = myalloc - 1; // Go back to the header info
mybucket = myalloc->bucket;
if (mybucket == NULL){
gkfatal("gkfree: Bad Bucket");
return;
}
queue(&mybucket->free_q,&myalloc->entry);
return;
}

1 comment:

petrenkov said...

It was rather interesting for me to read the post. Thanks the author for it. I like such themes and anything connected to this matter. I would like to read a bit more soon.

Best regards
Steave Markson