kawasin73のブログ

技術記事とかいろんなことをかくブログです

55 日かけて OS を作った

作ったもの C

整骨院は保険がきく。どうも、かわしんです。 突発的な不調の場合は整骨院は保険が適用され 3 割負担になります。慢性的なもの（肩こり）には適用されません。

さて、5 月 20 日に以下のように宣言して作り始めた OS が、昨日ようやくひと段落したのでまとめの記事を書くことにしました。

かの有名な「30日でできる! OS自作入門」（通称 : 30日OS本）をただ写経しただけなのですが、すごく勉強になりました。

30日でできる! OS自作入門

30日でできる! OS自作入門

この本は 30 日とうたっていますが、僕は 55 日かかりました。ただ忙しくて毎日はできなかっただけなので実働自体は 30 日なのですが、これも僕の実力です。

毎日 1 日分だけを進めて全て自分の手で打ち込み、サンプルコードからのコピペはしないという縛りで実装しました。もちろん、自分が書いたコードはコピペ可としました。そうしないと辛すぎるので。

だいたい 1 日分は 2 ~ 3 時間くらいかかりました。写経するだけですが、本の中身を読んで理解したり、写し間違えによるバグを直したりすると結構時間がかかります。

いつも、学校から帰ってきて仕事を始める前の息抜きに OS を作っていましたが、結局 OS を作るだけで1日が終わってしまうことが多々ありました。そのくらい重いです。

できたもの

出来上がった OS はこれです。

f:id:kawasin73:20190714140358p:plain

僕のプロフィール JPEG 画像を表示して、インベーダーゲームを表示してるだけですが、この裏で 1 文字 1 文字打ち込んだコードが動いています。

ソースコードはこれです。自分の名前をつけようと kos (kawasinOS) と名付けましたが、めんどくさくなったので途中からは本に書いてある通り Haribote OS の名前で実装しています。

リポジトリ名が kos-sample となっているのはその名残です。-sample とつけているあたり、またもう１つ OS を作る野望が見え隠れしますが疲れてしまったので次があるかは未定です。

github.com

感想

知識だけでない実践

OS の仕組み自体は大学の授業で習っていたので、ページングやスケジューリングアルゴリズム、プロセスの仕組み、ユーザランドとカーネルランド、CPUの保護、ファイルシステムなどの理論は知っていました。しかし、それを具体的にどのように実装するかは曖昧なままでした。

多分、すでに OS のコードベースがあってそれに機能追加やパフォーマンス改善をする OS 開発をすることはできたと思いますが、何もない状態から 0 ベースで作り上げることは無理だったと思います。

この 30 日 OS 本は、本当に 0 から作り上げていく本なので、どのようにコンピュータが動いているのか全てを理解したかった僕にはうってつけでした。

コンピュータと C 言語の本質

普段ソフトウェアを作るときのインターフェースは システムコール であり OS を相手取って操作します。また、システムコールの上に構築されたライブラリの関数呼び出しも利用します。

一方で、OS を作るときのインターフェースは CPU命令 であり、CPU を相手取って操作します。PIC (Programable Interrupt Controller) や PIT (Programable Interval Timer) やマウス・キーボードなどのデバイスなど、全て CPU 経由で操作します。CPU にはそのための命令が全て用意されており、その振る舞いも全て仕様が決まっています。

ソフトウェア開発との違いはインターフェイスがすでに C 言語の関数の形で用意されている点です（もちろんその関数自体はアセンブリで作られていますが）。OS 開発で必要なインターフェイスである CPU 命令は C 言語のインターフェイスを持っていないため、自分でアセンブリを書いて C 言語で扱える関数を用意 します。この辺りは、正月に作った C コンパイラ 1 の知識が役に立ちました。

そして、自分でアセンブリによって作った関数を C 言語から呼び出して OS を構築していきます。ここで C 言語は何も機能を持っておらず、所詮メモリを操作して関数を呼び出しているだけ のことしかできないのだと理解しました。なんでも自由にできる万能な言語だと思っていた C 言語が、メモリ操作 と 関数呼び出し だけしかできない低機能野郎だったと知れたのは意外な発見でした。

この辺りの C 言語の本質、CPU と OS との関わりなどは、大学の授業では知ることができませんがこの 30 日 OS 本を読むことで理解できました。

プログラミングの方法

また、30 日 OS 本では 基本的なプログラミングの方法 が学べます。この方法は DMM でインターンしてる時 2 にメンターさんに教えてもらった方法なのですが、この本でも全く同じ方法でプログラミングされておりプログラミングの基本中の基本とはこのことなのかと思いました。

普段フレームワークありきでアプリケーションなどを作っている場合にはなんとなく作ってもなんとなく動くものができてしまいますが、正しく動くメンテナブルなソフトウェア を 0 から作る場合にはこの基本は重要です。といっても大したことではないのですが。

まず、main 関数に全ての処理を愚直に書き連ね ます（30 日 OS 本では、HariMain ですが）。関数定義などはしません。main 関数一本勝負です（あまりに冗長なところは関数化してもいいですが）。そして、実際に動かしてみて正しく動くことを確認します。実際に 30 日 OS 本では、数百行の HariMain 関数まで育てています。

次に、main 関数の中身を眺めて共通化できそうなところを探して、関数に抽出 します。その時 1 つの関数には 1 つの役割のみを担わせるように注意します。それによって main 関数が読みやすくなります。また、同じ分野の処理は同じファイルにまとめるなどの分割を行うとよりわかりやすくなります。

ここで重要なのはある関数を変更した時に別の分野の関数に影響しないことです。これにより、手戻りが無くなります。正しく役割を分割して関数に抽出できていれば別ファイルの関数群を気にする事なく機能追加を行うことができます。

関数を抽出する時には、カプセル化 して実装の詳細を隠蔽することが重要です。これはよく言われていることですが、Haribote OS のコードを見るとうまく隠蔽されているように思います。一部（ビジュアル系など）は構造体のメンバにアクセスしてしまっているので完全ではないですが、程よく隠蔽されている感じでしょうか。

関数は引数に、コンテキストとなる構造体（コンソール系の処理なら struct CONSOLE など）を 1 つと新しい状態を表すデータを複数受け取ります。コンテキストとなる構造体の中身の操作は関数に隠蔽されます。

また、重要なこととして 最適化は一番最後 に行うということがあります。まず最初は 効率が悪くてもいいのでシンプルで正しく動くコード を実直に実装します。実際、30 日 OS 本では 平気で線形探索 をバンバンします。データ構造とアルゴリズムのへったくれもないです。関数に抽出するなどした後、実際に動かして遅い部分にデータ構造とアルゴリズムを適用して最適化していきます。

ただ写経しているだけでもこれだけのプログラミングの基本を学ぶことができるので、30 日 OS 本はいい本です。

TIPS

あとは、工夫したことや、新しく 30 日 OS 本をやる人へ向けたアドバイスなどを残しておきます。

macOS での開発する時の参考

30 日 OS 本は Windows での開発を前提とされています。完成品となるサンプルコードが本に CD で添付されており、github などでも公開されています。macOS で動かしたリポジトリが以下に公開されており、各チャプターごとのスナップショットがディレクトリわけしてあって、写経に便利なので参考にしていました。

github.com

確か、何かのデータが置かれているアドレスの値が本に書かれている値ではうまく動かなくて、このリポジトリの値を参考にしたらうまくいったということがあったような気がします。どの値だったかは忘れました。

また、専用のコンパイラ（gccベースらしい）やツールなどを揃える必要がありますが、Windows 向けのツールを macOS 向けに移植されたものを利用しているようです。

残念ながらその公開リンクはリンク切れしていましたが、こちらのリポジトリで公開されていました。GitHub - HariboteOS/z_tools_osx

そのソースコードがこちらのリポジトリで公開されていたので、それをコンパイルしてツール群を利用することにしました。GitHub - HariboteOS/tolsrc: Tool set for developing Haribote OS .

しかし、Xcode 10 からは 32 bit 環境向けのコンパイルは Deprecated になっていたため、解決策を調査して報告してプルリクエストを出し、マージしてもらいました。

github.com

30 日 OS 本の最初には 起動イメージバイナリをバイナリエディタでベタ書き するという洗礼があります。これを手打ちするわけですが、バイナリエディタには iHex を利用しました。

CPU が速すぎる

この本が出版された 2006 年当時の CPU で QEMU を動かすことを想定しているため、本の各所で「動かすとカクカクする」といった表現がされています。本の中ではそれを解決するために最適化を行う章が組み込まれています。

しかし、現代の CPU は当時に比べるととても速くなり、また QEMU のソフトウェアとしての品質も上がっているためだと思うのですが、ぶっちゃけカクカクしない という場面がところどころあり、時代の進歩を感じました。

一方で、CPU が速すぎるためにうまくいかなかった ところがあります。途中のタイマーのパフォーマンス計測のあたりだったと思うのですが、for ループの中で何度も io_cli() （割り込み禁止）と io_sti() （割り込み許可）を繰り返し呼び出す部分があります。

この処理の間に別の処理（グラフィックスのメモリ書き込みなど）を行なっている分には問題はないのですが、この 2 つの関数を交互に高速に呼び出すと QEMU が猛烈に遅くなりキーボードやマウスの割り込みをほとんど受け付けなくなります。CPU が速すぎてこの2つの関数呼び出しの数が多くなりすぎたため、逆に QEMU の動作が遅くなってしまうのが意外で面白かったです。

首をいわした

写経は肉体労働です。本を机に広げてその内容をディスプレイを見ながら打ち込んで行くのですが、僕の作業環境はこんな感じでした。

f:id:kawasin73:20190714171935j:plain

本の中身を首を下に向けて読んで、また首をあげてディスプレイをみるということを繰り返していたので、おかげさまで首をいわしました。プログラマの職業病です。

最初から、左の画面にサンプルコードを表示して、正面のディスプレイに写経することをすれば首の移動は左右だったので負担も少なかったのではないかと後悔しています。皆さんも気をつけてください。

  1. macOS で動かす C コンパイラを C で作った - kawasin73のブログ↩

  2. DMM を卒業しました - kawasin73のブログ↩

Twitter をフィルタリングする Twilter を作った

Go 作ったもの

あなたとわたしと Twitter。どうも、かわしんです。

今週の頭の日曜月曜火曜の 3 日間かけて Twilter というコマンド（？）サービス（？）を作ったので、その紹介をしたいと思います。

Github リポジトリはこちらです。star をつけていただけると喜びます。

また、良かったらご自身で運用してみてください。

github.com

なぜ Twilter を作ったのか

僕のツイッターライフ

僕は Twitter を情報収集と娯楽のために利用していますが、僕の性格として全ての情報を把握しておきたいため、フォローしている人の全てのツイートを読んでいます。

残念ながら Twitter の公式アプリは、勝手にツイートの順番を入れ替えたり、勝手にオススメのツイートだけをフィルタリングして上に表示したり、時間が経ってアプリを開くと勝手にスクロール位置を最新のツイートに変えてしまったりします。

余計なお世話にも程があります。僕はタイムラインの全てのツイートを確認したいのに勝手にスクロール位置やツイートの順番を変えられると、どこまで確認していたかがわからなくなってしまいます。

そこで、僕は Tweetbot という iOS アプリを利用してタイムラインの購読をしています。

Tweetbot 5 for Twitter

Tweetbot 5 for Twitter

このアプリは有料アプリですが、タイムラインの順番やスクロール位置を勝手に変えることはしません。また、複数の iOS デバイス間でスクロール位置を同期してくれるので、家で iPad で読んで通学途中で iPhone で読むみたいな場合でもシームレスにタイムラインの確認ができます。さらに、キャッシュなどの最適化を行なっているため通信状況が悪くてもツイートの確認ができるのもいいところです。

僕みたいな異常な完璧主義の方にオススメのアプリです。

さて、全てのツイートの監視をしている僕ですが時間は有限であるため、ツイートが増えるスピードがツイートを読むスピードを超えてしまうと未読のツイートが無限に増えてしまいます。

そのため、ツイート数とその人が垂れ流す情報の有用さのバランスを元にフォローしている人を定期的に整理して、ツイートの流速調整を行っていました。

今は 100 フォロー以下を目安にやっていますが、割ときつくて、70 ~ 80 フォローくらいがちょうどいい流速なのではないかと思っています。

迎える限界

そんなツイッターライフを送っていた僕ですが、ある日僕のルールの限界を感じさせるユーザーに出会います。

重曹 さんです。この方の代表作はこれです。死ぬほど面白い。複数のツイートに分割されているのでリプライを辿っていってください。

「なかのやま」さん「NZK」さん「重曹」さんのセンスの塊の３名で構成される LINE グループのチャット内容を時々ツイートされるのですが、これが死ぬほど面白いのでフォローして LINE チャット画面を楽しみにしていました。

しかし、重曹さんの毎日のツイート数はかなり多く、僕のタイムラインが爆発してしまいました。LINE グループのツイートの数に比べてその他のツイートが多すぎるため僕のルールではフォローを外すしかないのですが、どうしてもこのセンスあふれる LINE グループの画像は見たいという板挟みの状態になってしまいました。

その時の僕の心の叫びがこれです。

ということで、Twilter を作ることにしました。

Twilter とは何か

Twilter は Twi t ter を F ilter してくれるサービスです。安直な名前なのですでに Twilter という名前のアプリは色々あるようです。しかし、それらはブラウザのエクステンションでツイッターのウェブサイトで表示を消す程度のことしかしてくれないようなので、自分で Twilter を作ることにしました。

機能としては以下の通りです。

  • 特定のユーザーのツイートを定期的に確認し、
  • 設定された条件にマッチするツイートをフィルタリングし、
  • そのツイートを連携している Twitterアカウントでリツイートする

というものです。その連携している Twitter アカウントだけを自分の Twitter アカウントからフォローすれば、フィルタリングされたツイートを自分のアカウントのタイムラインで確認することができます。

こんな形で使います。この設定では、重曹さんのリツイートでないオリジナルの画像ツイートのみをフィルタリングします。

$ export TWITTER_CONSUMER_KEY=xxxxxxxxxxxxxxxxxx
$ export TWITTER_CONSUMER_SECRET=xxxxxxxxxxxxxxxxxx
$ export TWITTER_ACCESS_TOKEN=xxxxxxxxxxxxxxxxxx
$ export TWITTER_ACCESS_TOKEN_SECRET=xxxxxxxxxxxxxxxxxx
$ export REDIS_URL=redis://user:password@host_name:6379

$ twilter -target "YTmoyashifes:and(photo,not(rt))"

このコマンド自体はフォアグラウンドで動きますので、デーモン化は docker や systemd などで行なってください。

docker イメージは https://hub.docker.com/r/kawasin73/twilter で公開しています。

注意事項

まず注意事項を記載しておきますが、リツイートを行うアカウントは 鍵アカウント（Private Account）にすることを強く推奨します。

相手ユーザーに多くのリツイートによる通知が表示されて迷惑になってしまうことを防ぐためです。鍵アカウントであれば相手ユーザーはリツイートされたことがわかりません。

また、監視できる対象ユーザーはツイートをリツイート可能なパブリックアカウントのみです。鍵アカウントは対象外ですので注意してください。

オプション一覧

オプションはこんな感じになっています。

$ twilter -h
Usage of /usr/local/bin/twilter:
  -fallback int
        start filtering tweets fallback minutes ago if no checkpoint (minutes) (default 10)
  -interval int
        interval between monitoring (minutes) (default 10)
  -target value
        list of targets. target format = "<screen_name>:<filter>[/<filter>]"  filter format = "<filter_name>[(<attribute>[,<attribute>])]"
  -timeout int
        timeout for each monitoring + retweet loop (minutes) (default 5)

本当は設定ファイルから読み込めたら便利なんですが、Docker で運用する場合に面倒になるのと、ファイルフォーマットの策定など諸々めんどくさかったので対応していません。

フィルターについて

フィルタ設定は、target オプションによって設定します。複数の target を設定することもできます。

target は <twitter_id>:<filter>[/<filter>[/...]] のフォーマットで指定します。フィルターは / によって区切ることで複数設定できます。（本当は | で区切りたかったけど、シェルのパイプと認識されてしまうため / にしました）

これらのフィルターのうち１つでもマッチするものがあればリツイートされます。

フィルターは以下の種類があります。

  • rt : リツイートされているツイート
  • qt : 引用リツイートされているツイート
  • photo : 画像付きツイート
  • video : 動画付きツイート
  • not(<filter>) : 引数のフィルターにマッチしないツイート
  • and(<filter>[,<filter>[,...]]) : 引数のフィルターの全てにマッチするツイート
  • or(<filter>[,<filter>[,...]]) : 引数のフィルターのどれか１つでもマッチするツイート

まだ実装していませんが、特定のキーワードやハッシュタグを含むツイートのフィルターも作る予定です。

ここで特に特徴的なのは、最後の not、 and、 or フィルターの 3 つだと思っています。

この3つのフィルターを組み合わせることで比較的柔軟に色々な種類のフィルターを定義することができます。また、提供するフィルターの種類もプリミティブなものだけで済むので実装コストも抑えられるのもいいところです。

Redis との連携

Twilter はデフォルトでは起動時刻から fallback に設定された分だけ前のツイートからフィルタリングを始めます。これは再起動した場合に停止していた間のツイートを取りこぼさないためです。

Twilter はオプション機能として、Redis を用意して環境変数の REDIS_URL に接続情報を登録するとツイートの確認状況を Redis に保存します。再起動した場合は Redis に保存されているツイートより後のツイートからフィルタリングを始めます。これにより無駄にフィルタリングをせずに済みます。

Redis との連携機能はオプション機能なので、 Redis がなくても Twilter を利用することができます。

Rate Limit

Twitter にはリクエスト数の Rate Limit があり一定時間にできる API リクエストの数が決まっています。

Twilter ではリクエスト数制限に引っかかった場合でも自動で適切な時間待って再送する 再送処理を実装 していますが、これは一時的にバーストした場合のためのものなのであらかじめ適切にリクエスト数の見積もりと設定をする必要があります。

ユーザーごとのツイート一覧を取得する API のリクエスト数制限は 900 requests / 15 minutes の制限と、 2019 年 6 月 19 日からは 100,000 requests / day の制限があります。

GET statuses/user_timeline — Twitter Developers

Twilter では Twitter アカウントを監視する間隔を interval オプションで指定できます。デフォルトは 10 分になっています。単位は minute です。

ユーザーのツイート一覧取得は、1 回のリクエストあたり最大 200 ツイートを取得できるので、各自それに合わせて interval の値を設定してください。

また、リツイート投稿 API のリクエスト数制限は 300 requests / 3 hours です。リツイート投稿が多くならないようにユーザーの選定とフィルターの中身を設定してください。

POST statuses/retweet/:id — Twitter Developers

アクセストークンについて

Twitter のアクセストークンを取得するには開発者アカウントが必要です。

Twitter は気づいたら開発者アカウントを取得するために 200 字の作文を複数箇所行わなければならないようになってしまっていて、ハードルが上がっていて悲しいです。が、背に腹は変えられないので頑張って英語作文しましょう。

多分、インストール手順の中で Twitter の開発者アカウントを作成するのが一番難しいステップ です。本当に悲しい。

取得したアクセストークンは、TWITTER_CONSUMER_KEY TWITTER_CONSUMER_SECRET TWITTER_ACCESS_TOKEN TWITTER_ACCESS_TOKEN_SECRET の環境変数に設定して利用します。

TWITTER_CONSUMER_KEY と TWITTER_CONSUMER_SECRET には開発者アカウントの Consumer Key と Secret を登録してください。

TWITTER_ACCESS_TOKEN と TWITTER_ACCESS_TOKEN_SECRET には、開発者アカウントから発行されたリツイートを行う鍵アカウントの Access Token と Secret を登録してください。

多くの場合は開発者アカウントの Twitter アカウントとリツイートを行う Twitter アカウントは 別のもの を使うと思います。その場合はダッシュボードから TWITTER_ACCESS_TOKEN と TWITTER_ACCESS_TOKEN_SECRET を生成することができません。

twitter-auth というコマンドラインツールがアクセストークンの発行を簡単に行なってくれるため、利用することを推奨します。

github.com

最後に

と、まぁ、こんな感じです。

Twilter は自宅の kubernetes on Mac mini サーバーで運用しています。じわざわリツイートがタイムラインに流れてくるのを「ちゃんと動いているぞ」と思いながら眺めています。

情報をうまくフィルタリングして時間を有効活用できるようになりました。

Twilter では定期的にツイッターを監視するタスクスケジューリングの部分に一年前に 管理上手のうさちゃん を作った時に作ったタスクスケジューラ htask を使っています。

github.com

うまく汎用的なライブラリを再利用できて、ニヤニヤしてます。

では、良い Twitter ライフを !

Go Conference 2019 Spring で登壇しました

Go 参加記

困った時はドキュメント、どうもかわしんです。

去る 2019 年 5 月 18 日に開催された Go Conference 2019 Spring に LT 枠で登壇してきました。

数百人規模のカンファレンスで登壇するのは初めてだったのでいい経験になりました。ありがとうございました。

題名は「俺はビッグエンディアンでテストがしたいんだ！！！」ということで発表してきました。資料はこれです。

このブログの最初の記事である 俺はビッグエンディアンでテストがしたいんだ！！！ - kawasin73のブログ の内容を LT 向けに圧縮しています。

LT は発表時間が 5 分しかないので内容を削ったりしたのですが、実際の発表では早口すぎて 4 分 10 秒で完走してしまいました。

それだったらもうちょっと話すことがあったので反省点です。

Twitter でいろんな反応をいただいて嬉しいです。

最後に僕の自己満ですが、ツイートをたくさん引用して筆を置きたいと思います。

DMM を卒業しました

参加記 ポエム

初春の令月にして、気淑く風和らぎ、梅は鏡前の粉を披き、蘭は珮後の香を薫らす 1。どうもかわしんです。新しい元号、令和の 3 日目です。頑張っていきましょう。

さて、去る平成の 31 年 4 月 25 日にインターンしていた DMM を卒業しました。1 年と 11 ヶ月でした。

簡単にいえばこれはその退職エントリーです。

DMM に行くまでの経緯

2017 年の 3 月に起業していた会社を辞めることにし、休学していた大学に復学するまで半年ほど時間があったので新しいインターン先を探していました。

それまでの 2 年間は、 Web フロントエンドや、Rails を使ったバックエンド、iOS アプリ、Android アプリなど主にアプリケーションレイヤーのエンジニアをしていました。

しかし、プログラミング技術のコモディティ化とプログラミング人口の増加する未来に危機感を覚えて 2 、技術力に特化するためにミドルウェアやライブラリを作成するエンジニアインターンを探していました。

そこで、偶然参加した DMM が主催した勉強会の懇親会で当時人事だった星野さんとこの話をお話ししてインターン先を探していることを伝えると、DMM でできるかもしれないということで話が進み、DMM の CTO 室で 6 月からインターンをすることになりました。

どうやら、当時はパブリックにインターンの募集はしていなかったらしく、僕が DMM のエンジニアインターン第一号だったらしいです。

やってたこと

CTO 室では @mah0x211 さんに僕のメンターになっていただき、2 年弱ほとんどつきっきりで僕のメンタリングをしていただきました。

やったことは大きく以下の 3 つです。2 年もいてそこまで大きな成果が出せていないのが恥ずかしいです。

  • Lua で実装された KVS を Go に移植する

メンターさんが数年前に実装していたハイパフォーマンス KVS を Go に移植することをしました。実装は僕 1 人で行い、レビューや相談をメンターさんにお願いしていました。

ここで、システムコールなど様々な基礎的なプログラミングを学びました。 最後のベンチマークを計測したりするあたりが結構辛かったです。

  • データベースの分散ルータの設計

上で実装した KVS を分散環境で使えるようにするためのルーターの実装と設計を行いました。

途中で設計をやり直して、メンターさんとホワイトボードを使いながら詰めていく形で設計をしていました。 しかし、僕の技術力不足で残念ながら設計を最後まで完成させることができませんでした。

  • ログ転送エージェント

これは、メンターさんがメインで開発しているプロダクトの一部のタスクを僕が調査したり実装したりする形式で進めました。

僕のコードや設計に細かく丁寧にレビューをしていただき、この時が一番成長したと思います。

メンターさんから学んだこと

2年間 @mah0x211 さんにとてもお世話になり、たくさんのことを学びました。

今までの自分のプログラミングはプログラミングではなかった と感じるレベルで成長して変わることができました。

エンジニアリングに対する姿勢

まず、「ないものは自分で作る」という姿勢を学びました。

それまでの僕は、まずライブラリを探してそれを組み合わせてアプリケーションを作るイメージでした。完全に仕様を満たさないものや過多な機能を提供するライブラリであっても、作るアプリの仕様をそのライブラリに合わせて変えるなど工夫して使うようにしていました。仕様がライブラリに依存してしまっていたのです。

そうではなく、もし仕様に合致するライブラリがない場合はそれを自分で作ってプロダクトに組み込む考え方とそれを達成する技術力を学びました。

また、依存ライブラリの増大はその分だけプロダクトの保守性や品質を下げる可能性があります。プロダクトに必要のない機能がライブラリに含まれることで実行環境（実行バイナリや VM の大きさ）の肥大化や低速化に繋がったり、ライブラリのアップデートに追従する労力が発生してしまいます。

そのコストとライブラリを利用することによるメリットのトレードオフを考えてライブラリ利用か自分で実装するかの意思決定をする必要があることを学びました。

次に、「なんとなくで意思決定しない」という当たり前と言えば当たり前な考え方を学びました。

どのライブラリやミドルウェアを採用するかを「周りでよく使われているから」や「今日本で流行っているから」という曖昧な理由で決めるのではなく、ドキュメントを読んだり実際に試したりして調査することの大切さを学びました。

特に、それらの情報は一次情報である公式ドキュメントを当たる必要があり、英語を読む力も（読むのは遅いですが）身につきました。 また、ドキュメントだけで理解できない場合はソースコードを読んで理解することを徹底することも学びました。

この姿勢はプログラミングの中でも必要です。外部ライブラリやシステムコールが何を返すのか、発生しうるエラーは何か全て理解した上で実装する必要があります。

特にミドルウェアの実装では、起動されてから数年単位で稼働し続けることが求められ、多少のエラーで異常終了することは許されません。全てのエラーをハンドリングするためには全てのエラーを理解する必要があります。例えば、システムコールのドキュメントとして man page をよく読むようになりました。

プログラミングの基礎

プログラミングではまず「設計が大切」であることを学びました。

大きなプロダクトを作る上では、全てのコンポーネント同士の関係を絵に描いて説明できるレベルまで設計を詰めておく必要があります。 絵が複雑になったりする場合はその設計は不十分であることが自然と浮き上がってきます。

実装を始める前に設計をしっかり固めてからでないと手戻りが発生しやすくなってしまいます。

設計は「シンプルな実装を積み上げていく」ことが大切です。

設計では神の目になったつもり大雑把な動きを捉え、その流れに対してデータ構造やアルゴリズムを適用します。最初から複雑に考えるのではなく、一番小さな単位から設計を始めて、それに肉付けしていく形で仕様を満たす設計を作り上げていきます。そのためにも極力シンプルな設計を心がけなければなりません。そのほうがあとで肉付けをしやすくなります。

また、「コンポーネントとビジネスロジックを分離する」ことを意識することも大切です。まず、ビジネスロジックに依存しない足回りとなるコンポーネントを実装し、そのコンポーネントのインターフェイスを組み合わせることでビジネスロジックを組み上げていきます。

コンポーネントがビジネスロジックに依存しないことで、ビジネスロジックの修正はコンポーネントの組み合わせ方を変えるだけで対応でき、コンポーネントの修正は必要なくなるため堅牢なソフトウェアになります。また、汎用化されたコンポーネントはライブラリとして切り出すこともできます。

「データ構造とアルゴリズムは筋肉」です。様々なデータ構造とアルゴリズムを知っていることで最適なデータ構造とアルゴリズムを導入することができ、パフォーマンスの良いミドルウェアを作ることができます。AtCoder で競技プログラミングを始めて勉強するきっかけになりました。

コーディングでは、「読みやすくシンプルなコーディング」の大切さを学びました。関数の中でもサブロジックごとにコードをまとめてコメントをつけることで読みやすくなります。例としては、boltdb の作者である Ben Johnson さんのコードは、サブロジックごとに改行で区切られてコメントが付与されており、とても読みやすいです 3 。

ドキュメンテーションの基礎

ドキュメンテーションでは「読者が上から下に引っかかりなく読むことができる」ような書き方をする姿勢を学びました。上から読んですっと読者の中に内容が入るための、前提条件や因果関係を上から順番に書いたり、表記を統一してブレないようにしたり、重複しないようにしたり、読者が疑問に思うようなことはその場で補足したりするなどの書き方を学びました。

また、僕のドキュメントの癖として英語を多用してしまう「ルー語病」がありました。英語をなるべく日本語に翻訳して書くように意識するようになりました。

あと僕のブログなどの書き物で、数字や英単語の前後にスペースが空いているのは読みやすくするメンターさんの書き方の影響です。

まとめと今後

ここまで学んだことを雑多にまとめましたが、本当に DMM で @mah0x211 さんの下で学べてよかったです。多分 DMM に行っていなかったら今の僕はありません。本当に感謝しています。

そして、来年の 4 月からは GAFA の G 社に新卒で就職する予定です。ホワイトボードでの説明やお絵かきの方法や普段の会話の中での知識などDMM で学んだことが入社面接でとても役立ちました。これで気になった人は DMM の夏のインターンもあるみたいなので是非参加してみてください。

今は大学 4 年生なのでこれから 1 年間は大学の研究に専念することになります。趣味のプロジェクトなどもできたらいいなと考えています。今後ともよろしくお願いします。

  1. 新元号は「令和」 出典は「万葉集」｜NHK NEWS WEB↩

  2. 詳しくは、作る人と使う人 - kawasin73のブログ というポエムにまとめています↩

  3. 例: bolt/db.go at fd01fc79c553a8e99d512a07e8e0c63d4a3ccfc5 · boltdb/bolt · GitHub↩

Go 言語でタイムアウト付きのファイルロックを実現する

作ったもの Go

言語の壁をぶっ壊す。どうも、かわしんです。

プロセス間の待ち合わせの手法としてファイルロックがあります。このファイルロックをタイムアウトでキャンセルすることを可能にするために以下のライブラリを作ったのでその解説をしたいと思います。

github.com

対象

今回の対象は以下の環境とします

ファイルロックを実現するシステムコール

Linux では、fcntl と flock というシステムコールでファイルロックができます。

この 2 つで獲得されるロックはカーネル内では別のものとして扱われますが、 FLOCK の 注意 にもある通り、一部のシステムでは flock と fcntl が影響を与える可能性があるため、単一のプログラムの中ではどちらかのロックのみを使うようにした方が良さそうです。（プログラムの複雑性も軽減されます）

今回の話は、fcntl と flock のどちらでも共通の話なので、fcntl を使ってデモを行います。

FCNTL

fcntl は、ファイルディスクリプタを操作するシステムコールです。

Man page of FCNTL

#include <unistd.h>
#include <fcntl.h>

int fcntl(int fd, int cmd, ... /* arg */ );

以下のコマンドを指定して、引数に flock 構造体を渡すとファイルロックができます。

ロックはファイルのバイト単位で範囲を指定してロックします。

基本はアドバイザリーロックで、頑張ると強制ロックも可能です。

これらは POSIX で標準化されています。

  • F_SETLK : ロックの獲得をノンブロッキングで行います。ロックの獲得に失敗した場合は EACCES または EAGAIN エラーが返ります。
  • F_SETLKW : ロックの獲得を行います。ロックの獲得に失敗した場合はロックの獲得ができるまで処理をブロックします。
  • F_GETLK : ロックの情報を取得します。

ロックの種類は F_RDLCK と F_WRLCK があり flock 構造体で指定します。go でいう sync.RWMutex みたいな感じですね。F_UNLCK を指定するとロックを解除します。

FLOCK

次に flock は、名前の通りファイルをロックするシステムコールです。

Man page of FLOCK

flock は BSD 系由来のシステムコールで POSIX には含まれませんが、シンプルなインターフェイスです。

ロックの範囲はファイル全体のみで、fcntl のように特定の範囲のみをロックすることはできません。

ロックはアドバイザリーロックになります。

#include <sys/file.h>

int flock(int fd, int operation);

operation に以下のオペレーションを指定してファイルをロックします。

  • LOCK_SH : 共有ロック。fcntl でいう F_RDLCK みたいな
  • LOCK_EX : 排他ロック。fcntl でいう F_WRLCK みたいな
  • LOCK_UN : ロックの解除

また、operation に論理和で LOCK_NB を指定するとノンブロッキングでロックを獲得し、指定しない場合はロックを獲得できるまで処理をブロックします。

Go 言語におけるファイルロック

Go では syscall パッケージに syscall.FcntlFlock() と syscall.Flock() が用意されています。

// fcntl のインターフェイス
func FcntlFlock(fd uintptr, cmd int, lk *Flock_t) error

// flock のインターフェイス
func Flock(fd int, how int) (err error)

これらはあくまでもシステムコールをラップしただけのものなのでタイムアウトの機能を追加する必要があります。

github で file lock でタイムアウト付きのファイルロックの Go の実装を調べていると以下の2つのライブラリを探すことができました。

github.com/gofrs/flock

GitHub - gofrs/flock: Thread-safe file locking library in Go (originally github.com/theckman/go-flock)

gofrs/flock には、TryLockContext というメソッドがあり context.Context を利用してタイムアウトやロックの中断を実現できます。

func (f *Flock) TryLockContext(ctx context.Context, retryDelay time.Duration) (bool, error)

しかし、その内部実装は syscall.Flock をノンブロッキングモードで呼び出し、成功するまで for 文で retryDelay で設定された間隔で呼び出し続けるものになっています。

これでは、カーネル内部のロックキュー に入らないため、 複数プロセス間のロックの順序が崩れてしまいます 。(参考 : linux - flock locking order? - Stack Overflow)

また、ロックの獲得まで 最大で retryDelay の分の遅延が発生する ことになります。

github.com/jviney/go-filelock

GitHub - jviney/go-filelock

jviney/go-filelock では、Obtain 関数にタイムアウトの時間を渡してタイムアウト付きのファイルロックができます。

func Obtain(path string, timeout time.Duration) (lock *Lock)

しかし、その内部実装は syscall.Flock をブロッキングモードで実行する goroutine を立ち上げて、その終了とタイムアウトを Obtain 関数内で select 文で待つものでした。

タイムアウトするとさらに新しい goroutine を立ち上げ、その goroutine 内でロックが獲得できるまで待って即座にロックを開放するようにしています。

      // We hit the timeout without successfully getting the lock.
      // The goroutine blocked on syscall.Flock() is still running
      // and will eventually return at some point in the future.
      // If the lock is eventually obtained, it needs to be released.
      go func() {
        if err := <- flockChan; err == nil {
          releaseFlock(file)
        }
      }()

https://github.com/jviney/go-filelock/blob/ec38a70cdf163d7c9f50a224f4c422f8a1847d7a/filelock.go#L48-L56

ロックが獲得できなかった場合、 ロック開放用とロックを取得する 2 つの goroutine が残り続けます 。

また、ロックを獲得中のファイルディスクリプタを閉じるとロックが獲得するまでブロックします。 ファイルディスクリプタを解放することができない ためファイルディスクリプタも残り続けます。

これではリソース管理の面からガバガバです。

どうやってファイルロックを中断するか

上の 2 つのライブラリはファイルロックの直接的な中断ができなかったためにこのような課題が残っていました。

この点を解決するために、ここでどうやってブロックしているファイルロックを中断するかを考える必要があります。

答えは シグナル です。

ブロッキングするシステムコールはシグナルを受信することによってブロックが解除され EINTR エラーを返すようになっています。（タイムアウトという文脈では alarm を使うことが多そうです）

Timeouts for system calls are done with signals. Most blocking system calls return with EINTR when a signal happens, so you can use alarm to implement timeouts.

https://stackoverflow.com/questions/5255220/fcntl-flock-how-to-implement-a-timeout#answer-5255473

そのためシグナルを送信してロック獲得処理に EINTR を発生させることでファイルロックのタイムアウトや中断を実現できます。

シグナルによる割り込みを Go でも実現させる

シグナルを自分のプロセスに送れば解決するはずなのですが、Go では以下の 2 つの障壁があります。

  • SA_RESTART によって EINTR がそもそも発生しない
  • シグナルを pthread_kill 使って送信しないといけない

それぞれ順をおって解説します。

SA_RESTART によって EINTR がそもそも発生しない

SA_RESTART は sigaction に設定するフラグで、このフラグが設定されると、ブロッキングしているシステムコールがシグナルによって中断された場合でも EINTR を返さずにブロッキングを続行するようになります。

参考 : シグナルハンドラーによるシステムコールやライブラリ関数への割り込み

Go ではランタイムによって全てのシグナルに対して SA_RESTART が設定されています。これにより標準ライブラリは EINTR のエラーハンドリングをしなくてよくなります。（確かに標準ライブラリを読んでいると EINTR のハンドリングをしていないことに気づきます）

Also, the Go standard library expects that any signal handlers will use the SA_RESTART flag. Failing to do so may cause some library calls to return "interrupted system call" errors.

https://golang.org/pkg/os/signal/#hdr-Go_programs_that_use_cgo_or_SWIG

これは Go のランタイムの問題なのでどうしようもありません。Go 言語のレイヤーでは解決できません。

ここで、「 言語の壁をぶっ壊す 」CGO の出番です。Go 言語を壊していきます。

CGO によって直接 C 言語で sigaction を実行しシグナルハンドラを設定することで Go のランタイムが設定した SA_RESTART を上書きします。

この時点で Windows とかの可搬性は捨ててます。すみません。

void sighandler(int sig){
    // empty handler
}
static struct sigaction oact;

static int setup_signal(int sig) {
    struct sigaction act;
    // setup sigaction
    act.sa_handler = sighandler;
    act.sa_flags = 0;
    sigemptyset(&act.sa_mask);
    // set sigaction and cache old sigaction to oact
    if(sigaction(sig, &act, &oact) != 0){
        return errno;
    }
    return 0;
}

シグナルを pthread_kill 使って送信しないといけない

さて、SA_RESTART を上書きした上で自身のプロセスにシグナルを送るとブロッキングしているファイルロックを中断できる場合とできない場合が出てきます。

それは、事前に signal パッケージの signal.Ignore() や signal.Notify() などを呼び出した時です。

これらのメソッドを呼び出した時に Go のランタイムは signal mask thread を立ち上げそのスレッドが全ての sigaction の登録を行います。(具体的には ensureSigM という関数)

go/signal_unix.go at 2c5363d9c1cf51457d6d2466a63e6576e80327f8 · golang/go · GitHub

これによって プロセススコープに送られたシグナル はランタイムの signal mask thread に送られてしまいます。その場合は別のスレッドでファイルロックをブロックしているためシグナルが届かず EINTR も発生しません。

この解決策は スレッドスコープでシグナルを送る ことです。

残念ながら Go 言語は OS のスレッド意識させないような作りになっており、スレッドに対して直接シグナルを送ることはできません。

そこで、「 言語の壁をぶっ壊す 」CGO の出番です。どんどん Go 言語を壊していきます。

C では、pthread_kill という関数があり特定のスレッドにシグナルを送ることができます。

static pthread_t tid;

static int setup_signal(int sig) {
    ...
    // set self thread id
    tid = pthread_self();
    ...
}

static int kill_thread(int sig) {
    // send signal to thread
    if (pthread_kill(tid, sig) == -1) {
        return errno;
    }
    return 0;
}

これでブロックしているファイルロックを中断させることができるようになりました。

github.com/kawasin73/gointr を作った

これまでの知見を元にブロッキングしている処理を中断させる処理をライブラリ化しました。

github.com

使い方としては

  1. 中断に使うシグナルを指定して gointr.Intruptter を作成する (gointr.New(syscall.SIGUSR1))
  2. ブロッキングする処理を行う goroutine を立ち上げて intr.Setup() を実行してから、ブロッキング処理を行う
  3. ブロッキング処理が終わったら intr.Close() する
  4. もし、中断する場合は intr.Signal() を呼び出す

となります。中断された場合は EINTR がブロッキングするシステムコールから返ってきます。

注意点

注意点としては、以下のことが挙げられます。気をつけてください。

  • グローバル変数を内部で使っているため 複数のブロッキング処理の中断に対応していない
  • signal パッケージの関数を呼び出すと上書きした sigaction が上書きされ直されるので ブロッキング処理中は signal パッケージの関数を呼んではいけない
  • CGO を使っている

Example

package main

import (
    "fmt"
    "io"
    "log"
    "os"
    "os/signal"
    "syscall"
    "time"

    "github.com/kawasin73/gointr"
)

// lock locks file using FCNTL.
func lock(file *os.File) error {
    // write lock whole file
    flock := syscall.Flock_t{
        Start:  0,
        Len:    0,
        Type:   syscall.F_WRLCK,
        Whence: io.SeekStart,
    }

    if err := syscall.FcntlFlock(file.Fd(), syscall.F_SETLKW, &flock); err != nil {
        // FCNTL returns EINTR if interrupted by signal on blocking mode
        if err == syscall.EINTR {
            return fmt.Errorf("file lock timeout for %q", file.Name())
        }
        return &os.PathError{Op: "fcntl", Path: file.Name(), Err: err}
    }
    return nil
}

func main() {
    signal.Ignore()

    file, err := os.Create("./.lock")
    if err != nil {
        log.Panic(err)
    }

    // init pthread
    intr := gointr.New(syscall.SIGUSR1)

    // init error channel
    chErr := make(chan error, 1)

    // setup timer
    timer := time.NewTimer(3 * time.Second)

    go func() {
        // setup the thread signal settings
        if terr := intr.Setup(); terr != nil {
            chErr <- terr
            return
        }
        defer func() {
            // reset signal settings
            if terr := intr.Close(); terr != nil {
                // if failed to reset sigaction, go runtime will be broken.
                // terr occurs on C memory error which does not happen.
                panic(terr)
            }
        }()
        // lock file blocking
        chErr <- lock(file)
    }()

    for {
        select {
        case err = <-chErr:
            timer.Stop()
            if err == nil {
                log.Println("lock success")
            } else {
                log.Println("lock fail err", err)
            }
            // break loop
            return

        case <-timer.C:
            log.Println("timeout")

            // send signal to the thread locking file and unblock the lock with EINTR
            err := intr.Signal()
            log.Println("signal")
            if err != nil {
                log.Panic("failed to kill thread", err)
            }
            // wait for lock result from chErr
        }
    }
}

最後に

以上です。ありがとうございました。

ぶっちゃけ、ここまで厳密にするなら Go を使わなくていいと思うし、多分自分が使うとしたら github.com/gofrs/flock を使う。

未踏 Demo Day に行ってきた

参加記

ビールは 1 日 4 缶まで。どうもかわしんです。

2018 年度の未踏プロジェクトの Demo Day という名の成果発表会が秋葉原で 2/16 と 2/17 の2日間に渡って行われ、中高の同級生が未踏プロジェクトに採択されて発表するというので聞いてきました。

MITOU2018 Demo Day／2018年度（第25回）未踏IT人材発掘・育成事業 成果報告会 開催のご案内：IPA 独立行政法人 情報処理推進機構

懇親会でビールを 3 杯飲んで、家に帰ってからも感動が冷めやまず今ビールを 1 缶飲みながらこの記事を書いてます。

全体的な印象

話を聴きながら思ったことは、さすが未踏ということだけあって技術的にさらにもう一歩深掘りしているものが多かったということです。

テーマを聞いて僕なりにだいたいこんなことをするんだろうなということが考えつくのですが、そこまでは当たり前のように開発した上で、さらにもうひと押しして新しい機能を技術的課題を突破して開発し、システムの利便性を上げて報告会に望んでいるという印象を受けました。

なので、毎回期待を上回るものが聞けてワクワクしながら発表を聞くことができました。

また、そのもうひと押しというのはだいたい機械学習や遺伝的アルゴリズムなどで解決していることが多かったです。

僕は流行りに惑わされることが嫌だったので機械学習はやらないと、あえて決めてシステム開発に振ってエンジニアをやってきましたが、アプリケーションをもうひと押し使いやすくするためのツールとして機械学習を入れ込むことが必要になってきているのではないかと感じさせられました。

面白かった発表

特に印象に残ったのは以下の発表です。

AI 実況プレイ動画生成の発表は、プレゼンテーションのクオリティが常軌を逸していました。

プレゼンはエンターテイメントショーだということをマジマジと見せつけられました。

僕はスティーブ・ジョブスとかのプレゼンが好きでその演出とかに感動してしまうタイプなのですが、完全にエンターテイメントとしてストーリーを構成されている上に、そのプレゼンを死ぬほど練習したんだろうなということがうかがえるくらい完璧なプレゼンでした。

プレゼンのストーリーに必要のない過多な情報は全て切り捨て、質疑応答に回すという大胆な方法で、圧倒的わかりやすさとストーリーの没入感を演出していました。

このプレゼンは、もう一度観たいと思うほど感動した発表でした。

また、研究の内容もマリオカートの実況動画を作るためのステップを３つに分割して、それぞれのステップの課題を解決するための技術開発を行なっていてものすごいクオリティでした。 それぞれのステップが 1 つプロダクトになるレベルのことをやっていました。

面白かったです。

これはシンプルにプロダクトの完成度とそのプロダクトによる世界への影響度が半端ないと感じました。

数文字の文字のフォントを作ることによって最大 34 万字のフォントを自動生成するのは誰でもフォントを作ることができるため革新的です。 フォント生成をサーバーサイドではなくここのブラウザ上で行うことでサーバーコストを抑えることができるという有益な特徴を持っています。

また、デモやプロモーションの動画がとてもワクワクさせられました。

これが 2 日間で一番興奮した発表です。

発表の動画のビジュアルの完成度は圧倒的で、プレゼンの構成やスライドの作り方などもすごく考えられているんだろうなと伝わりました。

3D プリンターに印刷以上の機能を持たせるという既存の固定概念をぶっ壊して 3D プリンタを再発明するというテーマで、おそらく世界で誰もやっていないだろうことをやっており、新しい未来を作るんだという心意気が伝わってきました。

しかし研究の内容はテーマの鮮やかな感じとは打って変わって、解決したい大きな目標に達するまでに発生する課題を一つ一つ地道に潰しながら次のステップに進み、また課題を潰して次のステップに進み、という泥臭さがあり、発表の鮮やかさ、テーマの鮮やかさの中からもその泥臭さが伝わってきて、この1年という時間を妥協せずにこの研究に費やしてきたんだなと感動しました。

てか、1.5mm ~ 2.3mm という絶妙な数値なんだよ。その1つ1つのステップでレベルで試行錯誤してるのかよ。どんだけ時間がかかるんだ。

まさに努力の結晶という言葉がぴったりなプロダクトでドン引きしました。

人型ロボットを小学生から作り続けている高校生 2 人による発表でした。手作りのロボットのモーションを初心者でも簡単に作れるようにするアプリケーションでした。

これはもうひと押しどころか、もうふた押しくらいあるような深みのある研究でした。

ロボットのモーションを GUI で作れるようになるためのプラグインの開発を終えた後に、シミュレータのモデルと現実のモデルの重さや重心を合わせるために、ロボットを分解することなく各パーツの重さや長さを様々なポーズをさせた時の重心の位置の違いによって計測するというシステムを開発し（ひと押し目）、さらに GUI で作ったモーション（例えば二足歩行）が作成者の意図通りになるように遺伝的アルゴリズムを使ってシミュレーションして自動的に最適化させる（ふた押し目）というものでした。

ユーザーが求めているのはモーションを簡単に作ることだけではなく、自分が求めている動きによって機能が達成されることですが、とことんまでユーザーに求められるものを追求し、それに必要な技術的な課題を突破していく様は鮮やかですらありました。 僕は発表を聞いていて声が漏れました。

これらの他にも面白い発表ばかりでしたが、そろそろ眠いのでこのくらいにします。

また、発表の内容は後々 IPA の youtube で公開されるそうなので見てみてください。

発表でとったメモ

以下は、発表でとったメモです。両日とも遅刻していったので最初の発表のメモは薄いです。

また、メモの内容が薄い部分は僕がその発表に集中しすぎてメモを取ることを忘れてしまっているのでご容赦ください。

1 日目

タブ分類ブラウザ

氾濫するタブ一覧を自動で整理するモバイルブラウザ

モバイルブラウザのタブでメモを取る

キーワードだけでなく検索結果も含まれるから思い出しやすい

Search for Later メソッド

Leita

1週目のリテンションが悪い

ゲーム実況AI

マリオカートの実況をする

  • 見る
  • 感じる
  • 話す

見る

画面上の出来事を認識する

深層学習

  • 画像認識
    • CNN
  • 動作認識
    • LRCN
    • 1秒分の動作を認識
  • 物体検出
    • SSD
    • どこになるがあるかを検出

学習用のデータがない マリオカートコーパスの収集システムも作った

感じる

感情 ラッセルの感情モデル

喜怒哀楽の4つの感情を表す

ルールベース？

人間からデータをもらう プレイ中の心拍数

話す

どんなときにどんなリアクションをするのか。 既存の実況動画を分析する

毎回おなじリアクションになってしまう

自分なりのリアクションを生み出す

RNN を使う 多様なリアクションを取れる

リアクションを自動分類

展望

いろいろなゲームを実況する ゲームに関係ないことも話す

何をしようという意思は実況できるか？

顔の外見を変える顔拡張マスクの開発

お面

  • 正体を隠す
  • なりたい人やものに変化する

顔前面にディスプレイを設置 うまくいかなかった。思い、視界が悪い

お面を土台に

  • フォトクロミズムと赤外線ライト
    • 小型化が困難
    • 明るいところでは見えにくい

設計方針を決める

サーモクロミックと加熱回路層

銀ナノインクでプリントすることで回路をつくることを容易にした

ヒルベルト回路

文字形状を自動生成する Web フォント制作支援ソフトウェア

DeepGlyph

日本語フォントは、漢字が多いため制作コストが高い そのため日本語フォントは普及していない

普及させるために制作支援ソフトウェアを作った

ベクターデータとラスタデータをシームレスに行き来できる

生成の仕組み

深層学習を利用したスタイル変換

文字を画像として生成する

  • Content Reference
  • Style Reference

GAN でクロリティの高い書体を作り出す GAN を導入すると直線や曲線がなめらかになる

生成されたフォントの評価が難しい

Seed component 元になる文字

Glyph Wiki 34万字

WebDNN プレビュー Webブラウザ上で深層ニューラルネットワークの推論を行える

生成のコストを個々のマシンに負担させることができる

初心者でも作れる

https://deepglyph.app

配信もできるようにしたい

なんで10個なのか Seed component

C++ パッケージマネージャ

conan がある 使いづらい

poac

コミュニケーションロボットの会話制御ソフトウェア

なにを会話すればいいかわからない。 ロボットを十分に活用できていない

複数のロボット同士が会話する

同じ外見やアーキテクチャのロボット同士で会話する

GUI によるロボットプログラミング 1体の利用を想定した環境 できることは限られている

Roboript

  • Sota
  • Robohon
  • Pepper
  • Nao

ブロックベースの GUI プログラミング

話す順番を制御できる

Android アプリでプログラミング

ROS で通信 Android アプリが制御する ステップでブロックを当てはめる

ロボット場でロボットを制御するアプリを動かせる

保険で実証実験 子供を惹きつける

あらゆるアセットを管理するビジネスロジックを兼ね備えた汎用型分散台帳基盤の開発

クリエータがシステム運営者を選ぶ

活動が、ビットコインにおけるマイニングの代替となる

Proof of Creator

フォロー・フォロワーの有向グラフで表現

Proskenion

Merkle Patricia Tree

3D プリンタ

印刷以外もできるようにする

動くものを 3D ぷりんたで 破壊可能

3D プリンタの普及

印刷していないときのほうが長い これからは 3D プリンタが余る

直交ロボットだからプリント以外できるのは当たり前といえば当たり前

3D プリンタがその機能になる

エンドエフェクタ

エンドエフェクタ。ロボットの手みたいなもの 着脱可能なエンドエフェクタ

エンドエフェクタを 3D プリンタが印刷する

動くものを印刷する造形手法

中空にサポート材が必要

  • フィラメントのタレを利用

接地面と離れるくらいの厚みのタレをつくる

  • 剥がす・剥がさない

剥がれる場所 接地面を大きくする ガラスプレートに押し付ける

剥がれない場所 接地面を小さくするために、小さな柱をつける

  • 橋渡し

中空を作れる 柱を縁で繋いで橋渡しをする

  • 破壊可能なサポート材

3D プリンタでサポート材を破壊する

45 度だとサポート材のサポート材が必要ない

吹っ飛ばすために応力シミュレーションをする

  • 組み立て

ベベルギア 複雑な形状だと破壊できるサポート材でもできない

印刷後に組み立てる

デザインソフトウェア

パスを組み立てる

G-code を生成する

CAD 空間上と 3Dプランタうえの配置をする

エンドエフェクタの先端とエクストルーダの座標はことなるため

既存の3Dプリンタ

印刷いがいの動きを 3D プリンタに命令できるようにした

まとめ

  • 削ることができる
  • ディスプレイ表示
  • 既存のものを動かす

使わなくなったフィラメントを再利用 その場にあるものをふぃらめんとにする

宇宙開発でやくだつ

2 日目

認識 AI を迅速に賢くするフレームワークの構築

物体の画像認識

多視点画像収集 ロボットアームで多視点の画像を撮ることができる

自動アノテーション ものの周囲にAR マーカーを置くことで画像のものの輪郭を推測し、四角で囲む

15時間 -> 4分

学習データの準備

画像収集

ロボットアームのカメラ 回転ステージ

配置換えを自動化

画像を採用するかは特許技術になる

変形に対応できる さまざまな大きさに対応できる

ヒューマノイドロボット

人間型のロボット

ロボットの設計手法を情報発信してきた

知識がなくても動作をつくれる

歩かせるまでに9ヶ月かかった

40 分で素人ができるようになった

機体のモデルをつくる必要がある 重さなどが必要 分解しないで測る

Reficere 2分で1パーツ計測できる 重心センサーでわかる

誤差は 1.8%

Blender という 3DCG のソフトウェア ロボット用ではない

BlendMotion というアドオン

思った通りに動くようにシミュレーション環境で遺伝的アルゴリズムで試行錯誤する

倒れないように学習させる

ざっくりうごきをつくって、遺伝的アルゴリズムで最適化する 目的関数はどうするのか Blender の中で設定できる

分野限定型検索エンジンと分散型検索エンジン

kearch

自由な検索エンジンをつくる

作るのに莫大なリソースが必要

検索エンジンの不透明性

小リソースでだれでもデプロイ可能 アルゴリズムが公開 検閲ができない

分野を限定した検索エンジンを複数つなぎ合わせる

メタ検索エンジン、専門検索エンジン

専門検索エンジン

フォーカスクローリング 分野を限定する

メタ検索エンジン

Federated search

ユーザのクエリから専門検索エンジンを選ぶ

省リソース

専門分野のせってい

単語のリスト 起点となるURLのリスト

public と　protected を選べる

Google とも接続できる

分野を学習する

分野外は辿らない

専門検索エンジンからメタ検索エンジンにサマリーをおくって、メタ検索エンジンのクエリの判断に役立てる

くろーるできているのか

起点となる URL 出てくるのは有用な情報になるのか？

ユーザのクエリを全てに流しているのか？ 複数の場合はどのようにマージするのか 上位3つにクエリを投げる

一人称ライフログ映像から顔検出に基づいた社会活動量計の開発

ユーザ近傍におけるコンピューティング環境の開発

ローカル環境で使える物理基盤

便利な機能をパッケージ化

  • ネットワーク提供
  • 情報共有などのサービス提供

インターネットやネットワーク環境がなくてもサービスを提供できる

遠隔地との通信が不安定（遅延、トラフィックの集中）になる欠点がある

エッジコンピューティングが解決策

閉じた環境での共有ならクラウドサービスを使わなくてもいいのではないか

エッジコンピューティングの課題

  • ネットワーク構築
    • 設置する機材
  • システム運用
    • 故障、移動
  • コンピュータ制御機構
    • 柔軟に制御

一眼レフカメラのケースに入るくらい

tiparcel

ラズパイをアクセスポイントとして運用する 72Mbps

1万円のルーターは 800Mbps

72Mbps でも youtube 6台使えるくらい十分

電子ペーパーをモニタにした

Captive Portal は認証画面を自動で出す機能

認証画面ではなくサービス画面をだす

ストレージを気にした

ハードウェアを含めてパッケージ化されている ソフトウェアとして汎用化できないか その課題はなにか

ネットワークブートに依存している バイナリが arm に依存している

将来的にはシングルボードで動かしていく方針

NVDIMM 向けファイルシステムの開発

AEON

strace

システムコールの中身が違う

VMDIMM 不揮発性 RAM 速くて永続化する

速度を追求した設計 領域の使用効率をあげる

NOVA NVDIMM 専用ファイルシステム

スケーラビリティがある

使用効率をあげる

透過圧縮

設計

全体にカーネルアドレス空間にマッピング

先頭からのオフセットで全体を管理

カーネルからユーザランドへコピー　mmap で直接みれる？

Consistency Without Ordering ジャーナリングは使わずに、ポインタを相互に張る

対応したシステムコール

SSD との違い もっと早いだけ

DAX で直接読み書きする

設計がどのように変わるのか ブロック単位でなくてバイト単位でアクセスできるのが特徴

複数のプロセスが同時にアクセスできる

機械学習を用いたロボット制御のための汎用システムの開発

故障に強いロボット制御

  • 環境の変化
    • ゴミが落ちた床
  • 不測のトラブル
    • 故障
    • ケーブル破損

環境の変化は歩行で対応する

  • 真っ直ぐに進む
  • 妥当な動作

手法

  • 強化学習
    • 時間がかかる
    • 報酬設計が難しい
    • 予期した動きになるとは限らない
    • ロボットが壊れてしまう
  • シミュレーション上での学習
    • Sim to Real
    • 現実がちがう。床との摩擦、出力トルク
    • 強化学習とおなじデメリット
  • 既存歩行パターンの改善
    • 基本パターンから学習を開始
    • 馬など

具体的に

  • 基本歩行パターンから高評価なものを選定
  • 初期位置に関して学習
  • 動作パターンを学習
    • 壊れることによって無駄な動きがでてくるが省略することができる

初期位置が重要な理由

壊れた足を補うようにバランスを取る必要がある 脚の先端位置を微調整できるようになっている 初期位置を学習した

10~20分で学習できる

マーカーをつけて、カメラで撮影して正しく動いているかを判定する

プログラミングしたほうが早いのではないか？ ちょっとしたズレを見抜いて最適なものをやってくれる

反復運動に特化しているかもしれない

ボルダリングコース作成支援アプリケーション

課題帳にコースが表示されている 身長によって向き不向きなコースがある

  • ホールド難易度の推定
  • コース作成支援
  • 身長情報の反映

折り紙

折り紙技術を利用する

Crane

複雑な折り紙アート

変形を構造で制御する

剛体折り紙

折り紙の本質

  • 平面から立体へ
  • 硬くなる
  • 動きの制御
    • 一箇所を動かすと全体が動く

折り紙技術は実用化されていない 作るのが難しいから

頂点の周りの角度の総和が 2π になるような制約条件がある

製造用データのソフトウェア CAM がない

厚みが障壁となる 厚み処理ソフトが存在しない

Rhinoceros + Grasshopper を使う

macOS で動かす C コンパイラを C で作った

C 作ったもの

LISENCE と LICENSE 、正しいスペルがどっちかわからない。どうも、かわしんです。正解は LICENSE です。

僕は、よく MIT ライセンスを使います。気が向いたら WTFPL（ Do What The F*ck You Want To Public License ）を使います。趣がありますよね。

さて、僕の実家は山口にあるのですが、年末の帰省のタイミングで C コンパイラを作りました。正確には去年の 12月 30 日の東京発博多行き新幹線のぞみ号に乗った時から、今年の 1 月 4 日の夜までです。新幹線は片道5時間くらい乗ってるので開発にうってつけです。本当は東京に戻ってきたらやめると決めてたんですが、キリが悪かったので１日延長して昨日までやってました。

去年の夏あたりに Rui Ueyama さんが作った 9cc が話題になり、僕もいつか作ってみたいなと思っていました。

年末にまとまった時間が取れて、流石にそろそろ C 言語を使えるようにならないといけないと思っていたので、C 言語を理解するために C 言語を C 言語で実装してみました。

出来上がったのはこれです。MIT ライセンスです。

github.com

結局セルフコンパイルまではたどり着きませんでしたが、テストコードをコンパイルするところまでできて、キリがよかったのでここで一旦やめることにしました。

実装の方針

11 月のはじめに Rui さんが コンパイラを作る教科書の最初の部分 を公開されました。

この教科書で初歩的なコンパイラが作るところまでサポートしてくれるのでこの教科書に沿って実装を進め、そのあとは 9cc の実装などを参考に進めることにしました。

また、その後の開発の順番はこの記事にオススメの開発の順番が書かれているのでそれを参考にマイルストーンとしました。

Cコンパイラ制作の夏期集中コースが思っていた以上にうまくいった話｜Rui Ueyama｜note

この記事では開発の順番として 配列 を実装してから ポインタ を実装することがオススメされていますが、配列はポインタのように扱われるので、まず ポインタを実装してから配列を実装する のがいいと思いました。僕は一回配列から実装したのですがうまく行かず、実装を捨ててポインタから実装し直してから配列を実装しました。

また、これは重要な点なのですが、この教科書は スタックベースのコンパイラ を作るのに対して 9cc は レジスタベースのコンパイラ です。そのため構文解析や意味解析までは参考になりますが、アセンブリ言語への変換はあまり参考になりません。

そのため、スタックベースのコンパイラはセキュキャンのコースで一番早く実装が終わったという 艮 鮟鱇 さんの aqcc を参考にしました。ただ、コードベースが結構違うのでアセンブリへの変換のところあたりくらいしか読んでません。

今回は、macOS 上で動くスタックベースの C コンパイラ を作りました。

工夫した点（配列の扱い）

一番工夫したのは 配列の扱い です。以下の解説では、9cc のテストを C で書き直した時点のコミット と僕の kcc の比較として解説します。

C 言語では配列はポインタと同じように扱われます。値へのアクセスは、配列・ポインタ共に配列風のアクセス（ a[1] ）とポインタ風のアクセス（ *(a+1) ）ができます。

しかし、ポインタに配列を代入できますが、配列へは配列を代入することもポインタを代入することもできません。

int a[10];
int *b;
b = a;  // OK
// a = b; // NG

a[0] = 1; a[9] = 10;
b[0];    // 1
b[9];    // 10
*a;      // 1
*(a+9); // 10

void tmp(int *x) {
    // do something
}
tmp(a); // OK

では違いは何かというと、変数が宣言された時の挙動とその変数が指し示すものです。

ポインタはその変数が宣言されるとアドレスを格納するのに必要なサイズのメモリ（ 8 バイト ）が確保されます。ポインタ変数が指し示す値はアドレス値です。

一方、配列はその変数が宣言されると配列の長さ分のメモリ（ 型のサイズ * 配列の長さ ）が確保されます。配列変数が指し示す値は配列の先頭要素です。

9cc では、配列風のアクセスとポインタ風のアクセスは共に同じように ND_DEREF として構文解析 されています。

// 配列アクセスの構文解析
while (consume('[')) {
  lhs = new_expr(ND_DEREF, new_binop('+', lhs, assign()));
  expect(']');
}

// ポインタアクセスの構文解析
if (consume('*'))
  return new_expr(ND_DEREF, mul());

そして意味解析の中ではこれら２つのアクセス手法は扱われていますが、ND_DEREF の対象は ポインタに対するアクセスに限定 され、それ以外はエラーになるように実装されています。

配列へのアクセスをポインタに対するアクセスとして読み替えるために、意味解析の中の maybe_decay() で、配列へのアクセスノードと ND_DEREF ノードの間に ND_ADDR ノードを差し込んでポインタアクセスに変換しています。

ただし、代入では配列の値に直接書き込む必要があるのでポインタに変換してはいけません。そのため、decay という対象ノードが代入として扱われているかを示すフラグを意味解析の全てに引き回して decay が false の時は ND_ADDR ノードの差し込みを行わないように実装されています。

そのために再帰的に意味解析を行う walk() 関数のインターフェイスも変更されています。

// 配列のない時のインターフェイス
static void walk(Env *env, Node *node)

// 配列の解析が含まれた時のインターフェイス
static Node *walk(Env *env, Node *node, bool decay)

decay というフラグでコンテキストを引き回すのと、構築された AST を差し替えるのがなんとなく複雑だなと思ったのでなんとか工夫できないかを検討しました。

ポイントは、配列とポインタは同じように扱われる ということです。

9cc では、意味解析ステップ で AST の配列アクセスノードをポインタアクセスノードに差し替える ことで、配列とポインタを同じように扱っています。しかし、コンテキストを引き回したり AST を差し替えるため、ソースコードはやや複雑になっています。

僕の kcc では、AST からアセンブリの変換ステップ で 配列の値へのアクセス命令をアドレスの読み込み命令に切り替える ことで、配列とポインタを同じように扱っています。これにより、意味解析ステップでは以前と同じインターフェイスを保ち、アセンブリへの変換は ND_IDENT と ND_DEREF の処理を 配列へのアクセス時に切り替える条件分岐を入れる だけで済みます。

この方法では、配列へのアクセスが代入なのか値へ読み込みなのかのコンテキストを意識する必要がない ため実装が複雑になりません。

まだ、kcc は最適化などが最後まで実装できていないので本当にこの方針でいいのかはわかりませんが、とりあえず多次元配列の場合も含めてテストは通っているので大丈夫じゃないかと思っています。

macOS と Linux の非互換性

教科書、9cc、aqcc は全て Linux 上で動かすことを想定していると思います。確かに、Docker とか vagrant を使えばよかったんですが、やっぱりローカルで動かしたいなという軽い気持ちで macOS でコンパイルするコンパイラを作ることにしました。

教科書には、macOS と Linux の違いはラベルの書き方が先頭に _ をつけるようになるくらいのノリで書いてありましたが、教科書に載っている範囲を越えると割と非互換が多いのでハマります。（今教科書を確認したら、修正されて macOS は対象外になったようです。）

僕がハマった macOS と Linux との違いをここで紹介しておきます。もし macOS で作る場合は参考にしてみてください。

Makefile

Makefile で複数ファイルから実行バイナリを生成する 9cc: $(OBJS) の部分が mac に標準で用意されている make コマンドでは動きません。

ターゲット名だけでコンパイルする時はターゲット名と同じ .c ファイルが必要だったみたいです。

代わりに直接 gcc を呼び出すようにして解決しました。

CC=gcc
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

kcc: $(OBJS)
    $(CC) -o $@ $(OBJS) $(LDFLAGS)

グローバル変数の扱い

アセンブラではグローバル変数は、.data セクションに確保してラベル経由でアクセスします。

Linux ではグローバル変数のアドレスは、lea 命令を使って取得します。

しかし、macOS では lea はエラーになります。

error: 32-bit absolute addressing is not supported in 64-bit mode
  lea rax, .L.str474

macOS では、グローバルなラベルへのアドレスはグローバルなラベルテーブル経由（ GOTPCREL ）で引いてくる必要があります。

これは、グローバル領域のメモリは再配置されることがありアドレスの絶対値を持つことができないかららしいです。（macos - Why does this movq instruction work on linux and not osx? - Stack Overflow）

また、Apple の公式ドキュメントにも GOTPCREL のサンプルコードが載っていましたが AT&T 記法であったため、それを Intel 記法にするのにも苦労しました。その苦労の結果がこれです。

  mov rax, [label@GOTPCREL + rip]

これで、グローバル領域のラベルのアドレスを rax に読み込むことができます。

stderr

テストコードの中 でfprintf() でエラー出力するために extern int *stderr; が宣言されています。

Linux では、stderr は、_IO_FILE のポインタ変数です。

# Ubuntu 18.04 + gcc 環境
$ cat /usr/include/stdio.h | grep stderr
extern struct _IO_FILE *stderr;     /* Standard error output stream.  */
#define stderr stderr

しかし、macOS では stderr はマクロです。そのため僕は printf() 関数をエラー出力に追加ました。

今考えると stderr の代わりに __stderrp でよかったのかもしれないですが。

# macOS 10.14.2
$ cat /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h | grep stderr
extern FILE *__stderrp;
#define stderr  __stderrp

スタックサイズ

これは macOS と Linux の違いではなく両方とも対応する必要があると思いますが、スタックのサイズは 16 の倍数にアライメントされている必要があります。これに結構ハマりました。

printf を呼び出すテストでローカル変数を定義するとなぜか make: *** [test] Segmentation fault: 11 のエラーが発生し、llvm でデバッグ実行すると stack_not_16_byte_aligned_error エラーが発生していたのでわかりました。

$ lldb ./tmp-test
(lldb) target create "./tmp-test"
Current executable set to './tmp-test' (x86_64).
(lldb) run
Process 69817 launched: './tmp-test' (x86_64)
Process 69817 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00007fff59c5cc56 libdyld.dylib`stack_not_16_byte_aligned_error
libdyld.dylib`stack_not_16_byte_aligned_error:

デバッガを使えば一発でわかるエラーですが、デバッガを使う心理的障壁が高くてなかなか原因がわかりませんでした。

今後

やったことと未対応のことは以下の issue にまとめました。

Issues · Issue #1 · kawasin73/kcc · GitHub

あとは、大まかに以下のような項目が残っています。

ここまでやった感想としては、楽しかったのですが新しい型や演算子の対応は「やるだけ」という感じでめんどくさくなってきました。

テストを kcc でコンパイルできるところまでできたのでもういいかなという感じです。

時間があったら struct は実装しておきたいところです。

最後に、9cc と Cコンパイラの教科書 を無料で公開してくださった Rui Ueyama さんには深く感謝する次第です。ありがとうございました。