Lock-free структуры данных. Внутри. RCU


    В этой статье я продолжу знакомить хабрасообщество с техниками, обеспечивающими написание lock-free контейнеров, попутно рекламируя (надеюсь, не слишком навязчиво) свою библиотеку libcds.

    Речь пойдет об ещё одной технике безопасного освобождения памяти для lock-free контейнеров — RCU. Эта техника существенно отличается от рассмотренных ранее алгоритмов a la Hazard Pointer.

    Read – Copy Update (RCU) – техника синхронизации, предназначенная для «почти read-only», то есть редко изменяемых, структур данных. Типичными примерами такой структуры являются map и set – в них большинство операций является поиском, то есть чтением данных. Считается, что для типичного map'а более 90% вызываемых операций — это поиск по ключу, поэтому важно, чтобы операция поиска была наиболее быстрой; синхронизация поиска в принципе не нужна — читатели при отсутствии писателей могут работать параллельно. RCU обеспечивает наименьшие накладные расходы как раз для read-операций.

    Откуда взялось название Read – Copy Update? Первоначально идея была очень проста: есть некоторая редко изменяемая структура данных. Если нам требуется изменить её, то мы делаем её копию и производим изменение — добавление или удаление данных — именно в копии. При этом параллельные читатели работают с первоначальной, не измененной структурой. В некоторый безопасный момент времени, когда нет читателей, мы можем подменить структуру данных на измененную копию. В результате все последующие читатели будут видеть изменения, произведенные писателем.


    Создателем и активным популяризатором техники RCU является Paul McKenney. Он возглавляет целую школу «любителей RCU», из которой вышло немало известных ученых в области lock-free и нетрадиционных схем синхронизации, а также он является «главным по RCU» в ядре Linux (Linux-kernel RCU maintainer) и автором ряда работ по RCU.


    RCU была внедрена в ядро Linux в 2002 году и с тех пор все более и более врастает в код ядра, см. рисунок справа. Долгое время она позиционировалась как техника синхронизации именно для ядра операционной системы. Так как ядро имеет полный контроль над всеми потоками, — как пользовательскими, так и системными, — то в ядре довольно просто определить тот безопасный момент времени подмены данных на измененную копию. Но нас интересует прикладное применение RCU, возможно ли оно? Прежде чем ответить на этот вопрос, рассмотрим подробнее теорию RCU и применяемую в ней терминологию.

    Общее описание RCU



    Приведенное выше описание идеи RCU очень упрощенно. Как мы знаем, имея атомарные операции, мы можем не делать копию данных, а изменять структуру данных «на лету» параллельно с её чтением. Тогда «читателем» становится поток, выполняющий любую операцию, кроме удаления элемента из структуры данных. Писателем будем называть поток, удаляющий что-либо из структуры. Удаление должно производиться в момент времени, когда никто не «наступил» на удаляемые данные, иначе мы получим букет трудно обнаружимых проблем — от ABA-проблемы до memory corruption. RCU решает все эти проблемы, причем методом, отличным от рассмотренной ранее схемы Hazard Pointers.

    Читатели в технике RCU выполняются в критической секции чтения (read-side critical section). При входе в такую критическую секцию читатель вызывает функцию rcu_read_lock(), при выходе — rcu_read_unlock(). Это очень легкие функции, практически не влияющие на производительность; в ядре Linux они не весят вообще ничего (zero-overhead).
    Если поток находится не в критической секции чтения, то говорят, что поток в спокойном состоянии (quiescent state, quiescent-состояние). Любой период времени, в котором каждый поток хотя бы единожды находился в quiescent-состоянии, называют grace period. Каждая критическая секция чтения, которая началась перед grace period, должна закончиться прежде, чем закончится grace period. Каждый grace period гарантированно конечен, так как любая критическая секция чтения конечна (подразумевается, что число потоков конечно, а также что мы хорошие программисты и избегаем бесконечных циклов, равно как и краха потока).


    Поток-писатель, удаляющий элемент из структуры данных, исключает элемент из структуры, а затем ждет окончания grace-периода. Окончание grace-периода означает, что ни один читатель не имеет доступа к удаляемому элементу (см. рисунок, на нем прямоугольники «reads» — это критически секции чтения). Поэтому поток-писатель может безопасно физически удалить элемент.
    Удаление производится в два этапа: первый этап — «removal» — атомарно удаляет элемент из структуры данных, но не производит физического освобождения памяти. Вместо этого писатель объявляет начало grace-периода вызовом специального примитива synchronize_rcu() и ожидает его окончания. Удаленный элемент может быть доступен только тем читателям, которые объявили свою критическую секцию чтения параллельно с писателем (на рисунке такие секции выделены серым). По определению, все такие читатели закончат свою работу перед окончанием grace-периода. По окончании grace-периода, то есть когда все критические секции чтения, инициированные или активные во время grace-периода, завершатся, наступает второй этап удаления — «reclamation» — то есть физическое удаление памяти под элемент.

    Как видим, техника синхронизации RCU довольно проста. Остается вопрос — как определить окончание grace-периода в пользовательском коде? Оригинальный RCU сильно заточен на ядро Linux, где это определить значительно проще, так как мы имеем полный контроль над всеми потоками. Для user space-кода подходы оригинального RCU неприменимы.

    User-space RCU


    Решение дал в 2009 году M.Desnoyers, представитель школы P. McKenney, в своей диссертации, глава 6 которой так и называется: User-Level Implementations of RCU.
    M.Desnoyers предлагает 3 решения для user-space RCU (URCU):
    • Quiescent-State-Based Reclamation RCU – очень легкая для читателей схема, но требующая, чтобы потоки, находящиеся вне критической секции чтения, периодически объявляли «я нахожусь в quiescent-состоянии». Такое решение не подходит для библиотеки общего назначения, которой является libcds, поэтому я его рассматривать не буду.
    • User-space RCU общего назначения (General-Purpose URCU) – подходящий для общей реализации алгоритм, который я опишу далее.
    • User-space RCU на сигналах (RCU via Signal Handling) – тоже интересный алгоритм, основанный на сигналах (подходит для *nix-систем, неприменим для Windows). Реализован в библиотеке libcds, показывает производительность чуть хуже, чем general-purpose RCU. Я не буду его рассматривать в этой статье, интересующихся отсылаю к диссертации M.Desnoyers'а и к исходным кодам libcds.


    General-Purpose URCU



    M.Desnoyers настолько подробно и тщательно разбирает алгоритм URCU, что мне остается только следовать за ним, изменив только название некоторых переменных и функций, чтобы они соответствовали принятым в libcds.

    В схеме URCU определены две переменные:
    std::atomic<uint32_t>     g_nGlobalCtl(1) ;
    struct thread_record {
       std::atomic<uint32_t>  nThreadCtl;
       thread_record *        pNext;
    
       thread_record(): nThreadCtl(0), pNext(nullptr) {}
    };
    

    Структура thread_record содержит локальные для потока данные и связывает все такие объекты в список RCU-потоков.
    Младшие 31 бита nThreadCtl содержит счетчик глубины вложенности вызовов URCU (да, URCU допускает практически неограниченную вложенность критических секций чтения), старший бит определяет идентификатор grace-периода на момент входа потока в критическую секцию чтения. В описываемой схеме достаточно только двух идентификаторов для grace-периода.
    Старший бит глобальной переменной g_nGlobalCtl содержит идентификатор текущего grace-периода, младшие биты служат для инициализации per-thread переменных nThreadCtl и не изменяются.
    Для входа/выхода в/из критической секции чтения служат функции access_lock и access_unlock соответственно:
    static uint32_t const c_nControlBit = 0x80000000;
    static uint32_t const c_nNestMask =  c_nControlBit — 1;
    
    void access_lock()
    {
       thread_record * pRec = get_thread_record();
       assert( pRec != nullptr );
    
       uint32_t tmp = pRec->nThreadCtl.load( std::memory_order_relaxed );
       if ( (tmp & c_nNestMask) == 0 ) {
           pRec->nThreadCtl.store(g_nGlobalCtl.load( std::memory_order_relaxed ),
                std::memory_order_relaxed );
           std::thread_fence( std::memory_order_acquire );
       }
       else
           pRec->nThreadCtl.fetch_add( 1, std::memory_order_relaxed );
    }
    
    void access_unlock()
    {
       thread_record * pRec = get_thread_record();
       assert( pRec != nullptr );
    
       pRec->nThreadCtl.fetch_sub( 1, std::memory_order_release );
    }
    

    При входе в критическую секцию URCU проверяется, вложенный это вызов или нет. Если вызов вложенный (то есть счетчик в младших 31 бите не ноль), счетчик вложенности просто инкрементируется. Если же вызов не вложенный, переменной nThreadCtl текущего потока присваивается значение глобальной переменной g_nGlobalCtl; тем самым помечается, что вход в критическую секцию был произведен в определенный grace-период (старший бит g_nGlobalCtl), а единица в младших битах g_nGlobalCtl инициализирует счетчик вложенности текущего потока. При первом, самом внешнем входе в критическую секцию применяется acquire-барьер памяти. Он гарантирует, что последующий код не будет перенесен («оптимизирован») вверх за барьер ни процессором, ни компилятором. Тем самым обеспечивается видимость текущего grace-периода потока всем процессорам, — если нарушить этот порядок, алгоритм URCU рассыплется. При входе во вложенную критическую секцию барьера не требуется, так как текущий grace-период (старший бит) не изменяется.
    При выходе из критической секции (access_unlock) просто декрементируется счетчик вложенности в nThreadCtl текущего потока. Применяется release-семантика атомарной операции; на самом деле, release-барьер необходим здесь только при выходе из самой верхней критической секции (при переходе от 1 к 0 счетчика вложенности), при выходе из вложенной критической секции достаточно relaxed-семантики. Release-барьер при обнулении счетчика требуется потому, что при переходе счетчика вложенности от 1 к 0 фактически происходит объявление «поток более не использует RCU», то есть выход из grace-периода, что является критическим для алгоритма URCU, — нарушение порядка компилятором или процессором приведет к неработоспособности алгоритма. Распознание ситуаций «0 — не 0» в коде потребует условного перехода, что вряд ли добавит производительности функции access_unlock, да и основной паттерн использования критических секций URCU – без вложенности, поэтому release-семантика применяется здесь всегда.

    Как видно, код со стороны читателей довольно легковесный. Используются атомарные чтение-запись и thread-local данные. Конечно, это не zero-overhead, но все же намного лучше, чем мьютекс или CAS.

    Поток-писатель перед тем, как физически удалить элемент, должен убедиться, что grace-период завершен. Условия окончания grace-периода — одно из двух:
    • Младшие биты (счетчик вложенности) nThreadCtl каждого потока равны нулю, что означает, что поток не находится в критической секции URCU
    • Старший бит nThreadCtl не совпадает с со старшим битом g_nGlobalCtl, что означает, что читатель вошел в критическую секцию после начала grace-периода

    Эти условия проверяются следующей функцией:
    bool check_grace_period( thread_record * pRec )
    {
       uint32_t const v = pRec->nThreadCtl.load( std::memory_order_relaxed );
       return (v & general_purpose_rcu::c_nNestMask)
          && ((( v ^ g_nGlobalCtl.load( std::memory_order_relaxed )) & ~c_nNestedMask ));       }
    

    Писатель перед физическим удалением вызывает функцию synchronize, которая ожидает окончания текущего grace-периода:
    std::mutex  g_Mutex ;
    void synchronize()
    {
       std::atomic_thread_fence( std::memory_order_acquire );
       {
          cds::lock::scoped_lock<std::mutex> sl( g_Mutex );
          flip_and_wait();
          flip_and_wait();
       }
       std::atomic_thread_fence( std::memory_order_release );
    }
    

    Здесь g_Mutex — глобальный для алгоритма URCU мьютекс (да-да! URCU все же техника синхронизации, так что без мьютекса никуда). Таким образом, только один поток-писатель может войти в synchronize. Не забываем, что RCU позиционируется для «почти read-only» данных, так что особой толкотни на этом мьютексе не ожидается.
    Писатель ожидает окончания grace-периода, вызывая функцию flip_and_wait:
    void flip_and_wait()
    {
       g_nGlobalCtl.fetch_xor( c_nControlBit, std::memory_order_seq_cst );
       for (thread_record* pRec = g_ThreadList.head(std::memory_order_acquire);
             pRec!= nullptr; 
             pRec = pRec->m_pNext ) 
       {
         while ( check_grace_period( pRec )) 
         {
            sleep( 10 ); // ждем 10 миллисекунд
            CDS_COMPILER_RW_BARRIER ;
         }
       }
    }
    

    Эта функция меняет идентификатор grace-периода, что означает начало нового grace-периода, с помощью атомарного fetch_xor и ждет (вызовом check_grace_period), пока все потоки-читатели не закончат этот новый grace-период. В псевдокоде ожидание происходит простым sleep на 10 миллисекунд, в реальном коде libcds используется template-параметр, задающий back-off-стратегию.

    Почему писатель вызывает flip_and_wait дважды? Для пояснения рассмотрим такую последовательность действий с двумя потоками A и B. Предположим, что вызов flip_and_wait в synchronize только один:
    • Поток A вызывает access_lock. В теле этой функции определяется, что вызов не вложенный, читается глобальный g_nGlobalCtl, но пока не присваивается переменной nThreadCtl потока (все выполняется параллельно, так что такая ситуация вполне допустима)
    • Поток B вызывает synchronize. Вызывается первый flip_and_wait, который изменяет бит-идентификатор grace-периода в g_nGlobalCtl. Текущим идентификатором grace-периода становится 1
    • Так как в критической секции URCU никого нет (вспомним, что поток A ещё не успел присвоить значение своей переменной nThreadCtl), поток B завершает synchronize
    • Поток A выполняет присваивание своей переменной nThreadCtl. Вспомним, что поток прочитал старое значение grace-периода, равное 0
    • Поток A завершает access_lock и продолжает выполнение в критической секции
    • Поток B вызывает synchronize ещё раз (видимо, опять хочет что-то удалить). Опять происходит обращение текущего grace-периода в g_nGlobalCtl, так что его идентификатор теперь 0.

    Но поток A в критической секции, которая началась ранее, чем B изменил grace-период! Нарушение семантики URCU, которое приведет со временем ко всему букету — от ABA до memory corruption. Вспомним: synchronize вызывается писателем перед тем, как физически удалить память под элемент

    Вызывая flip_and_wait дважды, то есть дважды ожидая окончания grace-периода, мы решаем вышеописанную проблему, причина которой — конкурентное выполнение потоков.
    Другое решение
    Можно, конечно, решить эту проблему и по-другому, если использовать вместо бита-идентификатора grace-периода некий счетчик. Но тут возникает проблема, которую мы уже видели в статье про алгоритм tagged pointer, — счетчик подвержен переполнению! Для надежности счетчик должен быть 32-битным, тогда переполнение нам не страшно. Но такой счетчик приводит к необходимости иметь 64-битный атомарный тип на 32-битовых платформах. Такого типа либо нет, либо он довольно неэффективен. Либо нам придется отказаться от вложенности критических секций URCU, что тоже не очень удобно.
    Поэтому остановимся на общем решении с битом в качестве идентификатора grace-периода и вызовом двух flip_and_wait


    Реализация URCU в libcds



    Вышеописанный алгоритм URCU хорош всем, кроме того, что перед каждым удалением требуется вызывать довольно тяжелый synchronize. Можно ли как-то это улучшить?
    Да, можно, причем таким же методом, как и в алгоритме Hazard Pointer, — применить отложенное удаление. Будем вместо удаления помещать элементы в некоторый буфер. Функцию synchronize будем вызывать только когда буфер заполнится. В отличие от Hazard Pointer, в URCU буфер будет общим для всех потоков (вообще, можно сделать и per-thread буферы, ничто этому не мешает).
    Более того, чтобы не тормозить писателя, на долю которого выпала доля чистить буфер при его переполнении, функционал очистки буфера, то есть действительного удаления, можно поручить отдельному потоку.

    Библиотека libcds имеет пять реализаций URCU, все они живут в пространстве имен cds::urcu:
    • general_instant — реализация, точно следующая описанному алгоритму URCU: каждое удаление вызывает synchronize, никакой буферизации. Если удаление у нас довольно частая операция, то есть структура не слишком-то «почти read-only», данная реализация довольно тормозная
    • general_buffered — реализация с общим lock-free буфером предопределенного размера. В качестве lock-free буфера используется очередь Дмитрия Вьюковаcds::container::VyukovMPMCCycleQueue. Производительность такой реализации сравнима с Hazard Pointer
    • general_threaded — подобна general_buffered, но очистку буферов производит выделенный поток. Такая реализация немного уступает general_buffered за счет дополнительной синхронизации с выделенным потоком, зато не тормозит писателей
    • signal_buffered — аналог general_buffered, но основан на signal-handled URCU. Не для Windows-систем
    • signal_threaded — аналог general_threaded для signal-handled URCU. Также не для Windows


    Такое обилие реализаций URCU порождает проблему написания специализаций контейнеров под URCU. Дело в том, что реализация контейнеров под схему URCU значительно отличается от реализации для Hazard Pointer. Поэтому требуется отдельная специализация для URCU. Хотелось бы иметь одну специализацию, а не пять.
    Для облегчения написания специализации под URCU был введен класс-обертка cds::urcu::gc:
    template <typename RCUimpl> class gc;
    

    где RCUimpl — одна из реализаций URCU: general_instant, general_buffered и т. д. Имея такую обертку, специализацию для URCU написать легко и она будет единственной:
    template <
       class RCU,
       typename Key,
       typename Value,
       class Traits
    >
    class SplitListMap< cds::urcu::gc< RCU >, Key, Value, Traits > ...
    


    Cледует отметить, что в libcds основной функцией алгоритма URCU при удалении является не synchronize, а retire_ptr. Эта функция помещает удаляемый элемент в буфер URCU и в нужный момент (например, когда буфер заполнен) вызывает synchronize. Так что явный вызов synchronize не требуется, хотя и допустим. К тому же такое решение унифицирует интерфейс URCU и Hazard Pointer.

    Все перечисленные алгоритмы URCU реализованы в типичной для libcds манере: для каждой существует глобальный объект-синглтон, инициализация которого происходит вызовом конструктора объекта-обертки cds::urcu::gc<cds::urcu::general_buffered<> > в начале main(), после вызова cds::Initialize():
    #include <cds/init.h>  //cds::Initialize и cds::Terminate
    #include <cds/gc/general_buffered.h> // general_buffered URCU
    
    int main(int argc, char** argv)
    {
        // Инициализируем libcds
        cds::Initialize() ;
       {
           // Инициализируем general_buffered URCU синглтон
           cds::urcu::gc<cds::urcu::general_buffered<> > gbRCU ;
    
           // Если main thread использует lock-free контейнеры
           // main thread должен быть подключен 
           // к инфраструктуре libcds
           cds::threading::Manager::attachThread() ;
    
          // Всё, libcds готова к использованию
          // Далее располагается ваш код
          ...
       }
    
       // Завершаем libcds
       cds::Terminate() ;
    }
    
    


    Так же, как и для схемы Hazard Pointer, каждый поток, использующий URCU-контейнеры, должен быть инициализирован особым образом:
    // 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;
    }
    


    Использование URCU-контейнеров библиотеки libcds совершенно прозрачно: достаточно просто объявить объект-контейнер с URCU gc, — и всё. Вся специфика работы с URCU спрятана внутри URCU-специализации контейнера. Никакой внешней синхронизации при доступе к такому контейнеру не требуется.
    UPD: Упс!
    «Никакой внешней синхронизации не требуется» — это я несколько погорячился.
    На самом деле, некоторые методы некоторых URCU-контейнеров требуют предварительного входа в критическую секцию чтения. Как правило, это методы удаления (извлечения) элемента контейнера. URCU может обеспечить нам возможность возврата указателя на найденный по ключу элемент. Такая возможность — редкое исключение в мире lock-free, где обычно возврат указателя смерти подобен, так как элемент может быть удален в любой момент конкурирующим потоком. Но чтобы безопасно работать с возвращенным указателем на элемент, мы должны находится в критической секции чтения. Так что в этом случае следует явно перед вызовом метода контейнера вызвать access_lock, а по завершении работы с указателем — access_unlock, а лучшей (exception-safe) методикой будет применение scoped-lock в отдельном блоке кода.
    В описании каждого метода URCU-контейнера библиотеки libcds отмечается, как следует вызывать данный метод — в критической секции или нет.

    Если же вы решитесь сделать свой собственный класс контейнера, основанный на реализации URCU из libcds, следует подробно разобраться с внутренним устройством URCU-контейнеров библиотеки. В принципе, ничего сверхестественного нет: при входе в метод вызываем gc::access_lock(), при выходе — gc::access_unlock() (здесь gc — это одна из реализаций URCU; для безопасности исключений лучше использовать технику scoped lock вместо вызова функций). Единственный тонкий момент — удаление элемента: метод удаления также должен входить в критическую секцию чтения, но физическое удаление элемента, осуществляемое вызовом gc::retire_ptr, должно производиться вне критической секции, иначе возможен deadlock: метод gc::retire_ptr внутри может вызвать synchronize.

    Libcds определяет URCU-специализации для всех классов set и map. URCU-специализации для контейнеров типа «очередь» и «стек» не определено, — это не «почти read-only» контейнеры, так что URCU не для них.

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 19

      –2
      Фраза «В некоторый безопасный момент времени, когда нет читателей...» напомнила
      не моргай
      image
        +1
        1. Правильно ли я понимаю алгоритм работы с контейнером на чтение:
          scoped_lock lock(map);
          auto v = map[key];
          // Работаем с v...
          

          То есть, код работающий с контейнером сам должен вызвать access_lock() у контейнера или gc?

        2. Правильно ли я понимаю проблему с одним вызовом flip_and_wait()?
          • После того, как поток A входит в критическую секцию, то есть после выхода из access_lock(), он находит в контейнере указатель на объект E, сохраняет этот указатель локально и начинает работать с E.
          • В это время поток B удаляет из контейнера объект E и вызывает synchronize(), чтобы дождаться когда все потоки выйдут из своих критических секций, а после этого удалить E. Но сразу же выходит из synchronize(), так как идентификатор grace-периода у A равен 0, и текущий идентификатор grace-периода равен 0, то есть считается, что A находится в критической секции, которая началась уже после вызова synchronize(), что не так. Поэтому поток B удаляет E, а после этого в A происходит обращение к не выделенному участку памяти.

        3. Вы могли бы подробнее объяснить зачен нужен двойной вызов flip_and_wait()?
          Зачем нужен бит, показывающий номер текущего grace-периода, если мы всё равно сначала ждём завершения критических секций начатых при одном значении бита, а потом при другом? Разве нельзя избавиться от этого бита и в synchronize() один раз вызывать flip_and_wait(), где для каждого потока ждать завершения критической секции, в которой он находится в данный момент? Вроде бы при двойном flip_and_wait() так и происходит: сначала ждём завершения критических секций начатых в grace-периоде 0, а потом в grace-периоде 1, то есть всех критических секций.
          +1
          Хорошие вопросы, спасибо! Отвечу сначала на первый.
          Как всегда, ответ будет двоякий, — и не правильно, и правильно.
          Для большинства методов внешнюю rcu-блокировку своими силами выставлять не нужно. Все методы контейнеров делают это сами: блокируют и разблокируют RCU в своем теле там, где нужно.
          Более того, для erase-методов (тех, кто удаляет элементы из контейнера) это недопустимо, так как erase-методы в своем теле требуют вызова rcu.retire_ptr(). А rcu.retire_ptr() приводит (или может приводить в случае буферизованного rcu) к rcu.synchronize(), который ожидает завершения текущего grace-периода, то есть снятия блокировки. Получим deadlock.
          Поэтому в описании erase-методов на кошерном нижегородском английском явно написано, что RCU не должен быть блокирован.

          Но. Сейчас я работаю над новой фичей: добавить в lock-free set/map методы, возвращающие указатель на элемент контейнера. Это будут методы get() — поиск элемента по ключу, и extract() — удаление по ключу, оба возвращают указатель на найденный элемент. В RCU-специализациях таких контейнеров придется блокировать RCU перед вызовом явно в пользовательском коде, — именно то, что вы написали.

          Вопросы 2 и 3 взаимосвязаны и требуют приложения мозга. Попробую составить пример с одним flip-and-wait, который ломает RCU. Отвечу позже
            0
            Наконец-то посмотрел документацию, теперь понял как выполняется блокировка RCU внутри методов котейнеров. С lock-free контейнерами раньше не работал, поэтому и был вопрос про внешнюю блокировку, сейчас понял как всё работает и что за новую фичу вы собираетесь сделать.
            +1
            Попробую ответить на вопросы 2 и 3 на примере, — показать, что один flip_and_wait() приводит к проблеме. Отсюда же вытекает необходимость идентификатора grace-периода в один бит.
            Предположим, мы имеем один вызов flip_and_wait() в synchronize().
            Имеем потоки A, B, C.

            1. Поток A выполняет поиск E, поток C — удаление того же E. Оба не блокированы, входят в методы find/erase и вызывают access_lock(). В этом методе они успели прочитать текущее значение g_nGlobalCtl, в котором текущий grace-id = 0, но ещё не успели записать его в свои m_nThreadCtl.
            2. Поток B вызывает rcu.synchronize(). Вызывается flip_and_wait(), который меняет текущий grace-id на 1 (grace-id — идентификатор текущего grace-периода) и ждет окончания потоков A и C. Они ещё не успели указать, что находятся в критической секции, так что flip_and_wait() со свистом пролетает (в смысле завершается). Текущий grace-id=1.
            3. Потоки A и C сохраняют ранее прочитанный g_nGlobalCtl (в котором grace-id=0) в своих локальных m_nThreadCtl. Таким образом, они находятся в grace-период 0. Упс! Пока что только нарушение семантики RCU, ничего страшного.
            4. Поток A отыскал элемент E и собирается что-то с ним делать (вызов функтора), а поток C — удалил его.
            5. Поток C: при удалении вызывается rcu.synchronize(). Вызывается flip_and_wait(), который меняет текущий grace-id на 0 и ждет выхода A из предыдущего (xor — см. check_grace_period()) grace-периода. У потока A grace-id=0, текущий grace-id=0, их xor = 0 — можно выходить из rcu.synchronize() и удалять E.
            6. А в это время A вызывает user-функтор с параметром «ссылка на E»…

            Вроде бы, вполне реалистичный сценарий. Уверен, что можно найти и другие сценарии. Двойной вызов flip_and_wait() нас здесь спасает.
              +1
              Давайте, чтобы прийти к полному взаимопониманию, вы мне объясните всё с азов.
              Предположим, что мы работаем с map. Вопрос: какие значения лежат в map, объекты целиком или указатели на эти объекты, а сами объекты в динамической памяти?

              Как я понимаю, объект в map лежать не может, из-за того, что следующий псевдокод:
              erase(E_key) {
                  найти объект E;
                  вызвать synchronize(), чтобы дождаться момента, когда можно быть уверенным что никто не держит ссылок на E;
                  удалить объект E из map;
              }
              

              работать не будет. Так как между 2-м и 3-м шагом может появиться новый читатель, который получит ссылку на E, которая станет невалидной после 3-го шага.
              То есть, по-моему в данном случае для удаления элементов из map надо получить её в монопольный доступ, а это уже не lock-free алгоритм.

              Если же в map лежит указатель на объект, то удаление выполняется так:
              erase(E_key) {
                  используя lock-free алгоритм исключить указатель на E из map;
                  вызвать synchronize(), чтобы дождаться момента, когда можно быть уверенным что никто не держит указателей на E;
                  освободить память, занимаемую E;
              }
              

              Если ответ на вопрос выше — в map лежат указатели, то на 4-м шаге поток C исключил указатель на E из map, но сам объект ещё не удалил, удаление будет произведено на 5-м шаге, после выхода из rcu.synchronize(). Правильно?

              Если ответ да, то я не понимаю в чём может быть проблема при отсутствии grace-id и одном вызове flip_and_wait():

              2. Поток B вызывает rcu.synchronize(). Так как A и C ещё не вошли в критические секции, то он выходит из rcu.synchronize() и выполняет что хотел.

              5. Поток C хочет дождаться момента, когда можно освободить память, занимаемую E. Он вызывает rcu.synchronize() и, так как никаких grace-id нет, а поток A находится в критической секции, то ждёт выхода A из критической секции.
              6. Поток A завершает работу с E и выходит из критической секции.
              7. Поток C дождался выхода A из критической секции, так как другие потоки вне критической секции, он освобождает память, занимаемую E.
              Проблем не возникло.
              Или в моих рассуждениях где-то есть ошибка?
                +1
                В map лежат указатели. Да, erase всегда двухфазный: сначала мы удаляем (исключаем) элемент из map а ля lock-free, а затем, в подходящий момент времени, когда никто не держит ссылок на элемент, — удаляем (free) сам элемент. Одно и то же слово «удаляет» означает две совершенно разные вещи на «великом и могучем»…

                Кажется, я понимаю, что вы хотите сказать. Что-то очень напоминающее reference counting. Да, такая схема должна работать, но в ней вам придется при входе в критическую секцию чтения вызывать атомарную RMW-операцию atomic.fetch_and_add для инкремента счетчика критической секции, а при выходе — atomic.fetch_and_sub. Считается (не без оснований), что RMW-атомики довольно тяжелы, и чем мощнее железо, тем они тяжелее (это уже мое наблюдение). В RCU стремились как можно более облегчить read-часть, поэтому предложили схему, где access_lock/access_unlock использует только атомарные чтение/запись.
                  +1
                  Да, проблемы с терминологией есть, поэтому пытаюсь использовать слово «исключение» для удаления из контейнера, и «освобождение памяти» для операции delete.

                  Судя по ответам на базовые вопросы, у меня правильное понимание обсуждаемой проблемы, так что можно продолжить обсуждение алгоритма.

                  Вот предлагаемое мной решение:

                  // g_nGlobalCtl - не нужна
                  struct thread_record {
                     std::atomic<uint32_t>  nThreadCtl;
                     thread_record *        pNext;
                  
                     thread_record(): nThreadCtl(0), pNext(nullptr) {}
                  };
                  
                  
                  // c_nControlBit и c_nNestMask не нужны
                  
                  void access_lock()
                  {
                     thread_record * pRec = get_thread_record();
                     assert( pRec != nullptr );
                  
                     uint32_t tmp = pRec->nThreadCtl.load( std::memory_order_relaxed );
                     if ( tmp == 0 ) {
                         // Так как grace-id нет, то nThreadCtl выступает лишь в качестве счётчика вложенности
                         pRec->nThreadCtl.store(1, std::memory_order_relaxed );
                         std::thread_fence( std::memory_order_acquire );
                     }
                     else
                         pRec->nThreadCtl.fetch_add( 1, std::memory_order_relaxed );
                  }
                  
                  void access_unlock()
                  {
                     thread_record * pRec = get_thread_record();
                     assert( pRec != nullptr );
                  
                     pRec->nThreadCtl.fetch_sub( 1, std::memory_order_release );
                  }
                  
                  bool check_grace_period( thread_record * pRec )
                  {
                     uint32_t const v = pRec->nThreadCtl.load( std::memory_order_relaxed );
                     // Проверка нахождения в критической секции простая, так как не надо сравнивать grace-id
                     return 0 != v;
                  }
                  
                  std::mutex  g_Mutex;
                  
                  void synchronize()
                  {
                     std::atomic_thread_fence( std::memory_order_acquire );
                     {
                        cds::lock::scoped_lock<std::mutex> sl( g_Mutex );
                        // Двойной вызов flip_and_wait() не нужен
                        wait();
                     }
                     std::atomic_thread_fence( std::memory_order_release );
                  }
                  
                  // Никакого flip нет, потому функция называется просто wait
                  void wait()
                  {
                     // flip не нужен, так как нет grace-id
                     for (thread_record* pRec = g_ThreadList.head(std::memory_order_acquire);
                           pRec!= nullptr; 
                           pRec = pRec->m_pNext ) 
                     {
                       while ( check_grace_period( pRec )) 
                       {
                          sleep( 10 ); // ждем 10 миллисекунд
                          CDS_COMPILER_RW_BARRIER ;
                       }
                     }
                  }
                  
                  

                  Барьеры памяти я ещё не освоил до конца, поэтому они такие же как в вашем коде.

                  Рассуждения следующие:
                  RCU используем только для определения момента, когда можно освободить память из-под элемента, ранее исключённого из контейнера. Это гарантированно можно сделать когда все потоки выйдут из критических секций, в которых они находились в момент вызова synchronize(). Некоторые критические секции могли начаться после исключения элемента, но до вызова synchronize(), так что можно было бы не ждать окончания таких критических секций, но ожидание их завершения лишь скажется на времени работы synchronize(), но не нарушит логику работы. Так как корректность алгоритма важнее, то будем ждать окончания завершения таких критических секций.
                  Как реализовать ожидание: в synchronize() проверяем каждый поток, если он находится в критической секции, то ждём её завершения и переходим к следующему потоку.
                  Худший случая для данного варианта, это когда потоки-читатели постоянно находятся в критических секциях, в результате придётся ждать завершения критической секции для каждого потока:


                  Худший случай для двойного вызова flip_and_wait(), это когда сначала для потока 1 ждём выхода из критической секции, в которую он вошёл при grace-id == 0, потом пока ждали выхода других потоков из их критических секций, поток 1 опять входит в критическую секцию при grace-id == 1, при втором вызове flip_and_wait() надо опять ждать выход из критической секции потока 1:


                  На мой взгляд решение без grace-id имеет право на жизнь. Выбор подходящего варианта зависит от того, как часто потоки читатели входят в критические секции, сколько времени они там проводят, сколько потоков работают параллельно и используемой back-off-стратегии.
                    +1
                    Единственное «но», которое я вижу в вашей схеме без grace-id, — нет гарантии завершения grace-периода, его продолжительность может быть сколь угодно большой. Если один поток вызвал synchronize(), а другие читатели очень плотно работают со структурой данных, постоянно входя/выходя в/из критические секции чтения, то grace-период может никогда не закончиться.

                    В схеме же со flip_and_wait() время ожидания ограничено. Да, придется ждать окончания grace-id=0 и grace-id=1, но ситуация с бесконечным ожиданием может возникнуть только при крахе потока-читателя (или ошибки в реализации RCU), но крах потока обычно приводит к аварийному завершению всей программы. Без этих граничных случаев (крах потока/ошибка) ожидание гарантированно конечное.

                    PS: В моем предыдущем комментарии рассуждения насчет «RCU использует только атомарные чтение/запись» прошу считать бредом. Конечно, используются RMW fetch_add/fetch_sub.
                      +1
                      В моём варианте ожидание всё же конечно, если набор набор потоков-читателей фиксирован и фиксирован их порядок в списке g_ThreadList, то каждый поток будем ждать по одному разу. Если же будут постоянно появляться новые потоки и добавляться в конец списка, то тогда ожидание может быть бесконечным. Это недостаток 1.

                      Недостаток 2. Длительность ожидания в одном вызове flip_and_wait() определяется временем выполнения самой длинной критической секции среди всех потоков. А в моём варианте, ожидание определяется как сумма критических секций для всех потоков. То есть, при большом количестве потоков-читателей занимает намного больше времени.

                      Вот и ответ, зачем нужен grace-id и почему под него достаточно 1 бита.
                        +1
                        Да, действительно, ожидание конечно, согласен, был неправ.

                        Одно замечание: в вашем алгоритме ситуация может быть даже хуже, чем сумма критических секций всех потоков. Если ожидающий в synchronize() поток будет вытеснен (а это может произойти и при выборе неподходящей back-off стратегии: sleep() или yield()), то он может и не заметить, что один из читателей вышел из критической секции и вошел в неё снова. Получается, что ожидающий поток не должен вытесняться вовсе, — очень жесткое, часто невыполнимое (так как мы не можем управлять ядром ОС) требование.

                        Вы заставляете работать мозгами ;-), спасибо!
                          0
                          Действительно, никогда бы о таком не подумал. Получается, если читатель постоянно находится в критических секциях (вышел из одной, сразу вошёл в другую), то ожидающему потоку будет очень сложно попасть в окно между этими критическими секциями и ожидание может быть очень длительным. Вот и недостаток № 3, самый серьёзный.

                          Вам огромное спасибо за статьи, узнаю из них много нового.
                        0
                        Что-то очень напоминающее reference counting. Да, такая схема должна работать, но в ней вам придется при входе в критическую секцию чтения вызывать атомарную RMW-операцию atomic.fetch_and_add для инкремента счетчика критической секции, а при выходе — atomic.fetch_and_sub.

                        PS: В моем предыдущем комментарии рассуждения насчет «RCU использует только атомарные чтение/запись» прошу считать бредом. Конечно, используются RMW fetch_add/fetch_sub.


                        Фактически RCU с grace-period использует reference counting с тагированным счетчиком в переменной nThreadCtl (таг grace-периода в последнем бите 0x80000000 счетчика для защиты от ABA-проблемы).
                  +1
                  Что-то я начал с азов и быстро перешёл к обсуждению алгоритма :), а ещё один важный вопрос не спросил:
                  Правильно ли я понимаю, что map — это lock-free структура данных, и RCU нам нужен лишь для того, чтобы освобождать память после исключения указателей на объекты из map? И так как map — lock-free, то мы можем без блокировок её модифицировать добавляя и исключая элементы, а также выполнять поиск в ней (чтение)?
                    +1
                    Да, все правильно. В libcds RCU используется как алгоритм SMR (safe memory reclamation, безопасное освобождение памяти). В остальном все RCU-контейнеры построены на lock-free технике. Никаких блокировок не нужно, если иное не отмечено в описании метода, см. часть Но в моем комменте
                0
                Изобрёл свой велосипед, наткнулся на пост, и возник вопрос: почему так сложно?
                Почему бы просто не сделать массив с указателями (например, тремя) и бегать по этому массиву счётчиком? При каждой записи мы просто лочим на запись, записываем в текущий элемент (следующий относительно «итератора чтения») массива, а затем инкрементируем итератор чтения. Остаётся только подождать, пока предыдущий элемент перестанут читать.

                Набросал код:
                Код
                #include <atomic>
                #include <array>
                #include <thread>
                
                
                template <typename Value_type>
                struct Cell
                {
                  Value_type read()
                  {
                    ++_readers_counter;
                    auto result = _value;
                    --_readers_counter;
                    return  result;
                  }
                
                  std::atomic<short> _readers_counter;
                
                  Value_type _value;
                };
                
                template <typename Value_type>
                class Lock_free_cell
                {
                
                  Lock_free_cell() :
                    _read_cell_pointer_id(0),
                    _pointers({new Cell<Value_type>{0},
                               new Cell<Value_type>{0},
                               new Cell<Value_type>{0},
                               new Cell<Value_type>{0}})
                  {  }
                
                  Value_type read()
                  {
                    auto cell_pointer = _pointers[_read_cell_pointer_id.load() % 4];
                    auto result = cell_pointer->read();
                
                    return result;
                  }
                
                  bool write(const Value_type& new_value)
                  {
                    while (_is_write.test_and_set())
                    {
                      std::this_thread::sleep_for(std::chrono::milliseconds(10));
                    }
                
                    auto read_pointer_index = _read_cell_pointer_id.load();
                    _pointers[(read_pointer_index + 1) % 4]->_value  = new_value;
                    ++_read_cell_pointer_id;
                
                    auto previous_read_pointer = _pointers[read_pointer_index % 4];
                    while (previous_read_pointer->_readers_counter.load() != 0)
                    {
                      std::this_thread::sleep_for(std::chrono::milliseconds(10));
                    }
                
                    _is_write.clear();
                
                    return true;
                  }
                
                private:
                  std::atomic<unsigned char> _read_cell_pointer_id;
                
                  std::atomic_flag _is_write;
                
                  std::array<Cell<Value_type>*, 4> _pointers;
                };
                


                  0
                  Честно говоря, я из кода не понял, каким образом он что-либо защищает и что он гарантирует…
                    0
                    Упс, нашёл ошибку: после получения указателя для чтения, поток может заснуть и инкрементировать счётчик чтения уже в момент записи.
                  0
                  del

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое