C语言的固定块内存分配器

• 下载 C_Allocator.zip - 23.2 KB

引言

1998 年，我在《嵌入式系统编程》杂志上发表了一篇关于固定块内存分配器的文章。我因此获得了 750 美元。如今，文章都在 Code Project 等网站上免费发表。时代真是变了。

不变的是固定块分配器的实用性。在某些设备上，使用全局堆是绝对禁止的。纵观我的职业生涯，我写了无数个固定块内存分配器，以在内存受限的系统中提供高速的动态分配。一个通用、设计良好的固定块分配器通过在禁止使用堆的系统中提供动态内存分配，开辟了应用程序实现的可能性。

在 Code Project 上，我记录了各种 C++ 分配器实现（请参阅“参考文章”部分）。这一次，我将介绍一个 C 语言版本，它具有适合嵌入式设备或其他用途的独特功能。

此处提供的解决方案将

• 比全局堆更快
• 易于使用
• 线程安全
• 支持 malloc、free、realloc 和 calloc 的固定块版本
• 占用最少的代码空间
• 以固定时间执行
• 消除堆碎片内存故障
• 无需额外的存储开销（除了少量静态内存）
• 处理内存对齐
• 根据需求自动分配可变大小的块（类似 malloc）

两个简单的 C 模块，用于分配和回收内存，将提供上述所有好处，我将对此进行展示。

使用 CMake 创建构建文件。CMake 是免费开源软件。支持 Windows、Linux 和其他工具链。有关更多信息，请参阅 **CMakeLists.txt** 文件。

查看 GitHub 以获取最新源代码

• C 语言中的固定块内存分配器 - 作者：David Lafreniere

背景

自定义固定块内存分配器用于解决至少两类与内存相关的问题。首先，全局堆分配/释放可能速度慢且不确定。你永远不知道内存管理器需要多长时间。其次，消除因堆碎片导致的内存分配故障的可能性——这是一个有效的问题，尤其是在任务关键型系统上。

即使系统不被认为是任务关键型的，一些嵌入式系统也被设计为运行数周或数年而无需重启。根据分配模式和堆实现，长期使用堆可能导致堆故障。

fb_allocator

每个 fb_allocator 实例处理一个单一的块大小。接口如下所示

void ALLOC_Init(void);
void ALLOC_Term(void);
void* ALLOC_Alloc(ALLOC_HANDLE hAlloc, size_t size);
void* ALLOC_Calloc(ALLOC_HANDLE hAlloc, size_t num, size_t size);
void ALLOC_Free(ALLOC_HANDLE hAlloc, void* pBlock);

ALLOC_Init() 在启动时调用一次，ALLOC_Term() 在关闭时调用。其余的 API 操作方式与 CRT 的对应函数相同；ALLOC_Alloc() 分配内存，ALLOC_Free() 释放内存。

fb_allocator 实例使用文件作用域的 ALLOC_DEFINE 宏创建。下面的 TestAlloc 分配器定义了一个具有最多五个 16 字节块的固定块分配器。

ALLOC_DEFINE(TestAlloc, 16, 5);

分配一个 16 字节的块很简单。

void* data = ALLOC_Alloc(TestAlloc, 16);

完成后释放该块。

ALLOC_Free(TestAlloc, data);

x_allocator

x_allocator 模块使用两个或多个 fb_allocator 实例处理多个内存块大小；每个块大小对应一个 fb_allocator。在分配期间，x_allocator 根据调用者请求的大小，从其中一个 fb_allocator 实例返回一个块。x_allocator API 如下所示

void* XALLOC_Alloc(XAllocData* self, size_t size);
void XALLOC_Free(void* ptr);
void* XALLOC_Realloc(XAllocData* self, void *ptr, size_t new_size);
void* XALLOC_Calloc(XAllocData* self, size_t num, size_t size);

x_allocator 的用户通常会创建一个薄的包装器模块，该模块 (a) 定义两个或多个 fb_allocator 实例，以及 (b) 提供一个自定义 API 来访问 x_allocator 内存。通过一个简单的例子更容易解释。

my_allocator

假设我们想要一个固定块内存分配器来分配两种块大小：32 和 128。我们称之为 my_allocator，API 如下所示

void* MYALLOC_Alloc(size_t size);
void MYALLOC_Free(void* ptr);
void* MYALLOC_Realloc(void *ptr, size_t new_size);
void* MYALLOC_Calloc(size_t num, size_t size);

该实现创建了多个 fb_allocator 实例；一个实例负责处理每种所需的块大小。在这种情况下，我们将允许最多十个 32 字节的块和五个 128 字节的块。

#include "my_allocator.h"
#include "x_allocator.h"

// Maximum number of blocks for each size
#define MAX_32_BLOCKS   10
#define MAX_128_BLOCKS  5

// Define size of each block including meta data overhead
#define BLOCK_32_SIZE     32 + XALLOC_BLOCK_META_DATA_SIZE
#define BLOCK_128_SIZE    128 + XALLOC_BLOCK_META_DATA_SIZE

// Define individual fb_allocators
ALLOC_DEFINE(myDataAllocator32, BLOCK_32_SIZE, MAX_32_BLOCKS)
ALLOC_DEFINE(myDataAllocator128, BLOCK_128_SIZE, MAX_128_BLOCKS)

// An array of allocators sorted by smallest block first
static ALLOC_Allocator* allocators[] = {
    &myDataAllocator32Obj,
    &myDataAllocator128Obj
};

#define MAX_ALLOCATORS   (sizeof(allocators) / sizeof(allocators[0]))

static XAllocData self = { allocators, MAX_ALLOCATORS };

现在，简单的单行包装器函数提供了对底层 x_allocator 模块的访问。

void* MYALLOC_Alloc(size_t size)
{
    return XALLOC_Alloc(&self, size);
}

void MYALLOC_Free(void* ptr)
{
    XALLOC_Free(ptr);
}

void* MYALLOC_Realloc(void *ptr, size_t new_size)
{
    return XALLOC_Realloc(&self, ptr, new_size);
}

void* MYALLOC_Calloc(size_t num, size_t size)
{
    return XALLOC_Calloc(&self, num, size);
}

当调用者使用介于 1 到 32 之间的大小调用 MYALLOC_Alloc() 时，将返回一个 32 字节的块。如果请求的大小介于 33 到 128 之间，则提供一个 128 字节的块。MYALLOC_Free() 将块返回到原始的 fb_allocator 实例。通过这种方式，一组固定块内存分配器被组合在一起，根据应用程序需求在运行时提供可变大小的内存块。示例包装器模式会反复使用，为系统内的特定用途提供内存块组。

实现细节

分配器实现的大部分内容相对直接。但是，我将解释一些细节以帮助理解关键概念。

fb_allocator 空闲列表

这是一种巧妙的技术，可以在不消耗任何额外存储空间用于指针的情况下将块链接到空闲列表中。在用户调用 ALLOC_Free() 之后，一个固定内存块不再被使用，并被释放用于其他用途，例如下一个指针。由于 fb_allocator 模块需要保留已删除的块，我们将列表的下一个指针放在当前未使用的块空间中。当块被应用程序重新使用时，指针不再需要，将被用户对象覆盖。这样，链接块就不会产生每个实例的存储开销。

空闲列表实际上实现为一个单向链表，但代码只在头部添加/删除，因此其行为类似于堆栈。使用堆栈可以使分配/释放非常快速且确定。无需循环搜索空闲块——只需推送或弹出块即可。

将释放的对象空间用作链接块的内存意味着对象必须足够大以容纳一个指针。ALLOC_BLOCK_SIZE 宏确保满足最小尺寸要求。

fb_allocator 内存对齐

某些嵌入式系统要求内存按特定字节边界对齐。由于分配器的内存是一个连续的 static 字节数组，块从非对齐边界开始可能会在某些 CPU 上导致硬件异常。例如，如果需要 4 字节对齐，13 字节的块将导致问题。将 ALLOC_MEM_ALIGN 更改为所需的字节边界。块大小将向上舍入到最近的对齐边界。

x_allocator 元数据

x_allocator 实现为每个块添加 4 字节的元数据。例如，如果用户需要 32 字节的块，x_allocator 实际上使用 36 字节的块。额外的 4 字节用于隐藏块内的 fb_allocator 指针（假设指针大小为 4 字节）。

删除内存时，x_allocator 需要原始的 fb_allocator 实例，以便将 deallocation 请求路由到正确的 fb_allocator 实例进行处理。与 XALLOC_Alloc() 不同，XALLOC_Free() 不接受大小，只使用 void* 参数。因此，XALLOC_Alloc() 实际上通过在请求中添加额外的 4 字节，将一个指向 fb_allocator 的指针隐藏在内存块的未使用的部分。调用者获得指向块的客户端区域的指针，其中隐藏的 fb_allocator 指针不会被覆盖。

void* XALLOC_Alloc(XAllocData* self, size_t size)
{
    ALLOC_Allocator* pAllocator;
    void* pBlockMemory = NULL;
    void* pClientMemory = NULL;

    ASSERT_TRUE(self);

    // Get an allocator instance to handle the memory request
    pAllocator = XALLOC_GetAllocator(self, size);

    // An allocator found to handle memory request?
    if (pAllocator)
    {
        // Get a fixed memory block from the allocator instance
        pBlockMemory = ALLOC_Alloc(pAllocator, size + XALLOC_BLOCK_META_DATA_SIZE);
        if (pBlockMemory)
        {
            // Set the block ALLOC_Allocator* ptr within the raw memory block region
            pClientMemory = XALLOC_PutAllocatorPtrInBlock(pBlockMemory, pAllocator);
        }
    }
    else
    {
        // Too large a memory block requested
        ASSERT();
    }

    return pClientMemory;
} 

当调用 XALLOC_Free() 时，分配器指针将从内存块中提取出来，以便调用正确的 fb_allocator 实例来释放块。

void XALLOC_Free(void* ptr)
{
    ALLOC_Allocator* pAllocator = NULL;
    void* pBlock = NULL;

    if (!ptr)
        return;

    // Extract the original allocator instance from the caller's block pointer
    pAllocator = XALLOC_GetAllocatorPtrFromBlock(ptr);
    if (pAllocator)
    {
        // Convert the client pointer into the original raw block pointer
        pBlock = XALLOC_GetBlockPtr(ptr);

        // Deallocate the fixed memory block
        ALLOC_Free(pAllocator, pBlock);
    }
}

基准测试

在 Windows PC 上对分配器性能与全局堆进行基准测试，可以清楚地看到代码的速度有多快。通过在一定程度上交错地分配和释放 20000 个 4096 和 2048 字节的块的基本测试，可以测试速度的改进。有关确切算法，请参阅附加的源代码。

Windows 分配时间（毫秒）

分配器	模式	Run	基准测试时间（毫秒）
全局堆	Release	1	36.3
全局堆	Release	2	33.8
全局堆	Release	3	32.8
fb_allocator	静态池	1	22.6
fb_allocator	静态池	2	3.7
fb_allocator	静态池	3	4.9
x_allocator	静态池	1	33.9
x_allocator	静态池	2	6.9
x_allocator	静态池	3	7.7

Windows 在调试器内执行时使用调试堆。调试堆会添加额外的安全检查，从而降低了性能。发布堆速度更快，因为禁用了检查。可以通过在 **调试** > **环境** 项目选项中将 _NO_DEBUG_HEAP=1 设置为在 Visual Studio 中禁用调试堆。

此基准测试非常简单，更现实的场景，具有不同的块大小和随机的 new/delete 间隔，可能会产生不同的结果。但是，基本要点得到了很好的说明；内存管理器比分配器慢，并且高度依赖于平台的实现。

fb_allocator 使用静态内存池，不依赖于堆。一旦空闲列表填充了块，其执行时间就很快，大约为 4 毫秒。fb_allocator 运行 1 的 22.6 毫秒是第一次运行时将固定内存池分割成单个块所花费的时间。

bm_allocator 模块中使用的 x_allocator 速度稍慢，约为 7 毫秒，因为它具有分配/释放多个大小块的开销，而 fb_allocator 只支持一种块大小。

与 Windows 全局堆相比，fb_allocator 快约 8 倍，x_allocator 快约 5 倍。在嵌入式设备上，我曾见过比全局堆快 15 倍的速度提升。

线程安全

LockGuard 模块中的 LK_LOCK 和 LK_UNLOCK 宏实现了线程安全所需的软件锁。根据您的平台操作系统要求更新锁实现。

参考文章

• 高效的 C++ 固定块内存分配器 - 作者：David Lafreniere
• 使用快速固定块内存分配器替换 malloc/free - 作者：David Lafreniere
• 自定义 STL std::allocator 替换提高了性能 - 作者：David Lafreniere

结论

此处介绍的基于 C 的固定块内存分配器适用于任何 C 或 C++ 系统。有关具有独特功能的 C++ 特定实现，请参阅引用的文章。

当您需要分配单个块大小时，请使用 fb_allocator。当需要分配多个块大小时，请使用 x_allocator。创建多个 x_allocator 包装器，根据预期用途隔离内存池。

如果您有一个应用程序对堆的负载很大并且导致性能缓慢，或者您担心堆碎片故障，集成 fb_allocator 和 x_allocator 可能会帮助解决这些问题。该实现被保持在最低限度，便于在最小的嵌入式系统上使用。

历史

• 2018 年 12 月 23 日
  • 首次发布
• 2018 年 12 月 24 日
  • 为文章添加了基准测试部分
  • 更新了附带的源代码