Warum sind Stackoverflow-Fehler chaotisch?

Question

Diese einfache C-Programm beendet wird selten in der gleichen Aufruftiefe:

#include <stdio.h> 
#include <stdlib.h> 

void recursive(unsigned int rec); 

int main(void) 
{ 
    recursive(1); 
    return 0; 
} 

void recursive(unsigned int rec) { 
    printf("%u\n", rec); 
    recursive(rec + 1); 
} 

Was sind die Gründe für diese chaotische Verhalten sein könnte?

Ich benutze Fedora (16GiB Ram, Stackgröße von 8192) und kompiliert mit CC ohne Optionen.

EDIT

• Ich bin mir bewusst, dass dieses Programm einen Stackoverflow werfen
• Ich weiß, dass einige Compiler-Optimierungen ermöglicht, das Verhalten ändern und dass das Programm Integer-Überlauf erreichen.
• Ich bin mir bewusst, dass dies ein undefiniertes Verhalten ist, der Zweck dieser Frage ist es, einen Überblick über die Implementierung spezifischen internen Verhaltensweisen zu verstehen, die erklären könnten, was wir dort beobachten.

Die Frage ist mehr, da unter Linux der Thread-Stapelgröße festgelegt ist und gegeben durch ulimit -s, was die zur Verfügung stehenden Stapelgröße beeinflussen würde, so dass der Stackoverflow nicht immer bei der gleichen Aufruftiefe auftreten?

EDIT 2 @BlueMoon sieht immer die gleiche Leistung auf seinem CentOS, während auf meiner Fedora, mit einem Stapel von 8 M, I verschiedene Ausgängen (zuletzt gedruckten integer 261.892 oder 261.845 zu sehen, oder 261.826 oder ...)

Answer 1

Ändern der printf Aufruf:

printf("%u %p\n", rec, &rec); 

Diese gcc Kräfte auf den Stapel rec zu setzen und gibt Ihnen die Adresse, die ein guter Indikator für ist, was mit dem Stapelzeiger vor sich geht.

Führen Sie Ihr Programm ein paar Mal aus und notieren Sie, was mit der Adresse passiert, die am Ende gedruckt wird. Ein paar läuft auf meinem Rechner zeigt dies:

261958 0x7fff82d2878c 
261778 0x7fffc85f379c 
261816 0x7fff4139c78c 
261926 0x7fff192bb79c 

Das erste, was zu beachten ist, dass die Stapeladresse endet immer in 78c oder 79c. Warum das? Wir sollten beim Überschreiten einer Seitengrenze abstürzen, die Seiten sind 0x1000 Bytes lang und jede Funktion isst 0x20 Bytes des Stapels, so dass die Adresse mit 00X oder 01X enden sollte. Aber wenn wir uns das genauer ansehen, stürzen wir uns in libc. Der Stack-Überlauf findet also irgendwo innerhalb von libc statt. Daraus können wir schließen, dass der Aufruf von printf und allem, was er aufruft, mindestens 0x78c = 1932 (möglicherweise plus X * 4096) Bytes Stack benötigt.

Die zweite Frage ist, warum braucht es eine andere Anzahl von Iterationen, um das Ende des Stapels zu erreichen? Ein Hinweis ist in der Tatsache, dass die Adressen, die wir bekommen, bei jedem Lauf des Programms unterschiedlich sind.

1 0x7fff8c4c13ac 
1 0x7fff0a88f33c 
1 0x7fff8d02fc2c 
1 0x7fffbc74fd9c 

Die Position des Stapels im Speicher ist randomisiert. Dies wird getan, um eine ganze Familie von Pufferüberlauf-Exploits zu verhindern. Aber da Speicherzuordnungen, insbesondere auf dieser Ebene, nur in mehreren Seiten (4096 Bytes) durchgeführt werden können, würden alle anfänglichen Stapelzeiger bei 0x1000 ausgerichtet sein. Dies würde die Anzahl der zufälligen Bits in der randomisierten Stapeladresse reduzieren, so dass eine zusätzliche Zufälligkeit hinzugefügt wird, indem einfach eine zufällige Menge an Bytes an der Spitze des Stapels verschwendet wird.

Das Betriebssystem kann nur die Menge des von Ihnen verwendeten Speichers, einschließlich der Begrenzung auf dem Stapel, auf ganzen Seiten berücksichtigen. Auch wenn der Stapel bei einer zufälligen Adresse beginnt, ist die letzte zugängliche Adresse auf dem Stapel immer eine Adresse, die auf 0xfff endet. Die kurze Antwort lautet: Um die Zufälligkeit im randomisierten Speicherlayout zu erhöhen, werden einige Bytes oben auf dem Stapel bewusst verschwendet, aber das Ende des Stapels muss auf einer Seitengrenze enden.

Answer 2

Sie werden nicht das gleiche Verhalten zwischen Ausführungen haben, weil es auf dem aktuellen verfügbaren Speicher abhängt. Je mehr Speicher Sie zur Verfügung haben, desto weiter gehen Sie in dieser rekursiven Funktion.

Answer 3

Ihr Programm läuft unendlich, da in Ihrer rekursiven Funktion keine Basisbedingung vorhanden ist. Der Stapel wächst bei jedem Funktionsaufruf kontinuierlich an und führt zu einem Stapelüberlauf.
Wenn es der Fall von Tail-Rekursion Optimierung (mit Option -O2) wäre, dann wird Stapelüberlauf sicher auftreten. Es ruft undefiniertes Verhalten auf.

Was würde die verfügbare Stapelgröße beeinflussen, sodass der Stackoverflow nicht immer bei derselben Aufruftiefe auftritt?

Wenn ein Stapelüberlauf auftritt, wird ein nicht definiertes Verhalten ausgelöst. Über das Ergebnis kann in diesem Fall nichts gesagt werden.

Answer 4

Zwischen dem Stapelsegment und dem Heapsegment besteht eine Lücke. Da die Größe des Heaps variabel ist (ändert sich während der Ausführung ständig), ist das Ausmaß, in dem Ihr Stack wachsen wird, bevor der Stackoverflow auftritt, ebenfalls variabel. Dies ist der Grund, warum Ihr Programm selten in der gleichen Aufruftiefe endet.

Answer 5

Das kann über Code zwei Probleme verursachen:

• Stack-Überlauf.
• Integer Überlauf.

Stack-Überlauf: Wenn eine rekursive Funktion aufgerufen wird, alle seine Variablen werden auf die call stack einschließlich seiner return Adresse geschoben. Da es keine Basisbedingung gibt, die die Rekursion beendet und der Stack-Speicher begrenzt ist, wird der Stack erschöpft Stack Overflow Ausnahme. Der Aufrufstapel kann aus einer begrenzten Menge an Adressraum bestehen, der oft zu Beginn des Programms festgelegt wird. Die Größe des Call-Stack, hängt von vielen Faktoren ab, einschließlich der Programmiersprache, Maschinenarchitektur, Multi-Threading, und die Menge des verfügbaren Speichers . Wenn ein Programm versucht, mehr Speicherplatz zu verwenden, als auf dem Aufruf-Stack verfügbar ist (dh wenn es versucht, auf Speicher zuzugreifen, der über die Grenzen des Aufruf-Stacks hinausgeht, was im Wesentlichen ein Pufferüberlauf ist), wird der Stack überlaufen Programmabsturz.

Beachten Sie, dass jedes Mal, wenn eine Funktion exit/return ausgeführt wird, alle Variablen, die von dieser Funktion auf den Stack geschoben werden, freigegeben werden (dh sie werden gelöscht). Sobald eine Stapelvariable freigegeben wurde, wird diese Speicherregion für andere Stapelvariablen verfügbar. Für die rekursive Funktion befindet sich die Rückkehradresse jedoch noch auf dem Stapel, bis die Rekursion endet. Darüber hinaus werden automatische lokale Variablen als einzelner Block zugeordnet und der Stapelzeiger weit genug vorgeschoben, um die Summe ihrer Größen zu berücksichtigen. Sie interessieren sich möglicherweise für Recursive Stack in C.

Integer Überlauf: Wie in jedem rekursiven Aufruf von recursive() Schritten rec von 1, gibt es eine Chance, dass Integer Überlauf auftreten kann. Dafür muss Ihre Maschine einen riesigen Stapelspeicher haben, da der Bereich der Ganzzahl ohne Vorzeichen 0 bis 4.294.967.295 ist. Siehe Referenz here.

Answer 6

Ihr rekursiver Aufruf führt in der Praxis nicht unbedingt zu undefiniertem Verhalten aufgrund von stackoverflow (wird aber durch Integerüberlauf verursacht). Eine Optimierung der Compiler könnte einfach schalten Sie Ihren Compiler in eine unendliche „Schleife“ mit einem Sprungbefehl:

void recursive(int rec) { 
    loop: 
    printf("%i\n", rec); 
    rec++; 
    goto loop; 
} 

Beachten Sie, dass diese undefinierten Verhalten verursachen wird, da es rec (signed int Überlauf ist UB) zum Überlauf geht . Wenn zum Beispiel rec ein vorzeichenloses int ist, dann ist der Code gültig und sollte theoretisch für immer laufen.

Answer 7

Wenn ein Prozess ein Programm von einer ausführbaren Datei lädt, ordnet er normalerweise Speicherbereiche für den Code, den Stapel, den Heap, initialisierte und nicht initialisierte Daten zu. Der zugeteilte Stapelspeicherplatz ist normalerweise nicht so groß (wahrscheinlich 10s von Megabyte) und man könnte sich vorstellen, dass die Erschöpfung des physischen RAMs auf einem modernen System kein Problem wäre und der Stapelüberlauf immer in der gleichen Tiefe erfolgen würde Rekursion.

Aus Sicherheitsgründen ist der Stapel jedoch nicht immer an der gleichen Stelle. Address Space Layout Randomisation stellt sicher, dass die Basis der Position des Stapels zwischen den Aufrufen des Programms variiert. Das bedeutet, dass das Programm möglicherweise mehr (oder weniger) Rekursionen ausführen kann, bevor der Anfang des Stapels auf etwas trifft, auf das nicht zugegriffen werden kann, wie den Programmcode.

Das ist meine Vermutung, was passiert ist, jedenfalls.