Warum verursacht ein rekursiver Aufruf StackOverflow in unterschiedlichen Stapeltiefen?

Ich habe versucht herauszufinden, wie Tail-Aufrufe vom C # -Compiler verarbeitet werden.

(Antwort: Sie sind es nicht. Aber die 64-Bit- JITs werden TCE (Tail Call Elimination) ausführen. Es gelten Einschränkungen .)

Also habe ich einen kleinen Test mit einem rekursiven Aufruf geschrieben, der ausgibt, wie oft er aufgerufen wird, bevor StackOverflowExceptionder Prozess abgebrochen wird.

class Program
{
    static void Main(string[] args)
    {
        Rec();
    }

    static int sz = 0;
    static Random r = new Random();
    static void Rec()
    {
        sz++;

        //uncomment for faster, more imprecise runs
        //if (sz % 100 == 0)
        {
            //some code to keep this method from being inlined
            var zz = r.Next();  
            Console.Write("{0} Random: {1}\r", sz, zz);
        }

        //uncommenting this stops TCE from happening
        //else
        //{
        //    Console.Write("{0}\r", sz);
        //}

        Rec();
    }

Pünktlich endet das Programm mit einer SO-Ausnahme für:

• 'Build optimieren' AUS (entweder Debug oder Release)
• Ziel: x86
• Ziel: AnyCPU + "32 Bit bevorzugen" (dies ist neu in VS 2012 und das erste Mal, dass ich es gesehen habe. Mehr hier .)
• Ein scheinbar harmloser Zweig im Code (siehe kommentierten 'else'-Zweig).

Umgekehrt passiert bei Verwendung von 'Build optimieren' EIN + (Ziel = x64 oder AnyCPU mit 'Bevorzugen 32 Bit' AUS (auf einer 64-Bit-CPU)) TCE und der Zähler dreht sich für immer (ok, er dreht sich wahrscheinlich jedes Mal, wenn sein Wert überläuft ).

Aber ich habe ein Verhalten bemerkt, das ich in diesem StackOverflowExceptionFall nicht erklären kann: Es passiert nie (?) Bei genau derselben Stapeltiefe. Hier sind die Ausgaben einiger 32-Bit-Läufe, Release Build:

51600 Random: 1778264579
Process is terminated due to StackOverflowException.

51599 Random: 1515673450
Process is terminated due to StackOverflowException.

51602 Random: 1567871768
Process is terminated due to StackOverflowException.

51535 Random: 2760045665
Process is terminated due to StackOverflowException.

Und Debug Build:

28641 Random: 4435795885
Process is terminated due to StackOverflowException.

28641 Random: 4873901326  //never say never
Process is terminated due to StackOverflowException.

28623 Random: 7255802746
Process is terminated due to StackOverflowException.

28669 Random: 1613806023
Process is terminated due to StackOverflowException.

Die Stapelgröße ist konstant ( standardmäßig 1 MB ). Die Größen der Stapelrahmen sind konstant.

Was kann dann für die (manchmal nicht triviale) Variation der Stapeltiefe bei den StackOverflowExceptionTreffern verantwortlich sein?

AKTUALISIEREN

Hans Passant wirft das Problem auf Console.WriteLine, P / Invoke, Interop und möglicherweise nicht deterministisches Sperren zu berühren.

Also habe ich den Code so vereinfacht:

class Program
{
    static void Main(string[] args)
    {
        Rec();
    }
    static int sz = 0;
    static void Rec()
    {
        sz++;
        Rec();
    }
}

Ich habe es in Release / 32bit / Optimization ON ohne Debugger ausgeführt. Wenn das Programm abstürzt, hänge ich den Debugger an und überprüfe den Wert des Zählers.

Und es ist immer noch nicht dasselbe bei mehreren Läufen. (Oder mein Test ist fehlerhaft.)

UPDATE: Schließung

Wie von fejesjoco vorgeschlagen, habe ich mich mit ASLR (Address Space Layout Randomization) befasst.

Es ist eine Sicherheitstechnik, die es für Pufferüberlaufangriffe schwierig macht, den genauen Ort (z. B.) bestimmter Systemaufrufe zu finden, indem verschiedene Dinge im Prozessadressraum zufällig angeordnet werden, einschließlich der Stapelposition und anscheinend seiner Größe.

Die Theorie klingt gut. Lassen Sie es uns in die Praxis umsetzen!

Um dies zu testen, habe ich ein speziell für diese Aufgabe entwickeltes Microsoft-Tool verwendet: EMET oder The Enhanced Mitigation Experience Toolkit . Es ermöglicht das Setzen des ASLR-Flags (und vieles mehr) auf System- oder Prozessebene.
(Es gibt auch eine systemweite Registrierungs-Hacking-Alternative , die ich nicht ausprobiert habe.)

Um die Effektivität des Tools zu überprüfen, habe ich außerdem festgestellt, dass der Prozess-Explorer den Status des ASLR-Flags auf der Seite "Eigenschaften" des Prozesses ordnungsgemäß meldet. Hab das bis heute noch nie gesehen :)

Theoretisch kann EMET das ASLR-Flag für einen einzelnen Prozess (neu) setzen. In der Praxis schien sich daran nichts zu ändern (siehe Bild oben).

Ich habe jedoch ASLR für das gesamte System deaktiviert und (ein Neustart später) konnte ich endlich überprüfen, ob die SO-Ausnahme jetzt immer bei derselben Stapeltiefe auftritt.

BONUS

ASLR-bezogen, in älteren Nachrichten: Wie Chrome pwned wurde

Ich denke, es könnte ASLR bei der Arbeit sein. Sie können DEP deaktivieren, um diese Theorie zu testen.

Hier finden Sie eine C # -Dienstprogrammklasse zum Überprüfen der Speicherinformationen: https://stackoverflow.com/a/8716410/552139

Übrigens habe ich mit diesem Tool festgestellt, dass der Unterschied zwischen der maximalen und der minimalen Stapelgröße etwa 2 KB beträgt, was einer halben Seite entspricht. Das ist komisch.

Update: OK, jetzt weiß ich, dass ich recht habe. Ich habe die halbseitige Theorie weiterverfolgt und dieses Dokument gefunden, das die ASLR-Implementierung in Windows untersucht: http://www.symantec.com/avcenter/reference/Address_Space_Layout_Randomization.pdf

Zitat:

Sobald der Stapel platziert wurde, wird der anfängliche Stapelzeiger durch einen zufälligen dekrementellen Betrag weiter randomisiert. Der anfängliche Versatz beträgt bis zu einer halben Seite (2.048 Byte).

Und das ist die Antwort auf Ihre Frage. ASLR entfernt zufällig zwischen 0 und 2048 Bytes Ihres anfänglichen Stapels.

Wechseln Sie r.Next()zu r.Next(10). StackOverflowExceptions sollten in der gleichen Tiefe auftreten.

Generierte Zeichenfolgen sollten denselben Speicher belegen, da sie dieselbe Größe haben. r.Next(10).ToString().Length == 1 immer . r.Next().ToString().Lengthist variabel.

Gleiches gilt bei Verwendung r.Next(100, 1000)