Wikipédia

Hívási verem

verem-adatstruktúra, amely információkat tárol egy számítógépes program aktív alprogramjairól

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. Ezt a fajta vermet végrehajtási veremnek, programveremnek, vezérlő veremnek, futásiidő-veremnek vagy gépi veremnek is nevezik, és gyakran csak veremnek 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ímre ugró utasításokat követő címre kell lépnie, a visszatérési cím mindegyik hívással a hívási verem tetejére tolódik.

Leírás szerkesztés

Mivel a hívási verem veremké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 multitaskinghoz (mint setcontext). Mivel csak egy van ebben a fontos összefüggésben, ezért nevezhetjük a veremnek (konkrétabban „a feladat vermének”); azonban a Forth programozási nyelv az adatköteghez vagy a paraméterveremhez kifejezetten hozzáférnek mint a hívásveremhez, és általában veremnek nevezik (lásd alább).

Magas szintű programozási nyelvben 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 szerkesztés

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 nyelvtő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 processzorregisztereket 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 szerkesztés

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

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 keretmutatók szerkesztés

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 veremmutató rögzített csökkenését. A függvény visszatérésekor a veremmutató a keretmutatóra áll vissza, értéke pedig a függvény hívása előtti érték. 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 keretmutatója a veremmutató példánya, ahogyan a függvény indítása előtt állt.[1]

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 keretmutató helyét önmagában a kötegmutató negatív eltolásaként kell meghatározni.

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

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 szerkesztés

Azoknak a programozási nyelveknek, amik támogatják az alprogramokat, van egy úgy nevezett hívási mezője, ami arra a legutóbbi eljárásra mutat, mely legjobban beágyazza a hívottat, ez a hívott azonnali hatásköre.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.[2]

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 szerkeszté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 szerkesztés

Hívásoldal feldolgozása szerkesztés

Általában a szubrutinban a hívás helyén szükséges verem változtatása (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 szerkesztés

Az úgynevezett alprogramban az első végrehajtott kódot általában alprogram prológnak 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 prológ á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 prológ á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.

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

Visszatérés szerkesztés

Amikor egy alprogram kész a visszatérésre, végrehajt egy epilógot, amely visszavonja a prológ 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 epilóg á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 szerkesztés

A meghívott függvényből, való visszatérés a verem legfelső keretét érinti, esetleg visszatérési értéket hagy. Verem lezárásnak nevezzük azt az általánosabb műveletet, amikor amikor egy vagy több keret kiugrik a veremből, hogy folytatódjon a végrehajtás a program más részein. Ezeket akkor kell végrehajtani, amikor nem helyi vezérlő struktúrákat használunk 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 a 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ás kezelésére létrehozott veremben. 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 új értéket hívnak meg.

Ellenőrzés szerkeszté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 [3] é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. [4]

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 szerkesztés

Szabad mutatókkal vagy nem ellenőrzött tömbírással rendelkező nyelvben (például C-ben) a vezérlőáramlás-adatok keverése, amelyek befolyásolják a kód végrehajtását (visszatérési címek vagy a mentett keretmutatók) és az egyszerű program adatok (paraméterek vagy visszatérési értékek) keverése a hívási veremben biztonsági kockázatot jelent. Valószínűleg a leggyakoribb puffertúlcsordulásokon, a verem pufferek túlcsordulásán keresztül aknázható ki.

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

Jegyzetek szerkesztés

  1. ↑ Understanding the Stack. cs.umd.edu, 2003. június 22. (Hozzáférés: 2014. május 21.)
  2. ↑ Alternative Microprocessor Design
  3. ↑ McMaster, S.. Call Stack Coverage for GUI Test-Suite Reduction, 17th International Symposium on Software Reliability Engineering, 33–44. o.. DOI: 10.1109/ISSRE.2006.19 (2006). ISBN 0-7695-2684-5 
  4. ↑ Debugging with GDB: Examining the Stack. chemie.fu-berlin.de, 1997. október 17. [2021. április 14-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. december 16.)
  5. ↑ Doug Hoyte. "The Forth Programming Language - Why YOU should learn it".

Források szerkesztés

Fordítás szerkesztés

Ez a szócikk részben vagy egészben a Call stack című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Hívási_verem&oldid=25909018”