This is a conceptual issue that I am having in designing an algorithm for a memory allocator that works in conjunction with memory pooling. Free blocks are put on one of several free lists within the pool. The size of the block determines which list it is on. The question is how to figure out if the adjacent physical memory blocks are free and available for coalescing when they are on different lists? Or, in other words, how to figure out if physically adjacent memory blocks are also free when the blocks are on different lists and then combine them.
Granted, the time on this is expensive so I plan to run this only when a suitable block cannot be found or carved out of an existing block.
The only viable approach that I can think of is to scan the entire pool while looking for a signature. Then search all the lists to verify that the address of that block is on a list.
I have done some research and found the following links:
How does worst-fit memory allocation react when encountering contiguous empty memory blocks? http://faculty.kfupm.edu.sa/ICS/saquib/ICS202/Unit34_MemoryManagement.pdf
Any suggestions or ideas?