技術評論社 JAVA PRESS Vol22 より.
前回は,ベリファイ編の始めとしてクラスファイル=ベリファイヤ全体の流 れを説明しました.今回は,クラスファイル=ベリファイヤのパス3,即ちバイ トコード=ベリファイヤ部分について説明します.
既に述べた通り,バイトコード=ベリファイヤはクラスファイル=ベリファ イヤの一部であり,クラスファイル=ベリファイヤの中でも最も複雑な部分で す.またクラスファイル=ベリファイヤが従来のエラーチェックとは一線を画 す,クラスファイル=ベリファイヤの核となる部分でもあります.
バイトコード=ベリファイヤとは,簡単に言えばバイトコードの静的な安全 性はもちろん,動的な安全性の大半(残念ながら全てではない)も静的に検証 する機構です.
具体的には,バイトコード=ベリファイヤは次のような条件が初期状態や入 力に関係なく,全てのバイトコードに対して常に成立することを保証します.
(注1:正確には「型,クラス,又はインターフェース」とでも書くべき部 分ですが,あまり本質的な問題ではないので省略して「型」と書いています. この辺りはJavaVM仕様書でも記述に苦労しているようです.)
(注2:他のメソッドへのジャンプはinvokevirtual等のメソッド呼び出し命 令を使います.また,当然のことですがオペランド部へのジャンプは許されて いません.)
もちろん,検査すべき項目の詳細は各命令ごとに異ります.幾つかの命令につ いての例を図1に示します.
バイトコード=ベリファイヤの処理は,大きく次の三つのステップに分けられま す.
code配列自体は単なるバイト列ですので,そのままベリファイを実行する のは効率の面で非現実的です.そこで最初にベリファイの処理が簡単になるよ うに前処理しておきます.これは,平たく言えばコンパイラにおける字句解析 のようなものです.
code配列の先頭より順に一命令毎に切り分けながら,同時に仕様で定めら れたバイトコード以外の情報は入っていないかをチェックします.たとえブラ ンクやデッドコードでもバイトコード以外のものがcode配列中に入っていれば, その時点でエラーになります.
次に,各命令のオペランドを(iload_<n>やiconst_<i>ような 暗黙のオペランドも含む)の検証を静的に行います.この段階では具体的には 次のような点を検証します.
これらのオペランドのチェックは一度静的に行えば良いものなので,この 段階で行います.処理する内容も比較的単純なので,理解するのは難しくない と思います(注3).
(#注3:それでも実装するとなると,かなり面倒でした.)
Step2までで静的な検証を行った後,Step3で動的な検証を行います.動的 な検証を行うデータフローアナライザのアルゴリズムは比較的複雑です.少し 乱暴ではありますが,次のような二つのフェーズに分けて考えた方が分かり易 いでしょう.
このように二段階に分けたやり方でも,正しいクラスファイルについては ベリファイ可能です.しかし正しくないクラスファイルだと状態モデル表が完 成しないこともあり,ベリファイの正当性が保証できません.
(注4:説明のために導入したもので,仕様書ではこのような表は定義され ていませんし,実際にこのような表を作る必要は必ずしもありません.また, 状態モデルという単語も仕様書には出てきません.)
このフェーズでは,メソッドの全バイトコードに対し,「フレームの状態 モデル」を決定していきます.ここでいうフレームの状態は,次の三つで定義 されるものです.
このため,実際の動作時のフレームとは様々な点で異なります(図2).正確 にはもう少し複雑ですが,それはおいおい説明していきます.
正しいクラスファイルでは,この「カレントフレームの状態モデル」が, その命令に至るまでの分岐の成立/不成立やループを回った回数,例外処理の 有無などには関係なく,各バイトコードに対して一意に定まらなければなりま せん.
例えば,ループを回る毎にオペランドスタックの高さが変化したり,オペ ランドスタックのトップの型がintになったりfloatになったりするようなコー ドは,正しいバイトコードとは認められません.これは安全なクラスファイル が持たなければならない特性というよりは,ベリファイや実行効率を考慮して クラスファイルに課せられた制約と考えるべきでしょう.
状態モデルは各バイトコードに対して一意に定まるので,最終的には図3のよ うなフレームの状態モデル表を完成させることができるはずです.
この状態モデル表の作成作業は全く制約がない場合には,収束せずに無限 ループになることも考えられます.バイトコード=ベリファイヤでは先ほど述 べた制約があるため,通常は数パス程度(一般にはnパス(注5)で完了するよう になっています.
(注5:少なくとも初期のjavacでコンパイルした場合は,ほとんどの場合は 1パスになるようです.ただし,これは必要条件ではありません.)
この制約に関する重要な概念にマージ(merge)があります.マージは二つの フレームの状態モデルを融合し,それらの最大公約数的な一つの状態モデルを 作り出す作業のことです.たとえばintとintをマージすると同じくintのまま ですが,intとfloatでは使用不可(unusable)になります.なお使用不可のロー カル変数に上書きするのは許されていますが,読み出そうとするコードはエラー になります.詳細については後ほど詳しく説明しますが,この処理によって扱 う情報量が削減されます.
マージは必ずしもあらゆる組合わせについて可能というわけではなく,マー ジできない組合わせも存在します.マージできない組合わせの場合はベリファ イエラーになり,ベリファイは異常終了します.
マージは仕様としてはあらゆる命令に対して行わることになっていますが, 実装レベルで見ると図4のように分岐が合流する個所で起こると考えても,特 に問題はないでしょう.またこのようにイメージした方が理解し易いと思いま す.
マージによって状態モデル表に変更が加えられた場合,それ以降の命令に 対応する部分の状態モデル表にも順次修正を加える必要があります.すべての マージと修正が終わった時点で状態モデル表は完成します.バイトコード=ベ リファイヤが一般にはnパスになるのはこのためです.
この部分で,各バイトコードの動的な安全性の検証を行います.検証すべ き項目は各命令ごとに異りますが,例えば次のようなことが検証されます.
本来は,この処理は状態モデル表の作成と同時平行的に行われます.オペ ランドスタックやローカル変数で使用する型が正しくない場合は,そもそも状 態モデル表を作成するのは本質的に不可能です.そのような場合は,正しくな いことが分かった時点でエラーを発生させベリファイを終了する必要がありま す.逆にベリファイに成功する場合では,状態モデル表が完成した時点でバイ トコードの検証も終了しており,ベリファイヤは正常終了します.
次に,バイトコードの要であるデータフローアナライザを詳しく見てみましょ う.
バイトコード=ベリファイヤを実装する場合には,一例として次のようなデー タ構造が必要になるでしょう.これらはあくまで一つの例に過ぎず,当然まっ たく異なる実装も十分考えられます.
この他,コンスタントプールやメソッド情報など,通常のクラスファイル に対応したデータ構造も必要になります.
データフローアナライザの動作は次のようになっています.
変更ビットがセットされている場合は,まだ状態モデルを計算していない 命令か,状態モデルが変更された後に再処理されていない命令であることを意 味します.変更ビットが全てリセットされている場合はすべての変更が終了し ているので,ベリファイは正常終了します.
変更ビットがセットされている命令は,一般には複数存在します.仕様上 はその中の任意の命令を選んで良いわけですが,通常はPCの最も小さいものを 一つ選ぶのが無難だと思います(注9).また本質的には逐次処理する必要はな く,変更ビットがセットされたすべての命令に対して同時に並列実行しても問 題ないでしょう.
(注9:「多分」そうした方が状態モデルの再処理が少なくなるのではない かという程度の単純な理由です.あくまで単純に考えただけなので,今後研究 が進むと異なる結論が得られるかもしれません.)
各バイトコードによるオペランドスタックのプッシュ/ポップ,ローカル 変数への上書きなどに合わせて,現在の命令の実行後の新しいカレントフレー ムの状態モデルを作成します.同時にバイトコードが使用できる型かどうか, オペランドスタックのオーバーフロー/アンダーフローなども検証します.
この部分の処理はバイトコードによって様々です.各命令の動作そのもの はバイトコードの動作と基本的に同じなのですが,型情報中心であることや可 能な限り他のクラスの情報を使わずに処理を進める点などが異なります.
まず,簡単な例から見ていきましょう(図6).これらの命令では,違いは数値が 無視されるくらいで動作は実行時のものと同じです.
図6(a)のiload_1や(b)のistore_1では,数値ではなく型で表現されること を除けばバイトコードの動作と同じです.なおローカル変数中のlongやdouble は連続する2エントリを占有していますが,その片方にistore_1などで上書き した時はもう片方のエントリは使用不可になります.また片方のみを取り出す ことも許されていません(注10).
(注10:そもそもlongやdoubleの詳細は実装依存であり,「エントリの小さ い方に上位(或いは下位)32bitが入っている」などと決まっているわけではあ りません.このため,たとえ上位/下位ビットだけが取り出せたとしてもその 値には何の意味もないのです.)
図6(c)のiinc 1 10はintからintへ変換する命令なので,状態モデルの変更 は起こりません.これはi2c,i2s,inegなどでも同じです.
図6(d)のiaddでは,型情報以外はないので見た目では判断できませんが, int 値二つをポップしてint値一つがプッシュされています.モデルではint一 つがポップされたと考えても結果は同じですが,最初にオペランドスタック上 にint値が二つプッシュ済みでなければエラーになる点が異なります.図6(e) のif_icmp<op>でも同様にint値二つをポップしますが,プッシュはしま せん.
図6(f)newarray #10ではint型の配列インスタンスへの参照がプッシュされ
るわけですが,ここで必要なのは型情報だけなのでインスタンスそのものは生
成しません.このため参照の方も具体的な値を定義できず,状態モデルに代入
することができません.一つの方法としては,配列も含めて各クラスごとに一
意なIDを割り当てておき,参照を記録する代わりにそのIDを記録する方式が考
えられます.
次にもう少し複雑な命令について見てみましょう(図7).
この場合でも注意する点はそれほど変わりません.注意する点には次のような ものがあります.
これらの命令は本来かなり複雑な動作をしますが,ベリファイヤレベルで は単純なので図を見てもらえば概ね理解できると思います.なお,リターンや 例外(athrow)はメソッドを正常/異常終了させる命令なので,状態モデルの 更新やマージは必要ありません.
「次に実行する命令」というよりは「次に実行する可能性のあるすべての 命令」といった方がより正確でしょう.バイトコード=ベリファイヤは,次に 実行する可能性のある全ての命令に対し,いわば虱潰しに処理を進めます.次 に実行する命令は一つの場合もあれば,複数の場合もあります.またreturnや athrowのように一つもない場合もあります.
この「次に実行する命令」になる可能性のあるのは基本的に
の三つです.
正確には次のようになります.
例えば二つの例外テーブルで保護されているif_icmpgtの場合は,次の命令, 分岐先,二つの例外ハンドラ,の計4つの命令が「次に実行する命令」になり ます.
マージにはオペランドスタックのマージとローカル変数のマージがあり, その処理は微妙に異ります.
オペランドスタックのマージの例を図8に示します.
オペランドスタックのマージに成功するためには,次の条件を満たさなけ ればなりません.
双方の型が同じ場合はマージしても結果は同じです.異なっていて双方が 参照型の場合はマージの結果は双方に共通な最も近いスーパークラスになりま す.java.lang.Objectは全てのクラスの共通のスーパークラスなので,このよ うな共通のスーパークラスが存在することは保証されています.それ以外の場 合はマージに失敗し,ベリファイを異常終了します.
図9にローカル変数のマージの例を示します.
オペランドスタックのマージと似てますが,高さは常に同じであるため, そのための条件はありません.また型が異る場合の処理が異なります.
二つのローカル変数上で,対応するエントリに置かれているデータの型が 同じ場合は,オペランドスタックの時と同様に結果は変わりません.異なるも のの双方とも参照型である場合にマージの結果が双方に共通の最も近いスーパー クラスになる点も,オペランドスタックのマージと同じです.
異なるのはそれ以外の場合です.それ意外の組合せとしては参照型とプリ ミティブ型,プリミティブ型同士で型が違う,プリミティブ型と使用不可など が考えられますが,いずれの場合でもマージの結果は使用不可になります.こ のためローカル変数のマージが失敗することはありません.
以上のように,バイトコード=ベリファイヤのアルゴリズムは意外にシンプ ルで単純なものであることが分かると思います.シンプルで単純な技術という のは,Java全般に共通した特長であり,Javaの強みの一つだと言えるでしょう (注12).
(注12:CPUやOSのようにプラットフォームとなる技術には,高い汎用性や 柔軟性,拡張性が求められるため,通常は可能な限りシンプルな設計が求めら れます.複雑な技術は一見するとハイテクを駆使しているように見えるかもし れませんが,汎用性が低くなるなどの弱点があって意外に脆いものなのです.)
次回は特殊な処理が必要となるベリファイについて説明する予定です.
日本初のJavaOneということで当然私も参加しました.
私は知名度が低い(それ以上に顔が知られていない)だけに,読者の方との 語らいはほとんどありませんでした.この辺は,もう少し積極的に動いてもよ かったのかなと考えています.次ぎの機会があればプライベートな「仮想マシ ンBoF」か何かを主催してみるのも良いかも知れません.(一人も来ない可能性 もありますが....)
展示については,その性質上地味で小規模なものが多いとはいえ,Javaラ ンタイムやJavaプロセッサ(いずれもほとんどが組込み用)関連の展示も多数あ りました.
JavaプロセッサではARMのJazelle,富士通のMB92901,aJileのaJ-100, inSiliconのJVXtreme, Zucotto WIRELESSのXPRESSOなどがありました.Javaラ ンタイムではHPのChai,InsigniaのJeode,taoのIntentJTE,日立ソフトの SuperJ Engine,SUMSUNGの組込み用JITに加え,アプリックスのJTRON 仕様OS であるJBlendなどの展示がありました.
SuperJ EngineではSH用に(泥臭い)チューニング作業を行うことで,数倍の 高速化を達成したそうです.ある程度予想はしていましたが,こういうことは JavaVMの仕様書をいくら読んでも分からない部分で参考になります.またあの MD DISCAMの実物を触ったのは今回が初めてだったりしますが,操作性は噂ど おりなかなか良好だと感じました.
この辺は興味がない人には面白くもなんともないかもしれませんが,私の ような人間には,これだけのメンバーが勢ぞろいというだけでワクワクします. いつか機会があれば,この辺りの最新動向もフォローしていきたいと考えてい ます.
既にご存知の通り,JavaOneにて編集長の谷戸さんとばったり出会いました. (第一声は「奇遇ですね〜」.お互いここに来ていて当然の者同士なのだが, 何百何千といる中でばったり出会う確率はかなり低い.)JavaPRESSとの付き合 いは長いけれど,谷戸さんを含め編集部の人間と会ったのはこれが初めてです. なんせ,ず〜〜っとE-mailでのやりとりしかありませんでしたので.この業界 ならこういう形で仕事してる人も珍しくないでしょうね.考えてみればBtoC取 引なんてほとんどこの形だろうし,SOHOなんかでも似たようなものでは.
売店でデューク君人形を一ダースくらい買い占めようと企んでいたものの, 結局あっという間に売り切れたため一つも買えませんでした.もともと入荷量 も少なかったようです.残りのグッズは今ひとつ興味が湧かず,結局買ったの はJavaOne東京のバッジやキーホルダーくらい.
JavaOneは予想以上の盛況で,その分会場は窮屈なくらいでした.セッショ ンによっては立ち見まで出ていました.立ち見だけならまあ良いのですが,問 題は同時通訳レシーバーがないこと.席と同数のレシーバーしか用意してなかっ たらしく,立ち見の人にまではレシーバーが回りませんでした.発表者の大半 が英語ですから,英語が分からない人にはちと辛い.とはいえ,質疑応答を英 語でやる人もかなりいたことから見ると,一流の人ならば同時通訳なしでも困 らない人も多いのかも.(私は....f(^^;)
展示会場の方は,やはりJavaランタイムとJavaプロセッサ関係を中心に回 りました.どっちかというと地味でマイナーな業界だけにこういう人は珍しい のですかね.
「2001年 デューク君の旅」Tシャツももらってきました.あの映像は爆笑 ものなんですが,「最近の若い者」(差別的表現(^^; )はほとんど本も読まな いから知らないかな?アーサー=C=クラーク原作の古典的SF映画としても有名 だと思うのですがねえ.もちろん私はモノリスが出る前,BGMの段階で気づき ましたがね.2002年はカレルレンでも登場したりして.(R=ダニール=オリバー やピアスンのパペッティアやガニメアンだったりすると,何がなにやら分から んでしょうね.)
MD DISCAMは想像していた以上に良好な操作性を実現していました.あの小 さな画面であれだけ高度な機能が実現されていながら,マニュアルを読まなく ても十分使えるとは立派なものです.Java以外で記述した場合でもあの操作性 を実現するのは不可能ではないでしょうが,その場合は開発期間とコストが増 大して,到底採算が合わなくなるんでしょうね.(ちなみに某社のWind○wsCE の場合は,素人はおろかWind○ws95/NTユーザーでもろくに使えなかったりす る.基本操作さえできない人が大半だろう.CEの場合は「一見」95やNTに似て いるものの操作性は全く異なる.基本操作さえ共通していない.)
私は行きませんでしたがJavaNightはほとんど満員電車のようなすし詰め 状態だったとか.どうも当初予想の3〜4倍程度の人が集まった感じです.
不満なのは休憩時間が短いこと.前のセッションが終わったあと,移動時 間を考慮するとほとんど休みがない.朝から晩まで休みなしでレベルの高いセッ ションやBoFを聞き続けるのはいくらなんでも体が(というより頭が)もたな い.昼休みだって,移動時間とパビリオンを回る時間を引くと,ほとんど弁当 を飲み込むくらいの時間しか残りません.おかげで三日目ともなると疲労困憊.
展示会場では来場者に対し様々なプレゼントが用意されていましたが,ちょっ と目を引いたのが「Chaiのティーカップ」.駄洒落というが親父ギャグという か,こういう寒すぎるセンスは大好きです.ま,と言ってもあれを見て駄洒落 だと分かるのは,Chaiが何か知ってる人に限られますが.私はもちろん一目で 分かりましたけどね.この業界長いし.
意外と面白かったのはSUNでもらったボールペン.SUNに悪気は無いですが, このボールペンはヒューマン=インターフェースの優れた反面教師です.一見 すると単なるノック式ボールペンに過ぎないのですが,実は「ひねる」タイプ のボールペンなのです!これには百人中,九十九人は騙されるでしょう.これ を狙って作ったのなら,ある意味立派です.持っている方は大切にしましょう. (^^)
ちなみに某HPのJavaOneのページに私の写真が載ってました.なにも,こん なむさ苦しいおっさんを撮らんでも...
何人かと名刺交換もしましたが,普段表に出ないだけにかなりのレア物で す.どこぞのアイドルのサインなんかと違って,もらって喜ぶ人もいないけど.
http://www.netgene.co.jp/