QEMU/KVM侊 で Kubernetes The Hard Way 事前準備からTLS蚌明曞の䜜成たで

QEMU/KVM䞊で https://github.com/kelseyhightower/kubernetes-the-hard-wayを詊しおみたので、ログを残しおおく。 元々の文章では、GCPを前提ずしおいるが、今回は手元のQEMU/KVM䞊で構築した。 バヌゞョン䞀芧 kubernetes-the-hard-way bf2850974e19c118d04fdc0809ce2ae8a0026a27 Kubernetes 1.12.0 containerd Container Runtime 1.2.0-rc.0 gVisor 50c283b9f56bb7200938d9e207355f05f79f0d17 CNI Container Networking 0.6.0 etcd v3.3.9 CoreDNS v1.2.2 1. 事前準備 VMむメヌゞを取埗しお、起動するたで。 # VMむメヌゞの準備 $ http_dir=http://ftp.jaist.ac.jp/pub/Linux/Fedora/releases/30/Cloud/x86_64/images $ wget $http_dir/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 $ virt-customize -a /var/lib/libvirt/images/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 \ --run-command 'yum remove cloud-init* -y' \ --root-password password:root $ cd /var/lib/libvirt/images/ $ for i in 0 1 2 ; do \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 controller-$i.qcow2; \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 worker-$i.qcow2; \ done # VM起動 $ for name in controller-0 controller-1 controller-2 worker-0 worker-1 worker-2 do sudo virt-install --name=$name --virt-type kvm --graphics none \ --disk /var/lib/libvirt/images/$name....

July 28, 2020

Educational Codeforces Round 89 D. Two Divisors

提出したコヌド æ•Žæ•°$a \ge 2$が䞎えられるので、$gcd(d_1+d_2,a)=1$を満たすような組$(d_1,d_2)$を求めたい。 ただし、$d_1 \ge 2$か぀$d_2 \ge 2$。 これを$n$個回繰り返す。 たず $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$ のように玠因数分解を行う。 もし $m = 1$あるいは$a$が玠数の堎合には、答えは$(-1,-1)$。 $m \ge 2$の堎合には、$(p_1, p_2 \cdot p_3 \cdots p_m)$が答えずなる。 なぜこれが答えでよいのか芋おいく。 「$d_1 + d_2$がいかなる玠因数$p_i$に察しおも割り切れないこず」が蚀えればよい。 たず、「$d1 + d2$ が $p1$ で割り切れない」こずが正しいのか考えおみる。 $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1) $ より、$d1 + d2 \not \equiv 0 (mod \ p_1)$ ずなる。 続いお、「$d1 + d2$ は $p_i (2 \le i \le m)$ で割り切れない」こずが正しいのか考えおみる。 $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i) $ より、$d1 + d2 \not \equiv 0 (mod \ p_i)$ ずなる。...

July 21, 2020

ABC 173 F - Intervals on Tree

提出したコヌド 朚においお「連結成分の数 = 頂点数 - 蟺の数」で求められるこずに泚目する。 盎感的に、頂点が増えるず連結成分の数が1増え、蟺の数が増えるず連結成分の数が1枛るずいう感じで理解できる。 $f(L, R)$もこれで求められる。 $$ \begin{aligned} &f(L, R) \\ &= 区間[L \ R]に含たれる点の数 \\ &- 䞡端が区間[L \ R]に含たれる蟺の数 \\ \end{aligned} $$ これをLずRの党通りで求めお総和をずればよい。 頂点数ず蟺の数はそれぞれ独立に求めおいけばよい。 $$ \begin{aligned} &\sum_{L,R} f(L,R) \\ &= \sum_{L,R} 区間[L \ R]に含たれる頂点の数 \\ &- \sum_{L,R} 䞡端が区間[L \ R]に含たれる蟺の数 \\ &= V - E \end{aligned} $$ 以䞋のように図瀺しおみるず、ある頂点$i$は党䜓で$(i+1)(N-i)$回珟れるので、すべおの$i$でこれの総和を取っお$V$ずすればよい。 同様にある蟺$(u, v)$は党䜓で$(u+1)(N-v)$回珟れるので、すべおの蟺に぀いお総和を取っお$E$ずする。 $V-E$が答えずなる。

July 7, 2020

ABC 173 E - Multiplication 4

提出したコヌド コンテスト埌远加されたテストケヌス after_contest01.txt でコケた。 それ以倖は自力で通ったので考察の詰めが甘かった。 たず、A答えが負ずなる堎合ずB答えが非負ずなる堎合で堎合分けをする。 Aの堎合には、絶察倀の小さい順に貪欲にずればよい。Bの堎合を考えおいく。たず、キュヌを2぀甚意しおおく。 非負な倀を降順に゜ヌトしたもの䟋9 6 5 2 1 0 0 負な倀を昇順に゜ヌトしたもの䟋-8 -7 -3 2 単玔に、負数同士の積は正ずいう性質を䜿う。 $K$が2個以䞊残っおいる堎合には、2぀のキュヌからそれぞれ2぀の倀を取り出しお、倧小比范をする。 䟋えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキュヌから2぀倀を取り出せばよい。 䞀方で、非負なキュヌのほうが倧きい堎合には、非負のキュヌから1぀倀を取り出せばよい。 繰り返しになるが、非負なキュヌから取り出す堎合には、1぀の倀だけでよいこずに泚意する。 https://twitter.com/shirakia/status/1279773457413074944で䟋が蚀及されおいる。after_contest01.txtもこのケヌスに該圓しそう。 そのあずは、非負なキュヌからずる堎合は1぀ず぀、負なキュヌからずる堎合は2぀ず぀のペアずしお、取り出しおいけばよい。 Bの蚈算途䞭で、どうしおも答えを正数にするこずができない堎合には、Aの結果を答えずする。

July 6, 2020

ABC 172 F - Unfair Nim

提出したコヌド 前提知識ずしお、Nimずいうゲヌムであるこずを知っおおくず良い。Nimには必勝法があり、すべおの山の石の数 $A_i$ に぀いおXORをずり、その結果が0以倖であれば、その手番の人が最適な動きを取れば必ず勝぀。 必勝状態であるXOR != 0で手番が回っおきたずき、ある山からある数の石をうたく取り陀くず、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな遞び方をしおも、必ずXOR != 0 の状態必勝状態に遷移しおしたう。 タヌンの経過に䌎っお石の数の合蚈は枛っおいくので、必ずゲヌムは終わる。 Grundy数ずいうらしい。 これをふたえお、考察を進める。「1番目の山から0個以䞊$A_1$個未満の石を2番目の山に移すこずで  」ずあるので、先頭二぀の山に぀いおのみ考えればよいこずがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$ずする。たた、“移す"ずいう操䜜を$A$を$a$、$B$を$b$に倉曎するず蚀い換える。そうするず、以䞋の条件を満たし぀぀、できるだけ$a$を倧きくすればよい“移す"石の数が最小ずいうこずになる。 $$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$ これは桁DPによっお解くこずができる。$dp_{i,j,k}$を、䞋から$i$桁目たで芋たずきの$a$の最倧倀ずする。 ただし、䞀぀䞊の桁に察しお繰り䞊がりがある堎合は$j=1$、$i$桁目たで芋たずきに$a$が$A$を䞊回っおいれば$k=1$ずする。 50桁くらいたで芋れば十分。 提出コヌドにコメントを぀けおおく。初期倀は以䞋の通り。 rep(a, 2) { ull b = a ^ (X & 1); // b は a から決たる ull carry = a & b; ull _sum = a ^ b; if (_sum !...

July 5, 2020

KVM TLB Shootdown Preemption メモ

KVM FORUM 2018 で発衚されたTowards a more Scalable KVM Hypervisorに぀いおのメモ。 [PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown ゲストOSはOSレベルの同期機構であるTLB shoot downやRCUの凊理においお、ホストOSのスケゞュヌラの圱響を受ける。ベアメタル環境であればすぐに完了する操䜜であっおも、仮想環境䞊ではその遅延を無芖するこずができなくなる。 TLBTranslatoin Lookaside bufferは仮想メモリアドレスず物理メモリアドレスのマッピングをキャッシュするために䜿われる。あるCPUがそのマッピングを切り替えたずき、その以倖のCPUでTLBをflushしなかればならない。これを TLB shoot down ず呌ぶ。 モダンなOSでは、TLB shoot down はパフォヌマンスクリティカルな箇所ずしお䜍眮づけされ、この凊理によっお遅延が発生しないようチュヌニングされおいる。TLBのflushはすぐさた完了するずいう前提で、IPIInter Processor Interruptで実装されおいる。Remote CPUのTLB flushの完了は busy wait で埅っおいるため、ベアメタル環境ずは盞性が良い。䞀方で、仮想環境ではvCPUが別のゲストに暪取りされたり、実行がブロックされたり、ずいうこずが起きるため、長時間にわたっお busy wait が継続するこずになる。 この問題は、準仮想化TLB shoot down によっお解決できる。準仮想化TLB shoot down では、動䜜しおいないvCPUに察する操䜜を遅延させおおいお、次回そのvCPUが起動するずきに、KVMがTLB flushを担圓する。特にオヌバコミットされた環境で顕著なパフォヌマンス向䞊が芋られる。 ゲストずホストどちらからも参照できるメモリ領域に「あるvCPUが preempt されたかどうか」を瀺すフラグを甚意しおおく。pv_mmu_ops.flush_tlb_others関数は、アクティブなvCPUに察しおはIPI経由でTLB Flushの通知を送り、そうでないvCPUに察しおはKVM_VCPU_FLUSH_TLBフラグを付䞎しおおく。その埌、KVMはKVM_VCPU_FLUSH_TLBフラグが぀いおいるvCPUを起動する際に、INVVPIDを発行する。VM数が増えるに埓っおこのチュヌニングの効果が顕著に珟れる。

July 1, 2020

Civilization VI 初心者のメモ

䞀床Civilization VIを友人ずやった結果、どうやらこのたただず勝おそうにもないので、ちょっず調べおみる。 このゲヌムは遞択の連続なので、仕組みを知らずになあなあで進めおしたうず勝぀のは難しそう。 あくたでも初心者が自分のために曞いおいくメモなのであしからず。 詳しく知りたい方は CIVILIZATION VI wiki を芋おください。 たず、マップオプションから、グリッド、資源アむコン、算出アむコンを衚瀺するよう蚭定しおおく。 郜垂そのものを匷化するリ゜ヌスが、食料ず生産力。食料を増やすこずで人口が増え、生産力を増やすこずで区域・建造物の生産に぀ながる。生産力は、劎働者が鉱山を䜜るこずで埗られる。ゎヌルド・科孊力・文化力は、垂堎商業ハブ区画、図曞通キャンパス区画、円圢闘技堎劇堎広堎区画から埗られる。 序盀の戊闘に有利なアステカ、アメリカ、シュメヌル、ヌビア、ロヌマ、クリヌ、むンカが、初心者に向いおいる。 初期配眮に癖のあるヌビア、゚ゞプト、マリ、ロシア、カナダ、むギリス、むンドネシア、スペむン、ノルりェヌ、オランダ、フェニキア、マオリなどは難しい。たた、宗教メむンな文明や、特殊なプレむングが必芁な文明も向いおない。 ドむツが扱いやすいそうに感じる。固有区域ハンザが単玔に匷い。区域はハンザキャンパス商業ハブくらいで立おおいく。 序盀は、斥候、劎働者、戊士、開拓者で進めおいく。 郜垂が川や湖に隣接しおいるず䜏宅+3なのでよく吟味する。ナニットの䞭ではチャリオットのちの戊車、匓兵のちの野戊砲が匷い。 䞘陵地垯は生産力が匷力なので、そこを狙っお郜垂を䜜る。 郜垂を䜜った埌は、垂民管理で手動で人をどのタむルに配眮するか決めるこずができるので、定期的に芋盎すず良い。 劎働者はむやみに䜿わず、必芁な時たで眠らせおおけばよい。 åž‚æ°‘+2の䜏宅が必芁で、それを䞋回るずペナルティが発生しお、郜垂の成長が劚げられる。 亀易商は匷力なので、䜜れるタむミングなら優先しお䜜る。 倪叀の遺産はピラミッド、アポロン神殿が匷い。 それ以降の時代では、ペトラ、コロッセオ、アルハンブラ宮殿、チチェン・むツァ、 グレヌト・ゞンバブ゚遺跡、玫犁城、ポタラ宮、アルセナヌレ・ディ・ノェネツィア、ビッグベンが匷い。 戊争䞭は勝぀たで兵の増匷をやめない。盞手も兵の生産に集䞭しおいるはずなので。 遠距離攻撃する堎合は、移動力が1以䞊残っおいれば攻撃可胜なので、ヒットアりェむで戊う。 その他 最初期の探玢は重芁 郜垂で圹割分担 郜垂数ペナルティがないので、単玔に倧量に郜垂を䜜るず匷い 郜垂の人口は䜏宅数に制限されるため、食料よりも1人口あたりの生産力重芖 3぀の山岳があれば、キャンパス区画を䜜る 䞘陵ず鉱山で早期生産 遺産は奪う 高玚資源は売り぀ける

June 30, 2020

ABC 171 F - Strivore

提出したコヌド 解説を持っおみるず、どうやらアルファベットを適圓に$K$回挿入したあずの 長さ$N+K$の文字列の䞭で、$S$の各文字の䜍眮が固定されおいるず考えればうたくいくずいうこずだった。 そう考えるず、あずは長さ$N+K$の文字列で$K$文字をどうやっお挿入しおいくかだけを考えれば良い。 入力䟋1を䜿っお考える。 S = “oof” N = len(“oof”) = 3 K = 5 䟋えば、䜍眮1に’o’、䜍眮3に’o’、䜍眮5に’f’をおいおみる。 たた、長さ$N+K$の文字列を先頭から芋たずきに"oof"がはじめお登堎するのがこれらの䜍眮ずいうこずにする条件1。 このずき、䜍眮0には’o’以倖の25皮のアルファベットを挿入できる。 逆に、䜍眮0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にしお、䜍眮2にも’o’以倖の25皮のアルファベットを挿入できる。 たた、䜍眮4にも’f’以倖の25皮のアルファベットを挿入できる。 䜍眮6ず7に関しおは、特に制玄がないので、26皮のアルファベットを挿入できる。 たずめるず、‘f’の䜍眮$j$が$N-1 
 N+K-1$たで移動したずき、 2぀の’o’が取れる䜍眮の組み合わせは${}_j C _{N-1}$ ずなる。 たた、25皮のアルファベットを挿入する䜍眮は$j - (N-1) $個、 26皮のアルファベットを挿入する䜍眮は$(N+K-1)$個、ずなる。 ぀たり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$ずなる。

June 25, 2020

ABC 170 F- Pond Skater

提出したコヌド 解いた埌の振り返りが倧事だず思う。 2次元平面䞊で、スタヌト䜍眮からゎヌル䜍眮たでの最短経路を求める。 ただし、平面䞊にはいく぀かブロックがあり、そのセルは通れない。 さらに、䞀回の移動で、同䞀方向に$1 
 K$の任意の個数のセルを進めるこずができる。 頂点は$(y, x, dir)$ずしお、グラフを考えお、ダむクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以䞋の通り。 移動にかかるコストを$K$倍しお考えるずよい。 方向を倉えるずきは、$K$で切り䞊げ。 $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$ 同方向に移動。$dir$は䞊䞋巊右の4皮類。$dx$、$dy$は方向ごずの差分。 $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$ 蚈算量は$O(HW log(HW))$かな。

June 23, 2020

Educational DP Contest

EDPC を党郚埋めた。 雑倚なメモなので、きれいに解法をたずめたものではない。 W - intervals $dp_i$ を、いく぀かのビットに1が立っおいるずき、最も右偎にある1が$i$であるずきの最終スコアずする。 ここで、$dp_i$は$ max_{j=0 
 i-1} dp_j$ ず $i$ 文字目を1にしたずきに埗られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合ずしお、 $dp_i$を蚈算する際に、 $i$文字目を1にしたずきに埗られるスコアずしお $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも圱響するため、遅延セグメントツリヌを䜿っお、 圱響する $dp$ に区間加算を行う。 最終的な答えは $max_{i=0 
 N} dp_i$ ずなる。 はじめお、遅延セグメントツリヌを䜿った。埩習しおおく。 Z - Frog 3 $dp_i$ を足堎 $i$ に到達するたでの最小コストする。 初期倀は $dp_0 = 0$。 たずは玠盎にDPの曎新匏を䜜るず以䞋のようになる。 $$ \begin{aligned} dp_i &= min_{j=0 
 i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 
 i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 
 i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$...

April 26, 2020

Linux Observability with BPF 読曞メモ

Linux Observability with BPFを読んだので、メモしおおく。 今月、Brendan Gregg氏のBPF本も出るので、 それも読みたいな。 BPFを䜿うこずで、カヌネルのむベントをフックしお安党にコヌドを実行できる そのコヌドがシステムを砎壊したりクラッシュさせたりするこずが無いよう、BPF偎で怜蚌しおくれる カヌネルモゞュヌルず異なり、BPFプログラムはカヌネル再コンパむルの必芁がない BPFコヌドが怜蚌された埌、BPFバむトコヌドは機械呜什にJITされる BPFプログラムは、bpf syscall によっおBPF VMぞずロヌドされる 2014幎前半にAlexei Starovoitov氏がeBPFを導入した 過去のBPFでは2぀の32bit registerのみが䜿えたが、eBPFでは10個の64bit registerたで䜿える 2014幎6月にはeBPFはナヌザスペヌスにも拡匵された BPFプログラムタむプトレヌシングずネットワヌキングに倧きく分類できる Socket Filterカヌネルに最初に入ったプログラムタむプ。芳枬目的のみ Kprobekprobe ハンドラずしおBPFプログラムを動かす。関数に入るずきず出る時が、それぞれSEC(kprobe/sys_exec)ずSEC(kretprobe/sys_exec)に察応する Tracepoint事前にカヌネル偎で定矩されたtracepointに察しおBPFプログラムを動かす。/sys/kernel/debug/tracing/eventsで䞀芧を確認できる XDPパケット着信時に、早い段階でBPFプログラムを動かす。 Perfperf eventに察しおBPFプログラムを動かす。perfがデヌタを吐き出す床にBPFプログラムが実行される Cgroup Socketそのcgroup内のすべおのプロセスにアタッチされる Socket OptionFacebookはデヌタセンタヌ内の接続においお、RTOsrecovery time objectivesの制埡に、これを䜿っおいる。 Socket MapBPFでロヌドバランサを実装するずきに䜿う。CilliumやFacebook Katranはこれを䜿っおいる。 BFP Vefirier CVE-2017-16995 のように、過去BFPをバむパスしおカヌネルメモリをバむパスできる脆匱性があった DFSで、そのプログラムが終了するこず、危険なコヌドパスが存圚しないこずを怜蚌する 無限ルヌプを匟くために、すべおのルヌプを犁止しおいる。ルヌプ蚱可に぀いおは、本曞を曞いおいる時点では、ただ提案の段階。 呜什数は4096に制限されおいる bpf syscall の log_*を蚭定すれば、怜蚌結果を確認できる BPFプログラムは tail calls によっお、他のBPFプログラムを呌び出すこずができる 呌び出し時にすべおのコンテキストは倱われるので、䜕らかの方法で情報を共有する必芁がある BPFマップ 盎接bpf syscall でBPFマップを䜜成するこずができる bpf_map_createヘルパ関数を䜿うのが簡単 bpf_map_update_elem のシグネチャは、カヌネル偎bpf/bpf_helpers.hずナヌザ偎tools/lib/bpf/bpf.hで異なるので泚意する ゚ラヌ番号でsteerror(errno)で文字列にするず䟿利 bpf_map_get_next_keyはそのほかのヘルパ関数ず違っお、ナヌザ偎でのみ䜿えるので泚意する array, hash, cgroup storage maps に぀いおは、スピンロックがあるので、䞊行アクセス可胜 array map は芁玠数だけ事前にメモリが確保されお、れロで初期化される。グロヌバルな倉数確保のために䜿う LRUハッシュやLRMLongest Prefix MatchTrie mapもある Linux 4....

December 14, 2019

Kubernetes完党ガむド 読曞メモ

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....

November 23, 2019

TP-Link Archer T3U AC1300をLinuxから䜿う

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 の倀を芋るず、オンボヌドの子機偎を優先しおいた倀が小さいので入れ替えた。...

November 9, 2019

2019 越埌湯沢 秋桜ハヌフマラ゜ン

越埌湯沢で開催された秋桜ハヌフマラ゜ンに参加しおきた。 倧䌚自䜓はすごいよかったけど、コヌスの半分あたりから胃の調子が悪くなり、 13kmでリタむダずいう悔しい結果ずなった。 色々反省点があったので、蚘録ずしお残しおおく。 たず、そもそも食事のタむミングが悪かった。9時30分スタヌトで、8時あたりでおにぎりを食べた。 3時間前たでに取るようにしたい。盎前に口にいれるのであれば、れリヌ状のものにしたい。 6.7kmから15kmたで続く䞋り坂で飛ばしすぎた事も圱響しおいるず思う。 お腹が激しく䞊䞋しお気持ち悪くなっおしたった。 スタヌトから6.7kmたでの䞊り坂は走り方に気を぀けおいたが、それ以降に぀いおは、なんずかなるだろうず考えおいなかった。 加えお、腰にポヌチを巻いおいたので、お腹を圧迫しおいたのかもしれない。 塩风を少量持っおいただけなので、ポケットにいれおおけば事足りおいた。 前半の䞊䞋の坂でも貯金を䜜っおおこうず、い぀も以䞊に早めのペヌスで走っおいたので、 バテおしたったんだろうな。 ただ、自分でリタむダを決断できたのは唯䞀よかったこずだった。 以前膝を故障しおしたったずきは、脚を匕きずりながらも、無理しお走っおいお、 沿道で応揎しおくれた方からリタむダを勧められた。 どうも消化䞍良な感じなので、どこかでリベンゞしたい。

September 29, 2019

TCP技術入門 読曞メモ

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が䞀定数届いた堎合

September 25, 2019

ABC139-141

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で芋぀けた。...

September 20, 2019

ABC136-138

いく぀か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}) $$...

August 24, 2019

ABC135

今回は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 䞀発で行ける。...

August 3, 2019

ABC EF問題を埋めた続き

前回の続き。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し぀぀必芁な倀を埋めおいく。

July 15, 2019

ABC EF問題を埋めた

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に察応。 解説動画を芋るのがおすすめ。

June 16, 2019