At last it has happened! I have been putting off writing my memory allocator for MouthOS for some time. Up to now I’ve been able to survive without one by simply not having any ‘undefined’ data structures - everything in the kernel was a known, static size.

So after a interesting Solaris Advanced Crash Dump Analysis course last week (which has really put me back into my OS development mood) I decided it was time to make a move and I spent a large portion of Friday night working out how to allocate memory without overwriting the existing kernel, and at last by about 2am in the morning having messed around with the linker and some cleverly placed assembly labels I finally was able to kmem_alloc() some memory.

At this point I decided I was finished and went to bed. The next morning I awoke, pleased to have kmem_alloc() working, or so I thought. However, as the day progressed and I allocated more and more pages of memory I started to see some strange things happening. Why did that character on screen just go red? I never put a start on the screen…

After a fair amount of time debugging the issue I managed to isolate the problem. My array of free_pages_t structures were located, not at the end of the kernel stack as I thought (which is currently 8K), but in the last 1K of the stack. Ultimately the problem was a off by one (er, or 1024 depending on how you look at it) error in my programming. At last I was able to kmem_alloc() pretty much as much memory as  I wanted - but how to free.

This proved to be very easy. I simply modified my page_map_t structure to contain a grouping id. As such, when we call kmem_free(void *) we do the following to first make sure that the address we got was on a page boundary.

	while ( (addr % (PAGE_SIZE * 1024) != 0 )
		addr--;

	while ( page->addr != addr )
		page = page->next;

Now we’re on a page boundary we can just loop through the pages whilst the alloc_id’s are equal and set the flags to PAGE_FREE…

	int alloc_id = page->alloc_id;

	while ( page->alloc_id == alloc_id ) {
		page->alloc_id = 0;
		page->flags &= PAGE_FREE;
		page = page->next;
	}

With that working I then spent a bit more time perfecting and tweaking and now MouthOS is pretty good at allocating and freeing memory - at least, I think it is anyway. In the end it turned out not to be so difficult - you just have to get your head around the whole idea of allocating memory, before you have an allocator. When I thought about it this ended up not to be such an issue after-all….  Here is how we can do it.

1. You know the point where your kernel loads.
2. You can work out where your kernel ends by putting a label in its own section, and then using the linker to put that section at the end of the kernel.
3. You now know (from the placed label) where a safe place in the memory is to write without overwriting the existing kernel, so write all your required memory structures, of which you can calculate how many you need from the amount of memory in the system.
4. Finally,go back to your memory structures that you’ve just written and mark all the kernel space as allocated, including the space the memory structures take - which you know as you know the size of a memory struct, you know where it starts, and you know how many you’ve got.

Easy You can find the code for the new MouthOS memory allocator at: http://www.michael-clarke-blog.com/trac/MouthOS  -  if you’re remotely interested :p

Until next time.

This entry was posted on Sunday, June 8th, 2008 at 8:19 pm and is filed under MouthOS, Operating Systems, Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.