Jouw executable is een SQLite-database

Ik heb dit idee verkend tijdens mijn PhD-thesis, maar merkte dat de feedback van anderen onmotiverend was. Radicale ideeën zijn moeilijk te verkopen, omdat je werkt tegen de inertie van de gevestigde oplossing in.

Een van de resultaten van dat onderzoek was sqlelf, een tool waarmee je een ELF-bestand declaratief kunt verkennen met behulp van SQL. Ik schreef hierover een paper (arXiv:2405.03883), die ik niet gepubliceerd kreeg, en een vervolgbericht over het uitvoeren van queries ermee. In plaats van te worstelen met readelf en grep, kon je nu SELECT name FROM elf_symbols gebruiken.

Door gebruik te maken van virtuele tabellen over de ELF was dit opmerkelijk eenvoudig, en ik vond het een verfrissende verbetering in het verkennen van het ELF-bestandsformaat. Ik wist echter dat er nog iets veel groters gedaan kon worden.

Ik ben het idee nooit verloren en met de recente verbeteringen in LLM's vind ik het boeiend om deze ideeën verder uit te diepen. Specifiek: kunnen we ELF vervangen door SQLite als executable-formaat? 🤔

Niet "een database die een executable beschrijft", maar het eigenlijke bestand dat je chmod +x geeft en uitvoert.

$ 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

Ik heb een vrij uitgebreid prototype ontwikkeld. Het heet SELF (Structured Executable & Linkable Format), omdat ik niet origineel ben. Het staat op GitHub voor wie geïnteresseerd is. Ik ben verrast door alle interessante zaken die voortvloeien uit dit idee.

ELF is een database die weigert het toe te geven

Tijdens mijn PhD realiseerde ik me iets dat me stoorde: ELF is eigenlijk al een database. Het implementeert alleen veel database-primitieven handmatig, samen met een verrassend aantal datastructuren voor prestaties, zoals een bloom-filter voor symboolopzoeking.

ELF-mechanismeDe database-primitief die het heruitvindt
.strtab / .dynstrstring interning
.hash / .gnu.hasheen index (CREATE INDEX)
section header tablesqlite_schema, een tabel van tabellen
st_name → offset naar .strtabeen foreign key, handmatig gedaan
shoffset / shsizede record-layout van een b-tree pagina
.gnu.version_reen kolom
objcopy --strip-debugDELETE + VACUUM
ldconfig cache, debuginfodout-of-band indexes over bovenstaande

Als je ooit een ELF moet analyseren of parsen (denk aan de kernel, ld.so, binutils, LIEF, goblin, readelf), dan implementeer je telkens opnieuw dezelfde parser. Elke producent implementeert dezelfde serializer.

Het formaat zelf is ongelooflijk beknopt, ontworpen voor een wereld waarin schijfruimte en netwerkbandbreedte extreem schaars waren. Het formaat wijzigen is moeilijk; vaak moet je secties op nul zetten en nieuwe toevoegen omdat het zo compact is gepakt. Er is ook geen zelfbeschrijvend schema. ELF is een zeer generiek formaat dat datasecties ondersteunt die volgens conventie op specifieke manieren worden geïnterpreteerd, maar het formaat dwingt dit niet af.

SQLite is het tegenovergestelde. Het is een zelfbeschrijvend formaat dat extreem stabiel is. Het is ontworpen om uitgebreid te worden om nieuwe functies te ondersteunen zonder bestaande consumenten te breken, en om een breed scala aan queries performant te ondersteunen.

Als we ELF zouden vervangen door SQLite, wat zou er dan gebeuren en kan alle noodzakelijke informatie in een SQLite-database worden gerepresenteerd? Het antwoord is ja, en het is verrassend eenvoudig.

Wat valt er weg?

Een SELF-bestand heeft twee tabellen nodig om te kunnen draaien: self_meta (de ELF-header als key/value-paren) en segments (het load-image, één rij per program header met de bytes in een BLOB):

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

Een enkele tabel voor de symbooltabel vervangt veel van de ELF-secties en de .gnu.hash-index. Het is één tabel met één index:

CREATE TABLE symbols (
    id      INTEGER PRIMARY KEY,
    name    TEXT NOT NULL,
    -- 'GLIBC_2.2.5'
    version TEXT,
    value   INTEGER,
    size    INTEGER,
    -- 'func' | 'object' | 'tls' | ...
    type    TEXT,
    -- 'global' | 'weak' | 'local'
    bind    TEXT,
    defined  INTEGER NOT NULL,
    exported INTEGER NOT NULL
);
CREATE INDEX idx_symbols_name ON symbols(name, version);

Ons vermogen om een index op te nemen is equivalent aan .gnu.hash en .hash in ELF, maar het is een proper b-tree index die door SQLite wordt beheerd in plaats van een handmatig gemaakt bloom-filter. .gnu.hash is een bloom-filter plus bucket-chains, zo ingericht dat ld.so een 'miss' kan afwijzen zonder de chain aan te raken tijdens symboolontdekking.

Verrassend genoeg valt er nog veel meer weg: .dynstr verdwijnt, omdat name TEXT is en SQLite strings al intern beheert; symbol-versioning is een kolom in plaats van het .gnu.versionr / .gnu.versiond constructie, en er is geen behoefte aan een strings-tabel.

Er bestaan ook andere tabellen voor metadata die bedoeld zijn voor tooling: sections, notes, dynamic_entries. Verwijder deze en het programma draait nog steeds, wat betekent dat strip(1) een transactie is:

# ldd(1)
$ sqlite3 hello 'SELECT soname FROM ldd'
libc.so.6

# nm -D --undefined
$ sqlite3 hello 'SELECT name,version FROM imports LIMIT 3'
__libc_start_main|GLIBC_2.34
_ITM_deregisterTMCloneTable|
puts|GLIBC_2.2.5

# readelf -l
$ sqlite3 hello "SELECT type,vaddr,memsz,r,w,x FROM segments WHERE type='load'"
load|0|1744|1|0|0
load|4096|361|1|0|1
load|8192|312|1|0|0
load|15768|640|1|1|0

# strip(1)
$ sqlite3 hello 'DELETE FROM sections; DELETE FROM notes; VACUUM;'
# 57344 -> 49152 bytes
# draait nog steeds, de optionele tabellen waren optioneel
$ ./hello
Hello, world!

Alle tools die ELF-bestanden lezen, reduceren tot queries over de database. Elke tool die een ELF-bestand wijzigt, zoals strip, kan opereren op de database binnen een transactie in plaats van fragiele offset-chirurgie uit te voeren: strip is een DELETE en VACUUM. patchelf is een UPDATE.

Informatie die ontbreekt in het schema kan eenvoudig worden blootgesteld via een view. Bijvoorbeeld, ldd is een query over de needed-tabel, wat een join is van de symbols-tabel met de segments-tabel om de sonames van de benodigde bibliotheken te vinden.

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;

Hoe werkt het?

SQLite reserveert een 4-byte application_id op byte-offset 68 van zijn header, precies voor dit doel. We stempelen deze als SELF, zodat een gewone SQLite-database nooit overeenkomt:

$ xxd -s 64 -l 8 hello
00000040: 0000 0001 5345 4c46                      ....SELF

We kunnen nu gebruikmaken van binfmt_misc, het subsysteem dat toelaat om elk binair bestand aan te roepen alsof het native is. We hoeven alleen de "magic" te registreren waarop getriggerd moet worden en een interpreter die ons nieuwe bestandsformaat zal aanroepen.

Op NixOS bestaat de registratie uit een paar regels die matchen met de SQLite-magic op offset 0 en SELF op 68:

boot.binfmt.registrations.self = {
  recognitionType = "magic";
  offset = 0;
  # bytes 0-15, 68-71
  magicOrExtension = "SQLite format 3\\x00" + ... + "SELF";
  # negeer het midden
  mask = "\\xff..\\x00..\\xff";
  interpreter = "${self-exec}/bin/self-exec";
};

Voor nu heb ik een kleine tool, elf2self, die een ELF-bestand converteert naar een SELF-bestand. Het is een eenvoudige postFixup-hook die je per pakket op NixOS kunt inschakelen. De tool leest de ELF, extraheert de program headers en de symbooltabel, en schrijft deze in de SQLite-database. We zouden kunnen kijken naar het uitbreiden van gcc of ld om direct SELF te emitteren, maar voor nu is dit een eenvoudige manier om het idee te verkennen.

Workflow: ELF (hello) → elf2self (converter) → SELF (SQLite db) → binfmt_misc → self-exec (interpreter) → Running process.

self-exec is de interpreter. Het is een klein C-programma gelinkt tegen libsqlite3. De implementatie is opmerkelijk vergelijkbaar met die van ld.so, maar het haalt de program headers en de symbooltabel uit de database in plaats van ze uit het ELF-bestand te lezen. Het mapt de loadbare segmenten in het geheugen, relocate ze en springt naar het entry point.

Opmerking: self-exec moet zelf een ELF-bestand blijven. Een interpreter die ook matcht met de registratie zou direct recurseren in -ELOOP.

Dynamische linking

Het draaien van een statisch programma was snel en eenvoudig, maar saai. Het interessante deel is dynamische linking, waar de database echt schittert.

Ik heb twee verschillende manieren voor dynamische linking verkend. De eerste is om ld.so te behouden en alleen de lookup te vervangen door een SQL-query via de rtld-audit interface van glibc, om zo snel te kunnen itereren op het ontwerp. De tweede is om ld.so volledig te vervangen door een nieuwe dynamische linker die de gehele lookup en binding in SQL doet.

De rtld-audit interface van glibc laat een audit-library elke shared object lookup (laobjsearch) onderscheppen voordat er een zoekopdracht op het bestandssysteem plaatsvindt, inclusief dlopen. De audit-library kan dan de vraag "welke library voldoet aan dit symbool?" beantwoorden met een SQL-query in plaats van de RUNPATH en LDLIBRARY_PATH te doorlopen. De standaard ld.so mapt en relocate het, zodat alle glibc-functies werken: lazy PLT, IFUNCs, TLS en symbol versioning, terwijl library-opslag rijen zijn en library-lookups queries.

# geen ELF library overal op disk
$ rm libgreet.so.1
$ ./app
./app: error while loading shared libraries:
libgreet.so.1: cannot open ...
$ self scan --db system.db .
$ SELF_SYSTEM_DB=system.db LD_AUDIT=libself-audit.so ./app
Hello, world, from a SQLite library!

Ik was benieuwd hoe een volledig SQL-dynamische linker eruit zou zien, dus ik heb er een prototype van gemaakt. Het heet self-ld en is een klein C-programma dat de dynamische linker volledig in SQL implementeert. Het is een proof-of-concept, maar het werkt. Het mapt de segmenten van elk object, publiceert hun exports, en patcht voor elke relocation de GOT en springt naar het begin.

SELECT s.value + o.load_bias
FROM   relocations r
JOIN   symbols s ON r.symbol = s.id
JOIN   objects o ON s.object = o.id
WHERE  r.id = ?
ORDER BY o.load_order
LIMIT  1;

Kosten & Benchmark

De twee zaken die vaak van belang zijn bij het vervangen van een gevestigd formaat zijn grootte en latentie. Hoeveel groter is een SELF-bestand dan een ELF-bestand, en hoe veel langzamer is het om uit te voeren?

Grootte. Een SELF-bestand draagt de b-tree overhead van SQLite en is ongeveer twee keer zo groot als de ELF. Net als bij ELF-binaries is het meeste hiervan herstelbaar, omdat de overhead voornamelijk bestaat uit optionele tabellen voor debugging en tooling. Het strippen en verwijderen hiervan is een transactie. Een gestripte coreutils SELF is 1.794.048 B tegenover de 1.768.632 B van de ELF; dat is een verschil van minder dan 1%. We zullen zien dat er interessante manieren zijn om deze overhead verder te amortiseren.

Latentie. Ik heb verschillende binaries gebenchmarkt, van een 15 KiB hello tot een 42 MiB gdb die 47 libraries linkt. Er is een vaste overhead van ongeveer 5 ms om SQLite te openen en de interpreter te starten, plus een kopie die proportioneel is aan het image. Die kopie is erger dan het lijkt, omdat de b-tree pagina's niet in het geheugen worden gemapt. Twee processen die hetzelfde SELF-binair bestand draaien, delen de text-pagina's niet zoals een normaal mmap'd ELF-bestand dat doet, omdat de bytes uit de b-tree worden gekopieerd in plaats van gemapt.

Het systeem is een closure

Een SQLite-database hoeft echter niet slechts één executable te zijn. Het kan een closure zijn: één enkel bestand dat een programma en al zijn transitieve afhankelijkheden bevat. De ldd-output van een programma is ambigu: het vermeldt alleen de sonames van de benodigde bibliotheken, niet de specifieke bestanden die aan die behoeften voldoen. Nix verbetert dit door elke edge expliciet op te lossen naar een specifiek store-pad via het gebruik van RUNPATH.

We kunnen hetzelfde doen in SELF door het opgeloste pad van elke edge in de database op te slaan:

CREATE TABLE objects (id INTEGER PRIMARY KEY, path TEXT UNIQUE, soname TEXT, kind TEXT, is_root INTEGER);
CREATE TABLE needs (
  object_id     INTEGER REFERENCES objects(id),
  ord           INTEGER NOT NULL,
  soname        TEXT NOT NULL,
  -- de FK die ambiguïteit wegneemt
  resolved_path TEXT REFERENCES objects(path)
);

self closure pakt een binair bestand en zijn transitieve afhankelijkheden in één database, waarbij deze edges zijn ingevuld. Shared library resolution is geen gok meer, maar een foreign key, en ldd wordt een JOIN 🤯:

$ self closure "$(readlink -f $(command -v ls))" coreutils.db
ls + closure -> coreutils.db
$ sqlite3 -column coreutils.db \
"SELECT n.soname, substr(n.resolved_path, 12, 20)
FROM needs n JOIN objects o ON o.id = n.object_id
WHERE o.is_root = 1"
libgmp.so.10          rfabfsmwq02sn94mb3qg
libacl.so.1           x0zgiss9hdzcsll3cswg
libattr.so.1          08nfpyc4qhzdk37nznv
libc.so.6             8kvxvr3pmsypxiypq4g8

Deze enkele database is een closure van de ls executable en zijn vijf bibliotheken: zes objecten, inclusief segment bytes, in één bestand van 4,8 MiB. Er is geen soname-ambiguïteit binnen een closure, omdat een closure per definitie exact één provider per edge bevat.

Hoe ver gaat dit? Eén bestand, één userland

We kunnen zelfs nog verder gaan en meerdere closures in één enkele database pakken. Ik heb self closure gericht op elke ELF-binary in de PATH van dit systeem: 723 executables, die samen 400 verschillende shared libraries laden. 1.123 objecten, 346.386 symbolen, 3.808 dependency-edges, allemaal in één SQLite-bestand.

Het blijkt dat wanneer je dat doet, de database veel kleiner is dan je zou verwachten: 611,9 MiB aan database tegenover 644,4 MiB aan ELF-bestanden. Het hele userland, als één querybaar bestand, is kleiner dan de bestanden waar het vandaan kwam. De b-tree kosten die een enkele hello verdubbelden, amortiseren tot bijna niets over 1.123 objecten en bedragen ongeveer 6% bovenop de feitelijke program bytes.

De bibliotheken en closure worden gedeeld tussen de executables, vergelijkbaar met hoe Nix ze zou delen over meerdere closures als het store-pad hetzelfde was. Als elke root zijn eigen private closure zou verschepen (het AppImage-model), zouden diezelfde 723 programma's uitkomen op 5,53 GiB, maar de deduplicatie van bibliotheken en symbolen volgt natuurlijk uit het databaseschema.

$ sqlite3 userland.db \
'SELECT count(DISTINCT soname), count(*)
FROM objects WHERE soname IS NOT NULL'
345|399

$ sqlite3 -column userland.db \
'SELECT soname, count(*) FROM objects
WHERE soname IS NOT NULL
GROUP BY soname HAVING count(*) > 1
ORDER BY 2 DESC LIMIT 4'
libsystemd.so.0   3
libpthread.so.0   3
libgcc_s.so.1     3
libc.so.6         3

Veel algemene idiomen die we in ELF gebruiken, vloeien direct voort uit de database. Bijvoorbeeld: LDPRELOAD is een rij in een tabel in plaats van een omgevingsvariabele. De preload-tabel is een lijst van objecten die als laatste gemapt moeten worden, zodat hun exports winnen. Dit betekent dat het aan- en uitzetten van LDPRELOAD een transactie is.

$ ./app.self; echo $?
13
$ sqlite3 system.db "BEGIN;
CREATE TABLE preload(ord INTEGER PRIMARY KEY, path TEXT);
INSERT INTO preload VALUES (0, 'libmul.so.1.self');
COMMIT;"
# hetzelfde binary, geen env var, geen relink
$ ./app.self; echo $?
42
$ sqlite3 system.db 'DELETE FROM preload;'
$ ./app.self; echo $?
13

We konden een atomaire LD_PRELOAD over een heel userland in één bestand bewerkstelligen; "een tracing malloc overal interponeren en daarna ROLLBACK" is een enkele transactie. 😈

Waar het nu staat

Het formaat is voltooid en maakt lossless round-trips tussen ELF en SELF. De tooling is klaar en kan closures queryen, wijzigen en pakken. Lookup via SQL werkt perfect op ongewijzigde glibc-programma's en de native-SQL loader werkt voldoende om het als een mogelijkheid te verkennen.

Het geheel staat op fzakaria/selfdb. nix run .#self-vm start een NixOS VM waarin hello een SQLite-database is. 🙌

Nix stelt ons in staat om radicale ideeën als deze te verkennen. We kunnen de wereld herbouwen tot aan de Linux-kernel als dat nodig is. We hoeven ons niet te laten beperken door bestaande beslissingen en beperkingen uit het verleden. We kunnen nieuwe ideeën verkennen en zien wat daaruit voortvloeit. Ik hoop dat je dit idee net zo interessant vindt als ik.