در کرنل لینوکس LinkedList چگونه پیاده شده است؟

مقدمه

در این نوشته به چگونگی پیاده سازی یک داده ساختار معروف به نام LinkedList در کرنل لینکوس (Linux) می‌پردازیم. مخاطبان احتمالی این مطلب کسانی هستند که به برنامه نویسی و (چگونگی) توسعه کرنل لینکوس علاقه دارند. (جستوجو کنید kernel hacker)

در ابتدای این مطلب به معرفی داده‌ساختار (Data Structure) LinkedList پرداخته می‌شود. سپس در ادامه پیاده سازی آن در کرنل لینوکس بررسی می‌گردد. (در فارسی LinkedList را لیست‌پیوندی ترجمه کرده‌اند.)

+ نسخه کرنل استفاده شده 5.2 می‌باشد. (می‌توانید نسخه‌های متفاوت را از لینک دریافت کنید.)

معرفی LinkedList

یکی از داده‌ساختارهای ابتدایی که هر برنامه نویسی باید با آن آشنا باشد، LinkedList است. LinkedList برای ذخیره مجموعه‌ای از اطلاعات به صورت مرتب و با ترتیب خطی استفاده می‌شود و از این جهت به آرایه‌ها شبیه است. از طرفی، برخلاف آرایه، اندازه (تعداد عناصر) LinkedList می‌تواند در زمان اجرا تغییر کند و نیازی نیست که در هنگام استفاده از همان ابتدا یک بخش ثابت از حافظه را به این داده‌ساختار اختصاص داد.

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

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

به دلیل ساختار LinkedList و پیوسته نبودن آدرس عناصر آن در حافظه، برخلاف آرایه، امکان Random Access به عناصر وجود ندارد.

اگر هر عنصر LinkedList علاوه بر عنصر بعدی، آدرس عنصر قبلی خود را هم بشناسد به آن Doubly LinkedList می‌گویند.

پیاده سازی Doubly LinkedList در کرنل لینوکس

ساختار (struct) list_head نشان دهنده یک عضو در زنجیره داده‌ساختار Doubly LinkedList تعریف شده در کرنل لینوکس است. تعریف list_head در فایل (include/linux/types.h) types.h به صورت زیر پیدا می‌شود.

struct list_head {
	struct list_head *next, *prev;
};

در این ساختار مشاهده می‌شود که دو اشاره‌گر وجود دارد که یکی به عنصر بعدی و دیگری به عنصر قبلی اشاره می‌کند.

هر عضو از نوع list_head می‌تواند به عنوان شروع یک لیست تفسیر شود. پس اشاره‌گر به ابتدای لیست با اشاره‌گر به اعضای درون لیست تفاوتی ندارد.

نکته قابل توجه در مورد این نحوه تعریف Doubly LinkedList آن است که هیچ حافظه‌ای برای داده‌ای که قرار است نگهداری شود در نظر گرفته نشده است. و در نگاه اول اینگونه تعریف داده‌ساختار بدون کاربرد بنظر می‌رسد.

در واقع توسعه دهندگان کرنل با زیرکی خاصی این داده‌ساختار را بگونه‌ای طراحی کرده‌اند که بتوان برای تعریف لیستی از انواع مختلف داده استفاده کرد.

به عنوان مثالی از استفاده از list_head لیست formats را بررسی می‌کنیم. در این مثال هدف ما تمرکز بر ایجاد لیستی از انواع داده دلخواه است. جدا از چرایی وجود لیست formats و نقشی که در کرنل بازی می‌کند، در این لیست مجموعه‌ای از ساختار linux_binfmt نگهداری می‌شود. پیاده سازی این ساختار را در ادامه مشاهده می‌کنید.

/*
 * This structure defines the functions that are used to load the binary formats that
 * linux accepts.
 */
struct linux_binfmt {
	struct list_head lh;
	struct module *module;
	int (*load_binary)(struct linux_binprm *);
	int (*load_shlib)(struct file *);
	int (*core_dump)(struct coredump_params *cprm);
	unsigned long min_coredump;	/* minimal dump size */
} __randomize_layout;

اولین مشخصه این ساختار، فیلد lh، از نوع list_head است و طبق تعریفی که در بالا آورده شده است؛ فیلد lh دارای اشاره‌گر به عنصر بعدی و قبلی است. همان طور که می‌دانید نوع عنصری که lh به آن اشاره می‌کند از نوع list_head هست و نه از نوع linux_binfmt. سوال مهم این است که با این شرایط چطور می‌توان به عنصر بعدی linux_binfmt دسترسی داشت؟

شکل زیر به طور نمادین نحوه قرار گیری linux_binfmt در حافظه را نمایش می‌دهد. همان طور که می‌بینید در هر عنصر از ساختار linux_binfmt فیلد lh مکان قرار گیری lh عنصر بعدی را در حافظه می‌شناسد (خطوط قرمز). حال اگر بدانیم فیلد lh چند واحد از شروع عنصر در حافظه فاصله دارد (offset)، می‌توانیم آدرس lh عنصر بعدی را منهای offset کنیم تا ابتدای ساختار linux_binfmt را بدست آوریم.

پس به طور خلاصه با دنبال کردن list_head آدرس یک فیلد از ساختاری که اطلاعات مورد نظر را دارد را پیدا می‌شود و سپس با دانستن offset آن فیلد به ابتدای ساختار دسترسی خواهیم داشت.

پیاده سازی این فرآیند در کرنل توسط یک macro به نام list_entry صورت می‌گیرد. در ادامه پیاده سازی این macro بررسی می‌شود.

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

توضیح پارامتر‌هایی که به list_entry (و سپس به container_of) داده می‌شود به این صورت است. ptr اشاره‌گر به یک عنصر list_head است (در این مثال عنصر بعدی که lh به آن اشاره می‌کند). type نوع ساختاری که باید دریافت شود را مشخص می‌کند (در این مثال struct linux_binfmt). و member نام فیلدی درون ساختار گفته شده است که لیست مورد نظر ما را تشکیل می‌دهد (در این مثال lh).

همان طور که مشاهده می‌شود list_entry به صورت مستقیم container_of را فراخوانی ‌میکند. پیاده سازی container_of به صورت زیر است. (این پیاده سازی در فایل include/linux/kernel.h قرار دارد.)

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 &quotpointer type mismatch in container_of()&quot);	\
	((type *)(__mptr - offsetof(type, member))); })

این macro عجیب دقیقا همان کاری را می‌کند که دربالا گفته شد. یک اشاره‌گر را به عنوان ورودی ‌می‌گیرد (همان آدرس lh عنصر بعدی). بعد در خط آخر یک اشاره‌گر از نوع معین شده (type) بازگشت داده می‌شود که آدرس آن از تفریق آدرس گفته شده (ptr) و offset عضو داده شده (member) بدست می‌آید.

فاصله فیلد از ابتدای ساختار تعریف شده توسط offsetof محاسبه می‌شود که کد آن در ادامه آمده است.

#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)

این macro بیان می‌کند که اگر ساختار در خانه صفر حافظه باشد آنگاه عضو گفته شده چه آدرسی خواهد داشت. این همان offset است که با تفریق از آدرس اشاره‌گر ما را به ابتدای ساختار می‌رساند.

کد زیر یک مثال از استفاده از list_entry است. (کد زیر از کرنل لینوکس نیست.)

...
struct linux_binfmt next_element = list_entry(features.lh.next, struct linux_binfmt, lh);
...

در ادامه دیگر توابع و macro های پیاده سازی شده برای list_head به طور خلاصه معرفی می‌شود.

در کرنل تعدادی macro برای کار با  list_head وجود دارد. برای تعریف یک لیست از LIST_HEAD استفاده می‌شود که به صورت زیر تعریف شده است.

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

این macro یک اسم می‌گیرد و یک لیست با نام گفته شده تشکیل می‌دهد. در تعریف LIST_HEAD از یک macro دیگر با نام LIST_HEAD_INIT استفاده شده است که مقدار اولیه اشاره‌گر‌ بعدی و قبلی را برابر عنصر جدید ایجاد شده قرار می‌دهد. (انتها یک لیست وقتی است که عنصر بعدی همان عنصر ابتدایی است.)

برای ایجاد تغییر در لیست مجموعه‌ای از توابع مانند list_add، list_del، list_add_tail و ... موجود است. این توابع در فایل list.h (include/linux/list.h) تعریف گشته‌اند و نام آن‌ها به وضوح کاری را که انجام می‌دهند را مشخص می‌کند.

جمع بندی

در این نوشته به طور مختصر داده‌ساختار LinkedList معرفی شد و در ادامه بخش‌هایی از پیاده سازی کرنل لینوکس که مربوط به این داده‌ساختار بود بررسی گشت. (همچنین آدرس پیاده سازی آن‌ها در این نوشته موجود است. برای کسانی که علاقه به مطالعه بیشتر و دنبال کردن آن دارند).

امیدوارم این نوشته به بخشی از سوالات شما درباره چگونگی کارکرد کرنل لینوکس پاسخ داده باشد.