Executable Is a SQLite Database

可执行文件即 SQLite 数据库

I have been probably obsessed with two things in the last few years: Nix as a tool to explore innovative ideas that require the capability to rebuild the world and replacing ELF with SQLite as an executable format. You might have noticed that these two ideas are well suited to each other. 在过去的几年里，我可能一直痴迷于两件事：一是将 Nix 作为探索创新想法的工具，因为它具备重构世界的能力；二是将 ELF 替换为 SQLite 作为可执行文件格式。你可能已经注意到，这两个想法非常契合。

I explored the idea during my PhD thesis but found feedback from others unmotivating. Radical ideas are hard to sell, as you are working against the inertia of the established solution. One of the end results of that exploration was sqlelf, a tool that lets you explore an ELF file declaratively using SQL. I wrote a paper, arXiv:2405.03883, that I failed to get published and a follow-up post on querying with it. SELECT name FROM elf_symbols instead of fiddling with readelf and grep. It was remarkably simple by leveraging virtual tables over the ELF: however I found it to be a refreshing improvement to explore the ELF file format. I knew however that there is still something much bigger to be done. I never let the idea go and with the recent improvements with LLMs, I find it compelling to revisit these ideas to explore further. 我在博士论文期间探索过这个想法，但得到的反馈并不令人振奋。激进的想法很难推销，因为你是在对抗既定解决方案的惯性。那次探索的成果之一是 sqlelf，这是一个让你能够使用 SQL 以声明式方式探索 ELF 文件的工具。我写了一篇论文（arXiv:2405.03883）但没能发表，随后又写了一篇关于如何用它进行查询的后续文章。使用 SELECT name FROM elf_symbols 而不是摆弄 readelf 和 grep。通过在 ELF 之上利用虚拟表，这变得非常简单：然而，我发现这对于探索 ELF 文件格式来说是一个令人耳目一新的改进。但我知道，还有更宏大的事情可以做。我从未放弃这个想法，随着近期大语言模型（LLM）的进步，我觉得重新审视这些想法并进一步探索非常有意义。

Specifically, can we replace ELF with SQLite as an executable format? 🤔 Not “a database that describes an executable”, but the actual file you chmod +x and run. 具体来说，我们能否用 SQLite 替换 ELF 作为可执行文件格式？🤔 不是“描述可执行文件的数据库”，而是你通过 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

I developed a pretty fleshed out prototype. It is called SELF, the Structured Executable & Linkable Format, because I am unoriginal. It is on GitHub if you are interested. I’m surprised about all the interesting things that fall out of this idea. 我开发了一个相当完善的原型。它被称为 SELF（结构化可执行与可链接格式），因为我没什么创意。如果你感兴趣，它已经在 GitHub 上了。我惊讶于这个想法所带来的所有有趣的可能性。

§ELF is a database that refuses to admit it

§ELF 是一个拒绝承认自己是数据库的数据库

Working through my PhD, I realized something that bugged me. ELF is already a database. It just implements many database primitives by hand, along with a surprising number of data structures for performance, like a bloom filter for symbol lookup. 在攻读博士学位期间，我意识到了一件让我困扰的事情。ELF 本身就是一个数据库。它只是手动实现了许多数据库原语，以及大量令人惊讶的用于性能优化的数据结构，例如用于符号查找的布隆过滤器（bloom filter）。

ELF mechanism | The database primitive it reinvents

ELF 机制	它所重造的数据库原语
.strtab / .dynstr	string interning (字符串驻留)
.hash / .gnu.hash	an index (CREATE INDEX) (索引)
section header table	sqlite_schema, a table of tables (表结构表)
st_name → offset into .strtab	a foreign key, done by hand (手动实现的外键)
sh_offset / sh_size	the record layout of a b-tree page (B-tree 页的记录布局)
.gnu.version_r	a column (列)
objcopy —strip-debug	DELETE + VACUUM
ldconfig cache, debuginfod	out-of-band indexes over the above (带外索引)

If you ever have to analyze or parse ELF, the kernel, ld.so, binutils, LIEF, goblin, readelf, you are re-implementing the same parser over and over again. Every producer re-implements the same serializer. The format itself is incredibly terse, designed for a world where disk space and network bandwidth was at an extreme premium. Modifying the format is hard, you often have to zero out sections and add new ones since it is packed so tightly. There is also no self-describing schema. ELF itself is a very generic format that supports sections of data that by convention are interpreted in specific ways but the format does not enforce it. 如果你曾经需要分析或解析 ELF（无论是内核、ld.so、binutils、LIEF、goblin 还是 readelf），你其实是在一遍又一遍地重复实现同一个解析器。每个生产者都在重复实现同一个序列化器。这种格式本身极其简洁，是为磁盘空间和网络带宽极其昂贵的时代设计的。修改这种格式非常困难，由于它打包得太紧凑，你通常必须清空某些段并添加新的段。此外，它也没有自描述的模式（schema）。ELF 本身是一种非常通用的格式，支持按惯例以特定方式解释的数据段，但格式本身并不强制执行这些规则。

SQLite is the counter-example. They are a self-describing format that is extremely stable. It is designed to be extended to support new features without breaking existing consumers and supporting a wide range of queries performantly. If we were to replace ELF with SQLite, what would fall out and can all of the necessary information be represented in a SQLite database? The answer is yes, and it is surprisingly simple. SQLite 则是一个反例。它是一种极其稳定的自描述格式。它的设计初衷是在不破坏现有使用者的情况下扩展新功能，并高效地支持各种查询。如果我们用 SQLite 替换 ELF，会发生什么？所有必要的信息都能在 SQLite 数据库中表示吗？答案是肯定的，而且出奇地简单。

§What falls away

§哪些东西会被简化掉

A SELF file needs two tables to run: self_meta is the ELF header as key/value pairs and segments is the load image, one row per program header with the bytes in a BLOB. 一个 SELF 文件只需要两张表即可运行：self_meta 是以键值对形式存储的 ELF 头，segments 是加载镜像，每一行对应一个程序头，字节数据存储在 BLOB 中。

CREATE TABLE segments (
  -- original phdr index
  id INTEGER PRIMARY KEY,
  -- 'load' | 'tls' | 'stack' | 'relro'
  type TEXT NOT NULL,
  -- original file offset
  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,
  -- the segment bytes; NULL for pure BSS
  content BLOB
);

A single table for the symbol table replaces many of the ELF sections and the .gnu.hash index. It is a single table with a single index. 一张用于符号表的表可以取代许多 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);

Our capability to include an index is equivalent to .gnu.hash and .hash in ELF, but it is a proper b-tree index maintained by SQLite instead of a hand-rolled bloom filter. Surprisingly a lot more falls out as well: .dynstr is gone, because name is TEXT and SQLite already interns strings, symbol versioning is a column, not the .gnu.version_r / .gnu.version_d contraption and there is no need for a strings table. Other tables exist as well for metadata which exist for tooling: sections, notes, dynamic_entries. Delete them and the program still runs, which means strip(1) is a transaction. 我们包含索引的能力等同于 ELF 中的 .gnu.hash 和 .hash，但它是由 SQLite 维护的真正的 B-tree 索引，而不是手动编写的布隆过滤器。令人惊讶的是，更多东西被简化了：.dynstr 不见了，因为 name 是 TEXT 类型，而 SQLite 已经内置了字符串驻留；符号版本控制现在是一列，而不是 .gnu.version_r / .gnu.version_d 那种复杂的结构；也不再需要字符串表。其他用于工具的元数据表（如 sections, notes, dynamic_entries）也存在。删除它们，程序依然可以运行，这意味着 strip(1) 操作现在就是一个事务。