Byla vydána nová verze 24.04.28 s kódovým názvem Time After Time svobodného multiplatformního video editoru Shotcut (Wikipedie) a nová verze 7.24.0 souvisejícího frameworku MLT Multimedia Framework. Nejnovější Shotcut je vedle zdrojových kódů k dispozici také ve formátech AppImage, Flatpak a Snap.
Byla vydána verze 5.30 dnes již open source operačního systému RISC OS (Wikipedie).
V aktuálním příspěvku na blogu počítačové hry Factorio (Wikipedie) se vývojář s přezývkou raiguard rozepsal o podpoře Linuxu. Rozebírá problémy a výzvy jako přechod linuxových distribucí z X11 na Wayland, dekorace oken na straně klienta a GNOME, změna velikosti okna ve správci oken Sway, …
Rakudo (Wikipedie), tj. překladač programovacího jazyka Raku (Wikipedie), byl vydán ve verzi #171 (2024.04). Programovací jazyk Raku byl dříve znám pod názvem Perl 6.
Společnost Epic Games vydala verzi 5.4 svého proprietárního multiplatformního herního enginu Unreal Engine (Wikipedie). Podrobný přehled novinek v poznámkách k vydání.
Byl vydán Nextcloud Hub 8. Představení novinek tohoto open source cloudového řešení také na YouTube. Vypíchnout lze Nextcloud AI Assistant 2.0.
Vyšlo Pharo 12.0, programovací jazyk a vývojové prostředí s řadou pokročilých vlastností. Krom tradiční nadílky oprav přináší nový systém správy ladících bodů, nový způsob definice tříd, prostor pro objekty, které nemusí procházet GC a mnoho dalšího.
Microsoft zveřejnil na GitHubu zdrojové kódy MS-DOSu 4.0 pod licencí MIT. Ve stejném repozitáři se nacházejí i před lety zveřejněné zdrojové k kódy MS-DOSu 1.25 a 2.0.
Canonical vydal (email, blog, YouTube) Ubuntu 24.04 LTS Noble Numbat. Přehled novinek v poznámkách k vydání a také příspěvcích na blogu: novinky v desktopu a novinky v bezpečnosti. Vydány byly také oficiální deriváty Edubuntu, Kubuntu, Lubuntu, Ubuntu Budgie, Ubuntu Cinnamon, Ubuntu Kylin, Ubuntu MATE, Ubuntu Studio, Ubuntu Unity a Xubuntu. Jedná se o 10. LTS verzi.
Na YouTube je k dispozici videozáznam z včerejšího Czech Open Source Policy Forum 2024.
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.
-- H. Peter Anvin; Vikingové nikdy nebyli dobří, co se dopředné kompatibility týče
-- Alan Cox
-- Linus Torvalds nakreslil čáru do písku.
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í:
Čtení z /dev/zero nyní může být přerušeno signály. Teoreticky by touto změnou neměla být postižena žádná aplikace, ale i tak se skutečně jedná o změnu ABI pro uživatelský prostor.
Architektura x86 může nyní používat 46bitové fyzické adresy, což umožňuje využít až 64 TB fyzické paměti.
Mnoho vlastností Xenu, které jsou míněny jako podpora funkce Dom0 (například kód kanálu událostí /dev/xen/evtchn a /sys/hypervisor), bylo začleněny. Samotný kód Dom0 nicméně zůstává mimo.
Byla přidána podpora pro systémové volání rt_tgsigqueueinfo(), které vysílá signál (s pomocnými informacemi) skupině vláken.
Bylo přidáno mnoho vlastností ftrace. Mezi ně patří profiler funkcí, mnoho zlepšení sledovače událostí, nějaké nové sledovací body a nový docbook dokument popisující statické sledovací body v jádře.
Ovladač USB TTY portu byl přepracován způsobem, který ho přibližuje k POSIXovému chování a chování ostatních typů sériových portů. Alan Cox má obavy, že některé z aplikací, které závisí na starém chování, se mohou rozbít – i když jiné, které měly problémy s USB sériovými porty, by nyní měly začít fungovat.
Nový ladící prvek pro sysctl (/proc/sys/kernel/modules_disabled); zápis „1“ do tohoto souboru trvale zakáže nahrávání modulů.
Bezpečnostní modul SMACK má nyní nástroje pro podrobné logování.
Systémové volání splice() nyní funguje, i když jsou jak vstupní, tak výstupní soubor roury.
Patche topologie úložných zařízení (stručně zmíněné v dubnu) byly začleněny. Tento kód jádru umožňuje exportovat mnohem více informací o tom, jak jsou úložná zařízení strukturována, což umožňuje podporu nadcházejícího hardwaru.
Sada patchů čítačů výkonnosti (naposledy popisovaná v prosinci) byla začleněna. Tento kód poskytuje nové API pro využívání hardwarových čítačů výkonnosti; vytlačuje perfmon a mnoho dalších implementací v této oblasti.
Sada patchů pro znaková zařízení v uživatelském prostoru (CUSE) byla začleněna.
Z architektury ARM byla odstraněna arch-imx, protože byla nahrazena architekturou MXC.
Architektura s390 přidává podporu pro dynamické ftrace, stejně jako pro sledovače systémových volání a grafů funkcí.
Byly začleněny změny packet_mmap na vysílací straně paketových socketů, které umožňují efektivnější odesílání paketů z uživatelského prostoru téměř bez kopírování.
Subsystém controller area network (CAN) přidal rozhraní pro ovladač síťového zařízení a rozhraní netlink. Byly také začleněny nové ovladače pro zařízení CAN, které toto rozhraní ovladačů používají (vizte níže).
Do síťového subsystému byla přidána podpora pro sockety IEEE 802.15.4. Ty slouží pro levné pomalé „osobní sítě“ (personal area network).
Do kódu netfilteru bylo přidáno pasivní snímání otisků OS [Passive OS fingerprinting].
Souborový systém FAT získal připojovací volbu „error“, která řídí jeho chování při kritických chybách.
Architektura s390 získala podporu pro hibernaci
Byla přidána podpora pro hostitelské řadiče USB3.0/xHCI, žádný však ještě není k dispozici.
Bylo začleněno jaderné nastavování režimu pro ovladač radeon, který podporuje R1XX, R2XX, R3XX, R4XX, R5XX a radeon až po X1950.
Obvyklá hromada nových ovladačů:
Architektury/procesory/systémy:
Různé:
Síťování:
Zvuk:
Grafika:
Video:
Mezi změny viditelné vývojářům jádra patří:
Nová atomická funkce:
int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
Tato funkce dekrementuje cnt a získá daný zámek lock, když cnt klesne na nulu.
Bylo začleněno mnoho změn API fronty požadavků blokové vrstvy; všechny ovladače nyní musí požadavky vyjmout z fronty předtím, než je vykonají. Krom toho začlenění patchů pro topologii úložných zařízení (v rámci přípravy na disky s 4K sektory) znamená, že blokové ovladače nyní musí rozlišovat mezi velikostí fyzického bloku na disku a logickou velikostí bloku v jádře.
32bitová architektura x86 nyní podporuje typ atomic64_t.
Konečně byl začleněn jaderný detektor úniků paměti.
Byl začleněn backend fsnotify. Tento kód poskytuje novou společnou implementaci dnotify a inotify; také bude sloužit jako základna pro kód „fanotify“ (dříve TALPA), který v době psaní tohoto článku nebyl začleněn.
Btrfs se dočkal mnoha vylepšení včetně jednoho, které zahrnuje změnu formátu na disku. Existující souborové systémy btrfs budou s novým kódem fungovat, ale jakmile bude takový souborový systém připojen na systému s jádrem 2.6.31, se staršími jádry již fungovat nebude.
Stromové RCU (read-copy update) je nyní výchozí, klasické RCU je nicméně stále k dispozici.
Byly začleněny hlavičkové soubory include/asm-generic. Tyto změny mají sloužit jako model nebo být přímo využity novými architekturami místo toho, aby se kopíroval kód existující architektury. Architektura S+core (score) na těchto změnách závisí a architektura MicroBlaze je využije k tomu, aby pročistila své API.
Byla začleněna dost velká pročištění XFS, včetně přechodu na obecný kód POSIX ACL a odstranění vektoru funkcí pro operace s kvótami xfs_qmops.
Všechny síťové ovladače byly konvertovány na nové API net_device_ops a staré API dostupné s COMPAT_NET_DEV_OPS bylo odstraněno.
Jádro rfkill bylo přepsáno pro zařízení, která implementují způsob, jak vypnout veškeré rádiové přenosy od zařízení (například v reakci na klávesu laptopů, která vypíná bezdrátovou síťovou kartu). Také byly aktualizovány různé ovladače, aby toto nové API rfkill používaly.
Všechny odkazy na debugfs se změnily na /sys/kernel/debug jak v dokumentaci, tak v kódu. Krom toho byla do adresáře Documentation přidána Aktualizovaná příručka debugfs, jejíž originál vyšel na LWN.
Práce s unicode v jádře byla aktualizována, funkce jako utf_mbstowcs() byly přejmenovány na utf8s_to_utf16s() pro lepší čitelnost.
Byl začleněn kontrolor jaderné paměti kmemcheck, který detekuje používání neinicializované paměti v jádře.
Správce paměti GPU TTM (popisovaný před rokem a něco) byl začleněn.
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.
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.
„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ů.
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.
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).
To má několik důvodů. Nejjednodušší jsou ty, že:
Někdy potřebujeme seznam procházet v protisměru (následováním odkazu „prev“). Je pět maker, které prochází zpětně, a 15, které prochází dopředně.
Někdy chceme začít uprostřed seznamu a „pokračovat“ odtud dále, takže máme čtyři pokračující („continue“) makra a tři od („from“) makra, která tento počáteční bod interpretují trochu odlišně.
Někdy potřebujeme pracovat se struct list_head zabudovanou do cílové struktury, ale často ve skutečnosti chceme použít makro list_entry(), abychom získali přístup ke struktuře kolem list_head; nejsnáze ji najdeme, pokud to za nás udělá makro for_each. To poskytuje záznamové („entry“) verze makra for_each, kterých je 13 (více než polovina).
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:
Zabudovaná kotva: Dobrá cesta, jak zahrnout obecné objekty do datové struktury, je zabudovat do nich kotvu a vybudovat strukturu kolem těchto kotev. Objekt lze najít podle kotvy použitím container_of().
Široká rozhraní: Nespadněte do pasti myšlení, že „jedna velikost padne všem“. I když mít dvacet či více maker, která dělají v podstatě stejnou věc, není běžné, může to být velmi vhodný způsob, jak řešit složitost nalezení optimálního řešení. Snažit se vmáčknout všechny možnosti do jednoho úzkého rozhraní může být neefektivní a rozhodnout se neposkytnout všechny možnosti je kontraproduktivní. Dát k dispozici všechny permutace podporuje vývojáře v tom, aby pro daný úkol použili správný nástroj a nedělali kompromisy. V 2.6.30-rc4 je téměř 3000 použití list_for_each_entry(), přibližně 1000 list_for_each_entry_safe(), téměř 500 list_for_each() a méně než 1000 využití těch ostatních dohromady. Fakt, že některé způsoby se používají výjimečně, nijak nesnižuje jejich význam.
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.
Máme tedy další vzor:
Sada nástrojů: Někdy není nejlepší poskytnout kompletní řešení obecné služby, ale nabídnout sadu nástrojů, které lze použít k vytvoření uživatelských řešení.
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í.
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.
Zabudovaná kotva. Je velmi užitečná pro seznamy a lze ji zobecnit, což je k vidění, pokud prozkoumáte kobjects (cvičení pro čtenáře).
Široká rozhraní. Tento bod nám připomíná, že snaha namačkat spoustu případů využití do jednoho volání funkce není nutné – prostě poskytněte spoustu volání (s užitečnými a (snad) konzistentními jmény).
Sada nástrojů. Někde není nejlepší poskytnout kompletní řešení pro obecnou službu, ale raději sadu nástrojů, které lze použít k vytvoření uživatelského řešení.
Zamykání volajícím. Když máte pochyby, ať raději zámky získává volající než volaný. To dává klientu funkce do rukou více kontroly.
Předalokace vně zámků. To je v některých ohledech poměrně zjevné. V jádře je to ale široce využíváno, takže explicitní upozornění je na místě.
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ů.
Pro ty, kteří by rádi tyto myšlenky prozkoumali hlouběji, zde jsou nějaké body, odkud začít.
Vytvořte seznam všech datových struktur, které jsou zabudované, prozkoumáním všech využití makra container_of. Z nich udělejte seznam párů, které jsou zabudovány do stejné struktury (což modeluje vícenásobnou dědičnost). Okomentujte, jak se to odráží na celkové použitelnosti vícenásobné dědičnosti.
Napište implementaci přeskakujících seznamů [skiplist], která by byla použitelná v jádře. Zvažte aplikovatelnost všech vzorů, které byly diskutovány v tomto článku. Kredity navíc za využití seznamů list.h.
Linux obsahuje knihovnu mempool, kterou se radix-tree rozhodl nevyužít a preferovat místo ní svůj vlastní fond (v radix_tree_preload). Prozkoumejte důsledky změny radix-tree tak, aby používal mempool, a změny mempool tak, aby ji radix-tree mohl používat. Poskytněte patche, které vezmou zpět tuto návrhovou volbu radix-tree, nebo vzor, který ji vysvětlí.
Porovnejte implementace radix-tree a idr a zjistěte, jestli by jednu bylo možné implementovat použitím druhé bez obětování správnosti, udržovatelnosti a výkonnosti. Poskytněte buď vysvětlení, proč by měly zůstat oddělené, nebo patch, který nahradí jednu druhou.
Nástroje: Tisk bez diskuse
Tiskni
Sdílej:
Byla přidána podpora pro hostitelské řadiče USB3.0/xHCI, žádný však ještě není k dispozici.
Jsem rád, že je Linux připraven i když skutečných zařízení se stejně dočkáme tak nejdřív za rok.
17.7.2009 10:18
Petr Tomášek | skóre: 39
| blog: Vejšplechty
To by mě teda zajímalo, jak takovou věc testovali :=ooo
17.7.2009 08:46
Nikola Ciprich | skóre: 23
| blog: NiX_blog
| Palkovice
čipová sada AMD r60 čipová sada Intel IGDNG
asi chybi odrazka. jinak jako vzdy skvele pocteni!
asi chybi odrazkaDík, opraveno.
Nejak nerozumiem tomu konceptu "kotvy"; nemate niekto nejaky link kde je opisany?
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.
17.7.2009 10:26
alblaho | skóre: 17
| blog: alblog
AbcLinuxu.cz
ITBiz.cz
HDmag.cz
AbcPráce.cz
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
17.7.2009 13:45
alblaho | skóre: 17
| blog: alblog
17.7.2009 14:35
alblaho | skóre: 17
| blog: alblog
/**
* 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) );})
struct parent { ... };
struct s {
struct parent; // prvni prvek ve strukture
...
};
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().
Na strukturu s pak muzes pouzivat vsechny funkce (samozrejme s pretypovanim - coz ale za tebe muze delat nejake makro), ktere lze pouzit na strukturu parentTyvado 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...
To je taka ta vec ktoru maju lode a ked sa chcu urzat na mieste vypustia kotvu...
Keby si furt nieco nekopiloval a nepisal v terminale a namiesto to si dal Vistu, mal by si cas aj na vseobecne vzdelavanie :p