Operating Systems Module 7 – Memory management: addresses, segmentation and paging

Allocating memory: buddy, slab and malloc

How the buddy system splits and merges blocks, how slab caches serve objects, how malloc gets memory from the kernel and how ASan catches misuse.

Advanced
20 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Clang 21.0.0 and GCC 16.2.0
By MySmartCoPilot

Free: The buddy system splits blocks in halves and merges buddies back · A slab cache keeps objects of one size ready · malloc asks the kernel for memory in two ways · Practise: write a buddy allocator. With a pass: 3 in-depth parts and 3 interview answers, about 14 minutes.

What you will learn

Explain the buddy system and compute the splits and merges of a sequence of requests
Explain slab allocation and the role of Linux's SLUB allocator
Describe how malloc gets memory from the kernel with brk and mmap, and when it gives it back
Compute the internal fragmentation of power-of-two blocks and of slabs for given sizes
Find a use after free with AddressSanitizer and check that the fix removes it

Before you start

Contiguous allocation and fragmentation

What you’ll learn · Before you start

What you will learn

Explain the buddy system and compute the splits and merges of a sequence of requests
Explain slab allocation and the role of Linux's SLUB allocator
Describe how malloc gets memory from the kernel with brk and mmap, and when it gives it back
Compute the internal fragmentation of power-of-two blocks and of slabs for given sizes
Find a use after free with AddressSanitizer and check that the fix removes it

Before you start

Contiguous allocation and fragmentation

On this page

Ask a buddy allocator for 129 KiB and it hands out 256 KiB: its blocks come only in powers of two, so almost half of that block is never used. Operating systems keep several allocators because requests come in several shapes: the buddy system for runs of whole pages, slab caches for many objects of one size, and malloc for whatever a program asks for.

You will run a buddy allocator, follow a slab cache serving objects, and trace malloc down to the kernel calls behind it.

The buddy system splits blocks in halves and merges buddies back

A request for 100 KiB from a free arena of 1 MiB splits it in halves three times, 512, 256 and 128 KiB, and takes the lowest 128 KiB block. Every split leaves a free upper half, the buddy system: An allocator whose blocks are powers of two in size: a larger free block is split into two halves, the buddies, and a freed block merges with its buddy again whenever the buddy is free as well. of the half that was kept. Kenneth Knowlton described this scheme in 1965, and two rules make it fast. Blocks are powers of two, so a block of size s at offset a always has its buddy at offset a XOR s. A freed block merges with its buddy whenever the buddy is free, and the merged block may then merge again. The Linux kernel’s page allocator works this way: its documentation describes one free area for each power-of-two order, larger blocks halved until one of the right size is left, and a freed page joined to its buddy. The program runs four requests and four frees over 1 MiB, in 14 languages:

One program · 14 languages A buddy allocator splitting and merging 1 MiB at most one split or merge per order, 7 orders here

Python 3.14 · main.py

MIN, ORDERS = 16, 7
# Sizes in KiB; 0 frees the block of that name.
STEPS = [("A", 100), ("B", 20), ("C", 200), ("D", 40), ("B", 0), ("A", 0)]
STEPS += [("D", 0), ("C", 0)]

# free[k][i]: block i of 16 KiB << k is free.
free = [[False] * (1 << (ORDERS - 1 - k)) for k in range(ORDERS)]
free[ORDERS - 1][0] = True
used: dict[str, tuple[int, int]] = {}  # name -> (order, block)


def allocate(name: str, kib: int) -> str:
    order = 0
    while MIN << order < kib:
        order += 1
    k = order
    while not any(free[k]):
        k += 1
    i = free[k].index(True)
    free[k][i] = False
    while k > order:  # split; the upper half, its buddy, stays free
        k, i = k - 1, i * 2
        free[k][i + 1] = True
    used[name] = (order, i)
    size = MIN << order
    return f"{name} {kib} KiB -> {size} KiB at {i * size}"


def release(name: str) -> str:
    order, i = used.pop(name)
    size = MIN << order
    while order < ORDERS - 1 and free[order][i ^ 1]:  # the buddy is free: merge
        free[order][i ^ 1] = False
        order, i = order + 1, i // 2
    free[order][i] = True
    return f"free {name}: {size} KiB back"


for name, kib in STEPS:
    print(allocate(name, kib) if kib else release(name))
    sizes = [MIN << k for k in range(ORDERS)]
    blocks = [
        f"{s}@{i * s}" for s, row in zip(sizes, free) for i, f in enumerate(row) if f
    ]
    print("  free: " + " ".join(blocks))

In Python: free holds one list of booleans per order; free[k].index(True) finds the lowest free block, and i ^ 1 is the number of a block's buddy.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const MIN = 16;
const ORDERS = 7;
// Sizes in KiB; 0 frees the block of that name.
const STEPS = [
  ["A", 100],
  ["B", 20],
  ["C", 200],
  ["D", 40],
  ["B", 0],
  ["A", 0],
];
STEPS.push(["D", 0], ["C", 0]);

// free[k][i]: block i of 16 KiB << k is free.
const free = Array.from({ length: ORDERS }, (_, k) => new Array(1 << (ORDERS - 1 - k)).fill(false));
free[ORDERS - 1][0] = true;
const used = new Map(); // name -> [order, block]

function allocate(name, kib) {
  let order = 0;
  while (MIN << order < kib) order += 1;
  let k = order;
  while (!free[k].includes(true)) k += 1;
  let i = free[k].indexOf(true);
  free[k][i] = false;
  while (k > order) {
    // split; the upper half, its buddy, stays free
    k -= 1;
    i *= 2;
    free[k][i + 1] = true;
  }
  used.set(name, [order, i]);
  const size = MIN << order;
  return `${name} ${kib} KiB -> ${size} KiB at ${i * size}`;
}

function release(name) {
  let [order, i] = used.get(name);
  used.delete(name);
  const size = MIN << order;
  while (order < ORDERS - 1 && free[order][i ^ 1]) {
    free[order][i ^ 1] = false; // the buddy is free: merge
    order += 1;
    i >>= 1;
  }
  free[order][i] = true;
  return `free ${name}: ${size} KiB back`;
}

for (const [name, kib] of STEPS) {
  console.log(kib ? allocate(name, kib) : release(name));
  const blocks = free.flatMap((row, k) =>
    row.flatMap((isFree, i) => (isFree ? [`${MIN << k}@${i * (MIN << k)}`] : [])),
  );
  console.log(`  free: ${blocks.join(" ")}`);
}

In JavaScript: i ^ 1 flips the lowest bit of a block number, which gives its buddy, and i >>= 1 halves the number when two buddies merge.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
  static final int MIN = 16;
  static final int ORDERS = 7;
  // Sizes in KiB; 0 frees the block of that name.
  static final String[] NAMES = {"A", "B", "C", "D", "B", "A", "D", "C"};
  static final int[] SIZES = {100, 20, 200, 40, 0, 0, 0, 0};
  // free[k] holds the numbers of the free blocks of 16 KiB << k.
  static final BitSet[] free = new BitSet[ORDERS];
  static final Map<String, Block> used = new HashMap<>(); // name -> its block

  record Block(int order, int index) {}

  static String allocate(String name, int kib) {
    int order = 0;
    while (MIN << order < kib) {
      order++;
    }
    int k = order;
    while (free[k].isEmpty()) {
      k++;
    }
    int i = free[k].nextSetBit(0);
    free[k].clear(i);
    while (k > order) { // split; the upper half, its buddy, stays free
      k--;
      i *= 2;
      free[k].set(i + 1);
    }
    used.put(name, new Block(order, i));
    int size = MIN << order;
    return name + " " + kib + " KiB -> " + size + " KiB at " + i * size;
  }

  static String release(String name) {
    Block block = used.remove(name);
    int order = block.order();
    int i = block.index();
    int size = MIN << order;
    while (order < ORDERS - 1 && free[order].get(i ^ 1)) { // the buddy is free: merge
      free[order].clear(i ^ 1);
      order++;
      i /= 2;
    }
    free[order].set(i);
    return "free " + name + ": " + size + " KiB back";
  }

  public static void main(String[] args) {
    for (int k = 0; k < ORDERS; k++) {
      free[k] = new BitSet();
    }
    free[ORDERS - 1].set(0);
    for (int step = 0; step < NAMES.length; step++) {
      int kib = SIZES[step];
      System.out.println(kib > 0 ? allocate(NAMES[step], kib) : release(NAMES[step]));
      List<String> blocks = new ArrayList<>();
      for (int k = 0; k < ORDERS; k++) {
        int size = MIN << k;
        free[k].stream().forEach(i -> blocks.add(size + "@" + i * size));
      }
      System.out.println("  free: " + String.join(" ", blocks));
    }
  }
}

In Java: Each order's free blocks are a java.util.BitSet, so nextSetBit(0) finds the lowest free block and stream() lists the free ones.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <format>
#include <map>
#include <print>
#include <string>
#include <utility>
#include <vector>

constexpr int MIN = 16;
constexpr int ORDERS = 7;
// Sizes in KiB; 0 frees the block of that name.
const std::vector<std::pair<char, int>> STEPS{{'A', 100}, {'B', 20}, {'C', 200},
                                              {'D', 40},  {'B', 0},  {'A', 0},
                                              {'D', 0},   {'C', 0}};

// free_[k][i]: block i of 16 KiB << k is free.
std::vector<std::vector<bool>> free_;
std::map<char, std::pair<int, int>> used; // name -> (order, block)

std::string allocate(char name, int kib) {
  int order = 0;
  while ((MIN << order) < kib) {
    ++order;
  }
  int k = order;
  while (std::ranges::find(free_[k], true) == free_[k].end()) {
    ++k;
  }
  int i =
      static_cast<int>(std::ranges::find(free_[k], true) - free_[k].begin());
  free_[k][i] = false;
  while (k > order) { // split; the upper half, its buddy, stays free
    --k;
    i *= 2;
    free_[k][i + 1] = true;
  }
  used[name] = {order, i};
  const int size = MIN << order;
  return std::format("{} {} KiB -> {} KiB at {}", name, kib, size, i * size);
}

std::string release(char name) {
  auto [order, i] = used[name];
  used.erase(name);
  const int size = MIN << order;
  while (order < ORDERS - 1 &&
         free_[order][i ^ 1]) { // the buddy is free: merge
    free_[order][i ^ 1] = false;
    ++order;
    i /= 2;
  }
  free_[order][i] = true;
  return std::format("free {}: {} KiB back", name, size);
}

int main() {
  for (int k = 0; k < ORDERS; ++k) {
    free_.emplace_back(1 << (ORDERS - 1 - k), false);
  }
  free_[ORDERS - 1][0] = true;
  for (const auto &[name, kib] : STEPS) {
    std::println("{}", kib > 0 ? allocate(name, kib) : release(name));
    std::string blocks;
    for (int k = 0; k < ORDERS; ++k) {
      for (int i = 0; i < static_cast<int>(free_[k].size()); ++i) {
        if (free_[k][i]) {
          blocks += std::format(" {}@{}", MIN << k, i * (MIN << k));
        }
      }
    }
    std::println("  free:{}", blocks);
  }
}

In C++: std::vector<bool> stores one bit per block, and std::ranges::find gives the first free one.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

const int Min = 16;
const int Orders = 7;
// Sizes in KiB; 0 frees the block of that name.
(string Name, int Kib)[] steps =
[
    ("A", 100), ("B", 20), ("C", 200), ("D", 40), ("B", 0), ("A", 0), ("D", 0), ("C", 0),
];

// free[k][i]: block i of 16 KiB << k is free.
bool[][] free = [.. Enumerable.Range(0, Orders).Select(k => new bool[1 << (Orders - 1 - k)])];
free[Orders - 1][0] = true;
var used = new Dictionary<string, (int Order, int Block)>();

foreach (var (name, kib) in steps)
{
    Console.WriteLine(kib > 0 ? Allocate(name, kib) : Release(name));
    var blocks = Enumerable.Range(0, Orders).SelectMany(k => Enumerable.Range(0, free[k].Length)
        .Where(i => free[k][i]).Select(i => $"{Min << k}@{i * (Min << k)}"));
    Console.WriteLine($"  free: {string.Join(' ', blocks)}");
}

string Allocate(string name, int kib)
{
    int order = 0;
    while (Min << order < kib)
    {
        order++;
    }
    int k = order;
    while (!free[k].Contains(true))
    {
        k++;
    }
    int i = Array.IndexOf(free[k], true);
    free[k][i] = false;
    while (k > order) // split; the upper half, its buddy, stays free
    {
        k--;
        i *= 2;
        free[k][i + 1] = true;
    }
    used[name] = (order, i);
    int size = Min << order;
    return $"{name} {kib} KiB -> {size} KiB at {i * size}";
}

string Release(string name)
{
    var (order, i) = used[name];
    used.Remove(name);
    int size = Min << order;
    while (order < Orders - 1 && free[order][i ^ 1]) // the buddy is free: merge
    {
        free[order][i ^ 1] = false;
        order++;
        i /= 2;
    }
    free[order][i] = true;
    return $"free {name}: {size} KiB back";
}

In C#: free is a jagged array, bool[][], with one row per order, and Array.IndexOf finds the first free block of a row.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>

enum { MIN = 16, ORDERS = 7 };
// Sizes in KiB; 0 frees the block of that name.
static const char NAMES[] = "ABCDBADC";
static const int SIZES[] = {100, 20, 200, 40, 0, 0, 0, 0};

// free_block[k][i]: block i of 16 KiB << k is free.
static bool free_block[ORDERS][1 << (ORDERS - 1)];
static int used_order[26], used_block[26]; // indexed by name

static int first_free(int k) {
  for (int i = 0; i < 1 << (ORDERS - 1 - k); i++) {
    if (free_block[k][i]) {
      return i;
    }
  }
  return -1;
}

static void allocate(char name, int kib) {
  int order = 0;
  while ((MIN << order) < kib) {
    order++;
  }
  int k = order;
  while (first_free(k) < 0) {
    k++;
  }
  int i = first_free(k);
  free_block[k][i] = false;
  while (k > order) { // split; the upper half, its buddy, stays free
    k--;
    i *= 2;
    free_block[k][i + 1] = true;
  }
  used_order[name - 'A'] = order;
  used_block[name - 'A'] = i;
  const int size = MIN << order;
  printf("%c %d KiB -> %d KiB at %d\n", name, kib, size, i * size);
}

static void release(char name) {
  int order = used_order[name - 'A'], i = used_block[name - 'A'];
  const int size = MIN << order;
  while (order < ORDERS - 1 && free_block[order][i ^ 1]) { // merge with buddy
    free_block[order][i ^ 1] = false;
    order++;
    i /= 2;
  }
  free_block[order][i] = true;
  printf("free %c: %d KiB back\n", name, size);
}

int main(void) {
  free_block[ORDERS - 1][0] = true;
  for (int step = 0; NAMES[step] != '\0'; step++) {
    if (SIZES[step] > 0) {
      allocate(NAMES[step], SIZES[step]);
    } else {
      release(NAMES[step]);
    }
    printf("  free:");
    for (int k = 0; k < ORDERS; k++) {
      for (int i = 0; i < 1 << (ORDERS - 1 - k); i++) {
        if (free_block[k][i]) {
          printf(" %d@%d", MIN << k, i * (MIN << k));
        }
      }
    }
    printf("\n");
  }
  return 0;
}

In C: The names are single letters, so the blocks in use are kept in two small arrays indexed by name minus the letter A.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const MIN = 16;
const ORDERS = 7;
// Sizes in KiB; 0 frees the block of that name.
const STEPS = [
    ['A', 100], ['B', 20], ['C', 200], ['D', 40], ['B', 0], ['A', 0], ['D', 0], ['C', 0],
];

/** @param list<list<bool>> $free @param array<string, array{int, int}> $used */
function allocate(array &$free, array &$used, string $name, int $kib): string
{
    $order = 0;
    while (MIN << $order < $kib) {
        $order++;
    }
    $k = $order;
    while (!in_array(true, $free[$k], true)) {
        $k++;
    }
    $i = (int) array_search(true, $free[$k], true);
    $free[$k][$i] = false;
    while ($k > $order) { // split; the upper half, its buddy, stays free
        $k--;
        $i *= 2;
        $free[$k][$i + 1] = true;
    }
    $used[$name] = [$order, $i];
    $size = MIN << $order;
    return sprintf('%s %d KiB -> %d KiB at %d', $name, $kib, $size, $i * $size);
}

/** @param list<list<bool>> $free @param array<string, array{int, int}> $used */
function release(array &$free, array &$used, string $name): string
{
    [$order, $i] = $used[$name];
    unset($used[$name]);
    $size = MIN << $order;
    while ($order < ORDERS - 1 && $free[$order][$i ^ 1]) { // the buddy is free: merge
        $free[$order][$i ^ 1] = false;
        $order++;
        $i = intdiv($i, 2);
    }
    $free[$order][$i] = true;
    return "free {$name}: {$size} KiB back";
}

// $free[$k][$i]: block $i of 16 KiB << $k is free.
$free = array_map(
    fn(int $k): array => array_fill(0, 1 << (ORDERS - 1 - $k), false),
    range(0, ORDERS - 1),
);
$free[ORDERS - 1][0] = true;
$used = [];
foreach (STEPS as [$name, $kib]) {
    echo ($kib > 0 ? allocate($free, $used, $name, $kib) : release($free, $used, $name)) . "\n";
    $blocks = [];
    foreach ($free as $k => $row) {
        foreach (array_keys($row, true, true) as $i) {
            $blocks[] = (MIN << $k) . '@' . $i * (MIN << $k);
        }
    }
    echo '  free: ' . implode(' ', $blocks) . "\n";
}

In PHP: The free maps and the blocks in use are passed by reference, &$free and &$used, so that the functions can change them.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

use std::collections::HashMap;

const MIN: usize = 16;
const ORDERS: usize = 7;
// Sizes in KiB; 0 frees the block of that name.
const NAMES: &str = "ABCDBADC";
const SIZES: [usize; 8] = [100, 20, 200, 40, 0, 0, 0, 0];

fn allocate(free: &mut [Vec<bool>], kib: usize) -> Option<(usize, usize)> {
    let order = (0..ORDERS).find(|&k| MIN << k >= kib)?;
    let mut k = (order..ORDERS).find(|&k| free[k].contains(&true))?;
    let mut i = free[k].iter().position(|&f| f)?;
    free[k][i] = false;
    while k > order {
        k -= 1; // split; the upper half, its buddy, stays free
        i *= 2;
        free[k][i + 1] = true;
    }
    Some((order, i))
}

fn release(free: &mut [Vec<bool>], mut order: usize, mut i: usize) {
    while order < ORDERS - 1 && free[order][i ^ 1] {
        free[order][i ^ 1] = false; // the buddy is free: merge
        order += 1;
        i /= 2;
    }
    free[order][i] = true;
}

fn main() {
    // free[k][i]: block i of 16 KiB << k is free.
    let mut free: Vec<Vec<bool>> = (0..ORDERS)
        .map(|k| vec![false; 1 << (ORDERS - 1 - k)])
        .collect();
    free[ORDERS - 1][0] = true;
    let mut used = HashMap::new(); // name -> (order, block)
    for (name, kib) in NAMES.chars().zip(SIZES) {
        if kib > 0 {
            let Some((order, i)) = allocate(&mut free, kib) else {
                continue;
            };
            used.insert(name, (order, i));
            let size = MIN << order;
            println!("{name} {kib} KiB -> {size} KiB at {}", i * size);
        } else if let Some((order, i)) = used.remove(&name) {
            release(&mut free, order, i);
            println!("free {name}: {} KiB back", MIN << order);
        }
        let mut blocks = Vec::new();
        for (k, row) in free.iter().enumerate() {
            for (i, _) in row.iter().enumerate().filter(|&(_, &f)| f) {
                blocks.push(format!("{}@{}", MIN << k, i * (MIN << k)));
            }
        }
        println!("  free: {}", blocks.join(" "));
    }
}

In Rust: allocate returns an Option, so the ? operator stops it when no order or free block fits; release changes the maps and returns nothing.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const MIN = 16;
const ORDERS = 7;
// Sizes in KiB; 0 frees the block of that name.
const STEPS: [string, number][] = [
  ["A", 100],
  ["B", 20],
  ["C", 200],
  ["D", 40],
  ["B", 0],
  ["A", 0],
];
STEPS.push(["D", 0], ["C", 0]);

// free[k][i]: block i of 16 KiB << k is free.
const free = Array.from({ length: ORDERS }, (_, k) =>
  new Array<boolean>(1 << (ORDERS - 1 - k)).fill(false),
);
free[ORDERS - 1][0] = true;
const used = new Map<string, [number, number]>(); // name -> [order, block]

function allocate(name: string, kib: number): string {
  let order = 0;
  while (MIN << order < kib) order += 1;
  let k = order;
  while (!free[k].includes(true)) k += 1;
  let i = free[k].indexOf(true);
  free[k][i] = false;
  while (k > order) {
    // split; the upper half, its buddy, stays free
    k -= 1;
    i *= 2;
    free[k][i + 1] = true;
  }
  used.set(name, [order, i]);
  const size = MIN << order;
  return `${name} ${kib} KiB -> ${size} KiB at ${i * size}`;
}

function release(name: string): string {
  const block = used.get(name);
  if (block === undefined) throw new Error(`${name} is not allocated`);
  used.delete(name);
  let [order, i] = block;
  const size = MIN << order;
  while (order < ORDERS - 1 && free[order][i ^ 1]) {
    free[order][i ^ 1] = false; // the buddy is free: merge
    order += 1;
    i >>= 1;
  }
  free[order][i] = true;
  return `free ${name}: ${size} KiB back`;
}

for (const [name, kib] of STEPS) {
  console.log(kib ? allocate(name, kib) : release(name));
  const blocks = free.flatMap((row, k) =>
    row.flatMap((isFree, i) => (isFree ? [`${MIN << k}@${i * (MIN << k)}`] : [])),
  );
  console.log(`  free: ${blocks.join(" ")}`);
}

In TypeScript: used.get can return undefined, so release checks the name before it uses the block, as strict mode requires.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"slices"
	"strings"
)

const minKiB, orders = 16, 7

// Sizes in KiB; 0 frees the block of that name.
var steps = []struct {
	name string
	kib  int
}{
	{"A", 100}, {"B", 20}, {"C", 200}, {"D", 40}, {"B", 0}, {"A", 0}, {"D", 0}, {"C", 0},
}

var free [orders][]bool        // free[k][i]: block i of 16 KiB << k is free
var used = map[string][2]int{} // name -> {order, block}

func allocate(name string, kib int) string {
	order := 0
	for minKiB<<order < kib {
		order++
	}
	k, i := order, slices.Index(free[order], true)
	for i < 0 { // no free block of this order: look one order up
		k++
		i = slices.Index(free[k], true)
	}
	free[k][i] = false
	for k > order { // split; the upper half, its buddy, stays free
		k--
		i *= 2
		free[k][i+1] = true
	}
	used[name] = [2]int{order, i}
	size := minKiB << order
	return fmt.Sprintf("%s %d KiB -> %d KiB at %d", name, kib, size, i*size)
}

func release(name string) string {
	order, i := used[name][0], used[name][1]
	delete(used, name)
	size := minKiB << order
	for order < orders-1 && free[order][i^1] { // the buddy is free: merge
		free[order][i^1] = false
		order++
		i /= 2
	}
	free[order][i] = true
	return fmt.Sprintf("free %s: %d KiB back", name, size)
}

func main() {
	for k := range free {
		free[k] = make([]bool, 1<<(orders-1-k))
	}
	free[orders-1][0] = true
	for _, s := range steps {
		if s.kib > 0 {
			fmt.Println(allocate(s.name, s.kib))
		} else {
			fmt.Println(release(s.name))
		}
		var blocks []string
		for k, row := range free {
			for i, f := range row {
				if f {
					blocks = append(blocks, fmt.Sprintf("%d@%d", minKiB<<k, i*(minKiB<<k)))
				}
			}
		}
		fmt.Println("  free: " + strings.Join(blocks, " "))
	}
}

In Go: free is an array of seven slices, one per order. Between two operands ^ is exclusive or in Go, so i^1 gives the buddy.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let minKiB = 16
let orders = 7
// Sizes in KiB; 0 frees the block of that name.
let steps = [("A", 100), ("B", 20), ("C", 200), ("D", 40), ("B", 0), ("A", 0), ("D", 0), ("C", 0)]

// free[k][i]: block i of 16 KiB << k is free.
var free = (0..<orders).map { [Bool](repeating: false, count: 1 << (orders - 1 - $0)) }
free[orders - 1][0] = true
var used: [String: (order: Int, block: Int)] = [:]

func allocate(_ name: String, _ kib: Int) -> String {
  var order = 0
  while minKiB << order < kib { order += 1 }
  var k = order
  while !free[k].contains(true) { k += 1 }
  guard var i = free[k].firstIndex(of: true) else { return "\(name): no free block" }
  free[k][i] = false
  while k > order {  // split; the upper half, its buddy, stays free
    k -= 1
    i *= 2
    free[k][i + 1] = true
  }
  used[name] = (order, i)
  let size = minKiB << order
  return "\(name) \(kib) KiB -> \(size) KiB at \(i * size)"
}

func release(_ name: String) -> String {
  guard var (order, i) = used.removeValue(forKey: name) else { return "\(name) is not allocated" }
  let size = minKiB << order
  while order < orders - 1 && free[order][i ^ 1] {  // the buddy is free: merge
    free[order][i ^ 1] = false
    order += 1
    i /= 2
  }
  free[order][i] = true
  return "free \(name): \(size) KiB back"
}

for (name, kib) in steps {
  print(kib > 0 ? allocate(name, kib) : release(name))
  var blocks: [String] = []
  for (k, row) in free.enumerated() {
    for (i, isFree) in row.enumerated() where isFree {
      blocks.append("\(minKiB << k)@\(i * (minKiB << k))")
    }
  }
  print("  free: " + blocks.joined(separator: " "))
}

In Swift: used.removeValue(forKey:) returns an optional, so guard var takes the block or reports a name that is not allocated.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

MIN = 16
ORDERS = 7
# Sizes in KiB; 0 frees the block of that name.
STEPS = [['A', 100], ['B', 20], ['C', 200], ['D', 40],
         ['B', 0], ['A', 0], ['D', 0], ['C', 0]].freeze

# A buddy allocator: free[k][i] tells if block i of 16 KiB << k is free.
class Buddy
  attr_reader :free

  def initialize
    @free = Array.new(ORDERS) { |k| Array.new(1 << (ORDERS - 1 - k), false) }
    @free[ORDERS - 1][0] = true
    @used = {} # name -> [order, block]
  end

  def allocate(name, kib)
    order = (0...ORDERS).find { |k| MIN << k >= kib }
    i = take(order)
    @used[name] = [order, i]
    "#{name} #{kib} KiB -> #{MIN << order} KiB at #{i * (MIN << order)}"
  end

  def release(name)
    order, i = @used.delete(name)
    size = MIN << order
    while order < ORDERS - 1 && @free[order][i ^ 1] # the buddy is free: merge
      @free[order][i ^ 1] = false
      order += 1
      i /= 2
    end
    @free[order][i] = true
    "free #{name}: #{size} KiB back"
  end

  private

  def take(order)
    k = (order...ORDERS).find { |level| @free[level].include?(true) }
    i = @free[k].index(true)
    @free[k][i] = false
    # split; the upper half, its buddy, stays free
    (k - 1).downto(order) { |level| @free[level][(i *= 2) + 1] = true }
    i
  end
end

buddy = Buddy.new
STEPS.each do |name, kib|
  puts kib.positive? ? buddy.allocate(name, kib) : buddy.release(name)
  blocks = buddy.free.each_with_index.flat_map do |row, k|
    row.each_index.select { |i| row[i] }.map { |i| "#{MIN << k}@#{i * (MIN << k)}" }
  end
  puts "  free: #{blocks.join(' ')}"
end

In Ruby: find with a block gives the first order that fits, and the private method take splits the block, which keeps each method short.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

const val MIN = 16
const val ORDERS = 7

// Sizes in KiB; 0 frees the block of that name.
val steps =
    listOf("A" to 100, "B" to 20, "C" to 200, "D" to 40) +
        listOf("B" to 0, "A" to 0, "D" to 0, "C" to 0)

// free[k][i]: block i of 16 KiB shl k is free.
val free = List(ORDERS) { k -> BooleanArray(1 shl (ORDERS - 1 - k)) }
val used = HashMap<String, Pair<Int, Int>>() // name -> (order, block)

fun allocate(
    name: String,
    kib: Int,
): String {
    var order = 0
    while (MIN shl order < kib) order++
    var k = order
    while (true !in free[k]) k++
    var i = free[k].indexOf(true)
    free[k][i] = false
    while (k > order) { // split; the upper half, its buddy, stays free
        k--
        i *= 2
        free[k][i + 1] = true
    }
    used[name] = Pair(order, i)
    val size = MIN shl order
    return "$name $kib KiB -> $size KiB at ${i * size}"
}

fun release(name: String): String {
    var (order, i) = used.remove(name) ?: return "$name is not allocated"
    val size = MIN shl order
    while (order < ORDERS - 1 && free[order][i xor 1]) { // the buddy is free: merge
        free[order][i xor 1] = false
        order++
        i /= 2
    }
    free[order][i] = true
    return "free $name: $size KiB back"
}

fun main() {
    free[ORDERS - 1][0] = true
    for ((name, kib) in steps) {
        println(if (kib > 0) allocate(name, kib) else release(name))
        val blocks =
            free.flatMapIndexed { k, row ->
                row.indices.filter { row[it] }.map { "${MIN shl k}@${it * (MIN shl k)}" }
            }
        println("  free: " + blocks.joinToString(" "))
    }
}

In Kotlin: xor and shl are Kotlin's names for ^ and <<, and used.remove(name) ?: return handles a name that is not allocated.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const min = 16;
const orders = 7;
// Sizes in KiB; 0 frees the block of that name.
const steps = [
  ('A', 100), ('B', 20), ('C', 200), ('D', 40), //
  ('B', 0), ('A', 0), ('D', 0), ('C', 0),
];

// free[k][i]: block i of 16 KiB << k is free.
final free = List.generate(
  orders,
  (k) => List.filled(1 << (orders - 1 - k), false),
);
final used = <String, (int, int)>{}; // name -> (order, block)

String allocate(String name, int kib) {
  var order = 0;
  while (min << order < kib) {
    order++;
  }
  var k = order;
  while (!free[k].contains(true)) {
    k++;
  }
  var i = free[k].indexOf(true);
  free[k][i] = false;
  while (k > order) {
    // split; the upper half, its buddy, stays free
    k--;
    i *= 2;
    free[k][i + 1] = true;
  }
  used[name] = (order, i);
  final size = min << order;
  return '$name $kib KiB -> $size KiB at ${i * size}';
}

String release(String name) {
  var (order, i) = used.remove(name)!;
  final size = min << order;
  while (order < orders - 1 && free[order][i ^ 1]) {
    free[order][i ^ 1] = false; // the buddy is free: merge
    order++;
    i ~/= 2;
  }
  free[order][i] = true;
  return 'free $name: $size KiB back';
}

void main() {
  free[orders - 1][0] = true;
  for (final (name, kib) in steps) {
    print(kib > 0 ? allocate(name, kib) : release(name));
    final blocks = [
      for (var k = 0; k < orders; k++)
        for (var i = 0; i < free[k].length; i++)
          if (free[k][i]) '${min << k}@${i * (min << k)}',
    ];
    print('  free: ${blocks.join(' ')}');
  }
}

In Dart: The steps are records, (String, int), and so is each block in use, (int, int), taken apart with var (order, i).

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

A 100 KiB -> 128 KiB at 0
  free: 128@128 256@256 512@512
B 20 KiB -> 32 KiB at 128
  free: 32@160 64@192 256@256 512@512
C 200 KiB -> 256 KiB at 256
  free: 32@160 64@192 512@512
D 40 KiB -> 64 KiB at 192
  free: 32@160 512@512
free B: 32 KiB back
  free: 64@128 512@512
free A: 128 KiB back
  free: 64@128 128@0 512@512
free D: 64 KiB back
  free: 256@0 512@512
free C: 256 KiB back
  free: 1024@0

The four requests asked for 360 KiB and were given 480 KiB, so 120 KiB, a quarter of it, sat unused inside the blocks. Freeing B merged it with its free buddy at 160 into 64 KiB at 128. Freeing A merged nothing, because its buddy, 128 KiB at 128, still held D. Freeing D then merged twice, into 256 KiB at 0, and freeing C merged twice more: the arena was one block of 1 MiB again. Step through the same run as a tree of blocks:

Interactive · step by step Four requests and four frees in a buddy allocator Step through the splits that serve A, B, C and D, then the merges as each block is freed.

The drawing shows the whole scene; its 9 steps are listed below.

Every step as text

One free block. The arena starts as one free block of 1 MiB at offset 0. Every smaller block comes from halving a larger one, and the two halves of a block are buddies.
A asks for 100 KiB. A needs 128 KiB, the next power of two. No block of that size is free, so the 1 MiB block splits into two buddies of 512 KiB, at 0 and at 512.
Two more splits. 512 KiB at 0 splits into 256 KiB at 0 and at 256, and 256 KiB at 0 into 128 KiB at 0 and at 128. A takes the lower block; each upper half stays free.
B asks for 20 KiB. B needs 32 KiB. The free 128 KiB at 128 splits into 64 KiB at 128 and at 192, and 64 KiB at 128 splits into 32 KiB at 128 and at 160. B takes 32 KiB at 128.
C and D fit at once. C needs 256 KiB and takes the free block at 256 with no split. D needs 64 KiB and takes the free block at 192. The four asked for 360 KiB and hold 480 KiB.
B is freed. B's buddy is at 128 XOR 32 = 160, and it is free, so the two merge into 64 KiB at 128. That block's buddy, at 192, holds D, so the merging stops there.
A is freed. A's buddy is at 0 XOR 128 = 128. That block is split, and part of it holds D, so A stays on its own as a free block of 128 KiB.
D is freed. D merges with its free buddy at 128 into 128 KiB at 128, and that block merges with the free 128 KiB at 0 into 256 KiB at 0. Its buddy at 256 holds C.
C is freed. C merges with the free 256 KiB at 0 into 512 KiB at 0, whose buddy at 512 is free too. One more merge, and the arena is a single free block of 1 MiB again.

Key idea

The buddy system rounds every request up to a power of two, splits larger blocks in halves to get there, and merges a freed block with its buddy at address XOR size, so free memory never stays broken into small pieces for long.

Checkpoint

Check: Splitting and merging buddies

Question 1 of 2 In the lesson's arena, a free block of 32 KiB starts at offset 160 KiB. At which offset is its buddy, in KiB?
Type a number.
Your answer KiB

A hint

XOR the offset with the block's size.

Show the answer: Question 1 of 2

Answer: 128 KiB

160 XOR 32 = 128: the two 32 KiB blocks at 128 and 160 are the halves of the 64 KiB block at 128, which is what freeing B produced.
Question 2 of 2 Freeing A, 128 KiB at 0, merged nothing, although 64 KiB at 128 was free at that moment. Why?
Choose one answer.

Blocks at offset 0 never merge A was freed before B The free block at 128 was too small to hold A A's buddy is the whole 128 KiB block at 128, and D still used 64 KiB of it

Show the answer: Question 2 of 2

Answer: A's buddy is the whole 128 KiB block at 128, and D still used 64 KiB of it

A block merges only with a free buddy of its own size. D's block lay inside A's buddy, so the merge had to wait until D was freed.

A slab cache keeps objects of one size ready

The kernel allocates many small objects of a few kinds, and rounding them up to powers of two wastes memory: a 600-byte object in a 1,024-byte block leaves 424 bytes unused. A slab allocator: An allocator that keeps a cache for each kind of object, made of slabs: pages cut into slots of exactly that object's size, so that allocating or freeing an object takes or returns one slot., introduced by Jeff Bonwick in 1994, keeps one cache for each kind of object. Its slabs, in the paper’s words, are “one or more pages of virtually contiguous memory carved up into equal-size chunks”, so an allocation takes one slot and a free returns it. Step through a cache of 600-byte objects:

Interactive · step by step A slab cache serving 600-byte objects Step through an allocation from a partial slab, a free, and a new slab taken from the page allocator.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

A request. Kernel code asks the cache for one 600-byte object. Every slot in this cache has exactly that size, so there is no hole to search for and nothing to round up.
A partial slab. The cache takes the next free slot of a partial slab. A slab is one 16 KiB page cut into 27 slots of 600 bytes, with 184 bytes left over; this one has two slots free.
Ready to use. The slot goes back to the caller. A cache can keep its objects in their constructed state, so code that reuses one need not set it up again from nothing.
A free. When the object is freed, its slot goes back on its slab's free list. Nothing is merged, and no memory goes back to the page allocator.
Every slab full. Later every slab of the cache is full. The cache asks the page allocator, the buddy system of the first section, for one more page.
A new slab. The new page is cut into 27 slots, and the first one serves the request. The other 26 wait for the next allocations of this kind of object.
An empty slab. A slab whose objects are all freed again can go back to the page allocator when memory runs short, and the buddy system merges its page with a free buddy.

Linux’s slab allocator today is SLUB: Linux 6.8 removed the older SLAB implementation. Kernel code asks it for many identical objects through a cache made with kmem_cache_create, and for small objects of varying sizes through kmalloc.

malloc asks the kernel for memory in two ways

A C program’s malloc runs in the program itself and asks the kernel only for large pieces. glibc’s malloc(3) page names both paths: small requests come from the heap, which malloc grows with sbrk, and blocks larger than MMAP_THRESHOLD, 128 kB by default, each get a private mapping of their own from mmap. The heap ends at the program break: The first address after the end of a process's uninitialised data, where its heap ends. brk and sbrk move it to grow or shrink the heap., which brk and sbrk move.

Request with glibc	Comes from	When it is freed
Below 128 KiB	The heap, grown with `brk` and `sbrk`	Kept by malloc for reuse; the top of the heap goes back once enough is free
128 KiB or more	Its own mapping, from `mmap`	Unmapped, so the kernel has the memory back at once

macOS’s malloc differs: Apple’s guide describes small blocks taken from pools of pages and large ones mapped whole and page-aligned. glibc also raises its threshold as a program frees large blocks, and AddressSanitizer: A compiler option, -fsanitize=address in Clang and GCC, that checks the memory accesses of a program as it runs and stops it with a report at a use after free, an out-of-bounds access or a double free., instrumentation that the compiler adds with -fsanitize=address, checks a program’s accesses to catch a block used after it was freed.

Checkpoint

Check: Slab caches · How malloc gets memory from the kernel

Question 1 of 2 A slab of one 16 KiB page holds 600-byte objects. How many slots does it have?
Type a number.
Your answer slots

Show the answer: Question 1 of 2

Answer: 27 slots

16,384 ÷ 600 = 27.3, so 27 slots, with 16,384 − 27 × 600 = 184 bytes left over: the slab of the step-through.
Question 2 of 2 With glibc's default settings, where does a request of 1 MiB come from?
Choose one answer.

A slab cache A private mapping of its own, from mmap The stack The heap, grown with brk

Show the answer: Question 2 of 2

Answer: A private mapping of its own, from mmap

Blocks above the threshold get their own mapping, so freeing them returns the memory to the kernel at once.

Practise: write a buddy allocator

The exercise asks for the two halves of the program above: alloc, which splits, and free, which merges. Its sample tests check the addresses and the free blocks after each step.

Exercise · Medium · Python

Write a buddy allocator that splits and merges

Finish the class Buddy in buddy.py, a buddy allocator over an arena of total units whose blocks are powers of two from smallest up to total.

alloc(size) takes the smallest free block that holds size units, splitting a larger free block in halves as many times as needed; the lower half is used and the upper half, its buddy, stays free. It returns the block's offset, or None when no free block is large enough. When two free blocks of the right size exist, it uses the one at the lower offset.
free(offset) frees the block at that offset and merges it with its buddy, then the merged block with its own buddy, for as long as the buddy is free.

free_blocks() is written for you: it lists the free blocks as (offset, size) pairs, by offset. In an arena of 1,024 with a smallest block of 16, alloc(100) returns 0 and leaves the blocks (128, 128), (256, 256) and (512, 512) free.

Starter code · buddy.py

class Buddy:
    """A buddy allocator over `total` units, with blocks of `smallest` to `total` units."""

    def __init__(self, total, smallest):
        self.total = total
        self.smallest = smallest
        self.free_sets = {total: {0}}  # block size -> offsets of the free blocks of that size
        self.sizes = {}  # offset of a block in use -> its size

    def alloc(self, size):
        """The offset of a block that holds `size` units, or None."""
        # Replace this line with your code.
        return None

    def free(self, offset):
        """Frees the block at `offset`, merging it with its free buddies."""
        # Replace this line with your code.

    def free_blocks(self):
        """The free blocks as (offset, size) pairs, by offset."""
        return sorted((offset, size) for size, offsets in self.free_sets.items() for offset in offsets)

The sample tests · test_buddy.py

from buddy import Buddy


def test_first_split():
    """splits 1,024 down to 128 for a request of 100"""
    arena = Buddy(1024, 16)
    assert arena.alloc(100) == 0
    assert arena.free_blocks() == [(128, 128), (256, 256), (512, 512)]


def test_second_request_uses_a_buddy():
    """places 20 units in a block of 32 at offset 128"""
    arena = Buddy(1024, 16)
    arena.alloc(100)
    assert arena.alloc(20) == 128
    assert arena.free_blocks() == [(160, 32), (192, 64), (256, 256), (512, 512)]


def test_merge_back_to_one_block():
    """merges every buddy again when both blocks are freed"""
    arena = Buddy(1024, 16)
    a = arena.alloc(100)
    b = arena.alloc(20)
    arena.free(b)
    arena.free(a)
    assert arena.free_blocks() == [(0, 1024)]


def test_too_large():
    """returns None for a request larger than the arena"""
    assert Buddy(1024, 16).alloc(2000) is None

A hint

Keep a set of free offsets for each block size. A block of size s at offset a has its buddy at a ^ s, and the two merge into a block of size 2 * s at min(a, a ^ s). Remember the size of every block you hand out, so that free(offset) knows which size to start merging at.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Programmer Calculator (Bitwise) Check a buddy address: XOR an offset with the block size in hexadecimal or binary.

Then answer the questions on buddies, slabs and malloc, one at a time.

Buddy allocation in depth: waste measured, the buddy rule proved Pro: opens with a Pro, Premium or Ultimate pass

Powers of two make the buddy system fast and wasteful at once. This part measures the waste on 10,000 request sizes, compares it with finer size classes, proves why a block’s buddy sits at its address XOR its size, and reads Linux’s free lists.

In this part:

Internal fragmentation of power-of-two blocks, measured on 10,000 requests
Why a block’s buddy is at its address XOR its size
Linux’s free lists, and how to read them

1 runnable example (Python) · about 6 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Slab caches in depth: slots per slab, the measured gains and SLUB Pro: opens with a Pro, Premium or Ultimate pass

A slab cache wins by giving every object a slot of exactly its size. This part counts the slots and the leftover bytes for six object sizes, puts Bonwick’s measurements against the allocators of his time, and looks at how Linux’s SLUB caches objects today.

In this part:

Slots per slab and the bytes left over, for six object sizes
What Bonwick measured, and what SLUB keeps of it
Finding a corrupted object with SLUB’s debugging options

1 runnable example (Python) · about 5 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

malloc measured on this Mac, glibc's thresholds, and AddressSanitizer at work Pro: opens with a Pro, Premium or Ultimate pass

One call, malloc, hides a different policy on each system. This part measures what malloc hands out on this Mac, with and without AddressSanitizer, sets out the thresholds of glibc on Linux, and catches a use after free with a report, then checks the fix.

In this part:

What malloc hands out on this Mac, with and without AddressSanitizer
glibc on Linux: the heap, mmap and a threshold that moves
A use after free, caught, and the fix checked

4 runnable examples (C, Python, The bug, The fix) · about 6 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

The first question is answered below. The other three ask about 600-byte records, 256 KiB buffers that keep calling mmap and a use after free; their model answers are in the module’s question bank.

Fresher to mid · Warm-up

How does a buddy allocator split and merge blocks, and how does it find a block's buddy?

A buddy allocator hands out blocks whose sizes are powers of two. A request is rounded up to the next power of two; if no free block of that size exists, a larger free block is split in halves, again and again, and each split leaves the upper half free. The two halves of a block are buddies. Because a block of size s always starts at a multiple of s, its buddy is at its offset XOR s. When a block is freed, the allocator checks whether its buddy is free as a whole: if so, the two merge into one block of twice the size, and the check repeats one order up. In the lesson's run, four requests for 360 KiB got 480 KiB, and the four frees merged the arena back into one block of 1 MiB.
Mid to senior

A service keeps millions of 600-byte records in memory, allocated from an allocator that rounds every request up to a power of two. How much memory does it waste, and what would you change, with numbers?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

A Linux service built with glibc allocates and frees 256 KiB buffers thousands of times a second, and profiles show time in mmap, munmap and page faults. What is malloc doing with those buffers, and what would you change?

Model answer, Pro. First step and follow-ups
Mid to staff

A C service sometimes returns corrupted values and crashes once a week, and you suspect a use after free in your own code. How would you find it, and how would you make sure it does not come back?

Model answer, Pro. First step and follow-ups

Key takeaways

The buddy system rounds requests up to powers of two, splits larger blocks in halves and merges a freed block with its buddy at address XOR size: four requests for 360 KiB took 480 KiB, and four frees rebuilt the whole 1 MiB.
A slab allocator keeps a cache per kind of object, with slabs cut into slots of exactly that size, so a 600-byte object costs 600 bytes and not 1,024.
glibc’s malloc serves small requests from a heap grown with brk and sbrk, and gives blocks of 128 KiB or more a mapping of their own from mmap.

Terms in this lesson

AddressSanitizer: A compiler option, -fsanitize=address in Clang and GCC, that checks the memory accesses of a program as it runs and stops it with a report at a use after free, an out-of-bounds access or a double free.
buddy system: An allocator whose blocks are powers of two in size: a larger free block is split into two halves, the buddies, and a freed block merges with its buddy again whenever the buddy is free as well.
program break: The first address after the end of a process's uninitialised data, where its heap ends. brk and sbrk move it to grow or shrink the heap.
slab allocator: An allocator that keeps a cache for each kind of object, made of slabs: pages cut into slots of exactly that object's size, so that allocating or freeing an object takes or returns one slot.

References

A fast storage allocator (Communications of the ACM) (ACM (Kenneth C. Knowlton))
The Slab Allocator: An Object-Caching Kernel Memory Allocator (USENIX Summer 1994) (USENIX Association (Jeff Bonwick))
Physical Memory: zones, free areas and the buddy allocator (The Linux Kernel Organization)
Memory Allocation Guide: kmalloc, slab caches and vmalloc (The Linux Kernel Organization)
Short users guide for the slab allocator (The Linux Kernel Organization)
The /proc filesystem: /proc/buddyinfo (The Linux Kernel Organization)
Linux 6.8: the SLAB allocator removed (KernelNewbies)
Linux 6.18: slub sheaves (KernelNewbies)
malloc(3) (Linux man-pages project (man7.org))
mallopt(3): M_MMAP_THRESHOLD and M_TRIM_THRESHOLD (Linux man-pages project (man7.org))
brk(2), sbrk(2) (Linux man-pages project (man7.org))
Tips for Allocating Memory (Memory Usage Performance Guidelines) (Apple Developer Documentation)
AddressSanitizer (LLVM Project)

Report a problem with this lesson

In this module: Memory management: addresses, segmentation and paging

Linking, loading and address binding Free lesson, Pro answers: 20 minutes
Contiguous allocation and fragmentation Free core, Pro depth: 5 of 15 minutes free
Segmentation and segment tables Free core, Pro depth: 5 of 15 minutes free
Paging: pages, frames and page tables Free core, Pro depth: 6 of 15 minutes free
Allocating memory: buddy, slab and malloc Free core, Pro depth: 6 of 20 minutes free

Your country

Allocating memory: buddy, slab and malloc

What you will learn

Before you start

What you will learn

Before you start

The buddy system splits blocks in halves and merges buddies back

A slab cache keeps objects of one size ready

malloc asks the kernel for memory in two ways

Practise: write a buddy allocator

Write a buddy allocator that splits and merges

Results of the sample tests

Buddy allocation in depth: waste measured, the buddy rule proved Pro: opens with a Pro, Premium or Ultimate pass

Slab caches in depth: slots per slab, the measured gains and SLUB Pro: opens with a Pro, Premium or Ultimate pass

malloc measured on this Mac, glibc's thresholds, and AddressSanitizer at work Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

How does a buddy allocator split and merge blocks, and how does it find a block's buddy?

A service keeps millions of 600-byte records in memory, allocated from an allocator that rounds every request up to a power of two. How much memory does it waste, and what would you change, with numbers?

A Linux service built with glibc allocates and frees 256 KiB buffers thousands of times a second, and profiles show time in mmap, munmap and page faults. What is malloc doing with those buffers, and what would you change?

A C service sometimes returns corrupted values and crashes once a week, and you suspect a use after free in your own code. How would you find it, and how would you make sure it does not come back?

Key takeaways

References

Related tools