Buddy Memory Allocator

Buddy Memory Allocator

This is a simple memory allocator to design. Lots of internal fragmentation goes on, but the design is fairly simple. First off, when designing a memory allocator, basic essentials are understood as common sense knowledge.

Arena's are big memory "chunks" given to a user level process for dynamic memory allocation usage. Within each arena, there are fragments. Each arena manages its own
fragments that are allocated to the user. Also, above that, the memory allocator will license a memory fragment from any free memory segment >= to the fragment asked. Also, for alignment issues, the fragment asked will be the next highest byte-alignment for easy transaction. There are minimum and maximum memory allocation requests.

Also, the buddy memory allocation schema is used when freeing up memory allocations, and then coalescing fragments together to form the original allocation units. Also, when you coalesce two "buddies" together, they have to be of the same size (for easy manipulation). There are certain issues that the buddy memory allocator I have been studying does. It allocates the largest chunk first, and then goes down by powers of 2 until you run out of memory in the arena (also, note that no fragment size will be less than the minimum memory allocation unit defined).

With that in mind, the arena needs to know which fragments are being allocated and freed. Also, we need each fragment to know which arena it belongs to. There is an option also, to include an array of linked lists depending on the size of the allocation that it can perform. Also, there is the necessity of figuring out who the buddy of one fragment is. This is essential since we let each fragment have only one buddy. Therefore, the main target is to identify fragments->Arena and Arena->fragments relationships. Each fragment can have an identifier detailing the bitmap of the arena, and each arena could have a mapping detailing which allocations are free or not.

Therefore, here are a couple of attributes:

#define GET_BUDDY(arena,fragment,lg2size) \
   ((typeof(fragment))((char *)arena + 
               (((size_t)((char *)fragment - (char*)arena)) 
                 ^ (1<<(lg2size))))

typedef struct bitmap {
   uint32_t arenaKey1;
   uchar_t  bitset[TOTAL_FRAGMENTS / CHAR_BIT];
   uint32_t arenaKey2;
} bitmap_t;

typedef struct fragment {
   bitmap_t * arenaId;
   /* some fragment header info */
   uint32_t log2size;
} fragment_t;

/* Holds all fragment header's of a certain size, 
   and holds the fragment header's of all sizes. */
fragment_header_info * fragHeaders[N_ALLOCATION_SIZES];