Внутреннее устройство ядра 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;


list_for_each(tmp, &runqueue_head) { p = list_entry(tmp, struct task_struct, run_list); if (can_schedule(p)) { int weight = goodness(p, this_cpu, prev->active_mm); if (weight > c) c = weight, next = p; } }

Где поле p-> run_list объявлено как struct list_head run_list внутри структуры task_struct и служит для связи со списком. Удаление элемента из списка и добавление к списку (в начало или в конец) выполняются макросами list_del()/list_add()/list_add_tail(). Пример, приведенный ниже, добавляет и удаляет задачу из очереди runqueue:

static inline void del_from_runqueue(struct task_struct * p) { nr_running--; list_del(&p->run_list); p->run_list.next = NULL; }

static inline void add_to_runqueue(struct task_struct * p) { list_add(&p->run_list, &runqueue_head); nr_running++; }

static inline void move_last_runqueue(struct task_struct * p) { list_del(&p->run_list); list_add_tail(&p->run_list, &runqueue_head); }

static inline void move_first_runqueue(struct task_struct * p) { list_del(&p->run_list); list_add(&p->run_list, &runqueue_head); }


Содержание раздела