Наши партнеры

Книги по Linux (с отзывами читателей)

Библиотека сайта rus-linux.net

Вперед Назад Содержание

2. Управление процессами и прерываниями

2.1 Структура задачи и таблица процессов

Каждый процесс динамически размещает структуру struct task_struct. Максимальное количество процессов, которое может быть создано в Linux, ограничивается только объемом физической памяти и равно (см. kernel/fork.c:fork_init()):

     /*
         * В качестве максимально возможного числа потоков принимается безопасное
         * значение: структуры потоков не могут занимать более половины
         * имеющихся страниц памяти.
         */
        max_threads = mempages / (THREAD_SIZE/PAGE_SIZE) / 2;

что для архитектуры IA32 означает, как правило, num_physpages/4. Например, на машине с 512M памяти, возможно создать 32k потоков. Это значительное усовершенствование по сравнению с 4k-epsilon пределом для ядер 2.2 и более ранних версий. Кроме того, этот предел может быть изменен в процессе исполнения, передачей значения KERN_MAX_THREADS в вызове sysctl(2), или через интерфейс procfs:

# cat /proc/sys/kernel/threads-max
32764
# echo 100000 > /proc/sys/kernel/threads-max
# cat /proc/sys/kernel/threads-max
100000
# gdb -q vmlinux /proc/kcore
Core was generated by `BOOT_IMAGE=240ac18 ro root=306 video=matrox:vesa:0x118'.
#0  0x0 in ?? ()
(gdb) p max_threads
$1 = 100000

Множество процессов в Linux-системе представляет собой совокупность структур struct task_struct, которые взаимосвязаны двумя способами.

  1. как хеш-массив, хешированный по pid, и
  2. как кольцевой двусвязный список, в котором элементы ссылаются друг на друга посредством указателей p->next_task и p->prev_task.

Хеш-массив определен в include/linux/sched.h как pidhash[]:

/* PID hashing. (shouldnt this be dynamic?) */
#define PIDHASH_SZ (4096 >> 2)
extern struct task_struct *pidhash[PIDHASH_SZ];

#define pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

Задачи хешируются по значению pid, вышеприведенной хеш-функцией, которая равномерно распределяет элементы по диапазону от 0 до PID_MAX-1. Хеш-массив используется для быстрого поиска задачи по заданному pid с помощью inline-функции find_task_by_pid(), определенной в include/linux/sched.h:

static inline struct task_struct *find_task_by_pid(int pid)
{
        struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

        for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
                ;

        return p;
}

Задачи в каждом хеш-списке (т.е. хешированные с тем же самым значением) связаны указателями p->pidhash_next/pidhash_pprev, которые используются функциями hash_pid() и unhash_pid() для добавления/удаления заданного процесса в/из хеш-массив. Делается это под блокировкой (spinlock) tasklist_lock, полученной на запись.

Двусвязный список задач организован таким образом, чтобы упростить навигацию по нему, используя указатели p->next_task/prev_task. Для прохождения всего списка задач, в системе предусмотрен макрос for_each_task() из include/linux/sched.h:

#define for_each_task(p) \
        for (p = &init_task ; (p = p->next_task) != &init_task ; )

Перед использованием for_each_task() необходимо получить блокировку tasklist_lock на ЧТЕНИЕ. Примечательно, что for_each_task() использует init_task в качестве маркера начала (и конца) списка - благодаря тому, что задача с pid=0 всегда присутствует в системе.

Функции, изменяющие хеш-массив и/или таблицу связей процессов, особенно fork(), exit() и ptrace(), должны получить блокировку (spinlock) tasklist_lock на ЗАПИСЬ. Что особенно интересно - перед записью необходимо запрещать прерывания на локальном процессоре, по той причине, что функция send_sigio(), при прохождении по списку задач, захватывает tasklist_lock на ЧТЕНИЕ, и вызывается она из kill_fasync() в контексте прерывания. Однако, если требуется доступ ТОЛЬКО ДЛЯ ЧТЕНИЯ, запрещать прерывания нет необходимости.

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

В других версиях UNIX информация о состоянии задачи разделяется на две части, в одну часть выделяется информация о состоянии задачи (называется 'proc structure', которая включает в себя состояние процесса, информацию планировщика и пр.) и постоянно размещается в памяти, другая часть, необходима только во время работы процесса ('u area', которая включает в себя таблицу дескрипторов, дисковые квоты и пр.) Единственная причина такого подхода - дефицит памяти. Современные операционные системы (не только Linux, но и другие, современная FreeBSD например) не нуждаются в таком разделении и поэтому вся информация о состоянии процесса постоянно хранится в памяти.

Структура task_struct объявлена в include/linux/sched.h и на сегодняшний день занимает 1680 байт.

Поле state объявлено как:

volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */

#define TASK_RUNNING            0
#define TASK_INTERRUPTIBLE      1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_ZOMBIE             4
#define TASK_STOPPED            8
#define TASK_EXCLUSIVE          32

Почему константа TASK_EXCLUSIVE имеет значение 32 а не 16? Потому что раньше значение 16 имела константа TASK_SWAPPING и я просто забыл сместить значение TASK_EXCLUSIVE, когда удалял все ссылки на TASK_SWAPPING (когда-то в ядре 2.3.x).

Спецификатор volatile в объявлении p->state означает, что это поле может изменяться асинхронно (в обработчиках прерываний):

  1. TASK_RUNNING: указывает на то, что задача "вероятно" находится в очереди запущенных задач (runqueue). Причина, по которой задача может быть помечена как TASK_RUNNING, но не помещена в runqueue в том, что пометить задачу и вставить в очередь - не одно и то же. Если заполучить блокировку runqueue_lock на чтение-запись и просмотреть runqueue, то можно увидеть, что все задачи в очереди имеют состояние TASK_RUNNING. Таким образом, утверждение "Все задачи в runqueue имеют состояние TASK_RUNNING" не означает истинность обратного утверждения. Аналогично, драйверы могут отмечать себя (или контекст процесса, под которым они запущены) как TASK_INTERRUPTIBLE (или TASK_UNINTERRUPTIBLE) и затем производить вызов schedule(), который удалит их из runqueue (исключая случай ожидания сигнала, тогда процесс остается в runqueue).
  2. TASK_INTERRUPTIBLE: задача в состоянии "сна", но может быть "разбужена" по сигналу или по истечении таймера.
  3. TASK_UNINTERRUPTIBLE: подобно TASK_INTERRUPTIBLE, только задача не может быть "разбужена".
  4. TASK_ZOMBIE: задача, завершившая работу, до того как родительский процесс ("естественный" или "приемный") произвел системный вызов wait(2).
  5. TASK_STOPPED: задача остановлена, либо по управляющему сигналу, либо в результате вызова ptrace(2).
  6. TASK_EXCLUSIVE: не имеет самостоятельного значения и используется только совместно с TASK_INTERRUPTIBLE или с TASK_UNINTERRUPTIBLE (по OR). При наличии этого флага, будет "разбужена" лишь эта задача, избегая тем самым порождения проблемы "гремящего стада" при "пробуждении" всех "спящих" задач.

Флаги задачи представляют не взаимоисключающую информацию о состоянии процесса:

unsigned long flags;    /* флаги процесса, определены ниже */
/*
 * Флаги процесса
 */
#define PF_ALIGNWARN    0x00000001      /* Print alignment warning msgs */
                                        /* Not implemented yet, only for 486*/
#define PF_STARTING     0x00000002      /* создание */
#define PF_EXITING      0x00000004      /* завершение */
#define PF_FORKNOEXEC   0x00000040      /* создан, но не запущен */
#define PF_SUPERPRIV    0x00000100      /* использует привилегии супер-пользователя */
#define PF_DUMPCORE     0x00000200      /* выполнен дамп памяти */
#define PF_SIGNALED     0x00000400      /* "убит" по сигналу */
#define PF_MEMALLOC     0x00000800      /* Распределение памяти */
#define PF_VFORK        0x00001000      /* "Разбудить" родителя в mm_release */
#define PF_USEDFPU      0x00100000      /* задача использует FPU this quantum (SMP) */

Поля p->has_cpu, p->processor, p->counter, p->priority, p->policy и p->rt_priority связаны с планировщиком и будут рассмотрены позднее.

Поля p->mm и p->active_mm указывают, соответственно, на адресное пространство процесса, описываемое структурой mm_struct и активное адресное пространство, если процесс не имеет своего (например потоки ядра). Это позволяет минимизировать операции с TLB при переключении адресных пространств задач во время их планирования. Так, если запланирован поток ядра (для которого поле p->mm не установлено), то next->active_mm будет установлено в значение prev->active_mm предшествующей задачи, которое будет иметь то же значение, что и prev->mm если prev->mm != NULL. Адресное пространство может разделяться потоками, если в системный вызов clone(2) был передан флаг CLONE_VM, либо был сделан системный вызов vfork(2).

Поле p->fs ссылается на информацию о файловой системе, которая в Linux делится на три части:

  1. корень дерева каталогов и точка монтирования,
  2. альтернативный корень дерева каталогов и точка монтирования,
  3. текущий корень дерева каталогов и точка монтирования.

Эта структура включает в себя так же счетчик ссылок, поскольку возможно разделение файловой системы между клонами, при передаче флага CLONE_FS в вызов clone(2).

Поле p->files ссылается на таблицу файловых дескрипторов, которая так же может разделяться между задачами при передаче флага CLONE_FILES в вызов clone(2).

Поле p->sig содержит ссылку на обработчики сигналов и может разделяться между клонами, которые были созданы с флагом CLONE_SIGHAND.

2.2 Создание и завершение задач и потоков ядра.

В литературе можно встретить самые разные определения термина "процесс", начиная от "экземпляр исполняемой программы" и заканчивая "то, что является результатом работы системного вызова clone(2) или fork(2)". В Linux, существует три типа процессов:

  • фоновая задача(и),
  • потоки ядра,
  • пользовательские задачи.

Фоновая задача создается во время компиляции (at compile time) для первого CPU; и затем "вручную" размножается для каждого процессора вызовом fork_by_hand() из arch/i386/kernel/smpboot.c. Фоновая задача имеет общую структуру init_task, но для каждого процессора создается свой собственный TSS, в массиве init_tss. Все фоновые задачи имеют pid = 0 и никакой другой тип задач больше не может разделять pid, т.е. не могут клонироваться с флагом CLONE_PID через clone(2).

Потоки ядра порождаются с помощью функции kernel_thread(), которая делает системный вызов clone(2) в режиме ядра. Потоки ядра обычно не имеют пользовательского адресного пространства, т.е. p->mm = NULL, поэтому они явно вызывают exit_mm(), например через функцию daemonize(). Потоки ядра всегда имеют прямой доступ к адресному пространству ядра. Получают pid из нижнего диапазона. Работают в нулевом кольце защиты и, следовательно, имеют высший приоритет во всех операциях ввода/вывода и имеют преимущество перед планировщиком задач.

Пользовательские задачи создаются через системные вызовы clone(2) или fork(2). И тот и другой обращаются к kernel/fork.c:do_fork().

Давайте рассмотрим что же происходит, когда пользовательский процесс делает системный вызов fork(2). Хотя fork(2) и является аппаратно-зависимым из-за различий в организации стека и регистров, тем не менее основную часть действий выполняет функция do_fork(), которая является переносимой и размещена в kernel/fork.c.

При ветвлении процесса выполняются следующие действия:

  1. Локальной переменной retval присваивается значение -ENOMEM, которое возвращается в случае невозможности распределить память под новую структуру задачи
  2. Если установлен флаг CLONE_PID в параметре clone_flags, тогда возвращается код ошибки (-EPERM). Наличие этого флага допускается только если do_fork() была вызвана из фонового потока (idle thread), т.е. из задачи с pid == 0 (только в процессе загрузки). Таким образом, пользовательские потоки не должны передавать флаг CLONE_PID в clone(2), ибо этот номер все равно не "проскочит".
  3. Инициализируется current->vfork_sem (позднее будет очищен потомком). Он используется функцией sys_vfork() (системный вызов vfork(2), передает clone_flags = CLONE_VFORK|CLONE_VM|SIGCHLD) для того, чтобы "усыпить" родителя пока потомок не выполнит mm_release(), например , в результате исполнения exec() или exit(2).
  4. В памяти размещается новая структура с помощью макроса alloc_task_struct(). На x86 это производится с приоритетом GFP_KERNEL. Это главная причина, по которой системный вызов fork(2) может "заснуть". Если разместить структуру не удалось, то возвращается код ошибки -ENOMEM.
  5. Все поля структуры текущего процесса копируются во вновь созданную структуру посредством присваивания *p = *current. Может быть следует заменить на memset? Позднее, в поля, которые не наследуются потомком, будут записаны корректные значения.
  6. Для сохранения реентерабельности кода, выполняется big kernel lock.
  7. Если "родитель" является пользовательским ресурсом, то проверяется - не превышен ли предел RLIMIT_NPROC, если превышен - тогда возвращается код ошибки -EAGAIN, если нет - увеличивается счетчик процессов для заданного uid p->user->count.
  8. Если превышено системное ограничение на общее число задач - max_threads, возвращается код ошибки -EAGAIN.
  9. Если исполняемый формат программы принадлежит домену исполнения, поддерживаемому на уровне модуля, увеличивается счетчик ссылок соответствующего модуля.
  10. Если исполняемый формат программы принадлежит двоичному формату, поддерживаемому на уровне модуля, увеличивается счетчик ссылок соответствующего модуля.
  11. Потомок помечается как 'has not execed' (p->did_exec = 0)
  12. Потомок помечается как 'not-swappable' (p->swappable = 0)
  13. Потомок переводится в состояние TASK_UNINTERRUPTIBLE, т.е. p->state = TASK_UNINTERRUPTIBLE (TODO: зачем это делается? Я думаю, что в этом нет необходимости - следует избавиться от этого, Linus подтвердил мое мнение)
  14. Устанавливаются флаги потомка p->flags в соответствии с clone_flags; в случае простого fork(2), это будет p->flags = PF_FORKNOEXEC.
  15. Вызовом функции, kernel/fork.c:get_pid(), реализующей быстрый алгоритм поиска, находится pid потомка (p->pid) (TODO: блокировка (spinlock) lastpid_lock может быть опущена, так как get_pid() всегда выполняется под блокировкой ядра (big kernel lock) из do_fork(), так же можно удалить входной параметр flags для get_pid(), патч (patch) отправлен Алану (Alan) 20/06/2000).
  16. Далее инициализируется остальная часть структуры task_struct потомка. В самом конце структура хешируется в таблицу pidhash и потомок активируется (TODO: вызов wake_up_process(p) устанавливает p->state = TASK_RUNNING и добавляет процесс в очередь runqueue, поэтому, вероятно, нет нужды устанавливать p->state в состояние TASK_RUNNING ранее в do_fork()). Обратите внимание на установку p->exit_signal в значение clone_flags & CSIGNAL, которое для fork(2) может быть только SIGCHLD, и на установку p->pdeath_signal в 0. Сигнал pdeath_signal используется когда процесс лишается "родителя" (в случае его "смерти") и может быть получен/установлен посредством команд PR_GET/SET_PDEATHSIG системного вызова prctl(2)

Задача создана. Для завершения задачи имеется несколько способов.

  1. выполнить системный вызов exit(2);
  2. передать сигнал, приказывающий "умереть";
  3. вынужденная "смерть" в результате возникновения некоторых исключений;
  4. вызвать bdflush(2) с func == 1 (эта особенность Linux оставлена для сохранения совместимости со старыми дистрибутивами, которые имели строку 'update' в /etc/inittab - на сегодняшний день эта работа выполняется процессом ядра kupdate).

Имена функций, реализующих системные вызовы, в Linux начинаются с префикса sys_, но они, как правило, ограничиваются только проверкой аргументов или платформо-зависимой передачей информации, а фактически всю работу выполняют функции do_. Это касается и sys_exit(), которая вызываетdo_exit() для выполнения необходимых действий. Хотя, в других частях ядра иногда встречается вызов sys_exit (), на самом деле вызывается do_exit ().

Функция do_exit() размещена в kernel/exit.c. Некоторые примечания по поводу функции do_exit():

  • Устанавливает глобальную блокировку ядра (устанавливает, но не снимает).
  • Вызывает schedule(), которая уже не возвращает управление.
  • Переводит задачу в состояние TASK_ZOMBIE.
  • Передает всем потомкам current->pdeath_signal, если он не ноль.
  • Передает "родителю" current->exit_signal, который обычно равен SIGCHLD.
  • Освобождает ресурсы, захваченные при ветвлении, закрывает открытые файлы и т.д.

  • 2.3 Планировщик

    Работа планировщика заключается в разделении CPU между несколькими процессами. Реализация планировщика размещена в файле kernel/sched.c. Соответствующий заголовочный файл include/linux/sched.h подключается (прямо или косвенно) фактически к каждому файлу с исходным текстом ядра.

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

    • p->need_resched: это поле устанавливается если schedule() должна быть вызвана при 'первом удобном случае'.
    • p->counter: число тактов системных часов, оставшихся до окончания выделенного кванта времени, уменьшается по таймеру. Когда значение этого поля становится меньше либо равно нулю, то в него записывается ноль и взводится флаг p->need_resched. Иногда это поле называют "динамическим приоритетом" ('dynamic priority') процесса потому как он может меняться..
    • p->priority: статический приоритет процесса, может изменяться только через системные вызовы, такие как nice(2), POSIX.1b sched_setparam(2) или 4.4BSD/SVR4 setpriority(2).
    • p->rt_priority: приоритет реального времени (realtime priority)
    • p->policy: политика планирования, определяет класс планирования задачи. Класс планирования может быть изменен системным вызовом sched_setscheduler(2). Допустимые значения: SCHED_OTHER (традиционные процессы UNIX), SCHED_FIFO (процессы реального времени POSIX.1b FIFO) и SCHED_RR (процессы реального времени POSIX round-robin). Допускается комбинирование любого из этих значений с SCHED_YIELD по ИЛИ (OR) чтобы показать, что процесс решил уступить CPU, например при вызове sched_yield(2). Процесс реального времени FIFO будет работать до тех пор, пока не:
      a) запросит выполнение блоковой операции ввода/вывода,
      b) явно не отдаст CPU или
      c) будет вытеснен другим процессом реального времени с более высоким приоритетом (значение в p->rt_priority).
      SCHED_RR то же самое, что и SCHED_FIFO, за исключением того, что по истечении выделенного кванта времени, процесс помещается в конец очереди runqueue.

    Алгоритм планировщика достаточно прост, несмотря на очевидную сложность функции schedule(). Сложность функции объясняется реализацией трех алгоритмов планирования, а так же из-за учета особенностей SMP (мультипроцессорной обработки).

    Бесполезные, на первый взгляд, операторы goto в коде schedule() используются с целью генерации более оптимального (для i386) кода. Планировщик для ядра 2.4 (как и в более ранних версиях) был полностью переписан, поэтому дальнейшее обсуждение не относится к ядрам версии 2.2 и ниже.

    Разберем код функции подробнее:

    1. Если current->active_mm == NULL, то значит что-то не так. Любой процесс, даже поток ядра (для которого current->mm == NULL), всегда должен иметь p->active_mm.
    2. Если что либо планируется сделать с очередью tq_scheduler, то делать это надо здесь. Механизм очередей позволяет отложить выполнение отдельных функций на некоторое время. Этой теме будет уделено больше внимания несколько позднее.
    3. Локальным переменным prev и this_cpu присваиваются значения current (текущая задача) и CPU текущей задачи соответственно.
    4. Проверяется контекст вызова schedule(). Если функция вызвана из обработчика прерываний (по ошибке), то ядро "впадает в панику".
    5. Освобождается глобальная блокировка ядра.
    6. Если надлежить выполнить что-то, работающее через "мягкие" прерывания, то сделать это надо сейчас.
    7. Устанавливается указатель struct schedule_data *sched_data на область данных планирования для заданного CPU, которая содержит значение TSC для last_schedule и указатель на последнюю запланированную задачу (task_struct) (TODO: sched_data используется только для мультипроцессорных систем, зачем тогда init_idle() инициализирует ее и для однопроцессорной системы?).
    8. "Запирается" runqueue_lock. Обратите внимание на вызов spin_lock_irq(), который используется ввиду того, что в schedule() прерывания всегда разрешены. Поэтому, при "отпирании" runqueue_lock, достаточно будет вновь разрешить их, вместо сохранения/восстановления регистра флагов (вариант spin_lock_irqsave/restore).
    9. task state machine: если задача находится в состоянии TASK_RUNNING, то она остается в этом состоянии; если задача находится в состоянии TASK_INTERRUPTIBLE и для нее поступили сигналы, то она переводится в состояние TASK_RUNNING. В любом другом случае задача удаляется из очереди runqueue.
    10. Указатель next (лучший кандидат) устанавливается на фоновую задачу для данного CPU. Признак goodness для этого кандидата устанавливается в очень малое значение (-1000), в надежде на то, что найдется более лучший претендент.
    11. если задача prev (текущая) находится в состоянии TASK_RUNNING, то значение goodness принимает значение goodness задачи и она (задача) помечается как кандидат, лучший чем задача idle.
    12. Далее начинается проверка очереди runqueue, признак goodness каждого процесса сравнивается с текущим. Конкуренцию выигрывает процесс с более высоким goodness. Необходимо уточнить концепцию "может быть намечена на этом CPU": на однопроцессорной системе любой процесс из очереди runqueue может быть запланирован; на многопроцессорной системе, только тот, который не запущен на другом CPU, может быть запланирован для этого процессора. Признак goodness определяется функцией goodness(), которая для процессов реального времени возвращает их goodness очень высоким (1000 + p->rt_priority), значение больше 1000 гарантирует, что не найдется такого процесса SCHED_OTHER, который выиграл бы конкуренцию; таким образом конкуренция идет только между процессами реального времени, которую выигрывает процесс с более высоким p->rt_priority. Функция goodness() возвращает 0 для процессов, у которых истек выделенный квант времени (p->counter). Для процессов не реального времени значение goodness устанавливается равным p->counter - таким способом понижается вероятность захвата процессора задачей, которая уже получала его на некоторое время, т.е. интерактивные процессы получают преимущество перед продолжительными вычислительными процессами. Далее, реализуя принцип "cpu affinity", вес задачи, исполнявшейся на этом же процессоре, увеличивается на константу PROC_CHANGE_PENALTY, что дает небольшое преимущество перед другими процессами. Дополнительное преимущество придается и процессам, у которых mm указывает на текущий active_mm или не имееющим пользовательского адресного пространства, т.е. потокам ядра.
    13. если текущее значение goodness получается равным 0, то производится просмотр всего списка процессов (не только runqueue!) и производится перерасчет динамических приоритетов следуя простому алгоритму: 
      recalculate:
        {
                struct task_struct *p;
                spin_unlock_irq(&runqueue_lock);
                read_lock(&tasklist_lock);
                for_each_task(p)
                        p->counter = (p->counter >> 1) + p->priority;
                read_unlock(&tasklist_lock);
                spin_lock_irq(&runqueue_lock);
        }
      Следует отметить, что перед выполнением цикла перерасчета сбрасывается runqueue_lock, поскольку цикл может занять довольно продолжительное время, в течение которого schedule() может быть вызвана другим процессором, в результате чего может быть найдена задача с goodness достаточным для запуска на этом процессоре. По общему признанию это выглядит несколько непоследовательным, потому что в то время как один процессор отбирает задачи с наивысшим goodness, другой вынужден производить перерасчет динамических приоритетов.
    14. В этой точке next указывает на задачу, которая должна быть запланирована, далее в next->has_cpu заносится 1 и в next->processor заносится значение this_cpu. Блокировка runqueue_lock может быть снята.
    15. Если происходит возврат к предыдущей задаче (next == prev) то просто повторно устанавливается блокировка ядра и производится возврат, т.е. минуя аппаратный уровень (регистры, стек и т.п.) и настройки VM (переключение каталога страницы, пересчет active_mm и т.п.).
    16. Макрос switch_to() является платформо-зависимым. На i386 это имеет отношение к:
      a) обработке FPU (Floating Point Unit - арифметический сопроцессор)
      b) обработке LDT (Local Descriptor Table)
      c) установке сегментных регистров
      d) обработке TSS (Task State Segment) и
      e) установке регистров отладки.

    2.4 Реализация связанных списков в Linux

    Прежде чем приступить к знакомству с реализацией очередей ожидания, следует поближе рассмотреть реализацию двусвязных списков в ядре Linux. Очереди ожидания (так же как и все остальное в Linux) считаются тяжелыми в использовании и на жаргоне называются "list.h implementation" потому что наиболее используемый файл - include/linux/list.h.

    Основная структура данных здесь - это struct list_head:

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

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
        (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

    Первые три макроопределения предназначены для инициализации пустого списка с указателями next и prev, указывающими на сам список. Из синтаксических ограничений языка C явствует область использования каждого из них - например, LIST_HEAD_INIT()может быть использован для инициализирующих элементов структуры в объявлении, LIST_HEAD - может использоваться для инициализирующих объявлений статических переменных, а INIT_LIST_HEAD - может использоваться внутри функций.

    Макрос list_entry() предоставляет доступ к отдельным элементам списка, например (из fs/file_table.c:fs_may_remount_ro()):

    struct super_block {
   ...
   struct list_head s_files;
   ...
} *sb = &some_super_block;

struct file {
   ...
   struct list_head f_list;
   ...
} *file;

struct list_head *p;

for (p = sb->s_files.next; p != &sb->s_files; p = p->next) {
     struct file *file = list_entry(p, struct file, f_list);
     do something to 'file'
}

    Хороший пример использования макроса list_for_each() можно найти в коде планировщика, где производится просмотр очереди runqueue при поиске наивысшего goodness:

    static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;

list_for_each(tmp, &runqueue_head) {
    p = list_entry(tmp, struct task_struct, run_list);
    if (can_schedule(p)) {
        int weight = goodness(p, this_cpu, prev->active_mm);
        if (weight > c)
            c = weight, next = p;
    }
}

    Где поле p->run_list объявлено как struct list_head run_list внутри структуры task_struct и служит для связи со списком. Удаление элемента из списка и добавление к списку (в начало или в конец) выполняются макросами list_del()/list_add()/list_add_tail(). Пример, приведенный ниже, добавляет и удаляет задачу из очереди runqueue:

    static inline void del_from_runqueue(struct task_struct * p)
{
        nr_running--;
        list_del(&p->run_list);
        p->run_list.next = NULL;
}

static inline void add_to_runqueue(struct task_struct * p)
{
        list_add(&p->run_list, &runqueue_head);
        nr_running++;
}

static inline void move_last_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add_tail(&p->run_list, &runqueue_head);
}

static inline void move_first_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add(&p->run_list, &runqueue_head);
}

    2.5 Очереди ожидания (Wait Queues)

    Когда процесс передает ядру запрос, который не может быть исполнен сразу же, то процесс "погружается в сон" и "пробуждается", когда запрос может быть удовлетворен. Один из механизмов ядра для реализации подобного поведения называется "wait queue" (очередь ожидания).

    Реализация в Linux позволяет использовать семантику "индивидуального пробуждения" с помощью флага TASK_EXCLUSIVE. При использовании механизма waitqueues, можно использовать существующую очередь и просто вызывать sleep_on/sleep_on_timeout/interruptible_sleep_on/interruptible_sleep_on_timeout, либо можно определить свою очередь ожидания и использовать add/remove_wait_queue для добавления и удаления задач в/из нее и wake_up/wake_up_interruptible - для "пробуждения" их по мере необходимости

    Пример первого варианта использования очередей ожидания - это взаимодействие между менеджером страниц (page allocator) (в mm/page_alloc.c:__alloc_pages()) и демоном kswapd (в mm/vmscan.c:kswap()). Посредством очереди ожидания kswapd_wait,, объявленной в mm/vmscan.c; демон kswapd бездействует в этой очереди и "пробуждается" как только менеджеру страниц (page allocator) требуется освободить какие-либо страницы.

    Примером использования автономной очереди может служить взаимодействие между пользовательским процессом, запрашивающим данные через системный вызов read(2), и ядром, передающим данные, в контексте прерывания. Пример обработчика может выглядеть примерно так (упрощенный код из drivers/char/rtc_interrupt()):

    static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);

void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
        spin_lock(&rtc_lock);
        rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
        spin_unlock(&rtc_lock);
        wake_up_interruptible(&rtc_wait);
}

    Обработчик прерывания считывает данные с некоторого устройства (макрокоманда CMOS_READ()) и затем "будит" всех, кто находится в очереди ожидания rtc_wait.

    Системный вызов read(2) мог бы быть реализован так:

    ssize_t rtc_read(struct file file, char *buf, size_t count, loff_t *ppos)
{
        DECLARE_WAITQUEUE(wait, current);
        unsigned long data;
        ssize_t retval;

        add_wait_queue(&rtc_wait, &wait);
        current->state = TASK_INTERRUPTIBLE;
        do {
                spin_lock_irq(&rtc_lock);
                data = rtc_irq_data;
                rtc_irq_data = 0;
                spin_unlock_irq(&rtc_lock);

                if (data != 0)
                        break;

                if (file->f_flags & O_NONBLOCK) {
                        retval = -EAGAIN;
                        goto out;
                }
                if (signal_pending(current)) {
                        retval = -ERESTARTSYS;
                        goto out;
                }
                schedule();
        } while(1);
        retval = put_user(data, (unsigned long *)buf);
        if (!retval)
                retval = sizeof(unsigned long);

out:
        current->state = TASK_RUNNING;
        remove_wait_queue(&rtc_wait, &wait);
        return retval;
}

    Разберем функцию rtc_read():

    1. Объявляется новый элемент очереди ожидания указывающий на текщий процесс.
    2. Этот элемент добавляется в очередь rtc_wait.
    3. Текущий процесс переводится в состояние TASK_INTERRUPTIBLE которое предполагает, что процесс не должен учавствовать в процессе планирования.
    4. Проверяется - доступны ли данные. Если да - то цикл прерывается, данные копируются в пользовательский буфер, процесс переводится в состояние TASK_RUNNING, удаляется из очереди и производится возврат.
    5. Если данные недоступны, а пользователь запросил неблокирующую опрацию ввода-вывода, то возвращается код ошибки EAGAIN (который имеет тоже значение, что и EWOULDBLOCK)
    6. При наличии ожидающих обработки сигналов - "верхнему уровню" сообщается, что системный вызов должен быть перезапущен, если это необходимо. Под "если это необходимо" подразумеваются детали размещения сигнала, как это определено в системном вызове sigaction(2)
    7. Далее задача "отключается", т.е. "засыпает", до "пробуждения" обработчиком прерывания. Если не переводить процесс в состояние TASK_INTERRUPTIBLE то планировщик может вызвать задачу раньше, чем данные будут доступны, выполняя тем самым ненужную работу.

    Следует так же указать, что с помощью очередей ожидания реализация системного вызова poll(2) становится более простой.

    static unsigned int rtc_poll(struct file *file, poll_table *wait)
{
        unsigned long l;

        poll_wait(file, &rtc_wait, wait);

        spin_lock_irq(&rtc_lock);
        l = rtc_irq_data;
        spin_unlock_irq(&rtc_lock);

        if (l != 0)
                return POLLIN | POLLRDNORM;
        return 0;
}

    Вся работа выполняется независимой от типа устройства функцией poll_wait(), которая выполняет необходимые манипуляции; все что требуется сделать - это указать очередь,, которую следует "разбудить" обработчиком прерываний от устройства.

    2.6 Таймеры

    Теперь обратим наше внимание на таймеры ядра. Таймеры используются для передачи управления различным функциям (называющимся 'timer handler') в назначенное время. Основная структура данных - это struct timer_list объявленная в include/linux/timer.h:

    struct timer_list {
        struct list_head list;
        unsigned long expires;
        unsigned long data;
        void (*function)(unsigned long);
        volatile int running;
};

    Поле list служит для связи с внутренним списком, защищенным блокировкой (spinlock) timerlist_lock. Поле expires содержит значение времени (jiffies), оставшееся до вызова указанной function с входным параметром data. Поле running используется на SMP-системах для предотвращения запуска одного и того же обработчика на нескольких процессорах.

    Функции add_timer() и del_timer() добавляют и удаляют таймер в/из списка. По достижении заданного времени, таймер удаляется автоматически. Перед использованием таймер ДОЛЖЕН быть инициализирован вызовом функции init_timer(). А перед тем как добавить таймер в список должны быть установлены поля function и expires.

    2.7 Нижние половины (Bottom Halves)

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

    Bottom halves - это самый старый механизм отложенного исполнения задач ядра и был доступен еще в Linux 1.x.. В Linux 2.0 появился новый механизм - "очереди задач" ('task queues'), который будет рассмотрен ниже.

    Bottom halves упорядочиваются блокировкой (spinlock) global_bh_lock, т.е. только один bottom half может быть запущен на любом CPU за раз. Однако, если при попытке запустить обработчик, global_bh_lock оказывается недоступна, то bottom half планируется на исполнение планировщиком - таким образом обработка может быть продолжена вместо того, чтобы стоять в цикле ожидания на global_bh_lock.

    Всего может быть зарегистрировано только 32 bottom halves. Функции, необходимые для работы с ними перечислены ниже (все они экспортируются в модули):

    • void init_bh(int nr, void (*routine)(void)): устанавливает обработчик routine в слот nr. Слоты должны быть приведены в include/linux/interrupt.h в форме XXXX_BH, например TIMER_BH или TQUEUE_BH. Обычно подпрограмма инициализации подсистемы (init_module() для модулей) устанавливает необходимый обработчик (bottom half) с помощью этой функции.
    • void remove_bh(int nr): выполняет действия противоположные init_bh(), т.е. удаляет установленный обработчик (bottom half) из слота nr. Эта функция не производит проверок на наличие ошибок, так, например remove_bh(32) вызовет panic/oops. Обычно подпрограммы очистки подсистемы (cleanup_module() для модулей) используют эту функцию для освобождения слота, который может быть позднее занят другой подсистемой. (TODO: Не плохо бы иметь /proc/bottom_halves - перечень всех зарегистрированных bottom halves в системе? Разумеется, что global_bh_lock должна быть типа "read/write")
    • void mark_bh(int nr): намечает bottom half в слоте nr на исполнение. Как правило, обработчик прерывания намечает bottom half на исполнение в наиболее подходящее время.

    Bottom halves, по сути своей, являются глобальными "блокированными" тасклетами (tasklets), так, вопрос: "Когда исполняются обработчики bottom half ?", в действительности должен звучать как: "Когда исполняются тасклеты?". На этот вопрос имеется два ответа:
    а) при каждом вызове schedule()
    б) каждый раз, при исполнении кода возврата из прерываний/системных вызовов (interrupt/syscall return path) в entry.S.

    2.8 Очереди задач

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

    1. Фиксированное количество (32).
    2. Каждый bottom half может быть связан только с одним обработчиком.
    3. Bottom halves используются с захватом блокировки (spinlock) так что они не могут блокироваться.

    В очередь же, может быть вставлено произвольное количество задач. Создается новая очередь задач макросом DECLARE_TASK_QUEUE(), а задача добавляется функцией queue_task(). После чего, очередь может быть обработана вызовом run_task_queue(). Вместо того, чтобы создавать собственную очередь (и работать с ней "вручную"), можно использовать одну из предопределенных в Linux очередей:

    1. tq_timer: очередь таймера, запускается на каждом прерывании таймера и при освобождении устройства tty (закрытие или освобождение полуоткрытого терминального устройства). Так как таймер запускается в контексте прерывания, то и задачи из очереди tq_timer так же запускаются в контексте прерывания и следовательно не могут быть заблокированы.
    2. tq_scheduler: очередь обслуживается планировщиком (а так же при закрытии устройств tty, аналогично tq_timer). Так как планировщик работает в контексте процесса, то и задачи из tq_scheduler могут выполнять действия, характерные для этого контекста, т.е. блокировать, использовать данные контекста процесса (для чего бы это?) и пр.
    3. tq_immediate: в действительности представляет собой bottom half IMMEDIATE_BH, таким образом драйверы могут установить себя в очередь вызовом queue_task(task, &tq_immediate) и затем mark_bh(IMMEDIATE_BH) чтобы использоваться в контексте прерывания.
    4. tq_disk: используется при низкоуровневом доступе к блоковым учтройствам (и RAID). Эта очередь экспортируется в модули но должна использоваться только в исключительных ситуациях.

    Нет необходимости в драйвере вызывать run_tasks_queues(), если не используется своя собственная очередь задач, за исключением случаев, приведенных ниже.

    Драйвер, если помните, может запланировать задачи в очереди, но исполнение этих задач имеет смысл лишь до тех пор, пока экземпляр устройства остается верным - что обычно означает до тех пор, пока приложение не закрыло его. Поскольку очереди tq_timer/tq_scheduler используются не только в обычном месте (например они вызываются при закрытии tty устройств), то может возникнуть необходимость в вызове run_task_queue() из драйвера. для выталкивания задач из очереди, поскольку дальнейшее их исполнение не имеет смысла. По этой причине, иногда можно встретить вызов run_task_queue() для очередей tq_timer и tq_scheduler не только в обработчике прерываний от таймера и в schedule(), соответственно, но и в других местах.

    2.9 Tasklets

    Секция будет написана в одной из последующих версий документа.

    2.10 "Мягкие" IRQ

    Секция будет написана в одной из последующих версий документа..

    2.11 Как реализуются системные вызовы в архитектуре i386?

    В Linux существует два механизма реализации системных вызовов:

    • вентили lcall7/lcall27;
    • программное прерывание int 0x80.

    Чисто Линуксовые программы используют int 0x80, в то время как программы из других UNIX систем (Solaris, UnixWare 7 и пр.) используют механизм lcall7. Название lcall7 может ввести в заблуждение, поскольку это понятие включает в себя еще и lcall27 (например для Solaris/x86), но тем не менее, функция-обработчик называется lcall7_func.

    Во время начальной загрузки системы вызывается функция arch/i386/kernel/traps.c:trap_init(), которая настраивает IDT (Interrupt Descriptor Table) так, чтобы вектор 0x80 (of type 15, dpl 3) указывал на точку входа system_call из arch/i386/kernel/entry.S.

    Когда пользовательское приложение делает системный вызов, аргументы помещаются в регистры и приложение выполняет инструкцию int 0x80. В результате приложение переводится в привелигированный режим ядра и выполняется переход по адресу system_call в entry.S. Далее:

    1. Сохраняются регистры.
    2. В регистры %ds и %es заносится KERNEL_DS, так что теперь они ссылаются на адресное пространство ядра.
    3. Если значение %eax больше чем NR_syscalls (на сегодняшний день 256), то возвращается код ошибки ENOSYS.
    4. Если задача исполняется под трассировщиком (tsk->ptrace & PF_TRACESYS), то выполняется специальная обработка. Сделано это для поддержки программ типа strace (аналог SVR4 truss(1)) и отладчиков.
    5. Вызывается sys_call_table+4*(syscall_number из %eax). Эта таблица инициализируется в том же файле (arch/i386/kernel/entry.S) и содержит указатели на отдельные обработчики системных вызовов, имена которых, в Linux, начинаются с префикса sys_, например sys_open, sys_exit, и т.п.. Эти функции снимают со стека свои входные параметры, которые помещаются туда макросом SAVE_ALL.
    6. Вход в 'system call return path'. Это - отдельная метка, потому что этот код используется не только int 0x80 но и lcall7, lcall27. Это связано с обработкой тасклетов (tasklets) (включая bottom halves), проверяется необходимость вызова планировщика (tsk->need_resched != 0) и имеются ли ожидающие сигналы.

    Linux поддерживает до 6-ти входных аргументов в системных вызовах. Они передаются через регистры %ebx, %ecx, %edx, %esi, %edi (и %ebp для временного хранения, см. _syscall6() в asm-i386/unistd.h). Номер системного вызова передается в регистре %eax.

    2.12 Атомарные (неделимые) операции

    Имеется два типа атомарных операций: операции над битовыми полями и над переменными типа atomic_t. Битовые поля очень удобны, когда необходимо "устанавливать" или "сбрасывать" отдельные биты в больших коллекциях битов (битовых картах), в которых каждый бит идентифицируется некоторым порядковым номером, Они (битовые операции), так же, могут широко использоваться для выполнения простой блокировки, например для предоставлении исключительного доступа к открытому устройству. Пример можно найти в arch/i386/kernel/microcode.c:

    /*
 *  Bits in microcode_status. (31 bits of room for future expansion)
 */
#define MICROCODE_IS_OPEN       0       /* set if device is in use */

static unsigned long microcode_status;

    Очищать microcode_status нет необходимости, поскольку BSS обнуляется в Linux явно

    /*
 * We enforce only one user at a time here with open/close.
 */
static int microcode_open(struct inode *inode, struct file *file)
{
        if (!capable(CAP_SYS_RAWIO))
                return -EPERM;

        /* one at a time, please */
        if (test_and_set_bit(MICROCODE_IS_OPEN, &microcode_status))
                return -EBUSY;

        MOD_INC_USE_COUNT;
        return 0;
}

    Битовые операции:

    • void set_bit(int nr, volatile void *addr): устанавливает бит nr в карте, адресуемой параметром addr.
    • void clear_bit(int nr, volatile void *addr): сбрасывает бит nr в карте, адресуемой параметром addr.
    • void change_bit(int nr, volatile void *addr): изменяет состояние бита nr (если бит установлен, то он сбрасывается, если сброшен - устанавливается) в карте, адресуемой addr.
    • int test_and_set_bit(int nr, volatile void *addr): устанавливается бит nr и возвращается его предыдущее состояние.
    • int test_and_clear_bit(int nr, volatile void *addr): сбрасывается бит nr и возвращается его предыдущее состояние.
    • int test_and_change_bit(int nr, volatile void *addr): изменяется состояние бита nr и возвращается его предыдущее состояние.

    Эти операции используют макрос LOCK_PREFIX, который для SMP ядра представляет из себя префиксную инструкцию "lock" и пустой для UP ядра (include/asm/bitops.h). Он гарантирует неделимость доступа на мультипроцессорной платформе.

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

    • atomic_read(&v): возвращает значение atomic_t переменной v.
    • atomic_set(&v, i): записывает в atomic_t переменную v целое число i.
    • void atomic_add(int i, volatile atomic_t *v): складывает целое i и значение переменной v, результат помещается в переменную.
    • void atomic_sub(int i, volatile atomic_t *v): из переменной v вычитается целое i, результат помещается в переменную.
    • int atomic_sub_and_test(int i, volatile atomic_t *v): из переменной v вычитается целое i; возвращается 1 если новое значение переменной == 0, и 0 - в противном случае.
    • void atomic_inc(volatile atomic_t *v): увеличивает значение переменной на 1.
    • void atomic_dec(volatile atomic_t *v): уменьшает значение переменной на 1.
    • int atomic_dec_and_test(volatile atomic_t *v): уменьшает значение переменной на 1. Возвращает 1, если новое значение переменной == 0, 0 - в противном случае.
    • int atomic_inc_and_test(volatile atomic_t *v): увеличивает значение переменной на 1. Возвращает 1, если новое значение переменной == 0, 0 - в противном случае.
    • int atomic_add_negative(int i, volatile atomic_t *v): к переменной v прибавляется целое i, если результат меньше 0 - возвращается 1. Если результат больше либо равен 0 - возвращается 0. Эта операция используется в реализации семафоров.

    2.13 Блокировки (Spinlocks), Read-write блокировки и Big-Reader блокировки;

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

    Поддержка SMP была добавлена в Linux в версии 1.3.42 - 15 ноября 1995 (оригинальный патч был выпущен для 1.3.37 в октябре того же года).

    Если критическая секция кода, исполняется на однопроцессорной системе, либо в контексте процесса, либо в контексте прерывания, то установить защиту можно использованием пары инструкций cli/sti:

    unsigned long flags;

save_flags(flags);
cli();
/* критичный код */
restore_flags(flags);

    Вполне понятно, что такого рода защита, на SMP непригодна, поскольку критическая секция кода может исполняться одновременно и на другом процессоре, а cli() обеспечивает защиту на каждом процессоре индивидуально и конечно же не может воспрепятствовать исполнению кода на другом процессоре. В таких случаях и используются блокировки (spinlocks).

    Имеется три типа блокировок: vanilla (базовая), read-write и big-reader блокировки (spinlocks). Read-write блокировки должны использоваться в случае, когда имеется "много процессов - работающих только на чтение, и немного - на запись". Пример: доступ к списку зарегистрированных файловых систем (см. fs/super.c). Список защищен read-write блокировкой file_systems_lock, потому что исключительный доступ необходим только в случае регистрации/дерегистрации файловой системы, но любые процессы должны иметь возможность "читать" файл /proc/filesystems или делать системный вызов sysfs(2) для получения списка файловых систем. Такого рода ограничение вынуждает использовать read-write блокировки. Для случая read-write блокировки доступ "только для чтения" могут получить одновременно несколько процессов, в то время как доступ "на запись" - только один, при чем, чтобы получить доступ "на запись" не должно быть "читающих" процессов. Было бы прекрасно, если бы Linux мог корректно "обходить" проблему удовлетворения зароса "на запись", т.е. чтобы запросы "на чтение", поступившие после запроса "на запись", удовлетворялись бы только после того, как будет выполнена операция записи, избегая тем самым проблемы "подвешивания" "пишущего" процесса несколькими "читающими" процессами. Однако, на текущий момент пока не ясно - следует ли вносить изменения в логику работы, контраргумент - "считывающие" процессы запрашивают доступ к данным на очень короткое время, так должны ли они "подвисать", пока "записывающий" процесс ожидает получение доступа потенциально на более длительный период?

    Блокировка big-reader представляет собой разновидность блокировки read-write сильно оптимизированной для облегчения доступа "на чтение" в ущерб доступу "на запись". На текущий момент существует пока только две таких блокировки, первая из которых используется только на платформе sparc64 (global irq), и вторая - для сетевой поддержки (networking). В любом другом случае, когда логика доступа не вписывается ни в один из этих двух сценариев, следует использовать базовые блокировки. Процесс не может быть блокирован до тех пор, пока владеет какой либо блокировкой (spinlock).

    Блокировки могут быть трех подтипов: простые, _irq() и _bh().

    1. Простые spin_lock()/spin_unlock(): если известно, что в момент прохождения критической секции прерывания всегда запрещены или отсутствует конкуренция с контекстом прерывания (например с обработчиком прерывания), то можно использовать простые блокировки. Они не касаются состояния флага разрешения прерываний на текущем CPU.
    2. spin_lock_irq()/spin_unlock_irq(): если известно, что в момент прохождения критической секции прерывания всегда разрешены, то можно использовать эту версию блокировок, которая просто запрещает (при захвате) и разрешает (при освобождении) прерывания на текущем CPU. Например, rtc_read() использует spin_lock_irq(&rtc_lock) (внутри read() прерывания всегда разрешены) тогда как rtc_interrupt() использует spin_lock(&rtc_lock) (iвнутри обработчика прерывания всегда запрещены). Обратите внимание на то, что rtc_read() использует spin_lock_irq(), а не более универсальный вариант spin_lock_irqsave() поскольку на входе в системный вызов прерывания всегда разрешены.
    3. spin_lock_irqsave()/spin_unlock_irqrestore(): более строгая форма, используется, когда состояние флага прерываний неизвестно, но только если вопрос в прерываниях вообще. Не имеет никакого смысла, если обработчик прерываний не выполняет критический код.

    Не следует использовать простые spin_lock(), когда процесс конкурирует с обработчиком прерываний, потому что когда процесс выполняет spin_lock(), а затем происходит прерывание на этом же CPU, возникает ситуация "вечного ожидания": процесс, выполнивший spin_lock() будет прерван и не сможет продолжить работу, пока обработчик прерываний не вернет управление, а обработчик прерываний не сможет вернуть управление, поскольку будет стоять в ожидании снятия блокировки.

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

    spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

my_ioctl()
{
        spin_lock_irq(&my_lock);
        /* критическая секция */
        spin_unlock_irq(&my_lock);
}

my_irq_handler()
{
        spin_lock(&lock);
        /* критическая секция */
        spin_unlock(&lock);
}

    Следует обратить внимание на:

    1. Контекст процесса, представленный типичным методом (функцией) драйвера - ioctl() (входные параметры и возвращаемое значение опущены для простоты), должен использовать spin_lock_irq(), поскольку заранее известно, что при исполнении метода ioctl() прерывания всегда разрешены.
    2. Контекст прерываний, представленный my_irq_handler() может использовать простую форму spin_lock(), поскольку внутри обработчика прерывания всегда запрещены.

    2.14 Семафоры

    Иногда возникает необходимость в запрещении доступа к разделяемым данным, например, при копировании данных в пользовательское пространство. Для этих целей Linux предоставляет стандартные средства, называемые семафорами. Семафоры бывают двух типов: базовые и read-write семафоры. В зависимости от начального значения семафоры могут обеспечить либо взаимоисключающий (начальное значение 1), либо более сложный тип доступа.

    Read-write семафоры отличаются от базовых тем же самым, чем read-write блокировки отличаются от базовых блокировок: они разрешают множественный доступ "на чтение" одновременно нескольким процессам, но доступ "на запись" может получить только один процесс.

    Кроме того, семафоры могут быть прерываемыми - при использовании down/up_interruptible() вместо простых down()/up(). Если возвращаемое из down_interruptible() значение не ноль - то операция была прервана

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

    Простой пример использования семафоров можно найти в реализации системных вызовов gethostname(2)/sethostname(2) (kernel/sys.c).

    asmlinkage long sys_sethostname(char *name, int len)
{
        int errno;

        if (!capable(CAP_SYS_ADMIN))
                return -EPERM;
        if (len < 0 || len > __NEW_UTS_LEN)
                return -EINVAL;
        down_write(&uts_sem);
        errno = -EFAULT;
        if (!copy_from_user(system_utsname.nodename, name, len)) {
                system_utsname.nodename[len] = 0;
                errno = 0;
        }
        up_write(&uts_sem);
        return errno;
}

asmlinkage long sys_gethostname(char *name, int len)
{
        int i, errno;

        if (len < 0)
                return -EINVAL;
        down_read(&uts_sem);
        i = 1 + strlen(system_utsname.nodename);
        if (i > len)
                i = len;
        errno = 0;
        if (copy_to_user(name, system_utsname.nodename, i))
                errno = -EFAULT;
        up_read(&uts_sem);
        return errno;
}

    Комментарии к примеру:

    1. Блокировка может выполняться на время копирования в/из пространство пользователя в copy_from_user()/copy_to_user(). Поэтому здесь не используются какого либо рода блокировки.
    2. В системе возможно параллельное исполнение нескольких gethostname(2), для которых не требуется исключительного доступа, поэтому используется read-write семафор, а не базовый.

    Хотя реализация семафоров в Linux очень сложна, тем не менее возможны сценарии, которые еще не реализованы, например: нет концепции прерываемых read-write семафоров. Очевидно потому, что не встречалась реальная ситуация, которая требовала бы наличия таких экзотических свойств от семафоров.

    2.15 Поддержка загружаемых модулей

    Linux - это монолитная операционная система и не смотря на навязчивую рекламу "преимуществ", предлагаемых операционными системами, базирующимися на микроядре, тем не менее (цитирую Линуса Торвальдса (Linus Torvalds)):

    ... message passing as the fundamental operation of the OS is just an exercise in computer science masturbation. It may feel good, but you don't actually get anything DONE.

    Поэтому Linux есть и всегда будет монолитным, это означает, что все подсистемы работают в привелигированном режиме и используют общее адресное пространство; связь между ними выполняется через обычные C-функции.

    Однако, не смотря на то, что выделение функциональности ядра в отдельные "процессы" (как это делается в ОС на микро-ядре) - определенно не лучшее решение, тем не менее, в некоторых случаях, желательно наличие поддержки динамически загружаемых модулей (например: на машинах с небольшим объемом памяти или для ядер, которые автоматически подбирают (auto-probing) взаимоисключающие драйверы для ISA устройств). Поддержка загружаемых модулей устанавливается опцией CONFIG_MODULES во время сборки ядра. Поддержка автозагружаемых модулей через механизм request_module() определяется отдельной опцией (CONFIG_KMOD).

    Ниже приведены функциональные возможности, которые могут быть реализованы как загружаемые модули:

    1. Драйверы символьных и блочных устройств.
    2. Terminal line disciplines.
    3. Виртуальные (обычные) файлы в /proc и в devfs (например /dev/cpu/microcode и /dev/misc/microcode).
    4. Обработка двоичных форматов файлов (например ELF, a.out, и пр.).
    5. Обработка доменов исполнения (например Linux, UnixWare7, Solaris, и пр.).
    6. Файловые системы.
    7. System V IPC.

    А здесь то, что нельзя вынести в модули (вероятно потому, что это не имеет смысла):

    1. Алгоритмы планирования.
    2. Политики VM (VM policies).
    3. Кэш буфера, кэш страниц и другие кзши.

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

    1. caddr_t create_module(const char *name, size_t size): выделяется size байт памяти, с помощью vmalloc(), и отображает структуру модуля в ней. Затем новый модуль прицепляется к списку module_list. Этот системный вызов доступен только из процессов с CAP_SYS_MODULE, все остальные получат ошибку EPERM.
    2. long init_module(const char *name, struct module *image): загружается образ модуля и запускается подпрограмма инициализации модуля. Этот системный вызов доступен только из процессов с CAP_SYS_MODULE, все остальные получат ошибку EPERM.
    3. long delete_module(const char *name): предпринимает попытку выгрузить модуль. Если name == NULL, то выгружает все неиспользуемые модули.
    4. long query_module(const char *name, int which, void *buf, size_t bufsize, size_t *ret): возвращает информацию о модуле (или о модулях).

    Командный интерфейс, доступный пользователю:

    • insmod: вставляет одиночный модуль.
    • modprobe: вставляет модуль, включая все другие модули с соблюдением зависимостей.
    • rmmod: удаляет модуль.
    • modinfo: выводит информацию о модуле, например автор, описание, параметры принимаемые модулем и пр.

    Помимо загрузки модулей через insmod или modprobe, существует возможность загрузки модулей ядром автоматически, по мере необходимости. Интерфейс для этого, предоставляется функцией request_module(name), которая экспортируется в модули, чтобы предоставить им возможность загрузки других модулей. Функция request_module(name) создает поток ядра, который исполняет команду modprobe -s -k module_name, используя стандартный интерфейс ядра exec_usermodehelper() (так же экспортируется в модули). В случае успеха функция возвращает 0, но обычно возвращаемое значение не проверяется, вместо этого используется идиома прграммирования:

    if (check_some_feature() == NULL)
    request_module(module);
if (check_some_feature() == NULL)
    return -ENODEV;

    Например, код из fs/block_dev.c:get_blkfops(), который загружает модуль block-major-N при попытке открыть блочное устройство со старшим номером N. Очевидно, что нет такого модуля block-major-N (разработчики выбирают достаточно осмысленные имена для своих модулей), но эти имена отображаются в истинные названия модулей с помощью файла /etc/modules.conf. Однако, для наиболее известных старших номеров (и других типов модулей) команды modprobe/insmod "знают" какой реальный модуль нужно загрузить без необходимости явно указывать псевдоним в /etc/modules.conf.

    Неплохой пример загрузки модуля можно найти в системном вызове mount(2). Этот системный вызов принимает тип файловой системы в строке name, которую fs/super.c:do_mount() затем передает в fs/super.c:get_fs_type():

    static struct file_system_type *get_fs_type(const char *name)
{
        struct file_system_type *fs;

        read_lock(&file_systems_lock);
        fs = *(find_filesystem(name));
        if (fs && !try_inc_mod_count(fs->owner))
                fs = NULL;
        read_unlock(&file_systems_lock);
        if (!fs && (request_module(name) == 0)) {
                read_lock(&file_systems_lock);
                fs = *(find_filesystem(name));
                if (fs && !try_inc_mod_count(fs->owner))
                        fs = NULL;
                read_unlock(&file_systems_lock);
        }
        return fs;
}

    Комментарии к этой функции:

    1. В первую очередь предпринимается попытка найти файловую систему по заданному имени среди зарегистрированных. Выполняется эта проверка под защитой "только для чтения" file_systems_lock, (поскольку список зарегистрированных файловых систем не изменяется).
    2. Если файловая система найдена, то делается попытка получить новую ссылку и увеличить счетчик ссылок. Она всегда возвращает 1 для статически связанных файловых систем или для загруженных модулей. Если try_inc_mod_count() вернула 0, то это может рассматриваться как неудача, т.е, если модуль и имеется, то он был выгружен (удален).
    3. Освобождается file_systems_lock, потому что далее предполагается (request_module()) блокирующая операция и поэтому следует отпустить блокировку (spinlock). Фактически, в этом конкретном случае, отпустить блокировку file_systems_lock пришлось бы в любом случае, даже если бы request_module() не была блокирующей и загрузка модуля производилась бы в том же самом контексте. Дело в том, что далее, функция инициализации модуля вызовет register_filesystem(), которая попытается захватить ту же самую read-write блокировку file_systems_lock "на запись"
    4. Если попытка загрузить модуль удалась, то далее опять захватывается блокировка file_systems_lock и повторяется попытка найти файловую систему в списке зарегистрированных Обратите внимание - здесь в принципе возможна ошибка, в результате которой команда modprobe "вывалится" в coredump после удачной загрузки запрошенного модуля. Произойдет это в случае, когда вызов request_module() зарегистрирует новую файловую систему, но get_fs_type() не найдет ее.
    5. Если файловая система была найдена и удалось получить ссылку на нее, то она возвращается в качестве результата, в противном случае возвращается NULL.

    Когда модуль загружен, он может обратиться к любому символу (имени), которые экспортируются ядром, или другими в настоящее время загруженными модулями, как public, используя макрокоманду EXPORT_SYMBOL(). Если модуль использует символы другого модуля, то он помечается как в зависящий от того модуля во время пересчета зависимостей, при выполнении команды depmod -a на начальной загрузке (например после установки нового ядра).

    Обычно необходимо согласовывать набор модулей с версией интерфейсов ядра, используемых ими, в Linux это означает "версия ядра", так как не пока существует механизма определения версии интерфейса ядра вообще. Однако, имеется ограниченная возможность, называемыя "module versioning" или CONFIG_MODVERSIONS, которая позволяет избегать перекомпиляцию модулей при переходе к новому ядру. Что же происходит, если таблицы экспортируемых символов ядра для внутреннего доступа и для доступа из модуля имеют различия? Для элементов раздела public таблицы символов вычисляется 32-битная контрольная сумма C-объявлений. При загрузке модуля производится проверка полного соответствия символов, включая контрольные суммы. Загрузка модуля будет прервана если будут обнаружены отличия. Такая проверка производится только если и ядро и модуль собраны с включенной опцией CONFIG_MODVERSIONS. В противном случае загрузчик просто сравнивает версию ядра, объявленную в модуле, и экспортируемую ядром, и прерывает загрузку, модуля, если версии не совпадают.

    Вперед Назад Содержание