Альтернативы блокированию

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

Свободные от блокировки алгоритмы

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

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

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

Рисунок 5-1 показывает круговой буфер в нескольких состояниях заполненности. Этот буфер был определён так, что пустое состояние обозначается одинаковыми указателями чтения и записи, а состояние заполненности - когда указатель записи имеет значение непосредственно за указателем чтения (будьте внимательны с учётом переноса по достижении границ буфера!). После тщательного программирования этот буфер может быть использован без блокировок.

Рисунок 5-1. Круговой буфер

Круговые буферы появляются в драйверах устройств разумно часто. Сетевые адаптеры, в частности, часто используют круговые буферы для обмена данными (пакетами) с процессором. Отметим, что в ядре версии 2.6.10 есть общая реализация кругового буфера, смотрите <linux/kfifo.h> для получения информации о том, как его использовать.

Атомарные переменные

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

n_op++;

потребуют блокировки. Некоторые процессоры могут выполнять такого рода увеличение атомарным образом, но вы не можете на это рассчитывать. Но режим полной блокировки выглядит излишеством для простых целочисленных значений. В случаях, подобных этому, ядро обеспечивает атомарный целочисленный тип, названный atomic_t и определённый в <asm/atomic.h>.

atomic_t на всех поддерживаемых архитектурах содержит значение int. Однако, из-за особенностей работы этого типа на некоторых процессорах, полный диапазон целого числа может быть не доступен; таким образом, вы не должны рассчитывать, что atomic_t содержит более чем 24 бита. Для этого типа определены следующие операции и они гарантированно будут атомарными в отношении всех процессоров SMP компьютера. Операции очень быстрые, потому что когда это возможно, они компилируются в одну машинную команду.

void atomic_set(atomic_t *v, int i);

atomic_t v = ATOMIC_INIT(0);

Задать атомарной переменной v целое значение i. Вы также можете инициализировать атомарные значения во время компиляции с помощью макроса ATOMIC_INIT.

int atomic_read(atomic_t *v);

Возвращает текущее значение v.

void atomic_add(int i, atomic_t *v);

Добавляет i к атомарной переменной, указываемой v. Возвращаемое значение является неопределённым, потому что существуют дополнительные расходы для возвращения нового значения и в большинстве случаев знать его нет необходимости.

void atomic_sub(int i, atomic_t *v);

Вычесть i из *v.

void atomic_inc(atomic_t *v);

void atomic_dec(atomic_t *v);

Увеличение или уменьшение атомарной переменной.

int atomic_inc_and_test(atomic_t *v);

int atomic_dec_and_test(atomic_t *v);

int atomic_sub_and_test(int i, atomic_t *v);

Выполнить указанные операции и проверить результат; если после операции атомарное значение равно 0, то возвращаемое значение является истинным (true); в противном случае, оно является ложным (false). Обратите внимание, что нет atomic_add_and_test.

int atomic_add_negative(int i, atomic_t *v);

Добавить целую переменную i к *v. Возвращаемое значение является истиной (true), если результат отрицательный, ложным (false), в противном случае.

int atomic_add_return(int i, atomic_t *v);

int atomic_sub_return(int i, atomic_t *v);

int atomic_inc_return(atomic_t *v);

int atomic_dec_return(atomic_t *v);

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

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

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

atomic_sub(amount, &first_atomic);

atomic_add(amount, &second_atomic);

Существует определенный период времени, когда amount был вычтен из первой атомарной величины, но ещё не добавлен ко второй. Если такое состояние может создать проблемы для кода, который может выполняться между двумя операциями, должны быть использованы какие-либо формы блокировки.

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

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

Атомарные битовые операции очень быстрые, так как они выполняют операции с использованием одной машинной инструкции без запрета прерываний всегда, когда нижележащая платформа может это сделать. Функции зависят от архитектуры и объявлены в <asm/bitops.h>. Они гарантированно атомарные даже на компьютерах с SMP и полезны для сохранения согласованности между процессорами.

К сожалению, типы данных в этих функциях зависят от архитектуры. Аргумент nr (описывающий биты для манипулирования) обычно определяется как int, но для нескольких архитектур является unsigned long. Адрес изменяемого, как правило, указатель на unsigned long, но на нескольких архитектурах вместо этого используется void *.

Доступными битовыми операциями являются:

void set_bit(nr, void *addr);

Установить бит номер nr в объекте данных, на который указывает addr.

void clear_bit(nr, void *addr);

Очищает указанный бит в данных типа unsigned long, которые находятся по addr. Иначе говоря, его семантика такая же, как у set_bit.

void change_bit(nr, void *addr);

Переключает бит.

test_bit(nr, void *addr);

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

int test_and_set_bit(nr, void *addr);

int test_and_clear_bit(nr, void *addr);

int test_and_change_bit(nr, void *addr);

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

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

Сегмент кода, которому необходимо получить доступ к объекту с общими данными, пытается получить блокировку атомарно используя либо test_and_set_bit, либо test_and_clear_bit. Здесь показана обычная реализация; она предполагает, что блокировка находится в бите nr по адресу addr. Предполагается также, что бит равен 0, когда блокировка свободна или ненулевой, когда блокировка занята.

/* пробуем установить блокировку */

while (test_and_set_bit(nr, addr) != 0)

    wait_for_a_while( );

/* выполняем работу */

/* освобождаем блокировку и проверяем... */

if (test_and_clear_bit(nr, addr) == 0)

    something_went_wrong( ); /* уже свободна: ошибка */

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

Последовательные блокировки

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

Последовательные блокировки (seqlock-и) определены в <linux/seqlock.h>. Есть два обычных метода для инициализации такого примитива (который имеет тип seqlock_t):

seqlock_t lock1 = SEQLOCK_UNLOCKED;

seqlock_t lock2;

seqlock_init(&lock2);

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

unsigned int seq;

do {

    seq = read_seqbegin(&the_lock);

    /* делайте, что необходимо */

} while read_seqretry(&the_lock, seq);

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

Если ваш примитив последовательной блокировки должен быть доступен из обработчика прерываний, вы должны вместо этого использовать IRQ-безопасные версии:

unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags);

int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags);

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

void write_seqlock(seqlock_t *lock);

Блокировка записи реализована со спин-блокировкой, так что применяются все обычные ограничения.

Сделайте вызов:

void write_sequnlock(seqlock_t *lock);

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

void write_seqlock_irqsave(seqlock_t *lock, unsigned long flags);

void write_seqlock_irq(seqlock_t *lock);

void write_seqlock_bh(seqlock_t *lock);

void write_sequnlock_irqrestore(seqlock_t *lock, unsigned long flags);

void write_sequnlock_irq(seqlock_t *lock);

void write_sequnlock_bh(seqlock_t *lock);

Существует также write_tryseqlock, которая возвращает ненулевое значение, если она смогла получить блокировку.

Прочитать-Скопировать-Обновить

Прочитать-Скопировать-Обновить (Read-copy-update, RCU) является расширенной схемой взаимного исключения, которая может принести высокую производительность в правильных условиях. Её использование в драйверов является редким, но не неизвестным, так что здесь стоит сделать краткий обзор. Те, кто заинтересовался полной информацией об алгоритме RCU, могут найти его в официальном документе, опубликованном его создателем (http://www.rdrop.com/users/paulmck/rclock/intro/rclock_intro.html).

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

В качестве примера реального использования RCU рассмотрим таблицы сетевой маршрутизации. Каждый исходящий пакет требует проверки таблиц маршрутизации для определения того, какой интерфейс должен быть использован. Проверка является быстрой и после того, как ядро нашло целевой интерфейс, оно больше не нуждается в таблице маршрутизации. RCU позволяет выполнять поиск маршрутов без блокировки, значительными увеличивая производительность. Starmode radio IP driver в ядре также использует RCU, чтобы отслеживать свой список устройств.

Код, использующий RCU, должен подключать <linux/rcupdate.h>.

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

struct my_stuff *stuff;

rcu_read_lock( );

stuff = find_the_stuff(args...);

do_something_with(stuff);

rcu_read_unlock( );

Вызов rcu_read_lock является быстрым, он отключает вытеснение в ядре, но ничего не ждёт. Код, который выполняется во время удержания "блокировки" чтения, должен быть атомарным. Нет ссылки на защищённый ресурс, которую можно было бы использовать после вызова rcu_read_unlock. Коду, которому требуется изменить защищаемую структуру, предстоит выполнить несколько шагов. Первая часть является простой; это создание новой структуры, копирование данные из старой, если необходимо, затем замена указателя, который виден коду чтения. На этом этапе с точки зрения читающей стороны изменение является полным; любой код, входящий в критическую секцию, видит новую версию данных.

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

Код, который изменяет защищённые RCU структуры данных, должен получить свой обратный вызов для очистки путём создания struct rcu_head, хотя инициализация этой структуры каким-либо способом не требуется. Часто эта структура просто внедрена в большой ресурс, который защищён RCU. После завершения изменения этого ресурса вызов должен выполнить:

void call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg);

Данная func вызывается, когда это безопасно для освобождения ресурсов; ей передаётся тот же самый arg, который был передан в call_rcu. Как правило, func необходимо сделать только одно - вызвать kfree.

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