2022-04-29

Roswellのinstall方法 on ubuntu

common lispでcliツールを作ろうと思い、実行ファイルを吐く機構が欲しくなった.

調べたらRoswellというツールで実行ファイルを作成できるみたいなので、install・使用法のメモ.

install

基本的には公式の通り

$ curl -L https://github.com/roswell/roswell/releases/download/v19.08.10.101/roswell_19.08.10.101-1_amd64.deb --output roswell.deb
$ sudo dpkg -i roswell.deb

これらのコマンドを実行すると、/usr/bin/にrosというbinaryがinstallされていると思う

$ find /usr/ -name 'ros*'
/usr/bin/ros

とりあえず、このrosを叩いてみる. するとおもむろにrosのセットアップが始まる (sbclのinstallも行ってるようだ)

$ ros

Installing sbcl-bin...
No SBCL version specified. Downloading platform-table.html to see the available versions...
[#########################                                                 ] 3[##################################################                        ] 6[##########################################################################]100%
Installing sbcl-bin/2.0.4...
Downloading https://github.com/roswell/sbcl_bin/releases/download/2.0.4/sbcl-2.0.4-x86-64-linux-binary.tar.bz2
...

セットアップが完了して、再度 ros を叩いてみて下記のhelpが表示されたら完了

ros
Common Lisp environment setup Utility.

Usage:

   ros [options] Command [arguments...]
or
   ros [options] [[--] script-path arguments...]

commands:
   run       Run repl
   install   Install a given implementation or a system for roswell environment
   update    Update installed systems.
   build     Make executable from script.
   use       Change default implementation.
   init      Creates a new ros script, optionally based on a template.
   fmt       Indent lisp source.
   list      List Information
   template  Manage templates
   delete    Delete installed implementations
   config    Get and set options
   version   Show the roswell version information

Use "ros help [command]" for more information about a command.

Additional help topics:

   options

Use "ros help [topic]" for more information about the topic.

実行ファイルを作成してみる

ros init <file name> ってやると、実行ファイルを作成するのに必要なros fileが生成される.
試しに↓みたいなprogramをbuildしてみる

#!/bin/sh
#|-*- mode:lisp -*-|#
#|
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  (ros:ensure-asdf)
  ;;#+quicklisp(ql:quickload '() :silent t)
  )

(defpackage :ros.script.ros_test.3860230012
  (:use :cl))
(in-package :ros.script.ros_test.3860230012)

(defun foo ()
  (print "hey from foo"))

(defun main (&rest argv)
  (declare (ignorable argv))
  (foo))
;;; vim: set ft=lisp lisp:

build

$ ros build ros_test.ros

$ ./ros_test
"hey from foo"

感想

とりあえず実行ファイルは簡単に作れた
build は遅い
実行したら明らかに落ちるerrorもbuild時には弾いてくれないことがある

開発中はscriptで書いて、配布時にbuildするって使い方かなー。
あとはmoduleの分け方を調べる。

2022-04-24

型パラメタによる抽象化コードを書くのに気をつけること

自分用反省メモ。Rustを想定してたりしてる。

・その型パラメタに具体的にどのような型が入るか想定できているか？

・その型パラメタには適切な境界が設定されてるか？境界設定が甘くて、ハンドルできないような型が含まれてしまっていないか？

・その型パラメタが最終的にハンドルされる場所はどこ？その場所ではそのパラメタがとりうる全ての型に対して処理がかける？

・困ったら、とりあえずtraitだけ型パラメタ入りの抽象にして、具体的なStructは具体的な型で埋める

結論: 抽象化したいってのが先に来ちゃうといいコードにはならないね(戒め

2022-04-18

ファイルシステムも単なるkey-valueストアにすぎない

最近この本をちまちま読んでいる.

www.oreilly.co.jp

databse internalsって本の邦訳なんだけど、これの前半がストレージエンジン*1の仕組みで使われているアルゴリズムの話になっている. どのようにストレージデバイスにデータを格納すれば読み出しや書き込み性能に優れたストレージにできるのか？という議論に対する、先人たちの知恵の集結本みたいな感じがして、書籍の内容自体はとても面白い. (後半は分散システムの話になってるんだけど、そこはまだ読めていない)

ところで、「ストレージに効率よくデータを格納したい」みたいなケースはプログラミングをしている中でよく起きるするケースなのでは？って思った. ざっと思いつくのだと

mallocによるメモリ管理 (空いてるheap領域にいかに効率よくデータを配置していけばいいか？)
ファイルシステム

あたり？例えばファイルシステムとかは結構この本の考え方が通じる部分がありそう.
てかそもそもデータベースとファイルシステムの違いは？と言われるとうまく答えられない気もしてきた. データの取得の仕方が違ったり(sqlかファイルpathか)みたいなのはあるけど、「ストレージデバイスに効率よくデータを保管してくれるソフトウェア」という点に関しては同じようなものとして見れる気がする.

「ファイルシステム」ってワードってなんだか仰々しい感じがするけど、実際ファイルシステムがやってることって、「ファイル名」を指定してその実態(がある場所)を返すってのが主な仕事なんだなーって一旦理解してる.

そこまで単純化して考えてみると、実はファイルシステムって、プログラマなら頻繁にお世話になるkey-valueストア的なデータ構造の延長として考えられるのでは？

ただのkey-valueストアだって捉えたらなんか一気に敷居が下がった気がしたから簡易的なファイルシステム的なものを自作してみても面白い、かも. *2 せっかく詳解データベースを読んで、効率よくデータを格納する技術に関して少し詳しくなれた気持ちになってるので記憶があせないうちにちょっと構想を考えてみようかしら. *3

*1:データベースにおけるストレージエンジンとはなんたるやに関しては、ここのblogの図が分かりやすかった

*2: ナイーブに考えていけば、そのうち "blockに分けた方が効率がいい"とか、"inodeみたいなメタデータだけを管理するデータ構造にした方がいい" みたいな現在使われている主要なファイルシステムの便利さがわかってくるのだろうと思う.

*3:データを効率よく保存する技術という点に関しては、データ指向アプリケーションデザインという書籍も気になっている.

2022-03-29

stackエンジンの進化

こいつの内容. stackoverflow.com

確かになぜcpuレベルでstackのpushやpopのサポートがあるかってのは聞かれてみたらよく話からんってなる. 実際に昔のcpu向けのcompileではmovで引き数渡しの処理が行われていたみたい

But Pentium-M introduced a "stack engine" in the front-end that eliminates the stack-adjustment part of stack ops like push/call/ret/pop. It effectively renames the stack pointer with zero latency. See Agner Fog's microarch guide and What is the stack engine in the Sandybridge microarchitecture?

そこから、pop/retなどの命令で自動的にrspが(ほぼゼロコストで)更新されるようにprocessorが進化したとのこと.

論理的にはmovができればPC上の計算においてpush/popなんぞ必要なさそうだけど、やはりそれだと遅いってことなんだろうか.

追記: 普通にwikiにもstackエンジンについての記述があった

2022-02-17

ループアンローリングが面白かった

チューニング技法入門という資料を読んでいた。

この手の最適化は大体処理系がやってくれる場合が多くて見えにくい。いろんな手法の最適化テクニックが紹介してあったのだけど、特にループアンローリングっていう最適化が面白かったので、そのメモ。

これを実際に試したコードをgithubにも上げてるので(こっちはGoで書いてますが)、良かったら参考にしてください

github.com

ループアンローリングの概要

以下、普通のloop処理。

for i = 0; i < 1000; i++ {
    something(i);
}

このfor文のアセンブリは以下のようになる (godboltから生成)

  movl $0, -4(%rbp)        # loop内の変数iを0に初期化
  jmp .L3                     
.L4:
  movl -4(%rbp), %eax
  movl %eax, %edi           # iを関数somethingの引数に
  call something
  addl $1, -4(%rbp)         # block内の処理を終えてiをincrement
.L3:
  cmpl $3, -4(%rbp)        # iとnを比較
  jle .L4

この際、loopの度に

iとnの比較
iのincrement

を行っていることがわかる( for文なので至極当たり前のことなんだけど)

この、「1回loop回す度にこれら2つの処理をいちいち実行すんのめんどくね？」ってのがループアンローリングの動機だと理解してる

じゃあどうするか

じゃあどうするか。ループアンローリングでは、以下のようにループを展開することで、ループの度の処理を減らす。

for(int i = 0; i < 1000; i = i +10) {
         something(i);
         something(i+1);
         something(i+2);
         something(i+3);
         something(i+4);
         something(i+5);
         something(i+6);
         something(i+7);
         something(i+8);
         something(i+9);
}

この例だと、上記の繰り返しに伴う2つの処理は1/10の回数に減らせることがわかる。なるほど...頭いい...。

どれくらい早くなるの？

雑な計測だけど、ここに一応メモしてある

2021-12-05

RustのABIと共有ライブラリ

最近Rust言語の人気が上がってきてると思います。自分も最近Rustを触り始めて、その魅力に取り憑かれてる身のうちの1人です。

そんな中である時、「rustには安定したABIがありません。」というissueを見つけました。(きっかけははっきり覚えてませんが。)

はじめは、「ABIが定まってないって、そもそもなにが問題なんやあ...」って感じだったのですが、ちょっと気になって調べてみると、このissueはRust言語の今後の立ち位置をも左右させうるようなかなりスケールの大きい話だったので、今回はそのお話を自分の理解でつらつらと書いていこうと思います。(認識違いやご意見感想などがあればぜひコメントいただけると励みになります！)

そもそもABIとは
RustにABIがないというのはどういうことか
ABIと共有ライブラリ
日々私たちはいかに共有ライブラリに依存してるか
ABIと共有ライブラリ 2
どうしてRustのABI安定が図られない？
まとめと今後の動向
参考文献

なおこの記事は CyberAgent 22 新卒 Advent Calendar 5日目の記事として投稿してます。

adventar.org

そもそもABIとは

ABIは「Application Binary Interface」の略で、アプリケーションコードと生成されるマシン語の間のインターフェースを指します。

似た言葉に、API(Application Programming Interface)があります。これはプログラムのソースコードと、ライブラリ間のインターフェースを指す用語として使用されます。

例えばIntをStringに変換するようなライブラリ関数

pub fn int_to_string(n: i32) -> String {...}

みたいなのがあった場合、

この関数はi32を引数にとる
返り値としてStringを返す

と言ったのがAPIの例と言えます。

ABIも同じような感じで、ソースコードがどのようなマシン語になるかを規定したものです。

よく出てくる例として、関数の呼び出し規約(引数はどのレジスタに渡されるか、stackのレイアウトはどのようになるか)や構造体のデータ構造をどのようなマシン語で実現するか、と言った話はABIと関連しています。*1

なので、ABIが安定しているとは、「関数呼び出しや構造体のデータ構造をどのような規則でマシン語にするかといった仕様がきちんと定義されている」と言い換えることができそうです。

ABIが安定している言語の例として、C言語が挙げられます。*2 これは、C言語のコンパイラが(x86_64において)Sytem V ABIと呼ばれる仕様に基づいてコード生成を行うため、安定していると言われているわけです。

RustにABIがないというのはどういうことか

では、RustのABIが定まってないとはどういうことでしょうか？自分なりに下記のようだと解釈しています。(まあ、そのままですが.)

関数の呼び出し規約や構造体のデータの表現方法などに代表される、マシン語の生成に関する仕様が明確に定まっていない.

例えば、Rustのunsafe code guidelinesには、コンパイル時の状況によって構造体のレイアウトが変化しうるという記述があり、これはABIが定まっていない挙動の1つ例として挙げることができます。*3 　これはわざと定めてないという訳ではなく、コンパイラの「構造体のフィールドをいい感じに並び替えて構造体サイズを最小にしようとする」という最適化の挙動から来てるものです。ただ、結果的にABIが定まっていないというデメリットも含んでしまってるわけです。

しかし、よくよく考えてみても、これのどこが問題なのでしょうか？実際、Rustは現在様々なシステム上で問題なく実行できていますし、自分もABIが定まっていないことによって、日々の趣味開発で不便さを感じたことがありません。

どうしてABIが定まってることが大事なのでしょうか？

ABIと共有ライブラリ

stableなABIが無いと困る場面として、システムの共有ライブラリを作成しにくい、という点が挙げられます。

ここで少し共有ライブラリの話をしてみましょう。

システムにおける共有ライブラリというのは、OSに標準でついてくる「頻繁に行う処理」を集めたライブラリです。*4 例えば「文字を出力する・読み込む」とか「新規プロセスを作成する」とかはシステム上において頻繁に行う操作なので、それらは共有ライブラリとして提供されています。

共有ライブラリにはいくつかメリットがあります。

まずは、実行ファイルの大きさを節約できるという点です。共有ライブラリの関数はリンク時ではなく実行時に解決されます。例えばC言語のおなじみprintf()は共有ライブラリが提供する関数ですが、printf()自体のマシン語はコンパイルした実行ファイルに含まれません。代わりに、実行時において共有ライブラリのprintf()のアドレスが実行ファイルのprintf()のcall先に埋め込まれます。このように、実行ファイル自体にはprintf()のマシン語は入らないので、普通の関数をコンパイルするのに比べてバイナリサイズを小さく保てるのです。

さらに、別のメリットとして共有ライブラリの関数は複数のプロセスでも共有できるという点もあります。例えば、マシン内でprintf()をコールするプロセスが複数あった場合を考えてみます。この場合、各プロセスに対して共有ライブラリprintf()がそれぞれ個別にメモリ上に展開されるわけではなく、展開されてる共有ライブラリのprintf()をそれぞれのプロセスが参照するような形をとります。

このように、共有ライブラリは「バイナリサイズを小さくする」、「実行時にメモリを節約する」といったメリットがあり、これは「システム内で頻繁に行う処理」に対して特に有効に働きます。

日々私たちはいかに共有ライブラリに依存してるか

ここで、共有ライブラリの重要性に関して述べたある記事を紹介します。

nibblestew.blogspot.com

これは、「もし共有ライブラリなしでLinuxディストリビューションを構成したらどうなってしまうのか？」ということに関して、仮説・検証も交えつつ非常に面白く解説している記事です。(短いし内容もわかりやすいのでぜひ直接読んでみてください)

この記事の要点は下みたいな感じです。

*  静的リンクしか提供していない言語DostでLinuxディストリビューションを構築する

という前提をおいた結果、

*  /usr/bin 配下のバイナリサイズが概ね4GB程度になる
*  静的リンクにより、動的リンクに比べバイナリサイズが20倍大きくなった  
* 動的リンクなしで、静的リンクだけでOSを構成するのは
という検証結果が得られた。

共有ライブラリがない世界、凄まじいですね。。実行ファイルが依存している処理を全てその実行ファイル自身が保持しているわけですが、それでここまでのサイズになるのは驚きです。これではPCの容量がいくらあっても足りない気がしますし、ましてや組み込みシステムなど、メモリ資源が潤沢でない環境などにおいては全く機能しなさそうです。

つまりOSのようなシステムプラットフォームを構築するにあたっては、共有ライブラリの概念は必須のものと言えるでしょう。

ABIと共有ライブラリ 2

あるシステムを構成するにあたり、共有ライブラリが重要な役割をはたしていることが分かりました。共有ライブラリがないと、私たちのシステムは、バイナリサイズがやけに大きい、しかも内部的に重複をたくさん含んだ無駄だらけの実行ファイルたちで埋め尽くされてしまいます。なので共有ライブラリを導入したいわけです。

では、どういった言語が共有ライブラリを構築するのに向いてるでしょうか？

様々な観点があると思いますが、ABIの安定性はまさにその特徴の1つになるでしょう。

仮にABIが安定していない言語で共有ライブラリを構成した時をイメージしてみます。 ABI仕様がコロコロ変更されるため、その度に共有ライブラリと、その共有ライブラリたちに依存しているバイナリ達(これは実質ほぼ全てのアプリが当てはまるでしょう)を再コンパルする必要があります。これはとんでもなく面倒です。そんな言語で、各種OSベンダ達はシステムを構築しようとは思わないでしょう。

どうしてRustのABI安定が図られない？

Rustに話を戻します。安定したABIを提供し、システム共有ライブラリを提供できるようになることは、Rustがシステムプログラミング言語となるための大きなステップであることは間違いなさそうです。

では一体、どうしてRustのABI安定が図られないのでしょうか。筆者が調べた中だと、概ね下記の懸念があるようです。

ABIを標準化することで、コンパイル時の最適化が行えなくなるケースが出てくる*5
genericsなどの、コンパイル時にコード生成を行う言語機能は、共有ライブラリに含めることがそもそも難しい*6

1つ目はRustのパフォーマンスとのトレードオフになっています。ABIを定義することにより、ある種の最適化が行えなくなるということです。例えば先に述べた構造体のフィールドレイアウトの話も、フィールド順を固定化するようなABIを定めてしまうと、構造体のpaddingを加味して構造体サイズを最小にするみたいな最適化ができなくなってしまいます。

2つ目はRust言語の複雑な言語機能に起因することです。C言語は長年共有ライブラリの父とも言える地位を築き続けてきていますが、それはシンプルな言語使用によってABIが決めやすいという部分も大きく寄与していたのかもしれません。Rustはどうでしょうか。ジェネリクスなどのコンパイル時にコード生成を行う機能はそもそも共有ライブラリと相性が悪いことに加え、所有権、非同期処理、マルチスレッドなど、Cにはない複雑、多様な言語機能を持っており、これらのABI仕様を決定するというのは相当タフなタスクであることは想像できます。*7

このようにABIは単に決めればいいだけという話ではなく、決定に際して様々なデメリットや必要となる作業が生じ、それらを加味した上で最善な判断を下さないといけないわけです。大変そうですね。

まとめと今後の動向

Rustは、C, C++のような「システムプログラミング言語」としての成長を期待されており、近年人気が上がってきている言語です。コンパイル時の静的検証・最適化に徹底しており、GCは無く、実行時のパフォーマンスは他の言語と比較してもかなり高い水準です。さらになんと言っても、 Cのダングリングポインタのようなつらーいメモリバグは、Rustの型システムの前では姿を消します。これらの特徴はシステム開発者にとっては非常に喜ばしい機能でしょう。

しかし、繰り返すように、Rustには安定したABIがありません。安定したABIがないと、共有ライブラリの例で挙げたように、Rustをインターフェースにしてある機能を提供するといったことが難しくなります。

そのため現状、Rustの良さを十分に把握し、「Rustを使いたい！」と思ってるシステムベンダーも、ABIが安定してないことに不安を覚えてRust導入に踏み切れないという面があるようです。低レイヤ言語としての地位を期待されてるRustとしては、システムの共有ライブラリを提供できないというのはデメリットが大きいのです。

ただ、良いニュースもあります。例えば1年前の春ごろにA Stable Modular ABI for Rustというタイトルで、Rust Internal Formalから下記のような投稿があったようです。

internals.rust-lang.org

これはRustのABIの安定化に向けた議論で、特にモジュラーABIという手法をRustに導入できないか、といった議論がされています。モジュラーABIというのは、コンパイラの1つのモジュールとしてABIモジュールというものを切り出せるようにし、ABIをユーザーが自由に選択可能となるようにする、といったものだそうです。これが実現できれば、例えばABI互換を持たせたいライブラリにはstable_abiモードでコンパイル、特に気にしない場合は通常通りのコンパイルを行う、といった選択ができるようになると説明されています。

さらにRust ABI wikiなるページもできており、Rustチームの中でもABI安定化に向けた動きは少しずつ進んでいるのかもしれません。

すでにRustは所有権モデルなどの斬新な言語機能で幅広いプログラマーから注目されています。

が、個人的には今後Rust言語がどのように「システムプログラミング言語」としての地位を獲得していくのかを特に注目していきたいです。

さらに、この過程をABIという観点で見ていくと、より面白いかもしれない、とissueを読みながら思ったりしました。

参考文献

A Stable Modular ABI for Rust
https://internals.rust-lang.org/t/a-stable-modular-abi-for-rust/12347

How Swift Achieved Dynamic Linking Where Rust Couldn't
https://gankra.github.io/blah/swift-abi/

Rust ABI wiki
https://slightknack.github.io/rust-abi-wiki/intro/intro.html

Rust does not have a stable ABI
https://people.gnome.org/~federico/blog/rust-stable-abi.html

Layout of structs and tuples
https://rust-lang.github.io/unsafe-code-guidelines/layout/structs-and-tuples.html

Is static linking the solution to all of our problems?
https://nibblestew.blogspot.com/2017/03/is-static-linking-solution-to-all-of.html

When is the ABI stable?
https://internals.rust-lang.org/t/when-is-the-abi-stable/10420/2

ABIバグは「悪夢」
https://www.snsystems.com/ja/technology/tech-blog/2015/06/11/abi-bugs-are-a-nightmare/

*1:例えば関数の呼び出し規約に関してはx86_64アーキテクチャだとSystem V Application Binary Interfaceという仕様に準拠してます。この仕様における関数の内部的な実行の流れを知りたい場合は、例えばここの投稿を参考にしてみてください。(説明がとても丁寧で図もあるので、関数の処理のされ方のイメージを掴みやすいと思います。

*2:Swift言語もSwift5からABI互換を謳っています。

*3:ただし構造体に関しては、#[repr()]といった属性をつけることでこの挙動をオプションにすることができます

*4:Linuxでは.soの拡張子で提供されてるアレです。http://archive.linux.or.jp/JF/JFdocs/Program-Library-HOWTO/shared-libraries.html

*5:こちらの参考リンクに詳細が書かれてました

*6:こちらの参考リンクに詳細が書かれていました

*7:実際、C++もCにはない言語機能に関してはABIの安定を保証していない?みたいです。

2021-11-24

x86エミュレータbochsとI/O port

x86 エミュレータ、bochs について。

元々cpuエミュレータはQEMUくらいしか知らなかったけど、xv6のソースを呼んでる中でbochsという単語がたまに出てきて知った。 QEMUとbochsのwikiをみたけど、やっぱQEMUの方がエミュレートできるマシンが多いみたいで、まあこの界隈だとQEMUがメジャーなんだろうか。

ただbochsの公式にx86のio portの一覧表があって、これがxv6を読むときに非常に参考になりそう。*1

引き続きxv6読んでいって、ある程度理解がまとまったタイミングで記事にする。

参考資料

https://bochs.sourceforge.io/

https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#io-port%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

*1:io portについてはここがわかりやすかった

mox692 のブログ

妄想の書き留め場所.