今日は昨日に引き続き仮想ページの管理機能を実装します。

昨日追加したカーネルの仮想メモリブロック（0xc0000000-0xffffffff）と19日目に設定したページテーブルの情報がマッチしていません。今日はまずこれらの情報を一致させていきます。

これらを一致させるアプローチはいくつか考えられます。ここでは3つのアプローチを検討しました。

1. 1つ目は，これまでのページテーブルは無視して，静的マッピング用のオブジェクトとページテーブルごと新しく作り直す方法です。この方法はオブジェクト・ページ情報とページテーブルが完全に一致するためコードが整うとは思いますが，折角リニアマッピングまでした領域が無駄になってしまいます。
2. 2つ目は，先日作成したページテーブルはそのままでオブジェクトの静的マッピングのみを変更する関数を用意することです。こちらの問題点はオブジェクトとページテーブルの情報が必ずしも一致せず，またその関数を間違って使ってしまうとページテーブルに作用しないマッピング（したつもりになる）領域ができてしまう点です。
3. 3つ目は，2つ目のアプローチに似ていますが，オブジェクト・ページの静的マッピングではなく，静的マッピングされていることを示すメモリブロックを用意して，そのメモリブロックで指定した領域はすべて静的マッピング済みとして確保してしまう方法です。こちらも全体ではページテーブルの情報との不一致が発生する恐れがありますが，通常のメモリブロック内での整合性は保つことができます。

今回は1つ目と3つ目のアプローチで悩みましたが，0xc0000000-0xffffffffの領域は1つ目のアプローチ，全メモリをリニアマッピングする領域については，page_tを全てに用意するのはもったいないので3つ目のアプローチを採用しました。

少し長いですが，仮想アドレスvirtualからnrページ分を物理アドレスphysicalにリニアマッピングする関数です。このページは（今回は実装しませんが）スワップアウトせずに常にメモリ割り付けられている領域なので，MEMORY_PGF_WIREDフラグを付けておきます。この領域は物理メモリを動的に割り当てておらず，解放することもないので，ゾーンやNUMAドメインは無効な値として扱います。

int
memory_wire(memory_t *mem, uintptr_t virtual, size_t nr, uintptr_t physical)
{
    virt_memory_block_t *b;
    uintptr_t endplus1;
    virt_memory_free_t *f;
    virt_memory_free_t *f0;
    virt_memory_free_t *f1;
    virt_memory_entry_t *e;
    size_t size;
    page_t *p;
    page_t **pp;
    int ret;
    int order;

    /* Page alignment check */
    if ( virtual & (MEMORY_PAGESIZE - 1) ) {
        return -1;
    }
    if ( physical & (MEMORY_PAGESIZE - 1) ) {
        return -1;
    }

    /* Find a block including the virtual address */
    b = _find_block(mem, virtual);
    if ( NULL == b ) {
        /* Not found */
        return -1;
    }

    /* Find a free space corresponding to the virtual address */
    f = _find_free_entry(b->frees.atree, virtual);
    if ( NULL == f ) {
        /* Not found */
        return -1;
    }

    /* Check if the whole size is within this space */
    size = MEMORY_PAGESIZE * nr;
    if ( virtual + size > f->start + f->size ) {
        return -1;
    }

    /* Prepare an entry and an object */
    e = (virt_memory_entry_t *)_data_alloc(mem);
    if ( NULL == e ) {
        goto error_entry;
    }
    e->start = virtual;
    e->size = nr * MEMORY_PAGESIZE;
    e->object = (virt_memory_object_t *)_data_alloc(mem);
    if ( NULL == e->object ) {
        goto error_obj;
    }
    e->object->size = nr * MEMORY_PAGESIZE;
    e->object->pages = NULL;

    /* Prepare for free spaces */
    f0 = (virt_memory_free_t *)_data_alloc(mem);
    if ( NULL == f0 ) {
        goto error_f0;
    }
    f1 = (virt_memory_free_t *)_data_alloc(mem);
    if ( NULL == f1 ) {
        goto error_f1;
    }

    /* Allocate and map all pages */
    endplus1 = virtual + size;
    pp = &e->object->pages;
    while ( virtual < endplus1 ) {
        /* Allocate a page data structure */
        p = (page_t *)_data_alloc(mem);
        if ( NULL == p ) {
            goto error_page;
        }
        p->flags = MEMORY_PGF_WIRED;
        p->next = NULL;
        /* Calculate the order to minimize the number of page_t */
        order = _order(virtual, physical, endplus1 - virtual);
        p->order = order;
        ret = mem->map(mem->arch, virtual, p);
        if ( ret < 0 ) {
            goto error_page;
        }
        virtual += 1ULL << (order + MEMORY_PAGESIZE_SHIFT);
        physical += 1ULL << (order + MEMORY_PAGESIZE_SHIFT);

        *pp = p;
        pp = &p->next;
    }

    /* Add this entry */
    ret = _entry_add(&b->entries, e);
    if ( ret < 0 ) {
        goto error_page;
    }

    /* Remove the free entry */
    f = _free_delete(b, f);
    kassert( f != NULL );
    if ( f->start == e->start && f->size == e->size  ) {
        /* Remove the entire entry */
        _data_free(mem, (union virt_memory_data *)f0);
        _data_free(mem, (union virt_memory_data *)f1);
    } else if ( f->start == e->start ) {
        /* The start address is same, then add the rest to the free entry */
        f0->start = f->start + e->size;
        f0->size = f->size - e->size;
        ret = _free_add(b, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
        _data_free(mem, (union virt_memory_data *)f1);
    } else if ( f->start + f->size == e->start + e->size ) {
        /* The end address is same, then add the rest to the free entry */
        f0->start = f->start;
        f0->size = f->size - e->size;
        ret = _free_add(b, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
        _data_free(mem, (union virt_memory_data *)f1);
    } else {
        f0->start = f->start;
        f0->size = e->start + e->size - f->start;
        f1->start = e->start + e->size;
        f1->size = f->start + f->size - f1->start;
        ret = _free_add(b, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
        ret = _free_add(b, f1);
        if ( ret < 0 ) {
            goto error_free;
        }
    }
    _data_free(mem, (union virt_memory_data *)f);

    return 0;

error_free:
    _free_delete(b, f0);
error_post:
    _entry_delete(&b->entries, e);
    /* Add it back */
    _free_add(b, f);
error_page:
    p = e->object->pages;
    virtual = e->start;
    while ( NULL != p ) {
        ret = mem->unmap(mem->arch, virtual, p);
        kassert(ret == 0);
        p = p->next;
    }
    _data_free(mem, (union virt_memory_data *)f1);
error_f1:
    _data_free(mem, (union virt_memory_data *)f0);
error_f0:
    _data_free(mem, (union virt_memory_data *)e->object);
error_obj:
    _data_free(mem, (union virt_memory_data *)e);
error_entry:
    return -1;
}

_init_kernel_pgt()関数内でこれを呼び出します。

    /* 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.");
    }
    /* Map the first 2 MiB */
    ret = memory_wire(&kvar->mm, 0xc0000000ULL, 512, 0x00000000ULL);
    if ( ret < 0 ) {
        panic("Failed to wire kernel memory (lower).");
    }
    /* Map the APIC region */
    ret = memory_wire(&kvar->mm, 0xfec00000ULL, 5120, 0xfec00000ULL);
    if ( ret < 0 ) {
        panic("Failed to wire kernel memory (upper).");
    }
    /* Linear mapping */
    ret = memory_block_add(&kvar->mm, (uintptr_t)KERNEL_LMAP,
                           (uintptr_t)KERNEL_LMAP
                           + npg * MEMORY_SUPERPAGESIZE - 1);
    if ( ret < 0 ) {
        panic("Failed to add linear mapping memory block.");
    }
    ret = memory_wire(&kvar->mm, (uintptr_t)KERNEL_LMAP,
                      npg << (MEMORY_SUPERPAGESIZE_SHIFT
                              - MEMORY_PAGESIZE_SHIFT),
                      0x00000000ULL);
    if ( ret < 0 ) {
        panic("Failed to wire linear mapping region.");
    }

0-1 GiBのリニアマッピング領域はBSPのスタックやACPI領域のパースなどで使用しているため，引き続き手動でマッピングしますが，今日メモリ割り当てを実装したら，後日こちらも取り除く予定です。

ここからはメモリ割り当てを実装していきます。まずカーネル内でのインターフェイスとして，nrページを割り当てるmemory_alloc_pages()関数を以下のように実装します。この関数は単純に，メモリブロックを順に走査し，要求されたメモリ量を割り当てるものです。割り当てが完了した場合は，メモリブロックの走査を止め，そのままポインタとして返します。

void *
memory_alloc_pages(memory_t *mem, size_t nr)
{
    virt_memory_block_t *block;
    void *ptr;

    block = mem->blocks;
    ptr = NULL;
    while ( NULL != block && NULL == ptr ) {
        ptr = _alloc_pages_block(mem, block, nr, MEMORY_ZONE_NUMA_AWARE,
                                 0);
        block = block->next;
    }

    return ptr;
}

次に特定のメモリブロックからページの割り当てを_alloc_pages_block()関数を実装します。この実装はmemory_wire()と似た実装になりますが，物理メモリの割り当てを行う点からpage_tのオーダーを極力ページサイズまたはスーパーページサイズに合わせるようにします。今回は別の関数として実装します。少し長くなってしまったのでリファクタリングしたいレベルですが，とりあえず実装として掲載します。

static void *
_alloc_pages_block(memory_t *mem, virt_memory_block_t *block, size_t nr,
                   int zone, int numadomain)
{
    int superpage;
    size_t size;
    virt_memory_free_t *f;
    virt_memory_free_t *f0;
    virt_memory_free_t *f1;
    virt_memory_entry_t *e;
    page_t **pp;
    page_t *p;
    void *r;
    size_t i;
    int ret;
    uintptr_t virtual;

    /* Search from the binary tree */
    size = nr * MEMORY_PAGESIZE;
    superpage = 0;
    if ( size >= MEMORY_SUPERPAGESIZE ) {
        /* Search larger size to make sure to align superpages */
        size += MEMORY_SUPERPAGESIZE;
        superpage = 1;
    }
    f = _search_fit_size(block, block->frees.stree, size);
    if ( NULL == f ) {
        /* No available space */
        return NULL;
    }

    /* Allocate an entry and an object */
    e = (virt_memory_entry_t *)_data_alloc(mem);
    if ( NULL == e ) {
        goto error_entry;
    }
    e->size = nr * MEMORY_PAGESIZE;
    e->object = (virt_memory_object_t *)_data_alloc(mem);
    if ( NULL == e->object ) {
        goto error_obj;
    }
    e->object->size = nr * MEMORY_PAGESIZE;
    e->object->pages = NULL;;

    /* Prepare for free spaces */
    f0 = (virt_memory_free_t *)_data_alloc(mem);
    if ( NULL == f0 ) {
        goto error_f0;
    }
    f1 = (virt_memory_free_t *)_data_alloc(mem);
    if ( NULL == f1 ) {
        goto error_f1;
    }

    /* Align for superpages */
    if ( superpage ) {
        if ( f->start & (MEMORY_SUPERPAGESIZE - 1) ) {
            /* Not aligned to superpage, then align */
            e->start = (f->start + (MEMORY_SUPERPAGESIZE - 1))
                & ~(uintptr_t)(MEMORY_SUPERPAGESIZE - 1);
        } else {
            /* Aligned to superpage */
            e->start = f->start;
        }
    } else {
        e->start = f->start;
    }

    /* Allocate and map superpages */
    pp = &e->object->pages;
    for ( i = 0;
          i + (1 << (MEMORY_SUPERPAGESIZE_SHIFT - MEMORY_PAGESIZE_SHIFT)) <= nr;
          i += (1 << (MEMORY_SUPERPAGESIZE_SHIFT - MEMORY_PAGESIZE_SHIFT)) ) {
        p = (page_t *)_data_alloc(mem);
        if ( NULL == p ) {
            goto error_page;
        }
        p->zone = zone;
        p->numadomain = numadomain;
        p->flags = 0;
        p->order = MEMORY_SUPERPAGESIZE_SHIFT - MEMORY_PAGESIZE_SHIFT;

        /* Allocate a physical superpage */
        r = phys_mem_alloc(mem->phys, p->order, p->zone, p->numadomain);
        if ( NULL == r ) {
            _data_free(mem, (union virt_memory_data *)p);
            goto error_page;
        }
        p->physical = (uintptr_t)r;

        /* Map */
        ret = mem->map(mem->arch, e->start + i * MEMORY_PAGESIZE, p);
        if ( ret < 0 ) {
            _data_free(mem, (union virt_memory_data *)p);
            phys_mem_free(mem->phys, (void *)p->physical, p->order, p->zone,
                          p->numadomain);
            goto error_page;
        }

        *pp = p;
        pp = &p->next;
    }

    /* Allocate and map pages */
    for ( ; i < nr; i++ ) {
        p = (page_t *)_data_alloc(mem);
        if ( NULL == p ) {
            goto error_page;
        }
        p->zone = zone;
        p->numadomain = numadomain;
        p->flags = 0;
        p->order = 0;

        /* Allocate a physical page */
        r = phys_mem_alloc(mem->phys, p->order, p->zone, p->numadomain);
        if ( NULL == r ) {
            _data_free(mem, (union virt_memory_data *)p);
            goto error_page;
        }
        p->physical = (uintptr_t)r;

        /* Map */
        mem->map(mem->arch, e->start + i * MEMORY_PAGESIZE, p);
        if ( ret < 0 ) {
            _data_free(mem, (union virt_memory_data *)p);
            phys_mem_free(mem->phys, (void *)p->physical, p->order, p->zone,
                          p->numadomain);
            goto error_page;
        }

        *pp = p;
        pp = &p->next;
    }

    /* Add this entry */
    ret = _entry_add(&block->entries, e);
    if ( ret < 0 ) {
        goto error_page;
    }

    /* Remove the free entry */
    f = _free_delete(block, f);
    kassert( f != NULL );
    if ( f->start == e->start && f->size == e->size  ) {
        /* Remove the entire entry */
        _data_free(mem, (union virt_memory_data *)f0);
        _data_free(mem, (union virt_memory_data *)f1);
    } else if ( f->start == e->start ) {
        /* The start address is same, then add the rest to the free entry */
        f0->start = f->start + e->size;
        f0->size = f->size - e->size;
        ret = _free_add(block, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
    } else if ( f->start + f->size == e->start + e->size ) {
        /* The end address is same, then add the rest to the free entry */
        f0->start = f->start;
        f0->size = f->size - e->size;
        ret = _free_add(block, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
        _data_free(mem, (union virt_memory_data *)f1);
    } else {
        f0->start = f->start;
        f0->size = e->start + e->size - f->start;
        f1->start = e->start + e->size;
        f1->size = f->start + f->size - f1->start;
        ret = _free_add(block, f0);
        if ( ret < 0 ) {
            goto error_post;
        }
        ret = _free_add(block, f1);
        if ( ret < 0 ) {
            goto error_free;
        }
    }
    _data_free(mem, (union virt_memory_data *)f);

    return (void *)e->start;

error_free:
    _free_delete(block, f0);
error_post:
    _entry_delete(&block->entries, e);
    /* Add it back */
    _free_add(block, f);
error_page:
    p = e->object->pages;
    virtual = e->start;
    while ( NULL != p ) {
        ret = mem->unmap(mem->arch, virtual, p);
        kassert(ret == 0);
        phys_mem_free(mem->phys, (void *)p->physical, p->order, p->zone,
                      p->numadomain);
        virtual += ((uintptr_t)MEMORY_PAGESIZE << p->order);
        _data_free(mem, (union virt_memory_data *)p);
        p = p->next;
    }
    _data_free(mem, (union virt_memory_data *)f1);
error_f1:
    _data_free(mem, (union virt_memory_data *)f0);
error_f0:
    _data_free(mem, (union virt_memory_data *)e->object);
error_obj:
    _data_free(mem, (union virt_memory_data *)e);
error_entry:
    return NULL;
}

ページの解放は割り当てよりも単純です。以下のロジックでページの解放をします。

まず，解放する仮想アドレスに対応するメモリブロックを探索します。そのメモリブロック内の割り当て済みエントリの木構造から，解放する仮想アドレスに対応するエントリを探します。そのエントリの銭湯アドレスが解放対象でなければ，解放対象ではないので終了します。見つかったエントリからオブジェクト，ページリストと辿り，_pages_free()関数でページを全て解放しながらページテーブルから消します。その後，対象のエントリを空き領域として解放します。

この実装を以下に掲載します。

void
memory_free_pages(memory_t *mem, void *ptr)
{
    virt_memory_block_t *b;
    uintptr_t addr;
    virt_memory_entry_t *e;
    page_t *page;
    void *r;

    /* Convert the pointer to the address in integer */
    addr = (uintptr_t)ptr;

    /* Find a block */
    b = _find_block(mem, addr);
    if ( NULL == b ) {
        /* Not found */
        return;
    }

    /* Find an entry corresponding to the virtual address */
    e = _find_entry(b->entries, addr);
    if ( NULL == e ) {
        /* Not found */
        return;
    }
    if ( addr != e->start ) {
        /* Start address does not match. */
        return;
    }

    /* Find pages from the object */
    page = e->object->pages;
    /* Free the corersponding pages */
    _pages_free(mem, page);
    /* Free the object */
    _data_free(mem, (union virt_memory_data *)e->object);
    /* Retuurn to the free entry */
    r = _entry_delete(&b->entries, e);
    kassert( r == e );
    _entry_free(mem, b, e);
}

ここから呼び出される_pages_free()および_entry_free()は以下の通りです。

static void
_pages_free(memory_t *mem, page_t *p)
{
    while ( NULL != p ) {
        /* Free physical pages */
        phys_mem_free(mem->phys, (void *)p->physical, p->order, p->zone,
                      p->numadomain);

        /* Free this page */
        _data_free(mem, (union virt_memory_data *)p);

        p = p->next;
    }
}

static int
_entry_free(memory_t *mem, virt_memory_block_t *b, virt_memory_entry_t *e)
{
    virt_memory_free_t free;
    virt_memory_free_t *f;
    void *r;
    int ret;

    /* Find a neighboring free entry by address */
    f = _find_neighbor_free_entry(b->frees.atree, e->start, e->start + e->size);
    if ( NULL == f ) {
        /* Not found, then convert the data structure to free entry */
        kmemset(&free, 0, sizeof(virt_memory_free_t));
        free.start = e->start;
        free.size = e->size;
        f = (virt_memory_free_t *)e;
        kmemcpy(f, &free, sizeof(virt_memory_free_t));

        /* Add this node to the free entry tree */
        ret = _free_add(b, f);
        if ( ret < 0 ) {
            return -1;
        }
    } else {
        /* Remove the node first */
        r = _free_delete(b, f);
        kassert( r != NULL );

        /* Expand the free region */
        if ( f->start == e->start + e->size ) {
            f->start = e->start;
            f->size = f->size + e->size;
        } else {
            f->size = f->size + e->size;
        }
        _data_free(mem, (union virt_memory_data*)e);

        /* Rebalance the size-based tree */
        ret = _free_add(b, f);
        kassert( ret == 0 );
    }

    return 0;
}

今日はページ単位でのメモリアロケータを実装しました。明日はページ未満のオブジェクトの管理をしていこうと思います。