0x19fの日報

なるべく毎日書きます

【メモ】UNIX V6コードリーディング(メモリ周りの整理/まとめ)

今回の内容

前回まではトラップハンドラについて読み進めていました.

0x19f.hatenablog.com

前回とは大きく内容が変わってメモリ周りの話を整理していきたいと思います(先にシグナルを読んでもよかったかも). 実は先々週あたりの勉強会を思い出して書いているので内容が確かじゃないかもしれないです. 書籍のページ数が結構飛び飛びになるので, 適宜どのあたりの話をしているか書いていきたいと思います.

アドレス変換(p52〜p55)

仮想アドレスから物理アドレスへの変換はp52に書かれていますが, 1点だけ補足を. APRが8つあるということは, 逆に言うと仮想アドレス空間は8Kバイト(= 213)毎に違うAPRを参照して物理アドレスへの変換を行うことになります. p50に書かれている「データ領域はテキストセグメントの後ろの8Kバイト刻みのアドレスに割り当てられます」の理由はここにあります. テキストセグメントとデータセグメントは物理アドレス上では連続していません. つまり, 同じAPRに割り当てられません. このあたりはアドレス変換の仕方についてよく考えると確かにそうなるなぁという感じになります.

仮想アドレス空間(p48〜p52)

細かいメモリの操作をする箇所を読むにあたって, 仮想アドレス空間物理アドレス空間がどのようにマッピングされているかを理解しておくと非常に理解が進みます. 意識しておいたほうが良さそうなポイントをいくつか.

  1. テキストセグメントとデータセグメントは物理メモリ上では別々の連続した領域.
  2. テキストセグメントはプロセス間で共有される.
  3. データセグメントはPPDA, データ領域(ヒープ領域を含む), スタック領域からなる.
  4. PPDAにはuser構造体とカーネルスタック領域が置かれる.
  5. PPDAはユーザープロセスの仮想アドレス空間マッピングされない(ユーザー空間からはアクセスできない).
  6. データ領域とスタック領域は物理アドレス空間では連続している.
  7. ヒープ領域はアドレスが大きくなる方向に, スタック領域は小さくなる方向に伸びていく.
  8. スタック領域は仮想アドレス空間の一番上位(0xffff)に割り当てられている.
  9. 物理アドレス上でヒープとスタックがぶつかった場合は拡張が行われる(expand関数).

仮想アドレス空間の操作

仮想アドレス空間に対する操作を行っている(と思われる箇所)をピックアップしてみました.

仮想アドレス空間マッピングの変更はestabur, suregあたりで行われるようです(p103〜). 細かいところは読めてないですが, estaburでuser構造体にAPRにセットする情報を格納, suregでuser構造体の情報に従ってAPRの値を操作するようです.

データ領域の拡張はbreakシステムコールで実現されます(p118). Cライブラリのmallocなどの内部で使用されるようです. 長年疑問だったmallocした時のメモリはどこから出てくるのかに対する答え(?)が少し得られたようで, 個人的には結構面白いと感じました. 実際にはOS側はデータ領域を拡張/縮小しているだけで, その他の諸々はCライブラリのmallocがやってくれているという感じなんでしょうか?

スタック領域の拡張はトラップハンドラの中で行われます(p176, grow).

ちなみに, 実行プロセスのPPDAはカーネル用のAPR6から参照できるようになっており, プログラム中ではuという変数で参照できます(p54一番下). この切り替えはコンテキストスイッチの際にしれっと行われています(p78). 当然ですが, このときにユーザー空間のマッピングが変更されます. おそらく, estabursuregが分かれている理由はこの辺にあって, コンテキストスイッチの際はuser構造体に格納された情報からマッピングし直すだけなのでsuregだけが呼び出されてます. (細かく中を読めていないので間違ってるかもしれないですが...)

まとめ

メモリ周りをいろいろと整理してみましたが, これを一発で理解するのは無理ですね(). ただ, いろいろと考えながら読んでみると本当によくできているなぁと思わされることばかりです.

次回の予定

スワッピングあたり?

【メモ】UNIX V6コードリーディング(トラップハンドラ/システムコール, p171〜184)

今回の内容

前回は, 主にタイマー割り込みに関連する箇所を読んでいました.

0x19f.hatenablog.com

今回は, トラップハンドラでの処理を見ていきます. システムコールについてもこの辺りに書かれています.

トラップハンドラtrap

トラップハンドラも割り込みハンドラ同様に呼び出しが行われcsvが実行された後のスタックの状態は以下のようになります.

引数 備考
sp pc csvから戻るのに使用されるだけ(あまり関係ない)
退避されたr2
退避されたr3
退避されたr4
r5 退避されたr5
pc(割り込みハンドラから返る先)
マスクされたPSW dev
割り込まれたプロセスのsp sp
古いr1 r1
PSW nps
古いr0 r0
割り込まれたプロセスのpc pc
割り込まれたプロセスのPSW ps

trap関数の9行目でu.u_ar0に引数r0のアドレスを格納していますが, これはスタック上のアドレスになります. 実際にスタック上の値を操作する際はu.u_ar0[R0]のようにして操作するのですが, R0はただの定数でスタック上のr0が格納されている位置からのオフセットです. 同様にしてR0R7RPS(PSWの操作に用いる)を使ってスタック上の値を書き換えています. トラップハンドラ内ではあまりこの操作は行われませんが, システムコールハンドラ内で行われるのでしょうか?

その後のswitch分でdev(トラップ種別)の値によって処理が分岐していきますが, 基本的にはシグナルを送って処理は終わりです. 例外はillegal instruction, floating exception(カーネルプロセス), segmentation exception, システムコールの時です.

illegal instructionの時はSETDなる謎の命令か否かをチェックしているようですが, 正直なんのためのものなのかあまりわかってないです.

カーネルプロセスでは浮動小数点演算を行わないらしいのですが, PDP11の特性上ユーザープロセスが行った浮動小数点演算によるfloating exceptionがトラップ発生後に引き起こされることがあるらしく, その場合はそのユーザープロセスにシグナルを送って関数から抜けます.

segmentation exceptionの場合, スタックを拡張します. それでもexceptionを回避できない場合は, プロセスにシグナルを送ります. このスタックの拡張はgrowという関数の中で行われるのですが, 仮想メモリ空間の話とかをあまりちゃんと理解していないので一旦飛ばします. ちなみに, growの前にbackupという関数が実行されているのですが, この関数はUNIX V6の中で最難関らしいです. exceptionが起きた時の状態を再現する関数らしいのですが, すべてアセンブリで書かれておりおまけに中でPDP11にはないレジスタの挙動をエミュレートしているようです. 実際にソースコードを読むと/ hard partというコメントが見つけられます. 最難関なのでは仕方ないので飛ばします.

システムコールの場合の処理の前にシステムコールの処理の流れをまとめたいと思います.

システムコールの処理の流れ

システムコールハンドラはsysent構造体によって管理されます. この構造体にはシステムコールの引数の数とハンドラのアドレスが格納されます.

sysent構造体の配列sysentに各システムコールの引数の数とハンドラのアドレスが格納されています. この配列は要素数が64で, 添字はsys命令のオペランド(6 bit)と対応しています.

システムコールの0番は間接呼び出しに割り当てられています. 間接呼び出しというものを自分は初めて知ったのですが, どうやら普通の呼び出しと異なるのは引数の渡し方のようです. 通常の呼び出しは, sys命令の後に引数が埋め込まれます. 一方で, 間接呼び出しの場合は, sys命令の後に引数のアドレスが埋め込まれます. これは推測なのですが, 直接命令の場合は引数が埋め込まれる場所がテキストセグメントになるため, 動的にシステムコールの引数が変わる場合に困ってしまうのでこのような仕組みが用意されているのではないかと考えています. sys命令の次にデータ領域のアドレスを埋め込んでおけば, 複数のプロセスでテキストセグメントを共有しつつ個別に引数を扱うことができます. あるいは, 引数の数が動的に変わる場合などでしょうか.

システムコールの引数は上述のようなsys命令の後に埋め込むものと, r0を経由するものがあります.

トラップハンドラ内でのシステムコールの処理

話はトラップハンドラのswitch文に戻ってくるのですが, システムコールの場合の処理を見ていきます. 基本的にはエラーフラグを初期化, 間接呼び出し/直接呼び出しそれぞれの場合で引数とシステムコールの番号を取得, trap1を呼び出してシステムコールハンドラを実行, エラーフラグの処理という流れです.

特筆すべきなのがtrap1を用いてハンドラを呼び出している点です. trap1の中を見てみるとわかるのですが, フラグを立ててからsavuしてシステムコールハンドラを呼び出しています. これが意味するところなのですが, これはシステムコール中にシグナルを受け取った場合にエラーを起こすためのものらしいです. 詳しくはシグナル処理のあたりで書かれています. このsavuに対応するaretusleep関数の末尾にあります. このエラーはシステムコールハンドラがsleepを実行して処理を中断している間にシグナルを受け取った場合に起こるものらしいです. シグナルを受け取った場合は, trap1が返る場所から処理が継続されます. この場合は, フラグが立ったまま処理が続行されるため, その後のtrapでの処理でユーザープロセスにはエラーが返ります. このエラーを見てユーザープロセスは再度システムコールを実行することができるようになっています.

まとめ

ということで割り込みとトラップを見てきましたが, なかなか複雑だなぁという感想です. もう一度プロセス管理あたりも読み直してみると納得感が増すのかなぁと思います.

次回の予定

シグナル?メモリ管理? 未定です

Code Thanks Festival 2017 参加記

Code Thanks Festival 2017に参加してきました

12/2(土)に行われたCode Thanks Festival 2017に参加してきました. 運良く予選で良いパフォーマンスを出すことができて, 参加権を勝ち取ったという感じです.

www.recruit-jinji.jp

会場到着まで

起きると脳が直感的に開始時刻に間に合わないことを理解した. 開始時刻が11:25なのに対して僕が起きた時刻が10:30, 会場のお台場まで1時間はかかるのでどう考えても間に合わない. とにかく家を飛び出した. 久しぶりのゆりかもめに揺られながら会場への到着を待つ.

結局なんとかコンテスト開始前には会場にたどり着くことができ, ほっと胸を撫でおろす.

コンテスト

コンテストは100 - 200 - 300 - 300 - 400 - 500 - 600 - 600の計8問. 1800点以上だとパーカーがもらえるとのことなので1800点を目標に頑張ろうという気持ちになる.

コンテスト開始と同時にA, B, Cと順調にACしていく. D問題には少し苦戦した, 制約を見るにgcdなんだろうなぁと思うのだがどうすればいいのかわからない. いろいろと悩むが, 高校数学で教わった1次不定方程式を思い出しAC. あと2問でパーカーだ.

しかし, ものごとはそう順調には進まない. E問題がインタラクティブ形式, 問題を見てすぐに13の累乗をクエリとして出力すればいいと思った. しかし, これが罠だった. よくよく考えると134は10000を超えてしまうのだ. 頭のついていない僕はこのことに気づくのに30分を要した. 問題を読み始めてから1時間ほど経つが一向に糸口がつかめない. 焦りばかりが募っていく. 落ち着け, まだ問題は他にもあるんだ, そう自分自身に言い聞かせた.

心を切り替えてF問題を読んでいく. 制約が小さければ, 単純なDPだ. しかし, 制約が大きい. 代わりに和が一定で抑えられるという謎の条件が付け加えられている. 瞬間的に頭にルートという言葉が浮かんできた. そうだ, 何かがルートで抑えられるに違いない. 大量のWAを出しながら, 一歩ずつ答えに近づいていく. 残り40分というところでついにFを通した.

ここで, 苦戦していたEに戻る. これを通せばパーカーだ, 何としても通したい. なんらかの方法でクエリからコインの重さが復元可能なのであれば, 和と5種類のコインの重さの組は1対1に対応するはずだ. そう思い手当たり次第にいろいろな枚数の組み合わせで, このような条件を満たすものを探し始めた. すると5の累乗であればこの条件を満たすことを発見した. 残り20分, まだ焦る時間じゃない. そう言い聞かせながら, 不恰好なプログラムを書いていく. クエリの応答からコインの重さを逆引きするテーブルを作りそれを参照する作戦だ. 一心不乱にコピペを駆使してプログラムを書き上げ, 提出した. 結果は......AC. 残り時間は10分だった.

結果は参加者100人中の54位. なによりも1800点を達成できたことが嬉しかった.

表彰 and 解説

大学の先輩であらせられるtossyさんが1位だったり, imulanさんが3位だったりして, やはり目指すべきはあそこなんだなぁと思った. ふーらくたるさんが折角の5位なのにマイクが入っておらずコメントが全く聞き取れなくておもしろかった.

あと, chokudaiさんはファッション英語勢なのかと思っていたけれど, 本当に英語苦手みたいだった.

懇親会

TLのみなさんにこんにちは. 名前入りの名札を見て「あの赤いCの人」とわかってもらえるのは非常に便利なので, みなさんも実名Twitterしていきませう. 懇親会の間にtreeoneさんの通知が400件溜まっていたらしく, 本当におもしろい.

解散の後も参加者の方々とボーリングしたりカラオケしたりしてきました. いやー, 非常に楽しかったですねぇ.

【メモ】UNIX V6コードリーディング(クロック割り込み, p160〜170)

今回の内容

前回までは, 割り込みとトラップが発生してからハンドラが実行されるまでの流れを追っていました.

0x19f.hatenablog.com

今回は, クロック割り込みハンドラのお話です. クロック割り込みによって処理される指定時間実行とsleepシステムコールも一緒に見ていきます.

クロック装置

UNIX V6では以下の2種類のクロックが使用可能です.

前者のクロックは電源周波数が50Hzか60Hzかによってクロック周波数が変わります. 後者のクロックの間隔などを設定することができるようです.

クロック周波数はparams.hの中でHZとしてdefineされているようです. 書籍ではどちらの装置を用いるにしてもクロック周波数が60Hzであるという前提で解説を進めています.

クロック割り込みハンドラ

クロック割り込みハンドラはC言語で書かれたclock関数になります. この関数に前回まで見てきた箇所で積まれたスタックの中身が引数として渡ります.

C言語で書かれている関数は, コンパイルの際に先頭にcsvというアセンブリで書かれた関数の実行が挿入されます. 簡単に説明だけしておくと, r2, r3, r4を退避する関数です. このcsvについては, 書籍の78ページから詳しく説明されています. (このメモを書き始める前に読んでます.)

csvが実行された直後のスタックの状態とclock関数の引数の対応は以下のようになります. 引数の内容がわからなくなったらここを見ましょう.

引数 備考
sp pc csvから戻るのに使用されるだけ(あまり関係ない)
退避されたr2
退避されたr3
退避されたr4
r5 退避されたr5
pc(割り込みハンドラから返る先)
マスクされたPSW dev
割り込まれたプロセスのsp sp
古いr1 r1
PSW nps
古いr0 r0
割り込まれたプロセスのpc pc
割り込まれたプロセスのPSW ps

クロック割り込みハンドラの中身を読んでいくと以下の処理が上から順にされていることがわかります.

  • クロック毎の処理
    • クロック装置のレジスタを再設定
    • 指定時間実行の処理を行う ... (1)
    • CPU時間のインクリメント
  • 1秒毎の処理
    • 時刻のインクリメント
    • sleepしているプロセスを起こす ... (2)
    • プロセスの実行優先度を再計算 ... (3)
    • スワップ処理を継続できない場合の再スケジューリング ... (4)
    • シグナル処理 ... (5)
  • 4秒毎の処理

以下, いくつか数字を振ったものについて補足しておきます.

(1) 指定時間実行

これについては, 書籍の162ページから詳しく書かれています. 指定時間に実行したい関数を登録するtimeout関数などのソースコードが出てきますが, 書いてある通りに読めば難しい箇所はないと思います. クロック割り込みハンドラの中では, 指定時間になった関数の実行をしています.

(2) sleepしているプロセスを起こす

書籍の165ページにsleepシステムコールのハンドラであるsslepが掲載されているのですが, これだけでは少し何が起きているのかわからないのでメモをば.

まず, timeグローバル変数で現在の時刻を秒単位で管理しています. いわゆるUNIX時間(?). この時刻データは, 2 word分(32 bit)に収められています. dpadd, dpcmpはこの2 wordをまとめて足したり比較したりするための関数です. 書籍の441ページに説明があります.

もう一つ関数の中に出てくるグローバル変数に, toutという時刻データがあります. これは, 次にsleepから起こされる関数が起こされる時刻を表しています.

個人的にここが今回得られた理解の中で一番おもしろかったのですが, sleepしているプロセスはtoutが示す時刻を過ぎたらすべて起こされます. そして, 指定された時刻を過ぎていないプロセスは再びsleep状態に戻ります.

これを実現しているのがsslep関数中のwhile文です. while文の条件が真になるのは, 指定された秒数分sleepした場合のみです. 真になるまでは, if文によって直近に起こさないといけないプロセスを起こす時間をtoutに格納して, sleep関数を呼び出しています. sleep関数については, 73ページにソースコードが掲載されています. sleep関数の第一引数には待っている資源のアドレスを渡すのですが, ここではtoutのアドレスを渡しています. clock関数の中でwakeup関数にtoutを渡して, すべてのsleep中のプロセスを起こしています. 起こされたプロセスはwhile文の最後から処理を再開し, while文の継続条件を判定してsslep関数から抜けるもしくは再度sleep関数を呼び出します.

このようにしてsleepシステムコールは実現されているわけですが, これって何かに似てるなーと思ったらJavaのマルチスレッドプログラミングで出てくるwait/notifyAllと同じようなもんかなという気持ちになりました. あれもnotifyAllですべてのプロセスが起きた時にwhile文でガードするってことをしますよね.

(3) プロセスの実行優先度を再計算

プロセスのあたりは一応読んだはずなのですが, 細かいところはかなり忘れているので再度読み直します...

(4) スワップを継続できない場合の再スケジューリング

スワップ辺りを飛ばしているので, あまりよくわかってないです...

(5) シグナル処理

シグナルの話は次の章に出てくるので一旦飛ばす.

(6) lightning bolt

lightning boltというのは, カーネルが特に待ち時間は決まっていないけれど適当に待たせておきたい時に使用するものらしいです. lbolt変数を待ち資源にしてsleepさせておくんでしょうか? 4秒に1度clock関数の中で起こされます.

次回の予定

トラップハンドラの中身を読み進めていきたいと思います.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159, その2)

今回の内容

前回の続きから.
アセンブリで書かれたtrapcallを詳しく見ていきます.

0x19f.hatenablog.com

前回解決できなかった疑問点

nofaultが設定されている場合の割り込み箇所への復帰方法について, 前回の記事には,

もう一つわからないことがあって, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.

なんてことを書いたのですが, そもそも前提が間違ってました.
nofaultを設定した上で命令を実行するのはカーネルプロセスでした.
このnofaultというのは, カーネルプロセスが例外が起きるとまずい命令を実行する前に設定するというものみたいです.
ここからは推測ですが, こういった命令を実行する直前にカーネルnofaultにエラーハンドラを設定しカーネルスタックに戻り先のアドレスを積んだ状態で命令を実行するのではないかと.
すると, 例外が起きた場合には, スタックに戻り先のアドレスのみが積まれた状態でnofaultが指すアドレスにジャンプし, その処理の最後にrtsで戻り先に復帰するという風になるんじゃないでしょうか.

こっちの方はわかってないのですが, 読み進めていく上ではあまり問題なさそうなので一旦スルーします.

ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.

trapnofaultが設定されていない場合

nofaultに値が入っていない場合は, 前回軽く書いた通りSR0, SR2を退避, SR0を初期化してjsr命令でcall1へとジャンプします.
この時, 古いr0の値がスタックに積まれ, r0には_trap(C言語で書かれたtrap関数のアドレス)が格納されることに注意してください.

call1にジャンプすると, spをひとつ上にずらし, プロセッサ優先度を0にし, callの途中へとジャンプします.
ここからの処理は後述するcallでの処理とほぼ同じです.
callの1行目を実行した直後とスタック, r0の状態は同じ形になっている点に注意.

最終的なスタックの状態は以下のようになっており, r0にはtrap関数のアドレスが入っています.

sp トラップ種別を含んだPSW
古いr0
割り込まれたプロセスのpc
割り込まれたプロセスのPSW

callの処理

前々回ぐらいのおさらいになるのですが, callに処理が移った時のスタックの状態は以下のようになっています.

sp 古いr0
割り込まれたプロセスのpc
割り込まれたプロセスのPSW

ここにPSWの値が積まれて以下のような状態になります.

sp PSW
古いr0
割り込まれたプロセスのpc
割り込まれたプロセスのPSW

ここからはtrapnofaultが設定されていない場合と同じ処理になります.
スタックが同じような形をしているところに気をつけてください.

まず, 古いr1がスタックに積まれます.
次にmfpi命令を用いて割り込まれたプロセスのspをスタックに積みます.
mfpi命令はPSWの前のモードの仮想アドレス空間から値を取得して現在のモードのスタックに積む命令です.
ここで得たspを用いて割込みハンドラの中でスタックを操作するのかな?と予想しています.
さらに, SPWをスタックに積み, 下位5ビット以外を0でクリアします.

ここで, 割り込まれたプロセスがユーザーモードだったかカーネルモードだったかで処理が分岐するのですが, やっていることは大きくは変わらないです.

ユーザーモードだった場合は, jsr命令で現在のpcをスタックに積みながらr0に設定された割り込みハンドラにジャンプします.
ここで積んだpcが割り込みハンドラからの戻り先になります.
割り込みハンドラから処理が戻ると, コンテキストスイッチを行います.
割り込みによってプロセスの実行可能状態や優先度が変化した分を考慮するためのものかなと考えています.
最後に, mtpi命令で前モードのspの値を戻します.

カーネルモードだった場合は, PSWの前モードをユーザーモードに書き換えてから, 割み込みハンドラへジャンプします.
ここは上記と同様にjsrを用いています.

割り込みハンドラが呼び出される時のスタックは以下のような状態になります.
実際にはこれがハンドラ関数の引数として扱われます.
具体的にどのように使われるのかはclock, trapなどの関数を見ていくことになるかと思います.

sp pc(割り込みハンドラから返る先)
マスクされたPSW
割り込まれたプロセスのsp
古いr1
PSW
古いr0
割り込まれたプロセスのpc
割り込まれたプロセスのPSW

ここからは両モード共通です.
スタックに積んでいたr1, r0を復帰してrtt命令で割り込まれた箇所に復帰します.

まとめ

ソースコードを読むだけだと理解しづらいので, 簡単にまとめておきます.

  • カーネルは例外が起こりうる命令を実行する前にnofaultを設定することがある.
  • nofaultが設定されているトラップは設定されたハンドラによって処理される.
  • そうでないトラップはtrap関数によって処理される.
  • 割り込みはそれぞれの割り込みハンドラによって処理される.

次回の予定

割り込みハンドラ(clock)とトラップハンドラ(trap)を読んでいく予定.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159)

今回の内容

前回の続きから.
アセンブリで書かれたcallとtrapの実行を詳しく見ていきます.

0x19f.hatenablog.com

call, trapの実行

書籍ではあまり言及されていない箇所が多くあまり進みませんでした.
以下, ざっくりとした理解です.
(間違っている箇所がありそう.)

割り込みの場合は, callの内部でr0に格納された割り込みハンドラが呼び出されます.
このr0に割り込みハンドラが格納される箇所は前回見たとおりです.

トラップの場合は, nofaultにトラップハンドラが指定されている場合とそうでない場合で分岐が発生します.
nofaultにトラップハンドラが指定されている場合は, そのトラップハンドラが呼び出されます.
そうでない場合は, callの中へとジャンプしC言語で書かれたtrap関数が呼び出されます.
(アセンブリ中では_trapで参照されています.)

基本的には, スタックになにが積まれていくのかが大事なようです.
ちらっと先読みした感じだと, この後割り込みハンドラ/トラップハンドラに処理が移った際にこのスタックがC言語で書かれた関数の引数になるようです.

trap

トラップ種別が含まれたPSWの値をカーネルスタックに格納します.
trap関数内でこの種別によって処理が分岐するんでしょうか.
nofaultが0かで分岐するのをtst, bne命令で実現しています.

nofaultにトラップハンドラが指定されている場合:
SR0レジスタを1で初期化.
ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.
実は割り込みが発生したタイミングでMMUが無効になってたりするんでしょうか.
nofaultカーネルスタック上の割り込みされたプロセスのpcが格納されている場所に格納.
rtt命令でnofaultが指すトラップハンドラに飛びます.
もう一つよくわかっていないのが, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.
rttによって割り込まれたプロセスのPSWとpcが元に戻されているところまではわかるのですが...

nofaultにトラップハンドラが指定されていない場合: あまり細かく読んでいないのでざっくりと. jsr命令でr0を退避, _trapのアドレスを代わりに格納してcall1にジャンプ. callの中へジャンプ.

call

全然読めてないです.
最終的には割り込みハンドラへと飛んでいく感じ?

次回の予定

もう少しcallとtrapを詳しく.

DDCC2017本戦に参加してきました

11/3(金)にDisco Discovery Channel Code Contest 2017の本戦に参加してきました.
予選ではC問題を解くのが遅めで本戦通らないかと思ったのですが, 19卒枠の繰り上がりで本戦に参加することができました.

discoverychannel.jp

会場はDiscoのオフィスでした(200人も入れるスペースがあってすごい).
到着するとすでに多くの方がDDCC Tシャツに着替えて準備万端という感じでした.

コンテスト本戦

まずは, 10:30からコンテスト本戦.

ddcc2017-final.contest.atcoder.jp

コンテスト時間は2時間で問題は5問.
自分はABを解いて2完, 最終的な順位は200人中の88位.
90分間座ってるだけコンテストでした.

A問題:
問題を見た瞬間に第一象限だけ調べて4倍しようと思ったのですが, 200/Kや300/Kが奇数の場合に正方形の頂点がグリッド上に乗らないことに気づき場合分け.
結構時間がかかってしまいました.
円の中心を(0, 0)に置くって固定観念にとらわれなければもう少し楽に解けますね...

B問題:
サンプルを見てこれはA[i]とZのGCDを計算してLCMを取ればいいのでは?と思い書いてみたら通ってしまいました.
個人的にはAよりもBの方が簡単だと思います().

C問題:
何もわからない, ばなな.
そもそもグラフの上でループを考える時にどうすればいいのかが全くわかりませんでした.
解説を読んでもあんまり理解できてないです.

D問題:
一応目を通しましたが, 見た瞬間にわからなさそうだということがわかりました(?).

E問題:
実はC問題がわからなさすぎてコンテスト中はずっとE問題を考えていました.
まぁ, もちろん解けませんでしたよね.
これ以上辺を伸ばしたら直径を維持できないという状態になったあとは葉を選んで辺を伸ばしていけばいいと思ったのですが, その状態までがどうすればいいのかわからず.

お昼のビュッフェ

お昼は会場でビュッフェでした.
以前にオンサイトでお会いした方やTwitterではよく絡むけど実際には会ったことないという方と交流できて楽しかったです.

ただし, お腹いっぱいになってきたタイミングで寿司が出てきたことだけは許さない().

座談会

お昼の後は, Ponanza開発者の山本さんとプロ棋士の西尾さんの対談(with モデレーターのchokudaiさん)でした.

いろいろと面白いお話が聞けたのですが, 中でも興味深かったのがプログラムを生成する人工知能が今後どれぐらいの速度で成長するのかという話題.
競技プログラミングにおいても問題を解くAIというのがちょこちょこ研究されているらしいですが, 驚くことにそういったAIはすでにAtCoderのレートで言うと1000を超えてきているとのこと.

ちなみに, このAIはサンプルの入出力に合うようなプログラムをひたすら投げ続けるというものみたいです.
前日にDDCC参加者のみなさんとご飯を食べていた時に話題に出たのですが, 過去のAtCoderのコンテストでこの方法を使って3秒でA問題をACしたという事例があるそうです.
(探してみたけれどこれでしょうか?Submission #286413 - AtCoder Regular Contest 030 | AtCoder)

問題の内容を把握した上で正解を導くというのはまだまだ先になりそうですが, こういった無理やり試す系のものはこれからどうなっていくのか楽しみですね.
懇親会の時にも, CodeforcesなどのHackが可能なコンテストなら大量にプログラムを収集してきて適当な入力を入れてみて出力が同じになるものとそうでないものに分ければ後者をHackできるのでは?などといった話が出ていました.

他に印象に残っているのは, プロ棋士の方が機械学習のアイディアを取り入れて将棋の学習をしている話でしょうか.
細かいことは忘れてしまったのですが, 棋譜を学習データとテストデータに分けるらしいです.
いや, 凄まじいなと...

会社見学

会社見学ではA問題の元ネタ(?)であるシリコンウェハから正方形のチップを切り出す機械などを見せていただきました.
そもそも「Discoって何してる会社なの?」という感じだったので, 非常におもしろかったです.
ちなみに, シリコンウェハが円盤状なのはシリコンの単結晶が円柱状になっていてそれをスライスしてシリコンウェハが作られるかららしいです.

懇親会 & 記念撮影

懇親会も豪華で再びお寿司が出てきました.
なお, お寿司は一瞬でなくなりました.
一般枠で参加されていた大学のOBの方とお話ができたりもしました.

あと, 話題のchokudaiさん看板で記念撮影もしてきました.
僕はchokudaiさん本人が看板の写真と同じポーズをしている公式コラ画像(?)が一番好きです.

最後は参加者全員で記念撮影.
コンテスト運営の方々, お話してくださった参加者のみなさん, ありがとうごいました.
CODE THANKS FESTIVALに参加される方はまた近いうちに, そうでない方はまたいつかお会いしましょう.