Sign In
Forgot Password?
Sign In | | Create Account

Heap contiguity revisited

Colin Walls

Colin Walls

Posted Oct 12, 2009
0 Comments

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.

Heap, C, Memory, Dynamic Memory, MMU

More Blog Posts

About Colin Walls Follow on Twitter

Colin WallsI have over twenty-five years experience in the electronics industry, largely dedicated to embedded software. A frequent presenter at conferences and seminars and author of numerous technical articles and two books on embedded software, I am a member of the marketing team of the Mentor Graphics Embedded Systems Division, and am based in the UK. Away from work, I have a wide range of interests including photography and trying to point my two daughters in the right direction in life. Learn more about Colin, including his go-to karaoke song and the best parts of being British: http://go.mentor.com/3_acv Visit The Colin Walls Blog

More Posts by Colin Walls

Comments

No one has commented yet on this post. Be the first to comment below.

Add Your Comment

Please complete the following information to comment or sign in.

(Your email will not be published)

Archives

Tags

 
Online Chat