pavel-kirienko/o1heap

Constant-complexity deterministic memory allocator (heap) for hard real-time high-integrity embedded systems. There is very little activity because the project is finished and does not require further changes.

O(1) heap

O1heap is a highly deterministic constant-complexity memory allocator designed for hard real-time high-integrity embedded systems. The name stands for O(1) heap.

The allocator offers a constant worst-case execution time (WCET) and a well-characterized worst-case memory fragmentation (consumption) (WCMC). The allocator allows the designer to statically prove its temporal and spatial properties for a given application, which makes it suitable for use in high-integrity embedded systems.

The codebase is implemented in C99/C11 following MISRA C:2012, with several intended deviations which are unavoidable due to the fact that a memory allocator has to rely on inherently unsafe operations to fulfill its purpose. The codebase is extremely compact (<500 LoC) and is therefore trivial to validate.

The allocator is designed to be portable across all conventional architectures, from 8-bit to 64-bit systems.

Design

Objectives

The core objective of this library is to provide a dynamic memory allocator that meets the following requirements:

• Memory allocation and deallocation routines are constant-time.

• For a given peak memory requirement $M$, the worst-case memory consumption $H$ is predictable (i.e., the worst-case heap fragmentation is well-characterized). The application designer shall be able to easily predict the amount of memory that needs to be provided to the memory allocator to ensure that out-of-memory (OOM) failures provably cannot occur at runtime under any circumstances.

• The implementation shall be simple and conform to relevant high-integrity coding guidelines.

Theory

This implementation derives from or is based on the ideas presented in:

• "Timing-Predictable Memory Allocation In Hard Real-Time Systems" -- J. Herter, 2014.
• "An algorithm with constant execution time for dynamic storage allocation" -- T. Ogasawara, 1995.
• "Worst case fragmentation of first fit and best fit storage allocation strategies" -- J. M. Robson, 1975.

This implementation does not make any non-trivial assumptions about the behavioral properties of the application. Per Herter [2014], it can be described as a predictably bad allocator:

An allocator that provably performs close to its worst-case memory behavior which, in turn, is better than the worst-case behavior of the allocators discussed [in Herter 2014], but much worse than the memory consumption of these for normal programs without (mostly theoretical) bad (de-)allocation sequences.

While it has been shown to be possible to construct a constant-complexity allocator which demonstrates better worst-case and average-case memory requirements by making assumptions about the memory (de-)allocation patterns and/or by relying on more sophisticated algorithms, this implementation chooses a conservative approach where no assumptions are made about the application and the codebase is kept simple to facilitate its integration into verified and validated high-integrity software.

The library implements a modified half-fit algorithm -- a constant-complexity strategy originally proposed by Ogasawara. In this implementation, memory is allocated in fragments whose size is rounded up to the next integer power of two. The worst-case memory consumption (WCMC) $H$ of this allocation strategy has been shown to be:

$$ H(M,n) = 2 \ M \ (1 + \lceil{} \log_2 n \rceil{}) $$

Where $M$ is the peak total memory requirement of the application (i.e., sum of sizes of all allocated fragments when the heap memory utilization is at its peak) and $n$ is the maximum contiguous fragment that can be requested by the application. The provided equation is a generalized case that does not explicitly take into account a possible per-fragment metadata allocation overhead.

Memory allocators used in general-purpose (non-real-time and/or non-high-integrity) applications often leverage a different class of algorithms which may feature poorer worst-case performance metrics but perform (much) better on average. For a hard real-time system, the average case performance is generally less relevant, so it can be excluded from analysis.

The two-level segregated fit (TLSF) algorithm is a more complex $O(1)$ algorithm similar to half-fit that is often found in real-time applications. While TLSF provides a better average-case memory fragmentation due to its more sophisticated approach to heap segmentation, its worst-case fragmentation bound is often higher than that of half-fit (for practically useful heap parameters) and is the same as for an ordinary best-fit allocator, being approximately $H = M (n-2)$. Due to its increased internal complexity, TLSF offers a somewhat higher (albeit still constant) WCET and requires a larger number of lines of code to implement. From this it is possible to conclude that half-fit can be considered a superior choice for high-integrity applications compared to TLSF.

Allocation strategy	WCMC
First-fit	$H = M \ (1 + \lceil{} \log_2 n \rceil{})$
Half-fit	$H = 2 M \ (1 + \lceil{} \log_2 n \rceil{})$
Best-fit	$H = M \ (n - 2)$
TLSF	(see best-fit)

The state of catastrophic fragmentation is a state where the allocator is unable to serve a memory allocation request even if there is enough free memory due to its suboptimal arrangement. By definition, if the amount of memory available to the allocator is not less than $H$, then the state of catastrophic fragmentation cannot occur.

The above-defined theoretical worst-case upper bound H may be prohibitively high for some memory-constrained applications. It has been shown [Robson 1975] that under a typical workload, for a sufficiently high amount of memory available to the allocator which is less than $H$, the probability of a (de-)allocation sequence that results in catastrophic fragmentation is low. When combined with an acceptable failure probability and a set of adequate assumptions about the behaviors of the application, this property may allow the designer to reduce the amount of memory dedicated to the heap while ensuring a sufficient degree of predictability and reliability. The methods of such optimization are outside the scope of this document; interested readers are advised to consult with the referred publications.

Following some of the ideas from [Herter 2014], this implementation takes caching-related issues into consideration by choosing the most recently used memory fragments to minimize cache misses in the application.

Implementation

The implemented variant of half-fit allocates memory in fragments of size:

$$ F(r) = 2^{\lceil{} log_2 (r+a) \rceil{}} $$

Where $r&gt;0$ is the requested allocation size and $a$ is the fixed per-allocation metadata overhead implicitly introduced by the allocator for memory management needs. The size of the overhead $a$ is represented in the codebase as O1HEAP_ALIGNMENT, because it also dictates the allocated memory pointer alignment. Due to the overhead, the maximum amount of memory available to the application per allocation is $F^\prime{}(r) = F(r) - a$. The amount of the overhead per allocation and, therefore, pointer alignment is 4×(pointer width); e.g., for a 32-bit platform, the overhead/alignment is 16 bytes (128 bits).

From the above follows that $F(r) \ge 2 a$. Remember that $r&gt;0$ -- following the semantics of malloc(..), the allocator returns a null pointer if a zero-sized allocation is requested.

It has been mentioned that the abstract definition of $H$ does not take into account the implementation-specific overheads. Said overheads should be considered when calculating the amount memory needed for a specific application. We define a refined worst-case memory consumption (WCMC) model below.

$$ n_f = \lceil{} \frac{n}{l} \rceil{} $$

$$ M_f = \lceil{} \frac{M}{l} \rceil{} $$

$$ k = M_f - n_f + 1 $$

Where $l$ -- the smallest amount of memory that may be requested by the application; $n_f$ -- the size of the largest allocation expressed as the number of min-size fragments; $M_f$ -- the total amount of heap space that may be requested by the application in min-size fragments; $k$ -- the maximum number of fragments. The worst case number of min-size memory fragments required is $H_f(M_f,n_f) = H(M_f,n_f)$. The total amount of space needed to accommodate the per-fragment overhead is $k\times{}a$. Then, the total WCMC, expressed in bytes, is:

$$ H_b(M,n,l,a) = a \ k + \frac{ 2 \ l \ n \ M_f \ (\lceil{} log_2 \ n_f \rceil{} + 1) }{ l+n } $$

The above equation should be used for sizing the heap space. Observe that the case of $l=n$ degenerates to the standard fixed-size block allocator.

The following illustration shows the worst-case memory consumption (WCMC) for some common memory sizes; as explained above, $l$ is chosen by the application designer freely, and $a$ is the value of O1HEAP_ALIGNMENT which is platform-dependent:

Usage

Integration

Copy the files o1heap.c and o1heap.h (find them under o1heap/) into your project tree. Either keep them in the same directory, or make sure that the directory that contains the header is added to the set of include look-up paths. No special compiler options are needed to compile the source file (if you find this to be untrue, please open a ticket).

Dedicate a memory arena for the heap, and pass a pointer to it along with its size to the initialization function o1heapInit(..).

Allocate and deallocate memory using o1heapAllocate(..) and o1heapFree(..). Their semantics are compatible with malloc(..) and free(..) plus additional behavioral guarantees (constant timing, bounded fragmentation).

If necessary, periodically invoke o1heapDoInvariantsHold(..) to ensure that the heap is functioning correctly and its internal data structures are not damaged.

Avoid concurrent access to the heap. Use locking if necessary.

Build configuration options

The preprocessor options given below can be overridden to fine-tune the implementation. None of them are mandatory to use.

O1HEAP_CONFIG_HEADER

Define this optional macro like O1HEAP_CONFIG_HEADER="path/to/my_o1heap_config.h" to pass build configuration macros. This is useful because some build systems do not allow passing function-like macros via command line flags.

O1HEAP_ASSERT(x)

The macro O1HEAP_ASSERT(x) can be defined to customize the assertion handling or to disable it. To disable assertion checks, the macro should expand to (void)(x). If not specified, the macro expands to the standard assertion check macro assert(x) as defined in <assert.h>.

O1HEAP_LIKELY(x)

Some of the conditional branching statements are equipped with this annotation to hint the compiler that the generated code should be optimized for the case where the corresponding branch is taken. This is done to reduce the worst-case execution time.

The macro should expand to a compiler-specific branch weighting intrinsic, or to the original expression (x) if no such hinting is desired. If not specified, the macro expands as follows:

• For some well-known compilers the macro automatically expands to appropriate branch weighting intrinsics. For example, for GCC, Clang, and ARM Compiler, it expands to __builtin_expect((x), 1).
• For other (unknown) compilers it expands to the original expression with no modifications: (x).

O1HEAP_CLZ(x)

The count leading zeros (CLZ) function is used for fast binary logarithm computation (which has to be done multiple times per allocation, so its performance is critical). Most of the modern processors implement dedicated hardware support for fast CLZ computation, which is available via compiler intrinsics.

If not overridden by the user, for some compilers O1HEAP_CLZ(x) will expand to the appropriate intrinsic (e.g., __builtin_clzl(x) for GCC/Clang). For other compilers it will default to a slow software implementation, which is likely to significantly degrade the performance of the library.

Development

Dependencies

The following tools should be available locally to conduct library development:

• Modern versions of CMake, GCC, Clang, and Clang-Tools.
• An AMD64 machine.
• (optional) Valgrind.

Conventions

The codebase shall follow the Zubax C/C++ Coding Conventions. Compliance is enforced through the following means:

• Clang-Tidy -- invoked automatically while building the test suite.
• Clang-Format -- invoked manually as make format; enforced in CI/CD automatically.
• SonarCloud -- invoked by CI/CD automatically.

Testing

Please refer to the continuous integration configuration to see how to invoke the tests.

Releasing

Update the version number macro in the header file and create a new git tag like 1.0.

MISRA compliance

MISRA compliance is enforced with the help of the following tools:

• Clang-Tidy -- invoked automatically during the normal build process.
• SonarCloud -- invoked as part of the continuous integration build.

Every intentional deviation shall be documented and justified in-place using the following notation, followed by the appropriate static analyser warning suppression statement:

// Intentional violation of MISRA: <valid reason here>
// NOSONAR
// NOLINT

The list of intentional deviations can be obtained by simply searching the codebase for the above comments.

Do not suppress compliance warnings using the means provided by static analysis tools because such deviations are impossible to track at the source code level. An exception applies for the case of false-positive (invalid) warnings -- those should not be mentioned in the codebase.

Further reading

• Timing-Predictable Memory Allocation In Hard Real-Time Systems, J. Herter, 2014.
• Worst case fragmentation of first fit and best fit storage allocation strategies, J. M. Robson, 1975.
• Dynamic Memory Allocation In SQLite -- on Robson proof and deterministic fragmentation.
• [Russian] Динамическая память в системах жёсткого реального времени -- issues with dynamic memory allocation in modern embedded RTOS and related popular misconceptions.

Changelog

v2.1

• Significantly accelerate (de-)allocation by replacing the naïve log2 implementation with fast CLZ intrinsics; see O1HEAP_CLZ(x).
• Do not require char to be 8-bit wide: replace uint8_t with uint_fast8_t. This is to enhance compatibility with odd embedded platforms where CHAR_BIT!=8 (e.g., ADSP TS-201, TMS320C2804).

v2.0

• Remove critical section hooks to enhance MISRA conformance #4
• Add support for config header via O1HEAP_CONFIG_HEADER #5

v1.0

The first release.

License

The library is available under the terms of the MIT License. Please find it in the file LICENSE.

o1heap's Issues

Coverage metrics reported by SonarCloud are incorrect

SonarCloud reports coverage at 72.8%, while the actual value is 100%. I suspect this might be caused by the assertion macros --- each contains a conditional with two branches, of which one (the failure case) is never executed. We should find a way to exclude assertion checks from coverage analysis; perhaps we could set NDEBUG or build in RelWithDebInfo mode (although I'm worried that the latter may render coverage data less accurate due to optimization).

https://sonarcloud.io/component_measures?id=pavel-kirienko_o1heap&metric=coverage&selected=pavel-kirienko_o1heap%3Ao1heap%2Fo1heap.c&view=list

Provide the number of allocated fragments in the diagnostic struct

This is occasionally helpful for testing.

Assertion error

Hello, I am having the following error every now and then when using this library along with openCyphal.
Is there any insight in what could be causing this?

I am running the code on a Raspberry Pi Compute modul 4 64b OS

The error happens when sending a service request. I have not found a pattern for when the error happens

o1heap/o1heap/o1heap.c:364: o1heapAllocate: Assertion `frag->header.size >= amount + (sizeof(void*) * 4U)' failed.

Migrate to GitHub Actions

add o1HeapMaxSize

Add size_t o1HeapMaxSize(O1HeapInstance* const handle) so I can implement allocator_traits<T>::max_size(T&); when using in C++.

O1HeapDiagnostics peak alloc > peak requested, is this expected behaviour?

I've implemented a status message in my application to keep track of the O1Heap I'm using but I've noticed that the diagnostics function reports that peak_allocated is greater then peak_request_size.

INFO [uavcan_v1] Heap status 64/8000 Peak alloc 896 Peak req 256 OOM count 0

I would've expected them to be equal or that peak_request_size would be greater then peak_allocated. Is there a technical reason why this occurs?

Remove critical section hooks to enhance MISRA conformance

Remove critical section enter/leave hooks:

o1heap/o1heap/o1heap.h

Lines 98 to 99 in bd93277

	const O1HeapHook critical_section_enter,
	const O1HeapHook critical_section_leave);

Equivalent behaviors can be implemented by wrapping library calls in custom user code instead.

Feature request: memalign allocation.

Is it possible to implement O(1) memalign?

Use a dedicated config header instead of preprocessor macros

CMake does not support function-like macros, so it is not possible to override O1HEAP_ASSERT. Consider adding a config header instead of passing config options via the command line.

Add o1HeapReallocate

supporting realloc would be particularly powerful when an allocation's fragment size was much larger then the requested allocation. Subsequent reallocs would incur no memory movement costs where the new size remained within the size of the fragment.

o1heap asserting on frag == NULL

I am on an STM32G474.

This assert is failing?

https://github.com/pavel-kirienko/o1heap/blob/master/o1heap/o1heap.c#L328

Here are the diagnostics at the time of the error.

capacity = {size_t} 9824
allocated = {size_t} 64
peak_allocated = {size_t} 576
peak_request_size = {size_t} 40
oom_count = {uint64_t} 0

How can I fix this? It crashes the program which is not good for something intended to be flying :(

Should the o1heap opaque pointer be declared volatile? How about the memory arena? Should it also be volatile?

o1heap is being used inside an interrupt in my application as I use libcanard.

Question about specific use of O1HEAP_LIKELY

Hello! Thank you for publishing this code – I'm learning a lot from it! I noticed a line in o1heapAllocate that made me curious:

o1heap/o1heap/o1heap.c

Line 376 in aa3c253

if (O1HEAP_LIKELY((out == NULL) && (amount > 0U)))

If I understand correctly, this conditional checks for allocation failure with an allocation size greater than zero. In practice, we expect most allocations to succeed. If the purpose of O1HEAP_LIKELY is to signal to the compiler that an expression is likely to be true, why is this a good place to put O1HEAP_LIKELY?

It seems to me that that amount > 0 is likely, but out == NULL is not, and so the conjunction is unlikely.

Experiment: replace the standard heap in NuttX with O1Heap

Stock NuttX seems to be using a standard O(n) best-fit list-traversal allocator. It should be trivial to replace and benchmark.

provide an error code out argument for o1heapInit

int error_code = O1HEAP_NO_ERROR;
O1HeapInstance* h = o1heapInit(my_buffer, my_buffer_size, &error_code);

if (error_code == O1HEAP_ERR_BASE_TOO_SMALL)
{
    throw my_buffer_too_small_exception();
}

etc.