Содержание


Инструменты программирования в ядре: Часть 65. Работа с динамическими структурами памяти

Comments

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

  • статическая память: надёжность, живучесть и меньшая подверженность ошибкам;
  • динамическая память: гибкость использования.

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

Циклический двусвязный список

Чтобы сократить дублирование кода, разработчики ядра, начиная с версии ядра 2.6, ввели стандартную реализацию кругового, двойного связного списка; и всем программистам, планирующим использовать списки для решения своих задач, рекомендуется использовать именно эту реализацию. Поэтому мы должны подробно рассмотреть подобные списки.

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

Для использования механизма списка драйвер должен подключить файл <linux/list.h>, в котором объявлена структура типа list_head:

struct list_head {
   struct list_head *next, *prev;
};

Чтобы воспользоваться возможностями списков в собственном коде достаточно вставить list_head внутрь собственных структур, входящих в список, например:

struct todo_struct {
   struct list_head list;
   int priority;
   /* добавить другие зависимые от задачи поля */
};

Заголовки списков должны быть проинициализированы перед использованием с помощью макроса INIT_LIST_HEAD. Заголовок списка может быть объявлен и проинициализирован динамически, как показано ниже:

struct list_head todo_list;
INIT_LIST_HEAD( &todo_list );

Также списки могут быть созданы и проинициализированы статически при компиляции:

LIST_HEAD( todo_list );

Некоторые функции для работы со списками определены в файле <linux/list.h>. API для работы с циклическим списком позволяет выполнять любые операции с элементами списка, не прибегая к манипуляциям с внутренними полями списка, отвечающим за связи между элементами. Эта особенность помогает обеспечить целостность списков.

list_add( struct list_head *new, struct list_head *head );

Метод list_add добавляет новый элемент new сразу же после элемента head, как правило, в его начало. Этот метод может быть использован для создания стеков. Но, следует отметить, что элемент head должен быть фактической головой списка, так как если передать структуру list_head, которая окажется где-то в середине списка, то новая запись будет вставлена сразу после неё. Так как списки Linux являются круговыми, то голова списка обычно ничем не отличается от любой другой записи.

list_add_tail( struct list_head *new, struct list_head *head );

Метод list_add_tail добавляет элемент new перед элементом head в конец списка, другими словами, этот метод можно использовать для создания FIFO-очередей "первый вошёл - первый вышел".

list_del( struct list_head *entry );
list_del_init( struct list_head *entry );

Данные методы удаляют запись из списка. Если эта запись может быть впоследствии добавлена в другой список, то следует использовать метод list_del_init(), инициализирующий заново указатели связного списка.

list_move( struct list_head *entry, struct list_head *head );
list_move_tail( struct list_head *entry, struct list_head *head );

Эти методы перемещают запись с текущего положения в начало / конец списка.

list_empty( struct list_head *head );

Этот метод возвращает ненулевое значение, если данный список пуст.

list_splice( struct list_head *list, struct list_head *head );

Данный метод объединяет два списка вставкой нового списка list сразу после головы head.

Структуры list_head хорошо подходят для реализации линейных списков, но программисты чаще заинтересованы в более крупных структурах, которые увязаны со списком в единое целое. Существует макрос list_entry, связывающий указатель структуры list_head с указателем на содержащую его структуру:

list_entry( struct list_head *ptr, type_of_struct, field_name );
  • ptr является указателем на используемую структуру list_head;
  • type_of_struct является типом структуры, содержащей этот ptr;
  • field_name является именем поля списка в этой структуре.

Пример: в показанной ранее структуре todo_struct поле списка называется list. Таким образом, превратить запись в списке listptr в соответствующую структуру, можно с помощью следующего кода:

struct todo_struct *todo_ptr = list_entry( listptr, struct todo_struct, list );

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

Обход связных списков выполняется с помощью указателей prev и next. В качестве примера предположим, что требуется сохранить список объектов todo_struct, отсортированный в порядке убывания. Функция добавления новой записи будет выглядеть примерно следующим образом:

void todo_add_entry( struct todo_struct *new ) {
   struct list_head *ptr;
   struct todo_struct *entry;
   /* голова списка поиска: todo_list */
   for( ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next ) {
      entry = list_entry( ptr, struct todo_struct, list );
      if( entry->priority < new->priority ) {
         list_add_tail( &new->list, ptr);
         return;
      }
   }
   list_add_tail( &new->list, &todo_list );
}

Однако, лучше воспользоваться одним из предопределённых макросов для создания цикла для перебора списка. Например, предыдущий цикл можно было бы написать так:

void todo_add_entry( struct todo_struct *new ) {
   struct list_head *ptr;
   struct todo_struct *entry;
   list_for_each( ptr, &todo_list ) {
      entry = list_entry( ptr, struct todo_struct, list );
      if( entry->priority < new->priority) {
         list_add_tail( &new->list, ptr );
         return;
      }
   }
   list_add_tail( &new->list, &todo_list );
}

Использование предусмотренных макросов помогает избежать простых ошибок при программировании; так как их разработчики уже приложили некоторые усилия для повышения их производительности. Существует несколько вариантов подобных макросов:

list_for_each( struct list_head *cursor, struct list_head *list )
list_for_each_prev( struct list_head *cursor, struct list_head *list )

Эти макросы создают цикл for, выполняемый по одному разу для указателя cursor, который поочередно устанавливается на каждую последовательную позицию в списке (перемещение может выполняться как впёрёд по списку, так и в обратную сторону).

list_for_each_safe( struct list_head *cursor, 
                    struct list_head *next, struct list_head *list )

Будьте осторожны в ситуациях, когда модификация списка выполняется одновременно с итерацией по нему. Если операции в цикле могут удалить запись в списке, то используйте макрос list_for_each_safe, сохраняющий следующую запись в списке в next для продолжения цикла. Поэтому, даже если запись, на которую указывает cursor, будет удалена, это не приведёт к ошибке.

list_for_each_entry( type *cursor, struct list_head *list, member )
list_for_each_entry_safe( type *cursor, type *next, struct list_head *list, member )

Эти макросы облегчают процесс просмотр списка, содержащего структуры указанного типа type. Здесь cursor является указателем на содержащий структуру тип, а member является именем структуры list_head внутри содержащей структуры. С этими макросами нет необходимости помещать внутри цикла вызов макроса list_entry().

В заголовках файла <linux/list.h> присутствуют и другие дополнительные декларации для описания динамических структур.

Модуль, использующий динамические структуры

В листинге 1 показан пример модуля ядра, создающего и использующего простейшую динамическую структуру в виде односвязного списка. Полный код примера можно найти в архиве list.tgz в разделе "Материалы для скачивания".

Листинг 1. Пример использования односвязного списка (mod_list.c)
#include <linux/slab.h>
#include <linux/list.h>
MODULE_LICENSE( "GPL" );
static int size = 5;
module_param( size, int, S_IRUGO | S_IWUSR ); // размер списка как параметр модуля
struct data {
    int n;
    struct list_head list;
};
void test_lists( void ) {
   struct list_head *iter, *iter_safe;
   struct data *item;
   int i;
   LIST_HEAD( list );
   for( i = 0; i < size; i++ ) {
      item = kmalloc(  sizeof(*item), GFP_KERNEL );
      if( !item ) goto out;
      item->n = i;
      list_add( &(item->list), &list );
   }
   list_for_each( iter, &list ) {
      item = list_entry( iter, struct data, list );
      printk( KERN_INFO "[LIST] %d\n", item->n );
   }
out:
   list_for_each_safe( iter, iter_safe, &list ) {
      item = list_entry( iter, struct data, list );
      list_del( iter );
      kfree( item );
   }
}
static int __init mod_init( void ) {
   test_lists();
   return -1;
}             
module_init( mod_init );

И пример запуска такого модуля

$ sudo /sbin/insmod ./mod_list.ko size=3
insmod: error inserting './mod_list.ko': -1 Operation not permitted
$ dmesg | tail -n3
[LIST] 2
[LIST] 1
[LIST] 0

Сложно-структурированные данные

Уже одной ограниченной структуры данных struct list_head вполне достаточно для построения динамических структур практически любой степени сложности, как, например, сбалансированных B-деревьев, красно-чёрных списков и т.д. Именно поэтому ядро 2.6 было полностью переписано в части используемых списковых структур для использования struct list_head. Вот как можно представить бинарное дерево с помощью этих структур:

struct my_tree {
   struct list_head left, right; /* левое и правое поддеревья */
   /* добавить другие зависимые от задачи поля */
};

Заключение

При обсуждении заголовков списков, было показано две альтернативных возможности объявить и инициализировать такой заголовок списка:

  • статически, когда переменная объявляется макросом и тут же выполняются все действия по инициализации:
    LIST_HEAD( todo_list );
  • динамически, когда переменная сначала объявляется, как и любая переменная элементарного типа, и только потом инициализируется указанием её адреса:
    struct list_head todo_list;
    INIT_LIST_HEAD( &todo_list );

Такая же двойственность (статика + динамика) возможностей будет наблюдаться и в последствии, например относительно всех примитивов синхронизации. Напрашивается вопрос: зачем необходима такая избыточность и в каких случаях применять тот или иной подход? Дело в том, что очень часто подобные переменные не фигурируют в коде автономно, а встраиваются в более сложные структуры данных. Для таких встроенных объявлений подходит только динамический способ инициализации, а единичные переменные проще создавать статически.

На этом мы завершим обсуждение особенностей распределения памяти в ядре Linux и перейдём к следующей теме, посвящённой работе с временем в этой ОС.


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=937742
ArticleTitle=Инструменты программирования в ядре: Часть 65. Работа с динамическими структурами памяти
publish-date=07182013