среда, 24 ноября 2010 г.

Lock-free программирование - часть 3

В первых двух статьях мы ознакомились с атомарными операциями, базовой техникой lock-free программирования, а также с некоторыми алгоритмами сборки мусора. Мы убедились, что разработка неблокирующих алгоритмов довольно сложна, а разработка эффективных алгоритмов вдвойне сложнee. В этой статье я хочу написать об очень важной составляющей процесса разработки программ – о тестировании и отладке. Отладка многопоточных программ (а тем более неблокирующих) занятие не из простых. Те, кто хоть раз отлаживал сложную систему, знают, как сложно найти ошибку в программе, если ошибка не воспроизводится. Ошибки, возникшие в условиях высокой нагрузки очень сложно воспроизвести в режиме отладки, когда нагрузка отсутствует. Чтобы попадать в подобные ситуации как можно реже, желательно тестировать каждый модуль в отдельности и под высокой нагрузкой с помощью unit-test - ов и в этой статье мы рассмотрим инструмент, предназначенный для тестирования алгоритмов синхронизации, написанных на C++0x.

Relacy Race Detector

Инструмент, автором которого является Dmitriy Vyukov, представляет собой набор заголовочных файлов C++, предоставляющих интерфейс, похожий на интерфейс библиотеки C++ threading library из стандарта C++0x. Он симулирует указанное количество потоков и позволяет выявить race condition, проблемы переупорядочения, попытки обращения к удаленным участкам памяти, и так далее... Рассмотрим несколько нюансов работы с relacy race detector.

relacy/relacy_std.hpp – единственный заголовочный файл из библиотеки, который нужно включать в программу.
Для атомарных типов используется шаблонный класс std::atomic<T>.
Например:
std::atomic<node*> head;
std::atomic<int> count;
Обычные (не атомарные), но shared переменные должны быть обернуты в шаблонный класс rl::var<Т>, эти переменные будут участвовать в проверке на race condition.
Доступы к атомарным переменным типа std::atomic<T> и rl::var<T> должны иметь суффикс ($).
Например:
head($).load();
count($).store(0);
Проверки состояния программы совершаются с помощью макроса RL_ASSERT.
Тесты пишутся в классе/структуре, наследуемой от шаблонной структуры rl::test_suite, в которую в виде шаблонных параметров передается тип наследуемого класса (CRTP) и количество потоков для симуляции. Каждый поток запускает функцию thread наследуемой структуры, передавая ему в качестве аргумента свой последовательный идентификатор. Также структура может содержать функции before и after для инициализации и пост-проверок состояние программы.
struct test: rl::test_suite<test, 2>
{
    void before() {}
    void after() {}
    void thread(unsigned index) {}
};
Запуск симуляции происходит в функции main вызовом функции rl::simulate
rl::test_params params;
rl::simulate<test>(params);
rl::test_params params;
rl::simulate<test>(params);
Параметры можно не передавать, тогда симуляция будет запущена с параметрами по умолчанию.
Ну что же, посмотрим на него в деле. Для начала напишет самый просто тест, тест на инкремент не атомарной переменной из двух потоков – т.е. тест на race condition.
#include "relacy/relacy_std.hpp"

struct data_race_test : rl::test_suite<data_race_test, 2>
{
    rl::var<int> x;

    void before()
    {
        x($) = 0;
    }
    void thread(unsigned)
    {
        x($)++;
    }
};

int main()
{
    rl::simulate<data_race_test>();
}
Сначала мы инициализируем переменную x, а потом пытаемся ее модифицировать одновременно из двух потоков. Поскольку переменная x не атомарна, здесь имеет место быть проблематичный race condition.
Теперь исходник надо откомпилировать, передав компилятору путь к директории relacy, и запустить.
5test1
DATA RACE (data race detected)
iteration: 1

execution history (10):
[0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419)
[2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[3] 1: <0x76d8160> store, value=0, in before, main.cpp(9)
[4] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419)
[5] 1: <0x76d8160> load, value=0, in thread, main.cpp(13)
[6] 1: <0x76d8160> store, value=1, in thread, main.cpp(13)
[7] 1: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419)
[8] 0: <0x76d8160> load, value=0, in thread, main.cpp(13)
[9] 0: DATA RACE (data race detected), in thread, main.cpp(13)

thread 0:
[8] 0: <0x76d8160> load, value=0, in thread, main.cpp(13)
[9] 0: DATA RACE (data race detected), in thread, main.cpp(13)

thread 1:
[0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419)
[2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[3] 1: <0x76d8160> store, value=0, in before, main.cpp(9)
[4] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419)
[5] 1: <0x76d8160> load, value=0, in thread, main.cpp(13)
[6] 1: <0x76d8160> store, value=1, in thread, main.cpp(13)
[7] 1: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419)
Отлично! Мы нашли ошибку в самом начале и сэкономили кому-то (скорее всего самому себе) множество часов кропотливой работы. Исправим код так, чтобы избавиться от этой проблемы и запустим тест заново. Изменим тип переменной x и сделаем ее атомарной.
#include "relacy/relacy_std.hpp"

struct data_race_test : rl::test_suite<data_race_test, 2>
{
    std::atomic<int> x;

    void before()
    {
        x($) = 0;
    }
    void thread(unsigned)
    {
        x($)++;
    }
};

int main()
{
    rl::simulate<data_race_test>();
}
Теперь осталось откомпилировать и запустить.
5test1
iterations: 1000
total time: 10
throughput: 100000
Все отлично, тест прошел успешно, можно конечно добавить количество итераций и оставить его работать на ночь, но в данном случае в этом нет необходимости. Идем дальше.
Усложним задачу.
Как уже говорилось в первой части статьи, все операции с атомарными переменными по умолчанию являются последовательно-консистентными (sequentially consistent), и хотя широко используемые процессорные архитектуры (x86-64) предоставляют последовательную консистентность без особых потерь, на других процессорах это может значительно повлиять на производительность.
Вспомним статью про барьеры памяти и проверим пример, приведенный там.
void func_on_cpu1()
{
    a = 1;
    b = 1;
}
void func_on_cpu2()
{
    while (b == 0);
    assert(a == 1);
}
Перепишем его на C++0x и напишем для него unit-test. Разумеется переменные a и b должны быть атомарными, но для воспроизведения проблемы, все операции с ними не должны содержать никаких барьеров и не должны быть последовательно-консистентными. Для этого, вместо memory_order_seq_cst, который передается по умолчанию, мы передаем в функции store и load параметр rl::memory_order_relaxed (std::memory_order_relaxed в C++0x), принуждая тем самым компилятор “расслабить” данную операцию.
#include "relacy/relacy_std.hpp"

struct ordering_test : rl::test_suite<ordering_test, 2>
{
    std::atomic<int> a;
    std::atomic<int> b;

    void before()
    {
        a($).store(0);
        b($).store(0);
    }
    void thread(unsigned index)
    {
        if (index == 0)
        {
            a.store(1, rl::memory_order_relaxed);
            b.store(1, rl::memory_order_relaxed);
        } else
        {
            while (b.load(rl::memory_order_relaxed) == 0);
            RL_ASSERT(a.load(rl::memory_order_relaxed) == 1);
        }
    }
};

int main()
{
    rl::simulate<ordering_test>();
}
Осталось откомпилировать и запустить .
13ordering_test
USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1)
iteration: 5

execution history (14):
[0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419)
[2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[3] 1: <0x13610250> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(10)
[4] 1: <0x13610278> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(11)
[5] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419)
[6] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22)
[7] 0: <0x13610250> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(18)
[8] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22)
[9] 0: <0x13610278> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(19)
[10] 0: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419)
[11] 1: <0x13610278> atomic load, value=1, order=relaxed, in thread, main.cpp(22)
[12] 1: <0x13610250> atomic load, value=0 [NOT CURRENT], order=relaxed, in thread, main.cpp(23)
[13] 1: USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1), in thread, main.cpp(23)

thread 0:
[7] 0: <0x13610250> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(18)
[9] 0: <0x13610278> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(19)
[10] 0: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419)

thread 1:
[0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419)
[2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419)
[3] 1: <0x13610250> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(10)
[4] 1: <0x13610278> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(11)
[5] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419)
[6] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22)
[8] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22)
[11] 1: <0x13610278> atomic load, value=1, order=relaxed, in thread, main.cpp(22)
[12] 1: <0x13610250> atomic load, value=0 [NOT CURRENT], order=relaxed, in thread, main.cpp(23)
[13] 1: USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1), in thread, main.cpp(23)
Отлично! Мы опять выявили проблему. Теперь попытаемся ее исправить так, как описано в статье барьеры памяти, т.е. установим барьер записи (release) в первом потоке и барьер чтения (acquire) во втором. Для этого мы заменяем rl::memory_order_relaxed на rl::memory_order_release в первом, и на rl::memory_order_acquire во втором.
void thread(unsigned index)
{
    if (index == 0)
    {
        a.store(1, rl::memory_order_relaxed);
        b.store(1, rl::memory_order_release);
    } else
    {
        while (b.load(rl::memory_order_acquire) == 0);
        RL_ASSERT(a.load(rl::memory_order_relaxed) == 1);
    }
}
Теперь компилируем и запускаем
13ordering_test
iterations: 1000
total time: 10
throughput: 100000
Вот и все, тест пройден.

Пользуйтесь unit-test – ами как можно чаще. Выявление ошибок синхронизации на этапе написания кода сэкономят много времени и сил. И не забывайте про code-review, ведь самому сложно замечать свои же ошибки.
Скачать инструмент relacy race detector, а также задать вопрос автору и посмотреть примеры использования можно по адресу http://groups.google.com/group/relacy/web.