A pure-software rasterizer for low-end devices

Tiny circuit for 0.5 redstone tick delay (JE)

#dev #cpp

Вы все, конечно, знаете, что локальные функции в C++ нужно помечать словом static, потому что если не пометить, линкер ругнется на то, что у вас двойное определение:

// a.cpp
#include <cstdio>

void foo() {
  puts("foo from a");
}

// b.cpp
#include <cstdio>

void foo() {
  puts("foo from b");
}

/usr/bin/ld: /tmp/b-46f1fb.o: in function `foo()':
b.cpp:(.text+0x0): multiple definition of `foo()'; /tmp/a-2156f5.o:a.cpp:(.text+0x0): first defined here

Его можно понять, ведь все функции в C++ по умолчанию глобальны. Но сейчас я хочу на всякий случай напомнить, что static надо ставить не потому, что линкер ругается, а потому, что это UB, и как каждое другое UB, ODR violation ловится не всегда. Вот этот забавнейший кусок кода:

// a.cpp
#include <cstdio>

__attribute__((noinline))
inline void foo() {
  puts("foo from a");
}

__attribute__((always_inline))
inline void bar() {
  puts("bar from a");
}

void a() {
  foo();
  bar();
}

// b.cpp
/* то же самое с b вместо a */

// main.cpp
void a(void);
void b(void);

int main() {
  a();
  b();
}

...компилируется без ворнингов на -Wextra и выводит

foo from a
bar from a
foo from a
bar from b

Если вы не в курсе, механизм компиляции inline-функций немного необычный. inline — это не про инлайнинг (для этого есть атрибуты), а исключительно выключалка для проверки ODR. Каждая единица трансляции собирает свою копию inline-функции, а в итоговом исполняемом файле они "склеиваются", и остается только одна копия. bar помечена как always_inline, поэтому она резолвится внутри единицы трансляции, а вот вызов в foo остается и приводит к необычным эффектам.

Ухудшает ситуацию то, что inline-функции люди пишут не то чтоб прям часто, а вот шаблонные функции, которые тоже неявно inline, чтобы можно было засунуть реализацию в заголовочный файл — каждый день. То есть если у вас вдруг каким-то чудом в двух библиотеках авторы забыли сделать локальную шаблонную функцию map статической, вам будет больно. Ну или не будет, если одна из них достаточно мелкая, чтобы заинлайниться.

Еще бывает прикольно, когда функция вроде как одна, но собирается в разных местах с разными #defineами. На первый взгляд ODR violation нет, на второй — вы начинаете интерпретировать UCS-2 текст как ASCII.

Весело, в общем.

В продолжение этой катавасии идут локальные шаблонные классы с generic названиями в духе Node, авторы которых не подумали, что конструктор, да и все другие методы, надо бы сделать статическими:

// a.cpp
#include <cstdio>

template<typename T>
struct Foo {
  int field;

  Foo() {
    puts("construct a");
  }
};

void a() {
  Foo<int> tmp;
}

// b.cpp
/* то же самое с b вместо a */

// main.cpp
void a(void);
void b(void);

int main() {
  a();
  b();
}

construct a
construct a

Но static в классах означает совсем другое, поэтому вместо него надо использовать анонимные namespaceы. Если класс обернуть в inline namespace { ... }, то проблема уйдет. Функции, кстати, тоже можно туда засунуть, вместо того, чтобы писать static. Вроде хорошая идея, но потом вы случайно создадите анонимный namespace внутри заголовочного файла, и вашему ICFу придется работать в двадцать раз сильнее.

Можно еще использовать именованные пространства имен, это что-то в духе золотой середины, только надо понимать, что уникальность имен namespace'ов никто не проверяет, а популярные либы любят брать себе generic имена типа testing (looking at you, Google Test), так что вам придется взять себе в качестве названия UUID.

Размышления о том, почему на дворе 2025 год, а namespace { ... } нужно писать даже с модулями (хотя ODR violation они ловят), оставлю за кадром.

#dev #cpp #rust

Есть баян, что вот в таком коде функция в качестве коллбека менее эффективна, чем лямбда:

#include <cstdio>

__attribute__((noinline))
void invoke_callback(auto callback) {
    callback();
}

void my_callback() {
    puts("invoke via function");
}

int main() {
    invoke_callback(my_callback);

    invoke_callback([]() {
        puts("invoke via lambda");
    });
}

Ларчик открывается просто: my_callack мгновенно превращается в указатель на функцию, и invoke_callback приходится делать непрямой вызов по указателю. Лямбда же является уникальным типом с фиксированным перегруженным operator(), поэтому коллбек спокойно инлайнится. Не менее баян, что в Rust это не проблема, и

#[inline(never)]
fn invoke_callback(callback: impl FnOnce()) {
    callback();
}

fn my_callback() {
    println!("invoke via function");
}

#[no_mangle]
fn main() {
    invoke_callback(my_callback);

    invoke_callback(|| {
        println!("invoke via lambda");
    });
}

работает эффективно в обоих случаях, ведь в Rust функции являются не указателями, а анонимными ZST-типами, прям как лямбды. А вот вам не баян: оказывается, если заменить вызов invoke_callback на invoke_callback(my_callback as fn()), чтобы произошел вызов по указателю, производительность не ухудшится! Почему?

Здесь происходит нечто в духе девиртуализации. При интер-процедурном анализе компилятор видит, что аргумент invoke_callback<fn()> — это всегда указатель на my_callback, поэтому callback() можно оптимизировать до my_callback().

Почему Clang не может сделать то же самое, ведь он тоже использует LLVM? Может, если invoke_callback сделать статической функцией (GCC тоже делает девиртуализацию, но потом не инлайнит вызов). Функции без static же видны из других единицах трансляции, поэтому вполне возможно, что кто-нибудь "снаружи" вызовет invoke_callback<void (*)()> с аргументом помимо my_callback, и в этом случае оптимизация неприменима.

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

Забавно, что даже то, что invoke_callback — шаблонная функция, не помогает, хотя, казалось бы, раз каждый cpp-файл #include'ит в себя заголовок с реализацией шаблонной функции, то проводить оптимизацию в рамках единицы трансляции корректно. Это не так по двум причинам.

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

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

// a.cpp
#include <iostream>

template<typename T>
void print(T value) {
  std::cout << value;
}

template void print<int>(int value);
template void print<const char*>(const char* value);

// main.cpp
template<typename T>
void print(T value);

int main() {
  print(2);
  print(" + ");
  print(2);
  print(" = ");
  print(4);
  print("\n");
}

Конструкция с template без угловых скобок инстанциирует шаблонную функцию для данного T, и другие единицы линковки потом могут к этим инстансам линковаться. (Попытка использовать в main.cpp print с неинстанциированными типами при этом приведет к ошибке линковки.)

Напоследок приведу еще один похожий пример. Как должно было стать ясно из текста выше, __attribute__((noinline)) еще не означает, что inter-procedure optimizations при этом отключаются, и периодически из-за этого создается ощущение, будто атрибут не сработал (https://godbolt.org/z/Eja43fMfr, Clang only):

__attribute__((noinline)) int f(int x) { return x; }
int g(int x) { return f(x); }

f(int):
        mov     eax, edi
        ret

g(int):
        mov     eax, edi
        ret

На это корректно смотреть так. Компилятор отслеживает некоторые очень простые соотношения между входными аргументами и выходом функции и благодаря этому может вместо возвращаемого значения функции использовать сразу аргумент. Иными словами, return f(x); оптимизируется до f(x); return x;, потому что где-то записано, что f возвращает значение аргумента. После этого отдельной оптимизацией вызов f удаляется, потому что это чистая функция. В более сложном случае, когда f не чистая, этот вызов остается, но оптимизация возвращаемого значения все еще присутствует (https://godbolt.org/z/Y1Prj9q93):

void side_effect(void);

__attribute__((noinline))
static int f(int x) {
    side_effect();
    return x;
}

bool g(int x) {
    return f(x * 2) == x * 2;
}

g(int):
        push    rax
        call    f(int, int)
        mov     al, 1
        pop     rcx
        ret

f(int, int):
        jmp     side_effect()@PLT

Здесь произошло сразу несколько интересных вещей:

1. g всегда возвращает 1, а не проводит честное сравнение, потому что компилятор знает, что f(x * 2) возвращает x * 2.
2. f помечена как noinline, поэтому вызов f остается, а не превращается в вызов side_effect.
3. Поскольку возвращаемое значение f теперь игнорируется, f даже не пытается вернуть x, а сразу делает tail call.
4. Поскольку f теперь не использует свои аргументы, g даже не пытается их передавать.

Так оказывается, что в достаточно сложном коде единственное, на что влияет noinline — делается ли call на f и затем тут же jmp на side_effect, или сразу call на side_effect.

(И да, умножение на 2 нужно для того, чтобы удостовериться, что x не передается напрямую из g в f просто своим присутствием в edi.)

Если вы все ждали, когда это произойдет: на free-плане GitHub CI наконец появился arm64 Linux!

...со сломанным железом:
https://github.com/rust-lang/rust/issues/135867
https://github.com/orgs/community/discussions/149715
https://github.com/actions/partner-runner-images/issues/36
https://github.com/rust-lang/rust/issues/135939

#dev #rust

Last week has been hectic: среди прочего допиливала напильником Lithium и подумала, что будет весело рассказать, сколько всего сломалось в таком маленьком проекте.

- Переключилась на ARMовский раннер от GitHub на CI, получила фликеры.

- Переменной окружения CARGO_TARGET_..._RUNNER можно сказать, каким скриптом запускать программы при cargo run. Нужно для кросс-тестирования. Оказывается, там не синтаксис шелла, а просто сплит по пробелам. Под виндой эскейпинг решил заэкранировать \, CI сдох.

- На том же CI сломался valgrind, потому что появилась утечка в std. Единственная намеренная на текущий момент! Ну, по крайней мере, из известных мне.

- Нужно написать функцию, которая гарантированно выйдет из программы с данной ошибкой в ситуации, когда продолжать работу нельзя. Пишу eprintln!("{message}"); std::process::exit(1);. Сигнатура fn(&str) -> !, вроде все нормально. eprintln! кидает панику, из функции происходит unwind, сверху запускается деструктор или происходит еще что похуже. Fin.

- nightly rustc обновился и начал генерировать код под WASM, который не понимает старый NodeJS. Из-за этого сломался CI. Почему NodeJS старый? Потому что докер-контейнер из cross для кросс-тестирования никто не обновлял кучу времени, потому что проект сдох.

- #[repr(align(16384))] роняет rustc по SIGILL. Иногда.

- Unwinder Wine'а недописан и генерирует бесконечные стектрейсы. Rust выводит стектрейсы на паниках, но обрубает их после 100го фрейма. В какой-то момент Rust решает, что паник было многовато, мы вот-вот упадем, и надо бы помочь уже программисту и вывести стектрейс целиком...

- #[thread_local] unsound под *-pc-windows-gnu, но при этом компилируется и на первый взгляд работает. На практике линкер от binutils не умеет их выравнивать, ближайшая оптимизированная SIMDом копия дает недетерминированный STATUS_ACCESS_VIOLATION.

- #[thread_local] sound под *-pc-windows-msvc и *-pc-windows-gnullvm, потому что у них линкер свой, который заполняет структуры PE правильно. Жаль только, что Wine смотрит на них, как баран на новые ворота...

- rustc обновил LLVM, под WASMом начало проходить на один тест больше. Теперь делов-то, осталось rustc пропатчить. Сбилдила локальный rustc, получила LLVM assertion failure на "Hello, world!". Выключила ассерты, получила ud2 в другом месте на другом тесте. Удалила локальный rustc.

А на скольки внешних багах заблочены ваши петы?

Clang 19 научился компилировать битреверс

long bit_reverse(long x) {
    return __builtin_bitreverse64(x);
}

в

bit_reverse:
        vmovq   xmm0, rdi
        vgf2p8affineqb  xmm0, xmm0, qword ptr [rip + .LCPI0_1]{1to2}, 0
        vmovq   rax, xmm0
        bswap   rax
        ret
.LCPI0_1:
        .byte   1
        .byte   2
        .byte   4
        .byte   8
        .byte   16
        .byte   32
        .byte   64
        .byte   128

Интересно, думали ли Intel о том, что умножением матриц будут пользоваться для general-purpose перестановки битов
Посмотреть самим: https://godbolt.org/z/GdTz4Psoc
Смешно (смеемся): https://www.youtube.com/watch?v=2O_DG4PWecA

Сишники, это вам

https://www.wikihow.com/Check-Null-in-C

#dev

Все мы знаем, что разыменовывать нулевой указатель плохо, потому что программа крашнется и вообще это UB, отстаньте. На самом деле, за этим утверждением скрывается много всякого интересного и неожиданного.

Начнем с того, что есть нуль, а есть ноль. NULL не обязан иметь адрес 0 и, например, на некоторых архитектурах и интерпретаторах C это не так. Прагматичным людям из POSIX это не нравится, поэтому там NULL всегда имеет адрес 0. Впрочем, не обязательно даже уходить далеко в прошлое: amdgcn определяет NULL как -1, так что встретиться с таким сегодня вполне реально. Типичное определение NULL как (void*)0 на таких машинах все еще работает, потому что (void*)0 стандарт определяет равным NULL, но вот int x = 0; (void*)x портабельно NULL не даст.

Как вытекает из предыдущего, ничего особенного в адресе NULLа нет, и в железе никто не запрещает существовать странице по адресу 0. Железу плевать на то, какие правила накладывает стандарт C, и поэтому, например, на процессорах x86 в real mode по адресам 0 — 256 хранятся таблицы прерываний. Разыменовывать адрес 0 в C все еще UB, но вот 1 разыменовать никто не запрещает.

Впрочем, одно дело — UB по стандарту, другое — поведение на практике. В прошлом стандарт C воспринимался скорее как гайдлайн, чем правила. Старые компиляторы не делали умных оптимизаций, и вообще Ритчи не подразумевал, что за счет UB будут оптимизировать, поэтому на многих платформах разыменование нулевого указателя только и делало, что читало значение в памяти по адресу 0. Компилятор C на HP-UX (это были еще те времена, когда свободных компиляторов C не было, и под каждую платформу были свои компиляторы, зачастую платные), например, давал опцию: мапать страницу по адресу 0, чтобы *(int*)NULL возвращало 0 (гарантированно! без современного понимания UB!), или не мапать, чтобы падало.

В современном мире писать по адресу, совпадающему с адресом NULL, опасно прям совсем. В embedded, где такое периодически приходится делать, у этой проблемы есть два решения: молоток и микроскоп. Во-первых, можно написать код для записи по адресу 0 на ассемблере, железо сожрет. Во-вторых, иногда железо игнорирует старшие биты адреса, поэтому можно записывать не по адресу 0, а, например, по адресу 0x80000000, который железо воспримет так же, а компилятор проинтерпретирует корректно.

Хочется верить, что по крайней мере на современных платформах разыменовывание NULL (если его не выкинет компилятор, конечно) приведет к сегфолту или чему-то подобному. Это не так. Во-первых, Linux поддерживает флаг personality MMAP_PAGE_ZERO, аллоцирующий страницу по адресу 0 на старте программы для совместимости с System V. Во-вторых, даже без этого вы можете с помощью mmap аллоцировать страницу по адресу 0 руками — этим даже пользовались эмуляторы.

Потом эту лавочку прикрыли, и даже не потому, что это скрывает баги в программах на C. Ну, точнее, ровно поэтому, только программой на C здесь выступает само ядро. Достаточно большое количество ядерных эксплоитов того времени заключалось в том, чтобы дата рейсом или иным методом заставить ядро разыменовать нулевой указатель. Поскольку внутри ядра (была) видна память текущего процесса, это приводило к тому, что пользовательская память начинала интерпретироваться как ядерные структуры. Чтобы этого избежать, сейчас Linux не позволяет аллоцировать страницы ниже адреса sysctl vm.mmap_min_addr — 64 кибибайта на большинстве устройств. (Нет бы писать без багов...)

На этом история с разыменованием нуля могла бы закончиться: в Windows ограничение на память на малых адресах было уже давно, в Linux ввели, других операционных систем не существует. Но хипстеры придумали WebAssembly, и поскольку с ним вопрос об изоляции внутри контейнера не встает, по адресу 0 здесь вполне есть доступная память. Некоторых это бесит, некоторых удивляет, меня — радует, ибо нефиг проталкивать ограничения уровней абстракции вниз (впрочем, с этим в WebAssembly проиграли в других местах).

Такие дела.

#dev

https://purplesyringa.moe/blog/falsehoods-programmers-believe-about-null-pointers/

^ mostly the same content in a different form, integrating additional information from comments

Через неделю начнется соревнование по информационной безопасности, которое организую в частности я: 2025.ugractf.ru. Мы работаем в жанре jeopardy, т.е. даем много независимых задач, из которых надо как можно больше решить за 36 часов. Если вы примерно знаете что-то про компьютеры и безопасность (полагаю, большинство здесь), но не настолько прокачались, что меньше, чем DEF CONом вас не заинтересуешь — приходите, будет весело. Наша основная аудитория — школьники и студенты, но мы готовим задачи самой разной сложности и позволяем участвовать кому угодно.

А пока соревнование не началось и чтоб меня не обвинили в пустой рекламе, держите кек из разработки заданий в этом году.

У нас есть собственная система изоляции контейнеров, по сути легковесный Docker, чтобы можно было дешево поднимать по контейнеру на команду, а не давать всем доступ в одну систему. Контейнеры, понятное дело, имеют изолированную от хоста файловую систему, поэтому для доступа в корень контейнеры мы используем procfs: /proc/<pid>/root — это виртуальная директория, в которую ядро проецирует корень FS, как его видит процесс с данным PID.

У контейнеров есть healthcheck'и, чтобы не проксировать, например, HTTP-запросы до того, как контейнер поднимется. Для коммуникации в контейнерах мы используем не TCP (нужно аллоцировать порты, IPшники, а вдруг не хватит, а как аккуратно прокидывать через netns, etc.), а Unix-domain sockets, которые видны как файлы в файловой системе. Обычно каждый сервис выставляет внешний UDS в /tmp/app.sock, который принимает, например, HTTP-запрос, парсит, и проксирует дальше в /proc/<pid>/root/tmp/app.sock нужного контейнера.

Как вы можете заметить, названия сокетов снаружи и внутри контейнера совпадают, хотя, строго говоря, ничего этого не требует. Так получилось, что в одной из задач в этом году мы захотели использовать разные пути... после чего соединения радостно начали виснуть без видимой причины.

Разгадка. Healthcheck увидел, что файла /proc/<pid>/root/tmp/app.sock нет, и решил подождать, пока он создастся. Поскольку путь к файлу составлялся руками чуть ли не конкатенацией, в этот момент он прогонялся через realpath, чтобы его нормализовать и получить более-менее уникальный идентификатор, об который не обломаются библиотеки для inotify. realpath увидел, что /proc/<pid>/root — символическая ссылка (что странно, но терпимо), зарезолвил ее в / и сократил путь просто до /tmp/app.sock — то есть вместо создания файла во внутреннем контейнере мы ожидали создания файла с тем же именем во внешнем. Проще говоря, healthcheck на существование файла все это время был бесполезен. Раньше это компенсировалось тем, что мы все равно ждали, когда сокет начнет принимать соединения уже по правильному пути, а с переименованием сокета это перестало работать вообще.

А теперь вопрос: почему /proc/<pid>/root — это символическая ссылка на /, хотя в /proc/<pid>/root видны не те же файлы, что в /? Дело в том, что это виртуальный файл — ядро нестандартно определяет для него набор операций. Есть операция get_link, возвращающая по сути inode директории, а есть операция readlink, возвращающая путь, на который указывает симлинк. В норме get_link реализован через readlink, а readlink просто возвращает то, что хранится в файловой системе. Но в случае с /proc/<pid>/root все наоборот: get_link первичен, а вот readlink пытается восстановить путь пост-фактум. Как жаль, что во время этого процесса он восстанавливает путь только до корня текущего контейнера — то есть всегда выдает /.

Несколько оффтоп, но мне ВНЕЗАПНО понадобилось установить Windows на старый MacBook Air, а нормальная установка через UEFI не работала, решила написать инструкцию на будущее для себя и на случай, если кому-то ещё понадобится:

https://gist.github.com/purplesyringa/0083a8b553df3a22b55136289dcd2f7e