処理 - みる会図書館

1. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門定度か高いという点も見逃せません。自分でプログラムを作成した場合には、プログラム中に誤りが含まれてしまうこともあるでしよう。もちろん、 UNIX のコマンドだからといってバグがまったくないわけではありませんが、いきなり作成したプログラムにくらべれは少ないと考えてよいでしよう。また、巨大な入力が与えられた場合を考えてみてください。自分でプログラムを作成する場合、もっとも簡単な方法は、メモリ上にファイルの内容をすべて手寺しながら逆順に出力することになるでしようが、メモリ上に一尉寺できないほどの入力が学えられたらどうなるでしよう。 sort コマンドはこのあたりにもちゃんと対処してくれます。これを実際にプログラムするとなると、ちょっと面倒です。安定したプログラムを簡単に作ることができるのも、 UNIX コマンドを組み合わせるガ去の利点の 1 っといえるでしょう。うまく UNIX コマンドを組み合わせられるように日頃からどのようなコマンドカ甘是供されているのかを調べたり、 man コマンドを利用したり Web で検索するなどして、必要な機能をもつコマンドを上手にみつけられるようにしておくことが大切です。これは、アルゴリズムをたくさんみておく理由と共通していますれもちろん、この場合にもプログラムを和実行する必要があるかや、プログラムに対する入力はどの程度大きいのかを考慮すべき点は変わりません。 UNIX のコマンドは単体でみればかなり高速に重川するプログラムですが、あくまでも汎用のプログラムですから、間題領域に合わせて作成した専用のプログラムのほうか高速に処理できると考えてよいでしよう。アルゴリズムも、間題に合わせてチューニングできるのであれは、そのはうか高速に重川乍させることができます。入力が巨大であったり、プログラムの実行回数か膨大な場合には、専用のプログラムを作成する去も忘れてはいけません。その場合には、自分でアルゴリズムを尺しなけれはなりません。「作ってみたのはよいけれど、 UNIX コマンドを組み合わせたほうか高速だった」というのではちょっと寂しいですよね。日頃から手間を見積もる癖をつけておくと、プログラムを作るほうか得なのか、コマンドを組み合わせるはうがよいのかという勘がだんだん働くようになります。うまく見積もれるようになれば、けっきよくは処理の結果を早く手にすることができるわけです。 UNIX MAGAZINE 2003.5 お勧めなのは、とりあえす既存のコマンドでうまく処理できるものがないかを調べるガ去です。間題にはさまざまなものがあると思いますが、それらの間題の本質的な部分は探索であったり、整列であったり、基本的な操作であることがはとんどです。この部分をうまく既存のコマンドで処理できるように、前処理や後処理を付け足すのです。前処理や後処理では、間題領域に特化した処理が必要になることが多いので、 awk や PerI 、 Ruby などのちょっと賢いスクリプト言語を使うことも多いでしようし、 C 言語で書くこともできます。これらを組み合わせて、とりあえず正しく動作するプログラムを作ってしまいましよう。そのプログラムを使っていて「どうしても遅い」ということになれば、それから改良を始めてもよいのです。プログラムを釧乍させながら改良をおこない、最終的に早く答の出たほうを採用してもよいでしよう。計算機のパワーを無駄に使っているようにもみえますが、山も匠の言 1 算機は強力になっていますし、個人用の引算機カ甘是供されている環竟も多いと思います。どうせ余っているパワーであれはどんどん使うべきです。引・算機はうまく活用してください。 ☆ 今月は、前回までの、、探索 " に続いて、文字列ク架索という特定のアプリケーションを対象とした探索問題をみてきました。具イ勺には、力すくのガ去に始まり、 Knuth- Morris-Pratt のアノレゴリズム、 Boyer-Moore のアノレゴリズム、 Rabin-Karp のアルゴリズムを紹介しました。先人たちは、文字列の探索に関してもさまざまな工夫を凝らし、高速に動作するアルゴリズムをいくつも考え出していることが分かっていただけたと思います。また、実際にプログラムを作成する際に注意してはしい点もいくつカ呂介しました。けっきよくのところ、重要なのは結果が早く手に入ることです。どうするのがよいかをよく考えてプログラミング ( コり組んでください。 ( いまいすみ・たかし千葉大学 ) 101

2. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門り返します。もう文字列か残っていないという状態になったときには、目自勺の探索文字列が含まれなかったことになるため、文字列が存雀しないことを示す一 1 を返します。 while (i く = tlen) { if (hs (t) return 」 ; ()t + ASIZE * PRIME * b) % PRIME; ()t * ASIZE + t [ i + + ] ) ht return ー 1 ; % PRIME; ハッシュ値の更新においては、すでに計算してあるハッシュ値から、ハッシュ値の引算に関与・しなくなる先頭の文字 ( 新 ) による景彡響をなくすために減算し、全体を ASIZE 倍したあとに新たな末尾の文字 (t[i]) の景斧加えるために加算しています。最初の行の計算で ASIZE x PRIME を加えているのは、その直後の減算により全体が負の数になってしまうのを避けるためです。残念ながら、負の数の値に対する剰余演算の結果が正の数になる処理系と負の数になる処理系があるため、どちらの処理系でも正しく動作するようによけいな値を加えています。ここで加えた値は、最後に剰余演算によって消えてしまうので、この値を加えたためにおかしくなるようなことはありません。こで作成したプログラムは、 0 ( m 十れ ) で動作します。ところが、厳密にはこのプログラムは正しくありません。というのも、ハッシュ値カ尊しい場合に文字列が一一致していると判断していますが、これはかならずしも真ではありません、で 1 ・算しているのはあくまでハッシュ値ですから、ハッシュの衝突か起きる場合もあります。そのため、実際にはハッシュ値か等しいときにかならす文字列自身の上交をおこなう必要があります。文字列の上師交をおこなって等しいときにのみ、探索文字列を検出したとするのです。ノ、ツシュ値カ尊しいときに文字列を石忍するコードを付けると、最悪の場合の引算量は 0 ( m れ ) となってしまいます。これは、すべての部分文字列のハッシュ値か 1 司し値になった場合を考えてみれは分かると思います。すべての部分文字列を調べるために広そのそれぞれについて文字列自身か等しいかどうかを調べるために m の手間がかかるので、けっきよく 0 ( れ m ) となってしまいます。しかし実 98 際には、さきはども述べたように PRIME を大きな値にできるため、ハッシュの衝突はほとんど発生しないようにすることができます。したがって、実用的には 0 ( rn 十れ ) と考えても間題はありません。実際のプログラミングにあたってこれまでみてきたように、同じ問題を鮹夬するにも複数の去があります。実際に間題を解決するためには何をすれはよいのでしようか。最初にやるべきことは間題の整理問題の整理と分析ーロに探索といっても、前回までにとりあげた、あるデータ集合のなかから単一のデータを探しだす方法と、今回紹介した文字列のなかから探索文字列を探しだす方法では、利用するアルゴリズムか異なります。文字列のなかからある探索文字列を探しだすために普通の探索のアルゴリズムを使おうとすれは、探索文字列の長さ倍の領域や時間がかかるでしよう。というのも、通常のでは、要素がキーの値と等しいかどうかは 1 回の上交で判定できるという前提て考えてきました。しかし文字列探索の場合には、それぞれの文字の上交に対して手間を言算します。単純に考えても、上交のために探索文字列の長さ倍の手間がかかってしまうはすです。領域についても同様です。文字列として捉えれば途中のどこから始まっても同しだということが分かりますが、通常の探索ではそれぞれのデータが独立して存在しているものと仮定しています。すると、なえられた文字列から取り出すことが可能な探索文字列と同じ長さのすべての文字列か存在するものとして処理を進めることになるでしよう。この場合には、領域カ甘架索文字列の長さ倍必要になってしまうわけです。間題を分析して、どのような処理が可能かを検詞することも重要になります。探索が必要となる場面は、これまでみてきたようなデータの探索や文字列架索といった基本的な問題だけとはかぎりません。一見すると、もっと複雑にみえるような間題の場合もあります。たとえは、 DNA のなかから特定の遺伝子の部分を抽出 UNIX MAGAZINE 2003.5

3. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門するという間題を考えてみましよう。この間題は、きわめて長い DNA の塩基配列のなかから、特定の配列となっている部分を抽出する間題と捉えることができます。このような見方をすると、この間題は文字列探索とよく似ていることが分かります。したがって、 BM 法のような高速な文字列探索アルゴリズムを利用すれはよさそうだと予想がつきます。アルゴリズムを学ふ際には、ます探索や整列などの基本アルゴリズムをいくつも教え込まれます。ここで紹介されたアルゴリズムをそのまま適用できる間題はそれほど多くないでしようが、これらを変形することで与・えられた出題に適用できるかもしれません。しかし、基本アルゴリズムを知らなけれはどう応用するかも分かりません。そのためにも、いろいろなアルゴリズムをみておくべきです。重要なのは、アルゴリズムの田を完全に理解することではありません。どのようなアルゴリズムがあり、それぞれがどのような特生をもっているかを知ることが大事なのです。しかも、同じ問題に対するアルゴリズムでもさまざまな持匪があるのは、すでにみてきたとおりです。対処したい間題に適した特性をもつアルゴリズムを選択することで、効率のよい処理がおこなえます。これまで、同じ間題に対するアルゴリズムを、ややくどいくらいにいくつも紹介してきたのはそのためです。さまざまなアルゴリズムを紹介する理山はもう 1 つあります。前回みたように、アルゴリズムにはそれなりのパターンがあります。実際のアルゴリズムを多数みることにより、アルゴリズム構築の際にそれらを応用できるようになるからです。もちろん、アルゴリズムの言手法としてはうリ統治法や重加鮖 T 画法など、いくつかの知られた手法があります。しかし、それを直接学ぶ前に、実際のアルゴリズムをみることで感 : に理解してもらえるのではないかと思います。アルゴリズムの選択と手間の見積りアルゴリズムを〕尺する理山は、効率よく処理したいからでしよう。この点でも考えてはしいことがあります。最終的な出力を得るのに、手作業であれは 10 分かかるとします。これを言 t 算機て処理す川ま、 12 秒て終るとしましょう。これだけをみると、明らかに言 fr 算機て処理したはうがよさそうですが、本当にそうでしようか。 UNIX MAGAZINE 2003.5 実際に言 fr 算機で処理するまでには、プログラムを作成する必要があります。ここではそのための手間をまったく考慮していません。実際に動作するプログラムか完成するまでに 30 分かかるとす川ま、この処理を計算機でおこなうと、全体として手竹喋の場合よりも長い時間がかかってしまうのです。つまり、最終的な出力をもっとも早く得られるのは、手作業で処理する場合だということになります。このような場合に、無理に言 fr 算機で処理をしようとするのは賢明ではありません。ところが、これは処理を 1 度だけおこなうときの話です。同様な処理を 5 回おこなわなけれはならないケースではどうでしようか。手竹でおこなう場合、 12 する場合には、となり、 50 分の時間がかかります。一方、計算機で処理 10 x 5 = 50 60 30 十一一 x 5 = 31 99 行するかによります。もちろん、プログラムの作成を始めだけの効果か得られるかどうかはそのプログラムを和徊実とができます。しかし、本としてみた場合、実際にそれムを熟考することで、より効率のよいプログラムを得るこ多くの場合、アルゴリズムを注意深ぐ尺し、プログラることができるのです。となり、全体としてほば半分の時ですべての処理を終え 60 60 十一一 x 1000 = 110 て倍の時間、つまり 60 分かかるとしても、ログラムを作成するのに、さきほどのプログラムとくらべは、 3 秒で処理できるようになるかもしれません。このフグラムを改良してより効率のよいアルゴリズムを〕尺すれとなり、 4 時間近くかかってしまいます。しかし、プロ 60 30 十一一 x 1000 = 230 12 算では、さなけれはならないとしたらどうでしよう。さきはどの計この回数がさらに増えて、同し作業を 1 , 000 回繰り返早く仕事を終えることができます。ケースでは、明らかに算機て処理したはうか、全体としてとなり、 31 分ですべてを処理することができます。この

4. UNIX MAGAZINE 2003年5月号

連載 / IPv6 の実装ー⑩ 図 3 key-checktunnelsanity() 関数 954 if ( !key_checktunnelsanity(sav, AF_INET6, (caddr_t)&src_sa, 955 961 (caddr-t)&dst-sa) ) { goto fail; 962 } 内側の IP ヘッダにはなんの関連もないため、 M-AUTH- IPHDR と M-AUTHIPDGM フラグを無効にしておきます。内側の IP ヘッダの認証は、内側の IP バケットが処理される過程で実行されます。もちろんその際、内側の IP バケットは認証ヘッダをもっていなければなりません。 973 key_sa_recordxfer(sav, m) ; SAD 工ントリには有交丿期限があります。長い期間使われていなかったり、頻繁に利用された SAD 工ントリは、セキュリティを向上させるために更新すべきです。 key- sa•ecordxfer() は、 SAD 工ントリの利用時刻や通信に利用された回数、通信量などの情報を更新します。 key- 974 if (ipsec—addhist (), IPPROTO-AH, sa•ecordxfer() の言岩田については彳あします。 992 ~ 997 行目で、内側の IP / ヾケットを IP ノヾケットの入力キューに追加します。ここでキューに追加されたパケットは、ふたたび ip6-input() て処理されます。 999 1000 1004 m = NULL ; schednetisr (NETISR—IPV6) ; IPPROTO_DONE; nxt 975 977 978 } spi) ! = 0 Ⅱ ipsec—addhist (), IPPROTO—IPV6, goto fail; すでにみてきたように、 IP セキュリティの処理では、処理の過程でヘッダを削除することがあります。トンネルモードの処理では、外側の IP ヘッダと言 E ヘッダか削除されます。 ipsec-addhist() は、 IP セキュリティの処理により削除されたヘッダを言当求します。なお、 ipsec-add- hist() は、引数としてプロトコル番号などを渡せるように言されていますが、点では利用されていません。この情報は、トンネルモードの内側のバケットがふたたび ip6-input() て処理されるときに使われます。 ip6än- put() では、処理中のバケットがネットワーク・インターフェイスから入力されたものか、トンネル経山て再入力されたものかを区別しなければならない場合があるからで 1005 } else { バケットの処理が完了したので、 999 行目で m を NULL に設定します。 schednetisr() を呼び出すことで、 997 行目でキューに追加したバケットに対して ip6-in- put() の呼出しがスケジュールされます。 1 , 005 行目以降は、を行で説明するトランスポート・モードの処理になります。トランスポート・モードの処理 1 , 005 ~ 1 , 066 行目はトランスポート・モードの処理です。 1016 prvnxtp = ip6-get-prevhdr (), off) ; 1017 *prvnxtp = nxt ; トランスポート・モードでは、認証ヘッダを削除したあと、彳茫、、ツダの処理へ進みます。 1 , 016 行目まで処理が進んだ段階では、認証ヘッダの直前のヘッダの次へッ刀直が言正へッダになっています。これから正へッダを削除するので、認証ヘッダに設定されている次へッダ値を、認証ヘッダの直前のヘッダの次へッ刀直に設定します。 ip6- get-prevhdr() は、オフセット。仕て示されるヘッダの直前に配置されているヘッダの次へッダ値フィールドへのポインタを返す関数です。す。 992 995 996 997 if (IF-QFULL(&ip6intrq) ) { goto fail; IF_ENQUEUE (&ip6intrq, m) ; 1019 1025 1026 1027 1028 ip6 = mtod(), struct ip6—hdr * ) ; ovbcopy ( (caddr—t) ip6 , ( (caddr—t) ip6) + stripsiz, 0ff) ; m—>m_data 十 = stripsiz; m—>m_len stripsiz; m—>m—pkthdr. len StriPSIZ; UNIX MAGAZINE 2003.5 71

5. UNIX MAGAZINE 2003年5月号

連載 / lPv6 の実装ー⑩ 図 4 トランスポート・モードでの認証ヘッダの削除ァータバケット先頭認証ヘッダ削除前旧ヘッダバケット先頭認証ヘッダ削除後旧ヘッダ 1 , 069 行目では、ヘッダ処理の過程で変化した mbuf ポインタを更新します。認証ヘッダ上書き旧ヘッダ 1071 1074 1075 1077 if (sav) { key-freesav(sav) ; 1 , 019 ~ 1 , 028 行目で認証ヘッダを削除します。実装 - E かたちになっています ( 図 4 ) 。は、認証ヘッダより前のデータを認証ヘッダに上書きする 1057 1059 ip6 = mtod(m , struct ip6_hdr * ) ; ip6—>ip6-p1en = htons (ntohs (ip6—>ip6-p1en) stripsiz) ; バケットのう巨頁アドレスか変わっているため、 1 057 行目でポインタ変数 ip6 を更新します。また、認証ヘッダを削除したことによって IP バケットのペイロード長も短を更新します。くなりますから、 1 , 059 行目で IP ヘッダのペイロード長 1061 1062 1064 1065 1066 } key—sa—recordxfer(sav, m) ; if (ipsec—addhist (m , IPPROTO—AH , spi) ! = 0 ) { goto fail; SAD 工ントリは参照カウンタをもっています。 key- allocsa() の実行時にこの参照カウンタか増えているので、言正へッダの処理カ鮗了し、 SAD 工ントリを利用する必要がなくなった点で key-freesav() を使って解放します ( 1 , 071 ~ 1 , 075 行目 ) 。最後に、次に処理するプロトコル番号 ( 次へッダ仙を、呼出し元の ip6-input() べ区します ( 1 , 077 行目 ) 。セキュリティ・データベースの処理証ヘッダの入力処理自体に難しい点はありません。基山い本的にはバケットのチェックサムを計算するだけですから、糸響各制征卩ヘッダや断片ヘッダなどよりも処理は簡単です。むしろ、ヘッダの処理に必な周辺データベースとの関係を理解するほうか大変です。以下では、認証ヘッダの入力処理で用いられるセキュリティ・データベース関連の関数を解説します。 SAD 工ントリの検索と解放 IP セキュリティの処理では、頻繁に SAD 工ントリの清報を参照します。 KAME ではカーネル内から容易に SAD 工ントリにアクセスできるようにいくつかの関数を用意しています。以後、とくに明記しないかぎりコードトンネルモードのときと同様、 SAD 工ントリの利用時刻や利用回数、通信量を key-sa-recordxfer() で更新します。また、トランスポート・モードの処理の過程て認証ヘッダか削除されているので、 ipsec-addhist() でヘッダの削除を言求します。 1068 *offp = 0ff ; *mp = m ; 1069 1 , 068 行目で後続ヘッダへのオフセットを史新します。ただし、実際には。仕の値は ah6-input() か呼び出されたときから変化していません。トンネルモードの場合は、すでに処理か完了しているのて続くへッダを処理する必要はありませんし、トランスポート・モードの場合は認証ヘッダを削除してしまったので、もともと認証ヘッダか配置されていたオフセットに次に処理されるべきへッダが移動し 72 てきているからです。は key. c のものです。 955 struct secasvar * 956 key—allocsa(family, src , dst , proto , spi) 957 958 959 960 { u—int family, proto; caddr_t src , dst ; u—int32—t spi ; 956 行目の key-allocsa() は、引数て指定した条件に適合する SAD 工ントリを secasvar 構造体のポインタで返します。 key-allocsa() に指定する条件は次の 5 つです。・アドレス・ファミリー (family) UNIX MAGAZINE 2003.5

6. UNIX MAGAZINE 2003年5月号

tsort コマンドにはオフションがいくつか用意されており、いすれも依存関係の循環を検出したときの重川乍を制御するためのものです。ー 1 は、依存関係の循環を発見したときに、それらの循環のなかから最長のものをみつけるためのオプションです。 -d は、循環が発生した原因をより詳しく表示し、循環を解消する丁掛かりを提供します。最後の一 q は、上記の 2 つのオフションとは考え方が異なります。これは、循環があってもそれをエラーとして扱わすに処理を続けるためのオプションです。こで、 tsort コマンドの生い立ちを紹介しておきましよう。もともと、 tsort はライプラリに登録するファイルの順番を決めるために使われるコマンドでした。ライプラリへの追加はファイル単位でおこなわれます。このとき、ファイルに含まれる複数の関数はまとめて追加することになります。あるライプラリ関数をプログラムのなかて利用すると、その関数が含まれるファイルがライプラリ・ファイルから取り出され、プログラムのリンク時に結合されます。ここで問題となるのは、プログラムで用いられるライプラリ関数自身が、別のライプラリ関数を利用することがある点です。このような場合には、間接的に利用されるライプラリ関数もリンク時に結合する必要があります。これらの関数か同じライプラリに登録されているとき、間接的に利用するライプラリ関数のはうか現在処理している場所より後ろにオ内されていれは、ライプラリを一度処理するだけで必要な関数をすべて結合することができます。しかし、現在処理している場所よりも前にオ内されていると、もう一度ライプラリ全体を処理しなけれは結合できません。プログラムが printf 関数を利用する場合を考えてみましよう。 printf 関数は、内部で write 関数を呼び出しています。 libc ライプラリに printf 、 write の順にオ内されている場合、プログラム側で printf 関数が必要なときに libc ライプラリを前から順番に処理していってそれを結合します。この段階で write 関数も必要なことが分かりますが、そのまま libc ライプラリの処理を進めていけばこれも結合できます。一方、 write 、 printf の順に登録されている場合はどうでしよう。 libc ライプラリを処理していき、 printf 関数を結合するところまでは同じです。しかし、 write 関数が必要なことが分かった段階で、 libc ファイルの write 関数 114 か登録されている場所はすでに処理を終えているため、のまま libc ファイルの末尾まて処理しても write 関数を結合することはできません。けっきよく、もう一度 libc ライプラリを : 麪頁から処理しなおさなければなりません。このような条件下で、できるかぎり 1 回の処理でリンク作業を終らせるには、ライプラリ関数間の依存関係を抽出し、その関係がイ尉寺される順番でライプラリに登録すればよいでしよう。この順番を引算するために作られたのが tsort 関数です。現在はライプラリ内にインデックスが作成されているので、後ろに登録された関数から前に登録されている関数を呼び出せないといった制限はありません。したがって、 tsort 関数は当初の彳難リを終えたわけですが、コマンド自体は残り、オプションも当時の名残をとどめています。 -q オフションが作られたのは、ライプラリを構築する際にやむをえす循環か生じるような場合に、いちいち工ラーか報告されるのを避けるためでしよう。このオプションを指定すると、ライプラリに登録するファイルの順番を決める際に循環カ吽しても、エラーメッセージを表示しないようになります。 tsort コマンドでのテータベースの利用 tsort コマンドでは、入力として・与えられたグラフの情報をイ寺しておかなけれは、、出力を引算することができません。 tsort コマンドは、このグラフの情報を一尉寺するためにデータベースを利用しています。データベースを検索するときのキーになるのは、ノードの名前です。データベース検索の結果として得られるデータ構造には、ノードに必要帯に ( たとえば、そのノードから出ているアークの一覧など ) か含まれています。こて利用しているデータ構造は、もちろん構造体の形式で定義されています。しかも、あるノードから出るアークの数はあらかしめ決定できないため、データ構造としてはポインタ寺し、その先に複数のアークを登録できるようにしています。また、データ構造のなかにはノードの名前も含まれますが、これも長さによって実際に占める領域のサイズが変わります。こで扱うデータ構造は可変長のデータであつまり、り、固定長のデータを登録するデータベースには向いてい UNIX MAGAZINE 2003.5

7. UNIX MAGAZINE 2003年5月号

連載 / IPv6 の実装ー⑩ 図 2 反復攻撃を防ぐための情報の更新 0 & & sav—>replay) { if ( (sav—>flags & SADB—X-EXT-OLD) 910 911 913 914 if (ipsec-updatereplay(ntohl( ((struct newah *)ah)—>ah-seq) , goto fail ; sav) ) { 915 } 類できます。 1 つは個々のノードが 1 対 1 で IP セキュリティの機能を利用する場合で、トランスポート・モードと呼はれます。もう 1 つは、おもにネットワーク同士を安全に接続するために利用される場合て、、トンネルモードと呼はれます。トンネルモードでは、 2 つのネットワークの境界ルータ間でのみ IP セキュリティの処理をおこない、それぞれのネットワーク内のノードは通常どおり通信します。境界ルータは、バケットを対向ネットワークに向けトンネル技術を使って IP'NP ケットの外て中幻医する際に、側に別の IP ヘッダを追加し、そのヘッダに対して IP セキュリティの処理を実行します。 942 943 945 946 947 } m = m—pullup(), sizeof(*ip6) ) ; goto fail; 918 920 921 923 924 if (sav—>flags & SADB—X-EXT-OLD) stripSIZ } else { stripsiz sizeof (struct SiZ1; sizeof (struct SiZ1; newah) + 948 ip6 = mtod(), struct ip6—hdr * ) ; 935 ~ 948 行目で外側の IP ヘッダを削除しています。 935 行目で flowinfo の値を保存している理由は、 ECN (Explicit Congestion Notification) [ 2 ] 関里の処理のためです。 936 行目で、入力した IP バケットの先頭から認証ヘッダの末尾までを切り詰めます。 937 ~ 947 行目では、 mbuf がすくなくとも IP ヘッダぶんの長さを連続したメモリ領域にイ尉寺していることを確認しています。さもなければ、 948 行目で設定するポインタ変数 ip6 を経由して内側の IP バケットの内部にアクセスできないからです。 IP ヘッダの長さに満たない場合は、すくなくとも IP ヘッダに相当する部分が麪頁の mbuf に入るように m-pullup() を呼び出します ( 942 行目 ) 。 if ( ! ip6—ecn—egress(ip6—ipsec—ecn, 950 トンネルモードを使って通信する場合、認証ヘッダの後ろに内側の IP バケットか読きます。まず、 918 ~ 924 行目で外側の IP バケットの認証ヘッダの長さを言 T 算します。 if (ipsec6—tunne1—va1idate(m, 0ff + 925 stripsiz, nxt , sav) ) { 925 行目の ipsec6-tunnel-validate() は、入力したパケットがトンネルモードで通信されているバケットかどうかを返します。トンネルモードで送信されたバケットなら、外側の IP ヘッダを削除し、内側にオ内されている IP バケットを入力処理ルーチンに渡さなけれはなりません。 ipsec6-tunnel-validate() についてはあとで解説し 952 &flowinfo, &ip6—>ip6—f10w) ) { goto fail; ます。 935 936 937 70 トンネルモードの処理は 1 , 004 行目まで続きます。 flowinfo ip6—>ip6—fIow; m—adj (), off + stripsiz) ; if (m—>m—len く sizeof (*ip6) ) { 953 } ip6-ecn-egress() は、外側の IP バケットを削除する際の ECN 処理を実行します。田は省きますが、基本的には、外側のバケットカ斗畠輳を検出していたら、内側のパケットにい獅奏を通知する情報を設定する処理です。図 3 の key-checktunnelsanity() は、外側の IP ヘッダと内側の IP ヘッダの整合を石忍するための関数ですが、現点では何も実行しない空の関数です。 969 m—>m—flags & = -M—AUTHIPHDR; 970 m—>m—flags & = -M—AUTHIPDGM ; 外側の IP バケットは認証ヘッダによって言正か完了していますが、内側のバケットについては何も処理していません。トンネルモードで通信する際、外側の IP ヘッダと UNIX MAGAZINE 2003.5

8. UNIX MAGAZINE 2003年5月号

特集 SoIaris 9 の管理と運用図 32 init 6 コマンドによるリプート # init 6 INIT: New run level : 6 The system is coming dOW 取 . P1ease wait . System services are now being stopped. httpd stopping ・ Print servlces already stopped. Jan 30 05 : 01 : 02 exp syslogd: going down 0 Ⅱ signal 15 Live Upgrade : Deactivating current b00t environment く S01aris9 ー 0902 ー Orig >. Live Upgrade : Executing Stop procedures for b00t environment く S01a て is9 ー 0902 ー 0 て土 g > . Live Upgrade : Current b00t environment is く S01aris9 ー 0902 ー Orig >. Live Upgrade: New bOOt environment i11 be く Solaris9 ー 0902 ー 2003 ー 01 ー 31 >. Live Upgrade: Activating b00t environment く S01aris9 ー 0902 ー 2003 ー 01 ー 31 > . Live Upgrade : The bOOt device for bOOt environment く S01aris9 ー 0902 ー 2003 ー 01 ー 31 > is く /dev/dsk/cOt2dOs6> . Live Upgrade : Activation 0f b00t environment く S01aris9 ー 0902 ー 2003 ー 01 ー 31 > completed. umount : /export/home busy The system is down. done syncing file systems . rebooting. Resetting 新環境でのフート新しい竟 , 、、のパッチやインストールイ乍業カったら、いよいよ、、環竟 " を切り替える。新たに作成した竟を初めて有効にしたときや、 luactivate コマンドに一 s オフションを指定した場合は、必要に応してシステムのいくつかの成疋ファイルか現在の竟から新しい工韆竟にコピーされる ( 同期処理 ) 。この同期処理の対象になるのは、所定のシステムファイルだけである。独自に定義した設定ファイルなどは同期処理の対象とはならないので、新しい工竟の作成後に設定ファイルを変更するのは避けたほうが無羅である。なお、同期処理中に新旧両方の環境で同しファイルが変更されていることか判明した場合はコピーはおこなわれない。すなわち、新しい環竟に加えた変更だけか有効になる。環境を切り替えるには、 luactivate コマンドを実行する ( 図 31 ) 。引数には、有効にしたい新しい環竟名を指定する。このコマンドを実行すると、新しい環竟でのプートに失敗した場合の回復方法か表示されるので、これをメモしておく。 Live Upgrade の仕組みから考えれば明らかだが、要するに PROM モニターが OS をプートするディスクスライスをもとに戻すだけである。旧い竟から新しい環竟ー、、の同期処理は、新しい竟を 56 万一、新しい工竟カワ。ートしないときは、 luactivate コマンドの実行時に表示された、、もとに戻す方法 " を用いて旧し寸竟でプートする。 SPARC アーキテクチャのシステムでは、 LI-STOP キーまたは BREAK キーを押してプートプロセスを中断し、 PROM の。 k プロンプトでプートテンヾイスを変更初めてプートした際におこなわれる。システムをリプート init 6 " コマンドを実行する ( 図 32 ) 。図するために、 31 の出力にも注意書きがあるように reboot コマンドや halt コマンドを使うと工竟の切替えはおこなわれない。 Live Upgrade による工竟切替えの処理がおこなわれたことか表示さオ L 、システムはリセットされる。リセットにともなうシステムの自己診析のあとに、システムのプート処理カまる ( 図 33 ) 。同期処理か正常におこなわれ、新しい工鳬か有効になったと表示される。場合によっては、カーネルのバージョンか更新されていることもある。ログインして、アップグレードが適切におこなわれているか、サービスやアプリケーションか正しく動くかを石忍しよう。パッチの適用やアップデート・リリースによって既存のアプリケーションか動作しなくなることはあまりないはずだが、絶対にないとはいえないからである。後始末 UNIX MAGAZINE 2003.5

9. UNIX MAGAZINE 2003年5月号

ループを抜けます。次に、読み込んだノードの名前をさきほ当呆したバッフアにオ褓内していきます。ここで使っている変数 nused は名前として何文字読み込んだかを示すためのものです。 do { bsize = b—>b_bsize; b = &bufs [ Ⅱ ] ; nused = 0 ; b—>b_bsize = bsize; b—>b_buf [nused] } while (c ! = EOF & & !isspace(c)) ; c = getc(fp) ; bSize * ー b->b-buf = grow-buf (b—>b—buf , bsize) if (nused b—>b-buf [nused + + ] 則を読み込んだかを調べます。読み込んでいれは、 add- ノード名として文字列を読み込んだところで、 2 つの名にし、バッフアの 0 サイズを修正してもムみは終了です。ヌル文字を加えてバッファ本を文字列として扱えるようフアのサイズを拡張します。最後に、ノヾッフアの末尾に数を読み込んだ場合は、 grow-buf 関数を呼び出してバッ文字すっオ褓内していきます。ノヾッフアのサイズぶんの文字文字は変数 c に順番に取り出されるので、バッフアに 1 arc 関数を呼び出して 2 つのノード間にアークを設疋し次に、アークを追加する add-arc 関数をみてみましょう。これは、文字列として与えられた 2 つのノードのあいだにアークを j 砌日します。具 f 勺には、アークの元となるノードを表すデータ構造に、アークの先となるノードを表すデータ構造へのポインタを j 助日します。ます、 get-node 関数を使って 2 つのノードを表すデータ構造へのポインタを取得します。 void add—arc(char *sl , NODE *n2 ; NODE *nl ; char *S2) ます。 if ( Ⅱ ) add -arc (bufs [ 0 ] . b-buf , bufs[l] . b_buf) ; これらの処理カ鮗ったら後処理に移ります。ます fclose 関数を呼び出してファイルをクローズします。さらにみ込んだ名前が偶数であることを石忍します。奇数の場合、ⅱ丿しこのあと、実際にトボロジカル・ソートをおこなう ts 。 rt exit(O) ; tsort() ; / * do the sort * / errx ( 1 , "odd if ( Ⅱ ) (void)fclose(fp) ; はエラーメッセージを出力します。 dat a C ount 関数を呼び出してプログラムを終了します。 116 int bsize , i; nl = get-node(sl) ; if (!strcmp(sl, s2)) n2 = get—node(s2) ; め、以降の処理 ( アークの追加 ) はイです。関数を呼び出した段階でノード自体は作成されているたこのとき、 2 つのノードが同し名前であれば get-node すでにアークがあれは j 助日する必要はないので、 return return ; Ⅱ 2 ) if (nl->n-arcs [i] i く nl—>n_narcs; i 十十 ) 次に、 nl から n2 へのアークがすでにあるかどうかを f or ( i = 0 ; 串ヾます。 UNIX MAGAZINE 2003.5 DBT data, key; get—node (char *name) NODE * していないときにのみ dbopen 関数を呼び出します。タベースをオープンします。まだデータベースをオープンに、データベースの操作が含まれています。最初に、デー次はノードを取得する getnode 関数です。この関数身の参照カウントをインクリメントしておきます。領域に余裕があれは、 n2 をアークとして追加し、 n2 自ます ( 図 4 ) 。は、アークを保持するための領域を長して不何呆しなおしてある領域の大きさと等しいかを調べます。等しい場合にす、すでに登録されているアークの数がアーク用に確保しこのあとは、アークを追加する処理をおこないます。ま文で関数を終了します。

10. UNIX MAGAZINE 2003年5月号

図 3 NODE 橢制本 typedef struct node—str NODE; struct node_str { NODE **n_prevp ; NODE *n_next ; NODE **n_arcs ; illt n_narcs ; int n_arcsize ; int n_refcnt ; int n—flags ; char n—name [ 1 ] ; プログラミング・テクニック・ name 0f this node * / # of arcs pointing to this node * / size 0f n—arcs ロ array * / number Of arcs in n_arcs [ ] * / array Of arcs tO Other nodes * / next node in graph * / pointer tO previous node ) S n—next * / ません。そこで、 tsort コマンドではノードに関するデータ自体をデータベースに登録するのではなく、ノードの情報はメモリ上凵尉寺し、そのアドレスだけを登録するようにしています。これにより、ファイルを用いたデータベースは利用できなくなりますが、可変長のデータでも上如勺簡単に扱えるようになります。それでは、いつものようにソースコードをみていきましよう。 tsort コマンドのソースコードは、 /usr/src/usr. bin/tsort ディレクトリに置かれています。プログラムのう頁のほうでは、さきはど紹介したノードを表すデータ構造を定義しています ( 図 3 ) 。ます nodestr という構造体に NODE という名前を付け、続いて本体を定義しています。ここで作成しているデータ構造は、基本的には二重リンクリスト構造です。 n- next メンノヾーが次のノードを指し、 n-prevp メンノヾーが則のノードを指しています。ただし、 n-prevp メンバーは則のノード自身ではなく、前のノードの n-next メンバーの位置を指しています。二重リンクリストで前のノードが必要になるのは、前のノードがもつ次のノードを指す場所を調整するためです。ここでは、処理の際にわざわざ n- next メンバーをたどらすにすむように、メンバーの位置を利用しています。直前のノードではなく、そのノードが次のノードを指すためのメンバーの位置を孑ことによる利点はもう 1 つあります。リスト構造の操作ではク頁のノードを特別扱いすることがよくありますが、これがイになります。地頁のノードを特別扱いする理山は、メンバーとして直前のノードを指すようにしていると、 : 頁のノードを指す部分 ( たソースコード UNIX MAGAZINE 2003.5 んなるポインタ ) と、 2 番目以降のノードを指す部分 ( 次のノードを指すメンバー ) が異なるため、処理を分けなければならないからです。しかし、ポインタやメンバーのアドレスを指すようにすれば、両者の処理を区別する必要がなくなるため、 1 つのコードでどちらも処理できます。 main 関数でのおもな作業は、引数やオプションの処理、入力の角斤などです。オフションの処理では、 getopt 関数を使って前述の 3 つのオプション (d 、 1 、 q) を処理します。これらのオフションカ甘旨定された場合、各オフションに対応する変数の値を真に設定します。オプションを処理したあと、引数にファイル名か残ってい川まそのファイルを、残っていなけれは標準入力を、グラフ情報の言囚み元として設定します。言ムみを開始する前に、バッフアを確保します ( 誌面の都合、て折り返しています。以ード同様 ) 。 for (b bufs, Ⅱ b->b_buf 2 ; grow-buf (NULL , - b—>b_bsize 1024 ) ; こて市寉保している 2 つのバッフアは、アークの元に 115 if (c 際、途中で入力カ鮗了してしまった場合は break により読込みの先頭では、空白文字を読み飛はします。その break ; = EOF) c = getc(fp) ; while (c ! = EOF & & isspace(c)) for ( Ⅱ = 0 , c = getc (fp) ; ; ) { 部も更新部もない無限ループとなっています。部分です。 for ループを使って : 滝見されていますが、条件次は、実際に入力を読み込んでグラフを認識するための期値として、 1 , 024 バイトのバッフアを作成しています。なるノードとアークカ甘旨すノードの 2 つに対応します。初