There are 3 different ways to keep track of free blocks:
In implicit free list implementation, any block in heap is linked using the block size stored in header. To find a free block, a pointer must traverse from prologue to epilogue by reading the block size in the header of each block and jump to the next block by adding the block size to the current address. The header also store the allocation status of the current block in lower bits (as the lower 4 bits are always 0 if the block size is multiple of 16) for the application to determine if the block is free.
Pros:
simple to implement
not required to occupy freed payload
no need to store additional address data
Cons:
In explicit free list implementation, instead of using block size, free block stores additional 2 address (in total of 16 byte in x86-64, since the client does not use the payload of freed block) in the location of payload. To find a free block, a pointer must traverse through the list by jumping to the next address indicated in the payload. All other operations, such as free and coalesce, must keep the this data structure of linked list.
Pros:
simple to implement
traverse takes O(f) where f is the number of free blocks.
Cons:
required to occupy freed payload
need to store additional address data
more operations used to keep data structure of linked list
increase the minimum size of free block, may lead to more fragmentation
traverse takes O(f) where f is the number of free blocks. (could be more efficient)
Segregated free list is a set of explicit free list each dedicated to store the address of linked list of freed blocks of similar size. In some list of smaller block size, typically only one linked list is dedicated to one size of block. In some list of bigger block size, the size of blocks increases by power of two. To find a free block, the program must traverse the linked list of corresponding block size. If none of the free block has size bigger than required, the program must go to the linked list of bigger block size to traverse again, until it run out of freed blocks or find a free block that fits.
Pros: simple to implement
potentially O(log(f)) where f is the number of free blocks.
first-fit search approximates a best-fit search of explicit free list as the number of linked-list increases
Cons:
required to occupy freed payload
need to store additional address data
increase the minimum size of free block, may lead to more fragmentation
more operations used to keep data structure of linked list
See image below (perhaps next page)
Table of Content