Внутреннее устройство ядра Linux 2.4



Реализация связанных списков в Linux


Прежде чем приступить к знакомству с реализацией очередей ожидания, следует поближе рассмотреть реализацию двусвязных списков в ядре Linux. Очереди ожидания (так же как и все остальное в Linux) считаются тяжелыми в использовании и на жаргоне называются "list.h implementation" потому что наиболее используемый файл - include/linux/list.h.

Основная структура данных здесь - это struct list_head:

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

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

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

#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0)

#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)

Первые три макроопределения предназначены для инициализации пустого списка с указателями next и prev, указывающими на сам список. Из синтаксических ограничений языка C явствует область использования каждого из них - например, LIST_HEAD_INIT()может быть использован для инициализирующих элементов структуры в объявлении, LIST_HEAD - может использоваться для инициализирующих объявлений статических переменных, а INIT_LIST_HEAD - может использоваться внутри функций.

Макрос list_entry() предоставляет доступ к отдельным элементам списка, например (из fs/file_table.c:fs_may_remount_ro()):

struct super_block { ... struct list_head s_files; ... } *sb = &some_super_block;

struct file { ... struct list_head f_list; ... } *file;

struct list_head *p;

for (p = sb->s_files.next; p != &sb->s_files; p = p->next) { struct file *file = list_entry(p, struct file, f_list); do something to 'file' }

Хороший пример использования макроса list_for_each() можно найти в коде планировщика, где производится просмотр очереди runqueue при поиске наивысшего goodness:

static LIST_HEAD(runqueue_head); struct list_head *tmp; struct task_struct *p;




Содержание  Назад  Вперед