使用分配器替换malloc()/free()？

Question

有没有一种便携的方法可以用STL样式的分配器包装替换malloc()/free()的使用？

背景：我有一个C库，允许指定自定义的malloc()/free()函数进行内存管理，并在多线程环境中使用。在寻找一个好的多线程分配器时，我发现GCC-libstdc++的mt_alloc适用于我的工作负载。现在我想在这个C库中使用它，但该怎么做呢？

我看到的主要问题在于deallocate()函数，与free()相反，它除了地址外还需要传入分配的内存块大小。因此，我需要以某种方式跟踪与每个内存分配相关联的大小，以便在释放内存时将其提供给deallocate()。我想到的最简单的解决方案是在内存块的开头存储分配的内存大小，但我不确定可能会出现的对齐问题该如何解决。

是否有我忽略的简单解决方案？

- bluescarni

---

请记住，容器会分配越来越大的内存块，并在其大小减小时保留任何内存。 您的 C 库可能没有相同的使用模式，因此您甚至可能看不到与容器相同的性能提升。 - Emile Cormier

@Emile：我想跟踪大小的想法是在块内分配额外的空间来存储块的大小。因此，如果请求n个字节，则分配类似于n + sizeof(std::size_t)（+-对齐考虑），并返回基地址+ sizeof(std::size_t)。释放指针p时，取p - sizeof(std::size_t)，读取大小并将其传递给deallocate()。 - bluescarni

是的，当我阅读你的问题时，不知怎么就错过了那个。可能是注意力缺陷障碍。 :-) - Emile Cormier

3.11 [basic.align]（n3242中的第5段）对齐： <quote>对齐方式从较弱到较强或更严格的对齐方式具有顺序。 更严格的对齐方式具有更大的对齐值。 满足对齐要求的地址也满足任何较弱的有效对齐要求。</quote> 因此，如果 alignof(std::size_t) >= alignof(<your Type>)，那么一切都应该没问题。 还要注意，alignof(std::max_align_t) 可能是最大的对齐方式（尽管实现可以自由地拥有具有 扩展对齐 的对象，但这很少见）。 - Martin York

注意：如果您的编译器尚不支持alignof，请尝试使用__alignof。 - Martin York

Answer 1

在我的平台上，malloc 确保分配的内存对齐在 8 字节边界上。为了模拟这种行为，使用一个 allocator<uint64_t>:

#include <stdint.h>
#include <ext/mt_allocator.h>

static __gnu_cxx::__mt_alloc<uint64_t> theAllocator;

void* mtmalloc(size_t size)
{
    // Divide size by sizeof(uint64_t) and round up
    size_t payloadElementCount = (size + sizeof(uint64_t) - 1) /
                                 sizeof(uint64_t);

    // Add an extra uint64_t to store the chunk size
    size_t chunkElementCount = 1 + payloadElementCount;

    // Allocate the chunk
    uint64_t* chunk = theAllocator.allocate(chunkElementCount);

    // Store the chunk size in the first word
    chunk[0] = chunkElementCount;

    // Return a pointer past where the chunk size is stored
    return static_cast<void*>(chunk + 1);
}

void mtfree(void* pointer)
{
    // The chunk begins one word before the passed in pointer
    uint64_t* chunk = static_cast<uint64_t*>(pointer) - 1;

    // Retrieve the chunk size
    size_t chunkElementCount = chunk[0];

    // Deallocate the chunk
    theAllocator.deallocate(chunk, chunkElementCount);
}

int main()
{
    int* array = (int*)mtmalloc(sizeof(int) * 4);
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
    mtfree(array);
}

针对您的平台，将uint64_t替换为相应的类型。

您应该使用像Valgrind这样的工具进行测试，以确保没有内存泄漏！

---

除了uint64_t之外，您可以使用GCC的__BIGGEST_ALIGNMENT__和Boost的aligned_storage 类型特征来实现可移植的解决方案：

typedef boost::aligned_storage<__BIGGEST_ALIGNMENT__, __BIGGEST_ALIGNMENT__> AlignedType;

- Emile Cormier

---

你的 size_t chunkSize = 1+payloadSize; 不会增加大小1个字节，同时进行指针转换为 uint64_t*，然后将其减少1实际上减少了指针 sizeof(uint64_t)。这基本上意味着当有人尝试分配 X 字节时，你实际上只分配了 X-(sizeof(uint64_t)-1) 字节并返回这样的指针？ - Simon

@Simon：allocator::allocate 的参数是元素的数量，而不是以字节为单位的大小。请参阅http://cplusplus.com/reference/std/memory/allocator/allocate/。 - Emile Cormier

重命名一些变量，以便更明显地表示它代表元素数量。 - Emile Cormier

嘿，谢谢，这看起来真的很不错。由于我正在使用c++0x，我想我可以使用alignof(std::max_align_t)代替__BIGGEST_ALIGNMENT__（至少在GCC中实现它后）。将答案标记为已接受。 - bluescarni

@bluescarni: 为了替换uint64_t，我认为你可以直接使用std::max_align_t而不是alignof(std::max_align_t)（我对C++0x的所有新功能都不熟悉）。你将需要进行一些指针转换，以便能够将块大小存储在std::max_align_t元素中。 - Emile Cormier

Answer 2

关于这个问题，Paul Laska在altdevblogaday上写了一系列很棒的文章。以下是第一篇文章的链接：http://altdevblogaday.org/2011/04/11/ready-set-allocate-part-1/

在这篇文章中，他关注块大小分配和对齐问题。它应该提供一个经过深思熟虑和精心编写的解决方案，以解决您的释放问题。

- Simon

Answer 3

我所知道的物体大小追踪的两种主要方法是：在侧面有元数据的尺寸分离分配器中隐式地实现（例如，Kingsley风格分配器），或将大小作为对象头放在对象前方来追踪尺寸（例如，dlmalloc）。一个非常糟糕的第三种解决方案是维护每个分配对象及其大小的映射。当然，该映射将由另一个分配器管理。

我认为您是正确的轨道上，并且了解对齐考虑因素是很好的。我试图查找有关mt_alloc的一些信息，以查看是否存在替代方案或意外情况，但似乎这样的信息并不容易得到。一些分配器有一种查询对象大小的方法（此方法可能便宜也可能不便宜）。如果dealloc函数需要明确传递大小，则我会猜测没有此类函数，但您永远不知道。

如果对齐很重要，则需要稍微调整一下计算，因为分配器可能不会返回适合您的内存对齐的内存。如果您对返回指针的对齐方式一无所知，则需要类似以下的内容：

struct object_header {
    size_t size;
};

void * buf = xxmalloc (2 * alignment + size + sizeof(object_header));
void * alignedPtr = (void *) (((size_t) buf + sizeof(object_header) + alignment - 1) & ~(alignment - 1));

如果mt_alloc不能容忍在内部指针上释放对象，那么这个方案会给你带来问题，因为通过填充额外的对齐空间，你不再知道返回给你的原始地址。在这种情况下，你可能需要在头部存储一个额外的字段。

根据mt_alloc如何管理内存，附加额外的头部也可能会给你带来相当大的开销。在大小分离的分配器中，附加这个头部可以使你的对象的空间开销增加到2倍，直到页面大小，此时你可以支付每个对象一个额外页面的成本。在其他分配器中，这可能不是一个问题，但这是需要注意的事情。

- Justin Aquadro

---

从什么时候开始，8字节对齐成为malloc的标准？标准规定：“如果分配成功，则返回的指针适当地对齐，以便可以将其分配给任何类型的对象的指针，然后用于访问在分配的空间中分配的此类对象或此类对象的数组（直到显式释放该空间）。”这显然是特定于平台（和编译器）的。 - Simon

你说得对，我在GNU领域工作的时间太长了。事实上，我应该知道得更清楚，因为我们一直在我们的分配器周围包装层来强制执行这个。 - Justin Aquadro

Answer 4

关于在块的开头存储值，请参阅我在这里的答案。您可以稍微修改它以满足您的需求。

- user541686