sunnysideup wrote:
Hello! I've been making a dynamic memory allocator. I'd love to hear your inputs and suggestions if I'm going wrong somewhere.... The idea is to have a minimal structure allocated at compile time (kernel_heap and kernel_heap_pool). The current implementation has a limited number of entries in the kernel_heap_pool, and perhaps soon I can use some sort of linked list structure to number of entries, where the first pool is allocated at compile time and the rest is a part of the heap itself.
Limiting the number of entries is a bad idea. Having a maximum number of allocations at any one point is a bad move, the heap is supposed to be a general purpose memory allocation, bounded by available memory rather than available statically allocated buffers. I understand you're keeping it simple and it's baby steps, but this sort of structure is just not going to be scalable and you'll soon outgrow it for the following reasons:
* Arbitrary number of allocations, as already mentioned.
* Linear searching of data structures. As you increase the number of allocations, you'll be increasing the size of these linear searches.
* I think the code relies on allocations being stored in address order. If you rely on this going forward, you'll have to maintain the structures in order, which isn't well suited to arrays or linked lists. You'd want a binary tree at least.
* You currently have no locking. When you add locking, and you'll need locking if you ever have more than one thread being able to allocate memory, then you'll have a bottleneck.
Most kernels these days tend to use a slab based allocators, which address many of the above issues:
* Slabs are some multiple of page size, and so it is easy to take an arbitrary pointer and find the container slab and associated structures.
* Slabs provide a natural point of synchronization, so that multiple threads can allocate from different slabs concurrently with minimal contention.
* Allocation and freeing an allocation of a slab chunk involves simple bit map manipulation (fast on most hardware) to find or free the chunk.
The only limitation of slab allocators is the maximum size of a single allocation is somewhat less than the size of your slab, so for allocations that are larger than your slab size, you'll need something else. But these should be rare, because larger allocations tend to be:
* Page based allocations, for things like assigning pages to handle page faults.
* Allocating memory for I/O - Tend to require aligned memory anyway.
These use cases wouldn't suit your allocator either, so this is no big problem. But if you do have bigger allocations, you can defer to an alternative allocator which allocates in multiples of page size, and can be selected based on the allocation size requested.