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

$ 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.

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

CREATE TABLE segments (
  id      INTEGER PRIMARY KEY,
  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,
  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:

CREATE TABLE symbols (
  id      INTEGER PRIMARY KEY,
  name    TEXT NOT NULL,
  version TEXT,
  value   INTEGER,
  size    INTEGER,
  type    TEXT,
  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:

$ sqlite3 hello 'DELETE FROM sections; DELETE FROM notes; VACUUM;'
$ ./hello
Hello, world!

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.

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;

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

self-exec is the interpreter. It is a small C program linked against libsqlite3. Its implementation is remarkably similar to that of ld.so but it fetches the program headers and symbol table from the database instead of reading them from the ELF file. It maps the loadable segments into memory, relocates them, and jumps to the entry point.

Note self-exec has to stay an ELF file. An interpreter that also matches the registration recurses straight into -ELOOP.

§Dynamic linking

Running a static program was quick and easy but boring and unimaginative. The interesting part is dynamic linking, which is where the database shines.

I explored two different ways to do dynamic linking. The first is to keep ld.so and just replace the lookup with a SQL query via glibc rtld-audit interface, to quickly iterate on the design. The second is to replace ld.so entirely with a new dynamic linker that does the entire lookup and binding in SQL.

glibc’s rtld-audit interface lets an audit library intercept every shared object lookup (la_objsearch) before any filesystem search happens, dlopen included. The audit library can then answer the question “which library satisfies this symbol?” with a SQL query instead of walking the RUNPATH and LD_LIBRARY_PATH.

I was curious what a fully SQL dynamic linker would look like, so I prototyped one. It is called self-ld and it is a small C program that implements the dynamic linker entirely in SQL.

§Cost & Benchmark

The two things that often matter when replacing a well-established format are size and latency. How much bigger is a SELF file than an ELF file, and how much slower is it to run?

Size. A SELF file carries SQLite’s b-tree overhead and lands at roughly double the ELF. Stripping them and deleting them is a transaction. A stripped coreutils SELF is 1,794,048 B against the ELF’s 1,768,632 B, that is within 1%.

Latency. I benchmarked various binaries from a 15 KiB hello to a 42 MiB gdb linking 47 libraries.

There is a fixed ~5 ms to open SQLite and start the interpreter, plus a copy proportional to the image. That copy is worse than it looks, because the b-tree pages are not mapped into memory. Two processes running the same SELF binary do not share text pages the way a normally-mmap‘d ELF does, because the bytes are copied out of the b-tree rather than mapped.

§The system is a closure

A SQLite database though need not merely be a single executable. It can be a closure, a single file that contains a program and all of its transitive dependencies. The ldd output of a program is ambiguous: it only lists the sonames of the libraries it needs, not the specific files that satisfy those needs.

We can do the same in SELF by storing the resolved path of each edge in the database:

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,
  resolved_path TEXT REFERENCES objects(path)
);

self closure packs a binary and its transitive dependencies into one database with those edges filled in. Shared library resolution stops being a guess and becomes a foreign key and ldd becomes a JOIN.

§How far does this go? One file, one userland

I hope you’ve been with me so far, because this is where it gets really interesting. We can go even further and pack multiple closures into a single database.

I pointed self closure at every ELF binary on this system’s PATH: 723 executables, which pull in 400 distinct shared libraries. 1,123 objects, 346,386 symbols, 3,808 dependency edges, all as one SQLite file.

611.9 MiB of database against 644.4 MiB of ELF files. The whole userland, as one queryable file, is smaller than the files it came from. The b-tree cost that doubled a single hello amortises to nearly nothing across 1,123 objects and is roughly 6% over the actual program bytes.

Many common idioms we use in ELF immediately fall out of the database. For example, LD_PRELOAD is a row in a table rather than an environment variable. The preload table is a list of objects to map last, so their exports win. This means that turning LD_PRELOAD on and off is a transaction.

§Where it stands

The format is done and round-trips between ELF and SELF losslessly. The tooling is done and can query, modify, and pack closures. Lookup through SQL works on unmodified glibc programs perfectly and the native-SQL loader works enough to explore it as a possibility for ideas.

The whole thing is at fzakaria/selfdb. nix run .#self-vm boots a NixOS VM where hello is a SQLite database. 🙌

Nix lets us explore radical ideas like this. We can rebuild the world down to the Linux kernel if needed. We need not be constrained by the existing decisions and constraints of the past. We can explore new ideas and see what falls out. I hope you find this idea as interesting as I do.