OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Nov 21, 2017 3:16 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: BMW's Kernel Memory Allocator Version 0.1
PostPosted: Wed Jul 03, 2013 2:41 am 
Offline
Member
Member
User avatar

Joined: Mon Nov 05, 2012 8:31 pm
Posts: 286
Location: New Zealand
Hi all,

I have developed a kernel memory allocator which uses a doubly linked list of headers to store information about memory blocks given out. Feel free to pick the code to bits and give constructive criticism, or use/modify the code (at your own risk).

I have done basic testing and it all seems to work like clockwork.

Please inform me of any mistakes I may have made. This (3 hour) project has been a good learning experience for me, and the satisfaction levels gained when watching it work are very high :D


Attachments:
File comment: BMW's Kernel Memory Allocator v 0.1
kmalloc.c [7.52 KiB]
Downloaded 81 times
File comment: BMW's Kernel Memory Allocator v 0.1 header file.
kmalloc.h [376 Bytes]
Downloaded 52 times

_________________
Currently developing Lithium OS (LiOS).

Recursive paging saves lives.
"I want to change the world, but they won't give me the source code."
Top
 Profile  
 
 Post subject: Re: BMW's Kernel Memory Allocator Version 0.1
PostPosted: Wed Jul 03, 2013 3:18 am 
Offline
Member
Member
User avatar

Joined: Sun Oct 22, 2006 7:01 am
Posts: 2559
Location: Devon, UK
Hi,

I've just quickly skimmed the source, so apologies for any false assumptons on my parse, but a few criticisms:

1. If you attempt to allocate below the basic minimum size, the allocator fails. Why not just round up?
2. The blocks are ordered linearly. This does not appear to make full use of the double linked list. Why not add a "size" field to the header and then maintain the double linked list by block size rather than linearly. This will automatically give you a best fit algorithm.
3. This is going to slow down a lot as it ends up becoming more fragmented (I'm aware you look to merge adjacent blocks on freeing - that's good). You may be better maintaining separate "free" and "allocated" linked lists. When combined with point 2 (best fit), this should make things a lot more scaleable.
4. You allocate physical memory for the entire heap. This will work while the kernel is small, but will could be a waste of physical RAM in the long run. You may want to consider paging in only when a PFE happens. This mechanism may lay a better foundation for your page file in the future. Separating your paging code will also give you a more portable allocator.

If you take the suggestion about maintenance of the double linked list, you may like to create separate functions specifically for list maintenance (add / remove etc). I use C++ and do this with a double linked list template class, but that can easily be adapted to C.

Cheers,
Adam


Top
 Profile  
 
 Post subject: Re: BMW's Kernel Memory Allocator Version 0.1
PostPosted: Wed Jul 03, 2013 3:26 am 
Offline
Member
Member
User avatar

Joined: Mon Nov 05, 2012 8:31 pm
Posts: 286
Location: New Zealand
AJ wrote:
Hi,

I've just quickly skimmed the source, so apologies for any false assumptons on my parse, but a few criticisms:

1. If you attempt to allocate below the basic minimum size, the allocator fails. Why not just round up?
2. The blocks are ordered linearly. This does not appear to make full use of the double linked list. Why not add a "size" field to the header and then maintain the double linked list by block size rather than linearly. This will automatically give you a best fit algorithm.
3. This is going to slow down a lot as it ends up becoming more fragmented (I'm aware you look to merge adjacent blocks on freeing - that's good). You may be better maintaining separate "free" and "allocated" linked lists. When combined with point 2 (best fit), this should make things a lot more scaleable.
4. You allocate physical memory for the entire heap. This will work while the kernel is small, but will could be a waste of physical RAM in the long run. You may want to consider paging in only when a PFE happens. This mechanism may lay a better foundation for your page file in the future. Separating your paging code will also give you a more portable allocator.

If you take the suggestion about maintenance of the double linked list, you may like to create separate functions specifically for list maintenance (add / remove etc). I use C++ and do this with a double linked list template class, but that can easily be adapted to C.

Cheers,
Adam

Thanks! That was exactly the reply I was hoping for!

1. Shouldn't I just remove the minimum feature then? If I were to still allocate requests below the minimum with rounding it up, I might as well just remove the minimum check. I am assuming you were assuming that there was a decent reason for the minimum, I don't know why I even put it in... I guess I'll remove it.
2. You mean I should order them from smallest to largest, then loop through until a large enough block is found? Good idea, this would help reduce fragmentation.
3. Excellent idea, I will add that to the todo list :D
4. Yeah, I will probably do that once I get page swapping happening - sadly that's probably not too soon.

Good idea, I might create a set of linked list functions for my OS :D

_________________
Currently developing Lithium OS (LiOS).

Recursive paging saves lives.
"I want to change the world, but they won't give me the source code."


Top
 Profile  
 
 Post subject: Re: BMW's Kernel Memory Allocator Version 0.1
PostPosted: Wed Jul 03, 2013 3:35 am 
Offline
Member
Member
User avatar

Joined: Sun Oct 22, 2006 7:01 am
Posts: 2559
Location: Devon, UK
Hi,

1. The main reason I can see for keeping the minimum block size is to keep the whole thing 32 bit aligned.
2. Yes :)

Cheers,
Adam


Top
 Profile  
 
 Post subject: Re: BMW's Kernel Memory Allocator Version 0.1
PostPosted: Fri Jul 05, 2013 5:42 am 
Offline

Joined: Mon Oct 29, 2012 1:22 pm
Posts: 10
void* kmalloc(uint32_t bytes) - why not size_t?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group