void push(T const& data) {
counted_node_ptr new_node;
new_node.ptr = new node(data);
new_node.external_count = 1;
new_node.ptr->next = head.load(std::memory_order_relaxed);
while (!head.compare_exchange_weak(
new_node.ptr->next, new_node,
std::memory_order_release, std::memory_order_relaxed));
}
А что можно сказать о коде pop()? Чтобы получить желаемое отношение происходит-раньше, перед доступом к next необходима операция с семантикой std::memory_order_acquire или более сильной. Указатель, который разыменовывается для доступа к полю next, — это прежнее значение, прочитанное операцией compare_exchange_strong() в increase_head_count(), поэтому указанная семантика нужна в случае успеха. Как и в push(), если обмен закончился неудачно, мы просто повторяем цикл, поэтому для отказа можно задать ослабленное упорядочение:
void increase_head_count(counted_node_ptr& old_counter) {
counted_node_ptr new_counter;
do {
new_counter = old_counter;
++new_counter.external_count;
}
while (!head.compare_exchange_strong(
old_counter, new_counter,
std::memory_order_acquire, std::memory_order_relaxed));
old_counter.external_count = new_counter.external_count;
}
Если вызов compare_exchange_strong() завершается успешно, то мы знаем, что раньше в поле ptr прочитанного значения находилось то, что теперь хранится в переменной old_counter. Поскольку сохранение в push() было операцией освобождения, а данный вызов compare_exchange_strong() — операция захвата, то сохранение синхронизируется-с загрузкой, и мы имеем отношение происходит-раньше. Следовательно, сохранение в поле ptr в push() происходит-раньше доступа к ptr->next в pop(), и мы в безопасности.
Отметим, что для этого анализа порядок доступа к памяти в начальном вызове head.load() не имел значения, поэтому в нем безопасно задать семантику std::memory_order_relaxed.
Далее на очереди операция compare_exchange_strong(), которая записывает в head значение old_head.ptr->next. Нужно ли наложить на нее какие-нибудь ограничения, чтобы гарантировать целостность данных в этом потоке? Если обмен завершается успешно, то мы обращаемся к ptr->data, поэтому должны быть уверены, что сохранение ptr->data в потоке, выполняющем push(), происходит-раньше загрузки. Но такая уверенность уже есть: операция захвата в increase_head_count() гарантирует, что существует отношение синхронизируется-с между сохранением в потоке, выполняющем push(), и операцией сравнения с обменом. Поскольку сохранение данных в потоке, выполняющем push(), расположено перед сохранением head, а вызов increase_head_count() расположен перед загрузкой ptr->data, то отношение происходит-раньше имеет место, и всё будет хорошо, даже если для операции сравнения с обменом в pop() задана семантика std::memory_order_relaxed. Есть еще всего одно место, где изменяется ptr->data — тот самый вызов swap(), на который вы сейчас смотрите, и ни один другой поток не может оперировать тем же узлом — в этом и заключается смысл сравнения с обменом.
Если compare_exchange_strong() завершается неудачно, то к новому значению old_head не будет обращений до следующей итерации цикла, и, поскольку мы уже решили, что семантики std::memory_order_acquire хватало в increase_head_count(), то здесь будет достаточно std::memory_order_relaxed.
Что можно сказать насчёт других потоков? Нужны ли более сильные ограничения, чтобы и другие потоки работали безопасно? Нет, не нужны, потому что head модифицируется только операциями сравнения с обменом. Будучи операциями чтения-модификации-записи, они составляют часть последовательности освобождений, начатой операцией сравнения с обменом в push(). Поэтому compare_exchange_weak() в push() синхронизируется-с операцией compare_exchange_strong() в increase_head_count(), которая прочитает сохраненное значение, даже если в промежутке другие потоки изменят head.
