Kalloc heaps: size classes, routing, free, and realloc

Allocator overview · Type isolation · Zone implementation · Kernel VM allocation

kalloc converts an allocation's size, content category, type view and flags into a zone allocation or a kernel VM allocation. It uses the zone allocator's elements and caches for small requests; it does not maintain an independent small-object free-list implementation. Fixed typed allocations usually bypass size selection at runtime because startup has already assigned their zone. Variable typed allocations and byte-buffer APIs enter the routing described here. Runtime dispatcher, fixed typed implementation.

The heap object is a routing and accounting view

The heap's actual representation is small:

Source: kalloc.h, lines 90–98

typedef struct kalloc_heap {
	zone_stats_t        kh_stats;
	const char         *__unsafe_indexable kh_name;
	zone_kheap_id_t     kh_heap_id;
	vm_tag_t            kh_tag;
	uint16_t            kh_type_hash;
	zone_id_t           kh_zstart;
	struct kalloc_heap *kh_views;
} *kalloc_heap_t;

There are several distinct bases in kalloc.c:

KALLOC_HEAP_DEFINE creates a view and startup registration. It cannot instantiate an arbitrary independent allocator. kheap_init_data and kheap_init_data_shared reuse their base's zones and allocate separate statistics. kheap_init_var chooses an existing flexible variable heap, copies that heap's starting zone, assigns a randomized adjusted type hash, and links the view into that heap's view list. A new name therefore does not guarantee a unique heap or unique physical pages. Macro and contract, view initialization.

The KHEAP_KT_VAR declaration still calls it a temporary heap awaiting variable-view support. The current dispatcher and initialization bodies already implement variable views. Likewise, old references to a data “submap” should be read with this checkout's current range selection and zone submap indices. Historical header comment, current variable-view dispatch, VM placement.

Size classes: two tables serve different purposes

Ordinary heaps and variable typed heaps have a computed size sequence. kalloc_zsize_compute initializes 16 and 32 bytes, then creates two classes per power-of-two step. With no classic KASAN adjustment the sequence begins:

16, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384.

Non-x86 builds extend this sequence to 24576 and 32768. KHEAP_MAX_SIZE is 16 KiB on x86_64 and 32 KiB otherwise in this source; KALLOC_SAFE_ALLOC_SIZE is separately 16 KiB. The latter is the public safe Z_NOFAIL bound, not a universal statement of the last zone size. Class constants, safe bound, class construction.

Fixed typed allocation uses a different kt_zone_cfg table. It has additional tuned sizes such as 80, 160, 288, 368 and 400. Startup groups fixed views using that table; applying the variable heap formula to a fixed type would predict the wrong zone in some cases. Classic KASAN adjusts selected class capacities through K_SIZE_CLASS. In the variable-heap runtime selector, a mathematical class that cannot hold the request advances to the next zone; fixed views receive their zone during startup. Fixed class table and sanitizer transformation, fixed assignment.

kalloc_zone_for_size_with_flags computes a variable heap index without scanning every zone:

Source: kalloc.c, lines 288–302

		if (size <= KHEAP_START_SIZE) {
			zid  += (size > 16);
		} else {
			/*
			 * . log2down(size - 1) is log2up(size) - 1
			 * . (size - 1) >> (log2down(size - 1) - 1)
			 *   is either 0x2 or 0x3
			 */
			idx   = kalloc_log2down((uint32_t)(size - 1));
			zid  += KHEAP_EXTRA_ZONES +
			    2 * (idx - KHEAP_START_IDX) +
			    ((uint32_t)(size - 1) >> (idx - 1)) - 2;
		}

		zone = zone_by_id(zid);

For example, a 100-byte ordinary data request selects the 128-byte class, and 257 bytes select 384, under the unmodified sequence above. These are calculations from the source constants, not observations of a running kernel. The requested byte count and element capacity remain different values.

Two flags alter selection before that formula:

• Z_KALLOC_ARRAY rounds to KALLOC_ARRAY_GRANULE for the encoded-array representation.
• Z_MAY_COPYINMAP lowers the x86_64 zone crossover to PAGE_SIZE - 1 for a historical sharing/remap ABI. It does not make an arbitrary zone element independently mappable into userspace. ARM follows its own backend and flag rules.

The x86 special case is explicit in the selector. kheap_size_from_zone contains a corresponding reallocation distinction: a full-size return can report PAGE_SIZE even when the original copyin-compatible request came from a zone. It checks the address's actual zone identity in that case. Old-allocation classification.

Runtime allocation: resolve the view, then choose storage

kalloc_ext accepts either a heap pointer or a specially marked variable type-view pointer. kt_is_var_view and kt_demangle_var_view discriminate that internal calling convention. For a type view it obtains the coarse heap family from flags, takes the assigned kt_heap_start when present, chooses the view's statistics when available, and extracts the type hash. Heap callers supply those fields directly. View pointer encoding, variable wrapper, dispatcher.

kalloc_type_get_heap routes data-only metadata to the private data family, processed nondata metadata to the typed family, and unprocessed nondata metadata to the default view. Selection of the particular variable heap comes from the view's starting zone rather than the coarse heap pointer alone. Heap classification.

Mermaid source

flowchart TD
    A[Variable type view or heap plus size and flags] --> B[Resolve statistics, starting zone, type hash]
    B --> C{Eligible for shared initial inventory?}
    C -->|yes| D[Use EARLY starting zone]
    C -->|no| E[Use assigned starting zone]
    D --> F[Compute size class with flag adjustments]
    E --> F
    F --> G{Zone class available?}
    G -->|yes| Z[kalloc_zone then zalloc_ext]
    G -->|no| V[kalloc_large then kmem_alloc_guard]
    Z --> R[Return requested size or full element capacity]
    V --> R

The final dispatch is short:

Source: kalloc.c, lines 2549–2555

	zstart = kalloc_use_early_heap(kheap, zstats, zstart, &flags);
	z = kalloc_zone_for_size_with_flags(zstart, size, flags);
	if (z) {
		return kalloc_zone(z, zstats, flags, size);
	} else {
		return kalloc_large(kheap, size, flags, kt_hash, owner);
	}

kalloc_zone calls zalloc_ext, using view statistics or the zone's own statistics. struct kalloc_result returns both address and size. Normally kalloc changes the returned size to the requested size; with Z_FULLSIZE or encoded-array allocation it reports the element capacity instead. KASAN tracks the requested/unused regions, and probabilistic guard-zone support can adjust the returned address within the element. Do not use allocator slack merely because a zone class is larger than the request; the selected API determines usable bounds. Result structure, zone wrapper.

EARLY routing is based on allocation history, not only boot time

Both variable routing and fixed typed allocation consult zs_alloc_not_early. Data heaps set that bit at initialization and do not use this sharing optimization. Eligible nondata views initially use shared EARLY zones; ordinary zalloc_item increments cumulative allocated bytes in the selected per-CPU statistics. Once sharing can end and a threshold is reached, it marks all CPUs' copies of that statistics view as no-longer-early. Existing objects stay where they were allocated. Data exclusion, variable routing, fixed routing.

Source: zalloc.c, lines 6092–6103

	if (__improbable(!zone_share_always &&
	    !os_atomic_load(&zs->zs_alloc_not_early, relaxed))) {
		if (flags & Z_SET_NOT_EARLY) {
			vm_size_t shared_threshold = zalloc_get_shared_threshold(zone, esize);

			if (zs->zs_mem_allocated >= shared_threshold) {
				zpercpu_foreach(zs_cpu, zstats) {
					os_atomic_store(&zs_cpu->zs_alloc_not_early, 1, relaxed);
				}
			}
		}
	}

The threshold depends on element size: up to 512 bytes it is a multiple of a quarter page; below 2048 it is a multiple of eight elements; otherwise it is a multiple of one chunk's element capacity. zalloc_iokit_lockdown permits this transition by clearing zone_share_always; zalloc_first_proc_made sets the threshold multiplier to one and enables zone caching. These are separate lifecycle events. Threshold formula, lifecycle hooks.

The consequence for type isolation is specific: startup's assigned destination is not necessarily where the first runtime object from that view is allocated. The free path recognizes the actual allocation and allows the EARLY family for eligible nondata frees. This sharing policy must be included when interpreting a zone dump or a statement that two types are separated. Free-family validation.

Large allocations preserve category and placement inputs

kalloc_large rejects Z_NOFAIL with a panic; rejects Z_NOWAIT, unrepresentable sizes and oversized encoded-array requests with an empty result; translates the other supported flags; and calls kmem_alloc_guard on kernel_map. There is no nonblocking large-allocation fallback into a different small-object pool. Large path.

The guard bundles different kinds of metadata:

Source: kalloc.c, lines 2107–2116

static kmem_guard_t
kalloc_guard(vm_tag_t tag, uint16_t type_hash, const void *owner)
{
	kmem_guard_t guard = {
		.kmg_atomic      = true,
		.kmg_tag         = tag,
		.kmg_type_hash   = type_hash,
		.kmg_context     = os_hash_kernel_pointer(owner),
	};

kmg_atomic protects the allocation as a complete map interval; kmg_context identifies the owner context used by applicable guarded operations; kmg_type_hash influences placement; kmg_tag accounts memory. None is an allocation's C++ RTTI or a general proof that a subsequent pointer has the expected source type. The kernel VM chapter follows the resulting range, guards and object/page population.

Memory tagging is another layer. Under ZONE_TAGGING, the large path can add KMA_TAG. In the HAS_MTE && !KASAN branch, the actual exclusion tests KMA_DATA, although the comment says both shared and private data are excluded. The caller sets KMA_DATA for KHEAP_DATA_PRIVATE and the separate KMA_DATA_SHARED bit for KHEAP_DATA_SHARED; those flags are mutually exclusive. Thus the inspected shared-data path retains KMA_TAG through local kmem object selection, page population and final tag generation. Do not substitute the comment for that predicate, or infer the same eligibility rule as small zone allocations. External monitor validation remains a separate boundary. Policy and caller, flag exclusivity/runtime gate, tagged object choice, mapping flags, final tagging.

A placement hash, a VM accounting tag and an MTE allocation tag are three different values with different purposes. MTE mitigation and page lifetime follows tag choice, retagging, checked mappings and fault outcomes; KASAN variants have their own instrumentation and policy.

Free validates storage identity before returning it

kfree_ext accepts null, rejects an absurd size, and selects its small or large path. For a small free, zone_element_size discovers the actual zone and element capacity from the address, including any guard-zone address adjustment. The supplied size plus adjustment must fit that element. It then passes the actual zone to kfree_zone. This is not simply “compute a size class and push the address into it.” Sized free.

kfree_zone resolves the expected heap family and statistics. Calls through the base KHEAP_DATA_PRIVATE and KHEAP_DATA_SHARED pointers must match their exact coarse family. Other heap pointers may also target EARLY; this includes custom data heap views because the strict branch tests pointer equality with the two bases. Typed data views resolve to the private-data base and take its strict branch. It clears the whole element with __nosan_bzero and calls zfree_ext with the element/request sizes packed for the lower layer:

Source: kalloc.c, lines 2884–2900

	zsflags = zone_security_config(z);
	if (kheap == KHEAP_DATA_PRIVATE || kheap == KHEAP_DATA_SHARED) {
		if (kheap->kh_heap_id != zsflags.z_kheap_id) {
			kfree_heap_confusion_panic(kheap, data, size, z);
		}
	} else {
		if ((kheap->kh_heap_id != zsflags.z_kheap_id) &&
		    (zsflags.z_kheap_id != KHEAP_ID_EARLY)) {
			kfree_heap_confusion_panic(kheap, data, size, z);
		}
	}

	DTRACE_VM3(kfree, vm_size_t, size, vm_size_t, zsize, void*, data);

	/* needs to be __nosan because the user size might be partial */
	__nosan_bzero(data, zsize);
	zfree_ext(z, zstats ?: z->z_stats, data, ZFREE_PACK_SIZE(zsize, size));

These checks deliberately have different precision from fixed typed free. Variable frees validate coarse heap family and storage size, not the unique source-language type or the exact variable heap selected at startup. Fixed typed free supplies its assigned zone; validation also accepts supported signature-equivalent zones and the EARLY alternative. The typed chapter details this distinction; allocation segregation should not be described as universal dynamic type checking.

kfree_addr_ext discovers the zone without a caller-supplied size. For a non-zone allocation it asks kmem_free_guard to infer the size using KMF_GUESS_SIZE. kfree_large applies guard/tag checks, removes the VM allocation and updates large-allocation counters and the thread ledger. The VM entry, rather than a size-class guess, describes that extent. Address-only free, large free.

kalloc_data_require illustrates a category assertion used by callers: it checks zone heap-family metadata and capacity, or containment in a private/shared data VM range. It does not inspect every byte to discover whether a caller wrote a pointer into a data buffer. Classification comes from the allocation contract. Data assertion.

Realloc is a decision tree with ownership consequences

krealloc_ext resolves the same view information as allocation, computes the destination class, and discovers the source's actual zone/capacity. Its main cases are:

Complete dispatcher. A same-capacity decision is not a promise that the pointer bits remain unchanged under every sanitizer/guard configuration. The code uses actual old storage rather than assuming that the current view would select the same destination as when the object was created. In particular, the zone fast path compares bucket sizes, not old_z == new_z; it can retain EARLY storage after the view has transitioned to an assigned typed family. That early-return path checks the recovered size bounds but does not call kfree_zone to validate the coarse heap family.

The allocate/copy/free branch makes the ordinary failure ownership explicit:

Source: kalloc.c, lines 3375–3387

	if (addr && kr.addr) {
		__nosan_memcpy(kr.addr, addr, min_size);
	}

	if (addr && (kr.addr || (flags & Z_REALLOCF) || !new_size)) {
		if (old_z) {
			kfree_zone(kheap_or_kt_view,
			    (char *)addr - oob_offs, old_size,
			    old_z, old_bucket_size);
		} else {
			kfree_large((vm_offset_t)addr, old_size, KMF_NONE, owner);
		}
	}

The lower large helper passes KMR_FREEOLD and optionally KMR_REALLOCF into VM. However, its Z_NOWAIT and size-range rejections occur before that VM call and return immediately; those branches do not free the old address merely because Z_REALLOCF was present. This is why flag semantics should be read through the selected route and valid calling contract. Large realloc checks, VM flags and call, VM resize ownership.

Encoded arrays carry capacity separately from ordinary pointers

The kalloc_array family wraps storage in a representation containing both pointer and usable capacity. Z_KALLOC_ARRAY affects class rounding, result size and address encoding. On ARM64e or tagged-zone builds, reserved pointer bits distinguish zone from VM allocations; low bits encode a zone size class or page count. Other builds use a different high-bit encoding. The decode helper reconstructs a kalloc_result; an encoded value is not an ordinary address to dereference before decoding. Array interface and contract, encode/decode implementations.

This is separate from ordinary kalloc_type(T, count, flags): both are array-oriented APIs, but the latter's type view does not by itself mean that its returned pointer contains encoded capacity. kalloc_next_good_size computes a growth class; VM-sized growth uses a page-rounded step derived from the requested period. Allocation, capacity growth and compiler type-layout classification are different decisions. Growth helper, API variants.

Sources and boundaries

The routing, class calculation, initial-sharing policy, allocation/free/realloc bodies and array encoding above were read directly. Type assignment, zone caches and reclaim, and VM guard allocation supply the deeper storage mechanisms. Compatibility and protected-memory interfaces follows IOKit, C++ and BSD callers into these routes.

This is a source trace for this checkout. No running kernel's zone assignment, tunable values or allocation distribution was measured. KASAN, MTE, architecture, external call sites and startup phase change the selected branches; comments describing older implementations are not treated as the current algorithm.