Rekursion vermeiden... Wieso?

[rüdiger]

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

[Bashar]

Bitte nicht füttern

[;fricky]

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?

[ykcirf;]

;fricky schrieb:

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

Du kennst die Bedeutung von "undefined behaviour"?

[;fricky]

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.

[;fricky]

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).

[;fricky]

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.

[Bashar]

hustbaer schrieb:

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

Wir waren die ganze Zeit am Anfang. Ich wollte nur nochmal wissen, ob du das wirklich meinst, was du die ganze Zeit andeutest.

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

Mir doch egal was die Schweizer abstimmen.

[hustbaer]

;fricky schrieb:

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?

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

Folgendes Programm:

#include <windows.h>
#include <stdio.h>

class needs_muchos_stackos_in_dtor
{
public:
	~needs_muchos_stackos_in_dtor()
	{
		char muchos_stackos[10 * 1024];
		strcpy(muchos_stackos, "~needs_muchos_stackos_in_dtor\n");
		::OutputDebugStringA(muchos_stackos);
	}

	char some_wasted_space_to_speed_things_up[50];
};

int recusrion()
{
	needs_muchos_stackos_in_dtor nms;
	if (::GetVersion() == 0)
		return 123;
	else
		return recusrion() + recusrion();
}

int main(int argc, char* args[])
{
	__try 
	{
		printf("%d\n", recusrion());
	}
	__except (EXCEPTION_EXECUTE_HANDLER)
	{
		::OutputDebugStringA("__except\n");
	}
}

Ergebnis mit /EHsc:

First-chance exception at 0x00cf1407 in vc9test.exe: 0xC00000FD: Stack overflow.
__except
The program '[876] vc9test.exe: Native' has exited with code 0 (0x0).

Der Dtor wird wie erwartet nicht ausgeführt, da /EHsc. Das Programm verhält sich nicht korrekt, da auf den Dtor geschissen wurde. Inakzeptabel.

Ergebnis mit /EHa:

First-chance exception at 0x00d21407 in vc9test.exe: 0xC00000FD: Stack overflow.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
Unhandled exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
The program '[5012] vc9test.exe: Native' has exited with code -1073741819 (0xc0000005).

Bumm. Inakzeptabel.

Noch Fragen?

[;fricky]

hustbaer schrieb:

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

ein 'bumm' ist es ja eben nicht, wenn du die exception geeignet abfängst.

hustbaer schrieb:

Das Programm verhält sich nicht korrekt, da auf den Dtor geschissen wurde

das ist allerdings wahr.

hustbaer schrieb:

Noch Fragen?

nö. ich könnte jetzt mal wieder ein paar ätzende bemerkungen über eine bestimmte programmiersprache machen, aber dass lasse ich diesmal.

[hustbaer]

;fricky schrieb:

hustbaer schrieb:

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

ein 'bumm' ist es ja eben nicht, wenn du die exception geeignet abfängst.

Man kann die Exception nicht geeignet abfangen, das ist es ja gerade.
Wenn du C programmieren willst fein, programmier C. Wenn du C++ programmieren willst kannst du es aber vergessen.

BTW: du kannst in C genauso probleme bekommen, wenn du __finally Blöcke verwendest die einiges an Stack brauchen.

[;fricky]

hustbaer schrieb:

Man kann die Exception nicht geeignet abfangen, das ist es ja gerade.
...
du kannst in C genauso probleme bekommen, wenn du __finally Blöcke verwendest die einiges an Stack brauchen.

doch, du darfst den stack erst wieder *nach* der exception benutzen, auch nicht in einem __finally-block, weil er dann noch nicht zurückgesetzt wurde. der stackoverflow-verursachende code muss immer in __try/__except eingeschlossen sein, dann wird alles wieder gut. der stackpointer erhält dann wieder den zustand, wie vor dem __try statement. alles was vorher auf dem stack war, behält weiterhin seine gültigkeit.

hustbaer schrieb:

Wenn du C++ programmieren willst kannst du es aber vergessen.

naja, aber C++ kann man auch ohne destruktoren verwenden, wenn sie solche mätzchen machen. das geht bestimmt.

[frosch03]

Jungs, schreibt eure Algorithmen tail-recursive, dann kann euch nix passieren

[hustbaer]

;fricky schrieb:

hustbaer schrieb:

Man kann die Exception nicht geeignet abfangen, das ist es ja gerade.
...
du kannst in C genauso probleme bekommen, wenn du __finally Blöcke verwendest die einiges an Stack brauchen.

doch, du darfst den stack erst wieder *nach* der exception benutzen, auch nicht in einem __finally-block, weil er dann noch nicht zurückgesetzt wurde. der stackoverflow-verursachende code muss immer in __try/__except eingeschlossen sein, dann wird alles wieder gut. der stackpointer erhält dann wieder den zustand, wie vor dem __try statement. alles was vorher auf dem stack war, behält weiterhin seine gültigkeit.

das ist theoretische und völlig unpraktikable hirnwichserei. interessiert mich kein bisschen. anwendbarkeit = 0.

hustbaer schrieb:

Wenn du C++ programmieren willst kannst du es aber vergessen.

naja, aber C++ kann man auch ohne destruktoren verwenden, wenn sie solche mätzchen machen. das geht bestimmt.

siehe oben. völlig unpraktikabel. kann ich gleich bei C bleiben.
DU magst C++ nicht, gut, bleib bei C. WENN man aber C++ verwendet, dann bitte richtig. und dann kann man keine kunstgriffe brauchen, die es einem verbieten destruktoren zu verwenden.

theoretisch ist viel möglich. bloss sinnvoll ist davon nicht viel.

[;fricky]

hustbaer schrieb:

das ist theoretische und völlig unpraktikable hirnwichserei. interessiert mich kein bisschen. anwendbarkeit = 0.

mannomann, natürlich bastelt sich keiner absichtliche stack-overflows oder so, aber das war nie die frage. es gibt seltene situationen, in denen sowas u.ä. vorkommen kann, und dann ist SEH eine sehr willkommene sache.

hustbaer schrieb:

WENN man aber C++ verwendet, dann bitte richtig. und dann kann man keine kunstgriffe brauchen, die es einem verbieten destruktoren zu verwenden.

was richtig oder falsch ist, kann immer noch jeder, situationsbedingt, für sich selbst entscheiden. aber diese starre schwarz/weiss-ganz-oder-garnicht haltung ist ja mal wieder typisch für dich. *cry*