Jaderné noviny - 9. 9. 2016: Reimplementace mutexů spárovanými zámky

18. 9. 2016 | Redakce | Jaderné noviny | 1793×

Stav vydání jádra. Citáty týdne: Rik van Riel a Linus Walleij. Reimplementace mutexů spárovanými zámky.

Stav vydání jádra

Současný vývojový kernel je 4.8-rc5, vydaný 4. září. Linus řekl: „Takže rc5 je výrazně větší než rc4 a minulý týden jsem si dělal naděje, že se vydání zklidní a zmenší, předčasně. (…) Ne, že by něco z toho bylo zvláště znepokojující, ale pokud se odteď věci nezačnou uklidňovat, může jít o jeden z cyklů, které potřebují rc8. Uvidíme.“

Stabilní aktualizace: 4.7.3, 4.4.20 a 3.14.78 byly vydány 7. září. Pozor, prodloužená podpora vydání 3.14 pomalu končí – podle plánu by se mělo dočkat už jen jedné aktualizace.

Citáty týdne

Existence poptávky po spolupráci na projektu založeném na společném jaderném stromu, který by zároveň obsahoval funkce žádané vývojáři embedded systémů, ukazuje, že ty problémy už sami pociťují.

Zbývá si uvědomit, že už máme takový jaderný strom, kde se všichni (nejen vývojáři embedded systémů) podílejí na vývoji funkcí.

Je to právě upstreamové jádro.

-Rik van Riel

To, co se ti ve skutečnosti povedlo s dodavateli SoC pro Chrome OS, kteří dostali jasnou zprávu, že přítomnost v upstreamu hrála roli při výběru zakázky, bylo to *jediné*, co jsem viděl opravdu zapůsobit na chování celé firmy, nejen několika odhodlaných zaměstnanců. (…)

V okamžiku, kdy lidé od Androidu řeknou, že všechna zařízení Nexus (apod.) poběží na jádře z upstreamu, a vyberou dodavatele SoC, který tomu vyhovuje, pak se začnou dít věci.

-Linus Walleij

Reimplementace mutexů spárovanými zámky

Slavný výrok Oscara Wilda praví, že „móda je tak nesnesitelný druh ohavnosti, že ji musíme obměňovat každých šest měsíců.“ Možná, že totéž platí i pro zamykací primitiva v jádře. Základní mechanismy jako mutexy si v průběhu let prošly mnoha různými podobami. Vypadá to, že tuto sezónu jsou mezi trendy vývojáři hitem spárované atomické zámky, takže by nemělo být překvapením, že na scénu přichází nová implementace využívající právě tyto zámky. Možná, že kód se leskne a třpytí, ale také má potenciál výrazně zjednodušit implementaci mutexů.

Mutex je spící zámek, což znamená, že jaderný kód, který se pokusí získat zabraný mutex, může jít spát a čekat, dokud nebude příslušný mutex dostupný. Prvotní implementace mutexů vždy čekatele uspaly, ale vzhledem k aktuálním trendům ve škálovatelnosti mutexy brzy získaly okouzlující příslušenství: optimistický spinning. Probuzení spícího vlákna může trvat dlouhou dobu a jakmile se vlákno rozběhne, může se stát, že cache procesoru již nebude obsahovat žádná jeho data, což povede k výskytu nemoderních cache miss. Namísto toho vlákno se spinem, které čeká na mutex, bude schopné ho rychle dostat a pravděpodobně bude mít data v cache stále k dispozici (cache-hot). Povolení optimistického spinningu může výrazně zlepšit výkon. Cenou je fakt, že mutexy již nejsou férové (mohou být „ukradeny“ z déle čekajícího vlákna), ale být skutečně in není nikdy zadarmo.

Optimistický spinning s sebou přináší zajímavou komplikaci v tom, že vyžaduje sledování současného majitele mutexu. Pokud majitel spí nebo pokud se změní, zatímco vlákno čeká se spinem, nemá další spinning smysl, protože by pravděpodobně trval dlouho. Jako pole v rámci mutexu je však informace o majiteli nejlépe chráněná samotným mutexem. Z principu ale musí být tyto informace přístupné i vláknům, která tento mutex nevlastní. Výsledkem je složitý kód, který se snaží nakládat se zámkem a informací o majiteli současně.

Peter Zijlstra poslal na přehlídku alternativní mechanismus. Vzniklý problém řeší tím, že kombinuje informace o majiteli a statutu zámku do jediného pole uvnitř mutexu. V současných jádrech udržuje pole count (hodnota atomic_t) status zámku samotného, zatímco owner (ukazatel na struct task_struct) naznačuje, které vlákno vlastní mutex. Peterův patch odstraňuje obě tyto pole a nahrazuje je jedinou hodnotou atomic_long_t, nazvanou „owner.“

Tato hodnota má velikost 64 bitů, takže je dost velká na to, aby obsáhla hodnotu ukazatele. Je-li mutex dostupný, neexistuje vlastník, hodnota nového pole owner je nula. Je-li mutex zabrán, dojde k vložení ukazatele na strukturu task_struct daného vlákna, čímž dává najevo jednak nedostupnost mutexu a jednak vlákno, které ho drží. Struktura task_struct musí být vždy řádně zarovnaná, což znamená, že spodní bity ukazatele na ni budou vždy nulové. Tyto bity jsou dostupné pro další využití při zamykání, jak velí současný trend párového zamykání, jejich dvojici si ve stručnosti popíšeme níže.

S novou organizací vypadá kód pro získání mutexu takto:

static inline bool __mutex_trylock(struct mutex *lock)
{
    unsigned long owner, curr = (unsigned long)current;
    
    owner = atomic_long_read(&lock->owner);
    for (;;) { /* must loop, can race against a flag */
        unsigned long old;
    
        if (__owner_task(owner))
    	return false;
        old = atomic_long_cmpxchg_acquire(&lock->owner, owner,
    	                                  curr | __owner_flags(owner));
        if (old == owner)
    	return true;
        owner = old;
    }
}

Makra __owner_task() a __owner_flags() jednoduše maskují příslušné části pole owner. Klíčem je volání atomic_long_cmpxchg_acquire(), které se snaží uložit současné vlákno jako majitele mutexu za předpokladu, že je dostupný. Pokud by ho vlastnilo některé jiné vlákno, toto volání selže a kód mutexu bude vědět, že musí více makat.

Momentálně existují dva příznaky, které je možné uložit do nejméně významných bitů pole owner. Pokud vlákno zjistí, že musí při čekání na zabraný mutex spát, nastaví MUTEX_FLAG_WAITERS. Vlákno, které mutex aktuálně vlastní, bude vědět, že při uvolnění mutexu musí vzbudit čekající vlákna. Doufá se, že většinou nikdo čekat nebude, udržování tohoto bitu umožňuje vynechat kousek zbytečné práce.

Jak bylo uvedeno výše, optimistický spinning, i když je dobrý pro výkon, není férový. V nejhorším případě by mohlo smolné vlákno soutěžící o vysoce žádaný mutex nadlouho vyhladovět. Zabránit tomu má druhý bit pole owner, MUTEX_FLAG_HANDOFF, který může změnit způsob, jakým zabraný mutex mění majitele.

Jestliže vlákno už během čekání bylo uspáno, pokusí se získat mutex a selže, může nastavit MUTEX_FLAG_HANDOFF dříve, než se vrátí ke spánku. Když potom dojde k uvolnění mutexu, uvolňující vlákno si všimne příznaku a bude se chovat jinak. Zejména se musí vyhnout vyčištění pole owner, jak by se stalo za normálních okolností, pro případ, že by jej ukradlo jiné vlákno čekající na mutex. Místo toho najde první vlákno ve frontě na mutex, předá mu vlastnictví přímo a probudí toto vlákno, jakmile je hotovo. Tento tanec vrací trochu férovosti za cenu, že všichni ostatní budou muset počkat, až se spící vlákno probudí a vykoná svou práci.

Nový kód značně zjednodušuje implementaci mutexů tím, že se zbavuje několika podivných případů zahrnujících oddělená pole count a owner. Lepší je to v tom, že kód je nově nezávislý na konkrétní architektuře, takže veškerý starý kód mutexů, který závislý na konkrétní architektuře je, se může odstranit. Tím pádem poslední řádek Peterova průvodního dopisu vypadá takto:

49 files changed, 382 insertions(+), 1407 deletions(-)

Odstraňování kódu, jak už to tak bývá, je vždy v módě. A odstraněním 1000 řádků choulostivého zamykacího kódu v jazyce symbolických adres je obzvláště šik. Za předpokladu, že tento kód nepřinese výkonnostní regrese, mohlo by jít o nezbytný doplněk na budoucím plesu začleňovacího okna.

       

Komentáře