Module kalloc::cached

Cached multi buddy system

It simply caches the pages used by the underlying buddy system. Assuming to_order is O(1), the allocation is amortized O(logN), worst-case O(N) and O(1) in most cases, which is much faster than O(logN). Deallocation is always O(1) since pages are cached in a freelist instead of returning to the buddy system.

When to use

If the system requires strict bound on running time (e.g. real-time system), use the buddy allocator. Otherwise, use this cached one to achieve faster performance in most scenarios.

Structs

Allocator	A thread-safe allocator with multiple buddy systems.
Cached	Allocator with cached pages.