Jaderné noviny – 31. 7. 2014: Rychlejší vypisování adresářů

19. 8. 2014 | Luboš Doležel

Články - Jaderné noviny – 31. 7. 2014: Rychlejší vypisování adresářů  

Aktuální verze jádra: 3.16-rc7. Citáty týdne: Dave Airlie, Andrew Morton, Greg Kroah-Hartman. Dvě cesty k lepšímu readdir(): xgetdents(); dirreadahead().

Obsah

• Aktuální verze jádra: 3.16-rc7
• Citáty týdne: Dave Airlie, Andrew Morton, Greg Kroah-Hartman
• Dvě cesty k lepšímu readdir()
  • xgetdents()
  • dirreadahead()

Aktuální verze jádra: 3.16-rc7

Aktuální vývojová verze jádra je 3.16-rc7 vydaná 27. července. Linus je s tempem změn už spokojenější: Je jasné, že tam *máme* opravdové změny, ale nic z toho nevypadá děsivě. A rc7 je konečně znatelně menší než předchozí rc, takže se to zjevně uklidňuje. Navzdory mým dřívějším obavám možná půjde o poslední rc, uvidíme, jak se to vyvine příští týden.

Stabilní aktualizace: verze 3.15.7, 3.14.14, 3.10.50 a 3.4.100 vyšly 28. července. Aktualizace 3.15.8, 3.14.15, 3.10.51 a 3.4.101 se právě revidují; jejich vydání můžeme čekat 1. srpna nebo později.

Citáty týdne: Dave Airlie, Andrew Morton, Greg Kroah-Hartman

A pak zveřejníte zdrojový kód.

A hele, zrovna jste vyšel z domu. Začlenění vašeho kódu je spoooustu kilometrů před vámi a teprve jste vyrazil na cestu, právě teď, ne když jste to začali psát, ne když jste začali dělat právní prověrku, ne když jste to interně počtvrté přepsali. Udělali jste to teprve až teď.

-- Dave Airlie

Ukazuje se, že jsem lehce úplatný. Kód vypadá čistě a jednoduše a nepřítomnost komentářů je osvobozující, akorát by lidi mátly.

-- Andrew Morton

Vždycky jsem doporučoval „Najděte si něco, co vám vadí, opravte to a pokračujte dál.“ A jestliže na svém stroji nemůžete najít problém s jádrem, pak se jen málo snažíte.

-- Greg Kroah-Hartman

Dvě cesty k lepšímu readdir()

Běžné používání systému souborů probíhá obvykle následovně: projít seznam souborů v adresáři a na každém zavolat stat() pro získání informací o každém z nich. Příkaz ls -l je typickou ukázkou této zátěže, ale najde se řada dalších příkladů. Tato operace na Linuxu vždy byla pomalejší, než by se vývojářům líbilo, a hledání řešení bylo ještě pomalejší. Abhi Das nedívno navrhl dvojici možných řešení; tentokrát se to možná opravdu vyřeší – tak trochu překvapivě.

Problém s ls -l je dosti jednoduchý: pro každý zkoumaný soubor jsou potřeba dvě systémová volání. Volání getdents() (obvykle přes funkci readdir() v knihovně C) získá název souboru v adresáři; pak se zavolá stat() pro zjištění informací o souboru. Hlavně volání stat() může být náročné, každé volání nutí příslušný systém souborů uskutečnit I/O operaci pro získání požadovaných informací. V některých případech tyto údaje mohou být rozprostřené napříč vícero datovými strukturami na disku, což vyžaduje ještě více I/O, i když volající aplikace neupotřebí všechno to, co stat() vrací. Provádění veškeré této práce je neefektivní; bylo by pěkné moci omezit shromažďované informace na to, co aplikace opravdu potřebuje, a získávat tyto informace po dávkách.

Tento problém není níčím novým; pravdou je, že byl starý už když se v roce 2009 probíral na Workshopu o linuxových úložištích a systémech souborů. Navrhované řešení, které mělo podobu systémového volání xstat(), bylo zasláno v roce 2010, ale daleko se nedostalo. V současnosti se některé systémy souborů pokoušejí provádět optimalizace pro tento druh zátěže, ale v jádře stále chybí obecné řešení. Za posledních několik let ale nebyl mezi vývojáří výraznější zájem o řešení problému.

Za těchto okolností přišel Abhi se dvěma nezávislými řešeními, která předvádějí dva oddělené způsoby, jak problém řešit. Jeho cílem je získat zpětnou vazbu na oba a jakmile se ukáže, který z nich je oblíbenější, pak jej chce dostat do hlavní řady jádra.

xgetdents()

První přístup je založený na systémovém volání xstat() od Davida Howellse z roku 2010. Přidává dvě nová systémová volání:

int xstat(int dirfd, const char *filename, unsigned int flags,
          unsigned int mask, struct xstat *info);
int fxstat(int fd, unsigned int flags, unsigned int mask, struct xstat *info);

První podoba dohledá soubor podle jména, zatímco druhá vrací informace pro otevřený soubor podle popisovače. Pole flags mění fungování systémového volání; v tomto patchi se příliš nevyužívá. Zajímavější je mask, které jádru sděluje, jaké informace aplikace žádá. Dá se toho docela dost nastavit; mimo jiné XSTAT_MODE (pro práva souboru), XSTAT_UID (pro vlastníka), XSTAT_RDEV (na jakém úložišti soubor je, XSTAT_ATIME (poslední čas přístupu nebo XSTAT_INO (číslo uzlu). Pro získání všech dostupných informací lze použít XSTAT_ALL_STATS. V případě úspěchu bude struktura info naplněna vyžádanými údaji.

Navrch tohoto přidal Abhi další systémové volání:

int xgetdents(unsigned int fd, unsigned int flags, unsigned int mask,
              void *buf, unsigned int count);

fd zde představuje popisovač adresáře, který nás zajímá, a flags a mask fungují stejně jako výše (i když mask bylo rozšířeno tak, aby aplikace mohla žádat různé typy rozšířených atributů). Informace jsou vraceny v buf, což je prosté pole bajtů, a count obsahuje délku v bajtech. Volání xgetdents() se pokusí získat informace o více souborech v daném adresáři, než se buf zaplní.

Data vracená v buf jsou poněkud složitá. Struktury nejvyšší úrovně definující tyto informace jsou:

struct xdirent_blob {
	unsigned int    xb_xattr_count;
	char            xb_blob[1]; /* contains variable length data like
				     * NULL-terminated name, xattrs etc */
};

struct linux_xdirent {
	unsigned long        xd_ino;
	char                 xd_type;
	unsigned long        xd_off;
	struct xstat         xd_stat;
	unsigned long        xd_reclen;
	struct xdirent_blob  xd_blob;
};

Dokumentace vraceného formátu je poněkud kusá. Ona vlastně žádná není, takže člověk je donucen si vše domyslet ze zdrojového kódu. Vypadá to, že informace o každém souboru budou vraceny ve struktuře linux_xdirent o proměnné délce. Název souboru je první věcí uloženou v xd_blob, následují pak informace o rozšířených atributech, pokud o toto bylo požádáno. Porozumění této struktuře nějakou chvíli potrvá, stejně tak rozebrání v uživatelském prostoru, ale má tu výhodu, že všechny informace mohou být shromážděny a vráceny v jediném systémovém volání.

dirreadahead()

Alternativní přístup je poněkud jednodušší. Přidává jediné systémové volání:

int dirreadahead(unsigned int fd, loff_t *offset, unsigned int count);

Toto volání se pokusí zahájit čtení informací o souboru pro count souborů v adresáři vyjádřeném popisovačem fd, a to od pozice offset v adresáři. Hodnota offset bude aktualizována podle toho, o kolika souborech byly přečteny informace. Proto je možné použít vícero volání dirreadahead() pro procházení adresáře, zatímco jádro spravuje hodnotu offset.

V tomto případě je nadále nutné volat getdents() a stat() pro zjištění potřebných informací. Mění se to, že systém souborů už snad bude mít potřebné údaje ve vnitřní cache, takže volání by měla být obsloužena rychle. Čtění informací o více souborech umožňuje provádění v dávkách; i když jsou data rozházená po fyzickém médiu, nezbytné I/O operace je možné přeuspořádat pro optimální provedení.

Úvodní zpráva do patche o dvou částech zahrnuje výsledky benchmarků nad systémem souborů GFS2. Oba přístupy si vedly lépe nežli současná jádra při velké zátěži systémovými voláními getdents() a stat(). Možná vás to překvapí, ale dirreadahead() fungovalo mnohem lépe než xgetdents(). Tento výsledek může být důsledkem implementace xgetdents() v GFS2, ale ukazuje to, že i mnohem jednodušší přístup na bázi přednačítání může stát za zvážení.

Myšlenka s přednačítáním vedla hnedle k otázce, jestli by jádro nemohlo provádět toto přednačítání automaticky, jak se děje u obyčejného I/O. Trond Myklebust poznamenal, že klient NFS se snaží detekovat zátěž, kde by tento typ přednačítání mohl být k užitku. Obecně je ale těžké takovou detekci dělat; v jádře není mezi voláními getdents() a stat() jasné spojení. Proto by alespoň prozatím mohl toto uživatelský prostor sdělovat napřímo. Mohlo by se k tomu použít některé ze dvou rozhraní zde popsaných, ale vypadá to, že jednoduchost dirreadahead() svědčí v jeho prospěch, i když nejsou k dispozici lepší benchmarky.

Diskuse k tomuto článku

[Jardík]

int xgetdents(unsigned int fd, unsigned int flags, unsigned int mask, void *buf, unsigned int count);

fd opravdu unsigned int?? Popisovač souboru vždy signed ne? Ale co je horší, count je unsigned int? Dopr*ele to zase navrhoval nějakej super programátor, co nezná size_t. Bohužel kernel je takovejhle blbin plnej.

[Ruža Becelin]

A proc to komentujes tady a ne na LWN?

[Jardík]

LWN nevím co je, asi nějakej web, ale nechodím tam. A většinou mi chcou na webech cpát registrace, sušenky a podobný zvěrstva, takže tak. A nechte mě bejt, si musím rejpnout. A teď jdu sníst nějaký ty sušenky k čajíčku, mám jich tu už nějak moc.

[citanus]

zde se nam formuje druhy BLEK!

[Petr Tomášek]

Zapomněl jsi na Zímu a jeho maniodepresivní výlevy...

[chrono]

xgetdents je len rozšírená verzia getdents, takže sťažovať sa treba na autorov funkcie getdents. ;)

[Lukas]

Je jen skoda ze neexistuje absolutne nic co bys s tim mohl udelat krome komentare na abclinuxu.cz

[koudy]

Opravit, udělat diff, zaslat patch a pak už se pouze hřát v láskyplné komunitě kernelových vývojářů a užívat si to, že jsem udělal ze světa lepší místo?

Well nikdy to není tak jednoduché jak se zdá ;)

[fe]

No nevím, školy nemám, ale proč by měl být count (předpokládám že je to nějaký počet položek) záporný?

[Tomáš]

Čéče, když ti nikdo nechce odpovědět, tak tě zkusím mystifikovat já. Některé funkce, které vracejí normálně nezáporné číslo, při neúspěchu vrátí záporné číslo. Myslím, že to hojně dělají funkce pro práci se znaky (písmeny). Nejspíš to count() dělá podobně. Je to spíš dědictví minulosti, kdy paměť byla k....sky druhá a a procesory pomalé, takže alokace každé proměnné a její předání do funkce byla drahá operace.

[Roman Došek]

Ale ne, size_t je neznaménkový typ - to co se Jardíkovi nelíbí je fakt, že pro vracení velikostí polí/počtu položek/whatever by se měl používat size_t, protože ten podle standardu zaručuje, že zvládne tu velikost vždycky obsáhnout. Zatímco unsigned int nemá podle standardu pevnou velikost a tak se liší napříč platformami. (což může i size_t samozřejmě)

Navíc použitím size_t dáváte najevo, že to je opravdu jen počet a nic jiného než počítání se to nepoužívá.

[z]

Dáváte na najevo, že je to velikost.

[dfgfcfg]

nevim jake typy jsou dnes zvykem, ale nebylo by fajn se zbavit kokotin jako size_t nebo ***_t a mit jasnou velikost podle systemu int, long.....

[mankind_boost]

Buď rád za size_t, co teprv třeba LPCSTR na Woknech?

[mankind_boost]

A co má bejt sakra LPCTSTR?

[Conscript89]

Zni mi to madarsky.

[mmmmario]

Long Pointer to Constant STRing, long protože Win16. typedef const char* LPCSTR;

[z]

Spíš narážel na Tstring, ty Trubko

[Vladimír Čunát]

size_t je integer o velikosti pointeru, coz se z principu musi lisit podle platformy. Kupodivu se to dost hodi, treba na delky poli, a ruzne pocty omezene pameti.

[Jardík]

Nemáte tak docela pravdu pravdu, vůbec nemusí být o velikosti pointeru. Chcete-li integer ve velikosti pointeru, musíte se podívat jinam.

[Ivan]

< flame > Me se zase nelibi, ze tomu davaji prefix "x". Co budou delat, kdyz zjisti, ze to jeste neni uplne dobre? Na woknach kdyz meni syscall tak mu daji suffix "Ex", pak "Ex2", "Ex3", ... Proste pocitaji s tim, ze to nemusi byt dobre ani na podruhe, na potreti, ..< /flame >

[R]

Vo Windows API je uplny bordel. Napr. CopyFile, CopyFile2, CopyFileEx.

[aubi]

JJ s CopyFileEx jsem si uzil... Koho by napadlo, ze to ve Win32s sice bude v API, ale nenaimplementovany! Ne aby udelali return CopyFile(...); a nadbytecny parametry zahodili, misto toho udelali return 0; a ja stravil tyden badanim, proc mi program nefunguje.

[chrono]

Urobia to isté, čo pri iných systémových volaniach (a teda, bude to xgetdents2) :)

[P_V]

Suffix je milionkrát lepší. Prefix dělá brajgl v nápovědě, která je podle abecedy

[Petr Tomášek]

Oprav si kurňa chyby!

nedívno

níčím

[Bedňa]

Ak by rýchlosť výpisu bola pre niekoho kritická, tak odporúčam použiť ReiserFS. Nebenčmarkoval som to, ale to ani nieje treba, pretože je to desiatky možno stovky krát rýchlejsie než s ExtX.

[Max]

Pokud by byla pro někoho rychlost výpisu kritická, doporučuji SSD :)
Zdar Max

[Bedňa]

Maxi, ale to moje riešenie je zdarma ;)

[Max]

Ale jen napůl funkční. Osobně jsem donedávna používal reiserfs (hafo let a na jiných pc stále ještě používám), takže vím, jak rychlý je s ním výpis. Před cca 14 dny jsem přešel na SSD Crucial MX100 128GB, čistě jen na systém + naladil btrfs. Rychlost je neporovnatelná.
Zdar Max

[Bedňa]

Máš pravdu, práve tunajšie diskusie ma doviedli k tomu vyskúšať SSD a ten rozdiel je naozaj priepastný. V second job mám pár mašín na Reiseri sú tam tisíce súborov (nie systémových) a neplánujem to v najbližšej dobe migrovať, výkon je viac ako dostačujúci a prechod na SSD by bol nákladný. Čo ma tiež odrádza sú diskusie o tom ako oživiť zhebnuté SSD. Toto beriem ako najväčšie mínus SSD, pokiaľ sa bavíme o užívateľských dátach ktoré sa denno denne menia.

[Max]

Ve firemní sféře (a mělo by to tak být všude) se neřeší, jak získat data z rozbitého hdd, ale řeší se to, jak moc chce mít člověk aktuální backup a s jak velkou historií.
Z tohoto hlediska tebou vznesené obavy postrádají smysl.
Zdar Max

[pavlix]

Nevím, co je to ta firemní sféra, ale asi to nebude sféra, kam patří všechny firmy, že. Nicméně souhlasím, že by to tak mělo být.

[Bedňa]

výkon je viac ako dostačujúci a prechod na SSD by bol nákladný

Toto je tiež dúfam dostačne Enterprise argument

[Max]

Nechápu, jak by to mělo souviset s mou připomínkou? Nikoho nenutím SSD používat, sám jej všude nepoužívám. Já jen nechápu, jak může někdo argumentovat tím, že nejdou z porouchaného SSD dostat data? To je snad fuk, ne? Pokud mi na datech záleží, tak mám zálohy, pokud ne, tak je nemám. Pokud mi na datech záleží a nemám zálohy, tak jsem idiot a s použitou technologií to nemá nic společného.
Zdar Max

[Jendа]

Čo ma tiež odrádza sú diskusie o tom ako oživiť zhebnuté SSD.

Tak rotační disky taky umírají. Umírají SSD nějak výrazně častěji?

[Bedňa]

Len z placky idú tie dáta väčšinou vrátiť späť a nestojí to majland ako u SSD.

[lertimir]

Nedal bys blogisek co to znamená "naladil btrfs pro SSD". Já mám v mount option "noatime,ssd,autodefrag,space_cache,discard".

[Conscript89]

To mi s NFS nepomuze bohuzel, tam je to dost poznat, "ls --color=no" je mnohokrat rychlejsi nez "ls --color=yes". I taky to resolvovani symlinku nemusi byt nejlevnejsi.