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

[dtestyk]

Фраза «В некоторый безопасный момент времени, когда нет читателей...» напомнила

не моргай

[yupic]

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, то есть всех критических секций.
   

[khizmax]

Хорошие вопросы, спасибо! Отвечу сначала на первый.
Как всегда, ответ будет двоякий, — и не правильно, и правильно.
Для большинства методов внешнюю 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. Отвечу позже

[yupic]

Наконец-то посмотрел документацию, теперь понял как выполняется блокировка RCU внутри методов котейнеров. С lock-free контейнерами раньше не работал, поэтому и был вопрос про внешнюю блокировку, сейчас понял как всё работает и что за новую фичу вы собираетесь сделать.

[khizmax]

Попробую ответить на вопросы 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() нас здесь спасает.

[yupic]

Давайте, чтобы прийти к полному взаимопониманию, вы мне объясните всё с азов.
Предположим, что мы работаем с 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.
Проблем не возникло.
Или в моих рассуждениях где-то есть ошибка?

[khizmax]

В map лежат указатели. Да, erase всегда двухфазный: сначала мы удаляем (исключаем) элемент из map а ля lock-free, а затем, в подходящий момент времени, когда никто не держит ссылок на элемент, — удаляем (free) сам элемент. Одно и то же слово «удаляет» означает две совершенно разные вещи на «великом и могучем»…

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

[yupic]

Да, проблемы с терминологией есть, поэтому пытаюсь использовать слово «исключение» для удаления из контейнера, и «освобождение памяти» для операции 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-стратегии.

[khizmax]

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

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

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

[yupic]

В моём варианте ожидание всё же конечно, если набор набор потоков-читателей фиксирован и фиксирован их порядок в списке g_ThreadList, то каждый поток будем ждать по одному разу. Если же будут постоянно появляться новые потоки и добавляться в конец списка, то тогда ожидание может быть бесконечным. Это недостаток 1.

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

Вот и ответ, зачем нужен grace-id и почему под него достаточно 1 бита.

[khizmax]

Да, действительно, ожидание конечно, согласен, был неправ.

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

Вы заставляете работать мозгами ;-), спасибо!

[yupic]

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

Вам огромное спасибо за статьи, узнаю из них много нового.

[AlexeyAB]

Что-то очень напоминающее 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-проблемы).

[yupic]

Что-то я начал с азов и быстро перешёл к обсуждению алгоритма :), а ещё один важный вопрос не спросил:
Правильно ли я понимаю, что map — это lock-free структура данных, и RCU нам нужен лишь для того, чтобы освобождать память после исключения указателей на объекты из map? И так как map — lock-free, то мы можем без блокировок её модифицировать добавляя и исключая элементы, а также выполнять поиск в ней (чтение)?

[khizmax]

Да, все правильно. В libcds RCU используется как алгоритм SMR (safe memory reclamation, безопасное освобождение памяти). В остальном все RCU-контейнеры построены на lock-free технике. Никаких блокировок не нужно, если иное не отмечено в описании метода, см. часть Но в моем комменте

[Centimo]

Изобрёл свой велосипед, наткнулся на пост, и возник вопрос: почему так сложно?
Почему бы просто не сделать массив с указателями (например, тремя) и бегать по этому массиву счётчиком? При каждой записи мы просто лочим на запись, записываем в текущий элемент (следующий относительно «итератора чтения») массива, а затем инкрементируем итератор чтения. Остаётся только подождать, пока предыдущий элемент перестанут читать.

Набросал код:

Код

#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;
};

[khizmax]

Честно говоря, я из кода не понял, каким образом он что-либо защищает и что он гарантирует…

[Centimo]

Упс, нашёл ошибку: после получения указателя для чтения, поток может заснуть и инкрементировать счётчик чтения уже в момент записи.

[khizmax]

del