GoKawiilI 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
... continue reading