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

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 但是没有它真正读取或写入底层缓冲区（并将所有分配 information/data 结构保存在单独的缓冲区中）

有什么想法吗？

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

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

Answer 1

我不知道是否有任何可以使用的固定实现。然而，这似乎并不是特别难以自己实现，只需使用 C++ 标准库中的普通容器即可。

我推荐一种使用两个 std::map 和一个 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。如果超出您的需要，return 多余部分将返回池中，就好像您不需要的额外金额正在被释放（下面的第 3 步）。最后插入到allocated数组中，让你记住分配的chunk有多大。
要释放一个块，在allocated数组中查找它，得到它的大小，从allocated数组中删除它，然后：
将其插入 unallocated 和 unallocated_lookup，类似于初始未分配块的插入方式，见上文。
但是你还没有完成。然后，您必须使用 unallocated_lookup 在内存缓冲区中简单地查找前面未分配的块和后面的未分配块。如果其中一个或两个紧邻新释放的块，则必须将它们合并在一起。那应该是一个非常明显的过程。您可以简单地完成正式删除相邻块的动作，从 unallocated 和 unallocated_lookup，然后释放一个合并的块。

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

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

最后：

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

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

Answer 2

我正在发布我们实际结束时所做的更新。我最终实现了自己的远程内存分配器（下面的源代码）。它在精神上与类似，但使用增强侵入式 RB 树来避免在释放、加入等时进行一些 log(N) 查找。它是线程安全的，并支持各种远程 pointer/offset 类型作为模板参数。它在很多方面可能并不理想，但它足以满足我们需要它做的事情。如果您发现错误，请告诉我。

/*
 * Thread-safe remote memory allocator
 *
 * Author: Yuriy Romanenko
 * Copyright (c) 2015 Lytro, Inc.
 *
 */

#pragma once

#include <memory>
#include <mutex>
#include <cstdint>
#include <cstdio>
#include <functional>

#include <boost/intrusive/rbtree.hpp>

namespace bi = boost::intrusive;

template<typename remote_ptr_t = void*,
         typename remote_size_t = size_t,
         typename remote_uintptr_t = uintptr_t>
class RemoteAllocator
{
    /* Internal structure used for keeping track of a contiguous block of
     * remote memory. It can be on one or two of the following RB trees:
     *    Free Chunks (sorted by size)
     *    All Chunks (sorted by remote pointer)
     */
    struct Chunk
    {
        bi::set_member_hook<> mRbFreeChunksHook;
        bi::set_member_hook<> mRbAllChunksHook;

        remote_uintptr_t mOffset;
        remote_size_t mSize;
        bool mFree;

        Chunk(remote_uintptr_t off, remote_size_t sz, bool fr)
                : mOffset(off), mSize(sz), mFree(fr)
        {

        }

        bool contains(remote_uintptr_t off)
        {
            return (off >= mOffset) && (off < mOffset + mSize);
        }
    private:
        Chunk(const Chunk&);
        Chunk& operator=(const Chunk&);
    };

    struct ChunkCompareSize : public std::binary_function <Chunk,Chunk,bool>
    {
        bool operator() (const Chunk& x, const Chunk& y) const
        {
            return x.mSize < y.mSize;
        }
    };
    struct ChunkCompareOffset : public std::binary_function <Chunk,Chunk,bool>
    {
        bool operator() (const Chunk& x, const Chunk& y) const
        {
            return x.mOffset < y.mOffset;
        }
    };

    typedef bi::rbtree<Chunk,
                       bi::member_hook<Chunk,
                                       bi::set_member_hook<>,
                                       &Chunk::mRbFreeChunksHook>,
                       bi::compare< ChunkCompareSize > > FreeChunkTree;

    typedef bi::rbtree<Chunk,
                       bi::member_hook<Chunk,
                                       bi::set_member_hook<>,
                                       &Chunk::mRbAllChunksHook>,
                       bi::compare< ChunkCompareOffset > > AllChunkTree;

    // Thread safety lock
    std::mutex mLock;
    // Size of the entire pool
    remote_size_t mSize;
    // Start address of the pool
    remote_ptr_t mStartAddr;

    // Tree of free chunks
    FreeChunkTree mFreeChunks;
    // Tree of all chunks
    AllChunkTree mAllChunks;

    // This removes the chunk from both trees
    Chunk *unlinkChunk(Chunk *c)
    {
        mAllChunks.erase(mAllChunks.iterator_to(*c));
        if(c->mFree)
        {
            mFreeChunks.erase(mFreeChunks.iterator_to(*c));
        }
        return c;
    }

    // This reinserts the chunk into one or two trees, depending on mFree
    Chunk *relinkChunk(Chunk *c)
    {
        mAllChunks.insert_equal(*c);
        if(c->mFree)
        {
            mFreeChunks.insert_equal(*c);
        }
        return c;
    }

    /* This assumes c is 'free' and walks the mAllChunks tree to the left
     * joining any contiguous free chunks into this one
     */
    bool growFreeLeft(Chunk *c)
    {
        auto it = mAllChunks.iterator_to(*c);
        if(it != mAllChunks.begin())
        {
            it--;
            if(it->mFree)
            {
                Chunk *left = unlinkChunk(&(*it));
                unlinkChunk(c);
                c->mOffset = left->mOffset;
                c->mSize = left->mSize + c->mSize;
                delete left;
                relinkChunk(c);
                return true;
            }
        }
        return false;
    }
    /* This assumes c is 'free' and walks the mAllChunks tree to the right
     * joining any contiguous free chunks into this one
     */
    bool growFreeRight(Chunk *c)
    {
        auto it = mAllChunks.iterator_to(*c);
        it++;
        if(it != mAllChunks.end())
        {
            if(it->mFree)
            {
                Chunk *right = unlinkChunk(&(*it));
                unlinkChunk(c);
                c->mSize = right->mSize + c->mSize;
                delete right;
                relinkChunk(c);
                return true;
            }
        }
        return false;
    }

public:
    RemoteAllocator(remote_size_t size, remote_ptr_t startAddr) :
        mSize(size), mStartAddr(startAddr)
    {
        /* Initially we create one free chunk the size of the entire managed
         * memory pool, and add it to both trees
         */
        Chunk *all = new Chunk(reinterpret_cast<remote_uintptr_t>(mStartAddr),
                               mSize,
                               true);
        mAllChunks.insert_equal(*all);
        mFreeChunks.insert_equal(*all);
    }

    ~RemoteAllocator()
    {
        auto it = mAllChunks.begin();

        while(it != mAllChunks.end())
        {
            Chunk *pt = unlinkChunk(&(*it++));
            delete pt;
        }
    }

    remote_ptr_t malloc(remote_size_t bytes)
    {
        std::unique_lock<std::mutex> lock(mLock);
        auto fit = mFreeChunks.lower_bound(
                    Chunk(reinterpret_cast<remote_uintptr_t>(mStartAddr),
                          bytes,
                          true));

        /* Out of memory */
        if(fit == mFreeChunks.end())
            return remote_ptr_t{0};

        Chunk *ret = &(*fit);
        /* We need to split the chunk because it's not the exact size */
        /* Let's remove the node */
        mFreeChunks.erase(fit);

        if(ret->mSize != bytes)
        {
            Chunk *right, *left = ret;

            /* The following logic decides which way the heap grows
             * based on allocation size. I am not 100% sure this actually
             * helps with fragmentation with such a big threshold (50%)
             *
             * Check if we will occupy more than half of the chunk,
             * in that case, use the left side. */
            if(bytes > ret->mSize / 2)
            {
                right = new Chunk(left->mOffset + bytes,
                                  left->mSize - bytes,
                                  true);
                relinkChunk(right);

                left->mSize = bytes;
                left->mFree = false;

                ret = left;
            }
            /* We'll be using less than half, let's use the right side. */
            else
            {
                right = new Chunk(left->mOffset + left->mSize - bytes,
                                  bytes,
                                  false);

                relinkChunk(right);

                left->mSize = left->mSize - bytes;
                mFreeChunks.insert_equal(*left);

                ret = right;
            }
        }
        else
        {
            ret->mFree = false;
        }

        return reinterpret_cast<remote_ptr_t>(ret->mOffset);
    }

    remote_ptr_t malloc_aligned(remote_size_t bytes, remote_size_t alignment)
    {
        remote_size_t bufSize = bytes + alignment;
        remote_ptr_t mem = this->malloc(bufSize);
        remote_ptr_t ret = mem;
        if(mem)
        {
            remote_uintptr_t offset = reinterpret_cast<remote_uintptr_t>(mem);
            if(offset % alignment)
            {
                offset = offset + (alignment - (offset % alignment));
            }
            ret = reinterpret_cast<remote_ptr_t>(offset);
        }
        return ret;
    }

    void free(remote_ptr_t ptr)
    {
        std::unique_lock<std::mutex> lock(mLock);
        Chunk ref(reinterpret_cast<remote_uintptr_t>(ptr), 0, false);
        auto it = mAllChunks.find(ref);
        if(it == mAllChunks.end())
        {
            it = mAllChunks.upper_bound(ref);
            it--;
        }
        if(!(it->contains(ref.mOffset)) || it->mFree)
            throw std::runtime_error("Could not find chunk to free");

        Chunk *chnk = &(*it);
        chnk->mFree = true;
        mFreeChunks.insert_equal(*chnk);

        /* Maximize space */
        while(growFreeLeft(chnk));
        while(growFreeRight(chnk));
    }

    void debugDump()
    {
        std::unique_lock<std::mutex> lock(mLock);
        int i = 0;
        printf("----------- All chunks -----------\n");
        for(auto it = mAllChunks.begin(); it != mAllChunks.end(); it++)
        {
            printf(" [%d] %lu -> %lu (%lu) %s\n",
                i++,
                it->mOffset,
                it->mOffset + it->mSize,
                it->mSize,
                it->mFree ? "(FREE)" : "(NOT FREE)");
        }
        i = 0;
        printf("----------- Free chunks -----------\n");
        for(auto it = mFreeChunks.begin(); it != mFreeChunks.end(); it++)
        {
            printf(" [%d] %lu -> %lu (%lu) %s\n",
                i++,
                it->mOffset,
                it->mOffset + it->mSize,
                it->mSize,
                it->mFree ? "(FREE)" : "(NOT FREE)");
        }
    }
};

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

memory heap allocator library that keeps separate structures?

c++

memory

boost

memory-management