Dynamic Memory Allocator

Given the following question, with provided answers below:

How can I compute the values in the green outlined areas? I believe I have a pretty solid understanding on how the free() function in C, works and what it does: clears the memory block dynamically allocated on the heap stack (either removing it entirely, or making it free for use, to future allocates).

What I don't understand is how a call to free(0x400b010) changes only some of the other heap blocks above? (those I've outlined with green). I get that the address 0x400b010 (with binary value: 01000000 00001011 01100000 00011100 does not change, as per the assignment its already freed, having 0in its bit 0.

Can anyone explain this to me? For instance the block at address 0x400b00c:0x000000013 changes its value (second argument after :) to 0x00000022, when the free is called upon the block above. This example is just one of the odd cases, where a block that is previously allocated (1 in bit 0) changes to be free, even though no free was called on that address.

Similar some of the blocks change their values while others do not.

I tried to engage this example in many different ways, and I have not been able to crack why the solution looks this way, so I hope someone in here can explain to me what exactly is going on.

The pointers returned by malloc (and then later passed to free) point at the first byte of the user content of the block, NOT at the header (or footer). So to find the header of the block in free, you need to subtract 4 from the pointer argument (the size of the header).

So when free(0x400b010) is called, the first thing is to subtract 4 and get the header of the block at 0x400b00c -- which is 0x13. This tells you that the block is 16 bytes (0x10) and is in use (bit 0 is set) and the previous block is in use (bit 1 is set). As part of freeing it, you need to check if either adjacent block is free. The bit 1 value tells you the previous block is not free, but to check the next block, you need to find it. To do that, you add the size (0x10) to the header address (0x400b00c) to get the next block's header address (0x400b01c), which igives you the header value of 0x12. This block is free, so you add it's size to the current block and mark the current block as free by setting the header of the current block to 0x22 (so it is now a free 32-byte block). You now also need to find the footer of this new coalesced block (at header address + size - 8 == 0x400b024) and change that to 0x22 as well.

It is not necessary to change the old footer of the block or the old header of the following free block that are being colasced, as these are now part of the contents of the free block (which are "don't care" values). Nor is it necessary to touch the previous block, as it is (still) in use.

There's a few odd things about this setup.

• recording the free/in use state of the previous block in bit 1 is an unnecessary complication. You could check it just as well by looking at the footer of the previous block. If it was free, you'd need the previous block's footer value anyways to find its size (and header).
• you really need to know the start and end of the heap in order to not accidentally go off the end checking the previous or next block. If this was the last block on the heap, trying to get the header of the next block would lead to errors as you run of the end of the heap.