Wächst der Stapel nach oben oder unten?

87

Ich habe diesen Code in c:

int q = 10;
int s = 5;
int a[3];

printf("Address of a: %d\n",    (int)a);
printf("Address of a[1]: %d\n", (int)&a[1]);
printf("Address of a[2]: %d\n", (int)&a[2]);
printf("Address of q: %d\n",    (int)&q);
printf("Address of s: %d\n",    (int)&s);

Die Ausgabe ist:

Address of a: 2293584
Address of a[1]: 2293588
Address of a[2]: 2293592
Address of q: 2293612
Address of s: 2293608

Ich sehe also , dass die Speicheradressen von abis a[2]um jeweils 4 Byte zunehmen. Von qbis sverringern sich die Speicheradressen jedoch um 4 Byte.

Ich frage mich 2 Dinge:

  1. Wächst der Stapel nach oben oder unten? (In diesem Fall sieht es für mich nach beidem aus)
  2. Was passiert zwischen a[2]und qSpeicheradressen? Warum gibt es dort einen großen Gedächtnisunterschied? (20 Bytes).

Hinweis: Dies ist keine Hausaufgabenfrage. Ich bin gespannt, wie Stack funktioniert. Vielen Dank für jede Hilfe.

Spikatrix
quelle
Die Reihenfolge ist beliebig. Die Lücke besteht wahrscheinlich darin, ein Zwischenergebnis wie & q oder & s zu speichern - schauen Sie sich die Demontage an und überzeugen Sie sich selbst.
Tom Leys
Ich stimme zu, lesen Sie den Assembler-Code. Wenn Sie solche Fragen stellen, ist es Zeit zu lernen, sie zu lesen.
Per Johansson
Eine einfach
Ciro Santilli 22 冠状 病 六四 事件 22

Antworten:

74

Das Verhalten des Stapels (Auf- oder Abwachsen) hängt von der Anwendungsbinärschnittstelle (ABI) und der Organisation des Aufrufstapels (auch als Aktivierungsdatensatz bezeichnet) ab.

Während seiner gesamten Lebensdauer muss ein Programm mit anderen Programmen wie dem Betriebssystem kommunizieren. ABI bestimmt, wie ein Programm mit einem anderen Programm kommunizieren kann.

Der Stapel für verschiedene Architekturen kann in beide Richtungen wachsen, für eine Architektur ist er jedoch konsistent. Bitte überprüfen Sie dies Wiki-Link. Das Wachstum des Stacks wird jedoch vom ABI dieser Architektur bestimmt.

Wenn Sie beispielsweise den MIPS ABI verwenden, wird der Aufrufstapel wie folgt definiert.

Betrachten wir, dass die Funktion 'fn1' 'fn2' aufruft. Nun ist der Stapelrahmen von 'fn2' aus wie folgt:

direction of     |                                 |
  growth of      +---------------------------------+ 
   stack         | Parameters passed by fn1(caller)|
from higher addr.|                                 |
to lower addr.   | Direction of growth is opposite |
      |          |   to direction of stack growth  |
      |          +---------------------------------+ <-- SP on entry to fn2
      |          | Return address from fn2(callee) | 
      V          +---------------------------------+ 
                 | Callee saved registers being    | 
                 |   used in the callee function   | 
                 +---------------------------------+
                 | Local variables of fn2          |
                 |(Direction of growth of frame is |
                 | same as direction of growth of  |
                 |            stack)               |
                 +---------------------------------+ 
                 | Arguments to functions called   |
                 | by fn2                          |
                 +---------------------------------+ <- Current SP after stack 
                                                        frame is allocated

Jetzt können Sie sehen, dass der Stapel nach unten wächst. Wenn die Variablen also dem lokalen Rahmen der Funktion zugewiesen werden, wachsen die Adressen der Variablen tatsächlich nach unten. Der Compiler kann die Reihenfolge der Variablen für die Speicherzuordnung festlegen. (In Ihrem Fall kann entweder 'q' oder 's' zuerst der Stapelspeicher zugewiesen werden. Im Allgemeinen führt der Compiler die Stapelspeicherzuweisung jedoch gemäß der Reihenfolge der Deklaration der Variablen durch.)

Bei den Arrays hat die Zuordnung jedoch nur einen einzigen Zeiger, und der zuzuweisende Speicher wird tatsächlich von einem einzelnen Zeiger angezeigt. Der Speicher muss für ein Array zusammenhängend sein. Obwohl der Stapel nach unten wächst, wächst der Stapel für Arrays nach oben.

Ganesh Gopalasubramanian
quelle
5
Außerdem, wenn Sie überprüfen möchten, ob der Stapel nach oben oder unten wächst. Deklarieren Sie eine lokale Variable in der Hauptfunktion. Drucken Sie die Adresse der Variablen. Rufen Sie eine andere Funktion von main auf. Deklarieren Sie eine lokale Variable in der Funktion. Drucken Sie die Adresse aus. Anhand der gedruckten Adressen können wir sagen, dass der Stapel nach oben oder unten wächst.
Ganesh Gopalasubramanian
danke Ganesh, ich habe eine kleine Frage: In der Abbildung, die Sie im dritten Block gezeichnet haben, meinten Sie "calleR gespeichertes Register wird in CALLER verwendet", denn wenn f1 f2 aufruft, müssen wir die Adresse f1 speichern (das ist die Rücksprungadresse) für f2) und f1 (calleR) Register nicht f2 (callee) Register. Richtig?
CSawy
44

Das sind eigentlich zwei Fragen. Zum einen geht es darum, wie der Stapel wächst, wenn eine Funktion eine andere aufruft (wenn ein neuer Frame zugewiesen wird), und zum anderen geht es darum, wie Variablen im Frame einer bestimmten Funktion angeordnet sind.

Beides ist nicht im C-Standard festgelegt, aber die Antworten sind etwas anders:

  • Wie wächst der Stapel, wenn ein neuer Frame zugewiesen wird ? Wenn die Funktion f () die Funktion g () aufruft, ist fder Frame-Zeiger größer oder kleiner als gder Frame-Zeiger? Dies kann in beide Richtungen gehen - es hängt vom jeweiligen Compiler und der jeweiligen Architektur ab (siehe "Aufrufkonvention"), ist jedoch innerhalb einer bestimmten Plattform immer konsistent (mit einigen bizarren Ausnahmen, siehe Kommentare). Abwärts ist häufiger; Dies ist bei x86-, PowerPC-, MIPS-, SPARC-, EE- und Cell-SPUs der Fall.
  • Wie sind die lokalen Variablen einer Funktion in ihrem Stapelrahmen angeordnet? Dies ist nicht spezifiziert und völlig unvorhersehbar; Dem Compiler steht es frei, seine lokalen Variablen anzuordnen, er möchte jedoch das effizienteste Ergebnis erzielen.
Crashworks
quelle
7
"es ist innerhalb einer bestimmten Plattform immer konsistent" - nicht garantiert. Ich habe eine Plattform ohne virtuellen Speicher gesehen, auf der der Stapel dynamisch erweitert wurde. Neue Stapelblöcke wurden praktisch mallociert, was bedeutet, dass Sie einen Stapelblock für eine Weile "runter" und dann plötzlich "seitwärts" zu einem anderen Block gehen würden. "Seitwärts" könnte eine größere oder eine kleinere Adresse bedeuten, ganz auf das Glück der Auslosung zurückzuführen.
Steve Jessop
2
Für zusätzliche Details zu Punkt 2 kann ein Compiler möglicherweise entscheiden, dass eine Variable niemals im Speicher sein muss (sie muss in einem Register für die Lebensdauer der Variablen gespeichert werden), und / oder ob die Lebensdauer von zwei oder mehr Variablen dies nicht tut. Bei Überlappung kann der Compiler entscheiden, denselben Speicher für mehr als eine Variable zu verwenden.
Michael Burr
2
Ich denke, S / 390 (IBM zSeries) hat einen ABI, bei dem Aufrufrahmen verknüpft sind, anstatt auf einem Stapel zu wachsen.
Ephemient
2
Korrigieren Sie auf S / 390. Ein Anruf ist "BALR", Zweig- und Verbindungsregister. Der Rückgabewert wird in ein Register gestellt und nicht auf einen Stapel verschoben. Die Rückgabefunktion ist eine Verzweigung zum Inhalt dieses Registers. Wenn der Stapel tiefer wird, wird Platz auf dem Heap zugewiesen und sie werden miteinander verkettet. Hier erhält das MVS-Äquivalent von "/ bin / true" seinen Namen: "IEFBR14". Die erste Version hatte eine einzige Anweisung: "BR 14", die zum Inhalt des Registers 14 verzweigte, das die Rücksprungadresse enthielt.
7.
1
Einige Compiler auf PIC-Prozessoren führen eine Analyse des gesamten Programms durch und weisen den automatischen Variablen jeder Funktion feste Speicherorte zu. Der eigentliche Stapel ist winzig und über Software nicht zugänglich. Es ist nur für Absenderadressen.
7.
13

Die Richtung, in die Stapel wachsen, ist architekturspezifisch. Meines Wissens nach haben jedoch nur sehr wenige Hardwarearchitekturen Stapel, die erwachsen werden.

Die Richtung, in die ein Stapel wächst, ist unabhängig vom Layout eines einzelnen Objekts. Während der Stapel möglicherweise verkleinert ist, werden Arrays nicht (dh & array [n] ist immer <& array [n + 1]);

R Samuel Klatchko
quelle
4

Der Standard enthält nichts, was vorschreibt, wie die Dinge auf dem Stapel überhaupt organisiert sind. Tatsächlich könnten Sie einen konformen Compiler erstellen, der Array-Elemente überhaupt nicht an zusammenhängenden Elementen auf dem Stapel speichert, vorausgesetzt, er verfügt über die Intelligenz, um Array-Element-Arithmetik weiterhin ordnungsgemäß auszuführen (sodass er beispielsweise wusste, dass eine 1 war 1K von einer [0] entfernt und könnte sich darauf einstellen).

Der Grund, warum Sie möglicherweise unterschiedliche Ergebnisse erhalten, liegt darin, dass der Stapel zwar nach unten wächst, um "Objekte" hinzuzufügen, das Array jedoch ein einzelnes "Objekt" ist und aufsteigende Array-Elemente in umgekehrter Reihenfolge aufweist. Es ist jedoch nicht sicher, sich auf dieses Verhalten zu verlassen, da sich die Richtung ändern kann und Variablen aus verschiedenen Gründen ausgetauscht werden können, einschließlich, aber nicht beschränkt auf:

  • Optimierung.
  • Ausrichtung.
  • die Launen der Person, die der Stapelverwaltungsteil des Compilers ist.

Siehe hier für meine ausgezeichnete Abhandlung über die Stapelrichtung :-)

Als Antwort auf Ihre spezifischen Fragen:

  1. Wächst der Stapel nach oben oder unten?
    Es spielt überhaupt keine Rolle (in Bezug auf den Standard), aber da Sie gefragt haben, kann es je nach Implementierung im Speicher nach oben oder unten wachsen .
  2. Was passiert zwischen einer [2] und einer q Speicheradresse? Warum gibt es dort einen großen Gedächtnisunterschied? (20 Bytes)?
    Es spielt überhaupt keine Rolle (in Bezug auf den Standard). Siehe oben für mögliche Gründe.
paxdiablo
quelle
Ich habe gesehen, dass Sie verlinken, dass die meisten CPU-Architekturen den "Herabwachsen" -Weg übernehmen. Wissen Sie, ob dies einen Vorteil hat?
Baiyan Huang
Eigentlich keine Ahnung. Es ist möglich, dass jemand dachte, der Code würde von 0 nach oben gehen, also sollte der Stapel von Highmem nach unten gehen, um die Möglichkeit von Überschneidungen zu minimieren. Einige CPUs führen jedoch speziell Code an Stellen ungleich Null aus, sodass dies möglicherweise nicht der Fall ist. Wie bei den meisten Dingen wurde es vielleicht einfach so gemacht, weil es der erste war, wie jemand daran dachte :-)
paxdiablo
@lzprgmr: Es gibt einige geringfügige Vorteile, wenn bestimmte Arten der Heap-Zuweisung in aufsteigender Reihenfolge durchgeführt werden, und es war in der Vergangenheit üblich, dass sich Stapel und Heap an entgegengesetzten Enden eines gemeinsamen Adressraums befinden. Vorausgesetzt, dass die kombinierte statische + Heap + Stack-Nutzung den verfügbaren Speicher nicht überschreitet, muss man sich nicht darum kümmern, wie viel Stack-Speicher ein Programm verwendet.
Supercat
3

Auf einem x86 besteht die Speicher- "Zuordnung" eines Stapelrahmens einfach darin, die erforderliche Anzahl von Bytes vom Stapelzeiger zu subtrahieren (ich glaube, andere Architekturen sind ähnlich). In diesem Sinne denke ich, dass der Stapel "verkleinert" wird, indem die Adressen zunehmend kleiner werden, wenn Sie tiefer in den Stapel aufrufen (aber ich stelle mir immer vor, dass der Speicher mit 0 oben links beginnt und größere Adressen erhält, wenn Sie sich bewegen nach rechts und nach unten wickeln, so dass in meinem mentalen Bild der Stapel wächst ...). Die Reihenfolge der deklarierten Variablen hat möglicherweise keinen Einfluss auf ihre Adressen. Ich glaube, der Standard erlaubt es dem Compiler, sie neu zu ordnen, solange dies keine Nebenwirkungen verursacht (jemand korrigiert mich bitte, wenn ich falsch liege). . Sie'

Die Lücke um das Array mag eine Art Polsterung sein, aber es ist für mich mysteriös.

rmeador
quelle
1
Tatsächlich weiß ich, dass der Compiler sie neu anordnen kann, da es auch kostenlos ist, sie überhaupt nicht zuzuweisen. Es kann sie einfach in Register eintragen und keinerlei Stapelplatz belegen.
Rmeador
Sie können nicht in die Register aufgenommen werden, wenn Sie auf ihre Adressen verweisen.
Florin
Guter Punkt, hatte das nicht berücksichtigt. aber es genügt immer noch als Beweis dafür, dass der Compiler sie neu
anordnen
1

Zuallererst wachsen die 8 Bytes nicht genutzten Speicherplatz im Speicher (nicht 12, denken Sie daran, dass der Stapel nach unten wächst, sodass der nicht zugewiesene Speicherplatz zwischen 604 und 597 liegt). und warum?. Weil jeder Datentyp ab der durch seine Größe teilbaren Adresse Speicherplatz belegt. In unserem Fall benötigt ein Array mit 3 Ganzzahlen 12 Byte Speicherplatz und 604 ist nicht durch 12 teilbar. Es bleiben also leere Leerzeichen, bis es auf eine Speicheradresse trifft, die durch 12 teilbar ist. Es ist 596.

Der dem Array zugewiesene Speicherplatz beträgt also 596 bis 584. Da die Array-Zuweisung jedoch fortgesetzt wird, beginnt das erste Element des Arrays mit der Adresse 584 und nicht mit 596.

Prateek Khurana
quelle
1

Dem Compiler steht es frei, lokale (Auto-) Variablen an einer beliebigen Stelle im lokalen Stapelrahmen zuzuweisen. Sie können die Richtung des Stapelwachstums nicht zuverlässig daraus ableiten. Sie können die Richtung des Stapelwachstums durch Vergleichen der Adressen verschachtelter Stapelrahmen ableiten, dh durch Vergleichen der Adresse einer lokalen Variablen innerhalb des Stapelrahmens einer Funktion im Vergleich zu ihrer Angerufenen:

#include <stdio.h>
int f(int *x)
{
  int a;
  return x == NULL ? f(&a) : &a - x;
}

int main(void)
{
  printf("stack grows %s!\n", f(NULL) < 0 ? "down" : "up");
  return 0;
}
Matja
quelle
5
Ich bin mir ziemlich sicher, dass es undefiniertes Verhalten ist, Zeiger auf verschiedene Stapelobjekte zu subtrahieren - Zeiger, die nicht Teil desselben Objekts sind, sind nicht vergleichbar. Natürlich stürzt es auf keiner "normalen" Architektur ab.
Steve Jessop
@SteveJessop Gibt es eine Möglichkeit, dies zu beheben, um die Richtung des Stapels programmgesteuert zu ermitteln?
xxks-kkk
@ xxks-kkk: im Prinzip nein, da für eine C-Implementierung keine "Stapelrichtung" erforderlich ist. Zum Beispiel würde es nicht gegen den Standard verstoßen, eine Aufrufkonvention zu haben, bei der ein Stapelblock im Voraus zugewiesen wird, und dann wird eine pseudozufällige interne Speicherzuweisungsroutine verwendet, um darin herumzuspringen. In der Praxis funktioniert es tatsächlich so, wie es Matja beschreibt.
Steve Jessop
0

Ich denke nicht, dass es so deterministisch ist. Das a-Array scheint zu "wachsen", da dieser Speicher zusammenhängend zugewiesen werden sollte. Da q und s jedoch überhaupt nicht miteinander verwandt sind, steckt der Compiler jeden von ihnen einfach an einen beliebigen freien Speicherplatz innerhalb des Stapels, wahrscheinlich diejenigen, die am besten zu einer ganzzahligen Größe passen.

Was zwischen a [2] und q passiert ist, ist, dass der Raum um qs Position nicht groß genug war (dh nicht größer als 12 Bytes), um ein 3-Integer-Array zuzuweisen.

javanix
quelle
Wenn ja, warum haben q, s, a kein ansteckendes Gedächtnis? (Beispiel: Adresse von q: 2293612 Adresse von s: 2293608 Adresse von a: 2293604)
Ich sehe eine "Lücke" zwischen s und a
Da s und a nicht zusammen zugewiesen wurden, müssen nur die Zeiger im Array zusammenhängend sein. Der andere Speicher kann überall zugewiesen werden.
Javanix
0

Mein Stapel scheint sich zu Adressen mit niedrigerer Nummer zu erstrecken.

Auf einem anderen Computer oder sogar auf meinem eigenen Computer kann dies anders sein, wenn ich einen anderen Compileraufruf verwende. ... oder der Compiler muss sich dafür entscheiden, überhaupt keinen Stack zu verwenden (alles inline (Funktionen und Variablen, wenn ich nicht die Adresse von ihnen genommen habe)).

$ cat stack.c
#include <stdio.h>

int stack(int x) {
  printf("level %d: x is at %p\n", x, (void*)&x);
  if (x == 0) return 0;
  return stack(x - 1);
}

int main(void) {
  stack(4);
  return 0;
}
$ / usr / bin / gcc -Wall -Wextra -std = c89 -pedantic stack.c
$ ./a.out
Stufe 4: x ist bei 0x7fff7781190c
Stufe 3: x ist bei 0x7fff778118ec
Stufe 2: x ist bei 0x7fff778118cc
Stufe 1: x ist bei 0x7fff778118ac
Stufe 0: x ist bei 0x7fff7781188c
pmg
quelle
0

Der Stapel wächst nach unten (auf x86). Der Stapel wird jedoch beim Laden der Funktion in einem Block zugewiesen, und Sie können nicht garantieren, in welcher Reihenfolge sich die Elemente auf dem Stapel befinden.

In diesem Fall wurde Platz für zwei Ints und ein Drei-Int-Array auf dem Stapel zugewiesen. Es hat auch zusätzliche 12 Bytes nach dem Array zugewiesen, also sieht es so aus:

a [12 Bytes]
Auffüllen (?) [12 Bytes]
s [4 Bytes]
q [4 Bytes]

Aus irgendeinem Grund hat Ihr Compiler entschieden, dass für diese Funktion 32 Byte und möglicherweise mehr zugewiesen werden müssen. Das ist für Sie als C-Programmierer undurchsichtig, Sie wissen nicht warum.

Wenn Sie wissen möchten, warum, kompilieren Sie den Code in Assemblersprache. Ich glaube, dass es -S auf gcc und / S auf dem C-Compiler von MS ist. Wenn Sie sich die Eröffnungsanweisungen für diese Funktion ansehen, sehen Sie, dass der alte Stapelzeiger gespeichert und dann 32 (oder etwas anderes!) Von ihm subtrahiert werden. Von dort aus können Sie sehen, wie der Code auf diesen 32-Byte-Speicherblock zugreift, und herausfinden, was Ihr Compiler tut. Am Ende der Funktion sehen Sie, wie der Stapelzeiger wiederhergestellt wird.

Aric TenEyck
quelle
0

Dies hängt von Ihrem Betriebssystem und Ihrem Compiler ab.

David R Tribble
quelle
Ich weiß nicht, warum meine Antwort abgelehnt wurde. Es hängt wirklich von Ihrem Betriebssystem und Compiler ab. Auf einigen Systemen wächst der Stapel nach unten, auf anderen nach oben. Auf einigen Systemen gibt es keinen echten Push-Down-Frame-Stack, sondern er wird mit einem reservierten Speicherbereich oder Registersatz simuliert.
David R Tribble
3
Wahrscheinlich, weil Aussagen mit einem Satz keine guten Antworten sind.
Leichtigkeitsrennen im Orbit
0

Der Stapel wächst nach unten. Also f (g (h ())), der für h zugewiesene Stapel beginnt an einer niedrigeren Adresse als g und g ist niedriger als f. Variablen innerhalb des Stapels müssen jedoch der C-Spezifikation folgen.

http://c0x.coding-guidelines.com/6.5.8.html

1206 Wenn die Objekte, auf die verwiesen wird, Mitglieder desselben Aggregatobjekts sind, werden Zeiger auf später deklarierte Strukturelemente größer als Zeiger auf Elemente, die früher in der Struktur deklariert wurden, und Zeiger auf Array-Elemente mit größeren tiefgestellten Werten verglichen mehr als Zeiger auf Elemente desselben Array mit niedrigeren tiefgestellten Werten.

& a [0] <& a [1] muss immer wahr sein, unabhängig davon, wie 'a' zugewiesen wird

user1187902
quelle
Bei den meisten Maschinen wächst der Stapel nach unten - mit Ausnahme derjenigen, bei denen er nach oben wächst.
Jonathan Leffler
0

wächst nach unten und dies liegt am Standard der kleinen Endian-Bytereihenfolge, wenn es um den Datensatz im Speicher geht.

Eine Möglichkeit, dies zu betrachten, besteht darin, dass der Stapel nach oben wächst, wenn Sie den Speicher von 0 von oben und max von unten betrachten.

Der Grund dafür, dass der Stapel nach unten wächst, besteht darin, dass er aus der Perspektive des Stapels oder Basiszeigers dereferenziert werden kann.

Denken Sie daran, dass die Dereferenzierung jeglicher Art von der niedrigsten zur höchsten Adresse zunimmt. Da der Stapel nach unten wächst (höchste bis niedrigste Adresse), können Sie den Stapel wie einen dynamischen Speicher behandeln.

Dies ist ein Grund, warum so viele Programmier- und Skriptsprachen eine stapelbasierte virtuelle Maschine anstelle einer registergestützten verwenden.

Nergal
quelle
The reason for the stack growing downward is to be able to dereference from the perspective of the stack or base pointer.Sehr schöne Argumentation
user3405291
0

Das hängt von der Architektur ab. Verwenden Sie diesen Code von GeeksForGeeks, um Ihr eigenes System zu überprüfen :

// C program to check whether stack grows 
// downward or upward. 
#include<stdio.h> 

void fun(int *main_local_addr) 
{ 
    int fun_local; 
    if (main_local_addr < &fun_local) 
        printf("Stack grows upward\n"); 
    else
        printf("Stack grows downward\n"); 
} 

int main() 
{ 
    // fun's local variable 
    int main_local; 

    fun(&main_local); 
    return 0; 
} 
kurdtpage
quelle