Jaderné noviny – 2. 8. 2012: Jak se kompilátorům brání v optimalizacích

20. 8. 2012 | Luboš Doležel

Články - Jaderné noviny – 2. 8. 2012: Jak se kompilátorům brání v optimalizacích  

Aktuální verze jádra: 3.5. Citáty týdne: Dave Jones, Paul McKenney, Linus Torvalds. Sbohem Andremu Hedrickovi. Začleňovací okno verze 3.6, část druhá. ACCESS_ONCE().

Obsah

• Aktuální verze jádra: 3.5
• Citáty týdne: Dave Jones, Paul McKenney, Linus Torvalds
• Sbohem Andremu Hedrickovi
• Začleňovací okno verze 3.6, část druhá
• ACCESS_ONCE()

Aktuální verze jádra: 3.5

Začleňovací okno řady 3.6 je nadále otevřené, proto zatím nevyšla žádná vývojová verze. Do hlavní řady se mezitím valí novinky, více se dozvíte dále.

Stabilní aktualizace: verze 3.2.24 vyšla 26. července, verze 3.4.7 30. července a 3.0.39 1. srpna. Kromě obvyklých oprav obsahuje 3.0.39 také velké množství backportovaných patchů pro zvýšení výkonu správy paměti.

Verze 3.2.25 se aktuálně reviduje.

Citáty týdne: Dave Jones, Paul McKenney, Linus Torvalds

Pokud někdo musí číst kód, aby zjistil, k čemu ten ovladač vlastně je, tak asi stojí tvůj popis za houby.

-- Dave Jones

Počet podtržítek před původní lokální proměnnou v rcu_dereference() byl výsledkem dohadování, jak hodně by název proměnné měl být komplikovaný, aby nehrozily kolize s názvy v nadřazeném scope. Devět počátečních podtržítek může vypadat přehnaně, nebo, jak jsi sám řekl, šíleně, ale na druhou stranu se ke mně nikdy nedostala žádná zmínka o kolizi.

-- Paul McKenney

V těchto případech udělám merge sám, ale po pravdě kontroluji svůj merge oproti mergi správce. A už se párkrát přihodilo, že se můj merge lišil a právě ten můj byl ten správný. Správce možná zná svůj kód lépe, ale já se zase vyznám ve slučování. Dělám jich spousty.

-- Linus Torvalds

Sbohem Andremu Hedrickovi

Na The Register vyšel článek o životě a smrti Andreho Hedricka, bývalého správce IDE v jádře, který zemřel dne 13. července. V dnešní době miliony lidí používají systémy DRM, které uzamykají knížky, písničky a hudbu – jako příklad poslouží Amazon Kindle, BBC iPlayer a Spotify – ale spotřebitelé se do tohoto smluvního vztahu dostávají vědomě. Nejde o výchozí tovární nastavení, jak tomu mohlo být. PC zůstává otevřené a nestalo se z něj jednoúčelové zařízení. Andre si nikdy nechtěl přiznat své zásluhy v této věci. Vzpomínky jsou také shromažďovány na tomto blogu.

Začleňovací okno verze 3.6, část druhá

V době psaní tohoto textu bylo do jádra přetaženo už 8200 neslučovacích změn; to jsou od předchozího týdne téměř 4000. Vypadá to, že přání, aby tento cyklus byl drobnější, se nenaplní. Přesto jdou věci relativně plynule, jen s nepatrným množstvím problémů.

Mezi změny viditelné uživatelům za poslední týden patří:

• Bylo začleněno btrfs send/receive. Send/receive umí spočítat rozdíly mezi dvěma podjednotkami btrfs nebo snapshoty a serializovat výsledek; může to být například použito ke snadnému zrcadlení jednotek nebo vytváření inkrementálních záloh.
• Btrfs také získalo schopnost aplikovat kvóty na podjednotky. Podle správce btrfs Chrise Masona: Toto umožňuje úplné sledování toho, kolik bloků je přiřazeno každé podjednotce (a všem snapshotům) a můžete nastavit omezení na úrovni podjednotek. Můžete také vytvářet skupiny kvót a umístit vícero podjednotek do jedné velké skupiny. Webhostingové společnosti pak postačí dát každého zákazníka do vlastní podjednotky.
• Jádro nabylo lepší podporu bootování na EFI. To by mělo umožnit odstranění spousty inicializačního kódu pro EFI z různých zavaděčů, od kterých se teď už očekává jen načtení jádra a skok na adresu.
• Nový kód pro „svázané cpuidle“ umožňuje lepší správu výkonu CPU na systémech, kde nelze jádra CPU vypínat odděleně. Více o fungování této funkce najdete v příslušném commitu.
• Kód pro LED nyní nabízí „jednorázový“ režim, ve kterém aplikace může požádat o jediné bliknutí LED přes sysfs. Více v dokumentaci.
• Byla začleněna spousta změn v generátorech náhodných čísel, což doufejme povede k bezpečnějším náhodným číslům, zejména na embedded zařízeních.
• Bylo začleněno VFIO, které by mělo představovat bezpečnou možnost vytváření ovladačů zařízení v uživatelském prostoru. Více v dokumentaci.
• Byla začleněna podpora swapování přes NFS, což dělá z této aktivity ne až tak šílenou záležitost.
• Podpora nového hardwaru.

Změny viditelné jaderným vývojářům zahrnují:

• Mechanismus perzistentního úložiště pstore má lepší ošetřování logových zpráv. Byl odstraněn mechanismus Android RAM buffer console, protože pstore už umí poskytovat to samé.
• Nový framework pro PWF usnadňuje psaní ovladačů pro tento hardware.
• Přibyla nová funkce memweight, která vrací počet bitů nastavených v daném paměťovém prostoru.
• Přibyl subsystém pro vkládání chyb do řetězců notifikačních volání.
• Nový příznak v __GFP_MEMALLOC umožňuje, aby alokace paměti sáhly do rezerv.
• Byl odstraněn příznak IRQF_SAMPLE_RANDOM.

ACCESS_ONCE()

Dokonce i příležitostný čtenář jaderného kódu nakonec narazí na použití makra ACCESS_ONCE(), aktuálně se jich v jádře nachází přes 200. Mnoho čtenářů se nebude zabývat tím, co to vlastně znamená, nedávná debata v mailing listu navíc ukázala, že to neví ani spousta hlavních vývojářů.

Funkčnost tohoto makra je popravdě dobře popsaná už jeho názvem; smyslem je zajistit, že hodnota předaná jako parametr je ve vygenerovaném kódu přečtena právě jednou. Člověk by se mohl divit, proč na tom záleží. Ve výsledku jde o to, že kompilátor C bude, pokud nic nebude naznačovat jinak, předpokládat, že se v daném paměťovém prostoru vyskytuje pouze jedno vlákno. Concurrency není věcí vestavěnou přímo do jazyka C, takže nástroje pro souběžný přístup musejí být postaveny nad tímto jazykem; ACCESS_ONCE() takovým mechanismem je.

Zvažme například tento kus kódu z kernel/mutex.c:

    for (;;) {
	struct task_struct *owner;

	owner = ACCESS_ONCE(lock->owner);
	if (owner && !mutex_spin_on_owner(lock, owner))
	    break;
 	/* ... */

Toto je drobný kód, který doufá, že se mu podaří rychle bez uspávání získat mutex, jakmile jej aktuální vlastník uvolní. V tomto for cyklu je toho ještě mnohem víc, ale toto nám pro ukázku stačí.

Představme si, že použitý kompilátor pochází od fanatických vývojářů, kteří se budou snažit vše optimalizovat, jak to jen půjde. To není jen naprostá iluze, jak Paul McKenney nedávno dosvědčil: Viděl jsem tu jiskru v jejich očích, když diskutovali o optimalizacích, o kterých byste nechtěli, aby vůbec věděly vaše děti! Takoví vývojáři mohou stvořit kompilátor, který vyvodí, že protože tento kód neupravuje lock->owner, není nutné hodnotu číst při každém průchodu cyklem. Kompilátor pak může kód takto přeorganizovat:

    owner = ACCESS_ONCE(lock->owner);
    for (;;) {
	if (owner && !mutex_spin_on_owner(lock, owner))
	    break;

Kompilátoru ale uniká to, že lock->owner je mezitím měněno jiným vláknem. Výsledkem je pak něco, co si nepovšimne změn, což má neblahé následky. ACCESS_ONCE() této optimalizaci brání, a tak by měl kód fungovat dle očekávání.

Jak už se to stává, přístupy zrušené optimalizací nejsou jediným nebezpečím. Některé architektury procesorů (např. x86) nejsou obdařeny velkým množstvím registrů; na takových systémech se kompilátor musí opatrně rozhodovat, které hodnoty si uchová v registrech, aby měl kód co nejvyšší výkon. Některé hodnoty mohou být z registru vytlačeny a pak opětovně načteny. Pokud by se to stalo ve výše uvedeném kódu, výsledkem by mohlo být více přístupů k lock->owner. A to by mohl být problém; pokud by se hodnota lock->owner změnila uprostřed cyklu, kód, který by očekával, že se tak nestane, by mohl být závažně zmaten. ACCESS_ONCE() říká kompilátoru, aby to nedělal.

Implementace ACCESS_ONCE() v linux/compiler.h je docela přímočará:

#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))

Funguje to tak, že to dočasně převede danou proměnnou na typ volatile.

Vzhledem k rizikům, jaká optimalizující kompilátory představují, byste se mohli divit, proč se s něčím takovým nesetkáváme častěji. Odpovědí je, že souběžný přístup k datům by měl být chráněn zámky. Spinlocky a mutexy oba fungují jako optimalizační bariéry, což znamená, že brání vlivu optimalizací z jednoho vlákna na druhé. Věci jako ACCESS_ONCE() jsou nutné jen tam, kde se ke sdíleným datům přistupuje bez zámku (nebo explicitních bariér). Požadavky na škálovatelnost mají vliv na vytváření více takového kódu, ale většina jaderných vývojářů toto nepotřebuje řešit.

Diskuse k tomuto článku

[Let_Me_Be]

Achjo, tyhle volatile prasarny fakt stoji za to. To makro ma fungovat presne obracene. Volatile ma byt default a pokud z nejake promenne nepotrebuju cist z vice vlaken tak si ji poznacim jako ne-volatile.

[dumblob]

+1

[Michal2]

Já jsem člověk, který ten kód musí psát, takže by mě SRALO kdybych v 99.99 (spíše ještě více) % pripadu musel předepisovat nonvolatile. Tudíž ti dávám -1

[D.A.Tiger]

+1

[Michal Vyskočil]

A vy běžně v kódu běžně píšete třeba takové auto?

[Sten]

auto označuje automatický typ, ne automatickou dedukci kompilátoru za pomoci binární křišťálové koule, jestli něco má být volatile nebo ne.

[Michal Vyskočil]

S tím souhlasím, ale jak to souvisí s tématem vlákna?

[Sten]

To, že nonvolatile by se muselo předepisovat i u všech prototypů funkcí a definicí struktur.

[Michal Vyskočil]

No ono by hypotetické --std=little.owl bylo asi dost nekompatibilní s jakýmkoli jiným C, takže asi ne :)

[little.owl]

ono by hypotetické --std=little.owl bylo asi dost nekompatibilní s jakýmkoli jiným C

Ja se rad pobavim na svuj ucet, ale tady mi nejak nedochazi. Proc --std=little.owl ?

[Michal Vyskočil]

No už jenom změna typu proměnné na volatile a zavedení nového klíčového nonvolatile slova je přeci na nový standard A jiné jméno, než --std=little.owl mě prostě nenapadlo. Nic ve zlém.

[little.owl]

Spojovat muj nick s takovou, od zacatku, peachovinou me temer urazi!

[Let_Me_Be]

Jasne. 99.99% promennych sdilenych mezi vlakny nepotrebuji byt volatile. To je fakt dobry blabol.

[tom]

* Zjevne jste nepochopil, jak to Michal2 myslel.

* Promenne chranene mutexy/semafory/syscallem opravdu volatile byt nepotrebuji a takovych promennych je v userspace programech vetsina.

[Let_Me_Be]

Ale na ty snad tohle makro (o kterem se tady bavime) pouzivat nebudu, ne?

[R]

Bud by si mal vsade volatile, alebo by bol vykon vies kde...

[Let_Me_Be]

Ano protoze je mnohem lepsi mit v pripade chyby podivne chovani kodu a nahodne hodnoty v promennych nez mit v pripade chyby nizsi vykon :-/

[Sten]

Takže kód by vlastně vůbec neměl používat registry? (To je totiž význam volatile) Měl by taky za každou operací, která modifikuje paměť, provést memory barrier, aby se změna skutečně projevila na všech jádrech, protože jinak na to bude potřeba nějaká „další prasárna“? Tipuji, že jste nikdy nic takhle nízkoúrovňově nedělal, proto nemáte tušení, jak pomalá by taková aplikace byla.

[Let_Me_Be]

Mam pocit ze neumis cist. Protoze to co pises se absolutne nevztahuje k tomu co jsem napsal ja. Cely vyznam toho makra je totiz v tom ze se volatile nepouziva a jenom tam kde je to potreba se pouzije tohle makro. Coz je prasarna.

[Sten]

To ale může způsobovat výkonostní problémy v zamčených místech, kde je vhodné, aby se zámek držel co nejkratší dobu.

[Let_Me_Be]

No a prave proto by to makro melo fungovat obracene. Kdyz mas vykonnostni problem (coz je vec, ktera se hleda mnohem lepe, nez vznik nahodne hodnoty) tak si tu promennou poznacis jako ne-volatile.

[Kvakor]

Normální SMTP procesory memory barrier nepotřebují, mají speciální obvody, co zajíšťují koherenci cache a paměti mezi jádry (tj. tu "prasárnu" dělá hardware ). Memory barrier je třeba až když se přistupuje k MMIO, ale jen pokud procesor neumí vypnou cachování jinak, např. u x86 jsou na to MTRR a u x86_64 atributy stránek.

[pc2005]

Normální SMTP procesory

SMP nebo link! :-O

[Kvakor]

Jasně že tam mělo být SMP, tohle byla jen IT varianta freudovského přeřeknutí

[pc2005]

A já se tak těšil na novou architekturu .

[Sten]

Já se teda na SMTP procesory netěším. Toho spamu je už teď hodně

[little.owl]

Svet je pestrejsi a na jinych platformach to neplati, tohle jsou implementacne a platforme zavisle veci.

[deda.jabko]

To mi prijde jako nesmysl, mnozstvi sdilenych promennych by melo byt co nejmensi, aby v tom byl poradek. S tvou logikou by se dalo tvrdit, ze vsechny promenne by mely byt z podstaty globalni a kdyz ji chci lokalni, tak si ji tak mam deklarovat.

[Let_Me_Be]

Co ma pocet sdilenych promennych spolecneho s tim ze ty ktere jsou sdilene maji byt volatile?

[deda.jabko]

ze ve slusnem kodu mas male mnozstvi sdilenych promennych (nejlepe) na jednom miste a mas je oznacene jako volatile a ostatni promenne to nepotrebuji, ergo implicitni volatile je nesmysl.

[Let_Me_Be]

Ale o nesdilenych promennych se tady vubec nevime. Bavime se tady o tomhle makru, ktere umoznuje mit sdilene promenne implicitne ne-volatile.

[pc2005]

Všechny proměnný ne, ale všechny proměnný definující zámky ano. Zajímalo by mě kolik se na tom ACCESS_ONCE ušetří času.

P.S. Nejvtipnější pak je, když se přetypovává proměnná, která už volatile je . Např. tady.

[little.owl]

Tam nejde o usporu casu, ale o to, ze promenna muze byt asynnchronne zmenena z jineho threadu a tudiz nektere predpoklady na zaklade nichz kompilator muze udelal optimalizaci proste neplati.

[Ivan]

JJ, tohle jsou ty nejnechutnejsi chyby. Takovy system muze bezet mesice a vsechno krasne funguje. A najednou se pri vetsi zatezi vyhrouti s nejakou obskurdni chybou. Lidi co umi tohle fixnout jsou fakt machri, vetsinou se ale takova chyba vyresi az kompletnim prepsanim kusu aplikace.

[pc2005]

Jo a buď by měly být všechny takový proměnný, kde může zapisovat 2 a více vláken, definovaný jako volatile (pak je ACCESS_ONCE zbytečné a je to workaround špatně definovaného kódu) a nebo se ptám jak velký výkon získám variantou: nesdílené proměnné + zamykatelné proměnné + proměnná, kterou mám nadefinovanou jako neměnnou, ale občas ji použiju jako volatile.

(když se nějaká proměnná jmenuje "lock" tak bych čekal, že bude už jako volatilní definovaná a nebudu ji muset přetypovávat)

Taky by mě zajímalo zda je nějaké využití efektu, kde musí být proměnná v jednu chvíli aktuálně načtená a po zbytek programu už může zůstat v registru.

[little.owl]

Jo a buď by měly být všechny takový proměnný, kde může zapisovat 2 a více vláken, definovaný jako volatile

Ani volatile vam moc nepomuze,to je jen hint pro kompilator aby to nezoptimalizoval, volatile nevklada memory barrier.

[pc2005]

Ovšem ACCESS_ONCE je volatile taky, nebo nějak paměťovou bariéru řeší? Jinak je to offtopic.

Samozřejmě v případě potřeby paměťové bariéry by se tam nějaká hodila.

[little.owl]

ACCESS_ONCE je volatile a to resi jen to ze vam kompilator neudela nejake nepredlozenosti pri optimalizaci. To zdali to budete moci bezpecne pouzit z vice vlaken, bude zalezet na implementaci kompilatoru a kontextu v jakem je kod pouzit - jedno jadro, pres stejne cache a podobne, cele je to implementacne zavisle.

[pc2005]

Mě jde o to, proč a zda je výhodnější přetypovat proměnnou někde v kódu a ne rovnou v definici.

[little.owl]

Protoze to nemusi nestacit. Vy muzete napriklad k promenne pristupovat neprimo pres pointer jako k mistu v pameti a tam snadno kompilator dostanete do uzkych. Navic tohle reseni vam umozni toto chovani lokalizovat tam kde je to potreba.

[little.owl]

Ehm: Protoze to nemusi stacit.

[pc2005]

Aha, tedy vzhledem k tomu, že lze udělat volatile pointer i pointer na volatile i volatile pointer na volatile proměnnou a za předpokladu, že tohle kompilátor ustojí. Pokud ne, tak je dost slabej (což ale klidně může být).

Tedy některé programy používaj pointery, které občas ukazují na volatile proměnnou a občas na normální? To mě přijde ale dost hazardní.

[Sinuhet]

Ted byste mel jeste vysvetlit, jak vam pomuze, ze pri pristupovani k promenne z vice vlaken si ji oznacite jako volatile.

[pc2005]

[rejp] Kromě speciálních případů nebude potřeba používat žádné makro [/rejp]

[Anonymous]

Náhodné generátory čísel, nebo generátory náhodných čísel?

P.S.: Děti věděly.

[Luboš Doležel (Doli)]

Díky.

[Sten]

Náhodné generátory náhodných čísel

[Marek]

…Concurrency není věcí vestavěnou přímo do jazyka C…

od dubna 2011 a C verze C11 to už umí. Je otázka jak to umějí kompilátory a jak se s tím popasují při kompilaci kernelu.

[little.owl]

Vzhledem k tomu, ze kernel se nedostal plne ani k C99, je mluveni o C11 v tomto kontextu z rise snu.

[JoHnY2]

Souhlas. Na druhou stranu, nikdo nerika, ze jadro musi pouzivat zrovna uplne vsechno z C99 nebo C11. Pokud se dobre ohlidaj konflikty, tak neni problem pouzivat casti C11 relativne brzo.

[zulu]

Já bych teda od "access once" čekal právě to, že první for se má chovat jako ten druhý.

[pc2005]

Jo mě to taky mate: Access once = načti jednou a pak recykluj hodnotu.