Memory order relaxed?

hi!
ich habe eine linked list erstellt. immer, wenn ein element am ende engefügt wird, soll im neuen element die nummer des vorigen elementes + 1 gespeichert werden.

wird der folgende code garantiert immer

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

ausgeben?

#include <iostream>
#include <thread>
#include <atomic>
#include <vector>
#include <algorithm>
#include <chrono>

struct node {
	node* prev = nullptr;
	int sequence = 0;
};

std::atomic<bool> start{ };
std::atomic<node*> tail{ };

void add(node* n) {
	node* expected = tail.load(std::memory_order_relaxed);
	do {
		n->prev = expected;
		n->sequence = expected->sequence + 1;
	} while(!tail.compare_exchange_weak(expected, n, std::memory_order_relaxed));
}

int main() {
	tail.store(new node);
	std::vector<node*> nodes(20);
	std::generate(std::begin(nodes), std::end(nodes), []() { return new node; });

	for(auto n : nodes) {
		std::thread([](std::atomic<bool>& start, node* n) {
			while(!start.load()) std::this_thread::yield();
			add(n);
		}, std::ref(start), n).detach();
	};

	start.store(true);

	while(tail.load(std::memory_order_relaxed)->sequence != 20) std::this_thread::yield();
	for(node* n = tail.load(); n != nullptr; n = n->prev)
		std::cout << n->sequence << ' ';
	std::cout << std::endl;
}

ich behaupte nein: wenn ein thread A einen node in die liste einfügt (per CAS), dann sind für ihn die writes in zeile 20,21 sequenced-before dem CAS und für ihn damit auch happened-before, aber der thread hat mit keinem anderen thread eine "synchronized-with"-Beziehung.
wenn jetzt ein zweiter thread B den neuen tail relaxed läd, kann es doch sein, dass der immer noch die alten werte von sequence und prev liest, obwohl der tail aktualisiert wurde, sodass jetzt eine Sequenznummer doppelt auftreten kann bzw. er den gleichen vorgänger wie der aus thread A ermittelt, richtig? und das auch unabhängig davon, ob prev und sequence atomics sind oder nicht.

richtig wäre also:

void add(node* n) {
	node* expected = tail.load(std::memory_order_acquire);
	do {
		n->prev = expected;
		n->sequence = expected->sequence + 1;
	} while(!tail.compare_exchange_weak(expected, n, std::memory_order_release, std::memory_order_relaxed));
}

wenn der CAS im thread A erfolgreich war, sind alle threads, die den tail infolgedessen mit acquire laden synchronized-with dem thread A. wenn der CAS fehlschlug, ist's eh egal, da dann sowieso nochmal geändert werden muss.

stimmt das so?

camper

Relax0r schrieb:

richtig wäre also:

void add(node* n) {
	node* expected = tail.load(std::memory_order_acquire);
	do {
		n->prev = expected;
		n->sequence = expected->sequence + 1;
	} while(!tail.compare_exchange_weak(expected, n, std::memory_order_release, std::memory_order_relaxed));
}

Der Fehlerfall bedarf acquire wegen des späteren Lesens von expected->sequence.
Normalerweise genügt es, ein Orderingargument anzubieten (std::memory_order_acq_rel). Der zweite Parameter wird automatisch passend gewählt.

hustbaer

Würde hier auch memory_order_consume reichen?
Also

void add(node* n) {
    node* expected = tail.load(std::memory_order_consume);
    do {
        n->prev = expected;
        n->sequence = expected->sequence + 1;
    } while(!tail.compare_exchange_weak(expected, n, std::memory_order_release, std::memory_order_consume));
}

camper

hustbaer schrieb:

Würde hier auch memory_order_consume reichen?

Ich denke schon.

Thread A

(1) n->sequence = ...                                                                                           -|A
    .                                                                                                            |
    . (sequenced before)                                                                                         |
    .                                                                                                            |
(2) *n = expected (CAS, release)                                              -|A                                |X- (inter-thread happens before 1.10/13.3.2)
    .                                                                          |                                 |
    . (dependency-ordered 1.10/12.1)                                           |                                 |
--------------------------------                                               |                                 |
Thread B                                                                       |                                 |
    .                                                                          |                                 |
(3) expected = *n (CAS, consume)           -|A                                 |X (dependency-ordered 1.10/12.2) |
    .                                       |                                  |                                 |
    . (carries dependency 1.10/11.2)        |                                  |                                 |
    .                                       |                                  |                                 |
(4) expected (lvalue->rvalue)               |X (carries dependency 1.10/11.3)  |                                 |
    .                                       |                                  |                                 |
    . (carries dependency 1.10/11.1)        |                                  |                                 |
    .                                       |                                  |                                 |
(5) expected->sequence (lvalue->rvalue)    -|B                                -|B                               -|B