Linuxカーネルに関する独自コードをメンテナンスするコスト
はじめに
Linuxカーネル(以下カーネル)に機能を追加する、あるいはバグを修正する自作コードには次の2つの種類があります。
これらの変更を長期間メンテナンスするには次の方法があります。
- Linux開発コミュニティに働きかけて独自コードを公式のmainlineと呼ばれるツリーにコードをマージする
- 独自コードを自分自身で管理して、mainlineカーネルの新バージョンが出るたびに追従する(後述)
本記事は前者の方法に比べて後者の方法をとった場合に必要なメンテナンスコストについて述べます。本記事の表題にはlinuxと書いていますが、linuxと似たようなドラスティックな変更(後述)を是とするソフトウェアすべてに当てはまる話なのでlinuxの開発には関係ないかたにも役立つ話かと思います。
独自カーネルモジュールを作る場合の追従コスト
昨日書いたエントリで述べたように、カーネルは外部インターフェース(ユーザ空間とのインターフェース)は基本的には変えませんが、内部インターフェースは変わることがままあります。インターフェースを変更するときはmainlineにマージされれているコードについては、インターフェースを変更した人やサブシステムメンテナなど1が責任を持って新しいインターフェースに置き換えます。
このときmainlineにマージされていないコードに対する配慮はありません。したがって、ある時点のカーネルバージョンに対応する独自カーネルモジュールを作っており、それが問題なくビルドできていたとしても、そのモジュールが使っているインターフェースがその後に変更された場合、それはビルドできなくなります。このため独自カーネルモジュールを新しいバージョンに追従するためのコストがかかります。さらに独自モジュールのコード量は時を経るほど増えていくので、一回の追従に必要なコストは増える一方です。
複数バージョンに対してモジュールをメンテナンスしなければいけない場合は、古いバージョンのモジュールに対して新しいバージョンの変更をバックポートしないといけないので、どんどん追従が困難になっていきます。
これを続けると、自作コードの量(ここではパッチの数)が増えるにつれて、および、追従すべきカーネルの数が増えるごとに追従コストが爆発的に増えていくことがわかっていただけると思います。
カーネル本体を変更する場合の追従コスト
カーネル本体を変更する場合は前節において説明した独自カーネルモジュールのメンテナンスにかかるコストに加えて、別のコストもかかります。カーネル内インターフェースが変わらなくても、関数内の処理論理が書き換えられることがあります。このときは既存カーネルに対する変更を新しい処理論理に合わせて変更する必要があります*1。
複数のmainlineカーネルバージョンに対して変更部分を管理しなくていけない場合、上記のコストに加えて、古いバージョンに対して新しいカーネルに入っている重大バグの修正パッチもバックポートし続ける必要があります。これらの修正はパッチ数でいうと1バージョンごとに数百、数千個にも及びますので、大量の人的資源が無いと現実的ではありません。
バックポートのコストはstableカーネルというものを使えば減らせます。linuxには各バージョンのmainlineカーネルに対して、より新しいカーネルからの重大なバグ修正パッチをバックポートしたstableカーネルがしばらくの間提供されます。これを利用すれば、古いカーネルについては新しいstableカーネルが出るたびに、その上に独自コードのパッチを(必要であれば変更した上で)当てたものを使えば、相当バックポートコストが減らせます((stableカーネルに似たような長期間サポートされるカーネルは他にも色々ありますが、それらについての説明は省略します)。ただしそれもstableカーネルが出る期間が終わるまでです。それ以降は自分でなんとかする必要があります。
上記の図の中では、見やすさのために新しいカーネルからのバックポートのためのコード量を少な目に表現していますが、実際には独自コードよりもはるかに大きいことにご注意ください。
バックポートコストを減らすためには、stableカーネル以外にも、ある時点でのstableカーネルをもとにディストリビューション独自の変更をしたディストリビューションカーネルをベースにするという方法もあります。ただしここで一点注意があります。ディストリビューションが提供するカーネルは独自パッチを当てるとサポート対象にならなくなります。商用ディストリビューションのサポートを受けているかたは、独自コードを使いたければmainlineに取り込んだ上でディストリビュータに取り込み依頼をしなければなりません。
mainlineにマージすべきか否か
これまでの記述によって「では必ずmainlineにマージすべきなの？」と思うかもしれませんが、必ずしもそうとも限りません。前述の追従コストに比べてmainline化のコストが高くなるような場合は、あえて独自管理をすることもありえます。その他にも、コードを一般公開したくないなどの理由によってmainline化をしない選択をする場合もあります。
おわりに
本記事で書いたことは一度体験してみないとなかなかわからないため、これまでに様々な組織が独自管理を選択した後に収集がつかない状態になった結果、独自コードのmainline化を基本方針にするようになりました。本記事を読むことによって、みなさまが先人達の轍を踏むことなく独自コードの将来的な管理コストについて学んでいただければ幸いです。
-
サブシステムメンテナがみなさん自身なら自分で書き換えなければいけないこともありますが…↩
*1:場合によっては当該パッチが不要になることもあります
Linuxのプロセススケジューラから見たSocionext SC2A11
はじめに
本記事はSocionext SC2A11のキャッシュメモリ構成の続きです。今回はLinuxのプロセススケジューラにはこのCPUがどのように見えているかについて調べました。
まずは前提知識としてLinuxカーネルのプロセススケジューラに存在するロードバランサという機能について説明します。その後に、ロードバランサからSC2A11がどのように見えているのかについて記載します。
ロードバランサ
システムに複数の論理CPU(1つのコア、あるいはSMT(1)が有効なら1つのスレッド)が存在する場合、Linuxのプロセススケジューラの中のロードバランサという機能がそれぞれの論理CPU上のプロセス数を平均化しようとします2。
たとえば1ソケット4コア、つまり4論理CPUのシステムにおいて実行可能プロセスが4つ存在する場合、1つの論理CPUに4つのプロセスが偏るようなことはなく、それぞれの論理CPUにプロセスが1つづつ割り振られます。一時的にそのようなことになる可能性はありますが、すぐに解消されます。
ロードバランサが単純に全論理CPUを平等に扱って負荷分散すると問題が発生します。たとえば2コア2プロセスの4論理CPUシステムについて考えてみましょう。論理CPU0,1と2と3がそれぞれ同じコア内の2スレッドとします。このとき実行可能プロセスが2つあるとすると、論理CPU0と1にプロセスが割り振られて、2と3がアイドルという状況が考えられます。
ペアになっているスレッドはほとんどのハードウェア資源を共有するため、現実的なワークロードの場合、2つのスレッド上に両方プロセスが動作している場合の性能は片方のスレッドにだけプロセスが存在する場合の高々1.5倍程度です。したがって、この場合は論理CPU0と1のいずれかに1つのプロセスを、論理CPU1と2のいずれかに1つのプロセスを割り振るほうがCPU資源を有効に使えます。
ロードバランサはCPU資源を有効に使うためにハードウェアから与えられた情報をもとにして論理CPUの階層構造を作り出し、上の階層から下の階層に順番に負荷分散します。それぞれの階層のことをスケジューラドメインと呼びます。たとえば前述の2コア2スレッドのシステムの場合は
という処理論理になっています。スケジューラドメインの階層構造は/proc/schedstatを見ればわかります。詳細については次節において述べます。
SC2A11の場合
SC2A11の/proc/schedstatの中身は次のようになっていました。
$ cat /proc/schedstat cpu0 0 0 0 0 0 0 40778266780070 212490834550 257123 domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu1 0 0 0 0 0 0 6518877752440 6168684830 155606 domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu2 0 0 0 0 0 0 2042515035170 7070977990 189374 domain0 00000c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu22 0 0 0 0 0 0 777618304410 8670056290 155964 domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu23 0 0 0 0 0 0 803551513420 8844408870 165495 domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 $
ここでは論理CPUごとに自身が属するスケジューラドメインについての情報が出力されます。各ドメインはdomain<階層番号>で表現されます。階層番号が大きいほど上の階層であることを示します。domain
上記の出力によって次のことがわかります。
続いてこの階層はどこから得られたものなのかを調査しました。arm64アーキテクチャにおけるスケジューラドメインの階層構造は最大3階層です。
この階層構造を作っているのがarch/arm64/kernel/topology.c内のコードです。ここで作成した情報は/sys/firmware/devicetree/base/cpus/cpu-map以下を見ればわかります。SC2A11の場合はcpu-mapディレクトリの下に12個のcluster<クラスタ番号>ファイル、そのまた下にcore<クラスタ内のコア番号>というディレクトリが存在します。つまりSC2A11は24個のコアが2個づつのコアから成る12個のクラスタによって構成されていることがわかりました。ちなみに1つのクラスタを構成する2つのコアは前回の記事においてL2キャッシュを共有していることがわかっています。
なお、このマシンは該当しませんが、SMT機能があるCPUの場合はcore
おわりに
次の記事はSocionext SC0FQAA-BはNUMAか否かです。
Socionext SC2A11のキャッシュメモリ構成の推測
はじめに
本記事はARM v8 アーキテクチャのネイティブな開発環境を提供するSC0FQAA-Bに搭載されているSocionext SC2A11 (24コア)のキャッシュメモリがそれぞれどのコア間で共有されているかを調べた結果をまとめた記事です。
なぜそんなことをしたかというと、SC2A11のカタログにはL1dが32KB, L2が256KB, L3が4MBということは書いてあったのですが、それぞれの共有関係については記載がなかったからです。公式サイトからたどれるその他ドキュメントにも同様に記載がありませんでした。
資料請求のフォームがあったのでそこから仕様書をもらって確認するという方法がありましたが
- 個人ユーザが「キャッシュメモリの情報を知りたかったから」という理由で資料をもらえる気がしない
- できたとしても面倒そうだし、時間もかかりそう
という理由により、実験によって情報を得ることにしました。
ちなみに実験に使ったマシンは自分で買ったわけではなく、東大PFLabが買ったもの同研究室のご厚意によって借りたものです。某SNSでこのキャッシュの疑問についてブツブツつぶやいていたら、PFLabでこのマシンをセットアップしたlivaさんがよきに計らってくれました。livaさんとPFLabには厚く御礼申し上げます。
調査結果
キャッシュメモリは恐らく次のような構成になっていることがわかりました。
| 名前 | 合計サイズ[KB] | 共有関係 | サイズ/コア[KB] |
|---|---|---|---|
| L1d | 32 | 全コア独立 | 32 |
| L2 | 256 | 2コアごとに共有 | 128 |
| l3 | 4096 | 全コアで共有 | 約170 |
(2018/3/16追記) 数日前、このマシン用のDevice Treeにキャッシュメモリ構成に関する情報を追加するパッチが投稿されていることをMasami Hiramatsuさんに教えていただきました。パッチの内容によると筆者の推測は正しかったようです。なお、このパッチはすでにマージされたので、いずれファームウェアのバージョンアップによってキャッシュメモリの情報が正しくlinuxから取得できるようになりそうです。
sysfsからの情報採取
カーネルが初期化時にハードウェアからキャッシュメモリの構成を得ている場合は/sys/devices/system/cpu/cpu
dmesgを見たところ、起動中に次のようなメッセージが出力されていました。
# dmesg ... [ 2.582856] cacheinfo: Unable to detect cache hierarchy for CPU 0 ...
これはlinuxカーネルのソースコードでいうと以下の部分に該当します。
...
static int detect_cache_attributes(unsigned int cpu)
{
int ret;
if (init_cache_level(cpu) || !cache_leaves(cpu))
return -ENOENT;
per_cpu_cacheinfo(cpu) = kcalloc(cache_leaves(cpu),
sizeof(struct cacheinfo), GFP_KERNEL);
if (per_cpu_cacheinfo(cpu) == NULL)
return -ENOMEM;
ret = populate_cache_leaves(cpu);
if (ret)
goto free_ci;
/* * For systems using DT for cache hierarchy, of_node and shared_cpu_map * will be set up here only if they are not populated already */
ret = cache_shared_cpu_map_setup(cpu);
if (ret) {
pr_warn("Unable to detect cache hierarchy for CPU %d\n", cpu); ... ★
goto free_ci;
}
cache_override_properties(cpu);
return 0;
free_ci:
free_cache_attributes(cpu);
return ret;
}
...
どうやらcache_shared_cpu_map_setup()が失敗したようです。この原因が次のうちどれなのかはわかっていません。
- 全アーキテクチャ共有コード(drivers/base/cacheinfo.cあたり)
- arm64のコード(arch/arm64/kernel/cacheinfo.cあたり)
- このマシン用のDevice Tree(/sys/firmware/devicetree以下にマップされている)
- その他
ここでこれ以上深堀りはしたくなかったので、次に示す実験によるアプローチによってキャッシュメモリ構成を推測することにしました。
実験
実験のコンセプトは次の通りです。
- コア0上で所定サイズのバッファにアクセスし続けるプログラム(memory_loadプログラム)を動かす
- コア0~23のいずれかの上で、所定サイズのバッファ(memory_loadプログラムのものとは別)に所定の回数アクセスすることによってアクセス速度を計測するプログラム(cacheプログラム)を動かす
- memory_loadプログラムのバッファサイズを(a) L1よりやや小さな値(30[KB])、(b) L2よりやや小さな値(500[KB])、(c) L3 よりやや小さな値(4000[KB])にする。これによって次のことが言える
- a) cacheプログラムのバッファサイズL1以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL1キャッシュを共有している
- b) 同バッファサイズがL2以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL2キャッシュを共有している
- c) 同バッファサイズがL3以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL3キャッシュを共有している
2つのプログラムのソースを示します。
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define CACHE_LINE_SIZE 64
int main(int argc, char *argv[])
{
char *progname;
progname = argv[0];
if (argc != 2) {
fprintf(stderr, "usage: %s <size[KB]>\n", progname);
exit(EXIT_FAILURE);
}
register int size;
size = atoi(argv[1]) * 1024;
if (!size) {
fprintf(stderr, "size should be >= 1: %d\n", size);
exit(EXIT_FAILURE);
}
char *buffer;
buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (buffer == (void *) -1)
err(EXIT_FAILURE, "mmap() failed");
struct timespec before, after;
clock_gettime(CLOCK_MONOTONIC, &before);
int i;
for (;;) {
long j;
for (j = 0; j < size; j += CACHE_LINE_SIZE)
buffer[j] = 0;
}
if (munmap(buffer, size) == -1)
err(EXIT_FAILURE, "munmap() failed");
exit(EXIT_SUCCESS);
}
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define CACHE_LINE_SIZE 64
#define NLOOP (64*1024*1024)
#define NSECS_PER_SEC 1000000000UL
static inline long diff_nsec(struct timespec before, struct timespec after)
{
return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
- (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));
}
int main(int argc, char *argv[])
{
char *progname;
progname = argv[0];
if (argc != 2) {
fprintf(stderr, "usage: %s <size[KB]>\n", progname);
exit(EXIT_FAILURE);
}
register int size;
size = atoi(argv[1]) * 1024;
if (!size) {
fprintf(stderr, "size should be >= 1: %d\n", size);
exit(EXIT_FAILURE);
}
char *buffer;
buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (buffer == (void *) -1)
err(EXIT_FAILURE, "mmap() failed");
struct timespec before, after;
clock_gettime(CLOCK_MONOTONIC, &before);
int i;
for (i = 0; i < NLOOP / (size / CACHE_LINE_SIZE); i++) {
long j;
for (j = 0; j < size; j += CACHE_LINE_SIZE)
buffer[j] = 0;
}
clock_gettime(CLOCK_MONOTONIC, &after);
printf("%f\n", (double)diff_nsec(before, after) / NLOOP);
if (munmap(buffer, size) == -1)
err(EXIT_FAILURE, "munmap() failed");
exit(EXIT_SUCCESS);
}
それぞれ次のようにビルドします。
$ cc -O3 -o memory_load memory_load.c $ cc -O3 -o cache cache.c
memory_loadプログラムを所定のCPU上で動かすときは次のようにします。
$ taskset -c <CPU番号> ./memory_load <バッファサイズ [KB]>
cacheプログラムを所定のCPU上で動かすときは次のようにします。
$ taskset -c <CPU番号> ./cache <バッファサイズ [KB]>
リファレンスとなるデータの採取
まずはすべてのデータの比較対象となる、負荷をまったくかけない状態の性能を計りました。その結果を以下に示します。
$ for i in 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 ; do taskset -c 0 ./cache $i ; done 0.494395338 0.4878244995 0.7931622984 0.849168839 0.8938277609 0.9555984775 1.041136652 1.064321914 1.069313969 1.158684927 1.505872599 1.577874511 $
コマンド実行結果の数値の単位はナノ秒です。これをグラフにすると次のようになります。x軸もy軸も対数なので見かたに注意してください。
おおよそL1(25 [KB]), L2(28 [KB]), L3(212 [KB])を境界として性能が悪くなってゆくことがわかります。
実験結果
L1の共有範囲
memory_loadのバッファサイズがL1よりやや小さな値(30KB)場合のデータをもとにしたグラフを以下に示します。
memory_loadプログラムとcacheプログラムを同じコア(コア0)上で動かした場合のみ性能が悪く、その他は同程度の性能となりました。ごちゃごちゃしていて見づらいので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
というデータのみを抽出したグラフを以下に示します。
コア0上でmemory_loadプログラムによってL1キャッシュをほとんど使っても他のコアにおける性能がほぼ変わらないことから、コア0とコア1~23はキャッシュを共有していないことがわかりました。
なお、cacheプログラムをコア0上で動かした場合の性能が悪いのは、2つのプログラムがCPU時間を分け合っているせいでしょう。
L2の共有範囲
memory_loadのバッファサイズがL2よりやや小さな値(500KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
- 同、コア2上で動かした場合
というデータのみを抽出しています。
cacheプログラムをコア1上で動かした場合にバッファサイズがL1のサイズ~L2のサイズあたりで性能劣化していることから、コア0とコア1はL2キャッシュを共有していると考えられます。
L3の共有範囲
memory_loadのバッファサイズがL3よりやや小さな値(4000 KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
- 同、コア2上で動かした場合
というデータのみを抽出しています。
cacheプログラムをコア2上で動かした場合にバッファサイズがL2のサイズ~L3のサイズあたりで性能劣化していることから、コア0とコア2(および3~23)はL3キャッシュを共有していると考えられます。
おわりに
今後も本マシンの色々なデータをとっていきたいと思います。バッファサイズをL3のサイズを超える16MBにしてmemory_loadプログラムを動かしたところ、コア0とL2を共有するコア1上でcacheプログラムを動かした場合の性能が上がったという謎現象(L2を共有していないかのような振舞いをする)が発生しました。
これが気になっているので最初に調査するかもしれませんし、気が変わってI/O性能測定などの全然違うことをするかもしれません。
(2018/3/13追記) 結局はさらに気が変わってSC2A11がプロセススケジューラからどう見えるかという観点で調査しました。
ソートの計算量と現実のプログラム
ソートアルゴリズムについての小ネタ。「ソートは迷わずクイックソート」と言われることがよくありますが1、場合によってはそれが最適ではないこともあるという話。ここではクイックソートと挿入ソートを比較します。
O-記法で書くとクイックソートの平均計算量はO(n*log(n))で、単純な挿入ソートのそれはO(n^2)なので、見かけ上は前者のほうが速そうなのです。ただし、あくまでこの記法はnが無限に近づいたときの振舞いについて述べているだけなので、現実的なプログラムでは必ずしもクイックソートのほうが速いというわけではないです。
次のような仕様のプログラムで実際に両者の速度を比較してみましょう。
この仕様を実装したのが以下のsortプログラムです。
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define NSECS_PER_MSEC 1000000UL
#define NSECS_PER_SEC 1000000000UL
static void insertion_sort(int *a, int len)
{
int i, tmp;
for (i = 1; i < len; i++) {
tmp = a[i];
if (a[i - 1] > tmp) {
int j;
j = i;
do {
a[j] = a[j - 1];
j--;
} while (j > 0 && a[j - 1] > tmp);
a[j] = tmp;
}
}
}
static inline long diff_nsec(struct timespec before, struct timespec after)
{
return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
- (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));
}
static void prepare_data(int *a, int len)
{
int i;
for (i = 0; i < len; i++)
a[i] = rand();
}
static int comp(const void *a, const void *b)
{
return *((int *)a) - *((int *)b);
}
static char *progname;
int main(int argc, char *argv[])
{
progname = argv[0];
if (argc < 3) {
fprintf(stderr, "usage: %s <len> <i|q>\n", progname);
exit(EXIT_FAILURE);
}
int len = atoi(argv[1]);
char type = argv[2][0];
if (!((type == 'i') || (type == 'q'))) {
fprintf(stderr, "%s: type should be 'i or q'\n", progname);
exit(EXIT_FAILURE);
}
int *a;
a = malloc(len * sizeof(int));
prepare_data(a, len);
struct timespec before, after;
if (type == 'i') {
clock_gettime(CLOCK_MONOTONIC, &before);
insertion_sort(a, len);
clock_gettime(CLOCK_MONOTONIC, &after);
} else {
clock_gettime(CLOCK_MONOTONIC, &before);
qsort(a, len, sizeof(int), comp);
clock_gettime(CLOCK_MONOTONIC, &after);
}
printf("%lu\n", diff_nsec(before, after));
exit(EXIT_SUCCESS);
}
ビルド方法は次の通り。
$ CFLAGS=-O3 make sort $
このプログラムを次のようなパラメタを使って実行しました。
| パラメタ | 値 |
|---|---|
| 第一引数(len) | 20, 1, 2, ..., 15 |
| 第二引数(type) | i, q |
結果を以下のグラフにプロットしました。x軸は2len、y軸はlog(所要時間)なのに注意してください。
lenが大きくなっていくと確かにクイックソートのほうが速くなってゆき、その差は大きくなるばかりです。しかしlenが小さいとき、ここでは2^8(=128)あたりまでは挿入ソートのほうが速いことがわかります。これはクイックソートのほうが挿入ソートに比べて複雑な処理をしているためです。したがって、通常はクイックソートを使っていれば悪いようにはなりませんが、プログラムをカリカリにチューニングしたいとき、かつ、lenがそれほど大きくならないとわかっているときは挿入ソートを使って高速化に挑戦してみるのも一つの手です。ただし、「早すぎる最適化」という言葉にもある通り、最初からこの手の細かいチューニングをする必要はないでしょう。
最後に一点。上記のような理由もあって、本記事で作成したプログラムでも使っているglibcのqsort()関数は、ある程度小さなlen(<=MAX_THRESH)に対しては内部的に挿入ソートを使っています。他にもこのような実装になっている実装は山ほどあります。興味のあるかたは色々なクイックソートの実装を見てみるとよいでしょう。
カーネルモジュール作成によるlinuxカーネル開発入門 - 第五回 排他制御
前回作成したスタックは、手元の端末でみなさんが対話的に操作しているうちは何も問題が起きません。しかし、このスタックを複数の処理が同時に操作した場合は問題が発生します。今回は、前回作成したスタックにどのような問題が存在しているのか、および、それを排他制御という仕組みによって解決する方法について述べます。
まずは今回用いるスタック作成モジュール用のソースを次に示します。前回作成したlist2.cのものに加えて、スタックのサイズを最大10に制限しています。
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>
MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");
struct mystack_entry {
struct list_head list;
int n;
};
#define MYSTACK_MAX_LEN 10
static LIST_HEAD(mystack);
static int mystack_len;
static void mystack_push(int n) {
struct mystack_entry *e;
if (mystack_len >= MYSTACK_MAX_LEN) {
return;
}
e = kmalloc(sizeof(*e), GFP_KERNEL);
INIT_LIST_HEAD(&e->list);
e->n = n;
list_add(&e->list, &mystack);
++mystack_len;
}
static int mystack_pop(int *np) {
struct mystack_entry *e;
if (list_empty(&mystack)) {
return -1;
}
e = list_first_entry(&mystack, struct mystack_entry, list);
if (np != NULL)
*np = e->n;
list_del(&e->list);
--mystack_len;
kfree(e);
return 0;
}
static void mystack_clean_out(void) {
while (!list_empty(&mystack)) {
mystack_pop(NULL);
--mystack_len;
}
}
static struct dentry *mylist_dir;
static struct dentry *showfile;
static struct dentry *pushfile;
static struct dentry *popfile;
static char testbuf[1024];
static ssize_t show_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
char *bufp = testbuf;
size_t remain = sizeof(testbuf);
struct mystack_entry *e;
size_t l;
ssize_t ret;
if (list_empty(&mystack)) {
ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
return ret;
}
list_for_each_entry(e, &mystack, list) {
int n;
n = snprintf(bufp, remain, "%d ", e->n);
if (n == 0)
break;
bufp += n;
remain -= n;
}
l = strlen(testbuf);
testbuf[l - 1] = '\n';
ret = simple_read_from_buffer(buf, len, ppos, testbuf, l);
return ret;
}
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
ssize_t ret;
int n;
ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
if (ret < 0)
return ret;
sscanf(testbuf, "%20d", &n);
mystack_push(n);
return ret;
}
static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
int n;
ssize_t ret;
if (*ppos || mystack_pop(&n) == -1) {
return 0;
}
snprintf(testbuf, sizeof(testbuf), "%d\n", n);
ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
return ret;
}
static struct file_operations show_fops = {
.owner = THIS_MODULE,
.read = show_read,
};
static struct file_operations push_fops = {
.owner = THIS_MODULE,
.write = push_write,
};
static struct file_operations pop_fops = {
.owner = THIS_MODULE,
.read = pop_read,
};
static int mymodule_init(void)
{
mylist_dir = debugfs_create_dir("mystack", NULL);
if (!mylist_dir)
return -ENOMEM;
showfile = debugfs_create_file("show", 0400, mylist_dir, NULL, &show_fops);
if (!showfile)
goto fail;
pushfile = debugfs_create_file("push", 0200, mylist_dir, NULL, &push_fops);
if (!pushfile)
goto fail;
popfile = debugfs_create_file("pop", 0400, mylist_dir, NULL, &pop_fops);
if (!popfile)
goto fail;
return 0;
fail:
debugfs_remove_recursive(mylist_dir);
return -ENOMEM;
}
static void mymodule_exit(void)
{
debugfs_remove_recursive(mylist_dir);
mystack_clean_out();
}
module_init(mymodule_init);
module_exit(mymodule_exit);
次に示すのは、大量のプロセスが同時に、かつ適当にスタックを操作するという拷問プログラムです。
#!/bin/bash
TOPDIR=/sys/kernel/debug/mystack
for ((i=0;j<10000;j++)) ; do
echo 0 >${TOPDIR}/push &
cat ${TOPDIR}/show >/dev/null &
cat ${TOPDIR}/pop >/dev/null &
done
別の端末上でVMのシリアルコンソールに接続します。
shell-session: $ virsh console elkdat_ktest Connected to domain elkdat_ktest Escape character is ^] Ubuntu 16.04.1 LTS packer-qemu ttyS0 packer-qemu login:
lock1.koをロードした状態で、拷問プログラムを動作させます。
... root@packer-qemu:/home/vagrant# insmod /vagrant/list2.ko root@packer-qemu:/home/vagrant# /vagrant/lock-torture root@packer-qemu:/home/vagrant# ...
このとき次のようなメッセージがシリアルコンソール上に大量に表示されます。
... [ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010 [ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1] [ 2186.662618] PGD 1cce9067 [ 2186.662958] PUD 1cce8067 PMD 0 [ 2186.663438] [ 2186.663643] Oops: 0000 [#1] SMP [ 2186.664082] Modules linked in: lock1(O) crct10dif_pclmul crc32_pclmul ppdev aesni_intel aes_x86_64 glue_helper lrw gf128mul ablk_helper cryptd input_leds joydev serio_raw parport_pc parport mac_hid i2c_piix4 sunrpc autofs4 cirrus drm_kms_helper syscopyarea sysfillrect sysimgblt fb_sys_fops psmouse floppy ttm drm pata_acpi [last unloaded: lock1] [ 2186.668308] CPU: 1 PID: 7243 Comm: cat Tainted: G O 4.9.0-ktest #1 [ 2186.669215] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Ubuntu-1.8.2-1ubuntu1 04/01/2014 [ 2186.670379] task: ffff8d3dd7c563c0 task.stack: ffffa0f3c1534000 [ 2186.671118] RIP: 0010:[<ffffffffc02910d5>] [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1] [ 2186.672246] RSP: 0018:ffffa0f3c1537dd0 EFLAGS: 00010203 [ 2186.672981] RAX: 0000000000000002 RBX: 00000000000003fe RCX: 0000000000000000 [ 2186.673801] RDX: 0000000000000001 RSI: ffffffffc0292029 RDI: 0000000000000000 [ 2186.674598] RBP: ffffa0f3c1537e00 R08: 0000000000000000 R09: 0000000000000000 [ 2186.675396] R10: 000000000000037b R11: ffffffffc0293681 R12: 0000000000020000 [ 2186.676193] R13: ffffa0f3c1537f18 R14: 0000000000000000 R15: ffffffffc0293682 [ 2186.677004] FS: 00007f94815eb700(0000) GS:ffff8d3ddfd00000(0000) knlGS:0000000000000000 [ 2186.677910] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 2186.678566] CR2: 0000000000000010 CR3: 000000001ba56000 CR4: 00000000000406e0 [ 2186.679360] Stack: [ 2186.679640] 00007f94815c9000 ffff8d3ddd2e7d80 0000000000000001 ffffffffc0293200 [ 2186.680561] ffff8d3dde0add00 0000000000020000 ffffa0f3c1537e48 ffffffff893deeb4 [ 2186.681554] 00007f94815c9000 ffffa0f3c1537f18 ffff8d3dde0add00 ffffa0f3c1537f18 [ 2186.682540] Call Trace: [ 2186.682930] [<ffffffff893deeb4>] full_proxy_read+0x54/0x90 [ 2186.683636] [<ffffffff8922bd27>] __vfs_read+0x37/0x150 [ 2186.684292] [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0 [ 2186.685037] [<ffffffff8922cf03>] vfs_read+0x93/0x130 [ 2186.685659] [<ffffffff8922e405>] SyS_read+0x55/0xc0 [ 2186.686239] [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0 [ 2186.686933] [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad [ 2186.687658] Code: bb 00 04 00 00 49 c7 c7 80 36 29 c0 49 81 fe f0 32 29 c0 75 16 eb 2e 4d 8b 36 48 98 49 01 c7 48 29 c3 49 81 fe f0 32 29 c0 74 1a <41> 8b 4e 10 48 c7 c2 26 20 29 c0 48 89 de 4c 89 ff e8 15 1e 2d [ 2186.690753] RIP [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1] [ 2186.691475] RSP <ffffa0f3c1537dd0> [ 2186.691913] CR2: 0000000000000010 [ 2186.695397] ---[ end trace 83771c8afec0d8dc ]--- ....
上記ログの中でとくに注目すべきは次の部分です。
... [ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010 # ... (1) [ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1] # ... (2) ... [ 2186.682540] Call Trace: [ 2186.682930] [<ffffffff893deeb4>] full_proxy_read+0x54/0x90 [ 2186.683636] [<ffffffff8922bd27>] __vfs_read+0x37/0x150 [ 2186.684292] [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0 [ 2186.685037] [<ffffffff8922cf03>] vfs_read+0x93/0x130 [ 2186.685659] [<ffffffff8922e405>] SyS_read+0x55/0xc0 # ... (3) [ 2186.686239] [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0 [ 2186.686933] [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad ...
ここから次のことがわかります。
- read()システムコールを発行した延長で(ログ内の(2)の部分)、show_read()関数の実行中に問題が発生した(ログ内の(2)の部分)
- カーネルがNULLポインタにアクセスした(ログ内の(1)の部分)にアクセスした
このようなことが起きた理由は、lock1.koが提供しているスタックの実装に使っているmystackに複数の処理が同時にアクセスしたものの、mystackは同時アクセスに耐えない作りになっていることです。これが具体的にどういうことなのかを、これから明らかにしています。
空のmystackにa, bという2つの要素をpushする場合を考えます。このとき、カーネルの中では次に示すlist_add()が二回呼ばれます1。
...
static inline void list_add(struct list_head *new, struct list_head *head)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next, new;
}
...
static list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
...
まずは正しく動作する、2つのpush処理A, Bが順番に動くケースについて記載します。コードで表現すると、次のようになります。
処理A 処理B
==================================================
mystack->prev = a;
a->next = mystack;
a->prev = mystack;
mystack->next, a;
a->prev = b;
b->next = a;
b->prev = mystack;
mystack->next, b;
図で書くと次のようになります。
ややわかりにくいですが、こちらは正しく動作しています。mystackからnextをたどっていくとmystack->b->a->mystackと循環しており、かつ、prevをたどっていくと、mystack->a->b->mystackと循環していることがわかります。
続いて2つのpushが同時に動くケースについて記載します。コードで表現すると、次のようになります。
処理A 処理B
=================================================
mystack->prev = a;
mystack->prev = b;
a->next = mystack;
b->next = mystack;
a->prev = mystack;
b->prev = mystack;
mystack->next, a;
mystack->next, b;
図で書くと次のようになります。
これはmystack内のリンク関係が無茶苦茶になっています。mystackにはbしか繋がっていない状態です。mystackからnextをたどっていくと、mystack->b->mystackと循環しており、かつ、prevをたどっていくと、mystack->b->mystackと循環しています。その一方でaはprevもnextもmystackを指しており、自分ではmystackに繋がっているつもりになっています。この後何が起きても不思議では無い状態です。拷問プログラムの動作時において、この問題はNULLポインタへのアクセスという障害として顕在化しました。
「同時に複数の処理が動く」と一口に言っても、その組み合わせは様々です。その上、list2.koではlist_add()とlist_del()以外にもlist_empty()などの他の処理も同時多発的に動きますので、拷問プログラムにおいて実際にどのように問題が顕在化するのかは毎回異なります。したがって、みなさんの環境では、冒頭で示したものとは異なるスタックトレースが見えるかもしれません。
ここでの問題の本質は、mystackに同時にアクセスしてしまったことです。これを避けるために、クリティカルセクションと呼ばれる特定のコード領域には、ただ1つの処理しか同時に侵入できないようにします。これを排他制御と呼びます(ようやく今回のタイトルの文言が出てきました)。
排他制御をする方法にはいろいろありますが、ここではmutextという方法を使います。mutexを使うには、次のような手順を踏みます。
- クリティカルセクションを定義する。ここではmystackを操作する箇所全てが該当する。それに加えて、testbufを操作する箇所も含める。これまで述べなかったが、testbufも複数処理から同時に更新されるとユーザからの入出力値が不正なものになる可能性がある。
- クリティカルセクションを保護するためのmutex(struct mutex型の変数)を定義する。ここではmystack_mutexとする。
- クリティカルセクションの前後に必ずmutexを獲得/開放する。
1は済んでいますから、2以降をコードに落としましょう。まずは2のmutexの定義から。
static DEFINE_MUTEX(mystack_mutex);
続いて3のmutexを使用するコードを書きます。例としてmystackに新要素をpushするpush_write()関数内を、mutexを用いて排他制御するように変更します。
...
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
ssize_t ret;
int n;
mutex_lock(&mystack_mutex);
ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
if (ret < 0) {
mutex_unlock(&mystack_mutex);
return ret;
}
sscanf(testbuf, "%20d", &n);
mystack_push(n);
mutex_unlock(&mystack_mutex);
return ret;
}
...
クリティカルセクションに入る前にmutex_lock()によってmutextを獲得し、そこを抜けたらmutex_unlock()によってmutexを開放しています。mutex_lock()の中では
- mutexが未獲得なら、獲得して先に進む
- mutexが獲得済みならmutexが開放されるまで待つ
という処理をします。これによって、複数の処理が同時にクリティカルセクションに入れなくなります。例えばリストへの同時アクセスだけに注目してみると、処理の流れが次のようになるためにmystackの破壊は防げます。
処理A 処理B
==========================================================================
mutex_lock(&mystack_mutex); # mutex獲得
mystack->prev = a;
mutex_lock(mystack_mutex);
a->next = mystack; ... # ここからmutex獲得待ち
a->prev = mystack; ...
mystack->next, a; ...
mutex_unlock(&mystack_mutex); ... # ここでmutex獲得
mystack->prev = b;
b->next = mystack;
b->prev = mystack;
mystack->next, b;
mutex_unlock(&mystack_mutex);
mutexを用いてlock1.cを書き直したものが次のリストです。
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>
MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");
struct mystack_entry {
struct list_head list;
int n;
};
#define MYSTACK_MAX_LEN 10
static LIST_HEAD(mystack);
static int mystack_len;
static DEFINE_MUTEX(mystack_mutex);
static void mystack_push(int n) {
struct mystack_entry *e;
if (mystack_len >= MYSTACK_MAX_LEN) {
return;
}
e = kmalloc(sizeof(*e), GFP_KERNEL);
INIT_LIST_HEAD(&e->list);
e->n = n;
list_add(&e->list, &mystack);
++mystack_len;
}
static int mystack_pop(int *np) {
struct mystack_entry *e;
if (list_empty(&mystack)) {
return -1;
}
e = list_first_entry(&mystack, struct mystack_entry, list);
if (np != NULL)
*np = e->n;
list_del(&e->list);
--mystack_len;
kfree(e);
return 0;
}
static void mystack_clean_out(void) {
mutex_lock(&mystack_mutex);
while (!list_empty(&mystack)) {
mystack_pop(NULL);
--mystack_len;
}
mutex_unlock(&mystack_mutex);
}
static struct dentry *mylist_dir;
static struct dentry *showfile;
static struct dentry *pushfile;
static struct dentry *popfile;
static char testbuf[1024];
static ssize_t show_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
char *bufp = testbuf;
size_t remain = sizeof(testbuf);
struct mystack_entry *e;
size_t l;
ssize_t ret;
mutex_lock(&mystack_mutex);
if (list_empty(&mystack)) {
ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
mutex_unlock(&mystack_mutex);
return ret;
}
list_for_each_entry(e, &mystack, list) {
int n;
n = snprintf(bufp, remain, "%d ", e->n);
if (n == 0)
break;
bufp += n;
remain -= n;
}
l = strlen(testbuf);
testbuf[l - 1] = '\n';
ret = simple_read_from_buffer(buf, len, ppos, testbuf, l);
mutex_unlock(&mystack_mutex);
return ret;
}
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
ssize_t ret;
int n;
mutex_lock(&mystack_mutex);
ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
if (ret < 0) {
mutex_unlock(&mystack_mutex);
return ret;
}
sscanf(testbuf, "%20d", &n);
mystack_push(n);
mutex_unlock(&mystack_mutex);
return ret;
}
static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
int n;
ssize_t ret;
mutex_lock(&mystack_mutex);
if (*ppos || mystack_pop(&n) == -1) {
mutex_unlock(&mystack_mutex);
return 0;
}
snprintf(testbuf, sizeof(testbuf), "%d\n", n);
ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
mutex_unlock(&mystack_mutex);
return ret;
}
static struct file_operations show_fops = {
.owner = THIS_MODULE,
.read = show_read,
};
static struct file_operations push_fops = {
.owner = THIS_MODULE,
.write = push_write,
};
static struct file_operations pop_fops = {
.owner = THIS_MODULE,
.read = pop_read,
};
static int mymodule_init(void)
{
mylist_dir = debugfs_create_dir("mystack", NULL);
if (!mylist_dir)
return -ENOMEM;
showfile = debugfs_create_file("show", 0400, mylist_dir, NULL, &show_fops);
if (!showfile)
goto fail;
pushfile = debugfs_create_file("push", 0200, mylist_dir, NULL, &push_fops);
if (!pushfile)
goto fail;
popfile = debugfs_create_file("pop", 0400, mylist_dir, NULL, &pop_fops);
if (!popfile)
goto fail;
return 0;
fail:
debugfs_remove_recursive(mylist_dir);
return -ENOMEM;
}
static void mymodule_exit(void)
{
debugfs_remove_recursive(mylist_dir);
mystack_clean_out();
}
module_init(mymodule_init);
module_exit(mymodule_exit);
これをロードした後にlock-tortureを実行しても問題は発生しません。試してみてください。
演習問題
- 第三回の debugfs3.c にも排他制御にまつわる問題があります。これについて、何が問題なのかを明らかにして、mutexを用いて問題が発生しないようにする。
おわりに
排他制御にはmutex以外にも様々な種類がありますが、すべてを紹介するにはまだ早いので、まずはここまで。ここでは、mutexの概念と、それを使用するために必要な手順だけを覚えていただければよいです。次回は多分デバイスドライバもどきを作成する予定です。
本章で作成したソースと同じものをexample/module/lock以下に配置しています。
Linuxカーネルソースの統計情報
はじめに
本記事はlinuxカーネルのソース分析によって、このソフトウェアの様々な特徴を可視化します。ソースの総行数といったありがちなものから、1つのバージョン内のrelease candidate(rc)ごとのパッチ数の推移やサブシステムごとのデータなども出しています。
linuxには、v2.6.x, v3.x, v4.xで表す、Linuxのオリジナル開発者であるLinus Torvalds氏がリリースするmainlineカーネル(通常、単にLinuxと言えばmainlineカーネルを指す)があります。このうち、データ採取した範囲はgitで追える範囲のv2.6.12〜v4.10までです。ものによってはv4.0〜v4.10までの範囲です。
全体の傾向
総行数
行数は*.[chS]というパターンにマッチする行の数を使いました。v2.6.12では600万行そこそこ(それでも凄いのですが)だったのが、12年弱後に出た執筆時点では最新のv4.10では約4倍の2100万行弱まで増加しています。行数はおおよそ単調増加していますが、唯一v3.17だけ4万行程度減少していました(理由は後日調査するかも)。増加速度が衰える気配は見えておらず、未だ活発なプロジェクトであることがわかります。
パッチ数
v2.6.24あたりまでは増加傾向にありますが、その後はバージョンごとに一万から一万五千パッチあたりをうろうろしています。やや増加傾向にあると言えるかもしれません。行数ではなくパッチ数という観点で見ても開発は活発といえます。
増加行数
ばらつきはありますが、平均すると、リリース毎におよそ25万行増加しています。linuxカーネルは9〜10週程度に一度新バージョンをリリースしますので(詳細は後述)、一週間ごとに2万〜3万行、一日ごとに3千〜4千行増加しています。linuxの開発には、いかに莫大なリソースが投入されているかがわかります。
ただし、これはあくまでリリース版に入ったコードだけの話なので、実際には
- 上記の通り、単に行の追加だけではなく削除もしている
- マージされなかったコードが星の数ほどある
などの理由によって、このデータに現れないものも含めた投入リソースはさらに多いです。
パッチごとの増加行数
時を経るに従って増減するわけではなく、バージョンごとにかなりばらばらです。平均すると1パッチごとに20行程度増加しているようですが、このデータだけでは平均値を使うのがそもそも適切かどうか怪しいところです。
rcごとのパッチ数から見るlinuxのリリースサイクル
mainlineカーネルのデータを見るとパッチ数はそれなりに安定していましたが、さらに粒度を細かく見ると、どうなるでしょうか。
linuxは新たなmainlineカーネルをリリースするごとに、その後二週間後に次のmainlineカーネルのrc1がリリースされます。その後一週間ごとにrc2, rc3...とバージョンを重ねることによって安定化させてゆき、rc7の一週間後に次のmainlineカーネルをリリースします。たまにLinus氏の判断により、rc7から一週間後でも安定していないとみなされた場合はrc8が出ることがあります1。
以下はrcリリースごとに見たパッチ数の推移です。
1つのバージョンのリリースまでの流れを追うと、rc1でほとんどのパッチが適用されて、その後はそれに比べればはるかに少ない数のパッチしかマージされないことがわかります。それもそのはず、rc1では新機能パッチに加えてあらゆる修正パッチが取り込まれますが、、rc2以降は基本的にはバグフィックスパッチしか入らないからです。
rc1のパッチ数が多すぎるので、縦軸のスケールを変えて、rc2以降に注目したグラフを見てみましょう。
時間の経過に伴い、マージされるパッチの数が減っていっていることがわかります。これは、次版のリリースが近づくほど重要なパッチしかマージしなくなってゆくという開発方針によるものです。
サブシステムごとの情報
これまでにカーネルの総行数について分析してきました。では、カーネルにある様々なサブシステムのうち、どのサブシステムの行数が多いのか、どのサブシステムに対するパッチが多いのかを見てみましょう。ここはソースのトップディレクトリのうち、
- カーネルに関係ないユーザ空間のもの
- ヘッダファイル用(include/)
- ドキュメント(Documentation/)
などを除いた以下のディレクトリをサブシステムとしてデータを採取しました。
| サブシステム名(ディレクトリ名) | 役割 |
|---|---|
| arch | 各CPUアーキテクチャ固有部分 |
| block | ブロックデバイス層 |
| crypto | 暗号化 |
| drivers | ドライバ。キャラクタデバイス、ブロックデバイス、NICなど |
| fs | ファイルシステム。ext4, XFS, Btrfs, nfsなど |
| init | 初期化 |
| ipc | System V IPC |
| kernel | コア部分。プロセススケジューラ、割り込み、タイマー、シグナル制御など |
| lib | 他のサブシステムから使うライブラリ |
| mm | メモリ管理 |
| net | ネットワーク。IPv{4,6}など |
| security | セキュリティ。SELinuxなど |
| sound | サウンド |
| virt | 仮想化。KVMなど |
どのサブシステムの行数が多いか
一見してドライバ(drivers/)のコードが圧倒的に多いことがわかります。その後にアーキテクチャ依存コード(arch/)、第三勢力のファイルシステム(fs/)、サウンド(sound/)、ネットワーク(net/)などが追いかけます。コア部分(kernel/)やメモリ管理(mm/)は実は全体から見ると大した規模ではないというのが面白いところです。
どのサブシステムの増加行数が多いか
ドライバが圧倒的多数を占めており、それに比べるとその他のサブシステムの増加量はほとんど誤差範囲です。linuxのコード量が前述の通り年々凄まじい速度で増加しているのは事実だとしても、その増加量のうちのほとんどはドライバのコードだということがわかります。
ドライバを除いた場合についても見てみましょう。
行数の場合の二位であったアーキテクチャ依存コード(arch/)、第三勢力であったファイルシステム(fs/)、サウンド(sound/)、ネットワーク(net/)の変更量が多いことがわかります。ただし、どのバージョンでどのサブシステムが主に変更されるかについては、とくに規則性は無いようです。
v4.1においてアーキテクチャ依存コードが大幅に減少している理由は不明です。v4.3においてファイルシステムの行数が大量に減少しているのは、ext3のコードが全て削除されたことが主な原因です(ext3が非サポートになったわけではなく、ext3をマウントするとext4のコードで操作するようになりました)。
ドライバのコード
ドライバの種類別のコード量
さきほどlinuxのコードの大部分はドライバのコードだと書きました。では、どのような種類のドライバが多いのかを円グラフにまとめました。v4.10におけるdrivers/以下のディレクトリのうち、ソース行数の多かった上位10のディレクトリと、その他のディレクトリの行数を合計した値を表示しています。
ネットワーク(net/)、GPU(gpu/)、カメラやビデオ、TVなどのマルチメディア(media/)あたりのコードが多いことがわかります。ネットワークドライバについては、ネットワークプロトコル(トップディレクトリの下のnet/ディレクトリ)のコードも多かったことを考えると、linuxのソースはネットワーク関連のコードの割合が高いと言えます。その一方、ブロックデバイスやキャラクタデバイスなどは上位10個に入らない程度のコード量しか無いことがわかります。
新規デバイスをサポートするためのコードと既存ドライバを変更するコード
ドライバに関するソースの増分のうち、ほとんどが新規ドライバ用のコードであり、既存ドライバの変更分はそれに比べると遥かに少ないことがわかります。上述の通り、全体に対する変更量のほとんどがドライバのものであることを考えると、Linuxのソースの増分のうち、かなりの割合が新規デバイスサポート用のコードであるということが言えます。
stableカーネル
linuxにはmainlineカーネルに加えて、あるmainlineカーネルがリリースされてから次のmainlineカーネルがリリースされるまで、重大なバグ修正パッチだけを適用するstableカーネルが不定期にリリースされます。stableカーネルのバージョン番号はv2.6.x.y, v3.x.y, およびv4.x.yです。
各stableカーネルの最新のバージョン番号
あるmainlineカーネルに対する最新のstableカーネルのバージョン(上述のバージョン名のルールにおけるyの部分)を次に示します。
ほとんどの場合、stableカーネルのリリースは数回ないし十数回程度です。しかし、一部のものは、それより明らかに多くリリースされています。これはlongtermカーネルと呼ばれるもので、特定のstableカーネルを長くサポートしたいという人が、その人が定める期限(EOL)まで次版をリリースし続けるというものです。
stableカーネルをリリースするのは、通常はlinuxカーネル開発の大物であるGreg KH氏ですが、別の人がリリースすることもあります。最初はGreg氏がリリースを担当するものの、後になって別の人が引き継ぐこともあります。Grep氏以外にstableバージョンをリリースするのは、ディストリビュータ関連の人が多いです。
stableカーネルのサポート期限
あるmainlineカーネルがリリースされてから、それに対応する最新のstableカーネルがリリースされるまでの日数を次のグラフに示します。
ほとんどは3ヶ月未満(次のmainlineカーネルがリリースされるまでの日数にほぼ一致)でリリースが止まりますが、longtermのものについてはそれより長いです。場合によっては複数年にわたることもあることがわかります。
linuxのバージョンについて説明しているページの"Longterm"の項に記載されているバージョンについては、今後もリリースが続くことに注意してください。
stableバージョンのパッチごとの追加行数
これは明らかに通常バージョンのものより少ないです。1パッチあたり高々平均5行程度の増加に留まっています。これは、stableバージョンに取り込まれるパッチは重大バグの修正であるというだけでは不十分で、ある程度修正量が小さいもののみが取り込まれるというルールに由来しています。
おわりに
本書で統計情報に使ったソースはgithub上に置いています。
Linuxカーネルで学ぶC言語のマクロ
はじめに
本記事は電子書籍版もあります。
linuxカーネルはC言語のマクロを駆使して書かれています。それらのうち、凝ったマクロになじみの無い人には初見では意図がわからない&わかってみれば面白いであろうものをいくつか紹介いたします。対象読者は、C言語のユーザだけれども、マクロは定数定義くらいにしか使わないというライトなマクロユーザです。
マクロを使用する場所に依存するエラーを防ぐ
次のマクロは、二つの引き数の値を置換するだけの単純なものです。
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
注目すべきはマクロの定義全体を囲んでいるdo { ... } while (0)という表記です。初見の人には何のことかわからないと思います。考えられる最も単純な定義から遡って、なぜこのような定義にするとよいのかを見てみましょう。
このマクロのdo {} while文のブロックを外したバージョンのマクロを使ってみましょう。
#include <stdio.h>
#define swap(a, b) \
typeof(a) __tmp = (a); (a) = (b); (b) = __tmp;
int main(void)
{
int a = 0, b = 1;
swap(a, b);
printf("%d %d\n", a, b);
return 0;
}
実行例を示します。
$ make swap cc swap.c -o swap $ ./swap 1 0 $
ちゃんと動いているように見えます。しかし、これが次のような使い方だといかがでしょうか。
#include <stdio.h>
#define swap(a, b) \
typeof(a) __tmp = (a); (a) = (b); (b) = __tmp;
int main(void)
{
int a = 0, b = 1;
if (0)
swap(a, b);
printf("%d %d\n", a, b);
return 0;
}
コンパイルします。
$ make swap2
cc swap2.c -o swap2
swap2.c: In function 'main':
swap2.c:4:9: error: expected expression before 'typeof'
typeof(a) __tmp = (a); (a) = (b); (b) = __tmp;
^
swap2.c:10:3: note: in expansion of macro 'swap'
swap(a, b);
^~~~
swap2.c:4:49: error: '__tmp' undeclared (first use in this function)
typeof(a) __tmp = (a); (a) = (b); (b) = __tmp;
...
make: *** [swap2] Error 1
$
期待値はif文の中のswap()マクロは実行せずに端末上に"0 1¥n"という出力をする、というものですが、実際は山ほどエラーが出てコンパイルが失敗しました。ソースをコンパイルせずにプリプロセッサだけをかけて原因を探ってみましょう。
$ cc -E swap2.c
...
int main(void)
{
int a = 0, b = 1;
if (0)
typeof(a) __tmp = (a); (a) = (b); (b) = __tmp;;
printf("%d %d\n", a, b);
return 0;
}
$
一見正しいように見えますが、制御構造を意識して整形してみると、おかしい点がわかってきます。
int main(void)
{
int a = 0, b = 1;
if (0)
typeof(a) __tmp = (a);
(a) = (b);
(b) = __tmp;;
printf("%d %d\n", a, b);
return 0;
}
swap()マクロ内の3つの命令のうち、一行目の一時変数__tmpを宣言している行はif文の中にありますが、それ以外の2命令はif文の外に出てしまっています。これではまともに動くはずがありません。さらに、if文の中に変数宣言のみを1行置くことは許されないので、上記コンパイルログの一行目のようなエラーが出ています。
では次のようにマクロ定義を単にブロック("{}")で囲めばいいのではないか、というかたもいらっしゃるかと思うので、試してみます。
#include <stdio.h>
#define swap(a, b) \
{ typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; }
int main(void)
{
int a = 0, b = 1;
if (0)
swap(a, b);
printf("%d %d\n", a, b);
return 0;
}
$ make swap3 cc swap3.c -o swap3 $ ./swap3 0 1 $
こちらはうまくいきました。しかしこれは次のようなケースではうまくいきません。
#include <stdio.h>
#define swap(a, b) \
{ typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; }
int main(void)
{
int a = 0, b = 1;
if (0)
swap(a, b);
else
printf("Always print this message¥n");
printf("%d %d\n", a, b);
return 0;
}
$ make swap4 cc swap4.c -o swap4 swap4.c: In function 'main': swap4.c:11:2: error: 'else' without a previous 'if' else ^~~~ <builtin>: recipe for target 'swap4' failed make: *** [swap4] Error 1 $
期待値は"Always print this message¥n"の後に"0 1¥n"が出力される、なのですが、謎のコンパイルエラーが発生しました。これについてもプリプロセッサによる処理後のソースを見てみましょう。
$ cc -E swap4.c
...
# 6 "swap4.c"
int main(void)
{
int a = 0, b = 1;
if (0)
{ typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; };
else
printf("Always print this message¥n");
printf("%d %d\n", a, b);
return 0;
}
さきほどと同様に、制御構造を意識してソースを整形します。
int main(void)
{
int a = 0, b = 1;
if (0)
{ typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; }; # ... (1)
else
printf("Always print this message");
printf("%d %d\n", a, b);
return 0;
}
ややわかりにくいのですが、ソース内の(1)のところでCの構文上if文は完結しています。したがって、それに続くelse節はコンパイラから見るとif文無しに突然出てきたように見えるため、エラーが出ていたのでした。
この場合はswap(a,b);の末尾のセミコロンを省けばうまく動作します。しかしこれは明らかに直感的ではないので、このような使い方はできれば避けたいです。上記の命令列を単なるブロックではなく do {} while (0)で囲めば、それが可能になります。コード例は出しませんが、この場合は上記すべての場合についてうまく動作します。
上記のような「うまくいかないケース」を全て知らないと、なかなかこの do {} while (0) の意図は理解できないと思います。linuxカーネル以外でも頻出のCマクロのイディオムなので、覚えておいて損はないと思います。
ジェネリックプログラミング
さきほどのswap()の例をもう一度見てみましょう。
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
これはインライン関数で実装しても同じように見えますが、実際やってみると面倒なことがわかります。以下のコードを見て下さい。
static inline void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
これはこれで動くのですが(引数に変数でなく変数へのポインタを指定しないといけないところは異なります)、このswap()はintにしか使えません。別の型については別のswap()を定義する必要があります。しかも、Cは関数のオーバーロード機能1が無いため、複数の型に対するswap()を同時に定義したい場合は、例えば次のように定義する必要があります。
static inline void swap_int(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
static inline void swap_double(double *a, double *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
呼び出すためにいちいち型名を指定する必要がある上に、同じような意味のコードを重複して書く必要があるので保守性が非常に悪いです。マクロを使えばこのような問題を避けられます。ちょうどC++のテンプレートを使ったジェネリックプログラミングのようなことができます。
ビルドの設定に応じて何もしない関数/マクロを定義する
linuxカーネルでは、特定のビルド設定において、特定の関数を何もしないように定義している箇所が多々あります。次に示す実際のコードを見てみましょう。
...
#if BITS_PER_LONG==32 && defined(CONFIG_SMP)
#include <linux/seqlock.h>
#define __NEED_I_SIZE_ORDERED
#define i_size_ordered_init(inode) seqcount_init(&inode->i_size_seqcount)
#else
#define i_size_ordered_init(inode) do { } while (0)
#endif
...
このコード断片は、ぱっと見ややこしそうですが、言葉で説明すると次のようなことをしています。
- i_size_ordered_init()というマクロを定義する
- ビルド対象アーキテクチャのlongのサイズが32であり、かつ、マルチプロセッサ環境であればseqcount_init()を呼ぶ
- そうでなければ何もしない
注目してもらいたいのはi_size_ordered_init()マクロのdo { } while (0)という定義です。これは先程の例の応用で、「何もしない」関数/マクロを定義しています。
このマクロを呼び出している箇所でいちいち
...
{
...
#if BITS_PER_LONG==32 && defined(CONFIG_SMP)
i_size_ordered_init();
#endif
...
}
...
などとするよりはるかにコードの保守性が高いです。
なお、#define i_size_ordered_init(inode)(マクロ定義を空にする)や、#define i_size_ordered_init(inode) {}などという定義にすると、前述のようなさまざまなコーナーケースが存在してしまいます。
引数の文字列化
次は、マクロの引数を文字列にする方法について学んでみましょう。例として、以下のlinuxカーネル内のコードを示します。
... #ifdef CONFIG_SCHED_DEBUG #define SCHED_WARN_ON(x) WARN_ONCE(x, #x) #else ... #endif ...
ここでは簡単のためCONFIG_SCHED_DEBUGが定義されていると考えて、SCHED_WARN_ON()マクロが何をするものなのかを見ていきます。このマクロは、スケジューラのコードの中で、スケジューラが異常な状態であることを示す条件を満たした(満たしてしまった)ときにカーネルのログに、どの条件文が成立したかを示す警告メッセージを表示するためのものです。
SCHED_WARN_ON()の中で使われているWARN_ONCE()マクロは、第一引数に指定された条件が満たされたときに、第二引数に指定されたデバッグ用メッセージを出力します2。
SCHED_WARN_ON()を素直に実装、使用しようとすると次のようになります(実際のものとは異なります)。
#define SCHED_WARN_ON(x, msg) WARN_ONCE(x, msg)
...
{
...
SCHED_WARN_ON(number_of_runnanble_processes < 0, "number_of_runnable_processes < 0");
...
}
...
これで一応目的を達成できるのですが、一見してわかるように、なんだかダサいです。同じテキスト("number_of_runnable_processes < 0")を二回書かなくてはいけないため、書くのが面倒な上に、条件を変えたときにメッセージの追従を忘れたりする可能性があり、保守性が悪いです。これを避けるのがCマクロの、引き数の文字列化機能です。
引数の文字列化機能は、マクロの引数の前に"#"という演算子を付けることによって実現します。たとえば#define tokenize(a) #aとマクロを定義すると、tokenize(test)は"test"と評価されます。上記の実際のSCHED_WARN_ON()は、これを応用して、第一、そして唯一の引数に条件文を渡すことで、当該条件を満たした際に、条件式を示す文字列をログに出力できます。
実際の使用例は次の通りです。
...
#define SCHED_WARN_ON(x) WARN_ONCE(x, #x)
...
static inline struct cpuidle_state *idle_get_state(struct rq *rq)
{
SCHED_WARN_ON(!rcu_read_lock_held());
return rq->idle_state;
}
...
cpuidle_state()関数の定義はプリプロセッサによって次のように変換されます。
static inline struct cpuidle_state *idle_get_state(struct rq *rq)
{
WARN_ONCE(!rcu_read_lock_held(), "!rcu_read_lock_held()");
return rq->idle_state;
}
上記の素直な実装例よりはるかに書くのが楽で、かつ保守性の高いコードになることがわかります。
トークンの連結
Cのマクロ定義の中では、2つのトークン3の連結によって新たなトークンを生成できます。これは文字列の連結とは全く異なります。以下のサンプルコードをごらんください。
#define concat_token(a) \
static int func_##a(void) \
{ \
return 0; \
}
concat_token(foo)
int main(void)
{
return func_foo();
}
先頭のconcat_token()マクロの定義の中のfunc_##aという箇所に注目してください。これは"func_"というトークンと、引数aで示したトークンの2つを連結したトークンを作るという意味です。多分意味不明だと思うので、実例を見てみましょう。
conat_token(foo)を評価した場合、func_##aはfunc_fooになります。その後、マクロ全体の評価結果は次のようになります。
static int func_foo(void) \
{ \
return 0; \
}
ソース全体をプリプロセッサにかけてみましょう。
$ cc -E concat_token.c
...
static int func_foo(void) { return 0; }
int main(void)
{
return func_foo();
}
$
func_foo()という関数が定義されていることがわかります。つまりこのマクロは、引き数に指定したトークン(ここでは"foo")を含む関数を定義するものであることがわかります。
これだけでは用途がわかりにくいので、linuxカーネル内の使用例を見てみましょう。
...
#define EXT4_FEATURE_COMPAT_FUNCS(name, flagname) \
static inline bool ext4_has_feature_##name(struct super_block *sb) \
{ \
return ((EXT4_SB(sb)->s_es->s_feature_compat & \
cpu_to_le32(EXT4_FEATURE_COMPAT_##flagname)) != 0); \
} \
static inline void ext4_set_feature_##name(struct super_block *sb) \
{ \
EXT4_SB(sb)->s_es->s_feature_compat |= \
cpu_to_le32(EXT4_FEATURE_COMPAT_##flagname); \
} \
static inline void ext4_clear_feature_##name(struct super_block *sb) \
{ \
EXT4_SB(sb)->s_es->s_feature_compat &= \
~cpu_to_le32(EXT4_FEATURE_COMPAT_##flagname); \
}
...
一見複雑ですが、実はやっていることは単純です。これはext4ファイルシステム内の各機能(mkfs.ext4(8)やtune2fs(8)の-Oオプションによって有効/無効を設定)に関する関数を一括定義するためのマクロです。第一引数nameが示す機能について、第二引数flagnameによって示すフラグを操作する、一連の関数を定義します。
例えば次のように使用します。
EXT4_FEATURE_COMPAT_FUNCS(dir_prealloc, DIR_PREALLOC)
これは次のように展開されます。
...
static inline bool ext4_has_feature_dir_prealloc(struct super_block *sb) \
{ \
return ((EXT4_SB(sb)->s_es->s_feature_compat & \
cpu_to_le32(EXT4_FEATURE_COMPAT_DIR_PREALLOC)) != 0); \
} \
static inline void ext4_set_feature_dir_prealloc(struct super_block *sb) \
{ \
EXT4_SB(sb)->s_es->s_feature_compat |= \
cpu_to_le32(EXT4_FEATURE_COMPAT_DIR_PREALLOC); \
} \
static inline void ext4_clear_feature_dir_prealloc(struct super_block *sb) \
{ \
EXT4_SB(sb)->s_es->s_feature_compat &= \
~cpu_to_le32(EXT4_FEATURE_COMPAT_DIR_PREALLOC); \
}
上記3つの関数の定義はそれぞれ次の通りです。
- ext4_has_feature_dir_prealloc: 引数sbで指定したext4ファイルシステムがdir_prealloc機能4を持っているかどうかを判定
- ext4_set_feature_dir_prealloc: 同機能を有効化
- ext4_clear_feature_dir_prealloc: 同機能を無効化
一見3つの関数をマクロ内で定義するなどという回りくどいことをせずに直接定義したほうが簡単そうに見えますが、同じような定義が何度も続くような場合にこのマクロは大きな威力を発揮します。実際、ext4のdir_prealloc以外の様々な機能について同様な定義が必要であり、それぞれについて上記のEXT4_FEATURE_COMPAT_FUNCS()マクロ5で一括定義しています。これによって膨大な量の機械的なつまらないコーディングを減らせます。
EXT4_FEATURE_COMPAT_FUNCS(dir_prealloc, DIR_PREALLOC) EXT4_FEATURE_COMPAT_FUNCS(imagic_inodes, IMAGIC_INODES) EXT4_FEATURE_COMPAT_FUNCS(journal, HAS_JOURNAL) EXT4_FEATURE_COMPAT_FUNCS(xattr, EXT_ATTR) EXT4_FEATURE_COMPAT_FUNCS(resize_inode, RESIZE_INODE) EXT4_FEATURE_COMPAT_FUNCS(dir_index, DIR_INDEX) EXT4_FEATURE_COMPAT_FUNCS(sparse_super2, SPARSE_SUPER2)
トークンの連結は一見便利そうですが、cscopeなどのツールが、マクロによって生成される変数や関数をうまく認識してくれずに、ソースコードリーディングが面倒になるなどという欠点もあります。cscopeなどを使って関数やマクロの定義を探しても全く出てこないという場合は、##演算子を使って定義されたものであるかどうかを疑ってみるとよいと思います。
構造体のフィールドから、それを埋め込んだ親構造体へのポインタを得る
次に示すのは、ある構造体のフィールドから、それを埋め込んでいる親構造体へのポインタを得るマクロです。
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
ptr(第一引数)がmember(第三引数)というフィールド名で埋め込まれたtype(第二引数)型のデータのアドレスを求めます。まずは、どうやってこのような機能を実装しているかを、これから紐解いていきます。
container_of()の中にあるoffsetof()の定義を示します6。
... #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) ...
このマクロによって、TYPE(第一引数)で示される構造体の中のMEMBER(第二引数)フィールドのバイト単位のオフセットが求められます。このマクロは、ゼロ番地に配置したTYPE型データの中のMEMBERフィールドのアドレス(をsize_t型にキャストしたもの)はTYPE内のMEMBERのオフセットに等しいという性質を利用しています。わかってしまえば簡単なのですが、初見ではけっこう意味不明で引いてしまうかもしれません。
これを踏まえてcontainer_of()の定義を再度見てみましょう。
...
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
一行目はちょっと回りくどく見えますが、単に mptr変数にptr(第一引数)を代入しているだけです。二行目では mptr(すなわちptr)から、type内のmemberのオフセットを引いています。つまり、これでptrの埋め込み元であるtype型のデータが求まってしまうということです。一見一行目を省いて二行目を(type *)((char *)ptr - offsetof(type,member))だけにすれば済みそうに見えますが、一行目によって、ptrとmemberの型の対応が取れていない場合に警告メッセージが出るようになっており、思わぬバグを防げるようになっています。
例によって、これだけでは何が嬉しいのかよくわからないので、linuxカーネルのファイルシステムのコードを実例として紹介します。
linuxカーネルにおいて、ファイルシステムのコードはVirtual File System層(以後VFS層と記載)という全ファイルシステム(ext4, XFS, Btrfsなど)共通のコードと、各ファイルシステム固有のコードに分かれています。たとえば全ファイルシステムに共通するinodeに関する情報はVFS層に存在するstruct inodeという構造体によって表現します。これに対して、各ファイルシステムは、自身固有のinode情報を含む構造体を持っており、その中にstruct inodeを埋め込んでいます。
Btrfsを例にとって説明すると、btrfs固有のinode情報はstruct btrfs_inode構造体に格納されます。そのうちファイルシステム共通の部分、つまりさきほど述べたstruct inodeは、この構造体の中のvfs_inodeというフィールドとして埋め込まれています。
...
struct btrfs_inode {
...
struct inode vfs_inode;
};
...
Btrfs内のinodeの各種時刻([cma]time)を更新する際は、VFS層からbtrfs_update_time()という関数が呼ばれます。
static int btrfs_update_time(struct inode *inode, struct timespec *now,
int flags)
{
struct btrfs_root *root = BTRFS_I(inode)->root;
...
}
この関数のインターフェイスはBtrfsを含む個々のファイルシステムではなくVFS層によって定義されていますので、その引き数によって渡されるinode情報は必然的にstruct btrfs_inodeではなく、struct inodeになります。しかし、Btrfsとしては時刻の更新に伴って後者だけではなく前者の情報を使って処理をする必要があります。
ではどうすればいいかというと、ここでcontainer_of()が登場します。btrfs_update_time()冒頭のBTRFS_I()の中で、container_of()を呼び出すことによって、inode(第一引数)をvfs_inode(第三引数)というフィールド名で埋め込んでいるstruct btrfs_inode(第二引数)のアドレスを求めます。
static inline struct btrfs_inode *BTRFS_I(struct inode *inode)
{
return container_of(inode, struct btrfs_inode, vfs_inode);
...
}
後は求めたstruct btrfs_inodeのデータへのポインタを使って粛々と処理をするだけです。具体的にどういう処理をするかは本書の対象範囲外なので割愛します。
リスト操作
linuxカーネルは、その中にstruct list_headという構造体によって管理する双方向リストの実装を持っています。このリストは例によって、C言語のマクロを最大限に活用して実装されています。この節ではその実装について扱います。
リストについての基本的な知識は、お手数ですが別記事の"リストの構造"という節に書いていますので、そちらを参照してください。短いし単純なので、短時間で読めると思います。
リストを処理するためのマクロは多くありますが、ここではその中でマクロを活用している処理について2つ紹介します。
まずは指定したstruct list_headのデータから、それを埋め込んだ親構造体を求めるlist_entry()マクロです。
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
これは定義を聞いただけでピンと来るかもしれませんが、内部でcontainer_of()を呼び出しているだけです。これでptr(第一引数)をmember(第三引数)というフィールド名で埋め込んでいるtype型のデータへのポインタを獲得できます。
続いて、リスト内の全エントリを順番に処理するlist_for_each_entry()マクロを見てみます。
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
この関数は、headで示されるリストの中の全要素について、各要素をposという名前で取り出すことによってそれぞれに対して処理をします。ここで、posの中でheadに対応するリストはmemberというフィールド名で埋め込まれています。
使用例を示します。サンプルプログラムの仕様とソースは次の通りです。
仕様:
- mylistというリストがある
- mylist内のエントリはint型のnという名前の唯一のデータを持つ
- mylist_show()は、mylist内のすべてのエントリに対してnをカーネルログに出力する
static LIST_HEAD(mylist);
struct mylist_entry {
struct list_head list;
int n;
};
...
static void mylist_show(void) {
struct mylist_entry *e;
printk(KERN_ALERT "mylist: show contents\n");
list_for_each_entry(e, &mylist, list) {
printk(KERN_ALERT "\t%d\n", e->n);
}
}
一見関数のように見える list_for_each_entry()マクロからブロックが生えてその中で処理をしているというのはC言語を知っていれば知っているほど驚くと思いますが、前述のようなマクロ定義をしていればこのような芸当が可能なのです。
linuxカーネルの中には他にも"for_each"という文字列を含む名前の類似のマクロが随所に出てきます。たとえば各エントリの処理中にエントリの削除が可能なlist_for_each_safe()があります。他にも、リストとは別のデータ構造にも類似したAPIが用意されていることもあります。興味があれば、それぞれの定義を見てみると面白いと思います。
おわりに
本記事は執筆時点で自分の脳内にたまたま残っていたマクロについて書いただけなので、他にも面白いマクロはいくらでもあると思います。思い出したらまた追記する予定です。読者のかたがたも、「これも紹介してくれ」とか「このマクロの意味がわからないんだけど」などありましたら、教えていただけると、今後追記するかもしれません。
-
同じ名前で別の引数、戻り値を持つ関数を定義できる機能。例えばswap(int a, int b)とswap(double a, double b)が共存できる。Cでこれをやろうとすると、同名関数が2つ定義されているという旨のコンパイルエラーが出ます。↩
-
最初に条件を満たしたときのみ出力されます。それ故に
_ONCEという名前が付いています)。↩ -
トークンという言葉がよくわからなければ、ここではなんとなく、コンパイラに変数名や関数名と解釈される文字列と考えてもらっていいです。↩
-
ここでは機能そのものの意味は重要ではないので割愛↩
-
より正確には、これに加えてEXT4_FEATURE_RO_COMPAT_FUNCS()マクロ、およびEXT4_FEATURE_INCOMPAT_FUNCS()マクロも用いる。↩
-
実際には下記定義を直接使うのではなくコンパイラ(通常gcc)組み込みの同等機能を使うのですが、理解を簡単にするためにこちらを例に使います。↩
