OSDev.org

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

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

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
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

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

void* kmalloc(uint32_t bytes) - why not size_t?