Cómo `malloc` rompió el `JPGLoader` de Serenity, o: el secreto para ganar la lotería (2021)

• El error de color en JPG de SerenityOS parecía un problema con el orden de argumentos RGB/BGR, pero en realidad comenzó porque JPGLoader dejaba el orden de componentes, que sí importa, en manos del orden de iteración de un HashTable
• Con la incorporación de malloc_good_size() en AK+LibC, Vector y HashTable pasaron a aprovechar el tamaño real de los chunks asignados por malloc, y como resultado cambió la cantidad de buckets del HashTable, dejando al descubierto un bug oculto
• El código anterior estaba leyendo por casualidad los componentes Y, Cb, Cr del JPG en el orden correcto, y gracias a que coincidían el resultado de int_hash y la cantidad de buckets, quedaba oculto el error en el procesamiento del flujo Huffman
• La investigación de la causa comenzó con JPGLoader.cpp sin cambios recientes, y durante un bisect de 1000 commits hubo que recompilar varias veces por completo un sistema operativo de unas 3400 archivos debido a cambios en AK
• La corrección final consistió en hacer que los componentes se recorrieran en un orden determinista, y un parche temporal que solo cambiara el orden de los argumentos de color podía volver a causar el mismo problema la próxima vez que cambiara el orden

---

Error de color JPG que parecía una confusión RGB/BGR

• En SerenityOS ocurría un problema donde al abrir imágenes JPG los colores se mostraban incorrectamente
• Si se cambiaba el orden de los argumentos del constructor de Color en JPGLoader.cpp, la imagen parecía verse bien
  • Código original: se pasaban en orden Y, Cb, Cr
  • Cambio temporal: orden Cr, Cb, Y
• Sin embargo, el último cambio no-revert reciente en JPGLoader.cpp había sido más de un mes antes según Git, y además existía el recuerdo de que hace 1 o 2 semanas una imagen JPG de fondo se veía correctamente
• Por eso, era más probable que no se tratara de un simple error en el orden de los canales de color, sino de otro cambio que había dejado expuesto un bug ya existente

Un bisect más difícil por culpa de AK

• SerenityOS usa su propia biblioteca estándar, AK (Agnostic Kit)
  • AK cumple un papel parecido al STL de C++, pero se modifica junto con el código del sistema operativo dentro del mismo repositorio
• Cuando AK cambia, el impacto es amplio
  • Casi todo el código incluye la biblioteca estándar
  • Las plantillas de C++ deben definirse en headers, así que cambios en los headers de AK provocan recompilaciones masivas
• Cada vez que el bisect pasaba por un commit con cambios en AK, había que volver a compilar todo el sistema operativo
  • Aproximadamente 3400 archivos al momento de escribir el texto
  • Durante el bisect sobre un rango de 1000 commits, se hicieron 4 o 5 builds completos en una laptop Sandy Bridge Mobile de 2011
• ccache tampoco pudo ayudar en este caso, y por el ritmo rápido de cambios del proyecto SerenityOS, AK cambiaba aproximadamente una vez cada 100 commits

malloc_good_size() dejó al descubierto el problema oculto

• Después de hacer bisect sobre 1000 commits, el cambio que rompía los colores del JPG no apareció en JPGLoader, sino del lado de AK+LibC
• El commit que dejó visible el problema fue f89e8fb71a4893911ee5125f34bd5bbb99327d33
  • Título: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
  • Fecha de creación: 15 de mayo de 2021
• Ese commit implementó la API de macOS malloc_good_size()
  • Devuelve el tamaño real asignado para una solicitud de memoria
  • Por ejemplo, si una solicitud de 35 bytes usa internamente un chunk de 64 bytes, permite aprovechar los 29 bytes restantes
• Tras el cambio, Vector, HashTable y otros pasaron a aprovechar mejor la memoria utilizable dentro del chunk asignado por malloc
• Como en el commit inmediatamente anterior la imagen JPG se mostraba bien, se acotó la causa a que este cambio había dejado expuesto un problema previo que estaba oculto

Un decodificado que dependía de la capacidad del HashTable

• Al principio se sospechó que JPGLoader o código de más alto nivel podía estar dependiendo incorrectamente de la capacidad de Vector y escribiendo directamente donde no debía
• Los cambios relacionados afectaban tanto a HashTable como a Vector, y ambos se usaban en el código de JPGLoader
• Al eliminar al azar la línea que aplicaba kmalloc_good_size() del lado de HashTable y recompilar, el problema desapareció
  • El código eliminado era la parte que ajustaba la capacidad de nuevos buckets según el tamaño real asignado
• Con eso se confirmó que el cambio en la cantidad de buckets de HashTable afectaba el resultado del decodificado JPG
• HashTable no es un contenedor para usarse como si fuera un flujo de datos secuencial, así que no se debía depender ni de su capacidad ni de su orden de iteración

Cómo se procesaban los componentes JPG

• El JPGLoader original leía la información de componentes en la sección Start of Frame del archivo JPG y la guardaba en una estructura Component
• Cada Component tenía un serial_id que representaba su posición dentro del archivo JPG
  • El orden de componentes en JPG normalmente debería ser Y, Cb, Cr
• Estos componentes se guardaban en un HashTable
  • Después se usaban para comparar con el orden de componentes de la sección Start of Scan y verificar si era el orden esperado
• En la etapa de decodificación, se recorrían estos componentes para usar la información necesaria en la conversión de macroblocks
• El problema era que componentes cuyo orden sí importa se estaban metiendo en un HashTable y recorriendo con el iterador por defecto

Diferencia en el orden de iteración entre el commit roto y el bueno

• En el commit con colores rotos, la salida de depuración recorría los componentes en este orden
  • 0
  • 2
  • 1
• En el commit anterior, donde todo funcionaba, el orden era distinto
  • 0
  • 1
  • 2
• Esa diferencia estaba relacionada con un resultado que se veía como una inversión de canales de color
• Mientras se probaba cambiar manualmente el orden de componentes junto con CxByte, apareció el siguiente error
  • Huffman stream exhausted. This could be an error!
  • Failed to build Macroblock 3277
• Ese error mostró que la decodificación JPG era sensible al orden del flujo, y confirmó que el orden de iteración de los componentes era la causa principal

Un orden de HashTable que coincidía por pura casualidad

• La causa de fondo era haber guardado objetos cuyo orden importa en un HashTable y recorrerlos con el iterador por defecto
• El hash del ID de componente JPG se usaba para elegir bucket a través de int_hash
• Antes coincidían al mismo tiempo dos casualidades
  • El resultado de int_hash para los valores 0, 1, 2 era estable
  • La cantidad de buckets de AK::HashTable era justo la adecuada para que los componentes quedaran acomodados en el orden correcto
• Gracias a esa coincidencia, JPGLoader leía el flujo Huffman en el orden correcto para cada componente, y el bug había quedado oculto desde el principio
• Cuando se introdujo malloc_good_size() y cambió la cantidad de buckets de HashTable, también cambió el orden de los componentes y aparecieron imágenes con los canales rojo y azul intercambiados

La corrección final: iteración determinista

• Después de unas 10 horas de depuración, se creó el commit de corrección
• El commit de corrección fue a10ad24c760bfe713f1493e49dff7da16d14bf39
  • Título: LibGfx: Make JPGLoader iterate components deterministically
  • Fecha de creación: 31 de mayo de 2021
• La esencia de la corrección fue hacer que JPGLoader recorriera los componentes en un orden determinista
• Cambiar simplemente el orden de los argumentos de Color también hacía que la imagen pareciera correcta por el momento, pero si más adelante otro cambio volvía a alterar el orden de iteración, podía romperse otra vez
• Fue un caso donde un problema que parecía un pequeño error de visualización terminó revelando una dependencia incorrecta del orden de iteración de un contenedor, combinada con cambios en el tamaño de asignación de memoria

[GN⁺]

Opiniones en Hacker News

• Esta es una de las razones por las que muchas implementaciones de tablas hash incorporan un elemento aleatorio en el algoritmo.
  Como el orden de los elementos cambia en cada ejecución, si por accidente dependes de ese orden, el problema aparece rápido.
  Si el algoritmo de hash es fijo, se pueden crear claves que caigan todas en el mismo bucket y aprovecharlo para un ataque de denegación de servicio; esto también ayuda bastante a evitar ese tipo de problemas de seguridad.

  • Hoy en día, al contrario, también hay muchas implementaciones que garantizan que una tabla hash siempre se recorra en orden de inserción.
    Prefiero ese enfoque, porque no tengo que decidir cada vez si necesito un mapa ordenado o uno no ordenado.
    Varias veces pensé que un mapa no ordenado bastaba y terminé equivocado por razones sutiles.
  • Está bien si el elemento aleatorio es una semilla que se puede especificar, guardar, registrar y reproducir a la fuerza.
    Si no, es una idea pésima, porque hace mucho más difícil depurar otros problemas.
    La aleatoriedad no es una amiga, es una enemiga.
    Hace unos 20 años, al atacar servidores web Java, existía una técnica que manipulaba los parámetros de la URL para que todos cayeran en el mismo bucket, y se convirtió en un gran ataque de denegación de servicio.
    Si no recuerdo mal, los servidores web PHP sufrieron exactamente el mismo problema de seguridad.
    Se arregló agregando una semilla a la tabla hash, y por supuesto esa semilla podía ser controlada por el desarrollador. Porque la aleatoriedad no es una amiga, es una enemiga.

• Esto parece un caso en el que se habría ahorrado tiempo depurando un poco más, en vez de hacer un bisect estilo búsqueda binaria a ciegas.
  Al final, de todos modos había que agregar logs que imprimieran el orden de los componentes.

• La depuración estuvo buena, pero el mensaje del commit también es excelente.
  Logró condensar muy bien la causa y la corrección en unos pocos párrafos.

• Si esperamos lo suficiente, C++ también tendrá una función equivalente a malloc_good_size.
  https://github.com/cplusplus/papers/issues/18

• El título necesita [2021].

• Esto no es culpa de Gunnar. El problema está en quien guardó datos con orden en un archivo hash.
  En décadas haciendo esto, me tocó muchas veces ver cómo un cambio en la disposición de memoria revelaba bugs ocultos.
  Cada vez, depurarlo lleva de horas a días.
  Si programar no fuera difícil, no haría falta que existiéramos. Aunque no sé cuánto más aguantará esa frase en la era de los modelos de lenguaje grandes.

  • Exacto. Incluso si hubiera sido culpa de Gunnar, no parece necesario ponerlo en el mensaje del commit.
    Gunnar mejoró algo, y en el proceso solo salió a la luz un problema de código viejo y roto.
    Pero como recompensa por ese esfuerzo termina recibiendo algo como “Gunnar, I like you, but please don't make me go through this again. :^)”.
  • Mientras los modelos de lenguaje grandes se entrenen con código con bugs, van a sugerir código con bugs.
  • Exacto. Y, a diferencia de lo que dice el título, tampoco es culpa de malloc().

• Tengo entendido que en SerenityOS hay personas que se ayudan mutuamente con recursos de prueba o PCs.

• Haber compilado SerenityOS desde cero 4 o 5 veces en una laptop Sandy Bridge Mobile de 2011 es parecido a intentar hacer desarrollo de Windows Vista en una computadora de la época entre Windows 3.1 y Windows 95.

  • Por intervalo de tiempo, sí, pero no en términos de rendimiento real.
    Desde 2011, las CPU no han cambiado relativamente tanto, mientras que entre Windows 3.1 y Vista se popularizó x64 y se volvieron comunes las CPU multinúcleo.
  • Buena comparación. La CPU del desarrollador tiene unos 13 años.
    Vista se lanzó internacionalmente a comienzos de 2007, así que una CPU de 13 años al momento del lanzamiento sería de 1994, alrededor de un año después de que saliera el Pentium original.
    En ese entonces todavía había mucha gente usando la confiable 486 DX2-66.
    Es bastante impresionante que una CPU de hace 13 años todavía pueda servir hoy para trabajar en un proyecto moderno. En aquella época era difícil decir lo mismo.
    Espero que las CPU que salen hoy puedan seguir usándose satisfactoriamente hasta después de 2037.
  • Durante el último año he usado como escritorio principal una Lenovo i5 de 2011 con Windows 11 y doble monitor.
    Visual Studio corre bien, y Photoshop también; solo las herramientas de IA integradas en el sistema se sienten apenas un poco lentas.
    Probablemente tengo unas 200 pestañas de Chrome abiertas, junto con Slack, WhatsApp y 3 navegadores de prueba.
    Me gustaría que CapCut fuera un poco más rápido al editar en 4K, pero aguanta perfectamente proyectos complejos en 2K.
    Solo encontré un poco el límite con proyectos complejos de After Effects. Eso sí que no le gusta.
    Tendría que actualizar, pero para ser un sistema que básicamente rescaté de la basura, está bastante bien.

• Al ver “Alien Lenna” sentí déjà vu, y efectivamente era un artículo que ya había visto y hasta comentado antes.
  https://news.ycombinator.com/item?id=27374942 (2021)