Разработка ядра Linux - [195]

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), то обычно по нему определяется и вся последовательность. Для приложений, которые требуют истинно случайных чисел, как, например, криптография, псевдослучайные числа обычно не подходят.

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

Физический термин энтропия — это мера беспорядка и случайности в любой системе. Энтропия измеряется в единицах энергии на единицу температуры (Джоуль на градус Кельвина). Когда Клод Шеннон (Claude Shennon)[98], создатель информационной теории, искал термин для представления случайности информации, великий математик Джон фон Нейман (John von Neumann)[99] предложил ему использовать термин энтропия, потому что никто толком не понимает, что за этим понятием кроется. Шеннон согласился, и сегодня это звучит как энтропия Шеннона. Некоторые ученые считают, что такое двойное название только вносит путаницу, и когда речь идет об информации, то используют термин неопределенность. Разработчики ядра, наоборот, считают, что "энтропия" — это "круто", и поддерживают использование данного термина.

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

Генератор случайных чисел ядра был предложен в версии 1.3.30 и находится в файле drivers/char/random.c.

Принцип работы и реализация

Компьютеры — это предсказуемые устройства. Действительно, трудно найти случайное поведение в системе, поведение которой можно практически полностью программировать. Однако окружающая среда, где находится машина, полна различных шумов, которые недетерминированы и которые можно измерить. Источники таких шумов включают моменты времени, в которые возникают события, связанные с аппаратными устройствами, а также события, связанные с взаимодействием пользователей и компьютера. Например, интервалы времени между нажатиями клавиш, перемещения мыши, интервалы времени между некоторыми типами прерываний и время выполнения запроса блочного ввода-вывода являются недетерминированными, и, кроме того, их не может измерить внешний злоумышленник. Случайная информация, которая получается из этих событий, записывается в пул энтропии. Пул растет и заполняется случайными и непредсказуемыми шумовыми данными. По мере добавления данных в пул вычисляется оценка энтропии, и итоговое значение запоминается. Это позволяет всегда иметь информацию о значении энтропии в пуле. На рис. Б. 1 показана диаграмма прохождения потока энтропии в пул и из пула.