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

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