Welcome back, dear reader!
In the previous post in the series we walked through dumping our big memory chunk to understand its contents. This time we’ll start using this memory to allocate smaller chunks by user request.
Let’s get to it!
What’s a chunk, again?
The idea behind our memory manager was to divide a given big memory chunk into smaller chunks of user-requested size. We decided these smaller memory chunks would look like this:
So, where do we store the memory a user requested? I don’t see any field for it. Glad you asked.
We’re going to treat this
cMemoryChunk struct as the header of the user-requested slice of the total memory we’re managing. The real memory the user requested will be right next to it. Does that sound right?
Let’s check it with an example.
Anatomy of a chunk
Suppose the start of the memory we manage is at
0x00000000 and the user requests 4 bytes from it. We would need to store the
cMemoryChunk header first, and then the 4 bytes we were requested, right?
Assume we already had a method on our manager called
allocate that receives the number of bytes an user has requested. Let’s say we called:
With the previous definition we gave for our chunks, we’d expect the dump to be:
This dump means:
With this in mind, let’s answer some questions so we understand the key points here.
What’s the address of the chunk?
We’re, again, saying the chunk is just the header of the user-requested memory. And we’ve assumed the memory we manage starts at
So that’s it, the chunk starts at
chunk == 0x00000000.
What’s the address of the user-requested memory?
We’d want to keep this header somewhat private to the manager and we don’t want to return its address to the user. Instead, we want to return the start of the
AA:AA:AA:AA we saw in the dump. What’s that address?
In the dump you can see it starts at
0x00000010. More generally, the address is
chunk + sizeof(cMemoryChunk).
Now that we’ve got this straight, let’s implement the
If we remember
malloc, it has the following signature:
Did you notice the
void * return value? That’s the address to the start of the memory the system is returning to the user. With this in mind we’re defining
It’s not exactly the same signature because we’re using
unsigned int instead of
size_t (it is a more explicit type, but type
size_t can be bigger than, equal to or smaller than
unsigned int depending on the platform, so be careful).
First steps on allocation
To obtain the previous dump, we used the following code:
I’m sure you have noticed something wrong already, but let’s understand it step by step and address the problems later.
First of all, we get a pointer to the start of the memory we’re managing into
chunkAddress. We get another pointer to it into
chunk but this time we interpret it as a
cMemoryChunk. This way we can reference its members and treat that slice of the memory as a fully-fledged
What’s the total size of the user-requested memory, then? For each memory request we need to create a header, so we’ll be using
sizeof(cMemoryChunk) + bytes. That’s what we subtract from
m_freeBytesCount, so we can keep track of the remaining free memory.
Do you remember the
AA:AA:AA:AA bytes we had in the previous dump? Checking back the previous entry in the series we defined these trashing options:
This way, we know the memory we’re returning to the user is initialized to something we can easily see in the dump.
Finally, the address we return to the user is the one right after the header, or
chunk + sizeof(cMemoryChunk).
I already heard your brain yelling: okay, okay, but this code only allows to have one chunk at a time!. You are right, that’s the problem I mentioned earlier! Let’s fix that now!
Creating new chunks
For our memory manager, there’s a thing that must hold true at any given time: we need an empty chunk at the tail of the list of chunks. If you remember, the first thing we do when we build the manager is creating an empty chunk.
So, as part of the
allocate method we need to create this trailing empty chunk. How do we do it?
Step by step, again.
Where does the new chunk start? Well, we know a chunk occupies the size of the header and the user-requested memory, right? That’s where we point
We’ve got the address, but we want to interpret that memory as a
cMemoryChunk. This time, we’re building a new
cMemoryChunk in that memory address, so we’re using the placement new instead of reinterpreting the address. But, we see in the code:
cMemoryChunk(chunk->m_bytes - bytes - chunkSize), why is that?
When we build a
cMemoryChunk we tell it how many bytes are free from it and on. Because we always start with an empty chunk, we assume we’ll have the correct number of free bytes until the next chunk or the end of our managed memory.
Again, a chunk occupies the size of the header and the user-requested memory; so the new available memory after the chunk is the one it had, minus the bytes the user requested, minus the memory it takes to allocate a new header for the empty trailing chunk.
Finally, we’ve got to link the new chunk with the previous and next ones. We’ll always have a previous one, as we’ve earlier said this chunk was the tail. However, later on when we deallocate chunks, we can have an empty chunk in between two in-use chunks. When we use that empty space to create a new chunk, we’ll have a following one that’s in use (so the new one isn’t the tail anymore). In other words, it’s a doubly-linked list and we have to keep the links pointing to the right places.
Phew! So, what’s missing? So far we’ve created a new chunk, but if we were to call
allocate several times in a row we would be overriding the same first chunk over and over. What are we missing?
Instead of starting at
m_memory, which is the pointer to the start of the memory we manage, we have to find the first chunk that can store the memory that’s been requested. It can happen that we’ve ran out of usable memory, so we’ll be returning
nullptr when we can’t hand in any memory to the user.
If you double-check, the test
chunk->m_bytes >= (bytes + chunkSize) is using the same total size we mentioned earlier when creating a new chunk.
Allocate method put together
Now that we’ve seen the parts, let’s see the full code of the
We can improve it further and add a new case on the search for a valid chunk. Stay with me as I explain it.
We could also use a free chunk that’s followed by another one even when the user-requested bytes fit in it but a new header doesn’t: we’d skip creating a new header in it, link the chunk to the next one and say it uses as many extra bytes as needed to fill up to the next chunk. Got it? :)
Alright! Let’s see if our hard work yielded something useful! This is our test program:
We’d have these dumps:
First dump: several allocations
Okay, so we’ve performed two allocations: one for a single
unsigned int value and one for 4
int values. In terms of chunks, this would’ve been the step by step evolution:
- We create the memory manager and a single empty chunk with it.
- We perform the first allocation, using the empty chunk and creating an empty one at its tail.
- We perform the second allocation, using the former tail and creating a new empty trailing one.
Is that what we’ve got?
Great! Looks like it’s working! Good job :)
Second dump: user-modified memory
What would happen to the memory when the user modifies the memory we returned? Let’s just focus on the
0xAA bits, which are the ones modified:
Phew, it worked flawlessly! Great job!
Bonus: two’s complement
0xFFFFFFF6 is a negative number in two’s complement. To get the decimal value we’ve got to invert all bits and then add 1 in its binary representation, or subtract the value to its most negative number:
0x100000000 (yes, that’s 9 digits because we’re using a 4-byte number). With that, we’ve got:
The result is
-0x0A, which is
-10 in decimal as we expected.
This is the end of this entry! You can find the code we’ve created here.
In the next entry we’ll explore the deallocation of chunks and which problems arise when doing so.
Thanks a lot for reading!