c++でLock-free stackの仕組みを実装したがうまくいかない

Question

c++11以降の標準ライブラリを用いてLock-free stackを実装したく、コードを書きましたが
どうもどこかでスタック構造が破綻しメモリアクセスエラーが発生してしまいます。
どこに問題があるのかご教授いただければと思います。

出力例

4
Segmentation fault

発生個所はコード中にコメントで示しています。
高確率で発生しますがたまに成功することにご注意ください。

該当のソースコード

#include <thread>
#include <random>
#include <atomic>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	auto size = thread::hardware_concurrency();
	cout << size << endl;
	vector<thread> worker(size);
	union Item {
		Item* next{};
		intptr_t value;
	};
	
	atomic<Item*> pool;
	for (auto& w : worker) {
		w = thread{ [&] {
			mt19937 engien(random_device{}());
			uniform_int_distribution<uint32_t> random;
			for (int i = 0; i < 10000; ++i) {
				// プールから未使用アイテムを取得もしくは新規作成
				auto top = pool.load(memory_order_acquire);
				Item* next;
				do {
					if (!top) {
						top = new Item;
						break;
					}
					next = top->next;    // !ここでセグメンテーション違反!
				} while (!pool.compare_exchange_weak(top, next));
				// 取得したアイテムを使用
				top->value = random(engien);
				// 使用済みアイテムをプールへ返却
				auto old = pool.load(memory_order_relaxed);
				do {
					top->next = old;
				} while (!pool.compare_exchange_weak(old, top));
			}
		} };
	}
	for (auto& w : worker) {
		if (w.joinable())w.join();
	}
	for (auto h = pool.load(); h;) {
		auto tmp = h->next;
		delete h;
		h = tmp;
	}
	return 0;
}

試したこと

1. プールからアイテムを取得せずに毎回newした場合問題ありません。
2. シングルスレッドで動かした場合問題ありません。
3. Itemをstructにした場合エラーの発生位置がメモリ解放処理になります。

　　ただし、その前にスタック構造が破綻しています。（自身を指すItemが現れる）
4. Item*ではなくただの整数値で同様に処理してちゃんと破綻しないか確認したが問題なかった。

int main()
{
	auto size = thread::hardware_concurrency();
	cout << size << endl;
	vector<thread> worker(size);
	for (int i = 0; i < 12; ++i) {
		atomic<intptr_t> pool;
		for (auto& w : worker) {
			w = thread{ [&] {
				for (int i = 0; i < 10000; ++i) {
					auto h = pool.load(memory_order_consume);
					intptr_t next;
					do {
						next = h + 1;
					} while (!pool.compare_exchange_weak(h, next));
					auto o = pool.load(memory_order_relaxed);
					do {
						h = o - 1;
					} while (!pool.compare_exchange_weak(o, h));
				}
			} };
		}
		for (auto& w : worker) {
			if (w.joinable())w.join();
		}
		cout << pool << endl;     // 0であること
	}
	return 0;
}

Comments

[yohhoy]

FYI: 本題から外れますが、memory_order_consumeは非推奨となっており利用は避けたほうがよいです。MemoryOrder指定をしたければココはacquireで代替可能です。https://ja.cppreference.com/w/cpp/atomic/memory_order#Release-Consume_ordering （CPUアーキテクチャによっては、どれを指定しても結局は同じ命令になることもありますケド）

[tanakanata]

ありがとうございます。

Answer 1

ポインタ単体だけでなく追加データとセットでCAS操作することで解決しました。