Hívási lista - Call stack

A számítástechnikában a hívásverem egy verem adatstruktúra , amely információkat tárol egy számítógépes program aktív alprogramjairól . Ez a fajta halom végrehajtási , program- , vezérlő- , futásidejű vagy gépi kötegként is ismert , és gyakran csak " verem " -re rövidül . Bár a hívásverem fenntartása fontos a legtöbb szoftver megfelelő működéséhez , a részletek általában rejtettek és automatikusak a magas szintű programozási nyelvekben . Számos számítógépes utasításkészlet speciális utasításokat tartalmaz a verem manipulálására.

A hívásköteget több kapcsolódó célra használják, de ennek fő oka annak nyomon követése, hogy az egyes aktív szubrutinoknak vissza kell-e adniuk a vezérlést, amikor befejezik a végrehajtást. Az aktív szubrutin meghívott, de még nem fejeződött be a végrehajtásig, utána a vezérlést vissza kell adni a hívási pontig. A szubrutinok ilyen aktivációi bármilyen szintre beágyazódhatnak (speciális esetben rekurzívak), ezért a verem struktúrája. Például, ha egy alprogram négy különböző helyről DrawSquarehív egy alprogramot DrawLine, DrawLineakkor tudnia kell, hova térjen vissza, amikor a végrehajtása befejeződik. Ennek megvalósításához a címet követő utasítást , hogy ugrik DrawLine, a visszatérési cím , ráhúzzák a tetején a hívási verem minden hívás.

Leírás

Mivel a hívási verem szerveződik, mint a verem , a hívó kitolja a visszatérési címet a verembe, és a hívott szubrutin amikor befejezi, húzás vagy kiugrik a visszatérési címét a hívás verem és átadja a vezérlést a címet. Ha egy hívott szubrutin még egy alprogramot hív meg, akkor egy másik visszaküldési címet tol a hívásverembe, és így tovább, az információk halmozásával és kibontásával, ahogy a program diktálja. Ha a leküldés elfogyasztja a hívásverem számára lefoglalt összes helyet, veremtúlcsordulásnak nevezett hiba lép fel, ami általában a program összeomlását okozza . Egy szubrutin bejegyzésének hozzáadását a hívásveremhez néha "tekercselésnek" nevezik; ellenkezőleg, a bejegyzések eltávolítása "kikapcsolás".

Általában van pontosan egy hívási verem társított futó program (vagy pontosabban, minden egyes feladat vagy menet egy folyamat ), bár további halom lehet létrehozni jel kezelése vagy kooperatív multitasking (mint setcontext ). Mivel csak egy e fontos összefüggésben lehet a továbbiakban a verem (implicite „a feladat”); Azonban a Forth programozási nyelv a adatok stack vagy paraméter stack érhető konkrétabb, mint a hívási verem, és gyakran nevezik a verem (lásd alább).

A magas szintű programozási nyelvek , a pontos részletek a hívási verem általában rejtve maradnak a programozó. Csak bizonyos funkciókhoz férnek hozzá, nem pedig a verem memóriájához. Ez az absztrakció példája . A legtöbb szerelési nyelv viszont megköveteli, hogy a programozók részt vegyenek a verem manipulálásában. A verem tényleges részletei egy programozási nyelven a fordítótól , az operációs rendszertől és az elérhető utasításkészlettől függenek .

A hívásverem funkciói

Amint fentebb említettük, a hívásverem elsődleges célja a visszatérési címek tárolása . Szubrutin meghívásakor valahova el kell menteni annak az utasításnak a helyét (címét), amelyen a hívó rutin később folytatható. 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 feladatnak meg lehet a maga vereme, és így a szubrutin szálbiztos lehet , vagyis egyszerre lehet aktív különböző feladatokhoz, különböző dolgokat végezve. Másik előnye, hogy azáltal, hogy reentrancy , rekurzió automatikusan támogatja. Amikor egy függvény rekurzívan hívja magát, a függvény minden egyes aktiválásához meg kell tárolni egy visszatérési címet, hogy később a funkció aktiválásából visszatérhessen. A veremszerkezetek ezt a képességet automatikusan biztosítják.

A nyelvtől, az operációs rendszertől és a gép környezetétől függően a hívásverem további célokat szolgálhat, például:

Helyi adattárolás
Lásd még: Veremalapú memóriafoglalás
Egy alprogramnak gyakran szüksége van memóriaterületre a helyi változók értékeinek tárolásához , azok a változók, amelyek csak az aktív szubrutinon belül ismertek, és a visszatérés után nem tartják meg az értékeket. Gyakran kényelmes helyet szánni erre a célra úgy, hogy a verem tetejét egyszerűen eléggé elmozdítja a hely biztosításához. Ez nagyon gyors, ha összehasonlítjuk a halomterületet használó dinamikus memória-allokációval . Ne feledje, hogy egy alprogram minden egyes aktiválása külön helyet kap 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 helyet lehet biztosítani a hívásveremben. Általában, ha csak néhány apró paraméter van, processzor regisztereket használnak az értékek továbbításához, de ha több paraméter van, mint amennyit így kezelni lehet, memóriaterületre lesz szükség. A hívásköteg jól működik ezeknek a paramétereknek a helyeként, különösen azért, mert minden alprogramba érkező hívás, amelynek paraméterei eltérő értékekkel bírnak, külön helyet kapnak a hívásveremben ezekhez az értékekhez.
Értékelő verem
A számtani vagy logikai műveletek operandusait leggyakrabban regiszterekbe helyezik és ott működtetik. Bizonyos helyzetekben azonban az operandusok tetszőleges mélységig halmozódhatnak, ami azt jelenti, hogy a regisztereken kívül mást is kell használni (ez a regiszter kiömlésének esete ). Az ilyen operandusok veremét, mint az RPN-kalkulátorban , értékelési veremnek nevezzük, és helyet foglalhatnak a hívásveremben.
Mutató az aktuális példányhoz
Egyes objektumorientált nyelvek (pl. C ++ ) metódusok meghívásakor tárolják ezt a mutatót a függvény argumentumokkal együtt a hívásveremben. Az ezt mutató a tárgy esetben társított módszer lehet hivatkozni.
Szubrutin kontextus bezárása
Egyes programozási nyelvek (pl. Pascal és Ada ) támogatják a beágyazott szubrutinok deklarálását , amelyek hozzáférhetnek a bezáró rutinjaik kontextusához, azaz a külső rutinok körébe tartozó paraméterekhez és lokális változókhoz. Az ilyen statikus fészkelés megismétlődhet - a függvényen belül deklarált függvényen belül deklarált függvény ... A megvalósításnak biztosítania kell egy olyan eszközt, amellyel egy meghívott függvény bármely adott statikus fészkelési szinten hivatkozhat a befoglaló keretre minden befoglaló fészkelési szinten. Általában ezt a hivatkozást a bezáró függvény legutóbb aktivált példányának, az úgynevezett "downstack link" vagy "static link" keretének mutatója valósítja meg, hogy megkülönböztesse azt a "dinamikus linktől", amely a közvetlen hívóra vonatkozik ( amelyek nem feltétlenül a statikus szülőfüggvények).

Statikus hivatkozás helyett a becsatoló statikus keretekre való hivatkozások összegyűjthetők a kijelző néven ismert mutató tömbbe, amelyet indexelnek a kívánt keret megkereséséhez. A rutin lexikális fészkelésének mélysége ismert állandó, ezért a rutin megjelenítésének mérete rögzített. Ezenkívül ismert az átmenő hatókörök száma, a kijelző mutatója szintén rögzített. Általában egy rutin kijelzője a saját veremkeretében található , de a Burroughs B6500 olyan kijelzőt valósított meg hardverben, amely akár 32 statikus fészkelést támogatott.
A hatóköröket jelölő megjelenítési bejegyzéseket a hívó kijelzőjének megfelelő előtagjából kapjuk. A megismétlődő belső rutin minden híváshoz külön híváskeretet hoz létre. Ebben az esetben a belső rutin összes statikus kapcsolata ugyanarra a külső rutinkörnyezetre mutat.
Egyéb visszatérési állapot
A visszaküldési cím mellett bizonyos környezetekben előfordulhatnak más gépi vagy szoftverállapotok, amelyeket vissza kell állítani, amikor egy alprogram visszatér. Ez magában foglalhat például privilégiumszintet, kivételkezelési információkat, számtani módokat és így tovább. Szükség esetén ez tárolható a hívásveremben, éppen úgy, mint a visszatérési cím.

A tipikus hívási verem használják a visszatérési címet, a helyiek, és a paramétereket (más néven a hívást frame ). Bizonyos környezetekben több vagy kevesebb funkció van hozzárendelve a hívásveremhez. Például a Forth programozási nyelvben általában csak a visszatérési címet, a megszámlált hurok paramétereit és indexeit, esetleg lokális változóit tárolják a hívásverem (ezt a környezetet visszatérési veremnek hívják ), bár bármilyen adat ideiglenesen elhelyezhető speciális visszatérési verem kezelési kód használata mindaddig, amíg a hívások és visszajelzések igényeit tiszteletben tartják; A paramétereket általában külön adat- vagy paraméter-veremben tárolják , amelyeket a Forth terminológiában általában veremnek nevezünk, annak ellenére, hogy van hívásverem, mivel ezekhez általában kifejezettebb hozzáférés szükséges. Néhány Forth-nak van egy harmadik vereme is a lebegőpontos paraméterekhez.

Szerkezet

Image
Hívásköteg elrendezés a felfelé növekvő halmokhoz

A hívási verem áll stack frame (más néven aktiválás bejegyzések vagy aktiválás keretek ). Ezek gép- és ABI- függő adatstruktúrák, amelyek szubrutin állapotinformációkat tartalmaznak. Minden veremkeret egy alprogram meghívásának felel meg, amely még nem fejeződött be visszatéréssel. Például, ha DrawLineéppen fut egy nevű szubrutin DrawSquare, amelyet egy szubrutin hívott meg, akkor a hívásverem felső része elrendezhető, mint a szomszédos képen.

Egy ilyen diagram mindkét irányban megrajzolható, amíg a tetejének elhelyezése és így a verem növekedésének iránya megérthető. Ezenkívül ettől függetlenül az architektúrák különböznek abban a tekintetben, hogy a híváshalmazok magasabb vagy alacsonyabb címek felé nőnek-e. A diagram logikája független a címzési választástó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 (push sorrendben):

  • a rutinnak átadott argumentumok (paraméterértékek) (ha vannak ilyenek);
  • a rutin hívójának visszaküldési címe (pl. a DrawLineveremkeretben egy cím a DrawSquarekódjába); és
  • hely a rutin helyi változóinak (ha vannak).

Verem és keret mutatók

Amikor a veremkeretek méretei eltérhetnek, például a különböző funkciók vagy egy adott függvény meghívásai között, akkor a keretnek a veremből való kipattanása nem jelenti a veremmutató fix csökkentését . A függvény visszatérésekor a veremmutató visszaáll a keretmutatóra , a veremmutató értékére közvetlenül a függvény meghívása előtt. Minden veremkeret tartalmaz egy halommutatót a keret tetejére, közvetlenül az után. A veremmutató egy megváltoztatható regiszter, amelyet az összes meghívás megoszt. A függvény adott meghívásának keretmutatója a veremmutató másolata, mint az a függvény meghívása előtt volt.

Az összes többi mező helyét a keretben meghatározhatjuk akár a keret tetejéhez viszonyítva, mint a veremmutató negatív eltolódásaként, vagy pedig az alsó keret tetejéhez viszonyítva, a keretmutató pozitív eltolásaként. Maga a keretmutató helyét eredendően a veremmutató negatív eltolásaként kell meghatározni.

A cím tárolása a hívó keretébe

A legtöbb rendszerben a veremkeretnek van egy mezője, amely tartalmazza a keretmutató regiszter előző értékét, azt az értéket, amely a hívó futtatása közben volt. Például a veremkeret DrawLinememóriahelye megtartja a használt keretmutató értékét DrawSquare(amely nem látható a fenti ábrán). Az érték az alprogramba való belépéskor mentésre kerül, a visszatéréskor pedig helyreáll. Ha egy ilyen mező a veremkeretben egy ismert helyen van, lehetővé teszi a kód számára, hogy egymás után elérje az egyes kereteket az éppen végrehajtó rutin kerete alatt, és lehetővé teszi a rutin számára, hogy a keretmutatót könnyen visszaállítsa a hívó keretébe, még mielőtt visszatérne.

Lexikailag beágyazott rutinok

További információk: Beágyazott függvény és nem lokális változó

A beágyazott szubrutinokat támogató programnyelveknek a híváskeretben van egy olyan mezője is, amely az eljárás legutóbbi aktiválásának veremkeretére mutat, amely a legszorosabban kapszulázza a kagylót, vagyis a kósza közvetlen körét . Ezt nevezzük hozzáférési linknek vagy statikus linknek (mivel a dinamikus és rekurzív hívások során nyomon követi a statikus fészkelést), és minden fészkeléskor biztosítja a rutinszerű (valamint bármely más rutin, amelyre hivatkozhat) hozzáférést a beágyazó rutinjainak helyi adataihoz szint. Egyes architektúrák, fordítók vagy optimalizálási esetek egy-egy linket tárolnak minden egyes bezárási szinthez (nem csak az azonnali bezáráshoz), így a sekély adatokhoz hozzáférő, mélyen beágyazott rutinoknak nem kell több linket bejárniuk; ezt a stratégiát gyakran "kijelzőnek" nevezik.

A hozzáférési linkek akkor optimalizálhatók, ha egy belső függvény nem fér hozzá semmilyen (nem állandó) helyi adathoz a kapszulában, mint például a csak függvényekkel, amelyek csak argumentumokon és visszatérési értékeken keresztül kommunikálnak. Egyes történelmi számítógépek, mint például a Burroughs nagy rendszerek , speciális "megjelenítési regiszterekkel" rendelkeztek az egymásba ágyazott funkciók támogatására, míg a legtöbb modern gép fordítói (például a mindenütt jelen lévő x86-osok) szükség esetén egyszerűen fenntartanak néhány szót a veremben.

Átfedés

Bizonyos célokból az alprogram és a hívójának veremkerete átfedésnek tekinthető, az átfedés abból a területből áll, ahol a paraméterek átkerülnek a hívótól a hívott félig. Bizonyos környezetekben a hívó minden argumentumot a veremre tol, így meghosszabbítja annak veremkeretét, majd meghívja a hívottakat. Más környezetekben a hívónak van egy előre kijelölt területe a veremkeretének tetején, hogy megtartsa azokat az argumentumokat, amelyeket más által meghívott alprogramokhoz továbbít. Ezt a területet néha kimenő argumentum területnek vagy kiemelő területnek nevezik . Ennél a megközelítésnél a fordító úgy számítja ki a terület méretét, hogy az legyen az egyik alprogramnak szükséges legnagyobb.

Használat

Hívási webhely feldolgozása

Általában a szubrutinhoz történő hívás helyén szükséges hívásverem-manipuláció minimális (ami jó, mivel minden hívható alprogramhoz sok hívási hely lehet). A tényleges argumentumok értékeit kiértékelik a hívás helyén, mivel azok az adott hívásra jellemzőek, és vagy a verembe tolják, vagy regiszterekbe helyezik, a használt hívási megállapodás szerint . A tényleges hívási utasítást, például az "elágazást és összekapcsolást", akkor hajtják végre, hogy átvigyék a vezérlést a cél szubrutin kódjára.

Szubrutin bejegyzés feldolgozása

A hívott szubrutinban az első végrehajtott kódot általában szubrutin prológnak nevezik , mivel elvégzi a szükséges háztartást, mielőtt a rutin utasításainak kódja megkezdődik.

Azon utasításkészlet-architektúrák esetében, amelyekben az alprogram meghívására használt utasítás a visszatérési címet egy regiszterbe helyezi, ahelyett, hogy a veremre tolná, a prológus általában elmenti a visszatérési címet azáltal, hogy az értéket a hívásveremre tolja, bár ha a meghívott Az alprogram nem hív más rutinokat, így hagyhatja az értéket a regiszterben. Hasonlóképpen az aktuális veremmutató és / vagy keretmutató értékei tolhatók.

Ha keretmutatókat használnak, akkor a prológ általában a verem mutatóból állítja be a keret mutató regiszter új értékét. A veremben a helyi változók számára helyet akkor lehet felosztani a veremmutató fokozatos megváltoztatásával.

A negyedik programozási nyelv lehetővé teszi a hívásverem (az úgynevezett "visszatérő verem") kifejezett feltekercselését.

Visszatérés feldolgozása

Amikor egy szubrutin készen áll a visszatérésre, egy epilógust hajt végre, amely visszavonja a prológ lépéseit. Ez általában visszaállítja a mentett regiszterértékeket (például a keretmutató értékét) a veremkeretről, a veremmutató értékének megváltoztatásával a teljes veremkeretet leveszi a veremről, és végül elágazik a visszatérési címen lévő utasításhoz. Sok hívási szokás szerint az epilógus által a veremből felbukkanó elemek tartalmazzák az eredeti argumentumértékeket, ebben az esetben általában nincs további veremmanipuláció, amelyet a hívónak el kell végeznie. Egyes hívási konvenciók esetén azonban a hívó felelőssége, hogy a visszatérés után eltávolítsa az érveket a veremből.

Kikapcsolás

A meghívott funkcióból visszatérve a felső keret leugrik a veremről, esetleg visszatérési értéket hagyva. Az általánosabb műveletet, amely szerint egy vagy több keretet kiugrunk a veremből, hogy folytassuk a végrehajtást a program másutt, verem letekerésnek nevezzük, és akkor kell végrehajtani, ha nem lokális vezérlő struktúrákat használnak, például a kivételkezeléshez . Ebben az esetben a függvény veremkerete egy vagy több bejegyzést tartalmaz, amelyek megadják a kivételkezelőket. Kivétel dobásakor a verem addig kerül letekerésre, amíg egy olyan kezelőt nem találnak, amely felkészült a dobott kivétel típusának kezelésére (elkapására).

Néhány nyelv rendelkezik más vezérlési struktúrákkal, amelyek általános kikapcsolást igényelnek. A Pascal lehetővé teszi, hogy egy globális goto utasítás átadja a vezérlést egy beágyazott függvényből egy korábban meghívott külső függvénybe. Ehhez a művelethez szükséges a verem letekerése, annyi veremkeret eltávolítása, amely szükséges ahhoz, hogy helyreállítsa a megfelelő kontextust, hogy az irányítást át lehessen vinni a cél utasításba a melléklő külső függvényen belül. Hasonlóképpen, C-nek vannak setjmpéslongjmp funkciói, amelyek nem lokális gótként működnek. A Common Lisp lehetővé teszi a unwind-protectspeciális operátor használatával, hogy mi történjen a verem letekerésekor .

Folytatás alkalmazásakor a verem (logikusan) letekerésre kerül, majd a folytatás veremével feltekercselhető. Nem ez az egyetlen módja a folytatások megvalósításának; például több, explicit halom használatával a folytatás alkalmazása egyszerűen aktiválhatja a veremét, és feltörheti az átadandó értéket. A Scheme programozási nyelv lehetővé teszi tetszőleges ütések végrehajtását a vezérlőköteg "letekerésén " vagy "visszatekerésénél" meghatározott pontokon, amikor folytatásra kerül sor.

Ellenőrzés

Lásd még: Profilozás (számítógépes programozás)

A hívásverem néha ellenőrizhető a program futása közben. A program írásának és fordításának módjától függően a verem információi felhasználhatók a köztes értékek és a függvényhívás nyomainak meghatározására. Ezt használták finom szemcsés automatizált tesztek előállítására, és olyan esetekben, mint a Ruby és a Smalltalk, az első osztályú folytatások megvalósítására. Például a GNU Debugger (GDB) interaktív vizsgálatot hajt végre egy futó, de szüneteltetett C program híváskötegében.

A hívásverem rendszeres idejű mintavétele hasznos lehet a programok teljesítményének profilozásában, mert ha egy szubrutin mutatója sokszor megjelenik a hívásverem mintavételi adatain, az valószínűleg egy kód szűk keresztmetszete, és ellenőrizni kell a teljesítményproblémák szempontjából.

Biztonság

Fő cikk: Verem puffer túlcsordulás

Szabad mutatókkal vagy nem ellenőrzött tömb-írásokkal (például C-ben) használt nyelven a vezérlő folyamat adatainak keverése, amely befolyásolja a kód (a visszatérési címek vagy az elmentett keretmutatók) és az egyszerű programadatok (paraméterek vagy visszatérési értékek) végrehajtását ) hívás verem a 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 az egyik puffer tetszőleges futtatható kóddal való feltöltését, majd ugyanannak vagy valamilyen más puffernek a túlcsordulását, hogy néhány visszatérési címet felülírjon egy olyan értékkel, amely közvetlenül a futtatható kódra mutat. Ennek eredményeként, amikor a függvény visszatér, a számítógép végrehajtja ezt a kódot. Ez a fajta támadás könnyen blokkolható a W ^ X segítségével . Hasonló támadások még akkor is sikeresek lehetnek, ha engedélyezve van a W ^ X védelem, beleértve a visszatérést a libc-re vagy a visszatérés-orientált programozásból származó támadásokat . Különböző mérsékléseket javasoltak, például tömbök tárolását a visszatérő veremtől teljesen elkülönített helyen, ahogy ez a Forth programozási nyelv esetében is történik.

Lásd még

Hivatkozások

További irodalom

Külső linkek