Call stack

Een call stack (ook wel control stack of run-time stack genoemd) is een datastructuur (een stack of stapel) die in het geheugen van een computer wordt bijgehouden tijdens de uitvoering van een programma.

De call stack wordt gebruikt om twee soorten gegevens op te slaan:

• Gegevens die in het programma gebruikt worden, zoals lokale variabelen.
• Administratieve gegevens die nodig zijn tijdens de uitvoering van het programma, zoals de oude inhoud van registers die tijdelijk hergebruikt worden.

De call stack van een programma wordt bijgehouden door het programma zelf. De machinecode die hiervoor verantwoordelijk is wordt door de compiler tijdens de compilatie gegenereerd. De programmeur die een programma schrijft hoeft hier zelf geen rekening mee te houden.

Sommige assemblerinstructies manipuleren de call stack expliciet (bijvoorbeeld met POP en PUSH instructies) of impliciet (bijvoorbeeld CALL en RET, die het retouradres op de stack plaatsen en er weer afhalen).

Activation frames

De call stack (of kortweg stack) bestaat uit activation frames (ook wel activation records of stack frames genoemd) van wisselende grootte. Voor iedere actieve instantie van een subroutine (of functie, of procedure) bevat de stack een activation frame. Een actieve instantie van een subroutine ontstaat wanneer de subroutine aangeroepen wordt en eindigt wanneer de subroutine eindigt. De subroutine kan op zijn beurt andere subroutines aanroepen. Omdat er meer actieve instanties van dezelfde subroutine kunnen zijn, bijvoorbeeld in het geval van recursie, kunnen er op de stack meerdere activation frames aanwezig zijn die bij dezelfde subroutine horen (maar bij verschillende actieve instanties van die subroutine).

Verschillende actieve instanties van subroutines zijn niet-overlappend of ze zijn genest. Twee actieve subroutines zijn niet-overlappend als ze op geen enkel moment tegelijk actief zijn. Twee actieve subroutines 'a' en 'b' zijn genest als geldt dat wanneer 'a' actief wordt voordat 'b' actief wordt, dat 'b' eerder eindigt dan 'a'.

Wanneer een programma start is de stack leeg. Telkens als er een subroutine aangeroepen wordt, wordt er een nieuw frame op de top van de stack geplaatst. Het frame dat bij de meest recent gestarte subroutine hoort bevindt zich dus altijd op de top van de stack. Wanneer een subroutine eindigt wordt zijn frame van de top van de stack verwijderd. Nu bevindt het frame van de aanroepende subroutine, die nu weer verdergaat met zijn uitvoering, zich op de top van de stack. Dit werkt omdat subroutines altijd niet-overlappend of genest zijn: de subroutine die als laatste begonnen is, is altijd als eerste klaar en zijn frame bevindt zich dus altijd op de top van de stack.

Voor het benaderen van de stack en het huidige frame zijn er een of meer speciale registers in de processor aanwezig. Hoeveel dit zijn en welke dit zijn verschilt per processorarchitectuur, maar meestal is sprake van een stackpointer en een framepointer (ook wel basepointer of local basepointer genoemd). In de Intel x86-architectuur zijn hiervoor de registers SP (stackpointer) en BP (basepointer) beschikbaar. De stackpointer SP wijst altijd naar de top van de stack (en wordt door sommige machine-instructies zoals POP en PUSH automatisch verhoogd respectievelijk verlaagd). De framepointer BP wijst naar het begin van het huidige activation frame. Het huidige frame bestaat dan altijd uit het gedeelte van de stack dat zich tussen het adres in SP (de top) en het adres in BP bevindt.

Proloog, epiloog, contextwisselingen en stackpointers

Als de compiler een subroutine compileert voegt hij aan het begin en aan het eind van de subroutine extra code toe: een 'proloog' (of function prologue) aan het begin en een epiloog (of function epilogue) aan het eind van de routine. Daarnaast wordt er ook extra code gegenereerd voor en na iedere subroutine-aanroep. De code die uitgevoerd wordt voordat een nieuwe subroutine actief wordt, wordt de calling sequence genoemd en de code die uitgevoerd nadat de subroutine klaar is wordt de return sequence genoemd. Samen zorgen deze vier codefragementen voor alle administratieve taken die uitgevoerd moeten worden als er een nieuwe subroutine wordt aangeroepen of een lopende routine klaar is en het programma terugkeert naar de plek waar ze gebleven was in de aanroepende code.

Het moment dat een nieuwe subroutine actief wordt en het moment dat een subroutine klaar is en het programma terugkeert naar de aanroepende code worden contextwisselingen genoemd. Hoe het werk verdeeld wordt tussen de aanroepende code (in de calling sequence en de returning sequence) en de aangeroepen routine (in de proloog en de epiloog) verschilt per architectuur en de programmeertaal waarin het programma geschreven is. In het algemeen gebeurt er het volgende:

Als een subroutine aangeroepen wordt, wordt de calling sequence in de aanroepende code actief. Deze zorgt voor

• het berekenen van de actuele waarden van de door te geven parameters en het op de juiste plaats zetten ervan (op de stack of in registers),
• het opzoeken van het adres van de code van de aan te roepen routine,
• het opslaan van de inhoud registers die nog in gebruik zijn,
• het opslaan van het adres van de instructie waar het programma bij terugkeer verdergaat (het returnadres)
• en het overdragen van de besturing aan de subroutine door middel van bijvoorbeeld een CALL-instructie.

Het adres van de subroutinecode wordt nu in het instructieregister gezet waarmee de aangeroepen subroutine actief wordt. Deze begint met het uitvoeren van de proloog, die

• de huidige waarde van de framepointer opslaat en de nieuwe framepointer naar de top van de stack laat wijzen (wat nu het tevens het begin van het nieuwe frame is),
• en de nieuwe waarde van de stackpointer berekent en deze in het stackregister plaatst waarmee het nieuwe frame klaar is voor gebruik.

Nu wordt de subroutine zelf actief. Nadat deze zijn werk gedaan heeft, wordt vervolgens de epiloog uitgevoerd. Deze

• zet een eventuele returnwaarde op de juiste plaats (op de stack of in een register),
• kopieert de waarde van de framepointer naar de stackpointer en zet de oude, opgeslagen, waarde van de framepointer terug,
• haalt het returnadres van de stack en zet deze in de instructionpointer.

De aanroepende code is nu weer actief en de return sequence wordt uitgevoerd. Deze

• zet de oude waarden van gebruikte registers terug en
• haalt de returnwaarde op om deze vervolgens te gebruiken.

Sommige processors hebben speciale instructies, die een deel van het werk in de proloog en epiloog uitvoeren. Zo hebben Intel processoren een ENTER en LEAVE instructie voor respectievelijk de proloog en de epiloog en processoren van Motorola hebben hiervoor de LINK- en UNLK-instructies.

Inhoud

Een stack waarbij een routine DrawLine actief is, aangeroepen door DrawSquare. Aangegeven zijn de plaats van de parameters, het returnadres en de lokale variabelen. De stackpointer wijst naar de top van de stack en de framepointer naar een plek in het actieve stackframe. Merk op dat de stack zoals gebruikelijk van beneden naar boven weergegeven is, met de top bovenaan. In werkelijkheid zit de stack in het geheugen omgekeerd: met de top lager in het geheugen.

Welke informatie er in de activation frames wordt opgeslagen verschilt per processorarchitectuur. Deze bevat meestal in ieder geval de volgende onderdelen:

1. Programmagegevens

Lokale variabelen

Omdat lokale variabelen alleen gebruikt worden in de subroutine waarin ze gedeclareerd zijn, worden ze op de stack opgeslagen. Als een routine eindigt, worden de lokale variabelen samen met de rest van het frame verwijderd en daarmee is het door de variabelen gebruikte geheugen weer vrijgegeven. Omdat lokale variabelen in het frame worden opgeslagen, hebben verschillende actieve instanties van dezelfde subroutine (die elk immers hun eigen frame hebben) hun eigen set lokale variabelen. Hierdoor kan de programmeur gebruikmaken van recursieve functies.

Functieparameters

Wanneer een routine een andere routine aanroept, zet deze de parameters die aan de aangeroepen routine doorgegeven moeten worden in zijn eigen frame of (afhankelijk van de gebruikte conventies) in het frame van de aangeroepen procedure. In de praktijk worden parameters overigens zo veel mogelijk via registers doorgegeven omdat dit sneller is. Welke parameters via registers doorgegeven kunnen worden, wordt door de compiler bepaald.

Returnwaarden

Returnwaarden worden, wanneer deze niet via een register worden doorgegeven, doorgegeven via de stack. De aangeroepen routine plaatst zijn returnwaarde direct boven het frame van de aanroepende routine.

2. Administratieve gegevens

Statusinformatie

Wanneer een nieuwe subroutine start moet de processor bepaalde gegevens over de huidige status van het programma opslaan omdat deze na afloop van de routine weer nodig zijn. Hiertoe behoort onder andere de huidige inhoud van de instructionpointer (het register dat het geheugenadres van de volgende uit te voeren instructie bevat; in de x86-architectuur is dat het EIP-register). Wanneer een routine aangeroepen wordt, wordt de waarde van de instructionpointer op de stack opgeslagen en de instructionpointer wordt gevuld met het adres van de routine die aangeroepen wordt. Als die routine klaar is, moet de oude waarde van de instructionpointer (het returnadres) hersteld worden zodat de uitvoering in de aanroepende routine weer verdergaat. Ook de huidige waarde van de frame- of basepointer wordt opgeslagen voordat deze naar het begin van het nieuwe frame gaat wijzen.

Opgeslagen registers

Als een subroutine een andere subroutine aanroept die gebruikmaakt van een aantal van dezelfde registers en de aanroepende routine heeft de waarden in deze registers later nog nodig, dan moeten deze waarden tijdelijk worden opgeslagen zodat de registers na terugkeer uit de aangeroepen routine in oude staat hersteld kunnen worden. Welke registers wanneer opgeslagen moeten worden, wordt door de compiler bepaald tijdens de registerallocatie.

Tussentijdse resultaten

Dit zijn gegevens die de gegenereerde machinecode gebruikt bij zijn berekeningen. Deze worden opgeslagen in zogenaamde tempories. De compiler bepaalt tijdens de codegeneratie hoeveel tempories een routine nodig heeft en reserveert hiervoor de benodigde ruimte in het frame.

Plaats

Wanneer een programma gestart wordt, krijgt het van het besturingssysteem een deel van het geheugen toegewezen. Dit geheugen wordt ingedeeld in een aantal segmenten. Welke dit zijn hangt af van het systeem en het soort programma maar in ieder geval zijn er een codesegment (waar het programma zelf zich bevindt, d.w.z. de instructies waaruit het programma bestaat), een stacksegment en een datasegment aanwezig.

Het stacksegment en het datasegment vormen samen het werkgeheugen waar het programma over kan beschikken. Het datasegment vormt de heap en wordt door het programma gebruikt voor globale data (zoals globale variabelen en constanten) en voor dynamische geheugenallocatie. Het stacksegment wordt door het programma gebruikt voor de call stack.

Om voornamelijk historische redenen begint de stack op de meeste systemen (waaronder de Intel, de SPARC en de MIPS) 'bovenin' het stacksegment en 'groeit' ze naar beneden (richting lagere geheugenadressen). Dat wil zeggen dat het meeste recente frame zich op de laagste geheugenadressen bevindt.

Efficiëntie

Over het algemeen leent het systeem van de call stack zich goed voor de compilatie en uitvoering van moderne imperatieve en objectgeoriënteerde programmeertalen. Soms laat de efficiëntie echter te wensen over omdat er veel code nodig is voor het afhandelen van de contextwisselingen. Bij kleine subroutines die vaak worden aangeroepen kan het zijn dat het programma meer bezig is met het bijhouden van de stack dan met het uitvoeren van de routines zelf. Om deze situatie te optimaliseren wordt gebruikgemaakt van verschillende methoden.

De programmeur kan ervoor kiezen om het aantal subroutine-aanroepen te verminderen. Bijvoorbeeld door in plaats van voor een recursief algoritme voor een lineair algoritme, gebaseerd op een lus, te kiezen. Daarnaast kan zij gebruikmaken van preprocessormacro's als de brontaal deze ondersteund.

Daarnaast zorgen veel compilers voor vergaande optimalisatie. Hieronder valt ook het zogenaamde function inlining waarbij de aanroepen van kleine, veelgebruikte subroutines vervangen worden door de functionaliteit van de subroutine zelf. Recursieve subroutines die staartrecursie bevatten kunnen geoptimaliseerd worden door stack frames opnieuw te gebruiken in plaats van telkens een nieuwe te maken.

Veiligheid

Een veelvoorkomende klasse beveiligingslekken richt zich specifiek op de stack. Bij programmeertalen (in de praktijk meestal C) die het gebruik van pointers mogelijk maken of die bij het gebruik van arrays de lengte niet controleren, kan bij onzorgvuldig programmeren de mogelijkheid van een bufferoverloop (buffer overflow) ontstaan. Wanneer de betreffende buffer lokaal in een subroutine gedeclareerd is, wordt hij in het frame van deze routine opgeslagen. Het gevolg is dat bij een bufferoverloop andere gegevens in het frame overschreven worden. Omdat de stack op de meeste systemen van hogere naar lagere geheugenadressen groeit, maar de gegevens in arrays van lagere naar hogere adressen opgeslagen worden, ontstaat de mogelijkheid om behalve lokale variabelen ook administratieve gegevens in het frame te overschrijven. Dit wordt wel "smashing the stack" genoemd.

Het grootste gevaar ontstaat door de mogelijkheid van het overschrijven van het in het frame opgeslagen terugkeeradres. Wanneer er sprake is van mogelijke bufferoverloop kan een hacker een zorgvuldig samengestelde invoer samenstellen die gevaarlijke machinecode bevat en tevens het returnadres in de stack overschrijft met het adres van deze machinecode in de buffer. Het gevolg is dat wanneer de routine eindigt de uitvoering van het programma niet verdergaat in de code die de routine aanriep maar in de door de hacker opgegeven code.

Alternatieven: statisch en heap-dynamisch

Het gebruik van een stack voor het beheren van activation frames kunnen we stack-dynamisch noemen, ter onderscheid van de mogelijke alternatieven. We spreken over 'dynamisch' omdat het creëren en afbreken van activation frames tijdens de uitvoer van het programma (runtime) plaatsvindt. Tijdens het compileren van het programma (compile time) weet de compiler niet waar de verschillende activation frames zich zullen bevinden. De compiler produceert daarom extra code voor het beheren van de stack tijdens runtime. Twee alternatieve strategieën zijn statische allocatie van frames en heap-dynamische allocatie van frames.

Bij statische allocatie van activation frames bepaalt de compiler tijdens compilatie waar de activation frames van alle subprogramma's zich in het geheugen zullen bevinden. De activation frames van alle functies krijgen een vaste plek. Omdat de compiler weet waar het frame van iedere functie zich bevindt en ook waar de verschillende lokale variabelen zich in de activation frames bevinden, weet de compiler waar iedere variabele zich bevindt. Het dynamisch beheren van activation frames is niet nodig en hiervoor hoeft geen extra code gegenereerd te worden. De voordelen van statische allocatie van activation frames is dat deze methode eenvoudiger en efficiënter is. De compiler kan eenvoudiger gehouden worden en het gecompileerde programma is efficiënter omdat er minder extra code uitgevoerd hoeft te worden.

Het belangrijkste nadeel van statische allocatie is het gebrek aan ondersteuning voor recursie. Omdat ieder subprogramma één frame heeft dat telkens opnieuw gebruikt wordt, mag er op ieder moment maar één instantie van ieder subprogramma actief zijn. De eerste versies van Fortran waren zo ontworpen dat Fortran-compilers gebruik konden maken van statische allocatie van activition frames. Het gebruik van recursieve subprogramma's werd geïntroduceerd in Fortran 90 (hoewel sommige implementaties van Fortran 77 het gebruik van recursie ook al mogelijk maakten).

Een tweede alternatief voor stack-dynamische allocatie van activation frames is heap-dynamische allocatie van activition frames. Bij heap-dynamische allocatie worden de frames niet op een stack geplaatst, maar wordt er iedere keer dat een subprogramma actief wordt en er een nieuw activation frame voor dat subprogramma gecreëerd moet worden, een nieuw stuk vrij geheugen gereserveerd (gealloceerd). Het op aanvraag reserveren van geheugenblokken en het weer vrijmaken ervan gebeurt door een heap manager. De heap manager is in feite extra code die door de compiler gegenereerd wordt voor het beheren van het heap-geheugen. Voor talen die dynamische geheugenallocatie toestaan (bijvoorbeeld door middel van een speciale malloc-functie zoals in C of door middel van dynamische creatie van objecten zoals in Java) moet de code voor beheren van de heap toch al aanwezig zijn en vormt dit dus geen probleem. Heap-dynamische allocatie vergt echter meer overhead en is daarom minder efficiënt dan stack-dynamische en statische allocatie.

Vrijwel alle moderne gangbare programmeertalen maken gebruik van stack-dynamische allocatie van activation frames. Deze wordt echter ook vaak gecombineerd met de genoemde alternatieven die worden ingezet 'waar nodig'. Er zijn namelijk situaties waarvoor stack-dynamische allocatie niet geschikt is. Dit geldt bijvoorbeeld wanneer een subprogramma langer actief kan zijn dan het aanroepende subprogramma, wanneer bepaalde variabelen in een subprogramma hun waarde moeten behouden tussen verschillende aanroepen van dat subprogramma (dit soort variabelen worden soms 'statische' genoemd) of wanneer een functie een closure retourneerd.

Bronnen, noten en/of referenties

• Compilers: principles, techniques and tools, Alfred V. Aho, Ravi Sethi en Jeffrey D. Ullman, Addison-Wesley, 1988, ISBN 0201100886
• Modern Compiler Implementation in Java, 2e editie, Andrew W. Appel, Cambridge University Press, 2002, ISBN 052182060X
• Advanced Compiler Design & Implementation, S.S. Muchnick, Morgan Kaufmann Publishers, 1997, ISBN 1558603204

Voetnoten