HotXLS، CRC32 در zlib-ng، و سرریز پشته در رشته‌های Delphi

HotXLS می‌تواند یک رشته‌ی کارگر Delphi را بدون هیچ استثنای قابل‌گرفتنی کرش کند وقتی یک بخش بزرگ XML کاربرگ را در یک فراخوانی چک‌سام می‌کند: zlib-ng بالای تقریباً ۱۱۹ کیلوبایت ورودی به الگوریتم Chorba خودش سوییچ می‌کند، و نوع generic-C آن الگوریتم یک آرایه‌ی scratch به‌اندازه‌ی کافی بزرگ تخصیص می‌دهد که پشته‌ی پیش‌فرض ۱ مگابایتی رشته را منفجر کند. Delphi هرگز فرصتی برای واکنش نشان دادن پیدا نمی‌کند، چون یک سرریز پشته از آن نوع استثنایی نیست که try/except برای گرفتنش ساخته شده

HotXLS یک کتابخانه‌ی بومی Delphi و C++Builder برای خواندن و نوشتن کاربرگ‌های اکسل است، و این کرش به نویسنده‌ی کاربرگش برمی‌گشت. اولین نشانه‌ی مشکل یک تیکت پشتیبانی بود: یک job export شبانه تقریباً دوبار در هفته کرش می‌کرد، همیشه در میانه‌ی اجرا، بدون هیچ دیالوگ استثنای Delphi و بدون هیچ خطای لاگ‌شده، فقط یک فرآیند که ناپدید می‌شد و یک ورودی Windows Error Reporting که به هیچ‌جای مفیدی اشاره نمی‌کرد. بازتولید آن پشت میز کاملاً مسئله‌ی دیگری بود. کاربرگ‌های کوچک خوب ذخیره می‌شدند. کاربرگ‌های بزرگ هم خوب ذخیره می‌شدند، تا زمانی که ذخیره روی رشته‌ی اصلی با یک دیباگر از پیش پیوست‌شده اجرا می‌شد. یک دسته‌ی واقعی از فایل‌های به‌اندازه‌ی تولید که از مسیر export چندرشته‌ای واقعی عبور می‌کردند لازم بود تا کرش را به خانه بیاورد، تا آن نقطه‌ای که I/O دیسک، فشار حافظه، و یک الگوی مظنون هرکدام از پیش رد شده بودند

یک ذخیره‌ی کاربرگ چطور به یک فراخوانی غول‌آسای CRC32 تبدیل می‌شود

فایل‌های XLSX کانتینرهای ZIP هستند، و قالب ZIP به یک چک‌سام CRC-32 برای هر ورودی نیاز دارد، ثبت‌شده هم در هدر فایل محلی و هم در directory مرکزی. HotXLS آن چک‌سام را با فراخوانی یک wrapper کوچک به نام ZLibCRC32 محاسبه می‌کند، که به‌نوبه‌ی خود روال crc32 خودِ zlib-ng را به‌محض اینکه SaveAs مونتاژ XML یک کاربرگ در حافظه را تمام کرد فرا می‌خواند، و برای مدتی طولانی آن فراخوانی کل بافر فشرده‌نشده را در یک فراخوانی تکی حمل می‌کرد. این یک طراحی معقول برای یک کاربرگ کوچک است. همان لحظه‌ای که یک برگه از نوعی باشد که در راهنمای ما درباره‌ی کارایی کاربرگ بزرگ در HotXLS پوشش داده شده، جایی که XML یک برگه‌ی تکی به‌طور معمول پیش از اینکه اصلاً فشرده شود از چند صد کیلوبایت عبور می‌کند، به یک فراخوانی خیلی بزرگ تبدیل می‌شود

چرا zlib-ng برای CRC32 به یک بافر پشته‌ای غول‌آسا نیاز دارد؟

zlib-ng از یک پیاده‌سازی CRC-32 برای هر فراخوانی استفاده نمی‌کند. زیر یک آستانه‌ی اندازه، بافر را با جستجوهای جدولی و ترفندهای تاکردن می‌پیماید که به هیچ حافظه‌ی اضافی معنادار نیاز ندارد، و بالای آن آستانه، تقریباً ۱۱۹ کیلوبایت، دقیقاً ۱۱۸٬۹۶۰ بایت در ساختی که HotXLS به آن لینک می‌شود، به یک الگوریتم سریع تخصصی به نام Chorba سوییچ می‌کند. پیاده‌سازی generic-C آن مسیر حافظه را با سرعت معامله می‌کند: یک آرایه‌ی scratch روی پشته به‌جای heap تخصیص می‌دهد، اندازه‌گذاری‌شده تا حلقه‌ی درونی الگوریتم سریع باشد، نه اینکه به‌راحتی درون هر بودجه‌ی پشته‌ای که رشته‌ی فراخواننده اتفاقاً حمل می‌کند جا بگیرد. هیچ‌کدام از این‌ها از سمت فراخواننده قابل‌مشاهده نیست. یک تابع چک‌سام معمولاً یک فراخوانی برگ است، چند بایت بخوان، یک عدد برگردان، هیچ تخصیصی ارزش بحث ندارد، و این فرض برای اکثریت قریب به اتفاق فراخوانی‌ها به zlib-ng درست تا همان لحظه‌ای که یک بافر به‌اندازه‌ی کافی بزرگ که از آستانه‌ی Chorba عبور کند وارد یکی شود، برقرار می‌ماند

function BuildWorksheetPartCrc(const XmlBytes: TBytes): LongWord;
begin
  // One call over the whole worksheet XML buffer: fine for a small
  // sheet, but a large enough input pushes zlib-ng onto its Chorba
  // fast path and that path's stack-hungry scratch buffer
  Result := ZLibCRC32(0, XmlBytes[0], Length(XmlBytes));
end;

چرا رشته‌های کارگر آن را دیدند و دیباگ تعاملی هرگز ندید

ماشه‌کشیدن این کرش دو شرط را همزمان می‌طلبد: یک بخش XML کاربرگ به‌اندازه‌ی کافی بزرگ که از آستانه‌ی Chorba در zlib-ng عبور کند، و یک رشته که فقط پشته‌ی پیش‌فرض معمولی را دارد نه چیزی جادارتر. jobهای export تولیدی هر دو را می‌زدند. آن‌ها به‌عنوان jobهای دسته‌ای سمت-سرور که نوشتن‌های HotXLS را در سراسر یک استخر از رشته‌های کارگر پخش می‌کنند اجرا می‌شوند، هرکدام حامل پشته‌ی پیش‌فرض ۱ مگابایتی که ویندوز رزرو می‌کند مگر اینکه فراخواننده‌ای بیشتر بخواهد، و هرکدام کاربرگ‌های مشتری را که به‌اندازه‌ی کافی بزرگ‌اند که اهمیت داشته باشند پردازش می‌کند. دیباگ پشت میز به‌طور قابل‌اعتماد هیچ‌کدام از این شرایط را نمی‌زد: فایل‌های نمونه معمولاً کوچک‌تر از آستانه بودند، و اجراهای step-by-step تمایل داشتند روی رشته‌ی اصلی به‌جای درون یک کارگر تازه‌شروع‌شده اتفاق بیفتند، پس دو شرطی که باید در تولید هم‌راستا می‌شدند تقریباً هرگز پشت میز یک توسعه‌دهنده هم‌راستا نمی‌شدند

پیگیری یک کرش که تابع اشتباه را سرزنش کرد

گزارش‌های کرشی که تیم می‌توانست به آن‌ها دست پیدا کند به یک موقعیت درون تابع deflate در zlib-ng اشاره می‌کردند، نه به هیچ کدی از HotXLS، و نه آشکارا به کد CRC-32 هم. آن یک جزئیات، پاس اول تحقیق را به‌سمت مسیر فشرده‌سازی سوق داد: اندازه‌های بافر سپرده‌شده به deflate، window bits، سطح فشرده‌سازی، همه‌ی مظنونان معمول برای یک کرش بومی که از یک codec بیرون می‌آید. هیچ‌کدام از آن‌ها دوام نیاوردند

یک frame بالایی گمراه‌کننده

یک سرریز پشته نوع عجیبی از کرش برای نمادسازی است، چون تا زمانی که گزارش شود، اشاره‌گر پشته از پیش از فضایی که برایش رزرو شده بود عبور کرده. هر چیزی که آن گزارش کرش را تولید کرده، به احتمال زیاد آدرس خطاده را به نزدیک‌ترین نمادی که هنوز می‌توانست پیدا کند حل کرده، و نزدیک‌ترین نقطه‌ی ورود export‌شده که کنار مقصر واقعی نشسته بود اتفاقاً deflate بود. خطای واقعی در تخصیص بافر scratch از Chorba درون مسیر CRC-32 نشسته بود، کامپایل‌شده در همان کتابخانه، به‌اندازه‌ی کافی نزدیک در باینری که با تابعی که واقعاً در حال اجرا بود اشتباه گرفته شود

Bisect کردن با timestamp به‌جای دیباگر

یک کرش که کل فرآیند را از بین می‌برد چیزی برای یک نشست دیباگر معمولی Delphi برای گرفتن باقی نمی‌گذارد، پس تیم به checkpointهای GetTickCount انداخته‌شده در اطراف هر فراخوانی مظنون و یک bisection دستی در سراسر مسیر ذخیره فروبازگشت، و باریک کرد که کدام عملیات در لحظه‌ی مرگ فرآیند در پرواز بود. در کنار آن، یک ساخت خط‌مبنای شناخته‌شده-خوب همان فایل‌های تولیدی را کنار‌به‌کنار با نسخه‌ی فعلی اجرا کرد، به‌طور مشخص برای رد‌کردن یک رگرسیون در تغییرات همان دور پیش از نگاه‌کردن هرگونه بیشتر بالادست. فقط پس از اینکه هر دو بررسی تمیز برگشتند، تحقیق روی یک وابستگی شخص ثالث ساکن شد که کاری غیرمنتظره با یک ورودی کاملاً معتبر انجام می‌داد

چرا try/except در گرفتن یک سرریز پشته شکست می‌خورد؟

یک سرریز پشته استثنایی نیست که کد Delphi هرگز عمداً raise کند، و به همان روشی هم که ویندوز یک access violation یا تقسیم-بر-صفر را تحویل می‌دهد تحویل داده نمی‌شود. این به‌شکل یک خطای guard-page سخت‌افزاری نمایان می‌شود، گزارش‌شده از طریق همان سازوکار structured exception handling که try/except در Delphi روی آن ساخته شده، اما در همان لحظه‌ی دقیقی که شلیک می‌شود معمولاً هیچ فضای پشته‌ای باقی نمانده تا یک handler اجرا شود، کد پاک‌سازی را باز کند، یا حتی گزارش خطا را تمیز تمام کند. روی یک رشته‌ی کارگر که فقط رزرو پیش‌فرض ۱ مگابایتی را حمل می‌کند، با یک بافر scratch به آن اندازه که از پیش بیشتر آنچه باقی مانده را مصرف کرده، چیزی برای زمان‌اجرا برای کار‌کردن باقی نمی‌ماند

procedure TExportWorker.Execute;
var
  Workbook: TXLSXWorkbook;
begin
  Workbook := TXLSXWorkbook.Create;
  try
    try
      BuildWorksheet(Workbook);
      Workbook.SaveAs(FTargetFile);  // crashes the process here on a
                                      // large enough sheet: try/except
                                      // never gets a chance to run
    except
      on E: Exception do
        LogError('Export failed: ' + E.Message);
    end;
  finally
    Workbook.Free;
  end;
end;

آن بلوک except شبیه یک تور ایمنی به‌نظر می‌رسد، و در برابر اغلب شکست‌ها هم یکی است، اما اینجا هیچ کاری نمی‌کند. تیم این را در عمل تأیید کرد: try/except چیزی نگرفت، بلوک finally هم هرگز فرصت قابل‌اعتمادی برای اجرا پیدا نکرد، و اپراتور یک فرآیند مرده را بدون هیچ ورودی لاگ در سطح برنامه دید، دقیقاً همان چیزی که تیکت پشتیبانی اصلی توصیف می‌کرد

راه‌حل: تغذیه‌ی CRC32 در تکه‌های ۶۴ کیلوبایتی به‌جای یک فراخوانی غول‌آسا

راه‌حلی که HotXLS عرضه کرد هیچ چیزی درباره‌ی خودِ zlib-ng و هیچ چیزی درباره‌ی سطح فشرده‌سازی استفاده‌شده برای نوشتن کاربرگ را تغییر نمی‌دهد. ZLibCRC32 حالا ورودی را در تکه‌های ثابت ۶۴ کیلوبایتی می‌پیماید، ۶۵۵۳۶ بایت هرکدام، crc32 خودِ zlib-ng را یک‌بار به‌ازای هر تکه فرا می‌خواند و مقدار چک‌سام در حال اجرا را از یک فراخوانی به فراخوانی بعدی نخ می‌کند. CRC-32 از نظر ساختاری یک الگوریتم افزایشی است، پس یک چک‌سام ساخته‌شده در سراسر چند تکه بیت‌به‌بیت با یکی که در یک فراخوانی تکی در سراسر همان بایت‌ها محاسبه شده یکسان است: راه‌حل نحوه‌ی تقسیم کار را تغییر می‌دهد، نه آنچه محاسبه می‌کند

function ZLibCRC32(crc: LongWord; const buffer; count: Longint): LongWord;
const
  // 64 KB keeps every call comfortably under the Chorba threshold
  CrcChunkSize = 65536;
var
  Cursor: PByte;
  ThisChunk: Longint;
begin
  Result := crc;
  Cursor := PByte(@buffer);
  while count > 0 do
  begin
    ThisChunk := count;
    if ThisChunk > CrcChunkSize then
      ThisChunk := CrcChunkSize;
    Result := zng_crc32(Result, Cursor, Cardinal(ThisChunk));
    Inc(Cursor, ThisChunk);
    Dec(count, ThisChunk);
  end;
end;

هیچ چیزی درباره‌ی فراخوانی SaveAs پیرامون نیاز به تغییر برای کار‌کردن این نداشت، و هیچ چیزی درباره‌ی ورودی‌های ZIP که HotXLS می‌نویسد هم تغییر نکرد: مقدار CRC-32ای که در نهایت در هدر فایل محلی و directory مرکزی می‌افتد دقیقاً همان مقداری است که یک فراخوانی غول‌آسای تکی تولید می‌کرد، فقط از تکه‌های کوچک‌تر مونتاژ شده. تنزل zlib-ng یا فروبازگشت به یک پیاده‌سازی CRC-32 کندتر و سبک‌تصمیم‌گیری هم می‌توانست از این کرش اجتناب کند، اما با هزینه‌ی واقعی برای هر فایلی که در وهله‌ی اول هرگز نزدیک آستانه نشده، به همین دلیل هیچ‌کدام عرضه نشدند

این برای شما اگر zlib-ng را از رشته‌های کارگر خودتان فراخوانی می‌کنید چه معنایی دارد

حالت شکست سرریز پشته‌ی توصیف‌شده در اینجا هیچ ربطی به صفحه‌گسترده‌ها به‌طور مشخص ندارد. هر برنامه‌ای که یک بافر بزرگ را به zlib-ng می‌سپارد، چه برای فشرده‌سازی، رمزگشایی، یا یک چک‌سام، از یک رشته که فقط پشته‌ی پیش‌فرض پلتفرم را حمل می‌کند می‌تواند به همان نوع دیوار برخورد کند، چون کتابخانه الگوریتمش را بر اساس اندازه‌ی ورودی انتخاب می‌کند و برخی از آن الگوریتم‌ها فرض می‌کنند پشته‌ای اضافی وجود دارد. دو دفاع بدون لمس‌کردن خودِ zlib-ng کار می‌کنند: تغذیه‌ی بافرهای بزرگ به روال‌های حساس-به-اندازه در تکه‌های ثابت شرط ماشه را کاملاً برای هر الگوریتمی که به‌طور طبیعی افزایشی است حذف می‌کند، و جایی که تکه‌کردن گزینه‌ای نیست، دادن یک پشته بزرگ‌تر از پیش‌فرض پلتفرم به رشته‌ی فراخواننده اهرم دیگر است. هرکدام از فهمیدن درباره‌ی یک آستانه‌ی اندازه‌ی مستندنشده از یک گزارش کرش تولیدی که تابع اشتباه را سرزنش می‌کند ارزان‌تر است

این آستانه‌ی خاص نامرئی ماند تا زمانی که یک کاربرگ تولیدی به‌اندازه‌ی کافی بزرگ روی نوع اشتباه رشته از آن عبور کرد، که دقیقاً همان نوع شکستی است که فقط زمانی نمایان می‌شود که کد در برابر فایل‌های واقعی به‌جای fixtureهای کوچک اجرا شود. مسیر CRC-32 تکه‌شده حالا به‌عنوان بخشی از خط لوله‌ی نوشتن استاندارد در کامپوننت Excel از HotXLS برای Delphi و C++Builder عرضه می‌شود، بدون هیچ چیزی برای فراخواننده برای پیکربندی و بدون هیچ ویژگی‌ای که آن را روشن یا خاموش کند