Saturday, May 16, 2009

Связные списки в ядре Linux

Введение:

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

Ясная, лёгкая в использовании реализация циклического двусвязного списка на С находится в файле include/linux/list.h. Код этой реализации эффективен и переносим - в противном случае он не был бы в ядре. Если при программировании ядра необходим список для работы с множеством данных любой структуры, то используют двусвязные списки ядра linux. Путём минимальной правки (удаление аппаратно-зависимого ускорения предвыборки записей списка) списки могут быть адаптированы к использованию в приложениях пользовательского режима. Здесь находится версия файла, пригодная для такого использования.

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

  1. Независимость от типа:
    Вы можете использовать любую структуру данных, какую заблагорассудится.
  2. Переносимость:
    Хотя я не пробовал использовать списки на всех платформах, но можно предположить, что данная реализация весьма переносима. В противногм случае она бы не попала в дерево исходного кода ядра.
  3. Простота использования:
    В силу независимости списков от типа данных записей для инициализации, доступа к элементам списка, прохождения по списку используются одни и те же функции.
  4. Простота восприятия:
    Макросы и подставляемые (inline) функции делают код очень элегантным и простым для понимания.
  5. Экономия времени:
    Вам не нужно изобретать колесо. Использование списков позволяет существенно сэкономить время на отладку и повторное создание списков для каждой структуры данных, которая используется в программе.
Реализация списков в ядре linux отличается от той, которую Вы могли видеть ранее. Обычно, данные содержатся в элементах связанного списка:
struct my_list {
        void *myitem;
        struct my_list *next;
        struct my_list *prev;
};
Реализации списков в ядре создаёт иллюзию, что это данные содержат в себе список! Например, если у Вас есть список данных со структурой struct my_cool_list, то список будет выглядеть следующим образом:
struct my_cool_list {
        struct list_head list; /* kernel's list structure */
        int my_cool_data;
        void* my_cool_void;
};
Следует отметить следующее:
  1. Список содержится в структурах, которые необходимо связать.
  2. Структуру struct list_head можно поместить везде в объявлении Вашей структуры.
  3. struct list_head может иметь любое имя.
  4. У вас в Вашей структуре может быть несколько полей типа struct list_head!
Например, объявление, приведённое ниже также правильно:
struct todo_tasks{
        char *task_name;
        unsigned int name_len;
        short int status;

        int sub_tasks;

        int subtasks_completed;
        struct list_head completed_subtasks; /* структура списка */

        int subtasks_waiting;
        struct list_head waiting_subtasks;  /* ещё один список таких же или других элементов! */

        struct list_head todo_list;  /* список дел - todo_tasks */
};
Вот несколько примеров использования списокв в самом ядре: Раз уж мы вплотную подошли к спискам, то посмотрим на объявление типа struct list_head в include/linux/list.h:
struct list_head{
        struct list_head *next;
        struct list_head *prev;
};
Пожалуй, самое время перейти к деталям. Для начала, давайте посмотрим, как можно использовать этот тип в нашей программе, а затем рассмотрим, как эта структура работает.

Использование списка:

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

Ниже приведён пример создания, добавления, удаления и прохождения списка.

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct kool_list{
        int to;
        struct list_head list;
        int from;
};

int main(int argc, char **argv)
{
        struct kool_list *tmp;
        struct list_head *pos, *q;
        unsigned int i;
        struct kool_list mylist;
        INIT_LIST_HEAD(&mylist.list);
        /* вместо строки выше можно было бы использовать макрос
         * LIST_HEAD(mylist) при объявлении списка; данный макрос объявляет
         * переменную типа struct list_head с указанным именем и инициализирует её.
         */

        /* добавление элементов в mylist */
        for (i = 5; i != 0; --i) {
                tmp = (struct kool_list *)malloc (sizeof (struct kool_list));
                 /* INIT_LIST_HEAD(&tmp->list); 
                 *
                 * здесь производится инициализация поля list динамически созданной структуры типа struct
                 * kool_list. Эту инициализацию можно пропустить, если следуим будет вызов add_list() или
                 * любая другая функция подобного рода, которая выполняет инициализацию полей next, prev
                 */
                 printf ("enter to and from:");
                 scanf ("%d %d", &tmp->to, &tmp->from);

                 /* добавить новый элемент 'tmp' в список элементов mylist */
                 list_add(&(tmp->list), &(mylist.list));
                 /* можно также использовать list_add_tail(), которая добавляет новые элементы
                  * в хвост списка
                  */
        }
        printf ("\n");

        /* теперь у нас есть циклически связанный список элементов типа struct kool_list.
        * теперь распечатаем весь список
        */

        /* list_for_each() - это макрос, реализующий цикл прохождения по элементам списка.
        * первый аргумент макроса используется как счётчик, или иными словами в цикле он
        * используется для указания на поле типа list_head текущего элемента списка.
        * второй аргумент - указатель на список. Макрос не манипулирует этим указателем.
        */
        printf ("traversing the list using list_for_each()\n");
        list_for_each(pos, &mylist.list) {
                 /* в этой строке: pos->next указывает на поле 'list' следующего элемента списка, а
                 * pos->prev  - на поле 'list' предыдущего элемента. Здесь элемент - это запись типа
                 * struct kool_list. Но нам нужен сам элемент, а не его поле 'list'! list_entry() позволяет
                 * получить указатель на сам элемент. Как это делается, см. ниже в части "Как
                 * это работает?".
                 */
                 tmp = list_entry (pos, struct kool_list, list);

                 /* в качестве аргументов макрос принимает указатель на struct list_head, в котором
                 * хранится текущая позиция списка, второй аргумент - тип пользовательской структуры,
                 * членом которой является поле, на которое указывает, первый аргумент и третий
                 * аргумент - имя этого поля (член типа struct list_head в пользовательской структуре).
                 * Макрос возвращает указатель на структуру, членом которой является первый аргумент.
                 * Или точнее говоря, на который указывает первый аргумент - pos.
                 * Например, выше list_entry() возвратит указатель на элемент типа struct kool_list,
                 * частью которого является pos
                 */

                 printf("to = %d from= %d\n", tmp->to, tmp->from);
        }
        printf ("\n");
         /* т.к. наш список цикличен, то его можно обойти и в обратном порядке.
          * всё, что для этого надо - заменить макрос 'list_for_each' на 'list_for_each_prev',
          * а всё остальное останется без изменений.
          *
          * Также можно использовать list_for_each_entry(), чтобы пройти по элементам списка
          * данного типа. Например:
          */
        printf ("traversing the list using list_for_each_entry()\n");
        list_for_each_entry(tmp, &mylist.list, list)
                printf ("to = %d from = %d\n", tmp->to, tmp->from);
                /* Как видно, здесь мы не используем макрос list_entry(), чтобы получить указатель
                 * на элемент списка типа struct kool_list. Этот указатель помещается в         переменную tmp
                 * на "полуавтомате" самим макросом list_for_each_entry() :)
                 */
        printf ("\n");

        /* теперь будем вежливыми и освободим память, захваченную под записи kool_list items.
         * т.к. мы будем удалять записи из списка с помощью list_del(), нам нужна защищённая
         * версия макроса list_for_each().
         * такая версия названа list_for_each_safe(). Этот макрос НЕОБХОДИМО использовать
         * для организации цикла, который предусматривает удаление или перемещение записей
         * из одного списка в другой.
         */
        printf ("deleting the list using list_for_each_safe()\n");
        list_for_each_safe(pos, q, &mylist.list){
                 tmp = list_entry(pos, struct kool_list, list);
                 printf ("freeing item to = %d from = %d\n", tmp->to, tmp->from);
                 list_del(pos);
                 free (tmp);
        }

        return 0;
}

Как это работает?

В общем, большая часть реализации довольна тривиальна, но тонко она выполнена. Тонкость заключается в том, чтобы получить адрес целой структуры по адресу члена, являющегося частью этой структуры (т.е., получить указатель на структуру, содержащую в себе элемент типа struct list_head). Этот трюк проделывает макрос list_entry(), как мы увидели ранее. Теперь попытаемся понять, как он это делает.

#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Если опираться на ранее приведённый пример, то макрос будет развёрнут следующим образом:
        ((struct kool_list *)((char *)(pos) - (unsigned long)(&((struct kool_list *)0)->list)))
Это смущает многих, однако приём достаточно прост и является широко известным (см. вопрос 2.14 - англ.). Используя указатель на поле типа struct list_head в структуре данных, макрос list_entry() просто высчитывает адрес самой структуры. Чтобы выполнить такой расчёт, необходимо выяснить, где в структуре данных находится член типа list_head (смещение list_head). Затем просто вычисляется смещение члена типа list_head по отношению к указателю, который был передан макросу в качестве первого аргумента.

Следующий вопрос, как нам вычислить смещение элемента внутри структуры данных? Допустим, у нас есть структура struct foo_bar и нам надо найти смещение элемента boo, который является членом структуры. Сделаем это следующим образом:
        (unsigned long)(&((struct foo_bar *)0)->boo)
Возьмём нулевой адрес памяти и приведём его к указателю на нашу структуру - в данной случае, к указателю на struct foo_bar. Затем возьмём адрес поля, которое нас интересует. Это и будет смещение данного поля внутри структуры. Так как мы узнали абсолютное положение данного элемента в памяти, мы теперь можем с помощью этого элемента получить указатель на конкретный экземпляр целой структуры, опираясь на некоторые данные (например, аргумент pos в случае с макросом list_entry). Вот и всё. Чтобы лучше понять, что происходит, советую вам погонять этот код.
#include <stdio.h>
#include <stdlib.h>

struct foobar {
        unsigned int foo;
        char bar;
        char boo;
};

int main (int argc, char** argv)
{
        struct foobar tmp;

        printf ("address of &tmp is= %p\n\n", &tmp);
        printf ("address of tmp->foo= %p \t offset of tmp->foo= %lu\n", &tmp.foo,
                 (unsigned long) &((struct foobar *)0)->foo);
        printf ("address of tmp->bar= %p \t offset of tmp->bar= %lu\n", &tmp.bar,
                 (unsigned long) &((struct foobar *)0)->bar);
        printf ("address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n", &tmp.boo,
                 (unsigned long) &((struct foobar *)0)->boo);

        printf ("computed address of &tmp using:\n");
        printf ("\taddress and offset of tmp->foo= %p\n",
                (struct foobar *) (((char *) &tmp.foo) - ((unsigned long) &((struct foobar *)0)->foo)));
        printf ("\taddress and offset of tmp->bar= %p\n",
                (struct foobar *) (((char *) &tmp.bar) - ((unsigned long) &((struct foobar *)0)->bar)));
        printf ("\taddress and offset of tmp->boo= %p\n",
                (struct foobar *) (((char *) &tmp.boo) - ((unsigned long) &((struct foobar *)0)->boo)));

        return 0;
}
Вывод приведённого куска кода:
address of &tmp is = 0xbfffed00

address of tmp->foo = 0xbfffed00   offset of tmp->foo= 0
address of tmp->bar = 0xbfffed04   offset of tmp->bar= 4
address of tmp->boo = 0xbfffed05   offset of tmp->boo= 5

computed address of &tmp using:
address and offset of tmp->foo = 0xbfffed00
address and offset of tmp->bar = 0xbfffed00
address and offset of tmp->boo = 0xbfffed00

См. также:

  • Код хэш-таблиц, организованных в виде списков.
  • Ещё код /sutff/src/

Оригинал статьи на английском лежит здесь.

No comments:

ПОСЕТИТЕЛИ

free counters