O1Heap Documentation

The library implements a modified half-fit algorithm. Memory is allocated in fragments whose size is rounded up to the next integer power of two.

Key Characteristics:

• Constant-time complexity: Both allocation and deallocation are $O(1)$.
• Predictable fragmentation: The worst-case memory consumption is well-characterized, making it suitable for hard real-time and high-integrity systems.
• Metadata Overhead: Each allocation incurs an overhead $a$, defined by O1HEAP_ALIGNMENT. This value also dictates the pointer alignment. On 32-bit platforms, this overhead is typically 8 bytes (2 $\times$ pointer width).
• Cache Optimization: The implementation uses the most recently used memory fragments to minimize cache misses.

Comparison of Strategies:

To ensure that out-of-memory (OOM) failures cannot occur at runtime, you must provide enough memory to account for the Worst-Case Memory Consumption (WCMC). This implementation uses a modified half-fit algorithm where memory is allocated in fragments rounded up to the next power of two.

To calculate the total required heap space in bytes ($H_b$), use the following refined WCMC model:

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

Parameters:

• $M$: Peak total memory requirement of the application (sum of all allocated fragments at peak utilization).
• $n$: Maximum contiguous fragment size requested by the application.
• $l$: The smallest amount of memory that may be requested (chosen freely by the designer).
• $a$: The per-allocation metadata overhead, represented by O1HEAP_ALIGNMENT (platform-dependent; e.g., 8 bytes on 32-bit platforms).
• $n_f = \lceil{} \frac{n}{l} \rceil{}$
• $M_f = \lceil{} \frac{M}{l} \rceil{}$
• $k = M_f - n_f + 1$

By providing at least $H_b$ bytes, you guarantee that 'catastrophic fragmentation' (where the allocator cannot serve a request despite having enough total free memory) cannot occur.

O1Heap is designed for easy integration into embedded projects. Follow these steps:

1. Copy Source Files: Copy o1heap.c and o1heap.h from the o1heap/ directory into your project tree.
2. Configure Includes: Ensure the directory containing o1heap.h is in your compiler's include search paths.
3. Prepare Memory Arena: Dedicate a memory arena (a block of memory) for the heap. Ensure the arena is properly aligned according to O1HEAP_ALIGNMENT.
4. Initialize: Call o1heapInit(..) with a pointer to your arena and its size.
5. Manage Concurrency: O1Heap does not handle concurrent access. If your application uses multiple threads or interrupts that access the heap, you must implement your own locking mechanism.

Note: No special compiler options are required for standard compilation.

/* Basic integration pattern */
#include "o1heap.h"
#include <stdalign.h>

// Define an aligned arena
static alignas(O1HEAP_ALIGNMENT) unsigned char heap_arena[32768];

void setup() {
    O1HeapInstance* heap = o1heapInit(heap_arena, sizeof(heap_arena));
    if (heap == NULL) {
        // Handle error: arena not aligned or too small
    }
}

You can fine-tune the O1Heap implementation using several preprocessor macros. These can be defined in your code or via compiler flags.

Warning: If O1HEAP_CLZ(x) is not mapped to a hardware-supported intrinsic on your architecture, performance will degrade significantly.

O1Heap provides a constant-time memory management API with semantics similar to malloc and free.

• o1heapInit(arena_ptr, size): Initializes the heap using the provided memory arena. Returns an O1HeapInstance* or NULL if initialization fails (e.g., due to alignment or insufficient size).
• o1heapAllocate(heap, size): Allocates size bytes of memory. This operation has a constant worst-case execution time (WCET).
• o1heapFree(heap, ptr): Deallocates the memory pointed to by ptr. This operation also has a constant WCET.
• o1heapDoInvariantsHold(heap): (Optional) Periodically invoke this to verify that the heap's internal data structures remain intact and uncorrupted.

#include "o1heap.h"

// ... initialization code ...

void* ptr = o1heapAllocate(heap, 200); // Constant-time allocation
if (ptr != NULL) {
    // Use memory
    o1heapFree(heap, ptr); // Constant-time deallocation
}

// Periodically check integrity
o1heapDoInvariantsHold(heap);