Kubernetes完全ガイド を読んだので、メモを残しておく。 普段、意識していなかったコマンドや仕組みをまとめておく。 サイズの小さなイメージを作りたければ scratch や apline をベースにする ENTRYPOINT と CMD が設定されているときは、$ENTRYPOINT $CMD が実行されるようなイメージ マルチステージビルド：ビルド専用のコンテナでだけ処理を行い、成果物を実行専用コンテナにコピーすることが出来る CNCF ではプロジェクトの成熟度を「Graduated」「Incubating」「Sandbox」の3段階に設定している オンプレで構築する場合はAWS や GCP でのインスタンスサイズが目安になる Flannel：ノード間でオーバーレイネットワークを構成する Docker, Inc. が提供するkubernetes のプレイグラウンドがある kubernetes のリソースは大きくわけて5種類 Workloads, Discoverty &LB, Config & Storage, Cluser, Metadata 特に Metadata はクラスタ内で他のリソースを操作するためのリソース（HorizontalPodAutoscaler など） Deployment/CronJob > ReplicationController/ReplicaSet/DaemonSet/StatefulSet/Job > Pod という階層構造がある kubectl get all：ほぼすべてのリソースを一覧取得 Stateful Set：0番目の Pod が最初に作られ、最後に削除される kubeconfig clusters、users、contexts の3種類を設定（どれも複数登録可能） context や namespace の切り替えが冗長であれば、kubectx や kubens を使うと良いかも kube-ps1 を使うと cluster と namespace をプロンプトに出力できる source <(kubectl completion bash)などで zsh/bash の補完機能を使える コンウェイの法則：組織図と、マニフェストの管理方法やマイクロサービスのアーキテクチャが似ている kubectl scale：ReplicaSet, ReplicationController, Deployment, StatefulSet, Job, CronJob でスケーリング kubectl apply --prune：実行時にマニフェストから削除されたリソースを検知して、自動で削除 CI/CDでは、単純にこのコマンドを投げ続けるだけでよい kubectl apply --prune --all：クラスタ内に存在するすべてのマニフェストを読み込ませないと、漏れがあったリソースが消えてしまい危険 kubectl apply --prune -l system=a：基本的にラベルを指定しておく デバッグ kubectl cp：コンテナとローカルマシンの間でファイル転送 kubectl port-forward：コンテナとローカルマシンの間でポート転送 kubectl -v：デバッグ出力 サービスディスカバリ spec....

USB接続の無線LAN子機 TP-Link Archer T3U AC1300 を、Thinkpad X1 Carbon 2015（Fedora release 29 (Twenty Nine)、linux 5.3.6-100.fc29.x86_64）から使えるようにしたので手順を残しておく。 # 公式HPではドライバが配布されていなかったので rtl88x2bu を使った git clone https://github.com/cilynx/rtl88x2bu cd rtl88x2bu/ git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12 VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf) sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER} # /usr/src/<module_name>_<module_version> に移動させて dkms で管理する sudo dkms add -m rtl88x2bu -v ${VER} sudo dkms build -m rtl88x2bu -v ${VER} sudo dkms install -m rtl88x2bu -v ${VER} sudo dkms status sudo modprobe 88x2bu 2種類の子機（オンボードの子機とTP-Linkの子機）を同一のネットワークにつなぐと、metric によって優先順位が決まる。 metric の値を見ると、オンボードの子機側を優先していた（値が小さい）ので入れ替えた。...

越後湯沢で開催された秋桜ハーフマラソンに参加してきた。 大会自体はすごいよかったけど、コースの半分あたりから胃の調子が悪くなり、 13kmでリタイヤという悔しい結果となった。 色々反省点があったので、記録として残しておく。 まず、そもそも食事のタイミングが悪かった。9時30分スタートで、8時あたりでおにぎりを食べた。 3時間前までに取るようにしたい。直前に口にいれるのであれば、ゼリー状のものにしたい。 6.7kmから15kmまで続く下り坂で飛ばしすぎた事も影響していると思う。 お腹が激しく上下して気持ち悪くなってしまった。 スタートから6.7kmまでの上り坂は走り方に気をつけていたが、それ以降については、なんとかなるだろうと考えていなかった。 加えて、腰にポーチを巻いていたので、お腹を圧迫していたのかもしれない。 塩飴を少量持っていただけなので、ポケットにいれておけば事足りていた。 前半の上下の坂でも貯金を作っておこうと、いつも以上に早めのペースで走っていたので、 バテてしまったんだろうな。 ただ、自分でリタイヤを決断できたのは唯一よかったことだった。 以前膝を故障してしまったときは、脚を引きずりながらも、無理して走っていて、 沿道で応援してくれた方からリタイヤを勧められた。 どうも消化不良な感じなので、どこかでリベンジしたい。

TCP技術入門を読んだので、 気になったところを雑多な感じだがメモしておく。まず前半部分。 ネットワークまわりの話は聞いたことはあるが、使わずに忘れてしまっていることが多い。 1章 TCP入門 伝送効率 Ethernetフレーム 1500 バイト、TCPヘッダが 60 バイト、IPヘッダが20バイトとする アプリケーションが使えるのは 1420 バイト Ethernetヘッダ 14 バイト、FCS（Frame Check Sequence）4バイトを考慮すると、伝送効率は$1420/(1500+18) \times 100=93.5 %$ UDP 実際にUDPがやっていることは、転送先へデータを送ることと、チェックサムの確認だけ TCPはユニキャストだが、UDPはユニキャストに加えて、マルチキャストとブロードキャストにも対応 シーケンス番号とタイムスタンプを追加したRTP（Real-time Transport Protocol）や、それに加えて再送機能も追加したRUDP（Reliable user Datagram Protocol）もある QUIC はUDPベースで、それを使ったHTTP/3（HTTP-over-QUIC）。コネクション確立とTLS確立を同時に実施。 TCP ACKのシーケンス番号は、次に受信したい番号。当該セグメントが届くまで、同じシーケンス番号を返送し続ける。 フロー制御：受信側のバッファ溢れを防ぐために、送信データ量を調整すること。TCPでは一度に送信可能なサイズをウィンドウと呼ぶ。特に、送信側がもつパラメータを swnd （send window）と表記する。対して、受信側はrwnd（recieve wndoe）。 TCP輻輳制御 Loss-based：データの消失から輻輳を判断 Delay-based：RTTから輻輳を判断 特定の用途向けプロトコル RUDP（Reliable User Datagram Protocol）：UDPベースで、シーケンス番号、ACK、再送、フロー制御を加えたもの DCCP（Datagram Congestion Control Protocol）：UDPにおける輻輳緩和が目的 2章 TCP/IPの変遷 ARPNETなどではネットワークが信頼性を担保していたが、TCP/IPは各ノードがその役割を担う Nagleアルゴリズム：TCP/IPの送出パケット数削減の方法。輻輳制御アルゴリズムのはしり Windows95（OSR2以降）にTCP/IPが搭載されたことが普及のきっかけになった IEEE 802.11ではMACレイヤーでCSMA/CAを採用 3章 TCPとデータ転送 MTUは、イーサネットは1500バイト、PPPoEでは1492バイト、ATMは9180バイト。ただ最近は任意に設定できる MSS（Maximum Segment Size）：TCPが区切る最大パケット長さ MTU（1500バイト）= IPヘッダ（20バイト）+ TCPヘッダ（20~60バイト）+ アプリケーションデータ（MSS以下） MSSは、TCPのペイロードのみ MTUは、TCPのペイロードからTCPヘッダやIPヘッダまで。Ethernetヘッダは含まない ACK（Acknoledgement Number）：確認応答番号。次に送ってほしいシーケンス番号 コントロールフラグ RST（Reset the connection）：コネクションを強制切断。使われていないポート番号に送るなど、異常があれば有効になる CWR（Congestion Window Reduced）：輻輳ウィンドウの減少を通知する。ECNとセットで使われる ECE（ECN echo）：輻輳が発生したら通知 ウィンドウ制御：一度に送信可能なウィンドウサイズ $swnd$ を調整 $swnd = min(rwnd, cwnd)$ フロー制御：受信側から送信側に送信量を通知して、調整する。受信側は、送信側へ受信可能なバッファ量$rnwd$を通知 輻輳制御：輻輳ウィンドウ $cwnd$ を調整 スロースタート 通信開始時点で、ACKを受け取るたびに $cwnd$ を1セグメントずつ増やしていく $cwnd = cwnd + mss$ 指数的に $cwnd$ が拡大 輻輳回避 スロースタートを行うと、再び再送が起きやすい 再送が起きた時の $cwnd$ の半分 $cwnd/2$を閾値として、それを越えた時は更新を緩やかにする $cwnd = cwnd + mss/cwnd$ RTTごとに線形に増える 高速リカバリー 輻輳のたびに、スロースタート→輻輳回避という挙動をするのは効率が悪い 重複ACKを契機とする Recoで採用 セグメントの消失 再送タイマーがタイムアウトした場合 重複ACKが一定数届いた場合

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両方向に冗長な経路を取る必要がある。 p +----+ (X,Y) | Y (0,0)+ - t | | t = K-X |-----|----| X p = (K+X-Y)/2 4) X+Y==K 一発で行ける。...

前回の続き。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....

京都マラソンから、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....