不確定特異点

広く深く、ところどころ超深く

メモリ割り当てアルゴリズム (2)

組み込みRTOS用のメモリ割り当て処理を作るにあたり目標を考えてみます。

  1. 省メモリであること
  2. 高速であること

組み込み用途ではメモリ制約が厳しいため、フラグメンテーションを押さえつつ小規模かつ高速なアルゴリズム性能にするためのバランスが難しそうです。そうは言っても、今のところタスク生成に必要なメモリ割り当て処理が必要なのであって、小さなオブジェクトを頻繁に malloc/free するような用途は想定していないため、first fit 法のような単純なアルゴリズムでも実用上問題にならない気もします。

というわけで、まずは基本の first fit 法を見てみます。実は K&R にそのまま載ってたりします。

typedef long Align;

union header {
    struct {
        union header *ptr;
        unsigned size;
    } s;
    Align x;
};

typedef union header Header;

アラインメントするサイズの型でAlign型を決めて、ヘッダがそのサイズのアラインメントになるように union させるテクニックのようです。最近のコンパイラは構造体のサイズがアラインメントされるようにパディングされるので、このようなケアは不要(?)な気がします。

static Header base;
static Header *freep = NULL;

void *kr_malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;
    
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if ((prevp = freep) == NULL) { /* 初期設定 */
        base.s.ptr = freep = prevp = &base; /* 要素なしの単方向循環リスト */
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits)
                prevp->s.ptr = p->s.ptr; /* p が指すブロックは消滅 */
            else {
                p->s.size -= nunits; /* p が指すブロックの末尾から割り当て */
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp; /* 次回で割り当て処理を開始するブロックを更新 */
            return (void *)(p+1);
        }
        if (p == freep) /* 空きリストを1週回っても空きが見つからなかった */
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

空きブロックの循環リストを辿っていき必要な大きさの空きブロックを見つけます。見つけた空きブロックの末尾から割り当てていくことにより、ヘッダの size の更新を行うだけでよくなります。要求された大きさと空きブロックの size が一致した場合は、割り当て後は size == 0 になりますので、直前のブロックから次のブロックにかけてリンクを飛ばし、循環リストから外します。

また、freep を確保に成功した空きブロックの手前(prevp)に設定します。次回の kr_malloc() はここから再開します。今回確保できたのだから、次回もこの場所から探せば必要な空きブロックが見つかりやすいだろう、ということなんでしょうか。(その期待は当たるのか?)

循環リストを一周回った場合は適当な空きブロックを見つけることが出来なかったため、morecore() を実行して空きブロックをつなぎ足し、再度割り当てを試みます。morecoreで nunits 以上の空きブロックを確保するので、必ず割当たります。

#define NALLOC 1024

Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    kr_free((void *)(up+1));
    return freep;
}

先々を見越して最低でも NALLOC 分のメモリを確保します。後述の kr_free() で空きブロックとして循環リストにつなぎ込みます。蛇足ですが、kr_free() の実装を見ると、sbrk() が返却するポインタが比較可能、かつ、単調増加することが仮定されているように見えます。

void kr_free(void *ap)
{
    Header *bp, *p;

    bp = (Header *)ap - 1;
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) { /* 直後の空きブロックと併合可能 */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    }
    else
        bp->s.ptr = p->s.ptr;
    if (p + p->s.size == bp) { /* 直前の空きブロックと併合可能 */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    }
    else
        p->s.ptr = bp;
    freep = p;
}

解放するメモリのアドレスをもとに、循環リストにつなぐ位置を定めます。ここで、bp は解放する領域へのポインタ、p は解放する領域からみて 1 ブロック手前の空きブロックへのポインタです。解放する領域の直前または直後の空きブロックのサイズを調べ、領域が連続する場合は併合します。最後に解放したブロックに freep を設定します。次回 kr_malloc() を実行した場合はここから割り当てを再開します。

コード量は短いですが、思った以上に色々なことをやっていて密度が高かったです。しかも無駄がなくシンプル。もうこれでいいんじゃね?という気がしてきましたw