And along came this dudes, the Memory System a.k.a. The Evil Heap Twins!

Hey guys, long time without hearing from me, I know, I owe every one of you a big apology. The last weeks were tough, but I came on top, victorious nonetheless. Going back and forward between the four systems, trying to finish them up first, and then doing some tuning and re-coding. As Prof. Keenan says "For every line of code you write, you will be re-writing it at least seven times" (I guess he was right about that last one). So, I will try to write a series of posts this week to summarize my design and implementation of the systems.

Today is all about the Memory System, the Evil Heap Twins. Why twins you may ask? The answer goes like this: this system is a memory manager, and one way to handle this (the Windows' way at least) is trough the use of memory heaps, and in this particular case I will be using two types of heaps: Variable-size Block heaps and Fixed-size Block heaps, hence the name "twin".

Lets talk about the Variable-size type first. For this one I am completely relying on the Win32 Library (Windows.h) for the management and placement of the blocks inside the actual heap, therefore I have no control over how the free space is handled and fragmentation is being solved. I am doing it this way for time reasons, because building this kind of heap from scratch takes much more time than I probably have for this whole project. So, it's all about me finding time in the near future to upgrade this part of the system and manage the whole thing myself. I am writing it down now: it's officially part of my bucket list to port this part of the system to be 100% my creation.

Back to the heap topic. I am using the functions HeapCreate and HeapDestroy for the allocation/destruction of huge blocks of memory to use as my heaps. Everytime one of this heaps is created I place a small block inside called "Heap Header", which stores some basic information about the heap itself (stats): total size, number of blocks allocated, maximum number of blocks allocated, used space, a pointer to the first allocated block in the heap and a pointer to the next heap in the system. All heaps in the system (no matter its type) are connected together by their headers, forming a Linked List which only the Memory System have access to.

Then, as the user requests/free blocks of memory for his pleasure, I allocate/destroy blocks of memory inside the heap. In order to do this, I rely on functions HeapAlloc and HeapFree, which as their name implies just allocate and free space in a previous created heap. These blocks of memory have small headers inside, all of them connected together via pointers (forming a double linked list), and also storing the size of the block and a pointer to the heap header (used later to free the block in constant time). You can have a better idea or understanding of this heap type by looking at the following diagram:

On the right side of the diagram you can have a look at the Fixed-size block heap type (the other evil twin, the less powerful one). This one is a little easier to understand and handle, and the best part is that it is a 100% my creation, no Win32 Library involved (Sweet!). As you might guess, what we have here is a heap that contains an specified (n) number of blocks of the same size. When the heap is created (a simple call to the malloc function), we first store the header at the top of it, then we proceed to divide the rest of the space between the n blocks, all linked together by one pointer in each block header (single linked list), and having the heap header point to the first one.

Once the user requests a block from this heap, the first free block is returned by the Memory System, but behind the scenes two other things happen: the second free block in the list becomes the first (the heap header now points to this one) and the pointer inside the new used block header now points to the heap header instead of the next used block. This pointer is used to return to the heap header from the block, which is done when the user requests to free the block.

For the free operation the user only gives the system the pointer to the block itself (not the block header, which the user actually doesn't know of its existence). So, no matter what type of heap it is, the system must be able to go back from the block to the actual heap, so in order to do this as fast as possible (constant time in my case), we store a pointer to the heap header inside each block header, giving us an speed advantage in exchange for a small storage penalty. Not a bad deal in my opinion.

Well guys (if there is actually anybody reading this apart from me), there you have my memory system, a large post that summarizes a few thousands lines of code in low-level C++. This one is my pride as a programmer, and one that made me realize how little I knew about C++.

See you guys around… Adios!

P.S.: Don't you dare think this is over! I still have to talk about the evil minions of the system! Come back tomorrow for the rest of the story.