今日は仮想ページの管理を実装していきます。なお，仮想メモリ管理機能はsrc/kernel/memory.cに実装していきます。このファイルは物理メモリ管理の機能を実装していますが，行数が増えてきたので，物理メモリ関連の関数はsrc/kernel/physmem.cに移しました。

仮想ページは，通常物理メモリ領域よりも広いアドレス領域を割り当てることができます。そのため，フラグメンテーションは物理メモリほど問題になりません。物理メモリを効率的に使用するためには，（MMIOのように連続した物理メモリ領域が必要な場合は除き）2^nページの連続した物理メモリ領域ではなく，非連続な物理ページを仮想ページに割り当てる方が効率が良くなります。ページテーブルを用いることで，このような連続する仮想ページに対して離散的な物理ページの割り当てを行うことができますが，メモリ管理システムでこのマッピングを管理する必要があります。

また，ページテーブルのエントリはCPU内部ではTranslation Lookaside Buffer (TLB)と呼ばれる高速なメモリ（CAM: Content Addressable Memory）にキャッシュされるのですが，このキャッシュミスが起こるとDRAMのページテーブル参照が発生します。そのため，大きな仮想メモリ領域は，4 KiBページよりも2 MiBページを使った方がTLBを効率的に使用できます。この一段大きいページ（x86-64では2 MiBページ）を スーパーページ（Superpage） と呼びます。スーパーページは，物理メモリ領域でも仮想メモリ領域でも連続した512個の4 KiBページで，アライメントが2 MiBページングに揃っている必要があります。

advosでは，以下の構造体を割り当てたページ管理に用います。physicalは物理アドレス，zoneおよびnumadomainは物理メモリアロケータのメモリゾーンおよびNUMAドメインを保存します。orderは物理メモリ管理で使用しているバディシステムのオーダーを指定します。また，このオーダーにより，オーダーが9以上であればスーパーページを構成するようにします。メモリの割り当ては，複数のページを割り当てるため，連続した仮想ページを連結リストで表します。nextは連結リストの次のページへのポインタです。

typedef struct page page_t;
struct page {
    /* Physical address */
    uintptr_t physical;
    /* Zone of the buddy system */
    uint8_t zone;
    /* Order of the buddy system */
    uint8_t order;
    /* Numa-domain if available */
    uint32_t numadomain;
    /* Pointer to the next page in the same object */
    page_t *next;
};

連続したページで構成される領域は オブジェクト と呼ばれれます。オブジェクトはmmapシステムコールなどで割り当てる単位です。POSIXでは，mmapの際に書き込みや実行を可能にするフラグを設定しますが，今回は以下の構造体のように，単純に先ほど定義したページ構造体へのポインタ（リスト）とオブジェクトのサイズを定義します。

typedef struct virt_memory_object virt_memory_object_t;
struct virt_memory_object {
    /* Pointer to the list of pages */
    page_t *pages;
    /* Size */
    size_t size;
};

このオブジェクトの領域は，メモリ領域へのエントリとして以下の構造体で表します。この領域は現状はオブジェクトと1対1対応していますが，共有メモリなど，同一のオブジェクトを異なる仮想アドレス・ページテーブルから参照可能なように，別の構造体として定義しています。

typedef struct virt_memory_entry virt_memory_entry_t;
struct virt_memory_entry {
    /* Start virtual address of this entry */
    uintptr_t start;
    /* Size */
    size_t size;
    /* Pointer to the object */
    virt_memory_object_t *object;

    /* Binary tree for start address ordering */
    struct {
        virt_memory_entry_t *left;
        virt_memory_entry_t *right;
    } atree;
};

メモリ領域のエントリ一覧を管理するには，メモリ領域を連結リストで管理する方法と，二分木で管理する方法の二種類が主に使われますが，今回は二分木で管理します。そのため，上述の構造体は二分木の子ノードへのポインタatree.leftおよびatree.leftを定義しています。

また，仮想ページの空き領域管理も同様に，ページの空き領域を連結リストで管理する方法と，二分木で管理する方法の二種類が主に使われています。二分木で管理する場合は，利用中のメモリ領域の管理ではアドレスでの二分木のみで管理しましたが，空き領域はサイズで探索するため，適切な空き領域を探すためにサイズでソートした二分木と連続した空き領域を結合するためのアドレスでソートした二分木の2つの探索木で管理します。今回は探索木を使います。AVL木などの平衡木を使った方が良いのですが，今回は簡単のために単純な二分木で実装します。

以下の構造体は空き領域を表します。atree.leftおよびatree.rightはアドレスでソートした二分木，stree.leftおよびstree.rightはサイズでソートした二分木を表します。

typedef struct virt_memory_free virt_memory_free_t;
struct virt_memory_free {
    /* Start address of this space */
    uintptr_t start;
    /* Size of this space */
    size_t size;

    /* Binary tree for start address ordering */
    struct {
        virt_memory_free_t *left;
        virt_memory_free_t *right;
    } atree;
    /* Binary tree for size ordering */
    struct {
        virt_memory_free_t *left;
        virt_memory_free_t *right;
    } stree;
};

上述の各構造体の関係をまとめると下図のようになります。

仮想メモリ空間は（すべての領域は使えませんがx86-64では）64ビットの空間があります。これまで説明してきた通り，advosでは0xc0000000-0xffffffffをカーネル，0x100000000から必要な領域を物理メモリのリニアマッピングで使用します。仮想メモリの一部の領域をメモリブロックとして定義します。メモリブロックは以下の構造体で定義します。メモリブロックの数は多くならないように設計するため，メモリブロックはソート済み連結リストで表します。nextは連結リストのポインタを表します。また，entriesは割り当て済みの領域の木構造，freesは空き領域の木構造（アドレスおよびサイズでソート済み）を表します。

typedef struct virt_memory_block virt_memory_block_t;
struct virt_memory_block {
    /* Start virtual address of this block */
    uintptr_t start;
    /* End virtual address of this block */
    uintptr_t end;
    /* Pointer to the next block */
    virt_memory_block_t *next;

    /* Allocated entries */
    virt_memory_entry_t *entries;

    /* Free space list */
    struct {
        virt_memory_free_t *atree;
        virt_memory_free_t *stree;
    } frees;
};

上述した仮想メモリを管理するための構造体も動的に割り当てる必要があります。しかし，これらから現在実装中のメモリ割り当て機能を呼ぶと，呼び出しが循環してしまい，可読性が低くなってしまいます。そのため，今回はこれら仮想メモリ管理構造体を予め割り当てたプールから割り当てることにします。割り当てを簡略化するために，これらの構造体をすべて同一サイズに揃えます。そのために以下の共用体を定義しました。

union virt_memory_data {
    page_t page;
    virt_memory_object_t object;
    virt_memory_entry_t entry;
    virt_memory_free_t free;
    virt_memory_block_t block;
    union virt_memory_data *next;
};

これを物理メモリから割り当て，リニアマッピングしている仮想アドレスのまま使用します。src/kernel/memory.cのmemory_init()関数の以下のコードがその部分に値します。今回は2 MiBをこの構造体用に予約しています。

    /* Allocate 2 MiB for page management */
    data = phys_mem_buddy_alloc(phys->czones[MEMORY_ZONE_KERNEL].heads, 9);
    if ( NULL == data ) {
        return -1;
    }
    nr = (MEMORY_PAGESIZE << 9) / sizeof(union virt_memory_data);
    for ( i = 1; i < nr; i++ ){
        data[i - 1].next = &data[i];
    }
    data[nr - 1].next = NULL;

メモリ管理構造体を以下の通り定義します。メモリブロックの連結リストを表すblocks，物理メモリ管理構造体へのポインタphysの他に，上述の仮想メモリ管理構造体用の割り当て領域listsを定義しています。

typedef struct {
    /* List of blocks */
    virt_memory_block_t *blocks;

    /* Physical memory manager */
    phys_memory_t *phys;

    /* List of memory management data structures */
    union virt_memory_data *lists;

    /* Architecture-specific defintions */
    void *arch;
    int (*map)(void *, uintptr_t, page_t *);
    int (*unmap)(void *, uintptr_t, page_t *);
} memory_t;

仮想メモリと物理メモリの対応付け（ページテーブルがある場合はページテーブルの設定）のコードはCPUアーキテクチャに大きく依存します。まだ，他のCPUアーキテクチャについて勉強できていないのでこの実装が正しいかはわかりませんが，今回は少なくともx86-64でアーキテクチャ依存のコードをsrc/kernel/memory.cから分離するために，この割り付けおよび解放は抽象化したmapおよびunmap関数，およびアーキテクチャ依存のデータ構造へのポインタarchをこの構造体に定義しました。

これをアーキテクチャ依存コードから初期化する関数がmemory_init()です。memory_init()関数は以下のプロトタイプ宣言で定義しています。

int
memory_init(memory_t *mem, phys_memory_t *phys, void *arch,
            int (*map)(void *, uintptr_t, page_t *),
            int (*unmap)(void *, uintptr_t, page_t *));

第1引数はメモリ管理構造体へのポインタです。これを初期化します。第2引数はコアゾーン初期化済みの物理メモリ管理構造体です。第3引数から第5引数がアーキテクチャ依存のデータおよび関数を渡すための引数です。

この初期化はsrc/kernel/arch/x86-64/arch.cに実装しています。今回実装する初期化コードは，以下の部分です。

    /* Initialize the virtual memory management */
    ret = memory_init(&kvar->mm, &kvar->phys, &kvar->pgt, arch_memory_map,
                      arch_memory_unmap);
    if ( ret < 0 ) {
        panic("Failed to initialize the memory manager.");
    }
    ret = memory_block_add(&kvar->mm, 0xc0000000ULL, 0xffffffffULL);
    if ( ret < 0 ) {
        panic("Failed to add kernel memory block.");
    }

ここでmemory_block_add()関数はメモリブロックを初期化する関数でsrc/kernel/memory.cに以下の通り定義しています。内容は単純に，第2引数で指定した仮想アドレスから第3引数のブロックを確保し，そのブロック内で空き領域として追加する関数です。

int
memory_block_add(memory_t *mem, uintptr_t start, uintptr_t end)
{
    virt_memory_free_t *fr;
    virt_memory_block_t *n;
    virt_memory_block_t **b;

    /* Allocate data and initialize the block */
    n = (virt_memory_block_t *)_data_alloc(mem);
    if ( NULL == n ) {
        return -1;
    }
    n->start = start;
    n->end = end;
    n->next = NULL;
    n->entries = NULL;
    n->frees.atree = NULL;
    n->frees.stree = NULL;

    /* Add a free entry aligned to the block and the page size */
    fr = (virt_memory_free_t *)_data_alloc(mem);
    if ( NULL == fr ) {
        _data_free(mem, (union virt_memory_data *)n);
        return -1;
    }
    fr->start = (start + MEMORY_PAGESIZE - 1)
        & ~(uintptr_t)(MEMORY_PAGESIZE - 1);
    fr->size = ((end + 1) & ~(uintptr_t)(MEMORY_PAGESIZE - 1)) - fr->start;
    n->frees.atree = fr;
    n->frees.stree = fr;

    /* Insert the block to the sorted list */
    b = &mem->blocks;
    while ( NULL != *b ) {
        if ( (*b)->start > n->start ) {
            /* Try to insert here */
            if ( n->end >= (*b)->start ) {
                /* Overlapping space, then raise an error */
                _data_free(mem, (union virt_memory_data *)fr);
                _data_free(mem, (union virt_memory_data *)n);
                return -1;
            }
            break;
        }
        b = &(*b)->next;
    }
    n->next = *b;
    *b = n;

    return 0;
}

今日は，仮想メモリ管理関連の構造体の定義と空き領域の初期化を実装しました。明日は仮想ページの割り当てを実装します。