[Перевод] Фокусы оптимизации размера исполняемых файлов ELF. Поддержка 4 ОС в 400 байт единственного бинарника
В этом посте я расскажу о некоторых уловках, которыми я воспользовалась, чтобы уменьшить двоичные файлы С/С++/Python с помощью ассемблера для x86. Здесь всё крутится вокруг кодовой базы Cosmopolitan. Дело в том, что из недавнего отзыва по проекту ELKS я узнала, что мой код там всем понравился и они хотят узнать больше о том, что трюки cosmo могут дать проектам вроде «Linux-порта i8086». Я почувствовала, что мы с ребятами проекта ELKS «одной крови», ведь первое, что я написала при создании Cosmopolitan, — это загрузчик i8086, который назывался Actually Portable Executable. А ещё мне было приятно узнать, что людям, которые погрузились в эту проблему гораздо раньше меня, нравятся мои наработки в Cosmopolitan. И тогда я решила, что неплохо было бы поделиться ими с более широкой аудиторией.
![[Shinmyoumaru Sukuna]](https://habrastorage.org/r/w1560/webt/fz/j8/2s/fzj82s9csxx81rj8iyj7ph38l3q.png)
Почему это так важно?
Мне нравится философия UNIX: делать много маленьких программ. Настолько нравится, что в репозитории файлов Cosmopolitan у меня таких программ сотни.
$ git clone https://github.com/jart/cosmopolitan
$ cd cosmopolitan
$ make -j16 MODE=tiny
$ find o/tiny -name \*.com | wc -l
741
Сборка целого репозитория с нуля на моём компьютере занимает всего около 15 секунд. Из 741 исполняемых файлов 403 — текстовые. Здорово, что каждый набор тестов располагается в отдельном исполняемом файле. Так меньше вероятность испортить что-то глобальное одним кривым тестом, который приводит к трудно диагностируемым ошибкам повсюду. По той же причине htop может служить бесплатной панелью мониторинга состояния тестов. Каждый «дотком» — это статический двоичный файл, который ведёт себя как контейнер Docker, так как обычно это zip-файл с данными вендора (например, с данными tzinfo). А я уже писала, что каждый исполняемый файл также работает на семи операционных системах?
# процесс тестирования
for f in $(find o/tiny/test -name \*_test.com); do
for os in freebsd openbsd netbsd rhel7 rhel5 win7 win10 xnu; do
scp $f $os:
ssh $os ./${f##*/}
done
done
Остаётся протестировать 400 программ на 8 поддерживаемых системах (это всего 3200 тестов!) Можно просто скопировать их через scp на каждый хост и запустить. Благораря runit и runitd больше 15 секунд это не займёт. Это значительно повышает производительность и позволяет вести разработку на основе тестов (TDD) с быстрой обратной связью.
Программирование — это непросто, но мы поможем разобраться:
Управляемость процесса построена на малом весе двоичного кода. Чем меньше что-то, тем больше экземпляров этого можно собрать при масштабировании. Это важно не только при работе на старых компьютерах и не только при игре в «код-гольф». Речь идёт о том, что всем нам хочется меньше отдавать, больше иметь и наслаждаться всеми радостями программерской жизни. Вот несколько конкретных примеров того, насколько маленькими могут быть по-настоящему портабельные исполняемые файлы, созданные с помощью Cosmopolitan Libc:
16K o/tiny/examples/hello2.com # вызывает write (links syscall)
20K o/tiny/examples/hello.com # вызывает fputs (links stdio)
24K o/tiny/examples/hello3.com # вызывает printf (links fmt+stdio)
100K o/tiny/test/libc/calls/access_test.com # линкует библиотеку тестов
216K o/tiny/tool/net/redbean-original.com # http/1.1 server
1.8M o/tiny/examples/pyapp/pyapp.com # статически подключаемое приложение Python
Смогла бы я так герметично изолировать этот процесс, если бы писала на языке, которому для двоичного представления нужно 3 Мб? У меня локальная сеть на гигабит. И мне не нужен офис крупной компании с качественным оптоволокном для передачи этих ~100-килобитых тестовых бинарников. Вот несколько расчётов на глаз:
# теоретическое минимальное время передачи тестовых двоичных файлов cosmo в секундах при скорости 1Гбит/с по ЛВС без сжатия
>>: (400*8 * 16*1000) / (1024*1024*1024/8)
0.3814697265625
# теоретическое минимальное время передачи тестовых двоичных файлов go в секундах при скорости 1Гбит/с по ЛВС без сжатия
>>: (400*8 * 3*1000*1000) / (1024*1024*1024/8)
71.52557373046875
Для передачи файлов — много. Нужно меньше. И это «меньше» — даже не о самом масштабировании, а о возможности до него дожить. Cosmopolitan — это работа из множества обрывков. В репозитории сейчас всего 1,5 миллиона строк кода. Пока другие воюют с техническими недоработками, я думаю, как залить на хосты ещё один миллион. «Меньше» — это и об использовании ресурсов. Большое начинается с малого. Кому захочется писать уйму кода с помощью дорогих инструментов? Оплата услуг облачных провайдеров может слить весь ваш бюджет. Altavista запустила весь свой поисковый движок на одном компьютере. А вы говорите, надо подключать Full Story Elecron IDE к кластеру Kubernetes, чтобы отдать всю математику приложению C++. Как это увязать?
![[ABC - Always Be Coding]](https://habrastorage.org/r/w780q1/webt/tm/ad/9b/tmad9bydx60phsofz3ilii3mbkg.jpeg)
Неудачники [это слова автора] всегда жалуются, что всё это не раздутость, а просчитанный компромисс. Но компромисса не существует, и это нужно учесть. Инженеры просто становятся жертвами сложности современных программ. Им уже всё равно. Они просто ждут очередного перерыва, пока код компилируется. Прямо как Дэннис из «Парка Юрского периода». Раздутость похожа на масштабирование бизнеса с созданием фальшивых рабочих мест. Она будоражит умы изголодавшихся по трудным задачам разработчиков, но не даёт никаких преимуществ. Раньше я работала с репозиторием на эксабайты данных. Скажу честно, это мало чем отличалось от работы с самыми маленькими программами в мире, которыми я занялась теперь. Тогда это был просто промежуточный этап, не очень-то привлекающий.
Как увлечённая читательница кодовых баз, я не люблю слишком много кода. Кажется, в этих базах уже десятки лет не было женщины, которая расставила бы всё по полочкам. Особенно это касается открытого кода. Туда нога женщины вообще никогда не ступала. Пора бы это исправить, но, нужно разнообразить её развлечениями. А что может быть веселее кодирования «точно в размер» (size coding)!
Заглянем в бинарник
Мне кажется, самая большая проблема тех, кто пытается оптимизировать код системно, — сложность интуитивного восприятия. Особенно в традиционных шестнадцатеричных редакторах (hex editors). Вот так выглядят данные, закодированные по длине строки:
0002d0b0 01 00 01 03 01 06 01 09 01 0c 01 0f 01 12 14 1e |................|
0002d0c0 01 15 04 1e 01 18 17 1e 01 1e 1c 1e 01 1b 00 00 |................|
0002d0d0 21 01 01 00 02 01 01 00 01 01 09 00 01 01 0a 00 |!...............|
0002d0e0 01 01 01 00 01 01 01 00 03 01 1a 00 04 01 01 00 |................|
0002d0f0 01 01 1a 00 03 01 01 00 81 01 00 00 00 00 00 00 |................|
0002d100 21 01 01 00 02 01 01 00 01 01 16 00 01 01 01 00 |!...............|
0002d110 01 01 1c 00 04 01 01 00 01 01 1a 00 03 01 01 00 |................|
0002d120 81 01 00 00 00 00 00 00 21 01 01 00 02 01 01 00 |........!.......|
0002d130 01 01 09 00 01 01 0c 00 01 01 01 00 03 01 1a 00 |................|
Шестнадцатеричные редакторы хороши, когда вы ищете что-то конкретное, но о форме и виде двоичного кода из них мы узнаём немного. На самом деле вы не смотрите на этот код, как на что-то цельное. Вы просто пристально вглядываетесь в отдельные эмпирические данные. От этого даже зрение становится туннельным. Blinkenlights решает эту проблему при помощи кодовой страницы IBM CP437. Если мы используем её для визуализации тех же данных с кодированием по длине строки, о котором я уже писала выше, мы увидим больше.
![[RLE-кодированные данные в blinkenlights]](https://habrastorage.org/r/w1560/webt/36/yf/v5/36yfv5zpjy0kav8pjzdqlm-acsg.png)
Учтите и то, что такое отображение кода полностью интуитивно. Да, человек, не знакомый с CP437, увидит абракадабру. Но вряд ли кто-то поспорит, что это выглядит лучше, чем сплошная стена из разделителей разрядов, с точки зрения лаконичности, с которой кодируется информация высокой сложности. CP437 — это, по сути, 256-буквенный алфавит. Прокручивая страницу за страницей, вы будете замечать всё и выявлять закономерности. Это магия! Можно догадаться, что делают те или иные данные. Вот, например, таблица косвенных переходов:
![[jumptab.png]](https://habrastorage.org/r/w1560/webt/s8/15/mg/s815mgrn5zyqd2oabufkcchgy-i.png)
Вот так выглядит наш struct при компиляции через __attribute__((__packed__)):
![[packed.png]](https://habrastorage.org/r/w1560/webt/3t/c2/2s/3tc22s_p2k5ysqx6asn4am0okeq.png)
Вот так выглядит код для архитектуры x86–64:
![[x86-64-code.png]](https://habrastorage.org/r/w1560/getpro/habr/post_images/34b/04d/1f7/34b04d1f7264cc1f868704de04a18698.png)
А вот так — /dev/urandom:
![[urandom.png]](https://habrastorage.org/r/w1560/webt/pz/jz/tq/pzjztqhgoh1h_egam-xbjnnw-nk.png)
А это — вид двоичных файлов, генерируемых в UBSAN (Undefined Behavior Sanitizer). Как видите, можно сделать и лучше, и это объясняет, почему двоичные файлы на UBSAN получаются настолько огромными. Дело в плохой упаковке структур (struct).
![[ubsan-bing.png]](https://habrastorage.org/r/w1560/webt/co/ex/pv/coexpv5bhdvue6zwqrfhpjthh5w.png)
Cosmopolitan — это база данных, созданная из ничего. В начале проекта у меня был только пустой файл и ассемблер. Практически каждый байт, попавший после этого в APE, выполнял свою задачу, связанную либо с генерацией, либо с проверкой. Поэтому и два своих первых инструмента для Cosmopolitan Libc я написала именно для этих целей.
-rwxr-xr-x 1 501 jart 52K Jun 9 09:08 bing.com (see bing.c)
-rwxr-xr-x 1 501 jart 32K Jun 9 09:08 fold.com (see fold.c)
Я использую их с оболочкой для скриптов, которая называется ~/bin/bf.
#!/bin/sh
bing.com <"$1" |
fold.com |
exec less
Когда мне хочется заглянуть внутрь файла, я просто набираю эту команду:
bf o//examples/hello.com
Я написала ещё несколько скриптов, которые бывают очень кстати. Вот, например, ~/bin/bloat. Он показывает самые большие символы файла .com.dbg.
#!/bin/sh
nm -C --size "$@" |
sort -r |
grep ' [bBtTRr] ' |
exec less
Организация полей структур
Компоновка структур — бесспорно, хорошая и здоровая привычка, которая способствует снижению размера файла. Например, при просмотре Python 3.6 через bing | fold я заметила одну любопытную вещь. Структура основного парсера Python неоптимальна:
typedef struct {
int s_narcs;
arc*s_arc;
int s_lower;
int s_upper;
int*s_accel;
int s_accept;
} state;
Если бы я просто читала код, то не заметила бы этого. У айсберга всегда есть подводная часть. Структура выше на двоичном уровне эквивалентна следующей:
typedef struct {
int s_narcs;
int __pad1; // четыре байта потрачены впустую
arc*s_arc;
int s_lower;
int s_upper;
int*s_accel;
int s_accept;
int __pad2; // и ещё четыре байта
} state;
Я перенесла поле s_accept на другую строку и срезала по 4 Кб с каждого бинарника Python:
typedef struct {
int s_narcs;
int s_accept;
arc*s_arc;
int s_lower;
int s_upper;
int*s_accel;
} state;
Жизнь состоит из мелочей. Думаю, у некоторых фирм могут быть руководства по стилю, где предпочтение отдано последнему коду. Только из их политики. Ведь с точки зрения читабельности плохо, когда люди ломают головы, выискивая пробелы в ваших структурах, когда им нужна уверенность в правильности кода на двоичном уровне. Таким образом, мы не только экономим место, но и очищаем код.
RLE-кодирование
Сейчас выходит так много новостей о мощных алгоритмах сжатия, как с машинным обучением, так и классических, что многие программисты-самоучки, думаю, даже не знают, что в некоторых случаях хорошо работают гораздо более простые и примитивные алгоритмы. Один из примеров — RLE-кодирование. Пусть у нас есть такая последовательность:
1,1,1,1,1,1,1,1,2,2,2,3
И вы задаёте её как последовательность кортежей {count, thing} со знаком завершения {0,0}.
8,1, 3,2, 1,3, 0,0
Я люблю RLE-кодирование (1) за простоту ручного редактирования потока сжатых данных и (2) за то, что код распаковщика весит всего 14 байт.
/14-байтный распаковщик
/
/@paramdi указывает на буфер вывода
/@paramsi указывает на uint8_t {len₁,byte₁}, ..., {0,0}
/@archx86-64,i386,i8086
/@seelibc/nexgen32e/rldecode.S
rldecode:
31 c9xor%ecx,%ecx
ac0:lodsb
86 c1xchg%al,%cl
aclodsb
e3 05jrcxz2f
aa1:stosb
e2 fdloop1b
eb f5jmp0b
c32:ret
.typerldecode,@function
.sizerldecode,.-rldecode
.globlrldecode
Этот пример прекрасен своей двоичной совместимостью с i8086, i386 и x86–64. Но ассемблер не всегда означает скорость. Для наглядности и эффективности можно взять такой код на С:
struct RlDecode {
uint8_t repititions;
uint8_t byte;
};
void rldecode2(uint8_t *p, const struct RlDecode *r) {
for (; r->repititions; ++r) {
memset(p, r->byte, r->repititions);
p += r->repititions;
}
}
RLE-кодирование подходит только для сжатия разреженных данных, а размер плотных данных RLE удвоит! Но, когда мы облегчаем двоичные файлы, разреженных структур становится много, и RLE-кодирование становится эффективным.
Пример — таблицы преобразования символов веб-сервера redbean для парсинга URI и HTTP-сообщений. Очень многие разработчики, которые пишут на C или C++, приходят к пониманию того, что поиск символов в таблице с 256 записями очень эффективен. Почему? Потому что компилятор C собирает код на C вроде rdi[al & 255] в такие блоки:
movzbl%al,%eax
mov(%rdi,%rax),%al
Это очень быстро и безопасно для памяти. Схемотехники назвали бы это таблицей соответствия или LUT. Это неотъемлемая часть разработки микропроцессоров. Для архитектуры x86 даже написана устаревшая инструкция под названием XLAT, полностью посвящённая этой таблице. Важным применением LUT в HTTP является проверка допустимости символов. Например, многие элементы сообщения HTTP, согласно RFC2616, должны являться базовыми элементами (токенами):
CHAR =
SP =
HT =
CTL =
token = 1*
separators = "(" | ")" | "<" | ">" | "@"
| "," | ";" | ":" | "\" | <">
| "/" | "[" | "]" | "?" | "="
| "{" | "}" | SP | HT
В простом коде на C мы могли бы записать токен LUT так:
const char kHttpToken[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x00
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x10
0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, // 0x20 ! #$%&‘ *+ -.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, // 0x30 0123456789
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0x40 ABCDEFGHIJKLMNO
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, // 0x50 PQRSTUVWXYZ ^_
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0x60 `abcdefghijklmno
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, // 0x70 pqrstuvwxyz | ~
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x80
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x90
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xa0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xb0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xc0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xd0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xe0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xf0
};
Чтобы проверить, допустим ли символ в токене, можно просто ввести kHttpToken[c & 255]. Но, если мы хотим сэкономить 200 байт в двоичном представлении, можно использовать метод RLE-кодирования:
.globlkHttpToken
.section .bss.sort.100.kHttpToken,"aw",@nobits
/@seenet/http/khttptoken.S
kHttpToken:
.zero256
.section .rodata.sort.100.kHttpToken,"a",@progbits
.byte 33,0 # 00-20 ∅-␠
.byte 1,1 # 21-21 !-!
.byte 1,0 # 22-22 "-"
.byte 5,1 # 23-27 #-‘
.byte 2,0 # 28-29 (-)
.byte 2,1 # 2a-2b *-+
.byte 1,0 # 2c-2c ,-,
.byte 2,1 # 2d-2e --.
.byte 1,0 # 2f-2f /-/
.byte 10,1 # 30-39 0-9
.byte 7,0 # 3a-40 :-@
.byte 26,1 # 41-5a A-Z
.byte 3,0 # 5b-5d [-]
.byte 29,1 # 5e-7a ^-z
.byte 1,0 # 7b-7b {-{
.byte 1,1 # 7c-7c |-|
.byte 1,0 # 7d-7d }-}
.byte 1,1 # 7e-7e ~-~
.byte129,0 # 7f-ff ⌂-λ
.byte0,0 # terminator
.section .init.sort.100.kHttpToken,"a",@progbits
callrldecode
В кодовой базе Cosmopolitan есть инструмент для автоматической генерации этих файлов ассемблера:
o//tool/build/xlat.com -TiC ' ()<>@,;:\"/[]?={}' -iskHttpToken
Децентрализованные разделы
Код ассемблера, сгенерированный на xlat.com в предыдущем разделе, может показаться странным даже при большом опыте программирования на ассемблере для архитектуры x86. Это уникальная методика чтения старых кодов из 70-х и 80-х, воскрешённая мной для Cosmopolitan. Назовём её «децентрализованные разделы» (decentralized sections).
Децентрализованные разделы позволяют охватить несколько файлов одной функцией. Канонический пример — _init(), классическая функция UNIX. В большинстве современных кодовых баз её оставляют пустой. Потому что написание _init() — это что-то вроде утраченного искусства с последующей сборкой скриптом редактора связей (линкера).
Работает это так. Ваша libc определяет заглушки кода входных и выходных данных функции _init(). Cosmopolitan Libc (слегка доработанная для уменьшения количества макросов и, как следствие, удобства чтения и копирования) определяет их так:
.section .init_prologue,"ax",@progbits
.globl_init
/@paramr12 is argc (регистр сохранён)
/@paramr13 is argv (регистр сохранён)
/@paramr14 is envp (регистр сохранён)
/@paramr15 is envp (регистр сохранён)
/@noterdi is __init_bss_start (регистр монотонно возрастает)
/@notersi is __init_rodata_start (регистр монотонно возрастает)
/@seelibc/runtime/init.S
_init:push%rbp
mov%rsp,%rbp
lea__init_bss_start(%rip),%rdi
lea__init_rodata_start(%rip),%rsi
.previous/*
...
децентрализованное содержимое
...
*/.section .init_epilogue,"ax",@progbits
_woot:leave
ret
.previous
Ваша libc тоже должна задать заглушки для разделов данных. Технически это можно сделать в скрипте редактора связей, но красивее — записать их в .S, чтобы не определять символы, пока они не будут слинкованы.
.section .init_rodata_prologue,"a",@progbits
.globl__init_rodata_start,__init_rodata_end
.align__SIZEOF_POINTER__
__init_rodata_start:
.previous/*
...
децентрализованное содержимое
...
*/.section .init_rodata_epilogue,"a",@progbits
__init_rodata_end:
.byte0x90
.previous
.section .init_bss_prologue,"aw",@nobits
.globl__init_bss_start,__init_bss_end
.align__SIZEOF_POINTER__
__init_bss_start:
.previous/*
...
децентрализованное содержание
...
*/.section .init_bss_epilogue,"aw",@nobits
__init_bss_end:
.byte0
.previous
Затем настраиваем скрипт редактора связей:
/* смотрите ape/ape.lds */
SECTIONS {
.text . : {
KEEP(*(.init_prologue))
KEEP(*(SORT_BY_NAME(.init.sort.*)))
KEEP(*(.init))
KEEP(*(.init_epilogue))
*(.text .text.*)
KEEP(*(SORT_BY_NAME(.rodata.sort.*)))
*(.rodata .rodata.*)
}
.bss . : {
KEEP(*(SORT_BY_NAME(.bss.sort.*)))
*(SORT_BY_ALIGNMENT(.bss))
*(SORT_BY_ALIGNMENT(.bss.*))
*(COMMON)
}
}
Теперь файлы ассемблера можно писать со вставкой содержимого в функцию _init() вместе с сопутствующими структурами данных __init_rodata_start и __init_bss_start. Разделы данных только для чтения и неинициализированных данных (BSS) опциональны. Обязательно только одно: в отличие от простого двоичного интерфейса System V Application Binary Interface, нашему коду _init () нельзя затирать RDI и RSI. Потому что в них хранятся указатели на жёсткую конфигурацию rodata и bss.
Вот пример применения проще приведённого выше примера с kHttpToken. Допустим, нам нужна поддержка микроархитектур AMD K8 и Barcelona, но при этом полностью использовать SSSE3 (лучшее расширение SSE). Здесь общепринятая практика — запускать идентификацию центрального процессора CPUID после двойной проверки защиты pthread_once(). Потому что при каждом запуске инструкция CPUID занимает 50 нс, в то время как однократная защита усредняется по многим вызовам и требует половину наносекунды. Но есть решение лучше — можно воспользоваться функцией _init(). Необходимость в библиотеках синхронизации уходит на второй план, ведь _init() вызывается перед всеми конструкторами. Поэтому создание каких-либо потоков маловероятно.
.section .bss.sort.100.kCpuid1,"aw",@nobits
/uint32_t kCpuid1[4];
/@seelibc/nexgen32e/kcpuids.S
kCpuid1:.long0,0,0,0
.globlkCpuid1
.typekCpuid1,@object
.sizekCpuid1,.-kCpuid1
.section .init.sort.100.kCpuid1,"a",@progbits
53push%rbx
6a 01push$1
58pop%rax
0f a2cpuid
abstosl
93xchg%eax,%ebx
abstosl
91xchg%eax,%ecx
abstosl
92xchg%eax,%edx
abstosl
5bpop%rbx
Если маркетинг Intel сбивал вас с толку и вы пытались понять по названиям микроархитектур, у каких центральных процессоров какие функции, всё это кратко поясняется в файле microarch.txt.
Приведённые выше строки добавляют всего 14 байт двоичного кода. Они масштабируются в рамках модели разработки. Сколько бы библиотек вы ни включили в кодовую базу, они уживутся с этим процессом и не будут наступать друг другу на пятки. Модель децентрализованных разделов — это золотая жила для исполинских кодовых баз, горячо любимых крупными компаниями. С другой стороны, такой подход позволяет создавать крошечные двоичные файлы, которые обожают инди-разработчики. Это намного проще, чем подтягивать зависимость к -lpthread. Теперь, когда захочется проверить доступность SSSE3, нужно лишь узнать девятые биты ECX, которые мы сохранили ранее:
if (kCpuid1[2][1<<9]) {
// есть ssse3!
} else {
// это k8 или barcelona
}
Если вы пользуетесь другой libc, а не той, что я предлагаю в cosmo (например, musl, glibc), вам подойдёт тот же метод, но с небольшой корректировкой:
.bss
kCpuid1:.long0,0,0,0
.globlkCpuid1
.typekCpuid1,@object
.sizekCpuid1,.-kCpuid1
.section .init,"a",@progbits
53push%rbx
48 8d 3d 00 00 00 00leakCpuid1(%rip),%rdi
6a 01push$1
58pop%rax
0f a2cpuid
abstosl
93xchg%eax,%ebx
abstosl
91xchg%eax,%ecx
abstosl
92xchg%eax,%edx
abstosl
5bpop%rbx
Теперь нам нужно «заплатить» ещё по 7 байт (всего нужен 21 байт), поскольку в Cosmo взаимодействие с жёсткой конфигурацией между _init() / rodata / bss построено уникальным образом. В других библиотеках на C такого нет. В любом случае оба способа на ассемблере очевидно превосходят эквивалент на C/C++, который съест 42 байта.
uint32_t kCpuid1[4];
__attribute__((__constructor__)) static void kCpuid1Init() {
uint32_t ax, bx, cx, dx;
asm("cpuid" : "=a"(ax), "=b"(bx), "=c"(cx), "=d"(dx) : "0"(1));
kCpuid1[0] = ax;
kCpuid1[1] = bx;
kCpuid1[2] = cx;
kCpuid1[3] = dx;
}
Если нотация «Richard Stallman Math 55» для ключевого слова asm() вас озадачила, пояснение есть в файле rmsiface.txt.
Если я поняла нечто важное при работе с Cosmopolitan, это то, что компилятор C при должной сноровке можно заставить выдавать очень лёгкий код, если хочется писать код ассемблера в строковых литералах. GCC и Clang (код ниже) сделают это за 30 байт. Стоит ли дело того или же просто написать всё это в ассемблере — решать вам.
uint32_t kCpuid1[4];
__attribute__((__constructor__)) static void kCpuid1Init() {
uint32_t ax, *di;
asm volatile("cpuid\r\n"
"stosl\r\n"
"xchg\t%%ebx,%%eax\r\n"
"stosl\r\n"
"xchg\t%%ecx,%%eax\r\n"
"stosl\r\n"
"xchg\t%%edx,%%eax\r\n"
"stosl"
: "=a"(ax), "=D"(di)
: "0"(1), "1"(kCpuid1)
: "rbx", "rcx", "rdx", "memory");
}
Больше всего код на C делает неуклюжим необходимость генерировать 8-байтные указатели функций в разделах .ctors. Их нужно отдельно добавлять в редактор связей (линкере). Как правило, ваша библиотека на C вызывает .ctors по завершении _init(). На самом деле, приемлемых способов заставить современный компилятор C сгенерировать код в духе «децентрализованного раздела» нет. Clang тут не подойдёт: он хочет власти над всеми регистрами. Как максимум, можно при помощи GCC сделать следующее:
register long di asm("rdi");
register long si asm("rsi");
__attribute__((__section__(".bss.sort.100.kCpuid1,\"aw\",@nobits #")))
uint32_t kCpuid1[4];
__attribute__((__used__,
__section__(".init.sort.100.kCpuid1,\"a\",@progbits #")))
static void kCpuid1Init(void) {
uint32_t ax;
asm volatile("push\t%%rbx\r\n"
"cpuid\r\n"
"stosl\r\n"
"xchg\t%%ebx,%%eax\r\n"
"stosl\r\n"
"xchg\t%%ecx,%%eax\r\n"
"stosl\r\n"
"xchg\t%%edx,%%eax\r\n"
"stosl\r\n"
"push\t%%rbx"
: "=a"(ax), "+D"(di)
: "0"(1)
: "rcx", "rdx", "memory");
__builtin_unreachable(); // блокируем генерацию инструкции RET
}
Проблема такого кода — хрупкость. Для его правильной работы компилятору нужно передать флаги -ffixed-rdi -ffixed-rsi -fomit-frame-pointer -O -fno-sanitize=all. А ценность компилятора C состоит в возможности нагрузить код инструментами отладки (вроде ASAN), если это понадобится. Так что с кодом вроде этого, где отладчики не нужны, лучше просто писать на ассемблере.
Удаление мёртвого кода
Само собой, если вы используете Libc от Cosmopolitan, все фокусы выше с CPUID уже проделаны за вас, остаётся только написать:
// смотрите libc/nexgen32e/x86feature.h
if (X86_HAVE(SSSE3)) {
// у нас ssse3!
} else {
// это k8 или barcelona
}
Реализация в x86feature.h стоит вашего внимания. Возможно, это самая красивая абстракция из созданных на препроцессоре C. Её можно найти во всей кодовой базе. А ещё она воплощает один из важнейших подходов в написании макроса Cosmopolitan — слияние времени компиляции с проверкой согласования типов во время выполнения. Это необходимо в Actually Portable Executable, где очень важна диспетчеризация во время выполнения. В то же время у нас есть все традиционные возможности настройки всеми любимых флагов define в процессе компиляции. Например, #ifdef здесь можно реализовать так:
#if X86_REQUIRE(SSSE3)
// есть ssse3!
#else
// это k8 или barcelona
#endif
В данном случае ваша программа поддерживает SSSE3, только если пользователь установит флаг компиляции -mssse3. Лучше пользоваться макросом X86_HAVE(), так как он делает то же, что и X86_REQUIRE(SSSE3), за исключением проверки во время выполнения. По умолчанию, если вы не передали никаких флагов микроархитектуры GCC или Clang, обе ветви войдут в двоичный файл.
if (X86_HAVE(SSSE3)) {
// делаем несколько диких хаков ssse3 на ассемблере
} else {
// возвращаемся к медленному коду ansi c
}
Если же пользователь решит передать флаг -mssse3, компилятор при оптимизации устранит всю эту раздутость для поддержки старых моделей ЦПУ, вместе с самой проверкой при выполнении.
if (X86_HAVE(SSSE3)) {
// делаем несколько диких хаков ssse3 на ассемблере
} else {
// возвращаемся к медленному коду ansi c
}
Это как раз то, что MODE=opt делает с конфигурацией сборки Makefile по умолчанию. Компилятор получает флаг -march=native, который запрашивает параметры ЦПУ вашего хоста. После этого Cosmopolitan и GCC совместно создают двоичный файл, адаптированный под ваш компьютер и оптимально быстрый. Цена этого трюка — невозможность передавать такие двоичные файлы на другие машины, ведь там могут быть другие модели процессоров x86.
Основная идея гибридной модели для удаления мёртвого кода и ветвления кода при исполнении проще и лаконичнее всего описана в ape/loader.c и libc/dce.c.
#define LINUX 1
#define METAL 2
#define WINDOWS 4
#define XNU 8
#define OPENBSD 16
#define FREEBSD 32
#define NETBSD 64
#define SupportsLinux() (SUPPORT_VECTOR & LINUX)
#define SupportsXnu() (SUPPORT_VECTOR & XNU)
#define SupportsFreebsd() (SUPPORT_VECTOR & FREEBSD)
#define SupportsOpenbsd() (SUPPORT_VECTOR & OPENBSD)
#define SupportsNetbsd() (SUPPORT_VECTOR & NETBSD)
#define IsLinux() (SupportsLinux() && os == LINUX)
#define IsXnu() (SupportsXnu() && os == XNU)
#define IsFreebsd() (SupportsFreebsd() && os == FREEBSD)
#define IsOpenbsd() (SupportsOpenbsd() && os == OPENBSD)
#define IsNetbsd() (SupportsNetbsd() && os == NETBSD)
Один из примеров гибкости APE — возможность настраивать сборку вот так:
make MODE=tiny CPPFLAGS+=-DSUPPORT_VECTOR=0b00000001
Если вам нужен бинарник «hello world» на 4 Кб, который работает только на Linux и не содержит лишние 12 Кб для поддержки Windows, MacOS, FreeBSD, NetBSD, OpenBSD и выгрузки из BIOS «на голом железе», один из лучших вариантов — использование только операционных систем ELF. Просто установите соответствующие биты для Linux + BSD.
make MODE=tiny CPPFLAGS+=-DSUPPORT_VECTOR=0b01110001
δzd-кодирование
Python — один из наиболее оптимальных по размеру кода в базе Cosmopolitan. Здесь нам пришлось выйти за рамки «код-гольфа» и ради лёгкого кода пустить в ход кое-что потяжелее. Лучшее оружие в своём арсенале (которое сжало статически связанные двоичные файлы Python до 2 Мб) мы называем схемой сжатия Delta Zig-Zag Deflate или, для краткости, δzd.
Это не обобщённый алгоритм сжатия типа DEFLATE с кодированием Хаффмана (с RLE наподобие LZ4). Это узкоспециализированный алгоритм, эффективный только для определённых видов исполняемого содержимого. При программировании нужно самостоятельно решать, какой метод сработает лучше всего. Однако δzd показал отличные результаты.
Как вам такая дилемма? Алфавиты китайского, японского и корейского языков огромны. Некоторые их символы до сих пор даже не согласуются с UTF-8. При этом есть множество индивидуальных наборов символов, и все они поддерживаются Python. Для поддержки CJK таблицы стандарта UNICODE тоже должны иметь огромный размер. Большинству людей за пределами трёх стран не нужны эти данные в двоичных файлах, но мы предпочитаем держать их там ради инклюзивности и поддержки таких языков как Python — чтобы в случае надобности раскинуть огромный шатёр, в котором будут рады всем.
С помощью способа упаковки δzd можно значительно уменьшить эти таблицы соответствий. Тогда пользователю не придётся расплачиваться за неиспользуемые им функции. Один из множества нуждающихся в такой обработке символов в кодовой базе Python — это _PyUnicode_PhrasebookOffset2 с начальным размером 178 Кб. С помощью delta-кодирования, zig-zag-кодирования и затем, наконец, DEFLATE он сжимается до 12 Кб. Таким образом мы выигрываем у DEFLATE с чистым кодированием Хаффмана и у BZIP2 с преобразованием Барроуза — Уилера в 10 раз!
_PyUnicode_PhrasebookOffset2: size is 178,176 bytes
_PyUnicode_PhrasebookOffset2: packed size is 100,224 bytes
_PyUnicode_PhrasebookOffset2: rle size is 282,216 bytes
_PyUnicode_PhrasebookOffset2: deflate size is 52,200 bytes
_PyUnicode_PhrasebookOffset2: bz2 size is 76,876 bytes
_PyUnicode_PhrasebookOffset2: δleb size is 47,198 bytes
_PyUnicode_PhrasebookOffset2: δzd size is 12,748 bytes
По адресу third_party/python/Tools/unicode/makeunicodedata.py можно узнать больше о том, как эти таблицы разделены. Представление Python для кодирования Delta-ZigZag-DEFLATE также может выглядеть так:
def uleb(a, x):
while True:
b = x & 127
x >>= 7
if x:
a.append(b | 128)
else:
a.append(b)
break
def zig(x):
m = (2 << x.bit_length()) - 1
return ((x & (m >> 1)) << 1) ^ (m if x < 0 else 0)
def zleb(a, x):
return uleb(a, zig(x))
def δzd(data):
n = 0;
i = 0
p = 0
a = bytearray()
for x in data:
zleb(a, x - p)
p = x
return deflate(a), len(a)
Код на C для распаковки сжатых данных Python можно прочитать в libc/x/xloadzd.c, libc/fmt/unzleb64.c, libc/runtime/inflate.c и third_party/zlib/puff.c. Лучший из них — Puff. Это оптимизированная по размеру, но не такая быстрая версия zlib, которую написал Марк Адлер. Там проходит только распаковка в DEFLATE с двоичным остатком 2 Кб. Когда нужна правильная распаковка в DEFLATE, ключевые библиотеки Cosmopolitan Libc очень часто дают на Puff сильную ссылку (strong link) как на «сильное звено», а на zlib — слабую (weak link) (поскольку эти библиотеки не могут зависеть от вещей вроде malloc). Поэтому Puff используется по умолчанию, если более быстрая библиотека zlib не имеет сильной ссылки, связывающей её с чем-то другим.
Перекрытие функций
Если языки программирования высокого уровня, такие как C, — замок изо льда, а ассемблерный код — вершина айсберга, то кодирование Intel с переменной длиной поля записи (variable length encoding) — подводная часть того же айсберга. Именно оно быстро делает загрузочные сектора доступными лишь посвящённым, поскольку их трудно визуализировать программным способом. Вот пример:
/ %ip is 0
mov $0xf4,%al
ret
/ %ip is 1
.byte 0xb0
wut: hlt \# and catch fire
retВсё — как в шахматах, где ход на соседнюю клетку меняет всю партию. А здесь — перемещение счётчика команд на единицу меняет всю программу x86. Мы можем обратить это в свою пользу, ведь это даёт нам возможность кодировать функции с перекрытием.
/ SectorLISP code.
89 D6 Assoc: mov %dx,%si
8B 3C 1: mov (%si),%di
8B 30 mov (%bx,%si),%si
AF scasw
75 F9 jne 1b
F6 .byte 0xF6
8B 39 Cadr: mov (%bx,%di),%di
3C .byte 0x3C
AF Cdr: scasw
8B 05 Car: mov (%di),%ax
C3 ret
89 D6 Assoc: mov %dx,%si
8B 3C 1: mov (%si),%di
8B 30 mov (%bx,%si),%si
AF scasw
75 F9 jne 1b
F6 8B 39 3C AF testw $0xaf,0x3c39(%bp,%di)
8B 05 mov (%di),%ax
C3 ret
8B 39 Cadr: mov (%bx,%di),%di
3C AF cmp $0xaf,%al
8B 05 mov (%di),%ax
C3 ret
AF Cdr: scasw
8B 05 mov (%di),%ax
C3 ret
8B 05 Car: mov (%di),%ax
C3 retОптимизация printf
С точки зрения размера кода одна из проблем printf(), — тяжёлые зависимости, которые эта функция тянет за собой:
- gdtoa требуется для форматирования типов double и long double через
%f,%gи т. п. При форматировании плавающей точки здесь появляется глубина и выделяется память. Поэтому связываниеgdtoaдобавляет около 32 Кб двоичного кода. - Для форматирования строк с выравниванием по ширине (через
%*sи т. п.) с поддержкой Юникода нужна таблица ширины CJK, которая показывает, займёт ли терминальный символ две ячейки. Это возможно, например, в случае китайских иероглифов или эмодзи. - Форматирование директивой GNU
%mдляstrerror()в Cosmopolitan чуть более затратно: там системным кодом служат не символы, а магические числа. А значит, дляstrerror()нужно взять сразу все переменныеerrno. Необходимо также встроить кучу строк ошибок и инструменты для их получения через API WIN32. К размеру бинарника это добавляет около 8 Кб.
И всё же, несмотря на всю раздутость функции printf(), двоичные файлы, которые случайно связываются с ней (например, examples/hello3.c) могут занимать всего 24 Кб. И всё благодаря макросу PFLINK().
/* см. libc/fmt/pflink.h */
/* см. libc/stdio/stdio.h */
#define printf(FMT, ...) (printf)(PFLINK(FMT), ##__VA_ARGS__)
#define PFLINK(...) _PFLINK(__VA_ARGS__)
#define _PFLINK(FMT, ...) \
({ \
if (___PFLINK(FMT, strpbrk, "faAeg")) STATIC_YOINK("__fmt_dtoa"); \
if (___PFLINK(FMT, strpbrk, "cmrqs")) { \
if (___PFLINK(FMT, strstr, "%m")) STATIC_YOINK("strerror"); \
if (!IsTiny() && (___PFLINK(FMT, strstr, "%*") || \
___PFLINK(FMT, strpbrk, "0123456789"))) { \
STATIC_YOINK("strnwidth"); \
STATIC_YOINK("strnwidth16"); \
STATIC_YOINK("wcsnwidth"); \
} \
} \
FMT; \
})
#define ___PFLINK(FMT, FN, C) \
!__builtin_constant_p(FMT) || ((FMT) && __builtin_##FN(FMT, C) != NULL)
Это работает только в GCC, но никак не в Clang. И работает это, потому что первый аргумент printf () — почти всегда строковый литерал. GCC хватает «ума» для запуска функций вроде __builtin_strstr() во время компиляции. Это что-то вроде функции constexpr на C++. Когда GCC определяет, что нужная нам функция много весит, она делает с соответствующим символом то, что мы называем «выдёргиванием» (yoinking).
Вот как это работает: с двоичными файлами ELF можно проделать трюк, который я назвала бы «игрой в слабое звено со слабыми ссылками» (weak linking). Реализация printf () имеет код вроде такого:
case 'm':
p = weaken(strerror) ? weaken(strerror)(lasterr) : "?";
signbit = 0;
goto FormatString;
Когда функция объявлена операцией weaken «слабым звеном», она не попадает в конечный двоичный файл, если к ней не будет сильного (strong reference) или нормального (normal reference) обращения от другого модуля. Один из способов добиться попадания в двоичный файл — «выдернуть» (yoink) её. Однако «выдёргивание» предназначено для особой ситуации, когда нет кода, который использует символ, но всё равно хочется перетащить его в двоичный файл.
.section .yoink
noplsymbol
.previous
Поэтому с помощью макроса «yoink» мы создаем ссылку внутри раздела, которая явно отбрасывается скриптом редактора связей:
/DISCARD/ : {
*(.yoink)
}
Поэтому, даже если ссылка в конечном счёте будет отброшена, она всё равно сможет заставить ld.bfd вывести объект ссылки в конечный двоичный код.
Метод не идеален, но он того стоит. Большие программы неявным образом «выдернут» всё необходимое на довольно долгое время, а значит, для таких программ это не проблема. А вот в маленьких редактору связей иногда может явно потребоваться помощь. Например, вы можете иногда совершить грехопадение с точки зрения безопасности и использовать нелитеральные строки. В этом случае волшебный макрос «выдернет» все строки, оставляя их незаметными в процессе компиляции. Если вы всё ещё хотите оставаться «на лёгкой стороне силы», то можете потом «расколдовать» эти строки вызовом printf():
(printf)("last error is %m\n");
Наконец, все приведённые в PFLINK() функции, которые вам нужны, можно явно «выдёргивать» при помощи вашего модуля main().
STATIC_YOINK("strerror");
Маленький портабельный ELF
На странице «Насколько толстым должен быть толстый двоичный формат?» можно в интерактивном режиме создавать двоичные файлы Cosmopolitan Actually Portable Executable. Как видим, такие свойства, как SUPPORT_VECTOR, дают пользователю всю мощь и гибкость настроек, необходимую, чтобы сделать его программы настолько малыми, насколько этого захочется [конечно, в пределах возможного].
Но представим на минутку, что наши цели ограничиваются ELF, такими как Linux, FreeBSD, NetBSD и OpenBSD. А ещё представим, что вы хотите создать двоичный файл,
