Hi guys,
I am writing a microkernel, and i am thinking of using a simple heap allocator for the kernel, and the buddy allocator for userspace. I was wondering what peoples opinions or experiences are, and if you have your own kernel what you use?
Mike Brown
Best Kernel and Userspace Allocator?
Re: Best Kernel and Userspace Allocator?
Microkernels tend to have only a few type of objects and the objects tend to be small (often less than 64 bytes). Allocations and deallocations follow fairly rigid patterns. I tend to think that some form of slab allocator is more suited in kernel space.
Buddy allocators are mainly useful in monolithic kernels where allocated objects can be quite large, even larger than a page and where there are a large number of different sizes needed.
Userspace allocations are far less predictable and so malloc style allocators (see Doug Lea's malloc source in newlib for an example) have proven to be useful. These allocators use all manner of algorithms internally - binning, caching, pre-allocation, deferred coalescing etc. and perform very well.
Buddy allocators are mainly useful in monolithic kernels where allocated objects can be quite large, even larger than a page and where there are a large number of different sizes needed.
Userspace allocations are far less predictable and so malloc style allocators (see Doug Lea's malloc source in newlib for an example) have proven to be useful. These allocators use all manner of algorithms internally - binning, caching, pre-allocation, deferred coalescing etc. and perform very well.
If a trainstation is where trains stop, what is a workstation ?
-
OSwhatever
- Member
- Posts: 595
- Joined: Mon Jul 05, 2010 4:15 pm
Re: Best Kernel and Userspace Allocator?
Inside the kernel you actually need a range of different allocators.
First you need the physical page allocator. Popular algorithms here are bitmaps, buddy algorithm, stacks or a combination of buddy algorithm and stacks.
Then you need the allocator that allocates virtual address space in the kernel. This algorithm should be able to handle arbitrary paged align sizes. Common algorithm used here is an AVL-tree that keeps track of free and used chunks. Also buddy algorithm can be candidate here if you know your kernel doesn't allocate that much space.
Then if necessary you need an allocator that splits the kernel virtual address space into smaller chunks, this is where the slab allocator is handy. With sizes above some threshold, you usually use the kernel virtual address space allocator directly since the slab allocator is mostly suitable for smaller sizes.
First you need the physical page allocator. Popular algorithms here are bitmaps, buddy algorithm, stacks or a combination of buddy algorithm and stacks.
Then you need the allocator that allocates virtual address space in the kernel. This algorithm should be able to handle arbitrary paged align sizes. Common algorithm used here is an AVL-tree that keeps track of free and used chunks. Also buddy algorithm can be candidate here if you know your kernel doesn't allocate that much space.
Then if necessary you need an allocator that splits the kernel virtual address space into smaller chunks, this is where the slab allocator is handy. With sizes above some threshold, you usually use the kernel virtual address space allocator directly since the slab allocator is mostly suitable for smaller sizes.