Table of Contents

[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:

• void *malloc(size_t size)
  Allocates the specified number of bytes, given by size parameter. On success, it returns the pointer to the beginning of the newly allocated block. On failure, it returns the NULL pointer. Note that the content of the allocated memory is not initialized, so may contain random data.
• void* calloc (size_t nmemb, size_t size)
  Allocates the specified number of bytes, given by the number of objects to allocate (nmemb) and the size in bytes of each single object (size). On success, it returns the pointer to the beginning of the newly allocated block. On failure, it returns the NULL pointer. The allocated memory is initialized to 0.
• void *realloc(void *ptr, size_t size)
  Deallocates the memory pointed to by ptr and allocates a new memory space with the specified number of bytes given by size parameter. In other words, it changes the size of the memory pointed to by ptr. In general, it is most often used to enlarge an existing memory region. The content of memory region is preserved up to the lesser of the new and old sizes. If the size of the new memory region is larger, the content of the newly allocated additional memory is not initalized. The behavior is undefined if ptr is not a pointer that has been returned by malloc(), calloc() or realloc() or if it has been already deallocated by realloc() or free().
  On success, it returns the pointer to the beginning of the newly allocated block. On failure, it returns the NULL pointer.
• void free(void *ptr)
  Deallocates the memory pointed to by ptr. It does not do anything if ptr is the NULL pointer. The behavior is undefined if ptr is not a pointer that has been returned by malloc(), calloc() or realloc() or if it has been already deallocated by realloc() or free(). Does not return any value.

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:

• uint32_t size: Size of memory segment in bytes, without size of control data.
• uint8_t used: Flag to store if memory segment is currently allocated (used) or if it is free and ready to be allocated. This is not actually not necessary, but simplifies debugging the heap control data.
• struct MyHeapNodeTypeTag* nextNode: Pointer to next heap entry in list.
• struct MyHeapNodeTypeTag* prevNode: Pointer to previous heap entry in list.

[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.

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

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:

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:

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:

[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:

[Back to top]

3.6 Initialized memory reallocation (calloc)

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

• Instead of specifying the number of bytes to allocate, the number of objects and the size of single objects is given. However, it's only a simple multiplication to get the number of bytes to allocate.
• The allocated memory region is initialized with 0. Using a memset() function, either easily implemented oneself (see source code) or using the higher optimized version of the C standard library, it's just a simple function call.

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

[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:

• uint32_t size: Size of memory segment in bytes, without size of control data.
• struct MyHeapNodeTypeTag* nextNode: Pointer to next heap entry in list.

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:

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:

[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:

[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:

• Alignment was not taken into account yet. For example, it's possible to allocate 11 bytes that could cause alignment problems on some platforms. So as first step, the requested memory size could be rounded up to meet the alignment requirements. If the alignment is a power of two, then the round up is especially easy to implement - the following code snippet rounds up the requested size to a multiple of 8:
  #define ALIGNMENT 8 /* must be power of two */
  /* round up requested size to a multiple of ALIGNMENT - left out possible casting */
  size = (size + (ALIGNMENT - 1)) & ~ALIGNMENT;
  
  
• The example implemenation allows to request very small sizes, e.g. only one byte. This has the drawback that the heap control node structure will occupy more memory than the actual requested memory block. So it could be feasible to either do not allow such small memory requests (just return a NULL pointer), or increase the requested memory size to a minimum value.
  
  
• The implementation is not multithreading capable. If more than one thread would access the heap structure at the same time, it would most likely become inconsistent and thus invalid. To support it, mutual exclusion for accessing the heap would be required inside the memory functions to limit the "simultaneous users" of the heap control structure to one.
  
  
• In general, C memory functions are error prone due to the pointer handling. Therefore only use well-tested implementations.

[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