Hello again, reader, and welcome back to the series on Memory Management in C++!
In the previous post we went through the process of a basic allocation for our Memory Manager. Via memory dumps, we checked how the memory was laid out as we kept performing allocations. This time we’ll find out how to recover that memory and avoid memory leaks.
Ready, set, go!
Memory after some allocations
If you remember from last post, we ended up having this test case:
And that yielded this memory layout:
Graphically, it means we’ve got this scenario:
So, let’s try to find out how we can deallocate these chunks!
First of all, we need to know what’s the signature of our deallocation function. How about this one?
We only take a pointer to memory, which should have been previously returned by a call to allocate.
The idea is as follows: ensure we’ve received a valid pointer, find the chunk that contains that memory and deallocate it. Or, in code:
Let’s now find out what these methods do individually.
So, first of all, we’ve got to implement isAddressInMemoryRange. Because we’re the ones managing the memory, we know where that memory starts and how many chunks it’s divided into.
Let’s use this knowledge to decide whether the given address is even part of our managed memory.
Alright, step by step!
We’re allowing calls to deallocate with a pointer that’s nullptr. This is part of C99 standard in the free function, so we’ll use it as well.
Next, we check whether the pointer we’ve received is in the range of our managed memory. We know where it starts, we know how long it is, so we can compare those with the given pointer because they’re just numbers (memory positions).
Finally, we also check the pointer isn’t within the first memory chunk header: no user memory can be part of a chunk header.
Now we know the address is in fact part of our managed memory, it’s time to find which chunk it belongs to. Remember that, in this approach we’re using, user memory is laid out right after its chunk header.
So, we need to iterate over the chunks we’ve got until we find the one that contains this address.
Again, when we want to iterate over chunks we have to reinterpret_cast<cMemoryChunk> the pointer to the raw memory we manage so we can access its members more easily.
A valid pointer is the one whose chunk header is located at address - sizeof(cMemoryChunk) or, graphically:
Oh, and don’t forget a valid chunk to deallocate is the one that’s already in use! We can’t deallocate a free one.
Alright, so now that we’ve found the chunk we want to deallocate, it’s time to perform the deallocation itself! How do we do it?
What makes one of our chunks be allocated? You guessed right, the m_isInUse member! We could implement deallocateChunk like so:
Boom! Deallocated! So easy!
Or is it?
Okay, now that we’ve implemented the deallocate method it’s time to test it out. Let’s perform some tests.
Testing range checks
Let’s do this:
As you can see, the memory is left untouched as all of the range checks didn’t allow the deallocation algorithm to continue. Great job!
Testing naive deallocation
What about this one?
Okay, has anything changed? You are right, 0x03231978 had value 0x01 and now it has 0x00 which is the m_isInUse member of our chunk header! Awesome!
Allocating after deallocation
Okay, let’s now allocate again after a deallocation to see how it behaves:
What’s up this time? The first dump shows the first allocation:
While the second one shows the same thing with a 0x00 in the m_isInUse member for the first chunk.
However, the third one shows this layout:
Or, graphically, we have this:
So, before performing the second allocation we had a free chunk with 4 bytes, and another free chunk with 28 bytes. We wanted to allocate 8 bytes, which couldn’t fit in the first free chunk so we had to carve them out of the second one.
Now we have three chunks: a free one with 4 bytes, an in-use one with 8 bytes and a free one with 4 bytes. Or:
What if we now deallocate this second chunk? What will be the memory layout then?
If we continued allocating and deallocating chunks we’d end up having a lot of free chunks with different sizes. It is sure to happen that, eventually, we’ll try to allocate a number of bytes but no existent chunk would have enough free ones to hold them. Even if all of the chunks were set as free!
When this happens, we say the memory is fragmented. We need to try to avoid this situation as much as we can or we’ll be, in fact, wasting memory. Can you think of a way of reducing fragmentation?
Let’s reimplement deallocateChunk with another strategy: try to merge any preceding and following chunks which are free. This way, we avoid having two free chunks next to each other and maximize the memory we’re recovering from a deallocation.
This time, this code is a bit harder to understand. Let’s read it thoroughly.
First of all, we know this cMemoryManager acts as a Doubly Linked List. That means we’ve got a pointer to the previous chunk and another one to the next chunk. We must keep them pointing to the right places at all times.
When deallocating, we want to get the left most chunk that’s free (the one we’re deallocating or its previous one) and know the number of bytes until the next in-use chunk. In chunkToStartDeallocation we store the left most free chunk; in previousChunk we store the one previous to that.
As for the free bytes, we’re recovering the in-use ones from the chunk we’re given. When we have a free previous chunk, we also recover its bytes (which are already free) and our chunk header as it’s being merged. A picture is worth a thousand words, so:
Let’s do the same with the next chunk, if there’s any.
As opposed to the previous chunk, which is guaranteed to exist because of the way we’re creating the chunks, we might not have a next chunk. If that happens, it means we’re the last in the list of chunks.
When we have a following chunk, we have to let it know which chunk is its previous one (might have changed if we merged with the preceding one). Then, we might have to merge it as well if it’s free.
When merging with the next chunk we have to update their pointers and take note of how many bytes we’re recovering. Again, as many bytes as that chunk had (already free) and the header as we’re merging it. Put it graphically, it is:
Phew, we’ve wired everything together, so what is left?
Creating free chunk
Finally, we have to create a new free chunk starting at the left most free chunk and spanning as many bytes as necessary to fill the merged ones.
Nice, now our chunk points to the correct chunks and everything is tied up together.
Bonus: trashing on deallocation
Remember we had the ability to fill memory with some data so we can see the state of the memory when dumping the contents? We can do the same when deallocating!
And that’s it! We’ll have the newly-free bytes set to the given mask (0xDD in our case).
Should we put it to the test? Yes, we should.
Testing deallocation, again
This time, we’ll test several scenarios in an attempt to cover all cases.
Test: single chunk
In the first dump we see what we’re used to: an in-use chunk with 4 bytes, no previous chunk and a next pointer to another chunk that’s free. This time, we’re not using the memory we’re allocating, hence those 0xAA bytes you can see (our trashing mask when allocating).
What about the second dump? We’ve got a single chunk with its m_isInUse member set to false, 0x20 free bytes, previous and next chunk pointers are set to nullptr. Then, all of those 32 free bytes are set to 0xDD: our trashing mask on deallocation so we can see it better.
That means we’ve merged together the chunk we’ve deallocated and the trailing free one.
Great job, test passed!
Test: two chunks, deallocate head
The first dump shows three chunks: an in-use one with 4 bytes (not modified, still with 0xAA), an in-use one also with 4 bytes (also not modified, still with 0xAA) and a free trailing one with 8 free bytes.
We deallocate the first allocation, so the first chunk now appears as free and its 4 bytes are set to 0xDD. Because we didn’t merge anything, all pointers are left untouched and we have: free chunk with 4 bytes, in-use chunk with 4 bytes, free chunk with 8 bytes.
Test: two chunks, deallocate tail
This test is basically the same as the first one, but this time we have a preceding chunk. That chunk is left untouched as our deallocated chunk is merged with the trailing one into a bigger chunk with 0x1C free bytes.
Test: two chunks, deallocate head then tail
This time, let’s mix them together, in an attempt to perform a double merge in a single deallocation.
We already know what the first two dumps are about, so let’s skip them.
In the third dump we’ve performed the double merge: a chunk which had free previous and next chunks. So, we have a single free chunk with 0x30 free bytes and whose previous and next chunks are nullptr. Those 48 free bytes are trashed to 0xDD, and everyone is happy!
So that’s it! Now we know how to deallocate memory from our manager!
As usual, you can find the code we’ve used for this entry here.