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. Sealing pointers for tamper proofing.
This uses the static sealing mechanism described in Section 4.13. Building software capabilities with sealing. 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 capability 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, uint32_t flags)Non-standard allocation API. Allocates size bytes.
The heapCapability quota object must have remaining capacity sufficient for the requested size as well as any padding required by the CHERIoT capability encoding (see its ISA document for details) and any additional space required by the allocator's internal layout, which may be up to CHERIOTHeapMinChunkSize bytes. Not all of these padding bytes may be available for use via the returned capability.
Blocking behaviour is controlled by the flags and the timeout parameters. Specifically, the flags parameter defines on which conditions to wait, and the timeout parameter how long to wait.
The non-blocking mode (AllocateWaitNone, or timeout with no time remaining) will return a successful allocation if one can be created immediately, or nullptr otherwise.
The blocking modes may return nullptr if the condition to wait is not fulfiled, 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).
This means that calling this with AllocateWaitAny and UnlimitedTimeout will only ever return nullptr if the allocation cannot be satisfied under any circumstances.
In both blocking and non-blocking cases, -ENOTENOUGHSTACK may be returned if the stack is insufficiently large to safely run the function. This means that the return value of heap_allocate should be checked for the validity of the tag bit *and not* nullptr.
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, -EINVAL if ptr is not a valid pointer to the start of a live heap allocation, or -ENOTENOUGHSTACK if the stack size is insufficiently large to safely run the function.
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, -EPERM if this is not a valid heap capability, or -ENOTENOUGHSTACK if the stack size is insufficiently large to safely run the function.
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. Creating custom allocation capabilities.
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 object given the key.
The key may be either a static or dynamic key (i.e. one created with the STATIC_SEALING_TYPE macro or with token_key_new) and the object may be either allocated dynamically (via the token APIs) or statically (via the DEFINE_STATIC_SEALED_VALUE macro).
Returns the unsealed object if the key and object are valid and of the correct type, null otherwise.
This function is equivalent to calling both token_obj_unseal_static and token_obj_unseal_dynamic and returning the result of the first one that succeeds, or null if both fail.
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.
ssize_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.
This will return the size of the allocation claimed on success (which may be larger than the size requested in the original heap_allocate call; see its documentation for more information), 0 on error (if heapCapability or pointer is not valid, etc.), or -ENOTENOUGHSTACK if the stack is insufficiently large to run the function.
If you need to ensure that an allocation remains valid for a brief, scoped, period then heap_claim_fast may be more useful. This function places an ephemeral claim on one or two objects.
The heap_claim_fast function is poorly named (and will probably be renamed something like heap_claim_ephemeral in a future version). It is not just a fast version of heap_claim, it is a different function with different guarantees.
int heap_claim_fast(Timeout * timeout, const void * ptr, const void * ptr2)Interface to the fast claims mechanism. This claims two pointers using the hazard-pointer-inspired lightweight claims mechanism. If this function returns zero then the heap pointers are guaranteed not to become invalid until either the next cross-compartment call or the next call to this function.
A null pointer can be used as a not-present value. This function will treat operations on null pointers as unconditionally successful. It returns -ETIMEDOUT if it failed to claim before the timeout expired, or EINVAL if one or more of the arguments is neither null nor a valid pointer at the end.
In the case of failure, neither pointer will have been claimed.
This function is provided by the compartment_helpers library, which must be linked for it to be available.
Every thread has two hazard slots that can hold pointers. The heap_claim_fast function manages these two slots. These are cleared on every cross-compartment call and can be cleared explicitly by passing NULL to heap_claim_fast.
If a pointer passed to heap_free is present in the allocator, the allocator will defer freeing the object. Writing to the hazard slots is very fast. Unlike heap_claim, this does not require a cross-compartment call.
Any claim applied with heap_claim_fast is lost on any cross-compartment call. This includes any blocking operation, which will invoke the scheduler. In general, do not use heap_claim_fast for anything other than a local read or write of a single object.
The heap_claim_fast API is intended for very brief accesses to objects. You can claim two pointers to support the common pattern of memcpy between two caller-provided (i.e. untrusted) buffers. You can claim both and then copy between them.