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