doc/allocators/api-basics.md

# XNU Allocators best practices

## Introduction

XNU proposes two ways to allocate memory:

- the VM subsystem that provides allocations at the granularity of pages (with
  `kernel_memory_allocate` and similar interfaces);
- the zone allocator subsystem (`<kern/zalloc.h>`) which is a slab-allocator of
  objects of fixed size.

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>` for interfaces that need to be exported
  for introspection and implementation purposes, and is not meant
  for general consumption.

This document will present the best practices to allocate memory
in the kernel, from a security perspective.

## Permanent allocations

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.

## Allocation flags

Most `zalloc` or `kalloc` functions take `zalloc_flags_t` typed flags.
When flags are expected, exactly one of `Z_WAITOK`, `Z_NOWAIT` or `Z_NOPAGEWAIT`
is to be passed:

- `Z_WAITOK` means that the zone allocator can wait and block,
- `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, this is only useful
  for the buffer cache, and most client should either use `Z_NOWAIT` or `Z_WAITOK`.

Other important flags:

- `Z_ZERO` if zeroed memory is expected (nowadays most of the allocations will
  be zeroed regardless, but it's always clearer to specify it), note that it is
  often more efficient than calling bzero as the allocator tends to maintain
  freed memory as zeroed in the first place,
- `Z_NOFAIL` if the caller knows the allocation can't fail: allocations that are
   made with `Z_WAITOK` from regular (non exhaustible) zones, or from `kalloc*`
   interfaces with a size smaller than `KALLOC_SAFE_ALLOC_SIZE`,
  will never fail (the kernel will instead panic if no memory can be found).
  `Z_NOFAIL` can be used to denote that the caller knows about this.
  If `Z_NOFAIL` is incorrectly used, then the zone allocator will panic at runtime.

## Zones (`zalloc`)

The first blessed way to allocate memory in the kernel is by using zones.
Zones are mostly meant to be used in Core XNU and some "BSD" kexts.

It is generally recommended to create zones early and to store the `zone_t`
pointer in read-only memory (using `SECURITY_READ_ONLY_LATE` storage).

Zones are more feature-rich than `kalloc`, and some features can only be
used when making a zone:

- the object type being allocated requires extremely strong segregation
  from other types (typically `zone_require` will be used with this zone),
- the object type implements some form of security boundary and wants to adopt
  the read-only allocator (See `ZC_READONLY`),
- the allocation must be per-cpu,
- ...

In the vast majority of cases however, using `kalloc_type` (or `IOMallocType`)
is preferred.


## The Typed allocator

Ignoring VM allocations (or wrappers like `IOMemoryDescriptor`), the only
blessed way to allocate typed memory in XNU is using the typed allocator
`kalloc_type` or one of its variants (like IOKit's `IOMallocType`) and untyped
memory that doesn't contain pointers is using the data API `kalloc_data` or
one of its variants (like IOKit's `IOMallocData`). However, this comes with
additional requirements.

Note that at this time, those interfaces aren't exported to third parties,
as its ABI has not yet converged.

### A word about types

The typed allocators assume that allocated types fit a very precise model.
If the allocations you perform do not fit the model, then your types
must be restructured to fit, for security reasons.

A general theme will be the separation of data/primitive types from pointers,
as attackers tend to use data/pointer overlaps to carry out their exploitations.

The typed allocators use compiler support to infer signatures
of the types being allocated. Because some scalars actually represent
kernel pointers (like `vm_offset_t`,`vm_address_t`, `uintptr_t`, ...),
types or structure members can be decorated with `__kernel_ptr_semantics`
to denote when a data-looking type is actually a pointer.

Do note that `__kernel_data_semantics` and `__kernel_dual_semantics`
are also provided but should typically rarely be used.

#### fixed-sized types

The first case is fixed size types, this is typically a `struct`, `union`
or C++ `class`. Fixed-size types must follow certain rules:

- types should be small enough to fit in the zone allocator:
  smaller than `KALLOC_SAFE_ALLOC_SIZE`. When this is not the case,
  we have typically found that there is a large array of data,
  or some buffer in that type, the solution is to outline this allocation.
- for union types, data/pointer overlaps should be avoided if possible.
  when this isn't possible, a zone should be considered.

#### Variable-sized types

These come in two variants: arrays, and arrays prefixed with a header.
Any other case must be reduced to those, by possibly making more allocations.

An array is simply an allocation of several fixed-size types,
and the rules of "fixed-sized types" above apply to them.

The following rules are expected when dealing with variable sized allocations:

- variable sized allocations should have a single owner and not be refcounted;
- under the header-prefixed form, if the header contains pointers,
  then the array element type **must not** be only data.

If those rules can't be followed, then the allocation must be split with
the header becoming a fixed-sized type becoming the single owner
of an array.

#### Untyped memory

When allocating untyped memory with the data APIs ensure that it doesn't
contain kernel pointers. If your untyped allocation contains kernel pointers
consider splitting the allocation into two: one part that is typed and contains
the kernel pointers and the second that is untyped and data-only.

### API surface

<table>
  <tr>
    <th>Interface</th>
    <th>API</th>
    <th>Notes</th>
  </tr>
  <tr>
    <td>Data/Primitive types</td>
    <td>
      <p>
      <b>Core Kernel</b>:<br/>
      <tt>kalloc_data(size, flags)</tt><br/>
      <tt>krealloc_data(ptr, old_size, new_size, flags)</tt><br/>
      <tt>kfree_data(ptr, size)</tt><br/>
      <tt>kfree_data_addr(ptr)</tt>
      </p>
      <p>
      <b>IOKit untyped variant (returns <tt>void *</tt>)</b>:<br/>
      <tt>IOMallocData(size)</tt><br/>
      <tt>IOMallocZeroData(size)</tt><br/>
      <tt>IOFreeData(ptr, size)</tt>
      </p>
      <p>
      <b>IOKit typed variant (returns <tt>type_t *</tt>)</b>:<br/>
      <tt>IONewData(type_t, count)</tt><br/>
      <tt>IONewZeroData(type_t, count)</tt><br/>
      <tt>IODeleteData(ptr, type_t, count)</tt>
      </p>
    </td>
    <td>This should be used when the allocated type contains no kernel pointer only</td>
  </tr>
  <tr>
    <td>Fixed-sized type</td>
    <td>
      <p>
      <b>Core Kernel</b>:<br/>
      <tt>kalloc_type(type_t, flags)</tt><br/>
      <tt>kfree_type(type_t, ptr)</tt>
      </p>
      <p>
      <b>IOKit:</b><br/>
      <tt>IOMallocType(type_t)</tt><br/>
      <tt>IOFreeType(ptr, type_t)</tt>
      </p>
    </td>
    <td>
      <p>
      Note that this is absolutely OK to use this variant
      for data/primitive types, it will be redirected to <tt>kalloc_data</tt>
      (or <tt>IOMallocData</tt>).
      </p>
    </td>
  </tr>
  <tr>
    <td>Arrays of fixed-sized type</td>
    <td>
      <p>
      <b>Core Kernel</b>:<br/>
      <tt>kalloc_type(type_t, count, flags)</tt><br/>
      <tt>kfree_type(type_t, count, ptr)</tt>
      </p>
      <p>
      <b>IOKit:</b><br/>
      <tt>IONew(type_t, count)</tt><br/>
      <tt>IONewZero(type_t, count)</tt><br/>
      <tt>IODelete(ptr, type_t, count)</tt>
      </p>
    </td>
    <td>
      <p>
      <tt>kalloc_type(type_t, ...)</tt> (resp. <tt>IONew(type_t, 1)</tt>)
      <b>isn't</b> equivalent to <tt>kalloc_type(type_t, 1, ...)</tt>
      (resp. <tt>IOMallocType(type_t)</tt>). Mix-and-matching interfaces
      will result in panics.
      </p>
      <p>
      Note that this is absolutely OK to use this variant
      for data/primitive types, it will be redirected to <tt>kalloc_data</tt>.
      </p>
    </td>
  </tr>
  <tr>
    <td>Header-prefixed arrays of fixed-sized type</td>
    <td>
      <p>
      <b>Core Kernel</b>:<br/>
      <tt>kalloc_type(hdr_type_t, type_t, count, flags)</tt><br/>
      <tt>kfree_type(hdr_type_t, type_t, count, ptr)</tt>
      </p>
      <p>
      <b>IOKit:</b><br/>
      <tt>IONew(hdr_type_t, type_t, count)</tt><br/>
      <tt>IONewZero(hdr_type_t, type_t, count)</tt><br/>
      <tt>IODelete(ptr, hdr_type_t, type_t, count)</tt>
      </p>
    </td>
    <td>
      <p>
      <tt>hdr_type_t</tt> can't contain a refcount,
      and <tt>type_t</tt> can't be a primitive type.
      </p>
    </td>
  </tr>
</table>

## C++ classes and operator new.

### `OSObject` subclasses

All subclasses of `OSObject` must declare and define one of IOKit's
`OSDeclare*` and `OSDefine*` macros. As part of those, an `operator new` and
`operator delete` are injected that force objects to enroll into `kalloc_type`.

Note that idiomatic IOKit is supposed to use `OSTypeAlloc(Class)`.

### Other classes

Unlike `OSObject` subclasses, regular C++ classes must adopt typed allocators
manually. If your struct or class is POD then replacing usage of `new/delete`
with `IOMallocType/IOFreeType` is safe. However, if you have non default
structors or members of your class/struct have non default structors, then you
must override operator new/delete as follows, which lets you to continue to use
C++'s new and delete keywords to allocate/deallocate instances.

```cpp
struct Type {
public:
    void *operator new(size_t size)
    {
        return IOMallocType(Type);
    }

    void operator delete(void *mem, size_t size __unused)
    {
        IOFreeType(mem, Type);
    }
}
```
When operator new/delete is overriden for a specific class, all its subclasses
must also redefine their operator new/delete to use the typed allocators.

### The case of `operator new[]`

The ABI of `operator new[]` is unfortunate, as it denormalizes
data that we prefer to be known by the owning object
(the element sizes and array element count).

It also makes those allocations ripe for abuse in an adversarial
context as this denormalized information is at the begining
of the structure, making it relatively easy to attack with
out-of-bounds bugs.

However, if those must be used, the following can be used
to adopt typed allocators:

```cpp
struct Type {
    /* C++ ABI for operator new[] */
    struct cpp_array_header {
        size_t esize;
        size_t count;
    };

public:
    void *operator new[](size_t count)
    {
        struct cpp_array_hdr *hdr;
        hdr = IONew(struct cpp_array_hdr, Type, count);
        if (hdr) {
            hdr->esize = sizeof(Type);
            hdr->count = count;
            return (void *)(&hdr[1]);
        }
        return nullptr;
    }

    void operator delete[](void *ptr)
    {
        struct cpp_array_hdr *hdr;

        hdr = (struct cpp_array_hdr *)((uintptr_t)ptr - sizeof(*hdr));
        IODelete(hdr, struct cpp_array_hdr, Type, hdr->count);
    }
}
```

### Wrapping C++ type allocation in container OSObjects
The blessed way of wrapping and passing a C++ type allocation for use in the
libkern collection is using `OSValueObject`. Please do no use OSData for this
purpose as its backing store should not contain kernel pointers.