Portál AbcLinuxu, 19. dubna 2024 14:52
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.
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)
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>
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:
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.
Č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ů:
Probuzení jádro docílí převrácením pořadí manipulace se seznamy zařízení:
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
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.
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?
# CONFIG_HZ_100 is not set CONFIG_HZ_250=y # CONFIG_HZ_1000 is not set
.
A co takhle prostě „dvojbarevný strom“? 
ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.
14.7.2006 19:03
14.7.2006 16:03