Hívási verem

A számítástechnikában a hívási verem olyan verem- adatstruktúra, amely információkat tárol a számítógépes program aktív alprogramjairól . Ez a fajta verem végrehajtási veremnek, program veremnek, vezérlő veremnek, futási idő veremnek vagy gépi veremnek is nevezik, és gyakran csak " verem " -re rövidítik. Bár a hívási verem karbantartása fontos a legtöbb szoftver megfelelő működéséhez, a részletek nem láthatók és automatikusan működnek a magas szintű programozási nyelveken . Számos számítógépes utasításkészlet különleges utasításokat tartalmaz a verem kezelésére.

A hívási verem több célra használható , de elsődleges feladata az, hogy nyomon kövesse azt a pontot, amelyhez az aktív alprogramoknak vissza kell adniuk az irányítást, amikor végrehajtják. Az aktív alprogram az, amelyet meghívtak, de a végrehajtás még nem fejeződik be, miután az irányítást vissza kell adni a hívás helyére. Az alprogramok ilyen aktiválása bármilyen szintre beágyazható (különleges esetként rekurzív), következésképpen a verem szerkezetébe is. Például, ha egy alprogram a DrawSquare négy különféle helyről hív fel egy DrawLine alprogramot, akkor a DrawLine -nak tudnia kell, hogy hova kell visszatérnie, amikor a végrehajtás befejeződik. Ennek megvalósításához a DrawLine -ra a visszatérési cím-re ugró utasítástokat követő címre kell lépnie , a visszatérési cím, mindegyik hívással a hívásverem tetejére tolódik.

Leírás

Mivel a hívási verem, verem -ként van rendezve, a hívó kitolja a visszatérési címet a verembe, és a hívott alprogram amikor befejezi, kiszedi a visszatérési címét a hívási veremből és átirányítja a vezérlést erre a címre. Ha a hívott alprogram újabb alprogramot hív , akkor egy másik visszatérési címet továbbít a híváskötegre, és így tovább, az információk egymásra helyezésével és leválasztásával, amint a program előírja. Ha a bepakolás a hívásveremhez kiosztott összes helyet elhasználja, verem túlcsordulásnak nevezett hiba jelentkezik, ami általában a program összeomlását okozza. Egy alprogram bejegyzésének hozzáadása a hívási veremhez néha "felsorakoztatás (felhúzás)"-nak; nevezzük , ezzel szemben, a bejegyzések eltávolítása a "felszabadítás".

Általában pontosan egy hívási verem van társítva egy futó programmal (vagy pontosabban, minden egyes feladattal vagy egy folyamat szálával ), bár további vermek is létrehozhatók jelkezeléshez vagy kooperatív multitasking-hoz (mint setcontext ). Mivel csak egy van ebben a fontos összefüggésben, ezért nevezhetjük a verem-nek (konrétabban „a felada verménekt”); azonban a Forth programozási nyelv az adatköteghez vagy a paraméter-veremhez kifejezetten hozzáférnek, mint a hívásveremhez, és általában veremnek nevezik (lásd alább).

Magas szintű programozási nyelveken a hívási verem specifikációit általában elrejtik a programozótól. Csak egy sor funkcióhoz férnek hozzá, nem pedig a verem memóriájához. Ez egy példa az absztrakcióra . A legtöbb assembly nyelv viszont megköveteli a programozók részvételét a verem manipulálásában. A verem tényleges részletei programozási nyelven a fordítótól, az operációs rendszertől és a rendelkezésre álló utasításkészlettől függnek.

A hívási verem funkciói

Mint fentebb megjegyeztük, a hívási verem elsődleges célja a visszatérő címek tárolása . Alprogram behívásakor az utasítás helyét (címét), amelyen a hívási rutin késõbb folytatódhat, valahol el kell menteni. A verem használata a visszatérési cím mentéséhez fontos előnyökkel jár az alternatív hívási konvenciókkal szemben . Az egyik az, hogy minden egyes feladat lehet saját verem, és így az alprogram lehet szálbiztos, azaz egyszerre aktív különböző feladatok elvégzésekor. Egy másik előnye az, hogy az újraértékelés biztosításával a rekurzió automatikusan támogatott. Amikor egy eljárás rekurzívan hívja magát, a függvényben minden aktiválásakor visszaadási címet kell tárolni, hogy később felhasználható legyen a metódus aktiválásakor. A verem struktúrák ezt a képességet automatikusan biztosítják.

A nyelvetől, az operációs rendszertől és a számítógépes környezettől függően a hívásverem további célokat szolgálhat, többek között:

Helyi adattárolás

Az alprogramnak gyakran szükséges memóriaterület a helyi változók értékeinek tárolására, olyan változókra, amelyek csak az aktív alprogramban ismertek, és amelyek visszatérés után nem tartják meg az értékeket. Gyakran kényelmes erre a célra helyet kiosztani, ha egyszerűen csak mozgatják a verem tetejét a hely biztosításához. Ez nagyon gyors a dinamikus memóriaelosztáshoz képest, amely a kezelt területet használja fel. Figyelembe veszi , hogy az alprogram minden egyes aktiválása külön helyet fog kapni a veremben a helyiek számára.

Paraméterátadás

Az alprogramok gyakran megkövetelik, hogy a paraméterek értékeit a hívó kód adja meg nekik, és nem ritka, hogy ezeknek a paramétereknek a helyét el lehet helyezni a hívási veremben. Általában, ha csak kevés paraméter van, akkor az értékek átadására a processzor regisztereket használjuk, de ha több paraméter létezik, mint amennyit ilyen módon lehet kezelni, akkor memóriahelyre lesz szükség. A hívási verem jól működik ezeknek a paramétereknek a helyén, különösen mivel minden olyan alprogramhoz történő hívás, amelynek a paraméterek eltérő értékei vannak, külön helyet fog hagyni a hívási veremben ezekre az értékekre.

Értékelési verem

A számtani vagy logikai műveletek operandusait általában regiszterekbe helyezik, és ott működtetik. Bizonyos helyzetekben azonban az operandusok tetszőleges mélységbe rakhatók, ami azt jelenti, hogy nem csupán regisztereket kell használni (ez vonatkozik a regiszterek kiszórására ). Az ilyen operandusok halmazát, inkább, mint egy RPN számológépben, értékelési veremnek nevezik, és helyet foglalhat el a hívási veremben.

Mutató az aktuális példányra

Néhány objektum-orientált nyelv (pl. C ++ ) tárolja <i id="mwVQ">ezt a</i> mutatót a függvény argumentumokkal együtt a hívási veremben metódusok meghívásakor. Ez a mutató a meghívandó módszerhez társított objektumpéldányra mutat.

Befoglaló alprogram kontextus

Néhány programozási nyelv (pl. Pascal és Ada ) támogatja a beágyazott alprogramok deklarálását, amelyek hozzáférhetnek a záró rutinok kontextusához, azaz a külső rutinok hatókörén belüli paraméterekhez és helyi változókhoz. Az ilyen statikus beágyazás megismétlődik - egy függvényen belül deklarált függvényen deklarált függvény. . . A megvalósításnak olyan eszközt kell biztosítania, amellyel a meghívott függvény adott statikus beágyazás szinteken hivatkozhat a körülvevő keretre minden egyes záró beágyazás szintnél. Általában ezt a hivatkozást egy mutató hajtja végre a mellékelt funkció legutóbb aktivált példányának keretére, úgynevezett "downstack link" vagy "statikus link", hogy megkülönböztesse azt a "dinamikus link" -től, amely a közvetlen hívóra utal ( amelyeknek nem kell a statikus szülőfüggvénynek lennie).

Statikus kapcsolat helyett a mellékelt statikus keretekre mutató hivatkozásokat össze lehet gyűjteni egy olyan mutatóegység-sorozatban, amelyet kijelzőnek hívunk, és amelyet a kívánt képmeghatározáshoz indexelnek. A rutin lexikális beágyazás mélysége ismert állandó, tehát a rutin megjelenítésének mérete rögzített. Szintén ismert az áthaladási skálák száma, a kijelzőn szereplő index is rögzítve van. Általában egy rutin kijelzője a saját verem keretében található, de a Burroughs B6500 olyan képernyőt valósított meg a hardverben, amely akár 32 szintű statikus beágyazást is támogatott.

A hatóköröket tartalmazó kijelzőbejegyzéseket a hívó fél kijelzőjének megfelelő előtagjából szerezzük. A visszatérő belső rutin minden híváshoz külön hívási keretet hoz létre. Ebben az esetben a belső rutin statikus összeköttetései ugyanarra a külső rutin kontextusra mutatnak.

Egyéb visszatérési állapot

A visszatérési cím mellett néhány környezetben előfordulhatnak más gépi vagy szoftver állapotok is, amelyeket vissza kell állítani, amikor az alprogram visszatér. Ide tartozhatnak például a jogosultsági szint, a kivételkezelési információk, a számtani módok és így tovább. Szükség esetén ez tárolható a hívási veremben, ugyanúgy, mint a visszatérési cím.

A tipikus hívási vermet a visszatérési címek , a helyi változók és a paramétereket használják(más néven a hívást keret). Bizonyos környezetekben előfordulhat, hogy több vagy kevesebb funkció van hozzárendelve a hívási veremhez. Például az Forth programozási nyelvben általában csak a visszatérési címet, a megszámlált hurok paramétereket és az indexeket, valamint esetlegesen a helyi változókat tárolják a hívási veremben (amelyet ebben a környezetben visszatérési veremnek neveznek), bár bármilyen adat átmenetileg elhelyezhető ott speciális visszatérő verem kezelési kódot használnak mindaddig, amíg a hívások és a visszatérések igényeit tiszteletben tartják. A paramétereket általában külön adathalmazon vagy paraméter- verm-en tárolják, amelyet általában a veremnek hívnak a Forth terminológiában, annak ellenére, hogy van egy hívási verem, mivel ehhez általában kifejezetten hozzáférnek. Néhány Forth-nak van egy harmadik verem is a lebegőpontos paraméterekhez.

Szerkezet

Hívásverem-elrendezés felfelé növekvő verem-hez

A hívási verem veremkeretből áll (más néven aktiválás bejegyzések vagy aktiválás keretek). Ezek gépi és ABI- függő adatstruktúrák, amelyek alprogram állapotinformációkat tartalmaznak. Mindegyik verem-keret egy olyan alprogram hívására vonatkozik, amely még nem fejeződött be visszatéréssel. Például, ha jelenleg egy DrawLine nevű alprogram fut, amelyet egy DrawSquare alprogram DrawSquare, akkor a DrawSquare felsõ része el lehet DrawSquare, mint a szomszédos képen.

Az ilyen ábra bármelyik irányba rajzolható, amennyiben megértjük a teteje elhelyezkedését és a verem növekedésének irányát. Ezen felül, az építményektől függetlenül, abban különbözik egymástól, hogy a híváskötegek magasabb vagy alacsonyabb címek felé növekednek-e. A diagram logikája független a címzés választásától.

A verem tetején lévő veremkeret az éppen végrehajtott rutinhoz tartozik. A veremkeret általában legalább a következő elemeket tartalmazza (nyomtatási sorrendben):

• a rutinnak átadott argumentumok (paraméterértékek) (ha vannak ilyenek);
• a visszatérési cím a rutin hívójának vissza (pl. a DrawLine verem keretben, egy cím a DrawSquare kódjába); és
• hely a rutin helyi változóinak (ha vannak).

Verem és keret mutatók

Ha a verem keretmérete eltérő lehet, például a különféle függvények között vagy egy adott eljárás meghívása között, akkor a keret felbukkanása a veremből nem jelenti a verem mutató rögzített csökkenését. A függvény visszatérésekor visszaállítja a keret mutatót , a verem mutató a függvény meghívása előtti állapotra. Mindegyik veremkeret tartalmaz egy veremmutatót ami közvetlenül a keret tetejére mutat. A veremmutató egy változtatható regiszter, amely megoszlik az összes meghívás között. A függvény adott meghívásának keret mutatója a verem mutató példánya, ahogyan a függvény indítása előtt állt.

A keret összes többi mezőjének helyét a keret felső részéhez viszonyítva lehet meghatározni, a keret mutatójának negatív eltolásaként, vagy az alatta lévő keret felső részéhez viszonyítva, a keret mutatójának pozitív eltolásaként. Maga a keret mutató helyét önmagában a köteg mutató negatív eltolásaként kell meghatározni.

A cím tárolása a hívó keretbe

A legtöbb rendszerben a verem keretnek van egy mezője, amely tartalmazza a keret mutató regiszter korábbi értékét, , amely a hívó végrehajtása közbeni érték volt. Például a DrawLine a verem keretének olyan memória helye lenne, amelyben a keret mutató értéke szerepel, amelyet a DrawSquare használ (a fenti ábra nem mutatja). Az érték elmentésre kerül az alprogramba való belépéskor, és visszatéréskor helyreáll. Ha egy ilyen mező található a verem keretben egy ismert helyen, lehetővé teszi a kódban, hogy az egyes keretekhez egymás után hozzáférhessen a jelenleg végrehajtó rutin keretén belül, és lehetővé teszi a rutin számára, hogy a keret mutatóját könnyen visszaállítsa a hívó fél keretében, még mielőtt visszatérne.

Lexikálisan beágyazott rutinok

A beágyazott alprogramokat támogató programozási nyelveknek is van egy mezője a híváskeretben, amely az eljárás legfrissebb aktiválásának veremkeretére mutat, amely a legjobban körülöleli a hívót, azaz a hívó fél közvetlen hatáskörét . Ezt nevezik hozzáférési kapcsolatnak vagy statikus linknek (mivel nyomon követi a statikus beágyazást a dinamikus és rekurzív hívások során), és a rutinhoz (valamint minden más rutinhoz, amelyet felhívhat) hozzáférést biztosít a külső rutin helyi adataihoz minden beágyazási szinten. Egyes architektúrák, fordítók vagy optimalizálási esetek mindegyik záró szinthez egy linket tárolnak (nem csak a közvetlen záró szintet), így a sekély adatokhoz hozzáférő mélyen beágyazott rutinoknak nem kell több linket átjárniuk; ezt a stratégiát gyakran "megjelenítésnek" hívják.

A hozzáférési kapcsolatok akkor optimalizálhatók, ha egy belső függvény nem fér hozzá a (nem állandó) helyi adatokhoz a beágyazásban, mint például a tiszta függvények esetében, amelyek például csak a visszatérési értékek útján kommunikálnak. Néhány történelmi számítógép, például a Burroughs rendszerek, speciális "megjelenítő regiszterekkel" rendelkeztek a beágyazott funkciók támogatására, míg a legtöbb modern gépi fordító (például a mindenütt jelen lévő x86) szükség esetén csak néhány szót foglalnak el a veremben a mutatók számára.

Átfedés

Bizonyos célokból úgy lehet tekinteni, hogy az alprogram és a hívó fél halmazkerete átfedésben van, és az átfedés azon területből áll, ahol a paraméterek átadódnak a hívótól a hívóig. Bizonyos környezetekben a hívó fél minden argumentumot a verembe tolja, ezzel meghosszabbítva a verem keretét, majd meghívja a hívót. Más környezetekben a hívó félnek van egy előre kiosztott területe a verem keretének tetején, hogy megőrizze azokat az érveket, amelyeket más hívott alprogramokhoz szolgáltat. Ezt a területet néha a kimenő argumentumok vagy a feliratok területének nevezik. Ennek a megközelítésnek a felhasználásával a fordító kiszámítja a terület nagyságát, hogy a legnagyobb legyen az úgynevezett szubrutinok számára.

Használat

Hívásoldal feldolgozása

Az alprogramhoz való hívás helyén általában szükséges a minimális hívásverem-manipuláció (ami jó, mivel sok hívóhely lehet minden egyes meghívandó alprogram számára). A tényleges érvek értékeit a hívás helyén értékelik, mivel azok az adott hívásra specifikusak, és vagy a verembe kerülnek, vagy regiszterekbe kerülnek, a használt hívási konvenció szerint . A tényleges hívási utasítás, például a "branch és link", célja , hogy átvegye az irányítást az alprogram kódja felett .

Alprogram belépésének feldolgozása

Az úgynevezett alprogramban az első végrehajtott kódot általában alprogram prologue-nak nevezzük, mivel az elvégzi a szükséges tisztítást, mielőtt a rutin utasításaihoz tartozó kód elindul.

Az olyan utasításkészlet-architektúrák esetében, amelyekben az alprogram hívására használt utasítás a visszatérési címet egy regiszterbe helyezi, nem pedig a verembe tolásáig, a prologue általában megmenti a visszatérési címet az értéknek a hívási verembe való beillesztésével, és bár ha a hívott alprogram nem hív meg semmilyen más rutint, az értéket a regiszterben hagyhatja. Hasonlóképpen a jelenlegi veremmutató és / vagy a keret mutató értékei is tolhatók.

Keret mutatók használata esetén a prologue általában meghatározza a keretmutatók regiszterének új értékét a veremmutatóból. A verem helyét a helyi változók számára ezután el lehet osztani a verem mutató fokozatos megváltoztatásával.

Az Forth programozási nyelv lehetővé teszi a hívás verem kifejezett felcsévélését (ott „visszatérő veremnek” hívják).

Visszatérés

Amikor egy alprogram kész a visszatérésre, végrehajt egy epilogue-t, amely visszavonja a prologue lépéseit. Ez általában visszaállítja az elmentett regisztrációs értékeket (például a keret mutató értékét) a verem keretéből, az egész verem keretet kiszorítja a veremből a verem mutató értékének megváltoztatásával, és végül átalakul a visszatérési címen található utasításhoz. Számos hívási konvenció szerint az epilogue által a veremből kilépő tételek tartalmazzák az eredeti argumentumértékeket, amely esetben általában nincs további veremkezelés, amelyet a hívó félnek kell elvégeznie. Néhány hívási szabállyal azonban a hívó feladata a paraméterek eltávolítása a verembõl a visszatérés után.

Lezárás

.Ha visszatér a meghívott függvényből, akkor a felső keret kilép a veremből, esetleg visszatérési értéket hagy. Az a általánosabb művelet, hogy egy vagy több keretet kiugrik a veremből a végrehajtás folytatásához a program más részein, ezt verem lezárásának nevezzük, és ezt nem helyi vezérlő struktúrák használatakor kell végrehajtani, például azokat, amelyek kivétel kezelésére szolgálnak. Ebben az esetben a függvény veremkerete egy vagy több bejegyzést tartalmaz, amely meghatározza a kivételkezelőket. Egy kivétel dobásakor a vermet addig tölti, amíg olyan elemet nem talál, ami tudja kezeli (elkapni) a dobott kivétel típusát

Egyes nyelveknek vannak más vezérlési struktúrái is, amelyek általános meghatározást igényelnek. A Pascal lehetővé teszi a globális goto utasítás számára az irányítás áthelyezését egy beágyazott függvényből egy korábban meghívott külső függvénybe. Ez a művelet megköveteli a verem kiürítését, annyi veremkeret eltávolításával, amelyre szükség van a megfelelő környezet helyreállításához, és így a vezérlés átkerül a cél utasításhoz a mellékelt külső függvényen belül. Hasonlóképpen, C nyelv rendelkezik a setjmp és longjmp függvényekkel, amelyek nem helyi longjmp -ként működnek. A Common Lisp lehetővé teszi annak ellenőrzését, hogy mi történik, ha a verem kiürül, az unwind-protect speciális operátor segítségével

Folytatás alkalmazásakor a verem (logikusan) lezárásra kerül, majd feltöltésre kerül a folytatódás vermével. Ez nem az egyetlen mód a folytatások végrehajtására; Például több, explicit adat használatával a folytatódás egyszerűen aktiválhatja a vermet, és felcserélheti az átadandó értéket. A séma programozási nyelve lehetővé teszi az önkényes feladatok végrehajtását a megadott pontokban a vezérlőcsomag "lezárását" vagy " újra töltését", amikor folytatódást hívnak meg.

Ellenőrzés

A hívási verem néha megvizsgálható, a program futása közben. A program írásának és fordításának módjától függően a veremben található információk felhasználhatók a közbenső értékek és a függvényhívási utasítások meghatározására. Ezt automatizált tesztek generálására használják és olyan esetekben, mint például a Ruby és a Smalltalk, az első osztályú folytatások végrehajtására. Például a GNU Debugger (GDB) egy futó, de szüneteltetett C program híváskötegének interaktív ellenőrzését valósítja meg.

Rendszeres időtartamú minták vétele a hívási veremből hasznos lehet a programok teljesítményének profilozásában, mivel ha egy alprogram rámutat többször a hívásverem-mintavételi adatokra, akkor valószínűleg egy szűk keresztmetszet áll fenn, és azt ellenőrizni kell a teljesítményproblémák szempontjából.

Biztonság

Szabad mutatókkal vagy nem ellenőrzött tömbírásos nyelven (például C-ben) a vezérlőáramlás-adatok keverése, amelyek befolyásolják a kód (visszatérési címek vagy a mentett keretmutatók) és az egyszerű program adatok (paraméterek vagy visszatérési értékek) végrehajtását ) hívás veremben biztonsági kockázat, esetleg hasznosítható keresztül verem puffer túlcsordulást a leggyakoribb típusú puffer túlcsordulás .

Az egyik ilyen támadás magában foglalja egy puffer tetszőleges futtatható kóddal való feltöltését, majd ugyanazon vagy más puffer túlcsordulását, hogy egy visszatérési címet felülírjon egy olyan értékkel, amely közvetlenül a végrehajtható kódra mutat. Ennek eredményeként, amikor a funkció visszatér, a számítógép végrehajtja ezt a kódot. Az ilyen támadást könnyen blokkolni a W ^ X segítségével .   Hasonló támadások akkor is sikeresek lehetnek, ha engedélyezve van a W ^ X védelem, ideértve a visszatérés-libc támadást vagy a visszatérés-orientált programozásból származó támadásokat. Különféle megoldási javaslat, például a tömböknek a visszatérési veremtől teljesen különálló helyen való tárolása, amint az a Forth programozási nyelv esetében is elő fordul..

Lásd még

• Automatic memory allocation
• Calling convention
• Coroutine
• Overhead (computing)
• Spaghetti stack
• Stack-based memory allocation
• Stack machine

További irodalom

• Dijkstra (1960). „Recursive Programming”. Numerische Mathematik 2 (1), 312–318. o. DOI:10.1007/BF01386232.  
• Wilson, P. R.. Dynamic storage allocation: A survey and critical review, Memory Management, Lecture Notes in Computer Science, 1–116. o.. DOI: 10.1007/3-540-60368-9_19 (1995). ISBN 978-3-540-60368-9 
• 2.4. The Stack, MCS-4 Assembly Language Programming Manual - The INTELLEC 4 Microcomputer System Programming Manual, Preliminary, Santa Clara, California, USA: Intel Corporation, 2-7 – 2-8. o.. MCS-030-1273-1 (1973. december 1.). Hozzáférés ideje: 2020. március 2.  (NB. Intel's 4-bit processor 4004 implements an internal stack rather than an in-memory stack.)

Külső linkek

• Function Calling and Frame Pointer Operations in 68000
• The libunwind project - a platform-independent unwind API