Jaderné noviny - 28. 6. 2006

11. 7. 2006 | Robert Krátký | Jaderné noviny | 5811×

Stav vývoje jádra. Citát týdne: Matthew Frost. Stromy II: Red-black stromy. Zásadní změny v suspend. Časovače s vysokým rozlišením a bezčasové jádro.

Stav vývoje jádra

Od posledního týdne se do Linusova jádra dostalo kolem 2800 dalších změn. Aktualizace se týkaly ALSA, i2c, hwmon, PCI, USB, XFS, ovladačového kódu, architektur Power PC, ARM, SPARC 64, m68k a x86-64, síťových ovladačů, SATA, ACPI, síťovacího kódu, V4L ovladačů, NFS, Infiniband, DM, MD, sestavovacího systému, OCFS2, XFS, CIFS, JFFS2 a mnoha dalších částí jádra. Stručně řečeno, obrovský objem nově začleněných oprav a aktualizací, který dává znát, že vývoj se nikterak nezpomalil.

(Greg Kroah-Hartman)

Citát týdne: Matthew Frost

Ne, to tahle nevyhnutelná hádka lidem nevybíravým způsobem říká, že zdrojáky jádra nemají rozbalovat jako root. Celé to vychází z rozporu o tom, jestli máme lidem důvěřovat, že se o bezpečnost svého počítače postarají sami, protože dobře vědí, jak fungují nástroje, které používají, nebo chceme předpokládat, že nejsou dost inteligentní na to, aby své nástroje využívali rozumně a bezpečně, a proto je raději omezíme. Ta druhá možnost je neslušná, i když to tak nebývá podáváno. Ta první uživateli důvěřuje.

Ano, nejdříve je nutné se učit. Tak je to vždy. Nikdy se nejde vyhnout začátkům.

-- Matthew Frost <artusemrys -at- sbcglobal.net>

Stromy II: Red-black stromy

Tento článek je trošku opožděným pokračováním Stromy I: Radix stromy. Kromě radix stromů obsahuje jádro implementaci datové struktury známé jako "red-black strom" [červeno-černý]. Tyto stromy (v jádře nazývané "rbtrees") jsou formou polovyvážených [semi-balanced] binárních stromů. Každý uzel ve stromě obsahuje hodnotu a až dvě děti; hodnota uzlu je větší než hodnoty všech dětí v "levé" větvi a menší než hodnota všech dětí v "pravé" větvi. Takže red-black strom je možné zřetězit provedením průchodu, který jde nejprve do hloubky a pak zleva doprava.

Každý uzel v red-black stromu je zabarven buď červeně nebo černě, přičemž kořen je vždy černý. Existují poměrně komplikovaná pravidla určující zabarvení jednotlivých uzlů a především to, jak mají být barvy využívány k rozhodování o času a způsobu nového vyvažování stromu. Nebudu se věnovat podrobnostem mechanismu red-black stromů, zvláště protože je dobře popsán v článku ve Wikipedii (který je také zdrojem zde použitého obrázku). Místo toho se zaměřím na to, jak jsou red-black stromy využívány v linuxovém jádře.

Komplexní pravidla red-black stromů mají své výhody. Protože jde o binární strom, může provádět vyhledávání v logaritmickém čase. Je-li strom správně spravován, nebude nikdy nejdelší cesta k uzlu více než dvojnásobek nejkratší cesty - jinými slovy, strom je vždy v přibližné rovnováze. Ale vlastnost, která je z hlediska jádra asi nejužitečnější, je to, že vkládání i mazání je 1) rychlé, 2) prokazatelně časově omezené. Veškeré úsilí vývojářů věnované snižování latencí by přišlo nazmar, kdyby bylo datové struktuře umožněno věnovat se vyvažování po neomezeně dlouhou dobu. Uživatelé red-black stromů trošku platí za to, že strom není dokonale vyvážený, ale na oplátku dostanou rychlé a časově omezené vkládací a mazací operace. Red-black strom je tedy možné používat v situacích, ve kterých uzly rychle vznikají a zanikají.

V jádře je red-black stromů několik. Anticipatory, deadline a CFQ I/O schedulery [plánovače] používají rbstromy k sledování požadavků; ovladač pro paketový zápis na CD/DVD dělá totéž. Kód časovače s vysokým rozlišením používá rbstrom k organizaci čekající požadavků. Souborový systém ext3 sleduje pomocí rbstromu položky adresářů. Oblasti virtuální paměti (VMA) jsou sledovány rbstromy, stejně jako popisovače souborů epoll a šifrovací klíče.

Začíná se includováním <linux/rbtree.h>. Jde však o jednu ze záludnějších datových struktur. Při navrhování obecné datové struktury pro jazyk jako je C se vývojář musí rozhodnout, jak do struktury začlenit libovolné typy, a jak je porovnávat. Člověk, který implementoval linuxové rbstromy (copyright v kódu ukazuje na Andrea Arcangeliho), se rozhodl takto:

• Struktury, které mají být součástí stromu, musí obsahovat struct rb_node; pro oddělení objektů nebudou žádné void * ukazatele. Protože jde o běžný způsob implementace jaderných datových struktur, moc lidí to nepřekvapí.
• Kód rbstromů nepoužívá žádné zpětné volání, které by "porovnávalo dva objekty". Místo toho musí uživatelé rbstromů napsat vyhledávací a vkládací funkce vyšší úrovně sami za pomoci základních nízkoúrovňových funkcí [primitives]. Kvůli tomu je používání rbstromů trošku náročnější a datová struktura méně černobílá, než by se učitelům programování líbilo. Na druhou stranu to znamená rychlejší celkovou implementaci bez hromady nepřímých volání funkcí v nejexponovanější části průchodových smyček.

Nemělo by se také zapomínat na to, že rbstrom, podobně jako mnoho dalších datových struktur v jádře, neimplementuje vlastní zamykání. Každý kód, který rbstrom využívá, musí implementovat vlastní vzájemné vyloučení, aby nedošlo k poškození stromu. Obyčejně bude takové zamykání dobře zapadat do schématu, které daný kód využívá, takže není potřeba mít nezávislý zamykací mechanismus.

Kořen rbstromu je typu struct rb_root; strom lze inicializovat do prázdného stavu následujícím řádkem:

    struct rb_root the_root = RB_ROOT;

Předpokládejme na chvíli, že už máme red-black strom plný zajímavých dat. Průchod takovým stromem (bez vyhledávání) je jednoduchý:

    struct rb_node *rb_first(struct rb_root *tree);
    struct rb_node *rb_last(struct rb_root *tree);
    struct rb_node *rb_next(struct rb_node *node);
    struct rb_node *rb_prev(struct rb_node *node);

Volání rb_first() vrátí ukazatel na první položku stromu, zatímco rb_last() vrátí poslední položku. Pro pohyb vpřed i vzad po stromu stačí volání rb_next() a rb_prev(). Ve všech těchto případech značí vrácená hodnota NULL, že požadovaný uzel neexistuje.

Protože struktury rb_node jsou vloženy do dalších struktur, které nás zajímají, stačí pro nalezení rb_node použít správné pole struktury. Avšak volání jedné z výše popsaných funkcí vrátí ukazatel na vloženou rb_node strukturu, ne obalovou strukturu - což bývá to, co programátor ve skutečnosti chce. Pro takovou situaci bylo vytvořeno makro container_of(), i když v tomto případě není nutné použít container_of() přímo. Místo toho by se použila rb_entry():

    rb_entry(ukazatel, typ, člen);

Kde ukazatel je ukazatel na strukturu rb_node, typ je typ obalovací struktury a člen je název rb_node struktury v kontejneru.

Prohledávání existujícího stromu je prosté: začneme u kořene, pak porovnáváme hodnotu každého uzlu s předmětem hledání a podle potřeby sledujeme buď levou nebo pravou větev. Takže všechen kód pro prohledávání rbstromů vypadá asi takto:

    struct my_stuff *my_rb_search(struct rb_root *root, int value)
    {
        struct rb_node *node = root->rb_node;  /* vrchol stromu */

        while (node)
	{
	    struct my_stuff *stuff = rb_entry(node, struct my_stuff, node);

	    if (stuff->coolness > value)
		node = node->rb_left;
	    else if (stuff->coolness < value)
		node = node->rb_right;
	    else
		return stuff;  /* Nalezeno */
  	}
	return NULL;
    }

Hledáme struct my_stuff, jejíž pole coolness odpovídá dané value. Celočíselná hodnota je použita kvůli zjednodušení, ale ne všechna použití musí být tak prostá. Je-li coolness kořenového uzlu větší než hledaná hodnota, musí být hodnota nalezena v levé větvi stromu (pokud vůbec ve stromu je), takže hledání jde podél větve rb_left a začne znovu. Hledaná hodnota vyšší než aktuální uzel značí, že by měla být prohledána pravá větev. Funkce nakonec buď najde přesnou trefu, nebo dojde na konec stromu.

Vkládání už je ošemetnější. Kód musí stromem procházet, dokud nenalezne uzel, kde má k vložení dojít. Jakmile je místo objeveno, je nový uzel vložen jako "červený" a podle potřeby je provedeno vyvážení. Vkládácí kód obyčejně vypadá takto:

    void my_rb_insert(struct rb_root *root, struct my_stuff *new)
    {
        struct rb_node **link = &root->rb_node, *parent;
        int value = new->coolness;

        /* Jdi na konec stromu */
        while (*link)
        {
            parent = *link;
            struct my_stuff *stuff = rb_entry(parent, struct my_stuff, parent);

            if (stuff->coolness > value)
                link = &(*link)->rb_left;
            else
                link = &(*link)->rb_right;
        }

	/* Sem vlož nový uzel */
	rb_link_node(new, parent, link);
	rb_insert_color(new, root);
    }

V tomto případě vypadá průchod stromem podobně jako hledání. Ukazatel link je však dvojitě nepřímý; nakonec bude využit k tomu, aby kódu rbstromu řekl, který ukazatel větve (rb_left nebo rb_right) by měl být nasměrován na novou položku. Kód stromem prochází až na úplný konec - v tu chvíli ukazatel parent označí rodiče nového uzlu a link ukáže na příslušné pole v rámci parent. Pak je zavoláno:

    void rb_link_node(struct rb_node *new_node,
                      struct rb_node *parent,
		      struct rb_node **link);

Toto volání nalinkuje nový uzel do stromu coby červený. Po takovém volání však už strom nemusí splňovat všechny požadavky na red-black strom, takže může dojít k vyvažování. To se provede voláním:

    void rb_insert_color(struct rb_node *new_node, struct rb_root *tree);

Po dokončení bude strom konzistentní.

Do předchozího příkladu je zabudován důležitý předpoklad: nová hodnota vkládaná do stromu tam v tu chvíli ještě není. Není-li tento předpoklad splněn, mohl by být výsledný strom poškozený. Existuje-li možnost duplicitního vložení, kód musí otestovat, jestli už hodnota není přítomna (jako v případě hledání), a skončit (bez vložení uzlu), je-li hodnota nalezena.

Odstranění uzlu ze stromu je snazší; zavolejte:

    void rb_erase(struct rb_node *oběť, struct rb_root *strom);

Po tomto volání už oběť nebude součástí stromu, který byl možná v rámci operace znovu vyvážen. Je-li však jedna položka nahrazována jinou se stejnou hodnotou, není nutné podstupovat odstraňování a vkládání. Místo toho použijte:

    void rb_replace_node(struct rb_node *starý, 
                         struct rb_node *nový,
			 struct rb_root *strom);

To rychle nahradí starý za nový. Pokud však nový nemá stejnou hodnotu jako starý, dojde k poškození stromu.

Zásadní změny v suspend

Článek napsal Greg Kroah-Hartman.

Během minulých dvou týdnů probíhala dlouhá diskuze o budoucnosti suspend [uspání] v Linuxu. Ne, nešlo o to druhé suspend; tohle je o tom, co uživatelé opravdu chtějí - funkční suspend do RAM.

Všechno načalo několik jednoduchých patchů od Linuse, které implementují rámcové řešení umožňující debugování problémů během uspávání. Rychle se to však zvrtlo v remcání o tom, jak špatně teď jádro uspávání řeší:

> Myslím, že se snažíš měnit model, který funguje...

Bzzt. Konec hry.

Faktem je, že ta věc nefunguje už léta. Jednou už se musíme smířit s tím, že nejde jen o "ovladače". Nefunguje ještě něco jiného - a vsadím se, že je to ten model.

A jak se všichni dlouhá léta pletli v tom, jak by mělo uspávání správně fungovat:

Chápeš? TOHLE NEDĚLÁME. Říkám už roky, že bychom to měli dělat. Snažil jsem se prosadit dvoufázové uspávání. Snažil jsem se vysvětlit důvody. Zjevně jsem neuspěl, protože nic podobného neděláme.

Místo toho říkáme zařízením to naše "spěte prosím" jednofázově. Žádná podpora pro samostatné volání "uložte prosím svůj stav". Na houby.

Když se o tomto posledním bodu Linus dohadoval už několik emailů, udělal to, co by měl udělat každý, kdo chce dokázat, že je jeho tvrzení správné: napsal fungující patch, který navrhované změny implementuje.

K plnému pochopení problému je třeba se podívat na rozhraní, které má uspávání na starosti, a které dnes jádro ovladačům nabízí. Když si jádro přeje vypnout zařízení (pro nějakou uspávací akci), prochází se celý strom zařízení a dojde k volání zpětného volání suspend.

U PCI zařízení vypadá toto zpětné volání takto:

int (*suspend) (struct pci_dev *dev, pm_message_t state);

Ukazatel na PCI zařízení, které má být uspáno, je předán ovladači společně se stavem, do něhož chce jádro přejít. V rámci této jediné funkce je ovladač zodpovědný za provedení všech uspávacích úkolů, které dané zařízení vyžaduje.

Velký problém tohoto přístupu je, že pokud není možné zařízení uspat právě v ten okamžik, musí se velmi složitě snažit dát jádru vědět, že by jej mělo opět zavolat (dělá se to vrácením -EAGAIN - pak se doufá, že bude opět zavoláno). A další potíž je, že ovladač má v této funkci na starosti kompletní vypnutí zařízení. To jádru brání například ve vytváření snímků systému (aktuální stav systému). Co také dělat, nemá-li ovladač dostatek paměti k uložení stavu zařízení, aby mohlo dojít k řádnému uspání?

A dále: většinu procesu uspávání by měly zajišťovat "třídy", ne jednotlivé ovladače. Například síťový kód by měl vypínat přenosové fronty a všechno pro ovladače utišit, aby to nebylo potřeba provádět samostatně v každém ovladači. Tento poslední bod představuje hlavní změnu v Linusově modelu. A dle mého mínění jde i o nejdůležitější věc.

Linus tedy uspávací proces mění na sérii kroků:

• Všechna zařízení jsou na začátku součástí seznamu dpm_active a jsou, jak patrno, "aktivní" neboli spuštěná.
• Pro každé zařízení v globálním stromu zařízení je voláno nové zpětné volání. Nazývá se suspend_prepare a má stejné parametry jako má stávající suspend pro každý druh sběrnice. Zařízením zatím není dovoleno se odpojit od jádra (jako se před vypnutím odpojují USB zařízení) a jejich ovladače musí provést všechny přípravy pro pozdější uspání. Většinou jde o alokaci potřebné paměti k uložení stavu zařízení nebo jiné uklízecí práce. Mělo by proběhnout vše, co může snadno selhat. Když se něco nepovede, chyba bude nahlášena. Ovladače mohou volat funkce, které možná spí, protože přerušení nejsou vypnuta.
• Jádro pak prochází celým seznamem dpm_active, přesunuje do seznamu dpm_off a volá zpětné volání suspend pro různé subsystémy (to je novinka). Po uspání subsystémů je voláno zpětné volání suspend pro sběrnice.
• Vypnutí přerušení.
• Jádro prochází celým seznamem zařízení dpm_off a přesunuje do seznamu dpm_off_irq, přičemž volá nové zpětné volání nazvané suspend_late().
• Po dokončení lze systém uspat vypnutím procesoru, který je uveden do požadované úrovně spánku.

Probuzení jádro docílí převrácením pořadí manipulace se seznamy zařízení:

• Jádro prochází seznamem dpm_off_irq a přesunuje zařízení do seznamu dpm_off, přičemž volá nové zpětné volání resume_early.
• Zapnutí přerušení.
• Jádro prochází celým seznamem zařízení dpm_off a přesunuje do seznamu dpm_active, přičemž volá zpětné volání resume (nejprve resume funkci pro sběrnice, potom pro třídy).

Nové schéma jádru umožňuje správně reagovat na chybové podmínky v případě, že se během procesu uspávání něco nepovede. Je-li například způsobena chyba během procesu suspend_late, pak bude zpětné volání resume_early voláno jen u zařízení v seznamu dpm_off_irq, aby byl systém správně probuzen a mohl se z chyby zotavit.

Linusův patch je malý - nemá více než 400 řádků. Ostatní vývojáři jádra, kteří si na nové schéma začínají zvykat, jej hodnotili kladně. Zatím se neobjevil v žádných veřejných jaderných stromech, ale doufejme, že bude Linux brzy řešit otázku uspávání daleko spolehlivějším a správnějším způsobem.

---

Následující obsah je © KernelTrap

Časovače s vysokým rozlišením a bezčasové jádro

23. čer, originál

Thomas Gleixner a Ingo Molnar poslali aktualizaci svého časovače s vysokým rozlišením pro jádro 2.6.17, na kterém jsme založili implementaci bezčasového [tickless] jádra (dyntick) a také funkci "dynamické HZ". Patch v současné době funguje na x86, porty na x86_64, PPC a ARM se připravují. Thomas vysvětlil: Časovače s vysokým rozlišením (CONFIG_HIGH_RES_TIMERS) umožňují POSIXovým časovačům a funkci nanosleep(), aby byly tak přesné, jak jen to dovoluje hardware (kolem 1usec na běžném hardwaru). Jde o transparentní funkci - je-li zapnuta, jsou prostě časovače o hodně přesnější než se stávajícím rozlišením v HZ. Bezčasové jádro popisuje takto:

Funkce bezčasového jádra (CONFIG_NO_HZ) umožňuje přerušení časovače 'na vyžádání': nemá-li v okamžiku, kdy systém přestane pracovat, vypršet žádný časovač dejme tomu 1,5 vteřiny, bude systém naprosto nečinný 1,5 vteřiny. To by mělo pomoci ochladit procesory a ušetřit energii: na našich testovacích strojích jsem naměřili změnu účinné rychlosti IRQ z HZ na 1-2 přerušení časovače za vteřinu.

       

Komentáře

[Thunder.m]

No velmi mě těší že si špatně fungujícího uspávání konečně vývojáři všimli, bylo by super moci bez obav uspat počítač a pak ho taky ve více než 99,9% úspěšně probudit :)

[filbar]

Tak mi hibernace do ram i hibernace na disk se suspend2 fungovala až do jádra 2.6.17. V tomto jádře se muselo něco změnit, protože s jádrem 17 se mi přestal probouzet monitor jak u nb, tak stolního PC. Doufám, že to bude brzy opraveno.

[Drew]

no mě jakožto majiteli notebooku přijde hibernace mnohem důležitější neš suspend to ram - ono už je jedno, jeslti se to vybije za dvě nabo za tři hodiny...

[Martin Beránek]

coze? rozdil mezi STR a zapnutym systemem jenom 1hodina??? ne ze by mi STR v Linuxu fungoval, ale na Win mi notes vydrzi hodne dlouho...

[robertK]

tam dost záleží na typu notebooku.

[čavo]

Osobne som mal na starom notebooku, ak sa nemýlim rozdiel 2 hodiny voci 30 hodinám. Ak máte len taký krátky rozdiel, tak je niekde chyba. (na novom notebooku mi Suspend to RAM nefunguje. Zatial.

[helb]

Vám vydržel notebook 30 hodin!?

[tomas84]

Mně vydrží i déle než 30 hodin... po 24 hodinách zbývá ještě cca 30% baterky... samozřejmě pokud byla před suspendováním nabitá naplno.

[Michal Čihař]

Já bych to řekl přesně opačně - STR mi vydrží cca týden, takže hibernaci v podstatě nepoužívám.

[tomas84]

To nemyslíte vážně?

Hibernace vyjde nastejno jako vypnutí a nové zapnutí...

V Suspen to RAM mi vydrží book několik dní a přepnutí do něj trvá 6 sekund a probuzení 8 sekund.

[Milan Horák]

Citát týdne do kamene tesat. Zvlášť poslední odstaveček.

[Zdeněk Štěpánek]

Me na starym Compaqu fungovalo Suspend To Ram uplne bez problemu. Zmacknul jsem cudl, system chcipnul, znovu jsme zmacknul a pokracoval (treba i v prehravani MP3 pres XMMS).

Pokud mame funkcni Suspend To Disk, tak Suspend To Ram nepovazuju za az tak dulezitou vec.

Zdenek

[Peter Golis]

aj u mna, ale musel som rucne spustit synchronizaciu hodin - compaq armada 4120 (P120Mhz).

[peter_h]

Nevie niekto blizsie info, ako to funguje? Neviem o tom moc najst. Toto moze chladit cpu len ak je fakt pomale a 1000 preruseni za sekundu je prenho uz dost slusna zataz. Sice nechapem presne ako to funguje, ale idealne by bolo, keby to fungovalo tak, ze ked je system pod zatazou, tak sa zvysi pocet preruseni za sekundu az po nejake pevne stanovene maximum, aby bola dobra interaktivita a ked sa nic nerobi, tak klesne az na nulu.
A je to kompatibilne so vsetkymi ovladacmi?

[disorder]

scheduler linuxu je ok, interaktivita funguje ako ma aj pri plnej zatazi.

na vymyslanie kde usetrit elektriku su ini experti. a este si vsimni na kolko je vytazeny procesor, ked "nic" nerobi - aj vtedy mas rovnaky pocet preruseni, to je minimalna zataz.

[peter_h]

Ja som to skor myslel koli tomuto:

cat /proc/acpi/processor/CPU0/power
active state:            C2
max_cstate:              C8
bus master activity:     00000000
states:
    C1:                  type[C1] promotion[C2] demotion[--] latency[000] usage[156480960]
   *C2:                  type[C2] promotion[--] demotion[C1] latency[001] usage[17186371]

Preco je pri C2 tak malo, ked skoro cely den na notebooku nic nerobim?

[Michal Čihař]

Tak si nastav míň, když 1000 je moc (což IMHO je pro většinu použití):

# CONFIG_HZ_100 is not set
CONFIG_HZ_250=y
# CONFIG_HZ_1000 is not set

[peter_h]

Mam 100. Ale v tomto teple je to horuce aj ked je to vypnute .
No rozhodne ten patch skusim, ci je to na nieco. Skor by ma zaujimalo ako jadro hodnoti, kedy prejst do vyssieho C-state. Uz viem s cim sa budem hrat, az nebudem mat nic ine na praci...

[God.zilla]

Red-black tree se překládá jako bílo-černý strom. Když jsem se s tím červeno-černým překladem setkal poprvé, tak mě to dost zmátlo...

[God.zilla]

Teda, má to být "černobílý"... ale stejně to je divné

[Kyosuke]

Zvláštní. A já se s tím překladem s bílou a černou setkal až dnes. A co takhle prostě „dvojbarevný strom“?

[Pinky]

Strom, možná. Ale pochybuji o tom.

[Josef Kufner]

Pampeliška?

[egg]

Na Matfyzu se to přednáší vždycky jako červeno-černé stromy. I ve státnicových otázkách se tak jmenují.