Jaderné noviny - 5. 12. 2007

31. 12. 2007 | Robert Krátký

Články - Jaderné noviny - 5. 12. 2007  

Aktuální verze jádra: 2.6.24-rc4. Citáty týdne: James Morris, Alan Cox. SEEK_HOLE nebo FIEMAP? Návrat síťových kanálů.

Obsah

• Aktuální verze jádra: 2.6.24-rc4
• Citáty týdne: James Morris, Alan Cox
• SEEK_HOLE nebo FIEMAP?
• Návrat síťových kanálů

Aktuální verze jádra: 2.6.24-rc4

Aktuální předverze je (k 5. 12. 2007) 2.6.24-rc4, vydaná 3. prosince. Linus Torvalds k tomu řekl, že velikost patche je trochu skličující - začleněno totiž bylo docela dost změn. Jsou to skoro všechno opravy, ale přibylo i počítání využití procesoru skupinami procesů. Vizte krátký changelog nebo podrobnosti v dlouhém.

Od vydání -rc4 se do hlavního repozitáře dostalo téměř 100 dalších patchů.

Aktuální verze -mm stromu je 2.6.24-rc4-mm1. Mezi nedávné změny patří poslední verze API timerfd, nový paměťový řadič a reimplementovaný ovladač ramdisku.

Citáty týdne: James Morris, Alan Cox

Člověk by musel čekat s otevřenou pusou hodně dlouho, než by mu do ní přiletěl pečený holub.

-- James Morris

Chceš-li zjistit, co je potřeba, můžeš si představit jednoduchý uživatelský příklad - třeba systém, který tě ochrání před díly Erica S. Raymonda. Nahraď matematickou analýzu a heuristiku nástrojem pro uživatelské prostředí, který vyhledá různé texty od ESR, a pak to navrhni pro něj, jestli ti to udělá radost.

SELinux asi zvládne všechnu tu špinavou práci sám, protože umí označit soubor jako eric_t a omezit k němu další přístup.

-- Alan Cox

SEEK_HOLE nebo FIEMAP?

Rozptýlené soubory vypadají, že jsou větší než objem úložného prostoru, který je pro ně ve skutečnosti alokován. Běžný způsob vytvoření takových souborů je přesunout interní ukazatel pozice v souboru za jeho konec a pak tam zapsat nějaká data; unixové systémy tradičně nealokují diskové bloky pro část souboru za původním koncem, který byl přeskočen. Výsledkem je "díra", neboli kus souboru, který logicky existuje, ale není nijak reprezentován na disku. Operace čtení na takové díře uspěje, ale vrácená data budou nuly. Průměrně chytré komprimační a archivační utility díry v souborech rozpoznají; tyto díry nejsou ve výsledných archívech uloženy a při obnovení souboru z archívu nebudou zaplněny.

Postup rozpoznávání děr je poměrně primitivní: v podstatě jediný způsob, jak to udělat přenositelně, je hledat bloky zaplněné nulami. Ta technika sice funguje, ale vyžaduje procházení dat, aby se získaly informace, které už nižší úrovně systému znají. Zdá se, že by měl existovat šikovnější způsob.

Přibližně před dvěma lety navrhli vývojáři Solarisu a ZFS rozšíření lseek(), které by aplikacím umožnilo hledat díry v rozptýlených souborech efektivněji. Toto rozšíření přidává dvě nové možnosti "odkud":

• SEEK_HOLE umísťuje popisovač souboru na začátek první díry, která se nachází za daným offsetem. Pro účely této operace je "díra" definována jako oblast samých nul libovolné délky, ale od systému se nevyžaduje, aby všechny díry detekoval. Takže v praxi budou krátké rozsahy nul přeskočeny, stejně jako (s největší pravděpodobností) velké (víceblokové) rozsahy, které už byly zapsány na disk.


• SEEK_DATA posouvá na začátek další oblasti (po daném offsetu), která není díra.

Tato funkčnost už je nějakou chvíli součástí Solarisu; vývojáři Solarisu by však chtěli, aby se rozšířila i jinde a stalo se z ní něco více než jen rozšíření Solarisu. Josef Bacík proto nedávno navrhl implementaci tohoto rozšíření pro Linux. Z interního hlediska přidává nového člena do struktury file_operations (seek_hole_data()), který by měl souborovým systémům umožnit novou operaci efektivně implementovat.

Dalo by se namítnout, že pokud někdo chce oddělit v souboru díry od dat, může to už udělat pomocí ioctl() příkazu FIBMAP. To je sice pravda, ale FIBMAP není efektivní způsob, jak získávat tento druh informací - zvláště ne na souborových systémech, které podporují extenty. Volání FIBMAP vrátí mapovací informace o jediném bloku; mapování velkého souboru by si mohlo vyžádat miliony volání, a přitom už by souborový systém měl (opět) vědět, jak takové informace poskytnout mnohem přímočařejším způsobem.

Přesto to však vypadá, že se tento patch do jádra nedostane. API není moc oblíbené, protože je považováno za ošklivé, a navíc mění sémantiku volání lseek(). Ale především by mohlo být zajímavé se dozvědět o reprezentaci souboru více než jen to, kde jsou díry. A ukazuje se, že už byl navržen ioctl() příkaz, který umí všechny tyto informace poskytnout. Jde o rozhraní FIEMAP, které v říjnu specifikoval Andreas Dilger.

Volání FIEMAP bere jako parametr následující strukturu:

    struct fiemap {
	__u64	fm_start;	 /* logický offset počátečního bajtu */
	__u64	fm_length;	 /* logická délka mapy (dovnitř/ven) */
	__u32	fm_flags;	 /* FIEMAP_FLAG_* příznaky pro žádost (dovnitř/ven) */
	__u32	fm_extent_count; /* počet extentů v fm_extents (dovnitř/ven) */
	__u64	fm_end_offset;	 /* konec mapování v posl. ioctl */
	struct fiemap_extent	fm_extents[0];
    };

Aplikace, která se chce něco dozvědět o tom, jak je soubor uložen, nastaví počáteční offset v fm_start a délku oblasti, o kterou se jedná, v fm_length. Obsahuje-li fm_flags FIEMAP_FLAG_NUM_EXTENTS, systémové volání prostě nastaví fm_extent_count na počet extentů použitých na uložení specifikovaného rozsahu bajtů a ukončí se. V této podobě může být FIEMAP použit k určení, jak moc je soubor na disku fragmentovaný.

Pokud chce aplikace více informací, alokuje se dost místa pro ještě jednu strukturu fm_extents:

    struct fiemap_extent {
    	__u64 fe_offset;   /* offset počátku extentu v bajtech */
    	__u64 fe_length;   /* délka extentu v bajtech */
    	__u32 fe_flags;    /* vrácené příznaky FIEMAP_EXTENT_* extentu */
    	__u32 fe_lun;      /* logické číslo zařízení extentu (začínající 0)*/
    };

V tomto případě by fm_extent_count mělo být nastaveno na počet těchto struktur, než bude zavoláno FIEMAP. Po ukončení budou tyto struktury (tolik, kolik udává vrácená hodnota fm_extent_count) vyplněny informacemi o vlastních extentech souboru; fe_offset říká, kde (na disku) extent začíná, a fe_length je velikost extentu. V poli fe_flags se může objevit hned několik hodnot:

• FIEMAP_EXTENT_HOLE říká, že v této oblasti souboru nejsou žádná data - je to díra.


• FIEMAP_EXTENT_UNWRITTEN říká, že místo bylo alokováno na disku, ale nic do něj nebylo zapsáno. Takto označeno bude místo, které bylo prealokováno pomocí fallocate().


• FIEMAP_EXTENT_UNMAPPED naopak označuje extent, kam nějaká aplikace zapsala data, ale nebylo pro něj alokováno žádné místo na disku.


• FIEMAP_EXTENT_DELALLOC značí, že je prováděna opožděná alokace; tento příznak automaticky znamená i FIEMAP_EXTENT_UNMAPPED.


• FIEMAP_EXTENT_SECONDARY dává najevo, že data pro tento segment jsou umístěna někde jinde; s tímto příznakem se setkáte na souborových systémech spravovaných nějakým hierarchickým způsobem. Tento příznak také předznamenává FIEMAP_EXTENT_UNMAPPED.


• FIEMAP_EXTENT_NO_DIRECT říká, že k datům nelze přistupovat přímo - nejprve je nutné je zpracovat (například dekomprimace nebo rozšifrování).


• FIEMAP_EXTENT_LAST značí konečný extent souboru.


• FIEMAP_EXTENT_EOF říká, že požadovaný rozsah jde až za konec souboru.


• FIEMAP_EXTENT_ERROR značí extent, u kterého došlo k nějaké chybě; pole fe_offset bude v tomto případě obsahovat číslo chyby.


• FIEMAP_EXTENT_UNKNOWN říká, že data existují, ale neví se kde. Tento příznak by asi popisoval většinu prostoru s mými osobními soubory, i když není jasné, jak by se to jádro domáklo.

Jak je vidět, toto nové volání poskytuje opravdu bohaté informace, včetně údajů o tom, jak je soubor na disku rozdělen, alokačních strategiích, a dokonce i rozhodnutích hierarchických ukládacích enginů. Implementace už existuje pro souborový systém ext4. Kód zatím nebyl navržen k začlenění do hlavního jádra, ale bylo by překvapivé, kdyby k tomu co nevidět nedošlo. Až to přijde, bude moci knihovna C implementovat SEEK_HOLE a SEEK_DATA v uživatelském prostoru, pokud o to bude zájem.

Návrat síťových kanálů

Koncept síťových kanálů poprvé přednesl Van Jacobson téměř před dvěma lety na konferenci linux.conf.au 2006. Tato myšlenka slibuje zlepšení výkonu síťování přesunutím zpracovávání síťových dat co nejblíže koncovému bodu - nejlépe až do uživatelského prostoru. Kanálová schémata chtějí jádro vyšoupnout ze zpracovávání paketů a udržet to na jediném místě (na stejném procesoru). Díky tomu by se měly minimalizovat nepodařené pokusy o využití keše [cache misses], přepínání kontextů a další aktivity, které zhoršují výkon. Kanály však v reálném světě tvrdě narazily; když se začnou brát v potaz potřeby jako filtrování paketů, překlady adres a tak podobně, začne být těžké zachovat jednoduchost, na které výkon kanálů závisí. Takže o dva roky později stále neexistuje implementace kanálů, která by měla aspoň šanci na začlenění do hlavního jádra.

To však neznamená, že by se v té oblasti nic nedělo. Evgenij Poljakov [Evgeniy Polyakov], hacker, který se nikdy nenechá odradit (vizte rozhraní kevent), dále vyvíjí patche se svou implementací kanálů; 22. verze vyšla 4. prosince.

Tato verze patche má dobře definovanou interní strukturu, která jadernému kódu umožňuje se na kanály napojit [hook]. Nejlépe vyvinutý režim je však ten, který pouze přenáší pakety z a do uživatelského prostředí. K tomu účelu přibylo nové systémové volání:

    int netchannel_control(struct unetchannel_control *ctl);

Kompletní obsah struktury unetchannel_control najdete v patchi. Ta důležitější pole jsou:

• cmd popisuje akci, kterou si volající kód přeje spustit. Na rozdíl od předchozích verzí patche je teď podporována jen jedna akce: NETCHANNEL_CREATE, která vytváří nový kanál.


• type je typ kanálu, který se má vytvořit. V současné době je implementován pouze typ NETCHANNEL_COPY_USER, který kopíruje pakety z a do uživatelského prostoru.


• unc.data popisuje kanál, který má být vytvořen: obsahuje zdrojové a cílové adresy a porty a číslo protokolu.

Jakmile je kanál vytvořen, přidá se do vyhledávacího stromu, který je orientován na bleskově rychlé hledání. V kódu pro příjem paketů je nový háček [hook], který v tom stromu vyhledává každý příchozí paket; pakety, které tam nejsou nalezeny, jsou normálně zpracovány jaderným síťovým stackem. Ale všechny pakety, jejichž adresy, porty a protokol jsou ve stromu objeveny, jsou odkloněny na kód kanálů, ještě než se vůbec dostanou do fronty síťového stacku.

Posledním kouskem (na přijímací straně) je jednoduchá implementace read(). Proces, který si přeje přijmout paket ze síťového kanálu, musí pouze přečíst příslušný popisovač souboru a další dostupný paket bude nakopírován do poskytnutého bufferu. Bylo by samozřejmě fajn se zbavit toho kopírování, ale to není vůbec lehké: paket musí být přijat, dříve než je znám jeho cíl. Existují síťové adaptéry, které umějí směrovat pakety podle informací v jejich hlavičce, ale stávající netfilter nemá potřebná vylepšení API pro ovladače, aby mohl tuto možnost využít pro provoz bez kopírování.

Podobné je to s operací write(), která způsobí, že bude příslušný paket nakopírován do jádra a nacpán na poměrně nízké úrovni do síťového stacku. Ani v případě zápisu to zatím nejde bez kopírování.

Evgenij však nad postupem, který by nevyužíval kopírování, zjevně přemýšlí. Pravděpodobně by použil síťový alokátor. I bez toho to však vypadá, že jsou kanály velmi rychlé, když se použijí s jeho síťovým stackem pro uživatelský prostor. Některé představené výsledky benchmarků ukazují výrazné zlepšení oproti běžnému linuxovému síťovému stacku - třikrát více než šířka pásma při použití třetiny výkonu procesoru, když jsou přenášeny malé pakety. U větších paketů (4096 bajtů) výkonnostní zlepšení v podstatě mizí - hlavní příčinou je nejspíše režie způsobená kopírováním paketů z a do jádra.

Zlepšení výkonu u malých paketů je vítané: existuje hodně aplikací, včetně profesionálního finančnictví, které vyžadují velká množství malých přenosů. Přidání podpory provozu bez kopírování by mohlo zlepšit i výkon u velkých paketů. Hlavní zkouška však bude přidání všech funkcí, které současní uživatelé od síťování očekávají - většina zatím v implementaci kanálů chybí. V kódu už jsou háčky určené pro přidání zpracovávání jednotlivých paketů; mohly by být použity pro filtrování, překlady adres, kontrolu provozu nebo kteroukoliv jinou požadovanou funkci. Zbývá zjistit, jestli bude možné tyto háčky využít, aniž by se přišlo o výkonnostní náskok kanálů. Ale Evgenij se asi nevzdá, dokud na to nebude mít odpověď.

Diskuse k tomuto článku

[Jan Kundrát (jkt)]

"vyhledat místo za koncem souboru a pak tam zapsat nějaká data" je dosti nestastne, snad spis "presunout interni ukazatel pozice v souboru za jeho konec a pak tam zapsat nejaka data"

[salam]

Kdo nerozuměl tomu prvnímu, ten neporozumí ani tomu druhému

[blah]

to prvni sem nepochopil to druhe jo. to prvni totiz nedava moc smysl

[YYY]

Me se zdaji oboje alternativy celkem stejne srozumitelne :)

[Robert Krátký]

Díky, tak je to lepší.

[filbar]

Nevíte někdo, co je to ten extent? Nějak se mi to nepodařilo pochopit

[Jirka P]

IMHO na filesystémech, co je podporují, jde o něco jako blok, akorát proměnné velikosti. Tzn. kus souboru, který je na disku fyzicky souvislý a na který stačí filesystému jeden záznam. V kontextu toho FIEMAP ale dost možná půjde jen o kus souboru který je na disku souvislý, tzn. n bloků na ext3, které jsou na disku za sebou = jeden extent.

[zde]

Test jestli 4k blok obsahuje samé nuly není přece žádná věda. Když se implementuje efektivně (prefetch, SSE), bude to IMHO zhruba stejně rychlé jako volání té kernelové zbytečnosti :(

[Dan]

Ale volani te kernelove "zbytecnosti" ma slozitost O(1) (zejmena na FS zalozenem na extentech) kdezto seek k dire/datum s hledanim nul ma slozitost O(n).

[zde]

Každé volání kernelu má především velkou fixní režii. Než se přehodí kontexty, načtou registry z userspacu, a provedou ty šílené demultiplexory podle čísla syscallu a podle čísla IOCTL, tak by mohl čistě userspace kód mít blok už dávno schroustaný.

To že jde o O(N) vs O(1) je sice pravda, ale jediné rozumné využití má hledání děr při backupu souborů, čili jako součást O(N) operace, a O(1) + O(N) = O(N). Místo těchto blbostí a nesmyslného bobtnání kernelového API by měli řešit zásadnější věci- třeba konečně zprovoznit suspend, nebo aby wifiny běhaly hned, bez patchování a ndiswrapperu.

[Mordae]

Sorry, ale ja jen kvuli tomuhle ted na Debian nainstaloval vyvojove jadro, protoze me napadla docela pekna aplikace. Co se tyce toho cteni a porovnavani s nulami, obcas je rozdil mezi tim, jestli je to dira, nebo blok nul. Treba kdyz vedome delas copy-on-write nad velkym souborem pomoci sparse-filu. A ano, vim, ze pouzit vlastni vyhledavaci strom asociovany s tim sparse-filem pro oznaceni pouzitych bloku zni taky funkcne, na co ale implementovat neco, co uz jadro beztak dela?

Navic si uvedom, ze jadru staci prozkoumat meta-data a vi, jestli je blok dira nebo ne. Tak jak to navrhujes ty, bych musel cely ten soubor precist, coz je naprosto silene, pokud se bavime o souborech, ktere mohou mit stovky az tisice gigabytu, ale jen nekolik megabytu z toho neni dira.

Takze tak, pekny den.