Combining adjacent memory blocks 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?
I would suggest keeping a hash table (which you possibly are) to search for addresses.  Use one table for all the different pools.  Do not keep separate tables for each pool.

The idea is that you start from a newly released block. You know its start address and its length.

To find blocks after the newly released one we simply calculate the first address after the block and search for it.  If we find one we join them.

Now we search backwards.

To search backwards our address table must contain not only the start, but the end of blocks.

We search the table for entries matching our end-of-block address.  Again if we find them we join.

If we are doing this check every time we get a newly released block then we do not need to check more than one post- and pre- address block each time.  As these are hash table look-ups they'll be fast.

If we do this check periodically we will need to scan all blocks systematically for matches, including rechecking new joined up super blocks for additional matches.