tkokamoの日記

HPCの研究開発なのでそんなことをかきたい

RCU(Read Copy Update)をちゃんと知る(2)-1 RCUにおけるポインタの更新と参照

はじめに

前回(http://tkokamo.hateblo.jp/entry/2017/08/12/191142)で概要は終わりにし、 今回からはコードを見ていこうと思います。

大体以下のような流れでRCUの実装を見ていこうかと思います。

  • rcu_dereference(), rcu_assign_pointer() ← 今回
  • Classic RCU
  • Tree RCU

rcu_read_lock()rcu_read_unlock()はプリエンプションの無効化/有効化である、ということは前回述べたので触れないです。

RCUでのポインタの更新(と参照)

概要(http://tkokamo.hateblo.jp/entry/2017/05/31/213427)で述べたように、
RCUにおけるデータの更新は、更新後データの初期化を行った後、古いデータを指していたポインタを新しいデータに置き換えることで行われます。(下図参照)

f:id:tkokamo:20170816144144p:plain

更新後データは、値の初期化後にポインタによって指されるため、参照側に中途半端な状態(更新中のデータ)が見えることは無いはずですが、
現在のシステムでこれを保証するには少しだけ細工をしなければいけません。

データの初期化後にポインタで指す、という例として以下にコードを示します。

struct foo {
   int a;
   int b;
};

struct foo *foop = NULL;
struct foo new;

/*foop!=NULLで値を出力*/
void reader()
{
    int a, b;
    if (foop != NULL) {
        a = foop->a;
        b = foop->b;
        printk("Set. a = %d, b = %d\n", a, b);
    }
    return;
}

/*newを初期化しfoopにセット*/
void writer()
{
    new.a = 1;     // (1)
    new.b = 1;     // (2)
    foop = &new;   // (3)
    return;
}

reader()は、writer()によりnewfoopにセットされていればその値を読み出し出力する、という関数ですが、
writer()(1), (2), (3)の順序が変わってしまう場合には、Set. a = 1, b = 1が出力されるとは限りません。
そして、これらは以下の2つのメモリアクセス順序の変更によって実際に起きることがあります。

  • コンパイラによるメモリアクセス順序の変更
    静的なリオーダリング
  • CPUによるメモリアクセス順序の変更(目に見えるのはSMP)
    動的なリオーダリング

RCUにおけるポインタの更新と参照は、上記2種類のリオーダリングを適切に防ぐことで実装されています。 以下ではそれぞれのリオーダリングについて見たあとに、rcu_dereference()rcu_assign_pointer()の実装を見てみます。

コンパイラによるメモリアクセス順序の変更

人間はしばしばおバカなコードを書いてしまい、メモリアクセスの観点から効率が悪いことがありますが、
コンパイラはその尻拭いをしてくれます。

例を下に示します。

// おばかなコード
#include <stdio.h> 
 
int main() 
{ 
        unsigned long arr[16]; 
        int i; 
 
        arr[0] = 1; 
        arr[8] = 1; 
        arr[1] = 1; 
        arr[9] = 1; 
        arr[2] = 1; 
        arr[10] = 1; 
        arr[3] = 1; 
        arr[11] = 1; 
        arr[4] = 1; 
        arr[12] = 1; 
        arr[5] = 1; 
        arr[13] = 1; 
        arr[6] = 1; 
        arr[14] = 1; 
        arr[7] = 1; 
        arr[15] = 1; 
 
        for (i = 0; i < 16; i++) 
                printf("%lu", arr[i]); 
 
        printf("\n"); 
        return 0; 
}

上のコードは二つのキャッシュラインを交互に見て1を代入しているおばかなコードです。(家の環境のi7-2600は確かキャッシュラインサイズが64B)
これをgccで最適化なしでコンパイルすると、、、

; 最適化なしの代入コード
        movq    $1, -144(%rbp)  ;arr[0] = 1
        movq    $1, -80(%rbp)   ;arr[8] = 1
        movq    $1, -136(%rbp)  ;arr[1] = 1
        movq    $1, -72(%rbp)   ;arr[9] = 1
...

馬鹿な人間に忠実なコードを吐いてくれますが、-O3をつけると

; -O3付き
        movdqa  %xmm0, (%rsp)
        movdqa  %xmm0, 16(%rsp)
        movdqa  %xmm0, 32(%rsp)
...

となります。movdqa命令はいわゆるSIMD命令です。
-O3を付けてコンパイルをすると、配列アクセスがプログラマが書いたようにではなく、ストリーム的にアクセスされるよう最適化されています(ストリームというにはしょぼいか)。
上記のようなコードであれば、特に意味も変わりませんが、代入の順番が大きな意味を持つ場合、最適化されてしまっては困ります。

gccではasm volatile("" ::: "memory");を入れることで、その前後のメモリアクセス順序がコンパイラによって変更されることを防ぐことができます。
今回の例の各代入文の間にasm volatile("" ::: "memory");を入れると、-O3を付けたとしても、メモリアクセス順序が人間の意図したままに維持されます。(興味があれば試してみてください)

CPUによるメモリアクセス順序の変更

こちらの方が少し理解に苦しむかも知れませんが、コンパイラ同様CPUもメモリアクセス順序を変更し、プログラム実行の最適化を図っています。
CPUによるリオーダリングが効いてくる例を見てみます。

// mem.c
#include <stdio.h>
#include <pthread.h>

struct arg {
        int a;
        int b;
        int c;
        int d;
};

void *t1_func(void *p)
{
    struct arg *arg = (struct arg *)p;

    arg->a = 1;
    if (arg->b == 0)
        arg->c = 1;

    return NULL;
}

void *t2_func(void *p)
{
    struct arg *arg = (struct arg *)p;

    arg->b = 1;
    if (arg->a == 0)
        arg->d = 1;
    
    return NULL;
}

int main()
{
    pthread_t t1, t2;
    struct arg arg;       

        /* 全部0で初期化 */
    arg.a = 0;
    arg.b = 0;
    arg.c = 0;
    arg.d = 0;

        /* スレッド生成 */
    pthread_create(&t1, NULL, t1_func, &arg);
    pthread_create(&t2, NULL, t2_func, &arg);

    /* スレッド終了待ち */
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

        /* a,b,c,dを出力 */
    printf("%d%d%d%d\n", arg.a, arg.b, arg.c, arg.d);
    return 0;
}

上記コードは、a,b,c,dを0で初期化したのちに2つのスレッドを生成し、各スレッドは以下の処理を行います。

// スレッド1
    arg->a = 1;
    if (arg->b == 0)     // (1)
        arg->c = 1;
// スレッド2
    arg->b = 1;
    if (arg->a == 0)     // (2)
        arg->d = 1;

親スレッドはスレッド1、スレッド2の終了後、a,b,c,dの値を出力しますが、
このコードは出力が1110または1101になることを期待しています。
その理由は以下の通りです。

  • (1)が成立するということは、スレッド1のarg->a = 1は実行されているが、スレッド2のarg->b = 1は実行されていない状態である。
    この時、スレッド2の(2)は成り立たず、4値の出力は1110となる。

  • (2)が成立するということは、スレッド2のarg->b = 1は実行されているが、スレッド2のarg->a = 1は実行されていない状態である。
    この時、スレッド1の(1)は成り立たず、4値の出力は1101となる。

しかし、SMP環境では1111が出力されてしまうことがあります。
以下では、上記コードを10000回実行し、出力が1111となってしまう回数を調べています。

答えが先になってしまいますが、1111が出力される理由はCPUによってメモリアクセス順序が変更されているからです。
下では、上記コードに対し、特定箇所にコンパイラ/CPUによるリオーダリングを禁止する命令を追加した場合、
シングルコアで上記コードを実行した場合に1111がどれくらい出力されてしまうかも合わせて示しています。

◯ 上で示したコード(SMP環境)
# for i in `seq 1 10000`; do ./mem >> mem.log; done
# grep 1111 mem.log | wc
    470     470    2350  ★470回1111が出力された

◯ 上で示したコード(シングルコア)
# echo 0 > /sys/devices/system/cpu/cpu1/online
# echo 0 > /sys/devices/system/cpu/cpu2/online
# echo 0 > /sys/devices/system/cpu/cpu3/online
# echo 0 > /sys/devices/system/cpu/cpu4/online
# echo 0 > /sys/devices/system/cpu/cpu5/online
# echo 0 > /sys/devices/system/cpu/cpu6/online
# echo 0 > /sys/devices/system/cpu/cpu7/online
# lscpu | grep On-line
On-line CPU(s) list:   0
# for i in `seq 1 10000`; do ./mem >> mem_uni.log; done
# grep 1111 mem_uni.log | wc
      0       0       0  ★1111は出力されなかった

◯ 特定箇所のコンパイラによるメモリリオーダリングを禁止したコード
# for i in `seq 1 10000`; do ./mem_comp >> mem_comp.log; done
# grep 1111 mem_comp.log | wc
    487     487    2435  ★487回1111が出力された

◯ 特定箇所のCPUによるメモリリオーダリングを禁止したコード
# for i in `seq 1 10000`; do ./mem_cpu >> mem_cpu.log; done
# grep 1111 mem_cpu.log | wc
      0       0       0  ★1111は出力されなかった

出力結果が1111となってしまう、ということはスレッド1の(1)、スレッド2の(2)が成り立ってしまった、ということです。
そして、この原因はCPUによるメモリアクセス順序の変更にあります。

/*再掲*/
// スレッド1
    arg->a = 1;
    if (arg->b == 0)     // (1)
        arg->c = 1;
// スレッド2
    arg->b = 1;
    if (arg->a == 0)     // (2)
        arg->d = 1;

SMP環境において、CPUは依存関係の無い二つのメモリアドレスに対するアクセス順序を動的に変更し、プログラム実行を高速化しています。
メモリアクセスはloadかstoreですから、依存関係の無い二つのメモリアドレスに関してload -> loadload -> storestore -> loadstore -> storeの4種類のどのアクセス順序を変更して良いか、というポリシーが各CPUで決められています。
x86は比較的メモリアクセス順序を守るほうなのですが、store -> loadに関してはその順序を入れ替えても良い(コア間で見え方が違っても良い)、というポリシーになっています。(そうでないx86のCPUもあります)
上記の例では、このリオーダリングが見事に現れました。
つまり、スレッド1とスレッド2が別コアで動いた時、それぞれのarg->a = 1arg->b = 1は互いに反映される前に、loadが先行され(1)、(2)が成立してしまったわけです。
コンパイラ同様、CPUによるメモリアクセスのリオーダリングを防ぐ方法もあり、asm volatile("mfence" ::: "memory");がこれに該当します。
この1行を以下の箇所に入れることで、期待通り1111の出力を防ぐことができます。

// mem.cの改良
void *t1_func(void *p)
{
...
    arg->a = 1;
    asm volatile("mfence" ::: "memory");
    if (arg->b == 0)
...
}

void *t2_func(void *p)
{
...
    arg->b = 1;
    asm volatile("mfence" ::: "memory");
    if (arg->a == 0)
...
}

CPUのメモリアクセスのリオーダリングなんて無い(プログラムからは順番どおりに見える)ほうが良いじゃないか!という気持ちはわかりますが、
異なるコア間、ましてやNUMAなどの異なるチップ感でメモリの見え方を完全に一致させるには、同期を行うコストが大きくなり、性能に与える影響も小さくありません。
中国の「神威・太湖之光」やpezy computingのプロセッサでは、CPUによるリオーダリングを自由にし、プログラマが必要な箇所のみで同期を行うことで、データ並列性の高いアプリケーションでの実行速度を上げているようです。

でRCUではなにやってんの?

かなり寄り道してしまった感もありますが、再び最初に見たコードを思い出してみましょう。

struct foo {
   int a;
   int b;
};

struct foo *foop = NULL;
struct foo new;

/*foop!=NULLで値を出力*/
void reader()
{
    int a, b;
    if (foop != NULL) {
        a = foop->a;
        b = foop->b;
        printk("Set. a = %d, b = %d\n", a, b);
    }
    return;
}

/*newを初期化しfoopにセット*/
void writer()
{
    new.a = 1;
    new.b = 1;
    foop = &new;
    return;
}

上記コードでは、参照時にfoop->afoop->bが1になっていない可能性がある、ということを冒頭で述べました。
x86のCPUを前提とした場合、どうすればこれを防げるか、というと、、、

struct foo {
   int a;
   int b;
};

struct foo *foop = NULL;
struct foo new;

/*foop!=NULLで値を出力*/
void reader()
{
    int a, b;
    if (foop != NULL) {
        a = foop->a;
        b = foop->b;
        printk("Set. a = %d, b = %d\n", a, b);
    }
    return;
}

/*newを初期化しfoopにセット*/
void writer()
{
    new.a = 1;   // (1)
    new.b = 1;   // (2)
    asm volatile("" ::: "memory");  //★
    foop = &new; // (3)
    return;
}

asm volatile("" ::: "memory");foop = &new;の前に入っただけです。
「え〜っ」って感じですが、x86に関してはこれだけで、上記コードは思った通りに動作します。
以下その理由です。
x86のCPUは、store -> storeのメモリアクセス順序は変更しません。 つまり、writer()(1), (2), (3)コンパイラによってメモリ順序の変更が起きない限り、意図通りに動くわけです。
そのため、asm volatile("" ::: "memory");を(1)、(2)と(3)の間に入れ、この間のコンパイラによるメモリ順序の変更を防いでいます。

そして、何を隠そうこれがRCUにおけるアトミックなポインタの更新と参照になるのです。
アーキテクチャが異なると実装も異なります。

/*注意!!!以下は正しい使い方ではありません!!!*/

void reader()
{
    struct foo *p;
    int a, b;

    p = rcu_dereference(foop);  //★
    if (p != NULL) {
        a = p->a;
        b = p->b;
        printk("Set. a = %d, b = %d\n", a, b);
    }
    return;
}

void writer()
{
    new.a = 1;
    new.b = 1;
    rcu_assign_pointer(foop, &new); //★
    return;
}

では、念の為嘘をついていないことを確認しましょう。
以下はv4.3のコードです。

rcu_assign_pointer

#define rcu_assign_pointer(p, v) smp_store_release(&p, RCU_INITIALIZER(v))

#define smp_store_release(p, v)                                         \
do {                                                                    \
        compiletime_assert_atomic_type(*p);                             \
        // コンパイラによるリオーダリングを禁止
        // #define barrier() __asm__ __volatile__("": : :"memory")
        barrier();                                                      \
        // 代入
        WRITE_ONCE(*p, v);                                              \
} while (0)

rcu_dereference

#define rcu_dereference(p) rcu_dereference_check(p, 0)

#define rcu_dereference_check(p, c) \
        __rcu_dereference_check((p), (c) || rcu_read_lock_held(), __rcu)

#define __rcu_dereference_check(p, c, space) \
({ \
        /* Dependency order vs. p above. */ \
        typeof(*p) *________p1 = (typeof(*p) *__force)lockless_dereference(p); \ //★
        RCU_LOCKDEP_WARN(!(c), "suspicious rcu_dereference_check() usage"); \
        rcu_dereference_sparse(p, space); \
        ((typeof(*p) __force __kernel *)(________p1)); \
})

#define lockless_dereference(p) \
({ \
        // 代入しているだけ
        typeof(p) _________p1 = READ_ONCE(p); \
        // x86の場合からっぽ
        smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
        (_________p1); \
})

(嘘を見つけた方はコメント頂けると大変助かります)

おわりに

もともとここはさらっと行こうと思ったのですが、考えてみたら、いつもコード書くときにメモリオーダリングとか全く意識しないなぁ、という感じだったので、自分の勉強がてら調べてみました。
今回はRCUというよりはプリミティブな部分の話でしたが、次回からはRCUっぽい話ができるかと思います。

RCU(Read Copy Update)をちゃんと知る(1)-2 実装よりの概要

はじめに

前回(http://tkokamo.hateblo.jp/entry/2017/05/31/213427)は、かなりざっくりとした理解だったのでもう少し実装に近づいた概要です。

(1) 概要(概要)← 前回と今回
(2) Linuxでの実装
(3) rcu-walk(RCUの応用先)

今回までで概要は終わらして、次回からは実際の実装を見ていこうと思っています。

RCUの種類

現在のLinuxには大きく以下のRCUの実装があるようです。(https://lwn.net/Articles/541037/)

参照クリティカルセクション内でブロック不可 ブロック可
SMP非対応 Tiny RCU Tiny Sleepable RCU
SMP対応 Tree RCU (これを理解したい) Tree Sleepable RCU

Sleepable RCU(SRCU)について


クリティカルセクション内で眠れるなんて、すばらしいじゃないか!と思いますが、実際はそんなに使われていません。 (4.13-rc3では、rcu_read_lock:875件、srcu_read_lock:57件)

SRCUの実装はよくわかっていませんが、参照クリティカルセクションでブロックが発生すると参照期間が当然伸びます。そして、これは古いデータが解放されるまでの時間(grace period)が伸びるということを意味します。
grace periodが長くなると、その間に複数世代のデータが作られメモリを圧迫してしまう危険があるので、好ましくありません。
SRCUについてはこれ以上深くはつっこみませんが、興味がある方はhttp://www.rdrop.com/~paulmck/RCU/srcu.2007.01.14a.pdfを見ると良いかと思います。(少し古いです)

Classic RCUとTree RCU


v2.6で当初実装されたRCUはClassic RCUと呼ばれていますが、CPU数が増えると更新側の性能がスケールしない、無駄に電力を使ってしまう、などといった問題がありました。(※CPU数が増えると、といっても数百とかいったレベルらしい)
これらの問題を解決したRCU実装がTree RCUで、現在はTree RCUが用いられています。
参考:http://www.atmarkit.co.jp/flinux/rensai/watch2009/watch04a.html RCUの全面書き直しも! 2.6.29は何が変わった?(1/2) − @IT

Tree RCU(とrcu walk)を理解するのが目的ですが、SMP環境におけるRCUの仕組みを知るには、まずはClassic RCUから見ると良いかと思うので、Classic RCUについて見ていってからTree RCUに手を伸ばそうと思います。(今回ではないです)

RCUのAPIと処理概要

以下に参照側と更新側が用いるRCUのAPIとgrace periodの関係などを表してみました。

f:id:tkokamo:20170812174518p:plain

参照側が呼び出す関数は以下の通りです。

関数 説明
rcu_read_lock() 参照側クリティカルセクションを開始する。実際はただプリエンプションを無効にするだけ
rcu_read_unlock() 参照側クリティカルセクションを終了する。実際はただプリエンプションを有効にするだけ
rcu_dereference() RCUで管理されているデータのポインタを参照する。

更新側が呼び出す関数は以下の通りです。

関数 説明
rcu_assign_pointer() RCUで管理されているデータのポインタを更新する。
call_rcu() 更新前の古いデータへの参照がなくなった時に呼ばれる回収用のコールバック関数を登録する。
synchronize_rcu() grace periodがすぎるまで待ち合わせる。古いLinuxではsynchronize_kernel()

上の図では、CPU0の更新者(update)がcall_rcu()を呼んだ時、参照側クリティカルセクション内にいるCPU2、CPU3の参照者(read)が参照側クリティカルセクションを抜けるまで、古いデータを保持しておく必要があります。
CPU1の2つ目の参照者はcall_rcu()後に参照を始めているため、最新の値を参照しています。そのため、このタスクが参照をやめるまで待つ必要はありません。

実際には、call_rcu()呼び出し後、全てのCPUについてcontext switchが起きたらcall_rcu()で登録されたコールバック関数を呼び出し、古いデータの回収を行うことができます。
最初は「?」となりましたが、以下のように少し整理すると、正しいことがわかります。
参照側クリティカルセクションではプリエンプションが禁止されており、この間にcontext switchが起きることはありません。
逆にいうと、context switchが起きたCPUは参照側クリティカルセクションにいないことが保証されます。
そのため、call_rcu()後、すべてのCPUでcontext switchが起きた時、古いデータの参照は終わっていると判断できるのです。

おわりに

前回と今回でRCUの大雑把な理解はできると思います。
間違いなどありましたら、指摘いただけると助かります。

次回からは、実際にRCUのAPIのコードを以下のような流れで見ていこうと思います。

  • rcu_dereference(), rcu_assign_pointer()
  • Classic RCUの回収処理など
  • Tree RCUの回収処理など

RCU(Read Copy Update)をちゃんと知る(1)-1 ほんとの概要

はじめに

ファイルシステムのrcu-walkを理解するためにRCUの勉強から始めようと思ったので書留ます。
RCUとはざっくりこんなものだ、と分かっている前提での記録です。
予想している流れとしては、

  • 概要(概要)← 今回
  • Linuxでの実装
  • rcu-walk(RCUの応用先)

と考えています。原稿も無いので、次回がいつになるかわかりません(社内勉強会でrcu-walkを語ろうと思っているので完遂はすると思われます)

今回は、wikipediaとかよんでで「?」となった当たりを捕捉。

RCUとは?

図を用いた簡単な理解

複数のタスクで共有するデータの参照/更新をきちんと行う場合、大抵は適切に排他区間をロックによって設けてそれを実現します。
理想的には、タスク間で共有するデータの参照/更新をロックフリーで行えるとよいのですが、一般的にそのようなことを実現する方法は考えられていません。
しかし、特定のデータ構造(※)の参照/更新については、ロックフリーでそれを行うことができます。
RCU(Read Copy Update)とはそのような手法です。

(※)リード・コピー・アップデート - Wikipedia によるとRCUの応用範囲も研究の対象らしいです。


では、RCUはどのようにロックフリーにデータの参照/更新を実現しているのか、ということを知るために以下の図を用いて考えてみます。

f:id:tkokamo:20170816144144p:plain

上図は単方向リストによって構築されているツリー構造を表しています。
(1)ノードAはノードBおよびノードCを指しています。
(2)Cの更新を行いたいタスクは、Cのコピーを作成しそれに対してデータの更新を行います。仮にCを参照中のタスクが他に存在していても、更新を行うタスクはコピー先に対して更新を行うため、参照中のタスクに対して中途半端な状態が見えることがありません。
(3)C'の更新が終わり他のタスクから参照されても問題ない状態になった時、AがもともとCを指していたポインタをC'を指すように更新します。逆に言うと、この時点でCはツリー構造から削除される(※)ことになります。
このため、データを参照するタスクは古いCか新しいC'を参照するのみで、中途半端な状態を参照することは起きません。ポインタから外されたCは参照者が居なくなった時点で解放(※)されます。
(※)リード・コピー・アップデート - Wikipedia には「削除と再利用のフェーズを分ける」とありますが、これは「removal and reclaim」の和訳が適切ではなく「削除と解放(回収)のフェーズを分ける」ということと理解しています。

日本語で詰まったところ

更新前の古いデータCは、Cを参照するタスクが居なくなった時点で解放(reclaim)されます。古いデータを参照するタスクは、新しいデータC'がツリーに追加された後(つまりremoval後)には新規に現れません。(removal後のタスクはC'を参照することになる。)
古いデータの解放タイミングを知るために参照側の把握が必要であり、これがRCUの参照側クリティカルセクションという概念に繋がっているのではないかと考えています。
仮にCを参照するタスクが長いことスリープしたりすると、古いデータがメモリ上にずっと残ってしまうことになります。この期間が長いと、その間にC'が更新されC'‘になり、世代が異るデータがメモリに置かれることとなり容量効率が悪いです。そのため、参照者はスリープやブロックをせず極力参照時間を短く抑える必要があります。
日本語訳で少し不明瞭だった言葉にgrace period(猶予期間)がありますが、これは古いデータCが削除後(AのポインタがC'に更新された後)に回収されるまでの期間を表しています。
参照時間を短くする努力というのは、すなわちgrace periodを短くする努力ということになります。

おわりに

概要ということでかなりざっくりと、主に自分がよくわからんと思ったところを書きとどめました。
次回からLinuxにおける実装を見てみようと思いますが、大体以下の部分を調べていきたいかと思います。

カーネルスタックがvmalloc領域になったことの確認

Linux 4.9からカーネルスタックにvmalloc領域が用いられるようになった。
v3.10系とv4.10系で以下のモジュールをロードしてみて、実際に確認してみた。
ディストリはCentOS7.2

stack_test.c

#include <linux/module.h>
#include <linux/kernel.h>

static int __init stack_test_module_init( void )
{
        int sp; 
        printk( KERN_INFO "int sp is @ %p\n", &sp );
        return 0;
}


static void __exit stack_test_module_exit( void )
{
}

module_init( stack_test_module_init );
module_exit( stack_test_module_exit );

MODULE_DESCRIPTION( "stack_test" );
MODULE_LICENSE( "GPL2" );

Makefile

obj-m := stack_test.o

ROOTDIR  := /usr/src/kernels/`uname -r`/
PWD   := $(shell pwd)

default:
    $(MAKE) -C $(ROOTDIR) M=$(PWD) modules

clean:
    rm -f *.o *.ko

上記コードをmakeして、ロードした結果それぞれ以下のメッセージが/var/log/messagesに出力される。

v3.10系

Mar 30 21:00:24 localhost kernel: int sp is @ ffff88018c22fd4c


v4.10系

Mar 30 20:37:21 localhost kernel: int sp is @ ffffc90003607c7c


x86_64のメモリマップは、LinuxのソースのDocumentation/x86/x86_64/mm.txtによると

Virtual memory map with 4 level page tables:

0000000000000000 - 00007fffffffffff (=47 bits) user space, different per mm
hole caused by [48:63] sign extension
ffff800000000000 - ffff87ffffffffff (=43 bits) guard hole, reserved for hypervisor
ffff880000000000 - ffffc7ffffffffff (=64 TB) direct mapping of all phys. memory ★v3.10系のスタックはここ
ffffc80000000000 - ffffc8ffffffffff (=40 bits) hole
ffffc90000000000 - ffffe8ffffffffff (=45 bits) vmalloc/ioremap space ★v4.10系のスタックはここ
ffffe90000000000 - ffffe9ffffffffff (=40 bits) hole
ffffea0000000000 - ffffeaffffffffff (=40 bits) virtual memory map (1TB)
... unused hole ... 
ffffec0000000000 - fffffc0000000000 (=44 bits) kasan shadow memory (16TB)
... unused hole ... 
ffffff0000000000 - ffffff7fffffffff (=39 bits) %esp fixup stacks
... unused hole ... 
ffffffef00000000 - ffffffff00000000 (=64 GB) EFI region mapping space
... unused hole ... 
ffffffff80000000 - ffffffffa0000000 (=512 MB)  kernel text mapping, from phys 0
ffffffffa0000000 - ffffffffff5fffff (=1526 MB) module mapping space
ffffffffff600000 - ffffffffffdfffff (=8 MB) vsyscalls
ffffffffffe00000 - ffffffffffffffff (=2 MB) unused hole

となり領域が異なることが分かる。

何がうれしいか?

v3.10系のカーネルスタックが置かれていた領域は開始アドレスの違いこそあれ、物理メモリがそのまま連続してマッピングされている。
この領域の良い点の1つは、メモリ割り当て/解放の速度が高速であることである。(仮想アドレスに対応する物理アドレスが予めわかっているため、ページテーブルの設定やTLBのフラッシュが必要ない)
一方で、物理的に連続したメモリを確保出来無い時はメモリ割り当てが失敗してしまうなどの欠点も存在する。

従来のカーネルでは、カーネルスタックとしてこの領域を用いており、各タスクに対し一定(最近は16KiBになったっぽい)のスタックを割り当てていた。
恐らく、カーネルの開発者はカーネルスタックを食い尽くさないように身長にコードを設計する必要があった。
というよりは、必要となるデータ構造のメモリ領域をスラブを用いてプールしておいたり、動的に確保することでスタックを食い尽すことを回避していたのだろう。

一方、v4.10系のカーネルスタックが置かれているvmalloc領域は、物理メモリが非連続的に仮想アドレスにマッピングされている。
非連続的なマッピングであるため、物理連続なメモリを確保できないからと言って、メモリ割り当てが失敗することはない。(基本的には)
しかし、割り当て/解放のたびにページテーブルをいじったりするので、vmalloc領域のメモリ確保/解放は遅い。(頻繁に呼ばれる処理で毎回この領域の獲得/解放を行うのはやめなければならない)
この領域をカーネルスタックに用いた場合、v3.10まで存在したスタックの限界というものが、かなり緩和されることとなる。
カーネル開発者は、スタックの枯渇に神経質になることもなく、また割り込みがネストしてしまいスタックを食い尽すという心配から解放されるようだ。
※7/1 勘違いでした。

おわりに

思い立って10分ほどで記事を書いたので、大分大雑把な説明になってしまっている。
今後は、v4.9以降スタックオーバーフローが起きたときにどう回復しているのかなど、もう少し見ていきたい。

7/1 追記

Ubuntuではカーネルアドレス空間のレイアウトを少しいじっていることが分かった。 → カーネル空間のASLR的なものっぽい。

CentOS 7.2は上で示したレイアウトどおりっぽい

Jul  1 19:30:19 localhost kernel: vmalloc_start = ffffc90000000000 # VMALLOC_START
Jul  1 19:30:19 localhost kernel: vmalloc_end = ffffe8ffffffffff # VMALLOC_END
Jul  1 19:30:19 localhost kernel: page_offset = ffff880000000000 # PAGE_OFFSET ストレートマップの開始

Ubuntu 17.04は微妙に異なる。

Jul  1 19:27:49 ubuntu kernel: [22205.401374] vmalloc_start = ffffb58cc0000000 # VMALLOC_START
Jul  1 19:27:49 ubuntu kernel: [22205.401375] vmalloc_end = ffffd58cbfffffff # VMALLOC_END
Jul  1 19:27:49 ubuntu kernel: [22205.401376] page_offset = ffff892280000000 # PAGE_OFFSET

### 再起動後、変わっている。
Jul  1 20:08:18 ubuntu kernel: [   45.508327] vmalloc_start = ffffb6a340000000
Jul  1 20:08:18 ubuntu kernel: [   45.508328] vmalloc_end = ffffd6a33fffffff
Jul  1 20:08:18 ubuntu kernel: [   45.508328] page_offset = ffff9cc740000000

カーネルスタックのオーバーフローによる権限昇格とかが問題になることがしばしばあるので、ASLRで防ぐっていうのりですかね。 参考:

Kernel address space layout randomization [LWN.net]

1の位が5の自然数の2乗の計算方法

25×25 = 625は以下のように計算する

20×30 = 600
+
5×5 = 25

→625

もっと大きくても同様で

215×215

210×220 = 46100
+
5×5 = 25

→46125

数式的に成り立つのか確認してないけど、試したものは全部うまくいってるからいけるんだろう。

算数の先生になったわけではありません。過去の稚拙なvirtioの記事でも多少ニーズがあるようなので時間ができたらコンピュータのことかきたいです。

3辺が整数の直角三角形を無限に見つける方法

ピタゴラスの定理的にも成り立つので、どこかにのっているだろうけど、自分では見つけられなかったので記録。
小学校とかで直角三角形を沢山見つけろと言われたら参考にしてください。


ピタゴラスの定理ってのは、直角三角形の斜辺がc、一番短い辺がa、次に短い辺がbだとすると、

a×a + b×b = c×c

がなりたつよ〜ということだったはず。
この定理からa、b、c全部が整数となる組を見付けるのは少し大変そうなんだけど、aは奇数、かつb = c - 1と仮定してみて、

a×a = b + c

となるa、b、cの整数の組を見つけてみると、それはピタゴラスの定理を満す。(逆がそうかはちゃんと考えていません)


以下に例を列挙します。

3×3 = 4 + 5
5×5 = 12 + 13
7×7 = 24 + 25
9×9 = 40 + 41
...

こんな幹事

Xen on KVM (1)

KVMの上でXen(HVM)を動かそうとした時になかなか、解決方法がわからなかったので記録しておく。

とは言っても、まだXenの上でDom Uは動かして無いんですが、、、。

Dom 0が動くまでの道のりは以下の通り

動作環境はホストがUbuntu 14.04、ゲストがUbuntu 12.04

  1. Linuxの/etc/modprobe.d/qemu-system-x86.confを編集し、ネステッドEPTを行う設定にする
  2. virt-managerから(あるいはVMxmlをいじる)、仮想CPUの設定をホストと一緒にする
  3. VMを作り、その上でXenのビルド、インストールを行う。
  4. Xen がエラーを起こして起動しないので、仮想CPUの設定変更
  5. Xenは動いたがDom0のロード中にloop modules loadedでとまるので、virtioを用いないようにするに変更する

これでDom0の起動までは行えた。大変だったのは4, 5に気付くまで、、、。

1. /etc/modprobe.d/qemu-system-x86.confの編集

ハイパーバイザの上までは、通常ハードウェアによる仮想化支援が届かない。これを有効にするために以下のように編集する。

#echo 'options kvm_intel nested=1' > /etc/modprobe.d/qemu-system-x86.conf

qemu-system-x86.confはUbuntuでのファイルでcentOSなどはkvm.confを編集。

2. VMのCPUの設定をホストと一緒にする。

virt-managerを起動し 起動するVMを開き、メニューから[view]>[Details]を選び、ProcessorのConfiguration項目のModelを自分の物理マシンのCPUにし、Copy host CPU configutationをクリックすることで、VMのCPUの設定をホストと同じにできる。

3. Xenのビルドとか

aptで入れても、コンパイルしていれてもおk

4. VMのCPU設定でx2apicをdisableにする

さぁ、起動とおもって動かしたら起動しない。。。色々調べたら、2.でも触れたConfigurationのでx2apicが有効になっていることが問題らしい。x2apicをdisableにすることで解決。
x2apicはNehalemから採用された割り込みコントローラらしい。有効だとなぜ動かなくなるのか謎、、、だがとりあえず解決したので気にしない。

ここまでは調べて出てきた。

5. Dom0のロード中にloop modules loadedでとまる

いつもののりでvirtio、virtio、、、と無意識に設定してたのが落とし穴だった。良く考えたらxenに準仮想化のフロントエンドドライバなんてないの当たり前。ということで、すべてvirtioを用いない設定にすることで解決。
めでたしめでたし



とりあえず、まだ起動してログインができただけの段階なので色々頑張っていきたい。