Rekursion vermeiden... Wieso?

hustbaer

Bashar schrieb:

mit try ... catch? Dürfte in jeder höheren Programmiersprache gehen.

Nein, ganz sicher nicht.

hustbaer

frosch03 schrieb:

Nur mal so aus Interesse, weil ich's mir grad nicht vorstellen kann. Kann man
Stack-Overflow's tatsächlich zuverlässig abfangen? Und falls ja, wie würde man so etwas anstellen?

C, C++, Java und C# bieten keinen mir bekannte Mechanismus an, mit dem man einen Stack-Overflow behandeln/abfangen/... könnte.

Das OS in Zusammenarbeit mit dem Compiler kann allerdings "reine" Stack-Overflows sehrwohl zuverlässig erkennen (also welche die nicht mit "unchecked buffer" Fehlern o.Ä. kombiniert sind). Ob man den betroffenen Thread danach noch weiterverwenden kann ist eine andere Frage.

Machen tut man das mit Guard-Pages und Stack-Probes.
Dazu generiert der Compiler am Anfang jeder Funktion, die mehr als eine Page an Stack braucht, eine kleine Schleife, die im Abstand von einer Page einfach Werte vom Stack ausliest (oder schreibt - ist egal). Ausgehend vom aktuellen Stack-Pointer, und bis zum neuen Wert des Stack-Pointers. Damit ist garantiert, dass keine Page übersprungen wird.

Am "Ende" des Stacks befindet sich dann eine Guard-Page, also eine Page die "not present" markiert ist. Wenn das OS im entsprechenden Trap-Handler sieht dass eine Guard-Page "getroffen" wurde, weiss es, dass das Programm einen Stack-Overflow gebaut hat.

frosch03

Ah, dat is ja spannend... Erinnert mich jetzt gerade ein wenig an diese "Stack Canaries"
mit denen man buffer-overflow's erkennen kann.

Aber sehe ich das richtig, mit dieser Erkennung rettet man nur das OS vor dem sichern
Suizid? Der Prozess der den stack-overflow verursacht hat davon erstmal wenig?

Ich glaube im übrigen, dass man solche stack-overflow's garnicht allgemein im
Voraus erkennen kann. Denn irgendwie scheint mir, als käme dass der Lösung des
Halte-Problems gleich (Und dat hat ja bekanntlich noch niemand gelöst :))

In jedem Fall 'ne Spannende Geschichte die ganze Thematik.

frosch03 schrieb:

Aber sehe ich das richtig, mit dieser Erkennung rettet man nur das OS vor dem sichern
Suizid? Der Prozess der den stack-overflow verursacht hat davon erstmal wenig?
Ich glaube im übrigen, dass man solche stack-overflow's garnicht allgemein im
Voraus erkennen kann. Denn irgendwie scheint mir, als käme dass der Lösung des
Halte-Problems gleich (Und dat hat ja bekanntlich noch niemand gelöst)

naja, normalerweise passiert dem OS nichts, wenn ein prozess sich 'nen stacküberlauf leistet. was eine erkennung oder vermeidung im voraus angeht, könnte man sich sicherlich was ausdenken (wäre vielleicht nicht so ganz kompatibel mit programmiersprachen wie C u.ä.). und dieses 'halteproblem' wird zwar problem genannt, aber 'problem' hört sich schlimmer an als es ist.

rapso

Ishildur schrieb:

Ich erspahre mir also den rekursiven Funktionsaufruf...

du sparst dir vor allem returns.
compiler veruchen das aber schon zu optimieren, wenn du also ne rekursion hast die z.b. immer die selben objekte weitergibt, diese aber nach dem return aus der rekursiven funktion nicht weiter verwendet, werden manche compiler den call+return zu einem simplen jump umstellen.

...Und tausche diesen gegen gleich zwei davon (Push und Pop auf der Hilfstruktur Stack)??

push und pop hast du sowieso auf dem stack, jedoch
-sparst du dir das ablegen von ein paar registern und legst nur wirklich noetige dinge ab
-kannst du cpu freundlicher sein wenn du alle deine variablen per index, also pStack[0]=...;pStack[1]=....; ablegst statt mit *pStack++= zu arbeiten wie es die CPU normalerweise macht.
-..

Ausserdem habe ich dann noch entweder ein new und delete (LinkedList) oder sonstige Umkopiererei (DynamicArray) je nach Stack Implementation.

sowas zu machen waere natuerlich dumm, wenn jemand das vor hat, dann wird er natuerlich schlechter abschneiden als ne rekursion zu machen.
Die idee an sich ist nur die rekursionsaufrufe zu sparen, andere laufzeiteigenschaften sollten sich nicht veraendern. alle allokationen die sonst auf dem stack waeren muessen also weiterhin auf dem stack liegen.

Der Einzige Vorteil für den iterativen Approach sehe ich darin, dass damit die Gefahr eines Überlaufs des Applikationsstacks durch die rekursiven Aufrufe gebannt ist.

nicht sonderlich, man muss beim aufruf der funktion gleich den stack anlegen. man wird also eher merken falls man in einen kritischen bereich kommt (also wenig stack da ist), weil unabhaengig von der rekursionstiefe gleich der volle speicher allokiert ist.
mehr noch, es ist relativ billig nen stackcheck einzubauen, da man das ja nicht rekursiv immer wieder macht, sondern nur im entry der funktion.

Was sagt ihr dazu?

du hast schon recht, die meisten labern bei sowas nach was sie gehoert haben und machen dann implementationsfehler weil sie sich keine gedanken darueber machen "Iterativ ist schneller, basta, aus".

du wirst aber auch vermutlich mal feststellen, dass deine iterative implementierung langsammer ist als die stackversion, obwohl du alles richtig gemacht hast. gruende koennen sein
- dass CPU hersteller (eigentlich nur amd+intel) einiges an optimierungen haben um die ueblichen stackprobleme zu umgehen.
- stack lokalitaet verloren ist aufgrund der initialen grossen allokation, z.b.

uint8_t Stack[1<<20];
size_t StackPtr=0;

sorgt dafuer dass der erste zugriff auf den stackptr garantiert ein cachemiss ist, weil fast alle cpus <=64kb an L1 cache haben, man aber 1MB weiter zugreifen will.
- compiler eben auch stackoptimierungen haben, sie verwenden moeglichst viel wieder an stack memory und versuchen unnoetige rekursionen mit jmps zu ersetzen, was sie nicht machen wenn du per hand in nem loop deinen stack bearbeitest.

am ende hilft nur benchmarken was schneller ist.

hustbaer

frosch03 schrieb:

Aber sehe ich das richtig, mit dieser Erkennung rettet man nur das OS vor dem sichern
Suizid? Der Prozess der den stack-overflow verursacht hat davon erstmal wenig?

Dem OS ist das herzlich egal.
Ich denke da gehts eher darum das Programm davor zu schützen dass es seine eigenen Daten überschreibt.

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Das Programm würde dann ganz normal weiterlaufen, aber der Datenbereich "neben" dem Stack wäre voll mit lauter Schrott aus alten Flippern.

Da ist es denke ich besser, wenn man den Prozess sterben lässt.

BTW: ich weiss garnicht ob man den Prozess sterben lassen *muss* in so einem Fall. Es kann leicht sein, dass man nur den Thread der den Stack-Overflow ausgelöst hat sterben lassen muss. Vielleicht sogar nichtmal den, wobei mir auf die Schnelle aber nicht einfällt, wie man den vernünftig weiterlaufen lassen könnte.

Bashar

hustbaer schrieb:

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Wozu muss man das überhaupt über eine Guard-Page realisieren? Man kann doch bei jedem Funktionsaufruf erstmal gucken, ob über dem Stackpointer bis zum Beginn des Heaps oder was auch immer danach kommt noch genug Platz ist?

Wenn das ginge, müsste man den Aufruf mit einer Exception sterben lassen und das wärs gewesen. In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

Bashar schrieb:

In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

kannste aber abfangen, z.b. so:

public class test
{
    static void smash_the_stack()
    {
        smash_the_stack();
    }

    public static void main( String[] args )
    {
        try
        {
            smash_the_stack();    
        }
        catch (StackOverflowError e)
        {
            System.out.println ("huch? ein ... " + e);
        }
        System.out.println ("still alive :)");
    }
}

^^der stack ist danach auch wieder wie neu.

rüdiger

@;fricky
Das ist aber iirc undefined behaviour. Weil es ein VirtualMachineError ist (wie Bashar schon gesagt hat).

Bashar

Bitte nicht füttern

rüdiger schrieb:

Das ist aber iirc undefined behaviour. Weil es ein VirtualMachineError ist

probier's aus. die sun-VM jedenfalls crashed nicht dabei und der stackspeicher wird auch freigegeben. gibt es überhaupt java-VMs, bei denen StackOverflowError nicht fangbar ist?

;fricky schrieb:

probier's aus. die sun-VM jedenfalls crashed nicht dabei

Du kennst die Bedeutung von "undefined behaviour"?

ykcirf; schrieb:

;fricky schrieb:

probier's aus. die sun-VM jedenfalls crashed nicht dabei

Du kennst die Bedeutung von "undefined behaviour"?

klar, aber ich glaube nicht, dass es undefiniert ist. wozu bräuchte man dann einen fangbaren 'StackOverflowError'? es soll angeblich JVMs, die stattdessen einen 'OutOfMemoryError' bringen (die haben einen dynamisch erweiterbaren stack, der den selben bereich nutzt, wie normale Java-objekte auch). da könnte es sein, das bei 'nem stacküberlauf die VM aussteigt. vielleicht kann uns mal einer erleuchten.

hustbaer

Bashar schrieb:

hustbaer schrieb:

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Wozu muss man das überhaupt über eine Guard-Page realisieren?

Weil es schneller ist.

Bei Funktionen die weniger als 1 Page Stack brauchen muss bei Verwendung von Guard-Pages garkein zusätzlicher Code erzeugt werden/laufen.
Und "nix" ist halt immer schneller als "nicht nix".

Wenn das ginge, müsste man den Aufruf mit einer Exception sterben lassen und das wärs gewesen. In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

Ich bin mir fast sicher, dass es sowohl mit Java als auch mit C, C++, ... möglich wäre, dem Thread bloss eine Exception vor den Latz zu knallen, und ihn dann weiterlaufen zu lassen.

Bloss würde das wirklich viel bringen? Ist es so wichtig nach eine Stack-Overflow weitermachen zu können?
IMO ist das ähnlich wie wenn man Access-Violations in C++ fangen möchte. Mit diversen Compilern geht das auch durchaus, nur bestreite ich dass es sonderlich sinnvoll ist. Lieber ein Programm schreiben was garnicht erst solchen Mist baut, als dann schwindligerweise diverse Exceptions zu fangen.

Bashar

hustbaer schrieb:

Bloss würde das wirklich viel bringen? Ist es so wichtig nach eine Stack-Overflow weitermachen zu können?
IMO ist das ähnlich wie wenn man Access-Violations in C++ fangen möchte. Mit diversen Compilern geht das auch durchaus, nur bestreite ich dass es sonderlich sinnvoll ist. Lieber ein Programm schreiben was garnicht erst solchen Mist baut, als dann schwindligerweise diverse Exceptions zu fangen.

Das ist nicht ganz vergleichbar. Ein Stackoverflow heißt ja erstmal nur, dass das Programm zuviele Resourcen belegt. Vielleicht hätten ja 4 zusätzliche Bytes schon ausgereicht, wer weiß? Das ist eher einem OutOfMemory vergleichbar. Eine Access Violation deutet dagegen immer auf einen Programmierfehler hin.

hustbaer schrieb:

Ich bin mir fast sicher, dass es sowohl mit Java als auch mit C, C++, ... möglich wäre, dem Thread bloss eine Exception vor den Latz zu knallen, und ihn dann weiterlaufen zu lassen.

mit java geht's ja (siehe oben), mit C (C++ wohl auch), allerdings mit unterstützung des OS (windoof in dem fall) geht es so:

include <stdio.h>                

#define GET_ESP(x) __asm mov x, esp;

void crash (void)
{
  unsigned stackptr;
  GET_ESP(stackptr);
  printf ("%x ", stackptr);
  crash();  // recursive on all control paths, function will cause runtime stack overflow
}

int main(void) 
{
  unsigned before, after;

  GET_ESP(before);
  __try
  {
    crash();
  }
  __except (1)
  {
    puts ("\nCRASH!");
  }
  GET_ESP(after);

  printf ("ESP before: %x after: %x\n", before, after);

}

^^ und der compiler muss __try/__except kennen (ms visualC z.b.)

hustbaer

@Bashar:
Ein Stack-Overflow ist IMO auch ein Programmierfehler.

In C++ kommt übrigens auch noch etwas dazu: das Stack-Unwinding. Schreib mal eine Klasse mit dtor, wo der dtor sagen wir mal 10KB Stack braucht.

Dann nimm den Code von fricky, und leg in "crash" eine lokale Instanz dieser Klasse an.
Und dann guck, ob das Programm das überlebt.

Ich schätze die Chancen sind fast null. Du wirst während des Stack-Unwinding nach dem Stack-Overflow einen weiteren Stack-Overflow basteln. Und tschüss.

Da es mittlerweile recht üblich ist, diverse potentiell Stack-hungrige Operationen in einem dtor laufen zu lassen (RAII, bzw. ganz allgemein modernes C++), ist das Beispiel IMO auch nicht ganz unrealistisch.

Stack-Overflow ist Kacke, und hat in einem korrekten Programm nix verloren. Gibt IMO keine Entschuldigung dafür. Daher finde ich die Suche nach Möglichkeiten nach einem Stack-Overflow zu recovern auch nicht sinnvoll.

Bashar

hustbaer schrieb:

@Bashar:
Ein Stack-Overflow ist IMO auch ein Programmierfehler.

Das heißt Rekursion ist ein Programmierfehler. Magst du so sehen, seh ich anders.

hustbaer

*seufz*

Jetzt sind wir wieder ganz am Anfang angelangt, der ganze schöne Thread war also für nichts.

Naja, es kann nicht jeder alles verstehen.

Dabei steht doch schon in der Bibel "Du sollst nicht Stapel überlaufen" (oder so ähnlich).

hustbaer schrieb:

In C++ kommt übrigens auch noch etwas dazu: das Stack-Unwinding. Schreib mal eine Klasse mit dtor, wo der dtor sagen wir mal 10KB Stack braucht.
Dann nimm den Code von fricky, und leg in "crash" eine lokale Instanz dieser Klasse an.
Und dann guck, ob das Programm das überlebt.

ich schätze das wird es, denn das __try merkt sich den ESP vorm funktionsaufruf, sollte also egal sein, was die funktion mit dem stack anstellt. schon mal ausprobiert?

Bashar schrieb:

Das heißt Rekursion ist ein Programmierfehler.

rekursion, ohne die rekursionstiefe zu berücksichtigen, ist ein programmierfehler. aber zum glück brauchen sinnvolle rekursive algos garnicht so viel stackspeicher wie's scheint.