HN 日本語サマリー

← 一覧へ戻る
プログラミング

実行可能ファイルはSQLiteデータベースである

Executable Is a SQLite Database (fzakaria.com)

462 pointsby setheron88 コメント

要約

この記事では、実行可能ファイルフォーマットとしてELFに代わりSQLiteを使用するという革新的なアイデアを探求しています。ELFは本質的にデータベースであり、多くのデータベースプリミティブを手作業で実装していると筆者は指摘します。SQLiteを代替フォーマットとして使用することで、sqlelfのようなツールでELFファイルをSQLで探索したり、SELF(Structured Executable & Linkable Format)というプロトタイプで実行可能ファイル自体をSQLiteデータベースとして扱ったりすることが可能になります。これにより、ファイル解析や操作が簡素化され、トランザクション処理のようなデータベースの利点を活用できるようになります。

全文翻訳

実行可能ファイルはSQLiteデータベースである

ここ数年、私はおそらく2つのことに夢中になっていました。それは、革新的なアイデアを探求するためのツールとしてのNix(世界を再構築する能力を必要とする)と、ELFをSQLiteに置き換えるという実行可能フォーマットとしてのアイデアです。これらの2つのアイデアが互いに非常によく適合していることに気づいたかもしれません。

私は博士論文でこのアイデアを探求しましたが、他の人からのフィードバックは意欲を削ぐものでした。急進的なアイデアは売り込みが難しく、確立されたソリューションの慣性に逆らって働くことになるからです。

[画像: 4コマ漫画。マイクの前に立ったカラスが「Nixは素晴らしい」と言うと、観客はブーイングし「もっと良いネタを考えろ」と叫ぶ。カラスはショックを受けた様子。最後のコマでは、残りのキューカードに「SQLiteはオブジェクトファイルフォーマットになりうる」と書かれている。]

その探求の成果の一つがsqlelfでした。これは、SQLを使ってELFファイルを宣言的に探索できるツールです。私は論文arXiv:2405.03883を執筆しましたが、掲載に失敗し、その後クエリ方法についての投稿をしました。readelfやgrepをいじる代わりにSELECT name FROM elf_symbolsを使います。ELFの仮想テーブルを活用することで、驚くほどシンプルでしたが、ELFファイルフォーマットを探索するための爽快な改善だと感じました。しかし、もっと大きなことがまだできるとわかっていました。

私はこのアイデアを諦めず、最近のLLMの進歩により、これらのアイデアをさらに探求するために再訪することが説得力のあるものになりました。具体的には、ELFをSQLiteに置き換えることは可能でしょうか?🤔

「実行可能ファイルを記述するデータベース」ではなく、chmod +xして実行する実際のファイルのことです。

$ file hello
hello: SQLite 3.x database, application id 0x53454c46, user version 1

$ ./hello
Hello, world!

$ sqlite3 hello 'SELECT soname FROM ldd'
c.so.6

かなり充実したプロトタイプを開発しました。私は独創性に欠けるので、それはSELF、Structured Executable & Linkable Formatと呼ばれています。興味があればGitHubにあります。このアイデアから生まれる興味深いことがたくさんあることに驚いています。

ELFはそれを認めようとしないデータベースである

博士課程を進める中で、私は気になることに気づきました。ELFはすでにデータベースなのです。ただ、データベースの多くのプリミティブを独自に実装しており、シンボルルックアップのためのブルームフィルターのような、パフォーマンスのための驚くほど多くのデータ構造を持っています。

ELFメカニズムそれが再実装するデータベースプリミティブ
.strtab / .dynstr文字列インターニング
.hash / .gnu.hashインデックス (CREATE INDEX)
セクションヘッダーテーブルsqlite_schema、テーブルのテーブル
st_name → .strtabへのオフセット手動で行われる外部キー
sh_offset / sh_sizeBツリーページのレコードレイアウト
.gnu.version_rカラム
objcopy --strip-debugDELETE + VACUUM
ldconfigキャッシュ、debuginfod上記に対する帯域外インデックス

ELFを分析またはパースする必要がある場合、カーネル、ld.so、binutils、LIEF、goblin、readelfは、すべて同じパーサーを繰り返し再実装しています。すべてのプロデューサーは同じシリアライザーを再実装しています。

フォーマット自体は信じられないほど簡潔で、ディスクスペースとネットワーク帯域幅が極端に貴重だった時代のために設計されています。フォーマットの変更は難しく、非常にタイトに詰め込まれているため、セクションをゼロクリアして新しいセクションを追加する必要があることがよくあります。自己記述的なスキーマもありません。ELF自体は非常に汎用的なフォーマットであり、慣習的に特定の意味で解釈されるデータセクションをサポートしますが、フォーマット自体はそれを強制しません。

SQLiteはその対極にあります。自己記述的なフォーマットであり、非常に安定しています。既存のコンシューマーを壊すことなく新機能のサポートを拡張し、幅広いクエリを効率的にサポートするように設計されています。

もしELFをSQLiteに置き換えるとしたら、何が失われ、必要な情報はすべてSQLiteデータベースに表現できるでしょうか?答えは「はい」であり、驚くほどシンプルです。

何が失われるか

SELFファイルが実行されるには、2つのテーブルが必要です。self_metaはキー/バリューペアとしてのELFヘッダー、segmentsはロードイメージで、プログラムヘッダーごとに1行、バイトはBLOBとして格納されます。

CREATE TABLE segments (
  -- 元のphdrインデックス
  id      INTEGER PRIMARY KEY,
  -- 'load' | 'tls' | 'stack' | 'relro'
  type    TEXT NOT NULL,
  -- 元のファイルオフセット
  offset  INTEGER NOT NULL,
  vaddr   INTEGER NOT NULL,
  filesz  INTEGER NOT NULL,
  memsz   INTEGER NOT NULL,
  r INTEGER, w INTEGER, x INTEGER,
  align   INTEGER NOT NULL DEFAULT 4096,
  -- セグメントバイト; 純粋なBSSの場合はNULL
  content BLOB
);

シンボルテーブル用の単一のテーブルが、多くのELFセクションと.gnu.hashインデックスを置き換えます。これは単一のテーブルと単一のインデックスです。

CREATE TABLE symbols (
  id      INTEGER PRIMARY KEY,
  name    TEXT NOT NULL,
  -- 'GLIBC_2.2.5'
  version TEXT,
  value   INTEGER,
  size    INTEGER,
  -- 'func' | 'object' | 'tls' | ...
  type    TEXT,
  -- 'global' | 'weak' | 'local'
  bind    TEXT,
  defined  INTEGER NOT NULL,
  exported INTEGER NOT NULL
);
CREATE INDEX idx_symbols_name ON symbols(name, version);

インデックスを含める能力は、ELFの.gnu.hashと.hashに相当しますが、手作りのブルームフィルターではなく、SQLiteによって維持される正規のBツリーインデックスです。.gnu.hashはブルームフィルターとバケットチェーンで構成されており、ld.soがシンボル発見中にチェーンに触れることなくミスを拒否できるように配置されています。

驚くべきことに、さらに多くのものが失われます。.dynstrは不要になります。なぜなら、nameはTEXTであり、SQLiteはすでに文字列をインターニングしているからです。シンボルバージョニングはカラムであり、.gnu.version_r / .gnu.version_dのような仕組みではありません。また、stringsテーブルも不要です。

メタデータ用の他のテーブルも存在し、ツールで使用されます。sections、notes、dynamic_entriesです。これらを削除してもプログラムは実行されるため、strip(1)はトランザクションになります。

# ldd(1)
$ sqlite3 hello 'SELECT soname FROM ldd'
libc.so.6

# nm -D --undefined
$ sqlite3 hello 'SELECT name,version FROM imports LIMIT 3'
__libc_start_main|GLIBC_2.34
_ITM_deregisterTMCloneTable|
puts|GLIBC_2.2.5

# readelf -l
$ sqlite3 hello \
    "SELECT type,vaddr,memsz,r,w,x FROM segments WHERE type='load'"
load|0|1744|1|0|0
load|4096|361|1|0|1
load|8192|312|1|0|0
load|15768|640|1|1|0

# strip(1)
$ sqlite3 hello 'DELETE FROM sections; DELETE FROM notes; VACUUM;'
# 57344 -> 49152 バイト

# まだ実行できる、オプションのテーブルはオプションだった
$ ./hello
Hello, world!

ELFファイルを操作するすべてのツール(読み取り用)は、データベースに対するクエリに還元されます。stripのようなELFファイルを変更するツールは、壊れやすいオフセット操作を実行する代わりに、トランザクション内でデータベースを操作できます。stripはDELETEとVACUUMです。patchelfはUPDATEです。

スキーマに欠けている情報は、ビューを介して簡単に公開できます。例えば、lddはneededテーブルに対するクエリであり、これはsymbolsテーブルとsegmentsテーブルの結合によってプログラムが必要とするライブラリのsonameを見つけます。

CREATE VIEW exports AS SELECT name, version, type, size FROM symbols WHERE exported = 1;
CREATE VIEW imports AS SELECT name, version FROM symbols WHERE defined = 0;
CREATE VIEW ldd     AS SELECT ord, soname FROM needed ORDER BY ord;

どうやって機能するのか

SQLiteは、ヘッダーのオフセット68バイト目に、この目的のために正確に4バイトのapplication_idを予約しています。私たちはこれをSELFとスタンプするので、通常のSQLiteデータベースは決して一致しません。

$ xxd -s 64 -l 8 hello
00000040: 0000 0001 5345 4c46                      ....SELF

これで、binfmt_miscを活用できます。これは、任意のバイナリをネイティブであるかのように呼び出すことができるサブシステムです。トリガーするマジックと、新しいファイルフォーマットを呼び出すインタープリターを登録するだけで済みます。

NixOSでは、登録はSQLiteのマジック(オフセット0)とSELF(68バイト目)に一致する数行です。

boot.binfmt.registrations.self = {
  recognitionType = "magic";
  offset = 0;
  # バイト 0-15, 68-71
  magicOrExtension = "SQLite format 3\x00" + ... + "SELF";
  # 中間は無視
  mask = "\xff..\x00..\xff";
  interpreter = "${self-exec}/bin/self-exec";
};

今のところ、ELFファイルをSELFファイルに変換する小さなツールelf2selfがあります。これは、NixOSの各パッケージでオプトインできる簡単なpostFixupフックです。このツールはELFを読み込み、プログラムヘッダーとシンボルテーブルを抽出し、それらをSQLiteデータベースに書き込みます。gccやldを拡張して直接SELFを出力することを検討できますが、今のところこれはアイデアを探求するための簡単な方法です。

elf hello (ELF) -> elf2self -> conv elf-> self hello (SQLite db) -> conv-> self krn execve() binfmt_misc self->krn magic SELF@68 interp self-exec (interpreter) krn->interp run running process interp->run

self-execがインタープリターです。これはlibsqlite3にリンクされた小さなCプログラムです。その実装はld.soの実装と驚くほど似ていますが、ELFファイルから読み取るのではなく、データベースからプログラムヘッダーとシンボルテーブルを取得します。ロード可能なセグメントをメモリにマッピングし、リロケーションを行い、エントリポイントにジャンプします。

注意 self-execはELFファイルでなければなりません。登録に一致するインタープリターが自身を呼び出すと、-ELOOPに陥ります。

動的リンク

静的プログラムを実行するのは迅速かつ簡単でしたが、退屈で想像力に欠けていました。興味深いのは動的リンクであり、ここでデータベースが輝きます。

動的リンクには2つの異なる方法を探求しました。1つ目はld.soを維持し、glibcのrtld-auditインターフェースを介してSQLクエリでルックアップを置き換えることで、設計を迅速に反復処理します。2つ目は、SQL全体でルックアップとバインディングを行う新しいダイナミックリンカでld.soを完全に置き換えることです。

glibcのrtld-auditインターフェースにより、監査ライブラリは、ファイルシステム検索(dlopenを含む)が行われる前に、すべての共有オブジェクトルックアップ(la_objsearch)をインターセプトできます。監査ライブラリは、「どのライブラリがこのシンボルを満たすか?」という質問に、RUNPATHやLD_LIBRARY_PATHをウォークする代わりにSQLクエリで答えることができます。標準のld.soはそれをマッピングしてリロケートするため、glibcのすべての機能(遅延PLT、IFUNC、TLS、シンボルバージョニング)が機能します。ライブラリのストレージは行、ライブラリのルックアップはクエリになります。

# ディスク上にELFライブラリはどこにもない
$ rm libgreet.so.1
$ ./app
./app: error while loading shared libraries: 
       libgreet.so.1: cannot open ...

$ self scan --db system.db .
$ SELF_SYSTEM_DB=system.db LD_AUDIT=libself-audit.so ./app
Hello, world, from a SQLite library!

完全にSQLベースのダイナミックリンカがどのようになるか知りたかったので、プロトタイプを作成しました。それはself-ldと呼ばれ、SQLでダイナミックリンカ全体を実装する小さなCプログラムです。これは概念実証ですが、機能します。各オブジェクトのセグメントをマッピングし、エクスポートを公開し、各リロケーションに対してGOTをパッチして開始点にジャンプします。

SELECT s.value + o.load_bias
FROM   relocations r
JOIN   symbols s ON r.symbol = s.id
JOIN   objects o ON s.object = o.id
WHERE  r.id = ?
ORDER BY o.load_order
LIMIT  1;

コストとベンチマーク

確立されたフォーマットを置き換える際に常に問題となるのは、サイズとレイテンシです。SELFファイルはELFファイルよりもどれくらい大きくなり、実行はどれくらい遅くなるのでしょうか?

サイズ。 SELFファイルはSQLiteのBツリーオーバーヘッドを運び、ELFの約2倍のサイズになります。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 10 100 1K 10K 100K gdb git curl hello 2.3x 2.2x 2.5x 3.6x オンディスクサイズ (KiB, 対数スケール) ELF SELF

ELFバイナリと同様に、そのほとんどは回復可能です。なぜなら、オーバーヘッドの大部分はデバッグやツールのためのオプションテーブルだからです。それらをストリップして削除することはトランザクションです。ストリップされたcoreutilsのSELFは1,794,048バイトですが、ELFは1,768,632バイトであり、これは1%以内です。

さらに、オーバーヘッドをさらに償却する興味深い方法があることがわかります。これは非常にユニークで興味深い発見でした。

レイテンシ。 15 KiBのhelloから42 MiBのgdb(47ライブラリをリンク)まで、さまざまなバイナリをベンチマークしました。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ hello curl git gdb 1 3 10 30 100 実行レイテンシ (ms, 対数スケール) ELF SELF

SQLiteを開いてインタープリターを開始するのに固定で約5ミリ秒かかり、それに加えてイメージに比例するコピーが発生します。このコピーは見た目よりも悪いです。なぜなら、Bツリーページはメモリにマッピングされないからです。同じSELFバイナリを実行する2つのプロセスは、バイトがBツリーからコピーされるため、通常のmmapされたELFのようにテキストページを共有しません。curl(274 KiB、27ライブラリ)がELFのgit(4.6 MiB、5ライブラリ)よりも遅く開始することに気づくかもしれません。これは、私が以前に不満を述べたように、バイト数ではなくオブジェクト数に比例する作業を行うld.soのためです。

システムはクロージャである

SQLiteデータベースは、単一の実行可能ファイルである必要はありません。それはクロージャ、つまりプログラムとそのすべての推移的な依存関係を含む単一のファイルになり得ます。プログラムのldd出力は曖昧です。必要なライブラリのsonameのみを示し、それらのニーズを満たす特定のファイルは示しません。Nixは、RUNPATHの使用により、すべてのエッジを特定のストアパスに明示的に解決することでこれを改善します。私は以前、NixにおけるRUNPATHについて、冗長にすることや高速化することについて書いてきました。

SELFでも同様のことを、各エッジの解決済みパスをデータベースに格納することで実現できます。

CREATE TABLE objects (id INTEGER PRIMARY KEY, path TEXT UNIQUE,
                      soname TEXT, kind TEXT, is_root INTEGER);
CREATE TABLE needs (
  object_id     INTEGER REFERENCES objects(id),
  ord           INTEGER NOT NULL,
  soname        TEXT NOT NULL,
  -- 曖昧さを解消するFK
  resolved_path TEXT REFERENCES objects(path)
);

self closureは、バイナリとその推移的な依存関係を1つのデータベースにパックし、それらのエッジを埋め込みます。共有ライブラリの解決は推測ではなくなり、外部キーとなり、lddはJOINになります🤯。

$ self closure "$(readlink -f $(command -v ls))" coreutils.db
ls + closure -> coreutils.db

$ sqlite3 -column coreutils.db \
    "SELECT n.soname, substr(n.resolved_path, 12, 20)
     FROM needs n JOIN objects o ON o.id = n.object_id
     WHERE o.is_root = 1"
libgmp.so.10          rfabfsmwq02sn94mb3qg
libacl.so.1           x0zgiss9hdzcsll3cswg
libattr.so.1          08nfpyc4qhzdkc37nznv
libc.so.6             8kvxvr3pmsypxiypq4g8

この単一のデータベースは、ls実行可能ファイルとその5つのライブラリのクロージャです。6つのオブジェクト、セグメントバイトすべてを含み、1つの4.8 MiBファイルになります。クロージャ内では、クロージャの定義により各エッジにプロバイダーが1つだけ存在するため、sonameの曖昧さはありません。

ls ls (is_root) libc libc.so.6 ls->libc gmp libgmp.so.10 ls->gmp acl libacl.so.1 ls->acl attr libattr.so.1 ls->attr gmp->libc acl->libc acl->attr attr->libc

どこまで行くのか?1つのファイル、1つのユーザーランド

ここまでついてきてくれたなら幸いです。なぜなら、ここからが本当に面白くなるからです。さらに進んで、複数のクロージャを単一のデータベースにパックすることができます。

[画像: 5パネルのインセプションミーム。コブ:「あなたの実行可能ファイルはSQLiteデータベースです。」フィッシャー:「そしてそれがリンクするライブラリは?」コブ:「それらもSQLiteです。ユーザーランド全体も、1つのファイルです。」フィッシャー:「これはどこまで続くのですか?」コブ、ウィンクして:「あなたは今、その中にいます。」]

このシステムのPATHにあるすべてのELFバイナリに対してself closureを実行しました。723個の実行可能ファイルが400個の異なる共有ライブラリをプルします。1,123個のオブジェクト、346,386個のシンボル、3,808個の依存関係エッジがすべて1つのSQLiteファイルになります。

実際にやってみると、データベースは予想よりもはるかに小さくなることがわかりました。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 0 200 400 600 セグメントペイロード (プログラムバイト) 単一のSQLiteデータベース 元のELFファイルオンディスク 644.4 MiB 611.9 MiB 576.9 MiB 合計サイズ (MiB)

611.9 MiBのデータベースに対して、644.4 MiBのELFファイル。 クエリ可能な単一ファイルとしてのユーザーランド全体は、それらが元になったファイルよりも小さいです。Bツリーのコストは、単一のhelloファイルを2倍にしたものですが、1,123個のオブジェクトに分散されるとほとんどゼロになり、実際のプログラムバイトに対して約6%になります。

ライブラリとクロージャは、Nixが複数のクロージャ間でそれらを共有するのと非常に似た方法で、ストアパスが同じであれば共有されます。もし各ルートが独自のプライベートクロージャ(つまりAppImageモデル)を出荷した場合、同じ723個のプログラムは5.53 GiBになりますが、ライブラリとシンボルの重複排除はデータベーススキーマから自然に生まれます。

$ sqlite3 userland.db \
    'SELECT count(DISTINCT soname), count(*) 
     FROM objects WHERE soname IS NOT NULL'
345|399

$ sqlite3 -column userland.db \
    'SELECT soname, count(*) FROM objects 
     WHERE soname IS NOT NULL 
     GROUP BY soname HAVING count(*) > 1 
     ORDER BY 2 DESC LIMIT 4'
libsystemd.so.0   3
libpthread.so.0   3
libgcc_s.so.1     3
libc.so.6         3

$ sqlite3 userland.db \
    "SELECT count(*)
    FROM needs
    WHERE resolved_path IS NULL AND soname NOT LIKE 'ld-%'"
4

ELFで使用される多くの一般的なイディオムは、データベースから直接生まれます。例えば、LD_PRELOADは環境変数ではなく、テーブルの行になります。preloadテーブルは最後にマッピングされるオブジェクトのリストであり、そのエクスポートが優先されます。これは、LD_PRELOADのオン/オフがトランザクションであることを意味します。

$ ./app.self; echo $?
13

$ sqlite3 system.db "BEGIN;
    CREATE TABLE preload(ord INTEGER PRIMARY KEY, path TEXT);
    INSERT INTO preload VALUES (0, 'libmul.so.1.self');
  COMMIT;"

# 同じバイナリ、環境変数なし、再リンクなし
$ ./app.self; echo $?
42

$ sqlite3 system.db 'DELETE FROM preload;'
$ ./app.self; echo $?
13

単一のファイルで、ユーザーランド全体にわたるアトミックなLD_PRELOADを達成できました。「トレーシングmallocをすべてにインターセプトし、その後ROLLBACK」は単一のトランザクションです。😈

現状

フォーマットは完成しており、ELFとSELFの間でロスレスに往復できます。ツールも完成しており、クロージャをクエリ、変更、パックできます。SQLを介したルックアップは、変更されていないglibcプログラムで完全に機能し、ネイティブSQLローダーは、アイデアの可能性として探求するのに十分なほど機能します。

すべてはfzakaria/selfdbにあります。nix run .#self-vmは、helloがSQLiteデータベースであるNixOS VMを起動します。🙌

Nixは、このような急進的なアイデアを探求することを可能にします。必要であれば、Linuxカーネルまで世界を再構築できます。過去の既存の決定や制約に縛られる必要はありません。新しいアイデアを探求し、何が生まれるかを見ることができます。このアイデアが私と同じくらい興味深いと思っていただければ幸いです。