Библиотека памяти кучи памяти, которая поддерживает отдельные структуры?

Ответ 1

Я публикую обновленную информацию о том, что мы действительно сделали. Я завершил реализацию своего собственного удаленного распределителя памяти (источник ниже). Это духовно похожее на ответить Сэму", но использует усиленные интрузивные деревья RB, чтобы избежать некоторых поисков журнала (N) при освобождении, присоединении и т.д. Это поточно-безопасный и поддерживает различные типы удаленного указателя/смещения в качестве параметров шаблона. Вероятно, он не идеален во многих отношениях, но он работал достаточно хорошо для того, что нам нужно. Если вы найдете ошибки, сообщите мне.

/*
 * 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 not the exact size */
        /* Let 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 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)");
        }
    }
};

Ответ 2

Я не знаю, с верхней части моей шляпы, любой консервированной реализации, которая может быть использована. Однако это не представляется особенно сложным для реализации, используя только садовые контейнеры в стандартной библиотеке С++.

Я бы рекомендовал простой подход, который использует два std::map и один std::multimap. Скажем, что bufaddr_t - непрозрачное целое число, представляющее адрес во внешнем буфере. Поскольку мы говорим о 16-гигабайтном буфере, он должен быть 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 - это карта, привязанная по адресу каждого нераспределенного фрагмента, который дает вам итератор для этой записи chunk в 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 и unallocated_lookup, а затем освободить один, объединенный кусок.

Это реальная цель unallocated_lookup, чтобы иметь возможность легко объединять смежные нераспределенные куски.

Насколько я могу судить, все вышеперечисленные операции несут логарифмическую сложность. Они полностью основаны на методах std::map и std::multimap, которые имеют логарифмическую сложность и ничего больше.

Наконец:

В зависимости от поведения вашего приложения вы можете легко настроить реализацию, чтобы внутренне округлить размер выделенного фрагмента до того, что вам нужно. Или отрегулируйте стратегию распределения - выделите из самого маленького фрагмента, который достаточно велик, чтобы удовлетворить запрос на распределение, или просто выделите из большого нераспределенного фрагмента (просто, используйте end(), чтобы найти его) и т.д.

Это преимущество для вашей собственной реализации - вы всегда будете иметь гораздо большую гибкость, чтобы настроить свою собственную реализацию, тогда вы, как правило, будете иметь некоторую консервативную внешнюю библиотеку.