اشاره‌گرهای نشان‌دار چگونه از خطای ABA در ساختارهای داده بدون قفل جلوگیری می‌کنند؟

پلتفرم‌های معاملات بسامدبالا (HFT) و موتورهای پایگاه داده در زیر بار پردازش‌های همگام و شدید، دیگر بی‌سروصدا دچار خرابی ناگهانی نمی‌شوند؛ زیرا پردازنده‌های امروزی بی‌آنکه جلب توجه کنند، برچسب‌های شماره‌گذاری مخفی را به آدرس‌های حافظه پیوست می‌کنند. این سازوکار در سطح سخت‌افزار از یک شرایط رقابتی فاجعه‌بار جلوگیری می‌کند؛ رخدادی که وقتی چندین هسته پردازشی به طور هم‌زمان ساختار داده بدون قفل یکسانی را دستکاری می‌کنند، پدید می‌آید.[1]

توسعه‌دهندگان نرم‌افزار به صورت سنتی برای جلوگیری از تخریب داده‌ها از قفل‌های انحصار متقابل (Mutex) استفاده می‌کنند که رشته‌های پردازشی (Threads) را پیش از دسترسی به حافظه اشتراکی وادار به صف کشیدن و انتظار می‌سازد. در مقابل، رویکرد برنامه‌نویسی بدون قفل این گلوگاه‌های نرم‌افزاری را کنار می‌زند و دست به دامن دستورالعمل‌های اتمیک در دل سخت‌افزار می‌شود.[4]

موریس هرلیهی و نیر شاویت در کتاب مرجع خود درباره برنامه‌نویسی چندپردازنده‌ای این استاندارد را صورت‌بندی کرده‌اند: «یک شیء همگام زمانی بدون قفل خوانده می‌شود که تضمین کند دست‌کم یک رشته پردازشی همواره می‌تواند عملیات خود را در تعداد محدودی گام به پایان برساند.»[4]

این تضمین ساختاری بدان معناست که کل سامانه هرگز از کار نمی‌ایستد، حتی اگر پردازشِ رشته‌های منفرد با تاخیر مواجه شود. تحقق چنین دستاوردی نیازمند این است که پردازنده عملیات خواندن، ویرایش و نوشتن را در قالب یک گام تفکیک‌ناپذیر واحد اجرا کند.[7]

سراب یکنواختی وضعیت داده‌ها

پایه و اساس برنامه‌نویسی بدون قفل، دستورالعمل «مقایسه و جابه‌جایی» (Compare-and-Swap یا CAS) است؛ سازوکاری که پیش از بازنویسی داده در یک موقعیت حافظه، ابتدا بررسی می‌کند مقدار آن تغییر نکرده باشد. اگر مقدار فعلی با مقداری که رشته در ابتدا خوانده بود همخوانی داشته باشد، سخت‌افزار داده جدید را جایگزین می‌کند.[2]

این شیوه بر این فرض استوار است که برابری مقدار، حتماً به معنای یکسان ماندن وضعیت کلی ساختار داده است. همین فرض، نقصی امنیتی و بنیادین پدید می‌آورد که به «مسئله ABA» مشهور است؛ مشکلی که نخستین بار در سال ۱۹۸۳ میلادی در معماری IBM System/370 شناسایی شد.[1][6]

یک پشته (Stack) بدون قفل را فرض کنید که در آن رشته شماره ۱ قصد دارد گره A را از بالای پشته بردارد؛ گره‌ای که هم‌اکنون به گره B اشاره می‌کند. رشته ۱ آدرس گره A را می‌خواند، اما سیستم‌عامل درست پیش از اجرای دستور مقایسه و جابه‌جایی، اجرای آن را معلق می‌کند.[4]

در حالی که رشته ۱ در حالت تعلیق است، رشته ۲ فعال می‌شود و ابتدا گره A و سپس گره B را برمی‌دارد و سرانجام مجدداً گره A را بالای پشته بازمی‌گرداند. اکنون دوباره گره A در بالای پشته قرار دارد، اما این بار به جای گره B، به گره C اشاره می‌کند.[1]

رشته ۱ دوباره به جریان می‌افتد و دستور مقایسه و جابه‌جایی خود را اجرا می‌کند. سخت‌افزار بالای پشته را بازرسی می‌کند، می‌بیند گره A هنوز آنجاست، و بدون درک جزییات می‌پندارد هیچ تغییری رخ نداده است؛ در نتیجه اشاره‌گر سر پشته را با گره B جایگزین می‌کند که هم‌اکنون دیگر وجود ندارد و حذف شده است.[3]

مکانیک درونی دستور مقایسه و جابه‌جایی

حالا ساختار داده دچار تخریب شده و به قطعه‌ای از حافظه آزادشده ارجاع می‌دهد؛ رخدادی که به محض اقدام برنامه برای پیمایش این پشته، به سقوط حتمی برنامه می‌انجامد. سخت‌افزار دقیقاً طبق فرمان عمل کرده است، زیرا دستور CAS صرفاً آدرس باینری را کنترل می‌کند و توان ارزیابی دیگری ندارد.[2]

پردازنده‌ها معنا و منطق حافظه‌ای را که دستکاری می‌کنند درک نمی‌کنند. برای سیلیکون، یک نشانی بازیافتیِ حافظه با نشانی دست‌نخورده تفاوتی ندارد و همین امر مقایسه سطحی تساوی را برای بازیافت حافظه ذاتاً نارسا می‌کند.[5]

مهندسان نرم‌افزار نمی‌توانند صرفاً از سخت‌افزار بخواهند که تمام محتویات گره را یکجا چک کند، چرا که دستورهای اتمیک دقیقاً محدود به پهنای ثبات‌های ثبتی پردازنده‌اند. یک پردازنده ۶۴ بیتی استاندارد تنها می‌تواند ۶۴ بیت از داده‌ها را در یک چرخه ساعت ساعت مقایسه و جایگزین کند.[2]

این محدودیت معمارانه، توسعه‌دهندگان را ناچار می‌کند که پیشینه و تاریخچه یک نشانی حافظه را درون خودِ اشاره‌گر بگنجانند. اگر اشاره‌گر با هر تغییر در گره دگرگون شود، دستور مقایسه و جابه‌جایی به درستی خطا خواهد داد و جلوی بازنویسی اشتباه را می‌گیرد.[6]

راهکار این چالش در یکی از شگردهای معماری رایانه‌های معاصر نهفته است. هرچند تراشه‌های کنونی در قالب دستگاه‌های ۶۴ بیتی بازاریابی می‌شوند، اما پردازنده‌های امروزی x86-64 در واقعیت فقط از ۴۸ بیت پایینی برای آدرس‌دهی حافظه مجازی بهره می‌برند.[2]

شمارنده‌های نسلی و اشاره‌گرهای نشان‌دار

این ویژگی طراحی موجب می‌شود ۱۶ بیت بالایی هر اشاره‌گر برای سیستم‌عامل عملاً دست‌نخورده و بدون استفاده باقی بماند. برنامه‌نویسان سیستمی از همین فضای خالی برای نشاندن یک شمارنده نسلی در دل آدرس حافظه سوءاستفاده می‌کنند.[1]

هربار که رشته‌ای یک گره را از ساختار داده خارج می‌کند، این شمارنده ۱۶ بیتی را پیش از افزودن دوباره گره، یک واحد افزایش می‌دهد. آدرس فیزیکی در حافظه یکسان است، اما برچسب متصل به آن با هر بار دگرگونی تغییر می‌کند.[4]

هنگامی که رشته ۱ فعال شده و اجرای مقایسه و جابه‌جایی را امتحان می‌کند، دیگر صرفاً به دنبال گره A نیست، بلکه گره A با برچسب نسخه ۱ را طلب می‌کند؛ این در حالی است که پشته در حال حاضر گره A را با برچسب نسخه ۳ در خود دارد.[1][6]

سخت‌افزار کل این رشته ۶۴ بیتی را به مثابه یک عدد صحیح واحد می‌سنجد. از آنجا که بیت‌های بالایی همخوانی ندارند، آزمون برابری شکست می‌خورد، عملیات مقایسه و جابه‌جایی متوقف می‌شود و رشته ۱ مجبور می‌گردد عملیات خود را با وضعیت صحیح ساختار از سر بگیرد.[2]

این روش که با نام «اشاره‌گر نشان‌دار» شناخته می‌شود، در عمل یک آدرس فضایی در حافظه را به یک موقعیت زمانی تغییر می‌دهد و به تراشه این امکان را می‌دهد که استفاده اولیه از آدرس را با دفعات بعدی بازیافت آن متمایز کند.[3]

پشتیبانی سخت‌افزار و مجموعه دستورالعمل‌ها

به‌کارگیری اشاره‌گرهای نشان‌دار نیازمند پشتیبانی اختصاصی سخت‌افزاری است، زیرا پردازنده باید قبل از خواندن حافظه (Dereferencing)، این برچسب الحاقی را حذف کند. هر تلاشی برای ارجاع به آدرسی با ۱۶ بیتِ غیرصفر بالایی، بلادرنگ به خطای دسترسی به حافظه (Segmentation Fault) منجر می‌شود.[2]

شرکت‌های اینتل و ای‌ام‌دی این مسئله را با معرفی دستور CMPXCHG16B برطرف کردند که مقایسه و جابه‌جایی ۱۲۸ بیتی را پشتیبانی می‌کند. بدین‌ترتیب برنامه‌نویس می‌تواند اشاره‌گر ۶۴ بیتی را دست‌نخورده حفظ کند و شمارنده ۶۴ بیتی نسلی را در حافظه مجاور آن بنشاند.[2]

دستورالعمل ۱۲۸ بیتی هر دو قلم اشاره‌گر و شمارنده را به شکل هم‌زمان تعویض می‌کند. این رویکرد نیاز به ماسک‌گذاری بیتی را برطرف کرده و بازه بسیار فراخ‌تری برای شمارنده فراهم می‌آورد؛ هرچند نیازمند چینش و تراز دقیق داده‌ها در خطوط کش پردازنده است.[1][2]

معماری آرم (ARM) این مسئله را از زاویه‌ای دیگر حل می‌کند و از شیوه پیوند بارگذاری/ذخیره‌سازی مشروط (Load-Link/Store-Conditional) بهره می‌برد. دستور LDREX آدرس حافظه را می‌خواند و پایش می‌کند و در ادامه دستور STREX تنها زمانی در آن می‌نویسد که رشته پردازشی دیگری آن نقطه پایش‌شده را دستکاری نکرده باشد.[5]

این تفاوت در معماری پردازنده‌ها باعث می‌شود کدهای بدون قفل به‌ندرت میان پلتفرم‌های گوناگون به‌سادگی قابل انتقال باشند. پیاده‌سازی اشاره‌گر نشان‌دار نوشته‌شده برای سرور اینتل، بدون ایجاد لایه‌های انتزاعی قابل‌توجه بر روی تلفن هوشمند با معماری آرم کامپایل نخواهد شد.[5][6]

سقف سرریز بیتی در شمارنده‌های ۱۶ بیتی

اگرچه نشاندن شمارنده درون ۱۶ بیتِ دست‌نخورده اشاره‌گر راهکاری خوش‌تراش به نظر می‌رسد، اما یک رخنه ریاضیاتی ناخوشایند درون خود دارد. یک عدد صحیح ۱۶ بیتی پیش از رسیدن به نقطه سرریز و بازگشت به صفر، تنها گنجایش ذخیره ۶۵٬۵۳۶ مقدار منحصربه‌فرد را دارد.[1]

اگر یک رشته پردازشی معلق بماند و هم‌زمان دقیقا ۶۵٬۵۳۶ دگرگونی روی یک گره رخ دهد، شمارنده دقیقا روی همان نسخه مورد انتظار رشته معلق ریست می‌شود؛ در این حالت دستور مقایسه و جابه‌جایی به اشتباه پیروز شده و مسئله ABA با وجود تمام تمهیدات پدیدار می‌شود.[4]

محاسبات کوهستون درباره احتمال تداخل اشاره‌گرها در جریان دگرگونی‌های متوالی نشان می‌دهد که این سقف چقدر بحرانی است. روی یک هسته پردازشی ۵ گیگاهرتزی معاصر، در شرایط حداکثر تداخل، این شمارنده ۱۶ بیتی می‌تواند تنها ظرف ۲۶ میکروثانیه سرریز کند و مجدداً به نقطه آغاز برگردد.[1]

این واقعیت نشان می‌دهد اشاره‌گرهای نشان‌دار به‌تنهایی از حیث ریاضیات پاسخگوی امنیت کامل در سامانه‌های مالی با تاخیر فرابسیار پایین نیستند. احتمال آماری برخورد شاید کم به نظر برسد، اما در سامانه‌هایی با میلیاردها تراکنش در روز، رخدادهای نادر اجتناب‌ناپذیرند.[1][3]

برای کاهش این خطر، توسعه‌دهندگان باید یا سرعت بازیافت حافظه را به شکل مصنوعی محدود سازند یا به شمارنده‌های عریض‌تر روی بیاورند. دستور مقایسه و جابه‌جایی ۱۲۸ بیتی این بحران را حل می‌کند؛ زیرا دور زدن و سرریز یک شمارنده ۶۴ بیتی با سرعت پردازنده‌های امروزی قرن‌ها زمان می‌برد.[2]

بدیل‌های نرم‌افزاری اشاره‌گرهای نشان‌دار

به دلیل همین وابستگی‌های سخت‌افزاری و خطرات سرریز، بسیاری از معماری‌های مدرن اشاره‌گرهای نشان‌دار را رها کرده‌اند. آنها در عوض به «اشاره‌گرهای پرخطر» (Hazard Pointers) تکیه می‌کنند؛ تکنیکی که ماجد مایکل در سال ۲۰۰۴ معرفی کرد و از بازیافت حافظه تا زمان مطالعه آن توسط رشته‌ها جلوگیری می‌کند.[3]

در روش اشاره‌گرهای پرخطر، هر رشته پردازشی نشانی‌هایی را که مشغول خواندنشان است در یک لیست اشتراکی ثبت می‌کند. سامانه تخصیص حافظه پیش از آزادسازی گره‌ها، این لیست را وارسی می‌کند تا مطمئن شود هیچ نشانیِ فعالی زودتر از موعد بازیافت نشود.[3][4]

این متدولوژی مسئله ABA را از ریشه می‌خشکاند و دیگر نیازی به کشف اثر آن پس از وقوع فاجعه نیست. نیازی به دستورالعمل‌های اختصاصی سخت‌افزاری ندارد و از سقف محاسباتی شمارنده‌ها برکنار است، هرچند افت عملکرد جزئی ناشی از سربار نرم‌افزاری به همراه دارد.[3]

انتخاب میان اشاره‌گرهای نشان‌دار و اشاره‌گرهای پرخطر همچنان از مباحث داغ در مهندسی سامانه‌ها به شمار می‌رود. عامل تعیین‌کننده نهایی احتمالاً مصوبات آتی کمیته استاندارد C++ درباره مدل‌های حافظه اتمیک و نیز گسترش احتمالی آدرس‌دهی مجازی به بیش از ۴۸ بیت در معماری‌های نوین پردازنده خواهد بود.[1][6]