Sunday, January 25, 2009

Art of structure definition

به نام دوست

در حالت عادی تعریف یک ساختار شامل تعریف و چینش عناصر آن میباشد. در این میان توجه به مشخصات سخت افزار و رفتار کامپایلر نقش به سزایی در قابل حمل بودن برنامه دارد. این موضوع مخصوصا در تقابل سیستمهای 32 بیتی و 64 بیتی ظهور بیشتری دارد. در صورت استفاده از قابلیتهای مختص GNU C مانند استفاده از آرایه های با طول صفر که معمولا برای دستیابی به انتهای حافظه در یک ساختار مورد استفاده قرار میگیرند، این موضوع پررنگتر میشود.
در این نوشته منظور از کامپایلر، کامپایلر gcc میباشد.

1- توجه به اندازه تایپها
تایپها در سخت افزارهای گوناگون اندازه های متفاوت دارند. بنابراین ساختار ما در سیستمها گوناگون اندازه های متفاوتی خواهد داشت. توجه به این نکته مخصوصا در ساختارهای که به جایگاه قرارگیری عناصرشان در حافظه حساس میباشند بسیار مهم است. در صورتیکه نیازمند استفاده از تایپهایی میباشید که میبایست در ساختارهای گوناگون اندازه یسکانی داشته باشند میبتوانید از تایپهای موجود در فایل asm/types.h و همچنین linux/types.h استفاده کنید.
تایپهای u8 (به معنای unsigned int with 8 bit length)و u16 و u32 و u64 تایپهایی با طول ثابت در تمام سخت افزارها برای استفاده در سطح کرنل میباشند. جهت استفاده در سطح کاربر میبایست از تایپهای u32__ و ... استفاده کرد. همچنین تایپهای u_int8_t و u_int16_t و ... تایپهایی از این تیپ میباشند که برای هر دو سطح کاربر و کرنل قابل استفاده میباشند.
نکته مهم دیگر اندازه اشاره گرها در هر سخت افزار است. درسیستمهای 32 بیتی اشاره گرها با فضای 4 بایتی و در سیستمهای 64 بیتی با فضای 8 بایتی نمایش داده میشوند. در صورتیکه ساختار ما دارای اشاره گر باشد، اندازه آن در سیستمهای 32 و 64 بیتی متفاوت خواهد بود. باید در تعریف عناصر ترتیب به گونه ای در نظر گرفته شود که موضوع Alignment (قسمت بعد) به خوبی رعایت شود و همچنین چنانچه لازم باشد تا مقدار یک اشاره گر در یک متغیر از نوع صحیح ذخیره شود تایپ پیشنهادی unsigned long میباشد. البته در استاندارد C99 تایپ uintptr_t برای این منظور در نظر گرفته شده که در فایل linux/types.h قرار دارد.

2- چینش عناصر: Alignment
مطلب مهم دیگری که باید به آن توجه داشت بحث Alignment میباشد. سخت افزارها معمولا انتظار دارند تا عناصر نسبت به طولشان به صورت درستی Align شده باشند. Align به زبان ساده بیانگر قرارگیری عناصر در آدرسی با ضریب مشخص نسبت به طولشان میباشد. به عنوان مثال در یک سیستم 32 بیتی که به Align حساس است، متغیر به طول 4 (u32) میبایست در آدرسی با ضریب چهار قرار گیرد. نکته مهم از منظر تفاوت در Align برای متغیرهای 64 بیتی میباشد که Align آن در سیستمهای 32 بیتی 4 و در سیستمهای 64 بیتی 8 میباشد.
کامپایلر (منظور gcc است) به صورت خودکار سعی میکند چینش عناصر ساختار را در حافظه مطابق خواست سیستم انجام دهد. چنانچه در هنگام تعریف عناصر بحث چینش به خوبی لحاظ نشود، احتمال بروز مکانهای بلااستفاده در ساختار و همچنین فاصله بایتی بین عناصر ساختار وجود خواهد داشت. به عنوان یک مثال ساختار زیر را در نظر بگیرید:

struct test_align {
u_int8_t e1;
u_int16_t e2;
};


در حالت معمولی اندازه این ساختار باید 3 بایت باشد اما به دلیل بحث Align و لزوم قرارگیری e2 در آدرسی با ضریب 2، یک بایت فضای خالی مابین e1 و e2 قرار گرفته و اندازه ساختار برابر با 4 خواهد شد.

3- اندازه ساختار
توجه به اندازه نهایی ساختار و همچنین جایگاه عناصر یک ساختار در بحث Align پررنگ شد. پارامتر دیگری نیز بر روی اندازه ساختار تاثیر دارد که به خصوصیات سخت افزار برمیگردد. معمولا اندازه ها در دنیای رایانه توان 2 هستند که این موضوع باعث افزایش کارآیی پردازنده در مراجعات به حافظه میشود.
در هنگام کامپایل برنامه، در صورتیکه این موضوع توسط برنامه نویس رعایت نشده باشد، بایتهای بلااستفاده در انتهای ساختار اضافه میشوند. در صورت عدم اگاهی از این موضوع، چنانچه دسترسی به انتهای ساختار در حافظه مهم باشد، دردسر ساز خواهد شد.
در سیستمهای 32 بیتی اندازه یا میتواند 8 و یا 16 بیتی باشد و برای بیشتر از آن باید ضریب 32 بیت باشد. همچنین در سیستمهای 64 بیتی این موضوع صحت داشته مگر اینکه اگر ساختار از 32 بیت بیشتر باشد اندازه آن باید ضریب 64بیت گردد.
البته این موضوع ذاتا به دلیل رعایت کردن همان بحث Alignment است که رخ میدهد.

4- یک مثال
یک مثال ساده برای نمایش تقابل سیستمهای 32(i386) بیتی و 64(x86_64) بیتی:

struct example {
u_int64_t e1;
u_int32_t e2;
char
end[0];
};


int
main() {
struct
example *e = malloc(2 * sizeof(struct example));

e[1].e1 = 10;
printf("%d\n", ((struct example *)e->end)->e1);

return
0;
}


این برنامه درسیستم 32 بیتی مشکلی نخواهد داشت. اما خروجی در محیط 64 بیتی غیر قابل پیش بینی خواهد بود (به علت موضوع سوم).

4- کلام آخر
مطالب بیان شده موضوعات مورد توجه در هنگام برنامه نویسی برای یک نرم افزار قابل حمل میباشد. ممکن است که قوانین بالا برای سخت افزار مشخصی متفاوت باشند اما موضوع اصلی توجه و بررسی به این پارامترها برای سخت افزارهای هدف میباشد.

منابع استفاده شده:
http://www.ibm.com/developerworks/library/l-port64.html
کتاب LDD: http://lwn.net/Kernel/LDD3/ فصل 11 این کتاب اندازه تایپها در سخت افزارهای گوناگون را بیان کرده که مفید میباشد.
http://sourceforge.net/projects/iptablestng/

Thursday, January 01, 2009

Locks in kernel ...

به نام دوست

مدیریت مناطق بحرانی در هسته لینوکس با توجه به قابل اجرا بودن لینوکس بر روی سیستمهای چند پردازنده ای و همچنین قابلیت Preemption جزء لاینفک برنامه نویسی هسته میباشد. اتخاذ مکانیزم مناسب با توجه به طبیعت برنامه امری بسیار مهم است که در صورت رعایت نشدن آن موجبات crashهای نامنظم سیستم را فراهم میکند. در مقاله What is RCU یک روش ایجاد همزمانی شرح داده شد. استفاده از لاکهای از دیگر روشهای مرسوم در ایجاد همزمانی میباشند با سابقه‌ای طولانی‌تر از rcu، که در این مقاله به صورت مختصر با آنها آشنا میشویم.

۱- روندهای اجرایی
در هسته لینوکس سه دسته روندهای اجرایی از نظر اولویت و تاثیر بر یکدیگر وجود دارند:
  1. IRQ Handler
  2. Soft IRQ, Tasklet, Timer
  3. User Context
دسته بندی بدین معناست که در صورت اجرای روند با شماره بیشتر بر روی یک cpu، امکان گرفتن cpu از آن و واگذاری آن به روند اجرایی با شماره کمتر وجود دارد. به عبارتی اولویتها از بالا به پایین کاهش می یابد.
در مورد دسته بندی ۲، اجرای یک نمونه از هر نوع بر روی یک cpu مانع اجرای دیگری از همان دسته بر روی آن cpu میشود.
با توجه به اینکه ساختمان داده مشترک ما (داده های بحرانی) توسط چه دسته‌ای از روندها مورد تاثیر قرار میگیرد مکانیزم مناسب باید اتخاذ گردد. توجه به طبیعت اجرای هر کدام از روندها موجب درک بهتر مکانیزم مورد استفاده خواهد بود.

۲- آشنایی اولیه با روندها
هسته یک برنامه بزرگ است که اجرای کد از مجاری مختلف و در قالب روندهای زیر صورت می‌پذیرد:
IRQ Handler: در اصل قطعه کدی است که در پاسخ به یک وقفه سخت افزاری اجرا میشود. این موضوع مورد توجه است که همیشه یک نمونه از یک نوع وقفه در حال اجرا خواهد بود. به عبارتی در صورتیکه ساختمان داده ما توسط یک نوع وقفه مورد دسترسی قرار میگیرد جای هیچ گونه نگرانی برای ایجاد همزمانی وجود ندارد.
SoftIRQ: وقفه نرم‌افزاری، معمولا قطعه کدی هست که کامل کننده کار یک وقفه سخت افزاری میباشد. به عبارتی این نوع وقفه‌ها برای کوتاه‌تر شدن مدت زمان اجرای وقفه‌های سخت‌افزاری ایجاد شده‌اند. در مورد شیوه اجرای این روندها باید گفت که همیشه امکان اجرای چندین نسخه از یک نمونه وقفه نرم‌افزاری وجود دارد. بنابراین حتی اگر یک نوع وقفه نرم‌افزاری به داده‌ها دسترسی دارد بیشک میبایست متدهای همزمانی مناسب مورد توجه قرار گیرند.
Tasklet: این نوع روندها در اصل نوعی از وقفه‌های نرم‌افزاری میباشند. تفاوت در این است که این نوع روندها در زمان اجرا قابل تعریف میباشند بر خلاف وقفه‌های نرم‌افزاری که به صورت استاتیک در کد کرنل تعریف شده‌اند. همچنین این تضمین وجود دارد که تنها یک نمونه از یک نوع Tasklet در یک زمان در حال اجرا باشد.
Timer: این نوع روندها نیز نوعی وقفه نرم افزاری هستند که به صورت دابنامیک قابل تعریف هستند (مانند Taskletها) و میبایست در موعد مشخصی(از نظر زمانی) اجرا شوند. این روندها در قالب وقعه نرم افزاری TIMER_SOFTIRQ اجرا میشوند.
UserContext: در مواردی همچون اجرای system call از پراسسهای سطح کاربر، با توجه به اینکه کد system call در سطح هسته اجرا میشود، اصطلاحا این روند اجرایی که حاصل سوییچ کردن از مود کاربر به مود هسته است را UserContext مینامند.
نکته مهم در مورد چهار روند اول آن است که با توجه به اینکه این روندها اجرای اینتراپتها را غیرفعال میکنند به هیچ عنوان نباید به حالت wait بروند. در نتیجه متد لاکی که برای این روندهای میبایست مورد استفاده قرار گیرد به هیچ عنوان نباید به حالت wait رود حتی در صورتیکه لاک مورد نظر در دسترس نباشد.

۳- انواع لاکهای
مکانیزمهای اصلی لاک در هسته لینوکس به این شرح هستند:
  1. spinlock (فایل include/asm/spinlock.h): مکانیزم spinlock اصطلاحا busy wait بوده و نمونه یک مکانیزم سریع و سبک میباشد. در این نوع قفل تنها یک پردازش در یک زمان میتواند لاک را تصاحب کند و همچنین پردازشهای منتظر به هیچ عنوان به خواب نمیروند، بنابراین این نوع لاک برای روندهای گروه ۱ و ۲ مناسب میباشد.
  2. semaphore (فایل include/asm/semaphore.h): در این مکانیزم بسته به مقدار اولیه سمافر،‌ تعداد پردازشهایی که میتوانند در یک زمان لاک را تصاحب کنند قابل تنظیم است. البته در اکثر اوقات به صورت حداکثر یک تصاحب کننده در یک زمان(مانند spin) مورد استفاده قرار میگرید که این لاکها اصطلاحا با نام mutex (فایل include/linux/mutex.h)شناخته میشوند. پردازشهایی که نتوانسته‌اند قفل را تصاحب کنند به حالت wait خواهند رفت. استفاده از این لاک برای گروههای ۱ و ۲ به هیچ عنوان صحیح نیست. این لاک مناسب برای استفاده توسط گروه ۳ میباشد.
۴- spinlock
این متد لاک Busy wait هست: بدان معنی که cpu آنقدر چرخ میزند تا لاک را بدست آورد. به عبارتی پراسسی که سعی در بدست آوردن لاک دارد به حالت wait نمیرود.
نکات مورد توجه در استفاده از این لاک:
  1. قسمت بحرانی به هیچ عنوان نباید به حالت wait برود.
  2. قسمت بحرانی در حد امکان باید کوتاه باشد. (نظر به اینکه cpu را مطلقا در اختیار میگیرد)
فرم ساده استفاده از این لاک به این صورت میباشد:
spinlock_t lock = SPIN_LOCK_UNLOCKED;

spin_lock(&lock);

//critical section

spin_unlock(&lock);

بسته به اینکه چه روندهایی به ساختمان داده ما دسترسی دارند میبایست روش مناسبی برای بدست آوردن لاک استفاده گردد. روشهای دیگر برای بدست آوردن لاک به این شرح هستند:
۴-۱: spin_lock/unlock_bh
این تابع علاوه بر بدست آوردن لاک، اجرای SoftIRQها را بر روی پردازنده فعلی غیر فعال میکند. استفاده از این متد برای ایجاد همزمانی User Context ها با گروه دوم الزامی است.
دلیل غیر فعال کردن گروه ۲ احتمال بروز Dead Lock میباشد. در صورتیکه از حالت معمولی استفاده شود احتمال دارد به هنگامی که پردازش UserContext لاک را گرفته و در منطقه بحرانی به سر میبرد، توسط SoftIRQ پردازنده گرفته شده و آن هم سعی در گرفتن همان لاکی کند که هرگز باز نخواهد شد. البته در ایجاد همزمانی در سمت مقابل (SoftIRQها) با UserContext از فرمت ساده استفاده میشود چرا که در صورتی که پردازنده به آنها واگذار شود به هیچ عنوان توسط UserContext قابل بازپس گیری نیست.
استفاده از این مکانیزم بدین شکل خواهد بود:






UserContextSoftIRQ
spin_lock_bh(&lock);spin_lock(&lock);
//critical section//critical section
spin_unlock_bh(&lock);spin_unlock(&lock);

۴-۲: spin_lock/unlock_irq
این متد باعث میشود تا اجرای اینتراپتهای سخت افزاری و نرم افزاری بر روی پردازنده فعلی غیر فعال شود. از این متد برای هماهنگی ما بین گروههای ۳ و ۲ با گروه ۱ استفاده میشود. توجه داشته باشید که این تابع به هیچ عنوان به وضعیت فعال یا غیر فعال بودن اینتراپتهای سخت افزاری توجهی ندارد بنابراین برای صدا زدن از IRQ Handlerها مناسب نیست.
با توجه به اینکه اینتراپتهای نرم‌افزاری نیز غیر فعال میشوند میتوان از این روش برای ایجاد همزمانی مابین گروه ۳ با گروه ۱ استفاده کرد.
۳-۴:spin_lock_irqsave, spin_unlock_irqrestore
این متد علاوه بر بدست آوردن لاک، پرچم حالت (وضعیت فعال یا غیر فعال بودن اینتراپتها) را ذخیره میکند که برای ایجاد همزمانی ما بین IRQ Handlerها مورد استفاده قرار میگیرد.

۵- semaphore
چنانچه قبلا ذکر شد این نوع لاک مناسب برای ایجاد همزمانی مابین روندهای UserContext میباشد. بدست آوردن لاک در این مکانیزم معمولا به دو صورت انجام میشود: ۱- استفاده از تابع down و ۲- استفاده از تابع down_interruptible.
تابع شکل دوم در صورتی استفاده میشود که شما خواسته باشید در صورت ارسال سیگنال(به عنوان مثال فشردن ctrl+c) یا اینتراپت به برنامه‌ای که در حالت wait قرار دارد،‌ برنامه از wait خارج شود. خروج بدین شکل از حالت wait باعث میشود تابع down_interruptible مقدار خطا برگرداند.
با توجه به اینکه معمولا از mutex (سمافور با مقدار اولیه یک - یک نگهدارنده در یک زمان) برای ایجاد همزمانی استفاده میشود طرح کلی استفاده از این سمافور به عنوان نمونه ذکر میشود:
DEFINE_MUTEX(mt_lock);
mutex_lock_interruptible(&mt_lock);
//critical section
mutex_unlock(&mt_lock);
۶- مکانیزم مناسب جهت ایجاد همزمانی
جدول زیر به صورت خلاصه مکانیزم مناسب جهت ایجاد همزمانی با استفاده از لاکها را مابین روندهای گوناگون نشان میدهد. در این جدول متدهای مناسب جهت فراخوانی معرفی شده‌اند.

۳

۲

۱

روندها

spin_lock

spin_lock

spin_lock_irqsave

۱

spin_lock

spin_lock

spin_lock_irq

۲

down_interruptible

spin_lock_bh

spin_lock_irq

۳

اطلاعات جزءی‌تر را میتوانید از اینجا بدست آورید.

منابع استفاده شده:
Unreliable guide to locking
kernel locking techniques
understanding linux kernel