Understand CPython's Memory Allocator: obmalloc

Topic Overview

CPython's obmalloc

Most \`malloc\` calls in CPython do not hit the system allocator directly. \`obmalloc\` in \`Objects/obmalloc.c\` layers pools, arenas, and size classes tuned for small, short-lived objects.

Pool Architecture

Allocation tiers:

• Pools: 4 KiB blocks carved into blocks of one size class
• Arenas: large chunks (256 KiB) holding many pools
• Raw allocator: falls through to \`malloc\` for oversized requests

Small object requests (typical \`PyObject\` headers plus payload) are served from a free list inside a pool, avoiding syscall overhead and reducing fragmentation.

For example, allocating thousands of identical small tuples reuses slots from the same pool rather than calling \`malloc\` each time.

Stats to watch: pool utilization, arena count, and fallback rate to the system allocator under memory pressure.

Design Notes

Falling through to system `malloc` for large allocations is intentional. Pool exhaustion under fragmentation is a sign workloads allocate many different sizes; watch arena growth in long-running servers.

For This Exercise

This exercise asks you to document obmalloc's pool and arena design. You will explain why Python allocates small objects differently than a generic \`malloc\` and how that shapes interpreter performance.

You will use the same mental model here when reading production interpreter source later in the track. Sketch one concrete input on paper, predict the outcome, then confirm with code. That discipline catches logic errors early and makes debugging far faster when you extend the implementation in follow-on tasks.

Your Task

Simulate obmalloc, CPython's small-object allocator (3.8 layout, 64-bit). Requests of 1..512 bytes are rounded up to a size class, a multiple of 16. They are served from 4 KiB pools, each dedicated to one class, carved from 256 KiB arenas of 64 pools. Everything else goes to the system malloc. Freed blocks return to their pool's free list, empty pools return to their arena, and a completely empty arena is released to the OS.

Input

cCopy
Loading…

Rules

• Class: (size - 1) / 16, so the block size is (class + 1) × 16. Sizes 0 and over 512 go to the system malloc.
• Pool: a 48-byte header, then (4096 - 48) / blocksize blocks. Pool p of arena a lives at 0x10000000 + a×0x40000 + p×0x1000, and block b lives at pool + 48 + b × blocksize. Freeing finds the pool from the address alone: addr & ~0xfff.
• usedpools[class] lists the pools with free blocks, most recent first. Allocation uses the first pool in the list:
  • a block popped from the pool's LIFO free list, else the next never-used block;
  • a pool that becomes full leaves the list;
  • freeing into a full pool puts the pool back at the front.
• New pool (when usedpools[class] is empty):
  • Choose the live arena with the fewest free pools that still has one (ties: lowest index). If there is none, allocate a new arena in the lowest free arena slot, up to 8 arenas.
  • In that arena, reuse the most recently emptied pool (LIFO), else carve the next never-used pool.
  • The pool is (re)initialized for the new class.
• Empty pool: when a pool's last block is freed, it leaves usedpools and goes to its arena's free pool list. If all 64 pools of the arena are then free, the arena is released.

Output

cCopy
Loading…

• Allocation tags: a malloc's tag is [new arena], [new pool] or [reused pool] when it obtained a pool, and none otherwise.
• malloc-many and free-many print only a summary: p0..p6: 7 x 512 bytes (class 31) (plus , N new arena(s)) and freed N block(s) named p*. Each arena released during them still prints arena N released to the system.
• stats prints arenas: L live, A allocated, R released. Then, for each live arena, arena N @ 0x...: U of 64 pools in use followed by class C (S bytes): P pool(s), U/T blocks used for each class present. It ends with system malloc: N block(s), B bytes.
• Errors:
  • malloc N: name in use
  • malloc N: bad size
  • malloc N: out of arenas
  • free N: not an allocated pointer
  • malloc-many: bad arguments

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Find a block's pool by masking its address, not by searching.
2. Keep the three levels separate: blocks on pool free lists, pools on usedpools and arena free lists, arenas live or released.

Hidden tests cover a full pool going back to the front of usedpools, overflow into a second arena, reusing an emptied pool for another size class, arenas released after bulk frees, a 0-byte request, and name errors.