Zásobník volání - Call stack

Ve vědě o počítačích , je zásobník volání je zásobník datová struktura , která uchovává informace o aktivních podprogramy jednoho počítačového programu . Tento druh zásobníku je také znám jako spouštěcí zásobník , programový zásobník , řídicí zásobník , zásobník za běhu nebo zásobník stroje a je často zkrácen pouze na „ zásobník “. Ačkoli je údržba zásobníku volání důležitá pro správné fungování většiny softwaru , podrobnosti jsou obvykle skryté a automatické v programovacích jazycích na vysoké úrovni . Mnoho počítačůinstrukční sady poskytují speciální pokyny pro manipulaci se zásobníky.

Zásobník volání se používá pro několik souvisejících účelů, ale hlavním důvodem, proč ho mít, je sledovat bod, do kterého by měl každý aktivní podprogram po dokončení provádění vrátit kontrolu. Aktivní podprogram je ten, který byl vyvolán, ale ještě není dokončen, po kterém by měl být ovládací prvek předán zpět volanému. Takové aktivace podprogramů mohou být vnořeny na libovolnou úroveň (rekurzivní jako speciální případ), proto je struktura zásobníku. Například pokud podprogram DrawSquarevolá podprogram DrawLineze čtyř různých míst, DrawLinemusí vědět, kam se vrátit, když je jeho provedení dokončeno. K dosažení tohoto cíle je adresa, která následuje po instrukci, na kterou skočí DrawLine, zpáteční adresa , při každém volání tlačena na horní část zásobníku volání.

Popis

Vzhledem k tomu, že zásobník volání je organizován jako zásobník , volající posílá zpáteční adresu do zásobníku a volaný podprogram po dokončení vytáhne nebo zobrazí zpáteční adresu ze zásobníku volání a předá řízení na tuto adresu. Pokud volaný podprogram zavolá ještě další podprogram, vloží do zásobníku volání další zpáteční adresu atd., Přičemž informace se budou skládat a odkládat podle pokynů programu. Pokud tlačení spotřebuje celý prostor přidělený pro zásobník volání, dojde k chybě nazývané přetečení zásobníku , což obvykle způsobí selhání programu . Přidání záznamu podprogramu do zásobníku volání se někdy nazývá „navíjení“; naopak, odstranění položek je „odvíjení“.

Tam je obvykle právě jeden zásobník volání spojené s běžící program (nebo přesněji, s každým úkolem nebo vlákno jednoho procesu ), i když další zásobníky mohou být vytvořeny pro signální manipulaci nebo kooperativní multitasking (jako setcontext ). Vzhledem k tomu, že je jediná v tomto důležitém kontextu to může být označován jako na stack (implicitně, „úkolu“); Nicméně, ve Forth programovacího jazyka údaje stack nebo parametr stack je přístupná explicitněji než v zásobníku volání a je běžně označován jako v zásobníku (viz níže).

V programovacích jazycích na vysoké úrovni jsou specifika zásobníku volání programátorovi obvykle skryta. Mají přístup pouze k sadě funkcí, nikoli k paměti na samotném zásobníku. Toto je příklad abstrakce . Většina montážních jazyků naopak vyžaduje, aby programátoři byli zapojeni do manipulace se zásobníkem. Skutečné podrobnosti zásobníku v programovacím jazyce závisí na kompilátoru , operačním systému a dostupné instrukční sadě .

Funkce zásobníku volání

Jak je uvedeno výše, primárním účelem zásobníku volání je ukládání zpátečních adres . Když je vyvolán podprogram, musí být někde uloženo umístění (adresa) instrukce, ve které může volací rutina později pokračovat. Použití zásobníku k uložení zpáteční adresy má oproti alternativním konvencím volání důležité výhody . Jedním z nich je, že každý úkol může mít svůj vlastní zásobník, a tak podprogram může být bezpečný pro vlákna , to znamená, že může být aktivní současně pro různé úkoly, které dělají různé věci. Další výhodou je to, že tím, že poskytuje opakovaného , rekurze je automaticky podporována. Když se funkce rekurzivně volá, je třeba pro každou aktivaci funkce uložit zpáteční adresu, aby ji bylo možné později použít k návratu z aktivace funkce. Stackové struktury tuto schopnost poskytují automaticky.

V závislosti na jazyce, operačním systému a prostředí stroje může zásobník volání sloužit dalším účelům, například:

Místní úložiště dat
Subrutina často potřebuje paměťový prostor pro ukládání hodnot lokálních proměnných , proměnných, které jsou známé pouze v rámci aktivního podprogramu a nezachovají hodnoty po jeho návratu. Často je vhodné přidělit prostor pro toto použití jednoduchým přesunutím horní části zásobníku o dostatek místa. To je ve srovnání s dynamickým přidělováním paměti , které využívá prostor haldy, velmi rychlé . Všimněte si, že každá samostatná aktivace podprogramu získá svůj vlastní samostatný prostor v zásobníku pro místní obyvatele.
Předávání parametrů
Subrutiny často vyžadují, aby jim hodnoty parametrů byly dodány kódem, který je volá, a není neobvyklé, že v zásobníku volání může být rozloženo místo pro tyto parametry. Obecně, pokud existuje jen několik malých parametrů, k předání hodnot se použijí registry procesoru , ale pokud existuje více parametrů, než je možné takto zpracovat, bude potřeba paměťový prostor. Zásobník volání funguje dobře jako místo pro tyto parametry, zejména proto, že každému volání podprogramu, který bude mít různé hodnoty parametrů, bude v zásobníku volání přidělen samostatný prostor pro tyto hodnoty.
Zásobník hodnocení
Operandy pro aritmetické nebo logické operace se nejčastěji umisťují do registrů a provozují se tam. V některých situacích však mohou být operandy naskládány do libovolné hloubky, což znamená, že musí být použito něco víc než registrů (to je případ rozlití registru ). Zásobník takových operandů, podobně jako v kalkulačce RPN , se nazývá vyhodnocovací zásobník a může zabírat místo v zásobníku volání.
Ukazatel na aktuální instanci
Některé objektově orientované jazyky (např. C ++ ) ukládají tento ukazatel spolu s argumenty funkcí do zásobníku volání při vyvolání metod. Na tento ukazatel nastaven na objektu instanci spojené s postupem, který se použil.
Uzavírací kontext podprogramu
Některé programovací jazyky (např. Pascal a Ada ) podporují deklaraci vnořených podprogramů , které mají přístup k kontextu svých obklopujících rutin, tj. K parametrům a lokálním proměnným v rámci vnějších rutin. Takové statické vnoření se může opakovat - funkce deklarovaná v rámci funkce deklarované v rámci funkce ... Implementace musí poskytovat prostředky, pomocí kterých může volaná funkce na kterékoli dané úrovni statického vnoření odkazovat na uzavírací rámec na každé úrovni uzavírajícího vnoření. Obvykle je tento odkaz implementován ukazatelem na rám naposledy aktivované instance uzavírací funkce, nazývané „downstack link“ nebo „static link“, aby se odlišil od „dynamického odkazu“, který odkazuje na okamžitého volajícího ( což nemusí být statická nadřazená funkce).

Namísto statického odkazu mohou být odkazy na uzavírající statické rámce shromážděny do řady ukazatelů známých jako displej, který je indexován tak, aby vyhledal požadovaný rámec. Hloubka lexikálního vnoření rutiny je známá konstanta, takže velikost zobrazení rutiny je pevná. Také je znám počet obsahujících oborů, které je třeba procházet, index na displeji je také pevný. Displej rutiny je obvykle umístěn ve vlastním rámu zásobníku, ale Burroughs B6500 implementoval takový displej v hardwaru, který podporoval až 32 úrovní statického vnoření.
Záznamové položky označující obory se získávají z příslušné předpony displeje volajícího. Vnitřní rutina, která se opakuje, vytváří pro každé vyvolání samostatné rámce volání. V tomto případě všechny statické odkazy vnitřní rutiny ukazují na stejný kontext vnější rutiny.
Jiný návratový stav
Kromě zpáteční adresy mohou v některých prostředích existovat další stavy strojů nebo softwaru, které je třeba obnovit, když se podprogram vrátí. To může zahrnovat věci jako úroveň oprávnění, informace o zpracování výjimek, aritmetické režimy atd. V případě potřeby to může být uloženo v zásobníku volání stejně jako zpáteční adresa.

Typický zásobník volání se používá pro zpáteční adresu, místní obyvatele a parametry (známé jako rámec volání ). V některých prostředích může být zásobníku hovorů přiřazeno více či méně funkcí. Například v programovacím jazyce Forth jsou obvykle na zásobníku volání uloženy pouze zpáteční adresa, počítané parametry smyčky a indexy a případně lokální proměnné (v tomto prostředí se jmenuje zpětný zásobník ), i když lze dočasně umístit libovolná data tam pomocí speciálního kódu pro zpracování zpětného zásobníku, pokud jsou respektovány potřeby volání a návratů; Parametry jsou obvykle uloženy na samostatném údaje zásobníku nebo parametru zásobníku , typicky volal stack v terminologii Forth, i když tam je zásobník volání, protože to je obvykle přístupný jasněji. Některé Forths mají také třetí zásobník pro parametry s plovoucí desetinnou čárkou .

Struktura

Rozvržení zásobníku volání pro vzestupné hromádky

Zásobník volání se skládá z rámců zásobníku (nazývaných také aktivační záznamy nebo aktivační rámce ). Jedná se o strojově závislé a ABI- závislé datové struktury obsahující informace o stavu podprogramu. Každý rámec zásobníku odpovídá volání podprogramu, který ještě nebyl ukončen návratem. Například pokud DrawLineaktuálně běží podprogram s názvem , který byl vyvolán podprogramem DrawSquare, může být horní část zásobníku volání rozložena jako na sousedním obrázku.

Schéma, jako je tento, lze nakreslit v obou směrech, pokud je rozuměno umístění vrcholu, a tak je pochopen směr růstu zásobníku. Kromě toho se nezávisle na tom architektury liší v tom, zda zásobníky volání rostou směrem k vyšším adresám nebo směrem k nižším adresám. Logika diagramu je nezávislá na volbě adresování.

Rámec zásobníku v horní části zásobníku je pro aktuálně prováděnou rutinu. Rámec stohu obvykle obsahuje alespoň následující položky (v pořadí push):

  • argumenty (hodnoty parametrů) předané rutině (pokud existují);
  • zpáteční adresa zpět volajícímu rutiny (např. v rámci DrawLinezásobníku, adresa do DrawSquarekódu); a
  • prostor pro místní proměnné rutiny (pokud existují).

Ukazatele zásobníku a rámečku

Když se velikosti rámce zásobníku mohou lišit, například mezi různými funkcemi nebo mezi vyvoláními konkrétní funkce, vyskakování rámce ze zásobníku nepředstavuje pevné snížení ukazatele zásobníku . Při návratu funkce se ukazatel zásobníku místo toho obnoví na ukazatel rámce , což je hodnota ukazatele zásobníku těsně před voláním funkce. Každý rámec zásobníku obsahuje ukazatel zásobníku na horní část rámu bezprostředně pod ním. Ukazatel zásobníku je proměnlivý registr sdílený mezi všemi vyvoláními. Ukazatel rámce daného vyvolání funkce je kopií ukazatele zásobníku, jaký byl před vyvoláním funkce.

Umístění všech ostatních polí v rámci lze definovat buď relativně k horní části rámečku, jako záporné posunutí ukazatele zásobníku, nebo relativně k horní části rámečku níže, jako pozitivní posunutí ukazatele rámečku. Samotné umístění ukazatele rámce musí být inherentně definováno jako záporné posunutí ukazatele zásobníku.

Uložení adresy do rámce volajícího

Ve většině systémů má rámec zásobníku pole, které obsahuje předchozí hodnotu registru ukazatele rámce, hodnotu, kterou měl během provádění volajícího. Například rám zásobníku DrawLineby měl místo v paměti, které drží hodnotu ukazatele rámce, která DrawSquarepoužívá (není zobrazeno na obrázku výše). Hodnota je uložena při vstupu do podprogramu a obnovena po návratu. Mít takové pole ve známém umístění v rámci zásobníku umožňuje kódu postupně přistupovat ke každému rámci pod rámcem aktuálně prováděné rutiny a také umožňuje rutině snadno obnovit ukazatel rámce na rámec volajícího , těsně před tím, než se vrátí.

Lexikálně vnořené rutiny

Programovací jazyky, které podporují vnořené podprogramy, mají také v rámci volání pole, které ukazuje na rámec zásobníku poslední aktivace procedury, která nejblíže zapouzdřuje volaného, ​​tj. Okamžitý rozsah volaného. Toto se nazývá přístupový odkaz nebo statický odkaz (protože sleduje statické vnoření během dynamických a rekurzivních hovorů) a poskytuje rutině (stejně jako jakýmkoli jiným rutinám, které může vyvolat) přístup k místním datům svých zapouzdřovacích rutin při každém vnoření úroveň. Některé architektury, kompilátory nebo optimalizační případy ukládají jeden odkaz pro každou uzavírací úroveň (nejen okamžitou uzavírací), takže hluboce vnořené rutiny, které přistupují k mělkým datům, nemusí procházet několik odkazů; tato strategie se často nazývá „display“.

Přístupové odkazy lze optimalizovat, když vnitřní funkce nepřistupuje k jakýmkoli (nekonstantním) místním datům v zapouzdření, jako je tomu například u čistých funkcí komunikujících pouze prostřednictvím argumentů a návratových hodnot. Některé historické počítače, jako například velké systémy Burroughs , měly speciální „zobrazovací registry“ na podporu vnořených funkcí, zatímco kompilátory pro většinu moderních strojů (například všudypřítomný x86) si podle potřeby jednoduše rezervovaly několik slov na zásobníku pro ukazatele.

Překrytí

Pro některé účely lze považovat rámec zásobníku podprogramu a jeho volajícího za překrývající se, přičemž překrytí se skládá z oblasti, kde jsou parametry předávány z volajícího volanému. V některých prostředích volající vloží každý argument do zásobníku, čímž rozšíří svůj rámec zásobníku a poté vyvolá volanou. V jiných prostředích má volající předem přidělenou oblast v horní části rámce zásobníku, aby držel argumenty, které dodává ostatním podprogramům, které volá. Tato oblast se někdy nazývá oblast odchozích argumentů nebo oblast popisků . V rámci tohoto přístupu vypočítá kompilátor velikost oblasti jako největší potřebnou pro jakýkoli volaný podprogram.

Použití

Zpracování stránky volání

Obvykle je manipulace se zásobníkem volání potřebná na místě volání podprogramu minimální (což je dobré, protože pro každý podprogram může být voláno mnoho míst volání). Hodnoty skutečných argumentů se vyhodnocují na webu volání, protože jsou specifické pro konkrétní volání a buď se posílají do zásobníku, nebo se umisťují do registrů, jak určuje použitá konvence volání . Skutečná volací instrukce, jako například „větev a spojení“, se poté obvykle provede k přenosu řízení do kódu cílového podprogramu.

Zpracování vstupu podprogramu

Ve volaném podprogramu se první spuštěný kód obvykle nazývá podprogram prologu , protože provádí potřebné úklidové práce před zahájením kódu pro příkazy rutiny.

Pro architektury sady instrukcí, ve kterých instrukce použitá k volání podprogramu vrací zpáteční adresu do registru, místo toho, aby ji tlačila na zásobník, prolog běžně uloží zpáteční adresu tím, že tlačí hodnotu na zásobník volání, i když pokud volaný podprogram nevolá žádné jiné rutiny, může ponechat hodnotu v registru. Podobně lze posunout aktuální hodnoty ukazatele zásobníku a / nebo ukazatele rámce.

Pokud se používají ukazatele rámce, prolog obvykle nastaví novou hodnotu registru ukazatele rámce z ukazatele zásobníku. Místo v zásobníku pro místní proměnné lze poté přidělit postupnou změnou ukazatele zásobníku.

Forth programovací jazyk umožňuje explicitní navíjení zásobníku volání (nazývané tam „return stack“).

Zpracování vrácení

Když je podprogram připraven k návratu, provede epilog, který zruší kroky prologu. Tím se obvykle obnoví uložené hodnoty registru (například hodnota ukazatele rámce) z rámce zásobníku, vypne se celý rám zásobníku ze zásobníku změnou hodnoty ukazatele zásobníku a nakonec se větev na instrukci na zpáteční adresu. Pod mnoha konvencemi volání položky vyskočené ze zásobníku epilogem obsahují původní hodnoty argumentů, v takovém případě obvykle již nedochází k žádné další manipulaci se zásobníkem, kterou musí volající provést. U některých konvencí volání je však odpovědností volajícího odstranit argumenty ze zásobníku po návratu.

Odvíjení

Návrat z volané funkce vyskočí horní snímek ze zásobníku, možná ponechá návratovou hodnotu. Obecnější úkon vyskakování jednoho nebo více rámců ze zásobníku, aby se pokračovalo v provádění jinde v programu, se nazývá odvíjení zásobníku a musí se provést, když se používají nelokální řídicí struktury, jako jsou ty, které se používají pro zpracování výjimek . V tomto případě rámec zásobníku funkce obsahuje jednu nebo více položek specifikujících obslužné rutiny výjimek. Když je vyvolána výjimka, zásobník je odvinut, dokud není nalezen obslužný program, který je připraven zpracovat (chytit) typ vyvolané výjimky.

Některé jazyky mají jiné řídicí struktury, které vyžadují obecné odvíjení. Pascal umožňuje globálnímu příkazu goto přenést řízení z vnořené funkce do dříve vyvolané vnější funkce. Tato operace vyžaduje odvíjení zásobníku, odebrání tolik rámců zásobníku, kolik je nutné k obnovení správného kontextu pro přenos řízení do cílového příkazu v rámci vnější funkce. Podobně má C funkce setjmpa,longjmp které fungují jako nelokální gotos. Common Lisp umožňuje ovládat, co se stane, když se stoh odmotá pomocí unwind-protectspeciálního operátoru.

Při použití pokračování se stoh (logicky) odvíjí a poté se převíjí se stohem pokračování. To není jediný způsob implementace pokračování; například pomocí vícenásobných, explicitních zásobníků může aplikace pokračování jednoduše aktivovat jeho zásobník a načíst hodnotu, která má být předána. Programovacího jazyka Scheme umožňuje libovolné thunks , které mají být prováděny v určitých bodech na „odvíjení“ nebo „převíjení“ kontrolního stohu, když je pokračováním vyvolána.

Inspekce

Zásobník volání lze někdy zkontrolovat, když je spuštěný program. V závislosti na tom, jak je program napsán a kompilován, lze informace o zásobníku použít k určení přechodných hodnot a tras volání funkcí. To se používá ke generování jemnozrnných automatizovaných testů a v případech, jako je Ruby a Smalltalk, k implementaci prvotřídních pokračování. Například GNU Debugger (GDB) implementuje interaktivní kontrolu zásobníku volání spuštěného, ​​ale pozastaveného programu C.

Odebírání vzorků zásobníku volání v pravidelném čase může být užitečné při profilování výkonu programů, protože pokud se ukazatel podprogramu na vzorcích dat zásobníku zásobníku objeví mnohokrát, je to pravděpodobně úzké místo kódu a mělo by být zkontrolováno kvůli problémům s výkonem.

Bezpečnostní

V jazyce s volnými ukazateli nebo nekontrolovanými zápisy do pole (například v C) je směšování dat toku řízení, které ovlivňuje provádění kódu (zpáteční adresy nebo uložené ukazatele rámce) a jednoduchých dat programu (parametry nebo návratové hodnoty ) v zásobníku volání je bezpečnostní riziko, případně zneužít prostřednictvím přetečení na zásobníku jako nejčastější typ přetečení zásobníku .

Jeden z takových útoků zahrnuje naplnění jedné vyrovnávací paměti libovolným spustitelným kódem a poté přetečení stejné nebo nějaké jiné vyrovnávací paměti, aby se přepsala nějaká zpáteční adresa hodnotou, která ukazuje přímo na spustitelný kód. Výsledkem je, že když se funkce vrátí, počítač tento kód provede. Tento druh útoku může být snadno blokován W ^ X . Podobné útoky mohou uspět i se zapnutou ochranou W ^ X, včetně útoku na návrat do libc nebo útoků pocházejících z návratově orientovaného programování . Byly navrženy různé zmírnění, například ukládání polí na zcela odděleném místě od zpětného zásobníku, jako je tomu v programovacím jazyce Forth.

Viz také

Reference

Další čtení

externí odkazy