Your executable is a SQLite database

For the past few years, the reporter has been fascinated by two ideas: Nix as a tool to explore innovative concepts and replacing ELF with SQLite as an executable format. These two ideas seem to complement each other well. The reporter explored this notion during their PhD but found the feedback from others unconvincing. Radical concepts are difficult to promote because they challenge the status quo.

The result of this exploration was sqlelf, a tool that allows for exploring ELF files using SQL. The reporter authored a paper (arXiv:2405.03883) and a follow-up post on querying with this tool, but they failed to get it published.

Despite this setback, the reporter remains convinced that there is more to be done. With the recent advancements in LLMs, the reporter finds it compelling to revisit these ideas and explore further. Specifically, can ELF be replaced with SQLite as an executable format?

The reporter developed a prototype called SELF, the Structured Executable & Linkable Format, which is available on GitHub. The idea of replacing ELF with SQLite is intriguing, as ELF already functions like a database, albeit with manual implementation of database primitives and numerous data structures for performance. By leveraging virtual tables over the ELF, the reporter found it refreshing to explore the ELF file format.

A SELF file requires two tables to run: self_meta contains ELF header information as key/value pairs, and segments hold the load image, with one row per program header containing the bytes in a BLOB. This approach eliminates many ELF sections and the .gnu.hash index, replacing them with a single table and a single b-tree index for symbol information. This design is more efficient than ELF's .gnu.hash and .hash, which are bloom filters and bucket chains, respectively.

Other tables in SELF include metadata such as sections, notes, and dynamic entries. Deleting these tables does not affect program functionality, making strip a simple transaction. Tools that operate on ELF files now reduce to queries over the database, simplifying the process.

To run SELF files, the reporter created an interpreter called self-exec, which is a small C program linked against libsqlite3. The interpreter maps loadable segments into memory, relocates them, and jumps to the entry point. While self-exec is an ELF file, it interacts with the SQLite database to perform the necessary operations.

Dynamic linking can be achieved using either an adapted version of ld.so with a SQL query for symbol lookup or by modifying existing tools to work with the SELF format. The reporter has an elf2self tool that converts ELF files into SELF format and a small NixOS integration to automate the conversion process. This approach allows for exploring the concept further and potentially extending gcc or ld to emit SELF files directly.