Skip to content

Power-of-two buddy allocator

Jacob Lorentzon requested to merge 4lDO2/kernel:faster into master

This MR replaces the kernel's frame allocator, with a new linked-list-based O(1) allocator. According to a recent profile, the time spent allocating memory is now reduced from 35% of the samples, to 0.9%, resulting in a very visible reduction in boot time.

Compared to the current RMM BuddyAllocator, this allocator is better integrated into the userspace virtual memory system. It allows reusing the PageInfos of free pages, which normally store the refcount when allocated, to store the prev and next pointers. Since most allocations will occur in the page fault handlers, in 4k units, this linked-list algorithm requires only two get_page_info lookups (one of which would have been necessary anyway to store the refcounts), followed by relinking the list. There is one list per order (order 0 is 4k, order 10 is 4M), and allocations and deallocations are done in LIFO order (FIFO behavior for cold pages can be implemented relatively easily later).

This removes support for non-power-of-two frame allocations, but most kernels including Linux will simply forbid any such requests (instead forcing the use of the regular virtual memory heap, i.e. vmalloc). It would however be useful to implement partial dealloc, which would simplify the phys_contiguous grant code. That would also solve nonaligned allocs up to the MAX_ORDER (4 MiB) limit.

Partial (opportunistic) allocations are still not yet supported, but it should be easy to tweak the allocator to simply select the largest frame of order in [min, max), rather than selecting in [min, MAX_ORDER) as it currently does.

(Adds a stub IDT entry that was used for debugging, which I think is useful anyway, but which can be safely removed otherwise.)

Edited by Jacob Lorentzon

Merge request reports