OS in 1,000 Lines のメモリアロケータを拡張してみた

はじめに

この記事は，怒田晟也氏が公開している教材「OS in 1,000 Lines」のメモリアロケータを拡張してみた記録です．

この教材は，約1,000行のコードで，システムコール，スケジューラ，メモリ管理などの OS 基本機能を自作するという趣旨のものです．

私は，低レイヤ技術の勉強の一環としてこちらに取り組んでおり，直近ではメモリアロケータを独自で拡張してみました．

本記事では，ポートフォリオという側面も兼ねて，実装したメモリアロケータ，及び実装した感想をまとめたいと思います．

注意点

繰り返しにはなりますが，本記事は，OS in 1,000 Linesの内容の拡張版になっています．そのため，「自分で拡張したい！！」という方にとっては，本記事の内容はネタバレになりかねませんので，その点に留意していただくよう，よろしくお願いします．

また，OS in 1,000 Linesをこれから進めようとしている方は，まずは教材の内容を自分で実装してみて，その後にこの記事を読むことをおすすめします．

実装したもの

一覧

私は今回，3種類のアロケータを実装しました．

1. バンプアロケータ
2. バンプ+フリーリストアロケータ
3. メモリ所有者を管理できるアロケータ

いずれも，ページ単位でメモリを割り当てる実装になっています．
それぞれについて，以下で紹介していきます．

バンプアロケータ

まずは，バンプアロケータを作りました．
これは，OS in 1,000 Linesでも紹介されているもので，以下の図のようなイメージです．

図のとおり，メモリ割当のたびに，どこまで割り当てたかのポインタを進めるだけという，非常に簡単なものです．
私は，以下のように実装しました．(OS in 1,000 Linesの実装の転載となります．なお，OS in 1,000 Linesのソースコード(nuta/operating-system-in-1000-lines - GitHub)は MIT License の下公開されています．)

bump allocator

// This code is from "OS in 1,000 Lines".
// Licensed under the MIT License.

// n ページ分のメモリ領域を割り当て，先頭アドレスを返す
paddr_t alloc_pages(uint32_t n) {
    static paddr_t next_paddr = (paddr_t) __free_ram;
    paddr_t paddr = next_paddr;
    next_paddr += n * PAGE_SIZE;

    if (next_paddr > (paddr_t) __free_ram_end)
        PANIC("out of memory");

    memset((void *) paddr, 0, n * PAGE_SIZE);
    return paddr;
}

バンプ+フリーリストアロケータ

ここからが私の独自拡張になります．
バンプアロケータは，非常に簡単に実装でき，高速に処理できる反面，メモリ解放ができないという欠点があります．なぜならば，バンプで管理できるのは「メモリをどこまで割り当てたか」という情報のみであり，「どこが空いてるのか」という情報は管理できないからです．

ということで，バンプアロケータに「フリーリスト - Wikipedia」の概念を組み込みました．

上図のように，空いているページをリストで繋ぐことで，空き領域を管理できるようにしました．
実装は以下のとおりです．

bump + free list allocator

struct free_page {
    struct free_page *next;
};

// フリーリストの先頭を指すポインタ
static struct free_page *free_list = NULL;

// n ページ解放（ページの中身にポインタを書き込んでリストへ）
void free_pages(paddr_t paddr, uint32_t n) {
    // 1ページずつフリーリストに追加していく
    for (uint32_t i = 0; i < n; i++) {
        paddr_t p = paddr + i * PAGE_SIZE; // ページの先頭アドレスを計算
        struct free_page *page = (struct free_page *) p; 
        page->next = free_list; // page というアドレスから始まる4KBのページのうち，先頭4バイト(つまり，next メンバ領域)に free_list の値(つまり，それまでの先頭要素)を格納
        free_list = page; // free_list の値を page に更新し，page をフリーリストの先頭にする．このようにすることで，page がフリーリストの先頭に割り込む形で登録される
    }
}

paddr_t alloc_pages(uint32_t n) {
    static paddr_t next_paddr = (paddr_t) __free_ram;
    
    // 単ページならフリーリストから取得を試みる
    if (n == 1 && free_list != NULL) {
        struct free_page *page = free_list; // フリーリストの先頭1要素をページとして割り当てる
        free_list = free_list->next; // それまで第二要素だったものをフリーリストの先頭にする
        memset((void *) page, 0, PAGE_SIZE);
        return (paddr_t) page;
    }

    // フリーリストに要素がない場合はバンプで割当
    // ...
}

バンプのみと比較して，以下のような変更を加えました．

1. フリーリストとして，free_list を用意
2. free_pages()を実装: 解放したページの中に，次の空きページへのアドレスを書いて，リストとして繋げる
3. alloc_pages()をアップデート: 可能であれば，フリーリストからページ割当を行う

これで，メモリ解放処理を行えるようになりました．
また，メモリ割当の際も，可能であればフリーリストの空き領域を再利用し，なるべくバンプのポインタが進まないようにしました．

メモリ所有者を管理できるアロケータ

バンプ+フリーリストにより，メモリ解放処理はできるようになりました．
しかし，まだ大きな問題があります．
それは，アロケータはメモリ所有者が誰なのかを知らないということです．
例えば，いくつかのページを割り当てられたプロセスが終了する際，そのプロセスの持っていたページを解放したいとします．
しかし，バンプ+フリーリストでは「空き領域がどこか」までしか管理できないため，特定プロセスのページのみ狙って解放，ということができません．

そこで，もう一段階拡張しました．

上図のように，各ページの所有者を管理する配列を用意しました．
実装は以下のとおりです．

page_owner_management_allocator

struct process *page_owners[TOTAL_PAGES];

void page_owners_init(void) {
    for (int i = 0; i < TOTAL_PAGES; i++)
        page_owners[i] = PAGE_UNALLOCATED;
}

// ページのインデックスを返す
uint32_t paddr_to_index(paddr_t paddr) {
    if (paddr < (paddr_t)__free_ram || paddr >= (paddr_t)__free_ram_end){ // 無効なアドレスの場合
        return -1; // 適当なエラー値を返す
    }    
    return (paddr - (paddr_t)__free_ram) / PAGE_SIZE; //__free_ram は，動的割当領域の開始アドレス
}

paddr_t alloc_pages(struct process* proc, uint32_t n) {
    static paddr_t next_paddr = (paddr_t) __free_ram;
    // 単ページならフリーリストから取得を試みる
    if (n == 1 && free_list != NULL) {
        // リスト操作
        // ...
        
        uint32_t page_index = paddr_to_index((paddr_t) page);
        page_owners[page_index] = proc; // ページの所有者を登録
        
        memset((void *) page, 0, PAGE_SIZE);
        return (paddr_t) page;
    }

    // フリーリストに要素がない場合はバンプで割当
    // ...
    
    // 割り当てる n ページ分すべてに所有者情報を登録
    for (uint32_t i = 0; i < n; i++) {
        uint32_t page_index = paddr_to_index(paddr + i * PAGE_SIZE);
        page_owners[page_index] = proc;
    }

    memset((void *) paddr, 0, n * PAGE_SIZE);

    return paddr;
}

// 引数に指定したプロセスのページを解放
void free_proc_pages(struct process *proc){
  for (int i = 0; i < TOTAL_PAGES; i++) {
        if (page_owners[i] == proc) {
            paddr_t page_addr = (paddr_t)__free_ram + i * PAGE_SIZE; // 該当ページのエントリを計算
            free_pages(page_addr, 1); // ページを解放
            page_owners[i] = PAGE_UNALLOCATED;
        }
    }
}

バンプ+フリーリストと比較して，以下のような変更を加えました．

1. page_owners[]という静的配列を用意
2. alloc_pages()をアップデート: ページ割当時，所有者情報を page_owners[] の該当要素に登録する
3. free_proc_pages()を実装: 指定したプロセスのページを解放．内部では，page_owners[] を走査して該当要素を PAGE_UNALLOCATED にする

OS in 1,000 Lines の範囲では，動的割当領域は固定長です．したがって，割り当てられるページ数も必然的に決まるため，静的配列を用いた簡単な実装にしました(実際は，プロセス管理構造体で，そのプロセスが持つページを管理するのが一般的だと思います)．

これでめでたく，各ページの所有者も管理できるようになり，プロセス終了時のメモリ解放処理も行えるようになりました．

感想

実装していると，「この設計だと，当初の理想通りには動かないかも……」という問題が何度も出てきました．そして，その問題を解決するためにコードを書き換えたり，設計を考え直したりしました．この試行錯誤を繰り返すことで，単に「こういう仕組みになっている」というところで留まらず，より深い学びがあったと感じました．また，今回は触れませんでしたが，実装中は「このままだと無駄に大きな領域を割り当てる場合もあるな」ということに気づいていました．そしてそれが「あ，授業で習った断片化ってこのことか」と，以前頭に入れた知識ともリンクしました．こういう学びがあるから，やっぱり手を動かして実装することは大事だと感じました．

おわりに

ここまで読んでくださりありがとうございます．
まだまだ独自拡張をしていきたいと考えており，出来次第そちらも記事にしていこうと思います．
また，今回は私の初めての Qiita 記事執筆となりました．
読みづらい点など多々あると思いますので，ぜひ改善点やアドバイスお待ちしております．

参考文献

• OS in 1,000 Lines
• nuta/operating-system-in-1000-lines - GitHub
• フリーリスト - Wikipedia

ライセンス

本記事では，OS in 1,000 Linesのソースコードの一部を掲載しています．

バンプアロケータのコードは，同教材の実装をそのまま転載したものです．
同リポジトリのソースコードは MIT License の下で公開されています．

• OS in 1,000 Lines - LICENCE.md
• MIT License