जब Malloc ने Serenity के JPGLoader को तोड़ दिया, या: लॉटरी जीतने का तरीका (2021)

 (sin-ack.github.io)
1 पॉइंट द्वारा GN⁺ 2024-07-08 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • SerenityOS में JPG रंग त्रुटि पहली नज़र में RGB/BGR argument order की समस्या लग रही थी, लेकिन असली वजह यह थी कि JPGLoader ने order-sensitive components का क्रम HashTable iteration order पर छोड़ दिया था
  • AK+LibC में malloc_good_size() आने के बाद Vector और HashTable ने actual malloc chunk size का उपयोग करना शुरू किया, और इसके परिणामस्वरूप HashTable bucket count बदल गई, जिससे छिपा हुआ bug सामने आ गया
  • पुराना code संयोग से JPG के Y, Cb, Cr components को सही क्रम में पढ़ रहा था, और int_hash के नतीजे तथा bucket count के मेल के कारण Huffman stream processing की गलती छिपी हुई थी
  • कारण की खोज JPGLoader.cpp में हाल में कोई बदलाव न होने की स्थिति से शुरू हुई, और 1000 commits की bisect के दौरान AK changes की वजह से लगभग 3400 files वाले OS को कई बार पूरी तरह rebuild करना पड़ा
  • अंतिम fix यह था कि components को deterministic order में iterate कराया जाए; केवल color argument order बदलने वाला अस्थायी उपाय अगली order change पर वही समस्या फिर पैदा कर सकता था

RGB/BGR भ्रम जैसा दिखने वाला JPG रंग bug

  • SerenityOS में JPG image खोलने पर रंग गलत दिखने की समस्या हुई
  • JPGLoader.cpp में Color constructor के arguments का क्रम बदलने पर image सही लगने लगी
    • पुराना code: Y, Cb, Cr क्रम में pass किया गया
    • अस्थायी बदलाव: Cr, Cb, Y क्रम में pass किया गया
  • लेकिन JPGLoader.cpp में हाल की आख़िरी non-revert change Git के हिसाब से एक महीने से भी पहले की थी, और 1–2 हफ्ते पहले JPG background image सही दिखने की याद थी
  • इसलिए यह संभावना अधिक थी कि यह सिर्फ़ color channel order bug नहीं, बल्कि किसी और change ने पुराने bug को उजागर किया हो

AK change की वजह से मुश्किल हुई bisect

  • SerenityOS अपनी standard library AK(Agnostic Kit) का इस्तेमाल करता है
    • AK की भूमिका C++ STL जैसी है, लेकिन यह उसी repository में OS code के साथ बदलती रहती है
  • AK बदलने पर उसका असर बहुत व्यापक होता है
    • standard library लगभग हर code path में शामिल होती है
    • C++ templates की definitions headers में होनी चाहिए, इसलिए AK headers में बदलाव बड़े पैमाने पर recompilation कराते हैं
  • AK change वाले commit को पार करते समय पूरे OS को फिर से build करना पड़ता था
    • लेख लिखे जाने के समय लगभग 3400 files
    • 1000 commits की bisect के दौरान 2011 के Sandy Bridge Mobile laptop पर 4–5 बार full build करनी पड़ी
  • ccache भी इस मामले में मदद नहीं कर पाया, और SerenityOS project की तेज़ development pace के कारण AK लगभग हर 100 commits में एक बार बदल रहा था

malloc_good_size() ने जो छिपी समस्या उजागर की

  • 1000 commits की bisect के अंत में पता चला कि JPG colors को बिगाड़ने वाला change JPGLoader में नहीं, बल्कि AK+LibC में था
  • समस्या को उजागर करने वाला commit था f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • शीर्षक: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • समय: 15 मई 2021
  • इस commit ने macOS API malloc_good_size() को implement किया
    • यह requested allocation size के लिए actual allocated size लौटाता है
    • उदाहरण के लिए, अगर 35 bytes की request अंदरूनी तौर पर 64-byte chunk इस्तेमाल करे, तो बचे हुए 29 bytes भी उपयोग में लाए जा सकते हैं
  • इस बदलाव के बाद Vector, HashTable आदि malloc chunk के भीतर उपलब्ध memory का बेहतर उपयोग करने लगे
  • क्योंकि ठीक पिछले commit में JPG image सही दिख रही थी, इसलिए यह साफ़ हुआ कि इस change ने पहले से मौजूद छिपी हुई समस्या को उजागर किया

HashTable capacity पर निर्भर decoding

  • शुरुआत में शक था कि शायद JPGLoader या उसके ऊपर का code Vector capacity पर गलत तरह से निर्भर है और direct write कर रहा है
  • संबंधित change HashTable और Vector दोनों में था, और दोनों का उपयोग JPGLoader code में हो रहा था
  • परीक्षण के तौर पर HashTable पक्ष में kmalloc_good_size() लागू करने वाली line हटाकर दोबारा build करने पर समस्या गायब हो गई
    • हटाया गया code नए bucket capacity को actual allocation size के अनुसार adjust करता था
  • इससे पुष्टि हुई कि HashTable की bucket count में बदलाव JPG decoding के नतीजे को प्रभावित कर रहा था
  • HashTable ऐसा container नहीं है जिसे contiguous data stream की तरह इस्तेमाल किया जाए, इसलिए उसकी capacity या iteration order पर निर्भर नहीं होना चाहिए था

JPG components को कैसे process किया जा रहा था

  • पुराना JPGLoader JPG file के Start of Frame section से component जानकारी पढ़कर Component struct में रखता था
  • हर Component के पास serial_id होता था, जो JPG file के भीतर उसकी position बताता था
    • JPG component order सामान्यतः Y, Cb, Cr होना चाहिए
  • इन components को HashTable में store किया जाता था
    • बाद में Start of Scan section के component order से तुलना कर यह जांचने के लिए कि क्रम expected है या नहीं
  • decoding चरण में इन्हीं components पर iterate करते हुए macroblock conversion के लिए ज़रूरी जानकारी ली जाती थी
  • समस्या यह थी कि order-important components को HashTable में डालकर default iterator से traverse किया जा रहा था

टूटे हुए और सही commit में iteration order का अंतर

  • टूटे हुए color वाले commit में debug output ने components को इस क्रम में iterate किया
    • 0
    • 2
    • 1
  • ठीक पिछले सही commit में क्रम अलग था
    • 0
    • 1
    • 2
  • यही अंतर उस नतीजे से जुड़ता है जो color channel inversion जैसा दिख रहा था
  • CxByte के साथ component order को हाथ से बदलकर देखते समय यह error मिला
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • इस error ने दिखाया कि JPG decoding stream order के प्रति संवेदनशील है, और component iteration order ही मूल कारण है

संयोग से सही बैठा हुआ HashTable order

  • मूल कारण यह था कि order-sensitive objects को HashTable में store किया गया और default iterator से traverse किया गया
  • JPG component IDs का hash int_hash से होकर bucket selection में इस्तेमाल हो रहा था
  • पहले दो संयोग एक साथ सही बैठ रहे थे
    • 0, 1, 2 values के लिए int_hash के नतीजे स्थिर थे
    • AK::HashTable की bucket count ठीक ऐसी थी कि components सही क्रम में place हो रहे थे
  • इसी संयोग के कारण JPGLoader हर component के लिए Huffman stream को सही क्रम में पढ़ रहा था, और bug शुरुआत से ही छिपा हुआ था
  • malloc_good_size() आने के बाद HashTable की bucket count बदल गई, component order बदल गया, और image में लाल तथा नीले channels अदल-बदल गए

deterministic iteration से हुआ अंतिम fix

  • लगभग 10 घंटे की debugging के बाद fix commit तैयार हुआ
  • fix commit था a10ad24c760bfe713f1493e49dff7da16d14bf39
    • शीर्षक: LibGfx: Make JPGLoader iterate components deterministically
    • समय: 31 मई 2021
  • fix का सार यह था कि JPGLoader components को deterministic order में iterate करे
  • केवल Color argument order बदलने का तरीका उस समय image को सही जैसा दिखा सकता था, लेकिन बाद में किसी और change से iteration order फिर बदलती तो समस्या दोबारा आ सकती थी
  • यह उस स्थिति का उदाहरण था जहाँ मामूली display error जैसी दिखने वाली समस्या, container iteration order पर गलत निर्भरता और allocation size में बदलाव के मेल से सामने आई

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-08
Hacker News की राय

  • कई hash table implementations में algorithm में random element डालने की एक वजह यही है
    हर run में elements का order बदल जाता है, इसलिए अगर गलती से order पर dependency हो तो समस्या जल्दी सामने आ जाती है
    अगर hash algorithm fixed हो, तो ऐसे keys बनाए जा सकते हैं जो एक ही bucket में इकट्ठे हो जाएँ और उनका इस्तेमाल denial-of-service attack के लिए किया जा सकता है; इस तरह की security problem भी इससे काफी अच्छी तरह रुक जाती है

    • आजकल उल्टा, कई implementations यह guarantee भी देती हैं कि hash table हमेशा insertion order में iterate करेगा
      मुझे यह तरीका पसंद है, क्योंकि हर बार यह तय नहीं करना पड़ता कि sorted map चाहिए या unsorted map
      कई बार मैंने सोचा कि unsorted map काफी होगा, लेकिन किसी subtle वजह से वह गलत निकला
    • अगर random element जबरन specify, store, log और reproduce किया जा सकने वाला seed हो, तो ठीक है
      वरना यह दूसरी समस्याओं को debug करना कहीं ज्यादा मुश्किल बना देता है, इसलिए यह सचमुच खराब idea है
      randomness दोस्त नहीं, दुश्मन है
      करीब 20 साल पहले Java web servers पर attack करने का एक तरीका था: URL parameters को manipulate करके सबको एक ही bucket में डाल देना, और यह बड़ा denial-of-service attack बन जाता था
      अगर मुझे सही याद है, तो PHP web servers को भी बिल्कुल वही security problem हुई थी
      इसे hash table में seed डालकर ठीक किया गया, और वह seed जाहिर है developer के control में हो सकता था। क्योंकि randomness दोस्त नहीं, दुश्मन है

  • यह ऐसा मामला लगता है जहाँ अंधाधुंध binary-search-style bisect करने के बजाय थोड़ा और debug किया होता तो समय बच जाता
    component order print करने वाला log आखिरकार वैसे भी डालना ही पड़ा

  • debugging अच्छी थी, लेकिन commit message भी शानदार है
    इसने cause और fix को कुछ paragraphs में अच्छी तरह compress कर दिया

  • अगर लंबा इंतज़ार करें, तो C++ में भी malloc_good_size के बराबर feature आने वाला है
    https://github.com/cplusplus/papers/issues/18

  • title में [2021] चाहिए

  • यह Gunnar की गलती नहीं है। समस्या उस तरफ है जिसने ordered data को hash file में store किया
    दशकों से यह काम करते हुए मैंने कई बार देखा है कि memory layout बदलने पर छिपे हुए bugs सामने आ जाते हैं
    हर बार debug करने में कुछ घंटों से लेकर कई दिन तक लग जाते हैं
    अगर programming मुश्किल न होती, तो हमारी जरूरत ही नहीं होती। बस यह नहीं पता कि large language models के युग में यह वाक्य और कितने समय तक टिकेगा

    • सही। भले ही यह Gunnar की गलती होती, commit message में उसे खास तौर पर लिखने की जरूरत नहीं लगती
      Gunnar ने कुछ improve किया, और उस process में पुराने broken code की problem बस सामने आ गई
      लेकिन उस मेहनत के बदले उसे “Gunnar, I like you, but please don't make me go through this again. :^)” जैसी बात सुननी पड़ती है
    • जब तक large language models buggy code पर train होते रहेंगे, वे buggy code ही suggest करेंगे
    • सही। और title के उलट, यह malloc() की गलती भी नहीं है

  • मेरी जानकारी में SerenityOS में testing resources या PCs के लिए एक-दूसरे की मदद करने वाले लोग हैं

  • 2011 के Sandy Bridge Mobile laptop पर SerenityOS को scratch से 4–5 बार build करना कुछ वैसा है जैसे Windows 3.1 और Windows 95 के बीच के दौर में आए computer पर Windows Vista development करने की कोशिश करना

    • time gap के हिसाब से यह सही है, लेकिन actual performance के हिसाब से अलग है
      2011 के बाद CPUs में relatively इतना बड़ा बदलाव नहीं आया, जबकि Windows 3.1 से Vista के बीच x64 mainstream हुआ और multicore CPU common हो गया
    • अच्छी तुलना है। developer का CPU करीब 13 साल पुराना है
      Vista early 2007 में internationally release हुआ था, इसलिए release time पर 13 साल पुराना CPU 1994 का होता, यानी original Pentium आने के लगभग 1 साल बाद का समय
      उस समय भी कई लोग भरोसेमंद 486 DX2-66 इस्तेमाल कर रहे थे
      यह काफी impressive है कि 13 साल पुराना CPU आज भी modern project work के लिए इस्तेमाल हो सकता है। तब ऐसा कहना मुश्किल था
      उम्मीद है आज release होने वाले CPUs भी 2037 के बाद तक संतोषजनक रूप से इस्तेमाल किए जा सकेंगे
    • पिछले 1 साल से मैं main desktop के रूप में 2011 Lenovo i5 पर Windows 11 चला रहा हूँ और dual monitors के साथ use कर रहा हूँ
      Visual Studio भी ठीक चलता है, और Photoshop में सिर्फ in-system AI tools थोड़े-से sluggish लगते हैं
      Chrome tabs शायद करीब 200 खुले हैं, साथ में Slack, WhatsApp और testing के लिए 3 browsers भी use करता हूँ
      CapCut में 4K editing थोड़ी और fast होती तो अच्छा होता, लेकिन complex 2K projects को यह अच्छी तरह संभाल लेता है
      सिर्फ complex After Effects projects में इसकी limit थोड़ी hit हुई। उसे यह पसंद नहीं करता
      upgrade तो करना चाहिए, लेकिन सच में dustbin से बचाए गए system के हिसाब से यह काफी ठीक है

  • “Alien Lenna” देखकर déjà vu महसूस हुआ, और सच में यह वही post निकली जिसे मैंने पहले देखा था और comment भी किया था
    https://news.ycombinator.com/item?id=27374942 (2021)