what the future allocator should look like #4

New issue

Open

opened 2026-09-03 19:55:03 +00:00 by tylercritchlow · 0 comments

tylercritchlow commented

2026-09-03 19:55:03 +00:00

Collaborator

use slab allocation as the top-tier allocator (what is called when you call kalloc()) combined with a low-level buddy page allocator.

slab allocation overview (not comprehensive, based on the wiki page.):

A slab is a contiguous piece of memory, in our case made of one or more pages provided by the buddy allocator. A slab can be empty, partial, or full depending on how many objects inside of it are currently allocated. Slabs belong to a certain cache. A cache in this case manages allocations for a specific type or size of object; for example, an object could be a process structure or another frequently allocated kernel object. If we are allocating the same type or size of object and there is a partial slab belonging to that cache, that slab is used instead of requesting a brand new slab from the buddy allocator. If no slab has enough free space, the cache requests more pages from the buddy allocator and creates a new slab from them.

buddy allocation overview:

First we figure out the smallest block of memory that we want to be possible. That lowest level becomes the order 0 block. From there, order 1, 2, 3, 4, etc. represent powers of two times the size of the order 0 block. For example, if order 0 is 4 KB, then order 1 is 8 KB, order 2 is 16 KB, order 3 is 32 KB, and order 4 is 64 KB. When the slab allocator wants memory, we figure out what order is large enough for the requested number of pages and check whether a free block of that order already exists. For example, suppose the initial state contains one free order 4 block and the slab allocator needs an order 2 block. The buddy allocator will split the order 4 block into two order 3 blocks. It will then split one of those order 3 blocks into two order 2 blocks. One order 2 block is returned to the slab allocator, while the other remains free and can be used by a future allocation.

When memory is freed, the buddy allocator checks whether the freed block's buddy is also free. Two blocks can only be merged if they are buddies: they must be the same order and be the correctly aligned pair that came from the same larger block. If both buddies are free, they are merged back into the next order. The allocator can continue doing this recursively. For example, two free order 0 buddies can merge into an order 1 block. If that new order 1 block's buddy is also free, the two order 1 blocks can merge into an order 2 block, and so on. Free blocks that are the same size but are not buddies cannot be merged.

For a better example of buddy allocation use the wikipedia page example at https://en.wikipedia.org/wiki/Buddy_memory_allocation#Example

ASCII Flow graph:

[kmalloc(64)]
      │
      ▼
[Slab Cache: "kmalloc-64"]
      │
      ├─► Has a page with a free slot? ──YES──► Pop slot from freelist ──► Return pointer
      │
     NO (Cache is empty)
      │
      ▼
[Call Buddy: alloc_pages(order = 0)] ──► Returns 4 KB physical frame
      │
      ▼
[Carve 4 KB Page into 64-byte slots]
      │
      ├─► Store freelist / tracking metadata
      │
      ▼
[Pop first slot] ────────────────────────────────────────────────────────► Return pointer

Step 1 — Buddy page allocator (replaces the free-list).
Step 2 — Page tables / VM.
With a frame source in place, paging can be built on top
Step 3 — Slab allocator (replaces kmalloc at the malloc() boundary).

- https://en.wikipedia.org/wiki/Slab_allocation - https://en.wikipedia.org/wiki/Buddy_memory_allocation use slab allocation as the top-tier allocator (what is called when you call `kalloc()`) combined with a low-level buddy page allocator. slab allocation overview (not comprehensive, based on the wiki page.): A slab is a contiguous piece of memory, in our case made of one or more pages provided by the buddy allocator. A slab can be empty, partial, or full depending on how many objects inside of it are currently allocated. Slabs belong to a certain cache. A cache in this case manages allocations for a specific type or size of object; for example, an object could be a process structure or another frequently allocated kernel object. If we are allocating the same type or size of object and there is a partial slab belonging to that cache, that slab is used instead of requesting a brand new slab from the buddy allocator. If no slab has enough free space, the cache requests more pages from the buddy allocator and creates a new slab from them. buddy allocation overview: First we figure out the smallest block of memory that we want to be possible. That lowest level becomes the order 0 block. From there, order 1, 2, 3, 4, etc. represent powers of two times the size of the order 0 block. For example, if order 0 is 4 KB, then order 1 is 8 KB, order 2 is 16 KB, order 3 is 32 KB, and order 4 is 64 KB. When the slab allocator wants memory, we figure out what order is large enough for the requested number of pages and check whether a free block of that order already exists. For example, suppose the initial state contains one free order 4 block and the slab allocator needs an order 2 block. The buddy allocator will split the order 4 block into two order 3 blocks. It will then split one of those order 3 blocks into two order 2 blocks. One order 2 block is returned to the slab allocator, while the other remains free and can be used by a future allocation. When memory is freed, the buddy allocator checks whether the freed block's buddy is also free. Two blocks can only be merged if they are buddies: they must be the same order and be the correctly aligned pair that came from the same larger block. If both buddies are free, they are merged back into the next order. The allocator can continue doing this recursively. For example, two free order 0 buddies can merge into an order 1 block. If that new order 1 block's buddy is also free, the two order 1 blocks can merge into an order 2 block, and so on. Free blocks that are the same size but are not buddies cannot be merged. For a better example of buddy allocation use the wikipedia page example at https://en.wikipedia.org/wiki/Buddy_memory_allocation#Example ASCII Flow graph: ``` [kmalloc(64)] │ ▼ [Slab Cache: "kmalloc-64"] │ ├─► Has a page with a free slot? ──YES──► Pop slot from freelist ──► Return pointer │ NO (Cache is empty) │ ▼ [Call Buddy: alloc_pages(order = 0)] ──► Returns 4 KB physical frame │ ▼ [Carve 4 KB Page into 64-byte slots] │ ├─► Store freelist / tracking metadata │ ▼ [Pop first slot] ────────────────────────────────────────────────────────► Return pointer ``` - Step 1 — Buddy page allocator (replaces the free-list). - Step 2 — Page tables / VM. With a frame source in place, paging can be built on top - Step 3 — Slab allocator (replaces kmalloc at the malloc() boundary).

tylercritchlow added the

refining

label

2026-09-03 19:58:07 +00:00

tylercritchlow removed the

refining

label

2026-09-06 02:11:22 +00:00