Nejdříve malá oprava k předchozímu dílu, na kterou mě upozornil někdo v diskusi — FreeBSD při wakeup neprochází všechny procesy, ale používá hashování — adresa je zahashována do 128 front. Při čtení zdrojáků jsem si toho nevšiml.
SMP
SMP znamená Symetric MultiProcessor a je to označení pro systémy s více procesory. Všechny procesory jsou si rovnocenné (vyjma startu systému, který je prováděn pouze jedním procesorem). Paměť je přístupná všem procesorům stejně. Je třeba si uvědomit, že současné procesory mění při provádění instrukcí jejich pořadí nebo složitější instrukce rozkládají na jednoduché mikroinstrukce, a proto je nutné počítat s tím, že ostatní procesory uvidí změny provedené jedním procesorem v libovolném pořadí. Pokud máme například deklarované proměnné volatile int a = 0, b = 0; a jeden procesor provede a = 1; b = 2;, může druhý procesor po určitý časový okamžik vidět b == 2 && a == 0 (pokud deklarace proměnných není volatile, může změnu pořadí přiřazení i čtení provádět už samotný kompilátor — nicméně proti přehazování instrukcí procesorem nás volatile neochrání). Pokud oba procesory provedou a++, může být výsledná hodnota a 1 nebo 2 — například na Pentiu 2 se totiž instrukce incl a rozloží na mikroinstrukce „přečti hodnotu z paměti”, „zvětši hodnotu o 1” a „ulož hodnotu do paměti”. Když se náhodou oba procesory sejdou tak, že budou současně číst, přičítat jedničku a ukládat do paměti, bude výsledná hodnota proměnné 1. Pokud nám záleží na pořadí, je třeba používat speciální atomické instrukce procesoru. U atomických instrukcí procesor zajistí, že jejich pořadí nebude měněno a že jiný procesor nebude moci přistupovat k paměťovým místům modifikovaným touto instrukcí. Kdyby ve výše uvedeném případě oba procesory provedly instrukci lock;incl a, bylo by zaručeno, že výsledná hodnota bude vždy 2.
Další problémy se SMP nastávají proto, že procesor může přehazovat vykonávání jednotlivých (mikro-)instrukcí. Může například načítat data dopředu, aniž zatím ví, zda je bude potřebovat, nebo může naopak zápisy opožďovat. IA32 garantuje, že ostatní procesory uvidí zápisy v tom pořadí, v jakém byly provedeny, nicméně na jiných architekturách není zaručeno ani to. Aby se efektům spojeným s přehazováním instrukcí dalo zabránit, byly vytvořeny speciální instrukce pro bariéry. rmb() je read-barrier a zaručuje, že žádné čtení nebude posunuto přes tuhle instrukci. wmb() je write-barrier a zaručuje, že žádný zápis nebude opožděn za tuto instrukci. mb() je bariéra pro čtení i zápis současně.
Při programování na SMP je třeba dávat zvláštní pozor na využití cachí procesoru. Každý procesor má svou vlastní L1 a L2 cache a tyto cache jsou mezi jednotlivými procesory synchronizovány pomocí metody MESI. MESI je zkratka složená z počátečních písmen názvů stavů, v jakých se řádka cache může nacházet: modified, exclusive, shared a invalid. Řádka je ve stavu shared, pokud obsah řádky odpovídá obsahu paměti a ostatní procesory mohou mít tutéž řádku ve své cachi. Stav exclusive znamená, že obsah řádky odpovídá obsahu paměti a žádný jiný procesor nemá řádku v cachi. Stav
modified znamená, že řádka byla modifikována a musí být zapsána do paměti a žádný jiný procesor tuto řádku v cachi nemá. Procesor může řádku cache číst ve všech stavech vyjma invalid. Procesor může do řádky cache zapisovat ve stavech modified a exclusive (v takovém případě stav změní na modified). Pokud procesor chce zapisovat a řádka je ve stavu shared, musí nejdříve požádat ostatní procesory, aby tuto řádku ze svých cachí uvolnily (tj. převedli ji do stavu invalid). To je pomalé, neboť to vyžaduje komunikaci po sběrnici. Každý procesor rovněž poslouchá všechny transakce na sběrnici — pokud jiný procesor čte řádku, která je ve stavu exclusive, změní stav na
shared. Pokud jiný procesor čte řádku, která je ve stavu modified, procesor zruší transakci a zapíše svou modifikovanou řádku do paměti. To je opět velmi pomalé. Z toho plyne poučení pro programování: pokud budou dva procesory vykonávat kód, který modifikuje tutéž paměť, nebo pokud bude jeden procesor do paměti zapisovat a druhý z toho samého místa číst, vykonávání bude velmi pomalé. V extrémním případě to může být i několikanásobně pomalejší než na jednoprocesorovém systému, neboť tam by cache spoustu přístupů zachytila, zatímco na víceprocesorovém systému bude docházet k neustálému přelévání cachových řádek po sběrnici mezi oběma procesory a jejich zneplatňování.Nyní popíšu, jakým způsobem byla na Linuxu a na FreeBSD podpora SMP implementována.
Obě jádra byla zpočátku navržena jako jednoprocesorová. Návrháři s možností více procesorů nepočítali. Kdyby takové jádro bylo puštěno na více procesorech současně, došlo by tam k velkému množství race-conditions (například už jen konstrukce while (lock) sleep_on(&queue); lock = 1; ... kritická sekce ...; lock = 0; wake_up(&queue), která se velmi často používala k zamykání, selže a do kritické sekce nám pustí oba procesory, pokud se sejdou v nevhodný okamžik). Nejjednodušší řešení takových problémů je takové, že do jádra pustíme nejvýše jeden procesor. Uživatelské procesy jsou vykonávány na všech procesorech současně, ale do jádra smí jen jeden. Pokud je nějaký proces v jádře a jiný proces na jiném procesoru chce vykonat nějaký syscall, musí počkat, než se první proces z jádra dostane. Taková implementace je velmi jednoduchá — stačí vzít jednoprocesorové jádro, do všech vstupů do jádra (t.j. syscall, interrupt, page-fault) přidat zámek — a už to může na víceprocesorovém stroji fungovat. Takhle to bylo implementováno v Linuxu 2.0 a FreeBSD 3. Problém této implementace je zcela evidentní — pokud procesy dělají hodně syscallů, tak pořád čekají na zámek, než se dostanou do jádra, a výkon se snižuje až na úroveň jednoprocesorového systému (nebo je dokonce ještě horší). Pro úlohy, které stráví většinu času v USER módu (například kompilace nebo různé výpočty), je taková implementace dostačující, nicméně pro úlohy, které volají často syscally (například síťový server), je naprosto nepoužitelná.
Spinlocky
V Linuxu 2.2 a FreeBSD 4 byla proto udělána lepší implementace SMP. Do jádra se již může dostat více procesorů najednou. K zamykání na krátkou dobu se používají spinlocky. Spinlock je jednoduchý zámek, který používá aktivní čekání. Pokud je spinlock zamknut a jiný procesor se ho pokusí znovu zamknout, bude tento procesor čekat v nekonečné smyčce, než první procesor spinlock uvolní. Pro zamčení spinlocku se používá atomická instrukce procesoru. Na Linuxu je spinlock deklarován ve struktuře spinlock_t. Pomocí makra spin_lock(spinlock_t lock) je možno spinlock zamknout. Pokud je spinlock již zamčen, čeká tato funkce v nekonečné smyčce. Spinlock se odemyká makrem spin_unlock(spinlock_t lock). Když je jádro zkompilováno pro jednoprocesorový systém, spinlocky jsou prázdné struktury a tato makra nedělají nic. Pokud proces drží nějaký spinlock, nesmí se zablokovat. Při zablokování dochází k přepnutí procesu a mohlo by se stát, že nový proces bude chtít zamknout tentýž spinlock a bude pak v nekonečné smyčce čekat na uvolnění, které nikdy nepřijde. Na Linuxu existují ještě rw-locky, což jsou spinlocky, které je možno zamykat pro čtení a pro zápis. Deklarují se ve struktuře rwlock_t a je možno na nich provádět operace read_lock, read_unlock, write_lock a write_unlock.
Linux 2.4 obsahuje brlocky, což jsou read-write spinlocky optimalizované pro rychlé čtení a pomalý zápis (např. pro routovací tabulky). Brlock se skládá z více rwlocků, pro každý procesor jeden. Při požadavku na čtení je zamčen jen ten jeden na daném procesoru pro čtení. Při požadavku na zápis jsou zamčeny všechny pro zápis. Brlock zabraňuje přelévání dat mezi cachovými řádkami, ke kterému by docházelo při použití rwlocku.
Linux 2.6 brlocky nemá a většinou místo nich používá techniku Read-Copy Update. Ta nepoužívá žádné zámky. Struktury chráněné touto technikou je možno číst v sekcích ohraničených voláními rcu_read_lock() a rcu_read_unlock(). Ta nemají žádné argumenty a pouze zabrání preemptivnímu volání scheduleru v jádře. Pokud chce někdo strukturu odstranit, odstraní ukazatel na ni, pak počká, až všechny procesory projdou „quiescent” stavem, a pak může strukturu odalokovat bez nebezpečí, že na ni bude někdo sahat. Quiescent stav je stav, kdy procesor nedrží žádné read-locky, a tedy ani žádné reference na daný objekt. V Linuxu quiescent stav nastane při vstupu do scheduleru z časovače (proto to zabraňování preempce v rcu_read_lock()), v jiných implementacích této techniky může nastávat pokaždé, když proces vyjde ze všech rcu_read_lock-sekcí. Pomocí volání call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg)) je možno umístit požadavek na callback, který bude zavolán, až všechny procesory projdou quiescent stavem. Typicky se sem umisťuje uvolnění struktury.
Přerušení na víceprocesorovém systému mohou přicházet na libovolný procesor. Linux 2.4 a vyšší má možnost přiřadit určitému přerušení jeden konkrétní procesor. Výhodou je lepší využití cachí — data, se kterými manipuluje obslužná rutina přerušení, budou moci být v cachi procesoru a nebudou přelévána mezi více procesory. Určitou nevýhodou může být nevyvážená zátěž procesorů. Pokud máme dvouprocesorový stroj se dvěma stejně zatíženými síťovými kartami, je dobré přerušení od každé karty přiřadit na jeden procesor. Pokud máme jen jednu síťovou kartu, je dobré přerušení přiřadit jednomu určitému procesoru, ale jen do chvíle, než daný procesor zátěž TCP/IP stacku přestane zvládat. Pak je vhodnější přerušení nechat posílat na oba procesory, nechat je oba zpracovávat zátěž a smířit se s tím, že k přelévání dat mezi cachemi bude docházet.
K synchronizaci s obsluhami přerušení se rovněž používají spinlocky. Rozdíl je v tom, že před vlastním zamčením spinlocku musí kód jádra zakázat přerušení na procesoru, na kterém běží. Kdyby kód jádra zamknul spinlock bez zakázání přerušení, mohlo by se stát, že přerušení přijde a bude chtít zamknout tentýž spinlock — to by ovšem znamenalo nekonečné čekání a zatuhnutí. K zamykání a odemykání je možno použít makra spin_lock_irq(spinlock_t spinlock) a
spin_unlock_irq(spinlock_t spinlock), která na procesoru, na němž běží, zakážou přerušení před vlastním zamčením a povolí je po odemčení, nebo makra spin_lock_irqsave(spinlock_t spinlock, unsigned long flags) a spin_lock_irqrestore(spinlock_t spinlock, unsigned long flags), která před zakázáním přerušení uloží stav zakázání do proměnné flags a po odemčení spinlocku tento stav obnoví (jedná se o makra preprocesoru a nikoli funkce, proto spin_lock_irqsave do proměnné flags zapisuje, ačkoli není tato proměnná předávána jako pointer). Pokud je jádro zkompilováno jako jednoprocesorové, spin_lock_irq funguje jako cli, spin_unlock_irq jako sti,
spin_lock_irqsave jako save_flags; cli a spin_unlock_irqsave jako restore_flags. Zakázání přerušení pomocí cli a sti se v Linuxu už téměř nepoužívá. Zakázání přerušení na všech procesorech je moc pomalé a zakázání přerušení na jednom procesoru nepomůže. K synchronizaci s obslužnými rutinami přerušení se používá zakázání přerušení na jednom procesoru a spinlock (pomocí maker spin_lock_irq a
spin_unlock_irq). Obslužná rutina přerušení pak vezme spinlock pomocí spin_lock a spin_unlock. U kódu, o kterém nevíme, zda bude volán se zakázanými, nebo povolenými přerušeními, je třeba použít spin_lock_irqsave a spin_lock_irqrestore. Tato metoda zamykání je v Linuxu používána téměř všude. Je zajištěno, že přerušení nepřijde na procesor, který zákaz provedl. Pokud přerušení přijde na jiný procesor, bude jeho obslužná rutina čekat ve spinlocku, než skončí kritická sekce.
Ve FreeBSD 4 existují také spinlocky, ale nazývají se simple locky. Jsou deklarované ve struktuře struct simple_lock a je možno na nich provádět funkce simple_lock a simple_unlock, které jsou funkčně ekvivalentní linuxovým spin_lock a spin_unlock. Na FreeBSD to jsou skutečné funkce — ne makra ani inline funkce — proto jsou mírně pomalejší.
Na FreeBSD 5 simple locky vymizely a objevila se nová struktura struct mtx. Tuto strukturu je možno používat jak pro spinlocky, tak pro sleep locky, které proces zablokují, pokud je zámek zamčený. Pokud je tato struktura použita jako blokující zámek, k zamykání a odemykání se používají funkce mtx_lock a
mtx_unlock. Pokud je použita jako spinlock, používají se mtx_lock_spin a mtx_unlock_spin. Tyto funkce pro spinlocky zakazují a povolují přerušení jako linuxové spin_lock_irqsave a spin_lock_irqrestore. Funkce jsou zčásti inlinované a implementace blokujících zámků je výrazně lepší než lockmgr (který byl naprosto nepoužitelný), nicméně jednoduchosti a rychlosti linuxových zámků stále nedosahují. Zejména možnost rekursivních zámků (pokud je při inicializaci nastaven příslušný příznak) je dle mého názoru zcela zbytečná. Spinlocky navíc nejsou plně inlinované — volají pořád funkci na zakázání přerušení a uložení stavu. FreeBSD 5 má i blokující read-write locky ve struktuře
struct sx. Jejich implementace není moc pěkná — při každém zamčení i odemčení sx locku dojde ke dvěma operacím na mtx locku. Ve FreeBSD 5 byl napsán speciální debuggovací kód nazvaný witness, který kontroluje všechny operace se zámky a ohlásí chybu, pokud je porušeno pořadí braní zámků (neboť při nedodržení pořadí hrozí deadlock) nebo pokud proces provede nedovolenou operaci — například se zablokuje a drží spinlock. Výhoda tohoto kódu je taková, že přímo ohlásí jméno souboru i řádku, kde k takové operaci došlo. Pokud je při kompilaci jádra witness povolen, způsobuje to samozřejmě velké zpomalení, neboť je třeba udržovat seznam držených zámků pro každý proces.
Big kernel lock
Při zavádění spinlocků bylo potřeba velké části kódu přepsat. To nebylo možno provést naráz pro celé jádro. Aby mohly být nadále používány části kódu napsané pro původní jednoprocesorové jádro, byl zaveden big kernel lock. Big kernel lock je spinlock, který má speciální vlastnost — proces držící tento spinlock se může zablokovat. Při zablokování procesu dojde k uvolnění big kernel locku a při opětovném probuzení procesu je lock opět zamčen. Kód napsaný pro původní jednoprocesorová jádra může být nadále používán — musí však běžet s big kernel lockem zamčeným.
Na Linuxu big kernel lock zamykáme a odemykáme pomocí funkcí lock_kernel() a unlock_kernel(). Na FreeBSD 4 se používají funkce get_mplock() a rel_mplock(), na FreeBSD 5 mtx_lock(&Giant) a mtx_unlock(&Giant). Na všech systémech je zámek rekursivní — na Linuxu je to asi jediný rekursivní zámek, který tam existuje. Na FreeBSD 4 navíc provedení get_mplock způsobí, že interrupty budou přicházet jen na ten jeden procesor, který get_mplock provedl. To zajistí, že synchronizace přerušení pomocí spl funkcí bude fungovat.
Kód běžící s big kernel lockem je nežádoucí, protože ho není možno paralelně vykonávat na více procesorech. Proto je snaha vývojářů tento big kernel lock odstraňovat. Na Linuxu 2.2 se nacházel na mnoha místech — v celém filesystému, swapperu a ve všech síťových funkcích. Na Linuxu 2.4 byl ve spoustě běžně vykonávaného kódu odstraněn —již je možné číst a zapisovat do souborů, swapovat stránky a provádět síťové operace, aniž by byl big kernel lock sebrán. Tyto operace je tedy možno provádět paralelně na několika procesorech, což vede k výrazně lepšímu využití víceprocesorového systému. FreeBSD je na tom se SMP paralelismem výrazně hůř. FreeBSD 4 sice synchronizační primitiva pro SMP má, nicméně jsou velmi málo využívána a vyjma osmi jednoduchých sycallů běží všechny s big kernel lockem. Na FreeBSD 5 SMP paralelismus pokročil; syscally již neberou big kernel lock hned při vstupu, v jádře se již začínají objevovat spinlocky, nicméně s big kernel lockem běží celé síťování, filesystém i správa paměti. Řekl bych, že FreeBSD 5 je tak asi úrovni Linuxu 2.2.
Chyby v SMP
SMP s sebou přináší i další problém, a tím jsou notoricky se vyskytující chyby v jádrech. Při psaní jádra pro jednoprocesorový systém člověk moc často chybu neudělá. K přepnutí procesu tam může dojít jen na stanovených místech a na těch je možno ohlídat, zda jiný proces nezměnil nebo neuvolnil struktury, se kterými právě pracujeme. Na SMP je situace mnohem nepřehlednější, neboť v jádře se může nacházet více procesorů současně a k synchronizaci je třeba spinlocky důsledně využívat. Nejhorší na tom je, že bugy v SMP synchronizaci se projevují velmi zřídka — pokud například programátor zapomene použít spinlock, systém zdánlivě běží v pořádku a vytuhne nebo spadne třeba jednou za měsíc, až se oba procesory náhodou zkříží v kritické sekci. To se samozřejmě ladí mnohem hůře, než kdyby se pád projevoval denně. Chyby v SMP zamykání v podstatě vůbec debuggovat nejdou a nezbývá než si celý kód přečíst a ujišťovat se, že je zamykání správné.
Například v jádře Linuxu 2.4.18 byly opraveny SMP race-conditiony při alokaci PID procesů, v implementaci syscallu dnotify a v netfilteru. Já jsem našel SMP bug v Linuxu 2.4.18 a 2.5.23 ve funkci mark_inode_dirty, který mohl způsobit, že inoda nebude zapsána na filesystém, pokud ji jeden procesor modifikuje a druhý zapisuje (bug spočíval v nerespektování možnosti, že procesor přehazuje instrukce, a nepoužití bariéry). Jak vidno, nejedná se tedy o nepodstatné drobnosti, které se běžným uživatelům neprojevují. Nejhorší vlastností SMP race-conditionů je, že se projevují velmi zřídka.
V Linuxu 2.0 a 2.2 je zase bug při přístupu k tabulce stránek. Pokud na jednom procesoru běží prohledávání tabulek stránek při vyswapovávání na disk a na druhém procesoru běží proces, jehož tabulka stránek je prohledávána, může nastat následující situace: první procesor přečte položku tabulky stránek a zjistí, že má shozené příznaky ACCESED a DIRTY a že tedy může být odstraněna. Druhý procesor zapíše do oné stránky, čímž nastaví příznaky ACCESSED i DIRTY. První procesor přepíše položku na neplatnou (neboť tam dříve viděl bity ACCESSED a DIRTY shozeny) a odstraní stránku z paměti. Druhý případ téhle race-conditiony je takový, že na počátku má položka tabulky stránek nastaven bit ACCESSED a shozen bit DIRTY. První procesor přečte položku tabulky stránek a rozhodne se, že příznak ACCESSED zruší a stránku nechá v paměti. Druhý procesor zapíše do stránky, čímž nastaví DIRTY. První procesor přemaže položku tabulky stránek původní položkou se smazaným příznakem ACCESSED, čímž bohužel smaže i právě nastavený příznak DIRTY. Při přístupu k tabulce stránek na víceprocesorovém systému je třeba používat atomické instrukce procesoru. Tento bug se projevuje jen u stránek namapovaných ze souboru při použití příznaků MAP_SHARED a PROT_WRITE. Naštěstí se neprojevuje u naalokovaných stránek nebo stránek namapovaných s MAP_PRIVATE. V jádrech 2.4 je opraven, vývojáři ho z mně neznámých důvodů odmítají opravit ve starších jádrech 2.2 a 2.0.
V Linuxu 2.2 je spousta dalších neopravených SMP bugů, například jsem v 2.2.21 našel špatnou implementaci funkcí wait_on_buffer a wait_on_inode, která může vést k zatuhnutí a nekonečnému čekání na inodu nebo buffer, který je již načten (nastane v situaci, kdy současně jeden procesor dokončuje načtení a druhý začíná čekat — jedná se rovněž o nerespektování možnosti přehazování instrukcí). V jádrech 2.4 jsou tyto bugy opraveny.
Závěr: SMP ve FreeBSD je použitelné pro případ, kdy procesy tráví většinu času v userspace. FreeBSD 5 je sice trochu lepší, nicméně to je experimentální verze, která by se na produktivních systémech neměla používat vůbec. V Linuxu 2.4 a 2.6 je podpora SMP kvalitní, nicméně to s sebou přináší riziko bugovitosti, takže bych nedoporučoval Linux 2.4 ani 2.6 na SMP používat, pokud je potřeba absolutní spolehlivost. Pokud nebudeme mapovat soubory do paměti a zapisovat do nich, tak nejstabilnější na SMP bude asi jádro Linuxu 2.0, neboť v něm nehrozí SMP race-conditiony. Nicméně takové jádro je zcela neefektivní pro servery nebo jiné úlohy, které volají hodně syscallů.
Preemptivní jádro Linuxu
S podporou SMP v Linuxu souvisí i další vlastnost — možnost preemptivního přepínání procesů uvnitř jádra. Jádro bylo z větší části přepsáno tak, aby se do něj mohlo dostat více procesorů, a tyto procesory se synchronizují pomocí spinlocků. Někoho tedy napadlo, že by spinlocky šly využít i k synchronizaci mezi jednotlivými procesy a ty by pak bylo možno přepínat kdykoli.
Možnost preemptivního přepínání procesů existuje pouze v experimentálních jádrech Linuxu 2.6. Implicitně je vypnutá; musí se zapnout při konfiguraci jádra. Funguje následovně: spinlocky zabraňují preemptivnímu přepnutí procesu uvnitř jádra. Pokud proces nedrží žádný spinlock, může být přepnut. Většina kódu napsaného pro SMP s nepreemptivním jádrem tak může fungovat i s preemptivním přepínáním procesů v jádře na jedno- nebo víceprocesorovém stroji. Problém nastane s kódem, který používal CPU-local storage (to je malá oblast paměti vyhrazená pro každý procesor). S nepreemptivním přepínáním procesů bylo možno, aby kód využíval CPU-local storage bez braní jakéhokoli spinlocku nebo zámku (pouze se během práce s CPU-local storage nesměl zablokovat), naproti tomu při preemptivním přepínání procesů v takovém kódu vznikne race-condition. Je potřeba všechny takové kusy kódu najít a přepsat pro použití preemptivního jádra. Doufejme, že to v 2.6 již bylo provedeno.
Preemptivní jádro vede k rychlejšímu probuzení procesů, nicméně garantovanou dobu probuzení nám nedává. Preempce se totiž vypíná, pokud nějaký proces vezme big kernel lock pomocí lock_kernel. A takových míst se stále ještě vyskytuje mnoho, i když ubývají. Preempce také může vést k určitému zpomalení na jednoprocesorových systémech, neboť spinlocky, které bez preempce nedělaly nic, nyní začnou zabraňovat přepínání.
