Введение

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

Библиотека Liburcu

В тесте используем библиотеку liburcu. Данная библиотека предоставляет как примитивы RCU так и работу с полноценными структурами, такими как хеш-таблицы, очереди, стеки и списки.

Подробное описание https://liburcu.org/

Для нашего сегодняшнего теста выбрана работа с динамическим RCU списком.

https://lwn.net/Articles/573441/.

Описание задачи

Поскольку основной смысл применения RCU это задачи с одним писателем и множеством читателей, попробуем реализовать следующий пример. Дан динамический список t_list в который необходимо добавлять и удалять записи, без блокировок чтения и нарушения целостности данных. Каждый элемент списка будет указывать на структуру node из структуры t_node в которой поля node и rcu_head необходимы для работы RCU, а value является пользовательскими данными.

CDS_LIST_HEAD(t_list);

struct t_node
{
    long long value;
    struct cds_list_head node;
    struct rcu_head rcu_head;
};

Для работы со списком формируем пул потоков из которых, один является писателем и определяется функцией void *test_l_add(void *arg) , а остальные будут читателями с функцией void *test_l_get(void *arg).

    for (i = 0; i < num_threads; i++) {
        if (i < 1)
            pthread_create(&tid[i], NULL, &test_l_add, (void *) i);
        else
            pthread_create(&tid[i], NULL, &test_l_get, (void *) i);
    }

После запуска нитей, основной поток ожидает 5 секунд, разблокирует Mutex остановки и ждет завершения всех дочерних нитей. Затем освобождение памяти и завершение процесса.

    sleep(5);
    pthread_mutex_unlock(&m1);

    for (i = 0; i < num_threads; i++) {
        pthread_join(tid[i], NULL);
    }

Писатель RCU

Функция писателя void *test_l_add(void *arg) выполняет бесконечный цикл в ожидании освобождения Mutex. В цикле выполняется имитация работы со списком, при каждой итерации цикла добавляются 2 элемента списка со значениями REZ1 и REZ2. Функция cds_list_add_tail_rcu выполняется вне секции rcu_read_lock и не блокирует читателей. Каждый читатель, пока находится в rcu_read_lock, будет видеть старую версию списка.

        struct t_node *node = malloc(sizeof(*node));
        if (node) {
            node->value = REZ1;
            cds_list_add_tail_rcu(&node->node, &t_list);
            count++;
        }

На каждый сотый цикл выполняется поиск и удаление всех элементов со значением REZ2. В данном фрагменте реализован механизм отложенного удаления ресурсов, после вызова функции cds_list_del_rcu вызывается функция call_rcu которой передается в качестве параметра имя функции для освобождения ресурсов.

        if (count1 % 100 == 0) {
            rcu_read_lock();
            struct t_node *node = NULL;
            cds_list_for_each_entry_rcu(node, &t_list, node)
            {
                if (node->value == REZ2) {
                    cds_list_del_rcu(&node->node);
                    call_rcu(&node->rcu_head, free_node_rcu);
                }
            }
            rcu_read_unlock();
        }

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

static void free_node_rcu(struct rcu_head *head)
{
    struct t_node *node = caa_container_of(head, struct t_node, rcu_head);
    node->value = 0;
    free(node);
}

Читатель RCU

Функция читателя void *test_l_get(void *arg) , также в бесконечном цикле выполняет чтение всего списка с проверкой корректности значений value. Чтение списка происходит в в секции rcu_read_lock(). Макрос cds_list_for_each_entry_rcu выполняет просмотр всего списка, возвращая указатель на структуру t_node. При освобождении Mutex нить завершает работу и выводит на экран количество циклов чтения и количество считанных элементов в последнем цикле. Необходимо обратить внимание что rcu_read_lock() и rcu_read_unlock() всегда парные , не допускайте незакрытую секцию чтения.

    while (pthread_mutex_trylock(&m1) == EBUSY) {
        rcu_read_lock();
        struct t_node *node = NULL;
        count_elm = 0;
        cds_list_for_each_entry_rcu(node, &t_list, node)
        {
            if (node->value != REZ1 && node->value != REZ2) {
                printf("Fatal error :%lld :%lld :%lld\n", i, count, count_elm);
                exit(-1);
            }
            count_elm++;
        }
        count++;
        rcu_read_unlock();
    }
    printf("End GET :%lld :%lld :%lld\n", i, count, count_elm);

Тестирование

Приступаем к тестированию основной задачи - показать что тестовое приложение работает эффективно в независимости от числа нитей читателей.

Первый запуск выполним для проверки холостой работы писателя. Установим количество нитей = 1. Результатом работы являются строка Start и End , которые показывают номер нити и количество циклов. List empty выдает информацию сколько в нашем списке значений value равно REZ1 и REZ2 соответственно. Результаты постоянно изменяются +/- тысяча при 350 тысячах циклов за 5 секунд это нормально. Итак примем что моих условиях одна нить совершает ~340-360 тысяч циклов.

Start ADD :0
End ADD :0 :356500
List empty 356500 1

Писателям без читателей скучно, добавим 1. Появилась запись End GET читатель выполнил 3947 циклов и в последнем цикле в списке было 359499 элементов.

Start ADD :0
Start GET :1
End GET :1 :3947 :359499
End ADD :0 :359440
List empty 359440 41

Добавим сразу до 4.

Start ADD :0
Start GET :2
Start GET :1
Start GET :3
Start GET :4
End GET :1 :4567 :364999
End ADD :0 :364977
End GET :4 :3669 :365055
End GET :2 :4175 :365055
End GET :3 :3794 :365055
List empty 364977 78

И до 12, больше чем количество ядер особого смысла нет.

Start ADD :0
Start GET :3
Start GET :2
Start GET :1
Start GET :4
Start GET :11
Start GET :10
Start GET :5
Start GET :7
Start GET :9
Start GET :6
Start GET :8
End GET :10 :4101 :387799
End GET :1 :4414 :387899
End GET :6 :3699 :387999
End GET :2 :4140 :387999
End ADD :0 :387974
End GET :3 :4957 :388049
End GET :4 :3901 :388049
End GET :5 :3550 :388049
End GET :7 :3999 :388049
End GET :11 :3917 :388049
End GET :8 :3637 :388049
End GET :9 :3755 :388049
List empty 387974 75

По результатам прошу обратить внимание что каждая из нитей останавливается со своим значением количество элементов, до тех пор пока не остановилась нить-писатель, далее все читатели считали зафиксированный результат 387974+75 и остановились.

И каков итог измерений? RCU работает и очень эффективно, важно только правильно применить.

Вывод

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

Код проекта https://github.com/vic-35/test_liburcu2 , проект создан в QT creator для облегчения отладки и запуска.

Просто о RCU (Read–Copy-Update). Часть 2