Skip to content

Day90 - Page Allocator

Goal

Implement a simplified Linux-style Buddy Allocator to understand how the kernel manages physical pages, performs page allocation, and minimizes memory fragmentation.

Learning Objectives

After completing this lab, you should understand:

  • Why the Linux kernel manages memory in units of pages
  • The role of struct page
  • Buddy allocation orders
  • Recursive page splitting
  • Buddy block merging
  • Memory fragmentation
  • How kmalloc() is ultimately backed by the Buddy Allocator

Lab1 - Physical Page Initialization

Objective

Implement a simplified physical page manager.

Implementation

Initialize a fixed-size physical page array and create the initial free block.

Implemented:

  • struct page
  • page_allocator_init()
  • dump_pages()

Verification

Verified:

  • Physical page initialization
  • Page metadata
  • Initial Order 6 free block

Lab2 - Buddy Split

Objective

Implement recursive page splitting during allocation.

Implementation

Implemented:

  • alloc_pages(order)
  • Recursive split
  • Allocation order handling

Verification

Verified:

  • Order reduction
  • Recursive split
  • Requested order allocation

Lab3 - Allocation Policy

Objective

Verify Buddy allocation behavior.

Implementation

Allocate multiple page blocks with different orders.

Observe whether the allocator:

  • Reuses existing free blocks
  • Splits larger blocks only when necessary

Verification

Verified:

  • Existing block reuse
  • Split-on-demand policy

Lab4 - Buddy Merge

Objective

Implement recursive buddy merging.

Implementation

Implemented:

  • free_pages()
  • Buddy lookup
  • Recursive merge

Buddy blocks are located using:

buddy_pfn = pfn ^ (1 << order)

Verification

Verified:

  • Buddy detection
  • Recursive merge
  • Recovery to the highest possible order

Implementation Highlights

A simplified Linux-style page allocator was implemented.

Major components include:

  • Physical page metadata (struct page)
  • Page allocation order
  • Buddy split
  • Buddy merge
  • Recursive allocation
  • Recursive merge
  • Page Frame Number (PFN)
  • Buddy address calculation using XOR

Key Takeaways

The Buddy Allocator manages physical memory in units of pages.

Instead of avoiding split and merge operations, it continuously combines adjacent free buddy blocks whenever possible to maintain larger contiguous free regions.

Higher-level allocators such as SLUB obtain physical pages from the Buddy Allocator and further divide them into fixed-size objects used by kmalloc().

  • alloc_pages()
  • free_pages()
  • kmalloc()
  • kzalloc()
  • kcalloc()