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`.
Defining `MI_CPYTHON` also enables it by default; other runtimes need not define
`MI_CPYTHON`. 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
disable early full-page abandonment. 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_prim` 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` appends an empty page with an
existing goal to the receiving theap's queue, or clears stale state on an
active page. 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

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_in_queue` in each page and
`qsbr_first`/`qsbr_last` in each theap. The membership bit 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 a 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

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. Reclaim does not require waiting if
the runtime permits compatible reuse. Empty arena singletons are **not** put in
those maps; they remain in the all-pages map. OS pages stay in the existing
abandoned OS-page list. No new shared delayed-page list is introduced.

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. An unfinished page
remains abandoned rather than falling through to nonempty-page reclaim logic.

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. The caller must first stop **all**
allocation, freeing, heap/theap lifecycle operations, and other collectors
that could access this heap. The allocator's heap lock alone does not provide
this exclusion. This is intended for runtime-controlled quiescent collection,
not concurrent background scanning. 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 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 protected page only
into its originating theap. 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

Forking requires other threads to be outside mimalloc. A host that also performs
uncoordinated fork-and-exec operations can define `MI_NO_PTHREAD_ATFORK=1` and
call `_mi_fork_child()` explicitly after a coordinated fork, before resuming
allocator use. Exec-only children must not use the allocator before exec.