とりあえず何を読もうか

どうも、クリスマスも近いというのに、ソースの読み書きか酒を飲んでいるかどちらかの@akachochinです。
今回の投稿参加は酒飲んだ勢いで決めました(笑)。

それはともかく。最近複数の方から「カーネルのソース読みたいけど、よくわからん」という相談を受けました。

その人の知識レベルにもよりますが、まずドライバを読んでカーネルコードの雰囲気を味わいつつ、カーネル内APIを調べたり読んだりして、徐々に領域を広げていくのが良いのかな、と思います。ただし、細かなデバイスの制御は無視したほうがよいでしょう。そういう意味で、仮想的なデバイスドライバは格好の教材だと思います。

ところで今回のネタは・・・ない・・・。そういえばAndroidカーネルもLinuxだったよな。Androidカーネル・・・すぐ読めそうなの・・・ソースを漁って・・・

ということでashmem読んでみます

ashmemは、shmemと同様にプロセス間でメモリを共有するための仕組みです。LWN.netの記事や京都マイクロコンピュータさんのスライド、Tech Noteというページによると、特徴は以下のとおりです。

ページピンニング(page pinning)という概念を導入している。ピン留めという名称から、ピン留めされている間、確保したメモリページを解放せずに保持する機能があることが推定できます。
その逆にUnpinnedされたページはメモリ不足の際に回収されるようです。
メモリを扱うために、/dev/ashmemというデバイスファイルを使ってアクセスを行う。
mmap()によってマップされた仮想アドレス空間もしくはread()を用いてメモリにアクセスします。
バッキングストアは単なるshmemファイル。shmemをラッピングして使いやすくした機能とも受け取れますね。

なお、バッキングストアは「RAMページの中身の元ネタとなるファイル」という意味くらいに捉えておけば良いと思います。(仮想記憶を本格的に読む場合、バッキングストアの概念を理解することは必須です。)

Linuxの場合、ググったり書籍を読んで調べると機能の概要を知ることができるケースが多いです。まず調べてみましょう。
機能の話はともかく、実装についてはあくまでも参考にしてください。文書作成以降に実装が大幅に変更され、乖離が生じることが多々あるためです。ソースで確認するのが確実です。特に職業でLinuxカーネルいじる場合は注意です。文書だけ鵜呑みにすると大変なことになるかもしれませんぜ。

Androidのソース取ってくるの面倒なので(おい)

手元にあるLinux4.3のdrivers/staging/android/ashmem.cを読むことにします。

まずは初期化処理

初期化処理を読むことで、データ構造を把握できることが非常に多いです。個人的には、最初に初期化処理に目を通すのが良いと考えます。

drivers/staging/android/ashmem.c

static struct shrinker ashmem_shrinker = {
    .count_objects = ashmem_shrink_count,
    .scan_objects = ashmem_shrink_scan,
/* 略 */
    .seeks = DEFAULT_SEEKS * 4,
};

static int __init ashmem_init(void)
{
    int ret;

    ashmem_area_cachep = kmem_cache_create("ashmem_area_cache",
                      sizeof(struct ashmem_area),
                      0, 0, NULL);
    /* 略 */
    ashmem_range_cachep = kmem_cache_create("ashmem_range_cache",
                      sizeof(struct ashmem_range),
                      0, 0, NULL);
    /* 略 */
    ret = misc_register(&ashmem_misc);
    /* 略 */
    register_shrinker(&ashmem_shrinker);
    /* 略 */
}

やっていることは事実上、以下3点です。

単純にashmem_range構造体とashmem_area構造体を確保している
register_shrinker()を呼び出して、仮想記憶システムに対してメモリ逼迫時に登録処理を呼び出すように依頼(Add a shrinker callback to be called from the vm)詳しくはmm/vmscan.cを読んでください。)
misc_register()を呼び出して、デバイスドライバのフレームワークにドライバI/Fなどを登録する。

ashmem_areaは共有メモリ領域を管理するための構造体です。fileやprot、sizeといったメンバからもメモリ領域を表現するデータ構造であることが伺えます。(先ほど「バッキングストアは単なるshmemファイル」と書いたことを思い出していただけると幸いです。)

drivers/staging/android/ashmem.c

/**
 * struct ashmem_area - The anonymous shared memory area
 * 略
 */
struct ashmem_area {
    char name[ASHMEM_FULL_NAME_LEN];
    struct list_head unpinned_list;
    struct file *file;
    size_t size;
    unsigned long prot_mask;
};

一方で、ashmem_range構造体は**「unpinnされたり、evictableされたページの範囲を表現する」構造体**と判断できます。その理由はコメントです。コメントはできる限り目を通してみましょう。残念SIerの「// iをインクリメントする」的な腹の足しにもならないコメントが書かれることはあまりありません。

drivers/staging/android/ashmem.c

/**
 * struct ashmem_range - A range of unpinned/evictable pages
 * 略
 * The lifecycle of this structure is from unpin to pin.
 */
struct ashmem_range {
    struct list_head lru;
    struct list_head unpinned;
    struct ashmem_area *asma;
    size_t pgstart;
    size_t pgend;
    unsigned int purged;
};

open()

初期化処理と並んで、ドライバの場合はopen()に目を通してみるのも良いと思います。
ashmemのopen()は以下のように、ashmem_area構造体の割り当てが処理の中心です。

drivers/staging/android/ashmem.c

static int ashmem_open(struct inode *inode, struct file *file)
{
    struct ashmem_area *asma;
    /* 略 */
    asma = kmem_cache_zalloc(ashmem_area_cachep, GFP_KERNEL);
    /* 略 */
    file->private_data = asma;

    return 0;
}

mmap

ashmemがユーザに公開しているI/Fの一つです。単なるパラメータチェック処理は省略します。また、最後に実施している特殊な処理も省略します。(特殊な処理の場合、コメントが手厚く付いていることが多かったりします。)
骨になるところだけ見ると、以下のようになると思います。
骨となるところを取捨選択して、とりあえず該当処理が何をやっていそうかイメージしていくことが大切です。

drivers/staging/android/ashmem.c

static int ashmem_mmap(struct file *file, struct vm_area_struct *vma)
{
    struct ashmem_area *asma = file->private_data;

/* 単なるパラメータチェックなので、略 */

    if (!asma->file) {
        /* 略 */
        /* ... and allocate the backing shmem file */
        vmfile = shmem_file_setup(name, asma->size, vma->vm_flags);
        /* 略 */
        asma->file = vmfile;
    }
    get_file(asma->file);
        /* 略 */
}

処理の中心は、shmem_file_setup()となることがわかります。つまり、バッキングストアとなるshmemファイルシステムのファイルを生成することがashmemのmmap()の骨格であると言えそうです。

shmem_file_setup()を読んでも良いですが、ひたすらパラメータを埋めていくだけの初期化系処理は読んでて面白くありません(笑)。
当面ashmemのソースを読むためには、「shmemファイルシステムへのアクセス時、つまりVFSのI/Fを通して最終的に呼ばれる具体的な関数は何か」という事項が分かれば十分と思われます。
具体的には、以下のとおりです。

mm/shmem.c

static const struct file_operations shmem_file_operations = {
    .mmap       = shmem_mmap,
#ifdef CONFIG_TMPFS
    .llseek     = shmem_file_llseek,
    .read_iter  = shmem_file_read_iter,
    .write_iter = generic_file_write_iter,
    .fsync      = noop_fsync,
    .splice_read    = shmem_file_splice_read,
    .splice_write   = iter_file_splice_write,
    .fallocate  = shmem_fallocate,
#endif
};
/* 略 */
static struct file *__shmem_file_setup(const char *name, loff_t size,
                       unsigned long flags, unsigned int i_flags)
{
    /* 略 */
    res = alloc_file(&path, FMODE_WRITE | FMODE_READ,
          &shmem_file_operations);
    /* 略 */
}

関数ポインタは、良い実装をする上でもちろん必要です。しかし、ソースを読むときは厄介です。なので、静的にソースを読む場合、関数ポインタの先に何がついているかを把握することは重要です。

read()

drivers/staging/android/ashmem.c

static ssize_t ashmem_read(struct file *file, char __user *buf,
               size_t len, loff_t *pos)
{
/* 略 */
    ret = __vfs_read(asma->file, buf, len, pos);
/* 略 */
}

実は、上記のread()は複数の関数呼び出しを経て、shmem_file_read_iter()を呼び出します。今はここでやめておきます。

ピン留め

「pin」でソースを調べてみると、以下の箇所が該当します。
ashmem_ioctl()であれば、ユーザプロセスからのioctl()経由で呼び出し可能です。

drivers/staging/android/ashmem.c

static long ashmem_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
{
/* 略 */
    case ASHMEM_PIN:
    case ASHMEM_UNPIN:
    case ASHMEM_GET_PIN_STATUS:
        ret = ashmem_pin_unpin(asma, cmd, (void __user *)arg);
        break;
/* 略 */
}

ASHMEM_PIN(ピン留め)の場合、ashmem_pin()が、ASHMEM_UNPIN(ピン留め解除)の場合はashmem_unpin()が呼び出されます。

ASHMEM_PIN(ピン留め)

以下の処理です。長いですが、あえて全部載せてみました。
この処理はashmemが管理する領域(第一引数)のうち、どの範囲をピン留めするか開始地点(第二引数)と終了地点(第三引数)を指定するI/Fです。
ここで、先に書いたとおり、「ashmem_range構造体は、ピン留めされていない領域を表現する」ことを頭に留めてください。

drivers/staging/android/ashmem.c

/*
 * ashmem_pin - pin the given ashmem region, returning whether it was
 * previously purged (ASHMEM_WAS_PURGED) or not (ASHMEM_NOT_PURGED).
 *
 * Caller must hold ashmem_mutex.
 */
static int ashmem_pin(struct ashmem_area *asma, size_t pgstart, size_t pgend)
{
    struct ashmem_range *range, *next;
/* 略 */
    list_for_each_entry_safe(range, next, &asma->unpinned_list, unpinned) {
        /* moved past last applicable page; we can short circuit */
        if (range_before_page(range, pgstart))
            break;

        /*
         * The user can ask us to pin pages that span multiple ranges,
         * or to pin pages that aren't even unpinned, so this is messy.
         *
         * Four cases:
         * 1. The requested range subsumes an existing range, so we
         *    just remove the entire matching range.
         * 2. The requested range overlaps the start of an existing
         *    range, so we just update that range.
         * 3. The requested range overlaps the end of an existing
         *    range, so we just update that range.
         * 4. The requested range punches a hole in an existing range,
         *    so we have to update one side of the range and then
         *    create a new range for the other side.
         */
        if (page_range_in_range(range, pgstart, pgend)) {
            ret |= range->purged;

            /* Case #1: Easy. Just nuke the whole thing. */
            if (page_range_subsumes_range(range, pgstart, pgend)) {
                range_del(range);
                continue;
            }

            /* Case #2: We overlap from the start, so adjust it */
            if (range->pgstart >= pgstart) {
                range_shrink(range, pgend + 1, range->pgend);
                continue;
            }

            /* Case #3: We overlap from the rear, so adjust it */
            if (range->pgend <= pgend) {
                range_shrink(range, range->pgstart, pgstart-1);
                continue;
            }

            /*
             * Case #4: We eat a chunk out of the middle. A bit
             * more complicated, we allocate a new range for the
             * second half and adjust the first chunk's endpoint.
             */
            range_alloc(asma, range, range->purged,
                    pgend + 1, range->pgend);
            range_shrink(range, range->pgstart, pgstart - 1);
            break;
        }
    }

    return ret;
}

指定された領域を「unpinned(ピン留めされていない)」から「pinned(ピン留めされた)」に変更する処理です。アルゴリズムはわかったでしょうか。
pinnedしたい領域を、ashmem_renge構造体がカバーしている場合、何らかの変更を加えないといけません。実は、上記のケースはそれぞれ以下の図に対応しています。

この図を読んで、読み直してみると、だいぶ理解も進むのではないかな、と思います。
カーネルに限らず、ソースを読むときには、globalやctagsなどのソースコードタグ付けツールやエディタの支援機能が役に立ちます。加えて、ペンと紙を用意してデータ構造やアルゴリズムなどをメモしながら読んでみることをオススメします。
手書きなので、フリーフォーマット。簡単にデータ構造やアルゴリズムをビジュアルにできるので、直感的な理解が進みます。さらに、職業でソースを読む場合、知識共有のための報告書を作成するときにも役立ちます。VisioやLibreOffice Drawで描く場合の下書きとしても、手書き文書をスキャンして貼り付けるにしても役に立つでしょう。

なお、ashmem_pin()と対になるashmem_unpin()は省略します。やっていることは「ashmem_range構造体をリストに挿入する。そのために、挿入位置を決めて、ashmem_range構造体を割り当てて挿入」というのが本筋です。練習がてら読んでみてください。

unpinする目的

最初に「その逆にUnpinnedされたページはメモリ不足の際に回収されるようです。」と書いてあったことを覚えているでしょうか。
また、初期化処理の説明で「register_shrinker()を呼び出して、仮想記憶システムに対してメモリ逼迫時に登録処理を呼び出すように依頼」と書いてあったのを覚えているでしょうか。

これらを確かめるため、register_shrinker()を見てみましょう。

mm/vmscan.c

/*
 * Add a shrinker callback to be called from the vm.
 */
int register_shrinker(struct shrinker *shrinker)
{
/* 略 */
    down_write(&shrinker_rwsem);
    list_add_tail(&shrinker->list, &shrinker_list);
    up_write(&shrinker_rwsem);
    return 0;
}
EXPORT_SYMBOL(register_shrinker);

渡された関数ポインタなどを含む構造体をshrinker_listにキューイングしています。
shrinker_listを漁るのはmm/vmscan.cのshrink_slab()で、呼び出し先を調べてみると「get_any_page()」とか「memory_failure()」とか必死さがじわじわ伝わってくるような関数たちになります。ただ、今回はこれら関数の実装解説はしません。

shrinker_listキュー経由で呼び出される関数はどうなっているのでしょうか。

drivers/staging/android/ashmem.c

static unsigned long
ashmem_shrink_scan(struct shrinker *shrink, struct shrink_control *sc)
{
/* 略 */
    mutex_lock(&ashmem_mutex);
    list_for_each_entry_safe(range, next, &ashmem_lru_list, lru) {
/* 略 */
        vfs_fallocate(range->asma->file,
                  FALLOC_FL_PUNCH_HOLE | FALLOC_FL_KEEP_SIZE,
                  start, end - start);
/* 略 */
    }   
    mutex_unlock(&ashmem_mutex);
    return freed;
}

vfs_fallocate()をasma->file、つまりshmemファイルシステムに対して呼び出しています。
最後に、vfs_fallocate()をちょっと覗いてみましょう。

vfsを少し覗く

VFSなので、基本的には最終的に各ファイルシステムごとの処理が呼ばれます。
先ほど、shmemファイルシステムの関数ポインタ群について書いてあったことを覚えているでしょうか。

mm/shmem.c

static const struct file_operations shmem_file_operations = {
/* 略 */
    .fallocate  = shmem_fallocate,

今回、vfs_fallocate()の第二引数に「FALLOC_FL_PUNCH_HOLE | FALLOC_FL_KEEP_SIZE」が指定されています。乱暴な言い方をすると、「ファイルの途中に何も割り当てられていない穴を開ける」というイメージです。「穴」はもちろんunpinnedな領域です。

mm/shmem.c

static long shmem_fallocate(struct file *file, int mode, loff_t offset,
                             loff_t len) 
{
/* 略 */
    if (mode & FALLOC_FL_PUNCH_HOLE) {
/* 略 */
        if ((u64)unmap_end > (u64)unmap_start)
            unmap_mapping_range(mapping, unmap_start,
                        1 + unmap_end - unmap_start, 0);
        shmem_truncate_range(inode, offset, offset + len - 1);
/* 略 */
        goto out;
    }

上記の処理を見ると、仮想アドレス空間から指定された範囲を消し(unmap_mapping_range())、実際に割り当てられていたメモリページを解放します。(shmem_truncate_range())。
shmem_truncate_range()は複数の関数呼び出しを経て、以下のshmem_undo_range()を呼び出し、この中でpagevec_release()を呼びます。
そして最後にはrelease_pages()を呼び出し、ページの解放を行います。
つまり、メモリ逼迫時にはashmem_shrink_scan()の処理によって不要なページが解放されることがわかります。(残念ですが、今回はrelease_pages()には踏み込みません。興味ある方はご一読を。)

mm/shmem.c

static void shmem_undo_range(struct inode *inode, loff_t lstart, loff_t lend,
                                 bool unfalloc)
{

    pagevec_init(&pvec, 0);
    index = start;
    while (index < end) {
        pvec.nr = find_get_entries(mapping, index,
            min(end - index, (pgoff_t)PAGEVEC_SIZE),
            pvec.pages, indices);
        /* 略 */
        pagevec_release(&pvec);
        cond_resched();
        index++;
    }
    /* 略 */

まとめ

この文書では、以下のことを書きました。これらはプレゼン資料などから読み取った内容です。ソースを読むことでかなり具体的にできました。

 - ページピンニング(page pinning)という概念を導入している。ピン留めという名称から、ピン留めされている間、確保したメモリページを解放せずに保持する機能があることが推定できます。
 - その逆にUnpinnedされたページはメモリ不足の際に回収されるようです。
 - メモリを扱うために、/dev/ashmemというデバイスファイルを使ってアクセスを行う。
 - mmap()によってマップされた仮想アドレス空間もしくはread()を用いてメモリにアクセスする。
 - バッキングストアは単なるshmemファイル。shmemをラッピングして使いやすくした機能とも受け取れますね。

最後にshmemファイルシステムのfallocate()の処理の一部に踏み込んだように、ashmemドライバのようなかなり小さめのドライバでもカーネルの処理に~~迷い込む~~踏み込む道はあります。

例えば、misc_register()を通してドライバのフレームワークに踏み込むのもよし、kmalloc()のようなメモリ割り当て関数を通して仮想記憶に足を踏み入れるもよし、ファイルシステムの処理を読むのもよしです。

いっぺんに全部把握するのは無理です！(きっぱり)少しずつで構わないので良い本を片手に読みつつ、ソースを読んで少しずつ周辺を固めていくのが良いかな、と思います。@masami256さんが書いたLinux Kernel Hack入門編という良記事がそのあたり大変参考になります。また、この記事の最後のほうに書かれているような勉強会に参加して、周りの人に質問してみるという手もあります。

何はともあれ、今年も少ないですが、今年も来年もHappy Hacking!