Семафоры

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

Alloc_undo()

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

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

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

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

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

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

static unsigned long microcode_status;

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

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

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

MOD_INC_USE_COUNT; return 0; }

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

void set_bit(int nr, volatile void *addr): устанавливает бит nr в карте, адресуемой параметром addr.

void clear_bit(int nr, volatile void *addr): сбрасывает бит nr в карте, адресуемой параметром addr.

void change_bit(int nr, volatile void *addr): изменяет состояние бита nr

(если бит установлен, то он сбрасывается, если сброшен - устанавливается) в карте, адресуемой addr.

int test_and_set_bit(int nr, volatile void *addr): устанавливается бит nr и возвращается его предыдущее состояние.

int test_and_clear_bit(int nr, volatile void *addr): сбрасывается бит nr и возвращается его предыдущее состояние.

int test_and_change_bit(int nr, volatile void *addr): изменяется состояние бита nr и возвращается его предыдущее состояние.

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

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

atomic_read(&v): возвращает значение atomic_t переменной v.

atomic_set(&v, i): записывает в atomic_t переменную v целое число i.

void atomic_add(int i, volatile atomic_t *v): складывает целое i и значение переменной v, результат помещается в переменную.

void atomic_sub(int i, volatile atomic_t *v): из переменной v вычитается целое i, результат помещается в переменную.

int atomic_sub_and_test(int i, volatile atomic_t *v): из переменной v вычитается целое i; возвращается 1 если новое значение переменной == 0, и 0 - в противном случае.

void atomic_inc(volatile atomic_t *v): увеличивает значение переменной на 1.

void atomic_dec(volatile atomic_t *v): уменьшает значение переменной на 1.

int atomic_dec_and_test(volatile atomic_t *v): уменьшает значение переменной на 1. Возвращает 1, если новое значение переменной == 0, 0 - в противном случае.

int atomic_inc_and_test(volatile atomic_t *v): увеличивает значение переменной на 1. Возвращает 1, если новое значение переменной == 0, 0 - в противном случае.

int atomic_add_negative(int i, volatile atomic_t *v): к переменной v прибавляется целое i, если результат меньше 0 - возвращается 1. Если результат больше либо равен 0 - возвращается 0. Эта операция используется в реализации семафоров.

Блокировки (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().

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

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() поскольку на входе в системный вызов прерывания всегда разрешены.

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); }

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

Контекст процесса, представленный типичным методом (функцией) драйвера - ioctl() (входные параметры и возвращаемое значение опущены для простоты), должен использовать spin_lock_irq(), поскольку заранее известно, что при исполнении метода ioctl()

прерывания всегда разрешены.

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

Convert_mode()

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

Copy_msqid_from_user()

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

Copy_msqid_to_user()

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

Count_semncnt()

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

Count_semzcnt()

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

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

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.

Expunge_all()

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

Free_msg()

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

Freeary()

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

Вызывается (через "обертку" sem_rmid()), чтобы удалить ID набора семафоров и получить указатель на набор семафоров.

Аннулируется список откатов для данного набора семафоров

Все ожидающие процессы пробуждаются, чтобы получить код ошибки EIDRM.

Общее количество семафоров уменьшается на количество семафоров в удаляемом наборе.

Память, занимаемая набором семафоров, освобождается.

Freeque()

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

Freeundos()

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

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

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

Операция GETALL загружает текущие значения

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

Операция GETNCNT возвращает число процессов,

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

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

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

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

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

Операция GETZCNT возвращает число процессов,

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

предоставляет возможность динамического изменения максимального

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

Ipc_addid()

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

Ipc_alloc()

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

Ipc_buildid()

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

Ipc_checkid()

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

Ipc_findkey()

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

Ipc_get()

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

IPC_INFO

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

IPC_INFO и SEM_INFO

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

заполняются элементы semusz и semaem

структуры в соответствии с требуемой операцией (IPC_INFO или SEM_INFO) и в качестве результата возвращается максимальный ID.

IPC_INFO ( или MSG_INFO)

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

Ipc_lock()

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

Ipc_lockall()

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

Ipc_parse_version()

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

IPC_RMID

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

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

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

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

IPC_SET

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

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

После проверки ID сегмента разделяемой памяти и прав доступа, uid, gid и флаги mode

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

IPC_STAT

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

IPC_STAT ( или MSG_STAT)

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

Ipc_unlockall()

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

Ipcperms()

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

Как реализуются системные вызовы в архитектуре 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. Далее:

Сохраняются регистры.

В регистры %ds и %es заносится KERNEL_DS, так что теперь они ссылаются на адресное пространство ядра.

Если значение %eax больше чем NR_syscalls

(на сегодняшний день 256), то возвращается код ошибки ENOSYS.

Если задача исполняется под трассировщиком (tsk->ptrace & PF_TRACESYS), то выполняется специальная обработка. Сделано это для поддержки программ типа strace (аналог SVR4 truss(1)) и отладчиков.

Вызывается sys_call_table+4*(syscall_number из %eax). Эта таблица инициализируется в том же файле (arch/i386/kernel/entry.S) и содержит указатели на отдельные обработчики системных вызовов, имена которых, в Linux, начинаются с префикса sys_, например sys_open, sys_exit, и т.п.. Эти функции снимают со стека свои входные параметры, которые помещаются туда макросом SAVE_ALL.

Вход в '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.

Кеш 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) то он удаляется из списка типа и очищается/удаляется полностью.

Кэш страниц в 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 этот метод не работает.

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 и далее загрузка продолжается как обычно.

Load_msg()

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

Механизмы IPC

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

"Мягкие" IRQ

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

Msg_setbuf

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

Newary()

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

В поле sem_base заносится адрес первого семафора в наборе.

Очередь sem_pending объявляетяс пустой.

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

Newque()

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

Инициализируется структура .

В поля q_stime и q_rtime

дескриптора заносится число 0. В поле q_ctime

заносится CURRENT_TIME.

Максимальный размер очереди в байтах (q_qbytes) устанавливается равным MSGMNB, текущий размер очереди в байтах (q_cbytes) устанавливается равным нулю.

Очередь ожидающих сообщений (q_messages), очередь ожидания процессов-получателей (q_receivers) и очередь ожидания процессов-отправителей (q_senders) объявляются пустыми.

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

Newseg()

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

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

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

Нижние половины (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.

Очереди ожидания (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():

Объявляется новый элемент очереди ожидания указывающий на текщий процесс.

Этот элемент добавляется в очередь rtc_wait.

Текущий процесс переводится в состояние TASK_INTERRUPTIBLE которое предполагает, что процесс не должен учавствовать в процессе планирования.

Проверяется - доступны ли данные. Если да - то цикл прерывается, данные копируются в пользовательский буфер, процесс переводится в состояние TASK_RUNNING, удаляется из очереди и производится возврат.

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

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

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

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

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

Фиксированное количество (32).

Каждый bottom half может быть связан только с одним обработчиком.

Bottom halves используются с захватом блокировки (spinlock) так что они не могут блокироваться.

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

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

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

tq_immediate: в действительности представляет собой bottom half IMMEDIATE_BH, таким образом драйверы могут установить себя в очередь вызовом queue_task(task, &tq_immediate) и затем mark_bh(IMMEDIATE_BH) чтобы использоваться в контексте прерывания.

tq_disk: используется при низкоуровневом доступе к блоковым учтройствам (и RAID). Эта очередь экспортируется в модули но должна использоваться только в исключительных ситуациях.

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

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

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

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

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

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

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

Pipelined_send()

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

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

Планировщик

Работа планировщика заключается в разделении 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 и ниже.

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

Если current->active_mm == NULL, то значит что-то не так. Любой процесс, даже поток ядра (для которого current->mm == NULL), всегда должен иметь p->active_mm.

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

Локальным переменным prev и this_cpu присваиваются значения current (текущая задача) и CPU текущей задачи соответственно.

Проверяется контекст вызова schedule(). Если функция вызвана из обработчика прерываний (по ошибке), то ядро "впадает в панику".

Освобождается глобальная блокировка ядра.

Если надлежить выполнить что-то, работающее через "мягкие" прерывания, то сделать это надо сейчас.

Устанавливается указатель struct schedule_data *sched_data на область данных планирования для заданного CPU, которая содержит значение TSC для last_schedule и указатель на последнюю запланированную задачу (task_struct) (TODO: sched_data используется только для мультипроцессорных систем, зачем тогда init_idle() инициализирует ее и для однопроцессорной системы?).

"Запирается" runqueue_lock. Обратите внимание на вызов spin_lock_irq(), который используется ввиду того, что в schedule() прерывания всегда разрешены. Поэтому, при "отпирании" runqueue_lock, достаточно будет вновь разрешить их, вместо сохранения/восстановления регистра флагов (вариант spin_lock_irqsave/restore).

task state machine: если задача находится в состоянии TASK_RUNNING, то она остается в этом состоянии; если задача находится в состоянии TASK_INTERRUPTIBLE и для нее поступили сигналы, то она переводится в состояние TASK_RUNNING. В любом другом случае задача удаляется из очереди runqueue.



Указатель next ( лучший кандидат) устанавливается на фоновую задачу для данного CPU. Признак goodness для этого кандидата устанавливается в очень малое значение (-1000), в надежде на то, что найдется более лучший претендент.

если задача prev (текущая) находится в состоянии TASK_RUNNING, то значение goodness принимает значение goodness задачи и она (задача) помечается как кандидат, лучший чем задача idle.

Далее начинается проверка очереди 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 или не имееющим пользовательского адресного пространства, т.е. потокам ядра.



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

В этой точке next указывает на задачу, которая должна быть запланирована, далее в next->has_cpu заносится 1 и в next->processor заносится значение this_cpu. Блокировка runqueue_lock

может быть снята.

Если происходит возврат к предыдущей задаче (next == prev) то просто повторно устанавливается блокировка ядра и производится возврат, т.е. минуя аппаратный уровень (регистры, стек и т.п.) и настройки VM (переключение каталога страницы, пересчет active_mm и т.п.).

Макрос switch_to() является платформо-зависимым. На i386 это имеет отношение к:

a) обработке FPU (Floating Point Unit - арифметический сопроцессор)

b) обработке LDT (Local Descriptor Table)

c) установке сегментных регистров

d) обработке TSS (Task State Segment) и

e) установке регистров отладки.

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

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).

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

Драйверы символьных и блочных устройств.

Terminal line disciplines.

Виртуальные (обычные) файлы в /proc и в devfs (например /dev/cpu/microcode и /dev/misc/microcode).

Обработка двоичных форматов файлов (например ELF, a.out, и пр.).

Обработка доменов исполнения (например Linux, UnixWare7, Solaris, и пр.).

Файловые системы.

System V IPC.

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

Алгоритмы планирования.

Политики VM (VM policies).

Кэш буфера, кэш страниц и другие кзши.

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

caddr_t create_module(const char *name, size_t size): выделяется size байт памяти, с помощью vmalloc(), и отображает структуру модуля в ней. Затем новый модуль прицепляется к списку module_list. Этот системный вызов доступен только из процессов с CAP_SYS_MODULE, все остальные получат ошибку EPERM.

long init_module(const char *name, struct module *image): загружается образ модуля и запускается подпрограмма инициализации модуля. Этот системный вызов доступен только из процессов с CAP_SYS_MODULE, все остальные получат ошибку EPERM.

long delete_module(const char *name): предпринимает попытку выгрузить модуль. Если name == NULL, то выгружает все неиспользуемые модули.

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; }

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

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

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

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

Освобождается file_systems_lock, потому что далее предполагается (request_module()) блокирующая операция и поэтому следует отпустить блокировку (spinlock). Фактически, в этом конкретном случае, отпустить блокировку file_systems_lock пришлось бы в любом случае, даже если бы request_module() не была блокирующей и загрузка модуля производилась бы в том же самом контексте. Дело в том, что далее, функция инициализации модуля вызовет register_filesystem(), которая попытается захватить ту же самую read-write блокировку file_systems_lock "на запись"

Если попытка загрузить модуль удалась, то далее опять захватывается блокировка file_systems_lock и повторяется попытка найти файловую систему в списке зарегистрированных Обратите внимание - здесь в принципе возможна ошибка, в результате которой команда modprobe "вывалится" в coredump после удачной загрузки запрошенного модуля. Произойдет это в случае, когда вызов request_module() зарегистрирует новую файловую систему, но get_fs_type() не найдет ее.



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

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

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

Построение образа ядра 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.

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

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

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

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

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

Назад

Реализация связанных списков в 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); }

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

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

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

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

Интерфейс VFS является экспортируемым и поэтому все файловые системы в Linux могут быть реализованы в виде модулей..

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

#include <linux/module.h> #include <linux/init.h>

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); }

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 делается то же самое).

Sem_exit()

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

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

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

Проверяется структура "отката" и ID набора семафоров.

В списке "откатов" соответствующего набора семафоров отыскиваются ссылки на структуры, которые удаляются из списка.

К набору семафоров применяются корректировки из структуры "отката".

Обновляется поле sem_otime в наборе семафоров.

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

Память, занимаемая структурой, освобождается.

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

---

---