drchat / buddyalloc Goto Github PK

First of all, thank you for implementing this crate, it seems to be the most readable and documented buddy allocator implementation I could find. It's really helpful.

It would be nice if it allowed to use heap sizes that are not power of two. This can be achieved by splitting the "tail" memory region into smaller blocks and putting them into the respective free lists.

This will cause Heap::buddy function to possibly return pointers that are not part of the heap, but it should be fine, because it's used only in removal. The Heap::free_list_remove will just not find these blocks and will not try to merge them.

Is this reasoning correct or am I missing something? I think I might try to implement this

Without benchmarking it, this is probably the biggest bottleneck of the design (with a large degree of fragmentation, iterating this list will become very slow, incurring a cache miss upon each traversal).

You could fix this by storing metadata outside of the allocated areas and using a doubly linked list to achieve O(1) removal.