Dnia pamiętnego Wed, 03 Jul 2013 02:29:38 +0200, Michoo wyjmując peta
oznajmił:

> On 02.07.2013 23:06, Edek wrote:
>> Dnia pamiętnego Tue, 02 Jul 2013 21:18:51 +0200, Michoo wyjmując peta
>> oznajmił:
>>
>>> On 02.07.2013 19:56, Edek wrote:
>>>> Dnia pamiętnego Tue, 02 Jul 2013 18:16:18 +0200, Michoo wyjmując peta
>>>> oznajmił:
>>>
>>>>> - w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
>>>>> została już wykonana
>>>>
>>>> Tak, ale nie miała miejsce synchronizacja.
>>>
>>> Jaka synchronizacja?
>>
>> No żeby udowodnić widzialność danych musisz udowodnić odpowiedni
>> 'ordering' pomiędzy wątkami.
>
> No i memory barrier jest definiowane jako:
> - wszystkie zapisy wykonane do tej pory zostają commitowane do pamięci
> - wszystkie odczyty od tej pory czytają ostatnio zapisany stan

Ale wątku B w tej sekwencji NIE MA BARRIERY. Jest:

if (false) {
}
continue happily.

Każdy kompilator może zamienić kod taki:
----------------
if (sth){
jakaś_funkcja()
}
zrobB
-----------------

na taki:

------------
wczytaj_dane_doB
if (sth){
jakas_funkcja();
wczytaj_dane_doB
}
uzyj_danych_dokonczB
-------------

Efekt jednego i drugiego kodu według as-if jest identyczny.

Niezależnie od architektury sprzętu jest to legalna i nawet dość
sensowna optymalizacja, przy spekulatywnym wykonaniu chowa się
latency danych B a nawet lepiej. W oryginalnym algorytmie n2660
będzie ok, w zmodyfikowanym dane_doB są czytane za wcześnie.

Ja w ogóle nie bardzo rozumiem w Twoim wywodzie jednej rzeczy:
skoro wątek B nie ma żadnej barriery i procesor ma pipeline,
to w którym stadium pipeline procesora z wątkiem B musi
nastąpić barriera wątku A i dlaczego?

>>>>> Pisane na szybko więc co przeoczyłem?
>>>>
>>>> Model pamięci C++11?
>>>
>>> pthreads z nie_pojebaną_architekturą (tm)
>>
>> ARM i Itanium się kwalifikują jako poyebane? IMHO tak.
>
> Imo nie. Nadal jak robisz barrierę to wszystkie zapisy są widoczne.

Może powiedz co rozumiesz przez słowo barriera. To że jeden
wątek coś robi nie ma żadnego magicznego związku z innymi wątkami. Musi
być happens-before, coś w wątku A przed czymś w wątku B wraz z memory
barrier. A tu w wątku B jest tylko odczyt *once, który nie ma semantyki
memory barrier.

>>>> Model Pamięci ma taką cechę że zapis w wątku A jest widoczny w wątku B
>>>> gdy nastąpi uszeregowanie poprzez release w A i acquire w B. Lock() to
>>>> aquire, unlock() to release, albo można w ogóle każdą operację na
>>>> mutexie traktować 'stricter' jako sequence point - czyli jeżeli oba
>>>> wątki przejdą op na mutex to zapis w A może być odczytany w B.
>>>
>>> Gwarancja jest oidp silniejsza - jeżeli wątek kończy release to zmiany
>>> są "commited" w pamięci.
>>
>> Nie bardzo. Gwarancje dotyczą widoczności pomiędzy wątkami, nie
>> ma Jednego Prawdziwego Stanu Pamięci. Nie znam finalnego standartu, ale
>> takie były proposale.
>
> Nawet w sytuacji gdy zapis jest "rozgłaszany" do odpowiedniego procesu
> dopiero w momencie wywołania którejś z funkcji synchronizacyjnych masz
> sytuację w której:
> - nie możesz czytać obiektów przed func() bo nie zostały zainicjalizowane
> - pierwszy odczyt powinien dostarczyć to co zostało commitnięte w
> ostatniej synchronizacji
> więc albo nie masz zsynchronizowanej wartości *once i wchodzisz do
> muteksu, albo masz zsynchronizowaną wartość *once ale wtedy masz
> zsynchronizowane też efekty func(). Wiem o write-reordering, ale barrier
> to barrier.

A gdzie jest ta bariera?

> Potraktuj to po prostu jako założenie(co napisałem) - tak jak autor
> oryginalnego algorytmu założył, że zapisy są "ordered" tak ja zakładam,
> że barrier znaczy barrier a nie niewiadomo-co.

Gdzie autor robił takie założenie?

Główny powód dla którego nie miesza się sprzętu do logiki poprawności
w abstrakcyjnym modelu jest to, że wiele elementów zachowuje się zgodnie
z tym modelem i w ramach tego modelu może robić co jest akurat potrzebne
- na przykład kompilator optymalizuje. Wolno mu, taki jest model,
a ty zakładasz, że kompilator nic nie robi i wszystko jest zgodne na
poziomie języka z właściwościami sprzętu. Nie jest.

>>>> Jeżeli
>>>> nie ma przejścia przez mutex obu wątków mamy race, czyli wątek B
>>>> czyta potencjalnie śmieci.
>>>
>>> Czyta albo stary stan, albo nowy stan[*] a nie śmieci - dlatego m.i. się
>>> używa sig_atomic_t - pierwotne rozwiązanie też to zakłada.
>>
>> A dlaczego wszystkie pola ustawiane przez func miałyby używać
>> sig_atomic_t? Nie doczytałeś, nie chodzi o zmienne
>> użyte w tym algorytmie, ale dowolne inicjalizowane przez func
>> a używane po przejściu tego algorytmu. Czyli w tym algorytmie ich
>> nie ma, są powodem istnienia once().
>
> Jest barriera przed zapisem *once, które jest atomowe. barriera jest
> ordered z operacją atomową, więc kolejność jest jasno zdefiniowana.

Żeby kolejność była zdefiniowa, musi zaistnieć happens-before, czyli
mamy 'barierę' w jednym wątku przed 'barierą' w drugim wątku. A tu
jest tylko w jednym, więc właśnie nie jest zdefiniowana wcale.

Zresztą na procesorze ogólnie jest podobnie, tylko x86 ma dość ścisły
model pamięci. Tak naprawdę pod tym względem x86 jest bardzo
tolerancyjnym sprzętem, dlatego działały wszystkie akcje typu
while(a==0) {}; jako cond.wait().

> Zaprezentowany algorytm jeżeli ma serializację odczytu to zgłosi wyjątek
> w momencie zapisu - coś jak javowe ConcurrentModificationException -
> pamięć została odczytana w sposób konfliktujący z zapisem.

Jaką serializację odczytu?

Tak btw, ConcurrentModificationException oznacza zmiany strukturalne
w kontenerze i użycie 'starego' iteratora, niekoniecznie ma związek z wątkami.

> Z tego wynika, że mutex_lock robi synchronizację pamięci:
> http://pubs.opengroup.org/onlinepubs/9699919799/base
defs/V1_chap04.html#tag_04_11

Jak rozumiesz "with respect to other threads"? Najwyraźniej inaczej niż ja.

> Drugi wątek ma prawo zrobić odczyt inicjalizowanych obiektów dopiero PO
> zakończeniu once().

Tak być powinno.

>> Czy ty mnie nie prowokujesz?
>
> Ależ oczywiście - wiem czego "unika" ta implementacja i uważam, że żadna
> istniejąca teraz architektura ani żadna która zaistnieje w przyszłości
> jeżeli daje gwarancję "serializowalności" to tym bardziej daje gwarancję
> uszeregowania barrier. Po prostu uważam, że w sprytny sposób unikany
> jest problem, który nie istnieje.

Ok...

Chcesz uważać że llvm i gcc dla c++11 mają UB i to jest zapisane
w standardzie że mają mieć zgodnie z n2660 - wolna wola, uchylę się od
dalszych odpowiedzi.

>>>> B 17: wątek używa wartości z A 6, które nie muszą być poprawne,
>>>> bo wątek B nie przeszedł przez żaden mutex. Może odczytać
>>>> śmieci, czyli mamy race
>>>
>>> No właśnie nie może, bo to oznacza, że masz architekturę na której
>>> zmiany wykonane po barrierze są widoczne przed zmianami wykonanymi przed
>>> barrierą.
>>
>> Inny punkt widzenia jest taki, że drugi wątek może czytać w innej
>> kolejności, skoro nie ma pomiędzy tymi punktami synchronizacji.
>
> Nie wolno mu czytać danych, które są dopiero inicjalizowane w once() do
> jego zakończenia - to by było UB. Skoro czyta nową wartość *once, które
> było modyfikowane PO barrierze to w dowolnej sensownej implementacji (to
> było założenie poprawności mojego algorytmu) dane zostaną commitnięte.

Oryginalna implementacja jest zgodna ze standardem. Spróbuj może znaleźć
odpowiednie zapisy w standarcie c++11 na poparcie Twojej tezy.

>> I nie, Intel tego nie zabrania, bo kompilator może inaczej
>> szeregować operacje, jeżeli tak mu wygodnie podczas optymalizacji.
>
> Kompilator też zna coś takiego jak barriera - przenośna biblioteka
> zgodna z pthreads powinna to używać w funkcjach synchronizujących.

No ale jak w wątku B nie ma barriery, to kompilator ma ją wymyśleć?

Poza tym pthreads miało rację bytu przed c++11 i kompilator jednak
nie zwracał większej uwagi na pthreads. Po prostu zakładał, że
każda nieznana funkcja może zrobić cokolwiek - to już załatwia
potencjalne problemy z pthreads. Istniał instrinsic chyba __mb(),
ale on nic nie robił poza wstawianiem odpowiednich instrukcji.
Kompilator przed C++11 sprawę wątków centralnie olewał, bo mógł.

> Nie. Użyty jest dostęp przez wskaźnik a nie jeden z konstruktów c++11.
> Standard wyraźnie mówi, że:
> - równoczesny dostęp i zapis są "confilicting"
> - "confliccting" bez synchronizacji z obu stron to UB

Któryś z nas jest mocno niewyspany. Jaki konstruktor?

Atomics z definicji są dostępne bez innej synchronizacji. Nawet na
Intelach niektóre orderings zaimplementowane są przez
mov value, [addr]
... bo skutek jest zgodny z modelem pamięci.

>> Sam fakt że może widzieć starą wartość algorytm uwzględnia i to nie
>> jest UB.
>
> Ale UB jest sam odczyt.

Bzdura. Dlaczego odczyt atomika miałby być UB?

>> Z wątkami tak jest, albo jeden może coś zrobić wcześniej a
>> drugi później albo odwrotnie i czy atomik już jest ustawiony
>> czy jeszcze nie nie jest żadnym UB.
>
> No i w moim też tak jest - najpierw jest niejawna barriera a dopiero
> potem atomic - jeżeli atomic jest widoczny to stan z przed barriery też.

Ano nie, standard przewiduje różne 'ordering' tych samych operacji. Dla
niektórych jest tak jak mówisz, dla innych nie. Jest, własnymi słowami,
1. sequence point (czyli Twoja bariera), 2. Acquire semantics
3. Release semantics (połowiczne barriery) i 4. Zapisz po prostu
atomicznie wartość bez żadnego szeregowania. *once ma tę ostatnią.

>> Swoją szosą UB stosuje się do reguły "as-if program działa w jednym
>> wątku".
>
> ???

Nigdy nie słyszałem, żeby określenie UB było stosowane do błędów
związanych z wielowątkowością. Przeciwnie, przed C++11 podstawowym
założeniem kompilatora było to, że kompilowany kod jest jednowątkowy
i tylko miejscami zawiera wywołanie nieznanej funkcji, która może
zrobić cokolwiek. I w ramach jednego wątku działa reguła as-if,
na której opierają się wszystkie optymalizacje, czyli wynik
[jednowątkowego] kodu musi być taki sam jak bez optymalizacji.
Kolejna reguła mówi, że kompilator może założyć że nie ma UB
(a jeżeli jest to programista ma problem tak czy inaczej).

Zwróć uwagę, że optymalizacja może zmienić kolejność dowolnych
odczytów i zapisów do pamięci jeżeli wynik jest taki sam,
o ile nie ma pomiędzy nimi wywołania nieznanej funkcji. I cała
Twoja bariera wyparowuje, gdy jej nie ma w wątku B, podobnie
uszeregowanie odczytów - kompilator nic o tym nie wie i zmieni
kolejność jak mu wygodnie.

> Jak czytałeś algorytmy stosowane w bazach danych to jest.
> Poza tym algorytm opiera się na założeniu, że odczyt konfliktujący z
> zapisem jest ok. A ty twierdzisz, że odczyt po barrierze nie gwarantuje
> spójności danych przed barrierą jeżeli barriera nie była wołana w obu
> wątkach. Czemu jedno założenie ma być lepsze od innego?

Prawdziwe założenie bywa lepsze od fałszywego. Możemy się
oprzeć co najwyżej na standarcie C++11.

--
Edek