Heap contiguity revisited

Two weeks ago, I posted a blog about heap contiguity, where I proposed an idea for using an MMU to solve fragmentation problems, which I had previously discussed in a Web seminar. I have worked in the embedded software business for many years and have met and worked with a lot of fine people. It seems that quite a few of the read this blog, which is great.

Two of them contacted me by email following that posting …

I got messages from Peykan Sahelnia and Michael Eager, both of whom politely explained why my idea would not really work. I thought that Michael’s explanation was particularly lucid, so, with his permission, I reproduce it here:

I saw your blog post about using an MMU to remap free memory to combat fragmentation. I don’t think that this will work in general. You’ve just moved the fragmentation problem from physical addresses to virtual addresses.

To use the MMU, you have to create a virtual address space which is mapped to physical memory addresses. Let’s say that you pick a common page size of 4K.

You map the virtual to physical memory using some scheme. Say you have a 10K physical heap and you map it to some virtual memory range much larger than 10K so you can remap as needed.

You allocate 3K, 4K, and 3K, as in your example. You free the two 3K blocks. Your virtual address space is just as fragmented. You cannot remap the two 3K blocks to be contiguous, because your page size is 4K. So the problem is just the same with a virtual address space as with physical.

So you revisit the page size and decide to use 1K pages. Presumably, you can remap the two non- contiguous blocks to be contiguous and allocate a 4K block using a different range of virtual addresses. Works fine for this example. (But your virtual address space is getting fragmented.)

Instead of allocating in 1K increments, allocate 20 512-byte blocks and then free every other block. Half the memory will be free and half will be used, but you will not have any contiguous space from which to allocate a 1K page. It really didn’t matter that you had an MMU; you have the same fragmentation.

I won’t go into the problems of creating a memory manager which allocates virtual address spaces based on the status underlying physical memory. You won’t be using malloc, that’s for sure, or any common allocation scheme.

—

Thanks Michael.

I regard my posting as a success because, even if my idea is not viable, it provoked some discussion, which is indeed success.

I have been thinking about this some more and I am working on a refined approach to using the MMU. I am not done with this, so there may be another part to this story.