Jaderné noviny – 30. 5. 2014: Mračna nad 8KB zásobníky (diskuse)

[ota]

Známý soudní znalec Smejkal zmanipuloval posudek softwaru pro IBM, což již pravomocně potvrdil soud. Kdyby v IBM používali Linux, tak se to nemůže stát.

[Conscript89]

A souvislost s Jadernymi novinkami?
Jinak dekuji ze novinky vychazi v cestine, ac nemam s anglicitnou problem, asi by se mi v ni cist nechtely.

[Pepa]

jakou má Linux souvislost se Smejkalem a jeho posudkem?

Aneb: kdybys nebyl hlupákem nestal by ses medvědem

[little.owl]

Linus zpočátku nebyl změně nakloněn a dal najevo, že práce na snížení využití zásobníku jádra musejí pokračovat. Ale i Linusovi nakonec došlo, že hrát si s přetečeními zásobníku na schovávanou problém nevyřeší spolehlivě.

To, ze systemu prokazatelne staci zasobnik pro vsechny mozne cesty volani, je zakladni pozadavek na spolehlivost systemu a bez toho muze Linux na jakoukoliv rozumnou certifikaci zapomennout. CONFIG_FRAME_WARN/checkstack.pl/CONFIG_DEBUG_STACK_USAGE jsou jen berlicky.

[nyan]

pro vsechny mozne cesty volani

Good luck with that...

(A vzhledem k tomu kdo vsechno uz jej vesele pouziva, rekl bych ze na tvoji "rozumnou" certifikaci s*re pes..)

[little.owl]

rekl bych ze na tvoji "rozumnou" certifikaci s*re pes..

Linux je kvuli tomu diskvalifikovan z cele rady aplikaci, kde se pak musi pouzivat QNX nebo VxWorks. Jinak snahy o to byly, MeeGo tam temer bylo.

[trekker.dk]

"Diskvalifikován" kvůli tomu, že by bylo něco závažně špatně, nebo protože si nějaký managor přečetl, že existují certfikace šč a fň a tak je musí mít? Jak psal předřečník - vzhledem k tomu kdo vsechno uz jej vesele pouziva...

[little.owl]

Tak certifikace je, rekneme, formalni potvrzeni nejake, byt treba vseobecne zname, kvality a casto je to proste v realnem svete nutne.

Je to jako s profesnimi certifikacemi - veci muzete tisickrat umet - ale pokud nemate potvrzeni, nekdy smula - ale zkuste se na to kouknout z druhe strany.

[Jendа]

a casto je to proste v realnem svete nutne.

Jak často vidíš systém crashovat, protože mu došlo místo na jaderném stacku? Podle mě je kolem milión pravděpodobnějších bugů.

[little.owl]

U safety-critical SW to byva casto i jedina forma dynamicke alokace a tak se musi prokazat, ze stack staci za kazdych podminek; vyzaduji to vicemene vsechny standardy a byva to prvni otazka auditoru. Maloktere bugy vam udelaji takovou paseku, jako prepisovani si zasobniku.

[pc2005]

Jo to by mě taky zajímalo, jak to maj řešený bezpečný operační systémy. Je to vůbec kompatibilní s modularitou? Osobně si ale myslím, že komunita by s vývojem typu OS do družice, moc kompatibilní nebyla .

[little.owl]

To je asi jen otazka penez, vice pravni nez technicka a existuje nekolik urovni. Certifikovany kernel by treba slo redukoval, osekaly by se drivery, to by zajistil dodavatel. Co nam bylo receno, problem neni s kvalitou kodu jadra kernelu, ale to ze se to porad prekopava, takze nakonec vzdy QNX.

Osobně si ale myslím, že komunita by s vývojem typu OS do družice, moc kompatibilní nebyla .

FreeRTOS to zvladl.

Druzice? - Tohle vynesou Indove za par supu (prevazne FreeRTOS, nekde Linux): zde , zde ci zde - i s Nexus-One telefonem.

[pc2005]

The kernel itself consists of only three or four C files.

Tak určitě by šlo osekat kernel, ale taky bych chtěl být schopen pustit si v takovém OS Minecraft .

Druzice? - Tohle vynesou Indove za par supu (prevazne FreeRTOS, nekde Linux): zde , zde ci zde - i s Nexus-One telefonem.

Tak já nevím, tys nepsal, na co přesně nemůžete Linux použít.

[little.owl]

Uvadel jsem FreeRTOS jako GPL licenced OS, za kterym stoji komunita (+ firma) a ktery byl schopen dosahnout na slusne certifikace; s Linuxem jako takovym to jiste nelze z hlediska komplexity srovnavat.

Tak já nevím, tys nepsal, na co přesně nemůžete Linux použít.

Cokoliv, co vyzaduje i mininalni SIL.

Linux by na certifikaci dosahl, treba preliminary hodnoceni pro Health and Safety Executive zde. Analyzovalo by se skutecne jen jadro kernelu. Bez Linux Foundation se to asi nikam nedostane, uz nekolik pokusu vzdy zamrzlo nekde uprostred cesty.

[David Jaša]

Cokoliv, co vyzaduje i mininalni SIL.

Nebyla právě tohle motivace sýmensů, aby vyvíjeli Jailhouse?

[little.owl]

Ano, jedna z cest. Pokud mate i jen SIL1 muzete zacit delat magii - kombinaci dvou SIL1 dosahnete na SIL2, nebo pouzijete SIL1 + maly SIL3 kontroler a podobne. Bez SIL ovsem smula, i kdyby melo jednat i jen o splachovani zachodu.

[Michal Kubeček]

Linus také sdělil, že nemá zájem měnit velikost zásobníku v Linuxu 3.15.

Hm, tak to mu to přesvědčení dlouho nevydrželo… :-(

[PetrHL]

Mohl byste mi nekdo, prosim, vysvetlit co se do toho zasobniku uklada a proc tak resi velikost?

[chrono]

Veľkosť sa rieši preto, lebo ten zásobník má pevnú veľkosť a vo fyzickej pamäti musia použité stránky jedného zásobníka nasledovať za sebou (čo by, na dlho bežiacom systéme s veľa procesmi/vláknami, mohol byť, pri príliš veľkom zásobníku, problém).

[j]

Ukladaji se do toho adresy, kam se ma vratit beh kodu, pokud zavolas nejaky podprogram (velmi zjednodusene) ... a ten muze volat dalsi ... a ten dalsi ... a musi se ti tam vejit proste vse do maximalni hloubky volani, jinak to zbuchne.

[Michal Kubeček]

Na zásobníku jsou především návratové adresy a lokální proměnné. Příliš malý zásobník je problém, pokud dojde k jeho přetečení, což znamená hodně vnořených úrovní volání a hodně lokálních proměnných. Abych pravdu řekl, nevím, co je na kódu filesystémů tak specifického, že mají s 8KB zásobníkem problémy. U síťového kódu jen zřídka vídám, že by se nevešel do 4 KB. Větší zásobník naopak znamená větší overhead procesu a potenciálně i problémy, není-li dost paměti a je-li fragmentovaná (potřebujete alokovat souvislý blok čtyř stránek místo dvou).

Obecně je kód jádra díky těm 8KB zásobníkům mnohem disciplinovanější, než je zvykem v userspace (zejména v glibc jsem viděl strašidelné věci), kde je běžné mít zásobník velký 256 KB nebo dokonce 8 MB a výrazně menší se používá jen u masivně multithreadových aplikací. Právě proto se trochu bojím, že přechod na 16 KB vývojářům "rozváže ruce" a přestanou si zásobník tolik hlídat, takže (katastrofický scénář) za pár let budeme tam, kde jsme byli. Případně že pokud 16KB zásobník bude jen na x86_64, začnou se objevovat problémy s přetečením zásobníku na ostatních architekturách, které nejsou tolik testované.

V každém případě je velkým - a nepříjemným - překvapením, že Linus takovou zásadní změnu vzal do RC8 (které IIRC možná původně ani nebylo v plánu) místo toho, aby počkal na 3.16-rc1 a byl čas nechat to aspoň trochu uzrát a prověřit.

[little.owl]

Právě proto se trochu bojím, že přechod na 16 KB vývojářům "rozváže ruce" a přestanou si zásobník tolik hlídat, takže (katastrofický scénář) za pár let budeme tam, kde jsme byli.

Prave. Mne to spise vyznelo tak, ze "my vime, ze 8KB neni nekde asi dost a tak tam dame 16KB a budem doufat, ze se to snad vyresi".

[Jindřich Makovička]

Filesystém je v tom podle výpisu nevinně, ten zabírá 1KB. Za většinou je blokové IO, virtuální paměť a swap. Hlavní problém je množství zanoření - nic tam není zjevně špatně, ale stokrát nic umořilo osla.

[little.owl]

No, zrovna XFS mi neprijde v tom nevinne, treba zde.

[Jindřich Makovička]

Ano, tohle je horší, v mailu odkazovaném v článku figuroval ext4. Ale pořád se XFS i přes tu hromadu vnoření vejde do nějakých 3.5KB. Zatímco do_select() hodí na zásobník poll_wqueues a skoro kilobajt je pryč.

[little.owl]

hodí na zásobník poll_wqueues a skoro kilobajt je pryč.

AFAIK, to je dusledek teto optimizace (SUSE ), coz by slo IMHO opravit snadneji nez prekopat XFS.

[deda.jabko]

Kdyz si vezmes, ze 32bitovym systemum staci 8KB, je mirne naivni si myslet, ze to bude stacit i 64bitovym, tech dat je tam proste vic... Navic si ted nejsem jisty, jestli i v pripade jaderneho kodu, prekladac generuje zarovnani zasobniku na 16B, nebo ne.

[Michal Kubeček]

Kdyz si vezmes, ze 32bitovym systemum staci 8KB, je mirne naivni si myslet, ze to bude stacit i 64bitovym

Tohle je logicky úplně chybná úvaha. Kdybyste míst "32-bitovým systémům stačí 8 KB" napsal "32-bitovým systémům nestačí 4 KB", tak by to sice pořád nebyl dostatečný argument, ale aspoň by to dávalo trochu smysl.

[frr]

mhmm... pokud jde o návratové adresy, tak na 64b architektuře bude návratová adresa 8B, na 32b stroji jsou to 4B. Dál je otázka, jaké procento objemu dat na zásobníku dělají návratové adresy, a jaké procento dělají lokální proměnné - a do jaké míry v průměru závisí délka lokálních proměnných na architektuře.

Ještě mě napadá, že modernější generace CPU mají čím dál širší např. "MMX" registry. Pokud má systém podporovat paralelní běh více procesů či vláken (která s novou širší množinou registrů pracují), musí kernelový plánovač při přepnutí kontextu pushnout čím dál větší objem dat - ovšem pokud tomu správně rozumím, pushuje ty data v každém běžícím vlákně jenom jednou, takže asi žádná křeč, není to důvod pro zdvojnásobení zásobníku. Samotný interrupt (který je základním spouštěčem plánovače) hardwarově v CPU pushne prakticky jenom návratovou adresu - další registry musí pushnout explicitně kód plánovače. Asi jsem konečně pochopil, k čemu si člověk v Menuconfigu vybírá model procesoru

Každopádně z těch řečí o zásobníku podle mě plyne ponaučení "nepoužívat autorekurzivní funkce v kernelu" (nebo autorekurzivní konglomeráty více funkcí). A nepoužívat zbytečně mnoho lokálních funkcí = alokovat všechna větší data (např. rozsáhlejší structy) zásadně na heapu.

[pc2005]

To pushování při IRQ závisí dost na architektuře. Některý můžou mít speciální stack na obsluhu přerušení ale některý umí přepnout banku regitrů (BTW naprogramovat v HDL lze cokoliv ). Třeba na Microblaze se registry ukládají do struktury ručně v assembleru. Jsou tam "vtipný triky", jak si uložit registrovou sadu včetně ukazatele na tu registrovou sadu.

[frr]

Ano máte pravdu, moje kusé populárně naučné znalosti se týkají x86. Prakticky jenom kecám z gauče, programování mě neživí... Díky za osvěžující podrobnosti "odjinud"

[nyan]

než je zvykem v userspace (zejména v glibc jsem viděl strašidelné věci), kde je běžné mít zásobník velký 256 KB nebo dokonce 8 MB

Tak ono tomu vydatne pomaha gcc a spousta programatoru o tom ani netusi..

Jsem videl kdesi funkci s masivnim switchem, ktera kvuli tedle drobnosti sezrala >3KB na volani...

[Michal Kubeček]

Ty příklady, které jsem měl na mysli, spočívaly v alokaci struktury s dynamickou a potenciálně neomezenou velikostí pomocí alloca(), to na gcc svedete jen s velkou dávkou fantazie. :-)

[nyan]

Tak ano, alloca je jednoduche (zne/po)uzivat jako prase. To ale nic nemeni na faktu, ktery sem popsal - totiz ze gcc velmi rado obetuje spoustu pameti aby usetrilo par instrukci. A tezko lze ocekavat od programatoru, ze budou hlidat kompilator, ze si dela svou praci poradne...

[chrono]

S gcc mám skôr opačné skúsenosti. Podľa mojich skúseností obetuje kopec inštrukcií, len aby bol kód nemerateľne rýchlejší.

[kdave]

Abych pravdu řekl, nevím, co je na kódu filesystémů tak specifického, že mají s 8KB zásobníkem problémy.

Neni to ciste filesystemovy kod, ale to v jakou chvili a z jakeho kontextu se filesystemovy kod muze volat, kdyz ma zapsat stranky. V tu chvili uz muze byt neco ze stacku sezraneho.

Dale pokud si filesystem v tu chvili usmysli, ze k tomu potrebuje jeste par bajtu pameti (aby nezral stack), tak nasledny kmalloc muze spustit dalsi retez akci, ktere mu tu pamet zajisti. V nejhorsim pripade je to direct reclaim, ktery uz nema moznost sahnout pro nejakou rychle uvolnitelnou pamet, a zkusi neco odswapovat.

Zapisy na zarizeni si taky kousek stacku vemou, zalezi na typu, ale nebyva to moc. Pokud je device poskladan z vice vrstev (MD-RAID, LVM, LUKS, multipath), tak se to nacita. Nebo pod tim jeste iscsi.

Z druheho konce se taky da lepit, NFS nebo eCryptfs.

U xfs byly reportovany problemy prave v kombinaci s MD-RAID a NFS, to neni nic neobvykleho, ani to ze se treba pouzivaji i ty zanorene raidove levely na vetsich polich.

Samotne xfs je uvnitr dost komplexni, nektere operace se zurnalem si dovedou vzit vyznamy kus. Pred casem museli offloadovat cast operaci do worker threadu, aby sehnali misto na stacku.

Co bezneho uzivatele trapit nemusi, jsou zapnute debugovaci volby (pro zamky, alokator). S temi se da stack prekrocit snadneji a je zahodno, aby to i s nimi jakz takz fungovalo.

[Filip Jirsák]

Je to zásobník volání podprogramů. Programy jsou naprogramovány tak, že se skládají z menších částí, ty se zase mohou skládat z dalších částí atd. Funguje to tak, že každá ta část programu je umístěná někde v paměti, a když je potřeba provést kód té části, skočí se v paměti na příslušné místo, kód se provede a na konci se skočí zpět na místo, ze kterého se ten podprogram vyvolal. Je tedy nutné si pamatovat, kam se má program vrátit, a to pamatování se dělá právě přes zásobník volání podprogramů. Takže když se volá podprogram, zapíše se na zásobník aktuální adresa, skočí se na podprogram, a když se dojde na konec podprogramu, vyzvedne se ta hodnota ze zásobníku. Protože se tohle dělá hodně často, je potřeba, aby to bylo co nejrychlejší – a toho se docílí jedině se zásobníkem s konstantní velikostí. Velikost zásobníku tedy určuje, kolikrát se může to volání podprogramu vnořit – když budete volat podprogram, v něm další podprogram a v něm ještě jeden vnořený podprogram, potřebujete zásobník alespoň na tři návratové adresy.

[PetrHL]

Dekuji vsem za odpovedi, zase jsem se dozvedel neco noveho.

[dword]

To je duvod proc tohle spadne :)

void function(void)
{
  function();
}

[tacoberu]

Což je hloupé.

 
long function(long l)
{
  if (l < 10000000) {
    return function(++l);   
  }   
  return l; 
} 
function(10);

[Michal Kubeček]

Podceňujete kompilátor. :-)

Upravil jsem to na

int main()
{
  function(10);

  return 0;
}

a dostal

(gdb) disassemble main
Dump of assembler code for function main:
   0x0000000000400410 <+0>:     xor    %eax,%eax
   0x0000000000400412 <+2>:     retq   
End of assembler dump.
(gdb) disassemble function
Dump of assembler code for function function:
   0x0000000000400500 <+0>:     mov    %rdi,%rax
   0x0000000000400503 <+3>:     cmp    $0x98967f,%rdi
   0x000000000040050a <+10>:    mov    $0x989680,%edx
   0x000000000040050f <+15>:    cmovle %rdx,%rax
   0x0000000000400513 <+19>:    retq   
End of assembler dump.

To první je podle očekávání, ale to druhé potěší.

[little.owl]

Ano, tail recursion/call optimization, bohuzel se mi zda ze v C++ to jde snadno rozbit.

[Michal Kubeček]

Tohle jde ještě trochu dál, protože kompilátor vyhodnotil, že ani cyklus není potřeba, a rovnou si to převedl na

  return (l <= 9999999) ? 10000000 : l;

[little.owl]

To ano.

Mam pocit, ze puvodni gcc optimizace byla postavena na teto praci, jak to je ted netusim.