Как malloc сломала JPGLoader в Serenity, или как выиграть в лотерее

Пару лет назад мне выпала возможность расследовать в SerenityOS интересный баг, связанный с декодированием изображений JPG, которые по какой-то причине при просмотре выглядели так, как вы видите выше.

Странно, не так ли? Похоже, будто просто перепутали RGB и BGR. При этом внесение в JPGLoader.cpp следующего изменения:

-   const Color color { (u8)block.y[pixel_index], (u8)block.cb[pixel_index], (u8)block.cr[pixel_index] };
+   const Color color { (u8)block.cr[pixel_index], (u8)block.cb[pixel_index], (u8)block.y[pixel_index] };
    context.bitmap->set_pixel(x, y, color);

приводит к корректному показу картинки. Вроде бы можно считать дело закрытым!

…Но нет. Возникает вопрос, почему вообще произошёл этот сбой?

Судя по информации Git, последнее сохранённое изменение в JPGLoader.cpp на тот момент было внесено более месяца назад:

Лог коммитов в момент сбоя JPGLoader

И я прекрасно помнил, что ещё пару недель назад JPG открывались нормально, так как тогда я как раз установил фоновую картинку и определённо заметил бы какие-то неполадки.

Что ж, бинарный поиск (имеется в виду git bisect, — прим. пер.) в помощь! Я не знал, с чего начать, поэтому выбрал последние 1 000 коммитов (которые давали корректные изображения) и приступил.

▍ Трудности поиска

Если вы не хотите читать мой нудёж про C++, то лучше сразу переходите к следующему разделу.
SerenityOS — это Unix-подобная операционная система, в которой также есть собственная стандартная библиотека AK (Agnostic Kit). Эта библиотека аналогична STL в C++, но является более читаемой, так как не обременена поддержкой всевозможных операционных систем и обязательством следовать чудовищным стандартам написания кода.

Плюсом нахождения стандартной библиотеки в одном репозитории с её пользователями является простота внесения изменений, так как они сразу распространяются на всех, кто подтягивает код из мастер-ветки. Тем не менее, когда мы говорим о С++, есть и обратная сторона. Во-первых, стандартную библиотеку задействуют все (даже если вы её не задействуете, это сделают ваши include). Во-вторых, система шаблонов этого языка подразумевает, что всё, сделанное по шаблону, должно также содержать в заголовке определения. Это означает, что как только кто-либо задействует AK в своём коммите, нужно заново собирать всю ОС (на момент прецедента это ~3 400 файлов). И ccache, оказывающаяся полезной во многих ситуациях, в этом случае не справлялась. Кроме того, ввиду стремительного развития проекта SerenityOS, кто-нибудь да затрагивает AK как минимум раз в 100 коммитов.

В результате на протяжении поиска по всей 1 000 выбранных мной коммитов мне пришлось с нуля собрать эту ОС 4 или 5 раз на ноутбуке 2011 года с архитектурой Sandy Bridge Mobile. И хотя это не вина проекта, я всё равно зол.

▍ Результаты поиска

Итак, после перебора 1 000 коммитов, неоднократной пересборки ОС и стенаний от непонимания, как работает этот бинарный поиск, я всё же нашёл коммит, виновный в искажении изображений. Внимание, барабанная дробь…

f89e8fb71a4893911ee5125f34bd5bbb99327d33
Author:     Gunnar Beutner
AuthorDate: Sat May 15 10:06:41 2021 +0200

AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable

This implements the macOS API malloc_good_size() which returns the
true allocation size for a given requested allocation size. This
allows us to make use of all the available memory in a malloc chunk.

For example, for a malloc request of 35 bytes our malloc would
internally use a chunk of size 64, however the remaining 29 bytes
would be unused.

Knowing the true allocation size allows us to request more usable
memory that would otherwise be wasted and make that available for
Vector, HashTable and potentially other callers in the future.

Простите, что?

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

Lenna, до сбоя в ОС

Обмен идеями с другими разработчиками навёл меня на мысль, что либо JPGLoader, либо что-то иное выше по цепочке зависит от вместимости Vector и пишет напрямую в него, когда в реале не должно. Тогда я начал искать возможные причины.

▍ Неожиданное открытие

Этот коммит был связан с двумя основными видами контейнеров — HashTable (от которого зависит HashMap) и Vector. Они оба используются в коде JPGLoader, и в этом случае причиной проблемы может быть любой из них.

Я случайным образом выбрал HashTable, удалил сомнительную строку:

         new_capacity = max(new_capacity, static_cast<size_t>(4));
-        new_capacity = kmalloc_good_size(new_capacity * sizeof(Bucket)) / sizeof(Bucket);

         auto* old_buckets = m_buckets;

и заново собрал систему, параллельно пошутив в чате о том, что проблема не может заключаться в этом.

…Но проблема ушла.

Что? Как? Почему отличие во вместимости HashTable имеет значение? HashTable — это даже не непрерывный поток данных, в который можно выполнять запись, поэтому у вас не должно быть возможности даже предположить её вместимость.

Но, прежде чем дать вам весь расклад, я должен коротко рассказать о том, как раньше работал JPGLoader.

▍ Недетерменированный перебор последовательных компонентов

Это, пожалуй, самый подходящий заголовок для текущего раздела.

Ранее JPGLoader считывала информацию о компоненте JPG из области «Start of Frame» файла в структуру Component, после чего сохраняла его в HashTable. Естественно, порядок расположения в файле компонентов должен соответствовать Y, Cb и Cr. Значит, структура Component должна содержать serial_id, представляющий позицию Component в файле. Все Component вносились в хэш-таблицу для того, чтобы затем их можно было сопоставить с порядком компонентов в разделе «Start of Scan» с целью подтверждения их правильной последовательности. Почему код был написан именно так, вместо того чтобы просто выполнять проверку по ID путём линейного перебора всех Component, мне непонятно.

Как бы то ни было, затем эти компоненты перебирались во время различных этапов декодирования JPGLoader, когда их информация использовалась для выполнения преобразований макроблоков.

▍ Приближаясь к решению

Когда я добавил несколько отладочных инструкций print(), чтобы пронаблюдать процесс считывания компонентов, то увидел в виновном коммите следующее:

ImageDecoder(33:33): Looking at component 0
ImageDecoder(33:33): Looking at component 2
ImageDecoder(33:33): Looking at component 1
ImageDecoder(33:33): Looking at component 0
ImageDecoder(33:33): Looking at component 2
ImageDecoder(33:33): Looking at component 1
...

А при проверке предшествующего ему коммита следующее:

ImageDecoder(33:33): Looking at component 0
ImageDecoder(33:33): Looking at component 1
ImageDecoder(33:33): Looking at component 2
ImageDecoder(33:33): Looking at component 0
ImageDecoder(33:33): Looking at component 1
ImageDecoder(33:33): Looking at component 2
...

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

ImageDecoder(32:32): Huffman stream exhausted. This could be an error!
ImageDecoder(32:32): Failed to build Macroblock 3277

…Ах да. Естественно, всё дело в потоке.

▍ Баг

Итак, вот краткое изложение бага:

• Кто-то использовал HashTable для хранения объектов, которые должны быть упорядочены, после чего перебирал таблицу с помощью её базового итератора.
• Хэш ID компонентов в файлах JPG передавался в int_hash для выбора бакета хэш-таблицы.
• И с целью соблюдения нужного порядка они не только получали правильное значение, но и вставлялись в хэш-таблицу, содержащую правильное количество бакетов.
• Это приводило к тому, что закодированный алгоритмом Хаффмана поток считывался с соблюдением правильной последовательности компонентов, тем самым маскируя баг.
• По счастливой случайности баг оставался скрыт с самого создания JPGLoader, пока кто-то не напортачил с размером HashTable.

▍ Исправление

Наконец, спустя примерно 10 часов отладки, мы составили коммит, исправляющий этот страшный баг:

a10ad24c760bfe713f1493e49dff7da16d14bf39
Author:     sin-ack
AuthorDate: Mon May 31 15:22:04 2021 +0000
Commit:     Linus Groh
CommitDate: Mon May 31 17:26:11 2021 +0100

LibGfx: Make JPGLoader iterate components deterministically

JPGLoader used to store component information in a HashTable, indexed
by the ID assigned by the JPEG file.  This was fine for most purposes,
however after f89e8fb7 this was revealed to be a flawed implementation
which causes non-deterministic iteration over components.

This issue was previously masked by a perfect storm of int_hash being
stable for the integer values 0, 1 and 2; and AK::HashTable having just
the right amount of buckets for the components to be ordered correctly
after being hashed with int_hash. However, after f89e8fb7,
malloc_good_size was used for determining the amount of space for
allocation; this caused the ordering of the components to change, and
images started showing up with the red and blue channels reversed. The
issue was finally determined to be inconsistent ordering after randomly
changing the order of the components caused Huffman decoding to fail.

This was the result of about 10 hours of hair-pulling and repeatedly
doing full rebuilds due to bisecting between commits that touched AK.
Gunnar, I like you, but please don't make me go through this again. :^)

Credits to Andrew Kaster, bgianf, CxByte and Gunnar for the debugging
help.

▍ Выводы

Иногда простейшие проблемы могут отражать собой серьёзные внутренние ошибки. Я, пожалуй, мог исправить этот баг, просто поменяв по месту порядок аргументов, и такое решение бы сработало…пока этот порядок в очередной раз не поменял бы кто-нибудь другой. К счастью, теперь мы сможем спокойно любоваться тубами в их естественных цветах.

Туба в корректных цветах. Источник: music123.com