WikiDer > Aufrufliste

EIN Aufrufliste (ebenfalls Kontrollstapel oder Laufzeitstapel genannt) ist a Datenstruktur (ein Stapel oder Stack) im Speicher von a . gespeichert Computer wird während der Ausführung von a . verfolgt Programm.

Das Aufrufliste wird verwendet, um zwei Arten von Daten zu speichern:

• Im Programm verwendete Daten, z. B. local Variablen.
• Administrative Daten, die während der Programmausführung benötigt werden, wie der alte Inhalt von old registriert die vorübergehend wiederverwendet werden.

Das Aufrufliste eines Programms wird vom Programm selbst verwaltet. Das Maschinensprache wer dafür verantwortlich ist soll sein Compiler während der Kompilierung erzeugt. Der Programmierer, der ein Programm schreibt, muss dies nicht berücksichtigen.

Etwas Montageanleitung manipulieren Aufrufliste explizit (z. B. mit POP und DRÜCKEN Anweisungen) oder implizit (zum Beispiel ANRUF und RET, die die Rücksendeadresse auf den Stack legen und wieder entfernen).

Aktivierungsrahmen

Das Aufrufliste (oder einfach Stapel) besteht aus Aktivierungsrahmen (ebenfalls Aktivierungsdatensätze oder Stapelrahmen genannt) unterschiedlicher Größe. Für jede aktive Instanz von a Subroutine (oder Funktion oder Prozedur) enthält die Stapel ein Aktivierungsrahmen. Eine aktive Instanz eines Unterprogramms entsteht, wenn das Unterprogramm aufgerufen wird und endet, wenn das Unterprogramm endet. Das Unterprogramm kann wiederum andere Unterprogramme aufrufen. Weil es mehrere aktive Instanzen desselben Unterprogramms geben kann, zum Beispiel im Fall von Rekursion, es kann auf der sein Stapel mehrere Aktivierungsrahmen die zum selben Unterprogramm gehören (aber verschiedene aktive Instanzen dieses Unterprogramms).

Mehrere aktive Instanzen von Unterprogrammen sind nicht überlappend oder verschachtelt. Zwei aktive Unterprogramme sind nicht überlappend, wenn sie zu keiner Zeit gleichzeitig aktiv sind. Zwei aktive Unterprogramme 'a' und 'b' werden verschachtelt, wenn 'a' aktiv wird, bevor 'b' aktiv wird, dann 'b' vor 'a' endet.

Wenn ein Programm startet, wird die Stapel leer. Jedes Mal, wenn ein Unterprogramm aufgerufen wird, wird ein neuer Rahmen oben auf den Stapel gelegt. Der dem zuletzt gestarteten Unterprogramm zugeordnete Rahmen steht daher immer ganz oben auf dem Stapel. Wenn ein Unterprogramm endet, wird sein Rahmen vom Anfang des . entfernt Stapel gelöscht. Nun steht der Rahmen des aufrufenden Unterprogramms, das nun seine Ausführung fortsetzt, über dem Stapel. Dies funktioniert, weil Unterroutinen immer nicht überlappend oder verschachtelt sind: Die zuletzt gestartete Unterroutine endet immer zuerst, sodass ihr Rahmen immer ganz oben im Stapel steht.

Um auf die zuzugreifen Stapel und dem aktuellen Frame gibt es ein oder mehrere Sonderregister im Prozessor vorhanden. Wie viele es sind und welche es sind, unterscheidet sich je nach Prozessorarchitektur, aber normalerweise gibt es eine Stapelzeiger und ein Rahmenzeiger (ebenfalls Basiszeiger oder lokaler Basiszeiger erwähnt). In dem Intel x86Architektur sind die Register dafür SP (Stapelzeiger) und BP (Basiszeiger) verfügbar^[1]. Das Stapelzeiger SP zeigt immer auf die Spitze des Stapel (und wird von einigen Maschinenanweisungen verwendet, wie z POP und DRÜCKEN automatisch erhöht bzw. verringert). Das Rahmenzeiger BP zeigt auf den Anfang des aktuellen Aktivierungsrahmens.^[2] Der aktuelle Rahmen besteht dann immer aus dem Teil des Stapels, der zwischen der Adresse in SP (oben) und der Adresse in BP liegt.

Prolog, Epilog, Kontextwechsel und Stackpointer

Wenn der Compiler eine Subroutine kompiliert, fügt er zusätzlichen Code am Anfang und Ende der Subroutine hinzu: einen 'Prolog' (oder Funktionsprolog) am Anfang und ein Epilog (oder Funktions-Epilog) am Ende der Routine. Außerdem wird vor und nach jedem Unterprogrammaufruf zusätzlicher Code generiert. Der Code, der ausgeführt wird, bevor ein neues Unterprogramm aktiv wird, heißt der Aufrufreihenfolge aufgerufen und der Code, der nach Beendigung der Subroutine ausgeführt wird, heißt der Rückreihenfolge erwähnt. Zusammen erledigen diese vier Codefragmente alle administrativen Aufgaben, die ausgeführt werden müssen, wenn eine neue Subroutine aufgerufen oder eine laufende Routine beendet wird und das Programm an die Stelle zurückkehrt, an der es im aufrufenden Code aufgehört hat.

In dem Moment, in dem ein neues Unterprogramm aktiv wird und in dem Moment, in dem ein Unterprogramm endet und das Programm zum aufrufenden Code zurückkehrt, sind Kontextänderungen erwähnt. Aufteilung der Arbeit auf den Aufrufcode (im Aufrufreihenfolge und der Rückreihenfolge) und die aufgerufene Routine (im Prolog und Epilog) unterscheidet sich durch die Architektur und die Programmiersprache, in der das Programm geschrieben ist. Im Allgemeinen passiert Folgendes:

Beim Aufruf eines Unterprogramms wird die Aufrufreihenfolge aktiv im Anrufcode. Dies stellt sicher

• die tatsächlichen Werte der zu übergebenden Parameter berechnen und an der richtigen Stelle platzieren (auf dem Stack oder in Registern),
• nachschauen Adresse des Codes der aufzurufenden Routine,
• Speicherung der noch verwendeten Inhaltsregister,
• Speichern der Adresse der Anweisung, bei der das Programm bei der Rückkehr fortgesetzt wird (die Rückkehradresse)
• und Übertragen der Steuerung an das Unterprogramm, beispielsweise durch einen CALL-Befehl.

Die Adresse des Unterprogrammcodes wird nun im Befehlsregister set, das das aufgerufene Unterprogramm aktiviert. Es beginnt mit der Aufführung des Prologs, der

• speichert den aktuellen Wert des Rahmenzeigers und zeigt den neuen Rahmenzeiger an die Spitze des Stapels (der jetzt auch der Anfang des neuen Rahmens ist),
• und berechnet den neuen Wert aus dem Stapelzeiger und platziert ihn in dem Stapelregister, um den neuen Rahmen gebrauchsfertig zu machen.

Jetzt wird das Unterprogramm selbst aktiv. Nachdem dieser seine Aufgabe erfüllt hat, wird dann der Epilog durchgeführt. Dieses

• jeden Rückgabewert an der richtigen Stelle platzieren (auf dem Stack oder in einem Register),
• kopiert den Wert vom Frame-Pointer auf den Stack-Pointer und stellt den alten, gespeicherten Wert vom Frame-Pointer wieder her,
• holt sich die Rücksprungadresse vom Stack und legt sie in den Instruktionszeiger.

Der aufrufende Code ist nun wieder aktiv und die Rückgabesequenz wird ausgeführt. Dieses

• die alten Werte der verwendeten Register wiederherstellen und
• ruft den Rückgabewert ab und verwendet ihn dann.

Einige Prozessoren haben spezielle Anweisungen, die einen Teil der Arbeit im Prolog und Epilog erledigen. Intel-Prozessoren haben zum Beispiel a EINGEBEN und VERLASSEN Anweisungen für den Prolog bzw. Epilog und die Prozessoren von Motorola habe den VERKNÜPFUNG- und UNLKAnleitung.

Inhalt

Ein Stack, wo eine Routine Linie zeichnen ist aktiv, aufgerufen von DrawQuadrat. Angegeben sind die Position der Parameter, die Rücksprungadresse und die lokalen Variablen. Der Stapelzeiger zeigt auf die Spitze des Stapels und der Rahmenzeiger zeigt auf eine Stelle im aktiven Stapelrahmen. Beachten Sie, dass der Stapel wie üblich von unten nach oben angezeigt wird, mit der Spitze nach oben. In Wirklichkeit ist der Stapel im Speicher umgekehrt: mit der Oberseite unten im Speicher.

Welche Informationen in den Aktivierungsframes gespeichert werden, unterscheidet sich je nach Prozessorarchitektur. Diese enthält in der Regel mindestens die folgenden Teile:

1. Programmdetails

Lokal Variablen

Da lokale Variablen nur in dem Unterprogramm verwendet werden, in dem sie deklariert sind, werden sie auf dem Stack gespeichert. Wenn eine Routine endet, werden die lokalen Variablen zusammen mit dem Rest des Rahmens entfernt, wodurch der von den Variablen verwendete Speicher freigegeben wird. Da lokale Variablen im Rahmen gespeichert werden, haben verschiedene aktive Instanzen desselben Unterprogramms (von denen jede ihren eigenen Rahmen hat) ihren eigenen Satz lokaler Variablen. Dies ermöglicht dem Programmierer, rekursive Funktionen zu verwenden.

Funktionsparameter

Wenn eine Routine eine andere Routine aufruft, legt sie die an die aufgerufene Routine zu übergebenden Parameter in einen eigenen Rahmen oder (je nach verwendeten Konventionen) in den Rahmen der aufgerufenen Prozedur. In der Praxis werden Parameter weitestgehend über Register übergeben, da dies schneller geht. Welche Parameter über Register übergeben werden können, bestimmt der Compiler.

Rückgabewerte

Rückgabewerte werden, wenn sie nicht durch ein Register geleitet werden, durch den Stack geleitet. Die aufgerufene Routine platziert ihren Rückgabewert direkt über dem Rahmen der aufrufenden Routine.

2. Verwaltungsdaten

Statusinformationen

Beim Start eines neuen Unterprogramms muss der Prozessor bestimmte Informationen über den aktuellen Zustand des Programms speichern, da diese nach dem Unterprogramm wieder benötigt werden. Dazu gehören die aktuellen Inhalte der Anweisungszeiger (das Register, das die Speicheradresse des nächsten auszuführenden Befehls enthält; in der x86-Architektur ist es EIPregistrieren). Wenn eine Routine aufgerufen wird, wird der Wert des Befehlszeigers auf dem Stapel gespeichert und der Befehlszeiger wird mit der Adresse der aufgerufenen Routine gefüllt. Wenn diese Routine abgeschlossen ist, wird der alte Wert des Instruktionszeigers (der Absender) werden wiederhergestellt, so dass die Ausführung in der aufrufenden Routine wieder aufgenommen wird. Es speichert auch den aktuellen Wert des Rahmens oder Basiszeigers, bevor er auf den Anfang des neuen Rahmens zeigt.

Gespeicherte Register

Wenn ein Unterprogramm ein anderes Unterprogramm unter Verwendung einiger derselben Register aufruft und die aufrufende Routine später die Werte in diesen Registern benötigt, müssen diese Werte zwischengespeichert werden, damit die Register nach der Rückkehr aus dem aufgerufenen wieder in ihren ursprünglichen Zustand zurückversetzt werden können Routine verwandeln. Welche Register wann gespeichert werden sollen, bestimmt der Compiler während der Registerzuordnung.

Zwischenresultate

Dies sind Daten, die der generierte Maschinencode bei seinen Berechnungen verwendet. Diese werden in sog provisorien. Bei der Codegenerierung ermittelt der Compiler, wie viele Tempories eine Routine benötigt und reserviert dafür den nötigen Platz im Frame.

Platz

Wenn ein Programm gestartet wird, empfängt es Betriebssystem zugewiesenen Teil des Speichers. Dieser Speicher ist in mehrere Segmente unterteilt. Welche das sind, hängt vom System und der Art des Programms ab, aber in jedem Fall gibt es ein Codesegment (wo sich das Programm selbst befindet, also die Anweisungen, aus denen das Programm besteht), ein Stack-Segment und ein Datensegment.

Das Stack-Segment und das Datensegment bilden zusammen den dem Programm zur Verfügung stehenden Arbeitsspeicher. Das Datensegment bildet die Haufen und wird vom Programm für globale Daten (wie globale Variablen und Konstanten) und für die dynamische Speicherzuweisung verwendet. Das Stack-Segment wird vom Programm für den Call-Stack verwendet.

Aus hauptsächlich historischen Gründen startet der Stack auf den meisten Systemen (einschließlich der Intel, das SPARC und der MIPS) 'an der Spitze' des Stack-Segments und 'wächst' es nach unten (in Richtung niedrigerer Speicheradressen). Das heißt, der jüngste Rahmen befindet sich in den niedrigsten Speicheradressen.

Effizienz

Im Allgemeinen eignet sich das Call-Stack-System gut zum Kompilieren und Ausführen moderner Imperativ und objektorientierten Programmiersprachen. Manchmal lässt die Effizienz jedoch zu wünschen übrig, da viel Code benötigt wird, um die Kontextänderungen zu handhaben. Bei kleinen Unterprogrammen, die häufig aufgerufen werden, ist das Programm möglicherweise mehr damit beschäftigt, den Stapel zu verwalten, als die Routinen selbst auszuführen. Um diese Situation zu optimieren, werden verschiedene Methoden verwendet.

Der Programmierer kann die Anzahl der Unterprogrammaufrufe reduzieren. Zum Beispiel durch statt für a rekursivAlgorithmus für einen linearen Algorithmus, basierend auf a Schleife, wählen. Außerdem kann sie Präprozessor-Makros wenn die Quellsprache dies unterstützt.

Darüber hinaus bieten viele Compiler weitreichende Optimierung. Dazu gehören auch die sog Funktion Inlining wobei die Aufrufe kleiner, häufig verwendeter Unterprogramme durch die Funktionalität des Unterprogramms selbst ersetzt werden. Rekursive Unterprogramme, die Schwanzrekursion enthalten kann optimiert werden, indem Stack-Frames wiederverwendet werden, anstatt jedes Mal einen neuen zu erstellen.

Sicherheit

Eine gemeinsame Klasse Sicherheitslücken konzentriert sich speziell auf den Stapel. Für Programmiersprachen (in der Praxis meist C) erfordert die Verwendung von Zeiger ermöglichen oder das bei der Verwendung Arrays Wenn Sie die Länge nicht überprüfen, kann es durch unachtsames Programmieren zu einem Pufferüberlauf (Pufferüberlauf) stammen. Wenn der betreffende Puffer lokal in einer Unterroutine deklariert wird, wird er im Rahmen dieser Routine gespeichert. Als Ergebnis überschreibt ein Pufferüberlauf andere Daten im Rahmen. Da bei den meisten Systemen der Stack von höheren zu niedrigeren Speicheradressen anwächst, die Daten aber in Arrays von niedrigeren zu höheren Adressen gespeichert werden, ergibt sich die Möglichkeit, neben lokalen Variablen auch administrative Daten im Frame zu überschreiben. Das wird sein "den Stapel zerschlagen" erwähnt.

Die größte Gefahr geht von der Möglichkeit aus, die im Frame gespeicherte Rücksendeadresse zu überschreiben. Bei einem möglichen Pufferüberlauf a Hacker einen sorgfältig gestalteten Eintrag erstellen, der gefährlichen Maschinencode enthält und auch die Rücksprungadresse im Stack mit der Adresse dieses Maschinencodes im Puffer überschreibt. Als Ergebnis wird die Ausführung des Programms nach Beendigung der Routine nicht in dem Code fortgesetzt, der die Routine aufgerufen hat, sondern in dem vom Hacker angegebenen Code.

Alternativen: Statisch und Heap Dynamic

Wir können einen Stack verwenden, um Aktivierungsframes zu verwalten stapeldynamisch von den möglichen Alternativen zu unterscheiden. Wir sprechen von 'dynamisch', weil das Erstellen und Brechen von Aktivierungsframes während der Programmausführung (Laufzeit) stattfinden. Beim Kompilieren des Programms (Kompilierzeit) weiß der Compiler nicht, wo sich die verschiedenen Aktivierungsframes befinden. Der Compiler erzeugt daher zusätzlichen Code, um den Stack zur Laufzeit zu verwalten. Zwei alternative Strategien sind die statische Zuweisung von Rahmen und die dynamische Haufenzuweisung von Rahmen.

Biene statische Zuordnung der Aktivierungsframes bestimmt der Compiler während der Kompilierung, wo sich die Aktivierungsframes aller Unterprogramme im Speicher befinden. Die Aktivierungsrahmen aller Funktionen erhalten einen festen Platz. Da der Compiler weiß, wo sich der Rahmen jeder Funktion befindet und wo sich die verschiedenen lokalen Variablen in den Aktivierungsrahmen befinden, weiß der Compiler, wo sich jede Variable befindet. Eine dynamische Verwaltung von Aktivierungsframes ist nicht erforderlich und es muss kein zusätzlicher Code dafür generiert werden. Der Vorteil der statischen Zuweisung von Aktivierungsrahmen besteht darin, dass dieses Verfahren einfacher und effizienter ist. Der Compiler kann einfacher gehalten werden und das kompilierte Programm ist effizienter, da weniger zusätzlicher Code ausgeführt werden muss.

Der Hauptnachteil der statischen Zuweisung ist die fehlende Unterstützung für Rekursion. Da jedes Unterprogramm einen Rahmen hat, der immer wieder verwendet wird, sollte zu jedem Zeitpunkt nur eine Instanz jedes Unterprogramms aktiv sein. Die ersten Versionen von fortran wurden so konzipiert, dass Fortran-Compiler eine statische Zuweisung von Aktivierungsrahmen verwenden können. Die Verwendung rekursiver Unterprogramme wurde in Fortran 90 eingeführt (obwohl einige Implementierungen von Fortran 77 bereits die Verwendung von Rekursion erlaubten).

Eine zweite Alternative für die stapeldynamische Zuweisung von Aktivierungsrahmen ist dynamische Heap-Zuweisung von Aktivierungsrahmen. Bei der dynamischen Heap-Allokation werden die Frames nicht auf einen Stack gelegt, sondern jedes Mal, wenn ein Unterprogramm aktiv wird und ein neuer Aktivierungsframe für dieses Unterprogramm erstellt werden muss, ein neuer freier Speicher reserviert (zugewiesen). Das Reservieren von Speicherblöcken bei Bedarf und das erneute Freigeben erfolgt durch a Heap-Manager. Der Heap-Manager ist im Grunde ein zusätzlicher Code, der vom Compiler zum Verwalten des Heap-Speichers generiert wird. Für Sprachen, die eine dynamische Speicherzuweisung ermöglichen (zum Beispiel durch ein spezielles malloc-Funktion wie in C oder durch dynamische Erstellung von Objekte wie in Java) muss der Code zur Verwaltung des Heaps bereits vorhanden sein und ist daher kein Problem. Die dynamische Heap-Zuordnung erfordert jedoch mehr Overhead und ist daher weniger effizient als die dynamische und statische Stack-Zuordnung.

Fast alle modernen gängigen Programmiersprachen nutzen die stapeldynamische Zuweisung von Aktivierungsrahmen. Häufig wird dies aber auch mit den oben genannten Alternativen kombiniert, die „bei Bedarf“ zum Einsatz kommen. Es gibt Situationen, für die die dynamische Stapelzuweisung nicht geeignet ist. Dies gilt zum Beispiel, wenn ein Unterprogramm länger aktiv sein kann als das aufrufende Unterprogramm, wenn bestimmte Variablen in einem Unterprogramm ihren Wert zwischen verschiedenen Aufrufen dieses Unterprogramms beibehalten müssen (diese Arten von Variablen werden manchmal als "statisch" bezeichnet) oder wenn eine Funktion Schließung ist zurückgekommen.