Fehlschlag: Stack Koroutinen

Aus Fehlern lernt man bekanntlich am meisten, und deshalb möchte ich einen meiner Irrtümer hier schildern.
Es begann mit der Idee:

Man könnte doch einen Stack durch diverse Funktionsaufrufe aufblasen und dann per setjmp() “Einsprungpunkte” in den Stack setzen. Wenn man dann noch einen Scheduler schreibt, der per longjmp() zwischen diesen Einsprungpunkten auswählen kann, dann hätte man:
Eine rein generische C Implementierung für Koroutinen.

Spoiler: Ich lag falsch.
Naja, in kleinen Teilen lag ich fast richtig … doch leider nur im 32 bit Debug-Modus, wo der Callstack schön und nicht normiert ist.
Ein Patent brauche ich auf meine Idee also nicht anmelden.

Es hat sich nämlich ganz deutlich gezeigt, dass man mit setjmp und longjmp() im Stack nur “zurückspringen” kann, also in Richtung des Aufrufers. Der andere Weg, also der Sprung in eine Unterfunktion klappt leider nicht und führt zu Segmentation-Faults und Schlimmerem.

Idee: Stack-Aufteilung per setjmp

Stellt euch vor, wer setzen in einer Funktion einen Anker mit setjmp() und rufen dann eine Funktion auf, die einen Datenblock auf dem Stack allokiert und sich dann selbst aufruft.
Zuvor legen wir mit einem weiteren setjmp einen Anker auf den aktuellen Funktionsaufruf, bevor wir uns selbst aufrufen.
Und mit einem Counter würden wir sicherstellen, dass das nicht unendlich oft passiert und wir nach N-Aufrufen per longjmp zum Ausgangspunkt zurückkehren.

Da wir (theoretisch) aus keiner Funktion mit return zurückgesprungen sind, sondern nur longjmp dafür gebraucht haben, sollte der Stapelspeicher (Stack) über uns (eigentlich unter uns) dann immer noch aufrecht sein.

Nun könnten wir mit weiteren longjmp Aufrufen zwischen den Stack-Teilen hin und her springen und dort andere Funktionen aufrufen, da wir ja stets einen “lokalen” Block allokiert hatten, der den Stack weiter aufgeblasen hat.
Die Funktionen in den Stack-Teilen sollten sich also gegenseitig nicht stören, so lange ihre eigenen Allokationen kleiner als unser Block sind.

Ein Beispiel-Code sagt mehr als tausend Worte:

 #include <setjmp.h>
 typedef void(*entry_point_function)(void* param);
 
 static jmp_buf volatile origin;
 
 struct context
 {
   jmp_buf volatile anchor;
   entry_point_function func;
  void* func_param;
};

#define MAX_STACKS 16
#define MAX_STACK_SIZE 16384

static struct context volatile contexts[MAX_STACKS];

static void stack_entry_point(int counter);

static void create_stack_partition(int counter)
{
  /* just reserve stack space */
  char volatile stack_buffer[MAX_STACK_SIZE];
  stack_entry_point(counter);
}

static void stack_entry_point(int counter)
{
  struct context volatile* ptr_context = &contexts[counter];
  if(setjmp(ptr_context->anchor) == 0)
  {
    /* stack-entry-point registration completed */
    if(counter > 0)
    {
      create_stack_partition(counter - 1);  
    }
  }
  else
  {
    /* entry point from longjmp() */
    ptr_context->func(ptr_context->func_param);
  }
  longjmp(origin, 1);
}

void scheduler()
{
  /* set function-pointers in @contexts */
  /* ... */
  /* prepare stack */
  if(setjmp(origin) == 0)
  {
    create_stack_partition(MAX_STACKS - 1);
  }

  /* longjmp into stack-partition */
  /* ... */
}

Jetzt muss man noch ein paar Details erweitern, z.B., dass am besten jede Variable volatile wird und der stack_buffer am besten mit einer for Schleife befüllt wird, weil der Compiler den Block trotz volatile gerne rausoptimiert … aber grundsätzlich “läuft das” … denkt man.

Problem != x86_32

Der x86 Befehlssatz im 32 Bit Modus erlaubt das tatsächlich. Wir könnten mit setjmp/longjmp tatsächlich Koroutinen bauen und mit ein paar Tricks auch manche Optimierungsfallen des Compiler umgehen.
Und ich wette, dass man auf x86-16bit und diversen Mikrocontrollern ebenfalls Erfolge sehen könnte.

Doch andere Architekturen wie x86-64 oder ARM sind durchaus anders aufgebaut und machen das Arbeiten mit longjmp generell schwer.
Microsoft schreibt etwa in seine Dokumentation:

In Microsoft C++ code on Windows, longjmp uses the same stack-unwinding semantics as exception-handling code. It is safe to use in the same places that C++ exceptions can be raised. However, this usage is not portable, and comes with some important caveats.

Tja, und da fängt wohl das Problem an, denn während unter 32-Bit das Exception-Handling von Funktion zu Funktion gesetzt werden musste, registrieren sich diese Handler heute über das OS um von dort im Fehlerfall aufgerufen zu werden.
Durch meinen longjmp nach der “Partitionierung” des Stacks zurück zur Scheduler-Funktion wird also die Stackaufteilung zerstört.
Und dass dann eine Funktion in ntdll.dll die Validität des Stacks prüft, wenn ein weiterer longjmp in ein Stack-Fragment erfolgt, ist für meine Zwecke natürlich schlecht
… aber es war ja auch nirgends definiert, dass das nicht so sein darf.

Letztendlich sind meine Experimente mit “undefiniertem Verhalten” gelaufen. Und bestimmt gibt es zahlreiche ähnliche Probleme auf weiteren Plattformen.

Fazit

Jetzt kenne ich also den Grund, warum boost::coroutine und andere Bibliotheken nicht ohne Assembler Code auskommen, um Ausführungskontexte zu sichern und wiederherzustellen.
Denn die hätten setjmp/longjmp ansonsten sicher auch gerne genutzt …

Wie heißt es etwa im Film Das Vermächtnis der Tempelritter:

Gescheitert bin ich nicht, ich kenne 2.000 Wege wie man Glühbirnen nicht bauen darf. Aber ein einziger hätte gereicht, damit es funktioniert.

Tja, schade. Ich hatte schon eine ganze Koroutinen Implementierung fertig, die auf diesem Schema basiert. Und laut einiger Tests hat die auch super funktioniert … aber eben nur unter Windows 32 bit und sonst nirgends.

Ich habe das “Negativ-Beispiel” trotzdem in den “Class-Room” aufgenommen. Denn wie schon gesagt: “Aus Fehlern lernt man.”