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

過去数年間、私はおそらく2つのことに夢中になっていました。 革新的なアイデアを探求するためのツールとしてのNix。世界を再構築する能力が必要なアイデアです。 そして、ELFをSQLiteに置き換えるという実行可能フォーマットとしてのアイデアです。 これらの2つのアイデアが互いに非常に適していることに気づいたかもしれません。 私は博士論文でこのアイデアを探求しましたが、他の人からのフィードバックは意欲を削ぐものでした。 急進的なアイデアは売り込みが難しいです。なぜなら、確立されたソリューションの慣性に逆らって作業しているからです。 その探求の成果の1つはsqlelfでした。 これは、ELFファイルを宣言的にSQLで探索できるツールです。 11 私は論文、arXiv:2405.03883を発表しましたが、掲載されませんでした。 そして、それをクエリするためのフォローアップ投稿を書きました。 readelfとgrepをいじる代わりに、SELECT name FROM elf_symbols。 仮想テーブルを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' libc.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_size Bツリーページのレコードレイアウト .gnu.version_r 上記に対する列 objcopy --strip-debug DELETE + VACUUM ldconfigキャッシュ、debuginfod アウトオブバンドインデックス ELFを分析または解析する必要がある場合、カーネル、ld.so、binutils、LIEF、goblin、readelfなど、誰もが同じパーサーを繰り返し再実装しています。 すべてのプロデューサーが同じシリアライザーを再実装しています。 フォーマット自体は信じられないほど簡潔で、ディスクスペースとネットワーク帯域幅が極端に貴重だった世界のために設計されています。 フォーマットの変更は困難です。詰め込まれているため、セクションをゼロアウトして新しいセクションを追加する必要があることがよくあります。 自己記述的なスキーマもありません。 ELF自体は非常に汎用的なフォーマットであり、慣習によって特定の方法で解釈されるデータセクションをサポートしていますが、フォーマットはそれを強制しません。 SQLiteは対照的な例です。 それらは自己記述的なフォーマットであり、非常に安定しています。 既存のコンシューマーを壊すことなく新機能のサポートを拡張し、幅広いクエリを効率的にサポートするように設計されています。 ELFをSQLiteに置き換えるとしたら、何が失われ、必要なすべての情報がSQLiteデータベースに表現できるでしょうか？ 答えは「はい」であり、驚くほどシンプルです。 §何が失われるか SELFファイルを実行するには2つのテーブルが必要です。 self_metaはキー/値ペアとしてのELFヘッダーです。 segmentsはロードイメージであり、BLOB内のバイトを含むプログラムヘッダーごとに1行です。 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 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); インデックスを含める能力は、.gnu.hashおよび.hash in ELFと同等ですが、手作業で作成されたブルームフィルターではなく、SQLiteによって維持される正規のBツリーインデックスです。 22.gnu.hashはブルームフィルターとバケットチェーンの組み合わせであり、シンボル検出中にミスをタッチせずにld.soがリジェクトできるように配置されています。 驚くほど多くのものが失われます。 .dynstrはなくなります。なぜなら、nameはTEXTであり、SQLiteはすでに文字列をインターンしているからです。 シンボルバージョニングは列であり、.gnu.version_r / .gnu.version_dの仕組みではありません。 文字列テーブルは不要になります。 ツール用に存在するメタデータ用の他のテーブルもあります。 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は、プログラムが必要とするライブラリのsonameを見つけるために、symbolsテーブルとsegmentsテーブルの結合であるneededテーブルに対するクエリです。 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では、登録はオフセット0のマジックと68のSELFに一致する数行です。 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) conv elf2self elf->conv 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はインタープリターです。 これはlibsqliteにリンクされた小さなCプログラムです。