Single-header memory block pool allocator in C

memory_block.h

///                            ____                   ______            __          __
///                           / __ `____  ___  ____  / ____/_  ______  / /_  ____  / /
///                          / / / / __ `/ _ `/ __ `/ /   / / / / __ `/ __ `/ __ `/ /
///                         / /_/ / /_/ /  __/ / / / /___/ /_/ / /_/ / / / / /_/ / /
///                         `____/ .___/`___/_/ /_/`____/`__, / .___/_/ /_/`__,_/_/
///                             /_/                     /____/_/
///
/// A header-only implementation of a fairly standard O(1) free-list block pool allocator.
/// Consider also O1Heap (https://github.com/pavel-kirienko/o1heap) if a more conventional heap is required.
///
/// This software is distributed under the terms of the MIT License.
/// Copyright (C) OpenCyphal Development Team  <opencyphal.org>
/// Copyright Amazon.com Inc. or its affiliates.
/// SPDX-License-Identifier: MIT
/// Author: Pavel Kirienko <pavel@opencyphal.org>

#pragma once

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

#ifdef __cplusplus
extern "C"
{
#endif

/// A helper that defines a block pool allocator in a static local array.
/// Typically you would place this in a singleton factory function that returns the allocator.
#define MEMORY_BLOCK_ALLOCATOR_DEFINE(name_, block_size_bytes_, block_count_)                                    \
    alignas(max_align_t) static uint_least8_t name_##_pool[(block_size_bytes_) * (block_count_)];                \
    static memory_block_t name_ = memory_block_init(sizeof(name_##_pool), &name_##_pool[0], (block_size_bytes_))

/// The user shall not attempt to change any of the fields manually.
typedef struct memory_block_t
{
    // Constant pool parameters.
    size_t block_count;
    size_t block_size_bytes;

    // Read-only diagnostic values.
    size_t   used_blocks;      ///< Blocks in use at the moment.
    size_t   used_blocks_peak; ///< Maximum number of blocks used at any point in time.
    uint64_t request_count;    ///< Total number of allocation requests.
    uint64_t oom_count;        ///< Total number of out-of-memory errors.

    // Private fields.
    void* head;
} memory_block_t;

/// Constructs a memory block allocator bound to the specified memory pool.
/// The block count will be deduced from the pool size and block size; both may be adjusted to ensure alignment.
/// If the pool or block size are not properly aligned, some memory may need to be wasted to enforce alignment.
static memory_block_t memory_block_init(const size_t pool_size_bytes, void* const pool, const size_t block_size_bytes)
{
    // Enforce alignment and padding of the input arguments. We may waste some space as a result.
    const size_t   block_size_aligned = (block_size_bytes + sizeof(max_align_t) - 1U) & ~(sizeof(max_align_t) - 1U);
    size_t         pool_size_aligned_bytes = pool_size_bytes;
    uint_least8_t* ptr                     = (uint_least8_t*)pool;
    while ((((uintptr_t)ptr) % sizeof(max_align_t)) != 0U) {
        ptr++;
        if (pool_size_aligned_bytes > 0U) {
            pool_size_aligned_bytes--;
        }
    }
    const size_t block_count = pool_size_aligned_bytes / block_size_aligned;
    for (size_t i = 0U; i < block_count; i++) {
        void** const node = (void**)(void*)(ptr + (i * block_size_aligned));
        *node             = ((i + 1U) < block_count) ? (void*)(ptr + ((i + 1U) * block_size_aligned)) : NULL;
    }
    memory_block_t out   = { 0 };
    out.block_count      = block_count;
    out.block_size_bytes = block_size_aligned;
    out.head             = ptr;
    return out;
}

/// O(1) instant allocation. NULL if no free blocks left or if the size is zero or exceeds the block size.
static void* memory_block_allocate(memory_block_t* const self, const size_t size)
{
    void* out = NULL;
    assert(self != NULL);
    self->request_count++;
    if ((size > 0U) && (size <= self->block_size_bytes)) {
        out = self->head;
        if (self->head != NULL) {
            self->head = *(void**)self->head;
            self->used_blocks++;
            self->used_blocks_peak =
              (self->used_blocks > self->used_blocks_peak) ? self->used_blocks : self->used_blocks_peak;
        }
    }
    if (out == NULL) {
        self->oom_count++;
    }
    return out;
}

/// O(1) instant deallocation. The pointer may be NULL, in which case this is a no-op.
static void memory_block_deallocate(memory_block_t* const self, void* const pointer)
{
    assert(self != NULL);
    if (pointer != NULL) {
        *(void**)pointer = self->head;
        self->head       = pointer;
        assert(self->used_blocks > 0U);
        self->used_blocks--;
    }
}

#ifdef __cplusplus
}
#endif