Jaderné noviny – 5. 12. 2013: Zákeřné mutexy (diskuse)

[Juraj]

Na toto predsa mame volania madvise aby OS nemusel hadat z kristovej gule....

[Juraj]

* z kristalovej gule :)

[kralyk z abclinuxu]

[Jardík]

Běžící blákno, které může takto rychle získat zámek ...

[frr]

Přečetl jsem si Linusův popis. Měl jsem maličko problém se v tom zorientovat, protože se bavíme o dvou patrech: A) o "uživatelsky viditelném" mutexu a jím chráněném reference countu, to vše v nějakém uživatelském objektu, a pak B) o patro níž o "struct mutex", kterýžto struct vlastně vypadá dost podobně:

struct mutex {
        atomic_t		count;
        spinlock_t		wait_lock;
        struct list_head	wait_list;
    };

Jádro pudla je v tomto nižším patře = v kernelovém mutexu. Všimněte si položky "struct list_head wait_list" - to je nějaký spojový seznam "čekatelů na zámek".

Uvnitř páru volání mutex_lock()/mutex_unlock() existují dvě cesty: rychlá a pomalá.

Pomalá cesta bere spinlock a hraje si s wait_listem (seznam čekajících procesů) = při mutex_lock() se vlákno do seznamu zapíše, při mutex_unlock() se vyškrtne.

Naproti tomu rychlá cesta uvnitř mutex_lock() za příznivých okolností jenom "proletí", nepřidává se do wait_listu = nebere spinlock, pouze si atomicky (s podporou CPU) dvakrát sáhne na položku count. Podobně uvnitř mutex_unlock().

Za příznivých okolností, konkrétně když o mutex soupeří dvě vlákna, a to ještě na konci delší "dávky" soupeřících vláken:

• první vlákno si zabralo mutex, tehdy ještě v pomalé cestě. Nyní v rámci mutex_unlock() už upravilo atomický "count" mutexu do podoby "nikdo další už nečeká"
• druhé vlákno rychlou cestou proletí mutexem ve chvíli, kdy první vlákno uvnitř mutex_unlock() dosud drží spinlock a ještě fidlá s wait_listem, což může být zdlouhavá paměťová operace (pointery vs. CPU cache apod.)

Což by nebyl problém v případě, že se na daném místě v programu nejedná o okamžité dealokaci předmětného structu mutex. Pokud ale druhé vlákno (rychlá cesta) dealokuje mutex okamžitě po návratu z mutex_unlock, "máme tu problém, přátelé".

To by mě zajímalo, jestli nějakou podobnou "rychlou cestu" obsahuje i user-space pthread_mutex_t, konkrétně v Glibc + NPTL nad jádrem 2.6.x/3.x, protože uživatelský reference counter chráněný mutexem uvnitř svých structů (objektů) občas používám...

Mimochodem ladit moje vlastní bugy v automatické dealokaci podle reference countingu (+strong pointery) ve vícevláknovém zaobjektěném prostředí je pro mě veliká zábava i v případě, že posixová synchronizační primitiva fungují, jak bych čekal. To je tak, když znovu vynalézám kolo, protože si ho chci maličko přitesat pro svoje potřeby...

[Ondrej 'SanTiago' Zajicek]

Jádro pudla je v tomto nižším patře = v kernelovém mutexu.

Strucne receno, mutex_lock() v jednom threadu uspeje drive nez skonci mutex_unlock() v druhem a ten druhy stale pristupuje k interni mutexove strukture.

Pokud se na takove chovani podivam z hlediska konvencni semantiky posixovych mutexu (tedy pokud by se tak chovali userspace mutexy), tak mi to jako zavadne neprijde (primarni cil - vzajemne vylouceni kodu *uvnitr* mutexove sekce - je zajisten), akorat mutex_destroy() by musel vzit spinlock a tim se ujistit, ze paralelni mutex_unlock() uz skoncil. To by mohlo byt i adekvatni reseni pro kernelove mutexy.

[Ray]

No, já nevím, ale přijde mi to jako úplně *běžná* race condition v multithreadingu... Kdo někdy vícero v tomto dělal, musel narazit na identické situace s "free" nebo "delete" (případně v rámci destruktorů). Tyhle chyby se vyloženě hnusně hledaj, to zase jo :) Celkově, obecně, uvolňovací "kaskády" maji vždy se debugovací kouzlo

R.

[Sten]

V C++ ani ne. Používat delete kdekoliv mimo destruktor smart pointerů pokládám za velmi špatný kód* a race conditions dealokací opět dobře řeší smart pointery používající atomický reference counter. Zde je to zesložitěné tím, že se tam snaží aktivně spouštět jiné vlákno, ale s něčím takovým se v user space setkáte jen výjimečně.

* Schválně za jak dlouho přijdete na to, že tohle leakuje?

class Socket
{
public: 
	Socket()
	{
		if (!connect())
			throw std::exception();
	}

	bool connect()
	{
		return false;
	}
};

class Test
{
public: 
	constexpr size_t BUF_SIZE = 4096;

	char *buf;
	Socket sock;

	Test()  
		: buf(new char[BUF_SIZE]())
	{}

	~Test()
	{
		delete[] buf;
	}
}

[frr]

Pro mne jako hobby kutila je to zajímavý dotaz - odhaduji, že konstruktor Socket::Socket() hodí výjimku, takže když je volán v rámci konstruktoru Test::Test() jako druhý v pořadí (implicitně, po alokaci "char* buf = new char[BUF_SIZE]", pořadí volání konstruktorů podle pořadí deklarace memberů ve třídě Test) tak běh programu skončí právě tou výjimkou, která neodchycena propadne až na nejvyšší úroveň a program skončí, aniž by dealokoval ten char[BUF_SIZE]...

Resp. pokud tu výjimku chytí někdo o kus výš, např. už ten kdo volá new Test(), a "ošetří" ji (v tom smyslu, že program běží dál), tak se mu ty alokované buffery mohou hromadit, pokud toto bude zkoušet opakovaně.

A proto jakožto nedouk nemám rád výjimky

Chápu, že to omezení na destruktor strong pointerů je součást nějakého programátorského postupu, jak dosáhnout "vzájemně zaručeného zničení". Nicméně mi to i tak přijde trochu nekompletní, pokud do věci vstupují výjimky...

[Sten]

Pokud program spadne, tak by to nevadilo, protože operační systém po něm uklidí. Problém nastane ve chvíli, kdy někdo ty výjimky bude zachytávat. Že se nepodaří otevřít socket, je nakonec celkem normální situace, která se běžně řeší výjimkou zachycenou na vhodném synchronizačním místě a případně dalším pokusem.

Ten problém zde je, že C++ standard říká, že dokud neskončí tělo konstruktoru (které v tomto případě ani nezačalo, protože výjimka vyletěla v implicitním inicializátoru člena sock), tak se nezavolá tělo destruktoru; nakonec to je logické, objekt se ještě nevytvořil, a tak není co ničit. C++ v takovém případě volá destruktory všech již zkonstruovaných členů a předků (pokud by Test měl předka, tak jeho destruktor se zavolá), zde tedy program zavolá destruktor buf, jenže to je char *, který se sám nedealokuje. Pokud by buf byl smart pointer, tak jeho destruktor tu paměť uklidí.

S výjimkami není problém, pokud dodržujete RAII, tedy že každý zabraný zdroj má vlastní „hlídací“ objekt, který jej v destruktoru uvolní. A tohle pravidlo právě vede k tomu, aby delete používaly akorát smart pointery (a výrazně zjednodušuje hlídání zdrojů oproti C ).

Ještě bych dodal, že existuje druhé pravidlo, a to že destruktor nemá vyhazovat výjimky, pokud je volán při zpracovávání výjimky (na rozdíl od toho, co méně zkušení programátoři často tvrdí, tak jinak může a dokonce by i měl, pokud třeba selže flush bufferu, tak se asi nepodařilo zapsat data, což by se program měl dozvědět, ale pokud je objekt ničen při zpracování výjimky, pak se stalo něco, co rozhodilo vyšší vrstvu a vzniklé problémy jsou velmi pravděpodobně zavlečené). To jde ale naštěstí vyřešit celkem snadno takto:

~Test()
try {
	⋮ // Volání funkcí, které mohou vyhodit výjimku, kromě destruktorů — tam by si to měl řešit ničené objekty
} catch (...) {
	if (std::uncaught_exception())
		// Případně nějaké logování, pokud vás to zajímá
		return;
	// catch blok, kterým končí konstruktor či destruktor, má implicitní rethrow
}

[frr]

Díky za dovysvětlení a doplnění mého vzdělání

[Sten]

Ještě jeden detail. V C++11 jsou destruktory ve výchozím stavu noexcept, je potřeba to zrušit:

~Test noexcept(false)

[pavlix]

To je syntaxe ve stylu: „Půjdu na nákup ne.“ To snad museli vymyslet Francouzi.

[kralyk z abclinuxu]

To je syntaxe ve stylu: „Půjdu na nákup ne.“ To snad museli vymyslet Francouzi.

Spíš lidi z Cisca (no shutdown)

Ale ono zrovna v tomhle případě to je namístě, u drtivé většina destruktoru je noexcept vhodný.

[pavlix]

Nikoliv. Jde o to, že noexcept plní formu věty či vyjádření a za ním je napsáno false, které obrací význam. Jenže ani francouzi takto neobrací význam něčeho, už má samo obrácený význam, nebo ano?

[Ray]

Proto neni jadro v C++ :) Pro tyhle a radu jinych veci, nekdy ne zcela determinstickych, osobne C++ nemam moc lasce. Prijde mi to nekdy az neprehledne, skoro jako jine write only jazyky. Ale nic proti tomu, ze kdyz jsou veci delat jednoduse, proc je nedelat slozite (:

Nemuzu rict, ze bych se tim v userspace nesetkaval. Minimalne u server side rozhodne. Kdysi jsem si musel napsat vlastni implementaci "theadu" a hlavne sync objektu, aby se mi pod WIN a Linuxem chovali opravdu *uplne* stejne (portabilni app). Protoze to co (pred tema par rokama, ted nevim) bylo v pthreads, to bylo spise na bliti, nez na cokoliv jineho.

Dalsi, kde mne podobne veci mockrat vyskolili je cokoliv 'sdileneho' s counterama, nedej bozxe kruhovejma vazbama (nejvic memory management). To je nemlich to same... Kupodivu na to dobre fungvoala HT technologie. Na realnym 2 procesorovy masine, co jsem tenkrat mel na vyvoj to bezelo, na signel taky, ale na HT to padalo a padalo :) Nikdy jsem neprisle na to proc konkretne.

Je fakt, ze nekdy clovek cumi na ocividnou blbost, ale nejak to nevidi, protoze to funguje. A bohuzel z 99.99999% :) Blahoreceny budiz chyby, ktere proste spolehlive vzdy spadnou na hubu...

R.

[Sten]

C++ je téměř zcela deterministické (všechny nedeterministcké věci má převzané z C, např. chybějící inicializaci základních typů), akorát je to deterministické chování někdy trochu jiné, než by programátor čekal. Na druhou stranu, když se člověk nad tím případem zamyslí, tak je logické, že se to tak chová: objekt ještě nebyl vytvořen, tak přeci není co ničit (ostatně jakýkoliv jiný objektový jazyk to udělá stejně, akorát ty ostatní jazyky většinou vynucují RAII). Ale jak jsem vysvětloval výše, pokud dodržíte RAII, tak nebudete mít problém.

S takovými problémy, jako je zde, se setkávám výjimečně. Ano, race condition, kdy někdo zapomene něco zamknout nebo místo deep copy provede shallow copy, s tím se setkávám běžně, ale race condition u delete jsem od té doby, co delete u kódu, který spravuji, smí používat jen smart pointery, neviděl.

Jádro není v C++ hlavně proto, že v roce 1991 byla podpora C++ dost mizerná. A taky proto, že v jádře bývá problém s implementací výjimek a RTTI, tak se to tam nepoužívá, čímž se C++ snižuje na C with classes. A to už pak rovnou jde psát v C.

[frr]

Nojo, ale mě se tohle běžně stávalo tím stylem, že jsem si naběhl na své vlastní zapomenuté hrábě - že jsem něco nedomyslel a dealokoval dřív, než jsem s tím doopravdy přestal pracovat (protože více vláken a sdílená kritická sekce obalená zámkem uvnitř objektu předávaného referencí atd.) Jako že se vlákna probudí z blokujícího volání v jiném pořadí, než usnula, to je jasné. Ale ještě se mi nestalo, že bych objevil nějakou pastičku uvedeného kalibru v posixových zámcích. Možná jsem toho jenom málo napsal... Nebo jsou moje vlastní zamykací finty při "ukončování práce" natolik defenzivní, že pokryjí i tenhle netušený zádrhel.

Třeba i pro poměrně prosté problémy typu producent-konzument, kde se učebnicově má používat semafor a fronta, já používám frontu opentlenou mutexem a podmínkovou proměnnou plus nějaké pomocné proměnné. Umožňuje mi to definovaně probudit konzumenta ve chvíli, kdy ho už nemám čím nakrmit, jenom se s ním chci slušně rozloučit... A protože tato dvě vlákna plus třeba několik dalších cyklí v blokujících smyčkách nad sdílenou instancí nějakého objektu, je tam ještě pro košer dealokaci reference counter vláken (nebo "bitmapa" nebo tak něco, prostě "píchačky") se zamykáním a přesně definovaný postup, jak se ten cirkus má ukázněně evakuovat.

V zásadě pro danou instanci objektu "poslední zhasne", ale ten poslední je vždycky jedno konkrétní vlákno, které má koncovku v popisu práce - ostatní mají pouze povinnost se s ním při odchodu "slušně rozloučit". Přitom konec může nastat z několika důvodů v různých vláknech - ale všechna pracovní vlákna nad sdíleným objektem mají definovaný postup, jak zasignalizovat "balíme" zmíněnému předem určenému "poslednímu" a kolegům (a pak se ještě musí jednotlivě definitivně rozloučit u píchaček, aby mohla proběhnout dealokace). Jako když dělník na vrátnici píchne kartičku a vrátí ji do "kartotéky", a teprve potom mávne na vrátného "já už jdu". Vrátného to probere z klimbání, zkontroluje jestli už jsou všichni pryč, a pokud ano, zavře svou kukaň a při odchodu zhasne. Pokud byl vrátný zrovna na WC nebo se nestačil vrátit ze svačiny, tak po návratu mrkne, jestli už jsou všichni pryč, a pokud ne, tak si ještě klimbne... Všimněte si, že tohle chce opět posixovou podmínkovou proměnnou, nebo musí mít vrátný kuchyňského budíka nastaveného "na chvilku" - aby se s posledním "neminul" a nechrápal v kukani navždy (resp. až do rána).

Hmm... tak mě napadá, že zrovna tady je potřeba, aby ten "poslední dělník" už byl zaručeně pryč ve chvíli, kdy vrátný dojde k závěru, že je na čase zhasnout. Aby nemohlo dojít k tomu, že vrátný zhasne, ještě než poslední stačil vytáhnout kartu z píchaček. Což pokud by posixový mutex nebyl "sám o sobě bezpečný vůči dealokaci", měli bychom oheň na střeše... a nepomohla by proti tomu ani podmínková proměnná. Třeba pokud by se vrátný vrátil z WC těsně po příchodu "posledního", nebo by přišli poslední dva, jeden by vrátného probudil z klimbání a ten by se při probuzení z podmínkové proměnné zavěsil těsně za "posledního" (a opustil by pthread_mutex_unlock() rychleji než on). Napadlo mě, že by "vrátný" mohl na závěr pro sichr ještě jednou "vzít a pustit mutex", ale teoreticky ani to by situaci bezezbytku neřešilo. Jedině udělat tam pro "posledního dělníka" ještě pro sichr další flag, který už by nebyl chráněný mutexem, ale "poslední dělník" by ho nastavil až ve chvíli, kdy by opustil pthread_mutex_unlock(). Takže by vrátný před zhasnutím musel tenhle flag ještě zkontrolovat, a pokud by nebyl shozený, udělal by ve smyčce schedule()/sleep(0) nebo pár těsných cyklů, dokud by ten flag nespadl.

Nebo by se ten objekt (resp. pointer na něj) dal hodit do fronty "objektů čekajících na uvolnění", kterou by čistilo extra globální vlákno. Vlastně by ten flag "delete je bezpečný" mohl hlídat vlastní destruktor objektu, jehož je mutex memberem. Ale to by zas destruktor musel spát... což možná není úplně čistá konstrukce. Spíš by ten flag "delete je bezpečný" měl být k dispozici jako veřejná proměnná nebo metoda, a volající ať se zařídí po svém.

Hmm... ještě přemejšlím... pokud by posixový mutex byl nad NPTL tímto způsobem děravý, tak by to např. mohlo znamenat, že pthread_cond_wait() není bezpečná vůči "minutí se" s pthread_mutex_lock() + pthread_cond_signal(). Protože pthread_cond_wait() má dělat implicitně atomicky pthread_mutex_unlock().

Já se snad do té glibc podívám...

[frr]

Tak jsem se podíval na NPTL v rámci glibc a nakonec bych skoro řekl, že user-space posixové mutexy jsou bezpečné vůči dealokaci.

Tady jsou zdrojáky user-space NPTL:

https://sourceware.org/git/?p=glibc.git;a=tree;f=nptl;h=af234acffb2fbacb622cfb4649dea20059719b4c;hb=HEAD

Konkrétně jsem napřed koukal do zdrojáků pthread_mutex_lock.c, pthread_mutex_unlock.c, pthread_mutex_init.c, pthread_cond_wait.c. Přiznám se, že to pro mne není úplně přehledné čtení, protože každá z těch funkcí se interně dál rozpadá na množství větví podle atributů mutexu (z větší části interních a nedokumentovaných), podle jednoho či dvou #ifdefů a taky podle toho, zda o mutex soupeří víc vláken či nikoli (to už je v souladu s drby ohledně NTPL).

Pár zajímavých střípků:

Low-level zamykání se děje buď přímo v user space pomocí cmpxchg (resp. je tam nějaké makro, které na x86 zřejmě vede na tuto instrukci), nebo vede na syscall futex(). Toto je zmiňováno i v různých "abstraktech" ohledně NTPL a její posixové synchronizace - údajně "řešení čistě v user space" znamená rychlou cestu (jak jinak), která se použije, pokud o mutex zrovna nesoupeří více vláken (je to možná reálně nepatrně složitější). Kernelový futex dále používá wait_queue a spinlocky - tzn. není založen na kernelovém mutexu, o kterém teď už víme, že má svoje háčky.

http://en.wikipedia.org/wiki/Native_POSIX_Thread_Library

http://en.wikipedia.org/wiki/Futex

http://man7.org/linux/man-pages/man2/futex.2.html

Je tedy zřejmé, že NPTL si posixové mutexy implementuje "po svém", nezávisle na linuxovém kernelovém mutexu. Z toho plyne otázka, zda je tato implementace bezpečná vůči dealokaci. Bohužel jsem to ze zdrojáků nedokázal pochopit (viz výše). V jedné konkrétní větvi, pokud má mutex interní atribut "robust", lze pozorovat posloupnost "nejdřív vyhákni vlákno ze seznamu uživatelů (linked list)" a "teprve poté odemkni mutex". Což zní slibně, ale týká se to pouze jedné z asi šesti variant, kterými se funkce pthread_mutex_unlock() může ubírat.

Ani v rámci pthread_cond_wait() jsem nedosáhl jednoznačného pochopení, jak je zajištěna atomicita odemčení mutexu a zavěšení na podmínku. Nicméně se zdá, že tato funkce napřed zamkne jakýsi low-level zámek na podmínkové proměnné, pak odemkne "uživatelem spřažený" posixový mutex, pak nainstaluje "wakeup handler" pro podmínku, pak odemkne zámek na podmínce - a na závěr se uloží ke spánku do futexu, kterým je podložena podmínková proměnná. Patrně je tím zajištěno, že se "neztratí" pthread_cond_signal(), který by se případně někdo pokusil doručit vzápětí po odemčení mutexu.

V rámci pthread_cond_wait() je zajímavý způsob, jak tato funkce odemkne "uživatelem spřažený mutex": zavolá si interní funkci __pthread_mutex_unlock_usercnt(mutex,decr), která je jinak i na pozadí veřejné pthread_mutex_unlock(), a zajistí si odemčení mutexu, aniž by se snížil jeho "user count" takže je mutex odemčený, a přitom o sobě ví, že je používán Odhaduji, že je to dobré spíš pro kontrolu chyb (pthread_mutex_destroy() vrátí v tomto stavu chybu) než k nějaké optimalizaci rychlosti.

Nakonec asi nejvíc optimismu mi vlévá do žil jedna poznámka v linuxové manuálové stránce pthread_mutex_init():

http://linux.die.net/man/3/pthread_mutex_init

Hledejte kapitolu Destroying Mutexes. Je tam kus zdrojáku, který přesně odpovídá našemu problému "poslední zhasne". A tvrdí se tam, že posixové mutexy jsou vůči tomuto stylu zrušení a dealokace odolné. Ještě mě napadlo, mkrnout se do zdrojáku pthread_mutex_destroy(), jestli je tam nějaký extra low-level zámek nebo kontrola - není, prostě se jenom zkontroluje user_count mutexu, bez zamykání. Takže je asi jinde zajištěno, že hodnotě user_count se dá věřit ve vztahu k bezpečné dealokaci. Popravdě řečeno pthread_mutex_destroy() tuto kontrolu provede pouze jednou, a pokud není splněna, vrátí chybu - ale vzorový zdroják v manuálové stránce ani nehlídá návratovou hodnotu pthread_mutex_destroy(), takže teoreticky předpokládá jistotu, že po návratu pthread_mutex_unlock() už žádný opozdilec s mutexem nefidlá (pokud jsme k tomuto závěru došli na základě našeho externího uživatelského reference countu).

[Ray]

Nekoukal jsem na zdrojak, ale principielne, to neni problem 'ptheadu' ale volajiciho, takze jak muze pthread ovlivnit identickou chybu ?

Pokud je sync objekt reprezentovan jako kus pameti - pak muze nastat situace jako u linuse. Pokud je to nejake cislo do nejakeho pole, potom pro zmenu muze ovlinovat jinej (coz je mozna jeste asi horsi).

Principielne to neni problem pthreadu ne ? Pokus by sync objekt byl staticky, podobny problem by neexistoval.

R.