return - みる会図書館


検索対象: UNIX MAGAZINE 2003年8月号
12件見つかりました。

1. UNIX MAGAZINE 2003年8月号

連載 / IPv6 の実装ーの 図 4 スコ 2422 2423 2424 2425 if ープ情報付きの始点 / 終点アドレスの言聢 ( ! ip6—setpktaddrs (), (struct sockaddr—in6 *)&sav—>sah—>saidx. src, (struct sockaddr-in6 *)&sav—>sah->saidx . dst) ) { return (ENOBUFS) ; 認証ヘッダ付きバケットの出力関数 IP セキュリティ処理全体をみると、認証ヘッダと暗号 化へッダの双方に大きな違いはありません。どちらも、ト ランスポート・モードであれ Xipsec6-output-trans() で 出力さトンネルモードなら ipsec6-output-tunnel() で出力されます。違いは最後の出力処理の部分のみで、認 証ヘッダの場合は ah6-output() にたどり着きます。以 下、参照するコードは ah-output. c からの抜粋です。 i nt 361 362 ah6—output (), nexthdrp , md, isr) 工ントリに言当求されているので、 SAD 工ントリ (sav) を もとに ah-hdrlen() を使って値を取得します。 389 393 394 395 390 391 for (mprev = m; mprev & & mprev—>m—next ! = mprev—>m_next) md ; mprev if ( !mprev Ⅱ mprev->m-next ! = (d) { m—freem(m) ; return EINVAL ; 363 364 365 366 367 { struct mbuf *m ; u—char *nexthdrp ; struct mbuf *md; struct ipsecrequest *isr; 389 ~ 395 行目では、引数として渡された m と md の 整合生を石忍しています。 m も md も同じ IP バケット の一部を指しているので、 m から始まる mbuf チェーン をたどっていけば md がみつかるはすです。 md が m を : 頁とする mbuf チェーンに含まれていない場合は、 393 行目て処理を中断します。 ah6-output() は 4 つの引数をもちます。 m は言正へッ タ処理をおこなう IP バケットを含む mbuf へのポインタ、 nexthdrp は認証ヘッダカ甘市入される位置の直前に配置さ れるヘッダの次へッダフィールド、 md は認証ヘッダの挿 入位置の直後に配置されるヘッダかオ褓内された mbuf への ポインタ、 isr は ipsecrequest 構造体へのホインタです。 if (m—>m-len く sizeof (struct ip6—hdr) ) { 379 397 398 399 400 401 402 403 404 405 406 407 408 409 MGET (mah , M_DONTWAIT , MT_DATA) ; return ENOBUFS ; m—freem(m) ; m—free (mah) ; if ( (mah—>m-flags & M_EXT) MCLGET (mah , M_DONTWAIT) ; (ahlen > MLEN) { return ENOBUFS ; m-freem(m) ; i f ( ! mah) { if 381 382 m—freem(m) ; return EINVAL ; 383 } 379 ~ 383 行目では先頭の mbuf の大きさを確認しま す。あとで IP ヘッダの内容をポインタ経由て参照するた め、すくなくとも IP ヘッタんの大きさが必要です。 385 386 387 ahlen = ah—hdrlen(sav) ; if (ahlen = の return 0 ; 385 ~ 387 行目では、挿入される言正へッダの大きさを 取得します。認証ヘッダの大きさは、使用される認証アル ゴリズムによって決まります。認証アルゴリズムは SAD 68 397 ~ 409 行目では認証ヘッダをオ褓内するための mbuf を確保します。認証ヘッダを各内するのに必要な大きさ は、 385 行目で ahlen に設定しています。 1 つの mbuf : コ乂まらないようであれば、 403 行目で mbuf クラスタの 石崗呆を試み、それにも失敗したら処理を中断します。 410 mah—>m_len = ahlen ; 411 mah—>m_next = md ; 412 mprev¯>m—next = mah ・ 413 m—>m—pkthdr .1en + = ahlen ; mbuf の確保に成功したら、確保した mbuf mah の長 さをこれから作成する認証ヘッダの大きさに調整し ( 410 行目 ) 、 ah6-output() に引数として渡された md の直前 UNIX MAGAZINE 2003.8

2. UNIX MAGAZINE 2003年8月号

252 253 254 224 連載 / IPv6 の実装ーの if ( (sav->flags & SADB-X—EXT-OLD) return EINVAL ; m—freem (m) ; ! sav->replay) { 224 ~ 254 行目は SAD 工ントリの正当性の確認です。 SAD 工ントリに SADB-X-EXT-OLD カ甘旨定されてい ない、すなわち RFC2406 にもとづく新しい形式の IP セ キュリティ・ヘッダカ甘旨定されているにもかかわらす、反 復攻撃検出のための構造体 (replay メンバー変印が存在 しない場合は、処理を中断します。 296 } 297 esphlen = esplen + ivlen; 287 ~ 297 行目では、暗号化されたデータ部を除く暙号 化へッダ部のみの長さを計算します。 RFC1827 形式で あれは esp 構造体を ( 289 行目 ) 、 RFC2406 形式の場 合は newesp 構造体の大きさを担售にヘッダ長を計算し ます ( 292 ~ 295 行目 ) 。 292 行目は、 draft-ietf-ipsec- ciph-des-derived[2] にもとづく暗号アルゴリズムが尺 されているときの例外処理です。この場合、旧い形式の暗 号化へッダか利用されます。 256 257 260 261 262 esp—algorithm—lookup(sav->alg-enc) ; algo if (!algo) { return EINVAL ; m—freem(m) ; 299 300 301 304 305 306 for (mprev = m ; mprev & & mprev—>m—next ! = mprev—>m_next) md ; mprev if (mprev = = NULL Ⅱ mprev¯>m—next ! = m—freem(m) ; return EINVAL ; 256 ~ 262 行目では暗号化アルゴリズムの確認をおこ ないます。 SAD 工ントリに指定されている暗号化アルゴ リズム番号 (alg-enc) を、 esp-algorithm 」 ookup() で esp-algorithm 構造体に変換します。サポートしていな いアルゴリズム番号が設疋されていたら、バケットを破棄 して処理を中断します。 263 264 266 267 268 sav—>spi ; SPI sav—>ivlen; ivlen if (ivlen く 0 ) { panic("invalid ivlen") ; 299 ~ 306 行目では、 esp-output() に引数として渡さ れた m と md の整合匪を石忍します。 m と md は同し IP バケットを指しているため、 m から始まる mbuf チェーン に md か含まれているはすです。 299 行目で mbuf チェー ンをたどりながら md を検索します。 md がみつからなけ れば、 m と md が異なるバケットを指していることを意 味するため、バケットを破棄して処理を中断します。 308 plen = 0 ; n—>m_next) 309 for ( Ⅱ = md; Ⅱ ; n 310 plen + = n—>m le ; 263 ~ 268 行目で SPI の値と IV (lnitialization Vec- tor) の値を SAD 工ントリから取得します。 IV か不正な 値 ( 負の値 ) になっていてはいけません。 暗号化へッダの構築 287 行目から暗号化へッダの作成に入ります。 308 ~ 310 行目で、暙号化される部分の長さを言算して plen に設定します。暗号化の対象となるのは md て示さ れる mbuf 以降のデータなので、 md 以後の mbuf チェー ンをたどりながら、それぞれの mbuf に含まれているデー タの長さを合言します。 287 289 290 292 293 294 295 if (sav—>flags & SADB—X—EXT—OLD) { if (sav—>flags & SADB-X-EXT-DERIV) sizeof (struct esp) ; } else { esplen 312 324 325 326 327 329 switch (af) { case AF_INET6: break ; hlen sizeof (*ip6) ; ip6 = mtod(), struct ip6—hdr * ) ; esplen esplen sizeof (struct esp) ; sizeof (struct newesp) ; UNIX MAGAZINE 2003.8 312 ~ 329 行目で、 IP ヘッダのう頁アドレスを変数 ip6 に、 IP ヘッダ長を hlen に設定します。 71

3. UNIX MAGAZINE 2003年8月号

連載 / IPv6 の実装ーの 475 476 477 478 479 484 485 486 } m—freem(m) ; return EINVAL ; sav—>replay—>count 十十 ; bzero(ahdr + 1 , plen) ; c ount ) ; ahdr->ah—seq = htonl(sav—>replay-> です。 711 712 713 714 715 716 717 i nt struct struct u_char struct esp6—output (m , nexthdrp, md, isr) mbuf *m ; * ne xthdrp ; mbuf *md ; IPSeCreqUeSt *isr; 468 ~ 484 行目で、反復攻撃検出に利用する通し番号を 設定します。 469 行目は通し番号の橢益れの石忍です。通 し番号が最大値に達しており、かっ SAD 工ントリでオ徹益 れを許さない設定になっている (SADB-X-EXT-CYC- SEQ か指定されていない ) 場合は、処理を中断します。通 し番号に間題がなけれは、 479 行目で番号を増やし、 484 行目で認証ヘッダに設定します。 esp6-output() 自体はたんなるラッパー関数で、実際 の処理は esp-output() か受け持ちます。名前から想像で きるように 、 esp-output() は IPv4/IPv6 共用の関数に なっています。 esp6-output() は 4 つの引数をとります。 m は暗号化の対象となるバケットをオ褓内した mbuf への ポインタ、 nexthdrp は暙号化へッダの直前に配置される ヘッダの次へッタ値フィールドへのポインタ、 md は暙号 化へッダの直後に配置されるヘッダをイ褓内した mbuf へ のポインタ、 isr はバケットの暗号化に利用される SAD ェントリを含む ipsecrequest 構造体へのホインタです。 492 493 495 496 498 499 502 503 } error = ah6—ca1ccksum(m , ahsumpos , key—sa—recordxfer(sav, } else { m-freem(m) ; if (error) { plen, algo, sav) ; 718 720 721 72 2 723 724 } if (m—>m—len く sizeof (struct ip6-hdr) ) { m—freem(m) ; return 0 ; return esp—output (), nexthdrp, md , isr, AF- 工 NET6) ; 最後に、 ah6-calccksum() で認証データをします。 この関数の引数は 5 つです。 m は計算の対象となる IP バケットをオ褓内した mbuf へのホインタ、 ahsumpos と plen は認証データの計算結果を格納するメモリ領域のア ドレスと長さ、 algo は言正データの引・算に使用するアルゴ リズム、 sav は SAD 工ントリです。 ahsurnpos は、実際 には作成中の認証ヘッダの内部を指すため、 ah6-caIcck- sum() が正常に終了した段階で言正へッダの構築か完了し ます。正常終了したら、 key-sa-recordxfer() で SAD 工 ントリの使用量と使用時刻を言当求し、鍵の更新に備えます ( 498 行目 ) 。 ah6-calccksum() でエラーが発生したら、 工ラー番号を呼出し元に通知して終了します。 暗号化へッダ付きバケットの出力関数 暗号化へッダ付きバケットは esp6-output() で作られ ます。以下、参照するコードは esp-output. c からの抜粋 70 証ヘッダのときと同様、 IP ヘッダは頁の mbuf に ルい 含まれていなけれはなりません ( 718 行目 ) 。う頁の mbuf の長さに間題がなければ、 723 行目で esp-output() を呼 び出し、バケットを暙号化します。 181 static int 182 esp—output (), nexthdrp, md, isr, af) 183 184 185 186 187 struct mbuf *m ; u—char *nexthdrp ; struct mbuf *md ; int af ; struct ipsecrequest *isr; 188 { esp-output() は 5 つの引数をもちます。第 4 引数ま では esp6-output() に渡されたものをそのまま受け継ぎ、 最後の引数はアドレス・ファミリーの指定です。 esp-out- put() は IPv4 と IPv6 のどちらでも利用できるように作 られており、引数によって挙動が変わるようになっていま す。以後のコードでは、 IPv6 の処理のみ解説します。 UNIX MAGAZINE 2003.8

4. UNIX MAGAZINE 2003年8月号

連載 / IPv6 の実装ーの に挿入します ( 411 ~ 413 行目 ) 。 if (m—>m—pkthdr. len ー sizeof (struct 416 447 448 450 451 452 453 454 455 456 457 —>flags struct plen & SADB_X_EXT_OLD) { mtod(mah, struct ah * ahdr sizeof (struct mah—>m_len 419 420 ip6-hdr) > IPV6—MAXPACKET) { m-freem(m) ; return EINVAL ; 認証ヘッダと巨大ペイロード・オプションを同時に利用 することはできません。認証ヘッタ挿入後のバケットが、 IPv6 の仕様で定められている最大バケット長 (IPV6- MAXPACKET) を超えたら、処理を中断します。 ip6 = mtod(), struct ip6—hdr * ) ; ip6->ip6—p1en = htons (m->m—pkthdr. len sizeof(struct ip6—hdr) ) ; ペイロード長に問題がなければ、 422 ~ 423 行目で IP ヘッダのペイロード長を認証ヘッタ師入後の大きさに更新 421 } 422 423 425 if ( (sav->flags & SADB-X-EXT-OLD) します。 (u-char *)(ahdr + 1 ) ; ahsump 0 s ahdr ー > ah_nxt *nexthdrp , *nexthdrp IPPROTO_AH ; ahdr—>ah—len = plen > > 2 ; ahdr—>ah—reserve = htons(O) ; ahdr->ah-spi SPI; bzero(ahdr + 1 , plen) ; 430 431 432 } ! sav—>replay) { m—freem(m) ; return EINVAL ; 425 行目では、反復攻撃を検出するためのデータ構造の 正当性を石忍します。 RFC2406 にもとづいた新しい言正 ヘッダカ甘旨定してあるにもかかわらす、反復攻撃検出のた めのデータが存在しない場合は処理を中断します。 447 ~ 457 行目は RFC1827 形式の場合の処理です。 397 行目て市呆した mbuf のデータ部のアドレスを RFC 1827 形式の認証ヘッタ構造体のポインタ変数 ahdr に設 定し、 ahdr 経由て値を設定します。 450 行目の plen は、 証ヘッダ全体から認証ヘッダ構造体の長さを引いた値 で、認証データ部の大きさです。 452 ~ 453 行目で、認証 ヘッダの直前に配置されるヘッダに言殳定された次へッダ値 を言正へッダの次へッタイ直フィールドにコピーし、同時に 直前のヘッダの次へッダ値フィールドを認証ヘッダ (IP- PROTO-AH) に設定します。認証ヘッダは 4 オクテッ ト単位て表現されるので、 454 行目で plen の値を 4 オク テット単位に変換し、認証ヘッダの長さ ()h 」 (n) として 設定します。 SPI (Security Policy lndex) は SAD 工 ントリから取得できます。 442 行目で取得した SPI 値を 証ヘッダの SPI フィールド (ah-spi) に設定します。 458 } else { 434 435 439 440 441 algo = ah—algorithm-lookup (sav->alg-auth) ; if (!algo) { m—freem (m) ; return EINVAL ; 434 行目は、認証アルゴリズムの確認です。 ah-algo- rithm-lookup() を使い、 SAD 工ントリに指定されてい るアルゴリズム番号 (alg-auth) を ah-algorithm 構造体 のポインタに変換します。カーネルかサポートしていない アルゴリズムカ甘旨定されており、ポインタへの変換に失敗 442 ~ 486 行目で、認証ヘッダの各フィールドに値を設 認証ヘッダの構築 したときは処理を中断します。 459 462 463 464 465 466 467 461 struct newah *ahdr = mtod (mah, struct newah * ) ; pIen = mah—>m—len ー sizeof (struct newah) ; (u-char * ) (ahdr + 1 ) ; ahsumpos ahdr—>ah_nxt *nexthdrp ; *nexthdrp = IPPROTO—AH; ahdr->ah-len = (plen > > 2 ) + 1 ; ahdr—>ah—reserve = htons(O) ; ahdr->ah-spi SPI ; 459 ~ 486 行目は、 RFC2406 にもとづく新しい認証へ ッダの場合の処理てす。新しい形式には反復攻撃検こ日用の フィールドが j 助日されているので、認証ヘッダの長さを計 算する際にそのぶんを加えています ( 465 行目 ) 。 定します。 442 SPI 468 469 sav—>spi ; UNIX MAGAZINE 2003.8 if (sav—>replay->count if ( (sav—>flags & SADB_X_EXT_CYCSEQ) 69

5. UNIX MAGAZINE 2003年8月号

図 1 連載 / IPv6 の実装ーの IP セキュリティ出力関数の呼出し系 ip6—output() 図 2 アドレス・ファミリーの寉認 ipsec6—getpolicybyaddr() i psec6—getpoli cybysock() ipsec6_output_trans() ipsec6—output_tunneI() esp6—output() ipsec6_encapsulate() ah6_output() 2237 2238 2239 2240 2241 2242 if ( ( (struct sockaddr *)&sav—>sah—>saidx. src)—>sa—family Ⅱ ( (struct sockaddr *)&sav—>sah—>saidx. src)—>sa—family ! = AF_INET6) { ( (struct sockaddr *)&sav—>sah—>saidx. dst) —>sa—family return EINVAL ; m—freem(m) ; 2256 2257 2230 { ipsec6-encapsulate() は、トンネルモードの出力処理 関数である ipsec6-output-tunnel() から呼び出されま す。 m はカフセル化されるバケットをオ褓内した mbuf への ホインタ、 sav はトンネルモードの IP セキュリティ処理 に利用される SAD (Security Association Database) 工ントリです。 2 , 237 ~ 2 , 242 行目 ( 図 2 ) はアドレス・ファミリーの確 訒です。 KAME では、トンネルモードでカプセル化され るバケット ( 内側のバケット ) と、カプセル化するバケッ ト ( 外側のバケット ) のアドレス・ファミリーか 1 司しでな け川まなりません。 2251 plen m—>m—pkthdr . len ; 2 , 251 行目で、カプセル化される IP バケットの全体長 を plen に取り出します。この値は最終的に、外側の IP バケットのペイロード長になります。 2 , 256 ~ 2 , 273 行目では、外側の IP ヘッダを追加する ための領域を作成します。 66 if (m—>m—len ! = sizeof (struct ip6—hdr) ) panic("ipsec6—encapsu1ate: assumption failed (first mbuf length) " ) ; ipsec6-encapsulate() か呼び出された時点で、ツ曰頁の mbuf は IP ヘッダと同じ大きさになっていなけれはなり ません。大きさの調整は、 ipsec6-encapsuIate() の前に ipsec6-splithdr() を呼び出しておこないます。 ipsec6- splithdr() は、 IP バケットを IP ヘッダと IP ペイロー ドにうリし、 IP ヘッダをう頁の mbuf に、ペイロードを それ以降の mbuf に配置する関数です。 2 , 256 行目の点 で麪頁の mbuf の大きさが IP ヘッダの大きさと異なる場 ロ、 ipsec6-encapsulate() が不正な場所から呼び出され たことを未します。 2263 2264 2265 2266 2267 2268 2269 2270 2 271 MGET ( Ⅱ , M_DONTWAIT , MT_DATA) ; UNIX MAGAZINE 2003.8 —>m—pkthdr . len + = sizeof (struct ip6—hdr) ; m—>m_next = Ⅱ ; n—>m_next = m¯>m_next ; 1 en sizeof(struct ip6—hdr) ; return ENOBUFS ; m—freem(m) ; n

6. UNIX MAGAZINE 2003年8月号

特集・プログラミング入門 オ褓内し、一日判勺な領域として使うために同じサイズの brr 配列を用意しました。そして、いったん arr 配列から brr 配列へコヒーしながらマージ操作をおこない、すべてのデ ータをマージし終えたら、それを再度 arr 配列に戻すよう にします。 マージソートを関数として実現するために、ますはその インターフェイスを定義しましよう。さきほど、配列とし て整列すべきデータと一時領域を用意すると書きました。 これまでのイ歹地でもそうだったように、これらは外部変数 として石呆しておきます。それぞれの関数で整列する範囲 を示すために、 2 つの引数を使います。この 2 つの値は、 整列すべき範川のもっとも小さい添字の値と、もっとも大 きい添字の値十 1 を指定します。これによって、条負半」断 を簡潔にまとめることができます。 それでは、コードを見ていくことにしましよう。関数の インターフェイスでは、 2 つの引数を亘暠しています。 VOid sortsub(int 10 , int high) int mid; int i , j , k ; if ( 10W + 2 > high) return; mid = ( 10W + high) / 2 ; sortsub(low, mid) ; sortsub(mid, high) ; 上で夬めたように、 1 。 w は調べる領域のもっとも小さい 添字で、 high は領域のもっとも大きい添字十 1 です。最 10W + 2 > high 初の if 文の条件である、 92 いきます。埋めるべき場所を示すのが変数 i 、左半分のな 一時領域の配列の整列したい範囲に対応する部分に埋めて 両方の列の先頭から小さいほうの要素を順番に取り出し、 これ以降は、マージの処理になります。この処理では、 とでそれぞオ L 整列します。 し、左半分と右半分の徊川を、再帰的に関数を呼び出すこ 調べる範囲が 1 よりも大きい場合には中間の値を計算 に return を実行して関数を終了します。 です。この点では実際の並べ替えは必要ないので、即座 調べなければならない範囲が 1 以下の場合に真となるわけ それよりも小さいときに真になります。つまり、この式は は、 high が low よりもちょうど 1 大きいとき、もしくは かで残りの地頁を指すのが変数 j 、右半分では変数 k を使 います。 10W ; k = mid ; の場合、どちらか小さいはうの値を変数 i カ甘旨す場所にコ 次は、両方にデータが残っているときの処理です。 10W ; i く high; i + + ) { for (i また、どちらか片方でもデータカ鮗了した場合には、残 brr Ci] = arr [ k + + ] ; } else { brr[i] = arr [ j + + ] ; if (arr [j] く = arr[k] ) { if (k く high) { if (j く mid) { ピーします。 っているほうのデータをそのままコピーします。 arrCj + + ] ; brr [i] } else { brr Ci] else { sortsub(), N) ; brr Ci] ; arr Ci] 10W ; i く high; i + + ) { for (i て、マージの処理を終了します。 最後に、一一印頁域からもともとの配列へコピーしなおし ポトムアップに木を構築するマージソート sort(void) VOid スを揃えるための関数を作っておきます。 スがこれまでの整列用関数と異なるため、インターフェイ これでマージソートは完成しましたが、インターフェイ UNIX MAGAZINE 2003.8 順に構築していくかたちになります。一方、ポトムアッフ 割し、さらにそれを半分にするというように、木の根から ッフダウンて構築していました。つまり、全体を半分に分 こまでにみた、再帰呼出しの呼出し構造を表す本はト

7. UNIX MAGAZINE 2003年8月号

特集・プログラミング入門 図 15 配列て表現 ヒープの管理 ヒープソートを実現するには、ヒープをつねに正しい状 態にする必があります。つまり、子をもっすべてのノー ドは、子のノードの値よりも大きな値をもたなければなり ません。なんらかの原因でこの条件が崩れてしまった場合 は、正しい状態に戻す必要があります。ます、この処理を 実現する関数を作成してみましよう。 関数を作成する前に、ヒープを正しく保っためのアルゴ リズムをまとめておきましよう。正しい状態のヒープにお 添字とする要素としてオ褓内するのです。 こでできあがる いて、根のノードに正しくない値をもつデータが置かれた 配列を縦に描くと、図 15 のようになります。 場合には、次のようなアルゴリズムを用いて全体を正しい この表現を利用すると、ある添字の値がのノードの子 ヒープに戻すことができます。 にあたるノードは ( もし存在するのなら ) 幻 + 1 と幻十 2 1. 根のノードに注目する。 になります。また、根のノード以外であま、その親ノー ドの添字は第一 1 ) / 2 」て求めることができます。 2. そのノードに子がいなければ終了する。 3. 子がいる場合は、そのなかて最大の値をもつものを〕尺 この方法を使う場合には、酉改」の要素にデータが含まれ する。 ているかどうかに注意が必要です。ポインタを用いた再帰 4. 親のノードの値のほうか大きけれは終了する。 的データ構造では、ポインタが何も指していない (NULL 5. 親と注目している子を入れ替える。 となっている ) ときには子はないと知ることができまし 6. 子のノードに注目し、 2 に戻る。 た。しかし今回は、たんに配列の添字に対する演算だけで 子をオ褓内すべき要素か分かってしまうため、本当にそこに これをプログラムにすると、次のような関数になりま 子のノードが入っているかを確かめる手段がありません。 す。 したがって、データが入っているかどうかという情報を VOid データ自体に組み込む必要があります。たとえは、配列の sortsub (int i , int Ⅱ ) 要素を橢匿体にしておき、データが入っているかを示すメ ンバーと実際にデータをオ内するためのメンバーを用意す るといったガ去が考えられます。 しかし、対象とするのカ院全二分木た、けであオ L は、もっ と簡単に判断できるでしよう。完全二分木の場合には、配 列の : 麪頁からびっしりと要素カ理まることになります。途 中の要素カ皺ける可能性はありません。そのため、どこが 末尾の要素かを示すことで、どこまで要素が入っていて、 どこから要素が入っていないのかを判断できます。たとえ は、さきほどの図 14 のような冓造の場合には、要素数 が 7 であることさえ分かれは、添字が 2 の要素には 2 つ の子があり、添字が 3 の要素には子がないことが分かり ます。 さきほど紹介した部分頂序付き木を配列を用いて表現し たものを、、ヒープ " と呼びます。ヒープソートは、このヒ ープを利用して整列をおこなうアルゴリズムです。 020000 int 」 ; while ( i くⅡ / 2 ) { i 十 i 十 1 ; if (j + 1 くⅡ ) { if (arr[j] く arrCj + 1 ] ) if (arr [i] く arr[j] ) swap(), j); return ; この関数は、引数を 2 っとります。第 1 引数には、注 目すべき部分木の根を指定します。上記のアルゴリズムで は、 6 で、、子のノードに注目 " と書いていますが、これは このノードを根とする部分木に注目している " と言い換 100 UNIX MAGAZINE 2003.8

8. UNIX MAGAZINE 2003年8月号

文房具としての カーネルの構築 カーネルとユーサーランドを構築するための一連の作 業は、 build. sh というスクリプトを利用しておこないま す。複雑な作業がユーサーの眼から隠さ単純なオプシ ョンを渡すだけで効率よく作業を終えることができます。 それでは、新しい竟の構築を始めます。最初に、環竟 の構築に不可欠なコンパイラなどのツールを作ります。 れらのツールは /usr/obj 以下に置かれますが、初期状態 ではこのディレクトリはありません。このまま build. sh を実行すると途中でストップしてしまうので、ます、 のディレクトリを作りましよう。 # mkdir /usr/obj そして、ツールを作成します。 # cd /usr/src # . /build . sh t001S 続いてカーネルを作ります。この時点でカーネルのオ プションを触ると、なんらかの不具合カ咄たときに原因が 分かりにくくなるので、とりあえすは GENERIC カー ネルを作ってみることにしました。 # . /build. sh kerneI=GENERIC カーネルはうまく make できました。 current を利用 しているので make に失敗することもあると思いますか : そんな場合も焦ってはいけません。 1 日ほどおいてから、 # cvs logout # cvs update —dP # cvs login # cd /usr/src いカーネルが /netbsd として置かれたはすです。再起動 これで、もとのカーネルは / 。 netbsd に移され、新し # make install # cd /usr/src/sys/arch/i386/compiIe/GENERIC さて、カーネルをインストールします。 付を指定して旧いツリーをもってきて試してみましよう。 としてソースツリーを更新し、再挑戦するか、 CVS で日 # reboot して新しいカーネルで起動してみましよう。 80 プをチェックしてみましよう。それでも角夬しなけれは、 ーリングリスト current-users@netbsd.org のアーカイ うまく起動したでしようか ? 起動できない場合は、メ このメーリングリストへ ( もちろん英語で ) 質問するとよ いかもしれません。 とりあえず、以前のカーネルて起動したい場合は、起 動開始時に、 Use hdla:netbsd to boot sd0 when wd0 is also installed Press return tO bOOt now, any Other key for boot menu booting wdOa :netbsd ー starting in 5 と表示されたところで、最後の数字生記の例では 5 ) が 0 になる前に Enter キー以外のキーを押すとメニューに 入れます。ここで、 > boot wdOa : onetbsd などとすれば、旧いカーネルて起動します。 ユーサーランドの構築 次に、ユーサーランドを構築します。 を利用して以下のように入力します。 # cd /usr/src これも build. sh # . /build . sh —D /usr/NetBSD—new—buiId , build 2 > & 1 build .10g —D オフションに続けて /usr/NetBSD-new-build を 指定しています。このディレクトリに、新しいシステムー 式が置かれることになります ( ですから、十分に大きな領 域を用意してください ) 。あとでいろいろとチェックする ために、ログをすべてファイル (build. log) に保存する ようにしています。 構築はうまくいったでしようか。もし工ラーで止ま ってしまったのなら、悪いタイミングでソースツリーを checkout してしまったのかもしれません。下記のページ に、ある時点のソースツリーて構築に成功したかどうかが 載っています。 ・ http://releng.netbsd.org/ab/B-HEAD/ 間題が一般的なものなのか、それとも個別のものかの 判断材科になると思うので、このページを見てみること をお勧めします。 正しく構築できると、 / etc 以下のファイルと新しいバ ージョンとの整合がとれているかを調べるためのスクリ プトが実行されます。 このとき、たとえば、 UNIX MAGAZINE 2003.8

9. UNIX MAGAZINE 2003年8月号

連載 / IPv6 の実装 - の 609 610 611 SIZ ((aalgo → sumsiz) (sav) + 3 ) & if (AH_MAXSUMSIZE く siz) panic("assertion failed for AH_MAXSUMSIZE" ) ; 647 bcopy(authbuf , p, siz) ; 621 ~ 646 行目で作成した領域に、 613 行目で言算した 認証データをコピーします ( 647 行目 ) 。 609 ~ 611 行目で認証データの大きさを石忍します。認 証ヘッダの場合と同様、認証データは AH-MAXSUM- SIZ ( 16 オクテット ) を超えてはなりません。 if (esp—auth(m, espoff , m—>m-pkthdr. len 613 672 673 674 681 682 noantireplay : key—sa—recordxfer(sav, m) ; return 0 ; 615 616 618 619 } espoff , sav, authbuf) ) { m-freem(m) ; error = EINVAL; goto fail; 613 行目の esp-auth() て認証データを計算します。計 算結果は authbuf で示されるバッファ : ゴ内されます。 621 622 623 625 626 627 628 629 630 631 632 633 636 637 638 639 640 641 642 643 644 645 646 Ⅱ = m; while (n—>m—next) n—>m_next ; Ⅱ if ( ! (n—>m_flags & M—EXT) & & siz M_TRAILINGSPACE (n) ) { n—>m len 十 = SIZ,• m—>m—pkthdr. Ien + = siz ; p = mtod(), u—char * ) + n—>m_len ー SIZ,• struct mbuf *nn ・ MGET ( ⅡⅡ , M_DONTWAIT , m—freem(m) ; く MT_DATA) ; error = ENOBUFS ; goto fail; nn—>m_len nn— >m_next n— >m_ne xt SIZ,• = NULL ; m—>m—pkthdr. 1en + = siz ; p = mtod(nn, u—char * ) ; 621 ~ 646 行目は、暗号化されたバケットの末尾に認 76 ら、説明は省略します。 号化へッダのトレイラー部のための領域作成と同しですか 証データを各内するための領域を作る処理てす。手順は暗 以 E で暗号化へッダ付きバケットの作成カ院了しまし た。 681 行目の key-sa-recordxfer() で、鍵更新に必要な 使用量と使用日該リの清報を言当求し、呼出し元に返ります。 690 } 686 684 fail: ☆ 終了します。 処理の途中でエラーが発生したら、エラー番号を返して UNIX MAGAZINE 2003.8 derived, July 1997 ESP DES- CBC 、佖れ s ル 7 、 m , draft-ietf-ipsec-ciph-des- [ 2 ] Perry Metzger and WiIIiam AIIen Simpson, The c 佖 0 れ (ECN) to IP, RFC3168 , September 2001 BIack, The d 市 0 れ可 E ェ〃 c Co れ ges 0 れル ot 第 - [ 1 ] K. K. Ramakrishnan, Sally Floyd and David L. [ 文献 ] ( しま・けいいち IIJ) を考えていく必要があるでしよう。 す。今後、誰もカ吶単に安全な通信ができるような本咎はみ 強固な技術を簡単に使える仕組みがないのは残念なことで 点ではたいへん素晴らしい技術です。しかしながら、その IP セキュリティ技術は、セキュリティの強固さという

10. UNIX MAGAZINE 2003年8月号

特集・プログラミング入門 えても同じ意味になります。このプログラムでは、あるノ ードを根とする : 冓造において、ヒープ条件を満たすよう に修正をおこないます。 第 2 引数では、二分木のサイズを指定します。この情 報がないと、子をもつかどうかをプログラムのなかで判断 できなくなってしまうからです。なお、この値は、、ノード の個数 " て指定することにします。つまり、この値を n と すると、実際にノードかオ内されるのは n ー 1 までとなり ます。 関数のメインループは、 i の値が n/2 未満であること を条件としています。 n はノードの個数ですから、最後の 要素の添字は n-l です。すると、その親は ( n ー 2 ) / 2 の 添字をもっことになります。見方を変えると、この値以 下のノードであ川ま、子をもっことになるわけです。そこ で、、、注目しているノードが子をもつあいだ " という条件 を、、、 i < n / 2 " と表現しています。注目しているノー ドが子をもたないときは、この条件が真にならないので、 while ループは実行されすに関数は終了します。 注目するノードが子をもっている場合、変数 j として左 の子のための添字の値を計算します。さらに、右の子もい るようならどちらの値カゞ大きいかを調べそれを j としま す。こうして求めた j のノードと自分自身のもつ値とを比 較し、自分の値のはうが大きけれは return 文で処理を終 了します。 子 (j) のもつ値のほうが大きい場合には、ノードを入れ 替え、入れ替えた子に注目点を移してルーフの : 頁に戻り ます。 ヒープの初期化 これでヒープの管理は可能になりましたが、この関数を 利用して正しくヒープを系財寺するには条件が 1 つありま す。最初に、本が正しいヒープになっている必要がある のです。この処理も、さきほど挙げた関数を利用して実現 できます。 冓造を思い浮かべてみましよう。当然ですが、葉のノ ードだけからなる部分木は子をもちません。したがって、 UNIX MAGAZINE 2003.8 けをもつノードはどうでしようか。下につながる部分木 それでは、そのすぐ上のノード、つまり、直接の子だ を満たしています。 子よりも小さな値となるはすはなく、すべてヒープの牛 は、左右どちらもヒープの条件を満たしています。もし、 この村冓造全体としてヒープの条件を満たしていないとす れは、それは子のノードのもつ値より根のノードのもつ値 のはうが小さくなっていることを意味します。このとき、 ヒープの条件を満たしていないのは根のノードの部分だけ です。 ここて思い出してはしいのは、さきほど作成した関数を 利用するための条件です。さきはどの関数を実行すると、 木構造全体が正しいヒープとなっていれば、たとえ根の ノードが条件を満たさないノードに置き換えられたとして も、条件を満たすように修正されます。いま注目している のはまさしくこの状態で、正しいヒープと上交して、根の ノードだけがおかしくなっている可能性があります。した がって、この状態のヨ冓造に対してさきほどの関数を適用 すれば、注目している部分木全体を正しい状態に修正でき ることになります。 : 冓造全体がヒープの条件を満たすようにするには、 の処理を根に向かってすべてのノードに対しておこなって いけばよいことになります。それぞれの部分木を処理して いけは、各部分木の根のノードにかならず最大の値をもつ データか置かれます。これをポトムアッフにおこなってい くと、最大の値をもつデータを根のノードに配置すること ができます。 ヒープソートの本体 こまで分かれば、あとはヒープソートの本体を言当す るだけです。 ヒープを管理する関数はさきはど完成させているので、 この関数は以下に示すようにごく簡単なものになっていま す。 VOid sort (void) int i ; for (i sortsub(i f or ( i = N swap(), i); sortsub(0, (N ー 2 ) / 2 ; i > = 0 ; 1 ; i > 0 ; 101