Your executable is a SQLite database

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. $ 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. ELF mechanism The database primitive it reinvents .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 .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. 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?

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: $ xxd -s 64 -l 8 hello 00000040: 0000 0001 5345 4c46 ....SELF 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: boot.binfmt.registrations.self = { recognitionType = "magic"; offset = 0; # bytes 0-15, 68-71 magicOrExtension = "SQLite format 3\\x00" + ... + "SELF"; # ignore the middle mask = "\\xff..\\x00..\\xff"; interpreter = "${self-exec}/bin/self-exec"; }; 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. 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 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.