How dlmalloc concatenates pieces?

Question

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

The dlmalloc part is reserved by some metadata, which includes information about the amount of space in the piece. Two adjacent free pieces may look like

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

In this case, we want to combine block B into block A. Now how many bytes of free space should the report block?

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

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

But I wonder if this is correct, because I have a tutorial that says that metadata will report 2X bytes , not including the extra space that we get from being able to write on metadata.

Answer 1

You can see the answer yourself by looking at the source . Start with line 1876 to check your chart. Metadata is just two unsigned integers, size_t , accessed by smoothing struct malloc_chunk (line 1847 ). The prev_size field is the size of the previous fragment, and size is the size of this. Both include the size of the struct malloc_chunk . It will be 8 or 16 bytes on almost all machines, depending on whether the code is compiled for 32- or 64-bit addressing.

The "normal case" collage code starts at line 3766 . You can see that the size variable used to track coalescence has a block size.

So - yes - /* consolidate backward */ and /* consolidate forward */ are marked in the code blocks, when it adds the size of the previous and subsequent fragments, it implicitly adds the size of struct malloc_chunk , as you suspected.

This shows that your interpretation is correct. My assumption is that the author of the textbook simply neglected the difference between the block size (including metadata) and the size of the memory block allocated to the user. By the way, malloc makes this difference on line 3397 .

Perhaps the big lesson here is that when you are trying to find out something, you should never miss the opportunity to go directly to the source and figure for yourself.