doc/qsbr.md

# Delayed page release (QSBR)

> note: this was generated by an agent but may still be useful to refer
> to with regard to the constraints and guarantees of the qsbr primitives.

Some runtimes reuse freed objects within a size class while lock-free readers
may still inspect their memory. They must delay returning an empty allocator
page to its arena or the OS until those readers have passed a grace period.
QSBR means *Quiescent-State Based Reclamation*.

This is an internal, compile-time integration for single-source builds. It
provides runtime bookkeeping primitives, not a QSBR implementation.
The runtime remains responsible for reader registration, memory ordering,
grace-period progress, and compatible object layouts. The CPython adapter itself
is not included here.

## Enabling the hooks

Define `MI_QSBR=1` before including mimalloc headers and `src/static.c`.
Supply function definitions for the runtime primitives declared in
`include/mimalloc/qsbr.h`, either in the same translation unit or linked from
another host source file.
Missing hooks deliberately fail to build rather than silently release pages.

`include/mimalloc/qsbr.h` selects the default value of `MI_QSBR` and, when
enabled, declares the metadata types `mi_page_qsbr_t` and `mi_heap_qsbr_t`.
The host must define their struct tags before including the internal headers or
`src/static.c`. Each is embedded by value as `qsbr` in the respective allocator
type:

```c
#include <stdint.h>

struct runtime_domain;
struct mi_page_qsbr_s {
  uint64_t goal;
};
struct mi_heap_qsbr_s {
  struct runtime_domain* domain;
};
#define MI_QSBR 1
#include "src/static.c"

/* Define the hooks here; their parameters point directly to the metadata. */
```

The types must be plain C-compatible data for which zero initialization is
valid. A zeroed `mi_page_qsbr_t` must satisfy `mi_page_qsbr_is_clear`, including
on allocation failures. Page metadata starts clear, and goals are established
lazily; no page or theap initialization hook is needed. No allocator backpointers
or queue fields are needed in the host metadata.

Create protected heaps with `mi_heap_new_qsbr()`, declared in `mimalloc.h`.
Mimalloc owns the heap's `qsbr_enabled` flag and initializes it before publishing
the heap. The flag cannot be changed during the heap's lifetime; there is no
setter. `mi_heap_new()` and `mi_heap_new_in_arena()` create unprotected heaps.
Without QSBR build support, `mi_heap_new_qsbr()` reports an error and returns
`NULL`.

The constructor calls `mi_heap_qsbr_init` once on the zero-initialized metadata
of a protected heap, before publishing it or creating any of its theaps.
Use this hook to bind a stable domain from the caller's runtime context.
It is not called for unprotected heaps. The domain must outlive all the heap's
pages, including abandoned pages; no direct access to `heap->qsbr` is needed.
The constructor does not create a theap for the new heap.

Use consistent definitions everywhere that accesses internal allocator types.
Do not mix this extended layout with an ordinary mimalloc library.
`test/test-qsbr.c` is a complete fake-runtime adapter with a manually advanced
grace period; it is not a reader-tracking algorithm for production use.

With `MI_QSBR=0` (the default), the metadata and queue fields are absent, the
struct tags need not be defined, and no runtime primitives are required.
Core QSBR helpers are always-defined inline functions with feature guards
inside their bodies, so callers need no conditional compilation. Disabled
helpers do nothing, report clear state as `true`, or report delay as `false`.
There is no runtime callback table or feature test on the allocation fast path.
The core gates heap initialization and delay decisions using
`mi_heap_qsbr_is_enabled(heap)`. This is a mimalloc-owned inline query, not a
runtime primitive: it reads the immutable
flag when QSBR is compiled in and returns `false` otherwise. Protected theaps
retain singleton pages; ordinary pages follow `page_full_retain`.
The host needs no copy of that flag.

## Primitive contract

Runtime primitives have `qsbr` in their function names. They have external C
linkage, without a leading underscore. Allocator operations remain
in mimalloc; internal public functions have a leading underscore.
The `page` and `heap` parameters below are pointers to `mi_page_qsbr_t` and
`mi_heap_qsbr_t`, respectively, not allocator structs. Queue operations are
entirely internal to mimalloc. The disabled results below describe the core's
behavior; it does not call runtime primitives in that configuration.

| Primitive | Responsibility | Disabled result |
| --- | --- | --- |
| `mi_heap_qsbr_init(heap)` | Initialize zeroed metadata once for a protected heap, before publication or theap creation. Bind the caller's stable runtime context; never called for unprotected heaps. | No-op |
| `mi_page_qsbr_clear(page)` | Invalidate the recorded goal. Must be idempotent and accept zeroed metadata, including for unprotected pages. Mimalloc handles unlinking. | No-op |
| `mi_page_qsbr_is_clear(page)` | Return whether no goal is recorded. Takes a `const mi_page_qsbr_t*`; used when reclaiming pages and asserting physical release. Queue membership is checked separately by mimalloc. | `true` |
| `mi_page_qsbr_should_delay(page, heap, page_bytes)` | For an empty protected page whose ownership bit is held, establish a goal if needed using its stable heap metadata and return whether release must be delayed. Preserve any existing goal. Returning `true` requires a recorded goal. Do not require thread-local runtime state. | `false` |

`page_bytes` is a `size_t` equal to the page's current capacity times its block
size. It lets a host use deferred-memory thresholds to advance its sequence
without inspecting allocator structs. The goal's representation and completion
test remain entirely host-defined; mimalloc uses the clear-state predicate
rather than inspecting or comparing goal values.

Primitives must not allocate, free pages, change mimalloc queues, recursively
collect the allocator, or wait for readers.
Some run while allocator locks are held, including during theap deletion and
thread termination. In particular, `mi_page_qsbr_should_delay` must use
stable heap context and a cached completed sequence, not scan or lock the
runtime's thread registry. Advance that cached sequence outside allocator locks.
Outside the heap initialization hook, do not assume the calling thread has a
runtime thread state.

## Allocator operations

Normal release attempts still call `_mi_page_free(page, pq)`. It returns `true`
if the page was freed, or `false` if its release was delayed. On a delay,
mimalloc clears `retire_expire`, moves a full page back to its size-class queue,
and appends it to its theap's QSBR queue unless already queued. Otherwise it
unlinks the page, clears its goal, and calls the static `mi_page_free_direct` for
physical release. The runtime never calls that primitive or implements the
release operation itself.

`_mi_page_abandon` unlinks the page before clearing its theap ownership,
preserving its goal. `_mi_theap_page_reclaim` clears stale state on an active
page, or calls `_mi_page_free` for an empty page to release it or queue it on
the receiving theap. It returns `true` if the page was freed; allocation-side
callers retry in that case. Neither operation is delegated to the runtime.

`_mi_theap_qsbr_collect_delayed` drains its theap's queue, collecting cross-thread
frees and calling the ordinary `_mi_page_free`. It removes active pages from
the queue and stops at the first unfinished goal. If collecting frees
establishes a new goal and appends the page at the tail, draining continues
from the new head. This operation is called during maintenance, collection,
and before allocating a huge page; its calls compile away when `MI_QSBR=0`.

## Owned pages and reuse

QSBR heaps follow `mi_option_page_full_retain` like ordinary heaps: nonnegative
values allow full pages to be abandoned, while negative values keep them in
the theap's full queue. QSBR does not force full-queue retention.

A delayed owned page belongs to two independent lists:

- Its ordinary mimalloc size-class queue, so it remains available for allocation.
- Its theap's QSBR queue, so ready pages can be drained efficiently.

Mimalloc owns `qsbr_next`, `qsbr_prev`, and `qsbr_xthread_id` in each page and
`qsbr_delayed`/`qsbr_delayed_last` in each theap. The membership bit (the lowest bit of
`qsbr_xthread_id`) distinguishes an
unlinked page from a singleton queue without dereferencing an abandoned page's
old theap. Only owned pages can be queued. A recorded goal alone does not imply
queue membership: abandoned pages retain their goals after being unlinked.

The queue is FIFO, not goal-sorted. Reclamation preserves an unfinished goal and
appends at the tail, even if the goal is older than the head's. As in CPython's v2 adapter,
the delayed collector stops at the first unfinished goal, so a ready page
behind it can remain retained. It does not scan past that head or require a
goal-comparison primitive. Other release attempts, such as a forced heap walk,
still check each empty page independently.

Unlike CPython's shared per-thread queue, collecting one theap does not drain
another's queue. Ready pages in an inactive theap wait until it is collected or
its pages are abandoned and subsequently collected. A runtime can collect all
its protected theaps during thread maintenance if it needs cross-heap progress.

Mimalloc's retirement cache is unchanged: it retains only a small prefix of
ordinary size-class queues for a limited number of maintenance cycles. That
cache is an allocation optimization, not a grace period and not the delayed
list. Full pages, huge pages, and pages beyond that prefix still pass through
`_mi_page_free`. Forced collection does **not** bypass protection.

The allocation fast path intentionally does not clear a page's old goal.
Instead, mimalloc clears it whenever the used count transitions from nonzero
to zero, including when collecting cross-thread frees. Thus:

1. A page becomes empty and receives goal A.
2. Allocation reuses the page without necessarily clearing A.
3. The last block is freed again; A is invalidated, even if the page still has
   an allocator retirement countdown.
4. The next release attempt establishes a new goal B.

Merely polling an already-empty page or transferring it between owners must
not restart its grace period. A delayed-list collector must check that a page
is still empty before releasing it. Slow-path page selection may clear its
old goal and list membership as well.

This delays **page release**, not block reuse. Readers must tolerate the
runtime's same-heap, same-size-class reuse rules and freelist writes. Debug
fills, padding, guarded allocations, and object-header layout must also be
considered by the adapter; these hooks alone do not make arbitrary reads after
`mi_free` valid.

## Abandoned pages and progress

Protected singleton pages stay in their owner's huge queue instead of being
abandoned when full, even when `page_full_retain` permits abandonment.
Before each huge allocation, the owner drains its delayed QSBR queue and
examines a bounded, rotating portion of the huge queue for remote frees.
Empty pages are queued for delayed release until their grace period completes.
Ordinary pages still follow `page_full_retain`, and thread exit or explicit
theap abandonment still abandons live singletons.

Empty singletons whose grace period is unfinished go to the heap's
`qsbr_delayed` list instead of the abandoned registries, unless a free can
return them to their existing originating theap. This covers both
arena and OS pages, whether they become empty before or after their owner
exits. They keep their ownership bit set, cannot be allocation-reclaimed,
and retain their existing goal. Other abandoned pages are unchanged.

`_mi_arenas_page_free` is the single place that decides how to release an
empty abandoned page. It establishes or polls its QSBR goal and then frees
the page, queues a delayed singleton, or re-abandons a delayed ordinary page
for reuse or visitation. It returns true only for physical release. Unowning
routes empty singletons, and pages that became empty through concurrent
frees, to it; other callers route pages they know to be empty to it. Callers that have already
established safety and cleared the goal, including terminal destruction, use
`_mi_arenas_page_free_direct` without starting another grace period.

The list is FIFO: insertion appends at the tail under a per-heap lock, so the
oldest pages are at the front. Huge allocations and periodic theap collection
try to collect at most eight heap-delayed pages; they skip the pass if the
lock is busy. A pass detaches pages from the front under the lock, then
polls QSBR and frees ready pages without holding it, and finally appends the
unfinished pages at the tail again (so they rotate). The lock thus only
protects list updates and is never held while calling into the embedder or
releasing memory. While detached, pages are invisible to other collectors.
The stopped-heap abandoned collector visits all heap-delayed pages, and
terminal destruction releases them without waiting for QSBR. All fields and
paths are compiled only with `MI_QSBR`.

V3 now permits an empty page to remain abandoned when its grace period is
unfinished. Mimalloc unlinks it while its old theap is still valid.
The page keeps its stable heap context and goal, but
`page->theap` may subsequently be dangling: abandoned-page hooks must not
dereference it.

Ordinary empty arena pages remain in the existing per-heap abandoned size-class
maps and can be reclaimed by allocation. If a full regular arena page becomes
empty while abandonment collects concurrent frees, delayed release re-abandons
it as mapped before releasing ownership. Reclaim does not require waiting if
the runtime permits compatible reuse. Heap-delayed arena singletons are **not** put in
those maps; they remain registered in the all-pages map. Heap-delayed OS singletons
are removed from the abandoned OS-page list and remain visible to heap visitation
through `qsbr_delayed`.

A page may also become empty only after its owner has terminated. A zero goal
in this case is **not** evidence of safety: `mi_page_qsbr_should_delay` must
establish a new grace period using the heap's stable domain. On a free-side
release attempt, an unfinished empty page is first reclaimed if the calling
thread already has its originating theap. Ordinary release then resets its
retirement countdown and queues it for local QSBR collection. This includes
singletons and OS pages and bypasses nonempty-page reclaim limits.
Otherwise a singleton goes to `qsbr_delayed`, while other pages remain
abandoned with their goals intact; the free does not
initialize a thread or create a theap. Ordinary arena pages are made available
for allocation reclaim, while non-singleton OS pages remain visible to the
abandoned-page collector. The empty-page path finishes handling the page and
does not fall through to nonempty-page reclaim. Non-singleton pages release
ownership when left abandoned; heap-delayed singletons stay owned by the shared list.
Thread-exit abandonment of other pages is unchanged.

A goal is a target QSBR sequence identifying the grace period that must finish
before releasing the page. Zero means that no goal has been recorded, not that
all readers have finished. For example, a live page can be abandoned with goal
zero and become empty only when another thread frees its last block. The safety
primitive then records a target sequence and checks whether that target has
been reached; subsequent checks preserve it. This is lazy initialization, so
the primitive is not a read-only query. In the v2 integration, goal initialization
lives in `_PyMem_mi_page_maybe_free`, not `_PyMem_mi_page_is_safe_to_free`.

Cold abandoned pages need an explicit progress path. The internal
`_mi_heap_collect_abandoned(heap)` helper scans the existing all-pages map
and abandoned OS list, claims abandoned pages before collecting their frees,
and releases only safe empty pages. Frees may run concurrently: pages owned by
a concurrent free are skipped, as that free collects the page itself. The caller
must first stop all allocation, heap/theap lifecycle operations, and other
collectors that could access this heap. The allocator's heap lock alone does not
provide this exclusion. If readers have not finished, pages remain retained and
a later sweep is required.

## Reclaim and heap lifetime

At heap initialization, mimalloc copies `mi_option_page_reclaim_on_free` into
the heap's `reclaim_on_free` field. The core inline getter
`mi_heap_reclaim_on_free(heap)` supplies this value to both theap initialization
and free-side reclaim decisions, in ordinary and QSBR-enabled builds. Changing
the global option affects newly created heaps, not existing heaps or their
future theaps.

The nonempty-page reclaim-on-free modes retain their existing meanings:
`-1` disables it, `0` allows the originating theap only, and `1` also permits
cross-theap reclaim subject to the existing limits. Set the global option
before creating heaps that need a particular mode.

For heaps created by `mi_heap_new_qsbr()`, positive values are capped at `0`;
negative values remain disabled. Thus a free can reclaim a nonempty protected
page only into its originating theap. Empty pages delayed by QSBR may also
return to their existing originating theap regardless of this policy, but are
never adopted into a foreign theap by a free. Empty delayed singletons go to
`qsbr_delayed` if their originating theap is unavailable. This cap
does not change allocation-side reclaim: other theaps may still obtain
compatible abandoned pages from the same heap when looking for a fresh page.

This change also fixes a v3 eligibility fallthrough: an ineligible non-origin
theap could previously reclaim a page when its destination queue was empty.
Such pages now remain abandoned. The correction applies to ordinary builds
too. The reclaim-on-free setting does not replace the abandoned-page safety
check for direct release.

`mi_heap_delete` normally migrates allocations to the main heap and destroys
the original heap's metadata. Mimalloc checks `mi_heap_qsbr_is_enabled` before
any mutation and rejects QSBR-enabled heaps, emitting a warning and leaving
the heap intact. This restriction applies even when the heap is empty or all
recorded grace periods have completed.

`mi_heap_destroy` is different: it is an explicit terminal operation that
invalidates all allocations. The caller must ensure that **all readers and
mutators have stopped**. It clears delayed-list state and releases pages
without waiting for grace periods. Mimalloc drains or unlinks each theap's queue
before freeing the theap, including during destruction performed by another
thread under external exclusion.

Quiescent heap inspection also collects pending frees. In hook-enabled builds
it temporarily claims abandoned pages for that collection, including empty
orphans awaiting terminal destruction.

## Fork handling

mimalloc registers a `pthread_atfork` child handler that only marks the threads
that do not exist in the child; their pages are abandoned lazily when a new
thread starts in the child (as it can reuse the thread id of a dead thread), or
during the periodic administration on the generic allocation path.
Uncoordinated fork-and-exec is therefore safe as long as the child does not use
the allocator before exec. A child that keeps allocating
requires that other threads were outside mimalloc at the fork (if such a thread
held an allocator lock, its pages are leaked in the child). With
`MI_NO_PTHREAD_ATFORK=1`, a host can call `_mi_fork_child()` itself after a
coordinated fork, before resuming allocator use.