6. Memory management in CHERIoT RTOS

It is common for embedded systems to avoid heap allocation entirely and preallocate all memory that they will need. This means that the total amount of memory that a system requires is the sum of the peak memory usage of all components.

The CHERIoT platform is designed to enable safe reuse of memory. The shared heap allows memory to be dynamically allocated for individual uses and then reused. This means that the total memory requirement for a system becomes the peak combined usage of all components. If two components use a lot of memory at different times, they can safely share the same memory.

6.1. Understanding allocation capabilities

The memory allocator uses a capability model. Every caller of a memory allocation or deallocation function must present a capability that authorises allocation. This is a sealed capability to an AllocatorCapabilityState structure. Sealed capabilities were introduced in Section 1.4.

This uses the static sealing mechanism described in Section 4.11. There is no limit to the number of allocator capabilities that a compartment can hold. Each allocation capability holds an independent quota.

There is no requirement that the sum of all allocation quotas is less than the total available heap space. You can over-commit memory if you know that it will not all be needed at the same time. The quota mechanism gives you a way of limiting the total memory consumption of individual compartments (or groups of compartments) and of cleaning up after failure.

6.2. Creating custom allocation capabilities

A compartment may hold different allocation capabilities for different purposes. The heap_free_all function allows you to free all memory allocated with a specified capability and so using multiple allocation quotas can be useful for error recovery.

You can forward-declare an allocator capability with the DECLARE_ALLOCATOR_CAPABILITY macro. This takes a single argument: the name of the allocator capability. You can then define the allocator capability with the DEFINE_ALLOCATOR_CAPABILITY macro, which takes the name and the quota size as arguments. These can be combined with the DECLARE_AND_DEFINE_ALLOCATOR_CAPABILITY macro.

The allocator capabilities are exposed as COMDATs in C++. This allows them to be defined in a header and used in multiple translation units. C does not expose a similar mechanism and so you must use the separate declare and define macros in C if your compartment has more than one compilation unit that wish to share an allocator capability and define the capability in a single compilation unit.

In future versions of CHERIoT RTOS, allocator capabilities are likely to gain additional restrictions (for example, separating the ability to allocate from the ability to claim).

6.3. Recalling the memory safety guarantees

Every pointer to a new allocation provided by memory allocator is derived from a capability to a large heap region and bounded. The monotonicity guarantees in a CHERI system ensure that a caller cannot expand the bounds of the returned pointer.

The CHERIoT platform provides two additional features for temporal safety. These both depend on a revocation bitmap, a shadow memory space that stores one bit per eight bytes of heap memory. When an object is freed, the allocator paints the bits associated with it.

The load filter then ensures that any pointer to the object will have its tag cleared when it is loaded. This gives deterministic use-after-free protection; any attempt to use a pointer to a deallocated object will trap. The object is then placed in quarantine.

The revoker periodically scans all memory and invalidates any pointers whose base address points to a deallocated object. The monotonicity of bounds ensures that the base of a capability always points either somewhere within the allocation or, if the length is zero, to the word immediately after it.

The allocator marks the metadata between allocations as freed. This means that a zero-length capability to the end of an object is likely to be untagged.

The load filter ensures that no new pointers to deallocated objects can appear in memory and so the revocation sweep can proceed asynchronously. Any object that is in quarantine at the start of a sweep is safe to remove from quarantine at the end.

This combination of features allows the allocator to provide complete spatial and temporal safety for heap objects.

6.4. Allocating with an explicit capability

void * heap_allocate(Timeout * timeout,
                     struct SObjStruct * heapCapability,
                     size_t size)

Non-standard allocation API.

Allocates size bytes. Blocking behaviour is controlled by the timeout parameter.

The non-blocking mode will return a successful allocation if one can be created immediately, or nullptr otherwise. The blocking versions of this may return nullptr if the timeout has expired or if the allocation cannot be satisfied under any circumstances (for example if size is larger than the total heap size).

Memory returned from this interface is guaranteed to be zeroed.

int heap_free(struct SObjStruct * heapCapability,
              void * ptr)

Free a heap allocation.

Returns 0 on success, or -EINVAL if ptr is not a valid pointer to the start of a live heap allocation.

The heap_allocate and heap_free functions take a capability, as described above, that authorises allocation and deallocation. When an object is allocated with an explicit capability, it may be freed only by presenting the same capability. This means that, if you pass a heap-allocated buffer to another compartment, that compartment cannot free it unless you also pass the authorising capability.

The allocation uses a timeout because the allocation API is able to block if insufficient memory is available. In contrast the deallocation API will always make progress. The allocator uses a priority-inheriting lock, which is dropped while blocking. If a high-priority thread frees memory while a lower-priority thread owns the lock then the lower-priority thread will wake up, complete its allocation or deallocation, release the lock, and allow the higher-priority thread to resume.

If you need to clean up all memory allocated by a particular capability, heap_free_all will walk the heap and deallocate everything owned by that capability. This is useful when a compartment has crashed, to reclaim all of its heap memory.

ssize_t heap_free_all(struct SObjStruct * heapCapability)

Free all allocations owned by this capability.

Returns the number of bytes freed or -EPERM if this is not a valid heap capability.

6.5. Using C/C++ default allocators

If you are porting existing C/C++ code then it is likely that it uses malloc / free or the C++ new / delete operators. These are implemented as wrappers around heap_allocate and heap_free that pass MALLOC_CAPABILITY as the authorising capability. You can also pass this capability explicitly to allocate things from the same quota as the standard allocation routines.

MALLOC_CAPABILITY is a macro referring to the default allocation capability in the current compartment. It refers to a different capability in every compartment.

You can control the amount of memory provided by this capability by defining the MALLOC_QUOTA for your compartment. If a compartment is not supposed to allocate memory on its own behalf, you can define CHERIOT_NO_AMBIENT_MALLOC. This will disable C’s malloc and free and C++'s global new and delete operators. Defining CHERIOT_NO_NEW_DELETE will disable the global C++ operator new and delete, but leave malloc and free available.

Defining these does not prevent memory allocation, you can still define non-default allocator capabilities and use them directly, but it prevents accidental allocation.

6.6. Defining custom allocation capabilities for malloc and free

If you simply wish to change the quota that is available to malloc and free then you can define MALLOC_QUOTA when compiling your compartment. If you require more control, such as controlling the compilation unit that contains the definition of the allocator capability, then you can define CHERIOT_CUSTOM_DEFAULT_MALLOC_CAPABILITY. This macro will cause stdlib.h to provide a forward declaration of the default allocator capability, but not to define it. You must define it as described in Section 6.2.

This is most useful for C compartments with multiple compilation units. These will need to define the malloc capability in a single compilation unit.

This limitation will be removed in a future toolchain iteration.

6.7. Allocating on behalf of a caller

Sometimes a compartment needs to be able to allocate memory but that memory is not logically owned by the compartment. This pattern appears even in the core of the RTOS. The compartment that provides message queues, for example, allocates memory on behalf of a caller, it does not hold the right to allocate memory on its own behalf. It does this by taking an allocator capability as an argument and forwarding it to the allocator.

Often, if a compartment is allocating on behalf of a caller, it needs to ensure that the caller doesn’t tamper with the object. The token APIs provide a lightweight mechanism for doing this.

SObj token_sealed_unsealed_alloc(Timeout * timeout,
                                 struct SObjStruct * heapCapability,
                                 SKey key,
                                 size_t sz,
                                 void ** unsealed)

Allocate a new object with size sz.

An unsealed pointer to the newly allocated object is returned in *unsealed, the sealed pointer is returned as the return value.

The key parameter must have both the permit-seal and permit-unseal permissions.

On error, this returns INVALID_SOBJ.

void * token_obj_unseal(SKey,
                        SObj)

Unseal the obj given the key.

The key must have the permit-unseal permission.

int token_obj_destroy(struct SObjStruct * heapCapability,
                      SKey,
                      SObj)

Destroy the obj given its key, freeing memory.

The key must have the permit-unseal permission.

When you call token_sealed_unsealed_alloc, you must provide two capabilities:

  • An allocator capability.

  • A permit-seal sealing capability.

The first of these authorises memory allocation, the second authorises sealing. The CHERIoT ISA includes only three bits of object type space in the capability encoding and so the allocator provides a virtualised sealing mechanism. This allocates an object with a small header containing the sealing type and returns a sealed capability to the entire allocation and an unsealed capability to all except the header.

The unsealed capability can be used just like any other pointer to heap memory. The sealed capability can be used with token_obj_unseal to retrieve a copy of the unsealed capability. The token_obj_unseal function requires a permit-unseal capability whose value matches the permit-seal capability passed to token_sealed_unsealed_alloc.

The virtualised sealing mechanism must be able to derive an accurate capability for the object excluding the header. This is trivial for objects up to a little under 4 KiB. After that, the allocator will create some padding. The padding is placed at the start of the allocation, so you can see how much is there by querying the base and address of the returned (sealed) capability.

An object allocated in this way can be deallocated only by presenting both the allocator capability and the sealing capability that match the original allocation. This is very convenient for compartments that expose services because the memory cannot go away while they are using it and can be reclaimed only when the same caller (or something acting on its behalf) authorises the deallocation.

6.8. Ensuring that heap objects are not deallocated

If malicious caller passes a compartment a buffer and then frees it, then the callee can be induced to trap. There are some situations where this is acceptable. In some cases, compartments exist in a hierarchical trust relationship and it’s fine for a more-trusted compartment to be able to crash a less-trusted one. In other cases, the compartment is fault tolerant. For example, the scheduler ensures that its data structures are in a consistent state before performing any operations on user-provided data that may trap. As such, it can unwind to the caller and, at worst, leak memory owned by the caller.

In situations involving mutual distrust, the callee needs to claim the memory to prevent its deallocation. The heap_claim function allows you to place a claim on an object. The claim is dropped by calling heap_free.

While you have a claim on an object, that object counts towards your quota. You can claim the same object multiple times, each time adds a new claim to the object but (if it is already claimed with that quota) does not consume quota.

You can pass a capability with bounds that do not cover an entire object to heap_claim but your claim will cover the entire object because you cannot free part of an object.
size_t heap_claim(struct SObjStruct * heapCapability,
                  void * pointer)

Add a claim to an allocation.

The object will be counted against the quota provided by the first argument until a corresponding call to heap_free. Note that this can be used with interior pointers.