用 SQLite 替代 ELF 作为可执行文件格式的工程实践

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.

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.11I 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. 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.

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.

§ELF is a database that refuses to admit it

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.

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.

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.

§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:

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:

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.22.gnu.hash is a bloom filter plus bucket chains, laid out so ld.so can reject a miss without touching the chain during symbol discovery.

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:

All the tools that operate on ELF files for reading, reduce to queries over the database. Any tool that modifies an ELF file, like strip, can operate on the database within a transaction rather than performing fragile offset surgery: strip is a DELETE and VACUUM. patchelf is an UPDATE.

Any information missing from the schema can be easily exposed via a view. For example, ldd is a query over the needed table, which is a join of the symbols table with the segments table to find the sonames of the libraries needed by the program.

§How does it work?

SQLite reserves a 4-byte application_id at byte offset 68 of its header, for exactly this purpose. We stamp it SELF, so an ordinary SQLite database never matches:

We can now leverage binfmt_misc, the subsystem that allows you to invoke any binary as if it were native. We need only to register the magic to trigger on and an interpreter that will invoke our new file format.

On NixOS the registration is a few lines matching the SQLite magic at offset 0 and SELF at 68:

For now, I have a small tool elf2self that converts an ELF file into a SELF file. It is a simple postFixup hook you can opt into per package on NixOS. The tool reads the ELF, extracts the program headers and symbol table, and writes them into the SQLite database. We could look at extending gcc or ld to emit SELF directly, but for now this is a simple way to explore the idea.