Sample implementation of C memory functions

Table of Contents


Download C source code (34 kb)

[Back to top]

1. Introduction

This article shows an example implementation of the C dynamic memory management functions malloc(), free, realloc() and calloc(). It's neither the best nor an efficient implementation, but it could serve as a good starting point - so in case you have ever wondered how to implement these functions, you are at the right place!

[Back to top]

1.1 Dynamic memory allocation

Dynamic memory management comes into play if the needed amount of memory is not known at compile time. A solution is to statically allocate some maximum needed amount of memory, i.e. by declaring an huge array of elements with static size, but that would be a waste of memory if only less memory is actually required. So dynamic memory management is used to allocate and deallocate memory of different sizes during runtime when the memory is actually needed and its size is known.
In general, one large memory region exists that is used to fulfill the different memory requests. This region is often called heap.
The task of the memory management functions is to serve the memory requests by allocating a part of the heap and provide it to the requester. The same applies if the user frees an previously allocated memory region, thus giving it back to the heap.
At any time, the memory mangement functions must keep track of the used and unused memory regions of the heap. Some parts of the heap are in use (thus allocated by the user), while other parts are free, ready to be allocated.

[Back to top]

1.2 Chicken or the egg dilemma

Well, memory is needed to store the current heap control data, as information like the number and size of allocated memory regions must be stored.
Because the number of memory regions allocated by the user depends on the user (actually each application allocates different size and number of memory regions), it would be waste to statically allocate the possible maximum heap control data. However, the memory required for the control data cannot be dynamically allocated because .... yeah because there is no support for dynamic memory allocation yet - it is our goal to implement dynamic memory allocation. So we have an chicken-and-egg problem!
The solution here is to use some of the heap memory for the control data by embedding it in a clever way into the heap area.

[Back to top]

2 C memory functions

The dynamic memory allocation functions which the C standard library provides are as follows:

Let's start to develop a simple exemplary implementation of those functions.

[Back to top]

3 Exemplary implementation


[Back to top]

3.1 Heap control data

A doubly linked list is used to store the heap data. Note that this is not most efficient way, but in my opinion one of the easier ones. See the alternative implementation described in chapter 4 for a more compact way.
The linked list is also stored in the heap area itself. Each item of the linked list, implemented as struct MyHeapNodeTypeTag has following elements:


[Back to top]

3.2 Initialization

The C dynamic memory allocation functions do not have an explicite initialization function, if necessary it is performed by the C startup routine before main() is going to be called.
For our exemplary implementation, the heap itself is a normal array of bytes (unsigned char) with size HEAP_TOTAL_SIZE. Additionally, the define HEAP_NODE_SIZE denotes the size of one heap control data structure and is defined as sizeof(MyHeapNodeType).
The global variable heapStart of type MyHeapNodeType* points to the start of the heap array. The pointer is never modified and does always represent the first node of the list.

static unsigned char MyHeapArea[HEAP_TOTAL_SIZE];
static MyHeapNodeType* heapStart = (MyHeapNodeType *)MyHeapArea;

An initialization function is provided to setup the first node of the heap as follows:

void mem1_init()
{
  heapStart = (MyHeapNodeType *)MyHeapArea;
  heapStart->size = HEAP_TOTAL_SIZE - HEAP_NODE_SIZE;
  heapStart->nextNode = NULL_PTR;
  heapStart->prevNode = NULL_PTR;
}

So actually, the first and only node of the linked list is initialized and is stored at the beginning of the initially completely free heap memory. The size of the available heap memory is the size of the total heap memory, but without the occupied memory of this first node itself.


[Back to top]

3.3 Memory allocation (malloc)

To allocate a new memory region, the heap list is traversed and searched for the best free memory region large enough to hold the request. The best block means the smallest free available block to satisfy the request.
If such a free heap region is found, the new node is created and inserted to the linked list. It holds the information about this memory region, the size and used flag, as well as the pointer to the previous and next heap node. Finally, the pointer to this newly allocated memory region is returned, ready to be used.
After initialization of the heap, without any memory allocated yet, the heap has following structure:


Figure: Empty heap

Above figure shows an empty heap. The grey block denotes the first and only heap node and it occupies some memory of the total heap memory itself.
If a new memory region is requested and the best block is found, it is splitted by inserting a new list node. The new node describes the requested memory region. The found best block is splitted and it's size is decreased accordingly. Its next pointer points to the newly allocated block.

Example:

Example:
A memory region of 100 bytes is requested in an empty heap. The list is traversed, but there is only one node which is not used and is large enough. The free area of the first node is then split, a new list node is inserted at the top of the free area with the requested size, and the next node pointer of the heap start node points to the newly allocated 100 byte memory region. The size of the first heap node decreases by the allocated 100 bytes and by the size of the heap control data of the new node. Figure 2 shows the structure of the heap after allocating the 100 bytes.



Figure: 100 byte memory region allocated

If another memory region of 200 bytes is requested afterwards, the heap would look like the following:



Figure: 100 byte memory region and 200 byte memory region allocated

In the example above, the best block was always the first one, which is always the case at the beginning when the memory regions are requested from an empty heap. Later the heap becomes fragemented, still the allocation will work the same, even if the best block is a region which is encompassed by other regions.
Following source code shows the implemenation of the described memory allocation algorithm:

void * mem1_malloc(size_t size)
{
  MyHeapNodeType* currentHeapBlock;
  MyHeapNodeType* bestHeapBlock;
  uint32_t bestHeapBlockSize;

  /* init current block to start of heap */
  currentHeapBlock = heapStart;
  /* init best heap block */
  bestHeapBlock = (MyHeapNodeType*)NULL_PTR;
  bestHeapBlockSize = HEAP_TOTAL_SIZE + 1; /* init with invalid size */

  while (currentHeapBlock)
  {
    /* check if current block matches and fittest best (so far) */
    if ( (!currentHeapBlock->used) &&
         (currentHeapBlock->size >= (size + HEAP_NODE_SIZE)) &&
         (currentHeapBlock->size <= bestHeapBlockSize) )
    {
      bestHeapBlock = currentHeapBlock;
      bestHeapBlockSize = currentHeapBlock->size;
    }

    currentHeapBlock = currentHeapBlock->nextNode;
  }

  if (bestHeapBlock != NULL_PTR)
  {
    MyHeapNodeType* heapNodeAllocate;

    /* found a matching block, split it up and return the top of the memory area to the user */
    /* the best matching block is decreased by the needed memory area*/
    bestHeapBlock->size = bestHeapBlock->size - size - HEAP_NODE_SIZE;
    /* new heap node is after the current heap + the size of its control data + allocated memory size */
    heapNodeAllocate = (MyHeapNodeType*)(((unsigned char*)bestHeapBlock) + HEAP_NODE_SIZE + bestHeapBlock->size);
    heapNodeAllocate->size = size;
    heapNodeAllocate->used = 1;
    heapNodeAllocate->nextNode = bestHeapBlock->nextNode;
    heapNodeAllocate->prevNode = bestHeapBlock;
    if (bestHeapBlock->nextNode != NULL_PTR)
    {
      /* next block exists */
      bestHeapBlock->nextNode->prevNode = heapNodeAllocate;
    }
    bestHeapBlock->nextNode = heapNodeAllocate;
    /* return pointer to memory of new heap node after control data */
    return (void*)((unsigned char*)heapNodeAllocate + HEAP_NODE_SIZE);
  }

  return NULL_PTR;
}

The pointer that is returned points to the newly allocated memory region that starts directly after the inserted heap control node.


[Back to top]

3.4 Memory deallocation (free)

To deallocate, or free, an allocated memory region, the C function free() is used to which a pointer to an memory region is passed that was previously returned by a malloc() call.
At first, from the provided pointer, the size of a heap control node is subtracted so that is points to the actual heap control list node of the memory region. Then it's marked as free by clearing the used flag, so the memory region is freed.
However, if nothing more would be done afterwards, the heap node would get filled with more and more heap control nodes and their corresponding freed memory regions, resulting in an increasingly fragmented heap. Because in each malloc() call, a new heap control node is created, but in free() the heap control node is just set to unused, somewhen the heap would be filled with heap control nodes and new allocation requests could not be handed.

Now comes the interesting part: If a precedent or successive heap memory region is already set to unused/free, the current memory region to be deallocated can be merged with this region, eliminating an heap control node and resulting in a larger free memory region. If both surrounding memory regions are free, then the current memory region is merged at first with one of them, afterwards the resulting memory region is merged with the second one.

Example:

Assume the heap looks like the following:


Figure: 200 byte memory region, 50 byte memory region and 100 byte memory region allocated

If the 50 byte memory region is now deallocated, it's used flag is set to false. However, whether the precedent nor the successive block is free, so nothing more can be done. So the heap looks like in following figure:



Figure: 200 byte memory region allocated, 50 byte memory region freed and 100 byte memory region allocated

Case A - Deallocating of the 100 byte memory region: If the 100 byte memory region is now deallocated, it's used flag is set to false. The precedent block is free. So the freed memory region can be merged with precedent block, removing the heap control node and merge the freed memory space to the precedent block. There is no successive block. So afterwards, the heap will look like in following figure.



Figure: 200 byte memory region allocated, other two blocks merged to free 150 byte memory region

Case B - Deallocating of the 200 byte memory region (starting again after the 50 bytes region was deallocated):, assume the 200 byte memory region is deallocated. The used flag is set to false, then the surrounding blocks are analyzed: The successive 50byte block is free, so merge the block with this one, resulting in following intermediate heap layout:



Figure: Intermediate heap after merging the 200 byte memory region with successive free 50 byte memory region

The precedent block is also free, so merge the intermediate block with the precedent block. Finally, after deallocating the 200 memory region, the heap looks like in following figure:



Figure: Heap after deallocating the 200 byte memory region

Following source code shows the implemenation of the described memory deallocation algorithm:

void mem1_free(void* p)
{
  if (p == NULL_PTR)
  {
    return;
  }

  /* get actual heap node */
  MyHeapNodeType* currentBlock = (MyHeapNodeType*)((unsigned char*)p - HEAP_NODE_SIZE);

  if (currentBlock == NULL_PTR)
  {
    return;
  }

  currentBlock->used = 0;

  /* check if we can merge with next block */
  if (currentBlock->nextNode != NULL_PTR)
  {
    if (!currentBlock->nextNode->used)
    {
      /* add size of next block and its control data to current block */
      currentBlock->size += currentBlock->nextNode->size;
      currentBlock->size += HEAP_NODE_SIZE;

      /* remove next block */
      /* link current block to next-next block */
      currentBlock->nextNode = currentBlock->nextNode->nextNode;
      /* link next-next block to current block if next-next block exists */
      if (currentBlock->nextNode != NULL_PTR) /* currentBlock->nextNode points to next-next block already! */
      {
        currentBlock->nextNode->prevNode = currentBlock;
      }
    }
  }

  /* check if we can merge with previous block */
  if (currentBlock->prevNode != NULL_PTR)
  {
    if (!currentBlock->prevNode->used)
    {
      /* add size of freed memory region and its control data to previous block */
      currentBlock->prevNode->size += currentBlock->size;
      currentBlock->prevNode->size += HEAP_NODE_SIZE;

      /* remove freed block from list */
      /* link previous block to next block */
      currentBlock->prevNode->nextNode = currentBlock->nextNode;
      /* link next block to previous block if next block exists */
      if (currentBlock->nextNode != NULL_PTR)
      {
        currentBlock->nextNode->prevNode = currentBlock->prevNode;
      }
    }
  }
}

[Back to top]

3.5 Memory reallocation (realloc)

Using the previously described allocation and deallocation functions, the implementation of the realloc() can be realized pretty straightforward. Remember that the task is to resize an already allocated memory region, in general to enlarge it. An easy approach is at follows:

  1. Allocate a new memory region of the requested size.
  2. Copy the content of the existing memory region to the new region.
    • If the new memory region is larger than the existing one, copy the whole content of the existing one to the new one. The content of the remaining new memory region is not initialized.
    • If the new memory region is smaller than the existing one, copy only the part of the existing memory region content that fits into the new memory region.
  3. Deallocate (free) the existing memory region.

The source may look like the following:

void* mem1_realloc(void* ptr, size_t size)
{
  void* p;

  /* allocate new block of requested size */
  p = mem1_malloc(size);
  if (p == NULL_PTR)
  {
    return p; /* return NULL_PTR in case of failure, not original ptr! */
  }

  /* copy buffer of original block */
  if (ptr != NULL_PTR)
  {
    /* get original size of memory block */
    size_t sizeToCopy;
    size_t originalSize = ((MyHeapNodeType* )((unsigned char*)ptr - HEAP_NODE_SIZE))->size;

    /* copy data of original memory block to new one - only valid data is copied */
    if (originalSize < size)
    {
      sizeToCopy = originalSize;
    }
    else
    {
      sizeToCopy = size;
    }
    mem1_memcpy(p, ptr, sizeToCopy);

    /* free original block */
    mem1_free(ptr);
  }

  return p;
}

[Back to top]

3.6 Initialized memory reallocation (calloc)

There are actually only two differences compared to the malloc() function.

Essentially, there is nothing left to say, so here the example source code:

void* mem1_calloc(size_t num, size_t size)
{
  void* p;
  size_t sizeInBytes;

  /* calculate actual memory size in bytes */
  sizeInBytes = num * size;
  /* allocate memory block */
  p = mem1_malloc(sizeInBytes);
  /* initialize memory block to zero */
  if (p != NULL_PTR)
  {
    mem1_memset(p, 0, sizeInBytes);
  }
  return p;
}


[Back to top]

4 Exemplary implementation variant 2


[Back to top]

4.1 Improvements

The used heap control data structure is not really big, but could be more optimized, resulting in less memory overhead especially if a lot of smaller memory regions are allocated.
The size of the memory region is required. Also a possibility to traverse the memory regions is necessary. However, instead of a doubly linked list, a singly linked list is sufficient by adapting the allocation and deallocation algorithms. Also the used flag is not essential; instead only the free available memory regions are kept in the list.
This results in following alternative variant of a node, implemented as new struct MyHeapNodeTypeTag with following reduced elements:

The initalization of the heap is actually the same as in variant 1, just without the removed elements of the optimized node struct, so following figure shows an initialized empty heap:


Figure: Empty heap in variant 2

So let's see how the algorithm and implementation of variant 2 works!


[Back to top]

4.2 Memory allocation (malloc - variant 2)

Actually the allocation algorithm remains nearly the same. Again the heap list is traversed to find the best matching free block. If found, this block is split up and a new block is allocated, similar to the way. However, the next block pointer of this best block will not point to the new block - remember, there is no 'block used' flag anymore and the linked list only contains the free blocks.

Example:

A memory region of 100 bytes is requested in an empty heap. The best (and only) block is split and the new block is allocated. Note that the next pointer of the first block (the one that was split) does not point to the newly allocated block. The heap structure list only holds free blocks. The next figure shows the structure of the heap after allocating the 100 bytes.



Figure: 100 byte memory region allocated in variant 2

If another memory region of 200 bytes is requested afterwards, the heap would look like the following:



Figure: 100 byte memory region and 200 byte memory region allocated in variant 2

As the approach is nearly the same as in variant 1, there is not much left to explain, so here's the implemenation:

void * mem2_malloc(size_t size)
{
  MyHeapNodeType* currentHeapBlock;
  MyHeapNodeType* bestHeapBlock;
  uint32_t bestHeapBlockSize;

  /* init current block to start of heap */
  currentHeapBlock = heapStart;
  /* init best heap block */
  bestHeapBlock = (MyHeapNodeType*)NULL_PTR;
  bestHeapBlockSize = HEAP_TOTAL_SIZE;

  while (currentHeapBlock)
  {
    /* check if current block matches and fittest best (so far) */
    if ( (currentHeapBlock->size >= (size + HEAP_NODE_SIZE)) &&
         (currentHeapBlock->size <= bestHeapBlockSize) )
    {
      bestHeapBlock = currentHeapBlock;
      bestHeapBlockSize = currentHeapBlock->size;
    }

    currentHeapBlock = currentHeapBlock->nextNode;
  }

  if (bestHeapBlock != NULL_PTR)
  {
    MyHeapNodeType* heapNodeAllocate;

    /* found a matching block, split it up and return the top of the memory area to the user */
    /* the best matching block is decreased by the needed memory area */
    bestHeapBlock->size = bestHeapBlock->size - size - HEAP_NODE_SIZE;
    /* new heap node is after the current heap + the size of its control data + allocated memory size */
    heapNodeAllocate = (MyHeapNodeType*)(((unsigned char*)bestHeapBlock) + HEAP_NODE_SIZE + bestHeapBlock->size);
    heapNodeAllocate->size = size;
    /* return pointer to memory of new heap node after control data */
    return (void*)((unsigned char*)heapNodeAllocate + HEAP_NODE_SIZE);
  }

  return NULL_PTR;
}

[Back to top]

4.3 Memory deallocation (free - variant 2)

Now comes the interesting part: How to find the adjacent block to the left and to the right of the block to allocate if it has no links to them? And how to deallocate the block and insert the freed memory region to the heap control list?

The algorithm works as follows:

  1. Find the adjacent free heap nodes:
    The address of the block to deallocate is known. The heap list is traversed from beginning and the address of each heap node is compared to the address of the block to deallocate. This way the 'last' block in the heap can be found that has a lower address than the block to deallocate - that is the block adjacent to the left. From this it follows that the next block of this 'last block' has a higher address than the block to deallocate - that is the block adjacent to the right.
  2. Reinsert the block back to the heap list:
    Having found both neighbor blocks, the block to deallocate is reinserted into the heap list. The next pointer of the block with lower address is set to the block to deallocate. And the next pointer of the block to deallocate is set to the block that followed the 'last block'; of course only if such a block exists.
  3. Merging:
    If the sequence would stop now, the block would has been successfully deallocated and given back to the heap list...
    However, a new node was added to the heap list. This means each time a block is deallocated, a new node is inserted! Of course, this will flood our heap memory with heap nodes and the memory blocks remaining for allocation will get smaller and smaller until no new block can be allocated anymore -> out of memory!

    This means the deallocated block must be merged with the adjacent blocks if possible.

    1. Merging with block to the right:
      If the block to the right exists and it is located exactly after the block to deallocate, both blocks are merged. Actually, the right block is removed from the heap list by adding it's size to the block to deallocate. The next pointer of the deallocated block is set to the block that follows the block to the right.
    2. Merging with block to the left:
      If the block to the left exists and it is located exactly before the block to deallocate, both blocks are merged. Actually, the block to deallocate is removed from the heap list by adding it's size to the block to the left. The next pointer of the left block is set to the block that follows the block to deallocate.

This sounds very complicated, so start with an easy example.

Example:

Assume the heap looks like the following, having only one allocated block that shall be freed:



Figure: Heap with one allocated block in variant 2

First, the heap list is traversed to find the block with the lower address. That's the heap start node. A block to the right does not exist.
Then, the block to deallocate is reinserted into the heap list, resulting in a temporary heap list as following:



Figure: Temporary heap before block to free is merge with the one to the left

Now comes the merge steps. There is no block to the right, so this step is skipped.
The block to the left is adjacent, so remove the block to deallocate by merging it with the left: The size of the deallocated block is added to the left block. And the next pointer of the left block is set the the next pointer of the block to free which is NULL.
Actually this results in exactly the initial empty heap:



Figure: Empty heap

Maybe the previous example is too trivial, so have a look at a more complex example:

Example:

Assume the heap looks like the following. The two red parts are allocated blocks, while the green parts are available heap memory regions. The task is to deallocate the block with 200 bytes.



Figure: Heap where the 200 byte block is freed next

Again, at first the heap list is traversed to find the free adjacent nodes left and right to the node to deallocate. The free block adjecent to the left is the heap start node and the one to the right to block with size 100.
Second step is to reinsert the heap the block to deallocate into the heap list, resulting in a temporary heap list as following:



Figure: Intermediate heap before 200 byte block is merged to the right with the 100 byte block

Now comes the merge steps:
There is a free block to the right, so the deallocated block can be merged with the free block with size 100.
The linked heap start node is free, but it is not directly adjacent to the block to deallocate because the block with size 150 is inbetween, so there is no merge possible to the left side.
This results in the following new final heap list after the block with size 200 is freed:



Figure: Heap after 200 byte block is freed and merged

For completeness, here my implementation of this second free() method:

void mem2_free(void* p)
{
  MyHeapNodeType* prevBlock;
  MyHeapNodeType* nextBlock;

  if (p == NULL_PTR)
  {
    return;
  }

  /* get actual heap node */
  MyHeapNodeType* blockToFree = (MyHeapNodeType*)((unsigned char*)p - HEAP_NODE_SIZE);

  if (blockToFree == NULL_PTR)
  {
    return;
  }

  /* start at beginning of heap, find neighbor block with lower address*/
  prevBlock = NULL_PTR;
  nextBlock = heapStart;
  while ((nextBlock != NULL_PTR) && (nextBlock < blockToFree))
  {
    prevBlock = nextBlock;
    nextBlock = nextBlock->nextNode;
  }

  /* add current block that shall be freed back to heap list */
  blockToFree->nextNode = nextBlock;
  if (prevBlock != NULL_PTR)
  {
    prevBlock->nextNode = blockToFree;
  }

  /* check if block can be merged with right block */
  if ( (nextBlock != NULL_PTR) &&
       ( ((unsigned char*)blockToFree + blockToFree->size + HEAP_NODE_SIZE) == (unsigned char*)nextBlock) )
  {
    blockToFree->size += nextBlock->size + HEAP_NODE_SIZE;
    blockToFree->nextNode = nextBlock->nextNode;
  }

  /* check if block can be merged with left block */
  if ( (prevBlock != NULL_PTR) &&
     ( ((unsigned char*)prevBlock + prevBlock->size + HEAP_NODE_SIZE) == (unsigned char*)blockToFree) )
  {
    prevBlock->size += blockToFree->size + HEAP_NODE_SIZE;
    prevBlock->nextNode = blockToFree->nextNode;
  }
}

[Back to top]

4.4 Memory reallocations (realloc/calloc - variant 2)

As both function realloc() and calloc() were already implemented in variant 1 in such a way that the exact knowledge of the heap control node and list structure is not relevant, the same implementations can also be used for variant 2.


[Back to top]

5. Limitations & outlook

This article has explained two slightly different ways to implement the C memory functions. The goal was to present the algorithms and the examples in an easy-to-understand way and also to show some simple implementation examples.
It works basically, but keep following limitations and notes in mind that were not addressed in the article yet for simplicity:


[Back to top]

6. Conclusion & References

Hope it was interesting for you and you had fun! Drop me a line for corrections, hints, criticism, praise ;)

Sunshine, September 2019

References

[1] C dynamic memory allocation @ Wikipedia
[2] C Standard General Utilities Library