doc/allocators.md
XNU proposes two ways to allocate memory:
kernel_memory_allocate and similar interfaces);<kern/zalloc.h>) which is a slab-allocator of
objects of fixed size.This document describes all the allocator variants around the zone allocator, how to use them and what their security model is.
In addition to that, <kern/kalloc.h> provides a variable-size general purpose
allocator implemented as a collection of zones of fixed size, and overflowing to
kernel_memory_allocate for allocations larger than a few pages (32KB when this
document was being written but this is subject to change/tuning in the future).
The Core Kernel allocators rely on the following headers:
<kern/zalloc.h> and <kern/kalloc.h> for its API surface, which most
clients should find sufficient,<kern/zalloc_internal.h> and <kern/zcache_internal.h> for interfaces that
need to be exported for introspection and implementation purposes, and is not
meant for general consumption.This section will give a rapid decision tree of which allocation method to use, and general best practices. The rest of the document goes into more details and offers more information that can explain the rationale behind these recommendations.
If you are allocating memory that is never freed, use zalloc_permanent*. If
the allocation is larger than a page, then it will use
kernel_memory_allocate with the KMA_PERMANENT flag on your behalf.
The allocation is assumed to always succeed (this is mostly reserved for early
allocations that need to scale with the configuration of the machine and
cannot be decided at compile time), and will be zeroed.
If the memory you are allocating is temporary and will not escape the scope
of the syscall it's used for, use kheap_alloc and kheap_free with the
KHEAP_TEMP heap. Note that temporary paths should use zalloc(ZV_NAMEI).
If the memory you are allocating will not hold pointers, and even more so
when the content of that piece of memory can be directly influenced by
user-space, then use kheap_alloc and kheap_free with the
KHEAP_DATA_BUFFERS heap.
In general we prefer zalloc or kalloc interfaces, and would like to abandon any legacy MALLOC/FREE interfaces over time.
For all kalloc or kheap_alloc variants, these advices apply:
Z_WAITOK semantics (allocation can block), consider adding Z_NOFAIL,bzero the memory on allocation, instead pass Z_ZERO which can be
optimized away more often than not.Performance wise, it is problematic to make a zone when the kernel tends to have less than several pages worth of elements allocated at all times (think commonly 200k+ objects). When a zone is underutilized, then fragmentation becomes a problem.
Zones with a really high traffic of allocation and frees should consider using zone caching, but this comes at a memory usage cost and needs to be evaluated.
Security wise, the following questions need answering:
zone_require() and will by default sequester the
virtual address space;ZV_NAMEI one for paths) instead;ZC_ZFREE_CLEARMEM will likely be a really marginal incremental cost that can
discover write-after-free bugs.There are several allocation wrappers in XNU, present for various reasons
ranging from additional accounting features (IOKit's IONew), conformance to
language requirements (C++ various new operators) or organic historical
reasons.
zalloc and kalloc are considered the primitive allocation interfaces which
are used to implement all the other ones. The following table documents all
interfaces and their various properties.
Until this limitation is lifted, general exposition to arbitrary
kernel extensions is problematic.
</td>
In kernel extensions, `kalloc` is equivalent to `kheap_alloc(KHEAP_KEXT)`.
Due to legacy contracts where allocation and deallocation happen on
different sides of the XNU/Kext boundary, `kfree` will allow to free to
either heaps. New code should consider using the proper `kheap_*` variant
instead.
</td>
Only kernel extensions that are providing core infrastructure
(filesystems, sandbox, ...) and are out-of-tree core kernel components
should use the primitive `zalloc` or `kalloc` directly.
</td>
When creating a subclass of `OSObject` with the IOKit macros to do so, an
`operator new` and `operator delete` is provided for this object that will
anchor this type to the `KHEAP_DEFAULT` heap when the class is defined in
Core XNU, or to the `KHEAP_KEXT` heap when the class is defined in a
kernel extension.
</td>
For backward compatbility reasons, it is still exported, but behaves
exactly like `MALLOC` otherwise.
</td>
Zones are created with zone_create(), and really meant never to be destroyed.
Destructible zones are here for legacy reasons, and not all features are
available to them.
Zones allocate their objects from a specific fixed size map called the Zone Map. This map is subdivided in a few submaps that provide different security properties:
It is worth noting that use of any allocation function in interrupt context is never allowed in XNU, as none of our allocators are re-entrant and interrupt safe.
<kern/zalloc.h> defines several flags that can be used to alter the blocking
behavior of zalloc and kalloc:
Z_NOWAIT can be used to require a fully non blocking behavior, which can be
used for allocations under spinlock and other preemption disabled contexts;Z_NOPAGEWAIT allows for the allocator to block (typically on mutexes),
but not to wait for available pages if there are none;Z_WAITOK means that the zone allocator can wait and block.It is worth noting that unless the zone is exhaustible or "special" (which is
mostly the case for VM zones), then zalloc will never fail (but might block
for arbitrarily long if the zone map is under a lot of pressure). This is not
true of kalloc when the allocation is served by the VM.
It is worth noting that Z_ZERO is provided so that the allocation returned by
the allocator is always zeroed. This should be used instead of manual usage of
bzero as the zone allocator is able to optimize it away when certain security
features that already guarantee the zeroing are engaged.
Zones that have relatively fast allocation/deallocation patterns can use zone
caching (passing ZC_CACHING) to zone_create(). This enables per-CPU caches,
which hold onto several allocations per CPU. This should not be done lightly,
especially for zones holding onto large elements.
zone_require())In order to be slightly more resilient to Use after Free (UaF) bugs, XNU provides two techniques:
ZC_SEQUESTER flag to zone_create();zone_require() or zone_id_require().The first form will cause the virtual address ranges that a given zone uses to never be returned to the system, which essentially pins this address range for holding allocations of this particular zone forever. When a zone is strongly typed, it means that only objects of that particular type can ever be located at this address.
zone_require() is an interface that can be used prior to memory use to assert
that the memory belongs to a given zone.
Both these techniques can be used to dramatically reduce type confusion bugs.
For example, the task zone uses both sequestering and judicious usage of
zone_require() in crucial parts which makes faking a task_t and using it
to confuse the kernel extremely difficult.
When zone_require() can be used exhaustively in choking points, then
sequestering is no longer necessary to protect this type. For example, the
ipc_port_t, will take the ip_lock() or an ip_reference() prior to any
interesting use. These primitives have been extended to include a
zone_id_require() (the fastest existing form of zone_require()) which gives
us an exhaustive protection. As a result, it allows us not to sequester the
ports zone. This is interesting because userspace can cause spikes of
allocations of ports and this protects us from zone map exhaustion or more
generally increase cost to describe the sequestered address space of this zone
due to a high peak usage.
IOKit is a subsystem that is often used by attackers, and reducing type confusion attacks against it is desireable. For this purpose, XNU exposes the ability to create a zone rather than being allocated in a kalloc heap.
Using the OSDefineMetaClassAndStructorsWithZone or any other
OSDefineMetaClass.*WithZone interface will cause the object's operator new
and operator delete to back the storage of these objects with zones. This is
available to first party kexts, and usage should be reserved to types that can
easily be allocated by user-space and in large quantities enough that the
induced fragmentation is acceptable.
A lot of bugs come from partially initialized data, or write-after-free. To mitigate these issues, zones provide two level of protection:
ZC_ZFREE_CLEARMEM).Page clearing is used when new pages are added to the zone. The original version of the zone allocator would cram pages into zones without changing their content. Memory crammed into a zone will be cleared from its content. This helps mitigate leaking/using uninitialized data.
Element clear on free is an increased protection that causes zfree() to erase
the content of elements when they are returned to the zone. When an element is
allocated from a zone with this property set, then the allocator will check that
the element hasn't been tampered with before it is handed back. This is
particularly interesting when the allocation codepath always clears the returned
element: when using the Z_ZERO (resp. M_ZERO) with zalloc or kalloc
(resp. MALLOC), then the zone allocator knows not to issue this extraneous
zeroing.
ZC_ZFREE_CLEARMEM at the time this document was written was default for any
zone where elements are smaller than 2 cachelines. This technique is
particularly interesting because things such as locks, refcounts or pointers
valid states can't be all zero. It makes exploitation of a Use-after-free more
difficult when this is engaged.
The zone allocator also does statistical poisoning (see source for details).
It also always zeroes the first 2 cachelines of any allocation on free, when
ZC_ZFREE_CLEARMEM isn't engaged. It sometimes mitigates certain kind of linear
buffer overflows. It also can be leveraged by types that have refcounts or locks
if those are placed "early" in the type definition, as zero is not a valid value
for such concepts.
The zone allocator provides ZC_PERCPU as a way to declare a per-cpu zone.
Allocations from this zone are returning NCPU elements with a known stride.
It is expected that such allocations are not performed in a rapid pattern, and zone caching is not available for them. (zone caching actually is implemented on top of a per-cpu zone).
Usage of per-cpu zone should be limited to extremely performance sensitive codepaths or global counters due to the enormous amplification factor on many-core systems.
The kernel sometimes needs to provide persistent allocations that depend on parameters that aren't compile time constants, but will not vary over time (NCPU is an obvious example here).
The zone subsystem provides a zalloc_permanent* family of functions that help
allocating memory in such a fashion in a very compact way.
Unlike the typical zone allocators, this allows for arbitrary sizes, in a
similar fashion to kalloc. These functions will never fail (if the allocation
fails, the kernel will panic), and always return zeroed memory. Trying to free
these allocations results in a kernel panic.
Kalloc is a general malloc-like allocator that is backed by zones when the size
of the allocation is sub-page (actually smaller than 32K at the time this
document was written, but under KASAN or other memory debugging techniques, this
limit for the usable payload might actually be lower). Larger allocations use
kernel_memory_allocate (KMA).
The kernel calls the collection of zones that back kalloc a "kalloc heap", and provides 3 builtin ones:
KHEAP_DEFAULT, the "default" heap, is the one that serves kalloc in Core
Kernel (XNU proper);KHEAP_KEXT, the kernel extension heap, is the one that serves kalloc in
kernel extensions (see "redirected" symbols in the Variants table above);KHEAP_DATA_BUFFERS which is a special heap, which allocates out of the "User
Data" submap, and is meant for allocation of payloads that hold no pointer and
tend to be under the control of user space (paths, pipe buffers, OSData
backing stores, ...).In addition to that, the kernel provides an extra "magical" kalloc heap:
KHEAP_TEMP, it is for all purposes an alias of KHEAP_DEFAULT but enforces
extra semantics: allocations and deallocations out of this heap must be
performed "in scope". It is meant for allocations that are made to support a
syscall, and that will be freed before that syscall returns to user-space.
The usage of KHEAP_TEMP will ensure that there is no outstanding allocation at
various points (such as return-to-userspace) and will panic the system if this
property is broken. The kheap_temp_debug=1 boot-arg can be used on development
kernels to debug such issues when the occur.
As far as security policies are concerned, the default and kext heap are fully segregated per size-class. The data buffers heap is isolated in the user data submaps, and hence can never produce adresses aliasing with any other kind of allocations in the system.
The zone subsystem provides several accounting properties that are reported by
the zprint(1) command. Historically, some zones have been introduced to help
with accounting, to the cost of increased fragmentation (the more allocations
are issued from the same zone, the lower the fragmentation). It is now possible
to define zone views and kalloc heap aliases, which are two similar concepts for
zones and kalloc heaps respectively.
Zone views are declared (in headers) and defined (in modules) with
ZONE_VIEW_DECLARE and ZONE_VIEW_DEFINE, and can be an alias either for
another regular zone, or a specific zone of a kalloc heap. This is for example
used for the ZV_NAMEI zone out of which temporary paths are allocated (this is
an alias to the KHEAP_DATA_BUFFERS 1024 bytes zone). Extra accounting is
issued for these views and are also reported by zprint(1).
In a similar fashion, KALLOC_HEAP_DECLARE and KALLOC_HEAP_DEFINE can be used
to declare a kalloc heap alias that gets its own accounting. It is particularly
useful to track leaks and various other things.
The accounting of zone and heap views isn't free (and has a per-CPU cost) and should be used wisely. However, if the alternative is a fully separated zone, then the memory cost of the accounting would likely be dwarfed by the fragmentation cost of the new zone.
At this time, views can only be made by Core Kernel.