自作Slab allocator ""SLOBA""

先日、セキュリティキャンプという全国からセキュリティに興味がある学生を集めて5日間講義をするというプログラムに参加してきました。応募した理由はプログラムの中に、Linux カーネル開発の勉強ができるトラックがあったからです。結果としては幸い合格することができ、そこで僕はLinux カーネルのSlab allocatorを再実装することになりました。

前提知識

この記事を読むにあったって知っておいた方が良い用語

SLOB・SLAB・SLUB
Buddy System

開発の流れ

キャンプ前

Linux カーネルの開発はやったことがなく、四苦八苦しながら開発していました。まずはSLOBという組み込み向けに使われるらしい簡単な実装のSlab allocatorを改造していきました。ですが、アルゴリズム自体はSLOBをベースにしたLinked Listを用いた空き領域確保アルゴリズムだったので、まあSLABには到底敵いませんでした。なんとかSLABに匹敵するレベルのSlab allocatorを作りたいと思った僕は、SLOBとは全く異なるアルゴリズムを考えなければならないと思い、試行錯誤の末、後述するアルゴリズムを思いつき実装をはじめました。しかし、一から自分のアルゴリズムを実装しているので、バグが入り込みやすく、カーネルパニックを起こしまくり、キャンプ当日まで一回も起動に成功しませんでした。

キャンプ中

心強い講師の方々の応援を受け開発を進めていきました。スピンロックの基礎的なところから、ページ確保中にロックしてはいけないなどのアドバイスも受けました。ですが3日目中盤ごろになっても起動に成功せず、焦っていました。ココらへんは記憶が曖昧なのですが、3日目の夕方か夜頃に初めてSLOBAを積んだカーネルがQEMU上で動作しました。めちゃくちゃ嬉しかったのですが、いざVirtualBoxで動作させてみると、起動中にカーネルパニックを起こして起動に失敗してしまいました。VirtualBox上でのkgdbを使ったデバッグ方法がわからなかったのでこれはまずいなぁと思っていたところ、ある講師の方の助言で、なぜか敬遠していた、kvmを使うことにしました。実際にkvmを使って起動してみるとVirtualBoxのように起動に失敗しました。kvm上で動作するカーネルに対してはkgdbでデバッグすることができたのでなんとか開発を続けることができました。4日目には発表があったのでその日は夜遅くまでデバッグ作業をしていましたが、結局起動しませんでした。いろいろ調査した結果、これも後述するんですが、freelistからの確保で怪しいアドレスが混じっているらしいことに気が付き、怪しいアドレスが来たら弾くという通常ありえないコードを埋め込み対処しました。（発表が近かったからしょうがない！）弾くことでページを有効活用できる量が減るので効率や速度が落ちるわけですが、結果はSLABとほぼ同等のパフォーマンスを発揮することができました。（このバグをちゃんと潰すことができればSLAB超えも？？）

キャンプの感想

キャンプの講師の方々に対しては心の底からお礼を言いたいです。今まで実際にLinux カーネルに変更を加えたことがなかった僕ですが、講師の方々のアドバイスもあって、なんとか形になるような成果を出すことができました。カーネル開発の独特なハマりポイントを早期に解決できたのは講師の方々の力のおかげということは言うまでもありません。また、キャンプそのものも良い機会だったなと思います。セキュリティ（僕の場合は低レイヤー）に興味がある友人ができたり、こういうイベントがあるからこそ、カーネル開発の勉強を必死になって行うことができました。そして、Linux カーネル開発を小さなものですが行うことができました。やる気と根気がある人はぜひセキュリティキャンプに応募してみてください！少なからず、なにか成長できるはずです！

SLOBA概説

SLOBAはキャンプの事前課題から当日の5日間を掛けて開発したSlab allocatorのLinux実装です。 SLOBAはSLOBのインターフェースを利用して、確保処理、解放処理のアルゴリズム独自のものに0から書き直しています。

（それ以外はSLOBの流用か、一部改善の状態ですね。）

パフォーマンスは以下のような感じです。

duコマンドをLinux カーネルのGitリポジトリに対して適用し、その処理時間を元にしています。この際、ディスクIOによってパフォーマンスが変化しないように、一度duを走らせた後、スラブキャッシュだけを解放し、再度duを実行しています。（ページキャッシュは残る） f:id:atsisy:20180825210249p:plain f:id:atsisy:20180825210126p:plain

ソースコード行数はLinux v4.18.1のSLABの行数が4477行で、SLOBAがキャンプ終了時で680行だったので大体1/6で同等のパフォーマンスを引き出すことができました。（SLOBのインターフェースを利用しているため、そりゃ短くなるわけなんですがね。）

これからのSLOBA開発

SLOBAはGPL v2に則り、GitHubをベースに開発を進めていく予定です。僕はまだカーネル開発の素人なので一緒に開発してくれる人がいると嬉しいです。 SLOBAに興味があって開発に参加したいなと思っている人はぜひGitHubの機能を使って参加していただけると嬉しいです。

GitHub リポジトリはこちら

github.com

SLOBAにはまだまだバグや修正すべき点が残っています。キャンプは限られた時間の中での開発だったので、SLOBAはまだとりあえず動くレベルのSlab allocatorです。僕はSLOBAをもっと良いSlab allocatorにしたいと思っています。目標はひとまずSLABに前述のパフォーマンス測定方法で常に勝利するっていうところですかね。（もちろんメモリの解放もしっかりとやった上で）

SLOBAアルゴリズム解説

データ構造

YI OS開発ゼミ Linux開発者を目指そう！.png SLOBAではページを配列のように扱いスラブオブジェクトを確保していきます。さらに、kmallocによる確保もkmem_cache_allocによる確保を特に区別することはありません。（kmallocの場合はmeta情報を書き込むが）なので、このようにサイズごとにキャッシュを保持する構造体を持つことで高速性とメモリ効率を高めます。また、CPUごとにこれらの構造体をもたせることでマルチコアのCPUでも高速に動作するようにしています。

cache_array構造体

struct cache_array {
        union {
                void *head; // address of first page
                void *last; // last available page
        };
        unsigned short size;  // object size
};

cache_array構造体はこのように定義しています。headとlastは共用体で、利用可能なページの先頭を指します。sizeはこのcache_arrayは何byte用のcache_arrayなのかを記憶しておくためのものです。では、なぜheadとlastは共用体として定義されているのでしょうか。これでは一つのページしか指すことができません。ですが、実際指すページは一つだけで十分です。これは後から理解できると思います。

ページの取り扱い (page_cache_head構造体)

struct page_cache_head {
        void *freelist;
        unsigned short avail;   // available objects
        unsigned short counter;
        unsigned short size;
};

SLOBAではBuddy Systemからもらったページの先頭にpage_cache_head構造体で表される情報を書き込んでいます。64bitのアーキテクチャではこの構造体のサイズは14byteで8byteアラインされれば16byteになります。つまりページ先頭16byteにはこの情報が書き込まれているということです。さらに言えば、cache_arrayのheadやlastはこのpage_cache_head構造体を指しているということです。 freelistメンバはkfreeやkmem_cache_freeによって解放された領域を非常に高速に再利用するための機構に利用しますが、これが今も悩んでいるバグの温床だったりします。このfreelistを使ったfreeされた領域の再利用方法は後述します。

availはあと何個のcache_arrayで定義されたサイズのオブジェクトがこのページに入ることができるのかという情報が入っています。これをデクリメントしていきながら、配列として分割されたページにアクセスしていくことで高速にメモリの割り当てを行うことができます。このアイデアはSLABからパクりました。 counterメンバは、現在何個の有効なオブジェクト（確保されたが解放されていない）がこのページに存在しているかを記録しています。availが一度すべて使い切られ、このcounterが0になった場合はページごと解放されます。 sizeメンバはこのページは何byte用のページなのかを示します。わざわざcache_arrayを見つけ出して獲得するのが面倒なのでここに入れました。（どうせアラインメントされて16byteの構造体になっちゃうしね）

kmallocのメタデータ

kmallocに関して、Slab allocatorはksize関数や内部処理においてもともと要求されていたサイズを覚えておく必要があります。SLOBAでは、kmallocによって確保されるサイズを2byte余計に取り、そこにメタデータを格納しています。これはkmalloc_meta_data型として持っています。定義は以下のような具合です。

typedef unsigned short kmalloc_meta_data;

この2byteにはkmallocに関して２つの情報が格納されています。もともと要求されていたサイズ。あと、格納されており領域確保の際にアドレスをアラインメントをしてから返却する必要あるんですが、何もデータを保持していないと、もともと確保した領域の先頭のアドレスがわからなくなってしまうので実際に確保した領域のアドレスとアラインメントされた後のアドレスの差分を格納しています。この２つの情報をうまく2byteに収めています。また、このkmalloc_meta_dataはencodeとdecode用の関数を定義していてそれぞれ次のように定義されています。

inline static unsigned short get_kmalloc_size(kmalloc_meta_data kmeta)
{
        return (kmeta >> 8) << 3;
}

inline static unsigned short get_kmalloc_delta(kmalloc_meta_data kmeta)
{
        return (kmeta & 0x00ff) << 3; 
}

inline static kmalloc_meta_data encode_kmalloc_meta_data(unsigned short size, unsigned short delta)
{
        return (kmalloc_meta_data)((size >> 3) << 8) | (delta >> 3);
}

kmallocのメモリ配置などは、言葉だけではなく実際に図があったほうがわかりやすいと思うので、一応置いておきます。

f:id:atsisy:20180825231820p:plain

今のSLOBAにはまだ不具合があります。この不具合はこのメタデータ配置位置かメタデータ取り出しにバグがあると僕は考えています。

確保処理

SLOBAではページをスラブオブジェクトの配列として扱います。ここでは、それについて解説していきます。

スラブオブジェクト確保処理

スラブオブジェクトの確保処理に関するコードを以下に示しておきます。全部載せるときりがないので、確保処理の本体だけにします。詳しく見たい方は前述のGitHub リポジトリからどうぞ。

static void *slob_alloc(size_t size, gfp_t gfp, int align, int node, char way)
{
    void *b = NULL;
        void *ret = NULL;
        unsigned long flags;
        size_t aligned_size = size + align;
        struct cache_array *slob_list = get_proper_sloba_list(aligned_size);
        struct page_cache_head *page_head;
        
        /*
         * this cache_array is not initialized
         */
        if(!slob_list->head)
                if(!cache_array_init_firstpage(slob_list, gfp, node))
                        return NULL;

        spin_lock_irqsave(&slob_lock, flags);
        // we'll allocate slab from this page
        page_head = slob_list->last;

        if((b = sloba_alloc_from_freelist(page_head, slob_list->size))){
               te spin_unlock_irqrestore(&slob_lock, flags);
                goto done;
        }
        spin_unlock_irqrestore(&slob_lock, flags);
        
        // if this page is not available, find available page
        if(!page_head->avail)
                page_head = slob_list->last = sloba_alloc_new_page(page_head, gfp, node, slob_list->size);
        
        // get slab from back
        b = (void *)(page_cache_get_head(page_head) + (slob_list->size * (--page_head->avail)));

done:
        page_head->counter++;
        ret = (void *)ALIGN((unsigned long)b, align);
        
    if (unlikely(gfp & __GFP_ZERO))
        memset(ret, 0, size);

        if (way == KMALLOC_ALLOCATE) {
                int delta = ret - b;
                spin_lock_irqsave(&slob_lock, flags);
                *(kmalloc_meta_data *)ret = encode_kmalloc_meta_data(size - KMALLOC_SIZE_BUF_SIZE, delta);
                spin_unlock_irqrestore(&slob_lock, flags);
                ret += KMALLOC_SIZE_BUF_SIZE;
        }
        
    return ret;
}

YI OS開発ゼミ Linux開発者を目指そう！(1).png YI OS開発ゼミ Linux開発者を目指そう！(2).png まあこんな感じで確保を行います。このavailが0になった場合は、新しくページを確保することになります。そのときの処理はこんな感じです。

static void *slob_alloc(size_t size, gfp_t gfp, int align, int node, char way)
{
        ...
        // if this page is not available, get free page
        if(!page_head->avail)
                page_head = slob_list->last = sloba_alloc_new_page(page_head, gfp, node, slob_list->size);
        ...
}

こんな感じです。これで次からは新しく確保したページから確保処理を行うようになります。いっぱいになってしまったページはいっぱいになったという印をつけられ、これ以降は解放処理しか受け付けなくなります。（というか、そもそも参照できない）これにより保持すべきページは一つだけでよくなるのでcache_array構造体にはページを指すポインタが一つしかないわけです。

freelistからの確保

以上のような確保処理のみだと解放された領域を再利用する手立てがありません。これではBuddy Systemによるページ確保処理が走りまくり性能が低下し、メモリ効率も悪いです。そこでfreelistからの確保を行います。ですが、list_headに代表されるLinked Listはアクセス速度が悪くSLOBに逆戻りしてしまいます。この処理はSLOBAのメモリ解放処理を理解していないと理解しきれないと思うので、飛ばして後から読んでください。

一応確保処理は確保処理でまとめたかったんですよね。すいません。

...

はい。free処理は読みましたね。読んでないと理解が浅くなりますよ。

では説明していきたいと思います。ページごとのデータ構造であるpage_cache_head構造体のfreelistメンバには、初期値としてNULLが入っています。（page_head_init関数を参照） slob_freeが走るとfreelistにはfreeされた領域のポインタが代入され、それが繰り返されるとLinked Listが構築されます。

なので、freelistからの確保というのは、このfreelistに入っている領域を新しく確保し、返すというものなんです。

では、実際にslob_alloc関数でどのように書かれているかを見ます。

static void *sloba_alloc_from_freelist(struct page_cache_head *page_head, size_t size)
{
        // available space is found in freelist
        if(page_head->freelist && check_address(page_head->freelist, page_head, size)){
                void *ret = page_head->freelist;
                page_head->freelist = *(void **)ret;
                return ret;
        }
        return NULL;
}

static void *slob_alloc(size_t size, gfp_t gfp, int align, int node, char way)
{
        ...
        if((b = sloba_alloc_from_freelist(page_head, slob_list->size))){
               te spin_unlock_irqrestore(&slob_lock, flags);
                goto done;
        }
        ...
}

もちろん、このfreelistからの確保の優先度は通常の確保よりも高いです。じゃないとfreelistから確保する以前に配列アクセスによってすべて使い切ってしまいますからね。 CPUのキャッシュにヒットさせるためにも、できるだけ早く解放された領域を使わなくてはいけません。

freelistからの確保で重要なのはsloba_alloc_from_freelist関数内の次の二行です。

void *ret = page_head->freelist;
page_head->freelist = *(void **)ret;

日本語力が乏しい僕にとっては図で説明する方が簡単なので、それで行きます。

f:id:atsisy:20180825181106p:plain f:id:atsisy:20180825181316p:plain

解放処理

スラブオブジェクト解放

スラブオブジェクトの解放処理はめちゃくちゃ簡単です。

static void slob_free(void *block, int size)
{
        struct page_cache_head *page_head;
        unsigned long flags;
        
        if (unlikely(ZERO_OR_NULL_PTR(block)))
            return;
        BUG_ON(!size);
        
        spin_lock_irqsave(&slob_lock, flags);

        page_head = (struct page_cache_head *)((unsigned long)block & PAGE_MASK);
        page_head->counter--;
        if(is_dead_page(page_head) && !page_head->counter){
                struct page *sp = virt_to_page(page_head);
                if (slob_page_free(sp))
                    clear_slob_page_free(sp);
                spin_unlock_irqrestore(&slob_lock, flags);
                __ClearPageSlab(sp);
                page_mapcount_reset(sp);
                slob_free_pages(page_head, 0);
                return;
        }

        *(void **)block = page_head->freelist;
        page_head->freelist = block;
        
        spin_unlock_irqrestore(&slob_lock, flags);
}

実際のソースはこれだけです。しかも、ページのそのものの解放が発生しなければ、数行で終わるような処理です。で、ここで何をやっているかを図で説明します。

※アドレスがおかしいとかポインタが格納できるだけのサイズが無いとかの矛盾がありますが、まあ例として見てやってください。

まず、アドレスaから始まる領域をfreeしたいとします。その時は、

f:id:atsisy:20180825145146p:plain

*(void **)block = page_head->freelist;
page_head->freelist = block;

この処理で解放が行われます。 SLOBAでは最小のスラブオブジェクトのサイズを8byteとしています。なので、いかなるスラブオブジェクトの領域でも先頭からポインタを書き込むことは可能です（ポインタが64bitのアーキテクチャならば）。さらに、freeされた後の領域には、外部からアクセスされないのでSlab allocatorが自由に書き込んでも大丈夫というわけです。引き続き見ていきます。 f:id:atsisy:20180825145333p:plain

freeが呼ばれるたびにこれが行われます。

f:id:atsisy:20180825145349p:plain f:id:atsisy:20180825145620p:plain f:id:atsisy:20180825145710p:plain f:id:atsisy:20180825145750p:plain

するとどうでしょう。なんと外部からメモリを確保することなく、空き領域をLinked List上につなぐことができました。しかもこれはスタックのようにListがつながっているので、解放されたばかりの領域から辿れるようになっています。

f:id:atsisy:20180825150448p:plain

スラブオブジェクトの際にはpage_cache_head構造体のcounterメンバがデクリメントされています。このカウンタが0になりかつ、このページは配列アクセスによりメモリを確保できない状態であれば、ページが解放されます。

ページ解放処理

ここの処理は普通にフラグの設定を行ったあと、free_pages関数のラッパ関数を呼び出して解放しているだけです。

まとめ

ソースコードをすべて説明していくと、記事を書くのが大変になって、書くのをやめてしまうので、これくらいにしておきます。おそらく、これでSLOBAのアルゴリズムの概要はつかめたと思います。もっと詳しく知りたいという人は、ぜひSLOBAのGitHub リポジトリを見てください。行数自体は少ないので簡単に読めると思います。

今回、Slab allocatorを実装しましたが、僕のカーネル開発歴（実際に既存カーネルのリビルドが必要になる程度の変更を加え始めてから）1ヶ月くらいです。Linux カーネルの内部は高度に抽象化が施されていて、一部の機能を除けば、ちょっと勉強すれば誰でも簡単に変更を加えることができます。さらに、Linux カーネル自体、ソースコードに対する資料の量は他のOSSに比べて圧倒的です。そういう面では、意外と変更の難易度の低いプロジェクトなのかもしれません。ぜひ、Linux カーネルの開発をしてみたいけど難しそうと思っているかたはぜひ手を動かしてやってみることをおすすめします。意外といけますよ！

ではここらへんで失礼します。次回はSLOBAの詳しいベンチマークとかかなぁ。

空き地の資料室

さとりが好きなプログラマが進捗をまとめて軽く記事を書きます。

セキュリティキャンプと自作Slab allocator SLOBA