Jaderné noviny – 17. 6. 2009

Aktuální verze jádra: 2.6.30. Citáty týdne: H. Peter Anvin, Alan Cox, Linus Torvalds. Začleňovací okno 2.6.31, týden 1. Souborový systém pouze pro čtení po chybě. Návrhové vzory linuxového jádra – část druhá: Abstraktní datové typy; Spojové seznamy; RB-stromy; Radix strom.

Obsah

Aktuální verze jádra: 2.6.30

Současné stabilní jádro je stále 2.6.30. Začleňovací okno 2.6.31 je otevřené (vizte níže).

Současná aktualizace stabilního jádra 2.6 je 2.6.29.5 vydaná 15. června. 2.6.27.25 bylo vydáno 11. června. Obě mají dlouhý seznam oprav v celém jádře.

Citáty týdne: H. Peter Anvin, Alan Cox, Linus Torvalds

-- H. Peter Anvin; Vikingové nikdy nebyli dobří, co se dopředné kompatibility týče

Začleňovací okno 2.6.31, týden 1

Proces začleňování patchů do 2.6.31 začal. V době psaní tohoto článku bylo do hlavní řady přidáno 6220 neslučovacích sad změn. Některé ze zajímavějších změn viditelných pro uživatele zahrnují:

Linus začal se začleňováním patchů 10. června, což naznačuje, že začleňovací okno zůstane otevřené přibližně do 24. června. To nás staví někam přibližně do poloviny okna. Tempo začleňování pravděpodobně po zbytek začleňovacího okna zpomalí, ale bezpochyby přijde více zajímavých změn. Zůstaňte na příjmu.

Souborový systém pouze pro čtení po chybě

K chybě v úložném subsystému může dojít z mnoha různých známých i neznámých důvodů. Souborový systém se může přepnout do režimu pouze pro čtení, když narazí na chybu v úložném subsystému nebo na kódovou cestu, kterou se kód souborového systému neměl dát (tj. cesta BUG()). Přepnutí do režimu pouze pro čtení je bezpečnostní opatření, které souborový systém implementuje, aby se zabránilo dalšímu poškození způsobeného chybou, na kterou se narazilo. Souborový systém, který se přepne do režimu pouze pro čtení, může způsobit zatuhnutí služeb, které potřebují zapisovat na disk, a v některých případech může dojít k tomu, že stroj přestane reagovat. V embedded zařízeních může stav, kdy aplikace umírají, protože nemohou zapisovat, způsobit, že je zařízení nepoužitelné, z čehož je uživatel zmaten.

Chyby souborového systému mohou být buď zotavitelné nebo nezotavitelné. Z chyb způsobených špatnými odkazy na bloky v datové struktuře inode nebo blokovém ukazateli se lze zotavit kontrolou souborového systému. Na druhou stranu z chyb způsobených vadou paměti nebo chybou programátora nemusí být možné se zotavit, protože nelze spolehlivě zjistit, která data jsou správná.

Denis Karpov zaslal sadu patchů, která v takové situaci upozorní uživatelský prostor, takže by bylo možné definovat politiku a provést odpovídající akci k tomu, aby se zabránilo přepnutí souborového systému do režimu pouze pro čtení. Tato sada patchů je v současnosti omezena pouze na souborový systém FAT. Upozornění pro uživatelský prostor by umožnila souborový systém nadále používat po nalezení „opravitelné chyby“, pokud by se přijala opatření k opravě. Takovéto nápravné akce mohou předejít nutnosti dlouhotrvající kontroly souborového systému, když je zařízení připojováno při dalším bootu.

Sada patchů přidává soubor /sys/fs/fat/<svazek>/fs_fault, který je při připojení souborového systému nastaven na 0. Při chybě se hodnota změní na 1. Program v uživatelském prostoru může na tento soubor použít poll() a testovat, jestli se jeho hodnota nezměnila, což znamená, že nastala chyba. Kromě dotazování se na tento soubor je generován uevent KOBJ_CHANGE, přičemž proměnná prostředí uevents FS_UNCLEAN je nastavena na 0, nebo 1. Pravidlo pro udev tedy může spustit správný program, který se postará o škody vzniklé chybou.

Kay Sievers není přesvědčen nápadem používat ueventy pro upozorňování uživatelského prostoru, protože byly navrženy k upozorňování na zařízení a pro návrhový cíl hlášení chyb souborového systému se tedy nehodí. Chyby souborového systému se často opakují v dávkách, například chyba při čtení může vést k vypsání několika chyb při čtení do dmesg pro každý blok, který nelze číst – vygenerovat událost pro každý blok by mohlo být víc, než je udev schopen zvládnout. Některé události se mohou ztratit nebo v horším případě může udev ignorovat uevent od ostatních zařízení, pokud se objeví v okamžiku, když zároveň dochází k mnoha chybám.

Mít <svazek>/fs_fault v sysfs také není nejlepší řešení, protože sysfs si není vědomo jmenných prostor souborových systémů. Primárním úkolem sysfs je zpřístupňovat vnitřní jaderné objekty. Jmenné prostory souborových systémů jsou sada připojení souborových systémů, která jsou viditelná pouze konkrétnímu procesu, a pro ostatní být viditelná nemusí.

Proces se soukromým jmenným prostorem obsahuje kopii jmenného prostoru místo sdíleného jmenného prostoru. Když systém nastartuje, obsahuje jeden globální jmenný prostor, který je sdílen mezi všemi procesy. Připojování a odpojování ve sdíleném jmenném prostoru je viditelné všem procesům v tomto jmenném prostoru. Proces vytvoří soukromý jmenný prostor, pokud je vytvořen systémovým voláním clone() s příznakem CLONE_NEWNS (clone New NameSpace). Proces sdílející veřejný jmenný prostor může také vytvořit soukromý jmenný prostor voláním unshare() s příznakem CLONE_NEWNS. Připojování a odpojování v soukromém jmenném prostoru jsou viditelná pouze tomu procesu, který jmenný prostor vytvořil. Potomek, který je vytvořen pomocí fork(), sdílí jmenný prostor svého rodiče.

Z tohoto důvodu mohou procesy zachytit chyby souborového systému z jiného jmenného prostoru, takže nebudou vědět, se kterým zařízením pracovat. Na tento problém lze také narazit v případě, kdy proces přistupuje k vázanému připojení [bind mount], jež bylo vytvořeno v jiném jmenném prostoru (vázané připojení připojuje podstrom souborového systému do jiného adresáře). Krom toho by souborové systémy, které jsou rozloženy na více zařízení, například btrfs, nebyly se současnou strukturou pojmenovávání schopny hlásit jméno zařízení.

Kay doporučuje jako lepší alternativu /proc/self/mountinfo, protože obsahuje seznam přípojných bodů ve jmenném prostoru procesu se specifikovaným PID (self). V současnosti se /proc/self/mountinfo mění, když se změní strom přípojných bodů. Lze to rozšířit tak, aby se chyby přenášely do uživatelského prostoru do správného jmenného prostoru s použitím poll() bez ohledu na jméno zařízení. /proc/self/mountinfo může pojmout volitelná pole, která obsahují hodnoty v podobě „značka:[hodnota]“ a která lze využít ke sdělení o povaze problému. Místo používání existující infrastruktury udev by to vyžadovalo k tomu určený program, který by monitoroval /proc/self/mountinfo, identifikoval chybu analýzou argumentu a jednal podle ní.

Jan Kara dále navrhl, aby se /proc/self/mountinfo používal jako odkaz, který by identifikoval zařízení souborového systému způsobující chyby:

I přes tyto námitky všichni souhlasí, že hlášení chyb do uživatelského prostoru nesmí být omezeno na hlášení v dmesg. Uživatelský prostor by měl být upozorňován na chyby hlášené souborovým systémech, aby mohl aktivně řešit chyby a snažit se je opravovat. Souborový systém /sys/, který nezná jmenné prostory ani upozorňování pomocí ueventů, nemusí být nejlepší řešení, ale pro nedostatek lepších rozhraní vývojáři použili sysfs a ueventy. Návrh se stále diskutuje a bude trvat nějaký čas, než se vyvine, nicméně je pravděpodobné, že nějaké řešení se do jádra dostane.

Návrhové vzory linuxového jádra – část druhá

„Komplexními datovými strukturami“ máme na mysli objekty, které jsou složeny z proměnného množství jednodušších objektů, může jít o homogenní i heterogenní sbírku. Obecně jde o strukturu, do které lze objekty vkládat, z ní vyjímat a v ní hledat. Preferovaným způsobem, jak s takovýmito datovými strukturami pracovat, když je studujeme v kurzu programování pro začátečníky, je použití abstraktních datových typů.

Abstraktní datové typy

Myšlenka za abstraktními datovými typy je obalit celou implementaci datové struktury a poskytnout pouze dobře definované rozhraní, kterým lze se strukturou manipulovat. Výhodou tohoto přístupu je, že poskytuje čisté oddělení – datový typ lze implementovat bez znalosti toho, jaká aplikace by ho mohla používat, a aplikaci lze implementovat bez znalosti implementačních detailů datového typu. Obě strany jednoduše píší kód založený na rozhraní, které zde slouží jako smlouva, jež explicitně říká, co je potřeba a co lze očekávat.

Na druhou stranu jedna z cen tohoto přístupu je těsně spjata s abstraktní povahou rozhraní. Důvodem k abstrakci rozhraní je odstranění nepotřebných detailů – to je dobré pro začínající studenty, ale špatné pro programátory jádra. Při programování jádra je velmi důležitá výkonnost, je to třetí pravidlo hned po správnosti a udržovatelnosti, přičemž někdy má přednost i před udržovatelností. Ne všechny kódové cesty v jádře jsou kritické pro výkonnost, ale u mnoha z nich to tak je a vývojový proces těží z toho, že jsou stejné datové struktury používány jak v kódových cestách kritických pro výkonnost, tak v těch ostatních. Je tedy důležité, aby datové struktury nebyly abstrahovány příliš, ale aby všechny detaily jejich programování byly viditelné a programátor tak byl schopen zvolit jejich optimální využití.

Prvním principem datových struktur v jádře je tedy neskrývat detaily. Abychom viděli, jak je to zajištěno, a abychom prozkoumali další principy, které se promítají do návrhového vzoru, prozkoumáme několik úspěšných datových typů použitých v linuxovém jádře.

Spojové seznamy

Začneme od jednoduchého. První datový typ, který prozkoumáme, je obousměrný spojový seznam. Ten je implementován v jediném hlavičkovém souboru <linux/list.h>. Není žádný zvláštní soubor „.c“ s knihovnou podpůrných funkcí; veškerý kód pro práci se spojovými seznamy je dostatečně jednoduchý k tomu, aby ho šlo implementovat používáním inline funkcí. Je tedy velmi jednoduché tuto implementaci využít v jakémkoliv jiném projektu (licencovaném GPLv2).

list.h má dva aspekty, na které je dobré upozornit, protože ukazují na možné vzory. První je struct list_head, která slouží nejenom jako začátek seznamu, ale také jako kotva pro položky, které jsou na seznamu. Neil, autor originálu článku, viděl implementace spojových seznamů, které vyžadovaly, aby první a druhý prvek v jakékoliv datové struktuře ukládané v seznamu byly ukazatele „další“ a „předchozí“ a obecný kód pro procházení seznamu tak bylo možné použít pro různé datové struktury. Seznamy v linuxovém jádře tímto omezením netrpí. Struktury list_head lze zabudovat kamkoliv do datové struktury a spojit několik instancí dohromady. Obalující strukturu lze najít pomocí ukazatelů ->next a >prev použitím makra list_entry().

Tento přístup má dvě výhody. Jednou z nich je, že programátor má plnou kontrolu nad umístěním polí ve struktuře pro případ, kdy je potřeba mít důležitá pole pohromadě kvůli využívání cache. Druhá je, že struktura může být ve dvou nebo více na sobě nezávislých seznamech tak, že obsahuje několik polí struct list_head.

Vkládání jedné struktury do jiné a získání rodičovské struktury pomocí potomka využitím container_of() (což je obecná podoba list_entry()) je v linuxovém jádře poměrně běžný postup, který trochu připomíná objektově orientované programování. Kontejner je něco jako podtyp zabudované struktury.

Dalším významným aspektem list.h je mnoho maker for_each – tato makra zjednodušují procházení seznamem a prohledávání každé položky. Je jich 20 (a do toho se nepočítají další čtyři z rculist.h, které se autor rozhodl v zájmu stručnosti ignorovat).

Tím se dostáváme k nenápadnějším důvodům; občas chceme vymazat současnou („current“) položku, aniž bychom narušili procházení seznamem. To vyžaduje vytvořit kopii ukazatele „next“ předtím, než se bude pracovat s aktuálním („this“) záznamem, což dává osm bezpečných („safe“) maker. Implementace spojových seznamů ve stylu ADT by pravděpodobně poskytla pouze bezpečné verze, aby se tyto detaily skryly, jaderní vývojáři nicméně nechtějí plýtvat úložným prostorem ani snahou kvůli kroku navíc, který není v běžných případech zapotřebí.

Pak je zde fakt, že ve skutečnosti máme dva trochu odlišné typy spojových seznamů. Běžné spojové seznamy používají jako hlavičku seznamu struct list_head. Tato struktura ukazuje ukazatel na začátek a na konec. V některých případech není zapotřebí hledat konec seznamu a mít možnost omezit velikost hlavičky na polovinu je velmi užitečné. Jedním z typických použití je tabulka hashů, ve které musí všechny hashe přejít do pole. Abychom tuto potřebu splnili, máme hlist, který je podobný běžnému seznamu až na to, že jediný potřebný ukazatel je ve struktuře struct hlist_head. Zde se objevuje dalších šest maker for_each.

Kdybychom měli všechny možné kombinace pro makra dopředná/zpětná, pokračující a ne, záznam a ne, bezpečná a ne a běžný seznam a hlist, měli bychom 32 různých maker. Naprogramováno jich nicméně bylo pouze devatenáct, takže se zdá, že ne všechny kombinace byly zapotřebí. Rozhodně bychom mohli naprogramovat zbývajících jedenáct, ale protože proti kódu, který se nikdy nepoužívá, bývají námitky, nestalo se tak.

Pozorný čtenář by si mohl všimnout malé neshody mezi čísly výše. Mezi dvaceti makry je jedno, které se nehodí do vzorů výše a které zdůrazňuje tvrzení o tom, že jaderní programátoři si cení výkonnosti. Toto poslední makro for_each je __list_for_each(). Všechna ostatní makra používají funkci přednačtení „prefetch“, aby se CPU naznačilo, že má na začátku každé iterace načítat ukazatel ->next, aby byl k dispozici v cache, když začne další iterace (i když „bezpečná“ makra jej ve skutečnosti nepřednačítají, ale načítají). I když to normálně výkonnost vylepší, existují případy, kdy se tím věci zpomalí. Když procházení seznamem téměř vždy skončí velmi brzy – obvykle hned po první položce – přednačítání bude často zbytečná snaha. Pro takové případy (v současnosti všechny v kódu síťování) je k dispozici makro __list_for_each(). To nepřednačítá nic. Lidé, kteří mají velmi striktní výkonnostní cíle, tedy mohou mít lepší šanci získat výkonnost, kterou chtějí.

Na tomto příkladu datové struktury můžeme vidět dva cenné vzory, kterých je dobré se držet:

RB-stromy

Další datovou strukturou je RB-strom či červeno-černý strom. To je polovyvážený binární strom, který obecně poskytuje operace vyhledávání, vkládání a vyjímání řádu log(n). Je implementován v <linux/rbtree.h> a lib/rbtree.c. Je velmi podobný seznamům z list.h v tom, že do každé datové struktury zabudovává kotvu (struct rb_node) a strom buduje z nich.

Zajímavou vlastností RB-stromu je, že nemá žádnou funkci pro vyhledávání. Prohledávání RB-stromu je opravdu velmi jednoduchá operace a lze ji implementovat na několika řádcích, jak je to ukázáno v příkladech na začátku rbtree.h. Určitě by bylo možné prohledávací funkcí napsat, ale vývojář se rozhodl to neudělat; hlavním důvodem, což nepřekvapí, je výkonnost. Aby bylo možné napsat prohledávací funkci, je nutné této prohledávací funkci předat funkci pro porovnávání („compare“). To se v C zajistí předáním ukazatele na funkci. Vzhledem k tomu, že porovnávací funkce často bývají velmi jednoduché, cena za následování ukazatele na funkci a volání funkce by často překročila cenu samotného porovnávání. Ukazuje se, že když je celá operace prohledávání zabudována do jedné funkce, kód je mnohem efektivnější. Stejné výkonnosti by možná šlo dosáhnout použitím maker nebo inline funkcí, ale vzhledem k tomu, že prohledávací funkce sama o sobě je velmi krátká, těžko by to mělo smysl.

Také si všimněte, že RB-strom úplně neposkytuje ani funkci pro vkládání. Místo toho vývojář musí napsat hledání; když hledání selže, nový uzel musí být vložen do bodu, kde se ukázalo, že chybí, a strom je potřeba znovu vyvážit. Pro toto konečné vložení a znovuvyvážení jsou funkce, protože se jedná o dostatečně složité operace, aby si vlastní funkci zasloužily.

Tím, že vývojář nese zodpovědnost za vyhledávání a část vkládání, knihovna RB-stromů poskytuje značnou svobodu. Vzor „hledej záznam, ale pokud není, tak ho vlož“ je poměrně běžný. Detaily toho, co se děje mezi fázemi „hledání“ a „vkládání“, však nejsou vždy stejné, a tak je nelze snadno vložit do knihovny. Tím, že jsou poskytnuty základní nástroje a detaily jsou řešeny podle specifické situace, jsou uživatelé RB-stromů osvobozeni, nemusí bojovat s knihovnou, která nedělá tak úplně přesně to, co by potřebovali.

Tento příklad RB-stromů posiluje vzor „zabudované kotvy“ a naznačuje vzor, že poskytnout nástroje je občas mnohem užitečnější než poskytnout hotové řešení. V tomto případě jsou poskytnuty základní datové struktury a nástroje potřebné pro vkládání, odstraňování a znovuvyvažování, ale kompletní řešení je šité na míru.

Tento vzor také popisuje jaderný přístup k hash tabulkám. To jsou velmi běžné datové struktury, ale neexistuje nic, co by alespoň trochu připomínalo definitivní implementaci. Místo toho jsou k dispozici základní stavební bloky hlist a pole společně s obecnými funkcemi pro výpočet hashe (<linux/hash.h>). Jejich spojení k tomu, aby se hodily k danému účelu, je na vývojáři.

Radix strom

Poslední datovou strukturou je Radix strom. Linux má dokonce dvě implementace radix stromu. Jedna je v <linux/idr.h> a lib/idr.c, druhá v <linux/radix-tree.h> a lib/radix-tree.c. Obě poskytují mapování z čísla (unsigned long) na libovolný ukazatel (void *), přičemž radix-tree také umožňuje ke každému záznamu přiložit dvě „značky“. Pro účely tohoto článku se budeme dívat pouze je jednu implementaci (na tu, se kterou je autor lépe obeznámen) – na radix-tree.

Radix-tree se drží vzoru, který jsme viděli v list.h: Má několik rozhraní místo toho, aby se snažil nacpat spoustu různých potřeb do jednoho. list.h má 20 maker for_each; radix-tree má šest funkcí pro vyhledávání („lookup“) podle toho, jestli chceme jenom jednu položku nebo rozsah (vyhledávání skupin [gang lookups]), nebo jestli chceme použít značky [tags] k omezení vyhledávání (hledání podle značek) a jestli chceme najít místo, kde je uložen ukazatel, místo ukazatele, který je tam uložen (to je potřeba pro jemné strategie zamykání cache stránek).

Radix-tree se nicméně nedrží vzoru zabudovaných kotev, které jsme viděli u datových struktur výše, a tím je zajímavý. U seznamů a RB-stromů je úložný prostor potřebný ke správě datových struktur přesně úměrný počtu položek v této struktuře v poměru jedna ku jedné, takže ukládat kotvu v položce funguje skvěle. U radix stromu je potřeba uložit několik malých polí, z nichž každé se odkazuje na několik položek. Vkládání těchto polí do položek fungovat nemůže. To znamená, že na rozdíl od list.h a RB-stromu radix-tree občas potřebuje alokovat nějakou paměť, aby byl schopen přidat do datové strukturu nějakou položku. To má několik zajímavých důsledků.

V předchozích datových strukturách jsme nezmiňovali zamykání. Pokud je zamykání potřeba, uživatel datové struktury pravděpodobně ví o specifických potřebách, takže jsou detaily zamykání ponechány na volajícím. (Nazýváme to „zamykání volajícím“, opačný princip je „zamykání volaným“. Zamykání volajícím je běžnější a obecně je preferováno.) To je pro seznamy a RB stromy v pořádku, protože nic z toho, co dělají, není nijak konkrétně ovlivněno zamykáním.

To ale neplatí v případě, že je zapotřebí alokovat paměť. Jestliže proces potřebuje alokovat paměť, je možné, že bude potřebovat spát, zatímco subsystém správy paměti zapíše data na úložiště, aby paměť uvolnil. Jsou přitom určité zámky (jako například spinlocky), které nesmí být drženy, když proces spí. Je zde tedy možná významná interakce mezi potřebou alokovat interně paměť kódu radix-tree a potřebou držet zámky mimo kód radix-tree.

Zjevné řešení tohoto problému (poté, co je pochopen) je předalokovat maximální možné množství potřebné paměti předtím, než je zámek získán. To je v radix-tree implementováno ve funkci radix_tree_preload(). Ta spravuje pro každé CPU fond dostupných uzlů radix_tree a zajišťuje, aby byl fond plný a nebyl využit jinou operací radix-tree. Obklopení radix_tree_insert() voláními radix_tree_preload() a radix_tree_preload_end() zajistí, že radix_tree_insert() neselže kvůli nedostatku paměti (i když radix_tree_preload() by mohlo) a že se neobjeví žádné nepříjemné záležitosti ohledně zamykání.

Shrnutí

Nyní můžeme shrnout seznam návrhových vzorů, o kterých jsme zjistili, že u datových struktur (i jinde) v jádře fungují dobře.

Příští týden dokončíme náš průzkum jaderných návrhových vzorů tím, že se podíváme na vyšší úroveň a podíváme se na některé vzory spojené s návrhem celých subsystémů.

Cvičení

Pro ty, kteří by rádi tyto myšlenky prozkoumali hlouběji, zde jsou nějaké body, odkud začít.

Diskuse k tomuto článku

Tie navrhove vzory su zaujimave; skoda ze nabuduce uz ma byt posledna cast. :-)

Nejak nerozumiem tomu konceptu "kotvy"; nemate niekto nejaky link kde je opisany?

17.7.2009 11:30 frr | skóre: 34
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Představte si, že máte struct, který obsahuje několik proměnných (memberů) různých typů - například další vnořené structy.

No a dostanete se ve zdrojáku do situace, kdy máte pointer na ten vnořený struct, a potřebujete zjistit pointer na ten větší struct, který ho obaluje. Vlastně jde o to, zjistit ofset vnořeného structu v tom obalovém structu (operace na úrovni statických typů, čili ta informace je k dispozici už při kompilaci) a odečíst ho od známého pointeru na vnořený struct.

Všiml jsem si, že to kernel umí řešit nějakými makry - patrně zmiňovaným container_of().

Omlouvám se, pokud tohle všechno je jasné :-) Dál to z hlavy dopodrobna neznám. Čili nevím přesně, jak "kotva" funguje.

Tuším že jsem to viděl v klasické kernelové knihovničce pro vytváření "spojových seznamů", kde "struct list_head" je vnořený do Vašeho uživatelského structu. No a při procházení seznamem pracujete s pointery na ten vnořený list_head, ale cílem je, dostat pointer na ten Váš uživatelský struct.

[:wq]

17.7.2009 13:26 cronin | skóre: 49
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Vdaka, uz tomu zacinam rozumiet. Pre rigidneho Javistu ako ja to vo vseobecnosti vyzera ako porusenie zapuzdrenia; na druhej strane je zjavne, ze na urcite typy pouzitia je to ucinny pristup.

Může mi někdo vysvětlit, co je to ta kotva? V životě jsem o žádné neslyše.

17.7.2009 12:39 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

No, pokud tomu dobře rozumím (Luk o tom ve svojí knížce o jádře mluví taky), je to asi takhle:

Obvyklá implementace spojového seznamu staví na struktuře, řekněme, ListNode, která vypadá zhruba takhle (pseudokód!):

class ListNode<T> {
  ListNode<T> next;
  T data;
}

Šikulové od jádra to převrátili vzhůru nohama a vymysleli asi tohle:

class ListNode {
  ListNode next;
}

class MyData {
  ...
  ListNode node;
}

Implementace seznamu pracuje s ListNode, ale navenek umí poskytnout přímo objekty dat. Představuju si to asi takhle nějak:

void forEach(ListNode head, {T -> void} callback) {
  ListNode curr = head;
  while (curr != null) {
    callback.invoke(CONTAINER_OF(curr)); // !!!
    curr = curr.next;
  }
}

MyData a = new MyData(...); a.node = new ListNode();
MyData b = new MyData(...); b.node = new ListNode(); b.node.next = a.node;

forEach(a) { MyData data -> ... }

Pochopitelně tohle je extrémně zjednodušené, ale myslím, že princip je správný. Pokud se pletu, někdo mne prosím opravte :-)

Ještě na tom nejsem tak špatně, abych četl Viewegha.

17.7.2009 13:45 alblaho | skóre: 17 | blog: alblog
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Hm, zajímavé. Asi si stáhnu zdrojáky a podívám se, jak je implementováno CONTAINER_OF, protože bych očekával, že ListNode by musel být vždy první field datové struktury (starý trik, používá mj. CSim). Jenže pak by struktura nemohla být ve více seznamech.

17.7.2009 14:35 alblaho | skóre: 17 | blog: alblog
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Dětská slavnost:

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

17.7.2009 18:08 danfis | skóre: 4
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Šikulové od jádra to převrátili vzhůru nohama a vymysleli asi tohle: ...

To je proto, aby se mohlo vice techto vzoru pouzivat v jedne strukture (napriklad aby mohla byt struktura ve vice seznamech). Implementace dedicnosti (od jednoho predka) by mohla jednoduse vypadat nejak takhle:

struct parent { ... };
struct s {
    struct parent; // prvni prvek ve strukture
    ...
};

Na strukturu s pak muzes pouzivat vsechny funkce (samozrejme s pretypovanim - coz ale za tebe muze delat nejake makro), ktere lze pouzit na strukturu parent bez pouziti maker typu container_of() nebo offset().

17.7.2009 18:15 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

To převrátili vzhůru nohama nemělo znít nijak pejorativně, je to výborný nápad (pro jaderné účely). Stejně tak jedna z implementací wait-free hashovací tabulky je vlastně postavená na hlavu (nejde o indexované seznamy, ale indexy do seznamu) :-)

Ještě na tom nejsem tak špatně, abych četl Viewegha.

18.7.2009 16:28 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Teď koukám, že kecám, ta hashovací tabulka, kterou jsem zmiňoval, je jenom lock-free. Ale stejně je to pěkný nápad :-)

Ještě na tom nejsem tak špatně, abych četl Viewegha.

17.7.2009 20:22 kralyk z abclinuxu | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Jaderné noviny – 17. 6. 2009

Na strukturu s pak muzes pouzivat vsechny funkce (samozrejme s pretypovanim - coz ale za tebe muze delat nejake makro), ktere lze pouzit na strukturu parent

Tyvado tak to je fikaný, by mě nenapadlo, ale to skutečně tak je. Akorát musí člověk pamatovat, že je potřeba alokovat/uvolnit víc paměti pro potomka, aby to nezatejkalo...

What Big Oil knew about climate change

Jaderné noviny – 17. 6. 2009

Obsah

Aktuální verze jádra: 2.6.30

Citáty týdne: H. Peter Anvin, Alan Cox, Linus Torvalds

Začleňovací okno 2.6.31, týden 1

Souborový systém pouze pro čtení po chybě

Návrhové vzory linuxového jádra – část druhá

Abstraktní datové typy

Spojové seznamy

RB-stromy

Radix strom

Shrnutí

Cvičení

Související články

Odkazy a zdroje

Další články z této rubriky

Diskuse k tomuto článku