vault

Arenas Pools and Blocks

15 min read

Arenas, Pools, and Blocks

The pymalloc small-object allocator manages memory in a strict three-level hierarchy: it requests big arenas from the operating system, divides each arena into fixed-size pools, and divides each pool into fixed-size blocks that hold one object each. Every level exists to amortize the cost of the level below it — one mmap yields an arena of many pools, one pool is initialized once and reused for thousands of same-size allocations, and one block is handed out and returned with nothing but a pointer push. This note documents the data structures and their lifecycle; the policy and fast path that drive them are in the sibling note The pymalloc Allocator. (Verified against Objects/obmalloc.c and Include/internal/pycore_obmalloc.h in CPython 3.14.)

This hierarchy is the concrete realization of pymalloc’s “simple segregated storage” strategy. Understanding it explains both why CPython’s small-object allocation is fast and why a CPython process can hold resident memory long after the objects that needed it have been freed — the topic of Memory Fragmentation in CPython.

Mental Model

The three levels nest like Russian dolls, each carved from the one above it:

flowchart TD
    OS["Operating System<br/>(mmap / VirtualAlloc)"] -->|"one mmap per arena"| A
    subgraph A["Arena — 1 MiB (64-bit default)"]
        direction TB
        AO["arena_object bookkeeping:<br/>address, pool_address (highwater),<br/>nfreepools, freepools list"]
        subgraph P1["Pool — 16 KiB"]
            PH1["pool_header:<br/>szidx=1 (32-byte class)<br/>ref.count, freeblock"]
            B1["block · block · block · …<br/>(32 bytes each)"]
        end
        subgraph P2["Pool — 16 KiB"]
            PH2["pool_header:<br/>szidx=5 (96-byte class)<br/>ref.count, freeblock"]
            B2["block · block · …<br/>(96 bytes each)"]
        end
        P3["… up to 64 pools per arena …"]
    end

    style A fill:#dbeafe
    style P1 fill:#dcfce7
    style P2 fill:#fef9c3
    style B1 fill:#fee2e2
    style B2 fill:#fee2e2

Figure: pymalloc’s arena → pool → block hierarchy on a default 64-bit CPython 3.14 build. The key insight is that one size class per pool: every block in a given pool is the same size, so a freed block can only be reused for an identical request — that is what prevents external fragmentation within a pool. An arena mixes pools of different size classes, and pools of one class can live across many arenas. The arena is the unit of OS allocation (1 MiB per mmap); the pool is the unit of size-class commitment (16 KiB); the block is the unit handed to an object.

Block Sizes — Arenas, Pools, and the 64-bit Defaults

The three sizes are compile-time macros in pycore_obmalloc.h, and their values depend on the build configuration. On the standard 64-bit build that almost everyone runs, two feature flags are on by default:

#if !defined(WITH_PYMALLOC_RADIX_TREE)
#define WITH_PYMALLOC_RADIX_TREE 1          /* on by default */
#endif
 
#if SIZEOF_VOID_P > 4                        /* 64-bit: 8-byte pointers */
#define USE_LARGE_ARENAS
#if WITH_PYMALLOC_RADIX_TREE
#define USE_LARGE_POOLS                      /* large pools need the radix tree */
#endif
#endif

The radix tree (used by address_in_range to decide whether a pointer belongs to pymalloc) is enabled by default, and on 64-bit it unlocks both USE_LARGE_ARENAS and USE_LARGE_POOLS. Those select the large values:

#ifdef USE_LARGE_ARENAS
#define ARENA_BITS              20                    /* 1 MiB */
#else
#define ARENA_BITS              18                    /* 256 KiB */
#endif
#define ARENA_SIZE              (1 << ARENA_BITS)
 
#ifdef USE_LARGE_POOLS
#define POOL_BITS               14                  /* 16 KiB */
#else
#define POOL_BITS               12                  /* 4 KiB */
#endif
#define POOL_SIZE               (1 << POOL_BITS)
 
#define MAX_POOLS_IN_ARENA  (ARENA_SIZE / POOL_SIZE)

So on a default 64-bit CPython 3.14:

  • ARENA_SIZE = 2²⁰ = 1 MiB (ARENA_BITS = 20).
  • POOL_SIZE = 2¹⁴ = 16 KiB (POOL_BITS = 14).
  • MAX_POOLS_IN_ARENA = 1 MiB / 16 KiB = 64 pools per arena.

The smaller values — 256 KiB arenas and 4 KiB pools — are the fallback used on 32-bit builds, or whenever the radix tree is disabled (-DWITH_PYMALLOC_RADIX_TREE=0). Notably, MAX_POOLS_IN_ARENA is 64 in both configurations, because the 4× factors in arena and pool size cancel.

This is a 3.14-era default; older Python used 256 KiB / 4 KiB universally

The “large pools / large arenas” path is the current default on 64-bit. Historically (and still on 32-bit or with the radix tree off), pymalloc used 256 KiB arenas and 4 KiB pools, and a pool was exactly one OS page. The large-pool path decouples pool size from page size — see the next callout. Values verified against the macro definitions in CPython 3.14 pycore_obmalloc.h; as-of CPython 3.14.

A 16 KiB pool is not one OS page on the default build

The macro SYSTEM_PAGE_SIZE is 4 * 1024 (4 KiB), so a 16 KiB pool spans four OS pages. The source enforces “pool == page” only when the radix tree is off — the guard #if !WITH_PYMALLOC_RADIX_TREE / #if POOL_SIZE != SYSTEM_PAGE_SIZE → #error "pool size must be equal to system page size" is gated on !WITH_PYMALLOC_RADIX_TREE (verified in pycore_obmalloc.h). With the radix tree on (the default), that guard is skipped and pool size is decoupled from page size. The long-standing “a pool of 4K (one VMM page)” wording in the design comment reflects the fallback config, not the default 64-bit build.

Arenas — the Unit of OS Allocation

An arena is the chunk pymalloc requests from the operating system. On a default 64-bit build it is 1 MiB, obtained with a single mmap (POSIX) or VirtualAlloc (Windows). The design comment stresses that reserving an arena does not commit physical memory: “A malloc(<Big>) is usually an address range reservation for <Big> bytes, unless all pages within this space are referenced subsequently” — so an under-used arena is “an addressable range wastage,” not wasted RAM, until its pools are actually touched (per pycore_obmalloc.h). The backend confirms the use of anonymous mappings:

ptr = mmap(NULL, size, PROT_READ|PROT_WRITE,
           MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);

Each arena is described by an arena_object — a bookkeeping struct kept separately from the arena memory itself:

struct arena_object {
    uintptr_t address;            /* base address of the arena (0 = unassociated) */
    pymem_block* pool_address;    /* pool-aligned pointer to next pool to carve */
    uint nfreepools;              /* free pools + never-allocated pools */
    uint ntotalpools;             /* total pools in the arena */
    struct pool_header* freepools;/* singly-linked list of available pools */
    struct arena_object* nextarena;
    struct arena_object* prevarena;
};

Walking the fields:

  • address is the arena’s base address from mmap. A value of 0 is the sentinel for “this arena_object slot is not currently backing any arena” — exploited because a successful malloc/mmap never returns address 0.
  • pool_address is the highwater mark: the next pool-aligned address that has never yet been carved into a pool. Pools below it have been initialized at least once; the region from pool_address to the arena’s end is virgin.
  • nfreepools counts pools available for (re)use — both the recycled ones on freepools and the never-touched ones above the highwater mark.
  • freepools is a singly-linked list of pools that were fully used and then emptied, threaded through each pool’s nextpool field.
  • nextarena / prevarena link the arena into one of two global lists, depending on its state (below).

The arena_object structs live in a growable vector (allarenas); CPython allocates INITIAL_ARENA_OBJECTS = 16 slots initially and doubles the vector when it fills (per new_arena in obmalloc.c). The source comment annotates this as “16 = … 16 * ARENA_SIZE = 4MB before growing,” but that 4 MB figure is stale arithmetic from the old 256 KiB arena; with the current 1 MiB default the same 16 slots track 16 MiB before the vector grows.

Pools — the Unit of Size-Class Commitment

A pool is one 16 KiB slice of an arena dedicated to a single size class. Its first bytes are a pool_header:

struct pool_header {
    union { pymem_block *_padding;
            uint count; } ref;          /* number of allocated blocks    */
    pymem_block *freeblock;             /* pool's free list head         */
    struct pool_header *nextpool;       /* see "Pool table" for meaning  */
    struct pool_header *prevpool;       /* "                             */
    uint arenaindex;                    /* index into arenas of base adr */
    uint szidx;                         /* block size class index        */
    uint nextoffset;                    /* bytes to virgin block         */
    uint maxnextoffset;                 /* largest valid nextoffset      */
};

Field by field:

  • ref.count is the number of blocks in this pool currently handed out. When it returns to 0 the pool is empty and can be recycled; the union lets the same slot double as padding to keep the header pointer-aligned.
  • freeblock is the head of the pool’s singly-linked free list of returned blocks. The free path pushes here; the fast path pops here.
  • nextpool / prevpool link the pool into the per-size-class circular list in the global usedpools table (described below) when the pool is partially used.
  • arenaindex is the pool’s index into allarenas, so POOL_ADDR(p) → arenaindex recovers the owning arena in O(1).
  • szidx is the size-class index this pool serves; combined with INDEX2SIZE it gives the block size.
  • nextoffset / maxnextoffset drive lazy virgin-block carving (next section).

POOL_OVERHEAD (the header rounded up to ALIGNMENT) is subtracted from POOL_SIZE to get the usable block region; NUMBLOCKS(I) = (POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I) is how many blocks of class I a pool holds. A 16 KiB pool of 32-byte blocks holds roughly (16384 − overhead)/32 ≈ 511 blocks.

Lazy block carving: virgin blocks, nextoffset, maxnextoffset

pymalloc “strives at all levels (arena, pool, and block) never to touch a piece of memory until it’s actually needed” (per pycore_obmalloc.h). So when a pool is first initialized, it does not thread all its blocks onto the free list. Instead, from allocate_from_new_pool:

pool->szidx = size;
size = INDEX2SIZE(size);
bp = (pymem_block *)pool + POOL_OVERHEAD;     /* first block */
pool->nextoffset = POOL_OVERHEAD + (size << 1);/* offset to the 3rd block */
pool->maxnextoffset = POOL_SIZE - size;        /* last legal block offset */
pool->freeblock = bp + size;                   /* free list = just the 2nd block */
*(pymem_block **)(pool->freeblock) = NULL;     /* terminate that 1-block list */
return bp;                                      /* hand out the 1st block */

Only the first two blocks are set up: block 1 is returned, and freeblock points at block 2 with a NULL terminator. The remaining blocks are virgin — never touched. nextoffset records the byte offset of the next virgin block (here block 3), and maxnextoffset is the offset of the last block that fits. When the free list runs dry, pymalloc_pool_extend exposes one more virgin block:

if (UNLIKELY(pool->nextoffset <= pool->maxnextoffset)) {
    pool->freeblock = (pymem_block*)pool + pool->nextoffset;
    pool->nextoffset += INDEX2SIZE(size);
    *(pymem_block **)(pool->freeblock) = NULL;
    return;
}

The comment states the invariant precisely: “All the blocks in a pool have been passed out at least once when and only when nextoffset > maxnextoffset.” This lazy carving means a pool that is only lightly used never dirties its tail pages — keeping the resident-memory footprint proportional to peak live blocks, not pool capacity.

Blocks — the Unit Handed to an Object

A block is a fixed-size slot — one of the 32 size classes on 64-bit — that holds exactly one allocation’s worth of bytes. Blocks carry no header: all metadata lives in the pool_header, found by rounding any block pointer down to its pool with POOL_ADDR(p) = _Py_ALIGN_DOWN(p, POOL_SIZE). This is why pymalloc has near-zero per-object overhead.

Free blocks form a singly-linked list threaded through the free blocks themselves — a freed block’s first machine word stores the pointer to the next free block. Allocation pops the head (bp = pool->freeblock; pool->freeblock = *(pymem_block**)bp); freeing pushes onto the head (*(pymem_block**)p = pool->freeblock; pool->freeblock = p). No separate free-list storage is needed because a free block, by definition, is not in use.

The Pool Table and the Three Pool States

The global usedpools table is “headed, circular, doubly-linked lists of partially used pools” — one list per size class (per pycore_obmalloc.h). (The usedpools[i+i] index-doubling trick that compresses each list head to two pointers is detailed in The pymalloc Allocator.) A pool, once carved off an arena’s highwater mark, is “in one of three states forever after”:

  • used — partially used (≥1 block allocated and ≥1 free). This is a pool’s initial state. It lives in the circular usedpools[szidx] list, linked via nextpool/prevpool. This is the only state the fast path services directly.
  • full — every block allocated. On the used→full transition the pool is unlinked from usedpools and “not linked to from anything” — pymalloc tracks full pools implicitly, through the blocks pointing back to them. A subsequent free of any block re-links the pool at the front of its usedpools list (so the just-freed block is reused next — an LRU-ish bias toward filling pools).
  • empty — every block free. On the used→empty transition the pool is unlinked from usedpools and pushed onto its arena’s freepools list, losing its size-class identity. The next allocation that finds an empty usedpools list grabs a pool off freepools; if that pool last held the same size class, header re-initialization is skipped.

These transitions are implemented in pymalloc_free / insert_to_usedpool / insert_to_freepool in obmalloc.c.

Arena Lifecycle — Allocation and Return to the OS

Arenas live on two global lists, switched by state:

  • unused_arena_objects — a singly-linked list of arena_object slots with no arena attached (address == 0). new_arena pops one and mmaps a real arena into it; freeing an arena pushes its slot back.
  • usable_arenas — a doubly-linked list of arenas that have at least one available pool, kept sorted in ascending order of nfreepools — that is, most-full arenas first. The comment explains the rationale: “the next allocation will come from a heavily used arena, which gives the nearly empty arenas a chance to be returned to the system” (per obmalloc.c). An arena whose pools are all in use is on neither list.

Keeping the list sorted used to be an O(n) linear search on every change, which became quadratic with many arenas; since Python 3.8 a “search finger” vector nfp2lasta[nfp] records the rightmost arena with nfp free pools, eliminating the search (per the obmalloc.c comment, which attributes the change to bpo-37029).

The return-to-OS decision happens in insert_to_freepool whenever freeing a block empties a pool. The comment enumerates four cases; the consequential one is Case 1:

if (nf == ao->ntotalpools && ao->nextarena != NULL) {
    /* Case 1: all pools free → return the arena to the system,
       UNLESS it's the last arena in the list (keep one to avoid thrashing). */
    /* ... unlink ao from usable_arenas, recycle the arena_object slot ... */
    _PyObject_Arena.free(_PyObject_Arena.ctx, (void *)ao->address, ARENA_SIZE);
    ao->address = 0;
    --narenas_currently_allocated;
    return;
}

_PyObject_Arena.free is munmap on POSIX (VirtualFree on Windows) — the arena’s full 1 MiB is genuinely handed back to the OS, dropping the process’s resident set. The crucial guard is && ao->nextarena != NULL: if this is the last arena on the list, pymalloc keeps it rather than freeing it, “to avoid thrashing… a simple loop would otherwise provoke needing to allocate and free an arena on every iteration” (per the obmalloc.c comment, which attributes this guard to bpo-37257). The other three cases keep the arena and re-sort the usable_arenas list: Case 2 re-adds a previously-full arena (its first pool just freed), Case 3 “slides this arena right” to maintain the nfreepools ordering, and Case 4 is a no-op when it is already in place.

How This Ties to Fragmentation

The hierarchy’s great strength — one size class per pool — eliminates external fragmentation within a size class but creates a coarse-grained retention problem. An arena is returned to the OS only when all 64 of its pools are simultaneously empty. A single live block — one long-lived 48-byte object — pins its entire pool, and a single live pool pins its entire 1 MiB arena. So a program that allocates millions of small objects, frees almost all of them, but leaves a sparse scattering alive across many arenas, can hold gigabytes resident even though live data is tiny. The usable_arenas “most-full-first” sort is specifically an attempt to concentrate allocations and let nearly-empty arenas drain to zero so they can be freed. The full treatment of this — and the workloads that defeat it — is in Memory Fragmentation in CPython.

Common Misunderstandings

  • “Freeing objects shrinks the process.” Not until whole arenas empty. Reference-count-zero frees a block instantly, but that block returns to a pool’s free list, not to the OS. RSS drops only on the munmap in Case 1 above.
  • “A pool is one OS page.” True only on the 256 KiB-arena fallback (4 KiB pool = 1 page). The default 64-bit build uses 16 KiB pools spanning four pages — see the callout above.
  • “Each arena holds one size class.” No — a pool holds one size class; an arena holds up to 64 pools of assorted size classes. Conversely, pools of one size class are scattered across many arenas.
  • “Blocks have headers like malloc chunks.” Blocks are header-free raw bytes; metadata is per-pool, recovered by pointer alignment.

See Also

Graph View

Backlinks