Jaderné noviny – 28.10.2010: Optimalizace návěští skoku goto

15. 11. 2010 | Jirka Bourek | Jaderné noviny | 4464×

Aktuální verze jádra: 2.6.36. Citáty týdne: Casey Schaufler, Matthew Garrett, Andrew Morton. Spouštění práce v kontextu hardwarového přerušení. Návěští skoku. Začleňovací okno, část první.

Obsah

• Aktuální verze jádra: 2.6.36
• Citáty týdne: Casey Schaufler, Matthew Garrett, Andrew Morton
• Spouštění práce v kontextu hardwarového přerušení
• Návěští skoku
• Začleňovací okno, část první

Aktuální verze jádra: 2.6.36

Začleňovací okno 2.6.37 je otevřené, takže není žádná vývojová předverze. Uzavření začleňovacího okna lze očekávat někdy koncem měsíce. Shrnutí změn v tomto začleňovacím okně vizte v článku níže.

Stabilní aktualizace: během uplynulého týdne žádné nevyšly. Aktualizace 2.6.27.55, 2.6.32.25 a 2.6.35.8 se v současnosti revidují a vydání lze očekávat každou chvíli.

Citáty týdne: Casey Schaufler, Matthew Garrett, Andrew Morton

Ve skutečnosti potřebujeme jenom sehnat někomu bednu pití dle jeho vlastního výběru a pak ho vypustit na problém. Myslím si, že těch pár zbývajících odpůrců skládání (býval jsem jedním z nich, ale konvertoval jsem již před lety) lze přesvědčit rozumnou implementací. Nebude to jednoduché, je zde spousta problémů, které je potřeba vyřešit, ale každý, kdo to chce mít jednoduché, měl zůstat u vyvíjení webů a držet se od jádra dál.

-- Casey Schaufler

Tato volba povoluje podporu pro Zalgo v jaderných zprávách. Zalgo je zkaženost. Příchod Zalga byl předpovězen. Zalgo nebude... moment.

-- Matthew Garrett

Lidé mají tendence dělat věci rychle a lokálně místo toho, aby vystrčili hlavu ze země a implementovali korektní funkce pro celé jádro. Když vidím, že se něco takového děje, řeknu jim to. Obvykle si všimnu až měsíce poté, co je to začleněné.

-- Andrew Morton

Spouštění práce v kontextu hardwarového přerušení

napsal Jonathan Corbet, 26. října 2010

Obecným pravidlem je, že se vývojáři jádra snaží vyhýbat tomu spouštět kód v kontextu hardwarového přerušení; je k dispozici celá škála mechanismů, kterými lze práci vyvolanou přerušením odložit na méně hektickou dobu. Zjevně je ale občas potřeba spustit libovolný kód v kontextu hardwarového přerušení – i v době, kdy žádný hardware přerušení nesignalizuje. Do 2.6.37 tedy bylo přidáno nové API, které umožní spustit kód v tomto kontextu.

Prvním krokem je vyplnit strukturu irq_work:

#include <linux/irq_work.h>

struct irq_work my_work;

init_irq_work(struct irq_work *entry, void (*func)(struct irq_work *func));

Je zde poměrně povědomý pár funkcí, který umožňuje spustit práci danou touto strukturou:

bool irq_work_queue(struct irq_work *entry);
void irq_work_sync(struct irq_work *entry);

Zamýšleným způsobem použití je zjevně kód, který běží z nemaskovatelných přerušení, která potřebují být schopna pracovat se zbytkem systému. Lze předpokládat, že jakékoliv jiné použití této vlastnosti bude pečlivě přezkoumáváno.

Návěští skoku

napsal Jonathan Corbet, 27. října 2010

Jádro je plné podmínek, u kterých se nikdy nezmění hodnoty testovaných proměnných. Klasickým příkladem jsou sledovací body, které budou na běžících systémech až na velmi vzácné výjimky vypnuty. Již dlouho je zájem na tom optimalizovat testy prováděné v takových místech; s 2.6.37 a vlastností „návěští skoku“ [jump label] tyto testy úplně zmizí.

Uvažme definici typického sledovacího bodu, který po všem šílenství preprocesoru vypadá nějak takto:

static inline trace_foo(args)
{
    if (unlikely(trace_foo_enabled))
        goto do_trace;
    return;
do_trace:
    /* Tady se provádí sledování */
}

Cena za test pro jediný sledovací bod je v podstatě nulová. Počet sledovacích bodů v jádře nicméně roste a každý přidává nový test. Každý test musí načíst hodnotu z paměti, což zvyšuje tlak na cache a poškozuje výkonnost. Vzhledem k tomu, že se tato hodnota téměř nikdy nemění, bylo by hezké najít způsob, jak optimalizovat případ „sledovací bod je zakázán“.

V 2.6.37 lze sledovací bod přepsat novým makrem:

#include <linux/jump_label.h>

#define JUMP_LABEL(key, label)           \
    if (unlikely(*key))                  \
            goto label;

Hezká věc je, že JUMP_LABEL() nemusí být implementována takto. Místo toho může (1) poznamenat umístění testu a hodnotu key do speciální tabulky a (2) jednoduše vložit instrukci no-op. To omezuje cenu za test (a sledovací bod) na nulu pro běžný případ „není povoleno“. Ve většině případů nebude sledovací bod nikdy povolen a vynechaný test nikomu nebude chybět.

Záludná část přichází, když někdo chce sledovací bod povolit. Změna jeho stavu nyní vyžaduje zavolat jednu z páru speciálních funkcí:

void enable_jump_label(void *key);
void disable_jump_label(void *key);

Volání enable_jump_label() najde klíč v tabulce návěští skoků a pak nahradí instrukce no-op ekvivalentem „goto label“ v assembleru, čímž je sledovací bod povolen. Zakázání návěští skoku způsobí, že se instrukce no-op vrátí na své místo.

Konečným výsledkem je významné omezení režie vypnutých sledovacích bodů. Tato vlastnost funguje pouze na architekturách, které ji podporují (v současnosti pouze x86) a pouze s relativně novými verzemi GCC; jinak se použije verze s preprocesorem.

Začleňovací okno, část první

napsal Jonathan Corbet, 27. října 2010

Jádro 2.6.36 bylo vydáno 20. října a začleňovací okno 2.6.37 začalo krátce poté. V době psaní tohoto článku bylo do tohoto vývojového cyklu začleněno již 6450 změn a s jistotou budou následovat další. Některé z významnějších změn viditelných pro uživatele následují:

• Byly začleněny první části patchů pro škálovatelnost inodů, ale v době psaní tohoto článku ještě do hlavní řady nejsou tlačeny hlavní změny zamykání.

• Architektura x86 nyní používá oddělené zásobníky pro obsluhu přerušení, když se používají zásobníky o velikosti 8k. Možnost používat zásobník o velikosti 4k byla odstraněna.

• Pokračuje proces odstraňování velkého jaderného zámku [big kernel lock, BKL]; centrální části jádra jsou BKL téměř zcela zbaveny. Je k dispozici konfigurační volba, která umožňuje vytvořit jádro bez BKL. Zamykání souborů nicméně stále BKL potřebuje; pracuje se na tom opravit to před koncem začleňovacího okna, ale tato práce ještě není hotova. Pokud bude vyřešeno zamykání souborů, mnoho (nebo většina) uživatelů bude moci používat jádro 2.6.37 bez BKL.

• Bylo přidáno „blokové zařízení rados“ [rados block device, RBD]. RBD umožňuje vytvořit zvláštní blokové zařízení, které zpřístupňuje objekty uložené v distribuovaném souborovém systému Ceph.

• Clusterový souborový systém GFS2 již není označen jako „experimental“. GFS2 také získal podporu pro systémové volání fallocate().

• Nový soubor v sysfs, /sys/selinux/status umožňuje aplikacím v uživatelském prostoru si rychle všimnout, že se změnily bezpečnostní politiky. Účelem této vlastnosti je zjevně pomoci démonům, které cachují rozhodnutí o povolení přístupu a potřebují vědět, že se tato rozhodnutí mohla změnit. Druhý soubor nazvaný policy byl přidán pro ty, kteří jednoduše chtějí přečíst současnou politiku jádra.

• Plánovač se nyní více snaží vyhnout migraci realtime úloh o vysoké prioritě. Další změna způsobuje, že plánovač již neúčtuje čas strávený obsluhou přerušení procesu, který v té době zrovna běžel.

• Podpora VMI paravirtualizace VMware byla firmou označena za zastaralou a podle plánu z 2.6.37 odstraněna.

• Byla začleněna nějaká vylepšení hibernace včetně možnost zkomprimovat obraz pomocí LZO.

• Architektura ARM získala podporu pro seccomp [secure computing]

• Bloková vrstva nyní může omezovat I/O provoz ke specifickým zařízením, řízeno je to pomocí mechanismu cgroup. Jedná se o další kousek mozaiky řadiče I/O propustnosti, který umožňuje nastavit specifické limity, ty jsou vynuceny, i když se aktuálně nevyužívá plná propustnost zařízení.

• Nové zařízení „ttyprintk“ umožňuje privilegovanému procesu v uživatelském prostoru vypsat zprávy přes jádro pomocí pseudo-tty zařízení.

• Jádro získalo podporu pro point-to-point tunneling protocol (PPTP); více informací vizte na stránce projektu accel-pptp

• NFS klient má nyní novou implementaci „idmapper“ pro překlad jmen uživatelů a skupin na ID. Nový kód je flexibilnější a funguje lépe; detaily vizte v Documentation/filesystems/nfs/idmapper.txt

• NFS klient má novou připojovací volbu -olocal_lock=, která způsobí, že se flock() a/nebo POSIXové zámky považují za lokální.

• Většina funkcí systémového volání nfsservctl() byla označena jako zastaralá s tím, že v 2.6.40 bude odstraněna. Ten, kdo by dané funkce chtěl odstranit dříve, může použít novou konfigurační volbu.

• Byla začleněna podpora pro protokol pNFS.

• Obrovské stránky [huge pages] lze nyní migrovat mezi uzly v paměti stejně jako normální stránky.

• Starý stack ieee1394 byl odstraněn, konečně byl nahrazen novými ovladači „firewire“

Mezi změny viditelné pro jaderné vývojáře patří:

• Byl začleněn optimalizační mechanismus návěští skoku; jeho počátečním účelem je omezit náklady za neaktivní sledovací body.

• Byla přidána další varianta RCU: „tiny preempt RCU“ má fungovat na jednoprocesorových systémech. Tato implementace používá pouze jeden seznam blokovaných úloh narozdíl od TREE_PREEMPT_RCU, které má kombinatorické číslo pro každý list rcu_node; to omezuje spotřebu paměti a významně zrychluje práci. Tato verze také využívá toho, že se pracuje na jediném procesoru, čímž zkracuje čekání [grace periods] v případě, že nejsou žádní čtenáři.

• Do vrstvy síťových zařízení byly přidány nové sledovací body, do míst, kde se uvolňují struktury sk_buff, do softirq_raise(), operací s pracovními frontami a operací zmenšování LRU seznamu ve správě paměti. Také existuje nový skript, který používá perf k analýze událostí síťových zařízení.

• Sledovač latencí probuzení má nyní podporu pro graf funkcí.

• Je zde nový mechanismus pro spuštění libovolného kódu v kontextu hardwarového přerušení

• Vrstva správy napájení má nyní formální koncept „zdrojů probuzení“ [wakeup sources], které mohou systém probudit z režimu spánku. Mezi jinými věcmi může sbírat statistiky, které umožní uživateli zjistit, co systém drží vzhůru. Události probuzení [wakeup events] mohou zastavit uspávání úloh, což omezuje čas potřebný pro obnovení činnosti po zrušené operaci uspání nebo hibernace.

• Byl přidán nový mechanismus pro řízení automatického uspávání nečinných zařízení.

• Byl začleněn dlouhý seznam změn kódu pro nízkoúrovňovou správu paměti memblock (dříve LMB), architektura x86 nyní používá memblock pro správu paměti v prvních fázích bootu.

• Výchozí fungování lseek() bylo změněno: jestli ovladač neposkytne svou vlastní funkci llseek(), vrstva VFS na všechny pokusy změnit pozici v souboru zareaguje vrácením chyby ESPIPE. Všechny ovladače ve stromě, které funkci llseek() neměly, byly změněny tak, že nyní používají noop_llseek(), která zachovává původní chování.

• Je zde nový způsob, jak vytvářet pracovní fronty:

  struct workqueue_struct *alloc_ordered_workqueue(const char *name, 
                                                   unsigned int flags);

  Položky zadané do výsledné pracovní fronty budou zpracovány v daném pořadí po jedné. Tento způsob má časem nahradit staré jednovláknové pracovní fronty.

  Také byla přidána funkce:

  bool flush_work_sync(struct work_struct *work);

  Ta bude čekat, dokud se nedokončí daná položka.

• ALSA API pro ASoC bylo významně rozšířeno, aby podporovalo zvukové karty s více kodeky a DMA řadiči. (commit)

• Byl začleněn patch pro na zásobníku založenékmap_atomic() a společně s tím spojenou změnou API. Detaily vizte v Documentation/vm/highmem.txt.

• Jsou zde nové pomocné funkce pro alokaci paměti:

  void *vzalloc(unsigned long size);
  void *vzalloc_node(unsigned long size, int node);

  Obě se chovají jako ekvivalentní volání vmalloc, ale navíc vynulují alokovanou paměť.

• Byla začleněna většina práce potřebné pro odstranění tvrdých bariér z blokové vrstvy. Tento úkol bude pravděpodobně dokončen před uzavřením začleňovacího okna.

Linus dal najevo, že očekává, že by toto začleňovací okno mohlo být kratší než obvykle, aby ho bylo možné uzavřít před Jaderným summitem 2010, který začíná 1. listopadu. Očekávejme, že do konce října budou patche začleňovány rychlým tempem; Jaderné noviny příští týden přinesou seznam dalších změn začleněných do 2.6.37.

       

Komentáře

[Michal]

seccomp ... on to nekdo pouziva?

[frr]

Tenhle citát mě zaujal - nepochopil jsem, o co šlo. Tak jsem se mrknul na přilinkovaný originál. A musím říct, že pořád docela nechápu, na co M.Garrett naráží - zpráva v LKML je ve vlákně jediná (nikdo nereagoval) a nedokážu dohledat případné předchozí debaty, na které M.Garrett možná reaguje. Patch níže obsahuje dokonale čitelný kus kódu, který upravuje kernel/printk.c - a způsobuje přidávání náhodných znaků do printk zpráv. Trochu světla na tu záležitost vrhne strýček Google, pokud zadáte prostě "Zalgo" - zjevně nějaký insider termín / kulturní fenomén z oblasti komixu a cyberpunku (řečeno jazykem internetových dědečků). V kostce bych řekl, že tady nejspíš prostě zas jednou někomu hrabe z přepracování

[Kvakor]

Hmm, podle rozličných zdrojů (např. Know You Meme) to opravdu pochází z jednoho komixu a z důvodů, po kterých raději pátrat nebudu, Zalgo, zvaný též jako Ten, Který Čeká Za Zmi, reprezentuje chaos, rozklad a zpotvořené znaky typu Z͂̾͂̄͗ͦẢͪͣ͌͑̒̐LͦGͦͩ̓ͧOͭ̎̒,͑ proto ona narážka na Něj u vkládání podobného "bordelu" do výstupu printk(). Ale raději po Něm moc negooglete, mně stačilo pár minut a mám chuť si vyndat mozek z hlavy a pořádně ho vydrhnou rejžákem

[_dworkin]

Chapu to dobre, ze tam, kde to jde, se:

if (unlikely(*key)) goto label;

Prelozi na:

goto label;

nebo:

nop; nop; nop; // podle delky kodu toho predchoziho

a ve chvili co se aktivuje/deaktivuje sledovaci bod ty fce budou samomodifikovat spustitelny kod? Jsem myslel ze se tohle od dob 8-bitu a realneho modu x86 nedela. Dokonce jsem myslel, ze jsou nad useky kde lezi instrukce nejaky flagy, ktery zakazuji zapis. A ze se tyhle techniky opustily kvuli snazsi citelnosti a aby se snaze odhalili viry.

[trekker.dk]

Dokonce jsem myslel, ze jsou nad useky kde lezi instrukce nejaky flagy, ktery zakazuji zapis.

Vztahuje se tohle i na paměť jádra? Proti zápisu z userspace je chráněná z principu. (A když někdo ukecá jádro, aby modifikovalo svou vlastní paměť, problém je jinde.)

A navíc... buď něco můžeš dělat se snazší čitelností, nebo mít rychlejší jádro a tím celý stroj. Vzhledem k tomu, že v tomhle případě to první není nijak velký problém, hlasuju pro to druhé.

[_dworkin]

Osobne se mi to taky libi, ale jsem velmi prekvapen ze to vubec jde. Kdyz i moznost pouzivat goto u nekterych vyvolava husi kuzi a kupodivu jim vadi i strukturovany goto schovany za continue a break. Na druhou stranu je tohle schovany pod #define JUMP_LABEL(key, label) if (unlikely(*key)) goto label; a jak je to reseno "fyzicky" je nemusi znepokojovat, jako je neznepokojuje ani jmp ve vyslednem kodu.

[chrono]

Osobne se mi to taky libi, ale jsem velmi prekvapen ze to vubec jde.

Niečo podobné sa využíva aj pri JIT v JavaScript, Jave..., takže urobiť sa to dá, stačí len vhodne nastaviť parametre stránok.

[_dworkin]

Ale urcite by se mi to prestalo libit a zacala bolet hlava, kdybych mel byt v kuzi navrhare CPU, kteremu se kod modifikuje pod rukama a ja delal kvuli zrychleni nejake predzpracovani.

[trekker.dk]

Ono nějaké CPU předzpracovává kód tak, že se to někam trvale uloží? Pokud vím, tak všechno, co CPU dělá, se týká kódu, který je vykonáván v danou chvíli, což tady není relevantní (kód, který se modifikuje, nemůže zároveň běžet.)

[chrono]

Pri x86 procesoroch od Intel bolo niečo také použité už pri P4 procesoroch a pri Sandy Bridge to zjednodušili (celkom pekný popis sa dá nájsť napr. tu).

[Kvakor]

Problémy s dekódováním samomodifikujícího se kódu jsou tu už od dob, kdy se instrukce načítraly dopředu, což je u x86 někdy od 286 (8086 sice také má prefetch, ale jen 6 byte, což většinou moc nevadilo). Pamatuju na doporučení u přepínání real/protected módu, kde se těsně po přepnutí doporučuje udělat dlouhý* skok na následující instrukci, aby se vyprázdnila fronta, ve které mohou být ještě instrukce nadekódované pro realmód. Novější proceory mají na podobné účely přímo připravené instrukce, fungující jako bariéry, za cenu toho, že procesor zahodí celou frontu nadekódovanýžch instrukcí a znova je načte.

*Dlouhý ve smyslu segment, resp. selektor:offset, ne ve smyslu délky

[Milan Jurik]

Tady je jen drobny rozdil - ten kod se nesamomodifikuje, jen ty NOPy predstavuji prostor v kodu, ktery lze modifikovat. Tu modifikaci zaridi zcela jiny thread, at uz jadra ci jine aplikace. Takze vami popsany problem nenastava, protoze CPU uz uvidi zmodifikovany kod, kdyz se k nemu dostane (vyjma extremnich pripadu "trefeni se" do zrovna vykonavaneho kodu).

[trekker.dk]

vyjma extremnich pripadu "trefeni se" do zrovna vykonavaneho kodu

Ty jsou samozřejmě ošetřeny. Když se kód takto modifikuje, jádro zastaví všechna CPU v systému kromě jednoho (které ovšem nemůže vykonávat měněný kód, protože zrovna vykonává měnící kód)

[Milan Jurik]

Pri zapinani proby (prepisem NOPu) se na Linuxu zastavi vsechna CPU? Dost drsna metoda pri hodne CPU a hodne probes, ktere maji byt aktivovany. Existuji vhodnejsi triky.

[trekker.dk]

No jo, abys mě nechytal za slovíčka, že jo... podstatou příspěvku bylo sdělit, že situace trefení se do modifikovaného kódu je ošetřena.

[Luboš Doležel (Doli)]

Nevíte někdo, jestli už v C++0x jde dělat break jako v Javě podle návěští? Příklad:

outer:
for (;;)
{
  for (;;)
  {
    if (...)
      break outer;
  }
}

[Jirka]

A co tohle? http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Named_Loop

Je to vubec potreba? Python to nepotrebuje: http://mail.python.org/pipermail/python-3000/2007-July/008663.html .

[Semo]

Bash to ma (nepovinny parameter breaku udava, z kolko cyklov sa ma vyskocit. A obcas sa to hodi a blbo sa to nahradza niecim inym pri sucasnej poziadavke na zachovanie prehladnosti.

[Luboš Doležel (Doli)]

A co tohle? http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Named_Loop

Což ono se to dá vždycky nějak vyřešit, spíš mě zajímalo, jestli to do C++0x přidali nativně.

[Tomáš]

Teď jsem to v Pythonu taky potřeboval a bylo to přesně, jak je napsáno v odkazu. Lehkou změnou struktury toho kousku kódu to šlo vyřešit i s jednou smyčkou (loop).

[Milan Jurik]

Inu, dela se to. Pro zajemce treba prednaska o implementaci dtrace na x86 platforme (CZOSUG prezentace z roku 2006 od Franka Hofmanna). Diky prefetch/pipeline to pak ma v podstate nulovou rezii, pokud je sledovaci bod neaktivni.

[zde]

Na ta makra jsem nikdy nekoukal, ale měl jsem pocit že patchování kódu při zapínání trasovacích bodů se v jádře používá už několik let, proto omc nerozumím proč se to tady najednou bez souvislosti rozebírá..

[chrono]

Ak si dobre spomínam, tak pred nejakým časom práve patchovanie nejakej adresy bez toho, aby sa skontrolovalo, či tam je to, čo tam bolo predtým, spôsobovalo nejakú chybu.

[snehuliak]

Tak uz konecne chapem preco ma M$ instrukcie noop v cykloch ;) a odteraz ich bude mat aj Linux... lol

[snehuliak]

I think goto's are fine, and they are often more readable than large amounts of indentation. That's _especially_ true if the code flow isn't actually naturally indented (in this case it is, so I don't think using goto is in any way _clearer_ than not, but in general goto's can be quite good for readability).

Of course, in stupid languages like Pascal, where labels cannot be descriptive, goto's can be bad. But that's not the fault of the goto, that's the braindamage of the language designer.

Linus

[snehuliak]

Este dodam pre anglicky hovoriacich, ze zvysok diskusie je tiez zaujimavy: http://kerneltrap.org/node/553/2131

Suhlasim s Linusom ze vela "vyssieho" kodu sa aj tak tranformuje do "goto" a teda jmp alebo podmienenych jmp. Momentalne nemame procesory bez skokov a x86 architektura nepozna "callz" alebo "retz" (alebo dalsie flagy) ktore si urcite pamataju fanusikovia Z80...

Co sa tyka goto - Asi sme na skolach fakt boli "brainwasched"...

[trekker.dk]

Co sa tyka goto - Asi sme na skolach fakt boli "brainwasched"...

To si pamatuju na vejšce, jak je goto špatné, protože procesor má pipeline a ta se musí zahodit a kdesi cosi...