Jaderné noviny – 14. 6. 2012: Jak jádro rychle zkoumá řetězce

2. 7. 2012 | Luboš Doležel | Jaderné noviny | 3629×

Aktuální verze jádra: 3.5-rc2. Citáty týdne: Steven Rostedt, David Miller. Chris Mason opouští Oracle. Alan Cox oslavuje královnu. Rozhraní word-at-a-time: API; Jak to funguje.

Obsah

• Aktuální verze jádra: 3.5-rc2
• Citáty týdne: Steven Rostedt, David Miller
• Chris Mason opouští Oracle
• Alan Cox oslavuje královnu
• Rozhraní word-at-a-time
  • API
  • Jak to funguje

Aktuální verze jádra: 3.5-rc2

Aktuální vývojová verze jádra je 3.5-rc2, vydaná Linusem dne 8. června. Řekl bych, že -rc2 je v docela dobrém stavu, opravdu jsem se agresivně snažil revertovat věci, které způsobovaly problémy (a někdy dokonce i věci, které jsem jen podezříval). Od tohoto vydání se toulal světem a vyhrával ceny světového významu, takže přísun změn do jádra se docela zpomalil.

Stabilní aktualizace: verze 3.0.34 a 3.4.2 byly vydány 9. června; verze 3.2.20 vyšla 11. června.

Citáty týdne: Steven Rostedt, David Miller

Nejradši bych všechny ty, co na x86_64 používají jádro pro i386 s jiným účelem, než ho jen ozkoušet, naházel do velkého vroucího kotle. Opravdu mě rozčiluje, když lidé provozují i386 na strojích s 16 GB paměti a stěžují si na výkon. highmem by mělo být zakázáno na všech x86_64 systémech s více než 1G RAM a i386 jádrem s takovouhle hláškou:

"Hovado! Proč do p*dele používáš i386 na svém nablýskaném x86_64 stroji s tunami gigabajtů RAM. Nabootuj proboha do jádra pro x86_64 a využij plný potenciál. Tvůj i386 userspace na tom bude fungovat dobře. Jsi jako jeden z těch 75letých dědků, co si konečně můžou pořídit Porsche, aby s ním nakonec jeli 10 mil pod povolenou rychlostí a měli za sebou kolonu aut!"

-- Steven Rostedt

Toto je jen dalším důkazem, proč vůbec nedává smysl něco měnit ve staré vrstvě IDE. Nikoho to nezajímá a je tu 99,999% riziko, že místo posunu vpřed tam nataháš chyby.

-- David Miller

Chris Mason opouští Oracle

Vývojář Btrfs Chris Mason oznámil, že opouští Oracle a přidává se ke stále početnějšímu zástupu jaderných hackerů ve Fusion-IO. Z pohledu Btrfs se toho moc nezmění. Nadále budu Btrfs udržovat a budu je otevřeně vyvíjet. Oracle bude stále používat Btrfs ve svých produktech Oracle Linux a budu spolupracovat s distribucemi, kde se Btrfs produkčně nasazuje.

Alan Cox oslavuje královnu

Během debaty o ACPI Alan Cox prohlásil: Během volna jsem se snažil vyhýbat mejdanu anglické královny a z republikána jsem se stával rozčileným republikánem. Linusovu odpověd ale musíte vidět.

Rozhraní word-at-a-time

I když je jádro důležitou částí snad čehokoliv, co můžete chtít na počítači dělat, je to málokdy jádro samotné, kdo odvede tu zajímavou část práce. Častěji to spíš vypadá, že je jen režií, která zabírá prostředky aplikacím, jež chce uživatel používat. Proto má smysl optimalizovat jaderné operace, co nejvíc to jen jde, zejména když jsou tyto operace vykonávány často a na výkonnostně kritických místech. Rozhraní „word at a time“ (slovo po slovu), které bylo pro verzi 3.5 zoptimalizováno a zobecněno, je dobrou ukázkou toho, jak daleko mohou snahy o optimalizaci dojít.

Jádro provádí spoustu operací nad řetězci, zejména (ale ne výhradně) při práci s cestami souborů. Často je nutné znát délku názvu nebo jen cesty. Programátor v C by obvykle napsal cyklus, kde by procházel řetězcem znak po znaku. Ale když už jde o více řetězců, tak se procházení po znacích stává časově náročným. Ukazuje se, že s dostatkem bitových operací se dá většina této režie vyřešit zpracováváním dat řetězce po 32bitových nebo 64bitových slovech. API „word at a time“ takové zpracovávání umožňuje – ale za cenu složitosti.

API

Kód, který chce použít toto rozhraní, by měl includovat <asm/word-at-a-time.h>. Uvnitř je definováno několik funkcí, první z nich je has_zero():

unsigned long has_zero(unsigned long value, unsigned long *bits, 
		       const struct word_at_a_time *constants);

Na první pohled je has_zero() jednoduchá booleovská funkce, která vrátí true, pokud value obsahuje nulový bajt. Ale co jsou ty dva další parametry? Začněme hodnotou constants, která musí být prostě jen nastavena na hodnotu definovanou v hlavičkovém souboru:

const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;

Jak si popíšeme podrobně později, tato struktura obsahuje nějaké ty užitečné konstanty. Struktura je malá a její obsah je závislý na architektuře, takže zřejmě bylo považováno za zbytečné vytvářet jedinou, globálně přístupnou kopii.

Parametr bits je zase místo, kam si has_zero() může ukládat dočasná data, která budou užitečná ostatním funkcím v tomto API. Těmito funkcemi jsou:

unsigned long prep_zero_mask(unsigned long value, unsigned long bits,
			     const struct word_at_a_time *constants);
unsigned long create_zero_mask(unsigned long bits);
unsigned long find_zero(unsigned long mask);

Jakmile has_zero() našlo slovo obsahující nulový bajt, všechny tyto tři zbylé funkce musí být použity ke zjištění, který bajt obsahuje nulu. Obvyklá sekvence pak používá asi tak následovně:

    if (has_zero(value, &bits, &constants)) {
        bits = prep_zero_mask(value, bits, &constants);
    	bits = create_zero_mask(bits);
    	zero_byte = find_zero(bits);
	/* ... */

Dá se to říct tak, že prep_zero_mask() a create_zero_mask() nejprve vezmou hodnotu bits od has_zero() a pak ji upraví tak, aby find_zero() mohlo vrátit pozici prvního nulového bajtu ve slově.

To může vypadat dosti pracně, ale má to svůj důvod. Rozdělení funkčnosti umožňuje různým architekturám poskytovat optimalizované funkce pro každou část procesu. Ale je tu ještě jedna zajímavost: mezi dvěma různými hodnotami bits ze dvou volání prep_zero_mask() lze dělat logický OR. Funkce hash_name() z fs/namei.c používá tuto funkci ke hledání nulového bajtu nebo lomítka – řetězec, který je zkoumán, končí buď nulovým bajtem nebo začátkem další komponenty v cestě. Jádro tráví hodně času zpracováním cest, takže tato optimalizace má smysl.

Je tu ještě jedna věc, na kterou se musí myslet: řetězec nemusí začínat na začátku slova. Zpracování nezarovnaných řetězců všechno ještě více komplikuje; zvědavci se mohou podívat do lib/strnlen_user.c na ukázku, jak se s nimi dá dělat. Suma sumárum, používání tohoto rozhraní věci natolik komplikuje, že to za to téměř nikdy nestojí. Ve výjimečným případech, kdy je procházení znak po znaku příliš náročné, může ale procházení po slovech pomoci.

Jak to funguje

x86 verze tohoto API je k nalezení v arch/x86/include/asm/word-at-a-time.h; nelze se divit tomu, že části tohoto souboru mohou někomu připadat jako výstup ze soutěže v obfuskovaném C. Začíná se definicí konstant zmíněných výše:

struct word_at_a_time {
	const unsigned long one_bits, high_bits;
};

#define WORD_AT_A_TIME_CONSTANTS { REPEAT_BYTE(0x01), REPEAT_BYTE(0x80) }

REPEAT_BYTE() je makro (definované v <linux/kernel.h>), které naplňuje slovo kopiemi daného bajtu. Na 32bitovém stroji tedy bude one_bits inicializováno na 0x01010101 a high_bits bude 0x80808080; na 64bitových strojích to bude jen dvakrát tak dlouhé.

has_zero je pak definováno takto:

static inline unsigned long has_zero(unsigned long a, unsigned long *bits, 
    				     const struct word_at_a_time *c)
{
	unsigned long mask = ((a - c->one_bits) & ~a) & c->high_bits;
	*bits = mask;
	return mask;
}

Kód dělá to, že odečte jedničku od každého bajtu, zamaskuje všechny bity, které byly nastaveny v původní hodnotě, a pak zamaskuje vše vyjma nejvyššího bitu v každém bajtu. Pokud budeme uvažovat o každém bajtu jako o nezávislé hodnotě, tak nejvyšší bit se pak dá vnímat jako znaménkový bit. Odečtení jedničky od hodnoty způsobí, že se znaménkový bit změní z nuly na jedničku tam, kde hodnota bajtu byla už předtím nulová. Takže tato série operací způsobí, že nejvyšší bit bude nastaven ve všech bajtech, kde předtím byla nula. (Pravdou je, že bajty nejsou nezávislé, a tudíž „zapůjčení“ způsobí odlišné hodnoty za prvním nulovým bajtem, ale zajímá nás jen ten první, takže je to jedno).

Na x86 nedělá prep_zero_mask() nic, takže je odstraněno kompilátorem. To ale není pravda v případě create_zero_mask():

static inline unsigned long create_zero_mask(unsigned long bits)
{
	bits = (bits - 1) & ~bits;
	return bits >> 7;
}

Odečítání způsobí, že všechny bity až do prvního nastaveného bitu budou mít hodnotu jedna; všechny ostatní bity jsou pak zamaskovány a výsledek je posunut doprava. Pak jsou všechny bajty až do prvního nulového bajtu (v původní hodnotě) nastaveny na 0xff. Teď už jen zbývá zjistit, kolik takových bajtů je. Kód, který toto dělá, není zrovna přímočarý, je to výsledek prosby, kterou Linus zveřejnil na Google+ v březnu. Na 32bitových strojích je find_zero() takovéto:

long a = (0x0ff0001+mask) >> 23;
/* Fix the 1 for 00 case */
return a & mask;

Na 64bitových systémech to zase vypadá takto:

return mask*0x0001020304050608ul >> 56;

V obou případech je výsledkem číslo, které je bajtovým offsetem první nuly.

Toto API je relativně nové, poprvé (a jen pro x86) bylo zařazeno ve vývojovém cyklu 3.4. V 3.5 bylo zásadně přepracováno a stalo se lépe použitelným. Pro x86 a powerpc existují specifické implementace (na powerpc se pro zrychlení používá instrukce „spočítej počáteční nuly“); existuje i „obecná“ verze, která funguje správně jen na big-endianu. To ale postačuje na to, aby celá řada architektur mohla tuto schopnost využít. Výsledné úspory v řádu mikrosekund nemusejí vypadat zázračně, ale když se vezmou všechny operace s řetězci, co v jádru jsou, tak se to nasčítá a jde o významné zlepšení.

       

Komentáře

[Michal2]

Hehe prave jmeno Jardika je Steven Rostedt. No ale ma bez pochyby pravdu ten pan. Vsichni HIGHMEMaci jsou... divni. Asi jako muj kamarad, ktery si vypnul polovinu jader v procesoru s komentarem, ze za 2 roky je zapne a bude to mit jako by udelal upgrade

[Jendа]

Vsichni HIGHMEMaci jsou... divni.

A co 32bitové Core 2 Duo s 4 GiB RAM?

[Jendа]

Core 2 Duo

Ale houbičky. Jak se jmenuje takový ten notebookový 32bit od Intelu z roku 2006?

I když 4 GiB si dokážu představit i u svého Atomu - to je taky 686.

[vlastikroot]

Myslis oblibene pentium M z centrina?

[pc2005]

To bude starší ne? Já bych na 2006 viděl Core duo ("Core" bylo 32bit a "Core 2" už 64bit). Jinak >1GB mohly mít skoro všechny procesory od 386 (kromě pár jader co měly moc málo nožiček nebo byly embedded).

[pushkin]

Atom je 32-bit? V dnešní době? :-O No, o důvod víc, proč to nepoužívat...

[pavlix]

Není (alespoň ne jen 32-bit), stačí použít wikipedii nebo google.

[Jendа]

Jak který, že. Třeba N270, který se s oblibou montoval do EEEček, je.

[pavlix]

Až nebudeš odpovídat v minulém čase na příspěvky v přítomném čase, tak se o tom můžeme bavit :).

[Jendа]

Dobře, oprava nutná.

[Jendа]

OK, navrhni něco jiného, co má i s grafikou spotřebu 3 W a výtečnou podporu v Linuxu. (a je to na trhu :)

[cronin]

No, len aby to nebolo tak, že vypol hyperthreading. Po dvoch rokoch to zapne, a zistí, že v rozpore s jeho očakávaním aj tvrdeniami marketingových materiálov Intelu v skutočnosti celú dobu bežal s tuningovými nastaveniami.

[bubla]

Když vyšel Half-Life 2, tak tvůrci doporučovali hrát s vypnutým HT. Já jsem zkusil hrát s vypnutým i zapnutým a s vypnutým to bylo horší, občas se mi tam trhal zvuk.

Měl jsem tehdy Pentium 4 s jádrem Prescott.

[cronin]

U nás záťažové testy viacvrstvovej aplikácie ukazovali na 5 až 15 percentný pokles priepustnosti pri zapnutom HT. Presný typ procesora si nepamätám, ale bol to HP ProLiant s dvomi fyzickými CPU na frekvencii kdesi tesne pod 3GHz.

[Lazar]

Neprojevuje se přínos hyperthreadingu při současném provozu zátěžově odlišných aplikací (INT, FP)? Vícevrstvá aplikace asi nebude tento případ.

[R]

HIGHMEM potrebujes uz od 1GB RAM. A to jednoducho urobis s kazdym CPU od PII vyssie:

135MB HIGHMEM available.
887MB LOWMEM available.
...
CPU: Intel Celeron (Coppermine) stepping 0a

[pushkin]

"Hovado! Proč do p*dele používáš i386 na svém nablýskaném x86_64 stroji s tunami gigabajtů RAM. Nabootuj proboha do jádra pro x86_64 a využij plný potenciál. Tvůj i386 userspace na tom bude fungovat dobře. Jsi jako jeden z těch 75letých dědků, co si konečně můžou pořídit Porsche, aby s ním nakonec jeli 10 mil pod povolenou rychlostí a měli za sebou kolonu aut!"

Jo, ten člověk mi mluví z duše (a nejde jenom o počítače)