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 🙂
why no use memset in the clear_heap_memory() function? It should be better than for loop.
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.
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.
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.
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
Also, please refer to some internet resources for further details on bare metal C++. https://arobenko.gitbooks.io/bare_metal_cpp/content/
https://github.com/cortexm/baremetal