Malloc'ın Serenity'nin JPGLoader'ını bozduğu olay veya: piyango kazanmanın sırrı (2021)

• SerenityOS'taki JPG renk hatası RGB/BGR argüman sırası sorunu gibi görünüyordu, ancak aslında JPGLoader sıralamanın önemli olduğu bileşenleri HashTable yineleme sırasına bırakıyordu
• AK+LibC içindeki malloc_good_size() eklenince Vector ve HashTable gerçek malloc parça boyutunu kullanmaya başladı; bunun sonucu olarak HashTable kova sayısı değişti ve gizli hata ortaya çıktı
• Mevcut kod JPG'nin Y, Cb, Cr bileşenlerini tesadüfen doğru sırada okuyordu; int_hash sonucu ile kova sayısı denk geldiği için Huffman akışı işleme hatası gizlenmişti
• Kök nedeni izleme süreci, JPGLoader.cpp'nin yakın zamanda değişmemiş olmasından başladı ve 1000 commit'lik bir bisect sırasında AK değişiklikleri yüzünden yaklaşık 3400 dosyalık işletim sistemini birkaç kez baştan derlemek gerekti
• Nihai düzeltme, bileşenlerin deterministik sırayla dolaşılmasını sağlamaktı; yalnızca renk argümanı sırasını değiştiren geçici çözüm, bir sonraki sıra değişiminde aynı sorunu yeniden üretebilirdi

---

RGB/BGR karışıklığı gibi görünen JPG renk hatası

• SerenityOS'ta JPG görüntüleri açıldığında renklerin yanlış gösterildiği bir sorun vardı
• JPGLoader.cpp içinde Color kurucusunun argüman sırasını değiştirince görüntü düzelmiş gibi görünüyordu
  • Eski kod: Y, Cb, Cr sırasıyla geçiriliyordu
  • Geçici değişiklik: Cr, Cb, Y sırasıyla geçiriliyordu
• Ancak JPGLoader.cpp üzerinde yakın zamandaki son revert olmayan değişiklik Git'e göre bir aydan daha eskiydi ve 1-2 hafta önce JPG arka plan görsellerinin düzgün çalıştığı hatırlanıyordu
• Bu yüzden bunun basit bir renk kanalı sırası hatası değil, başka bir değişikliğin mevcut bir bug'ı görünür kılmış olması daha olasıydı

AK değişiklikleri yüzünden zorlaşan bisect

• SerenityOS, kendi standart kütüphanesi olan AK (Agnostic Kit) kullanıyor
  • AK, C++ STL'e benzer bir rol oynuyor, ancak aynı depo içinde işletim sistemi koduyla birlikte değişiyor
• AK değiştiğinde etki alanı geniş oluyor
  • Standart kütüphane neredeyse tüm kod tarafından dahil ediliyor
  • C++ template'leri tanımların header içinde olmasını gerektirdiğinden, AK header değişiklikleri geniş çaplı yeniden derlemeye yol açıyor
• AK değişikliği içeren commit'ler geçilirken tüm işletim sistemini yeniden derlemek gerekiyordu
  • Yazının yazıldığı sırada yaklaşık 3400 dosya
  • 1000 commit'lik aralıkta bisect yapılırken 2011 model Sandy Bridge Mobile bir dizüstünde tam derleme 4-5 kez yapıldı
• ccache da bu durumda yardımcı olmadı ve SerenityOS projesinin hızlı değişim temposu nedeniyle AK yaklaşık her 100 commit'te bir değişiyordu

malloc_good_size()'ın ortaya çıkardığı gizli sorun

• 1000 commit'lik bisect sonunda JPG renklerini bozan değişikliğin JPGLoader değil, AK+LibC tarafında olduğu görüldü
• Sorunu görünür kılan commit f89e8fb71a4893911ee5125f34bd5bbb99327d33 idi
  • Başlık: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
  • Yazılma zamanı: 15 Mayıs 2021
• Bu commit macOS API'si olan malloc_good_size()'ı implemente ediyordu
  • İstenen tahsis boyutu için gerçek tahsis boyutunu döndürüyor
  • Örneğin 35 bayt istenip içeride 64 baytlık bir parça kullanılıyorsa, boştaki 29 bayt da kullanılabiliyor
• Değişiklikten sonra Vector, HashTable ve benzerleri malloc parçası içindeki kullanılabilir belleği daha fazla değerlendirmeye başladı
• Bir önceki commit'te JPG görüntüleri düzgün gösterildiği için, bu değişikliğin mevcut gizli sorunu açığa çıkardığı anlaşıldı

HashTable kapasitesine yaslanan decoding

• İlk başta JPGLoader ya da üst katmandaki kodun Vector kapasitesine yanlış biçimde güvenip doğrudan yazma yapıyor olabileceğinden şüphelenildi
• İlgili değişiklikler hem HashTable hem de Vector tarafındaydı ve ikisi de JPGLoader kodunda kullanılıyordu
• Rastgele biçimde HashTable tarafındaki kmalloc_good_size() uygulama satırı çıkarılıp yeniden derlenince sorun kayboldu
  • Kaldırılan kod, yeni kova kapasitesini gerçek tahsis boyutuna göre ayarlayan bölümdü
• Bu sonuç, HashTable içindeki kova sayısı değişiminin JPG decoding sonucunu etkilediğini doğruladı
• HashTable ardışık veri akışı gibi kullanılacak bir kapsayıcı olmadığından, kapasitesine ya da yineleme sırasına güvenilmemeliydi

JPG bileşenlerinin işlenme biçimi

• Eski JPGLoader, JPG dosyasının Start of Frame bölümünden bileşen bilgisini okuyup Component yapısında saklıyordu
• Her Component, JPG dosyası içindeki konumunu gösteren bir serial_id taşıyordu
  • JPG bileşen sırasının normalde Y, Cb, Cr olması beklenir
• Bu bileşenler bir HashTable içinde tutuluyordu
  • Daha sonra Start of Scan bölümündeki bileşen sırasıyla karşılaştırılıp beklenen sıra olup olmadığı denetleniyordu
• Decoding aşamasında bu bileşenler dolaşılıp macroblock dönüşümü için gereken bilgiler kullanılıyordu
• Sorun, sıranın önemli olduğu bu bileşenlerin HashTable içine konup varsayılan iterator ile dolaşılmasıydı

Bozuk commit ile sağlam commit arasındaki yineleme sırası farkı

• Bozuk renklerin görüldüğü commit'te debug çıktısı bileşenleri şu sırayla dolaşıyordu
  • 0
  • 2
  • 1
• Bir önceki sağlam commit'te sıra farklıydı
  • 0
  • 1
  • 2
• Bu fark, renk kanallarının ters dönmüş gibi görünmesiyle bağlantılıydı
• CxByte ile birlikte bileşen sırası elle değiştirilirken şu hata alındı
  • Huffman stream exhausted. This could be an error!
  • Failed to build Macroblock 3277
• Bu hata, JPG decoding'in akış sırasına duyarlı olduğunu gösterdi ve bileşen yineleme sırasının temel neden olduğunu doğruladı

Tesadüfen doğru çıkan HashTable sırası

• Temel neden, sıralamanın önemli olduğu nesneleri HashTable içinde tutup varsayılan iterator ile dolaşmaktı
• JPG bileşen ID'lerinin hash'i int_hash üzerinden geçerek kova seçiminde kullanılıyordu
• Daha önce iki tesadüf aynı anda doğru denk gelmişti
  • 0, 1, 2 değerleri için int_hash sonuçları stabildi
  • AK::HashTable kova sayısı, bileşenlerin doğru sıraya yerleşmesi için tam uygun durumdaydı
• Bu tesadüf sayesinde JPGLoader, Huffman akışını her bileşen için doğru sırada okuyordu ve bug en başından beri gizli kalmıştı
• malloc_good_size() eklenince HashTable kova sayısı değişti, bileşen sırası da değişti ve kırmızı ile mavi kanalların yer değiştirdiği görüntüler ortaya çıktı

Deterministik yineleme ile gelen nihai düzeltme

• Yaklaşık 10 saatlik debugging sonunda düzeltme commit'i oluşturuldu
• Düzeltme commit'i a10ad24c760bfe713f1493e49dff7da16d14bf39 idi
  • Başlık: LibGfx: Make JPGLoader iterate components deterministically
  • Yazılma zamanı: 31 Mayıs 2021
• Düzeltmenin özü, JPGLoader'ın bileşenleri deterministik sırayla dolaşmasını sağlamaktı
• Yalnızca Color argüman sırasını değiştirmek kısa vadede görüntüyü düzeltmiş gibi görünse de, daha sonra başka bir değişiklik yineleme sırasını yeniden değiştirirse sorun tekrar ortaya çıkabilirdi
• Küçük bir görüntüleme hatası gibi görünen şeyin, kapsayıcı yineleme sırasına yapılan yanlış bağımlılık ile tahsis boyutu değişiminin birleşmesi sonucu ortaya çıktığı görüldü

[GN⁺]

Hacker News yorumları

• Birçok hash tablosu implementasyonunun algoritmaya rastgele bir unsur katmasının nedenlerinden biri bu
  Her çalıştırmada öğelerin sırası değiştiği için, yanlışlıkla sıraya bağımlıysanız sorun kısa sürede ortaya çıkar
  Hash algoritması sabitse, aynı bucket'ta toplanan anahtarlar üretilip hizmet engelleme saldırısı için kötüye kullanılabilir; bu tür güvenlik sorunlarını da epey iyi önler

  • Günümüzde bunun tersine, hash tablolarının her zaman ekleme sırasına göre dolaşılacağını garanti eden implementasyonlar da çok
    Ben bunu tercih ediyorum; çünkü sıralı bir map mi yoksa sırasız bir map mi gerektiğine her seferinde karar vermek zorunda kalmıyorum
    Sırasız bir map'in yeterli olacağını düşünüp ince nedenlerle yanıldığım durumlar epey oldu
  • Rastgele unsur zorunlu olarak belirlenen, saklanan, loglanan ve yeniden üretilebilen bir seed ise sorun yok
    Aksi halde başka sorunları debug etmeyi çok daha zorlaştırdığı için gerçekten kötü bir fikir
    Rastgelelik dost değil, düşmandır
    Yaklaşık 20 yıl önce Java web sunucularına saldırırken URL parametrelerini manipüle edip hepsini aynı bucket'a düşürme yöntemi vardı ve bu büyük bir hizmet engelleme saldırısına dönüşüyordu
    Yanlış hatırlamıyorsam PHP web sunucuları da tam olarak aynı güvenlik sorununu yaşadı
    Hash tablosuna seed eklenerek düzeltildi ve o seed elbette geliştiricinin kontrol edebildiği bir şeydi. Çünkü rastgelelik dost değil, düşmandır

• Bu, körü körüne ikili arama tarzı bisect yapmak yerine biraz daha debug edilse zaman kazandıracak bir örnek gibi görünüyor
  Bileşen sırasını yazdıran log sonuçta nasılsa eklenmek zorundaydı

• Debug etmesi de iyiydi ama commit mesajı da harika
  Nedeni ve düzeltmeyi birkaç paragraf içinde iyi sıkıştırmış

• Yeterince beklersek C++'a da malloc_good_size karşılığı bir özellik gelecek
  https://github.com/cplusplus/papers/issues/18

• Başlığa [2021] eklenmeli

• Bu Gunnar'ın hatası değil. Sorun, sıralı veriyi hash dosyasına kaydeden tarafta
  Onlarca yıldır bu işi yaparken, bellek yerleşimi değişince gizli kalmış bug'ların ortaya çıktığı durumları birçok kez yaşadım
  Her seferinde debug etmek saatler ile günler arasında sürdü
  Programlama zor olmasaydı bize ihtiyaç olmazdı. Yalnız bu cümlenin büyük dil modelleri çağında ne kadar daha dayanacağını bilmiyorum

  • Doğru. Hatta Gunnar'ın hatası olsaydı bile, commit mesajında bunu özellikle yazmaya gerek yok gibi
    Gunnar bir şeyi iyileştirdi ve bu süreçte eski, bozuk kodun sorunu ortaya çıktı, hepsi bu
    Ama bu emeğinin karşılığı olarak “Gunnar, I like you, but please don't make me go through this again. :^)” gibi bir söz duyuyor
  • Büyük dil modelleri bug'lı kodla eğitildiği sürece bug'lı kod önerecekler
  • Doğru. Ayrıca başlığın aksine bu malloc()'un hatası da değil

• SerenityOS'ta test için kaynakları veya PC'leri birbirine sağlayarak yardımcı olan insanlar olduğunu biliyorum

• 2011 Sandy Bridge Mobile dizüstünde SerenityOS'u sıfırdan 4-5 kez derlemek, Windows 3.1 ile Windows 95 arasındaki dönemde çıkan bir bilgisayarla Windows Vista geliştirmeye çalışmaya benziyor

  • Zaman aralığı açısından doğru ama gerçek performans açısından değil
    2011'den sonra CPU'lar görece o kadar büyük değişmedi; oysa Windows 3.1 ile Vista arasında x64 yaygınlaştı ve çok çekirdekli CPU'lar sıradanlaştı
  • Güzel karşılaştırma. Geliştiricinin CPU'su kabaca 13 yıllık
    Vista 2007 başında uluslararası olarak çıktığına göre, çıkış anında 13 yıllık bir CPU 1994 model olurdu; orijinal Pentium'un çıkışından yaklaşık bir yıl sonrası
    O dönemde hâlâ güvenilir 486 DX2-66 kullanan çok kişi vardı
    13 yıl önceki bir CPU'nun bugün modern projelerde çalışmak için hâlâ kullanılabilmesi oldukça etkileyici. O zaman aynı şeyi söylemek zordu
    Bugün çıkan CPU'ları da 2037 sonrasına kadar memnuniyetle kullanabilmeyi umuyorum
  • Son bir yıldır ana masaüstü olarak 2011 Lenovo i5 üzerinde Windows 11'i çift monitörle kullanıyorum
    Visual Studio da gayet çalışıyor, Photoshop'ta da yalnızca sistem içindeki yapay zeka araçları çok az ağır kalıyor
    Chrome'da herhalde 200 kadar sekme açık, Slack, WhatsApp ve test için 3 tarayıcı da birlikte çalışıyor
    CapCut'ın 4K kurguda biraz daha hızlı olmasını isterdim ama karmaşık 2K projeleri yeterince kaldırıyor
    Yalnızca karmaşık After Effects projelerinde sınırlarına biraz dayandım. Onu pek sevmedi
    Yükseltme yapmam gerekecek ama aslında çöpten kurtarılmış bir sistem için epey iyi

• “Alien Lenna”yı görünce déjà vu hissettim; gerçekten de daha önce görüp yorum bile yaptığım bir yazıymış
  https://news.ycombinator.com/item?id=27374942 (2021)