c++ - 保持独立结构的内存堆分配器库？

Question

这是我的问题:我需要在我的程序无法读取或写入的远程连续缓冲区中管理内存。它需要有 malloc()/free() 语义，并支持设置最小对齐和碎片避免(只要可能)。由于我无法直接读取或写入此缓冲区，因此我需要使用本地结构来管理所有分配。

我已经在使用 boost，所以如果可以按摩 boost 内部的东西来做到这一点，那就太好了。但是，我并不反对使用 C 库或类似的东西。

例如，我需要一个非 IPC 版本:

boost::interprocess::basic_managed_external_buffer<
                     char,
                     boost::interprocess::rbtree_best_fit<
                                          boost::interprocess::mutex_family,
                                          boost::interprocess::offset_ptr<void>,
                                          SOME_ALIGNMENT>,
                     boost::interprocess::iset_index>

最好使用 malloc/free 语义而不是 new/delete
但没有它实际读取或写入底层缓冲区(并将所有分配信息/数据结构保存在单独的缓冲区中)

有什么想法吗？

附言我不希望 boost::interprocess 示例具有误导性，我只是熟悉界面，因此将其用作示例。该应用程序并不是真正的进程间，并且分配器只能在我的应用程序中使用。

具体来说，我希望能够管理一个 16GB 的外部缓冲区，分配大小从 128 字节一直到 512MB。这是严格的 64 位代码，但即便如此，我还是希望指针类型是模板参数，以便我可以显式使用 uint64_t。

Answer 1

我不知道，在我的帽子上，任何可以使用的 jar 头实现。然而，这似乎并不是特别难自己实现，只需使用 C++ 标准库中的各种容器即可。

我会推荐一种使用两个 std::map 的简单方法。 s 和一个 std::multimap .假设 bufaddr_t是一个不透明整数，表示外部缓冲区中的地址。由于我们谈论的是 16 gig 缓冲区，因此它必须是 64 位地址:

typedef uint64_t memblockaddr_t;

分配块的大小也是如此。

typedef uint64_t memblocksize_t;

你可以，我想，为 memblockaddr_t 使用别的东西，只要不透明数据类型具有严格的弱排序。

第一部分很容易。跟踪所有分配的块:

std::map<memblockaddr_t, memblocksize_t> allocated;

因此，当您在外部缓冲区中成功分配一块内存时，将其插入此处。当您希望释放一块内存时，您可以在此处查找已分配块的大小，并删除映射条目。足够简单。

但这当然不是故事的全部。现在，我们需要跟踪可用的、未分配的内存块。让我们这样做:

typedef std::multimap<memblocksize_t, memblockaddr_t> unallocated_t;

unallocated_t unallocated;

std::map<memblockaddr_t, unallocated_t::iterator> unallocated_lookup;

unallocated是外部缓冲区中所有未分配块的集合，以块大小为键。关键是块大小。所以，当你需要分配一块特定大小的内存时，你可以简单地使用 lower_bound()方法(或 upper_bound() ，如果您愿意)立即找到第一个块，其大小至少与您想要分配的一样多。

当然，由于您可以拥有许多相同大小的块， unallocated必须是 std::multimap .

另外， unallocated_lookup是一个以每个未分配块的地址为键的映射，它为您提供了该块在 unallocated 中的条目的迭代器.为什么你需要它，一会儿就会明白。

所以:

使用单个条目初始化一个新的、完全未分配的缓冲区:

memblockaddr_t beginning=0; // Or, whatever represents the start of the buffer.
auto p=unallocated.insert(std::make_pair(BUFFER_SIZE, beginning)).first;
unallocated_lookup.insert(std::make_pair(beginning, p));

然后:

要分配一个块，请使用我上面提到的lower_bound()/upper_bound() 方法来找到第一个至少同样大的未分配块，并从unallocated 中删除它的条目。和 unallocated_lookup .如果它超出了您的需要，请将多余的部分返回到池中，就好像您不需要的额外金额正在被释放一样(下面的第 3 步)。最后，将其插入allocated数组，所以你记得分配的块有多大。

要释放块，请在 allocated 中查找它数组，要获得它的大小，请将其从 allocated 中删除数组，则:

将其插入 unallocated和 unallocated_lookup ，类似于如何插入初始未分配的块，见上文。

但你还没有完成。然后您必须使用 unallocated_lookup在内存缓冲区中简单地查找前面的未分配块和后面的未分配块。如果它们中的一个或两个紧邻新释放的块，则必须将它们合并在一起。这应该是一个非常明显的过程。您可以简单地分别从 unallocated 正式删除相邻块的 Action 。和 unallocated_lookup ，然后释放单个合并的块。

这就是 unallocated_lookup的真正目的，以便能够轻松合并连续的未分配块。

据我所知，上述所有操作都具有对数复杂性。它们完全基于 std::map的和 std::multimap的方法具有对数复杂性，仅此而已。

最后:

根据您的应用程序的行为，您可以轻松地调整实现以在内部将分配的块的大小四舍五入到您希望的任何倍数。或者调整分配策略——从满足分配请求的最小的chunk中分配，或者就从未分配的大chunk中分配(简单，用 end()找)，等等...

这是滚动你自己的实现的一个优势——你总是有更大的灵活性来调整你自己的实现，然后你通常会有一些 jar 装的外部库。