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

C Code - Link List or Queues

One of my favorite real-time system tricks is to use queues, or linked-list
to handle message passing. Then the whole system can be lots of small co-routines, without the overhead of task-switching. Small and tight code really can run fast. Usually the problem you get with this is malloc/free overhead.

A pre-allocated chunk based system solves that. I'll post it to a future blog.

## queue.c
#include <stdio.h>
#include <stdlib.h>

#include "include/queue.h"
/*
** Queue.c
*/

struct entry_struct *unqueue(q)
struct queue_struct *q;
{
struct entry_struct *entry;

  if (q==NULL)         return(NULL);
  if (q->head == NULL) return(NULL);
  entry = q->head;
  q->head = entry->next;
  if (q->head == NULL) q->tail = NULL;
  entry->next = NULL;
  entry->prev = NULL;
  return(entry);
}

void queue(q,entry)
struct queue_struct *q; 
struct entry_struct *entry;
{
  if (q==NULL) return;
  if (entry == NULL) return;
  entry->next = NULL;
  entry->prev = NULL;
  if (q->head == NULL){
     q->head = entry;
     q->tail = entry;
    return;
    }
  entry->prev = q->tail;
  q->tail->next = entry;
  q->tail = entry;
 return;
}

struct queue_struct *init_queue(void)
{
struct queue_struct *q;

    q = (struct queue_struct *)malloc(sizeof(struct queue_struct *));
        q->head = NULL;
        q->tail = NULL;
        return(q);
}

## queue.h
/*
** Queue.h
*/

struct entry_struct {
       struct entry_struct *next;
       struct entry_struct *prev;
};

struct queue_struct {
     struct entry_struct  *head;
     struct entry_struct *tail;
};

struct entry_struct *unqueue(struct queue_struct *);
void queue(struct queue_struct *, struct entry_struct *);
struct queue_struct *init_queue(void);