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

17. 6. 2014 | Luboš Doležel | Jaderné noviny | 4070×

Aktuální verze jádra: 3.15-rc7. Zvětšování jaderného zásobníku. Kdo audituje kód pro audit?

Obsah

• Aktuální verze jádra: 3.15-rc7
• Zvětšování jaderného zásobníku
• Kdo audituje kód pro audit?

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

Aktuální vývojová verze jádra je 3.15-rc7 vydaná 25. května. Je to jen pár dnů po -rc6, ale jak jsem očekával, po návratu domů na mě čekaly různé věci, takže toto berte jako „normální“ vydání, zatímco rc6 bylo jen opožděné kvůli mému cestování.

Stabilní aktualizace: během minulého týdne žádné nevyšly. Aktualizace 3.14.5 a 3.10.41 se právě revidují; jejich vydání můžeme očekávat 31. května nebo později. Verze 3.12.21 se také reviduje a očekává se 2. června nebo později.

Zvětšování jaderného zásobníku

Každý proces zabírá určité množství paměti jen kvůli tomu, že existuje. I když se to může zdát málo, jedním z důležitějších kousků paměti nezbytné pro každý proces je místo pro zásobník jádra. Jelikož každý proces může teoreticky běžet v jádře současně, každý musí mít svou vlastní oblast zásobníku. Pokud je v systému mnoho procesů, pak se prostor zásobníků může pěkně nahromadit; skutečnost, že zásobník musí být fyzicky souvislá oblast paměti, může subsystému správy paměti také pěkně zadělat. Tyto obavy byly vždy silnou motivací, proč udržet velikost jaderného zásobníku malou.

Po většinu doby, co tu Linux je, měl zásobník jádra na většině architektur 8 KB – dvě fyzické stránky. Naposledy v roce 2008 se vývojáři snažili vejít do 4 KB, ale jejich cíl se ukázal být nereálným. Moderní jádra dovedou vytvořit překvapivě hluboko vnořená volání, která se do 4KB zásobníku zkrátka nevejdou.

Navíc se začíná čím dál víc zdát, že se na x86-64 nemusejí vejít ani do 8KB zásobníku. Minchan Kim nedávno odhalil původ jednoho pádu a ukázalo se, že jde o přetečení zásobníku; zareagoval návrhem zdvojnásobit velikost zásobníku na x86-64 na 16 KB. Podobné návrhy už dříve narazily na odpor a stalo se tak i tentorkát; Alan Cox sdělil, že řešení je třeba hledat někde jinde. Ale vypadá to, že je v tomto postoji už skoro sám.

Dave Chinner se často musí potýkat s problémy s přetečením zásobníku, protože se na XFS stávají často, jelikož XFS dává zásobníku zabrat více než jiní. Tento návrh tedy docela podporoval:

8KB zásobník nebyl pro IO architekturu Linuxu na x86-64 nikdy dostačující, ale nikdo kromě vývojářů IO a systémů souborů nebyl ochoten tento argument akceptovat, navzdory opakujícím se přetečením zásobníku, kvůli kterým se v systémech souborů lepí jedna obezlička na druhou.

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ě.

Takže mám v podstatě v plánu patch aplikovat, zároveň se ale ujistím, že řešíme problémy, které tu máme, a ne že je jen obcházíme. 8kB zásobník byl docela omezující a problémový a uznávám, že už je až moc nepříjemný, ale nechci abychom to vzdali, kdykoliv se objeví problém s příliš velkým využitím zásobníku.

Linus také sdělil, že nemá zájem měnit velikost zásobníku v Linuxu 3.15. Zanedlouho se ale otevře začleňovací okno 3.16; dost možná půjde o jednu z prvních změn v něm.

Kdo audituje kód pro audit?

Subsystém pro audit není zrovna oblíbenou částí jádra. Umožňuje vytváření proudu logů popisujících určité systémové události – systémová volání, úpravy určitých souborů, operace prováděné procesy s určitým ID uživatele apod. Pro některé jde o ideální způsob, jak se dozvědět, co se na systému děje a hlavně také jak zajistit splnění různých bezpečnostních certifikací (např. Common Criteria). Pro jiné jde o ošklivé a invazivní rozšíření jádra, které přidává režii bez přidávání užitečné funkčnosti. Nedávno se ale ukázalo, že audit přidává i vlastní bezpečnostní díry. Skutečným problémem je ovšem to, že skoro nikdo se na kód nedívá, takže chyby v něm mohou číhat po dlouhou dobu.

Mechanismus pro audit systémových volání vytváří záznamy v logu auditu v reakci na systémová volání; administrátor může načíst pravidla určující, která systémová volání se mají logovat. Tato pravidla mohou zahrnovat různé porovnávání s parametry systémových volání, ale je tam i jednoduchá bitová maska indexovaná podle čísla systémového volání určující, která volání nás zajímají. Jednou z prvních věcí, co kód pro audit dělá, je, že otestuje, zda je bit odpovídající aktuálnímu volání nastaven; pokud ne, tak se žádné auditování neprovádí.

Philipp Kern nedávno zaznamenal drobný problém týkající se toho, jak kód funguje s x32 ABI. Když kód běžící pod tímto ABI zavolá systémové volání, nepoužívá běžná čísla volání pro architekturu x86; volání x32 (která vyžadují speciální zacházení s určitými parametry) jsou označená nastavením dodatečného bitu (0x40000000) v čísle volání. kód pro audit tento bit před ověřením čísla volání neodstraňoval; asi si umíte představit, že výsledek nebyl zrovna správný. Philipp připojil patch odstraňující speciální bit pro x32, ale ukázalo se, že problém je větší, než se zdálo.

Při pohledu na Philippův patch si Andy Lutomirski uvědomil, že v kódu nechybí jen odstranění jednoho bitu; v kódu celkově schází jakákoliv kontrola mezí. Uživatelský prostor může předat jakékoliv číslo systémového volání a jádro jej použije jako index do bitové masky; stačí dostatečně velké číslo volání a je z toho předvídatelný oops jádra. Andy navíc řekl, že toto selhání by bylo možné použít ke zjištění hodnoty určitých bitů v jaderném prostoru, což vede ke zranitelnosti vyzrazením údajů.

Andy už zaslal patch pro tento konkrétní problém, ale neskončil jen u toho. Dospěl k závěru, že subsystém pro audit je zkrátka na šrot, takže jeho patch jej celý označuje za rozbitý a tedy obecně nepřístupný. Vyjmenoval řadu dalších problémů: škodí výkonu, i když se nepoužívá, podle něj není spolehlivý, má problémy na různých architekturách a jeho přístup k uvolňování paměti je děsivý. Suma sumárum, Andy říká, že bez něj nám bude lépe:

Celkově vzato je ten kód jeden obrovský binec. To, jak funguje, se ani skoro nedá pochopit. Obsahuje nejméně jednu závažnou chybu. Byl bych rád, kdyby byla opravena, ale mezitím si distribuce myslí, že povolení CONFIG_AUDITSYSCALL rozumná věc, já bych přitom řekl, že je to strašlivá volba pro kohokoliv, kdo nepotřebuje pravidla pro auditování systémových volání. A ani nevím, kdo to potřebuje.

Není překvapivé, že Eric Paris, kdo kód pro audit udržuje, s jeho hodnocením nesouhlasí. Podle něj jde jen o další chybu, kterou je potřeba opravit; nepoukazuje to na systémový problém v kódu pro audit.

Něco nám ale říká to, že tato konkrétní zranitelnost existuje v subsystému pro audit už od jeho vzniku. Kódu pro audit se dostává jen málo revidování; většina vývojářů jádra to pro svá vlastní jádra prostě vypíná a nevšímají si ho. Ale tento subsystém je přitom něčím, co distributoři téměř vždy musejí v jádře zapnout; někteří uživatelé to vyžadují, a tak to musí zapnout pro všechny. Následkem toho mají skoro všechny systémy audit povolený (podívejte se, jestli máte vlákno kauditd), i když jen málo z nich jej využívá. Tyto systémy trpí zhoršeným výkonem jen kvůli tomu, že audit je povolený, a přitom jsou zranitelné všemi chybami, co se v kódu pro audit najdou.

Kdyby byl audit implementován dnes, dotyční vývojáři by museli přinejmenším důsledně promyslet, zda nepoužít mechanismus pro trasování. Už má své háčky na všech správných místech, přitom tyto háčky mají (téměř) nulovou režii, pokud nejsou povoleny. Trasování má svůj vlastní vestavěný filtrovací mechanismus; přidání filtrů na bázi BPF tuto funkci učiní ještě mocnější a rovněž rychlejší. Subsystém pro audit vlastně obsahuje další jaderný virtuální stroj, který rozhoduje o tom, jaké události logovat; používání architektury pro trasování by umožnilo odstranění tohoto kódu a sjednocení do jediného virtuálního stroje, který je více udržován a revidován.

Systém pro audit, který teď máme, je ale starší než trasovací subsystém, takže nemohl být postaven na trasování. Jeho nahrazení bez způsobení problémů stávajícím uživatelům by nebylo triviální, i kdyby v kódu nebyly zádrhely, o kterých jsme mluvili (a jistě tam takové zádrhely jsou). Proto se současného subsystému pro audit v dohledné době jen tak nezbavíme (a určitě nebude v hlavní řadě jádra označen za „rozbitý“). Doufejme, že se i on sám dočká vlastního auditu pro případ, že by v něm byla další překvapení.

       

Komentáře

[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.