Разработка ядра Linux

Лав Роберт

Для объединения двух не перекрывающихся списков и повторной инициализации старого головного элемента служит следующая функция.

list splice_init(struct list head *list, struct list head *head);

Эта функция аналогична функции

list_splice

, за исключением того, что параметр

list

, представляющий список, из которого удаляются элементы, повторно инициализируется.

Как избежать двух лишних разыменований

Если вам уже доступны указатели

next

и

prev

, то можно сэкономить пару процессорных тактов (в частности, время выполнения операций разыменования

указателей) путем вызова внутренних функций работы со связанными списками. Все ранее рассмотренные функции в сущности не делают ничего, кроме получения указателей

next

и

prev

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

list_del(list)

, можно вызвать функцию

__list_del(prev, next)

. Это имеет смысл, только когда указанные указатели уже известны. В противном случае просто получится некрасивый код. Для подробной информации об этих интерфейсах можно обратиться к файлу

<linux/list.h>

.

Перемещение по связанным спискам

Теперь мы уже знаем, как объявлять, инициализировать и работать со связанными списками в ядре. Это все хорошо, но не имеет никакого смысла, если нет возможности работать С данными, которые хранятся в списках! Связанный список — это просто контейнер, в котором хранятся важные данные. Необходимо иметь способ перемещения по списку и доступа к данным. К счастью, ядро предоставляет набор полезных интерфейсов для перемещения по связанным спискам и обращения к структурам данных, которые хранятся в этих списках.

Обратите внимание, что, в отличие от подпрограмм управления списками, операции перебора элементов списка из

n

узлов масштабируются как O(n).

Наиболее простой способ выполнять итерации по элементам связанного списка — это использовать макрос

list_for_each

. Этот макрос принимает два параметра — указатели на структуры

list_head

. Первый параметр указывает на текущий элемент списка, а второй — на любой элемент списка, для которого необходимо обойти все узлы. На каждой итерации цикла первый параметр макроса указывает на текущий элемент списка, пока не будут пройдены все элементы, как в следующем примере.

struct list_head *p;

list_for_each(p, list) {

 /* p указывает на каждый элемент списка list */

}

Это пока все еще бесполезно! Указатель на структуру узла списка — это не то, что нам нужно. Нам нужен указатель на структуру данных, в которой содержится структура узла. В показанном ранее примере структуры данных

my_struct

необходимо получить указатель на каждый экземпляр структуры

my_struct

, а не на их поля

list

. Макрос

list_entry

возвращает структуру данных, которая содержит соответствующий элемент

list_head

. Этот макрос принимает три параметра: указатель на текущий узел, тип структуры данных, в которую включен узел списка, и имя поля структуры данных, в которой хранится этот узел.

struct list_head *p;

struct my_struct *my;

list_for_each(p, mine->list) {

 my = list_entry(p, struct my_struct, list);

 /*

 * указатель my указывает на все структуры данных,

 * в которые включено поле list

 */

}

Макрос

list_for_each

раскрывается в обычный цикл

for

. Предыдущий пример раскрывается следующим образом.

for (p = mine->list->next; p != mine->list; p = p->next)

Кроме этого, макрос

list_for_each

также выполняет предварительную загрузку (prefetch) данных в память, если процессор поддерживает такую возможность, чтобы все данные следующих элементов списка гарантированно находились в памяти. Когда нет необходимости выполнять предварительную загрузку, можно использовать макрос

__list_for_each

, который работает в точности, как цикл

for

. Если нет гарантии, что список содержит очень мало элементов или пустой, то всегда необходимо использовать версию с предварительной загрузкой. Никогда нельзя программировать цикл вручную, необходимо всегда использовать макрос.

Если необходимо выполнить прохождение по спискам в обратном порядке, то следует использовать макрос

list_for_each_prev

, который использует для прохождения указатель

prev

, а не указатель

next

.

Обратите внимание, что при прохождении связанного списка ничто не мешает удалять элементы из этого списка. Обычно, чтобы предотвратить конкурентный доступ, следует использовать блокировки. Макрос

list_for_each_safe

использует временные переменные, чтобы сделать прохождение списка безопасным при одновременном удалении элементов.

struct list_head *p, *n;

struct my_struct *my;

list_for_each_safe(p, n, &mine->list) {

 my = list_entry(p, struct my_struct, list);

 /*

 * указатель my указывает на каждый экземпляр

 * структуры my_struct в списке

 */

}

Обратите внимание, что этот макрос защищен только от операций удаления узлов списка. Для защиты отдельных элементов списка от конкурентного доступа необходимо использовать блокировки.

Приложение Б

Генератор случайных чисел ядра

В ядре Linux реализован генератор случайных чисел, который теоретически может генерировать истинно случайные числа. Генератор случайных чисел собирает в пул энтропии шумы внешней среды, которые поступают из драйверов устройств. Этот пул доступен как в ядре, так и для пользовательских процессов в качестве источника данных, которые не только случайны внутри системы, но и недетерминированы для внешних источников атак. Такие случайные числа используются различными внешними приложениями, особенно для целей криптографии.

Истинно случайные числа отличаются от псевдослучайных чисел, которые генерируются библиотечными функциями языка С. Псевдослучайные числа создаются с помощью детерминированных функций. Хотя такие функции и могут генерировать последовательности чисел, которые обладают некоторыми свойствами истинно случайных чисел, тем не менее такие числа только статистически случайны. Псевдослучайные числа являются детерминированными, потому что если известно хотя бы одно число последовательности, то можно определить и все остальные. Если известно так называемое порождающее число последовательности (seed), то обычно по нему определяется и вся последовательность. Для приложений, которые требуют истинно случайных чисел, как, например, криптография, псевдослучайные числа обычно не подходят.