どうも、しいたけです。

去年あたりからローレイヤー周りの知識を充実させようと思い、低レイヤを知りたい人のためのCコンパイラ作成入門 を読んでCコンパイラを書いてみたりx86_64の勉強をしたりしていました。

今年に入ってから、よりローなレイヤー、具体的にはハードウェアやOSについてもう少し知りたいと思い始め、手頃な書籍を探していました。CPUなどのハードウェア周りについては概要しか知らなくて手を動かしたことがないので、実際に何か作りながら学べるものとして、O'Reilly Japan - コンピュータシステムの理論と実装 に挑戦することにしました。

O'Reilly Japan - コンピュータシステムの理論と実装

成果物は以下のリポジトリに置いてあります。

yuroyoro/nand2tetris

結論から言うと、やってみて大変楽しめました！

特にハードウェア周りは今まで挑戦したことのない分野で、回路の設計がとても新鮮で楽しんで取り組めました。ちょこちょこ間が空いたりしたので、全部完走するまで10ヶ月ちょっとかかりましたが……。

コンパイラやVMの作成は、Cコンパイラ書いてみたりした経験があったのですんなりできましたが、実装言語にRustを採用することでRustの習熟にも役立ちました。(というかハマったのは主にRustの学習で、使い慣れた言語だったらおそらくすぐに実装できたはずです……)

OSに関してはかなり物足りなかったので、こちらは別な教材で改めて学びたいと思います。

Nand2Tetrisってなに?

「コンピュータシステムの理論と実装」(通称Nand2Tetris: NANDからテトリスへ)は、コンピューターの基本的な構成要素であるCPUやメモリから始めて、そのアーキテクチャ向けの機械語を生成するコンパイラ、アプリケーションとハードウェアの橋渡しをするOSまでを順を追って作成することで、基本的なコンピューターシステムの動作原理が理解できるような構成になっています。

Courseraにコースがあって、著者のShimon Schocken教授とNoam Nisan教授がインストラクターとしてオンラインで受講することができます。

Build a Modern Computer from First Principles: From Nand to Tetris (Project-Centered Course) | Coursera

僕はヘタレなので受講はせずに独学しましたが、気合入れて取り組むつもりなら受講するのもありではないでしょうか。

Nand2Tetrisでは、Hackという本書独自のアーキテクチャ用のCPUやメモリなどをNand回路から始めて作成し、Jackという本書独自のプログラミング言語のHackアーキテクチャ向けコンパイラを実装し、そのJack言語を用いてOSを書くことで、ハードウェアからOS、アプリケーションまですべてを自前で作っていきます。とはいえ、Hackアーキテクチャで作成するCPUは16bitでデータレジスタとアドレスレジスタがそれぞれひとつしかない単純なCPU(乗除算すらできません！)ですし、Jack言語はオブジェクト指向言語ですがJavaをかなり単純化した言語仕様です。また、OSはプロセス管理やファイル管理、ネットワークなどはサポートせず、単純にキーボードやスクリーンなどメモリマップドされたハードウェアを操作するための便利ライブラリのような位置づけです。

それでも、順番に実装していくと(シミュレーター上とはいえ)このようなゲーム(アプリケーション)を動作させることができます!

終わった。Nand2Tetris、Jack言語コンパイラのコード生成の実装が。

CPU、アセンブラ、スタックマシンVM、コンパイラと作ってきて、ようやくアプリケーションがエミュレータ上で動くようになったぞｫ……！！pic.twitter.com/KmojKek9wT

— 極限生命体しいたけNA (@yuroyoro)November 13, 2020

テトリスちゃうやんけ！！

さて本の構成ですが、おおまかにハードウェア、コンパイラ、OSの3つのパートに分けられており、各パートはいくつかの章で構成されます。章ごとに演習問題が用意されており、実際にその問題で作ったパーツが次の章で利用される仕掛けになっています。例えば、回路設計では最初の1章でANDやORゲートを作り、次の2章ではそれらを組み合わせて加算器を作る、といった具合です。

本書はテストするための回路シミュレーターやCPUシミュレーターがすでに用意されており、また章ごとの課題もテストケースが用意されています。課題の内容にしたがってHDLを書いたりプログラムを作成して、シミュレーター上で用意されているテストをパスすればその章はクリアです。

Home | nand2tetris

このシミュレーターやテストが用意されているのが非常に取り組みやすく、テストをパスすることを目標として実装すればよいので迷わなくてすむのがよかったです。そうしてテストをパスするように章ごとの課題をこなしていけばいつのまにかコンピューターシステムが完成しているのです。

1章から5章: ハードウェア

まず、最初はNandゲートを組み合わせて論理ゲートを作り、それらのパーツを組み合わせて加算器やメモリやALUなどを実装します。作ったALUをベースにCPUを設計し実装するところまでが、ハードウェアのパートでやることです。

• 1章　ブール論理 : Nandゲートを組みわせてAND, ORなどの論理ゲートを作成します。
• 2章　ブール算術 : AND, ORなどのパーツをもとに加算器やALU(算術論理演算器)を作ります
• 3章　順序回路 :フリップフロップを用いて1bitレジスタから始めて16KBメモリ, プログラムカウンタを作ります
• 4章　機械語 :機械語についてHackアーキテクチャ向けのアセンブラを書いて学びます
• 5章　コンピュータアーキテクチャ : ここまで作ってきたカウンタやALUを組み合わせて、4章で学んだHackアーキテクチャの機械語を実行できるCPUを作り、メモリや入出力と組み合わせます

回路設計ですが、HDLを書いてシミュレーター上でテストしながら進めていきます。本書のサポートサイトからダウンロードできるツールチェインにハードウェアシミュレータがあり、実装したHDLをそのシミュレーター上でテストします。HDLは書いたことがなかったのですが、本書で扱うものは非常に単純なルールなのですぐに覚えることができました。

こんな感じでやっていきます。

駆け出しエンジニアなので論理ゲートの実装の勉強をしていますpic.twitter.com/bdMv0B0wzM

— 極限生命体しいたけNA (@yuroyoro)February 6, 2020

回路設計に悩むようすです

Nand2Tetris、今日はプログラムカウンターの実装まで。わからんくなったので回路図書いたわ…pic.twitter.com/PkQZtmPl5l

— 極限生命体しいたけNA (@yuroyoro)May 6, 2020

CPUの実装でこのページが出てきたときはめっちゃテンションあがりましたね？

たのしい。さいこうpic.twitter.com/iHPZJmWqQB

— 極限生命体しいたけNA (@yuroyoro)May 13, 2020

シミュレーター上で、自分がHDL書いたCPUがHack機械語を実行できるようになったときの様子です。やりきった感あった。

CPUとMemoryを実装したので組み合わせて、シミュレーター上で機械語が動くようになったｿﾞｫ……
HWはこれで一段落#nand2tetrispic.twitter.com/Vx8hfZRowL

— 極限生命体しいたけNA (@yuroyoro)May 15, 2020

6章から11章:コンパイラ

6章からはコンパイラの実装です。本書独自のJack言語のコンパイラを実装して、Jack言語ソースコードからHack機械語を生成できるようになるまでが目標です。

• 6章　アセンブラ : Hack機械語を生成するアセンブラを実装します
• 7章　バーチャルマシン#1：スタック操作 : スタックベースのVMを実装します。VMソースコードから6章で作ったアセンブリを生成できるようにします。
• 8章　バーチャルマシン#2：プログラム制御 :VM実装の続きで主に関数呼び出しを実装します。
• 9章　高水準言語 : Jack言語の言語仕様についての説明です。実際にこれから作るJack言語を書いてみます。
• 10章　コンパイラ#1：構文解析 : Jack言語コンパイラのフロントエンド部分の実装です。再起下降パーサーを書いてAST生成まで実装します。
• 11章　コンパイラ#2：コード生成 : Jack言語コンパイラのバックエンド実装です。ASTからVM向けのコード生成を行います。

コンパイラの章は大きく分けて3部構成で、アセンブラ、バーチャルマシン、Jack言語コンパイラに分けられます。それぞれのパートで実際にアセンブラやコンパイラを実装するわけですが、言語仕様を満たす実装ができるのであれば使用するプログラミング言語は何を用いても構いません。

「せっかくだから俺はこのRustという言語をを選ぶぜ」

アセンブラやVMの実装では、生成された機械語やアセンブラがCPUシミュレーター上で動作するかを確認します。ハードウェアではHDL上で回路をテストしましたが、コンパイラは生成したコードをシミュレーターでテストします。テストケースとして入力となるソースコードとその期待する動作をテストするためのスクリプトが用意されているので、テストがパスするような機械語/アセンブリ/VMコードを生成できるよぅに頑張るだけです。

アセンブラの実装はasmファイルを行ごとに読んでパースして機械語に変換するだけなので悩みはなかったです。この頃は主にRustについて悩んでいた

Nand2Tetris、ようやくRustでのアセンブラ実装が終わってVMの実装に入ったぞ

VM作るのたのしい
たのしい

— 極限生命体しいたけNA (@yuroyoro)September 8, 2020

Nand2Tetrisのアセンブラ、GoとかRubyとかjsとか手慣れた言語で書いたら多分2, 3時間で実装できたと思うけど、うっかりRustを勉強しながら書いてみたら実質2週間くらいかかって学習効率よくなかったですね面白かったけど

— 極限生命体しいたけNA (@yuroyoro)September 8, 2020

スタックマシンはCコンパイラ作成入門で一度実装したことがあったので、関数呼び出し時のスタックとかリターンアドレスとかそのあたりは理解していたのですが、Hackはレジスタ2個しかなくて実装しんどかったです。

配列のn番目への書き込みにn回の命令が必要なアセンブリ吐いてすみません……レジスタが足りない

オフセットレジスタの有り難さを身を持って体感してるぞﾗ

— 極限生命体しいたけNA (@yuroyoro)September 18, 2020

レジスタ2個しか無いのでレジスタ割付とか実装しなくてよくて楽ですね😇

— 極限生命体しいたけNA (@yuroyoro)September 18, 2020

汎用データレジスタとアドレスレジスタが一つづつしか無いHackアーキテクチャで単純とは言えスタックマシン実装するのはダルかった。ツールチェインにCPU Emulatorがあって助かった

— 極限生命体しいたけNA (@yuroyoro)September 28, 2020

asm生成で最初はjmp命令を駆使してサブルーチン化したasmを吐いていたが、どうせ命令数変わらない(どころかjmpの分増える)のでインライン展開することにしたわ

— 極限生命体しいたけNA (@yuroyoro)September 17, 2020

コンパイラに感謝する様子です

アセンブリ書くのダルすぎるので、高水準言語からアセンブリや実行可能な機械語を生成してくれるコンパイラは最高という気持ち高まっています

— 極限生命体しいたけNA (@yuroyoro)September 24, 2020

コンパイラが頑張ってjump命令吐いてくれるおかげでGOTOから書かなくてもよいんだぞコンパイラに感謝して？

— 極限生命体しいたけNA (@yuroyoro)September 28, 2020

Rustへの理解が深まっていく様子です

Rust、所有権と借用についてはなれてきたけど、LIfetime修飾子だけは使いこなせる気がしないです

迷ったら、コピーですよ? (知能)

— 極限生命体しいたけNA (@yuroyoro)September 24, 2020

Rust、構造体メンバに参照もたせるとLIfetime修飾子で死ぬけど、std::rc::Rcで参照カウントで持たせたらLifetime考えなくても参照カウントで勝手に管理してくれるので解決では？？

(なお参照リークについては考えない事とする😇)

— 極限生命体しいたけNA (@yuroyoro)October 27, 2020

Rust、「こんなダルい思いするくらいならコピーのコストくらい払ったるわ」という誘惑と戦うプログラミング言語だという実感です

— 極限生命体しいたけNA (@yuroyoro)October 31, 2020

Rustのmacro、便利😇

— 極限生命体しいたけNA (@yuroyoro)November 4, 2020

Rust書いてる僕ですpic.twitter.com/cmdQHAOBi1

— 極限生命体しいたけNA (@yuroyoro)September 14, 2020

現状ですpic.twitter.com/Q70KBkJEyO

— 極限生命体しいたけNA (@yuroyoro)September 30, 2020

VM実装終わったとき

Nand2Tetris、RustでJackVMの実装まで終わったぞhttps://t.co/v18qXGtFZy

— 極限生命体しいたけNA (@yuroyoro)September 28, 2020

Jack言語コンパイラに関しては再起下降パーサーを書いたことがあるので実装面で悩むことはなかったです

再帰下降パーサー、好き♡

— 極限生命体しいたけNA (@yuroyoro)October 14, 2020

Rustで再帰下降パーサー書いてるけど、意図せずにstreamを消費するようなバグが起きにくいのでよい感じです

ただしコンパイル通すまでが厳しい

— 極限生命体しいたけNA (@yuroyoro)October 29, 2020

Rustで抽象構文木のような再帰的な構造を定義するとどうしてもBoxに入れざるを得なくて、rustcはどうやってるか見てみたらやっぱりBoxに入れてたので間違ってなかった

— 極限生命体しいたけNA (@yuroyoro)November 4, 2020

Rustでparserをベタで書いてみたけど、コンパイルエラーにすべき箇所がちゃんと型チェッカで網羅できたのでよかったです ᕕ( ᐛ )ᕗ

— 極限生命体しいたけNA (@yuroyoro)November 8, 2020

できた。Nand2Tetris 10章のJack言語コンパイラのフロントエンド部分のRust実装が。https://t.co/zXeqwuf4tN

— 極限生命体しいたけNA (@yuroyoro)November 8, 2020

12章:オペレーティングシステム

正直ここからはおまけです。Jack言語でOSを書くのですが、このOSは上で述べたとおりハードウェアとのやりとりをするためのメモリアクセスを便利にしてくれるライブラリみたいなものです。Jack言語も非力な言語なので書くのはダルかったです。ただ、自作したコンパイラがちゃんとシンタックスエラーを検出してくれたときはちょっとしたうれしみが湧き上がりましたね?

自作コンパイラ、ちゃんとコンパイルエラー検出してくれてすごい

— 極限生命体しいたけNA (@yuroyoro)November 16, 2020

たとえば、画面に文字を出力するのにDMAされた画面のピクセルに対応するメモリのビットをフォントにしたがって立てる処理とか書くのダルかったです。

画面に文字を出力するのマジでダルかったわpic.twitter.com/vqEok7c89y

— 極限生命体しいたけNA (@yuroyoro)November 23, 2020

あと、画面に●を描画する際の高速なアルゴリズムとか勉強になりましたね多分もう使うことないだろうけど

• Midpoint circle algorithm - Wikipedia
• 伝説のお茶の間 No007-09(1) 円の描画(1) MichenerとBresenham
• QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。

とはいえ、自分で書いたOS(っぽいライブラリ)でゲームが動いたときは達成感ありましたね。

Nand2Tetris 「コンピュータシステムの理論と実装」、完走しました

CPUからOSまで一気通貫で作るのは楽しかったですhttps://t.co/m223NjRcdS

— 極限生命体しいたけNA (@yuroyoro)November 23, 2020

まとめ

O'Reilly Japan - コンピュータシステムの理論と実装 、楽しいのでみんなやるといいですよ?

とくに、コンピューターサイエンスに苦手意識があるとかローレイヤー怖いとかの人におすすめです。やってみると、とてもシンプルな仕組みの積み重ねでコンピューターが動作していることが実体験として理解できます。そして、現代のCPUやOSがどれだけ進歩しているかも……

僕が今勉強で作ってるレジスタ2個しかなく乗除算すらできない16bitCPUに比べると、マルチコアでL1,L2キャッシュを持ちパイプライン化されて分岐予測やリオーダーを行い、浮動小数点演算どころかSIMDとかSHA計算までサポートする現代のCPUは超文明が残したオーパーツにしか見えないです

— 極限生命体しいたけNA (@yuroyoro)November 20, 2020

本書で取り扱うそれぞれのトピックは概要レベルですので、例えばコンパイラについてもっと学びたいとかOSを詳しく知りたいというニーズには適してはいませんが、全体を俯瞰する入り口としては最適だと思います。

そして、理解を深めるにはものすごく単純でもいいから自分で作ってみるてっとり早いのですが、本書はそれを手助けしてくれる素晴らしい内容でした。今後は、自作ブラウザとか自作TCP/IPプロトコル・スタックとか自作RDBMSとか、挑戦してみたいものが山積みです。

で次ですが、Nand2TetrisではOS部分が薄くて物足りないかったので、OSを作ってみることにしました。

買いましたよ？

30日でできる! OS自作入門【委託】 -達人出版会https://t.co/WfHOtXQSS6

— 極限生命体しいたけNA (@yuroyoro)November 17, 2020

12月は忙し目なので、年末年始からまた腰を据えて取り組みたいと思います。

あと、Rust完全にマスターしました(光を放ちながら消滅)

こんにちわ、しいたけです。

今は夏休みで奥さんと子どもたちが帰省しているので、動物と2人で暮らしています。

で、外出すると動物だけを家に残していくことになります。ペットモニターとか市販でもあるんですが、せっかくなので、 夏休みの自由研究として、ラズパイ+カメラモジュールとWebRTCを使って、外出先からでも動物の状態を確認できるやつを作ってみました。

↑ 死活監視される動物の様子です

用意したもの

• Pi3 B+ スターターキット V3 16GB 白
• Piカメラ Official V2 for 3/2/1/0
• Manfrotto ミニ三脚 PIXI ブラック MTPIXI-B カメラ用
• Manfrotto スマートフォン用三脚アダプター MCLAMP
• HAKUBA 自由雲台 BH-1

ラズパイ3とケースのセットとカメラモジュールはRaspberry Pi Shop by KSY で購入。期間限定セールでちょっと安かったです。このセットについてるケースは、ラズパイのマークの穴にカメラモジュールを固定することができて便利。時雨堂のmomoだと、Raspberry Pi のGPU のH.264 ハードウェアエンコーダー機能を利用できるらしいので、ラズパイzeroでも行けるらしいです。

で、ラズパイを三脚とスマホ用アダプタで固定します。こんな感じになる。

ラズパイの初期設定

まずはラズパイの初期設定でOSインストール。購入したキットのSDカードにすでにOSが用意されているので、電源入れて画面の通りにセットアップすれば終了。

Raspberry Pi 3 Model B+の初回セットアップ（購入から起動まで） - Qiita

あとは、sshとカメラモジュールをconfigから有効にしておく。

Raspberry Piカメラのセットアップ方法

最後に、mDNSとssh周りの設定を行って、GUIをオフにして完了。これで手元のmacbookからsshで接続して作業できるようになった。

手持ちのRaspberryPiをサクッとmDNSに対応させる - Qiita

WebRTC Native Client Momo

時雨堂のWebRTC Native Client Momo を使います。あっさり接続できて最高でした。

Githubのリリースページ から最新のバイナリがtarで配布されているので、ダウンロードして解凍するだけです。

必要なライブラリを入れて、

$ sudo apt-get install libnspr4 libnss3

あとはバイナリを実行するだけで、ラズパイのカメラモジュールを利用したストリーミングが可能になります。

$ ./momo --no-audio ayame wss://ayame-lite.shiguredo.jp/signaling <your-github-id>@<your-room-name> --signaling-key <your-signaling-key>

起動時のオプションは、シグナリングサーバーにAyameとそのURL、そしてルームIDを指定します。また、次で説明するシグナリングキーもわたします。

時雨堂 WebRTCシグナリングサービス Ayame Lite

WebRTCにおいてNAT超えで通信を行うにあたって、シグナリングサーバを介してそれぞれのピアの接続の調整を行う必要がある。時雨堂がWebRTC のP2P 利用向けに無料で利用できるシグナリングサービスを提供してくれているので、ありがたく使わせていただきます。

WebRTC シグナリングサービス Ayame Lite 開発ログ

P2Pで接続できる場合には、特に登録も必要なく使えます。4G回線の場合などTURNサーバーを経由する必要がある場合は、ベータテスト中のシグナリングキーを利用してTURNサーバーの払い出しをしてもらう必要があります。Githubアカウントでサインアップすると、シグナリングキーが発行されてTURN サーバの利用が可能になります。

STUN/TURNについてはこのあたり参照

• WebRTCの裏側
• 壁を越えろ！WebRTCでNAT/Firewallを越えて通信しよう | HTML5Experts.jp

4Gでつながらないとtwitterで囀っていたところ、@voluntas にベータ版使ってみる? とお誘いを受けたので、ありがたく使わせてもらいました。ちょうどオープンベータが始まったところでした。

Ayame Lite オープンベータテスト開始しました - shiguredo - Medium

こちらからGithubアカウントでサインアップできます。

Ayame Lite

時雨堂最高では?

クライアント側の実装

あとは、クライアントを準備して接続です。手っ取り早く試してみるのに、OpenAyame/ayame-react-sample: Ayame React サンプル を利用しました。上記のリポジトリをgit clone したあと、yarn install してyarn serve すると、localhostで動作確認ができます。

こんな感じで、AyameのURLと、自分で指定したルームID、シグナリングキーを入力して接続を押すと、ストリーミングでラズパイ側のカメラから配信されていることが確認できます。

iOSSafariの場合は再生ボタンを押す必要があるとのことで、video タグにcontrols を追加して対応しました。

<Videos>  <RemoteVideo ref={remoteVideoRef} muted autoPlay controls/></Videos>

その他調整

まず、クライアントのアセット一式を適当な場所から配信できるようにします。yarn build してできた成果物をさくらVPSにnginxを立ててﾚｯﾂをｴﾝｸﾘﾌﾟﾄしてhttpsで配信できるようにしました。httpsで配信できる場所なら、cloudfrontとかNetlifyとかでもいいと思います。

あとは、ラズパイ側のmomoをsystemdのサービスとして設定して起動時に起きるようにすれば終わりです。

Raspberry Pi で systemd を使ってプログラムを自動実行する - Qiita

まとめ

ラズパイでWebRTCするにあたって、当初はNTTコムさんの提供するSkyway とそのsdkを試してみたのですが、どうもデモが上手く動作しませんでした。時雨堂のmomoとOpenAyameを使ってみたところ、バイナリを落としてきてドキュメントの手順通りに進めるだけであっさり接続できてしまいました。

これで外出時でも動物の様子を死活監視ができて捗る。

時雨堂最高では?

タイトルで全部言い切ってますが

// Optional container like maybe monadclass Option{  constructor(value){this.value = value}  async promise(){returnnew Promise((resolve, reject) =>{if (this.value){        resolve(this.value);}else{        reject(undefined);}});}}

こんなMaybe とかOptionalっぽいやつを用意します。promise() で Promiseを生成して返すようにします。もってる値に応じてresolve (JustやSome)したりreject (Nothing)したりします。

const o1 =new Option("foo");const o2 =new Option("bar");const o3 =new Option(null);(async () =>{try{const v1 = await o1.promise();const v2 = await o2.promise();    console.log(v1, v2);}catch{}})();// => foo bar(async () =>{try{const v1 = await o1.promise();const v2 = await o2.promise();const v3 = await o3.promise();    console.log(v1, v2, v3);}catch{}})();// do nothing// introduce doM emulates do-like syntax sugarasyncfunction doM(f1, f2){try{return f1();}catch{if (f2){return f2();}}}// => foo bar

asyncの中で、promise() を awaitで呼び出すことで、 do記法っぽいあれ……に見えなくもなくないコードになりました。でも失敗系処理しない場合でもcatch 書く必要あるのダルいですね？try..catch を変わりにやってくれるヘルパーを導入しましょう

// introduce doM emulates do-like syntax sugarasyncfunction doM(f1, f2){try{return f1();}catch{if (f2){return f2();}}}

このdoM に asyncな無名関数を渡すと、その中でdo記法っぽいあれ……に見えなくもなくないコードを書けます。

doM(async () =>{const v1 = await o1.promise();const v2 = await o2.promise();  console.log(v1, v2);});// => foo bardoM(async () =>{const v1 = await o1.promise();const v2 = await o2.promise();const v3 = await o3.promise();  console.log(v1, v2, v3);});// do nothing

だからどうしたって話ですが、いろいろなモナドを作って合成して扱う場合に便利かもしれないですがそもそもモナドとかJavaScriptで作るな。以上

こんにちは、しいたけです。

某所で関数型プログラミングとはリスト処理のことなのか、と燃えているのを見て、関数型プログラミングとは何か、ということを自分なりの考えを述べたいと思いました。春なので。

この資料は2年ほど前にSupershipの社内勉強会で使ったものですが、この中で関数とオブジェクトを対比している箇所があります。関数もオブジェクトも、変数や関数の引数戻り値として扱える第1級の値であり、状態を持ち(メンバー変数/クロージャ)、組み合わせが可能(delegate, composition/関数合成)、である、と。

ではオブジェクト指向と関数型プログラミングで何が決定的に異なるかというと、設計・実装のアプローチに何を中心に据えるか、ということだと思います。

オブジェクト指向では、クラス・オブジェクトをモデリングし、各種のオブジェクト指向的デザインパターンを用いてオブジェクト同士を組み合わせながら設計・実装を行います。関数型プログラミングでは、関数を細かな組み合わせ可能な単位に分解し、関数合成、再帰、クロージャなどを駆使しながら組み合わせることで設計・実装します。

こう書いてみると当たり前のことですが、コードの記述スタイルだけ議論しても意味がなくて、そのような記述はプログラム全体を貫く思想のなかでどのような位置づけにあるのかのコンテキストが重要なのではないでしょうか。例えば、Goでは無理して無名関数を用いたリスト処理を書くより、forで書くほうがはるかに自然ですよね。JavaScriptでは……どうでしょうか、色々なスタイルで書けるので議論が紛糾するのかも。

map/reduceを使ったリスト処理が関数型プログラミングの全てかというとそうではなく、あくまで関数を中心に据えた考えた方の一つとして、遅延評価 +高階関数/クロージャの組み合わせによるストリームライクな実装がある、ということだと思います。関数を中心に据えると、「何をフィルターするか」「要素をどのように変換するか」という処理の単位が関数として抽出され、その組み合わせ方法として遅延評価リストと高階関数を用いる方法がある、というだけです。結果、関数を中心にすえたアプローチではmap/reduceを使う記述が自然と導かれます。とはいえ、 リスト処理の実装としては再帰を使う方法もあるので、あくまで関数型プログラミングによるリスト処理の1アプローチにすぎません。

どちらのスタイルで書くのがよいか、というのに絶対的な正解はないと思いますが、関数を中心としたアプローチを知っていると、手続き型のプログラムを書いていても思わぬ場面で役に立つことがあります。ちょうど最近役にたった実体験のひとつで、 あるrspecのパフォーマンスチューニングの際に遅延評価が役にたったことがあります。

error_msg = generate_error_message(actual_value, expected_value)expect(actula_value).to have_content(expected_value),  error_msg

こんな感じのrspecのコードで、 assertのエラー時に表示するerror_msg を生成するgenerate_error_message が非常にコストの掛かる処理でした。通常はassertに失敗する場合の方が稀なので、必要になるまで(assertに失敗するまで) この処理の呼び出しを遅延させることで性能が改善しそうです。

rspecのexpect はエラーメッセージの代わりにProc を渡すことが可能です。そこで、エラーメッセージを生成する処理をクロージャとして抽出し、expect に渡すことで遅延評価させることができます。

error_msg_generator = ->() { generate_error_message(actual_value, expected_value) }expect(actula_value).to have_content(expected_value),  error_msg_generator

関数型プログラミングの知識があると、expect の引数がProc を取る、というシグニチャから、遅延評価による性能改善に利用する発想が導かれます。このように、関数型プログラミングは通常の手続き型プログラミングでもおおいに役立ちますので、双方それぞれの手法を学んでおくとプログラミングの裾野が広がりま。これが、ぼくが関数型プログラミングを学ぶことをオススメする理由です。

まとめ

• 関数型プログラミングとは「関数を中心としたアプローチ」
• リスト処理は関数型プログラミングの一側面
• どっちがよいかはケースバイケース
• 関数型プログラミングを知っているとプログラミングの裾野が広がるよ

しいたけおいしいです。

ᕕ( ᐛ )ᕗ こんにちわ、しいたけです。

webのhttps化が推進される昨今ですね?
https通信は経路上での通信内容が盗聴・改竄されるのを防ぐことができますが、開発用途でhttps通信の内容を確認したい場合が稀にあります。
そのような場合はmitmproxy などを導入すればよいのですが、せっかくなので実際にこのようなProxyをGoで実装してみて、 中間者攻撃(Man-in-The-Middle Attack)がどのような手法でhttps通信を盗聴・改竄するのか確かめてみました。

実際に書いたProxyのコードはこちらです

yuroyoro/mitm_proxy_sample

https proxy と HTTP CONNECT tunneling

まず、通常のhttps Proxyの動作を確認してみましょう。

httpsでは、ProxyはクライアントからのCONNECTメソッドを受信すると、クライアントに代わって対象ホストとのTCPコネクションを確立し、以降はクライアントと対象ホストのTCP通信を転送します。クライアント-ホスト間のTLS接続のhandshakeもproxyを経由して行わます。
この方式により、Proxyを経由しつつクライアント-ホスト間でTLSセッションが確立され、Proxyを経由しつつも経路上では暗号化された通信が可能となります。

図にするとこんな感じです

実装

では具体的な実装を見てましょう。
まずはおなじみServeHTTP です。クライアントからCONNECT メソッドが送信されたら、通信を転送するrelayHTTPSRequest を呼び出します

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/main.go#L34

func (proxy *MiTMProxy) ServeHTTP(w http.ResponseWriter, r *http.Request) {// CONNECT メソッドが来たらif r.Method == http.MethodConnect {if proxy.mitm {            proxy.mitmRequest(w, r)// Man in The Middleする        }else {            proxy.relayHTTPSRequest(w, r)// Tunnelingで通信を転送する        }return    }    proxy.transportHTTPRequest(w, r)}

実際に通信を転送しているコードは以下のとおりです。処理の流れはコメントを読んでもらえばわかると思いますが、やっていることは単純です。
CONNECT メソッドで指定されたホストにTCP接続を張って、クライアントからの通信をそのまま流し込むだけです

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/https.go#L12

func (proxy *MiTMProxy) relayHTTPSRequest(w http.ResponseWriter, r *http.Request) {    proxy.info("relayHTTPSRequest : %s %s", r.Method, r.URL.String())// CONNECT先のHostへTCPコネクションを張る    dest, err := net.Dial("tcp", r.Host)if err !=nil {        http.Error(w, err.Error(), http.StatusServiceUnavailable)return    }// http.Hicjacker を利用してクライアントとの生のTCPコネクションを取り出す    conn := hijackConnect(w)// クライアントには200 OKを返す。これでクライアントはこのTCP接続にHTTPリクエストを送ってくる    conn.Write([]byte("HTTP/1.0 200 OK\r\n\r\n"))    proxy.info("relayHTTPSRequest : start relaying tcp packets %s %s", r.Method, r.URL.String())// クライアント-対象Host間のTCP通信をそのまま中継するgo transfer(dest, conn)go transfer(conn, dest)}func transfer(dest io.WriteCloser, source io.ReadCloser) {defer dest.Close()defer source.Close()    io.Copy(dest, source)}

Goにはhttp.Hijacker という便利なインターフェースがあり、http.ResponseWriter から生のクライアントとのTCP接続を取り出すことができます。
これを利用して、TCP通信の転送を行っています

func hijackConnect(w http.ResponseWriter) net.Conn {    hj, ok := w.(http.Hijacker)if !ok {panic("httpserver does not support hijacking")    }    conn, _, err := hj.Hijack()if err !=nil {panic("Cannot hijack connection " + err.Error())    }return conn}

実際はtimeoutなどを考慮した実装をすべきなのですが、これだけでも動きます。

Man in The Middel Proxyの仕組み

では、本題の中間者攻撃を行うProxyについてです。

通常のhttps proxyでは、クライアントからのCONNECT メソッドを契機に、対象HostとのTCP通信を中継していました。
Proxyを流れる通信内容はTLSによって暗号化されており、内容を盗聴・改竄することはできません。

しかし、対象Hostとクライアント間のTLS handshakeもProxyを経由するので、この段階でクライアントからのTLS handshakeを、対象ホストになりすましてProxyが行うとどうなるでしょうか？
つまり、Proxyは対象ホストのサーバー証明書をその場で生成して署名し、クライアントに提示します。
もちろん、Proxyが署名したサーバー証明書は信頼できないCAのものとしてブラウザには警告が出ますが、そのままユーザーが続行することでTLS handshakeが成功します。
クライアントは確立したTLS接続を対象ホストとのものだと思いこんで、Proxyがクライアントに送り込んだニセのサーバー証明書の公開鍵で通信を暗号化するので、Proxyはその内容を復号することができます。
あとは、復号したリクエストをそのまま対象のホストに転送すれば、httpsにも関わらずProxyは通信内容を把握しつつ、対象ホストとの通信を取り持つことができてしまいます。
これで中間者攻撃が成立しますʕ　 ﾟ皿ﾟ ʔ 。

図にすると以下の流れとなります

通常、このような攻撃はブラウザが警告を出すために成立しません。
まず、ユーザーが明示的にブラウザにProxyを指定する必要がありますし(port forwardを利用した透過Proxyはその限りではない)、Proxyが署名に使用するルート証明書(または中間証明書)がTrust Chainにないからです。
逆に言えば、信頼できないルート証明書をシステムにインストールしてしまうと、このような攻撃が成立する余地が生まれてしまいます。

実際に、一部のセキュリティアプライアンスやアンチウィルスソフトウェアは、このような手法でhttps通信の内容をチェックしています。
Avastを入れた状態でブラウザで証明書チェーンを確認すると、 「Avast trusted CA」という謎の認証局が出現するのはこのためです( ;ﾟ皿ﾟ)ﾉｼΣ ﾌｨﾝｷﾞｨｨｰｰｯ!!!

以前、LenovoのPCにプリインストールされたアドウェア「Superfish」がルート証明書をシステムにインストールした上に、全PCで共通のCA秘密鍵を使っていたことで大問題になりましたね。
Dellでも似たようなことがあったみたいです( ꒪⌓꒪)

LenovoのPC全機種にプレロードされているアドウェアが実は恐ろしいマルウェアだった！ | TechCrunch JapanDellのPCに不審なルート証明書、LenovoのSuperfishと同じ問題か - ITmedia エンタープライズ

実装

それでは具体的な実装の解説を行います。処理の流れは以下のとおりです。

1. CONNECTメソッドのリクエストから、http.Hijackerを使って生のTCPコネクションを取り出す
2. クライアントには200 okを返す
3. 接続先ホストの証明書を、予め用意してあるroot証明書でサインして生成する
4. 生成した証明書でクライアントとtls接続を確立する (root証明書が登録されていないとブラウザで警告が出る)
5. goroutine起こして、クライアントとのtls接続からhttp requestを読み込む
6. 受けたhttp requestをそのまま接続先hostに送信する
7. 接続先hostからのhttp responseを、クライアントtls接続に書き込む
8. EOFが来るまで 5-7繰り返し

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/https.go#L57

func (proxy *MiTMProxy) mitmRequest(w http.ResponseWriter, r *http.Request) {// http.Hicjacker を利用してクライアントとの生のTCPコネクションを取り出す    conn := hijackConnect(w)// クライアントに200 OKを返しておく    conn.Write([]byte("HTTP/1.0 200 OK\r\n\r\n"))// 以降の処理はgoroutine上で行うgo proxy.transportHTTPSRequest(w, r, conn)}func (proxy *MiTMProxy) transportHTTPSRequest(w http.ResponseWriter, r *http.Request, conn net.Conn) {    proxy.info("transportHTTPSRequest : %s %s", r.Method, r.URL.String())// 対象ホストのニセのサーバー証明書を生成して署名する    host := r.Host    tlsConfig, err := proxy.generateTLSConfig(host)if err !=nil {if _, err := conn.Write([]byte("HTTP/1.0 500 Internal Server Error\r\n\r\n")); err !=nil {            proxy.error("Failed to write response : %v", err)        }        conn.Close()    }// クライアントとのTCP接続上で、ニセのサーバー証明書を利用してTLS接続を待ち受ける    tlsConn := tls.Server(conn, tlsConfig)if err := tlsConn.Handshake(); err !=nil {        proxy.error("Cannot handshake client %v %v", r.Host, err)return    }defer tlsConn.Close()    proxy.info("transportHTTPSRequest : established tls connection")// ニセの証明書で確立したTLS接続上でクライアントからのリクエストを読み込む    tlsIn := bufio.NewReader(tlsConn)for !isEOF(tlsIn) {        req, err := http.ReadRequest(tlsIn)// http.Requestオブジェクトとして通信を読み込むif err !=nil {if err == io.EOF {                proxy.error("EOF detected when read request from client: %v %v", r.Host, err)            }else {                proxy.error("Cannot read request from client: %v %v", r.Host, err)            }return        }        proxy.info("transportHTTPSRequest : read request : %s %s", req.Method, req.URL.String())// 転送用にURLやヘッダーなどを設定        req.URL.Scheme ="https"        req.URL.Host = r.Host        req.RequestURI = req.URL.String()        req.RemoteAddr = r.RemoteAddr        dumpRequest(req)        removeProxyHeaders(req)// http.RoundTripper で受信したリクエストを対象ホストに転送し、レスポンスを受け取る        resp, err := proxy.transport.RoundTrip(req)if err !=nil {            proxy.error("error read response %v %v", r.URL.Host, err.Error())if resp ==nil {                http.Error(w, err.Error(),500)return            }        }        proxy.info("transportHTTPSRequest : transport request: %s", resp.Status)        dumpResponse(resp)// レスポンスをクライントへのTLS接続に書き込む        resp.Write(tlsConn)    }    proxy.info("transportHTTPSRequest : finished ")}

ポイントは、 リクエストを受けるとニセのサーバー証明書をその場で生成して、その証明書とhttp.Hijacker で取り出したクライントのTCPでtls.Server を用いてTLS接続をなりすますことです(生成した証明書はキャッシュします)。
証明書の生成は長くなるのでここには載せませんが、こちら を見てもらえばと思います。

クライントとのTLS接続を乗っ取れば、あとはその接続上でHttpリクエストを読み込み、対象ホストに転送すればOKです。Goでは、http.RoundTripper を利用すればhttp.Request をそのまま転送できるので便利です。その際に、リクエスト・レスポンスの内容をdumpしています。
悪意があれば、この段階で改竄も可能でしょう。

まとめ

以上が、Man-in-The-Middle Attackを行う簡単なProxyの実装です。この攻撃が成功する条件としては、

• 経路上にこのようなProxyが存在する (https通信がport forwardされている場合もある)
• Proxyが署名に使うルート証明書がTrust Chainに存在する

の2点です。特に2点目はTLSの根幹をなす部分で、それゆえにルート証明書の管理は厳格に行う必要があり、GoogleはSymantecの証明書を無効にし、LenoveやDellは責められるべきなのです。Avastもちょっとどうかと思います。

実際に手を動かして実装してみると、Proxyの実装で注意スべき点や、TLSと認証局の仕組みとか色々と学びがあり、よかったとおもいました( ꒪⌓꒪)

こんにちわ。しいたけです。今日はgoroutineの実行状況をいいかんじに可視化するツールの話です。

goのプロファイリングツールと言えば、runtime/pprof やnet/http/pprof ですよね。これらの使い方はググればすぐに出てくるのですが、 詳細なtraceを取得して可視化できるruntime/trace については、日本語の情報が殆ど無いので書いてみましいたけ。

runtime/trace はgoroutineの実行状況やsystem callのイベント、Heapやnetworkの状況をこんな感じに可視化してくれるので便利です。

これは自作のクローラーを動かしている際のtraceを可視化したもので、横軸がタイムラインになっており、上段に Heapの使用状況やgoroutineとos threadの数が, 下段はnetworkやProccesor(GOMAXPROCSで指定するgoroutineの実行環境)毎にどのコードが実行されているか、が表示されます。

Heapやgoroutines数の増減と処理の関連を時系列で追えるので、大まかなボトルネックの特定に便利です。また、各goroutine毎の開始/終了とsystem callやunblockイベント(goroutineの切り替え)を細かく追えるので、goroutineが刺さっている箇所の特定にも役立ちます

右側のboxの↓アイコンをクリックした上で、グラフ上でドラッグするとzoomin/outできます。また、View Options で Flow Eventsをチェックすると矢印が描画されます

ここに、実際に動かせるサンプルを置いておきます。

• http://yuroyoro.net/gotrace01/trace.html
• http://yuroyoro.net/gotrace02/trace.html

これはとある自作Proxyのtraceの一部で、Proc3で実行されている皆さんおなじみのnet/http.(*conn).serve がリクエストを受けて、 go 構文で新たなgoroutineを起動してProc2で実行される様子です。このように、どのタイミングでどのgoroutineが動いたのかが一目瞭然です。

これはGCが実行されている様子です。ほとんどのProcでGC関連の処理が動いた後に、上段のHeapのallocatedが減っている様子が見てとれます。

で、このtraceの可視化の方法ですが、 手っ取り早いのはruntime/trace パッケージをimportして、trace.Start(w io.Writer) とtrace.Stop() を呼び出す方法です

https://golang.org/pkg/runtime/trace/

package mainimport (    "log"    "os"    "runtime"    "runtime/trace")func main() {    f, err := os.Create("trace.out")    if err != nil {        log.Fatal(err)    }    defer f.Close()    trace.Start(f)    defer trace.Stop()  // do something ...}

このように、traceを取得したい処理の前後でtrace.Start を呼び出すと、結果がファイルに出力されます。 そのファイルをgo tool trace コマンドの引数に渡すと、ブラウザで取得したtraceを分析できるようになります。

net/http/pprof パッケージを使っているウェブアプリケーションでも、簡単にtraceを取得することができます。

pprofがlistenしているなら、/debug/pprof/trace?seconds=5 にリクエストを送ると、5秒間のtraceを取得して結果をダウンロードできます。得られたファイルをgo tool trace に渡せば、同様にブラウザ上で分析できます。

詳細なボトルネックの分析は、 pprofやgo-torchでのflamegraphの分析が有向ですが、go tool trace では時系列に対応しての分析が可能なので、それぞれ状況に合わせて使い分けると良いのではないかと思いましいたけ。

F.Y.I.

• Go Execution Tracer
• go tool trace - Making Pusher

こんにちわ。しいたけです。今日はディスク使用量をFlameGraphにするツールの話です。

FlameGraphについては、Flame Graphs やGolangでFlame Graphを描く | SOTA を読んでもらうのが手っ取り早いのですが、ようはプロファイル結果を可視化する方法です。縦軸が呼び出しの階層に、横軸がサンプル数や実行時間などに対応しており、どの関数が支配的かを直感的に見ることができる優れたグラフですよ。

で、このFlameGraph、別にプロファイル結果だけではなく、ツリー構造で各ノードが量を持つ場合に、枝毎の累積量を可視化するのに利用できます。プロファイル以外に、ツリー構造でノードが量を持つ例として、ディレクトリ階層毎のディスク使用量が考えられます。

というわけで、指定ディレクトリ以下のディスク使用量をFlameGraph化するツールを書きました。

GitHub - yuroyoro/du-flamegraph: visualize disk usage as flamegraph

こんな感じのグラフが出力されます

goで書かれており、使い方は、 `go get -u yuroyoro/du-flamegraph` でインストールできます。

このツールは、 FlameGraphの描画に `flamegraph.pl` というスクリプトが必要であり、これはGitHub - brendangregg/FlameGraph: Stack trace visualizer にあります。
これを git cloneなどで手元に入れて、 $PATHに追加するか、 `--flamegraph-script` で位置を指定するかしてやれば、FlameGraph がsvgとして出力されます。

NAME:   du-flamegraph - visualize disk usage as flamegraphUSAGE:   du-flamegraph [global options] [FILE]VERSION:   0.0.0GLOBAL OPTIONS:   --width value, -w value    width of image (default 1200) (default: 1200)   --height value, -h value   height of each frame (default 16) (default: 16)   --flamegraph-script value  path of flamegraph.pl. if not given, find the script from $PATH   --out value                distination path of grenerated flamegraph. default is ./du-flamegraph.svg (default: "./du-flamegraph.svg")   --verbose                  show verbose log   --version, -v              print the version

FlameGraph、色々と応用がききそうですね。