SQLite で ELF バイナリを実行する：SELF (Structured Executable & Linkable Format) の探求

近年、私は主に 2 つの技術に夢中になってきました。 一つは世界を再構築する能力を持つ革新的なツールである「Nix」。 もう一つは、実行ファイル形式として ELF（Executable and Linkable Format） を代替する 「SQLite」 を採用するというものです。

これら 2 つの着想は実に相性が良すぎます。私は博士課程時代にこの考え方を模索しましたが、既存の解決策への慣れ親しんだ人々の**惰性（Inertia）**に直面し、発表されることは叶いませんでした。しかし、このアイデアを放棄することはありませんでした。LLM の進歩に伴い、再度このコンセプトを深掘りする中で、驚くべき現実的な成果が生まれました。

§ 概要：SELF とは何なのか？

私が開発したのは、「実行可能コードを記述するデータベース」ではなく、実際に

chmod +x

GitHub で確認できる興味深いプロトタイプでは、ELF ファイルの構造を SQLite のテーブルに変換し、それを直接プログラムとして実行します。

動作のイメージ

# ELF ヘッダー情報に "SELF" と書かれている
$ file hello
hello: SQLite 3.x database, application id 0x53454c46, user version 1

# 通常の実行
$ ./hello
Hello, world!

# SQL クエリでライブラリ依存を確認
$ sqlite3 hello 'SELECT soname FROM ldd'
libc.so.6

§ ELF は「自覚していないデータベース」

ELF も実は既にデータベースですが、多くの機能は手動実装されています。

• シンボルルックアップ: Bloom Filter (ブルームフィルタ) 等。
• ツールの冗長性: カーネル、

  ld.so

  、binutils など、同じパースロジックを各自が再実装しています。
• 形式の硬さ: スキーマは自己記述的ではなく、セクション追加にはゼロ化が必要などの変更が困難です。

対照的に、SQLite は極めて安定した自己記述的な形式で、既存データを壊さずに新機能をサポートできます。ELF を SQLite に置き換えることで、以下のような劇的な変化が可能になります。

§ 何が残されるか (What falls away)

SELF ファイルを実行するには以下の 2 つのテーブルが必須です：

1. segments

   : ELF ヘッダーやロードイメージを保存（BLOB でプログラムヘッダを格納）。

2. symbols

   : シンボルテーブル全体を単一の表に集約（

   .gnu.hash

   の代わりとして正規の B-Tree インデックスを使用）。

メタデータの削減と簡素化

• .dynstr

  の省略:

  name

  が TEXT 型のため、SQLite は文字列を自動的にインターン（共有）するからです。
• バージョニングの単純化:

  .gnu.version_r

  のような複雑な機構は単なるカラムになり、文字列テーブルが不要になります。

デバッグ情報の削除 (

strip

)

プログラムが動作し続ける限り、不要なメタデータを削除できます。これは

VACUUM

DELETE

# ライブラリ依存の検索 (ldd)
$ sqlite3 hello 'SELECT soname FROM ldd' 
libc.so.6

# シンボル一覧 (nm)
$ sqlite3 hello 'SELECT name,version FROM imports LIMIT 3'
__libc_start_main|GLIBC_2.34
puts|GLIBC_2.2.5

# セクション情報の削除 (strip)
$ sqlite3 hello "DELETE FROM sections; DELETE FROM notes; VACUUM;"
# サイズ削減: 57344 -> 49152 bytes

# 動作確認
$ ./hello
Hello, world!

スキーマの拡張とビュー (View)

欠落している情報は、ビュー（VIEW）を通じて容易にアクセスできます。

ldd

nm

-- エクスポートされたシンボル
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;

-- ライブラリ依存一覧 (ldd)
CREATE VIEW ldd     AS 
  SELECT ord, soname FROM needed ORDER BY ord;

§ それはどのように機能するか？

ファイル形式の識別

SQLite ヘッダー（オフセット 68 バイト）には、通常の SQLite と区別するための

application_id

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

カーネルレベルでの実行 (

binfmt_misc

)

Linux カーネルの

binfmt_misc

• NixOS では数行の設定で、SQLite のマジック番号（オフセット 0）と SELF（オフセット 68）を登録できます。

boot.binfmt.registrations.self = {
  recognitionType = "magic";
  offset = 0;
  magicOrExtension = "SQLite format 3\\x00" + ... + "SELF";
  mask = "\\xff..\\x00..\\x00";
  interpreter = "${self-exec}/bin/self-exec";
};

エグジュート時の仕組み (

elf2self

)

ELF ファイルを SELF に変換するツール

elf2self

postFixup

1. 変換: ELF → SQLite データベース (

   elf2self

   )
2. 識別: カーネルがマジック番号 "SELF" を検知
3. インタープリタ: 予約されたバイトオフセット（68）を参照し、

   libsqlite3

   をリンクした

   self-exec

   が起動

graph LR;
    elf("elf<br/>hello") -- conv --> self("self<br/>hello<br/>(SQLite db)");
    magic -- "SELF@68" --> binfmt_misc["binfmt_misc"];
    binfmt_misc --> interp["interpreter (self-exec)"];
    interp --> run["running<br/>process"];
    
    subgraph krn ["kernel"]
        direction TB;
        execve["execve()"]
    end
    
    elf -- "magic SELF@68" -.-> magic;
    note["Note:<br/>self-exec は ELF ファイルである必要があります。<br>再帰するインタープリタは -ELOOP になります。"] -.-> self-exec["self-exec"];

インタープリタ (

self-exec

)

self-exec

ld.so

§ ダイナミックリンキング

静的リンクは簡単ですが面白くありません。ダイナミックリンキングこそが、データベースの真価を発揮する場所です。 2 つのアプローチを試みました：

1. rtld-audit:

   glibc

   のインタフェースを使い、ルックアップ処理を SQL クエリに置き換える（素早い反復）。
2. 完全置換: ルックアップ全体を SQL で実装し、

   ld.so

   を完全に置き換える (

   self-ld

   )。

rtld-audit を使ったルックアップ

glibc の

rtld-audit

dlopen

RUNPATH

# ライブラリを削除
$ rm libgreet.so.1
$ ./app # エラーが発生

# SQL を通じたルックアップ (rtld-audit)
$ SELF_SYSTEM_DB=system.db LD_AUDIT=libself-audit.so ./app
Hello, world, from a SQLite library!

完全 SQL 実装のダイナミックリンカー (

self-ld

)

オブジェクトのマッピング、エクスポート情報の公開、GOT パッチ適用など、すべての処理を SQL で行います。

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 ファイルは B-Tree オーバーヘッドの影響で、ELF の約 2 倍のサイズになります。ただし、不要なテーブル（デバッグ情報）をストリップすれば、1% 以内の差異まで削減可能です。

分析: 過剰なオーバーヘッドの多くは除去可能ですが、コアな構造（オブジェクト、セグメント、シンボル）は維持されます。

レイテンシ

• SQLite を開き、インタープリタを起動するには約 5 ms かかります。
• データベースの B-Tree ページがメモリにマッピングされていないため、イメージサイズに比例したコピーコストが発生します。

  • curl

    (274 KiB) と

    git

    (4.6 MiB) では、ライブラリ数の違いよりもコピーコストの影響を強く受けます。

§ システムはクロージャ（閉じた環境）である

SELF は単一ファイルではなく、プログラムとその**推移的依存関係を含むクロージャ（Closure）**として機能します。

• 従来の

  ldd

  は曖昧なライブラリ名 (

  soname

  ) しか出力しません。
• SELF は

  needs

  テーブルに解決済みパス (

  resolved_path

  ) を格納し、その曖昧さを解消します。

# クロージャ化 (self closure)
$ self closure "$(readlink -f $(command -v ls))" coreutils.db
ls + closure -> coreutils.db

# 依存関係の明示的なパス表示
$ sqlite3 coreutils.db "SELECT soname, resolved_path FROM needs WHERE is_root = 1"
libc.so.6          /nix/store/xxxxx/lib/libc-2.39.so
libgmp.so.10       /nix/store/yyyyy/lib/libgmp-12.so

これにより、単一のデータベースに実行ファイルと依存ライブラリをパックし、

soname

§ これはどこまで可能か？一つのファイル、一つのユーザーランド

さらに進んで、システム全体（Userland）のすべての ELF バイナリに対してクロージャ化を行いました。

• 対象: 723 つの実行可能ファイル、400 の異なる共有ライブラリ。
• 結果: 1,123 個のオブジェクト、346,386 個のシンボル、3,808 本の依存エッジが、1 つの SQLite ファイル (611.9 MiB) に収まりました。

これにより、以下のような革新的な機能が実現可能です：

• ライブラリ共有: 同じ

  libc.so.6

  は複数のクロージャ間で共有されます（ストアパス同一）。
• LD_PRELOAD のトランザクション化: 環境変数ではなくテーブル内の一行として表現され、オン/オフをトランザクション (

  BEGIN

  ...

  COMMIT

  ) で管理できます。

# Preload の動的追加 (1 行の INSERT)
sqlite3 system.db "INSERT INTO preload VALUES (0, 'libmul.so.1.self');"
./app.self  # 動作変化

# プリロードの即時無効化 (DELETE)
sqlite3 system.db 'DELETE FROM preload;'

§ 現在の立ち位置

• 形式: 完成。ELF と SELF の間でのラウンドトリップは無損失で行えます。
• ツールング: クエリ、変更、クロージャパッキングが可能。
• 互換性: glibc プログラムを修正せずとも SQL 通じたルックアップで動作し、ネイティブ SQL ロADER も検証には十分です。

fzakaria/selfdb でコードを確認できます。

nix run .#self-vm

Nix には、世界を再構築する自由があります。既存の決定や制約に縛られず、新たなアイデアを探求し、そこから何が生じるかを見ることも可能です。

参考文献:

1. sqlelf 論文
2. [.gnu.hash 実装詳細]
3. [B-Tree マッピングと mmap のパフォーマンス分析]
4. [NixOS での RUNPATH 最適化]