3
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Just something that came to mind: perhaps two bit vectors (one bit per minimum allocation unit, e.g. 16 bytes) with one indicating availability and the other bit indicating allocation "color" (bit count=size). (On coalescence, following bits would need to have their color inverted, so such bit vectors might be limited to modest size chunks (e.g., page size) or a sense bit might be used sort of like a carry save avoiding the "carry" of the color inversion through following words of the bit vector.) Freeing would be more expensive (using various base block sizes might help at cost of int. frag.) $\endgroup$ – Paul A. Clayton Dec 24 '15 at 15:43
  • 1
    $\begingroup$ I'll suggest Dynamic Storage Allocation, A Survey and Critical Review, Paul R Wilson et al. as a starting point, the section 3 gives several techniques. $\endgroup$ – AProgrammer Dec 24 '15 at 21:24
  • $\begingroup$ I found the paper and downloaded it. So I will be reading that to see what I can do with this problem that I'm having. $\endgroup$ – Daniel Rudy Dec 26 '15 at 7:17
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As intriguing as your idea is, how do you calculate the address of the next block? I don't think a hash table will work, if I understand your solution correctly. A hash table is good if you already know the next address. An address sorted list seems to be better, but then it becomes a linear search. Right now, the only way that I see how to do this reliably is to do a signature search forward and backward. According to that paper Dynamic Storage Allocation, when using separate free lists, deferred coalescence is a good thing. $\endgroup$ – Daniel Rudy Jan 3 '16 at 7:27
  • $\begingroup$ I have implemented a method to join adjacent blocks that are contiguous in memory if they are on the same list. However, on different lists, a full scan will be needed to do the job. $\endgroup$ – Daniel Rudy Jan 3 '16 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.