Deepesh Menon

Chapter 23 : Implementing A Custom Heap

Key-Words: Custom Heap, Allocating memory from heap, Releasing memory back to heap, Singleton Heap, Custom free store – Overloading new and delete

Topics at a glance:

  • How to implement a custom heap in C++
  • How to overload new and delete to make use of custom heap

In previous chapters we have seen how to implement custom Array class with iterator support, custom unique and shared pointers, custom queues etc. In this chapter, we will implement a custom heap. Heaps are used for dynamically allocating memory regions in course of a program execution. The program releases the memory back to heap once it is done with the usage of the memory. Heaps are usually implemented by the underlying platform usually an OS. C++ abstracts the entire heap management using an entity called the free store along with operators new and delete. But in certain cases, say, a small embedded system with a bare minimal operating system or say, just a bare metal platform where there is no operating system, one cannot use the C++’s default new and delete as there is no heap defined. In such cases when one has to mimic C++’s free store facilities such as new and delete, it is imperative to define your own custom heap. Let us see how to define a custom heap.

Custom Heap

The core logic here is to define a memory region either in BSS or an area in RAM defined in a linker script. This region is our heap memory. Then, we have to define operations for allocating memory from this region and de-allocating (releasing) memory back to this region. Also, to keep track of the memory blocks that are in use and blocks that are free, we will have to define a memory information structure that bears information such as whether a block is free or not, the size of the current block and a pointer to the next block. This resembles a singly-linked list, of course. The only difference being that these memory information blocks are allocated in the custom defined heap memory itself.

Allocating memory from heap

When allocating a new memory, the alloc() function iteratively goes through these memory block info structures and find a free block with adequate size. When the required size is less than the capacity of the block, an additional logic runs to allocate a free memory block at the end of this newly allocated block, as there will be remaining size left after this newly allocated memory block. This logic has to consider two cases mentioned below.

Case 1: Where there is already another block of memory present after this free block. This is analogous to a linked list implementation where one tries to insert one node between two nodes.

Case 2: There is no memory present after this free block. This is like adding a new node in a linked list at the very end.

Releasing memory back to heap

When deallocating memory simply mark the block as free. There is an improvement that could be done here. That is to merge this block with consecutive free memory block. This is not yet implemented in the current version.

Singleton Heap

In C++ implementation, I have defined one Heap class with all the above-mentioned functionalities implemented. One important thing with this implementation is that we cannot have multiple instances of this Heap class. So, the obvious choice here is to make this class a singleton class with a private constructor and a static member function to return the singleton instance of Heap class. But there is a small problem with singleton.

We know that for singleton, get_heap_instance method has to return an instance’s pointer. Constructor of Heap class is made private so that no one outside can instantiate Heap objects directly without get_heap_instance member function. The trick here is to define custom new function for Heap class that will actually allocates this Heap object from a pre-defined memory, either from BSS or from a location defined through linker script.

Custom free store

Now, we have a Heap class, the next step is to define custom new and delete operators for classes for which we want to instantiate objects from this custom heap. For demonstrating this I have defined one class A{}, that defined custom new and custom delete that will use Heap’s alloc and de-alloc functions. Let us see the implementation of our Custom Heap class.

heap.h file:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#ifndef HEAP_H
#define HEAP_H

class Heap
{
private:
	struct mem_info_t
	{
		struct mem_info_t *next;
		size_t size;
		bool is_free;
	};
	
	mem_info_t *root;
	char *heap_end;
private:
	Heap();
	static void* operator new(size_t size);
public:
	~Heap();
	void clear_heap_memory();	
	void* alloc_memory(size_t size);
	bool dealloc_memory(void *this_mem);
	void heap_dump();
	static Heap* get_heap_instance(void);
	
};


#endif /*HEAP_H*/

heap.cpp file

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <iomanip>
#include "heap.h"

using namespace std;

static const size_t max_heap_size = (10 * 1024); // 10 KB

static char heap_memory[max_heap_size];

static char heap_object[sizeof(Heap)];


Heap::Heap()
{
	clear_heap_memory();
	
	// set up the root node mem info structure 
	root = reinterpret_cast<mem_info_t*>(&heap_memory[0]);
	root->next = nullptr;
	root->size = max_heap_size;
	root->is_free = true;	
	
	heap_end = &heap_memory[max_heap_size-1];
	
	cout << "heap initialized" << endl;
}

Heap::~Heap()
{
	clear_heap_memory();
	cout << "Heap destroyed" << endl;
}

void Heap::clear_heap_memory()
{
	for (auto &byte : heap_memory)
	{
		byte = static_cast<char>(0);
	}
	
	return;
}

void* Heap::alloc_memory(size_t size)
{
	char *mem = nullptr;
	mem_info_t *block_info = root;
	// first check whether any free blocks are there 
	do
	{
		// check for free blocks and see whether the size is adequate 
		if( (block_info->is_free == true) && (block_info->size >= size) )
		{
			// found a node 
			// 1. allocate memory block 
			mem = reinterpret_cast<char*>(block_info + 1);
			// 2. update this block information 
			block_info->size = size;
			block_info->is_free = false;
			
			// 3. update mem_info for next block 
			if(block_info->next != nullptr)
			{
				mem_info_t *temp_next = reinterpret_cast<mem_info_t*>(block_info->next);
				// check of enough space is there to accommodate a new empty block in between
				size_t rem_size = size_t( ((size_t)temp_next) - ((size_t)(mem + size)) + ((size_t)1) );
				
				if (rem_size > sizeof(mem_info_t))
				{
					mem_info_t *temp_new = reinterpret_cast<mem_info_t*>(mem + size);
					temp_new->next = temp_next;
					temp_new->is_free = true;
					temp_new->size = rem_size - sizeof(mem_info_t);
					block_info->next = temp_new;
				}
				// else no block can be allocated here 					
			}
			// there is no more block allocated here 
			// check if a new block can be allocated here 
			else if( size_t(mem) + size < size_t(heap_end) )
			{
				
				size_t rem_size = size_t(heap_end) - ( size_t(mem) + size) + size_t(1);
				
				if (rem_size > sizeof(mem_info_t))
				{
					mem_info_t *temp_new = reinterpret_cast<mem_info_t*>(mem + size);
					temp_new->next = nullptr;
					temp_new->is_free = true;
					temp_new->size = rem_size - sizeof(mem_info_t);
					block_info->next = temp_new;
				}
				
			}
			
			break; // exit while loop 
		}
		
		block_info = block_info->next;
		
	}while(block_info != nullptr);
	
	return reinterpret_cast<void*>(mem);
}

bool Heap::dealloc_memory(void *this_mem)
{
	char *mem = reinterpret_cast<char*>(this_mem);
	bool status = false;
	if( (unsigned int)(mem) < (unsigned int)(heap_memory))
	{
		cout << "Invalid memory" << endl;
		return status;
	}
	
	mem_info_t *block_info = root;
	mem_info_t *required_mem_block = reinterpret_cast<mem_info_t*>(mem) - 1;
	
	do
	{
		if(block_info == required_mem_block)
		{
			cout << "found the memory to be deallocated at " << hex << (unsigned int)required_mem_block << endl;
			block_info->is_free = true;
			// clear the memory
			for(int c = 0; c < block_info->size; ++c)
			{
				mem = char(0);
			}
			status = true;
			break; //exit while loop 
		}
		
		block_info = block_info->next;			
		
	}while(block_info != nullptr);
	
	// TODO : To merge with consecutive free blocks 
	
}

void Heap::heap_dump()
{
	int i;
	cout << "\nHeap dump" << endl;
	
	for(auto byte: heap_memory)
	{
		cout << "Byte " << dec << i << " : " << hex << "0x" << (0xFF & (unsigned int)byte) << endl;
	}
	
	cout << endl;
}


static void* Heap::operator new(size_t size)
{
	// size is unused 
	return reinterpret_cast<void*>(heap_object);
}

Heap* Heap::get_heap_instance()
{
	static bool is_init = false;
	static Heap *heap = nullptr;
	
	if(is_init == false)
	{
		heap = new Heap();
		is_init = true;
	}
	
	return heap;
}

Now, let us test this heap.

heap_test.cpp file

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include "heap.h"

using namespace std;

class A
{
private:
	int a_;
public:
	explicit A(int a = 0):a_{a}
	{
		cout << "A created with : " << dec << a_ << endl;
	}
	
	~A()
	{
		cout << "A destroyed" << endl;
	}
	
	static void* operator new(size_t size)
	{
		cout << "Custom new size " << size << endl;
		Heap* heap = Heap::get_heap_instance();
		void *mem_new = heap->alloc_memory(size);
		return mem_new;
	}
		
	static void operator delete(void *mem)
	{
		cout << "Custom delete" << endl;
		Heap* heap = Heap::get_heap_instance();
		heap->dealloc_memory(mem);
		
		return;
	}
};


int main()
{
	char *mem1, *mem2, *mem3, *mem4, *mem5;
	
	Heap* heap = Heap::get_heap_instance();
	
	mem1 = reinterpret_cast<char*>(heap->alloc_memory(200));
	
	if(mem1 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem1 << endl;
		for(int c = 0; c < 200; ++c )
		{
			mem1 = (char)(c);
		}
		
		mem2 = reinterpret_cast<char*>(heap->alloc_memory(100));
		
		if(mem2 != nullptr)
		{
			cout << "second memory allocated at " << hex << (unsigned int)mem2 << endl;
			for(int c = 0; c < 100; ++c )
			{
				mem2 = (char)(c);
			}
		}
		else
		{
			cout << "memory not allocated" << endl;
		}
		
		mem3 = reinterpret_cast<char*>(heap->alloc_memory(300));
		
		if(mem3 != nullptr)
		{
			cout << "second memory allocated at " << hex << (unsigned int)mem3 << endl;
			for(int c = 0; c < 100; ++c )
			{
				mem3 = (char)(c);
			}
		}
		else
		{
			cout << "memory not allocated" << endl;
		}
		
	}
	
	// heap dump 
	//Heap::heap_dump();
	
	if(true == heap->dealloc_memory(mem2))
	{
		cout << "mem2 freed" << endl;
	}
	else
	{
		cout << "mem2 not freed" << endl;
	}
	
	// allocate a new memory 
	
	mem4 = reinterpret_cast<char*>(heap->alloc_memory(30));
	
	if(mem4 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem4 << endl;
	}
	
	mem5 = reinterpret_cast<char*>(heap->alloc_memory(30));
	
	if(mem5 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem5 << endl;
	}
	
	{
		A *a1 = new A(5);
		delete a1;
		
		A a2(10);
	}
	
	
	cout << "main ends" << endl;
	
	return 0;	
	
}

How to compile this using g++:

Invoke the command:

g++ -std=c++14 -I. -o heap_test.exe heap.cpp heap_test.cpp

Result:

heap initialized
memory allocated at 40704c
second memory allocated at 407120
second memory allocated at 407190
found the memory to be deallocated at 407114
mem2 freed
memory allocated at 407120
memory allocated at 40714a
Custom new size 4
A created with : 5
A destroyed
Custom delete
found the memory to be deallocated at 407168
A created with : 10
A destroyed
main ends

Of course there are further improvements as I have already pointed out above. I leave that to you.

Enjoyed the chapter? Let me know in the comments below. Thanks 🙂

Posted in General6 Comments

6 thoughts on “Chapter 23 : Implementing A Custom Heap”

    1. Yes you are right. I could have used standard memcpy(). But thought of restraining from depending upon libraries as much as possible. My intention behind this whole exercise was to show a bare-metal or a scaled down hosting environment. That’s the reason.

      Reply

    2. I meant memset(). iostream/iomanip are used only for cout to show some prints and see the output. Otherwise code on chapter 23 doesn’t use any C++ libraries.

      Reply

  2. What is the practical use of this? You probably will not be able to write any useful c++ code on embedded system which has no operating system.
    Unless you are writing memory manager for os.

    Reply

    1. I have written C++ code on bare metal embedded system platform. You just need C++ run time. Of course RTTI is a far cry. We use memory pools and pool Managers. I think you have not seen any bare metal platform hosting C++ applications before

      Reply

Leave a Reply