今日は物理メモリ管理のうち，バディシステムによるメモリ割り当てと解放を実装していきます。

バディシステムでのメモリの割り当ては非常に単純です。対応するオーダーの連結リストから1ブロック取り出すだけです。連結リストが空の場合は，上位のオーダーのブロックを分割します。これを再帰的に実行することで必要なサイズを確保します。

以下のコードはorderのオーダーに空きブロックが存在するように再帰的に上位のオーダーの分割をします。_split_buddy(buddy, order)関数は，orderに空きブロックを作るように上位の分割を試みる関数です。

static void
_split_buddy(phys_memory_buddy_page_t **buddy, int order)
{
    phys_memory_buddy_page_t *block;
    phys_memory_buddy_page_t *split;
    uintptr_t offset;

    if ( order >= MEMORY_PHYS_BUDDY_ORDER ) {
        return;
    }

    if ( NULL != buddy[order] ) {
        /* Valid block in this order */
        return;
    }

    /* Split the upper order if no block at the upper order */
    _split_buddy(buddy, order + 1);

    /* Check the upper order */
    if ( NULL == buddy[order + 1] ) {
        /* No valid block */
        return;
    }

    /* Take one block from the upper order */
    block = buddy[order + 1];
    buddy[order + 1] = buddy[order + 1]->next;
    block->next = NULL;

    /* Split the block into two */
    offset = MEMORY_PAGESIZE << order;
    split = (phys_memory_buddy_page_t *)((uintptr_t)block + offset);
    split->next = NULL;
    block->next = split;
    buddy[order] = block;
}

まず，

    if ( order >= MEMORY_PHYS_BUDDY_ORDER ) {
        return;
    }

でorderが18になったら再帰処理を分割する上位のオーダーがないため処理を中止します。

次に，

    if ( NULL != buddy[order] ) {
        /* Valid block in this order */
        return;
    }

で，orderに空きブロックがあるか確認します。空きブロックがあれば，上位のオーダーのブロックを分割する必要がないため，再帰処理を中断します。

現在のオーダーに空きブロックがなければ，一段上位のブロックに空きブロックができるようにさらに上位の分割を再帰的に試みます。

    /* Split the upper order if no block at the upper order */
    _split_buddy(buddy, order + 1);

    /* Check the upper order */
    if ( NULL == buddy[order + 1] ) {
        /* No valid block */
        return;
    }

上位のブロックの分割を行った結果，order + 1に空きブロックが作れなければ，ここで処理を中断します。

これで，order + 1に空きブロックがある状態になりました。以下のコードで，このブロックをorderのブロック2つに分割し，連結リストに追加します。

    /* Take one block from the upper order */
    block = buddy[order + 1];
    buddy[order + 1] = buddy[order + 1]->next;
    block->next = NULL;

    /* Split the block into two */
    offset = MEMORY_PAGESIZE << order;
    split = (phys_memory_buddy_page_t *)((uintptr_t)block + offset);
    split->next = NULL;
    block->next = split;
    buddy[order] = block;

以下のコードはorderのサイズのメモリを割り当てる関数です。上述の_split_buddy()関数により，orderの空きブロックを作成し，連結リストから1ブロック取り出すことでメモリ割り当てを実装します。

void *
phys_mem_buddy_alloc(phys_memory_buddy_page_t **buddy, int order)
{
    phys_memory_buddy_page_t *block;

    /* Exceed the supported order */
    if ( order > MEMORY_PHYS_BUDDY_ORDER ) {
        return NULL;
    }

    /* Try to split the upper order if needed */
    _split_buddy(buddy, order);
    if ( NULL == buddy[order] ) {
        /* No block found */
        return 0;
    }
    block = buddy[order];
    buddy[order] = buddy[order]->next;
    block->next = NULL;

    return block;
}

次にメモリの解放を実装します。バディシステムにおけるメモリの解放は，割り当てられたサイズの情報が必要になります。このサイズ情報をメモリアロケータ内で管理する必要がありますが，このバディシステムはメモリアロケータから呼ばれることを想定して作るので，サイズ情報は外部から正しい値が与えられる前提で作成します。

メモリ解放は解放するブロックの銭湯アドレスptrと割り当てたオーダーorderを指定します。

void
phys_mem_buddy_free(phys_memory_buddy_page_t **buddy, void *ptr, int order)
{
    _insert_buddy(buddy, (uintptr_t)ptr, order);
}

実態はptrからorderで指定されたメモリサイズをバディシステムに追加する関数_insert_buddy()です。この関数を以下に掲載します。

static void
_insert_buddy(phys_memory_buddy_page_t **buddy, uintptr_t addr, int order)
{
    phys_memory_buddy_page_t *block;
    phys_memory_buddy_page_t **cur;

    if ( order > MEMORY_PHYS_BUDDY_ORDER ) {
        return;
    }

    /* Search the position to insert */
    cur = &buddy[order];
    while ( *cur ) {
        if ( addr < (uintptr_t)(*cur) ) {
            /* Insert here */
            break;
        }
        cur = &(*cur)->next;
    }

    /* Insert at the tail */
    block = (phys_memory_buddy_page_t *)addr;
    block->next = *cur;
    *cur = block;
    _merge_buddy(buddy, order);
}

まず，

    if ( order > MEMORY_PHYS_BUDDY_ORDER ) {
        return;
    }

でオーダーが18以下であることを確認します。

以下のコードは昨日のバディシステムの初期化と同様に，連結リストをソートされた状態で，追加ブロックを挿入する処理です。

    /* Search the position to insert */
    cur = &buddy[order];
    while ( *cur ) {
        if ( addr < (uintptr_t)(*cur) ) {
            /* Insert here */
            break;
        }
        cur = &(*cur)->next;
    }

最後に

    _merge_buddy(buddy, order);

で追加したブロックが隣のブロックと合わせて上位のオーダーのブロックとしてできる場合には結合します。この処理を再帰的に実行します。

_merge_buddy()関数を以下に掲載します。

static void
_merge_buddy(phys_memory_buddy_page_t **buddy, int order)
{
    phys_memory_buddy_page_t **cur;
    uintptr_t block;
    uintptr_t blocksize;

    if ( order >= MEMORY_PHYS_BUDDY_ORDER ) {
        return;
    }

    blocksize = MEMORY_PAGESIZE << order;

    cur = &buddy[order];
    while ( *cur ) {
        block = (uintptr_t)*cur;
        if ( 0 == (block & ((blocksize << 1) - 1)) ) {
            /* is aligned for the upper order */
            if ( (uintptr_t)(*cur)->next == block + blocksize ) {
                /* is buddy */
                *cur = (*cur)->next->next;
                _insert_buddy(buddy, block, order + 1);
                if ( NULL == *cur ) {
                    break;
                }
            }
        }
        cur = &(*cur)->next;
    }
}

このコードのキモは以下の部分です。

        block = (uintptr_t)*cur;
        if ( 0 == (block & ((blocksize << 1) - 1)) ) {
            /* is aligned for the upper order */
            if ( (uintptr_t)(*cur)->next == block + blocksize ) {
                /* is buddy */

あるブロックが一段上位のオーダーにアライメントが揃っている，かつ，次のブロックが連続する（現在のオーダーのブロックサイズ分のアドレスを足したもの）に限り，マージできます。マージした場合は，このブロックを一段上位のオーダーに追加し，同様の処理を行います。

今日はバディシステムでのメモリ割り当て・解放を実装しました。そろそろデバッグやテストでkprintf()のようなものがないとつらくなってきたので，明日からはカーネルで使う便利関数を書いていこうと思います。10日目でやるべきだった……反省。