Executable Is a SQLite Database
Comments
andai
setheron
(author) I'm enjoying the comments. When I published a short-paper with this idea in academic circles, the feedback wasn't so kind
garganzol
Don't pay too much attention to the inner-circle feedback. Some people subconsciously use the tone of reception to control you, especially peers/colleagues are prone to this. They see someone having a bright idea, and they genuinely don't like it just because it makes them feel small in comparison. The thing they do next - they try to extinguish the spark by creating an illusion of worthlessness in your mind. By doing so, they are getting rid of a potential competitor on their own way to success. According to psychology, they start feeling normal again by reducing you, this is a natural compensatory mechanism ingrained in human archetypes.
The key thing here is to be able to discern between real and manipulated input information. For this, gut feeling usually works best: it spots that whiny, attention-insisting, importance-seeking, fear-inducing tone of a manipulator, but oftentimes the higher-level nervous system of the brain suppresses that signal (e.g. "How can a well-educated and charismatic person feel a bit off and responsibility-lacking sometimes? It cannot be right, so it must be something with my interpretation of reality. I bet they have the best intentions.")
An even better approach may be not to search for feedback at all, unless it's shared naturally without any strings attached.
genxy
I love your idea, 40% of which is because I had the same one. I think it is the next logical extension over using zip as the container (jar/ooxml/epub).
https://sqlite.org/draft/appfileformat.html
There is little reason that ELF needs to be so complex. My motivation was to bundle multiple wasm modules together along with data.
pkilgore
Curious what that feedback was, specifically?
setheron
I won't share any feedback specially but choosing low level primitives as research I found challenging due to the unfamiliarty in peer review circles.
I enjoyed all the papers I read on my graduate classes that bordered on "art" whereas now they seem to be obsessed with performance only.
bloppe
More nix content
inigyou
> I realized something that bugged me. ELF is already a database.
Even more broadly applied: Every base of data is already a database (that's what the compound word means). Programs like sqlite and postgres used to be called by the more precise term "Relational Data Base Management Software" or "RDBMS" until their use became so widespread that they were colloquially called databases instead.
The very first data base structures were more like, each geometric sector of a hard drive is a record, and each head is a column. This was a straightforward translation of punch-card workflow onto a magnetic disk.
agustechbro
yes you are right, in the article the author thinks he just realized something special "elf is a data base", but no, is not, its just a structured piece of data "a database", sqlite file format is also that, the only diference between Elf and sqlite file is that the latter has a a better "client" to inspect it.
Rendello
Like the Unicode Character Database, which is a series of text files in similar-seeming but disparate formats (it now also has an XML representation):
tengwar2
I understand what you are saying, but that's not close to the original meaning of the term, or at least not what I have seen in early papers. Originally the idea was a single central repository of information which would be used to run a company: so similar to systems like SAP, but obviously a lot simpler and with the assumption of running on a mainframe. It didn't refer to a particular choice of data structure, but to the way that multiple business processes would share information.
XJ6w9dTdM
Yes !
This has been on the back of my mind for a while. And, as other commenters have noted, it would be great for the file to contain the (self-modifiable) Lisp image, a builtin virtual file system, and whatever the application want to use as (runtime modifiable) extra tables.
I find SQLite dynamic linking being basically compatible with ELF dynamic linking to be very impressive, I can imagine that if well done, it cloud replace most uses of AppImages with a much more efficient format, like the author suggests.
How about an option for compressing section contents within the SQLite blobs, since the author mentioned you can't mmap directly the text pages and have to copy anyway ?
There are two extensions that I was thinking would make a SQLite executable truly unique.
First, a linking extension that would allow patching in functions and hooks more directly to allow for a very powerful plug-in system. Imagine the plug-in SQLite defining a BEFORE/AFTER/REPLACE hook for some symbol the host SQLite defines as extensible.
Second, re-linking at runtime. This would require application author cooperation because you won't be able to do that from anywhere, but imagine changing a dependency or loading a plugin at runtime through editing the db, and the interpreter just maps that on demand/automatically in the background, now next time your web server accept(), it calls the new version of the handling function.
inigyou
You can do any of this in-memory wife ELF of course, it's just that nobody does and nobody's written the tools for it (the most obscure tool I know of is `ld -r`, which links two or more .o files and produces a new .o file instead of an executable)
XJ6w9dTdM
For sure, the main advantage is that since the SQLite file format is easy to use compared to ELF, it's more likely that such experiments would be even tried at all.
I got another one: bundling multiple (completely separate) executables with shared dependencies in the same SQLite, selected by argv[0] when called, like what busybox does
Joker_vD
Also known as a directory.
inigyou
If a directory was contiguous on disk.
Joker_vD
Most files aren't contiguous on a disk either, you know.
Which makes inability to punch wholes in the middle of the files without having to read/write huge chunks of data quite annoying, especially when you write a linker or an archiver. Reserving enough space for the header is quite non-trivial.
inigyou
Filesystems try fairly hard to make files mostly contiguous on disk, but they don't do the same to directories.
inigyou
Also known as a zip file!
djoldman
> 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.
Sounds like a great use case for:
1. ELF file to SELF file
2. modify SELF file
3. SELF file to ELF fileDyslexicAtheist
nightmare for anything that relies on checksum based security :D
zbentley
Is it? ELF's specified enough that I can't imagine that it's too hard to avoid checksum mismatches between traditionally-modified ELF binaries and ELF-SELF-ELF-modified ones.
Like, it's an ugly spec, but it's clear enough on ordering/layout that I think checksumming is probably tractable to get parity for.
catlifeonmars
I can buy that an object file can be viewed as a relational db. Why SQLite though? Why not SQL query engine over the object file using a virtual table abstraction? I’m not seeing how most the SQLite features, with the exception of a subset of the query engine would translate over.
If the author wants to make a case for including schema metadata in an object file, again why SQLite? This strikes me a lot as someone who is trying to find uses for their favorite hammer (a very useful hammer I might say) rather than a serious exploration of what a new, improved object file format would look like.
(And that’s totally ok)
jonhohle
I wrote a tool[0] for manipulating elf files to support inline assembly for a compiler that doesn’t support it (based on a similar python tool). That required knowing any of the ELF sections that were being changed and how those changes would impact other sections.
sqlite would have made this pretty trivial. Replace the .text fields of a few rows. Insert a few rows for symbols, update a few from the old object.
The best part - there’s tons of library support for sqlite. If it was a new object format, there would be no support and I’d just have to write different parsers and generators.
The schema might the the biggest issue for efficiency. As others have noted, ELF->SELF->ELF might be the best use case for compatibility. That said, a big part of [0] was performance, and I don’t know how sqlite would have done compared to my naive elf parsing and manipulation.
catlifeonmars
> I wrote a tool[0] for manipulating elf files to support inline assembly for a compiler that doesn’t support it (based on a similar python tool). That required knowing any of the ELF sections that were being changed and how those changes would impact other sections.
Would this normally be something the compiler would handle, or would it be the linker? I guess I’m curious how this would impact any optimizations the compiler implements.
Also I’m guessing for your use case (elf edits) you would be looking at both SELECT and INSERT type operations?
jonhohle
There was a recent post that probably explains the details better than I could[0].
This would most like just be the concern of the compiler and assembler. In GCCs case, my understanding is it just inlines the assembly into the output assembly stream and the assembler is none the wiser. The issue is that MetroWerks doesn’t support inline assembly at the top level (for defining new function symbols), but only inline within the context of a function. That means some additional setup and tear down that shouldn’t be present may be injected instead of the raw assembly.
There’s possibly some upseet potential and the idea that it could be done in place could avoid loading the entire thing k to memory (though the files are small for modern systems).
setheron
(author) In the post I say I did write sqlelf which is just that, sqlite + virtual tables prior to this.
catlifeonmars
Thanks for responding! I hope I didn’t come across as being overly critical. I’m curious what you would consider if designing a greenfield implementation of an object file format. What would you optimize for, and perhaps more interestingly, what would you not optimize for?
setheron
I like your phrasing; I think too often we get caught trying to optimize for everything.
For my own edification I often let performance & size slip to see if I can re-imagine something simpler from the start from a complete new direction;
This is often the greenfield hubris because it doesn't have all the same battle-scars of the full implementation so I try to make sure I take a very different approach to make it worthwhile :)
Then I just have faith that performance and size can always be improved over time.
inigyou
sqlite is a great replacement for fopen - although the C interface is much more verbose.
catlifeonmars
Oh do you mean as a way to store app state? Yeah 100%. It also helps that there are native reimplementations in many major languages, which means you don’t even need to link a libsqlite3 in contexts where it can sometimes be impractical to use the official C library (looking at you, CGO_ENABLED=0). And let’s not forget about sqlite3 running in wasm :)
garganzol
The copied vs. mapped memory situation is the only deal breaker in this experiment. Otherwise, file format unification would be a big step forward. The PE/COFF executable file format used by Windows (and some older Unix systems) is a relational database as well. The same goes to .NET assembly format - it's a relational database too. The wheel gets reinvented over and over again.
stillpointlab
I was thinking that one could just write a loader that goes from SELF->ELF on load. You then pay the cost on startup. Probably not worth it for one-shot programs like ls/cat/etc, but for long running programs and daemons it might be workable.
garganzol
Another option is to adapt a database engine to support page-aligned blobs, which is probably not that hard to achieve.
stillpointlab
Of course there are many options, but the benefit of the SQLite approach is the existing tooling, support, etc. Like others have said, one could just write a SQL interface over a set of virtual tables derived from the actual elf (if one just wanted a CRUD-like interface to a binary).
All of the benefits of SQLite disappear once one diverges from the format in any way. At which point it would be better to ask: "what is the best first-principles implementation of this idea?", instead of "what is the minimal change to SQLite to achieve this specific narrow goal?"
setheron
I might look at this next; with Nix it's easy to explore and rebuild seamlessly ;P
hedgehog
I didn't understand the core issue, is it that due to non-alignment of the on-disk data you have to do a copy at load time, but if you could guarantee alignment of the actual blob content then you could use it directly?
garganzol
Exactly, a guaranteed alignment and continuity of a blob makes it memory-mappable allowing to avoid copying the data back and forth.
SmasherEpilepti
> ELF MECHANISM: .strtab / .dynstr > The database primitive it reinvents: string interning
> Surprisingly a lot more falls out as well: .dynstr is gone, because name is TEXT and SQLite already interns strings
What's with this claim? SQLite does not intern strings, as far as I can find anywhere, and a quick test shows that duplicate strings are actually duplicated in a database file. You can intern strings in SQLite manually with an intern string table, but it doesn't happen automatically.
unified101
I don't think this goes far enough! Make the actually app store be the same file itself. so it's a living application and the file is constantly updated to how you use it. Copy it around, and you carry your data wiht you as well.
Let's go deeper. it's a webserver app + the server code + application code + db, so pocketbase++ where it's also the deployment target.
Then combine it with APE liek system, and the same file loads and stores things on every platform. evil laugh
Very cool hacking! My hats off to the author.
arnsholt
The application writing its state to the executable is basically Smalltalk (or Lisp). It's an extremely powerful way of writing software, IMO.
inigyou
Or Forth. But all of these are extreme spaghetti-bait too. Being able to see all the code that goes into an executable, and generate a clean one using only that code, is important for good development hygiene, which of course they didn't know yet in the 1970s. Imagine trying to use version control on a REPL - it doesn't work - you have to version control the commands that go into the REPL and running them on a fresh REPL every time.
regularfry
I didn't have this idea exactly but I did play around with sqlite as an embedded database for packing ruby apps into a single file a while ago. It was less direct than this: you basically compiled all the dependencies (including .so's) into a fake filesystem that an overridden `require` loaded from, which was unpacked to a `:memory:` database at runtime from a `.data` section that got bolted onto the interpreter. It died when 1.8->1 9 changed how the build system works and I never got round to updating.
A version based on this which carries around an overlay filesystem would be comparatively straightforward, the hard work is already done.
wduquette
The TCL community experimented with an idea like this many years ago; they were called "structured documents" or "starpacks". What we found was that (A) it's usually more convenient to keep the data in a separate file, and (B) virus checkers can get suspicious when your app starts modifying itself, leading to unintentional comedy in operations. YMMV.
pizzafeelsright
This has been my hope.
BIOS -> Database that has everything including OS.
This way we get WORM and AI integration.
pstuart
Doesn't redbean do this in a more portable way (not ELF dependent)?
skavi
This was super fun. Dude’s been on an absolute tear recently.
JSR_FDED
I appreciate the inventiveness of this idea. But I don’t find myself thinking I must have this.
afarah1
Yeah... Original and clever, and a great read! But it seems mostly useful to the handful of people dealing with ELF internals, than to the vast majority of people executing ELF blissfully ignorant of its internals... Maybe if the latency and size trade-offs were the other way around it would be more appealing to the masses.
inigyou
So a great hacker project.
luciana1u
an executable that is also a database means my bugs get relational now. instead of a segfault i get a foreign key constraint violation.
dolmen
I wonder how flexible is the SQLite binary format to allow to design a tool that would take a SELF binary/db and rewrite it to make BLOB values more mmap-able (OS page aligned) in order to allow shortcuts in the self-exec loader.
inigyou
You'd have to at least increase the page size to allow 4kB of consecutive data without interfering with the page header.
OR you restructure the code and data to work around the page headers.
dist-epoch
Or you could write a new SQLite VFS that somehow separates the page headers from the page data.
inigyou
You still have row headers. Yes in the extreme you could write a VFS that parses the blobs out of the database and writes them sequentially somewhere, but it's much more practical to set the page size to 64kB and probably get 56kB of contiguous data in the middle of each page, then add padding into your blobs so that contiguous data is exactly the data you want to mmap
eqvinox
NB: ELF executables and libraries don't need to have sections, or a section header table. The program headers are what matters. You can use sstrip to remove the SHT.
ale42
I was thinking that someone managed to put an ELF header in an SQLite file while keeping it compatible with SQLite... but no, "just" a new binary format. Very interesting nevertheless!
c0wb0yc0d3r
Unless I missed something. The author queries the bin in one of the examples using sqlite3.
The author instructs the OS to execute it natively my adding it as a binary format.
dcrazy
Congratulations, you’ve rediscovered mainframes.
antonvs
In what way? Are you thinking of a particular mainframe?
My mainframe experience was on an IBM 370/158 using VM/CMS, and I can't see any real connection between the OP and its executables.
I suppose there's a very vague connection to how the LOADER could load TEXT files (similar to a .o file) into virtual storage, without having linked an executable (a MODULE). But that's about runtime usage, not file format, and there's certainly no SQL functionality that applies to executables on mainframes.
djhworld
This was a fantastic read thanks for putting it together. I'm always fascinated by binfmt_misc, I remember fooling around with steganography a few years ago and putting executables inside images that could then be executed using a wrapper tool + binfmt_misc.
I think this is awesome though, feels like a lot of things on OS's could just be represented by databases - where does it end?
kjuulh
Great read. I always find these turn a feature of a computer into a database an interesting read/idea. It certainly has upside, and downsides. For example having an entire filesystem as a sqlite database etc, or in this case an executable. It would be nice to have a structured way of talking to our utilities, rather than interpreting various commands as json through a few layers of tools to then get the output in a common format. That said I'd probably rather have a split up tool-set, than everything having to be in a single database for it to interoperate.
catlifeonmars
Two tools come to mind that you might be interested in
- osquery: virtual table abstraction over proc fs. https://www.osquery.io/
- nushell: shell with structured I/O. https://www.nushell.sh/
inigyou
We do have a single database, it's the filesystem. But quite importantly it's a very composable kind of database, because you can "section off" a part of the database, calling it a folder, and the folder looks like a whole filesystem of its own. Working in the folder is like working in a separate database that's visible from the outside but the outside isn't visible from the inside unless you deliberately choose to go out through the escape hatch. SQL isn't like that - it's a flat namespace and that is like the original filesystems that didn't have folders. Those were usable when a computer was only big enough to hold a few activities at a time and when you had a stack of disks next to your computer, each with a different program's filesystem.
A flat namespace might actually work with an app-based OS model (like on android) where everything that happens is associated with an app ID and apps mostly can't talk to each other. But there's a reason nerds don't do nerd stuff on smartphones.
athrowaway3z
These are the kind of posts i love.
One nit-pick;
> The preload table is a list of objects to map last, so their exports win.
made it sound like the 'map last' is a consequence of this new perspective, but it’s really still a loader convention: by definition, the symbol-resolution query needs to give entries in the preload table precedence over ordinary dependencies.
kjellsbells
Isn't "everything in a database" what AS/400 and PICK operating systems do?
Then there was Microsoft WinFS, which promised much but got killed in ~2003. A shame.
vlovich123
The lack of mmap is a problem, especially given how dynamic link heavy Linux distros are. It’s going to cause a lot of extra RAM usage and the kernel won’t know to dump those pages efficiently and will swap them to disk. The extra RAM usage will probably be recovered - the kernel typically these days has deduplication capabilities - but the lack of efficient swap is a problem.
mongol
So where does this lead to? Is it leading us towards SQLite as some kind of alternative container image format? Because the benefit seems to only occur when it incorporates dependencies
yellowapple
I've wanted to do something like this for a long while now. Seems like an obvious way to make executables of varying “fatness”: for example, starting with some platform-agnostic instruction set (like WebAssembly), and gradually adding natively-compiled pieces that the executable runner could swap in if the machine satisfies various conditions. Want to use some fancy new instruction set extension but you don't know if all your target machines support it? Ship multiple versions of that particular function in the same SQLite-database-based executable, and let the loader decide which function version to use based on the host machine's known capabilities.
howerj
I've wanted to do something like this for quite a while! Of course I wanted to make my own OS, language and DB from scratch in order to do it, so naturally I've never gotten around to it. It goes to show that there is nothing new under the sun.
enygmata
How many layers of "SQLite for everything" are we at now?
colinhb
The handling of dynamic libraries and closing over them into single dbs made this a fun read.
didip
A lot of kernel filesystem features should be inside a database as well.
andrewl
Yes. In this interview Michael Stonebreaker, one of the original developers of PostgreSQL, discusses (among other topics) replacing the file system with a database :
wduquette
This is one of those perennial ideas; let's get rid of hierarchical file systems and just keep all the files in a database. Speaking as a user who knows how to keep things organized, I like hierarchical file systems. Store the data in a database if you like, but don't break my metaphor.
andrewl
I like a hierarchy, too. Presumably the underlying engine could be a database but it would at least appear to the user as a tree. But with the option to find files with SQL or a SQL-like language. I would love to be able to find files based on all kinds of metadata that was available for searching with the OS’s file system, and not using any special tools. I’m thinking things like EXIF data, audio file metadata, text file line count, and so on.
test6554
The tree-view is practical for users but seems impractical for relational database performance.
SELECT * FROM files p LEFT JOIN files c ON p.id = c.parent_id LEFT JOIN files gc ON c.id = gc.parent_id LEFT JOIN files ggc ON gc.id = ggc.parent_id .... where p.id = 123
wduquette
Datalog could handle it, though.
test6554
When you have a hammer, everything starts to seem like a nail. /s :)
account42
Why the /s? There is a reason why we don't use hammers for all tasks even though we could find ways to accomplish many of them with one.
inigyou
I want to see a kernel managed by NETCONF.
Not the XML protocol, that's annoying (although usable) but the structured data model.
simonw
The word "Your" was dropped from the start of the title for some reason.
notpushkin
Well, for the usual reason :-)
I’m wondering if the anti-clickbait filter could benefit from some lightweight LLM integration. E.g. when the submission hits the front page, if the title was “de-clickbaited” and wasn’t changed manually yet, run it through a cheap model and see if that was the right call.
aniviacat
Maybe "your" at the beginning of a title should be replaced by "my" instead of getting stripped.
That would preserve the non-clickbait meaning of all such titles I can spontaneously think of.
notpushkin
“SQLite database as an executable format”? A bit farther away from the original but captures the meaning and sounds more neutral.
cobbzilla
This is really creative and clever, nicely done!
The “Inception” graphic was hilarious and made me wonder if perhaps the site itself is served by some SELF binary (is it?? that would be insane)
alex7o
What if, we put the sqlite driver in kernel space? So this is your only filesystem like a unikernel
jdub
It's a lot of machinery to put into a kernel.
(Even with ELF, a kernel can have a relatively simple parser and loader and leave more challenging work to user space... like relocations, dynamic libraries, etc.)
zokier
tbh execve should be userspace operation instead of syscall, idk why kernel needs to care about the executable format at all
self_awareness
> Two processes running the same SELF binary do not share text pages the way a normally-mmap‘d ELF does, because the bytes are copied out of the b-tree rather than mapped.
Isn't this the whole point of executable file formats? To avoid loading everything all at once, share immutable segments with other processes, be extremely fast when loading, and integrate with OS page fault handlers to load data on demand?
I don't understand this project at all.
Even if it's possible to query the executable using SQL, we can always just use the SQL frontend to interface with executable data. I mean, ELF as a backend format for the "executable database". Like osquery interfaces with the system using SQL language. Osquery doesn't convert all OS data structures to sqlite :)
Btw, I think SELF is already "coined" by Signed ELF executables - SELF files, existing for example on Playstation 3.
__m
not sure if the people exploring binaries prefer sql over command line tools
inigyou
SQL is so much more consistent and introspective though. No need to remember which flags are for readelf and which are for objdump.
miketery
As far as agent workflows are concerned whats needed is the other direction. Store the files wherever but let an agent interact with it as if its on local FS via bash or other languages using their file io.
Whats worked for others?
keeganpoppen
whoa this is wicked. nice work.
HackerThemAll
Yeah, I have been amazed for an entire life how many tools the IT industry invented during last 50 years to just disguise a database.
OK, in '70s, '80s or '90s when compute and storage resources were limited and every bit counted, specialized formats did make sense.
But nowadays we'd save enormous efforts by just packaging stuff in SQLite databases. Microsoft's proprietary file formats (Office, Power BI etc.), OpenOffice/LibreOffice OpenDocument format, or almost everything else would fit perfectly.
Documents, files, are all data (called "data files", aren't they?), including executables, which as can be seen in this article are also databases.
WorldMaker
Some of it is convergent evolution at work. 60s/70s/80s specialized formats as much predated modern database designs and data structures as coexisted with them. SQLite is the culmination of decades of database design. Some of that was influenced by those specialized formats of previous decades that SQLite could now in theory replace.
(Which is to say a lot of the specialized formats didn't exist just because of compute and storage resource limitations, but also because training/research/standards work came later. Plus complications like software patents. ZIP files have been around since the 1990s but ZIP only became a common general use container format for "everything" almost exactly 14 years later when patents finally expired.)
inigyou
At first I thought it was still for a word document to be saved in SQL but then I thought about embedded images and it makes complete sense. Makes more sense for a Publisher/Impress app though as they have more self-contained objects. In Word/Writer the main text is one huge run of characters, how would you sqlize that effectively?
garbagepatch
Current ooxml/odt formats use a zip file with xml files inside (plus other files like images). I'd guess one way would be to store the xml itself as a blob and another to use a json field, which Sqlite stores in a more efficient format called jsonb: https://sqlite.org/json1.html#jsonb
inigyou
Typo correction: At first I thought it was silly
pkilgore
ha ha ha
ha ha ha
yes
This whole article is fantastic, but already at the start, the SQLite virtual tables thing is blowing my mind.
https://www.sqlite.org/vtablist.html
You can "mount" your filesystem (or anything else) as a SQL database, wtf. That's amazing.
This sounds like it could be extremely useful.