Linked list allocator

はじめに

基本的なメモリ割り当て戦略を書きます. 空きメモリブロックをリンクリストで繋げる方法です. メモリ確保時に, 次のように空きからメモリブロックを切り出します. おそらくスタックベースの次に原始的な方法です.

解放

解放するブロックを, 空きリストの先頭に繋ぐだけなので簡単です.

これを繰り返すと, 空きリストは細かいメモリブロックに分断されます.

コンパクション

細かいメモリブロックが増加することを緩和するために, 簡単なコンパクションを行います. 解放時に前のブロックが空きかどうかを調べ, 空きならメモリブロックを結合します. 後のブロックを調べない理由は, 後を結合するとき, 後のブロックを指しているポインタを検索して書き換える必要があるからです.

実装

コードを張り付けるだけで申し訳ないです. 少し説明を加えると, コンパクションを簡単にする仕掛けは, メモリブロックのサイズに使用済みフラグを混ぜ, メモリブロックの最後にもサイズを設定しています. こうすることで, 一つ前のブロックが空いているか簡単に調べることができます.
ここでは実際のメモリと管理情報が分かれていますが, 用途に応じて実際のメモリの中に管理情報を入れ込むこともあります.

LinkAllocator

# include <cstdlib>
# include <cassert>
# include <cstdint>
# include <cstring>
# include <random>
# include <iostream>

typedef int32_t s32;
typedef uint16_t u16;
typedef uint32_t u32;

struct Handle
{
    void* ptr_;
    u32 size_;
    u32 offset_;
};

class LinkAllocator
{
public:
    static constexpr u16 Invalid = 0xFFFFU;
    static constexpr u16 Align = 2;
    static constexpr u16 AlignMask = Align-1;
    static constexpr u16 Size = 32;
    static constexpr u16 Used = 0x01U;

    LinkAllocator(u16 id);
    ~LinkAllocator();

    inline u16 getId() const;

    bool allocate(Handle& handle, u16 size);
    void deallocate(u16 id, u16 size, u16 offset);

# ifdef _DEBUG
    void print()
    {
        for(u32 i=0; i<Size; ++i){
            if(0 == (chunks_[i].size_ & Used)){
                printf("-");
            }else{
                char c = chunks_[i].next_ + 'A';
                printf("%c", c);
            }
        }
        printf("\n");
    }
# endif
private:
    LinkAllocator(const LinkAllocator&) = delete;
    LinkAllocator& operator=(const LinkAllocator&) = delete;

    struct Chunk
    {
        u16 next_;
        u16 size_;
    };

    void* heap_;
    u32 descriptorSize_;

    u16 id_;
    u16 empty_;
    Chunk chunks_[Size];
 };

inline u16 LinkAllocator::getId() const
{
    return id_;
}

LinkAllocator::LinkAllocator(u16 id)
    :heap_(nullptr)
    ,id_(id)
    ,empty_(0)
{
    heap_ = malloc(Size);
    memset(chunks_, 0, sizeof(Chunk)*Size);
    chunks_[0].next_ = Invalid;
    chunks_[0].size_ = Size;
    chunks_[Size-1].size_ = Size;
}

LinkAllocator::~LinkAllocator()
{
    free(heap_);
}

bool LinkAllocator::allocate(Handle& handle, u16 size)
{
    assert(0 < size && size<=Size);
    u16 alignedSize = (size + AlignMask) & ~AlignMask;

    u16 prev = Invalid;
    u16 current = empty_;
    while(Invalid != current){
        if(alignedSize<= chunks_[current].size_){
            //Allocate memory
            u16 offset = current;
            u16 remain = chunks_[current].size_ - alignedSize;
            if(0<remain){
                u16 next = current + alignedSize;
                if(Invalid != prev) {
                    chunks_[prev].next_ = next;
                } else {
                    empty_ = next;
                }
                chunks_[next].next_ = chunks_[current].next_;
                chunks_[next].size_ = remain;
                chunks_[next+remain-1].size_ = remain;
            }else{
                if(Invalid != prev) {
                    chunks_[prev].next_ = Invalid;
                } else {
                    empty_ = Invalid;
                }
            }

            u16 used = static_cast<u16>(alignedSize) | Used; //Set a used flag
            chunks_[current].size_ = used;
            chunks_[current].next_ = Invalid;
            chunks_[current + alignedSize - 1].size_ = used;
# ifdef _DEBUG
            for(s32 i=current; i<(current+alignedSize); ++i){
                chunks_[i].size_ |= Used;
                chunks_[i].next_ = current;
            }
# endif
            handle.ptr_ = reinterpret_cast<char*>(heap_);
            handle.size_ = size;
            handle.offset_ = offset;
            return true;
        }
        prev = current;
        current = chunks_[current].next_;
    }
    return false;
}

void LinkAllocator::deallocate(u16 id, u16 size, u16 offset)
{
    assert(id_ == id);
    assert(0 < size && size<=Size);
    assert(0 <= offset && offset<Size);

    u16 alignedSize = (size + AlignMask) & ~AlignMask;
    assert(alignedSize<=(Size-offset));

    Chunk& chunk = chunks_[offset];
    assert(0 != (chunk.size_&Used));
    assert(alignedSize == (chunk.size_&~Used));
# ifndef _DEBUG
    assert(Invalid == chunk.next_);
# endif
    chunk.size_ = alignedSize;
    chunk.next_ = empty_;
    chunks_[offset + alignedSize - 1].size_ = alignedSize;
    empty_ = offset;
    if(0<offset){
        if(0 == (chunks_[offset-1].size_&Used)){
            //Compact with a previous chunk
            empty_ = chunks_[offset].next_;
            u16 prev = offset-chunks_[offset-1].size_;

            chunks_[prev].size_ += chunks_[offset].size_;
            chunks_[offset].size_ = 0;
            chunks_[offset].next_ = 0;

            u16 tail = prev + chunks_[prev].size_-1;
            chunks_[tail].size_ = chunks_[prev].size_;
            chunks_[tail].next_ = 0;
# ifdef _DEBUG
            offset = prev;
            alignedSize =  chunks_[prev].size_;
# endif
        }
    }

# ifdef _DEBUG
    for(s32 i = offset+1; i < (offset + alignedSize-1); ++i) {
        chunks_[i].size_ = 0;
        chunks_[i].next_ = 0;
    }
# endif
}

int main(void)
{
    static constexpr u32 NumSamples = 16;
    static constexpr s32 MaxSize = LinkAllocator::Size/4;
    std::mt19937 random;
    {
        std::random_device device;
        random.seed(device());
    }
    std::uniform_int_distribution distribution(1, MaxSize-1);
    LinkAllocator allocator(0);
    Handle handles[NumSamples];
    s32 numAllocated = 0;
    for(u32 i=0; i<NumSamples; ++i){
        u16 size = static_cast<u16>(distribution(random));
        if(!allocator.allocate(handles[i], size)){
            break;
        }
        ++numAllocated;
    }
    allocator.print();
    std::shuffle(handles, handles+numAllocated, random);
    s32 half = numAllocated >> 1;
    for(s32 i=0; i<half; ++i){
        allocator.deallocate(0, handles[i].size_, handles[i].offset_);
    }
    allocator.print();
    for(s32 i=half; i<numAllocated; ++i){
        allocator.deallocate(0, handles[i].size_, handles[i].offset_);
    }
    allocator.print();
    return 0;
}

まとめ

何に使うの？というのは後日書くかもしれません.