Lock-free структуры данных. Извне: введение в libcds

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

Libcds является C++ библиотекой lock-free структур данных и методов безопасного освобождения памяти (safe memory reclamation, SMR) для lock-free структур. Она почти header-only – все структуры данных определены в .h-файлах заголовков и только реализация ядра алгоритмов SMR вынесена в небольшую динамическую библиотеку.

Краткий обзор SMR

Пожалуй, самый тонкий момент при разработке lock-free структуры данных – определить, в какой момент времени можно безопасно физически удалить элемент контейнера. Удаление элемента — всегда двухфазная операция: сначала мы исключаем элемент из контейнера, затем удаляем (deallocate) память, выделенную под элемент. При lock-free подходе вторая фаза – физическое удаление – требует, чтобы была полная уверенность, что никто (ни один из параллельных потоков) не имеет ссылки, глобальной или локальной, на удаляемый элемент.
За безопасное удаление отвечают алгоритмы SMR, которые можно рассматривать как специализированные сборщики мусора (garbage collectors, GC). В данной статье я не буду останавливаться на внутренних деталях реализации того или иного алгоритма SMR, дам лишь общее описание, достаточное для начала работы с libcds. Надеюсь подробно обсудить все алгоритмы в будущих статьях.

В libcds реализованы следующие алгоритмы SMR:

• Hazard Pointer – пожалуй, первый и самый известный из алгоритмов SMR. Изобретен Майклом (это фамилия) в 2002 году [Mic02, Mic03, Mic04]. Отличается относительной простотой и хорошим быстродействием, предназначен для «охраны» локальных ссылок на элементы контейнера. Недостаток – требует указания максимального числа одновременно работающих потоков. Заголовочный файл <cds/gc/hp.h>, класс cds::gc::HP
• Pass-the-Buck — концептуально похож на Hazard Pointer, но не зависит от числа потоков. Предложен в 2002 году Herlihy, V. Luchangco и M. Moir [Her02, Her05]. Из-за независимости от числа потоков немного тяжелее, чем Hazard Pointer. Заголовочный файл <cds/gc/ptb.h>, класс cds::gc::PTB
• Hazard Pointer with Reference Counting — разновидность алгоритма Hazard Pointer, предложенная представителями шведской школы во главе с Håkan Sundell’ом – Gidenstam’ом и др. [Gid05, Gid06]. Как и Hazard Pointer, зависит от числа потоков. Отличительная особенность – может защищать глобальные ссылки на элементы контейнера, то есть возможна реализация итераторов. Не рекомендован к применению из-за недостаточной производительности и редких глюков (не могу отладить его до конца). Заголовочный файл <cds/gc/hrc.h>, класс cds::gc::HRC
• RCU (Read-Copy Update) — в отличие от вышеприведенных, этот алгоритм относится к алгоритмам синхронизации, то есть приостанавливает выполнение потоков при удалении элементов, однако допускает параллельное выполнение прочих операций – вставки, поиска, — поэтому хорош для структур данных с редким удалением, типа map, set. Предложен Paul McKenney и активно применяется в ядре Linux; оригинальный RCU может быть реализован только в ядре ОС, но в 2009 году Desnoyers предложил версию RCU для прикладного применения (user-space RCU, URCU) [Des09, Des11], которая и реализована в libcds. Библиотека предлагает пять реализаций URCU, наиболее эффективная – buffered URCU. Заголовочный файл <cds/urcu/general_buffered.h>, класс cds::urcu::gc< cds::urcu::general_buffered<> >. В libcds URCU применяется только для map и set

Все алгоритмы SMR требуют единственного объекта, представляющего GC, то есть GC является синглтоном. В динамической библиотеке — ядре libcds – находится как раз реализация основных алгоритмов SMR.

Как правило, в вашем приложении должен использоваться только один алгоритм SMR (хотя libcds и допускает использовать несколько разных алгоритмов GC – так построены все тесты; но использовать два объекта одного и того же GC нельзя). Поэтому первое, что необходимо сделать – выбрать алгоритм SMR. Большинство классов структур данных в libcds имеют своим первым template-аргументом именно GC – алгоритм управления памятью. Более того, для каждого класса GC имеется своя собственная специализация шаблона (template) класса контейнера, так что для разных GC, как правило, следует включать (include) разные заголовочные файлы класса контейнера.

Для использования алгоритмов SMR нет необходимости знать внутреннее строение GC, — вся механика взаимодействия с GC спрятана внутри классов контейнеров. Но требуется инициализировать объект-синглтон GC в начале программы, а также в начале каждого потока (thread), который использует контейнеры, зависящие от GC.

Контейнеры без GC

В libcds есть некоторые lock-free структуры данных без GC:

• lock-based контейнеры, использующие изощренные (fine-grained) алгоритмы синхронизации
• ограниченные (bounded) по максимальному размеру контейнеры
• set и map, не поддерживающие операции удаления элементов (append-only). Как правило, каждый template-класс set/map имеет отдельную специализацию для “GC” cds::gc::nogc. Класс cds::gc::nogc представляет собой фактически отметку того факта, что контейнер не поддерживает удаление

Инициализация libcds

Инициализация библиотеки заключается в объявлении объекта GC. Этот объект должен быть единственным в вашей программе. GC-объект является просто объектно-ориентированной надстройкой над внутренней реализацией алгоритма SMR. Как правило, вашей программе не потребуется обращаться к методам GC-объекта, — все взаимодействие с GC спрятано внутри lock-free структуры данных,- поэтому GC-объект может быть локальным.
В libcds все разные типы GC — cds::gc::HP, cds::gc::PTB, cds::urcu::gc< cds::urcu::general_buffered<> > и пр. — инициализируются единообразно, но конструкторы могут принимать разные аргументы, задающие параметры конкретного GC. Все аргументы конструкторов GC имеют значения по умолчанию; в данной вводной статье я буду вызывать конструкторы без аргументов, полагаясь на значения по умолчанию.

Код инициализации для алгоритма управления памятью Hazard Pointer выглядит так:

#include <cds/init.h>  //cds::Initialize и cds::Terminate
#include <cds/gc/hp.h> //cds::gc::HP (Hazard Pointer)

int main(int argc, char** argv)
{
    // Инициализируем libcds
    cds::Initialize() ;
   {
       // Инициализируем Hazard Pointer синглтон
       cds::gc::HP hpGC ;

       // Если main thread использует lock-free контейнеры
       // main thread должен быть подключен 
       // к инфраструктуре libcds
       cds::threading::Manager::attachThread() ;

      // Всё, libcds готова к использованию
      // Далее располагается ваш код
      ...
   }

   // Завершаем libcds
   cds::Terminate() ;
}

Функция cds::Initialize() инициализирует некоторые глобальные внутренние данные libcds и определяет топологию системы. Далее следует создание GC-объекта, в данном примере – Hazard Pointer, класс cds::gc::HP, объект создается с аргументами по умолчанию.
В конце main следует вызвать функцию-терминатор библиотеки cds::Terminate, которая освободит (free) внутренние структуры.

Можно ли избавиться от вызова cds::Initialize() и cds::Terminate()?

Избавиться от вызова cds::Initialize() и cds::Terminate (например, определив их в DllMain dll-файла библиотеки для Windows или объявив как статические внутренние функции с атрибутом конструктора/деструктора для GCC) не получится, так как эти функции наполовину inline и в общем случае зависят от макросов, которые можно задать в командной строке компилятора.

Инициализация потоков

Многие алгоритмы SMR, равно как и lock-free структуры данных, требуют поддержки со стороны потоков (threads). Например, кое-какие данные являются локальными для потока (per-thread data), поэтому должны находиться в thread local storage (TLS). Для обеспечения этого некоторые реализации диктуют свою политику управления потоками или свою иерархию классов для потоков. Это, конечно, удобно для разработчика библиотеки, но совершенно неудобно для пользователя. Поэтому я при проектировании libcds пошел другим путем: библиотека не зависит от выбранной вами модели (или иерархии классов) потоков, но должна быть явным образом подключена (attach) к потоку.

Каждый поток (thread), работающий с контейнером из libcds, должен быть инициализирован следующим образом:

// cds::threading::Manager
#include <cds/threading/model.h>

int myThreadEntryPoint(void *)
{
    // Подключение потока к инфраструктуре libcds
    cds::threading::Manager::attachThread() ;

    // Теперь в данном потоке мы можем использовать 
    // lock-free контейнеры libcds
    ...

   // Отключение потока от libcds
   cds::threading::Manager::detachThread() ;

   return 0;
}

Класс cds::threading::Manager является классом-переходником для внутренней инфраструктуры управления потоками. Он вам может понадобиться только для подключения/отключения потока к инфраструктуре libcds.
Вышеприведенный код инициализации потока не безопасен с точки зрения исключений. Более правильный подход – использовать объект, конструктор которого подключает поток к инфраструктуре libcds, а деструктор – отключает. Для этого каждый класс GC имеет внутренний класс thread_gc. С ним инициализация потока выглядит так:

#include <cds/gc/hp.h>

int myThreadEntryPoint(void *)
{
    // Подключение потока к инфраструктуре libcds
    cds::gc::HP::thread_gc  threadGC ;

    // Теперь в данном потоке мы можем использовать 
    // lock-free контейнеры libcds
    ...

   return 0;
}

Как быть, если поток создан не нами?

Бывают ситуации, когда требуется подключить к libcds поток, который создан не нами, и мы никак не можем повлиять на инициализацию этого потока. Например, наше приложение является плагином к веб-серверу. Веб-сервер создает пул потоков (thread pool) и вызывает обработчики, реализованные в плагинах, в контексте этих потоков. В таком случае мы не можем ни создать GC-объект, ни инициализировать поток объявлением объекта типа GC::thread_gc. Что делать?

Придется использовать внутренние механизмы инициализации libcds: создать класс-инициализатор библиотеки и объявить статический объект этого класса:

#include <cds/gc/hp.h>

class LibcdsInit {
public:
    LibcdsInit()
    {
       // Инициализируем libcds
       cds::Initialize();
       // Инициализируем Hazard Pointer singleton
       cds::gc::hzp::GarbageCollector::Construct() ;
    }
    ~LibcdsInit()
    {
       // Терминация Hazard Pointer singleton
       // аргумент true – следует отключить 
       // от Hazard Pointer все потоки
       cds::gc::hzp::GarbageCollector::Destruct(true) ;

       // Терминация libcds
       cds::Terminate();
    };
};
// Объявляем статический инициализатор
static LibcdsInit libcdsInitializator ;

Вместо класса-инициализатора LibcdsInit соответствующие вызовы можно поместить в DllMain (для Windows) или в функции-конструкторы/деструкторы (__attribute__((constructor)) для GCC).

Инициализация потока заключается в подключении его “навсегда” вызовом cds::threading::Manager::attachThread():

// cds::threading::Manager
#include <cds/threading/model.h>

void callback() 
{
    Cds::threading::Manager::attachThread();

    // теперь можно использовать в потоке lock-free
    // контейнеры libcds
}

Отключение потока мы не вызываем.

Контейнеры

После инициализации библиотеки можно использовать lock-free структуры данных. В libcds контейнеры делятся на два больших класса – обычные и необычные интрузивные.
Обычные – это контейнеры в стиле STL, они хранят копию данных. Все такие контейнеры объявлены в пространстве имен cds::container.
Интрузивные контейнеры хранят собственно данные, а не их копии. Идея взята из boost::intrusive. Достоинство интрузивных контейнеров в том, что не надо вызывать аллокатор для создания копии данных. Считается, и не без оснований, что применение стандартного аллокатора сводит на нет идею lock-free, так как сам аллокатор содержит внутри себя примитивы синхронизации. В общем случае это правильно, но современные продвинутые аллокаторы могут оптимизировать распределение памяти, исключая внутреннюю синхронизацию за счет, например, наличия пула памяти для каждого потока.
Я не буду в этой статье подробно останавливаться на интрузивных контейнерах — они требуют особых приемов для освобождения памяти при исключении элемента из контейнера, это тема отдельного разговора. Здесь лишь отмечу, что большинство классов обычных контейнеров базируются на интрузивных, то есть, как правило, весь интересный lock-free код находится в классе интрузивного контейнера. Интрузивные контейнеры объявлены в пространстве имен cds::intrusive.

Все структуры данных в libcds являются шаблонными классами с единообразным template-интерфейсом. Можно выделить два типа template-интерфейсов:

• основанный на variadic template
• основанный на traits

Объявления, основанные на variadic template, используются для простых контейнеров – стеков и очередей. Общий паттерн таков:

template <typename GC, typename T, typename… Options>
class queue { … };

Для компиляторов, не поддерживающих variadic template, используется эмуляция.
Внутри класса контейнера Options упаковываются в структуру Traits.

Variadic template-подход оказался не очень удобным для сложного наследования, поэтому для классов более сложных контейнеров типа set, map и пр. используются traits-объявления:

template <typename GC, typename T, typename Traits>
class set { … };

Для каждого такого класса существует метафункция make_traits, преобразующая variadic template в traits:

template <typename… Options>
struct make_traits {
   typedef typename pack<Options…>::type type ;
};

С помощью make_traits объявление объекта контейнера принимает вид:

struct Foo { … };
cds::container::SkipListSet< cds::gc::HP, Foo, 
    typename cds::container::skip_list::make_traits<
      Opt1, 
      Opt2, 
      Opt3
    >::type
> theSkipListSet ;

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

struct Foo { … };

struct skipListSetTraits: 
    public cds::container::skip_list::make_traits<
      Opt1, 
      Opt2, 
      Opt3
    >::type
{};

cds::container::SkipListSet< cds::gc::HP, Foo, 
    skipListSetTraits
> theSkipListSet ;

Template-аргументами класса структуры данных являются:

• GC — используемый алгоритм SMR
• T — тип данных, хранимых в контейнере
• Options… или Traits — опции (policy, стратегии) контейнера

На опциях следует остановиться отдельно.

Опции

Каждый класс контейнера, помимо типа данных и алгоритма SMR, может иметь разнообразное число дополнительных настроек, задающих то или иное поведение. Например, для упорядоченных контейнеров (map, set) необходимо указать бинарный предикат сравнения элементов std::less<T>. Или задать ту или иную стратегию действий при обнаружении параллельной работы (back-off стратегия). Или установить аллокатор, используемый для создания элементов контейнера.
Каждый класс контейнера имеет несколько (до десятка) таких, как правило, необязательных настроек, которые я называю опциями. Подход, используемый в STL, когда каждая настройка является template-аргументом шаблона класса, мне не очень нравится: такие позиционно-зависимые аргументы с default-значениями усложняют применение класса. Если класс имеет 10 template-аргументов с default-значениями, то чтобы изменить восьмой аргумент, нам понадобиться указать default-значения всех семи аргументов, предшествующих восьмому. Это очень неудобно. Поэтому в libcds я использую позиционно-независимый подход.
При таком подходе каждая опция имеет свой тип; например, опция “аллокатор” имеет такое объявление:

template <typename Alloc>
struct allocator {
    template <typename Base>
    struct pack: public Base
    {
        typedef Alloc allocator ;
    };
};

Здесь template-аргумент Alloc — конкретный класс аллокатора, а сама структура allocator — имя опции. Вот как выглядит задание аллокатора через опцию:

cds::opt::allocator< std::allocator<int> >

С помощью таких объявлений опций довольно легко построить метафункцию, собирающую из опций структуру traits. Этот процесс называется упаковкой (packing).
В libcds существует два типа опций:

• Общие опции – применимы ко многим контейнерам. Объявления таких опций находится в пространстве имен cds::opt, а допустимые значения опций – в namespace cds::opt::v
• Специальные опции – применимы только к конкретному классу контейнера. Их объявления располагаются в пространстве имен конкретного контейнера, например, в cds::container::skip_list

В описании каждого класса контейнера приведен список допустимых опций.

Предикаты сравнения

Во многих контейнерах типа map, set следует указать предикат сравнения элементов. В STL для этого используются предикаты std::less<T>, которые умеют сравнивать только элементы типа T. Но очень часто это неудобно и накладно. Например, тип std::string может сравниваться со значением char const *, и для такого сравнения нет никакой необходимости в создании временного объекта std::string. Для set-контейнеров тип T, хранимый в контейнере, очень часто имеет ключевые поля, необходимые для сравнения, и «нагрузку» – собственно данные, никак не участвующие в поиске.
Учитывая все сказанное, в libcds используются расширенные предикаты, умеющие сравнивать значения разных типов. Предикаты задаются опциями. Более того, в качестве предиката сравнения можно использовать расширенный less (опция cds::opt::less< typename Less >) или расширенный compare (опция cds::opt::compare< typename Comparator >). Compare возвращает целое значение:

• cmp(a, b) < 0, если a < b
• cmp(a, b) == 0, если a == b
• cmp(a, b) > 0, если a > b

Так же действует функция-метод std::string::compare.
Написание расширенных предикатов (Less для опции cds::opt::less< typename Less > или Comparator для опции cds::opt::compare< typename Comparator >) – на вашей совести. Вот как может выглядеть Comparator для сравнения строк:

struct string_cmp
{
    int operator()(std::string const& s1, std::string const& s2) const
    { return s1.compare( s2 ); }
    int operator()(std::string const& s1, char const* s2) const
    { return s1.compare( s2 ); }
    int operator()(char const* s1, std::string const& s2) const
    { return –s2.compare( s1 ); }
};

Аллокаторы

Контейнеры из пространства имен cds::container хранят копии данных, поэтому одной из опций для них является cds::opt::allocator — аллокатор для распределения памяти под данные. Некоторые контейнеры имеют две опции аллокатора — одну для распределения данных (cds::opt::node_allocator), другую (cds::opt::allocator) — для выделения памяти под вспомогательные структуры контейнера. По умолчанию в качестве аллокатора используется std::allocator<int>. Если вы хотите использовать свой аллокатор, его интерфейс должен быть такой же, как и у std::allocator.

Библиотека существенно полагается на два свойства аллокаторов:

• каждый аллокатор имеет метафункцию template <typename Other> struct rebind, которая позволяет перестроить аллокатор под другой тип Other. Как я уже сказал, аллокатором по умолчанию является std::allocator<int>, — контейнер посредством метафункции rebind меняет тип int на требуемый
• аллокатор — глобальный объект. Это требование вытекает из того факта, что физическое удаление элемента lock-free контейнера является отложенным и может произойти после разрушения самого объекта контейнера. Поэтому, в отличие от STL, контейнеры libcds никогда не хранят ссылок на объект аллокатора и не имеют методов задания объекта-аллокатора. Если нужно распределить память внутри метода контейнера, аллокатор вызывается через временный объект: allocator_type().allocate( 1 ). Точно так же, освобождение памяти происходит вызовом allocator_type().deallocate( p ). Стоит ещё раз отметить, что освобождение является отложенным и может произойти уже тогда, когда самого объекта контейнера уже нет, да и вызывается оно из алгоритма SMR

Краткие технические характеристики

Поддерживаемые компиляторы:

• GCC 4.3 и выше
• MS Visual C++ 2008 и выше
• Clang 3.0 и выше (со стандартной библиотекой GCC libstdc++)

Поддерживаемые операционные системы и архитектуры процессоров:

• Windows x86, amd64
• Linux x86, amd64, Intel Itanium, Sparc
• Solaris Sparc
• HP-UX Intel Itanium

Поддержка других ОС или архитектур процессоров является делом возможным, но нетривиальным, особенно если целевой компилятор не поддерживает C++11 atomic.

Заключение

Надеюсь, после прочтения данной статьи будет понятно, как использовать библиотеку libcds. Кроме того, я попытался пояснить основные принципы, руководствуясь которыми я реализую в библиотеке структуры данных.

Я совершенно не касаюсь вопросов производительности. Как я ранее уже отмечал, о производительности можно говорить только применительно к конкретной задаче и конкретному железу. Современное железо очень по-разному относится к lock-free алгоритмам: одно благосклонно к ним, другое бывает нужным долго уговаривать, подбирая те или иные опции класса контейнера для достижения приемлемой производительности. Lock-free структуры данных довольно сложны по сравнению со своими обычными собратьями, поэтому начинает играть фактор «кто быстрее»: либо примитив синхронизации + обычный контейнер, либо сложный lock-free контейнер без внешней синхронизации.

Если вы хотите получить добрый совет, то вот он: старайтесь вовсе не использовать разделяемых (shared) данных. Америку таким советом я не открыл, но следовать ему в повседневной жизни бывает сложно.

Ссылки

[Des09] M.Desnoyers Low-Impact Operating System Tracing PhD Thesis,Chapter 6 «User-Level Implementations of Read-Copy Update»

[Des11] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole User-Level Implementations of Read-Copy Update

[Gid05] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas Practical and Efficient Lock-Free Garbage Collection Based on Reference Counting

[Gid06] A.Gidenstam Algorithms for synchronization and consistency in concurrent system services, Chapter 5 «Lock-Free Memory Reclamation» Thesis for the degree of Doctor of Philosophy

[Her02] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting dynamic-sized lockfree data structures Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002

[Her05] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support for Dynamic_Sized Data Structures ACM Transactions on Computer Systems, Vol.23, No.2, May 2005

[Mic02] Maged M.Michael Safe memory reclamation for dynamic lock-free objects using atomic reads and writes

[Mic03] Maged M.Michael Hazard Pointers: Safe memory reclamation for lock-free objects

[Mic04] Andrei Alexandrescy, Maged Michael Lock-free Data Structures with Hazard Pointers

Lock-free структуры данных

Начало
Основы:

• Атомарность и атомарные примитивы
• Откуда пошли быть барьеры памяти
• Модель памяти

Внутри:

• Схемы управления памятью
• RCU
• Эволюция стека
• Очередной трактат
• Диссекция очереди
• Concurrent maps: разминка
• Concurrent maps: rehash, no rebuild
• Concurrent maps: skip list
• Concurent maps: деревья
• Итераторы: multi-level array
• Iterable list

Извне:

• Введение в libcds