Внутреннее устройство Ядра Linux 2.4.

Linux-admin.net.ru / Работа с ядром Linux / Внутреннее устройство Ядра Linux 2.4.

Внутреннее устройство Ядра Linux 2.4.

Автор : Tigran Aivazian [email protected]

Перевод : Андрей Киселев [email protected]

1. Загрузка

1.1 Построение образа ядра Linux

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

Когда пользователь дает команду 'make zImage' или 'make bzImage', результат -- загрузочный образ ядра, записывается как arch/i386/boot/zImage или arch/i386/boot/bzImage соответственно. Вот что происходит в процессе сборки:

Исходные файлы на C и ассемблере компилируются в перемещаемый [relocatable] объектный код в формате ELF (файлы с расширением .o), при этом некоторые файлы, с помощью утилиты ar(1), дополнительно группируются в архивы (с раширением .a)
Созданные на предыдущем шаге, файлы .o и .a объединяются утилитой ld(1) в статически скомпонованный исполняемый файл vmlinux в 32-разрядном формате ELF 80386 с включенной символической информацией.
Далее, посредством nm vmlinux, создается файл System.map, при этом все не относящиеся к делу символы отбрасываются.
Переход в каталог arch/i386/boot.
Текст asm-файла bootsect.S перерабатывается с или без ключа -D__BIG_KERNEL__, в зависимости от конечной цели bzImage или zImage, в bbootsect.s или bootsect.s соответственно.
bbootsect.s ассемблируется и конвертируется в файл формата 'raw binary' с именем bbootsect (bootsect.s ассемблируется в файл bootsect в случае сборки zImage).
Содержимое установщика setup.S (setup.S подключает video.S) преобразуется в bsetup.s для bzImage (setup.s для zImage). Как и в случае с кодом bootsector, различия заключаются в использовании ключа -D__BIG_KERNEL__, при сборке bzImage. Результирующий файл конвертируется в формат 'raw binary' с именем bsetup.
Переход в каталог arch/i386/boot/compressed. Файл /usr/src/linux/vmlinux переводится в файл формата 'raw binary' с именем $tmppiggy и из него удаляются ELF-секции .note и .comment.
gzip -9 < $tmppiggy > $tmppiggy.gz
Связывание $tmppiggy.gz в перемещаемый ELF-формат (ld -r) piggy.o.
Компиляция процедур сжатия данных head.S и misc.c (файлы находятся в каталоге arch/i386/boot/compressed) в объектный ELF формат head.o и misc.o.
Объектные файлы head.o, misc.o и piggy.o объединяются в bvmlinux (или vmlinux при сборке zImage, не путайте этот файл с /usr/src/linux/vmlinux!). Обратите внимание на различие: -Ttext 0x1000, используется для vmlinux, а -Ttext 0x100000?-- для bvmlinux, т.е. bzImage загружается по более высоким адресам памяти.
Преобразование bvmlinux в файл формата 'raw binary' с именем bvmlinux.out, в процессе удаляются ELF секции .note и .comment.
Возврат в каталог arch/i386/boot и, с помощью программы tools/build, bbootsect, bsetup и compressed/bvmlinux.out объединяются в bzImage (справедливо и для zImage, только в именах файлов отсутствует начальный символ 'b'). В конец bootsector записываются такие важные переменные, как setup_sects и root_dev.

Размер загрузочного сектора (bootsector) всегда равен 512 байт. Размер установщика (setup) должен быть не менее чем 4 сектора, и ограничивается сверху размером около 12K - по правилу:

512 + setup_sects * 512 + место_для_стека_bootsector/setup <= 0x4000 байт

Откуда взялось это ограничение станет понятным дальше.

На сегодняшний день верхний предел размера bzImage составляет примерно 2.5M, в случае загрузки через LILO, и 0xFFFF параграфов (0xFFFF0 = 1048560 байт) для загрузки raw-образа, например с дискеты или CD-ROM (El-Torito emulation mode).

Следует помнить, что tools/build выполняет проверку размеров загрузочного сектора, образа ядра и нижней границы установщика (setup), но не проверяет *верхнюю* границу установщика (setup). Следовательно очень легко собрать "битое" ядро, добавив несколько больший размер ".space" в конец setup.S.

1.2 Загрузка: Обзор

Процесс загрузки во многом зависит от аппаратной платформы, поэтому основное внимание будет уделено платформе IBM PC/IA32. Для сохранения обратной совместимости, firmware-загрузчики загружают операционную систему устаревшим способом. Процесс этот можно разделить на несколько этапов:

BIOS выбирает загрузочное устройство.
BIOS загружает bootsector с загрузочного устройства.
Код bootsector-а загружает установщика, процедуры декомпрессии и сжатый образ ядра.
Ядро декомпрессируется в защищенном режиме (protected mode).
Выполняется низкоуровневый инициализирующий ассемблерный код.
Выполняется высокоуровневый инициализирующий C код.

1.3 Загрузка: BIOS POST

При включении питания запускается тактовый генератор и схема контроля питания устанавливает на шине сигнал #POWERGOOD.
На вывод CPU #RESET подается сигнал (после чего CPU переходит в реальный режим 8086).
%ds=%es=%fs=%gs=%ss=0, %cs=0xFFFF0000,%eip = 0x0000FFF0 (запуск кода Power On Self Test в ROM BIOS).
На время выполнения проверок, прерывания запрещены.
По адресу 0 инициализируется таблица векторов прерываний (IVT, Interrupts Vector Table).
По прерыванию 0x19 вызывается начальный (bootstrap) загрузчик BIOS, регистр %dl содержит 'номер загрузочного устройства'. В результате по физическому адресу 0x7C00 (0x07C0:0000) загружается содержимое первого сектора нулевой дорожки.

1.4 Загрузка: bootsector и setup

Для загрузки ядра Linux можно воспользоваться следующими загрузочными секторами:

Загрузочным сектором Linux из (arch/i386/boot/bootsect.S),
Загрузочный сектор LILO (или другого менеджера загрузки), или
обойтись без загрузочного сектора (loadlin и т.п.)

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

29 SETUPSECS = 4                /* число секторов установщика по умолчанию */
30 BOOTSEG   = 0x07C0           /* первоначальный адрес загрузочного сектора */
31 INITSEG   = DEF_INITSEG      /* сюда перемещается загрузчик - чтобы не мешал */
32 SETUPSEG  = DEF_SETUPSEG     /* здесь начинается установщик */
33 SYSSEG    = DEF_SYSSEG       /* система загружается по адресу 0x10000 (65536) */
34 SYSSIZE   = DEF_SYSSIZE      /* размер системы: в 16-байтных блоках */

(числа в начале - это номера строк в файле bootsect.S file) Значения DEF_INITSEG, DEF_SETUPSEG, DEF_SYSSEG и DEF_SYSSIZE берутся из файла include/asm/boot.h:

/* Ничего не меняйте, если не уверены в том, что делаете. */
#define DEF_INITSEG     0x9000
#define DEF_SYSSEG      0x1000
#define DEF_SETUPSEG    0x9020
#define DEF_SYSSIZE     0x7F00

Рассмотрим поближе код bootsect.S:

  54          movw    $BOOTSEG, %ax
    55          movw    %ax, %ds
    56          movw    $INITSEG, %ax
    57          movw    %ax, %es
    58          movw    $256, %cx
    59          subw    %si, %si
    60          subw    %di, %di
    61          cld
    62          rep
    63          movsw
    64          ljmp    $INITSEG, $go

    65  # bde - 0xff00 изменено на 0x4000 для работы отладчика с 0x6400 и выше (bde).
    66  # Если мы проверили верхние адреса, то об этом можно не беспокоиться. Кроме того,
    67  # мой BIOS можно сконфигурировать на загрузку таблицы дисков wini в верхнюю память
    68  # вместо таблицы векторов.  Старый стек может "помесить"
    69  # таблицу устройств [drive table].

    70  go:     movw    $0x4000-12, %di         # 0x4000 - произвольное значение >=
    71                                          # длины bootsect + длины
    72                                          # setup + место для стека;
    73                                          # 12 - размер параметров диска.
    74          movw    %ax, %ds                # INITSEG уже в ax и es
    75          movw    %ax, %ss
    76          movw    %di, %sp                # разместим стек по INITSEG:0x4000-12.

Строки 54-63 перемещают код начального загрузчика из адреса 0x7C00 в адрес 0x90000. Для этого:

в регистровую пару %ds:%si заносится значение $BOOTSEG:0 (0x7C0:0 = 0x7C00)
в регистровую пару %es:%di заносится значение $INITSEG:0 (0x9000:0 = 0x90000)
в регистр %cx записывается число 16-битовых слов (256 слов = 512 байт = 1 сектор)
В регистре флагов EFLAGS сбрасывается флаг направления DF (Direction Flag) (копирование с автоинкрементом адресных регистров) (cld)
копируется 512 байт (rep movsw)

Здесь умышленно не используется инструкция rep movsd (обратите внимание на директиву - .code16).

В строке 64 выполняется переход на метку go:, в только что созданную копию загрузчика, т.е. в сегмент 0x9000. Эта, и следующие три инструкции (строки 64-76) переустанавливают регистр сегмента стека и регистр указателя стека на $INITSEG:0x4000-0xC, т.е. %ss = $INITSEG (0x9000) и %sp = 0x3FF4 (0x4000-0xC). Это и есть то самое ограничение на размер setup, которое упоминалось ранее (см. Построение образа ядра Linux).

Для того, чтобы разрешить считывание сразу нескольких секторов (multi-sector reads), в строках 77-103 исправляются некоторые значения в таблице параметров для первого диска :

  77   # Часто в BIOS по умолчанию в таблицы параметров диска не признают
    78  # чтение по несколько секторов кроме максимального числа, указанного
    79  # по умолчанию в таблице параметров дискеты - что может иногда равняться
    80  # 7 секторам.
    81  #
    82  # Поскольку чтение по одному сектору отпадает (слишком медленно),
    83  # необходимо позаботиться о создании в ОЗУ новой таблицы параметров
    84  # (для первого диска).  Мы установим максимальное число секторов
    85  # равным 36 - максимум, с которым мы столкнемся на ED 2.88.
    86  #
    87  # Много - не мало.  А мало - плохо.
    88  #
    89  # Сегменты устанавливаются так: ds = es = ss = cs - INITSEG, fs = 0,
    90  # а gs не используется.


    91          movw    %cx, %fs                # запись 0 в fs
    92          movw    $0x78, %bx              # в fs:bx адрес таблицы
    93          pushw   %ds
    94          ldsw    %fs:(%bx), %si          # из адреса ds:si
    95          movb    $6, %cl                 # копируется 12 байт
    96          pushw   %di                     # di = 0x4000-12.
    97          rep                             # инструкция cld не нужна - выполнена в строке 66
    98          movsw
    99          popw    %di
   100          popw    %ds
   101          movb    $36, 0x4(%di)           # записывается число секторов
   102          movw    %di, %fs:(%bx)
   103          movw    %es, %fs:2(%bx)

Контроллер НГМД переводится в исходное состояние функцией 0 прерывания 0x13 в BIOS (reset FDC) и секторы установщика загружаются непосредственно после загрузчика, т.е. в физические адреса, начиная с 0x90200 ($INITSEG:0x200), с помощью функции 2 прерывания 0x13 BIOS (read sector(s)). Смотри строки 107-124:

 107  load_setup:
   108          xorb    %ah, %ah                # переинициализация FDC
   109          xorb    %dl, %dl
   110          int     $0x13
   111          xorw    %dx, %dx                # диск 0, головка 0
   112          movb    $0x02, %cl              # сектор 2, дорожка 0
   113          movw    $0x0200, %bx            # адрес в INITSEG = 512
   114          movb    $0x02, %ah              # функция 2, "read sector(s)"
   115          movb    setup_sects, %al        # (все под головкой 0, на дорожке 0)
   116          int     $0x13                   # читать
   117          jnc     ok_load_setup           # получилось - продолжить

   118          pushw   %ax                     # запись кода ошибки
   119          call    print_nl
   120          movw    %sp, %bp
   121          call    print_hex
   122          popw    %ax
   123          jmp     load_setup

   124  ok_load_setup:

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

Если загрузка setup_sects секторов кода установщика прошла благополучно, то производится переход на метку ok_load_setup:.

Далее производится загрузка сжатого образа ядра в физические адреса начиная с 0x10000, чтобы не затереть firmware-данные в нижних адресах памяти (0-64K). После загрузки ядра управление передается в точку $SETUPSEG:0 (arch/i386/boot/setup.S). Поскольку обращений к BIOS больше не будет, данные в нижней памяти уже не нужны, поэтому образ ядра перемещается из 0x10000 в 0x1000 (физические адреса, конечно). И наконец, установщик setup.S завершает свою работу, переводя процессор в защищенный режим и передает управление по адресу 0x1000 где находится точка входа в сжатое ядро, т.е. arch/386/boot/compressed/{head.S,misc.c}. Здесь производится установка стека и вызывается decompress_kernel(), которая декомпрессирует ядро в адреса, начиная с 0x100000, после чего управление передается туда.

Следует отметить, что старые загрузчики (старые версии LILO) в состоянии загружать только первые 4 сектора установщика (setup), это объясняет присутствие кода, "догружающего" остальные сектора в случае необходимости. Кроме того, установщик содержит код, обрабатывающий различные комбинации типов/версий загрузчиков и zImage/bzImage.

Теперь рассмотрим хитрость, позволяющую загрузчику выполнить загрузку "больших" ядер, известных под именем "bzImage". Установщик загружается как обычно, в адреса с 0x90200, а ядро, с помощью специальной вспомогательной процедуры, вызывающей BIOS для перемещения данных из нижней памяти в верхнюю, загружается кусками по 64К. Эта процедура определена в setup.S как bootsect_helper, а вызывается она из bootsect.S как bootsect_kludge. Метка bootsect_kludge, определенная в setup.S, содержит значение сегмента установщика и смещение bootsect_helper в нем же, так что для передачи управления загрузчик должен использовать инструкцию lcall (межсегментный вызов). Почему эта процедура помещена в setup.S? Причина банальна - в bootsect.S просто больше нет места (строго говоря это не совсем так, поскольку в bootsect.S свободно примерно 4 байта и по меньшей мере еще 1 байт, но вполне очевидно, что этого недостаточно) Эта процедура использует функцию прерывания BIOS 0x15 (ax=0x8700) для перемещения в верхнюю память и переустанавливает %es так, что он всегда указывает на 0x10000. Это гарантирует, что bootsect.S не исчерпает нижнюю память при считывании данных с диска.

1.5 LILO в качестве загрузчика.

Специализированные загрузчики (например LILO) имеют ряд преимуществ перед чисто Linux-овым загрузчиком (bootsector):

Возможность выбора загрузки одного из нескольких ядер Linux или одной из нескольких ОС.
Возможность передачи параметров загрузки в ядро (существует патч BCP который добавляет такую же возможность и к чистому bootsector+setup).
Возможность загружать большие ядра (bzImage) - до 2.5M (против обычного 1M).

Старые версии LILO ( версии 17 и более ранние) не в состоянии загрузить ядро bzImage. Более новые версии (не старше 2-3 лет) используют ту же методику, что и bootsect+setup, для перемещения данных из нижней в верхнюю память посредством функций BIOS. Отдельные разработчики (особенно Peter Anvin) выступают за отказ от поддержки ядер zImage. Тем не менее, поддержка zImage остается в основном из-за (согласно Alan Cox) существования некоторых BIOS-ов, которые не могут грузить ядра bzImage, в то время как zImage грузятся ими без проблем.

В заключение, LILO передает управление в setup.S и далее загрузка продолжается как обычно.

1.6 Высокоуровневая инициализация

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

Устанавливаются сегментные регистры (%ds = %es = %fs = %gs = __KERNEL_DS = 0x18).
Инициализируются таблицы страниц.
Разрешается листание страниц, установкой бита PG в %cr0.
Обнуляется BSS (для SMP (мультипроцессорных систем (прим. перев.)), это действие выполняет только первый CPU).
Копируются первые 2k bootup параметров (kernel commandline).
Проверяется тип CPU, используя EFLAGS и, если возможно, cpuid, позволяющие обнаружить процессор 386 и выше.
Первый CPU вызывает start_kernel(), все остальные - arch/i386/kernel/smpboot.c:initialize_secondary(), если переменная ready=1, которая только переустанавливает esp/eip.

Функция init/main.c:start_kernel() написана на C и выполняет следующие действия:

Выполняется глобальная блокировка (необходимая для того, чтобы через процесс инициализации проходил только один CPU)
Выполняются платформо-зависимые настройки (анализируется раскладка памяти, копируется командная строка и пр.).
Вывод "баннера" ядра, который содержит версию, компилятор, использованные при сборке, и пр., в кольцевой буфер для сообщений. Текст "баннера" задается в переменной linux_banner, определенной в init/version.c. Текст этот можно вывести на экран командой cat /proc/version.
Инициализация ловушек.
Инициализация аппаратных прерываний (irqs).
Инициализация данных для планировщика.
Инициализация данных хранения времени.
Инициализация подсистемы программных прерываний (softirq).
Разбор параметров командной строки.
Инициализация консоли.
Если ядро было скомпилировано с поддержкой загружаемых модулей, инициализируется подсистема динамической загрузки модулей.
Инициализируются профилирующие буферы, если командная строка содержит указание "profile=".
kmem_cache_init(), начало инициализации менеджера памяти.
Разрешаются прерывания.
Подсчет значения BogoMips для данного CPU.
Вызывается mem_init() которая подсчитывает max_mapnr, totalram_pages и high_memory и выводит строку "Memory: ...".
kmem_cache_sizes_init(), завершение инициализации менеджера памяти.
Инициализация структур данных для procfs.
fork_init(), создает uid_cache, инициализируется max_threads исходя из объема доступной памяти и конфигурируется RLIMIT_NPROC для init_task как max_threads/2.
Создаются различные кэши для VFS, VM, кэш буфера и пр..
Инициализируется подсистема IPC, если имеется поддержка System V IPC. Обратите внимание, что для System V shm, это включает монтирование внутреннего (in-kernel) экземпляра файловой системы shmfs.
Создается и инициализируется специальный кэш, если поддержка квот (quota) включена.
Выполняется платформо-зависимая "проверка ошибок" ("check for bugs") и, если это возможно, активируется обработка ошибок процессора/шины/проч. Сравнение различных архитектур показывает, что "ia64 не имеет ошибок" а "ia32 имеет несколько дефектов", хороший пример - "дефект f00f" который проверен только для ядра, собранного под процессор ниже, чем 686.
Устанавливается флаг, указывающий на то, что планировщик должен быть вызван "при первой возможности" и создается поток ядра init(), который выполняет execute_command, если она имеется среди параметров командной строки в виде "init=", или пытается запустить /sbin/init, /etc/init, /bin/init, /bin/sh в указанном порядке; если не удается ни один из запусков то ядро "впадает в панику" с "предложением" задать параметр "init=".
Переход в фоновый поток с pid=0.

Здесь важно обратить внимание на то, что задача init() вызывает функцию do_basic_setup(), которая в свою очередь вызывает do_initcalls() для поочередного (в цикле) вызова функций, зарегистрированных макросом __initcall или module_init() Эти функции либо являются независимыми друг от друга, либо их взаимозависимость должна быть учтена при задании порядка связывания в Makefile - ах. Это означает, что порядок вызова функций инициализации зависит от положения каталогов в дереве и структуры Makefile - ов. Иногда порядок вызова функций инициализации очень важен. Представим себе две подсистемы: А и Б, причем Б существенным образом зависит от того как была проинициализирована подсистема А. Если А скомпилирована как статическая часть ядра, а Б как подгружаемый модуль, то вызов функции инициализации подсистемы Б будет гарантированно произведен после инициализации подсистемы А. Если А - модуль, то и Б так же должна быть модулем, тогда проблем не будет. Но что произойдет, если и А, и Б скомпилировать с ядром статически? Порядок, в котором они будут вызываться (иницализироваться) зависит от смещения относительно точки .initcall.init ELF секции в образе ядра (грубо говоря - от порядка вызова макроса __initcall или module_init() прим. перев.). Rogier Wolff предложил ввести понятие "приоритетной" инфраструктуры, посредством которой модули могли бы задавать компоновщику порядок связывания, но пока отсутствуют заплаты, которые реализовали бы это качество достаточно изящным способом, чтобы быть включенным в ядро. А посему необходимо следить за порядком компоновки. Если А и Б (см. пример выше) скомпилированы статически и работают корректно, то и при каждой последующей пересборке ядра они будут работать, если порядок следования их в Makefile не изменяется. Если же они не функционируют, то стоит изменить порядок следования объектных файлов.

Еще одна замечательная особенность Linux - это возможность запуска "альтернативной программы инициализации", если ядру передается командная строка "init=". Эта особенность может применяться для перекрытия /sbin/init или для отладки скриптов инициализации (rc) и /etc/inittab вручную, запуская их по одному за раз

1.7 SMP Загрузка на x86

В случае SMP (многопроцессорной системы), первичный процессор проходит обычную последовательность - bootsector, setup и т.д., пока не встретится вызов функции start_kernel(), в которой стоит вызов функции smp_init(), откуда вызывается arch/i386/kernel/smpboot.c:smp_boot_cpus(). Функция smp_boot_cpus() в цикле (от 0 до NR_CPUS) вызывает do_boot_cpu() для каждого apicid. Функция do_boot_cpu() создает (т.е. fork_by_hand) фоновую задачу для указанного CPU и записывает, согласно спецификации Intel MP (в 0x467/0x469) трамплин-код, содержащийся в trampoline.S. Затем генерирует STARTUP IPI, заставляя вторичный процессор выполнить код из trampoline.S.

Ведущий процессор создает трамплин-код для каждого процессора в нижней памяти. Ведомый процессор, при исполнении "трамплина", записывает "магическое число", чтобы известить ведущий процессор, что код исполнен. Требование, по размещению трамплин-кода в нижней памяти, обусловлено спецификацией Intel MP.

Трамплин-код просто записывает 1 в %bx, переводит процессор в защищенный режим и передает управление на метку startup_32, которая является точкой входа в arch/i386/kernel/head.S.

При исполнении кода head.S, ведомый CPU обнаруживает, что он не является ведущим, перепрыгивает через очистку BSS и входит в initialize_secondary() которая переходит в фоновую задачу для данного CPU - минуя вызов init_tasks[cpu], поскольку она уже была проинициирована ведущим процессором при исполнении do_boot_cpu(cpu).

Характерно, что код init_task может использоваться совместно, но каждая фоновая задача должна иметь свой собственный TSS. Именно поэтому init_tss[NR_CPUS] является массивом.

1.8 Освобождение памяти после инициализации

После выполнения инициализации операционной системы, значительная часть кода и данных становится ненужной. Некоторые системы (BSD, FreeBSD и пр.) не освобождают память, занятую этой ненужной информацией. В оправдание этому приводится (см. книгу McKusick-а по 4.4BSD): "данный код располагается среди других подсистем и поэтому нет никакой возможности избавиться от него". В Linux, конечно же такое оправдание невозможно, потому что в Linux "если что-то возможно в принципе, то это либо уже реализовано, либо над этим кто-то работает".

Как уже упоминалось ранее, ядро Linux может быть собрано только в двоичном формате ELF. Причиной тому (точнее одна из причин) - отделение инициализирующего кода/данных, для создания которых Linux предоставляет два макроса:

__init - для кода инициализации
__initdata - для данных

Макросы подсчитывают размер этих секций в спецификаторах аттрибутов gcc, и определены в include/linux/init.h:

#ifndef MODULE
#define __init        __attribute__ ((__section__ (".text.init")))
#define __initdata    __attribute__ ((__section__ (".data.init")))
#else
#define __init
#define __initdata
#endif

Что означает - если код скомпилирован статически (т.е. литерал MODULE не определен), то он размещается в ELF-секции .text.init, которая объявлена в карте компоновки arch/i386/vmlinux.lds. В противном случае (т.е. когда компилируется модуль) макрос ничего не делает.

Таким образом, в процессе загрузки, поток ядра "init" (функция init/main.c:init()) вызывает функцию free_initmem(), которая и освобождает все страницы памяти между адресами __init_begin и __init_end.

На типичной системе (на моей рабочей станции) это дает примерно 260K памяти.

Код, регистрирующийся через module_init(), размещается в секции .initcall.init, которая так же освобождается. Текущая тенденция в Linux - при проектировании подсистем (не обязательно модулей) закладывать точки входа/выхода на самых ранних стадиях с тем, чтобы в будущем, рассматриваемая подсистема, могла быть модулем. Например: pipefs, см. fs/pipe.c. Даже если подсистема никогда не будет модулем напрмер bdflush (см. fs/buffer.c), все равно считается хорошим тоном использовать макрос module_init() вместо прямого вызова функции инициализации, при условии, что не имеет значения когда эта функция будет вызвана.

Имеются еще две макрокоманды, работающие подобным образом. Называются они __exit и __exitdata, но они более тесно связаны с поддержкой модулей, и поэтому будет описаны ниже.

1.9 Разбор командной строки

Давайте посмотрим как выполняется разбор командной строки, передаваемой ядру на этапе загрузки:

LILO (или BCP) воспринимает командную строку через сервис клавиатуры BIOS-а, и размещает ее в физической памяти.
Код arch/i386/kernel/head.S копирует первые 2k в нулевую страницу (zeropage). Примечательно, что текущая версия LILO (21) ограничивает размер командной строки 79-ю символами. Это не просто ошибка в LILO (в случае включенной поддержки EBDA(LARGE_EBDA (Extended BIOS Data Area) --необходима для некоторых современных мультипроцессорных систем. Заставляет LILO загружаться в нижние адреса памяти, с целью оставить как можно больше пространства для EBDA, но ограничивает максимальный размер для "малых" ядер - т.е. "Image" и "zImage" прим. перев. )). Werner пообещал убрать это ограничение в ближайшее время. Если действительно необходимо передать ядру командную строку длиной более 79 символов, то можно использовать в качестве загрузчика BCP или подправить размер командной строки в функции arch/i386/kernel/setup.c:parse_mem_cmdline().
arch/i386/kernel/setup.c:parse_mem_cmdline() (вызывается из setup_arch(), которая в свою очередь вызывается из start_kernel()), копирует 256 байт из нулевой страницы в saved_command_line, которая отображается в /proc/cmdline. Эта же функция обрабатывает опцию "mem=", если она присутствует в командной строке, и выполняет соответствующие корректировки параметра VM.
далее, командная строка передается в parse_options() (вызывается из start_kernel()), где обрабатываются некоторые "in-kernel" параметры (в настоящее время "init=" и параметры для init) и каждый параметр передается в checksetup().
checksetup() проходит через код в ELF-секции .setup.init и вызывает каждую функцию, передавая ей полученное слово. Обратите внимание, что если функция, зарегистрированная через __setup(), возвращает 0, то становится возможной передача одного и того же "variable=value" нескольким функциям. Одни из них воспринимают параметр как ошибочный, другие -как правильный. Jeff Garzik говорит по этом у поводу: "hackers who do that get spanked :)" (не уверен в точности перевода, но тем не менее "программисты, работающие с ядром, иногда получают щелчок по носу". прим. перев.). Почему? Все зависит от порядка компоновки ядра, т.е. в одном случае functionA вызывается перед functionB, порядок может быть изменен с точностью до наоборот, результат зависит от порядка следования вызовов.

Для написания кода, обрабатывающего командную строку, следует использовать макрос __setup(), определенный в include/linux/init.h:

/*
 * Used for kernel command line parameter setup
 */
struct kernel_param {
        const char *str;
        int (*setup_func)(char *);
};

extern struct kernel_param __setup_start, __setup_end;

#ifndef MODULE
#define __setup(str, fn) \
   static char __setup_str_##fn[] __initdata = str; \
   static struct kernel_param __setup_##fn __initsetup = \
   { __setup_str_##fn, fn }

#else
#define __setup(str,func) /* nothing */
endif

Ниже приводится типичный пример, при написании собственного кода (пример взят из реального кода драйвера BusLogic HBA drivers/scsi/BusLogic.c):

static int __init
BusLogic_Setup(char *str)
{
        int ints[3];

        (void)get_options(str, ARRAY_SIZE(ints), ints);

        if (ints[0] != 0) {
                BusLogic_Error("BusLogic: Obsolete Command Line Entry "
                                "Format Ignored\n", NULL);
                return 0;
        }
        if (str == NULL || *str == '\0')
                return 0;
        return BusLogic_ParseDriverOptions(str);
}

__setup("BusLogic=", BusLogic_Setup);

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

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, которые взаимосвязаны двумя способами.

как хеш-массив, хешированный по pid, и
как кольцевой двусвязный список, в котором элементы ссылаются друг на друга посредством указателей 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 означает, что это поле может изменяться асинхронно (в обработчиках прерываний):

TASK_RUNNING: указывает на то, что задача "вероятно" находится в очереди запущенных задач (runqueue). Причина, по которой задача может быть помечена как TASK_RUNNING, но не помещена в runqueue в том, что пометить задачу и вставить в очередь - не одно и то же. Если заполучить блокировку runqueue_lock на чтение-запись и просмотреть runqueue, то можно увидеть, что все задачи в очереди имеют состояние TASK_RUNNING. Таким образом, утверждение "Все задачи в runqueue имеют состояние TASK_RUNNING" не означает истинность обратного утверждения. Аналогично, драйверы могут отмечать себя (или контекст процесса, под которым они запущены) как TASK_INTERRUPTIBLE (или TASK_UNINTERRUPTIBLE) и затем производить вызов schedule(), который удалит их из runqueue (исключая случай ожидания сигнала, тогда процесс остается в runqueue).
TASK_INTERRUPTIBLE: задача в состоянии "сна", но может быть "разбужена" по сигналу или по истечении таймера.
TASK_UNINTERRUPTIBLE: подобно TASK_INTERRUPTIBLE, только задача не может быть "разбужена".
TASK_ZOMBIE: задача, завершившая работу, до того как родительский процесс ("естественный" или "приемный") произвел системный вызов wait(2).
TASK_STOPPED: задача остановлена, либо по управляющему сигналу, либо в результате вызова ptrace(2).
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 делится на три части:

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

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

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

Локальной переменной retval присваивается значение -ENOMEM, которое возвращается в случае невозможности распределить память под новую структуру задачи
Если установлен флаг CLONE_PID в параметре clone_flags, тогда возвращается код ошибки (-EPERM). Наличие этого флага допускается только если do_fork() была вызвана из фонового потока (idle thread), т.е. из задачи с pid == 0 (только в процессе загрузки). Таким образом, пользовательские потоки не должны передавать флаг CLONE_PID в clone(2), ибо этот номер все равно не "проскочит".
Инициализируется current->vfork_sem (позднее будет очищен потомком). Он используется функцией sys_vfork() (системный вызов vfork(2), передает clone_flags = CLONE_VFORK|CLONE_VM|SIGCHLD) для того, чтобы "усыпить" родителя пока потомок не выполнит mm_release(), например , в результате исполнения exec() или exit(2).
В памяти размещается новая структура с помощью макроса alloc_task_struct(). На x86 это производится с приоритетом GFP_KERNEL. Это главная причина, по которой системный вызов fork(2) может "заснуть". Если разместить структуру не удалось, то возвращается код ошибки -ENOMEM.
Все поля структуры текущего процесса копируются во вновь созданную структуру посредством присваивания *p = *current. Может быть следует заменить на memset? Позднее, в поля, которые не наследуются потомком, будут записаны корректные значения.
Для сохранения реентерабельности кода, выполняется big kernel lock.
Если "родитель" является пользовательским ресурсом, то проверяется - не превышен ли предел RLIMIT_NPROC, если превышен - тогда возвращается код ошибки -EAGAIN, если нет - увеличивается счетчик процессов для заданного uid p->user->count.
Если превышено системное ограничение на общее число задач - max_threads, возвращается код ошибки -EAGAIN.
Если исполняемый формат программы принадлежит домену исполнения, поддерживаемому на уровне модуля, увеличивается счетчик ссылок соответствующего модуля.
Если исполняемый формат программы принадлежит двоичному формату, поддерживаемому на уровне модуля, увеличивается счетчик ссылок соответствующего модуля.
Потомок помечается как 'has not execed' (p->did_exec = 0)
Потомок помечается как 'not-swappable' (p->swappable = 0)
Потомок переводится в состояние TASK_UNINTERRUPTIBLE, т.е. p->state = TASK_UNINTERRUPTIBLE (TODO: зачем это делается? Я думаю, что в этом нет необходимости - следует избавиться от этого, Linus подтвердил мое мнение)
Устанавливаются флаги потомка p->flags в соответствии с clone_flags; в случае простого fork(2), это будет p->flags = PF_FORKNOEXEC.
Вызовом функции, 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).
Далее инициализируется остальная часть структуры 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)

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

выполнить системный вызов exit(2);
передать сигнал, приказывающий "умереть";
вынужденная "смерть" в результате возникновения некоторых исключений;
вызвать 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:
<;blockquote>
```
/*
 *  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, µcode_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. В противном случае загрузчик просто сравнивает версию ядра, объявленную в модуле, и экспортируемую ядром, и прерывает загрузку, модуля, если версии не совпадают.

3. Virtual Filesystem (VFS)

3.1 Кеш Inode и взаимодействие с Dcache

Для поддержки различных файловых систем Linux предоставляет специальный интерфейс уровня ядра, который называется VFS (Virtual Filesystem Switch). Он подобен интерфейсу vnode/vfs, имеющемуся в производных от SVR4 (изначально пришедшему из BSD и реализаций Sun)

Реализация inode cache для Linux находится в единственном файле fs/inode.c, длиной в 977 строк (Следует понимать, что размер файла может колебаться от версии к версии, так например в ядре 2.4.18, длина этого файла составляет 1323 строки прим. перев.). Самое интересное, что за последние 5 - 7 лет этот файл претерпел незначительные изменения, в нем до сих пор можно найти участки кода, дошедшие до наших дней с версии, скажем, 1.3.42

Inode cache в Linux представляет из себя:

Глобальный хеш-массив inode_hashtable, в котором каждый inode хешируется по значению указателя на суперблок и 32-битному номеру inode. При отсутсвии суперблока (inode->i_sb == NULL), вместо хеш-массива inode добавляется к двусвязному списку anon_hash_chain. Примером таких анонимных inodes могут служить сокеты, созданные вызовом функции net/socket.c:sock_alloc(), которая вызывает fs/inode.c:get_empty_inode().
Глобальный список inode_in_use, который содержит допустимые inodes (i_count>0 и i_nlink>0). Inodes вновь созданные вызовом функций get_empty_inode() и get_new_inode() добавляются в список inode_in_use
Глобальный список inode_unused, который содержит допустимые inode с i_count = 0.
Список для каждого суперблока (sb->s_dirty) , который содержит inodes с i_count>0, i_nlink>0 и i_state & I_DIRTY. Когда inode помечается как "грязный" (здесь и далее под термином "грязный" подразумевается "измененный" прим. перев.), он добавляется к списку sb->s_dirty при условии, что он (inode) хеширован. Поддержка такого списка позволяет уменьшить накладные расходы на синхронизацию.
Inode cache суть есть - SLAB cache, который называется inode_cachep. Объекты inode могут создаваться и освобождаться, вставляться и изыматься из SLAB cache

Через поле inode->i_list с inode вставляется в список определенного типа, через поле inode->i_hash - в хеш-массив. Каждый inode может входить в хеш-массив и в один и только в один список типа (in_use, unused или dirty).

Списки эти защищаются блокировкой (spinlock) inode_lock.

Подсистема inode cache инициализируется при вызове функции inode_init() из init/main.c:start_kernel(). Эта функция имеет один входной параметр - число страниц физической памяти в системе. В соответсвии с этим параметром inode cache конфигуририруется под существующий объем памяти, т.е. при большем объеме памяти создается больший хеш-массив.

Единственная информация о inode cache, доступная пользователю - это количество неиспользованных inodes из inodes_stat.nr_unused. Получить ее можно из файлов /proc/sys/fs/inode-nr и /proc/sys/fs/inode-state.

Можно исследовать один из списков с помощью gdb:

(gdb) printf "%d\n", (unsigned long)(&((struct inode *)0)->i_list)
8
(gdb) p inode_unused
$34 = 0xdfa992a8
(gdb) p (struct list_head)inode_unused
$35 = {next = 0xdfa992a8, prev = 0xdfcdd5a8}
(gdb) p ((struct list_head)inode_unused).prev
$36 = (struct list_head *) 0xdfcdd5a8
(gdb) p (((struct list_head)inode_unused).prev)->prev
$37 = (struct list_head *) 0xdfb5a2e8
(gdb) set $i = (struct inode *)0xdfb5a2e0
(gdb) p $i->i_ino
$38 = 0x3bec7
(gdb) p $i->i_count
$39 = {counter = 0x0}

Заметьте, что от адреса 0xdfb5a2e8 отнимается число 8, чтобы получить адрес struct inode (0xdfb5a2e0), согласно определению макроса list_entry() из include/linux/list.h.

Для более точного понимания принципа работы inode cache, давайте рассмотрим цикл жизни обычного файла в файловой системе ext2 с момента его открытия и до закрытия.

fd = open("file", O_RDONLY);
close(fd);

Системный вызов open(2) реализован в виде функции fs/open.c:sys_open, но основную работу выполняет функция fs/open.c:filp_open(), которая разбита на две части:

open_namei(): заполняет структуру nameidata, содержащую структуры dentry и vfsmount.
dentry_open(): с учетом dentry и vfsmount, размещает новую struct file и связывает их между собой; вызывает метод f_op->open() который был установлен в inode->i_fop при чтении inode в open_namei() (поставляет inode через dentry->d_inode).

Функция open_namei() взаимодействует с dentry cache через path_walk(), которая, в свою очередь, вызывает real_lookup(), откуда вызывается метод inode_operations->lookup(). Назначение последнего - найти вход в родительский каталог и получить соответствующий inode вызовом iget(sb, ino) При считывании inode, значение dentry присваивается посредством d_add(dentry, inode). Следует отметить, что для UNIX-подобных файловых систем, поддерживающих концепцию дискового номера inode, в ходе выполнения метода lookup(). производится преобразование порядка следования байт числа (endianness) в формат CPU, например, если номер inode хранится в 32-битном формате с обратным порядком следования байт (little-endian), то выполняются следующие действия:
(Считаю своим долгом подробнее остановиться на понятии endianness. Под этим термином понимается порядок хранения байт в машинном слове (или двойном слове). Порядок может быть "прямым" (т.е. 32-битное число хранится так 0x12345678) и тогда говорят "big endianness" (на отечественном жаргоне это звучит как "большой конец", т.е. младший байт лежит в старшем адресе) или "обратным" (т.е. 32-битное число хранится так 0x78563412 - такой порядок следования байт принят в архитектуре Intel x86) и тогда говорят "little endianness" (на отечественном жаргоне это звучит как "маленький конец", т.е. младший байт лежит в младшем адресе). прим. перев.)

unsigned long ino = le32_to_cpu(de->inode);
inode = iget(sb, ino);
d_add(dentry, inode);

Таким образом, при открытии файла вызывается iget(sb, ino), которая, фактически, называется iget4(sb, ino, NULL, NULL), эта функция:

Пытается найти inode в хеш-таблице по номерам суперблока и inode. Поиск выполняется под блокировкой inode_lock. Если inode найден, то увеличивается его счетчик ссылок (i_count); если счетчик перед инкрементом был равен нулю и inode не "грязный", то он удаляется из любого списка (inode->i_list), в котором он находится (это конечно же список inode_unused) и вставляется в список inode_in_use; в завершение, уменьшается счетчик inodes_stat.nr_unused.
Если inode на текущий момент заблокирован, то выполняется ожидание до тех пор, пока inode не будет разблокирован, таким образом, iget4() гарантирует возврат незаблокированного inode.
Если поиск по хеш-таблице не увенчался успехом, то вызывается функция get_new_inode(), которой передается указатель на место в хеш-таблице, куда должен быть вставлен inode.
get_new_inode() распределяет память под новый inode в SLAB кэше inode_cachep, но эта операция может устанавливать блокировку (в случае GFP_KERNEL), поэтому освобождается блокировка inode_lock. Поскольку блокировка была сброшена то производится повторный поиск в хеш-таблице, и если на этот раз inode найден, то он возвращается в качестве результата (при этом счетчик ссылок увеличивается вызовом __iget), а новый, только что распределенный inode уничтожается. Если же inode не найден в хеш-таблице, то вновь созданный inode инициализируется необходимыми значениями и вызывается метод sb->s_op->read_inode(), чтобы инициализировать остальную часть inode Во время чтения метдом s_op->read_inode(), inode блокируется (i_state = I_LOCK), после возврата из s_op->read_inode() блокировка снимается и активируются все ожидающие его процессы.

Теперь рассмотрим действия, производимые при закрытии файлового дескриптора. Системный вызов close(2) реализуется функцией fs/open.c:sys_close(), которая вызывает do_close(fd, 1). Функция do_close(fd, 1) записывает NULL на место дескриптора файла в таблице дескрипторов процесса и вызывает функцию filp_close(), которая и выполняет большую часть действий. Вызывает интерес функция fput(), которая проверяет была ли это последняя ссылка на файл и если да, то через fs/file_table.c:_fput() вызывается __fput(), которая взаимодействует с dcache (и таким образом с inode cache - не забывайте, что dcache является "хозяином" inode cache!). Функция fs/dcache.c:dput() вызывает dentry_iput(), которая приводит нас обратно в inode cache через iput(inode). Разберем fs/inode.c:iput(inode) подробнее:

Если входной параметр NULL, то абсолютно ничего не делается и управление возвращается обратно.
Если входнй параметр определен, то вызывается специфичный для файловой системы метод sb->s_op->put_inode() без захвата блокировки (так что он может быть блокирован).
Устанавливается блокировка (spinlock) и уменьшается i_count. Если это была не последняя ссылка, то просто проверяется - поместится ли количество ссылок в 32-битное поле и если нет - то выводится предупреждение. Отмечу, что поскольку вызов производится под блокировкой inode_lock, то для вывода предупреждения используется функция printk(), которая никогда не блокируется, поэтому ее можно вызывать абсолютно из любого контекста исполнения (даже из обработчика прерываний!).
Если ссылка была последней, то выполняются дополнительные действия.

Дополнительные действия, выполняемые по закрытию в случае последней ссылки функцией iput(), достаточно сложны, поэтому они рассматриваются отдельно:

Если i_nlink == 0 (например файл был удален, пока мы держали его открытым), то inode удаляется из хеш-таблицы и из своего списка. Если имеются какие-либо страницы в кеше страниц, связанные с данным inode, то они удаляются посредством truncate_all_inode_pages(&inode->i_data). Затем, если определен, то вызывается специфичный для файловой системы метод s_op->delete_inode(), который обычно удаляет дисковую копию inode. В случае отсутствия зарегистрированного метода s_op->delete_inode() (например ramfs), то вызывается clear_inode(inode), откуда производится вызов s_op->clear_inode(), если этот метод зарегистрирован и inode соответствует блочному устройству. Счетчик ссылок на это устройство уменьшается вызовом bdput(inode->i_bdev).
Если i_nlink != 0, то проверяется - есть ли другие inode с тем же самым хеш-ключом (in the same hash bucket) и если нет, и inode не "грязный", то он удаляется из своего списка типа, вставляется в список inode_unused, увеличивая inodes_stat.nr_unused. Если имеются inodes с тем же самым хеш-ключом, то inode удаляется из списка типа и добавляется к списку inode_unused. Если это анонимный inode (NetApp .snapshot) то он удаляется из списка типа и очищается/удаляется полностью.

3.2 Регистрация/Дерегистрация файловых систем.

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

В мире широко используются различные операционные системы и чтобы люди не потеряли деньги, затреченные на покупку легального программного обеспечения, Linux должен был предоставить поддержку большого количества файловых систем, большинство из которых реализовано исключительно для совместимости.
Интерфейс для новых файловых систем должен был быть очень простым, чтобы разработчики могли легко перепроектировать существующие файловые системы в их версии "ТОЛЬКО ДЛЯ ЧТЕНИЯ". Linux значительно облегчает создание таких версий, 95% работы над созданием новой файловой системы заключается в добавлении поддержки записи. Вот конкретный пример, я написал файловую систему BFS в версии "ТОЛЬКО ДЛЯ ЧТЕНИЯ" всего за 10 часов, однако мне потребовалось несколько недель, чтобы добавить в нее поддержку записи (и даже сегодня некоторые пуристы говорят о ее незавершенности, поскольку в ней "не реализована поддержка компактификации"). .
Интерфейс VFS является экспортируемым и поэтому все файловые системы в Linux могут быть реализованы в виде модулей..

Рассмотрим порядок добавления новой файловой системы в Linux. Код, реализующий файловую систему, может быть выполнен либо в виде динамически подгружаемого модуля, либо может быть статически связан с ядром. Все, что требуется сделать - это заполнить struct file_system_type и зарегистрировать файловую систему в VFS с помощью функции register_filesystem(), как показано ниже (пример взят из fs/bfs/inode.c):

#include 
#include 

static struct super_block *bfs_read_super(struct super_block *, void *, int);

static DECLARE_FSTYPE_DEV(bfs_fs_type, "bfs", bfs_read_super);

static int __init init_bfs_fs(void)
{
        return register_filesystem(&bfs_fs_type);
}

static void __exit exit_bfs_fs(void)
{
        unregister_filesystem(&bfs_fs_type);
}

module_init(init_bfs_fs)
module_exit(exit_bfs_fs)

Макросы module_init()/module_exit(), в случае, когда BFS компилируется как модуль, преобразуют функции init_bfs_fs() и exit_bfs_fs() в init_module() и cleanup_module() соответственно. Если BFS компилируется статически, то код exit_bfs_fs() исчезает, поскольку необходимость в нем отпадает.

Структура struct file_system_type объявлена в include/linux/fs.h:

struct file_system_type {
        const char *name;
        int fs_flags;
        struct super_block *(*read_super) (struct super_block *, void *, int);
        struct module *owner;
        struct vfsmount *kern_mnt; /* For kernel mount, if it's FS_SINGLE fs */
        struct file_system_type * next;
};

Поля структуры:

name: Удобочитаемое название файловой системы, которое выводится в файле /proc/filesystems и используется как ключ для поиска файловой системы по имени; это же имя используется как аргумент в вызове mount(2) и должно быть уникальным. Для модулей имя указывает на адресное пространство модуля так, что в случае, когда модуль уже выгружен, но файловая система еще остается зарегистрированной, то команда cat /proc/filesystems может вызвать oops.
fs_flags: один или более флагов (объединенных по OR): FS_REQUIRES_DEV для файловых систем, которые могут быть смонтированы только с блочных устройств, FS_SINGLE для файловых систем, имеющих только один суперблок, FS_NOMOUNT для файловых систем которые не могут быть смонтированы из пользовательского пространства системным вызовом mount(2), однако такие файловые системы могут быть смонтированы ядром через вызов kern_mount(), например pipefs.
read_super: указатель на функцию, которая считывает суперблок в процессе монтирования. Эта функция должна быть определена обязательно. В случае ее отсутствия, операция монтирования (независимо от того - из пользовательского ли пространства или из ядра выполняется монтирование) всегда будет терпеть неудачу, а в случае установленного флага FS_SINGLE попытка монтирования будет приводить к Oops в get_sb_single(), при попытке получить ссылку fs_type->kern_mnt->mnt_sb (в то время как fs_type->kern_mnt = NULL).
owner: указатель на модуль реализации файловой системы. Если файловая система связана в ядро статически, то этот указатель содержит NULL. Нет необходимости устанавливать его вручную, так как макрос THIS_MODULE делает это автоматически.
kern_mnt: только для файловых систем, имеющих флаг FS_SINGLE. Устанавливается kern_mount() (TODO: вызов kern_mount() должен отвергать монтирование файловых систем если флаг FS_SINGLE не установлен).
next: поле связи в односвязном списке file_systems (см. fs/super.c). Список защищается "read-write" блокировкой file_systems_lock и модифицируется функциями register/unregister_filesystem().

Функция read_super() заполняет поля суперблока, выделяет память под корневой inode и инициализирует специфичную информацию, связанную с монтируемым экземпляром файловой системы. Как правило read_super():

Считывает суперблок с устройства, определяемого аргументом sb->s_dev, используя функцию bread(). Если предполагается чтение дополнительных блоков с метаданными, то имеет смысл воспользоваться функцией breada(), чтобы прочитать дополнительные блоки асинхронно.
Суперблок проверяется на корректность по "магическим" последовательностям и другим признакам.
Инициализируется указатель sb->s_op на структуру struct super_block_operations. Эта структура содержит указатели на функции, специфичные для файловой системы, такие как "read inode", "delete inode" и пр.
Выделяет память под корневой inode и dentry вызовом функции d_alloc_root().
Если файловая система монтируется не как "ТОЛЬКО ДЛЯ ЧТЕНИЯ", то в sb->s_dirt записывается 1 и буфер, содержащий суперблок, помечается как "грязный" (TODO: зачем это делается? Я сделал так в BFS потому, что в MINIX делается то же самое).

3.3 Управление файловыми дескрипторами

В Linux между пользовательским файловым дескриптором и структурой inode в ядре, существует несколько уровней косвенных ссылок. Когда процесс открывает файл системным вызовом open(2), ядро возвращает положительное малое целое число, которое затем используется в операциях ввода/вывода над заданным файлом. Это целое число является индексом в массиве указателей на struct file. Каждая struct file содержит указатель на dentry file->f_dentry. Каждая dentry имеет указатель на inode dentry->d_inode.

Каждая задача содержит поле tsk->files которое указывает на struct files_struct, определенную в include/linux/sched.h:

/*
 * Структура таблицы открытых файлов
 */
struct files_struct {
        atomic_t count;
        rwlock_t file_lock;
        int max_fds;
        int max_fdset;
        int next_fd;
        struct file ** fd;      /* массив дескрипторов */
        fd_set *close_on_exec;
        fd_set *open_fds;
        fd_set close_on_exec_init;
        fd_set open_fds_init;
        struct file * fd_array[NR_OPEN_DEFAULT];
};

Поле file->count - это счетчик ссылок, увеличивается в get_file() (обычно вызывается из fget()) и уменьшается в fput() и в put_filp().Различие между fput() и put_filp() состоит в том, что fput() выполняет больший объем работы, необходимый для регулярных файлов, т.е. освобождение блокировок, освобождение dentry и пр., в то время как put_filp() работает только с таблицей файловых структур, т.е. уменьшает счетчик, удаляет файл из anon_list и добавляет его в free_list, под блокировкой files_lock.

Таблица tsk->files может использоваться совместно родителем и потомком, если потомок был создан системным вызовом clone() с флагом CLONE_FILES. В качестве примера можно привести kernel/fork.c:copy_files() (вызывается из do_fork()), где только лишь увеличивается счетчик ссылок file->count. вместо обычного (для классического fork(2) в UNIX) копирования таблицы дескрипторов.

При открытии файла в памяти размещается новая файловая структура, которая устанавливается в слот current->files->fd[fd] и взводится бит fd в current->files->open_fds. Действия эти выполняются под защитой от записи read-write блокировкой current->files->file_lock. При закрытии дескриптора сбрасывается бит fd в current->files->open_fds, а поле current->files->next_fd устанавливается равным fd на случай поиска первого неиспользуемого дескриптора при следующем открытии файла.

3.4 Управление файловой структурой

Структура file объявлена в include/linux/fs.h:

struct fown_struct {
        int pid;                /* pid или -pgrp процесса, которому должен передаваться SIGIO */
        uid_t uid, euid;        /* uid/euid процесса-владельца */
        int signum;             /* posix.1b rt signal to be delivered on IO */
};

struct file {
        struct list_head        f_list;
        struct dentry           *f_dentry;
        struct vfsmount         *f_vfsmnt;
        struct file_operations  *f_op;
        atomic_t                f_count;
        unsigned int            f_flags;
        mode_t                  f_mode;
        loff_t                  f_pos;
        unsigned long           f_reada, f_ramax, f_raend, f_ralen, f_rawin;
        struct fown_struct      f_owner;
        unsigned int            f_uid, f_gid;
        int                     f_error;

        unsigned long           f_version;

        /* требуется для драйвера tty, а возможно и для других */
        void                    *private_data;
};

Остановимся подробнее на полях struct file:

f_list: поле связи с одним (и только одним) из списков:
а) sb->s_files - список всех открытых файлов в данной файловой системе, если соответствующий inode не является анонимным, то dentry_open() (вызываемая из filp_open()) вставляет файл в этот список;
б) fs/file_table.c:free_list - список неиспользуемых структур;
в) fs/file_table.c:anon_list - в этот список включаются структуры, создаваемые в get_empty_filp().
Доступ к этим спискам производится под блокировкой files_lock.
f_dentry: dentry файла. Создается в процессе поиска nameidata в open_namei() (или точнее в path_walk()), но в действительности поле file->f_dentry заполняется в dentry_open().
f_vfsmnt: указатель на структуру vfsmount файловой системы, содержащей файл. Заполняется функцией dentry_open() и является частью nameidata, поиск которой производится в open_namei() (или точнее в path_init()).
f_op: указатель на список file_operations, который содержит адреса методов для работы с файлом. Копируется из inode->i_fop методом s_op->read_inode(), вызываемым в процессе поиска nameidata. Более подробно на списке file_operations мы остановимся ниже в этом разделе.
f_count: счетчик ссылок, изменяется в get_file/put_filp/fput.
f_flags: флаги O_XXX системного вызова open(2), копируются функцией dentry_open() (с небольшими изменениями в filp_open()), при чем флаги O_CREAT, O_EXCL, O_NOCTTY, O_TRUNC сбрасываются, поскольку они не могут модифицироваться по параметру F_SETFL (или F_GETFL) в системном вызове fcntl(2).
f_mode: комбинация флагов состояния, устанавливается в dentry_open(). Флаги режимов доступа для чтения и записи выведены в отдельные биты, чтобы облегчить контроль состояния: (f_mode & FMODE_WRITE) и (f_mode & FMODE_READ).
f_pos: текущая позиция чтения/записи в файле. Для архитектуры i386 имеет тип long long, т.е. 64 бита.
f_reada, f_ramax, f_raend, f_ralen, f_rawin: поддержка опережающего чтения (readahead) слишком сложна, чтобы обсуждаться простыми смертными ;)
f_owner: владелец файла, который будет получать I/O уведомления посредством механизма SIGIO (см. fs/fcntl.c:kill_fasync()).
f_uid, f_gid - user id и group id процесса, открывшего файл, заполняются во время создания структуры в get_empty_filp(). Если файл является сокетом, то эти поля могут быть использованы в ipv4 netfilter.
f_error: используется клиентом NFS для возврата ошибки записи. Поле устанавливается в fs/nfs/file.c и проверяется в mm/filemap.c:generic_file_write().
f_version - механизм контроля версий, служит для синхронизации с кэшем. Увеличивается на единицу (используя глобальный event) всякий раз, когда изменяется f_pos.
private_data: скрытая информация о файле, может использоваться файловой системой (например coda хранит здесь удостоверения) или драйверами устройств. Драйверы устройств (при наличии devfs) могут использовать это поле для различения нескольких экземпляров вместо классического анализа младшего номера версии в file->f_dentry->d_inode->i_rdev.

Перейдем к рассмотрению списка методов управления файлом file_operations. Позволю себе напомнить, что он копируется из inode->i_fop методом s_op->read_inode(). Структура (список методов) объявлена в include/linux/fs.h:

struct file_operations {
        struct module *owner;
        loff_t (*llseek) (struct file *, loff_t, int);
        ssize_t (*read) (struct file *, char *, size_t, loff_t *);
        ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
        int (*readdir) (struct file *, void *, filldir_t);
        unsigned int (*poll) (struct file *, struct poll_table_struct *);
        int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
        int (*mmap) (struct file *, struct vm_area_struct *);
        int (*open) (struct inode *, struct file *);
        int (*flush) (struct file *);
        int (*release) (struct inode *, struct file *);
        int (*fsync) (struct file *, struct dentry *, int datasync);
        int (*fasync) (int, struct file *, int);
        int (*lock) (struct file *, int, struct file_lock *);
        ssize_t (*readv) (struct file *, const struct iovec *, unsigned long, loff_t *);
        ssize_t (*writev) (struct file *, const struct iovec *, unsigned long, loff_t *);
};

owner: указатель на модуль рассматриваемой подсистемы. Это поле устанавливается только драйверами устройств, файловая система может игнорировать его, поскольку счетчик ссылок модуля файловой системы изменяется во время монтирования/демонтирования, в то время как для драйверов это должно делаться во время открытия/закрытия устройства.
llseek: реализация системного вызова lseek(2). Обычно опускается и используется fs/read_write.c:default_llseek(). (TODO: Принудительно устанавливать это поле в NULL, тем самым сэкономится лишний if() в llseek())
read: реализация системного вызова read(2). Файловые системы могут использовать mm/filemap.c:generic_file_read() для обычных файлов и fs/read_write.c:generic_read_dir() (которая просто возвращает -EISDIR) для каталогов.
write: реализация системного вызова write(2). Файловые системы могут использовать mm/filemap.c:generic_file_write() для обычных файлов и игнорировать его для каталогов.
readdir: используется файловой системой. Реализует системные вызовы readdir(2) и getdents(2) для каталогов и игнорируется для обычных файлов.
poll: реализация системных вызовов poll(2) и select(2)
ioctl: реализация специфичного для драйвера или для файловой системы метода ioctl ( управление вводом/выводом). Обратите внимание: общие методы ioctl типа FIBMAP, FIGETBSZ, FIONREAD реализуются на более высоком уровне, поэтому они никогда не пользуются методом f_op->ioctl().
mmap: реализация системного вызова mmap(2). Файловая система может использовать generic_file_mmap для обычных файлов и игнорировать это поле для каталогов.
open: вызывается во время выполнения open(2) функцией dentry_open(). Редко используется файловыми системами, например coda пытается кэшировать файл во время открытия.
flush: вызывается при каждом вызове close(2) для заданного файла, не обязательно в последнем (см. метод release() ниже). Единственная файловая система, которая вызывает этот метод - это NFS клиент, которая "выталкивает" все измененные страницы. Примечательно, что этот метод может завершаться с кодом ошибки, который передается обратно в пространство пользователя, откуда делался системный вызов close(2).
release: метод вызывается в последнем вызове close(2) для заданного файла, т.е. когда file->f_count станет равным нулю. Хотя и возвращает целое (int) значение, но VFS игнорирует его (см. code>fs/file_table.c:__fput()).
fsync: преобразуется в системные вызовы fsync(2)/fdatasync(2), причем последний аргумент определяет сам вызов - fsync или fdatasync. Не выполняет почти никаких действий за исключением преобразования файлового дескриптора в файловую структуру (file = fget(fd)) и сброса/установки семафора inode->i_sem. Файловая система Ext2, на сегодняшний день, игнорирует последний аргумент, передаваемый методу и выполняет одни и те же действия как для fsync(2) так и для fdatasync(2).
fasync: этот метод вызывается при изменении file->f_flags & FASYNC.
lock: специфичная для файловой системы часть механизма блокировки области файла POSIX fcntl(2). Единственная неувязка состоит в том, что этот метод вызывается перед независимой от типа файловой системы posix_lock_file(), если метод завершается успешно, а стандартный POSIX код блокировки терпит неудачу, то блокировка не будет снята на зависимом от типа файловой системы уровне..
readv: реализация системного вызова readv(2).
writev: реализация системного вызова writev(2).

3.5 Управление Суперблоком и точкой монтирования

В Linux, информация о смонтированных файловых системах хранится в двух различных структурах - super_block и vfsmount. Сделано это для того, чтобы имелась возможность смонтировать одну и ту же файловую систему к нескольким точкам монтирования одновременно, это означает, что одна и та же структура super_block может соответствовать нескольким структурам vfsmount.

В первую очередь рассмотрим структуру struct super_block, объявленную в include/linux/fs.h:

struct super_block {
        struct list_head        s_list;         /* Хранится первым */
        kdev_t                  s_dev;
        unsigned long           s_blocksize;
        unsigned char           s_blocksize_bits;
        unsigned char           s_lock;
        unsigned char           s_dirt;
        struct file_system_type *s_type;
        struct super_operations *s_op;
        struct dquot_operations *dq_op;
        unsigned long           s_flags;
        unsigned long           s_magic;
        struct dentry           *s_root;
        wait_queue_head_t       s_wait;

        struct list_head        s_dirty;        /* "грязные" inodes */
        struct list_head        s_files;

        struct block_device     *s_bdev;
        struct list_head        s_mounts;       /* vfsmount(s) of this one */
        struct quota_mount_options s_dquot;     /* параметры для Diskquota */

       union {
                struct minix_sb_info    minix_sb;
                struct ext2_sb_info     ext2_sb;
                ..... Информация sb-private, необходимая для всех файловых систем ...
                void                    *generic_sbp;
        } u;
       /*
         * Следующее поле предназначено *только* для VFS. 
         * Ни одна файловая система не должна изменять его,
         * даже если она обращается к этому полю.
         * Вас предупредили.
         */
        struct semaphore s_vfs_rename_sem;      /* Kludge */

        /* Следующее поле используется демоном knfsd для преобразования(inode number based)
         * file handle в dentry. Поскольку путь в дереве dcache строится снизу вверх
         * то в течение некоторого времени путь является неполным, никак не связанным
         * с главным деревом.  Этот семафор гарантирует существование единственного
         * такого свободного пути в файловой системе.
         * Заметьте, что такие "несвязанные" файлы допустимы
         * но не каталоги.
         */
        struct semaphore s_nfsd_free_path_sem;
};

Более подробно о полях структуры super_block:

s_list: двусвязный список всех активных суперблоков; Заметьте, что я не говорю "всех смонтированных файловых систем", потому что в Linux всем смонтированным экземплярам файловой системы соответствует единственный суперблок.
s_dev: предназначено для файловых систем, требующих наличие блочного устройства, т.е. для файловых систем, зарегистрированных с флагом FS_REQUIRES_DEV, это поле представляет собой копию i_dev блочного устройства. Для других файловых систем (называемых анонимными) представляет собой целое число MKDEV(UNNAMED_MAJOR, i), где i принадлежит диапазону от 0 до 255 включительно и является порядковым номером первого неустановленного бита в массиве unnamed_dev_in_use. Смотрите fs/super.c:get_unnamed_dev()/put_unnamed_dev(). Неоднократно предлагалось отказаться от использования поля s_dev анонимными файловыми системами.
s_blocksize, s_blocksize_bits: Размер блока и количество бит, необходимое для хранения размера блока (log2(blocksize)).
s_lock: индикатор блокировки суперблока функциями lock_super()/unlock_super().
s_dirt: устанавливается при внесении изменений в суперблок и сбрасывается при записи его обратно на диск.
s_type: указатель на структуру struct file_system_type, соответствующую файловой системе. Метод файловой системы read_super() не должен устанавливать это поле, так как это поле устанавливается VFS в функции fs/super.c:read_super(), в случае успешного вызова метода read_super() конкретной файловой, и сбрасывется в NULL в противном случае.
s_op: указатель на структуру (список) super_operations, которая содержит специфичные для заданной файловой системы методы, такие как чтение/запись inode и пр. Корректное заполнение этой структуры - задача метода файловой системы read_super().
dq_op: операции по дисковому квотированию.
s_flags: флаги суперблока.
s_magic: "магическое" число файловой системы. Используется файловой системой minix для различения разных вариантов ее.
s_root: dentry корня файловой системы. Метод read_super() считывает корневой inode с диска и передает его в d_alloc_root(), который выделяет память под dentry и заполняет ее. Некоторые файловые системы используют иное обозначение корня, нежели "/", поэтому используется более общая функция d_alloc() для образования полного имени, например pipefs использует "pipe:" для обозначения своего корня.
s_wait: очередь ожидания, в которой нахдятся процессы, ожидающие снятия блокировки с суперблока.
s_dirty: список всех "грязных" (измененных) inodes. Напомню, что если inode изменился (т.е. inode->i_state & I_DIRTY), то этот список связуется через inode->i_list.
s_files: список всех открытых файлов в данном суперблоке. Полезен при принятии решения о перемонтировании файловой системы в режиме "только для чтения", см. fs/file_table.c:fs_may_remount_ro(), которая просматривает список sb->s_files и отвергает возможность перемонтирования если имеется хотя бы один файл, открытый "на запись" (file->f_mode & FMODE_WRITE) или ожидающий удаления (inode->i_nlink == 0).
s_bdev: для случая FS_REQUIRES_DEV указывает на структуру block_device, описывающую блочное устройство, с которого смонтирована файловая система.
s_mounts: список всех структур vfsmount для каждого смонтированного экземпляра данного суперблока.
s_dquot: используется при квотировании диска.

Методы управления суперблоком перечисляются в структуре super_operations, объявленной в include/linux/fs.h:

struct super_operations {
        void (*read_inode) (struct inode *);
        void (*write_inode) (struct inode *, int);
        void (*put_inode) (struct inode *);
        void (*delete_inode) (struct inode *);
        void (*put_super) (struct super_block *);
        void (*write_super) (struct super_block *);
        int (*statfs) (struct super_block *, struct statfs *);
        int (*remount_fs) (struct super_block *, int *, char *);
        void (*clear_inode) (struct inode *);
        void (*umount_begin) (struct super_block *);
};

read_inode: операция чтения inode из файловой системы. Вызывается только в fs/inode.c:get_new_inode() из iget4() (и следовательно из iget()). Если файловая система предполагает вызов iget() то метод read_inode() должен быть реализован, в противном случае get_new_inode() будет приводить к "впадению в панику" (panic). Во время чтения inode заблокирован (inode->i_state = I_LOCK). Когда функция возвращает управление, все процессы из очереди inode->i_wait пробуждаются. В задачу метода read_inode() входит обнаружение дискового блока, который содержит заданный inode и с помощью функйии буферного кэша bread() прочитать его и инициализировать различные поля в структуре inode, например inode->i_op и inode->i_fop, чтобы уровень VFS "знал" какие операции над inode и соответствующим ему файлом, считаются допустимыми. Имеются файловые системы, в которых метод read_inode() не реализован - это ramfs и pipefs. Так ramfs имеет свою собственную функцию генерации inode (ramfs_get_inode()).
write_inode: операция записи inode на диск. так же как и read_inode() отыскивает нужный дисковый блок и вызывает функцию буферного кэша mark_buffer_dirty(bh). Этот метод вызывается для "грязных" inode (которые были помечены вызовом mark_inode_dirty()) при возникновении необходимости синхронизации как отдельно взятого inode, так и файловой системы в целом.
put_inode: вызывается всякий раз при уменьшении счетчика ссылок.
delete_inode: вызывается всякий раз, когда inode->i_count и inode->i_nlink достигают нулевого значения. Файловая система удаляет дисковую копию inode и вызывает clear_inode() для VFS inode, чтобы "прекратить его существование окончательно".
put_super: вызывается на последней стадии работы системного вызова umount(2), чтобы уведомить файловую систему о том, что любая приватная информация, удерживаемая ею, должна быть освобождена. Обычно это brelse() блока, содержащего суперблок, и kfree() для освобождения всех ранее размещенных блоков, inodes и т.п.
write_super: вызывается в случае необходимости записать суперблок на диск. Должен отыскать блок, содержащий суперблок, (обычно хранится в области sb-private) и вызвать mark_buffer_dirty(bh). А так же должен сбросить флаг sb->s_dirt flag.
statfs: реализация системного вызова fstatfs(2)/statfs(2). Заметьте, что указатель на struct statfs, передаваемый в качестве аргумента, является указателем пространства ядра а не пользовательского пространства, поэтому не следует выполнять каких либо операций ввода-вывода в пользовательском пространстве. В случае отсутствия этого метода вызов statfs(2) будет возвращвть код ошибки ENOSYS.
remount_fs: вызывается всякий раз при перемонтировании файловой системы.
clear_inode: вызывается из функции clear_inode() уровня VFS. Файловая система должна освободить приватную информацию в структуре inode (присоединенную через поле generic_ip).
umount_begin: вызывается в случае принудительно размонтирования для уведомления файловой системы заранее, чтобы убедиться, что она не занята. В настоящее время используется только NFS. Этот метод не имеет никакого отношения к идее поддержки принудительного размонтирования на уровне VFS.

Теперь рассмотрим последовательность действий, выполняемых при монтировании дисковой (FS_REQUIRES_DEV) файловой системы. Реализация системного вызова mount(2) находится в fs/super.c:sys_mount(), которая по сути является лишь оберткой, которая передает опции монтирования, тип файловой системы и название устройства в функцию do_mount().

В случае необходимости, загружается модуль драйвера файловой системы и увеличивается счетчик ссылок на этот модуль. Примечательно, что в процессе монтирования счетчик ссылок на модуль файловой системы увеличивается дважды - один раз в do_mount(), вызываемой из get_fs_type(), и один раз в get_sb_dev(), вызываемой из get_filesystem(), если read_super() выполнилась успешно. Первое увеличение предотвращает выгрузку модуля пока выполняется метод read_super() и второе увеличение указывает на то, что модуль используется смонтированным экземпляром. Вполне понятно, что перед завершением do_mount() уменьшает счетчик ссылок на единицу, таким образом суммарное приращение счетчика составляет единицу после каждого монтирования.
Для нашего случая выражение fs_type->fs_flags & FS_REQUIRES_DEV истинно, поэтому далее инициализируется суперблок, вызовом get_sb_bdev(), который получает ссылку на блочное устройство и вызывом метода read_super() заполняет поля суперблока. Если все прошло гладко, то структура super_block считается инициализированной и мы получаем дополнительно ссылку на модуль файловой системы и ссылку на основное блочное устройство.
В памяти размещается новая структура vfsmount и "прицепляется" к списку sb->s_mounts и к глобальному списку vfsmntlist. С помощью поля mnt_instances структуры vfsmount можно найти все смонтированные экземпляры файловой системы для одного и того же суперблока. С помощью списка mnt_list можно отыскать все смонтированные экземпляры файловых систем для всех суперблоков в системе. Поле mnt_sb указывает на данный суперблок, а mnt_root получает новую ссылку на sb->s_root dentry.

3.6 Пример виртуальной файловой системы: pipefs

В качестве простого примера файловой системы в Linux рассмотрим pipefs, которая не требует наличия блочного устройства для своего монтирования. Реализация pipefs находится в fs/pipe.c.

static DECLARE_FSTYPE(pipe_fs_type, "pipefs", pipefs_read_super,
        FS_NOMOUNT|FS_SINGLE);

static int __init init_pipe_fs(void)
{
        int err = register_filesystem(&pipe_fs_type);
        if (!err) {
                pipe_mnt = kern_mount(&pipe_fs_type);
                err = PTR_ERR(pipe_mnt);
                if (!IS_ERR(pipe_mnt))
                        err = 0;
        }
        return err;
}

static void __exit exit_pipe_fs(void)
{
        unregister_filesystem(&pipe_fs_type);
        kern_umount(pipe_mnt);
}

module_init(init_pipe_fs)
module_exit(exit_pipe_fs)

Файловая система принадлежит к типу FS_NOMOUNT|FS_SINGLE это означает, что она не может быть смонтирована из пространства пользователя и в системе может иметься только один суперблок этой файловой системы. Флаг FS_SINGLE означает также что она должна монтироваться через kern_mount() после того как будет выполнена регистрация вызовом register_filesystem(), что собственно и выполняется функцией init_pipe_fs(). Единственная неприятность - если kern_mount() завершится с ошибкой (например когда kmalloc(), вызываемый из add_vfsmnt() не сможет распределить память), то файловая система окажется зарегистрированной но модуль не будет инициализирован. Тогда команда cat /proc/filesystems повлечет за собой Oops. (передал Линусу "заплату", хотя это фактически не является ошибкой, поскольку на сегодняшний день pipefs не может быть скомпилирована как модуль, но в будущем вполне может быть добавлена взможность вынесения pipefs в модуль).

В результате register_filesystem(), pipe_fs_type добавляется к списку file_systems, который содержится в /proc/filesystems. Прочитав его, вы обнаружите "pipefs" с флагом "nodev", указывающим на то, что флаг FS_REQUIRES_DEV не был установлен. Следовало бы расширить формат файла /proc/filesystems с тем, чтобы включить в него поддержку всех новых FS_ флагов (и я написал такую "заплату"), но это невозможно, поскольку такое изменение может отрицательно сказаться на пользовательских приложениях, которые используют этот файл. Несмотря на то, что интерфейсы ядра изменяются чуть ли не ежеминутно, тем не менее когда вопрос касается пространства пользователя, Linux превращается в очень консервативную операционную систему, которая позволяет использование программ в течение длительного времени без необходимости их перекомпиляции.

В результате выполнения kern_mount():

Создается новое неименованное (anonymous) устройство установкой бита в unnamed_dev_in_use; если в этом массиве не окажется свободного бита, то kern_mount() вернется с ошибкой EMFILE.
Посредством get_empty_super() создается новая структура суперблока. Функция get_empty_super() проходит по списку суперблоков super_block в поисках свободного места, т.е. s->s_dev == 0. Если такового не обнаружилось, то резервируется память вызовом kmalloc(), с приоритетом GFP_USER. В get_empty_super() проверяется превышение максимально возможного количества суперблоков, так что в случае появления сбоев, при монтировании pipefs, можно попробовать подкорректировать /proc/sys/fs/super-max.
Вызывается метод pipe_fs_type->read_super() (т.е. pipefs_read_super()), который размещает корневой inode и dentry sb->s_root, а также записывает адрес &pipefs_ops в sb->s_op.
Затем вызывается add_vfsmnt(NULL, sb->s_root, "none"), которая размещает в памяти новую структуру vfsmount и включает ее в список vfsmntlist и sb->s_mounts.
В pipe_fs_type->kern_mnt заносится адрес новой структуры vfsmountи он же и возвращается в качестве результата. Причина, по которой возвращаемое значение является указателем на vfsmount состоит в том, что даже не смотря на флаг FS_SINGLE, файловая система может быть смонтирована несколько раз, вот только их mnt->mnt_sb будут указывать в одно и то же место.

После того как файловая система зарегистрирована и смонтирована, с ней можно работать. Точкой входа в файловую систему pipefs является системный вызов pipe(2), реализованный платформо-зависимой функцией sys_pipe(), которая в свою очередь передает управление платформо-независимой функции fs/pipe.c:do_pipe(). Взаимодействие do_pipe() с pipefs начинается с размещения нового inode вызовом get_pipe_inode(). В поле inode->i_sb этого inode заносится указатель на суперблок pipe_mnt->mnt_sb, в список i_fop файловых операций заносится rdwr_pipe_fops, а число "читателей" и "писателей" (содержится в inode->i_pipe) устанавливается равным 1. Причина, по которой имеется отдельное поле i_pipe, вместо хранения этой информации в приватной области fs-private, заключается в том, что каналы (pipes) и FIFO (именованные каналы) совместно используют один и тот же код, а FIFO могут существовать и в другой файловой системе, которые используют другие способы доступа в пределах этого объединения (fs-private) и могут работать, что называется "на удачу". Так, в ядре 2.2.x, все перестает работать, стоит только слегка изменить порядок следования полей в inode.

Каждый системный вызов pipe(2) увеличивает счетчик ссылок в структуре pipe_mnt.

В Linux каналы (pipes) не являются симметричными, т.е. с каждого конца канал имеет различный набор файловых операций file->f_op - read_pipe_fops и write_pipe_fops. При попытке записи со стороны канала, открытого на чтение, будет возвращена ошибка EBADF, то же произойдет и при попытке чтения с конца канала, открытого на запись.

3.7 Пример дисковой файловой системы: BFS

В качестве примера дисковой файловой системы рассмотрим BFS. Преамбула модуля BFS в файле fs/bfs/inode.c:

static DECLARE_FSTYPE_DEV(bfs_fs_type, "bfs", bfs_read_super);

static int __init init_bfs_fs(void)
{
        return register_filesystem(&bfs_fs_type);
}

static void __exit exit_bfs_fs(void)
{
        unregister_filesystem(&bfs_fs_type);
}

module_init(init_bfs_fs)
module_exit(exit_bfs_fs)

Макрокоманда DECLARE_FSTYPE_DEV() взводит флаг FS_REQUIRES_DEV в fs_type->flags, это означает, что BFS может быть смонтирована только с реального блочного устройства.

Функция инициализации модуля регистрирует файловую систему в VFS, а функция завершения работы модуля - дерегистрирует ее (эта функция компилируется только когда поддержка BFS включена в ядро в виде модуля).

После регистрации файловой системы, она становится доступной для монтирования, в процессе монтирования вызывается метод fs_type->read_super(), который выполняет следующие действия:

set_blocksize(s->s_dev, BFS_BSIZE): поскольку предполагается взаимодействие с уровнем блочного устройства через буферный кэш, следует выполнить некоторые действия, а именно указать размер блока и сообщить о нем VFS через поля s->s_blocksize и s->s_blocksize_bits.
bh = bread(dev, 0, BFS_BSIZE): читается нулевой блок с устройства s->s_dev. Этот блок является суперблоком файловой системы.
Суперблок проверяется на наличие сигнатуры ("магической" последовательности) BFS_MAGIC, если все в порядке, то он сохраняется в поле s->su_sbh (на самом деле это s->u.bfs_sb.si_sbh).
Далее создается новая битовая карта inode вызовом kmalloc(GFP_KERNEL) и все биты в ней сбрасываются в 0, за исключением двух первых, которые указывают на то, что 0-й и 1-й inode никогда не должны распределяться. Inode с номером 2 является корневым, установка соответствующего ему бита производится несколькими строками ниже, в любом случае файловая система должна получить корневой inode во время монтирования!
Инициализируется s->s_op, и уже после этого можно вызвать iget(), которая обратится к s_op->read_inode(). Она отыщет блок, который содержит заданный (по inode->i_ino и inode->i_dev) inode и прочитает его. Если при запросе корневого inode произойдет ошибка, то память, занимаемая битовой картой inode, будет освобождена, буфер суперблока возвратится в буферный кэш и в качестве результата будет возвращен "пустой" указатель - NULL. Если корневой inode был успешно прочитан, то далее размещается dentry с именем / и связывается с этим inode.
После этого последовательно считываются все inode в файловой системе и устанвливаются соответствующие им биты в битовой карте, а так же подсчитываются некоторые внутренние параметры, такие как смещение последнего inode и начало/конец блоков последнего файла. Все прочитанные inode возвращаются обратно в кэш inode вызовом iput() - ссылка на них не удерживается дольше, чем это необходимо.
Если файловая система была смонтирована как "read/write", то буфер суперблока помечается как "грязный" (измененный прим. перев.) и устанавливается флаг s->s_dirt (TODO: Для чего? Первоначально я сделал это потому, что это делалось в minix_read_super(), но ни minix ни BFS кажется не изменяют суперблок в read_super()).
Все складывается удачно, так что далее функция возвращает инициализированный суперблок уровню VFS, т.е. fs/super.c:read_super().

После успешного завершения работы функции read_super() VFS получает ссылку на модуль файловой системы через вызов get_filesystem(fs_type) в fs/super.c:get_sb_bdev() и ссылку на блочное устройство.

Рассмотрим, что происходит при выполнении опреаций ввода/вывода над файловой системой. Мы уже знаем, что inode читается функцией iget() и что они освобождаются вызовом iput(). Чтение inode приводит, кроме всего прочего, к установке полей inode->i_op и inode->i_fop; открытие файла вызывает копирование inode->i_fop в file->f_op.

Рассмотрим последовательность действий системного вызова link(2). Реализация системного вызова находится в fs/namei.c:sys_link():

Имена из пользовательского пространства копируются в пространство ядра функцией getname(), которая выполняет проверку на наличие ошибок.
Эти имена преобразуются в nameidata с помощью path_init()/path_walk(). Результат сохраняется в структурах old_nd и nd
Если old_nd.mnt != nd.mnt, то возвращается "cross-device link" EXDEV - невозможно установить ссылку между файловыми системами, в Linux это означает невозможность установить ссылку между смонтированными экземплярами одной файловой системы (или, особенно, между различными файловыми системами).
Для nd создается новый dentry вызовом lookup_create() .
Вызывается универсальная функция vfs_link(), которая проверяет возможность создания новой ссылки по заданному пути и вызывает метод dir->i_op->link(), который приводит нас в fs/bfs/dir.c:bfs_link().
Внутри bfs_link(), производится проверка - не делается ли попытка создать жесткую ссылку на директорию и если это так, то возвращается код ошибки EPERM. Это как стандарт (ext2).
Предпринимается попытка добавить новую ссылку в заданную директорию вызовом вспомогательной функции bfs_add_entry(), которая отыскивает неиспользуемый слот (de->ino == 0) и если находит, то записывает пару имя/inode в соответствующий блок и помечает его как "грязный".
Если ссылка была добавлена, то далее ошибки возникнуть уже не может, поэтому увеличивается inode->i_nlink, обновляется inode->i_ctime и inode помечается как "грязный" твк же как и inode приписанный новому dentry.

Другие родственные операции над inode, подобные unlink()/rename(), выполняются аналогичным образом, так что не имеет большого смысла рассматривать их в деталях.

3.8 Домены исполнения и двоичные форматы

Linux поддерживает загрузку пользовательских приложений с диска. Самое интересное, что приложения могут храниться на диске в самых разных форматах и реакция Linux на системные вызовы из программ тоже может быть различной (такое поведение является нормой в Linux) как того требует эмуляция форматов, принятых в других UNIX системах (COFF и т.п.), а так же эмуляция поведения системных вызовов (Solaris, UnixWare и т.п.). Это как раз то, для чего служит поддержка доменов исполнения и двоичных форматов.

Каждая задача в Linux хранит свою "индивидуальность" (personality) в task_struct (p->personality). В настоящее время существует (либо официально в ядре, либо в виде "заплат") поддержка FreeBSD, Solaris, UnixWare, OpenServer и многих других популярных операционных систем. Значение current->personality делится на две части:

старшие три байта - эмуляция "ошибок": STICKY_TIMEOUTS, WHOLE_SECONDS и т.п.
младший байт - соответствующая "индивидуальность" (personality), уникальное число.

Изменяя значение personality можно добиться изменения способа исполнения некоторых системных вызовов, например: добавление STICKY_TIMEOUT в current->personality приведет к тому, что последний аргумент (timeout), передаваемый в select(2) останется неизменным после возврата, в то время как в Linux в этом аргументе принято возвращать неиспользованное время. Некоторые программы полагаются на соответствующее поведение операционных систем (не Linux) и поэтому Linux предоставляет возможность эмуляции "ошибок" в случае, когда исходный код программы не доступен и такого рода поведение программ не может быть исправлено.

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

Реализация доменов исполнения находится в kernel/exec_domain.c и была полностью переписана, по сравнению с ядром 2.2.x. Список доменов исполнения и диапазоны "индивидуальностей", поддерживаемых доменами, можно найти в файле /proc/execdomains. Домены исполнения могут быть реализованы в виде подгружаемых модулей, кроме одного - PER_LINUX.

Интерфейс с пользователем осуществляется через системный вызов personality(2), который изменяет "индивидуальность" текущего процесса или возвращает значение current->personality, если в качестве аргумента передать значение несуществующей "индивидуальности" 0xffffffff. Очевидно, что поведение самого этого системного вызова не зависит от "индивидуальности" вызывающего процесса.

Действия по регистрации/дерегистрации доменов исполнения в ядре выполняются двумя функциями:

int register_exec_domain(struct exec_domain *): регистрирует домен исполнения, добавляя его в односвязный список exec_domains под защитой от записи read-write блокировкой exec_domains_lock. Возвращает 0 в случае успеха и ненулевое в случае неудачи.
int unregister_exec_domain(struct exec_domain *): дерегистрирует домен исполнения, удаляя его из списка exec_domains, опять же под read-write блокировкой exec_domains_lock полученной в режиме защиты от записи. Возвращает 0 в случае успеха.

Причина, по которой блокировка exec_domains_lock имеет тип read-write, состоит в том, что только запросы на регистрацию и дерегистрацию модифицируют список доменов, в то время как команда cat /proc/filesystems вызывает fs/exec_domain.c:get_exec_domain_list(), которой достаточен доступ к списку в режиме "только для чтения". Регистрация нового домена определяет "обработчик lcall7" и карту преобразования номеров сигналов. "Заплата" ABI расширяет концепцию доменов исполнения, включая дополнительную информацию (такую как опции сокетов, типы сокетов, семейство адресов и таблицы errno (коды ошибок)).

Обработка двоичных форматов реализована похожим образом, т.е. в виде односвязного списка форматов и определена в fs/exec.c. Список защищается read-write блокировкой binfmt_lock. Как и exec_domains_lock, блокировка binfmt_lock, в большинстве случаев, берется "только на чтение" за исключением регистрации/дерегистрации двоичного формата. Регистрация нового двоичного формата расширяет системный вызов execve(2) новыми функциями load_binary()/load_shlib() так же как и core_dump() . Метод load_shlib() используется только в устаревшем системном вызове uselib(2), в то время как метод load_binary() вызывается функцией search_binary_handler() из do_execve(), который и является реализацией системного вызова execve(2).

"Индивидуальность" процесса определяется во время загрузки двоичного формата соответствующим методом load_binary() с использованием некоторых эвристик. Например, формат UnixWare7 при создании помечается утилитой elfmark(1), которая заносит "магическую" последовательность 0x314B4455 в поле e_flags ELF-заголовка. Эта последовательность затем определяется во время загрузки приложения и в результате current->personality принимает значение PER_UW7. Если эта эвристика не подходит, то более универсальная обрабатывает пути интерпретатора ELF, подобно /usr/lib/ld.so.1 или /usr/lib/libc.so.1 для указания используемого формата SVR4 и personality принимает значение PER_SVR4. Можно написать небольшую утилиту, которая использовала бы возможности ptrace(2) Linux для пошагового прохождения по коду и принудительно запускать программы в любой "индивидуальности".

Поскольку "индивидуальность" (а следовательно и current->exec_domain) известна, то и системные вызовы обрабатываются соответственно. Предположим, что процесс производит системный вызов через шлюз lcall7. Такой вызов передает управление в точку ENTRY(lcall7) в файле arch/i386/kernel/entry.S, поскольку она задается в arch/i386/kernel/traps.c:trap_init(). После преобразования размещения стека, entry.S:lcall7 получает указатель на exec_domain из current и смещение обработчика lcall7 внутри exec_domain (которое жестко задано числом 4 в ассемблерном коде, так что вы не сможете изменить смещение поля handler в C-объявлении struct exec_domain) и переходит на него. Так на C это выглядело бы как:

static void UW7_lcall7(int segment, struct pt_regs * regs)
{
       abi_dispatch(regs, &uw7_funcs[regs->eax & 0xff], 1);
}

где abi_dispatch() - это обертка вокруг таблицы указателей на функции, реализующих системные вызовы для personality uw7_funcs.

4. Кэш страниц в Linux

В этой главе будет описан Linux 2.4 pagecache. Pagecache - это кэш страниц физической памяти. В мире UNIX концепция кэша страниц приобрела известность с появлением SVR4 UNIX, где она заменила буферный кэш, использовавшийся в операциях вода/вывода.

В SVR4 кэш страниц предназначен исключительно для хранения данных файловых систем и потому использует в качестве хеш-параметров структуру struct vnode и смещение в файле, в Linux кэш страниц разрабатывлся как более универсальный механизм, использущий struct address_space (описывается ниже) в качестве первого параметра. Поскольку кэш страниц в Linux тесно связан с понятием адресных пространств, для понимания принципов работы кэша страниц необходимы хотя бы основные знания об adress_spaces. Address_space - это некоторое программное обеспечение MMU (Memory Management Unit), с помощью которого все страницы одного объекта (например inode) отображаются на что-то другое (обычно на физические блоки диска). Структура struct address_space определена в include/linux/fs.h как:

     struct address_space {
                struct list_head        clean_pages;
                struct list_head        dirty_pages;
                struct list_head        locked_pages;
                unsigned long           nrpages;
                struct address_space_operations *a_ops;
                struct inode            *host;
                struct vm_area_struct   *i_mmap;
                struct vm_area_struct   *i_mmap_shared;
                spinlock_t              i_shared_lock;
 
        };

Для понимания принципов работы address_spaces, нам достаточно остановиться на некоторых полях структуры, указанной выше: clean_pages, dirty_pages и locked_pages являются двусвязными списками всех "чистых", "грязных" (измененных) и заблокированных страниц, которые принадлежат данному адресному пространству, nrpages - общее число страниц в данном адресном пространстве. a_ops задает методы управления этим объектом и host - указатель на inode, которому принадлежит данное адресное пространство - может быть NULL, например в случае, когда адресное пространство принадлежит программе подкачки (mm/swap_state.c,).

Назначение clean_pages, dirty_pages, locked_pages и nrpages достаточно прозрачно, поэтому более подробно остановимся на структуре address_space_operations, определенной в том же файле:

     struct address_space_operations {
                int (*writepage)(struct page *);
                int (*readpage)(struct file *, struct page *);
                int (*sync_page)(struct page *);
                int (*prepare_write)(struct file *, struct page *, unsigned, unsigned);
                int (*commit_write)(struct file *, struct page *, unsigned, unsigned);
                int (*bmap)(struct address_space *, long);
        };

Для понимания основ адресных пространств (и кэша страниц) следует рассмотреть ->writepage и ->readpage, а так же ->prepare_write и ->commit_write.

Из названий методов уже можно предположить действия, которые они выполняют, однако они требуют некоторого уточнения. Их использование в ходе операций ввода/вывода для более общих случаев дает хороший способ для их понимания. В отличие от большинства других UNIX-подобных операционных систем, Linux имеет набор универсальных файловых операций (подмножество операций SYSV над vnode) для передачи данных ввода/вывода через кэш страниц. Это означает, что при работе с данными отсутствует непосредственное обращение к файловой системе (read/write/mmap), данные будут читаться/записываться из/в кэша страниц (pagecache), по мере возможности. Pagecache будет обращаться к файловой системе либо когда запрошенной страницы нет в памяти, либо когда необходимо записать данные на диск в случае нехватки памяти.

При выполнении операции чтения, универсальный метод сначала пытается отыскать страницу по заданным inode/index.

hash = page_hash(inode->i_mapping, index);

Затем проверяется - существует ли заданная страница.

hash = page_hash(inode->i_mapping, index); page = __find_page_nolock(inode->i_mapping, index, *hash);

Если таковая отсутствует, то в памяти размещается новая страница и добавляется в кэш.

page = page_cache_alloc(); __add_to_page_cache(page, mapping, index, hash);

После этого страница заполняется данными с помощью вызова метода ->readpage.

error = mapping->a_ops->readpage(file, page);

И в заключение данные копируются в пользовательское пространство.

Для записи данных в файловую систему существуют два способа: один - для записи отображения (mmap) и другой - системный вызов write(2). Случай mmap наиболее простой, поэтому рассмотрим его первым. Когда пользовательское приложение вносит изменения в отображение, подсистема VM (Virtual Memory) помечает страницу.

SetPageDirty(page);

Поток ядра bdflush попытается освободить страницу, в фоне или в случае нехватки памяти, вызовом метода ->writepage для страниц, которые явно помечены как "грязные". Метод ->writepage выполняет запись содержимого страницы на диск и освобождает ее.

Второй способ записи намного более сложный. Для каждой страницы выполняется следующая последовательность действий (полный исходный код смотрите в mm/filemap.c:generic_file_write()).

page = __grab_cache_page(mapping, index, &cached_page); mapping->a_ops->prepare_write(file, page, offset, offset+bytes); copy_from_user(kaddr+offset, buf, bytes); mapping->a_ops->commit_write(file, page, offset, offset+bytes);

Сначала делается попытка отыскать страницу либо разместить новую, затем вызывается метод ->prepare_write, пользовательский буфер копируется в пространство ядра и в заключение вызывается метод ->commit_write. Как вы уже вероятно заметили ->prepare_write и ->commit_write существенно отличаются от ->readpage и ->writepage, потому что они вызываются не только во время физического ввода/вывода, но и всякий раз, когда пользователь модифицирует содержимое файла. Имеется два (или более?) способа обработки этой ситуации, первый - использование буферного кэша Linux, чтобы задержать физический ввод/вывод, устанавливая указатель page->buffers на buffer_heads, который будет использоваться в запросе try_to_free_buffers (fs/buffers.c) при нехватке памяти и широко использующийся в текущей версии ядра. Другой способ - просто пометить страницу как "грязная" и понадеяться на ->writepage, который выполнит все необходимые действия. В случае размера страниц в файловой системе меньшего чем PAGE_SIZE этот метод не работает.

5. Механизмы IPC

В этой главе описываются механизмы IPC (Inter Process Communication) - семафоры, разделяемая память и очередь сообщений, реализованные в ядре Linux 2.4. Данная глава разбита на 4 раздела. В первых трех разделах рассматривается реализация семафоров, очереди сообщений, и разделяемой памяти соответственно. В последнем разделе описывается набор общих, для всех трех вышеуказанных механизмов, функций и структур данных.

5.1 Семафоры

Функции, описываемые в данном разделе, реализуют механизм семафоров пользовательского уровня. Обратите внимание на то, что реализация пользовательских семафоров основывается на использовании блокировок и семафоров ядра. Во избежание неоднозначности в толковании под термином "семафор ядра" будут пониматься семафоры уровня ядра. Во всех других случаях под термином "семафор" следует понимать семафоры пользовательского уровня.

Семафоры. Интерфейс системных вызовов.

sys_semget()

Вызов sys_semget() защищен глобальным семафором ядра sem_ids.sem.

Для создания и инициализации нового набора семафоров вызывается функция newary(). В вызывающую программу возвращается ID нового набора семафоров.

Если через аогумент key передается существующий набор семафоров, вызывается функция поиска ipc_findkey() заданного набора. Перед возвратом ID проверяются права доступа вызывающей программы.

sys_semctl()

Для выполнения команд IPC_INFO, SEM_INFO, и SEM_STAT вызывает функцию semctl_nolock().

Для выполнения команд GETALL, GETVAL, GETPID, GETNCNT, GETZCNT, IPC_STAT, SETVAL, и SETALL вызывает функцию semctl_main() .

Для выполнения команд IPC_RMID и IPC_SET вызывает функцию semctl_down(). При этом выполняется захват глобального семафора ядра sem_ids.sem.

sys_semop()

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

Производится разбор всех, указанных пользователем, операций. В ходе разбора обслуживается счетчик для всех операций, для которых установлен флаг SEM_UNDO. Устанавливается флаг decrease, если какая либо операция выполняет уменьшение значения семафора, и устанавливается флаг alter, если значение любого из семафоров изменяется (т.е. увеличивается или уменьшается). Так же проверяется и номер каждого модифицируемого семафора.

Если установлен флаг SEM_UNDO для какой либо из операций, то в списке отыскивается структура отката текущей задачи (процесса), ассоциированной с данным набором семафоров. Если в ходе поиска в списке обнаруживается структура отката для несуществующего набора семафоров (un->semid == -1), то занимаемая память освобождается и структура исключается из списка вызовом функции freeundos(). Если структура для заданного набора семафоров не найдена, то вызовом alloc_undo() создается и инициализируется новая.

Для выполнения последовательности операций вызывается функция try_atomic_semop() с входным параметром do_undo равным нулю. Возвращаемое значение свидетельствует о выполнении последовательности операций - либо последовательность была выполнена, либо была ошибка при выполнении, либо последовательность не была выполнена потому что один из семафоров был заблокирован. Каждый из этих случаев описывается ниже:

Незаблокированные операции над семафорами

Функция try_atomic_semop() возвращает ноль, если вся последовательность операций была успешно выполнена. В этом случае вызывается update_queue(), которая проходит через очередь операций, ожидающих выполнения, для данного набора семафоров и активирует все ожидающие процессы, которые больше не нужно блокировать. На этом исполнение системного вызова sys_semop() завершается.

Ошибка при выполнении операций над семафорами

Отрицательное значение, возвращаемое функцией try_atomic_semop(), свидетельствует о возникновении ошибки. В этом случае ни одна из операций не выполняется. Ошибка возникает когда операция приводит к недопустимому значению семафора либо когда операция, помеченная как IPC_NOWAIT, не может быть завершена. Код ошибки возвращается в вызывающую программу.

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

Заблокированные операции над семафорами

Возвращаемое значение из try_atomic_semop(), равное 1 означает, что последовательность операций не была выполнена из-за того, что один из семафоров был заблокирован. В этом случае инициализируется новый элемент очереди sem_queue содержимым данной последовательности операций. Если какая либо из операций изменяет состояние семафора, то новый элемент добавляется в конец очереди, в противном случае новый элемент добавляется в начало очереди.

В поле semsleeping текущей задачи заносится указатель на очередь ожидания sem_queue. Задача переводится в состояние TASK_INTERRUPTIBLE и поле sleeper структуры sem_queue инициализируется указателем на текущую задачу. Далее снимается глобальная блокировка семафора и вызывается планировщик schedule(), чтобы перевести задачу в разряд "спящих".

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

Если набор семафоров был удален, то в вызывающую программу возвращается код ошибки EIDRM.
Если поле status в структуре sem_queue установлено в 1, то задача была разбужена для повторной попытки выполнения операций над семафорами. В этом случае повторно вызывается try_atomic_semop() для выполнения последовательности операций Если try_atomic_semop() вернула 1, то задача снова блокируется, как описано выше. Иначе возвращается 0 либо соответствующий код ошибки. Перед выходом из sys_semop() сбрасывается поле current->semsleeping и sem_queue удаляется из очереди. Если какая либо из операций производила изменения (увеличение или уменьшение), то вызывается update_queue(), которая проходит через очередь операций, ожидающих выполнения, для данного набора семафоров и активирует все ожидающие процессы, которые больше не нужно блокировать.
Если поле status в структуре sem_queue НЕ установлено в 1 и sem_queue не была удалена из очереди, то это означает, что задача была разбужена по прерыванию. В этом случае в вызывающую программу возвращается код ошибки EINTR. Перед возвратом сбрасывается поле current->semsleeping и sem_queue удаляется из очереди. А так же вызывается update_queue(), если какая либо из операций производила изменения.
Если поле status в структуре sem_queue НЕ установлено в 1, а sem_queue была удалена из очереди, то это означает, что заданная последовательность операций уже была выполнена в update_queue(). Поле status содержит либо 0, либо код ошибки, это значение и возвращается в вызывающую программу.

Структуры даных поддержки механизма семафоров

Следующие структуры данных используются исключительно для поддержки семафоров:

struct sem_array

/* По одной структуре данных для каждого набора семафоров в системе. */
struct sem_array {
    struct kern_ipc_perm sem_perm; /* права доступа .. см. ipc.h */
    time_t sem_otime;              /* время последнего обращения */
    time_t sem_ctime;              /* время последнего изменения */
    struct sem *sem_base;          /* указатель на первый семафор в массиве */
    struct sem_queue *sem_pending; /* операции, ожидающие исполнения */
    struct sem_queue **sem_pending_last; /* последняя ожидающая операция */
    struct sem_undo *undo;         /* список отката для данного массива * /
    unsigned long sem_nsems;       /* кол-во семафоров в массиве */
};

struct sem

/* По одной структуре для каждого семафора в системе. */
struct sem {
        int     semval;         /* текущее значение */
        int     sempid;         /* pid последней операции */
};

struct seminfo

struct  seminfo {
        int semmap;
        int semmni;
        int semmns;
        int semmnu;
        int semmsl;
        int semopm;
        int semume;
        int semusz;
        int semvmx;
        int semaem;
};

struct semid64_ds

struct semid64_ds {
        struct ipc64_perm sem_perm; /* права доступа .. см. ipc.h */
        __kernel_time_t sem_otime;  /* время последнего обращения */
        unsigned long   __unused1;  
        __kernel_time_t sem_ctime;  /* время последнего изменения */
        unsigned long   __unused2;
        unsigned long   sem_nsems;  /* кол-во семафоров в массиве */
        unsigned long   __unused3;
        unsigned long   __unused4;
};

struct sem_queue

/* По одной очереди на каждый ожидающий процесс в системе. */
struct sem_queue {
        struct sem_queue *      next;    /* следующий элемент очереди */
        struct sem_queue **     prev;    /* предыдующий элемент очереди, *(q->prev) == q */
        struct task_struct*     sleeper; /* этот процесс */
        struct sem_undo *       undo;    /* структура откатов */
        int                     pid;     /* pid процесса */
        int                     status;  /* результат выполнения операции */
        struct sem_array *      sma;     /* массив семафоров для выполнения операций */
        int                     id;      /* внутренний sem id */
        struct sembuf *         sops;    /* массив ожидающих операций */
        int                     nsops;   /* кол-во операций */
        int                     alter;   /* признак изменения семафора */
};

struct sembuf

/* системный вызов semop берет массив отсюда. */
struct sembuf {
        unsigned short  sem_num;        /* индекс семафора в массиве */
        short           sem_op;         /* операция */
        short           sem_flg;        /* флаги */
};

struct sem_undo

/* Каждая задача имеет список откатов. Откаты выполняются автоматически
 * по завершении процесса.
 */
struct sem_undo {
        struct sem_undo *       proc_next;      /* следующий элемент списка для данного процесса */
        struct sem_undo *       id_next;        /* следующий элемент в данном наборе семафоров */
        int                     semid;          /* ID набора семафоров */
        short *                 semadj;         /* массив изменений, по одному на семафор */
};

Функции для работы с семафорами

Следующие функции используются исключительно для поддержки механизма семафоров:

newary()

newary() обращается к ipc_alloc() для распределения памяти под новый набор семафоров. Она распределяет объем памяти достаточный для размещения дескриптора набора и всего набора семафоров. Распределенная память очищается и адрес первого элемента набора семафоров передается в ipc_addid(). Функция ipc_addid() резервирует память под массив элементов нового набора семафоров и инициализирует ( struct kern_ipc_perm) набор. Глобальная переменная used_sems увеличивается на количество семафоров в новом наборе и на этом инициализация данных ( struct kern_ipc_perm) для нового набора завершается. Дополнительно выполняются следующие действия:

В поле sem_base заносится адрес первого семафора в наборе.
Очередь sem_pending объявляетяс пустой.

Все операции, следующие за вызовом ipc_addid(), выполняются под глобальной блокировкой семафоров. После снятия блокировки вызывается ipc_buildid() (через sem_buildid()). Эта функция создает уникальный ID (используя индекс дескриптора набора семафоров), который и возвращается в вызывающую программу.

freeary()

Функция freeary() вызывается из semctl_down() для выполнения действий, перечисленных ниже. Вызов функции осуществляется под глобальной блокировкой семафоров, возврат управления происходит со снятой блокировкой.

Вызывается ipc_rmid() (через "обертку" sem_rmid()), чтобы удалить ID набора семафоров и получить указатель на набор семафоров.
Аннулируется список откатов для данного набора семафоров
Все ожидающие процессы пробуждаются, чтобы получить код ошибки EIDRM.
Общее количество семафоров уменьшается на количество семафоров в удаляемом наборе.
Память, занимаемая набором семафоров, освобождается.

semctl_down()

Функция semctl_down() предназначена для выполнения операций IPC_RMID и IPC_SET системного вызова semctl(). Перед выполнением этих операций проверяется ID набора семафоров и права доступа. Обе эти операции выполняются под глобальной блокировкой семафоров.

IPC_RMID

Операция IPC_RMID вызывает freeary() для удаления набора семафоров.

IPC_SET

Операция IPC_SET изменяет элементы uid, gid, mode и ctime в наборе семафоров.

semctl_nolock()

Функция semctl_nolock() вызывается из sys_semctl() для выполнения операций IPC_INFO, SEM_INFO и SEM_STAT.

IPC_INFO и SEM_INFO

Операции IPC_INFO и SEM_INFO заполняют временный буфер seminfo статическими данными. Затем под глобальной блокировкой семафора ядра sem_ids.sem заполняются элементы semusz и semaem структуры seminfo в соответствии с требуемой операцией (IPC_INFO или SEM_INFO) и в качестве результата возвращается максимальный ID.

SEM_STAT

Операция SEM_STAT инициализирует временный буфер semid64_ds. На время копирования значений sem_otime, sem_ctime, и sem_nsems в буфер выполняется глобальная блокировка семафора. И затем данные копируются в пространство пользователя.

semctl_main()

Функция semctl_main() вызывается из sys_semctl() для выполнения ряда операций, которые описаны ниже. Перед выполнением операций, semctl_main() блокирует семафор и проверяет ID набора семафоров и права доступа. Перед возвратом блокировка снимается.

GETALL

Операция GETALL загружает текущие значения семафора во временный буфер ядра и затем копирует его в пространство пользователя. При небольшом объеме данных, временный буфер размещается на стеке, иначе блокировка временно сбрасывается, чтобы распределить в памяти буфер большего размера. Копирование во временный буфер производится под блокировкой.

SETALL

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

Информация копируется в набор семафоров.
Очищается очередь откатов для заданного набора семафоров.
Устанавливается значение sem_ctime для набора семафоров.
Вызывается функция update_queue() , которая проходит по списку ожидающих операций в поисках задач, которые могут быть завершены в результате выполнения операции SETALL. Будятся любые ожидающие задачи, которые больше не нужно блокировать.

IPC_STAT

Операция IPC_STAT копирует значения sem_otime, sem_ctime и sem_nsems во временный буфер на стеке. После снятия блокировки данные копируются в пользовательское пространство.

GETVAL

Операция GETVAL возвращает значение заданного семафора.

GETPID

Операция GETPID возвращает pid последней операции, выполненной над семафором.

GETNCNT

Операция GETNCNT возвращает число процессов, ожидающих на семафоре, когда тот станет меньше нуля. Это число подсчитывается функцией count_semncnt().

GETZCNT

Операция GETZCNT возвращает число процессов, ожидающих на семафоре, когда тот станет равным нулю. Это число подсчитывается функцией count_semzcnt().

SETVAL

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

В очереди отката отыскиваются любые корректировки данного семафора и эти корректировки сбрасываются в ноль.
Значение семафора устанавливается в заданное.
Корректируется значение sem_ctime .
Вызывается функция update_queue(), которая проходит по очереди ожидающих операций в поисках тех из них, которые могут быть завершены в результате выполнения операции SETVAL. Все задачи которые оказываются больше незаблокированными - пробуждаются.

count_semncnt()

count_semncnt() возвращает число процессов, ожидающих на семафоре, когда тот станет меньше нуля.

count_semzcnt()

count_semzcnt() возвращает число процессов, ожидающих на семафоре, когда тот станет равным нулю.

update_queue()

update_queue() проходит по очереди ожидающих операций заданного набора семафоров и вызывает try_atomic_semop() для каждой последовательности операций. Если статус элемента очереди показывает, что заблокированная задача уже была разбужена, то такой элемент пропускается. В качестве аргумента do_undo в функцию try_atomic_semop() передается флаг q-alter, который указывает на то, что любые изменяющие операции необходимо "откатить" перед возвратом управления.

Если последовательность операций заблокирована, то update_queue() возвращает управление без внесения каких-либо изменений.

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

Если последовательность операций не предполагает внесения изменений, то в качестве аргумента do_undo в функцию try_atomic_semop() передается ноль. Если выполнение этих операций увенчалось успехом, то они считаются выполненными и удаляются из очереди. Ожидающая задача активируется, а в поле status ей передается признак успешного завершения операций.

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

try_atomic_semop()

Функция try_atomic_semop() вызывается из sys_semop() и update_queue() и пытается выполнить каждую из операций в последовательности.

Если была встречена заблокированная операция, то процесс исполнения последовательности прерывается и все операции "откатываются". Если последовательность имела флаг IPC_NOWAIT, то возвращается код ошибки -EAGAIN. Иначе возвращается 1 для индикации того, что последовательность операций заблокирована.

Если значение семафора вышло за рамки системных ограничений, то выполняется "откат" всех операций и возвращается код ошибки -ERANGE.

Если последовательность операций была успешно выполнена и при этом аргумент do_undo не равен нулю, то выполняется "откат" всех операций и возвращается 0. Если аргумент do_undo равен нулю, то результат операций остается в силе и обновляется поле sem_otime.

sem_revalidate()

Функция sem_revalidate() вызывается, когда глобальная блокировка семафора временно была снята и необходимо снова ее получить. Вызывается из semctl_main() и alloc_undo(). Производит проверку ID семафора и права доступа, в случае успеха выполняет глобальную блокировку семафора.

freeundos()

Функция freeundos() проходит по списку "откатов" процесса в поисках заданной структуры. Если таковая найдена, то она изымается из списка и память, занимаемая ею, освобождается. В качестве результата возвращается указатель на следующую структуру "отката"в списке.

alloc_undo()

Вызов функции alloc_undo() должен производиться под установленной глобальной блокировкой семафора. В случае возникновения ошибки - функция завершает работу со снятой блокировкой.

Перед тем как вызовом kmalloc() распределить память под структуру sem_undo и массив корректировок, блокировка снимается. Если память была успешно выделена, то она восстанавливается вызовом sem_revalidate().

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

sem_exit()

Функция sem_exit() вызывается из do_exit() и отвечает за выполнение всех "откатов" по завершении процесса.

Если процесс находится в состоянии ожидания на семафоре, то он удаляется из списка sem_queue при заблокированном семафоре.

Производится просмотр списка "откатов" текущего процесса и для каждого элемента списка выполняются следующие действия:

Проверяется структура "отката" и ID набора семафоров.
В списке "откатов" соответствующего набора семафоров отыскиваются ссылки на структуры, которые удаляются из списка.
К набору семафоров применяются корректировки из структуры "отката".
Обновляется поле sem_otime в наборе семафоров.
Вызывается update_queue(), которая просматривает список отложенных операций и активирует задачи, которые могут быть разблокированы в результате "отката".
Память, занимаемая структурой, освобождается.

По окончании обработки списка очищается поле current->semundo.

5.2 Очереди сообщений

Интерфейс системных вызовов

sys_msgget()

На входе в sys_msgget() захватывается глобальный семафор очереди сообщений ( msg_ids.sem).

Для создания новой очереди сообщений вызывается функция newque(), которая создает и инициализирует новую очередь и возвращает ID новой очереди.

Если значение параметра key представляет существующую очередь, то вызывается ipc_findkey() для поиска соответствующего индекса в глобальном массиве дескрипторов очередей сообщений (msg_ids.entries). перед возвратом ID очереди производится проверка параметров и прав доступа. И поиск и проверки выполняются под блокировкой (msg_ids.ary).

sys_msgctl()

Функции sys_msgctl() передаются следующие параметры: ID очереди сообщений (msqid), код операции (cmd) и указатель на буфер в пользовательском пространстве типа msgid_ds (buf). Функция принимает шесть кодов операций: IPC_INFO, MSG_INFO,IPC_STAT, MSG_STAT, IPC_SET и IPC_RMID. После проверки ID очереди и кода операции выполняются следующие действия:

IPC_INFO ( или MSG_INFO)

Глобальная информация очереди сообщений копируется в пользовательское пространство.

IPC_STAT ( или MSG_STAT)

Инициализируется временный буфер типа struct msqid64_ds и выполняется глобальная блокировка очереди сообщений. После проверки прав доступа вызывающего процесса во временный буфер записывается информация о заданной очереди и глобальная блокировка очереди сообщений освобождается. Содержимое буфера копируется в пользовательское пространство вызовом copy_msqid_to_user().

IPC_SET

Пользовательские данные копируются через вызов copy_msqid_to_user(). Производится захват глобального семафора очереди сообщений и устанавливается блокировка очереди, которые в конце отпускаются. После проверки ID очереди и прав доступа текущего процесса, производится обновление информации. Далее, вызовом expunge_all() и ss_wakeup() активируются все процессы-получатели и процессы-отправители, находящиеся в очередях ожидания msq->q_receivers и msq->q_senders соответственно.

IPC_RMID

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

sys_msgsnd()

Функция sys_msgsnd() принимает через входные параметры ID очереди сообщений (msqid), указатель на буфер типа struct msg_msg (msgp), размер передаваемого сообщения (msgsz) и флаг - признак разрешения перехода процесса в режим ожидания (msgflg). Каждая очередь сообщений имеет две очереди ожидания для процессов и одну очередь ожидающих сообщений. Если в очереди ожидания имеется процесс, ожидающий данное сообщение (msgp), то это сообщение передается непосредственно ожидающему процессу, после чего процесс-получатель "пробуждается". В противном случае производится проверка - достаточно ли места в очереди ожидающих сообщений и если достаточно, то сообщение сохраняется в этой очереди. Если же места недостаточно, то процесс-отправитель ставится в очередь ожидания. Более подробное освещение этих действий приводится ниже:

Производится проверка адреса пользовательского буфера и типа сообщения, после чего содержимое буфера копируется вызовом load_msg() во временный буфер msg типа struct msg_msg. Инициализируются поле типа сообщения и поле размера сообщения.
Выполняется глобальная блокировка очереди сообщений и по ID очереди отыскивается ее дескриптор. Если такой очереди не было найдено, то в вызывающую программу возвращается код ошибки EINVAL.
В функции ipc_checkid() (вызывается из msg_checkid()) проверяется ID очереди сообщений и права доступа процесса вызовом ipcperms().
Производится проверка - достаточно ли места в очереди ожидающих сообщений для помещения туда данного сообщения. Если места недостаточно, то выполняются следующие действия:
1. Если установлен флаг IPC_NOWAIT (в msgflg) то глобальная блокировка очереди сообщений снимается, память, занимаемая сообщением, освобождается и возвращается код ошибки EAGAIN.
2. Вызовом ss_add() текущий процесс помещается в очередь ожидания для процессов-отправителей. Так же снимается блокировкаи вызывается планировщик schedule() который переведет процесс в состояние "сна".
3. После "пробуждения" снова выполняется глобальная блокировка очереди сообщений и проверяется ID очереди сообщений. Если во время "сна" очередь была удалена, то процессу возвращается признак ERMID.
4. Если для данного процесса имеются какие либо сигналы, ожидающие обработки, то вызовом ss_del() процесс изымается из очереди ожидания для процессов-отправителей, блокировка снимается, вызывается free_msg() для освобождения буфера сообщения и процессу возвращается код EINTR. Иначе осуществляется переход обратно (к п.3) на выполнение необходимых проверок.
Для передачи сообщения напрямую процессу-получателю вызывается pipelined_send() .
Если процессов-получателей, ожидающих данное сообщение, не было обнаружено, то сообщение msg помещается в очередь ожидающих сообщений (msq->q_messages). Обновляются поля q_cbytes и q_qnum в дескрипторе очереди сообщений, а так же глобальные переменные msg_bytes и msg_hdrs, содержащие в себе общий объем сообщений в байтах и общее количество сообщений.
Если сообщение было благополучно передано процессу-получателю либо поставлено в очередь, то обновляются поля q_lspid и q_stime в дескрипторе очереди и освобождается глобальная блокировка.

sys_msgrcv()

На вход функции sys_msgrcv() передаются ID очереди (msqid), указатель на буфер типа msg_msg (msgp), предполагаемый размер сообщения (msgsz), тип сообщения (msgtyp) и флаги (msgflg). Функция, по очереди ожидающих сообщений, ищет сообщение с заданным типом и первое же найденное сообщение копирует в пользовательский буфер. Если сообщения с заданным типом не обнаружено, то процесс-получатель заносится в очередь ожидания для процессов-получателей и остается там до тех пор, пока не будет получено ожидаемое сообщение. Более подробное описание действий функции sys_msgrcv() приводится ниже:

В первую очередь вызывается функция convert_mode(), которая устанавливает режим поиска, исходя из значения msgtyp. Далее выполняется глобальная блокировка очереди сообщений и находится дескриптор очереди по заданному ID. Если искомая очередь сообщений не найдена, то возвращается код ошибки EINVAL.
Проверяются права доступа текущего процесса.
Для каждого сообщения, начиная с первого, в очереди ожидающих сообщений вызывается testmsg(), которая проверяет тип сообщения на соответствие заданному. Поиск продолжается до тех пор пока искомое сообщение не будет найдено либо пока не будет встречен конец очереди. Если режим поиска задан как SEARCH_LESSEQUAL, то результатом поиска будет первое же встретившееся сообщение с типом равным или меньшим msgtyp.
Если сообщение, удовлетворяющее критериям поиска, было найдено, то далее выполняются следующие действия:
1. Если размер сообщения больше чем ожидаемый и установлен флаг MSG_NOERROR, то глобальная блокировка снимается и в вызывающий процесс передается код E2BIG.
2. Сообщение удаляется из очереди ожидающих сообщений и обновляются статистики очереди сообщений.
3. Активируются процессы, находящиеся в очереди ожидания для процессов-отправителей. Удаление сообщения из очереди на предыдущем шаге делает возможным продолжить работу одному из процессов-отправителей. Переход к выполнению заключительных операций (к п. 10)
Если сообщение не было найдено, то проверяется msgflg. Если установлен флаг IPC_NOWAIT, то глобальная блокировка снимается и вызывающему процессу возвращается код ENOMSG. В противном случае процесс помещается в очередь ожидания для процессов-получателей:
1. В памяти размещается новая структура msg_receiver msr и добавляется в начало очереди ожидания.
2. В поле r_tsk в msr заносится указатель на текущий процесс.
3. В поле r_msgtype и r_mode заносятся ожидаемый тип сообщения и режим поиска соответственно.
4. Если установлен флаг MSG_NOERROR, то в поле r_maxsize заносится значение из msgsz, в противном случае - значение INT_MAX.
5. В поле r_msg заносится признак того, что сообщение не найдено.
6. После завершения инициализации, процесс приобретает статус TASK_INTERRUPTIBLE, глобальная блокировка очереди сообщений снимается и вызывается планировщик schedule().
После активизации ожидающего процесса сразу же проверяется поле r_msg. Это поле содержит либо сообщение переданное напрямую, либо код ошибки. Если поле содержит сообщение то далее переходим к заключительным операциям (к п. 10). В противном случае - опять выполняется глобальная блокировка.
После того как блокировка установлена, поле r_msg проверяется еще раз. Если в процессе установки блокировки было получено сообщение, то производится переход к заключительным операциям (к п. 10).
Если поле r_msg осталось без изменений, то, следовательно, процесс был активирован для выполнения повторной попытки получить сообщение. Проверяется наличие необработанных сигналов для данного процесса и если таковые имеются, то глобальная блокировка снимается и процессу возвращается код EINTR. Иначе - производится повторная попытка получить сообщение.
Если поле r_msg содержит код ошибки, то снимается глобальная блокировка и процессу передается ошибка.
После проверки адреса пользовательского буфера msp, тип сообщения записывается в mtype и содержимое сообщения копируется в поле mtext функцией store_msg(). И в заключение освобождается память вызовом функции free_msg().

Структуры очередей сообщений

Структуры данных механизма очередей сообщений определены в msg.c.

struct msg_queue

/* по одной структуре msq_queue на каждую очередь сообщений в системе */
struct msg_queue {
        struct kern_ipc_perm q_perm;
        time_t q_stime;                 /* время последнего вызова msgsnd */
        time_t q_rtime;                 /* время последнего вызова msgrcv */
        time_t q_ctime;                 /* время последнего изменения */
        unsigned long q_cbytes;         /* текущий размер очереди в байтах */
        unsigned long q_qnum;           /* количество сообщений в очереди */
        unsigned long q_qbytes;         /* максимальный размер очереди в байтах */
        pid_t q_lspid;                  /* pid последнего процесса вызвавшего msgsnd */
        pid_t q_lrpid;                  /* pid последнего процесса-получателя */

        struct list_head q_messages;
        struct list_head q_receivers;
        struct list_head q_senders;
};

struct msg_msg

/* по одной структуре на каждое сообщение */
struct msg_msg {
        struct list_head m_list;
        long  m_type;
        int m_ts;           /* размер сообщения */
        struct msg_msgseg* next;
        /* Далее следует само сообщение */
};

struct msg_msgseg

/* сегмент сообщения на каждое сообщение */
struct msg_msgseg {
        struct msg_msgseg* next;
        /* Далее следует остальная часть сообщения */
};

struct msg_sender

/* по одной структуре msg_sender на каждый ожидающий процесс-отправитель */
struct msg_sender {
        struct list_head list;
        struct task_struct* tsk;
};

struct msg_receiver

/* по одной структуре msg_receiver на каждый ожидающий процесс-получатель */
struct msg_receiver {
        struct list_head r_list;
        struct task_struct* r_tsk;

        int r_mode;
        long r_msgtype;
        long r_maxsize;

        struct msg_msg* volatile r_msg;
};

struct msqid64_ds

struct msqid64_ds {
        struct ipc64_perm msg_perm;
        __kernel_time_t msg_stime;      /* время последнего вызова msgsnd */
        unsigned long   __unused1;
        __kernel_time_t msg_rtime;      /* время последнего вызова msgrcv */
        unsigned long   __unused2;
        __kernel_time_t msg_ctime;      /* время последнего изменения */
        unsigned long   __unused3;
        unsigned long  msg_cbytes;      /* текущий размер очереди в байтах */
        unsigned long  msg_qnum;        /* количество сообщений в очереди */
        unsigned long  msg_qbytes;      /* максимальный размер очереди в байтах */
        __kernel_pid_t msg_lspid;       /* pid процесса последним вызвавшего msgsnd */
        __kernel_pid_t msg_lrpid;       /* pid последнего процесса-получателя */
        unsigned long  __unused4;
        unsigned long  __unused5;
};

struct msqid_ds

struct msqid_ds {
        struct ipc_perm msg_perm;
        struct msg *msg_first;          /* первое сообщение в очереди, не используется  */
        struct msg *msg_last;           /* последнее сообщение в очереди, не используется*/
        __kernel_time_t msg_stime;      /* время последнего вызова msgsnd */
        __kernel_time_t msg_rtime;      /* время последнего вызова msgrcv */
        __kernel_time_t msg_ctime;      /* время последнего изменения */
        unsigned long  msg_lcbytes;     /* Используется для временного хранения 32 бит */
        unsigned long  msg_lqbytes;     /* то же */
        unsigned short msg_cbytes;      /* текущий размер очереди в байтах */
        unsigned short msg_qnum;        /* количество сообщений в очереди */
        unsigned short msg_qbytes;      /* максимальный размер очереди в байтах */
        __kernel_ipc_pid_t msg_lspid;   /* pid процесса последним вызвавшего msgsnd */
        __kernel_ipc_pid_t msg_lrpid;   /* pid последнего процесса-получателя */
};

msg_setbuf

struct msq_setbuf {
        unsigned long   qbytes;
        uid_t           uid;
        gid_t           gid;
        mode_t          mode;
};

Функции поддержки механизма очередей сообщений

newque()

Функция newque() размещает в памяти новый дескриптор очереди сообщений (struct msg_queue) и вызывает ipc_addid(), которая резервирует элемент массива очередей сообщений за новым дескриптором. Дескриптор очереди сообщений инициализируется следующим образом:

Инициализируется структура kern_ipc_perm.
В поля q_stime и q_rtime дескриптора заносится число 0. В поле q_ctime заносится CURRENT_TIME.
Максимальный размер очереди в байтах (q_qbytes) устанавливается равным MSGMNB, текущий размер очереди в байтах (q_cbytes) устанавливается равным нулю.
Очередь ожидающих сообщений (q_messages), очередь ожидания процессов-получателей (q_receivers) и очередь ожидания процессов-отправителей (q_senders) объявляются пустыми.

Все действия, следующие за вызовом ipc_addid(), выполняются под глобальной блокировкой очереди сообщений. После снятия блокировки вызывается msg_buildid(), которая является отображением ipc_buildid(). Функция ipc_buildid() возвращает уникальный ID очереди сообщений, построенный на основе индекса дескриптора. Результатом работы newque() является ID очереди.

freeque()

Функция freeque() предназначена для удаления очереди сообщений. Функция полагает, что блокировка очереди сообщений уже выполнена. Она освобождает все ресурсы, связанные с данной очередью. Сначала вызывается ipc_rmid() (через msg_rmid()) для удаления дескриптора очереди из массива дескрипторов. Затем вызывается expunge_all для активизации процессов-получателей и ss_wakeup() для активизации процессов-отправителей, находящихся в очередях ожидания. Снимается блокировка очереди. Все сообщения из очереди удаляются и освобождается память, занимаемая дескриптором очереди.

ss_wakeup()

Функция ss_wakeup() активизирует все процессы-отправители, стоящие в заданной очереди ожидания. Если функция вызывается из freeque(), то процессы исключаются из очереди ожидания.

ss_add()

Функция ss_add() принимает в качестве входных параметров указатель на дескриптор очереди сообщений и указатель на структуру msg_sender. Она заносит в поле tsk указатель на текущий процесс, изменяет статус процесса на TASK_INTERRUPTIBLE после чего вставляет структуру msg_sender в начало очереди ожидания процессов-отправителей заданной очереди сообщений.

ss_del()

Удаляет процесс-отправитель из очереди ожидания.

expunge_all()

В функцию expunge_all() передаются дескриптор очереди сообщений (msq) и целочисленное значение (res) которое определяет причину активизации процесса-получателя. Для каждого процесса-получателя из соответствующей очереди ожидания в поле r_msg заносится число res, после чего процесс активируется. Эта функция вызывается в случае ликвидации очереди сообщений или в случае выполнения операций управления очередью сообщений.

load_msg()

Всякий раз, когда процесс передает сообщение, из функции sys_msgsnd(), вызывается load_msg(), которая копирует сообщение из пользовательского пространства в пространство ядра. В пространстве ядра сообщение представляется как связный список блоков данных. В первом блоке размещается структура msg_msg. Размер блока данных, ассоциированного со структурой msg_msg, ограничен числом DATA_MSG_LEN. Блок данных и структура размещаются в непрерывном куске памяти, который не может быть больше одной страницы памяти. Если все сообщение не умещается в первый блок, то в памяти размещаются дополнительные блоки и связываются в список. Размер дополнительных блоков ограничен числом DATA_SEG_LEN и каждый из низ включает в себя структуру msg_msgseg) и связанный блок данных. Блок данных и структура msg_msgseg размещаются в непрерывном куске памяти, который не может быть больше одной страницы памяти. В случае успеха функция возвращает адрес новой структуры msg_msg.

store_msg()

Функция store_msg() вызывается при передаче сообщения в пользовательское пространство. Данные, описываемые структурами msg_msg и msg_msgseg последовательно копируются в пользовательский буфер.

free_msg()

Функция free_msg() освобождает память, занятую сообщением (структурой msg_msg и сегментами сообщения).

convert_mode()

convert_mode() вызывается из sys_msgrcv(). В качестве входных параметров получает указатель на тип сообщения (msgtyp) и флаг (msgflg). Возвращает режим поиска отталкиваясь от значения msgtyp и msgflg. Если в качестве msgtyp передан NULL, то возвращается SEARCH_ANY. Если msgtyp меньше нуля, то в msgtyp заносится абсолютное значение msgtyp и возвращается SEARCH_LESSEQUAL. Если в msgflg установлен флаг MSG_EXCEPT, то возвращается SEARCH_NOTEQUAL, иначе - SEARCH_EQUAL.

testmsg()

Функция testmsg() проверяет сообщение на соответсвтвие заданным критериям. Возвращает 1, если следующие условия соблюдены:

Режим поиска - SEARCH_ANY.
Режим поиска - SEARCH_LESSEQUAL и сообщение имеет тип меньший либо равный требуемому.
Ркжим поиска - SEARCH_EQUAL и тип сообщения равен требуемому.
Режим поиска - SEARCH_NOTEQUAL и тип сообщения не равен требуемому.

pipelined_send()

pipelined_send() позволяет процессам передать сообщение напрямую процессам-получателям минуя очередь ожидания. Вызывает testmsg() в процессе помска процесса-получателя, ожидающего данное сообщение. Если таковой найден, то он удаляется из очереди ожидания для процессов-получателей и активируется. Сообщение передается процессу через поле r_msg получателя. Если сообщение было передано получателю, то функция >pipelined_send() возвращает 1. Если процесса-получателя для данного сообщения не нашлось, то возвращается 0.

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

copy_msqid_to_user()

copy_msqid_to_user() копирует содержимое буфера ядра в пользовательский буфер. На входе получает пользовательский буфер, буфер ядра типа msqid64_ds и флаг версии IPC. Если флаг имеет значение IPC_64 то копирование из буфера ядра в пользовательский буфер производится напрямую, в противном случае инициализируется временный буфер типа msqid_ds и данные из буфера ядра переносятся во временный буфер, после чего содержимое временного буфера копируется в буфер пользователя.

copy_msqid_from_user()

Функция copy_msqid_from_user() получает на входе буфер ядра для сообщения типа struct msq_setbuf, пользовательский буфер и флаг версии IPC. В случае IPC_64, copy_from_user() производит копирование данных из пользовательского буфера во временный буфер типа msqid64_ds, после этого заполняются поля qbytes,uid, gid и mode в буфере ядра в соответствии со значениями в промежуточном буфере. В противном случае, в качестве временного буфера используется struct msqid_ds.

5.3 Разделяемая память

Интерфейс системных вызовов

sys_shmget()

Вызов sys_shmget() регулируется глобальным семаформ разделяемой памяти.

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

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

sys_shmctl()

IPC_INFO

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

SHM_INFO

На время сбора статистической информации по разделяемой памяти, производится захват глобального семафора и глобальной блокировки разделяемой памяти. Для подсчета количества страниц, резмещенных резидентно в памяти и количества страниц на устройстве свопинга, вызывается shm_get_stat(). Дополнительно подсчитываются общее количество страниц разделяемой памяти и количество используемых сегментов. Количество swap_attempts и swap_successes жестко зашито в 0. Эти статистики заносятся во временный буфер shm_info и затем копируются в пользовательское пространство вызывающего приложения.

SHM_STAT, IPC_STAT

Для выполнения SHM_STAT и IPC_STAT инициализируется временный буфер типа struct shmid64_ds и выполняется глобальная блокировка разделяемой памяти.

Для случая SHM_STAT, параметр ID сегмента разделяемой памяти трактуется как простой индекс (т.е. как число в диапазоне от 0 до N, где N - количество зарегистрированных ID в системе). После проверки индекса вызывается ipc_buildid() (через shm_buildid()) для преобразования индекса в ID разделяемой памяти, который в данном случае и будет возвращаемым значением. Примечательно, что это обстоятельство не документировано, но используется для поддержки программы ipcs(8).

Для случая IPC_STAT, параметр ID сегмента разделяемой памяти трактуется как нормальный ID, сгенерированный вызовом shmget(). Перед продолжением работы ID проверяется на корректность. В данном случае в качестве результата будет возвращен 0.

Для обоих случаев SHM_STAT и IPC_STAT, проверяются права доступа вызывающей программы. Требуемые статистики загружаются во временный буфер и затем передаются в вызывающую программу.

SHM_LOCK, SHM_UNLOCK

После проверки прав доступа выполняется глобальная блокировка разделяемой памяти и проверяется ID сегмента разделяемой памяти. Для выполнения обеих операций вызывается shmem_lock(). Параметры, передаваемые функции shmem_lock() однозначно определяют выполняемую операцию.

IPC_RMID

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

IPC_SET

После проверки ID сегмента разделяемой памяти и прав доступа, uid, gid и флаги mode сегмента модифицируются данными пользователя. Так же обновляется и поле shm_ctime. Все изменения производятся после захвата глобального семафора разделяемой памяти и при установленной блокировке.

sys_shmat()

Функция sys_shmat() принимает в качестве параметров ID сегмента разделяемой памяти, адрес по которому должен быть присоединен сегмент (shmaddr) и флаги, котроые описаны ниже.

Если параметр shmaddr не нулевой и установлен флаг SHM_RND, то shmaddr округляется "вниз" до ближайшего кратного SHMLBA. Если shmaddr не кратен SHMLBA и флаг SHM_RND не установлен, то возвращается код ошибки EINVAL.

Производится проверка прав доступа вызывающего процесса, после чего поле shm_nattch сегмента разделяемой памяти увеличивается на 1. Увеличение этого поля гарантирует сегмент разделяемой памяти от ликвидации, пока он присоединен к сегменту памяти процесса. Эти операции выполняются после установки глобальной блокировки разделяемой памяти.

Вызывается функция do_mmap(), которая отображает страницы сегмента разделяемой памяти на виртуальное адресное пространство. Делается это под семафором mmap_sem текущего процесса. В функцию do_mmap() передается флаг MAP_SHARED, а если вызывающий процесс передал ненулевое значение shmaddr, то передается и флаг MAP_FIXED. В противном случае do_mmap() самостоятельно выберет виртуальный адрес для сегмента разделяемой памяти.

ВАЖНО Из do_mmap() будет вызвана функция shm_inc() через структуру shm_file_operations. Эта функция вызывается для установки PID, текущего времени и увеличения счетчика присоединений данного сегмента разделяемой памяти.

После вызова do_mmap() приобретается глобальный семафор и глобальная блокировка разделяемой памяти. Счетчик присоединений затем уменьшается на 1, уменьшение производится потому, что в вызове shm_inc() счетчик был увеличен на 1. Если после уменьшения счетчик стал равен нулю и если сегмент имеет метку SHM_DEST, то вызывается shm_destroy() для ликвидации сегмента разделяемой памяти.

В заключение в вызывающую программу возвращается виртуальный адрес разделяемой памяти. Если функция do_mmap() вернула код ошибки, то этот код будет передан как возвращаемое значение системного вызова.

sys_shmdt()

На время исполнения функции sys_shmdt() приобретается глобальный семафор разделяемой памяти. В структуре mm_struct текущего процесса отыскивается vm_area_struct, ассоциированная с заданным адресом разделяемой памяти. Если таковая найдена, то вызывается do_munmap(), чтобы отменить отображение сегмента разделяемой памяти в виртуальные адреса.

Важно так же то, что do_munmap() вызывает shm_close(), которая освобождает ресурсы, занятые сегментом разделяемой памяти, если не было выполнено других присоединений.

sys_shmdt() всегда возвращает 0.

Структуры данных механизма разделяемой памяти

struct shminfo64

struct shminfo64 {
        unsigned long   shmmax;
        unsigned long   shmmin;
        unsigned long   shmmni;
        unsigned long   shmseg;
        unsigned long   shmall;
        unsigned long   __unused1;
        unsigned long   __unused2;
        unsigned long   __unused3;
        unsigned long   __unused4;
};

struct shm_info

struct shm_info {
        int used_ids;
        unsigned long shm_tot;  /* общее количество сегментов */
        unsigned long shm_rss;  /* общее количество резидентных сегментов */
        unsigned long shm_swp;  /* общее количество сегментов на свопинге */
        unsigned long swap_attempts;
        unsigned long swap_successes;
};

struct shmid_kernel

struct shmid_kernel /* private to the kernel */
{
        struct kern_ipc_perm    shm_perm;
        struct file *           shm_file;
        int                     id;
        unsigned long           shm_nattch;
        unsigned long           shm_segsz;
        time_t                  shm_atim;
        time_t                  shm_dtim;
        time_t                  shm_ctim;
        pid_t                   shm_cprid;
        pid_t                   shm_lprid;
};

struct shmid64_ds

struct shmid64_ds {
        struct ipc64_perm       shm_perm;       /* права доступа */
        size_t                  shm_segsz;      /* размер сегмента в байтах */
        __kernel_time_t         shm_atime;      /* время последнего присоединения */
        unsigned long           __unused1;
        __kernel_time_t         shm_dtime;      /* время последнего отсоединения */
        unsigned long           __unused2;
        __kernel_time_t         shm_ctime;      /* время последнего изменения */
        unsigned long           __unused3;
        __kernel_pid_t          shm_cpid;       /* pid процесса-создателя */
        __kernel_pid_t          shm_lpid;       /* pid последней операции */
        unsigned long           shm_nattch;     /* количество присоединений */
        unsigned long           __unused4;
        unsigned long           __unused5;
};

struct shmem_inode_info

struct shmem_inode_info {
        spinlock_t      lock;
        unsigned long   max_index;
        swp_entry_t     i_direct[SHMEM_NR_DIRECT]; /* для первых блоков */
        swp_entry_t   **i_indirect; /* doubly indirect blocks */
        unsigned long   swapped;
        int             locked;     /* into memory */
        struct list_head        list;
};

Функции поддержки разделяемой памяти

newseg()

Функция newseg() вызывается, когда возникает необходимость в создании нового сегмента разделяемой памяти. В функцию передаются три параметра - ключ (key), набор флагов (shmflg) и требуемый размер сегмента (size). После выполнения проверок (чтобы запрошенный размер лежал в диапазоне от SHMMIN до SHMMAX и чтобы общее количество сегментов разделяемой памяти не превысило SHMALL) размещает новый дескриптор сегмента. Далее вызывается shmem_file_setup() для создания файла типа tmpfs. Возвращаемый ею указатель записывается в поле shm_file дескриптора сегмента разделяемой памяти. Размер файла устанавливается равным запрошенному размеру сегмента памяти. Дескриптор инициализируется и вставляется в глобальный массив дескрипторов разделяемой памяти. Вызовом shm_buildid() (точнее ipc_buildid()) создается ID сегмента. Этот ID сохраняется в поле id дескриптора сегмента, а так же и в поле i_ino соответствующего inode. Адрес таблицы файловых операций над разделяемой памятью записывается в поле f_op только что созданного файла. Увеличивается значение глобальной переменной shm_tot, которая содержит общее количество сегментов разделяемой памяти в системе. Если в процессе выполнения этих действий ошибок не было, то в вызывающую программу передается ID сегмента.

shm_get_stat()

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

shmem_lock()

shmem_lock() принимает в качестве параметров указатель на дескриптор сегмента разделяемой памяти и флаг требуемой операции - блокирование или разблокирование. Состояние блокировки запоминается в соответствующем inode. Если предыдущее состояние блокировки совпадает с требуемым, то shmem_lock() просто возвращает управление не производя дополнительных действий.

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

Функция find_lock_page() блокирует страницу (устанавливает бит PG_locked) и увеличивает счетчик ссылок на страницу. Увеличение счетчика ссылок служит гарантией того, что страница останется в памяти на все время выполнения операции.
Если страницу требуется заблокировать, то бит PG_locked сбрасывается, но счетчик ччылок не уменьшается.
Если страницу требуется разблокировать, то счетчик ссылок уменьшается дважды, первый раз аннулируется увеличение счетчика, выполненное функцией find_lock_page() и второй раз для ссылки, которая заблокировала страницу в памяти. После этого бит PG_locked сбрасывается.

shm_destroy()

В результате исполнения shm_destroy() общее количество страниц, занятых разделяемой памятью, уменьшается на количество страниц, занятых удаляемым сегментом. Затем вызывается ipc_rmid() (через shm_rmid()) для удаления ID сегмента Страницы памяти в сегменте разблокируются функцией shmem_lock. Счетчик ссылок каждой страницы устанавливается в 0. Вызывается fput(), чтобы уменьшить счетчик f_count соответствующего файла. И в заключение вызывается kfree() для освобождения памяти под дескриптором сегмента.

shm_inc()

shm_inc() устанавливает PID, текущее время и увеличивает счетчик подключений для заданного сегмента разделяемой памяти. Эти действия выполняются после выполнения глобальной блокировки разделяемой памяти.

shm_close()

Функция shm_close() обновляет содержимое полей shm_lprid и shm_dtim и уменьшает счетчик подключений. Если счетчик обнулился, то вызывается shm_destroy() для освобождения ресурсов, занятых сегментом разделяемой памяти. Эти действия выполняются после выполнения глобальной блокировки и получения глобального семафора разделяемой памяти.

shmem_file_setup()

shmem_file_setup() создает файл в файловой системе tmpfs с требуемым именем и размером. Если в системе достаточно ресурсов для размещения файла в памяти, то создается новый dentry в корне tmpfs и размещается новый файловый дескриптор и новый inode типа tmpfs. Затем связывает dentry и inode вызовом d_instantiate() и сохраняет адрес dentry в файловом дескрипторе. Поле i_size inode устанавливается равным размеру файла, а в поле i_nlink заносится 0. Также shmem_file_setup() записывает адрес таблицы файловых операций shmem_file_operations в поле f_op и инициализирует поля f_mode и f_vfsmnt файлового дескриптора. Для завершения инициализации inode вызывается shmem_truncate(). И в случае успешного выполнения всех операций возвращает новый файловый дескриптор.

5.4 Примитивы IPC в Linux

Универсальные примитивы, используемые всеми тремя механизмами IPC

Механизмы семафоров, очередей сообщений и разделяемой памяти в Linux основаны на наборе общих примитивов. Этот раздел посвящен их описанию.

ipc_alloc()

Если запрошен размер памяти больше чем PAGE_SIZE, то вызывает vmalloc(), иначе - kmalloc() с флагом GFP_KERNEL.

ipc_addid()

Когда создается новый набор семафоров, очередь сообщений или сегмент разделяемой памяти, ipc_addid() сначала вызывает grow_ary(), чтобы расширить соответствующий массив дескрипторов, если это необходимо. Затем в массиве дескрипторов первый неиспользуемый элемент. Если таковой найден, то увеличивается счетчик используемых дескрипторов. Затем инициализирует структуру kern_ipc_perm и возвращает индекс нового дескриптора. В случае успеха возврат производится под глобальной блокировкой заданного типа IPC.

ipc_rmid()

ipc_rmid() удаляет дескриптор из массива дескрипторов заданного типа, уменьшает счетчик используемых ID и, в случае необходимости, корректирует значение максимального ID. Возвращает указатель на дескриптор, соответствующий заданному ID.

ipc_buildid()

ipc_buildid() создает уникальный ID для дескриптора заданного типа. ID создается в момент добавления нового элемента IPC (например нового сегмента разделяемой памяти или нового набора семафоров). ID достаточно просто преобразуется в индекс массива дескрипторов. Каждый тип IPC имеет свой порядковый номер, который увеличивается каждый раз, когда добавляется новый дескрипторо. ID создается путем умножения порядкового номера на SEQ_MULTIPLIER и добавления к результату индекса дескриптора в массиве. Этот порядковый номер запоминается в соответствующем дескрипторе.

ipc_checkid()

ipc_checkid() делит заданный ID на SEQ_MULTIPLIER и сравнивает со значением seq в дескрипторе. Если они равны, то ID признается достоверным и функция возвращает 1, в противном случае возвращается 0.

grow_ary()

grow_ary() предоставляет возможность динамического изменения максимального числа идентификаторов (ID) для заданного типа IPC. Однако текущее значение максимального числа идентификаторовне может превышать системного ограничения (IPCMNI). Если настоящий размер массива дескрипторов достаточно велик, то просто возвращает его текущий размер, иначе создает новый массив большего размера, копирует в него данные из старого массива, после чего память под старым массивом освобождается. На время переназначения массива дескрипторов выполняется глобальная блокировка для заданного типа IPC.

ipc_findkey()

ipc_findkey() ищет в массиве дескрипторов объекта ipc_ids заданный ключ. В случае успеха возвращает индекс соответствующего дескриптора, в противном случае возвращает -1.

ipcperms()

ipcperms() проверяет uid, gid и другие права доступа к ресурсу IPC. Возвращает 0 если доступ разрешен и -1 - в противном случае.

ipc_lock()

ipc_lock() выполняет глобальную блокировку заданного типа IPC и возвращает указатель на дескриптор, соответствующий заданному ID.

ipc_unlock()

ipc_unlock() разблокирует заданный тип IPC.

ipc_lockall()

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

ipc_unlockall()

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

ipc_get()

ipc_get() по заданному указателю на механизм IPC (т.е. разделяемая память, очереди сообщений или семафоры) и ID возвращает укзатель на соответствующий дескриптор IPC. Обратите внимание, что хотя различные механизмы IPC используют различные типы данных, тем не менее в каждом из них первым элементом указана общая для всех структура kern_ipc_perm. Возвращаемое функцией ipc_get() значение имеет именно этот общий тип данных. Как правило ipc_get() вызывается через функции-обертки (например shm_get()), которые выполняют приведение типов.

ipc_parse_version()

ipc_parse_version() сбрасывает флаг IPC_64 во входном параметре, если он был установлен, и возвращает либо IPC_64, либо IPC_OLD.

Структуры IPC, используемые механизмами семафоров, очередей сообщений и разделяемой памяти

struct kern_ipc_perm

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

/* используется в структурах данных ядра */
struct kern_ipc_perm {
    key_t key;
    uid_t uid;
    gid_t gid;
    uid_t cuid;
    gid_t cgid;
    mode_t mode;
    unsigned long seq;
};

struct ipc_ids

Структура ipc_ids описывает данные, одинаковые для семафоров, очередей сообщений и разделяемой памяти. Существует три глобальных экземпляра этого типа -- semid_ds, msgid_ds и shmid_ds -- для семафоров, очередей сообщений и разделяемой памяти соответственно. Каждый экземпляр содержит семафор sem, предназначенный для разграничения доступа к нему. Поле entries указывает на массив дескрипторов и поле ary - блокировку доступа к этому массиву. Поле seq хранит порядковый номер, который увеличивается всякий раз при создании нового ресурса IPC.

struct ipc_ids {
    int size;
    int in_use;
    int max_id;
    unsigned short seq;
    unsigned short seq_max;
    struct semaphore sem;
    spinlock_t ary;
    struct ipc_id* entries;
};

struct ipc_id

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

struct ipc_id {
    struct kern_ipc_perm* p;
};

Обсудить данную тему на нашем форуме "Все о Linux"