Your executable is a SQLite database | Farid Zakaria’s Blog

Skip to content

I have been probably obsessed with two things in the last few years: Nix as a tool to explore<br>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.<br>Radical ideas are hard to sell, as you are working against the inertia of the established<br>solution.

One of the end results of that exploration was sqlelf,<br>a tool that lets you explore an ELF file declaratively using SQL.11I wrote a paper, arXiv:2405.03883,<br>that I failed to get published and a follow-up post on querying with it.<br>SELECT name FROM elf_symbols instead of fiddling with readelf and grep.<br>It was remarkably simple by leveraging virtual tables over the ELF: however I found it<br>to be a refreshing improvement to explore the ELF file format. I knew however that<br>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<br>and run.

$ file hello<br>hello: SQLite 3.x database, application id 0x53454c46, user version 1

$ ./hello<br>Hello, world!

$ sqlite3 hello 'SELECT soname FROM ldd'<br>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<br>data structures for performance, like a bloom filter for symbol lookup.

ELF mechanism<br>The database primitive it reinvents

.strtab / .dynstr<br>string interning

.hash / .gnu.hash<br>an index (CREATE INDEX)

section header table<br>sqlite_schema, a table of tables

st_name → offset into .strtab<br>a foreign key, done by hand

sh_offset / sh_size<br>the record layout of a b-tree page

.gnu.version_r<br>a column

objcopy --strip-debug<br>DELETE + VACUUM

ldconfig cache, debuginfod<br>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<br>bandwidth was at an extreme premium. Modifying the format is hard, you often have to zero out<br>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<br>are interpreted in specific ways but the format does not enforce it.

SQLite is the counter-example. They are a self-describing<br>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<br>pairs and segments is the load image, one row per program header with the bytes<br>in a BLOB:

CREATE TABLE segments (<br>-- original phdr index<br>id INTEGER PRIMARY KEY,<br>-- 'load' | 'tls' | 'stack' | 'relro'<br>type TEXT NOT NULL,<br>-- original file offset<br>offset INTEGER NOT NULL,<br>vaddr INTEGER NOT NULL,<br>filesz INTEGER NOT NULL,<br>memsz INTEGER NOT NULL,<br>r INTEGER, w INTEGER, x INTEGER,<br>align INTEGER NOT NULL DEFAULT 4096,<br>-- the segment bytes; NULL for pure BSS<br>content BLOB<br>);

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 (<br>id INTEGER PRIMARY KEY,<br>name TEXT NOT NULL,<br>-- 'GLIBC_2.2.5'<br>version TEXT,<br>value INTEGER,<br>size INTEGER,<br>-- 'func' | 'object' | 'tls' | ...<br>type TEXT,<br>-- 'global' | 'weak' | 'local'<br>bind TEXT,<br>defined INTEGER NOT NULL,<br>exported INTEGER NOT NULL<br>);<br>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.22.gnu.hash is a bloom filter plus bucket chains, laid out so<br>ld.so can reject a miss without touching the chain during symbol discovery.

Surprisingly a lot more falls out as well: .dynstr is gone, because name is TEXT and...