ABC #139 D - ModSum $p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。 ABC #139 E - League $i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。 ABC #139 F - Engines あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく（後々、楽になる）。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。 あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。 ABC #140 D - Fce Produces Unhappiness まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> （空）のように操作を繰り返せば良い。 ABC #140 E - Second Sum Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setのlower_boundで見つけた。 ...

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。 まとめて書いておく。 ABC #136 D - Gathering Children 一度RLの組に入ると抜け出せない。 偶数距離を移動させて、RLの組にくっ付ける。 ABC #136 E - Max GCD ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。 前と後の両方向から、累積和を求めておく。 ABC #136 F - Enclosed Points ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。 点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える 点$x$を含む場合は単純に$ABCD$ 領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。 ABC #137 D - Summer Vacation アルバイトはどれも一日で終るためコストは変わらず、単純に支払日だけが異なるだけ。 アルバイトを報酬の大きい順に見ていって、できるだけ後ろの日程から埋めていく。 ABC #137 E - Coins Respawn まず、DFSを使って、始点と終点どちらからも到達可能な頂点の集合$S$を求める。 あとはコストに$-1$を掛けて、ベルマンフォード法を適用して、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含まれていたら、$-1$を返す。 単純に、ベルマンフォード法で閉路を見つけるだけでは不十分なことに注意する。 ABC #137 F - Polynomial Construction フェルマーの小定理を使う。頻出テクニックだと思うので、復習しておきたい。 $a = {0,0,…,0}$の$i$番目を1にした$a’ = {0,0,..,1,…,0}$を考える。 そうすると、$a$を使った$f$と、$a’$を使った$f’$は以下のような関係になる。 これをすべての1が立っている$i$について、計算すればよい。 $$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$ ...

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説放送を聞いて、やっとわかってきた。 自分用のメモなので、日本語が雑になっている。。 ABC #135 D - Digits Parade dp[i][j]をi桁目まで見た時に、あまりがjとなる場合の数として、求めていく。 ABC #135 E - Golf 事前に、X>=0,Y>=0にしておく 1) X+Yが奇数 かつ Kが偶数 -1を返す。 どうやっても奇数番地にはたどり着けない 2) X+Y>K n=ceil(X+Y/K)として、X+Y と nK の偶奇が異ればn++とする。余剰 nK-X-Y のために、冗長な経路を作る。 ここで、X=0 だと、序盤の移動において、マンハッタン距離が正しくないので、swap(X,Y)しておく（もちろん出力時には戻す）。 +(X,Y) | Y (0,0)+ - t | | t = (nK-X-Y)/2 |-----| X 3)X+Y<K 3-1) X+Yが偶数 n=2となる。それ以降の計算は、2) と同じ。 +(X,Y) | Y (0,0)+ - t | | t = (2K-X-Y)/2 |-----| X 3-2) X+Yが奇数（ 1) の条件よりKも奇数） n=3になる。これは思いつかない。この場合のみ、X, Y両方向に冗長な経路を取る必要がある。 ...

前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、まとめておく。 まだまだ解説なしでは解けない。。 ABC #130 F - Minimum Bounding Box dp[i][j]をi,j番目が部分共通文字列となるときの組み合わせ数とする。 更新式もメモ化しておくと高速に計算できる。 ABC #131 F - Must Be Rectangular! (x,y)座標を2部グラフとみなす。 グラフに置き換えて考えることでスムーズに解ける。 ABC #132 F - Small Products N/xが同じ値になるxを同じグループとみなして、グループごとに計算を進める。 DPを圧縮していくイメージ。 ABC #133 F - Colorful Tree 木構造の頂点間の距離はLCA（最小共通祖先）を使うことで求めることができる。 実装解説は蟻本にまとまっている。 あらかじめクエリを先読みしておき、必要な頂点と色を抽出しておく。 DFSしつつ必要な値を埋めていく。

Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。 ABC #126 F - XOR Matching https://atcoder.jp/contests/abc126/submissions/5909511 M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。 このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。 K以外の要素について：間にはKだけが残ることになるので、条件を満す Kについて：間には <7,6,...,0>からKを除いた降順の数列 が残る。XORをとるとKになるので条件を満たす。 ABC #127 F - Absolute Minima https://atcoder.jp/contests/abc127/submissions/5930963 中央値が最小値となる性質を利用する。中央値が２つあるときには、左側を採用する。 中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。 解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、 ナイーブに一度だけ入れる方法でも問題ない。 キューが片方に偏らないように、整理する必要がある。 更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。 一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。 ABC #128 F - Frog Jump https://atcoder.jp/contests/abc128/submissions/5921198 A、Bをそのまま扱うのではなく、C=A-B と k=何度戻りが発生するか という変数に置き換えて考える。 Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。 同一の蓮を二度以上通るかどうかは、単純にsetで管理した。 ABC #129 F - Takahashi’s Basics in Education and Learning https://atcoder.jp/contests/abc129/submissions/5945816 難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,7と11,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。 A sum_i=0^(l-1) 10^k^iとB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。 どちらも漸化式に変換して解く（コード中のf,gに対応）。 解説動画を見るのがおすすめ。 ...

O’REILLYの「Go言語による並行処理」を読んので、自分用にメモを残しておく。 また、折角なのでhttps://godoc.org/github.com/bobuhiro11/gostream に、本文のアイデアをもとに並行処理に便利な関数群をまとめた。 競合状態は二つ以上の操作を正しい順番で実行しなければいけない状況で、プログラムがその順番を保証していないときに発生する。 論的な正当性を目指すべきで、Sleep関数を挟むような方法では解決しない。 デッドロックが起きる必要条件は、Coffman条件として知られている。 筆者の意見では、ライブロックはデッドロックよりも発見がむずかしい。プログラムの外部からリソース使用率を観測しても検出できないから。 並行処理に関わる関数には、適切にコメントをつける。誰が並行処理を担っているか、どのような並行処理のプリミティブに対応しているか、誰が同期処理を担っているか、を記述する。関数シグネチャでは不十分。 並行性（concurrent）はコードの性質、並列性（parallel）は実行中のプログラムの性質を指す。 Tony hoare「Communicationg Sequence Process」をもとに、Go言語の並行処理プリミティブは設計された。 CSPのほかにも、伝統的なメモリアクセス同期のコードも書ける。syncパッケージ中にまとめられている。 ただ、Goプログラミングスタイルでは、高水準の技術を使うのが推奨されている。ある瞬間に、ただ一つのゴルーチンのみが特定のデータを扱うようにすべき。 メモリ共有のかわりに、チャネルによる通信を行うべき。 メモリサイズに応じて、生成可能なゴルーチン数を概算できる。本文中の例によると、RAM 8GBで数百万のゴルーチンを生成できる。 sync.WaitGroupのAddの呼び出しはできる限り監視対象のゴルーチンの直前に書くのが良い。 デッドロックを避けるために、Mutexを使う時はUnlockの呼び出しをdeferの中で行う。 RWMutexはMutexよりも高機能。書き込みのロックを取っているものがいなければ、複数の読み込みロックを取得できる。 バッファ付きチャネルは早すぎる最適化になりやすい。デッドロックが見えなくなってしまう。 チャネルの所有権のスコープは小さくする。 Goランタイムはcase文全体に対して疑似乱数による一様選択をしている。 空select文 select {}は永遠にブロックする。 情報をたった一つの並行プロセスからのみ得られることを確実にする考え方に、拘束がある。 // チャネルへの書き込みスコープは、関数内にレキシカルに拘束される。 func owner() <-chan int { c := make(chan int) go runc() { defer close(c) for i:=0; i<10; i++ { c <- i } } return c } システムにキューを導入するのは便利だが、早すぎる最適化になってしまう。キュー導入の利点は、ステージの実行時間が減ることはなく、ステージのブロック状態の時間が減ること。 キューでは、リトルの法則でスループットを予測できる。 contextを関数の第一引数として渡す。よく使われるデータへの参照の保管には使わない。 ハートビートは必ずしも必要ではない。長時間稼働させる場合には有用。

BGP in the Data Centerの前半部分を読んだので、気になったところをメモしておく。CLOSネットワークをどのように設計するか、BGPをどのように運用するかについて、実践的な内容が書かれていた。普段触っていない領域なので、勘違いもあると思う。 1. Introduction to Data Center Networks ローカルネットワーク内のサーバ間通信をEast-Westトラフィック、ローカルネットワークと外部のネットワークの間の通信をNorth-Southトラフィックと呼ぶ。 大量のケーブルを管理する必要があるので、巨大なネットワークの管理者は、それぞれ管理技術を持っている。Prescriptive Topology Manager（PTM）というOSSもある。 同一のスイッチで巨大なネットワークを構成しておくと、故障した場合でも、単純に取り替えるだけで復旧できる。日々の運用コストについて考えておくことが大事。 CLOSネットワークを外部と接続するために、Border PodあるいはBorder Leavesを配置する。データセンタ内で使われているルーティングプロトコルは外部とは分離しておく。もし、Border PodやBordor Leavesを配置できない場合には、すべてのSpinesを外部と接続させる（Spineの対称性を保つため）。 iBGPに比較し、eBGPは理解やデプロイが容易なので、eBGPを採用するのが良い。歴史的な観点から、eBGPのほうが完成度の高い実装が多い。 2. How BGP Has Been Adapted to the Data Center PublicなASNは使わないほうが良い。オペレータを混乱させてしまったり、万が一外部に漏れた時にBGPハイジャックになってしまったりといった危険性がある。 2バイトのASNを4バイトへ拡張すると、およそ95,000,000個のprivate ASNを利用できる。 単純にすべてのBGPスピーカにユニークなASNを割り当てると、Path Huntingに苦しむことになる。 あるPrefixへの到達性をもつノードがダウンしたときに、その情報が収束するまでに時間がかかってしまう。これは、BGPのベストパス選択の性質に起因する。 真に到達不可能なのか、それとも別の経路でもって到達できるのかの区別ができない。 密に接続したCLOSトポロジでは、顕著な問題となる。 Path Hunting問題への対応として、以下のASN割り当てモデルがある。ループを検出できるので、必要以上にメッセージを送らなくて済む。ただし、Route Summarizationができないことに注意する。 すべてのToRはユニークなASN LeafはPodごとにユニークなASN。Pod内では同一のASN Spineは共通のASN OSPFやIS-ISはBest path選択のメトリクスを1つだけ。一方、BGPではそれが8つある。 Wise Lip Lovers Apply oral medication Every Night. Wight, LOCAL PREFERENCE, Locally originated, ASPATH, ORIGIN, MED, eBGP over iBGP, NextHop IGP Cost これら8つが等しければ、Equal Costと考えられ、Multipath Selectionできる。 ASPATHの比較については、長さに加えて要素がすべて等しければ、Equal Costとみなされる。 例えば、同一のPrefixが異なるASから届いた時には、Multi Pathとはならない。 ただし、bestpath -as-path multipath-relaxの設定を行うと、ASPATH長のみで（内容には触れずに）比較するよう設定できる。 タイマ設定を変更することで、CLOSトポロジにおける収束を早くする必要がある。ふつうはプロバイダ向けを想定して、安定性を第一にデフォルトが設定されていることが多いので、適宜設定する。 Advertisement Interval：このInterval内に含まれるメッセージは統合されて、送り出される。eBGPの場合、デフォルト30秒だが、0秒に設定すれば良い。 Keepalive and hold Timers：ある周期でkeepaliveメッセージをピアと交換する。Hold timeの期間内に、keepaliveを受け取らなかった場合は、ノードダウンと判定される。ケーブル障害の検知のために、BFD(Bidirectional forwarding Detectiion)を導入している場合でも、BGPプロセス自体のエラー検出のために、これらのタイマを調整する必要がある。おすすめは、3秒ごとのKeepaliveと9秒間のhold timersである。 Connect Timer：ピアの接続が切れた時、再接続までの待ち時間。 3. Bulding an Automatable BGP Configuration bgp router-idはIPアドレスにしておくのが良い。 広報したいprefixをstaticに設定するよりも、connected、kernel、ospf、bgp、ripなどのprotocolからrouteを引き継くとよい。 ただし、不正なアドレスをまちがって広報する可能性があるので、routing policyの設定が必要になる。 prefix equalよりもprefix belongsのほうが管理が楽。 また、routing policyはふつうroute-mapで設定される。 # routing policyの例 ACCEPT_DC_LOCAL(prefix) { if prefix belongs to 10.1.0.0/16 then accept else if (10.0.254.0/24 contains prefix and subnet equals 32) then accept else reject} }

京都マラソンから、2週間が経過し、2019.3.3（日）東京マラソンに参加した。 こちらも初応募で初参加となった。 スタート前からゴール後まで、雨が振り続いていた。 特に、スタート前に30分以上、屋根のない中、待っているのがつらかった。 後半は、半分くらい歩いていて、ペースはぐだぐだだったが、無事完走できてよかった。 これで、今冬のマラソン大会参加は一旦終わりにする。 次の東京マラソン参加がいつになるかわからないが、来年も応募しようかな。

2019.2.17（日）、京都マラソン2019に参加した。 初応募で初参加となった。 各地点での通過時間をメモしておく。ハーフ以降の距離でも、長い距離を歩くことはなかった。 スポーツ羊羹、ゼリー、塩飴など補給できるものを多く持っていったので、スタミナ切れがなかったのだろう。 他のマラソン大会だと7時間制限が多い気がするが、 京都マラソンは6時間制限なのでちょっときびしい。 特に、前半はスタートで出遅れたり坂があったりと遅れがちだが、 関門の制限時間がきびしくため、ギリギリで通過していた。 2週間後に、東京マラソンを控えている。そっちも頑張りたい。

Atcoder Beginner Contest #1 ~ #115 の CD 問題をすべて解いた。 C問題は7割くらい、D問題は半分くらい自分の力で解くことができた。 特殊なアルゴリズムを使うことはあまりなく、ちゃんと考察できれば、解けるんじゃないかなと思う。 役立ちそうなことを残しておく。 Example の最初の1~2個は手で解いてみる。特に、幾何の問題は実際に書いてみる。 複数のパラメータを総当たりするときはどちらか一方のパラメータを固定して考える。 あらかじめソートや累積和を計算しておく。 その他、Youtube の解説動画が充実していて、かなり助けになった。

あけましておめでとうございます。 x86のエミュレータの開発を続けてきましたが、半年が経過し開発速度もゆっくりになってきたので、 一旦このタイミングでコードを公開することにします。 https://github.com/bobuhiro11/tiny_x86_emu に置いているので、 興味があれば見てみてください。

先月、Go 1.11がリリースされ、WebAssemblyが実験的にサポートされるようになった。 開発中のエミュレータもGoで書かれているということで、せっかくなので、 WebAssemblyに移植した。 単純にGoをWebAssemblyにコンパイルすると標準出力としてブラウザのコンソールが使われるが、 divタグの中に出力したかったので、syscall/jsパッケージでDOMを操作した。 その他の部分は特に変更の必要がなかった。 https://bobuhiro11.net/tiny_x86_emu/に公開している。 まだ開発途中という状態で、ユーザプロセス実行に関する開発が滞っているので、そろそろ手をつけていきたい。

mpmain()、scheduler()、swtch()とプロセス切り替えできるまで、 エミュレータの開発が進んだ。 xv6のコードproc.cの334行目sti命令をずっと発行していて、どうやらループに入っているようなので、 ここでスケジューリング、コンテキストスイッチ周りをまとめたい。 切り替え先のプロセスは、切り替えられた直後forkret()、iinit()関数内にて、IOを行っている。 ここで、スリープ状態に入り、割り込みを待っているようだ。 proc構造体 xv6では各プロセスはproc構造体で管理される。 contextには、コンテキストスイッチのためのレジスタを格納する。 CSなどセグメントレジスタは、プロセス間で共通なので、保存する必要がない。 EAX、ECS、EDXなどは関数呼び出し時に自動的にスタックに保存されるため、contextに含めない。 最初のユーザプロセスは、userinit関数とallocproc関数で作成する。 proc構造体のコメントには、最初のユーザプロセスのデータをメモしておく。 トラップフレームは、ハードウェアとtrapasm.Sによりスタック上に積まれるもので、 trap関数へと引き渡される。 forkret関数のreturn先は、trapretに設定する。 struct proc { uint sz; // Size of process memory (bytes) pde_t* pgdir; // Page table char *kstack; // このプロセスのカーネルスタックの底 enum procstate state; // プロセスの状態：EMBRYO int pid; // PID：1 struct proc *parent; // 親プロセス：NULL struct trapframe *tf; // トラップフレーム struct context *context; // このプロセスのコンテキスト void *chan; // If non-zero, sleeping on chan int killed; // If non-zero, have been killed struct file *ofile[NOFILE]; // Open files struct inode *cwd; // カレントディレクトリ：/ char name[16]; // プロセス名：initcode }; struct context { uint edi; uint esi; uint ebx; uint ebp; uint eip; // forkret }; struct trapframe { // registers as pushed by pusha uint edi, esi, ebp, oesp, ebx, edx, ecx, eax; // rest of trap frame ushort gs, padding1, fs, padding2, es, padding3, ds, padding4; uint trapno; // below here defined by x86 hardware uint err; uint eip; ushort cs; ushort padding5; uint eflags; // below here only when crossing rings, such as from user to kernel uint esp; ushort ss; ushort padding6; }; struct { struct spinlock lock; struct proc proc[NPROC]; } ptable; カーネルスタック proc->kstackの中身を図示しておく。 swtchでは、espをproc->contextとして、edi、esi、ebx、ebpをpopする。 そして、最後にret命令で、eipを復元する。 ...

初めて読む486を読んだので、気になってことをメモしておく。 エミュレータを作っているので、参考になる。 全体を通して、図が分かりやすいので、図を見るだけでも勉強になる。 セグメント EIPから命令を読み出すときにはCSレジスタの指すセグメントが使われ、命令実行時のメモリアクセスにはDSレジスタの指すセグメントが使われる。また、PUSH、POP、CALL、RETなどスタックに関する操作には、SSレジスタの指すセグメントが使われる。スタックは下位アドレス方向に伸びるため、スタックセグメントのリミットは例外的に下限を指定する。 すべてのメモリアクセスのたびにセグメントディスクリプタを参照するのは、無駄が多いので、CPU内にセグメントディスクリプタ自体のキャッシュ（セグメントディスクリプタキャッシュ）を持つ。 プロテクトモードでは、CSレジスタが16ビットセグメントを指していれば、オペランドサイズとアドレスサイズは16ビットになる。同様に、32ビットセグメントでは、それらのサイズは32bitになる。 セグメントごとにDPL（Descriptor Privilege Level）で特権レベルを指定する。現在実行中のセグメントのDPLによって、CPL（Current Privilege Level）が決まる。CPLはCSレジスタの下位2bit、DPLはセグメントディスクリプタで設定される。ジャンプ先セグメントのDPLがCPLより高い場合には、直接ジャンプすることはできず、コールゲートを経由する必要がある。 ディスクリプタ GDTには、セグメントディスクリプタのほかに、TSS、コールゲート、タスクゲート、トラップゲート、割り込みゲートなど複数のシステムオブジェクトが格納される。 各種ゲートディスクリプタにもDPLを設定しておき、ゲートを呼び出すときに、CPLとDPLを比較する。CPLがゲートのDPL以上であれば、ゲートの先のセグメントのDPLによらず、そのセグメントにジャンプできる。 LDTを使うときは、GDT内にLDTを指すディスクリプタを作成して、そのセレクタ値をLDTRに設定する。 割り込み 割り込み番号は0x00~0xFFまで全256種類。 割り込みディスクリプタテーブル（IDT）には、ゲートディスクリプタを並べておく。割り込み番号がIDT内オフセットとなる。ゲートの種類は、割り込みゲート、トラップゲート、タスクゲートの3種類。 ふつうRET命令は単純にCS,EIPをPOPするだけだが、POPしたCSのDPLがCPLよりも低ければ、続けてSSとESPもPOPする。 低特権レベルからコールゲートを介してOSの関数を呼び出したとき、引数は低特権レベルのスタックにしか存在しないため、OSから簡単に扱えない。対策として、コールゲートのコピーカウントというパラメタに、引数のバイト数/4を設定しておき、自動的に引数をOS側のスタックにコピーさせる。戻るときは、オペランド付きRET命令を使い、OSのスタックをインクリメントさせる。 I/O IOポートはディスクリプタがないので、DPLを持たないが、代わりにIOポート専用の特権レベルIOPRL(I/O Privilege Level)がある。IOPRLは、EFLAGSレジスタで設定される。また、TSS内のIO許可マップで制御することもできる。 その他 クロックダブラーと呼ばれるクロック周波数を2倍にする技術があった。486DX2やODP（Over Drive Processor）で使われていた。 OSが利用するシステムレジスタはGDTR、IDTR、LDTR、TR、CR0~CR3。 DR0~DR7を操作することでブレークポイントを仕掛けて、デバッグできる。 アドレスバスとデータバスは32ビット、IOアドレスバスは16ビット。 オペランドサイズとアドレスサイズはそれぞれ32ビットあるいは16ビットで解釈される。どちらもプレフィックス（0x66あるいは0x67）をつけることでサイズを変更できる。 現在のタスクが使っているTSSのセレクト値は、TR（Task Register）に保持する。 同特権レベルでのCALL命令であれば、CSとEIPをPUSHして、ジャンプするだけ。異なる特権レベルへ移るためのコールゲートへのCALL命令であれば、スタックを切り替えてから、SS、ESP、CS、EIPをPUSHする。

xv6のページングについてまとめておきたい。 カーネルmain関数では、ページテーブルやページディレクトリの初期化が2度行われる。 1度目のページング機構の初期化は、 仮想アドレスの下位4MB 0x0 ~ 0x400000 をそのまま物理アドレス 0x0 ~ 0x400000 にマッピングする。 また、0x80000000をオフセットとした仮想アドレス 0x80000000 ~ 0x80400000 についても、 同じく物理アドレス 0x0 ~ 0x400000 にマッピングする。 このページングはカーネル初期化時にのみ利用される。 CR4のPage Size Extension（4bit目）を有効にすることで、 ページサイズを4MBに拡張している（スーパーページ）。 スーパーページでは、ページテーブルは利用せずページディレクトリだけを使う。 仮想アドレスの上位10ビットがページディレクトリのインデックス、 下位10ビットが4MBページ内のオフセットに対応する。 つまり、1段のページング。 kinit1関数では、カーネルの終端から4MB（0x801154a8 ~ 0x80400000）のページに対してkfreeを実行し、 freelist（空きメモリをつなげたlinked list）に繋いでいく。 続いて、2度目の初期化では、 4MBを超える仮想アドレスを対象としている。 こちらは、スーパーページは使わないので、ページサイズは4KBのままで、 ページディレクトリとページテーブルのどちらも使う。つまり、2段のページング。 kinit2関数で、0x80400000 ~ 0x8e000000のページをfreelistに繋ぐ。 今回は、2度目の初期化のところでバグがあったため、 kinit2内で不正なアドレスに書き込みを行っていた。 2段のページング機構でのページウォークを見直して、解決した。 CR3の上位20bitがページディレクトリのベース物理アドレスを指しているが、 そのアドレスはCR3 >> 20ではなくCR3 & 0xFFFFF000であることに注意する。 ページディレクトリエントリについても同様のことが言える。 つまり、ページディレクトリやページテーブルは4KBでアライメントされている。

自作エミュレータで学ぶx86アーキテクチャ という本を読んだ。 その続きとして、主に教育向けに使われているx86 OSのxv6を完動させることを目標に、 自作エミュレータを拡張していこうと思う。 比較的長期間にわたって開発することになるので、一旦今の状況をまとめておきたい。 現状では、ブートローダによってカーネル本体をメモリ上に展開し、 カーネルのmain関数から実行を開始できる状態になっている。 より正確には、ブートローダからカーネルのmain関数へと進み、 どこかの地点でカーネルパニックが起きている状態である。 また、シリアルポート（I/O Port 0x3F8）のエミュレートをできるようになっているので、 カーネルから cprintf 関数や panic 関数を呼び出すことで、任意の文字列を出力できる。 このあたりまでくるとCPU自体のエミュレートは落ち着いてきて、 各種IOや割り込みの実装が中心になってきていると感じる。 ある程度までまとまったら、コードを公開したい。 拡張にあたって、まずは本のコードの写経から始めた。 足りない命令については、インテルの仕様書を参考に随時追加していった。 Mod R/MやSIBバイトの動作については、手当たり次第に実装していたが、 インテルの仕様書を見れば一発でわかる話だった。 例外的な動作が多く、例えば、SIBバイトによるアドレス指定で Base=5 としたときには、 レジスタでなく disp8 や disp32 を使うことになる。 開発初期は各命令の動作を検証するために、QEMUの動作を正として、以下のようにQEMUのレジスタをトレースするGDBスクリプトを用意した。 10万ステップにわたり、自作エミュレータとQEMUのレジスタが一致するかどうかテストしながら、開発を進めた。 target remote localhost:1234 set architecture i8086 set confirm off break *0x7c00 c set variable $i = <numstep> while $i > 0 si info registers set variable $i -= 1 end quit xv6の動作についても、簡単にまとめておく。 xv6のイメージを指定し自作エミュレータを起動すると、 16bitモードで起動し、EIP=0x7c00 の状態からbootasm.Sのブートローダを開始する。 その後、32bitモードに移行して、Cコード bootmain.cへジャンプする。 bootmain.cでは、ディスクからELF形式のカーネル本体を読み込み、メモリ上に展開する。 main.cのカーネル本体では、 mpinit 関数や lapicinit 関数などから、各種デバイスの初期化を順に実行していく。 上から順番に初期化していれば良いので、わかりやすい。 コンテキストスイッチあたりまで話が進むとデバッグが大変になるんだろうと思う。 ...

Chefを利用する機会があり、体系的に知りたいと持って、Chef実践入門を読んだ。 自分用に、そのメモを残しておく。 概要 管理サーバを介するかどうかによって、2種類の動作形態がある。1つ目は、管理サーバとしてChef Serverを介するサーバクライアントモデル。ローカル端末と、管理対象ノードの他に、Chef Serverを必要とする。ローカル端末・Chef Server間、Chef Server・ノード（Chef Client）間でやり取りする。ノード数の増加に強い。2つ目は、Chef Soloを使ったスタンドアロンモデル。Chef ServerもChef Clientも不要。小規模な環境で使われることが多い。いずれもRubyで実装されているので、gem install chef knife-solo berkshelfのように、gemによってインストールできる。 リポジトリ（キッチン）、クックブック、レシピという階層構造を持つ。リポジトリは、Gitなどでバージョン管理をする。site-cookbooksに自作のクックブック、cookbooksに外部クックブック、data_bagsにリポジトリ全体でグローバルなスコープのデータ、environmentsにdev/prodなどの環境情報、nodesにノードごとの設定情報（nodeオブジェクト）を配置する。また、Berksfileに依存する外部クックブック一覧を記述する。 クックブックの実装 同一構成の複数ノードを管理する場合には、ノードをまとめたroleを定義する。<repository>/roles/<role name>.jsonを作り、run_listなどを書いていく。また、Attributesを上書きすることもできる。default_attributesは定義されていないものを定義し、override_attributesは強制的に上書きするもの。 Attributeというkey-valueを管理する仕組みがある。自分で設定したり、システムから自動抽出することができる。自動抽出する場合には、ohaiコマンドの結果が使われる。慣習的に、ohaiで取得したの値のキーに関してはnode[:platform]のようにシンボルを利用し、Nodeオブジェクトで定義したキーに関しては、node["httpd"]["port"]のように文字列を利用する。Attributeは、<cookbook name>/attributes/defaults.rbにデフォルト値を定義できる。Attributeの優先順は、Nodeオブジェクト＞ロール＞Environment＞レシピのAttribute＞クックブックのAttribute。 cookbook_fileリソースは<cookbook name>/files以下のファイルを転送し、fileリソースはファイルを新規作成するために使われる。 ifconfig、mount、gem_package、git、http_request、route、ruby_blockリソースなどがある。もし、これらのリソースを使っても管理できないものがあれば、scriptリソースを使う。ただ、not_if、only_ifなどをうまく使って、冪等性を自分で保証する必要がある。 設定ファイルの配置後に、notifies :reload, "service[httpd]"のようにして、サービスのリロードできる。あるいは、subscribes :reload "template[/etc/httpd.conf]"によって、逆方向で定義できる。どちらも動作は同じで、キューに詰め込まれてまとめて実行される。 if文でインデントが深くなり可読性が下がってしまう場合には、only_ifなどの条件付きアクションを使うと良い。 レシピに書かれたリソースはコンパイル後に収束のタイミングで実行されるが、その他のRubyコードはコンパイル時に実行される。収束のタイミングで実行されるRubyコードを書きたければ、ruby_blockリソースを使う。 一連のリソースや処理は、Definitionとして、マクロのように実装できる。 Chef Solo Cookbookを開発するサーバと、管理対象ノードが同一の場合には、knife cookbook create <cookbook name>によりクックブックを作成し、chef-solo -o <cookbook name>によりクックブックを実行する。こういう使い方はあまりしないのかな。 開発サーバと管理対象ノードが異なる場合には、開発サーバでknife-soloを使う。knife-soloコマンドは、手元のクックブックをノードへ転送し、chef-soloを実行する。まず、開発サーバで、knife solo init .により、リポジトリを準備する。次に、knife solo prepare <hostname>により、管理対象ノードにche-soloをインストールする。続いて、knife cookbook create <cookbook name> -o <repository>/site-cookbooksで、クックブックを作成する。その後、クックブックを編集して、<repository>/nodes/<hostname>.jsonの中で{'run_list': ["recipe[<cookbook name>:<recipe name>]"]}と記述する。<recipe name>を省略すると、default.rbが参照される。最後に、knife solo cook <hostname>で、ノードをプロビジョニングする。なお、knife solo prepare <hostname>とknife solo cook <hostname>をまとめたknife solo bootstrap <hostname>コマンドもある。また、chef-soloにのみ依存するものはknife soloを使い、それ以外のものはknifeを使う。 その他 Test Kitchenを使って、クックブックを統合テストできる。Vagrantなどで、複数のOSを立ち上げる。テストの実行は、クックブックの適用後に、surverspecによって行われる。実際にテストを適用せずに、振る舞いをテストしたければ、ChefSpecを利用する。 knife cookbook site search <cookbook name>で外部のクックブックを検索して、Berksfileにcookbook '<cookbook>'追加する。その後、berksコマンドで、cookbooksディレクトリにダウンロード、展開される。 Opscode、Basecamp、RiotGames、aws、engineyard、pivotal-sproutなどがコミュニティクックブックを公開している。 Chef Serverは、新規clientの登録時に双方のvalidation.pemをチェックして、認証する。その後、クライアントに秘密鍵を発行する。 knife statusで最後にChef Clientが実行された時間を確認できる。 Chefの持つ冪等性と、緊急時のロールバックは相性が悪い。そのため、Chefによるアプリケーションのデプロイは理想的ではない。 クックブックの適用忘れを防ぐためには、Chef Soloを定期実行するか、Server/Client構成にして自動適用する。 knifeコマンドやohaiコマンドのプラグインは、指定のディレクトリにRubyコードを配置することで、簡単に実装できる。

これまで、bobuhiro11.net と blog.bobuhiro11.net は、 自分で管理するサーバから配信していた。 ただ、どちらも静的サイトなので、必ずしも自分でインフラを管理する必要はなく、 楽をするために、これからはGithub Pagesを使って配信することにした。 調べてみたところ、Github Pagesでは、独自ドメインは利用できるが、HTTPSで配信することができない。 そこで、Github Pagesの前段に、SSL終端のできるCDNを配置した。 SSL終端のできるCDNは、いくつかあるようだが、 今回は無料で利用できるCloudflareを選択した。 Cloudflareには、DNSの機能もあるので、 お名前.comで登録している bobuhiro11.net とそのサブドメインを Cloudflareへ移行した。 まとめると、以下のようになる。 お名前.com：ドメインのレジストリ Cloudflare：DNSとCDN（SSL終端） Github Pages：静的サイトのビルドとHTTP配信 Githubの設定 2つのPrivateリポジトリを作成して、jekyllのコードをpush リポジトリの公開範囲がprivateであっても、gh-pagesブランチの内容は自動的に公開 リポジトリ直下に、ドメイン名を記述したCNAMEを配置 SettingsタブのGithub Pagesで確認 jekyllコードは自動でビルド Cloudflareの設定 ふつうzone apexにCNAMEレコードはマッピングできないが、 Cloudflareでは、CNAME Flatteningによって、例外的に割り当てることができる。 Aレコードよりも管理が楽なので、zone apexにもCNAMEを割り当てた。 適当にアカウントを登録して、設定を入れていく。 CloudflareとGithub Pagesの間では、sslを利用できないので、CryptoタブのSSL設定はFlexibleとした。 また、ブラウザにhttps接続を強制するために、HSTS（HTTP Strict Transport Security）の設定をする。 DNSタブ Type:CNAME, Name:blog, Value:bobuhiro11.github.io, TTL: Automatic, Status: DNS and HTTP proxy(CDN) Type:CNAME, Name:bobuhiro11.net, Value:bobuhiro11.github.io, TTL: Automatic, Status: DNS and HTTP proxy(CDN) Type:MX, Name:bobuhiro11.net, Value:xxxx, TTL: Automatic Type:TXT, Name:bobuhiro11.net, Value:xxxx, TTL: Automatic NSを2つ割り当ててくれるので、メモしておく（お名前.comの設定で使う） Cryptoタブ SSL: Flexible Always use HTTPS: On HSTS: Status: On, Max-Age: 6 months ,Include subdomains: On ,Preload: On ,No-sniff: On Automatic HTTPS Rewrites: On お名前.comの設定 DNSサーバを、Cloudflareのところでメモした*.ns.cloudflare.comに変更する お名前.comが管理しているDNSサーバ*.dnsv.jpのDNSレコードは削除しておく 設定情報の確認 しばらく待ってから、設定が正しく入っているかを確認 ...

GithubやBitbucketで管理している プライベートリポジトリに対して、 CI（継続的インテグレーション） とCD（継続的デリバリー）を実現する。 ここでは、werckerを使って、 テストとデプロイを自動化する方法をメモしておく。 werckerは、GithubとBitbucketどちらのプライベートリポジトリにも対応しており、 今のところ無料で利用できる。 デプロイ先はherokuとした。 herokuは、基本的に無料で、手軽にPaaS環境を利用できる。 ただし、無料枠での利用においては、 30分間アクセスがないとスリープ状態になったり、 稼働時間を月1,000時間に制限されたりするので注意する。 想定するアプリケーションは、Python3とFlask（Python向けウェブアプリケーションフレームワーク）で実装されたウェブサービスとする。 まず、リポジトリに3つの設定ファイル（wercker.yml、Procfile、runtime.txt）を追加する。 wercker.ymlは、werckerで利用する設定ファイルで、 大きく分けてbuildとdeployという2つのセクションから構成される。 buildセクションには、依存ライブラリのインストールと、ユニットテストの実行について記述する。 一方、deployセクションには、 herokuへのデプロイ時に参照するSSHキーペアの名前（key-name: HEROKU）を指定する。 HEROKUという名のSSHキーペアの作成手順は、後述する。 また、最新版のheroku CLIを利用するために、 install-toolbelt: true と記述しておく。 Procfileには、アプリケーション名: コマンドの記法で、起動コマンドを記述する。 さらに、runtime.txtでPythonのバージョンを指定する。 特に指定がなかった場合には、Python 2系がインストールされるので注意する。 # wercker.yml box: python services: build: steps: - script: name: install dependencies code: | pip3 install -r requirements.txt - script: name: test code: | python3 -m unittest discover -v && flake8 . deploy: steps: - heroku-deploy: install-toolbelt: true key-name: HEROKU # Procfile web: python -m web.main # runtime.txt python-3.6.1 続いて、werckerのウェブUIで、wercker・リポジトリ間の紐づけと、CIにおけるパイプラインを設定する。 werckerのユーザ登録後、アプリケーションをdashboardから追加し、リポジトリと紐付ける。 アプリケーションの追加後、Workflowsタブを選択し、Add new pipelineからdeployを追加する。 さらに、masterブランチへのPUSHのタイミングで、 buildとdeployが連続して動作するように、ウェブUI上でbuildの直後にdeployをつなげる。 また、deployの実行中にherokuへログインするために、 EnvironmentタブのGenerate SSH Keysボタンから、SSHキーペアを生成し、 環境変数（HEROKU_PRIVATEとHEROKU_PUBLIC）として格納する。 加えて、Environmentタブから、 herokuのアプリケーション名を指示する環境変数 （変数名はHEROKU_APP_NAME、値はherokuのアプリケーション名）を登録する。 ...

2017.3.12（日）に，石川県七尾市で 開催された能登和倉万葉の里マラソン2017 に参加した． 初めてのフルマラソンだった． 高低差が多いのは難点だったが， 七尾西湾を一周するコースだったので， 漁港，山，海，橋など自然を満喫できた． さらに， 能登マ丼（牡蠣の入った丼）やおにぎりを頂いたり， 気温・天候がちょうど良かったりと終始気持ち良かった． 5km毎の通過時間とラップタイムを記録しておく． だんだんとペースが落ちていて，安定していない． 序盤から中盤にかけて11本の坂道があり， そこで調子に乗ってスピードを出しすぎたと思う． 20km地点で， 右足の足裏が痛みだしたが， 中敷きを外すと楽になったので走り続けた． その後，30km地点を過ぎたあたりから急に歩くのすら辛くなって， 休憩しつつ歩いた． 結果，順位は5,152人中3,096位． ちなみに，去年12月に参加したハーフマラソンでは， 1:47:54という結果だったので， なかなか単純計算ではいかないなという印象． 05km 00:36:55 10km 01:06:53 (29:58) 15km 01:38:46 (31:53) 20km 02:12:33 (33:47) 25km 02:55:19 (42:46) 30km 03:42:12 (46:53) 35km 04:32:00 (49:48) 40km 05:22:07 (50:07) ゴール 05:41:03 前日に18切符で会場周辺まで移動して前泊． マラソン後は，温泉に浸かり， サンダーバードで帰阪． またの機会があれば，後泊したい．