C Language Memory management User-defined memory management
Example
malloc() often calls underlying operating system functions to obtain pages of memory. But there is nothing special about the function and it can be implemented in straight C by declaring a large static array and allocating from it (there is a slight difficulty in ensuring correct alignment, in practice aligning to 8 bytes is almost always adequate).
To implement a simple scheme, a control block is stored in the region of memory immediately before the pointer to be returned from the call. This means that free() may be implemented by subtracting from the returned pointer and reading off the control information, which is typically the block size plus some information that allows it to be put back in the free list - a linked list of unallocated blocks.
When the user requests an allocation, the free list is searched until a block of identical or larger size to the amount requested is found, then if necessary it is split. This can lead to memory fragmentation if the user is continually making many allocations and frees of unpredictable size and and at unpredictable intervals (not all real programs behave like that, the simple scheme is often adequate for small programs).
/* typical control block */
struct block
{
size_t size; /* size of block */
struct block *next; /* next block in free list */
struct block *prev; /* back pointer to previous block in memory */
void *padding; /* need 16 bytes to make multiple of 8 */
}
static struct block arena[10000]; /* allocate from here */
static struct block *firstfree;
Many programs require large numbers of allocations of small objects of the same size. This is very easy to implement. Simply use a block with a next pointer. So if a block of 32 bytes is required:
union block
{
union block * next;
unsigned char payload[32];
}
static union block arena[100];
static union block * head;
void init(void)
{
int i;
for (i = 0; i < 100 - 1; i++)
arena[i].next = &arena[i + 1];
arena[i].next = 0; /* last one, null */
head = &block[0];
}
void *block_alloc()
{
void *answer = head;
if (answer)
head = head->next;
return answer;
}
void block_free(void *ptr)
{
union block *block = ptr;
block->next = head;
head - block;
}
This scheme is extremely fast and efficient, and can be made generic with a certain loss of clarity.
