Внимание: содержит системное программирование. Да, в сущности, ничего другого и не содержит.

Давайте представим, что вам дали задание написать фэнтезийно-фантастическую игру. Ну там про эльфов. И про виртуальную реальность. Вы с детства мечтали написать что-нибудь эдакое и, не раздумывая, соглашаетесь. Вскоре вы понимаете, что о мире эльфов вы знаете по большей части из анекдотов со старого башорга и прочих разрозненных источников. Упс, неувязочка. Ну, где наша не пропадала… Научен��ый богатым программистским опытом, вы отправляетесь в Гугл, вводите «Elf specification» и идёте по ссылкам. О! Вот эта ведёт на какую-то PDF-ку… так, что тут у нас… какой-то Elf32_Sword — эльфийские мечи — похоже, то что нужно. 32 — это, по-видимому, уровень персонажа, а две четвёрки в следующих столбцах — это урон, наверное. Точно то, что нужно, да к тому же как систематизировано!..

Как говорилось в одной задаче по олимпиадному программированию после пары абзацев подробного текста на тему Японии, самураев и гейш: «Как вы уже поняли, задача будет совсем не об этом». Ах да, контест был, естественно, на время. В общем, пятиминутку упоротости объявляю закрытой.

Сегодня я попробую рассказать про разбор файла в 64-битном формате ELF. В принципе, что в нём только не хранят — нативные программы, библиотеки статические, библиотеки динамические, всякое implementation specific, вроде crashdump-ов… Используется он, например, на Linux и многих других Unix-like системах, да, говорят, даже на телефоны его поддержку раньше активно запихивали в патченных прошивках. Казалось бы, поддержать формат хранения программ из серьёзных операционных систем должно быть сложно. Так и я думал. Да так оно, наверное, и есть. Но мы будем поддерживать весьма специфический use case: загрузку байт-кода eBPF из .o-файлов. Почему так? Просто для дальнейших экспериментов мне понадобится какой-нибудь серьёзный (то есть не наколеночный) кроссплатформенный байт-код, который можно получить из C, а не вручную писать, поэтому eBPF — он простой и для него есть LLVM-бекенд. А ELF парсить мне нужно просто как контейнер, в который этот байт-код кладётся компилятором.

На всякий случай уточню: статья носит характер exploratory programming и не претендует на роль исчерпывающего руководства. Конечная цель — сделать загрузчик, который позволит читать скомпилированные в eBPF с помощью Clang программы на C — те, которые у меня есть — в объёме, достаточном для продолжения экспериментов.

Заголовок

Начиная с нулевого смещения в ELF лежит заголовок. Он содержит те самые буквы E, L, F, которые можно увидеть, если попытаться открыть его текстовым редактором, и некоторые глобальные переменные. Собственно, заголовок — это единственная структура в файле, расположенная по фиксированному смещению, и он содержит информацию, чтобы разыскать остальные структуры. (Здесь и далее я руководствуюсь документацией на 32-битный формат и elf.h, знающим про 64-битный. Так что, если заметите ошибки — смело поправляйте)

Первое, что нас встречает в файле — это поле unsigned char e_ident[16]. Помните эти забавные статьи из серии «все следующие утверждения ложны»? Вот тут примерно так же: ELF может содержать в себе 32- или 64-битный код, Little или Big Endian, да ещё и под десяток архитектур процессоров. Вы собрались читать его как Elf64 под Little endian — ну, удачи… Вот этот массив байт и является своеобразной сигнатурой того, что находится внутри и как это парсить.

С первыми четырьмя байтами всё просто — это [0x7f, 'E', 'L', 'F']. Если они не совпадают, то есть основания полагать, что это какие-то неправильные пчёлы. Следующий байт содержит класс ~~персонажа~~ файла: ELFCLASS32 или ELFCLASS64 — разрядность. Для простоты мы будем работать только с 64-битными файлами (а бывает ли 32-битный eBPF?). Если класс оказался ELFCLASS32 — просто выходим с ошибкой: всё равно структуры «поплывут», а sanity check сделать не помешает. Последний интересующий нас байт в этой структуре указывает на endianness файла — будем работать только с «родным» для нашего процессора порядком байт.

На всякий случай уточню: работая с форматом ELF на C не следует вычитывать каждый инт по хитро вычисленному смещению — elf.h содержит необходимые структуры, и даже номера байтов в e_ident: EI_MAG0, EI_MAG1, EI_MAG2, EI_MAG3, EI_CLASS, EI_DATA… Нужно просто привести указатель на вычитанные или отображённые в память данные из файла к указателю на структуру и читать.

Кроме e_ident заголовок содержит и другие поля, некоторые мы просто проверим, а некоторые используем для дальнейшего разбора, но потом. А именно, проверим, что e_machine == EM_BPF (то есть он «под архитектуру процессора eBPF»), e_type == ET_REL, e_shoff != 0. Последняя проверка имеет следующий смысл: файл может содержать информацию для линковки (section table и секции), для запуска (program table и сегменты) или оба типа. Двумя последними проверками мы проверяем, что нужная нам информация (как бы для линковки) в файле имеется. Также проверим, что версия формата имеет значение EV_CURRENT.

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

Таблица секций

Как я уже говорил, нас интересует linking view файла, то есть таблица секций и сами секции. Информация о том, где искать таблицу секций, находится в заголовке. Там же указан её размер, а также размер одного элемента — он может быть и больше, чем sizeof(Elf64_Shdr) (как это отразится на номере версии формата, честно скажу, не знаю). Некоторые старшие номера секций зарезервированы, и фактически в таблице не присутствуют. Отсылка к ним имеет специальное значение. Нас интересует, видимо, только SHN_UNDEF (ноль тоже зарезервирован — отсутствующая секция; кстати, как вы понимаете, её заголовок в таблице всё же имеется) SHN_ABS. Символ, «определённый в секции SHN_UNDEF» на самом деле undefined, а в SHN_ABS — на самом деле имеет абсолютное значение и не релоцируется. Впрочем, SHN_ABS мне, похоже, тоже пока не нужен.

Таблица строк

Здесь мы впервые натыкаемся на string tables — таблицы строк, используемых в файле. Фактически, если const char *strtab — это таблица строк, то имя sh_name — это просто strtab + sh_name. Да, это просто строка, начинающаяся с некого индекса, и продолжающаяся до нулевого байта. Строки могут пересекаться (точнее, одна может являться суффиксом другой). У секций могут быть имена, тогда в ELF Header поле e_shstrndx будет указывать на секцию таблицы строк (той, которая для имён секций, если их несколько), а поле sh_name в заголовке секции — на конкретную строку.

Первый (нулевой) и последний байты таблицы строк содержат нулевые символы. Последний понятно почему: значение-часовой, завершает последнюю строку. А вот нулевое смещение задаёт отсутствующее или пустое имя — в зависимости от контекста.

Загрузка секций

В заголовке каждой секции имеются два адреса: один, sh_addr — это адрес загрузки (куда секция будет помещена в памяти), другой, sh_offset — смещение в файле, по которому эта секция там лежит. Не знаю, как оба, но каждое по отдельности из этих значений может быть 0: в одном случае секция «остаётся на диске», поскольку там лежит какая-то служебная информация. В другом — секция не грузится с диска, например, её просто нужно выделить, и забить нулями (.bss). Честно говоря, пока мне не приходилось обрабатывать адрес загрузки — куда загрузилось, туда и загрузилось :) Впрочем, у нас и программы, прямо скажем, специфические.

Релокация

А теперь интересное: по технике безопасности в Матрицу без оператора, оставшегося на базе, как известно, не ходят. А поскольку у нас тут всё-таки фэнтези, то связь с оператором будет телепатическая. Ах да, я же объявил пятиминутку упоротости завершённой. В общем, кратенько обсудим процесс линковки.

Для моего эксперимента мне потребуется часть кода, скомпилированного в обычную so-шку, загружаемую обычной libdl. Тут я даже описывать подробно не буду — просто открываете dlopen, вытягиваете символы через dlsym, при завершении программы закрываете с помощью dlclose. Впрочем, даже это — уже детали реализации, не относящиеся к нашему загрузчику ELF-файлов. Просто есть некий контекст: возможность по имени получить указатель.

Вообще, набор инструкций eBPF представляет собой торжество выровненного машинного кода: инструкция всегда занимает 8 байтов и имеет структуру

struct {
  uint8_t opcode;
  uint8_t dst:4;
  uint8_t src:4;
  uint16_t offset;
  uint32_t imm;
};

Причём многие поля в каждой конкретной инструкции могут не использоваться — экономия места под «машинный» код — это не про нас.

На самом деле, за первой инструкцией может сразу идти вторая, не содержащая никаких опкодов, а просто расширяющая immediate поле с 32-х до 64-х бит. Вот патчинг такой составной инструкции и называется R_BPF_64_64.

Для того, чтобы выполнить релокацию, ещё раз просмотрим таблицу секций на предмет sh_type == SHT_REL. Поле sh_info заголовка укажет на то, какую секцию мы патчим, а sh_link — из какой таблицы брать описание символов.

typedef struct
{
  Elf64_Addr    r_offset;
  Elf64_Xword   r_info;
} Elf64_Rel;

Вообще-то, бывают секции релокации двух видов: REL и RELA — вторая в явном виде содержит дополнительное слагаемое, но я её пока не встречал, поэтому просто добавим assertion на то, что она и вправду не встретится, и будем обрабатывать. Далее я буду добавлять к тому значению, что записано в инструкциях, адрес символа. А откуда его взять? Тут, как мы уже знаем, возможны варианты:

Символ ссылается на секцию SHN_ABS. Тогда просто берём st_value
Символ ссылается на секцию `SHN_UNDEF. Тогда вытягиваем внешний символ
В остальных случаях просто патчим ссылку на другую секцию того же файла`

Как попробовать самому

Во первых, что почитать? Кроме уже указанной спецификации имеет смысл почитать этот файл, в котором команда iovisor собирает информацию, добытую из Linux kernel по eBPF.

Во вторых, как собственно, с этим всем работать? Для начала нужно откуда-то получить ELF-файл. Как сказано на StackOverfow, нам поможет команда

clang -O2 -emit-llvm -c bpf.c -o - | llc -march=bpf -filetype=obj -o bpf.o

Во вторых, нужно как-то получить эталонный разбор файла на кусочки. В обычной ситуации нам бы помогла команда objdump:

$ objdump
Использование: objdump <параметры> <файл(ы)>
 Отображает информацию из объекта <файл(ы)>.
 Должен быть указан по крайней мере один из следующих ключей:
  -a, --archive-headers    Display archive header information
  -f, --file-headers       Display the contents of the overall file header
  -p, --private-headers    Display object format specific file header contents
  -P, --private=OPT,OPT... Display object format specific contents
  -h, --[section-]headers  Display the contents of the section headers
  -x, --all-headers        Display the contents of all headers
  -d, --disassemble        Display assembler contents of executable sections
  -D, --disassemble-all    Display assembler contents of all sections
      --disassemble=<sym>  Display assembler contents from <sym>
  -S, --source             Intermix source code with disassembly
  -s, --full-contents      Display the full contents of all sections requested
  -g, --debugging          Display debug information in object file
  -e, --debugging-tags     Display debug information using ctags style
  -G, --stabs              Display (in raw form) any STABS info in the file
  -W[lLiaprmfFsoRtUuTgAckK] or
  --dwarf[=rawline,=decodedline,=info,=abbrev,=pubnames,=aranges,=macro,=frames,
          =frames-interp,=str,=loc,=Ranges,=pubtypes,
          =gdb_index,=trace_info,=trace_abbrev,=trace_aranges,
          =addr,=cu_index,=links,=follow-links]
                           Display DWARF info in the file
  -t, --syms               Display the contents of the symbol table(s)
  -T, --dynamic-syms       Display the contents of the dynamic symbol table
  -r, --reloc              Display the relocation entries in the file
  -R, --dynamic-reloc      Display the dynamic relocation entries in the file
  @<file>                  Read options from <file>
  -v, --version            Display this program's version number
  -i, --info               List object formats and architectures supported
  -H, --help               Display this information

Но в данном случае она бессильна:

$ objdump -d test-bpf.o 

test-bpf.o:     формат файла elf64-little

objdump: невозможно выполнить дизассемблирование для архитектуры UNKNOWN!

Точнее, секции-то она покажет, а вот с дизассемблированием проблема. Тут мы вспоминаем, что собирали с помощью LLVM. А у LLVM есть свои расширенные аналоги утилит из binutils, с именами вида llvm-<имя команды>. Они, например, понимают LLVM bitcode. А ещё они понимают eBPF — наверняка это зависит от параметров компиляции, но раз уж оно скомпилировало, то и распарсить, наверное, всегда должно. Поэтому для удобства рекомендую создать скрипт:

vim test-bpf.c # Подставить редактор по вкусу
clang -Oz -emit-llvm -c test-bpf.c -o - | llc -march=bpf -filetype=obj -o test-bpf.o
llvm-objdump -d -t -r test-bpf.o

Тогда для такого исходника:

#include <stdint.h>

extern uint64_t z;

uint64_t func(uint64_t x, uint64_t y)
{
    return x + y + z;
}

Будет такой результат:

$ ./compile-bpf.sh 

test-bpf.o:     file format ELF64-BPF

Disassembly of section .text:
0000000000000000 func:
       0:       bf 20 00 00 00 00 00 00         r0 = r2
       1:       0f 10 00 00 00 00 00 00         r0 += r1
       2:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00         r1 = 0 ll
                0000000000000010:  R_BPF_64_64  z
       4:       79 11 00 00 00 00 00 00         r1 = *(u64 *)(r1 + 0)
       5:       0f 10 00 00 00 00 00 00         r0 += r1
       6:       95 00 00 00 00 00 00 00         exit
SYMBOL TABLE:
0000000000000000 l    df *ABS*           00000000 test-bpf.c
0000000000000000 l    d  .text           00000000 .text
0000000000000000 g     F .text           00000038 func
0000000000000000         *UND*           00000000 z

Код.

Часть 1. QInst: лучше день потерять, потом за пять минут долететь (пишем инструментацию тривиально)

Часть 0. Требуется эльф для работы в Матрице. Возможна релокация