Пару лет назад мне выпала возможность расследовать в 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 на тот момент было внесено более месяца назад:
И я прекрасно помнил, что ещё пару недель назад 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.
Перевод
AK+Libc: реализация
Этот код реализует macOS API
Например, при запросе 35 байт
Понимание истинного объёма выделенной памяти позволяет запросить более подходящий её размер, который в противном случае оказался бы потрачен впустую, сделав его доступным для
malloc_good_size() и её использование для Vector/HashTableЭтот код реализует macOS API
malloc_good_size(), который возвращает истинный размер памяти, выделенной на указанный запрос о её выделении. Это позволяет задействовать всю доступную память в выделенной malloc области. Например, при запросе 35 байт
malloc внутренне использует область в 64 байта, оставив незадействованными 29. Понимание истинного объёма выделенной памяти позволяет запросить более подходящий её размер, который в противном случае оказался бы потрачен впустую, сделав его доступным для
Vector, HashTable и потенциально других вызывающих компонентов в будущем.Простите, что?
Но именно так. Сборка коммита, предшествовавшего этому, обеспечила корректный показ изображения:
Обмен идеями с другими разработчиками навёл меня на мысль, что либо
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.
Перевод
LibGfx: делает так, чтобы JPGLoader перебирал компоненты детерменированно.
Ранее проблема маскировалась из-за злосчастного совпадения двух факторов, когда
Это стало результатом примерно 10 часов мучений и повторяющихся пересборок из-за бинарного поиска по коммитам, затрагивавшим AK.
Благодарю Andrew Kaster, bgianf, CxByte и Gunnar за помощь в отладке.
JPGLoader сохранял информацию о компонентах в HashTable, которая индексировалась по ID, присвоенным файлом JPG. В большинстве задач это никаких проблем не создавало, но после f89e8fb7 выяснилась ошибочность этой реализации, которая вызывала недетерменированный перебор компонентов.Ранее проблема маскировалась из-за злосчастного совпадения двух факторов, когда
int_hash оказывалась стабильной для значений 0, 1 и 2, а AK::HashTable после хэширования с помощью int_hash имела нужное число бакетов для правильного упорядочивания компонентов. Тем не менее после f89e8fb7 для определения количества выделяемого пространства начала использоваться malloc_good_size, что вызвало изменение порядка компонентов и перестановку синего и красного каналов при показе изображений. В итоге было установлено, что проблема заключается в непоследовательном упорядочивании, вызванном сбоем при декодировании Хаффмана из-за произвольного изменения порядка компонентов. Это стало результатом примерно 10 часов мучений и повторяющихся пересборок из-за бинарного поиска по коммитам, затрагивавшим AK.
Благодарю Andrew Kaster, bgianf, CxByte и Gunnar за помощь в отладке.
▍ Выводы
Иногда простейшие проблемы могут отражать собой серьёзные внутренние ошибки. Я, пожалуй, мог исправить этот баг, просто поменяв по месту порядок аргументов, и такое решение бы сработало…пока этот порядок в очередной раз не поменял бы кто-нибудь другой. К счастью, теперь мы сможем спокойно любоваться тубами в их естественных цветах.
Telegram-канал со скидками, розыгрышами призов и новостями IT ?
