Coding — АТД ядра Linux и их использование в своих приложениях. Связные списки.

«Абстрактный тип данных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций» - Wikipedia.

В данной части мы будем говорить о реализации такого АТД, как cвязный список (уточнение: речь идет о кольцевых двусвязных списках, но для простоты будем говорить просто список/связный список/двусвязный список). Поверхностно рассмотрим общеизвестный подход к реализации списков, подход, который используется в ядре Linux, и как можно использовать эту реализацию в своих приложениях.

1.1. Общий подход к реализации связных списков

Всем привычный способ определения связного списка выглядит следующим образом:

1 2 3 4 5

struct list { void *data; struct list *next; struct list *prev; }

Обычно к моменту инициализации списка он является пустым (если только мы заранее не определили его элементы статически) и представляется всего лишь одним элементом, а именно «головой» списка:


Рис.1. «Голова» пустого списка

Как видно из рисунка, указатели на следующий next и предыдущий prev элементы указывают на элемент («голову»), к которому они принадлежат (в не кольцевых списках им было бы присвоено значение NULL).
На рисунке 2 можно проследить изменение указателей при добавлении новых элементов (синим цветом выделена «голова» списка).


Рис.2. Добавление элементов в связный список

Для того, чтобы удалить элемент из списка необходимо изменить связи между соседними элементами (переопределить указатели). Таким образом, если мы удалим второй элемент на рисунке 2 справа, то получим список, представленный слева. В коде это можно было записать так (node элемент некоторого списка типа struct list, который представлен выше):

1 2 3 4

... node->next->next->prev = node->prev->prev; node->prev->prev->next = node->next->next; ...

Такой подход к реализации связных списков используется уже давно и стал в некотором роде стандартом de facto, но давайте взглянем, что нам предлагают разработчики ядра Linux.

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

Представим определение списка, используя реализацию ядра:

1 2 3 4 5 6 7 8

struct list_head { struct list_head *next, *prev; } struct list { void *data; struct list_head nodes; }

Улавливаете разницу? Теперь список является частью структуры list, а не представляется самой структурой. Т.о., вся работа со списком сводится к манипуляциям над list_head, будь то добавление или удаление элемента из списка (мысленно уберите элемент data из рисунков 1 и 2). Обращение же к соответствующей структуре list, и, как следствие, к пользовательским данным (для нашего примера это поле data) производится с помощью специального макроса container_of():

1 2 3

#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})

Этот макрос вычисляет адрес ptr типа type по члену member. Если не совсем ясен принцип его работы, то обратитесь к списку источников, там вы найдете подробное объяснение его работы.
Но какой для нас толк от того, каким образом реализованы связные списки (и другие АТД) в ядре? Ведь, чтобы их использовать нам придется каждый раз писать модуль ядра, а это не оправданно, да и попросту было бы глупо. В действительности эта проблема решается довольно просто. Необходимо просто взять библиотеку ядра для работы со связными списками и убрать оттуда код связанный с отладкой и некоторыми специфичными функциями (например prefetch(), которая связана с кешированием данных). Готовую к работе библиотеку вы можете найти в pdf (см. в конце).

1.3. Использование «ядерной» реализации связных списков в своих приложениях

Реализуем небольшую программу, а точнее стек, на примере которого рассмотрим некоторые из доступных функций (для того, чтобы представленная реализация стека работала, необходимо вынести код из приложения в файл list.h, приложение представлено в pdf):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

#include <stdlib.h> #include <stdio.h> #include "list.h" struct stack { int data; struct list_head list; }; LIST_HEAD(top_stack); unsigned int push(int); void pop(void); void popall(void); void print_stack(void); void view(void); int main(int argc, char *argv ) { int n, data; view(); scanf("%d", &n;); while (1) { switch (n) { case 1: printf("Data: "); scanf("%d", &data;); push(data); break; case 2: pop(); break; case 3: print_stack(); break; } if (n == 4) break; view(); scanf("%d", &n;); } popall(); return 0; } unsigned int push(int data) { struct stack *element; if ((element = malloc(sizeof(struct stack))) == NULL) { perror("malloc: push()"); return 1; } element-&gt;data = data; INIT_LIST_HEAD(&element-;&gt;list); list_add(&element-;&gt;list, &top;_stack); return 0; } void pop(void) { struct stack *tmp; if (list_empty(&top;_stack)) printf("stack empty\n"); else { tmp = list_entry(top_stack.next, struct stack, list); list_del(top_stack.next); free(tmp); } } void popall(void) { struct stack *element, *next; if (!list_empty(&top;_stack)) { list_for_each_entry_safe(element, next, &top;_stack, list) { list_del(&element-;&gt;list); free(element); } } } void print_stack(void) { struct stack *element; if (list_empty(&top;_stack)) printf("stack empty\n"); else { list_for_each_entry(element, &top;_stack, list) printf("data: %d\n", element-&gt;data); } } void view(void) { printf("\n1: Push\n"); printf("2: Pop\n"); printf("3: Print\n"); printf("4: Exit\n"); printf("Your choise: "); }

Программа довольно проста для понимания (проверку ошибок мы опустили), поэтому пройдемся только по функциям, связанными со списками.
Итак, мы определяем структуру struct stack и инициализируем «голову» (head) списка top_stack при помощи макроса LIST_HEAD(). top_stack служит указателем на наш список (в данном случае указывает на вершину стека) и не является его частью. Макрос LIST_HEAD() принимает только имя «головного» элемента и аналогичен следующему коду:

1 2 3 4

struct list_head name { struct list_head *next = &name; struct list_head *prev = &name; }

Далее, добавление в стек нового элемента — push(). Функция push() принимает один аргумент, а именно, значение, которое мы хотим положить в стек. Выделяется память под структуру struct stack, инициализируются необходимые элементы структуры (INIT_LIST_HEAD() просто присваивает элементам next и prev адрес самой структуры), и добавляется новый узел в список при помощи функции list_add().
Функция list_add():

1	static inline void list_add(struct list_head *new, struct list_head *head)

Вставляет новый узел new в список после head (так как мы рассматриваем реализацию стека, то каждый новый элемент добавляется после вершины top_stack).
Если мы положили в стек пять элементов со значениями от 1 до 5, то вывод будет выглядеть следующим образом:

1 2 3 4 5

data: 5 data: 4 data: 3 data: 2 data: 1

Если необходимо распологать элементы в обратном порядке, то можно воспользоваться функцией list_add_tail(). Она работает аналогично list_add(), но новый узел вставляет не после head, а до него.
Если в нашей программе заменить list_add() на list_add_tail(), то вывод будет следующим (и вместо реализации стека, мы получаем очередь, которая работает по принципу FIFO):

1 2 3 4 5

data: 1 data: 2 data: 3 data: 4 data: 5

Переходим к функции pop(). pop() должна удалять узел из списка и освобождать память, занимаемую структурой, если список не является пустым.
Проверить является ли список пустым можно при помощи функции list_empty():

1	static inline int list_empty(const struct list_head *head)

Если список пуст, то функция возвращает ненулевое значение, в противном случае 0.
Вернемся к удалению элемента. Прежде чем удалить узел из списка, необходимо сохранить адрес структуры, связанной с данным узлом, чтобы освободить занимаемую ей память. Получить этот адрес можно при помощи макроса list_entry():

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

Данный макрос рассчитывает адрес структуры типа type в которой находится данный список ptr с именем memeber (в самом ядре, для вычисления адреса, используется макрос container_of(), который работает аналогичным образом). В нашей программе можно было бы использовать другой макрос — list_first_entry() для получения первого элемента списка, тогда код:

1	tmp = list_entry(top_stack.next, struct stack, list);

можно было бы заменить на:

1	tmp = list_first_entry(top_stack, struct stack, list);

Итак, адрес мы сохранили, но, прежде чем освободить память, нам надо удалить узел из списка. Сделать это можно с помощью функции list_del():

1	static inline void list_del(struct list_head *entry)

Функция list_del() просто принимает адрес узла, который необходимо удлать из списка (удалить не означает освободить память, она только «отвязывет» узел от списка, освобождать память необходимо самостоятельно).
Теперь рассмотрим функцию печати содержимого стека print_stack(). Для этого нам необходимо пройти все элементы списка и вывести содержимое каждого из них. Сделать это можно следующим образом:

1 2 3 4 5 6

struct stack *element; struct list_head *pos; list_for_each(pos, ⊤_stack) { element = list_entry(pos, struct stack, list); printf("data: %d\n", element->data); }

Макрос list_for_each() проходит по всем узлам списка, начиная с top_stack, и сохраняет текующую позицию в pos. Получить адрес структуры для pos мы можем с помощью ранее описанного макроса list_entry(). Но, так как разработчики люди предусмотрительные то, есть более простой способ выполнить описанную выше опирацию — использовать макрос list_for_each_entry(). Тогда код будет выглядить следующим образом:

1 2 3

struct stack *element; list_for_each_entry(element, ⊤_stack, list) printf("data: %d\n", element->data);

Если необходимо осуществить вывод в обратном порядке, то можно воспользоваться макросом list_for_each_entry_reverse().
И последняя функция, которую осталось рассмотреть — это popall(). popall() необходима в том случае, когда мы завершаем работу программы не освободив память всех элементов (т.е., если список не является пустым). Фактически, нам надо пройти по каждому узлу и удалить его из списка, а затем освободить память, занимаемую структурой. Это можно было бы сделать при помощи макроса list_for_each_entry() и функции list_del(), но пришлось бы хранить указатели next и prev (на следующий и предыдущий элементы, соответственно) во временных переменных. Поэтому для этих целей есть специально предназначенный макрос list_for_each_entry_safe(), который аналогичен list_for_each_entry(), но принимает еще один дополнительный аргумент next для временного хранения элемента:

1 2 3 4 5

struct stack *element, *next; list_for_each_entry_safe(element, next, ⊤_stack, list) { list_del(&element-;>list); free(element); }

Итак, мы рассмотрели несколько базовых функций управления связными списка, достаточных для реализации еще одного абстрактого типа данных — стека (и как мы выяснили очереди, если использовать функцию list_add_tail()). Все остальные функции (слияние списков, перемещение узлов из одного списка в другой и многие другие) вы можете найти в приложении pdf-файла и попробовать поэксперементировать с ними (все комментарии, описывающие назначение функций и макросов, оставлены).
В конце концов, мы имеем переносимую библиотеку для работы со связными списками, написанную разработчиками ядра Linux (а это не так уж и мало).

1.4. Источники

Исходный код оригинального list.h;
rflinux.ru — перевод статьи «связные списки в ядре linux»;
Роберт Лав «Разработка ядра Linux»;
Применение специальных возможностей GCC в ядре Linux — см. раздел «Предварительная выборка»;
Описание работы макроса container_of().P.S. Если вы время от времени заглядываете в исходный код каких-либо приложений, в частности ядра, то безусловно только выигрываете от этого. Вы видите как профессиональные разработчики пишут код, вы можете у них чему-то научиться, а главное, иногда появляется возможность использовать их наработки в своих приложениях. Так и в данном посте я не собирался рассказывать о работе со связными списками, а всего лишь хотел обратить внимание, что и в исходных кодах ядра можно найти много полезного.
И как всегда pdf'ка.