How does dlmalloc coalesce chunks?

Question

Here is a detailed description of the dlmalloc algorithm: http://g.oswego.edu/dl/html/malloc.html

A dlmalloc chunk is bookended by some metadata, which includes information about the amount of space in the chunk. Two contiguous free chunks might look like

[metadata | X bytes free space | metadata ][metadata | X bytes free space | metadata]
                Block A                                     Block B

In that case we want to coalesce block B into block A. Now how many bytes of free space should block A report?

I think it should be 2X + 2 size(metadata) bytes, since now the coalesced block looks like:

[metadata | X bytes free space   metadata  metadata   X bytes free space  | metadata]

But I'm wondering if this is correct, because I have a textbook that says the metadata will report 2X bytes without including the extra space we get from being able to write over the metadata.

Answer 1

You can see the answer yourself by looking at the source. Begin with line 1876 to verify your diagram. The metadata is just two size_t unsigned integers, accessed by aliasing a struct malloc_chunk (line 1847). Field prev_size is the size of the previous chunk, and size is the size of this one. Both include the size of the struct malloc_chunk itself. This will be 8 or 16 bytes on nearly all machines depending on whether the code is compiled for 32- or 64-bit addressing.

The "normal case" coalescing code starts at line 3766. You can see that the size variable it's using to track coalescing is chunk size.

So - yeah - in the code blocks marked /* consolidate backward */ and /* consolidate forward */, when he adds the size of the preceding and succeeding chunks, he's implicitly adding the size of the struct malloc_chunk as you suspected.

This shows that your interpretation is correct. My expectation is that the textbook author just got sloppy about the difference between chunk size (which includes metadata) and the size of the memory block allocated to the user. Incidentally, malloc takes care of this difference at line 3397.

Perhaps the bigger lesson here is that - when you're trying to learn anything - you should never skip an opportunity to go straight to the first-hand source and figure stuff out for yourself.