Последние несколько лет автора занимали две вещи: Nix как инструмент для пересборки мира с нуля и идея заменить ELF на SQLite в качестве формата исполняемых файлов. Эти две идеи неожиданно хорошо сочетаются друг с другом.

Идея прорабатывалась ещё во время работы над PhD-диссертацией, но отклик со стороны коллег был прохладным. Радикальные идеи трудно продать, когда приходится бороться с инерцией уже устоявшегося решения.

Одним из результатов этих исследований стал sqlelf — инструмент, позволяющий декларативно исследовать ELF-файл с помощью SQL¹. Запрос вида SELECT name FROM elf_symbols вместо возни с readelf и grep. Реализация оказалась удивительно простой благодаря использованию виртуальных таблиц поверх ELF — это стало приятным улучшением в изучении формата ELF-файлов. Но было ясно, что можно сделать что-то гораздо более масштабное.

Идея никуда не делась, а с недавним прогрессом в области LLM появился новый стимул вернуться к ней и развить дальше. Конкретный вопрос: можно ли заменить ELF на SQLite в качестве формата исполняемых файлов? 🤔

Речь не о «базе данных, описывающей исполняемый файл», а о самом файле, к которому применяется chmod +x и который запускается напрямую.

$ 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

В результате появился достаточно проработанный прототип под названием SELF — Structured Executable & Linkable Format (название неоригинальное, но по существу). Исходники доступны на GitHub. Из этой идеи вытекает неожиданно много интересных следствий.

ELF — это база данных, которая отказывается себя так называть

Во время работы над диссертацией стало очевидным то, что не давало покоя: ELF уже является базой данных. Просто он вручную реализует множество примитивов СУБД, плюс удивительное количество структур данных для производительности — например, фильтр Блума для поиска символов.

Любому, кому приходится анализировать или парсить ELF — будь то ядро, ld.so, binutils, LIEF, goblin или readelf, — приходится заново реализовывать один и тот же парсер. Каждый производитель ELF-файлов заново пишет один и тот же сериализатор.

Сам формат крайне лаконичен — он спроектирован для мира, где место на диске и пропускная способность сети были на вес золота. Изменять формат сложно: часто приходится обнулять секции и добавлять новые, поскольку всё упаковано очень плотно. Самоописываемой схемы тоже нет: ELF — очень общий формат, поддерживающий секции данных, которые по соглашению интерпретируются определённым образом, но сам формат этого никак не проверяет.

SQLite — противоположный пример. Это самоописываемый формат, при этом крайне стабильный. Он спроектирован так, чтобы расширяться новыми возможностями без поломки существующих потребителей и эффективно поддерживать широкий диапазон запросов.

Если заменить ELF на SQLite, что из этого получится и можно ли представить всю необходимую информацию в базе данных SQLite? Ответ — да, и на удивление просто.

Что отпадает за ненадобностью

Для запуска файла SELF достаточно двух таблиц: self_meta — это заголовок ELF в виде пар ключ/значение, а segments — образ загрузки, по одной строке на каждый program header, с байтами в BLOB:

CREATE TABLE segments (
  -- original phdr index
  id      INTEGER PRIMARY KEY,
  -- 'load' | 'tls' | 'stack' | 'relro'
  type    TEXT NOT NULL,
  -- original 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,
  -- the segment bytes; NULL for pure BSS
  content BLOB
);

Одна таблица для таблицы символов заменяет множество секций ELF и индекс .gnu.hash. Это единственная таблица с единственным индексом:

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);

Возможность включить индекс эквивалентна .gnu.hash и .hash в ELF, но это полноценный b-tree индекс, поддерживаемый SQLite, а не самодельный фильтр Блума².

Неожиданно отпадает и многое другое: .dynstr больше не нужен, потому что name имеет тип TEXT, а SQLite уже интернирует строки; версионирование символов — это просто колонка, а не конструкция из .gnu.version_r / .gnu.version_d; отдельная таблица strings тоже не требуется.

Существуют и другие таблицы для метаданных, нужных инструментарию: sections, notes, dynamic_entries. Их можно удалить, и программа всё равно запустится — а значит, strip(1) становится транзакцией:

# 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

# still runs,  the optional tables were optional
$ ./hello
Hello, world!

Все инструменты, работающие с ELF-файлами на чтение, сводятся к запросам к базе данных. Любой инструмент, изменяющий ELF-файл, например strip, может работать с базой в рамках транзакции вместо хрупкой хирургии над смещениями: strip — это DELETE и VACUUM. patchelf — это UPDATE.

Любая информация, отсутствующая в схеме, легко предоставляется через представление (view). Например, ldd — это запрос к таблице needed, которая является join таблицы symbols с таблицей segments для поиска sonames библиотек, нужных программе.

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;

Как это работает?

SQLite резервирует 4-байтовое поле application_id по смещению 68 в своём заголовке именно для подобных целей. В него записывается значение SELF, поэтому обычная база SQLite никогда не совпадёт с этой сигнатурой:

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

Далее можно задействовать binfmt_misc — подсистему ядра, позволяющую запускать любой бинарник так, как если бы он был нативным. Нужно лишь зарегистрировать магическую сигнатуру и интерпретатор, который будет вызываться для нового формата файла.

На NixOS регистрация — это несколько строк, сопоставляющих сигнатуру SQLite по смещению 0 и строку SELF по смещению 68:

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

Пока используется небольшая утилита elf2self, конвертирующая ELF-файл в файл SELF. Это простой хук postFixup, который можно включить для отдельного пакета на NixOS. Инструмент читает ELF, извлекает program headers и таблицу символов и записывает их в базу SQLite. В перспективе можно рассмотреть расширение gcc или ld для прямой генерации SELF, но пока это простой способ проверить идею на практике.

self-exec — это и есть интерпретатор. Это небольшая программа на C, слинкованная с libsqlite3. По реализации она очень похожа на ld.so, но получает program headers и таблицу символов из базы данных, а не читает их напрямую из ELF-файла. Она отображает загружаемые сегменты в память, выполняет релокации и передаёт управление на точку входа.

Примечание. self-exec должен оставаться ELF-файлом. Если бы интерпретатор сам подпадал под регистрацию binfmt, это привело бы к бесконечной рекурсии и ошибке -ELOOP.

Динамическая линковка

Запуск статической программы прошёл быстро и легко, но получился скучным и неинтересным. По-настоящему интересная часть — динамическая линковка, где база данных раскрывается полностью.

Были опробованы два разных подхода к динамической линковке. Первый — оставить ld.so как есть и просто заменить механизм поиска на SQL-запрос через интерфейс glibc rtld-audit, чтобы быстро проверить идею на практике. Второй — полностью заменить ld.so новым динамическим линковщиком, который выполняет весь поиск и связывание средствами SQL.

Интерфейс rtld-audit в glibc позволяет библиотеке аудита перехватывать каждый поиск разделяемого объекта (la_objsearch) до того, как начнётся поиск по файловой системе — включая случай dlopen. Библиотека аудита может ответить на вопрос «какая библиотека удовлетворяет этому символу?» с помощью SQL-запроса вместо обхода RUNPATH и LD_LIBRARY_PATH. Стандартный ld.so отображает объект в память и выполняет релокации, поэтому весь набор возможностей glibc продолжает работать: ленивая привязка PLT, IFUNC, TLS и версионирование символов, — при этом хранение библиотек становится строками, а их поиск — запросами.

# no ELF library anywhere on 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!

Возник интерес: как бы выглядел полностью SQL-based динамический линковщик? В качестве прототипа появился self-ld — небольшая программа на C, реализующая динамический линковщик целиком средствами SQL. Это proof-of-concept, но он работает. Он отображает сегменты каждого объекта, публикует их экспорты и для каждой релокации патчит GOT, после чего передаёт управление на точку входа.

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;

Цена и бенчмарки

Две вещи, которые обычно важны при замене устоявшегося формата, — это размер и задержка. Насколько больше файл SELF по сравнению с ELF и насколько медленнее он запускается?

Размер. Файл SELF несёт накладные расходы b-дерева SQLite и в итоге получается примерно вдвое больше ELF.

Как и в случае с ELF-бинарниками, большая часть этого объёма восстановима, поскольку накладные расходы приходятся в основном на опциональные таблицы для отладки и инструментария. Удаление этих таблиц — тоже транзакция. Очищенный SELF-файл coreutils занимает 1 794 048 байт против 1 768 632 байт у ELF — разница меньше 1%.

Далее будет показано, что есть интересные способы ещё сильнее амортизировать накладные расходы — и это оказалось особенно любопытным.

Задержка. Бенчмарк прогонялся на разных бинарниках — от 15-килобайтного hello до 42-мегабайтного gdb, линкующего 47 библиотек:

Есть фиксированные ~5 мс на открытие SQLite и запуск интерпретатора, плюс копирование, пропорциональное размеру образа. Это копирование хуже, чем кажется на первый взгляд, потому что страницы b-дерева не отображаются в память напрямую. Два процесса, запускающие один и тот же SELF-бинарник, не разделяют страницы кода так, как это делает обычный mmap-нутый ELF, потому что байты копируются из b-дерева, а не отображаются в память³.

Система как замыкание (closure)

При этом база данных SQLite не обязана представлять только один исполняемый файл. Она может быть замыканием (closure) — единым файлом, содержащим программу и все её транзитивные зависимости. Вывод ldd для программы неоднозначен: он перечисляет только sonames нужных библиотек, но не конкретные файлы, которые их удовлетворяют. Nix решает эту проблему, явно разрешая каждое ребро в конкретный путь в хранилище (store path) с помощью RUNPATH⁴.

То же самое можно сделать в SELF, сохраняя разрешённый путь для каждого ребра прямо в базе данных:

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,
  -- the FK that kills ambiguity
  resolved_path TEXT REFERENCES objects(path)
);

Команда self closure упаковывает бинарник и все его транзитивные зависимости в одну базу данных с уже заполненными связями. Разрешение разделяемых библиотек перестаёт быть гаданием и становится внешним ключом, а ldd превращается в 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          08nfpyc4qhzdkc37nznv
libc.so.6             8kvxvr3pmsypxiypq4g8

Эта единственная база данных является замыканием исполняемого файла ls и его пяти библиотек: шесть объектов, включая байты сегментов, в одном файле объёмом 4,8 МиБ. Внутри замыкания нет неоднозначности по soname, поскольку по построению замыкание содержит ровно одного поставщика на каждое ребро.

Насколько далеко это заходит? Один файл, один userland

Дальше становится по-настоящему интересно. Можно пойти ещё дальше и упаковать несколько замыканий в одну базу данных.

Команда self closure была применена ко всем ELF-бинарникам в PATH системы: 723 исполняемых файла, подтягивающих 400 различных разделяемых библиотек. В сумме — 1123 объекта, 346 386 символов, 3808 связей зависимостей, всё в одном файле SQLite.

Оказалось, что при таком масштабе итоговая база данных заметно меньше, чем можно было бы ожидать.

611,9 МиБ базы данных против 644,4 МиБ ELF-файлов. Весь userland в виде одного запрашиваемого файла оказывается меньше, чем файлы, из которых он был собран. Накладные расходы b-дерева, которые удваивали размер одного hello, амортизируются почти до нуля на 1123 объектах и составляют примерно 6% сверх реальных байт программ.

Библиотеки и замыкания разделяются между исполняемыми файлами примерно так же, как Nix мог бы разделять их между несколькими замыканиями, если бы store-path совпадал. Если бы каждый корневой бинарник поставлялся со своим приватным замыканием (то есть по модели AppImage), те же 723 программы заняли бы 5,53 ГиБ, но дедупликация библиотек и символов естественным образом вытекает из схемы базы данных.

$ 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

$ sqlite3 userland.db \
    "SELECT count(*)
    FROM needs
    WHERE resolved_path IS NULL AND soname NOT LIKE 'ld-%'"
4

Многие привычные приёмы работы с ELF естественным образом выражаются через базу данных. Например, LD_PRELOAD становится строкой в таблице, а не переменной окружения. Таблица preload — это список объектов, которые отображаются в память последними, поэтому их экспорты побеждают. Включение и выключение LD_PRELOAD становится транзакцией.

$ ./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;"

# same binary, no env var, no relink
$ ./app.self; echo $?
42

$ sqlite3 system.db 'DELETE FROM preload;'
$ ./app.self; echo $?
13

Таким образом удалось реализовать атомарный LD_PRELOAD для целого userland в одном файле: «подставить трассирующий malloc повсюду, затем сделать ROLLBACK» — это одна-единственная транзакция. 😈

Текущее состояние проекта

Формат готов и обеспечивает безлоссовое преобразование между ELF и SELF в обе стороны. Инструментарий готов и умеет выполнять запросы, модифицировать файлы и упаковывать замыкания. Поиск через SQL отлично работает на немодифицированных программах glibc, а нативный SQL-загрузчик работает в достаточной мере, чтобы исследовать эту идею как возможное направление.

Весь проект доступен по адресу fzakaria/selfdb. Команда nix run .#self-vm запускает VM с NixOS, где hello представляет собой базу данных SQLite. 🙌

Nix позволяет исследовать подобные радикальные идеи — можно пересобрать всю систему вплоть до ядра Linux, если это потребуется. Не обязательно быть ограниченным существующими решениями и ограничениями прошлого — можно исследовать новые идеи и смотреть, что из этого получится.