Question about FreeListAllocator

[milanow]

Hi mtrebi,

Thanks for the modification of making it running on Windows first. However I found places that confuse me a lot in FreeListAllocator.

First, is it a must that we have two header type "AdditionalHeader" & "FreeHeader"? I believe an additional header with storing size & padding is enough. And the m_free_list may become type of "SinglyLinkedList", Node type may become "SinglyLinkedList::Node".

Secondly, in the alloc implementation of FreeListAllocator. When adding new block/node due to rest of available memory. Checking "rest > 0" is not enough I believe, because every block must have a header. I checked "rest > sizeof(AdditionalHeader)" instead of "rest > 0", since I only have one additional header. If 0 < rest < sizeof(AdditionalHeader) then we cannot make it a block right?

How do you think of the thoughts above? I am just trying to figure out if it is necessary to have two headers and storing the block size repeatedly. Thanks and would love to hear from you.

[mtrebi]

First of all, my apologies for the soooooo late reply. I've been really busy the last weeks. I am sorry.

Regarding your first question, the answer is Yes. You can use one single struct for both purposes. But, this will (unnecessarily) increase the amount of data used for the FreeList nodes and thus reducing the amount of data that could be potentially used by the allocator. However, is not that bad.

The answer to your second question is Yes, we should make sure that we have enough space to actually create a new node. I totally agree. (Bug spotted). In fact, if there's not enough space we should (a) reject the creation of the data block requested or (b) increase the FreeList size by performing an additional memory allocation by calling malloc.

Thanks for sharing your thoughts!

EDIT:
I've jut read your comment again and at the end you say:

I am just trying to figure out if it is necessary to have two headers and storing the block size repeatedly.

I would like to make sure that there's no confusion about this: Each block size is stored only once in either an AdditionalHeader or a FreeHeader. I decided to use to different structs to make it easier to understand. Maybe it wasnt the right decision...

[m110h]

Secondly, in the alloc implementation of FreeListAllocator. When adding new block/node due to rest of available memory. Checking "rest > 0" is not enough I believe, because every block must have a header. I checked "rest > sizeof(AdditionalHeader)" instead of "rest > 0", since I only have one additional header. If 0 < rest < sizeof(AdditionalHeader) then we cannot make it a block right?

I solved this problem using if (rest >= (sizeof(Node)+alignment)) instead if (rest > 0).