A Simple, Fragmentation-Proof PMM Design

Physical Memory Manager (PMM) Design Document

Overview

A linked-list based physical memory manager designed for large fragmentation handling. Manages physical memory in contiguous page ranges with self-managing metadata.

Node Structure (16 bytes)

struct pmm_node {
    void* base;             // Physical base address (page-aligned)
    uint32_t count;         // Number of contiguous pages
    void* next;             // Index of next node in current list
    uint32_t self_idx;      // This node's own index in metadata page
} __attribute__((packed));

// 256 nodes per 4K page (4096 / 16 = 256)
// Index 0 reserved as null sentinel

Runtime Pointers

void* free_head;            // Head index of free list
void* allocd_head;          // Head index of allocated list  
void* next_head;            // Head index of free metadata slot list
uint32_t nodes_per_page;    // Bytes per page / Node size

Three Disjoint Lists

1. free - Tracks all unallocated contiguous page ranges
2. allocd - Tracks all allocated contiguous page ranges
3. next - Tracks free metadata slots (recycling)

Invariant: Every metadata slot belongs to exactly one list at all times.

Core Invariants

1. Sorted Order - free and allocd lists are always sorted in ascending order by physical base address. next list is always sorted in ascending order by slot index.
2. Maximally Coalesced - No two adjacent ranges exist in the same list without being merged. Both lists are always fully coalesced.
3. List Separation - free, allocd, and next lists are completely separate. Walking one list never touches nodes from another.

The Problem

Physical memory management has two classic challenges:

1. External fragmentation - Free memory becomes scattered in small pieces
2. Metadata management - The structures tracking memory themselves need storage

The intention: Making a design in which the metadata presents, tracks and manages itself with low overhead.

Core Insight

Track memory in contiguous ranges, not individual pages. Use three independent linked lists:

• free - Available page ranges
• allocd - Allocated page ranges
• next - Available metadata slots

Critical point: The linked lists are only logically seperated, not physically in seperate pages. Two different nodes can exist as neighbours, they just will be separate logically.

The Three Lists

free list: Heads of free physical ranges, sorted by base address
allocd list: Heads of allocated ranges, also sorted by base
next list: Heads of free metadata slots, sorted by slot index

Critical invariant: Every metadata slot belongs to exactly one list at all times.

Why next Is Special

The next list isn't just a freelist - it's a self-monitoring system:

1. Slots are inserted in ascending index order when freed
2. The head is always the smallest available slot (optimal packing)
3. The tail is always the highest available slot
4. If tail index == nodes_per_page - 1 (last slot in page), next allocation needs a new metadata page

Critical note: When the next linked list only has one entry left, it will make a new node just after the entry index. If the slots end there by condition 4, it will do the next allocation. This makes the next null entry ready for use and gives us automatic compaction and built-in expansion detection with zero additional state.

Allocation Logic

When requesting N pages:

1. Traverse free list (sorted by address) looking for range with count ≥ N
2. If exact fit: Remove node from free, insert into allocd (sorted)
3. If larger range found:
   • Pop new slot from next (always smallest available)
   • New node gets original base + N pages, inserted into allocd
   • Existing free node updates base/count
   • Check/merge adjacent in allocd
4. If no usable large enough range found: Return NULL pointer and exit

No bitmap scanning. No power-of-two constraints. Just list operations.

Free Logic

When freeing a previously allocated node:

1. Remove from allocd list
2. Find insertion point in free (by base address)
3. Check adjacency with neighbors:
   • Merge with lower if adjacent
   • Merge with higher if adjacent
   • If both, merge both
4. Recycled nodes go to next (inserted in sorted index order)

Merging logic:

1. If two adjacent nodes are to be merged
   • next of the lower base node will become next of the higher base node
   • count of the lower base node will be incremented by the count of the higher base node
   • The higher base node will be appended to next linked list
2. If a node is added such that it fills the gap between two nodes
   • next of the lowest base node will become next of the highest base node
   • count of the lowest base node will be incremented by the count of the highest and the middle base node
   • The middle and highest base node will be appended to next linked list

Eager coalescing ensures free list stays short and fragmentation never accumulates.

Metadata Expansion

When next list is empty (or tail indicates last slot):

1. Allocate a fresh physical page from free (using the PMM itself)
2. Format it as nodes_per_page new metadata slots
3. Link them into next list
4. Continue with original allocation

This is safe because we always have at least one slot available when we start (the tail warning).

Metadata Pages

• Each metadata page contains nodes_per_page fixed-size slots
• Pages are allocated from the free pool when needed
• New pages are formatted as a chain of free slots linked into next
• The next list's tail (last node) indicates expansion need by the following condition
  • If tail index == nodes_per_page - 1 (last slot in page), next allocation needs new page

Key Design Points

1. Range-based tracking - Minimizes nodes, handles large contiguous regions efficiently
2. Three-list separation - Clean state management, easy debugging
3. Next list recycling - Metadata never leaks, self-monitoring via tail
4. Eager coalescing - Prevents fragmentation in both RAM and metadata
5. Sorted lists - Enables efficient merging and first-fit
6. Index-based addressing - Metadata relocatable, no pointer issues
7. Page-based expansion - Scales with fragmentation, not total RAM

Complexity

• Allocation: O(n) worst-case, amortized O(1) in practice
• Free: O(n) worst-case, amortized O(1) in practice
• Node allocation: O(1) from next list
• Memory overhead: 16 bytes per active range + metadata pages

Invariants Summary

• Lists always sorted appropriately
• No adjacent ranges in same list
• Lists completely disjoint
• Every slot belongs to exactly one list
• next tail indicates expansion need

Why This Works

Simple invariants create complex behavior:

• Sorted lists → efficient merging
• Range tracking → few nodes
• Eager coalescing → short lists
• Next list recycling → no metadata leaks
• Tail monitoring → automatic expansion

Emergent properties:

• Amortized O(1) allocation (first fit hits early nodes)
• Metadata compacts naturally (smallest slots used first)
• Fragmentation impossible (adjacent ranges always merged)
• Self-sizing (more metadata only when fragmentation demands it)

Portability

• No assumptions about paging
• No MMU required
• Works on x86, ARM, RISC-V, embedded
• Just needs physical memory ranges

The Elegance

• Fragmentation can't happen (invariants prevent it)
• Metadata can't leak (next recycles everything)
• Expansion happens automatically (tail tells you when)
• Performance stays fast (lists stay short)

Contact

Author: debug

I would really appreciate you feedback. Feel free to contact me.

License

Released into the public domain under CC0 1.0 Universal
Feel free to use, modify, and distribute without restriction, just make sure to give me credit.