Библиотека сайта rus-linux.net
Ошибка базы данных: Table 'a111530_forumnew.rlf1_users' doesn't exist
API ядра Linux, Часть 3: Таймеры и списки в ядре 2.6
Оригинал: "Kernel APIs, Part 3: Timers and lists in the 2.6 kernel"Автор: M. Tim Jones
Дата публикации: 30 Mar 2010
Перевод: Н.Ромоданов
Дата перевода: 14 мая 2010 г.
Краткое содержание: Ядро Linux включает в себя разнообразные API, предназначенные помочь разработчикам создавать более простые и эффективные драйвера и приложения ядра. Два наиболее распространенных API, которые можно использовать для откладывания работ, являются API списков и API таймеров. Изучим эти API и научимся разрабатывать приложения ядра с использованием таймеров и списков.
В этой статье продолжается тема откладывания работ, которую я начал в статье "API ядра Linux, Часть 2: Функции отложенного выполнения, тасклеты ядра и очереди работ" (developerWorks, March 2010). На этот раз я расскажу об интерфейсе прикладного программирования (API) для таймеров, а также о ключевом элементе для всех схем откладывания работ — конструкте списков ядра. Я также рассмотрю API списков ядра, которые используются таймерами и другими механизмами откладывания работ (таких, как очереди работ).
Таймеры являются неотъемлемой частью любой операционной системы, и вы найдете множество механизмов, использующие таймеры. Давайте начнем с краткого обзора схем таймеров в Linux, а затем углубимся в вопросы их использования.
Природа времени (в Linux)
В ядре Linux время измеряется с помощью глобальной переменной с именем jiffies, которая определяет количество временных тиков (тактов), прошедших после загрузки системы. Способ, каким подсчитываются тики, зависит на самом низком уровне от конкретной аппаратной платформы, на которой вы работаете, однако, обычно увеличение значения происходит с помощью прерываний. Частота тиков (младший значащий бит в jiffies) конфигурируема, но в последнем
ядре 2.6 для архитектуры x86 продолжительность тика равна 4 мсек (250Hz). Глобальная переменная jiffies используется в ядре для различных целей, одной из которых является хранение абсолютного текущего времени, которое нужно для вычисления значения тайм-аута для таймера (позже вы увидите примеры этого).
Таймеры ядра
В последних ядрах 2.6 имеются несколько различных схем, используемых для таймеров. Самой простой и наименее точной из всех схем таймеров (хотя и пригодной в большинстве случаев) является интерфейс API для таймеров (timer API). Этот API позволяет создавать таймеры, которые используют переменную jiffies (с минимальным тайм-аутом в 4 мсек). Также имеется API для таймеров высокого разрешения, который позволяет создавать таймеры, время в которых определяется в наносекундах. В зависимости от вашего процессора и скорости, с которой он работает, ваши возможности могут варьироваться, но API позволяет планировать тайм-ауты с интервалом меньшим, чем продолжительность тиков jiffies.
Стандартные таймеры
Стандартный API таймеров является частью ядра Linux в течение довольно продолжительного времени (начиная с самых ранних версий ядра Linux). Хотя этот интерфейс предлагает меньшую точность, чем таймеры высокого разрешения, он идеально подходит для определения тайм-аута в традиционных драйверах и компенсирует ошибки, возникающие при работе с физическими устройствами. Во многих случаях эти тайм-ауты никогда не возникают, а лишь устанавливаются, а затем отменяются.
Простые таймеры ядра реализованы с использованием алгоритма timer wheel ("кольцо таймеров"). Идея впервые была предложена в 1997 году Финном Арне Генгстедом (Finn Arne Gangstad). В нем игнорируется проблема управления большим количеством таймеров, но для типичного случая - управление разумным количеством таймеров – он подходит. (Первоначально реализация таймеров представляла собой двусвязный список, упорядоченный в порядке истечения срока действия таймеров. Хотя этот подход концептуально прост, но он не масштабируем.) В алгоритме timer wheel используется набор слотов, где каждый слот представляет собой некоторый отсчет времени, по достижении которого в будущем истекает время таймера. Слоты определяются в соответствие с логарифмической шкалой времени, причем для этого используется пять слотов. С помощью переменной jiffies определяется количество групп, которые представляют собой время достижения срабатывания таймера в будущем (где каждая группа представляет собой список таймеров). Добавление таймера осуществляется с помощью операций со списками, сложность которых равна O (1) для случая, когда количество таймеров, время которых истекает, равно O (N). Истечение времен таймеров происходит в виде каскадных операций, когда при уменьшении срока действия таймеров они изымаются из слотов с высокой гранулярностью и переносятся в слоты с низкой гранулярностью. Теперь давайте посмотрим, как API используется для реализации этих таймеров.
API таймера
В Linux предлагается простой API для создания таймеров и управления ими. Интерфейс содержит функции (и helper-функции), создающие таймеры, удаляющие их и управляющие ими.
Таймеры задаются с помощью структуры timer_list, в которой хранятся все данные, необходимые для реализации таймера (в том числе указатели на списки и дополнительные статистические данные для таймера, собранные на этапе компиляции). Если рассматривать структуру timer_list с точки зрения ее использования, в ней хранится время истечения срока действия таймера, функция обратного вызова (действующую когда /если истечет время таймера), а также контекст, предоставленный пользователем. Затем нужно инициализировать таймер, что можно сделать несколькими способами. Простейшим способом является вызов функции setup_timer, которая инициализирует таймер и задает предоставленные пользователями функцию обратного вызова и контекст. Либо пользователь может задать эти значения (функцию и данные) непосредственно в таймере и просто вызвать функцию init_timer. Обратите внимание, что функция init_time вызывается внутри функции setup_timer.
void init_timer( struct timer_list *timer );
void setup_timer( struct timer_list *timer,
void (*function)(unsigned long), unsigned long data );
Теперь, когда таймер инициализирован, необходимо задать время работы таймера, что делается с помощью вызова функции mod_timer. Поскольку обычно указывается время работы таймера, которое относится к будущему, то обычно здесь добавляется значение переменной jiffies к смещению от текущего момента времени. С помощью функции del_timer можно можно также удалить таймер (если срок его действия не истек):
int mod_timer( struct timer_list *timer, unsigned long expires ); void del_timer( struct timer_list *timer );
Наконец, с помощью функции timer_pending можно определить, работает ли еще таймер (все еще включен) — функция возвращает 1, если таймер еще работает:
int timer_pending( const struct timer_list *timer );
Пример таймера
Давайте на практике рассмотрим некоторые функции этого API. В листинге 1 представлен простой модуль ядра, в котором демонстрируются основные особенности использования API для простого таймера. В модуле init_module вы с помощью функции setup_timer инициализируете таймер, а затем с помощью обращения к функции mod_timer запускаете таймер. Когда истекает время, установленное в таймере, вызывается функция обратного вызова (my_timer_callback). И наконец, когда модуль удаляется, то происходит удаление таймера (через del_timer). Обратите внимание на то, что функция del_timer возвращает значение, указывающее, продолжает ли таймер использоваться.
Листинг 1. Изучаем API простого таймера
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timer.h>
MODULE_LICENSE("GPL");
static struct timer_list my_timer;
void my_timer_callback( unsigned long data )
{
printk( "my_timer_callback called (%ld).\n", jiffies );
}
int init_module( void )
{
int ret;
printk("Timer module installing\n");
// my_timer.function, my_timer.data
setup_timer( &my_timer, my_timer_callback, 0 );
printk( "Starting timer to fire in 200ms (%ld)\n", jiffies );
ret = mod_timer( &my_timer, jiffies + msecs_to_jiffies(200) );
if (ret) printk("Error in mod_timer\n");
return 0;
}
void cleanup_module( void )
{
int ret;
ret = del_timer( &my_timer );
if (ret) printk("The timer is still in use...\n");
printk("Timer module uninstalling\n");
return;
}
Вы можете подробнее узнать об API таймеров в ./include/linux/timer.h. Хотя интерфейс API простых таймеров прост в использовании и эффективен, он не дает точности, необходимой для приложений реального времени. Поэтому давайте рассмотрим недавнее дополнение к Linux, поддерживающее таймеры высокого разрешения.
Таймеры высокого разрешения
Для таймеров высокого разрешения (или hrtimers) предлагается фреймворк, обеспечивающий высокую точность и управление таймерами и который реализован независимо от ранее рассмотренного фрейворка из-за сложностей, возникающих при объединении этих двух фреймворков. Хотя обычные таймеры работают с гранулярностью, определяемой переменной jiffies, таймеры hrtimers функционируют с гранулярностью в наносекунды.
Фреймворк hrtimer реализован иначе, чем API для традиционных таймеров. Вместо использования слотов и каскадной обработки таймеров, в таймерах hrtimers используются упорядоченные по времени структуры данных (таймеры вставляется в порядке их упорядочивания по времени с тем, чтобы минимизировать их обработку в момент их активации). Используемые структура данных представляют собой красно-черное дерево (одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла — прим.пер.), которое идеально подходит для приложений, предназначенных для достижения максимальной производительности (и обычно доступно в ядре в виде библиотеки).
Фреймворк для таймеров hrtimer имеется в ядре в виде API и может использоваться приложениями пользовательского пространства с помощью команд nanosleep, itimers и интерфейса таймеров POSIX (Portable Operating System Interface - переносимый интерфейс операционных систем Unix).
API таймеров высокого разрешения
Интерфейс hrtimer API имеет некоторое сходство с традиционным API, но также есть некоторые фундаментальные различия, связанные с дополнительным управлением временем. Первое, что вы заметите, что время представлено не в переменной jiffies, а в специальном типе данных, который называется ktime. Такое представление позволяет скрыть некоторые особенности, связанные с эффективным управлением временем на этом уровне гранулярности. В API формализовано различие между абсолютным и относительным временем и при вызове следует указать требуемый тип.
Как и в традиционном API, здесь таймеры представлены структурой, в данном случае - hrtimer. В этой структуре определяются компоненты таймера, необходимые пользователю (функция обратного вызова, срок действия и т. д.), а также указывается информация, используемая для его управления (где таймер размещается в структуре красно-черного дерева, дополнительные статистические данные и т. д.).
Процесс начинается с инициализации таймера с помощью hrtimer_init. В этом вызове указывается таймер, определяются часы (структура clockid_t) и режим таймера (однократный или перезапускаемый). Часы, которые будут использоваться, определяются в файле ./include/linux/time.h и представляют собой различные часы, поддерживаемые системой (например, часы реального времени или часы с равномерной шкалой времени, которые просто представляет собой время, пройденного от некоторого начального момента, например, от загрузки системы). Как только таймер будет инициализирован, его можно запустить с помощью hrtimer_start. В этом вызове указывается время срабатывания таймера (в ktime_t) и режим для значения времени (абсолютное или относительное время).
void hrtimer_init( struct hrtimer *time, clockid_t which_clock,
enum hrtimer_mode mode );
int hrtimer_start(struct hrtimer *timer, ktime_t time, const
enum hrtimer_mode mode);
После того, как таймер hrtimer будет запущен, его можно отменить с помощью обращения к hrtimer_cancel или hrtimer_try_to_cancel. В каждой функции есть ссылка на hrtimer с тем, чтобы таймер можно было остановить. Эти функции отличаются тем, что функция hrtimer_cancel пытается отменить таймер, но если он уже запущен, то функция будет ждать завершения функции обратного вызова. Функция hrtimer_try_to_cancel отличается тем, что она также пытается отменить таймер, но она вернет значение, указывающее на неудачную попытку (failure) в случае, если таймер уже запущен.
int hrtimer_cancel(struct hrtimer *timer); int hrtimer_try_to_cancel(struct hrtimer *timer);
Для того, чтобы убедиться, что hrtimer активирован, вы можете проверить функцию обратного вызова с помощью обращения к функции hrtimer_callback_running. Обратите внимание, что эта функция вызывается внутри функции hrtimer_try_to_cancel и она вернет ошибку в случае, если была вызвана функция обратного вызова таймера.
int hrtimer_callback_running(struct hrtimer *timer);
Интерфейс ktime API
Здесь не обсуждался интерфейс ktime API, в котором имеется богатый набор функции для управления временем с высоким разрешением. Вы можете изучить интерфейс ktime API в ./linux/include/ktime.h.
Пример использования hrtimer
Как видно в листинге 2, использование hrtimer API довольно простое. В модуле init_module вы можете начать с задания определения относительного времени для вашего тайм-аута (в данном случае, 200 мс). Вы инициализируете hrtimer с помощью обращения к функции hrtimer_init (используются часы с равномерной шкалой времени), а затем указываете функцию обратного вызова. И наконец, вы можете запустить таймер, используя для этого ранее созданное значение ktime. Когда таймер запущен, вызывается функция my_hrtimer_callback, которая возвращает значение HRTIMER_NORESTART с тем, чтобы таймер нельзя было автоматически перезапустить снова. Внутри функции cleanup_module вы выполняете сброс таймера путем отмены таймера с помощью функции hrtimer_cancel.
Листинг 2. Исследуем hrtimer API
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/hrtimer.h>
#include <linux/ktime.h>
MODULE_LICENSE("GPL");
#define MS_TO_NS(x) (x * 1E6L)
static struct hrtimer hr_timer;
enum hrtimer_restart my_hrtimer_callback( struct hrtimer *timer )
{
printk( "my_hrtimer_callback called (%ld).\n", jiffies );
return HRTIMER_NORESTART;
}
int init_module( void )
{
ktime_t ktime;
unsigned long delay_in_ms = 200L;
printk("HR Timer module installing\n");
ktime = ktime_set( 0, MS_TO_NS(delay_in_ms) );
hrtimer_init( &hr_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL );
hr_timer.function = &my_hrtimer_callback;
printk( "Starting timer to fire in %ldms (%ld)\n", delay_in_ms, jiffies );
hrtimer_start( &hr_timer, ktime, HRTIMER_MODE_REL );
return 0;
}
void cleanup_module( void )
{
int ret;
ret = hrtimer_cancel( &hr_timer );
if (ret) printk("The timer was still in use...\n");
printk("HR Timer module uninstalling\n");
return;
}
В интерфейсе hrtimer API есть много того, что здесь не было затронуто. Одной интересной особенностью является возможность задания контекста выполнения функции обратного вызова (например, в контексте softirq или в контексте hardiirq). Вы можете узнать больше об интерфейсе hrtimer API в /include/linux/hrtimer.h.
Списки ядра
Как уже упоминалось в начале этой статьи, списки являются полезными структурами, и в ядре имеется их эффективная реализация для типовых случаев их использования. Кроме того, вы здесь найдете списки для API, которые мы уже изучили к настоящему моменту. Изучение API для двусвязных списков поможет вам использовать в своей работе эту эффективную структуру данных, а также понять все богатство кода ядра, где используются списки. Давайте теперь сделаем краткий обзор API списков ядра.
В API предоставляется структура list_head, которая используется не только для представления заголовка списка (с которой начинает расти список), но также указателей, используемых в структуре списка. Давайте посмотрим на пример структуры, в котором показаны возможности работы со списком (см. листинг 3). Обратите внимание на дополнительные возможности структуры list_head, которые используются на этапе компоновки (откомпилированных — прим.пер.) объектов. И заметьте, вы можете добавить структуру list_head в любом месте вашей структуры данных, и, несмотря на некоторые магические возможности GCC (list_entry и container_of, определеных в ./include/kernel/kernel.h), вы сможете разыменовывать указатель списка и получать доступ к супер-объекту.
Листинг 3. Пример структуры с ссылками на список
struct my_data_structure {
int value;
struct list_head list;
};
Как и в любой другой реализации списка, вам нужен заголовок списка, который служит отправной точкой для работы со списком. Это обычно делается с помощью макроса LIST_HEAD, в котором выполняется объявление списка и его инициализация. Этот макрос создает объект со структурой list_head, к которому вы можете добавлять объекты.
LIST_HEAD( new_list )
Можно также с помощью макроса LIST_HEAD_INIT создать заголовок списка вручную (например, если заголовок список содержится в другой структуре).
Когда первоначальная инициализация будет завершена, вы сможете манипулировать со списком с помощью функций list_add и list_del (и еще многими другими функциями). Теперь, давайте перейдем к примеру кода, который лучше проиллюстрирует использование API.
Пример использования API списков
В листинге 4 представлен простой модуль ядра, в котором используется ряд функций из API списков (хотя их гораздо больше можно найти в ./include/linux/list.h). В этом примере создается два списка, в функции init_module они заполняются, а затем в функции cleanup_module с ними манипулируют.
Сначала вы создаете свою структуру данных (my_data_struct), которая включает в себя некоторые данные, а также два заголовка списков. В этом примере демонстрируется, что вы можете добавлять объект одновременно в несколько списков. После этого вы можете создать два заголовка списков (my_full_list и my_odd_list).
В функции init_module вы создаете 10 объектов данных и с помощью функции list_add загружаете их в списки (все объекты - в список my_full_list и все объекты с нечетными значениями - в список my_odd_list). Обратите внимание, что функция list_add имеет два аргумента, первый — ссылка на список, которая будет использоваться внутри объекта, а второй — указатель на начало списка. Это свидетельствует о возможности добавлять объект данных в несколько списков, используя для этого специальные внутренние возможности ядра, позволяющие обращаться к супер-объекту, в котором содержится ссылка на список.
В функции cleanup_module иллюстрируется несколько возможностей API списков, первой из которых является макрос list_for_each, который упрощает итерацию по элементам списка. В этом макросе вы указываете ссылку на текущий объект (pos) и ссылку на список, по которому нужно выполнить итерацию. При каждой итерации, вы получите ссылку на начало списка list_head, которая может быть передана в list_entry для определения объекта-контейнера (контейнера с вашей структурой данных). Укажите вашу структуру и переменную списка, находящуюся в вашей структуре и используемую внутри структуры для разыменования и обратного доступа к контейнеру.
Для работы со списком с нечетными элементами вы можете использовать для итерации другой макрос с именем list_for_each_entry. Этот макрос проще тем, что он автоматически предоставляет ваши структуры данных, устраняя необходимость выполнения функции list_entry.
Наконец, для обхода списка с целью убирания из него ранее размещенных элементов можно использовать макрос list_for_each_safe. Этот макрос выполняет итерацию по списку с гарантированным удалением элементов списка (что вы должны сделать как часть вашей итерации). Вы используете list_entry для получения вашего объекта данных (перемещая его обратно в пул ядра), а затем используете list_del для освобождения позиции в списке.
Листинг 4. Изучаем API списков
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list.h>
MODULE_LICENSE("GPL");
struct my_data_struct {
int value;
struct list_head full_list;
struct list_head odd_list;
};
LIST_HEAD( my_full_list );
LIST_HEAD( my_odd_list );
int init_module( void )
{
int count;
struct my_data_struct *obj;
for (count = 1 ; count < 11 ; count++) {
obj = (struct my_data_struct *)
kmalloc( sizeof(struct my_data_struct), GFP_KERNEL );
obj->value = count;
list_add( &obj->full_list, &my_full_list );
if (obj->value & 0x1) {
list_add( &obj->odd_list, &my_odd_list );
}
}
return 0;
}
void cleanup_module( void )
{
struct list_head *pos, *q;
struct my_data_struct *my_obj;
printk("Emit full list\n");
list_for_each( pos, &my_full_list ) {
my_obj = list_entry( pos, struct my_data_struct, full_list );
printk( "%d\n", my_obj->value );
}
printk("Emit odd list\n");
list_for_each_entry( my_obj, &my_odd_list, odd_list ) {
printk( "%d\n", my_obj->value );
}
printk("Cleaning up\n");
list_for_each_safe( pos, q, &my_full_list ) {
struct my_data_struct *tmp;
tmp = list_entry( pos, struct my_data_struct, full_list );
list_del( pos );
kfree( tmp );
}
return;
}
Существует много других функции для добавления элементов к концу списка, а не в его начало (list_add_tail), объединения списков (list_splice) и проверки содержимого списка (list_empty). Детали, касающиеся функций, работающих со списками ядра, смотрите в разделе "Ресурсы" в оригинале статьи.
Двигаемся дальше
В данной статье изучено несколько API, в которых продемонстрированы возможность разделения функциональности в случае, если это необходимо (API таймеров и API таймеров высокого разрешения hrtimer), и возможность обобщения кода для его повторного использования (API списков). Традиционные таймеры обеспечивают эффективный механизм для типичных тайм-аутов, используемых в драйверах, тогда как таймеры высокого разрешения hrtimer обеспечивают другой уровень качества обслуживания, необходимые для более точных таймеров. Интерфейс API списков является очень обобщенным, но эффективным интерфейсом с богатыми функциональными возможностями. Если вы пишете код ядра, вы воспользуетесь хотя бы одним или всеми тремя этими API, так что их определенно стоит изучать.