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. 1 instead of fiddling with and . 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 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. 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, , binutils, LIEF, goblin, , 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. A SELF file needs two tables to run: is the ELF header as key/value pairs and is the load image, one row per program header with the bytes in a : A single table for the symbol table replaces many of the ELF sections and the index. It is a single table with a single index: Our capability to include an index is equivalent to and in ELF, but it is a proper b-tree index maintained by SQLite instead of a hand-rolled bloom filter. 2 Surprisingly a lot more falls out as well: is gone, because is and SQLite already interns strings, symbol versioning is a column, not the / contraption and there is no need for a table. Other tables exist as well for metadata which exist for tooling: , , . Delete them and the program still runs, which means 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 , can operate on the database within a transaction rather than performing fragile offset surgery: is a and . is an . Any information missing from the schema can be easily exposed via a view. For example, is a query over the table, which is a join of the table with the table to find the sonames of the libraries needed by the program. SQLite reserves a 4-byte at byte offset 68 of its header, for exactly this purpose. We stamp it , 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 at 68: For now, I have a small tool that converts an ELF file into a SELF file. It is a simple 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 or to emit SELF directly, but for now this is a simple way to explore the idea. is the interpreter. It is a small C program linked against . Its implementation is remarkably similar to that of 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 has to stay an ELF file. An interpreter that also matches the registration recurses straight into . 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 and just replace the lookup with a SQL query via rtld-audit interface, to quickly iterate on the design. The second is to replace 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 ( ) before any filesystem search happens, included. The audit library can then answer the question “which library satisfies this symbol?” with a SQL query instead of walking the and . Stock maps and relocates it, so the full gamut of glibc features work: lazy PLT, IFUNCs, TLS and symbol versioning, while library storage are rows and library lookups are queries. I was curious what a fully SQL dynamic linker would look like, so I prototyped one. It is called and it is a small C program that implements the dynamic linker entirely in SQL. It is a proof-of-concept, but it works. It maps every object’s segments, publishes their exports, and for each relocation patches the GOT and jumps to the start. 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. Similar to ELF binaries, most of that is recoverable, because the overhead is mostly the optional tables for debugging and tooling. Stripping them and deleting them is a transaction. A stripped SELF is 1,794,048 B against the ELF’s 1,768,632 B, that is within 1% . We will see though that there are interesting ways to amortise the overhead even more which I found very unique and interesting. Latency. I benchmarked various binaries from a 15 KiB to a 42 MiB 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- ‘d ELF does, because the bytes are copied out of the b-tree rather than mapped. 3 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 output of a program is ambiguous: it only lists the sonames of the libraries it needs, not the specific files that satisfy those needs. Nix improves upon this by explicitly resolving every edge to a specific store path via the use of . 4 We can do the same in SELF by storing the resolved path of each edge in the database: 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 becomes a 🤯: This single database is a closure of the executable and its five libraries: six objects, segment bytes and all, in one 4.8 MiB file. There is no soname ambiguity inside a closure, because a closure by construction contains exactly one provider per edge. 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 at every ELF binary on this system’s : 723 executables, which pull in 400 distinct shared libraries. 1,123 objects, 346,386 symbols, 3,808 dependency edges, all as one SQLite file . Turns out when you do that, the database is much smaller than you would expect. 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 amortises to nearly nothing across 1,123 objects and is roughly 6% over the actual program bytes. The libraries and closure are shared across the executables very similar to how Nix might share them across multiple closures, if the store-path was the same. If every root shipped its own private closure (i.e. the AppImage model), the same 723 programs would come to 5.53 GiB but the deduplication of libraries and symbols falls out naturally from the database schema. Many common idioms we use in ELF immediately fall out of the database. For example, is a row in a table rather than an environment variable. The table is a list of objects to map last, so their exports win. This means that turning on and off is a transaction. We were able to accomplish an atomic across a whole userland in one file, “interpose a tracing everywhere, then ” is a single transaction. 😈 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 . boots a NixOS VM where 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. I wrote a paper, arXiv:2405.03883 , that I failed to get published and a follow-up post on querying with it . ↩ is a bloom filter plus bucket chains, laid out so can reject a miss without touching the chain during symbol discovery. ↩ You might notice that (274 KiB, 27 libraries) starts slower than ELF (4.6 MiB, 5 libraries). That is doing work proportional to the number of objects rather than the number of bytes, which I have complained about before . ↩ I have written about on Nix before such as making it redundant or speeding it up . ↩ I wrote a paper, arXiv:2405.03883 , that I failed to get published and a follow-up post on querying with it . ↩ is a bloom filter plus bucket chains, laid out so can reject a miss without touching the chain during symbol discovery. ↩ You might notice that (274 KiB, 27 libraries) starts slower than ELF (4.6 MiB, 5 libraries). That is doing work proportional to the number of objects rather than the number of bytes, which I have complained about before . ↩ I have written about on Nix before such as making it redundant or speeding it up . ↩
Sql
Programming