Plan 9カーネルがIPパケットをどうやってルーティングしているか調べた。Plan 9のネットワークプログラミングは少し癖があるので、まずカーネルが提供するファイルの使い方を整理する。
使い方
Plan 9でネットワークプログラミングを行う場合、一般的には/net以下のファイルを読み書きすることになる。例えばIPアドレスを設定する場合、/net/ipifc/cloneをopen(2)してaddコマンドを書き込むことで行う。
% echo add 192.168.1.3 255.255.255.0 >/net/ipifc/clone
追加したIPアドレスごとに、/net/ipifc以下に数字だけのサブディレクトリが作られる。/net/ipifc/0/localファイルを読むと、設定したIPアドレスを取得できる。他にも状態を取得するファイルなどが存在する。
/net/iprouteを読むと、現在のルーティングテーブルが読める。当然だけど上で追加したIPアドレスも含まれる。
% cat /net/iproute 0.0.0.0 /96 192.168.1.1 4 none - 192.168.1.0 /120 192.168.1.0 4i ifc - 192.168.1.0 /128 192.168.1.0 4b ifc - 192.168.1.3 /128 192.168.1.3 4u ifc 0 192.168.1.255 /128 192.168.1.255 4b ifc - 127.0.0.0 /104 127.0.0.0 4i ifc - 127.0.0.0 /128 127.0.0.0 4b ifc - 127.0.0.1 /128 127.0.0.1 4u ifc - 127.255.255.255 /128 127.255.255.255 4b ifc - 255.255.255.255 /128 255.255.255.255 4b ifc -
/net/iprouteにaddコマンドをwrite(2)すると、スタティックルートを追加できる。また、デバッグ機能もあって、ルーティングテーブルにrouteコマンドを書くと、宛先へのルートを出力してくれる。
% echo add 192.168.10.0 255.255.255.0 192.168.1.1 >/net/iproute % echo route 8.8.8.8 >/net/iproute
パケットを送る場合は、/net/udp/cloneや/net/tcp/cloneをopen(2)すると、openしている間は<n>ディレクトリが作られるので、/net/udp/<n>/ctlに宛先などをwrite(2)して*1/net/udp/<n>/dataに送りたいデータをwrite(2)する。
ソースコードを追う
大まかな使い方をみたので、続けてカーネルではどう扱われているかを調べる。以下では都度ソースコードを引用しているが、これらは必要なところを抜粋しているもので、完全なリストではない。また、ソースコードの場所は特に明記しない限り/sys/src/9/ipからの相対パスを使う。
カーネルの動作を追うにあたって、重要なデータ構造があるので先にそれを眺める。
9Pセッションの扱い
カーネルの中では、9PセッションはおよそChan構造体で管理されている。Plan 9カーネルは9Pクライアントの側面を持ち、同時に9Pサーバでもあるので少し表現が難しい。
struct Chan {
ulong dev;
Qid qid;
};
devは、カーネル内部に存在するipfsという配列のインデックスになっている。ipfsはユーザによってattach(5)されたIPプロトコルスタックの配列で、#I0, #I1などIPプロトコルスタック(devipと呼ばれる)を9Pでattachすると、カーネル内部のipfsにFs構造体が追加される。この処理はdevip.cのipattachが行う。attachが終わると、以降の9Pセッションで使うための、devとqidなどが初期化されたChan構造体を得る。
qidはunique idの略で、9Pにおいて特に重要な値となる。qidは9Pサーバ上のファイルを指し、名前の通りファイルサーバ上で一意となる。9Pセッションではqidを使ってopen(5)やread(5)を行うことになる。Unixのinodeと似ているが、qidにはファイルのバージョンも含まれる。
ipfs配列
ipfsはユーザによってattach(5)されたIPプロトコルスタックの配列と書いたが、具体的にどういった値を扱うのか見ていく。
enum { Maxproto = 20, Nfs = 128 }; struct Proto { int x; /* protocol index */ int ipproto; /* ip protocol type */ Conv *conv[]; /* array of conversations */ }; struct Fs { int dev; Proto *p[Maxproto+1]; }; Fs *ipfs[Nfs];
Proto構造体
ipfsは#I0などdevipをattach(5)したものなのでFsがそのまま#I<n>に対応するが、Protoとは何か。これは#I0/tcpや#I0/udpなど、/netディレクトリ以下にある各種プロトコルが対応する。#I0/ipifcなどPlan 9独自なものも含まれる。Protoのメンバー変数pは、attach(5)した時に初期化され、ユーザ操作によって増減することはおそらくない。
static Chan* ipattach(char *spec) { Chan *c; dev = atoi(spec); ipgetfs(dev); c = devattach('I', spec); mkqid(&c->qid, QID(0, 0, Qtopdir), 0, QTDIR); c->dev = dev; c->aux = newipaux(...); return c; } static Fs* ipgetfs(int dev) { /* ipprotoinitは9/port/mkdevcで生成したCのコードに含まれる */ /* 実態はudpinit, tcpinitなど各種プロトコルのinit関数 */ extern void (*ipprotoinit[])(Fs*); if(ipfs[dev] == nil){ f = smalloc(sizeof(Fs)); ip_init(f); arpinit(f); ... /* プロトコルごとにProtoを初期化してf->pに追加する */ for(i = 0; ipprotoinit[i]; i++) ipprotoinit[i](f); ipfs[dev] = f } return ipfs[dev]; }
Conv構造体
最後に、Protoのメンバー変数にconvというConv構造体の配列がある。これはざっくり言ってしまうと、現在アクティブなコネクションを表し、ユーザ操作によって増減する。
struct Conv { int x; /* conversation index */ Proto *p; uchar laddr[IPaddrlen]; /* local IP address */ uchar raddr[IPaddrlen]; /* remote IP address */ ushort lport; ushort rport; Queue *rq; /* queue data waiting to be read */ Queue *wq; /* queue data waiting to be written */ void *pctl; /* protocol specific stuff */ Route *r; /* last route used */ };
例えば/net/udp/cloneをopen(2)したとき、いろいろ経てカーネルのipopenに処理が移る。ここでFsprotoclone関数により、新しいConv構造体がProtoのconv配列に追加される。
static Chan* ipopen(Chan *c) { Proto *p; Conv *cv; Fs *f; f = ipfs[c->dev]; switch(TYPE(c->qid)){ case Qclone: p = f->p[PROTO(c->qid)]; cv = Fsprotoclone(p, ATTACHER(c)); mkqid(&c->qid, QID(p->x, cv->x, Qctl), 0, QTFILE); break; } ... }
以後、このChanが継続して利用される。ここで作られたConvは、close(2)が呼ばれたときにipcloseによりcloseconvが呼ばれて閉じる。
これまで出てきた構造体をユーザから見えるものに当てはめると
| 構造体 | 対応するファイル例 | メモ |
|---|---|---|
| Fs | /net, /net.alt | 実態は#I0, #I1... |
| Proto | /net/ipifc, /net/udp | |
| Conv | /net/udp/0, /net/udp/1 |
パケットを送出する場合
パケットを送出する場合に、カーネルではどう扱われるのか。
NICにIPアドレスを割り当てたとき
/net/ipifc/cloneへの書き込みはipifc.cのipifcctlに届く。addコマンドの場合は同ファイルのipifcaddに渡される。
static char* ipifcctl(Conv* c, char**argv, int argc) { Ipifc *ifc; ifc = (Ipifc*)c->ptcl; if(strcmp(argv[0], "add") == 0) return ipifcadd(ifc, argv, argc, 0, nil); } char* ipifcadd(Ipifc *ifc, char **argv, int argc, 一部省略) { Fs *f; Iplifc *lifc; f = ifc->conv->p->f; ... lifc = smalloc(sizeof(Iplifc)); ipmove(lifc->local, ip); ipmove(lifc->mask, mask); ...lifcの値を初期化... lifc->next = nil; ...ifc->lifcの末尾にlifcを追加... if(isv4(ip)) v4addroute(f, "ifc ", rem, mask, rem, Rifc); addselfcache(f, ifc, lifc, ip, Runi); if(isv4(ip) || ipcmp(ip, IPnoaddr) == 0){ bcast = (ipとmaskでブロードキャストアドレスを計算) addselfcache(f, ifc, lifc, bcast, Rbcast); bcast = (ipとmaskでネットワークアドレスを計算) addselfcache(f, ifc, lifc, bcast, Rbcast); addselfcache(f, ifc, lifc, (255.255.255.255), Rbcast); } }
色々やっているけど、ここでは以下の内容で簡単に覚えておくと良い。
- 自身のIPアドレスを設定
- ルーティングテーブルに
type = Rifcとして自身のルートを追加 - ルーティングテーブルに
type = Rbcastとしてサブネットを追加
ルーティングテーブルにスタティックルートを追加したとき
/net/iprouteにwrite(2)した場合のこと。上では簡単にしか書かなかったので、ここで詳しく読む。
ルーティングテーブルはプロトコルスタックごとに存在するので、Fs構造体にv4rootメンバー変数が用意されている。他にもIPv6の場合はv6rootが用意されているが、基本的には同じなのでここではIPv4だけをみていく。
#define Lroot 10 struct Fs { Route *v4root[1<<Lroot]; /* 1024個のルートツリー */ }; struct Route { RouteTree; V4route v4; }; struct RouteTree { Route *right; // Route.v4と比べて大きいアドレス(it > v4.address) Route *left; // Route.v4と比べて小さいアドレス(it < v4.endaddress) Route *mid; // Route.v4に含む(it >= v4.address && it <= v4.endaddress) uchar type; // Rv4 | Rifc | Rptpt | Runi | Rbcast | Rmulti | Rproxy Ipifc *ifc; ... }; struct V4route { ulong address; // (宛先アドレス&ネットマスク)の先頭アドレス ulong endaddress; // (宛先アドレス&ネットマスク)の最終アドレス uchar gate[IPv4addrlen]; // nexthop };
ところで、RouteのメンバーRouteTreeは型名だけ書かれている。Plan 9のCコンパイラは拡張されていて、Goの埋め込みと同じことができるようになっている*2。従って、Route *rという変数があれば、r->leftでRouteTreeのメンバー変数leftを扱える。
/net/iprouteへadd命令をwrite(2)した場合、文字列はそのままiproute.cのroutewriteに届く。ここでは書き込まれた文字列をパースして、ネットワークアドレス、ネットマスク、宛先アドレスをv4addrouteに渡す。
long routewrite(Fs *f, Chan *c, char *p, int n) { Cmdbuf *cb; cb = parsecmd(p, n); if(strcmp(cb->f[0], "add") == 0){ parseip(addr, cb->f[1]); parseipmask(mask, cb->f[2]); parseip(gate, cb->f[3]); v4addroute(f, tag, addr+IPv4off, mask+IPv4off, gate+IPv4off, 0); } } #define V4H(a) ((a&0x07ffffff)>>(32-Lroot-5)) void v4addroute(Fs *f, char *tag, uchar *a, uchar *mask, uchar *gate, int type) { Route *p; ulong sa, ea, m; int h, eh; m = nhgetl(mask); sa = nhgetl(a) & m; ea = sa | ~m; eh = V4H(ea); for(h = V4H(sa); h <= eh; h++){ p = allocroute(Rv4 | type); p->v4.address = sa; p->v4.endaddress = ea; memmove(p->v4.gate, gate, sizeof(p->v4.gate)); ... addnode(f, &f->v4root[h], p); } }
v4rootテーブル
v4addrouteはv4rootにルート情報を追加する。v4rootは全てのIPv4アドレスを1024分割して管理するテーブルで、IPネットワークアドレスのV4Hを計算して、該当するツリー全てに登録する。例えば0.0.0.0/0のマッチする範囲は0.0.0.0〜255.255.255.255なので全てのツリーに登録される。具体的にV4Hを計算してみると以下のようになる。
V4route r = {
.address = 0,
.endaddress = 0x07ffffff,
};
int sa = V4H(r.address) => 0
int ea = V4H(r.endaddress) => 1023
一方で192.168.1.0/24は192.168.1.0〜192.168.1.255の範囲なので、
V4route r = {
.address = 0xc0a80100,
.endaddress = 0xc0a801ff,
};
int sa = V4H(r.address) => a80100 => 84
int ea = V4H(r.endaddress) => a801ff => 84
他にも172.16.0.0/16の場合、
V4route r = {
.address = ac100000,
.address = ac10ffff,
};
となって、あとは同じなので省略するがv4rootの決まった位置に割りあげられる。なので上記の2つをルートに追加すると、カーネル内部ではこのようなツリーができる。
v4root[] = {
[0] = 0.0.0.0/0
[1] = 0.0.0.0/0
...
[84] = 0.0.0.0/0, 192.168.1.0/24
...
[1023] = 0.0.0.0/0
}
ルートを調べる場合は、宛先アドレスのV4Hを計算して該当するツリーだけ調べれば、ルート情報があれば見つかるし、ルートがなくても必ずデフォルトルートが選び出される。
パケットを送出するとき
/net/udp/<n>/dataに書き込むと9Pに変換されて、最終的にudp.cのudpkickへ書き込んだデータが届く。ここでヘッダなどを構築して、ipoput4に渡す。ここまでがUDPの責務で、ipoput4以降がIP層の責務となる。
ipoput4はip.cで実装されている。ipoput4は送出するNICを特定するためv4lookupを呼び出す。これはiproute.cで実装されていて、v4lookupはルートの追加でみたように、宛先アドレスのV4Hを計算して、対応するv4rootのツリーを探索する。
Route*
v4lookup(Fs *f, uchar *a, Conv *c)
{
Route *p, *q;
ulong la;
Ipifc *ifc;
la = nhgetl(a);
for(p=f->v4root[V4H(la)]; p;){
if(la >= p->v4.address){
if(la <= p->v4.endaddress){
q = p;
p = p->mid;
}else
p = p->left;
}else
p = p->left;
}
if(q){
if(q->type & Rifc)
gate = (q->v4.addressの値)
else
gate = (q->v4.gateの値)
ifc = findipifc(f, gate, q->type);
q->ifc = ifc;
}
return q;
}
ルートが定まれば(上のコードでif(q)のところ)パケットを送り出すべき宛先(nexthop)が得られるため、nexthopに対応するNICをfindipifcで探す。
これ以降もarpなど続くが、ルートを得る処理はここで終わり。Plan 9のIP関連コードのほとんどは/sys/src/9/ip*3にまとまっていて、全部で2万行程度なので読みやすくて非常に良い。