第85回　Linuxの成長過程をふりかえる［その4］

前回に引き続き、今回はlinux-2.1シリーズの成長過程を検討します。

linux-2.1のシリーズは1996年9月30日に公開されたlinux-2.1.0から開発が始まり、約2年3ヵ月の開発期間を経て1998年12月22日に公開されたlinux-2.1.132で開発終了、その後、翌年の1月中旬ぐらいまでデバッグや安定化のためにlinux-2.2.0-preXが公開され、次の安定版であるlinux-2.2.0は1999年1月26日に公開されました。

カーネルサイズの変遷グラフからlinux-2.0と2.1の2つのシリーズを取り出して描くと、図1のようになります。

図1を見ると、linux-2.0のシリーズは2.1の開発が終った後、すなわち次の安定版であるlinux-2.2が公開された後も、ずいぶん長くメンテナンスされていることに気づきます。

このころのLinuxは、同じ「安定版」とは言っても、2.0と2.2のように世代が異なるとカーネルの内部構造が大きく変更されていて、必須のツール類も多数更新する必要があると共に、カーネルの内部構造を利用していたソフトウェアが動かなくなったりしました。そのような事情から新しい安定版へ更新できない環境もあちこちにあり、そのためにメンテナンス期間を長く取っていたようです。

それではlinux-2.0と2.2の間でどのような変更が行なわれたかを、開発版であるlinux-2.1シリーズを元に検討してみましょう。

linux-2.1シリーズの概要

linux-2.1では130を越えるバージョンが公開されているので、前回よりもチェックポイントを1つ増やし、2.1.0、2.1.45、2.1.90、2.1.132の4つのバージョンについてソースコードをチェックしてみることにします。

前回同様、それぞれのバージョンごとに、ソースコードのトップディレクトリのサイズを調べると以下のような結果になりました。表中の各数字はKB単位で、1100は1100KB（1.1MB⁠）⁠、130000は130000KB（13MB）を意味します。

	2.1.0	2.1.45	2.1.90	2.1.132
Documentation	1100	1500	2000	2500
arch	5000	7200	8600	9800
drivers	13000	18000	23000	29000
fs	2100	2300	4000	4300
include	3800	5900	7400	8700
init	28	32	36	40
ipc	72	76	64	64
kernel	200	224	260	264
lib	64	64	64	64
mm	196	248	260	260
net	1500	2800	3200	4200
scripts	284	288	292	296
modules	0	-	-	-
Total	27000	38000	49000	59000

この表を見ると、linux-2.1シリーズの開発過程でソースコード全体は2倍強に増加しています。一方、それぞれのディレクトリを見るとarchやdirvers,fs,includeのように2倍強に増加したディレクトリとinitやipc,kernelのように2～3割の増加に留まっているディレクトリが見られます。

linux-2.1シリーズでは、driversのような大きなディレクトリとinitのような小さなディレクトリの差が700倍近くあり、前回までのような全体に占める割合を示す扇形グラフでは各ディレクトリの変化パターンが見えにくいので、今回は容量の大きいディレクトリとそれほどではないディレクトリをそれぞれ別のグラフに仕立ててみました。

図2は容量の大きいディレクトリのサイズがバージョンごとにどのように変化したかを示しました。このグループにはDocumentation、arch、drivers、fs、include、netの各ディレクトリが含まれます。図3は容量がそれほど大きくないディレクトリの変化で、init、ipc、kernel、lib、mm、scriptsの各ディレクトリが含まれます。

2つの図を比べると、容量の大きいディレクトリは2.1シリーズ全体を通してコンスタントに増加し続けているのに対し、容量の小さいディレクトリは横這いだったり、増加のペースにむらがあったりするようです。

ある意味これは当然の結果で、容量の大きいディレクトリ群に含まれているarchやdrivers、includeは、それぞれのハードウェアに依存するコードを集めた部分で、Linuxが新たなコンピュータ（CPU）に対応すると、そのためのコードがarchディレクトリに追加されると共に、そのコードを利用するためのヘッダファイルがincludeディレクトリに追加され、そのコンピュータ用の周辺機器用のドライバがdriversディレクトリに追加されます。すなわち、これらのディレクトリはLinuxが対応するハードウェアの増加に伴なって増えていくわけです。

事実、linux-2.1シリーズでは、1.xシリーズ同様、新しいコンピュータ（CPU）への対応が続いています。2.1.0、2.1.45、2.1.90、2.1.132のそれぞれでarchディレクトリは以下のように増加しています。

	2.1.0	2.1.45	2.1.90	2.1.132
alpha	396	516	684	948
arm	-	-	492	576
i386	808	892	996	1100
m68k	2400	2500	1900	2100
mips	280	1100	1200	948
ppc	412	376	912	1300
sparc	780	1300	1300	1500
sparc64	-	756	1300	1500
total	5000	7200	8600	9800

表に見るように、linux-2.1シリーズでは前期にSPARC64用のコードが、中期にARM用のコードがソースツリーにマージされ、Linuxの特徴のひとつとしてよくあげられる「上はスパコンから下は組み込みまで」の対応は、この時期に実現したと言えそうです。

NFSパフォーマンスの改善

linux-2.1シリーズでは前節で紹介した対応アーキテクチャの増加だけではなく、さまざまな部分の性能改善にも取り組んでいます。

その一つがNFS（Network File System）の性能問題です。NFSはUnix系OSで広く利用されているファイル共有手法で、Linuxでも1.xの時代から使えたものの、商用UNIXやBSD系UNIXに比べると性能が悪く、特に書き込み性能が悪いことが問題視されていました。

Linuxの開発者たち、特にネットワーク回りの開発者たちはそのような批判に発奮し、linux-2.1シリーズでネットワーク回りのコードを大きく改良しました。改良の成果は図2に示した倍以上に増大したnetディレクトリのサイズから見てとれるものの、その内容をより詳しく調べると以下のような結果になりました。

	2.1.0	2.1.45	2.1.90	2.1.132
802	40	288	292	292
appletalk	76	80	76	88
ax25	156	208	208	212
bridge	64	68	68	84
core	128	156	192	192
decnet	4	4	4	4
econet	-	-	-	28
ethernet	20	20	20	20
ipv4	680	788	992	1100
ipv6	4	328	368	408
ipx	68	68	72	92
irda	-	-	-	668
lapb	-	60	60	60
netbeui	-	32	32	-
netlink	-	-	26	32
netrom	104	100	100	104
packet	-	-	32	32
rose	-	124	120	136
sched	-	-	92	252
sunrpc	-	172	180	180
unix	44	52	52	52
wanrouter	-	40	40	40
x25	-	112	116	116
Total	1500	2800	3200	4200

この表で目を引くのは2.1.45あたりでマージされたsunrpcディレクトリです。このディレクトリにはNFSに必要なRPC（Remote Procedure Call）の機能が収められています。

linux-1.xではNFSデーモンはユーザ領域で起動され、クライアントからのリクエストに応じてカーネルにシステムコールを発し、必要なデータの読み書きを行っていました。しかし、この方法では充分なパフォーマンスが出せないと判断した開発者たちは、NFSデーモンをカーネル内部に取り込むことにしました。そのために必要になったのがカーネルにRPC機能を提供するsunrpcディレクトリです。

netディレクトリにsunrpcが追加されたのに合わせて、linux-2.1.45ではfsディレクトリにnfsdが用意され、実際のNFSデーモンはこのディレクトリのソースコードから作成されるようになりました。

こうしてNFS機能をカーネル内部に組み込んだ結果、評判が悪かったNFSのパフォーマンスも次第に改善し、linux-2.2の頃にはほとんど問題にならなくなりました。

NFSは元々UNIXワークステーションの草分けであるサン・マイクロシステムズが開発したファイル共有システムで、速度を重視してUDP上に実装したNFSv2と、信頼性を考慮してTCP上に実装したNFSv3の2つの規格がありました。NFSv2、NFSv3はUNIX系OSを中心に広く使われてきたファイル共有システムなものの、元々ローカルなネットワーク環境を前提にしていたため、ユーザ認証やセキュリティ機能が手薄でした。そのためNFSをインターネット経由でも利用できるように設計しなおしたNFSv4の規格がIETFを中心に策定されることになり、そのための開発環境にはLinuxが選ばれました。かつてNFSのパフォーマンス問題にイジめられてきたユーザからすると、LinuxがNFSの開発環境に選ばれるというのは隔世の感を禁じえないところです。

NFS関連以外にも、上表からはいくつか興味深い点が見てとれます。たとえば2.1.0では40Kバイトほどだった802ディレクトリが、2.1.45では6倍強の288KBまで増加しています。

802ディレクトリには、ローカルエリアネットワークの規格のうち、IEEE802で定めているデータリンク層と物理層を扱うためのコードが集められており、伝統的なTCP/IPのネットワークスタックをOSI的な階層モデルに整理し直そうという意図が伺えます。

またipv4ディレクトリのサイズも倍近くまで増大すると共に、別途Usagiプロジェクトで開発されていたIPv6用のコードがマージされ、IPv6にも正式に対応するようになりました。加えて、ユーザ領域のソフトウェアがカーネル内部のネットワーク関連の情報にアクセスするためのnetlinkインターフェイスなども追加され、ネットワーク回りのコードはlinux-2.1シリーズで全面改訂されたと言えそうです。

SMPのパフォーマンス改善

もうひとつ、開発者たちがlinux-2.1シリーズで取り組んだのはSMP（Symmetric Multi-Processing）性能の改善です。前回紹介したように、Linuxは1.3の時代からSMPに対応してはいたものの、当時の実装はいわゆるBKL（Big Kernel Lock）と呼ばれる、「⁠あるカーネルがカーネルモードに入っている間は他のカーネルはカーネルモードに入れない⁠」⁠、という単純な形を取っていました。このような実装でもCPUが2つになった程度ならそれなりに性能は上がるものの、4CPUや8CPUの環境では性能向上が頭打ちになってしまいます。

カーネル開発者たちがこの問題を解決するために採用したのは、spinlockと呼ばれるスレッド単位で排他制御する方法です。BKLではカーネル単位で排他制御するため、1つのカーネルがメモリや周辺機器を利用している間は、他のカーネルはカーネルモードには入れません。一方、spinlock方式ではカーネルが実行する処理単位（スレッド）ごとにspinlock()を呼び出してリソースをロックし、必要な処理が終ればunspinlock()でリソースを解放する、という方法を取るので、スレッドレベルでの競合が無ければ、複数のカーネルがメモリと入出力機器を同時に操作する、ということも可能になります。

これは言葉で言うのは簡単なものの、実際に実装するためにはカーネルのソースコード全体に渡って処理単位を整理し直し、適切な排他制御用のコードを追加する、という膨大な作業が必要になります。

Linuxの開発者たちがこの膨大な作業に立ち向かっていった過程をソースコードから眺めてみましょう。

まず、linux-2.1.0では"spinlock"という言葉は一部のヘッダーファイルやドキュメントにしか出てこず、実際には使われていませんでした。

$ find linux-2.1.0 -type f -a -exec grep -i spinlock {} \; -print
extern __inline__ void prim_spin_lock(struct spinlock *sp)
extern __inline__ int prim_spin_unlock(struct spinlock *sp)
extern __inline__ int prim_spin_lock_nb(struct spinlock *sp)
...
linux-2.1.0/include/asm-i386/locks.h
extern inline volatile smp_initlock(void *spinlock)
        *((unsigned char *) spinlock) = 0;
linux-2.1.0/include/asm-sparc/smpprim.h
volatile unsigned long smp_invalidate_needed;           /* Used for the invalidate map that's also checked in the spinlock */
...
'hlt' instructions and release the spinlock soon. Using 'hlt' is even more 
outside of (and by) the spinlock and message code. Amongst other things 
linux-2.1.0/Documentation/smp.tex

ソースコード全体を調べても、spilockという言葉は24回しか出てきません。

$ find linux-2.1.0 -type f -a -exec grep -i spinlock {} \;  | wc -l
24

一方、linux-2.1.45になるとspinlockという言葉はソースコード全体で203回使われていて、カーネルのスケジューラやfork回りで実際に使われ始めていました。

$ find linux-2.1.45 -type f -a -exec grep -i spinlock {} \; -print
 * A simple spinlock to protect the list manipulations
spinlock_t inode_lock = SPIN_LOCK_UNLOCKED;
linux-2.1.45/fs/inode.c
#include <asm/spinlock.h>
linux-2.1.45/fs/binfmt_misc.c
#include <asm/spinlock.h>
spinlock_t scheduler_lock = SPIN_LOCK_UNLOCKED;
static spinlock_t runqueue_lock = SPIN_LOCK_UNLOCKED;
static spinlock_t timerlist_lock = SPIN_LOCK_UNLOCKED;
spinlock_t tqueue_lock;
linux-2.1.45/kernel/sched.c
...

linux-2.1.90になるとspinlockはソースコード中に312回出てきて、それぞれのCPU固有のコードでも使われるようになります。

$ find linux-2.1.90 -type f -a -exec grep -i spinlock {} \; -print
...

#include 
void _spin_lock(spinlock_t *lock)
void _spin_unlock(spinlock_t *lp)
linux-2.1.90/arch/ppc/lib/locks.c
static spinlock_t regdump_lock = SPIN_LOCK_UNLOCKED;
                extern spinlock_t scheduler_lock;
linux-2.1.90/arch/sparc64/kernel/process.c
...
spinlock_t irq_controller_lock;
linux-2.1.90/arch/arm/kernel/irq.c
#include <asm/spinlock.h>
linux-2.1.90/arch/arm/kernel/traps.c
...

さらにlinux-2.1.132になると、spinlockはソースコード中の710ヵ所に出てきて、ネットワークカードやSCSIアダプタ用のドライバも対応するようになっていました。

$ find linux-2.1.132 -type f -a -exec grep -i spinlock {} \; -print
...
#include <asm/spinlock.h>
        spinlock_t lock;
        /* Set the spinlock before grabbing IRQ! */
        ((struct el3_private *)dev->priv)->lock = (spinlock_t) SPIN_LOCK_UNLOCKED;
linux-2.1.132/drivers/net/3c509.c
#include <asm/spinlock.h>
        spinlock_t lock;
linux-2.1.132/drivers/net/plip.c
 *   0.6  05.04.98  add spinlocks
linux-2.1.132/drivers/net/hamradio/hdlcdrv.c
   1998-10-21   Postponed the spinlock changes, would need a lot of
linux-2.1.132/drivers/net/hamradio/scc.c
#include <asm/spinlock.h>
        spinlock_t lock;
        sp->lock = (spinlock_t) SPIN_LOCK_UNLOCKED;
linux-2.1.132/drivers/net/eepro100.c
...
#include <asm/spinlock.h>
linux-2.1.132/drivers/scsi/eata_pio.c
 *  Converted cli() code to spinlocks, Ingo Molnar
#include <asm/spinlock.h>
   * We need a spinlock here, or compare and exchange if we can reorder incoming
    /* The detect routine must carefully spinunlock/spinlock if 
       spinlock as well.
       spinlock. For the time beeing let's use it only for drivers 
     * FIXME(eric) put a spinlock on this.  We force all of the devices offline
linux-2.1.132/drivers/scsi/scsi.c
...

もっとも、中には

* The spinlock is silly - we should really lock more of this
* is around this - scsi_sleep() assumes we hold the spinlock.
linux-2.1.132/drivers/scsi/sr_ioctl.c

みたいなコメントが引っかかっていることもあって、必ずしも全ての開発者がspinlockを使う方針に賛同していたわけではなさそうです。また、spinlockへの対応は2.1シリーズで完成したわけではなく、この後、長い時間をかけて少しずつ対応が広まってゆくことになります。

以上紹介してきたように、linux-2.1シリーズは対応ハードウェアの増加だけでなく、ネットワーク関連コードの改訂やよりよいSMP対応に向けたロック粒度の細分化など、商用UNIXに求められるスケーラビリティ強化のためにソースコードの全面的な見直しを行なった時期と言えそうです。

これはソースコードそのものとは関係ありませんが、誰がどの部分を担当しているかを示すMAINTAINERSファイルのdiffを見ていると、linux-2.1シリーズの間でLinusさんの状況が変わっていることに気付きました。

$ diff -u linux-2.1.{0,132}/MAINTAINERS 

-REST:
+THE REST
 P:     Linus Torvalds
-S:     Buried alive in email
+S:     Buried alive in diapers

2.1.0のころは「メールの山に生き埋め」だったのが、2.1.132では「オムツの山に生き埋め」だそうで、ちょうど2.1シリーズのころ、Linusさんに長女のPatriciaちゃんが生まれたんだったなぁ……、と思いだしました。その彼女も去年の9月に大学に進学し、デューク大学でコンピュータ工学を学んでいるそうです。

時の流れの早さを改めて感じると共に、それだけの期間、休むことなくLinuxの開発を主導してきたLinusさんの熱意と努力に改めて感心した次第です。