Memory Allocation

Why Memory Allocation Matters

Every non-trivial program asks the runtime for memory it cannot predict at compile time: an incoming packet, a parsed row, a new connection. The memory allocator must answer each such request with a starting address inside the heap — and it must do so quickly, without wasting space, and without ever handing out the same bytes twice. A naive allocator that scans for any hole or always appends to the end of the heap either fragments memory into unusable slivers or fails on requests that would clearly fit.

In practice, allocators sit at the base of every software stack: C library malloc, language runtimes with GC, kernel page allocators (Linux uses the Buddy system for physical pages and Slab-family caches for kernel objects), database buffer pools, and game-engine asset arenas. The placement policy inside the allocator — First Fit, Best Fit, or Worst Fit — directly determines fragmentation behavior and latency. After this lesson you will be able to trace all five strategies (First Fit · Best Fit · Worst Fit · Buddy Allocation · Slab Concepts) on a small heap, implement them in Python, C++, and Java with identical output, state their complexity and correctness invariant, and recognize the fragmentation pitfalls that make real allocators fail.

Memory Allocation solves the placement problem: given a request of $n$ units and a heap carved into allocated and free blocks, find a free block that fits $n$, carve the request out of it, and keep the remainder reusable. The core idea is a free list of unallocated blocks plus a placement policy that decides which hole pays for each request — the policy choice trades scan speed against internal and external fragmentation.

Core Concepts and Terminology

The allocator views the heap as a sequence of blocks, each described by a header recording its start address and size. The bytes not currently owned by any request form the free list — here, an address-sorted list of free blocks. An allocation request $n$ is served by selecting a free block of size $\ge n$ (the placement policy), carving $n$ units from it, and reinserting the remainder. The leftover inside the chosen block, $\text{block} - n$, is internal fragmentation; holes that are individually too small to serve any future request are external fragmentation. Freeing reverses the process: the block is reinserted and coalesced with adjacent free neighbours so the free list stays maximal. Buddy allocation restricts block sizes to powers of two so that split halves and merges are decided by address bits alone; a slab pre-carves fixed-size object caches per type so per-object allocation and free become $O(1)$. The invariant maintained throughout: allocated blocks and free blocks together partition the heap exactly, and no two free blocks touch.

Term	Definition	Role in the Algorithm	Example
Free List	The set of currently unallocated blocks, kept sorted by address.	The allocator's only search space; every policy scans it.	`[(0,8), (20,16), (48,12), (70,10), (100,30)]`
Placement Policy	The rule deciding which fitting free block serves a request.	Determines speed and fragmentation; First / Best / Worst Fit.	First Fit picks `(20,16)` for `n = 10`.
Internal Fragmentation	Leftover space inside an allocated block: $\text{block} - n$.	The price of carving; accumulates as unusable padding.	Allocating 10 from 16 wastes 6 units.
External Fragmentation	Free space that exists in total but in no single block big enough.	The reason allocations fail despite sufficient free bytes.	24 free units in holes of 16 and 8 cannot serve 30.
Coalescing	Merging a freed block with adjacent free neighbours.	Keeps free blocks maximal so large holes reappear.	Freeing at 30 merges with `(30,6)` and `(48,12)`.
Buddy System	Allocation restricted to power-of-two block sizes.	Splitting and merging are decided by one address bit.	Request 10 rounds to 16; 64 splits into 32+32, 16+16.
Slab Cache	A pre-carved pool of fixed-size objects of one type.	Reduces each object allocation to an $O(1)$ freelist pop.	Kernel `inode` caches; per-CPU object magazines.

How Memory Allocation Works, Step by Step

An allocation walks four states, in order. Scan: walk the free list and select a block according to the policy — First Fit stops at the earliest block with size $\ge n$, Best Fit at the smallest such block, Worst Fit at the largest. Split: carve $n$ units from the start of the selected block. Reinsert: if a remainder survives (and clears the minimum block size), push it back into the free list in address order. Record: store the header (start, size) so the eventual free can restore the exact region. Freeing runs the loop mirrored: the block is reinserted in address order, then coalesced left and right so that no two free blocks ever touch. The buddy allocator replaces the arbitrary split with power-of-two rounding — a request for 10 units takes a 16-block, produced by recursively halving larger blocks, and a freed block merges only with its exact mirror-image buddy.

Memory Allocation control flow

flowchart TD
    A[Request of n units] --> B{Policy: First / Best / Worst?}
    B --> C[Scan free list in address order]
    C --> D{Fitting block found?}
    D -- No --> E[Return failure: external fragmentation]
    D -- Yes --> F[Pick block by policy]
    F --> G{Leftover > 0?}
    G -- Yes --> H[Reinsert remainder into free list]
    G -- No --> I[Record header: start and size]
    H --> I
    I --> J[Return start address]
    K[Free: addr and n] --> L[Reinsert block into free list]
    L --> M[Merge with adjacent free neighbours]
    M --> N[Coalesced free list]

Worked Example with a Full Trace

Start from a deliberately fragmented heap of 130 units whose free list is $[(0,8), (20,16), (48,12), (70,10), (100,30)]$, and feed First Fit the request sequence $10, 12, 6, 9$. Each step below scans the free list in address order, carves the request, and reinserts the remainder — the changing free list is highlighted after every row.

Worked Example

Trace It by Hand

Scenario: Take the same fragmented heap — free list $[(0,8), (20,16), (48,12), (70,10), (100,30)]$ — but switch the placement policy to Best Fit. The request sequence is now $10, 12, 9$.

Predict before revealing:

For alloc(10): which block does Best Fit choose, and how much leftover remains?
For alloc(12): which block survives the policy now?
For alloc(9): with only three blocks left, which one wins, and how big is the leftover?
Does the whole sequence waste more or less than First Fit's 9 units?

Answer Verification:

Best Fit scans all fitting blocks and picks the smallest: $(70,10)$ is an exact fit → start = 70, leftover $0$.
With $(70,10)$ gone, the fitting blocks for 12 are $(20,16)$ and $(48,12)$ → the exact $(48,12)$ wins → start = 48, leftover $0$.
Remaining free list is $[(0,8), (20,16), (100,30)]$. The smallest block $\ge 9$ is $(20,16)$ → start = 20, leftover $(29,7)$.
Total internal fragmentation $= 0 + 0 + 7 = 7$ units — less than First Fit's 9 on this input, at the cost of scanning the whole free list on every request.

Implementation in Python, C++, and Java

The programs below implement the three placement policies over one shared free-list engine, plus a buddy allocator with split counting. All three languages run the identical sample heap $[(0,8), (20,16), (48,12), (70,10), (100,30)]$ with requests $10, 12, 6, 9$, then a 64-unit buddy heap with requests $10, 20, 5, 30$, and print byte-identical output.

def fmt(free):
    return "[" + ", ".join(str(s) + ":" + str(z) for s, z in free) + "]"


class PolicyAllocator:
    def __init__(self, free_blocks, mode):
        self.free = sorted(free_blocks)  # address-ordered
        self.mode = mode  # "first", "best", "worst"

    def _select(self, n):
        chosen = None
        for block in self.free:
            if block[1] < n:
                continue
            if chosen is None:
                chosen = block
                if self.mode == "first":
                    break
            elif self.mode == "best" and block[1] < chosen[1]:
                chosen = block
            elif self.mode == "worst" and block[1] > chosen[1]:
                chosen = block
        return chosen

    def alloc(self, n):
        block = self._select(n)
        if block is None:
            return None
        self.free.remove(block)
        start, size = block
        if size > n:
            self.free.append((start + n, size - n))
            self.free.sort()
        return start


class BuddyAllocator:
    def __init__(self, size):
        self.free = [(0, size)]  # sorted by (size, address)
        self.splits = 0

    def alloc(self, n):
        need = 1
        while need < n:
            need *= 2
        idx = -1
        for i, block in enumerate(self.free):
            if block[1] >= need:
                idx = i
                break
        if idx == -1:
            return None
        start, size = self.free.pop(idx)
        while size > need:
            size //= 2
            self.free.append((start + size, size))
            self.splits += 1
        self.free.sort(key=lambda b: (b[1], b[0]))
        return start, need


if __name__ == "__main__":
    requests = (10, 12, 6, 9)
    names = {"first": "First", "best": "Best", "worst": "Worst"}
    for mode in ("first", "best", "worst"):
        alloc = PolicyAllocator([(0, 8), (20, 16), (48, 12),
                                 (70, 10), (100, 30)], mode)
        print("=== " + names[mode] + " Fit ===")
        for n in requests:
            start = alloc.alloc(n)
            label = str(start) if start is not None else "FAIL"
            print("alloc(" + str(n) + ") -> start=" + label
                  + " | free=" + fmt(alloc.free))
        print()

    buddy = BuddyAllocator(64)
    print("=== Buddy (heap = 64) ===")
    for n in (10, 20, 5, 30):
        result = buddy.alloc(n)
        if result is None:
            print("alloc(" + str(n) + ") -> start=FAIL | free=" + fmt(buddy.free))
        else:
            print("alloc(" + str(n) + ") -> start=" + str(result[0])
                  + ", block=" + str(result[1]) + " | free=" + fmt(buddy.free))
    print("total buddy splits = " + str(buddy.splits))

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

typedef std::pair<int, int> Block;  // (start, size)

std::string fmt(const std::vector<Block>& freeBlocks) {
    std::string out = "[";
    for (size_t i = 0; i < freeBlocks.size(); ++i) {
        if (i > 0) out += ", ";
        out += std::to_string(freeBlocks[i].first) + ":" +
               std::to_string(freeBlocks[i].second);
    }
    return out + "]";
}

class PolicyAllocator {
    std::vector<Block> freeBlocks;
    char mode;  // 'f', 'b', 'w'

public:
    PolicyAllocator(std::vector<Block> blocks, char m)
        : freeBlocks(std::move(blocks)), mode(m) {
        std::sort(freeBlocks.begin(), freeBlocks.end());
    }

    int alloc(int n) {
        Block* chosen = nullptr;
        for (Block& b : freeBlocks) {
            if (b.second < n) continue;
            if (chosen == nullptr) {
                chosen = &b;
                if (mode == 'f') break;
            } else if (mode == 'b' && b.second < chosen->second) {
                chosen = &b;
            } else if (mode == 'w' && b.second > chosen->second) {
                chosen = &b;
            }
        }
        if (chosen == nullptr) return -1;
        Block b = *chosen;
        freeBlocks.erase(std::remove(freeBlocks.begin(), freeBlocks.end(), b),
                         freeBlocks.end());
        if (b.second > n) {
            freeBlocks.push_back({b.first + n, b.second - n});
            std::sort(freeBlocks.begin(), freeBlocks.end());
        }
        return b.first;
    }

    const std::vector<Block>& freeList() const { return freeBlocks; }
};

int main() {
    const int requests[4] = {10, 12, 6, 9};
    const char modes[3] = {'f', 'b', 'w'};
    const std::string names[3] = {"First", "Best", "Worst"};

    for (int k = 0; k < 3; ++k) {
        PolicyAllocator alloc({{0, 8}, {20, 16}, {48, 12}, {70, 10}, {100, 30}},
                              modes[k]);
        std::cout << "=== " << names[k] << " Fit ===\n";
        for (int n : requests) {
            int start = alloc.alloc(n);
            std::string label = (start == -1) ? "FAIL" : std::to_string(start);
            std::cout << "alloc(" << n << ") -> start=" << label
                      << " | free=" << fmt(alloc.freeList()) << "\n";
        }
        std::cout << "\n";
    }

    std::vector<Block> buddyFree = {{0, 64}};
    int splits = 0;
    std::cout << "=== Buddy (heap = 64) ===\n";
    const int buddyRequests[4] = {10, 20, 5, 30};
    for (int n : buddyRequests) {
        int need = 1;
        while (need < n) need *= 2;
        int idx = -1;
        for (size_t i = 0; i < buddyFree.size(); ++i) {
            if (buddyFree[i].second >= need) {
                idx = static_cast<int>(i);
                break;
            }
        }
        if (idx == -1) {
            std::cout << "alloc(" << n << ") -> start=FAIL | free="
                      << fmt(buddyFree) << "\n";
            continue;
        }
        Block b = buddyFree[static_cast<size_t>(idx)];
        buddyFree.erase(buddyFree.begin() + idx);
        int start = b.first, size = b.second;
        while (size > need) {
            size /= 2;
            buddyFree.push_back({start + size, size});
            splits++;
        }
        std::sort(buddyFree.begin(), buddyFree.end(),
                   {
                      if (x.second != y.second) return x.second < y.second;
                      return x.first < y.first;
                  });
        std::cout << "alloc(" << n << ") -> start=" << start
                  << ", block=" << need << " | free=" << fmt(buddyFree) << "\n";
    }
    std::cout << "total buddy splits = " << splits << "\n";
    return 0;
}

import java.util.*;

public class Main {

    static String fmt(List<int[]> free) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < free.size(); i++) {
            if (i > 0) sb.append(", ");
            sb.append(free.get(i)[0]).append(":").append(free.get(i)[1]);
        }
        return sb.append("]").toString();
    }

    static final class PolicyAllocator {
        private List<int[]> free;
        private final char mode;  // 'f', 'b', 'w'

        PolicyAllocator(List<int[]> blocks, char mode) {
            this.free = new ArrayList<>(blocks);
            this.mode = mode;
            this.free.sort(Comparator.comparingInt(b -> b[0]));
        }

        int alloc(int n) {
            int[] chosen = null;
            for (int[] b : free) {
                if (b[1] < n) continue;
                if (chosen == null) {
                    chosen = b;
                    if (mode == 'f') break;
                } else if (mode == 'b' && b[1] < chosen[1]) {
                    chosen = b;
                } else if (mode == 'w' && b[1] > chosen[1]) {
                    chosen = b;
                }
            }
            if (chosen == null) return -1;
            free.remove(chosen);
            if (chosen[1] > n) {
                free.add(new int[]{chosen[0] + n, chosen[1] - n});
                free.sort(Comparator.comparingInt(b -> b[0]));
            }
            return chosen[0];
        }

        List<int[]> freeList() { return free; }
    }

    public static void main(String[] args) {
        int[] requests = {10, 12, 6, 9};
        char[] modes = {'f', 'b', 'w'};
        String[] names = {"First", "Best", "Worst"};

        for (int k = 0; k < 3; k++) {
            List<int[]> initial = new ArrayList<>();
            initial.add(new int[]{0, 8});
            initial.add(new int[]{20, 16});
            initial.add(new int[]{48, 12});
            initial.add(new int[]{70, 10});
            initial.add(new int[]{100, 30});
            PolicyAllocator alloc = new PolicyAllocator(initial, modes[k]);
            System.out.println("=== " + names[k] + " Fit ===");
            for (int n : requests) {
                int start = alloc.alloc(n);
                String label = (start == -1) ? "FAIL" : String.valueOf(start);
                System.out.println("alloc(" + n + ") -> start=" + label
                        + " | free=" + fmt(alloc.freeList()));
            }
            System.out.println();
        }

        List<int[]> buddyFree = new ArrayList<>();
        buddyFree.add(new int[]{0, 64});
        int splits = 0;
        System.out.println("=== Buddy (heap = 64) ===");
        int[] buddyRequests = {10, 20, 5, 30};
        for (int n : buddyRequests) {
            int need = 1;
            while (need < n) need *= 2;
            int idx = -1;
            for (int i = 0; i < buddyFree.size(); i++) {
                if (buddyFree.get(i)[1] >= need) {
                    idx = i;
                    break;
                }
            }
            if (idx == -1) {
                System.out.println("alloc(" + n + ") -> start=FAIL | free="
                        + fmt(buddyFree));
                continue;
            }
            int[] b = buddyFree.remove(idx);
            int start = b[0], size = b[1];
            while (size > need) {
                size /= 2;
                buddyFree.add(new int[]{start + size, size});
                splits++;
            }
            buddyFree.sort((x, y) -> x[1] != y[1]
                    ? Integer.compare(x[1], y[1])
                    : Integer.compare(x[0], y[0]));
            System.out.println("alloc(" + n + ") -> start=" + start
                    + ", block=" + need + " | free=" + fmt(buddyFree));
        }
        System.out.println("total buddy splits = " + splits);
    }
}

Complexity, Correctness, and Invariants

Let $F$ be the number of blocks on the free list. First Fit stops at the earliest fitting block: $O(F)$ worst case, but often $O(1)$ on average once small holes accumulate at the front of the heap. Best Fit and Worst Fit always scan the entire free list, so they are $O(F)$ in best, average, and worst case — the price of the smarter placement. Freeing costs $O(F)$ for the address-ordered insert plus coalescing in all three policies. Across a workload of $M$ operations, the total is $O(M \cdot F)$, and since $F$ can grow to $O(N)$ blocks over $N$ allocations, the worst-case bound is $O(N^2)$ for list-based engines; balanced-tree or address-indexed free lists reduce each operation to $O(\log F)$. Buddy allocation spends $O(\log H)$ splitting or merging per operation on a heap of $H$ units, and a slab cache serves each object in $O(1)$ from its pre-carved freelist. Space overhead is $O(F)$ free-list nodes plus $O(1)$ header per allocated block for the list policies, $O(\log H)$ bookkeeping per buddy block, and one fixed array per slab type.

Strategy	Time per Alloc	Time per Free	Fragmentation Behavior	Key Assumption / Property
First Fit	$O(F)$ worst, often $O(1)$	$O(F)$ insert + coalesce	Tends to punch holes at the heap front; fast in practice.	Free list kept address-ordered.
Best Fit	$O(F)$ always (full scan)	$O(F)$ insert + coalesce	Minimal per-request leftover; produces many tiny unusable slivers.	Exact-size blocks preferred on ties.
Worst Fit	$O(F)$ always (full scan)	$O(F)$ insert + coalesce	Keeps large holes open; small requests waste big blocks.	Deliberately splits the largest hole.
Buddy Allocation	$O(\log H)$ split	$O(\log H)$ merge	Internal waste up to $\frac{n}{2} - 1$ from power-of-two rounding.	Only power-of-two block sizes; buddy address symmetry.
Slab Cache	$O(1)$ freelist pop	$O(1)$ freelist push	Zero per-object fragmentation for fixed-size objects.	One cache per object type and size class.

Partition Invariant: at every instant, the heap is exactly partitioned: each byte belongs to precisely one allocated block or one free-list block, and no two free blocks are adjacent. Because any placement policy that carves a request from a single free block and reinserts the exact remainder preserves this partition, and because free reinserts the header-recorded region before coalescing, the allocator can neither lose memory, double-allocate a byte, nor resurrect a stale pointer's region.

Variants, Pitfalls, and Optimizations

Production allocators refine the three textbook policies. Address-ordered first fit with coalescing is the core of the classic Knuth allocator; segregated free lists and size-class bins (glibc's ptmalloc small/large bins, tcache) turn the $O(F)$ scan into a near-$O(1)$ bin lookup; TLSF combines a two-level bitmap over size classes to give real-time first/best fit bounds; the buddy system underlies Linux physical page allocation; and slab-family caches (SLAB, SLUB, per-CPU magazines) layer fixed-size object pools on top of it. The bugs that appear in practice are consistent: forgetting to coalesce on free (the free list fills with unusable slivers), off-by-one split arithmetic that emits zero-size remainders or overlapping blocks, ignoring alignment and header sizes when computing $\text{block} - n$, and returning a block without recording its size so the later free cannot restore it.

Top Implementation Pitfalls:

Skipping Coalescing on Free: reinserting a freed block without merging its adjacent free neighbours leaves the free list full of slivers — external fragmentation grows until large allocations fail even though the total free space suffices.
Split Arithmetic Bugs: computing the remainder as $\text{block} - \text{block}$ vs $\text{block} - n$, or forgetting a minimum block size, yields zero-size or overlapping blocks; always assert $\text{remainder} = \text{size} - n \ge \text{min block}$ before reinserting.
Unrecorded Block Sizes: returning only the start address without storing the size in a header makes free impossible to implement safely — the allocator cannot restore the region it carved, and coalescing loses its boundary information.

Practice Problems and Real-World Use

The placement policies above are exercised directly in teaching labs and power some of the most heavily used subsystems in computing — any system that hands out fixed-size resources under contention is an allocator in disguise.

Problem / System	Core Idea Tested	Difficulty Label
"Design Memory Allocator" (LeetCode-style)	Allocate/free on a fixed array with a free list and exact reuse of freed regions.	Medium
xv6 / teaching-kernel kmalloc	Address-ordered first fit over a linked free list with header bookkeeping.	Medium-Hard
Simulate malloc with fragmentation metrics	Compare First/Best/Worst Fit on the same request stream and measure internal + external waste.	Medium-Hard
Buddy bitmap allocator lab	Implement split/merge using one address bit per order in a bitmap.	Hard
Linux page allocator (buddy)	Power-of-two order splitting and coalescing for physical pages.	Real-World System
Linux SLAB / SLUB caches	Per-type object caches with freelists layered over the buddy allocator.	Real-World System
glibc ptmalloc arenas	Size-class bins, tcache, and chunk coalescing for general-purpose malloc.	Real-World System
Game-engine asset pools	Slab-like fixed-size pools that avoid mid-frame allocation jitter.	Real-World System

Cookie Consent