Powered By Blogger

Wednesday, March 7, 2012

Примитивы синхронизации ядра - RCU

1. Авторские права и уведомления
2. Введение
2.1. Что такое механизм чтения-копирования при обновлении (RCU)?
2.2. Почему именно RCU?
2.3. Дополнительные источники
3. Описание примитивов RCU
3.1. struct rcu_head
3.2. call_rcu()
3.3. synchronize_kernel
3.4. Использование барьеров памяти
4. Применения RCU
4.1. RCU в хэш-таблице со счётчиком ссылок refcnt
4.2. Использование RCU совместно с kmem_cache_free()

1. Авторские права и уведомления [наверх]

Copyright © 2001 IBM Corporation. Авторские права защищены.

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

Данный документ предоставляется "AS IS," ("как есть") без каких-либо явных или подразумеваемых гарантий. Используя информацию из данного документа, вы действуете на свой страх и риск.

Особые замечания:

Linux является торговой маркой, принадлежащей Линусу Торвальдсу. Прочие названия компаний, продуктов или услуг могут быть товарными знаками или марками обслуживания других компаний.

2. Введение [наверх]

Данный документ описывает использование механизма чтения-копирования при обновлении (Read-Copy Update, RCU) в ядре Linux для реализации масштабируемых взаимных исключений. Здесь приводятся примеры и пояснения относительно интерфейса. Также поясняется, как экономить циклы используя RCU.

2.1. Что такое механизм чтения-копирования при обновлении (RCU)? [наверх]

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

Механизм чтения-копирования при обновлении (далее по тексту просто RCU для краткости) является одним из таких методов взаимного исключения, при котором читающие потоки (потоки, получающие доступ к данным, но не модифицирующие их) могут обращаться к разделяемым структурам без захвата традиционной блокировки. В то же самое время пишущие потоки (потоки, модифицирующие данные) используют особую схему обратного вызова для обновления данных. Все глобальные ссылки на модифицируемые данные обновляются и замещаются ссылками на изменённые данные. Механизм обратного вызова используется для освобождения старых копий данных после того, как все процессоры в системе теряют локальные ссылки на разделяемые данные при переходе в неактивное состояние (например, переключение контекста). Т.к. обеспечение доступа для записи более затратно по сравнению с обеспечением доступа по чтению, RCU наиболее подходит для осуществления сценариев, когда защищаемые данные чаще считываются, чем изменяются. На однопроцессорных системах RCU можно использовать, как альтернативу маскированию прерываний для обеспечения взаимного исключения. Т.о., RCU хорошо подходит для использования при обслуживании таблиц марштрутизации сетевых пакетов, таблиц состояний устройств, отложенного удаления структур данных, обеспечения многопутевого ввода-вывода (multi-path I/O) и т.д..

Изначально механизм RCU был разработан для DYNIX/ptx, вариант UNIX от Sequent Computer Systems Inc., ныне часть IBM. Сходные методы были использованы в проектах Tornado и K42 в универститете Торонто и исследованиях IBM.

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

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

2.2. Почему именно RCU? [наверх]

Ниже приводятся доводы, почему вам следует использовать механизм RCU, а также объясняются мотивы начала разработок в этом направлении.

Растущая цена традиционных блокировок

Скорости процессоров увеличиваются в 1,5-2 раза каждый год. Однако, рост скорости соединений (цепи на печатных платах и шины) составляет где-то лишь на 15% в год. Т.о., рост издержек использования традиционных блокировок стимулирует введение таких схем взаимного исключения, которые бы не зависели так сильно от путей коммуникации между относительно быстрыми процессорами.

RCU позволяет избегать блокировок при доступе для чтения.

Устранение сложноразрешимых ситуаций гонок

Механизм RCU не несёт риска взаимных блокировок (deadlocks), в отличие от явных блокировок. Снижение такого рода риска позволяет сократить или вовсе избежать использования избыточного кода, который бы потребовался в противном случае для отслеживания и исправления, а также предотвращения взаимных блокировок. Это, в свою очередь, снижает стоимость разработки и обслуживания программного обеспечения.

Оптимальное использование кэширования при неблокирующем чтении

Устраняя необходимость взведения блокировок при операциях чтения RCU позволяет избежать забивания строк кэша, которые бы использовались для обеспечения блокировок. В случаях, когда данные чаще читаются, такая безблокировочная система заметно выгоднее. Одним из примеров может служить синтетический тест производительности - "chat", где множество клонированных задач разделяют между собой данные в files_struct. Даже при использовании блокировки чтение-запись в процессе чтения файла через fget(), слишком интенсивное использование строк кэша для обеспечения самих блокировок ощутимо снижает эффективность системы при большом числе процессоров. Используя RCU, fget() может обращаться к указателю на файл без захвата блокировок, что существенно улучшит производительность системы.

2.3. Дополнительные источники [наверх]

Дополнительную информацию об RCU вы можете найти на домашней странице RCU http://lse.sourceforge.net/locking/rcupdate.html. Техническое описание реализации RCU в Linux было опубликовано на Linux-симпозиуме в Оттаве Ottawa в 2001. Этот документ можно найти здесь: http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf.

3. Описание примитивов RCU [наверх]

RCU состоит из интерфейса, который регистрирует функцию обратного вызова. Эта функция вызывается, когда все процессоры в системе прошли через одно из "состояний покоя" (переключение контекста, холостой цикл или переключение на пользовательский код). Данная функция может быть использоваться для обновления разделяемых структур данных. Однако, единовременно не может быть произведено более одной операции обновления, поэтому сами обновления должны происходить последовательно и управляться каким-либо традиционным механизмом взаимоисключения. Типичный код функции обновления должен следовать нижеописанным шагам:

  1. Захват блокировки.
  2. Обновление глобального указателя на данные (struct rcu_head) либо новым значением - адресом блока новых данных, либо NULL. После этого шага любой новый поток ядра, выполняемый на другом процессоре, увидит только новый указатель.
  3. Передача управления функции обратного вызова (call_rcu) для освобождения копии старых данных после прохождения всеми процессорами состояния покоя. Данный шаг гарантирует, что после удаления копии старых данных ни один из процессоров не будет ссылаться на эти данные.
  4. Освобождение блокировки механизма обновления.

Необходимые определения находятся в заголовочном файле linux/rcupdate.h.

3.1. struct rcu_head [наверх]

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

        struct rcu_head {
                struct list_head list;
                void (*func)(void *obj);
                void *arg;
        };


        #define RCU_HEAD_INIT(head) \
                { LIST_HEAD_INIT(head.list), NULL, NULL }
        #define RCU_HEAD(head) \
                struct rcu_head head = RCU_HEAD_INIT(head)
        #define INIT_RCU_HEAD(ptr) do { \
                        INIT_LIST_HEAD(&(ptr)->list); (ptr)->func = NULL; \
                        (ptr)->arg = NULL; \
                } while (0)

3.2. call_rcu() [наверх]

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

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

3.3. synchronize_kernel [наверх]

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

3.4. Использование барьеров памяти [наверх]

Порядок выполнения операций чтения и записи неявно обеспечивается в критических секциях, защищаемых традиционными механизмами блокировки. Однако при безблокировочном чтении данных в случае RCU важно обеспечить явный порядок процессорных операций доступа к памяти. Ядро Linux предоставляет множество функций, реализующих барьеры памяти. Наиболее часто используемые при работе с RCU функции: wmb() и rmb().

Примечение: в будущих версиях ядра имена этих функций могут быть изменены на write_barrier() и read_barrier() соответственно.

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

На стороне обновляющего кода:

  • Пометить элемент данных, как устаревший
  • Удалить его из списка
  • Запланировать выполнение функции обратного вызова RCU, чтобы удалить данные после цикла покоя

В читающем коде:

  • Для каждого элемента данных
    Если элемент данных element устарел - продолжить
  • если element->value == key
    возвратить element;

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

Пометить элемент данных element, как устаревший
wmb(); /* write_barrier() later */
Удалить элемент данных из списка
Запланировать вызов callback-функции для удаления данных после цикла покоя

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

Для каждого элемента
        rmb();
        если элемент element неактуален
                продолжить
        если element->value == key
                возвратить element;

На большинстве процессорных архитектур порядок обеспечивается по умолчанию, если есть зависимость данных. Чтобы избежать ненужных операций разрабатывается интерфейс read_barrier_depends(). Эта функция предусматривает rmb() только для архитектуры Alpha.

4. Применения RCU [наверх]

В этом разделе описывается несколько примеров применения механизма RCU.

4.1. RCU в хэш-таблице со счётчиком ссылок refcnt [наверх]

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

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

struct element {
        struct element *next;
        struct element *prev;
        atomic_t refcnt;
        int address;
        int data;
        struct rcu_head rcu;
};

/*
 * Ищет элемент с данным адресом, захватывает его блокировку и возвращает указатель на него.
 * Возвращает NULL если такой адрес не был найден.
 */
struct element *search(int addr)
{
        struct element *p;
        struct element *p0;

        p0 = &head[hashit(addr)];
        rmb(); /* read_barrier_depends() */
        p = p0->next;

        while (p != p0) {
                rmb(); /* read_barrier_depends() */

                if (p->address == addr) {
                        atomic_inc(&p->refcnt);
                        return (p);
                }

                p = p->next;
        }

        return ((struct element *)NULL);
}

/*
 * Вставка нового элемента в хэш-таблицу
 */
void insert(struct element *element)
{
        struct element *p0;

        p0 = &head [hashit(p->addr)];
        p->next = p0->next;

        /*
         * Необходимо убедиться, что следующий указатель добавленных данных
         * видим всем другим процессорам до собственно вставки. Это позволит
         * обеспечить безблокировочный поиск узла данных во всём списке.
         */
        wmb();
        p0->next = p;
}

void myfree(void *obj)
{
        struct element *p = obj;

        /*
         * Теперь мы можем безопасно проверить счётчик ссылок refcnt,
         * т.к. никто больше не воспользуется неактуальным указателем
         * на данный элемент после безблокировочного поиска через
         * search().
         */
        if (atomic_read(&p->refcnt)) {
                /*
                 * Позволим другому механизму сборки мусора
                 * удалить его.
                 */
                return;
        }

        kfree(obj);
}

/*
 * Удаляем указанный элемент из таблицы. Элемент должен быть под блокировкой.
 */
void delete(struct element *p)
{
        /*
         * Захватываем глобальную блокировку. Возможности взаимной блокировки нет,
         * т.к. глобальная блокировка всегда захватывается после взведения блокировки
         * отдельного элемента.
         */

        spin_lock(&hash_lock);

        /*
         * Удаляем элемент данных из списка, освобождаем блокировку,
         * удаляем элемент из памяти и возвращаем управление.
         */
        p->next->prev = p->prev;
        p->prev->next = p->next;
        spin_unlock(&hash_lock);

        call_rcu(&p->rcu, myfree, p);
        return;
}

4.2. Использование RCU совместно с kmem_cache_free() [наверх]

В отличие от [kv]free(), kmem_cache_free() требует дополнительного параметра в виде указателя на кэш, из которого был захвачен блок памяти. При использовании RCU это может быть проблемой, потому что мы имеем дело с обычным указателем (не структурой). Вы можете избежать этой проблемы, используя специальную функцию-деструктор для каждого кэша, который требует отложенного освобождения памяти. Если указатель на кэш - глобальная переменная, функция-деструктор может использовать эту переменную напрямую и вызывать kmem_cache_free() из функции обратного вызова. В ином случае внедрить указатель на кэш можно вместе с указателем на структуру типа struct rcu_head в данные, которые должны удаляться, так, что функция-деструктор сможет получить необходимую информацию оттуда.

Для случая с глобальным указателем на кэш наша функция будет выглядеть так:

static kmem_cache_t xxx_cache;

struct xxx_entry {
        struct xxx_entry *next;
        struct xxx_entry *prev;
        int flag;
        int info;
        struct rcu_head rch;
}

void xxx_destroy(void *ptr)
{
        struct xxx_entry *xp = (struct xxx_entry *)ptr;
        kmem_cache_free(&xxx_cache, (void *)xp);
}

void xxx_delete(struct xxx *xp)
{
        call_rcu(&xp->rch, xxx_destroy, xp);
}

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

struct xxx_entry {
        struct xxx_entry *next;
        struct xxx_entry *prev;
        int flag;
        int info;
        kmem_cache_t *cachep;
        struct rcu_head rch;
}

void xxx_destroy(void *ptr)
{
        struct xxx_entry *xp = (struct xxx_entry *)ptr;
        kmem_cache_free(&xp->cachep, (void *)xp);
}

void xxx_delete(struct xxx *xp)
{
        call_rcu(&xp->rch, xxx_destroy, xp);
}

ПОСЕТИТЕЛИ

free counters