docs/pws2002/coro.sdf

!init OPT_STYLE="paper"

!define DOC_NAME        "Coroutinen und Continuations mit dem Coro-Modul"
!define DOC_AUTHOR      "Marc Lehmann <pcg@goof.com>"
!build_title

H1: Die Entstehung des Coro-Moduls

Continuations für Perl5 stehen seit ca. 1996 auf meinem "TODO"-Zettel,
aber da ich immer dachte, es wäre viel zu langsam (Kopieren des gesamten
Stacks oder schlimmer?) und kompliziert, um jemals implementiert zu
werden.

H1: Das Problem

Um Coroutinen zu implementieren, reicht es, zwei Primitiven zu schreiben
(die Namen stammen aus Modula-2, die Perl-Syntax sieht etwas anders aus):

 NEWPROCESS(process,coderef)
 TRANSFER(oldprocess,newprocess)

C<NEWPROCESS< erzeugt einen neuen "Prozess", wobei ein "Prozess" im
wesentlichen einen Aufrufstack (zum Schachteln von Funktionsaufrufen)
und einen Startpunkt (C<coderef>) besitzt. Diese Daten werden in einer
Struktur (C<process>) abgelegt.

Um einen solchen Prozess zu starten muß man die Kontrolle an ihn abgeben,
indem man C<TRANSFER> mit einer leeren C<process>-Struktur als erstes
Argument und einer gültigen (z.b. von C<NEWPROCESS>) C<process>-Struktur
als zweites Argument aufruft.

C<TRANSFER> sichert nun die Daten des {{aktuellen}} Prozesses in
C<oldprocess> und "springt" in den neuen.

Damit lassen sich Continuations und kooperatives und preemptives
Multitasking implementieren, wenn man es zu nutzen weiß.

H1: Teil 1: Implementation

H2: Erste Erfolge und erste Probleme

Im Juli 2001 war es dann so weit: in einem Anflug von Leichtsinn dachte
ich mir, "ein paar Pointer-Austauscher könnten doch zum Ziel führen".

(Es folgen einige Haarsträubende Implementationsdetails, wer will, kann
die überspringen und direkt zum interessanten Teil übergehen ;)

Und tatsächlich, wenige Stunden (und Zeilen) später hatte ich ein Modul,
daß die beiden obigen Primitiven implementiert. Es funktionierte sogar:

!block "C"
 save_state(pTHX_ Coro__State c, int flags)
 {
   c->curstackinfo = PL_curstackinfo;
   c->curstack = PL_curstack;
   c->mainstack = PL_mainstack;
   c->stack_sp = PL_stack_sp;
   c->op = PL_op;
   ...
   c->curcop = PL_curcop;
   c->top_env = PL_top_env;
 }

 load_state(pTHX_ Coro__State c)
 {
   PL_curstackinfo = c->curstackinfo;
   PL_curstack = c->curstack;
   PL_mainstack = c->mainstack;
   PL_stack_sp = c->stack_sp;
   PL_op = c->op;
   ...
   PL_curcop = c->curcop;
   PL_top_env = c->top_env;
 }
!endblock

Bis einmal zwei Coroutinen dieselbe Funktion aufriefen. Viele
Stunden später kam dann das "Aha! So macht Perl das also. Na so ein
Mist...". Leider reicht es nicht, einfach die vielen Stacks auszutauschen,
die Perl benutzt. Denn Perl modifiziert bei jedem Aufruf einer Funktion
die Funktion (genauer: den CV) selbst:

!block "C"
  /* aus pp_entersub */
  CvDEPTH(cv)++;
  if (CvDEPTH(cv) < 2)
      (void)SvREFCNT_inc(cv);
  else {        /* save temporaries on recursion? */
      PERL_STACK_OVERFLOW_CHECK();
      if (CvDEPTH(cv) > AvFILLp(padlist)) {
         /* hier wird eine neue padlist erzeugt - 40 Zeilen Magie */
         ...
      }
  }
  ...
  PL_curpad = AvARRAY((AV*)svp[CvDEPTH(cv)]);
!endblock

Da wurde mir auch klar, weshalb Threads so langsam sind, denn die müssen
unglaubliche Anstrengungen unternehmen, damit sich einzelne Threads nicht
in die Queue kommen. C<pp_entersub> ist alles andere als trivial, ein
Wunder, daß Perl so schnell ist.

Im wesentlichen geht es darum, für jede Rekursionsstufe eine C<padlist>
(in der werden lokale Variablen u.ä. gespeichert) zu erzeugen, wobei die
erste schon beim Kompilieren erzeugt wird.

Solange eine Coroutine nicht in eine Funktion springt, die schon rekursiv
aufgerufen wurde, ist das kein Problem, da CvDEPTH dann 1 ist und die
erste padlist leer. Andernfalls wird die Rekursionsstufe erhöht, auch
kein Problem.  Wenn die erste Coroutine dann aber wieder aus der Funktion
zurückkehren will, gibt es ein Problem, denn das käme dem Problem
gleich, die n-te Rekursionsstufe zu beenden während die n+1-te nich immer
aktiv ist.

Die Lösung ist eklig, aber noch nicht unzumutbar langsam: Da ein
Perl-Modul nicht die Freiheit hat, C<pp_entersub> zu verändern (die
Perl-Thread-Implementation kann sich das leisten), muss der Aufrufstack
hinaufgewandert werden und manuell eine Art "Rücksprung" organisiert werden:

!block "C"
 save_state(pTHX_ Coro__State c, int flags)
 ...
    /* this loop was inspired by pp_caller */
    for (;;)
      { 
        while (cxix >= 0)
          {
            PERL_CONTEXT *cx = &ccstk[cxix--];
            
            if (CxTYPE(cx) == CXt_SUB)
              {
                CV *cv = cx->blk_sub.cv;
                if (CvDEPTH(cv))
                  {
                    EXTEND (SP, CvDEPTH(cv)*2);

                    while (--CvDEPTH(cv))
                      {
                        /* this tells the restore code to increment CvDEPTH */
                        PUSHs (Nullsv);
                        PUSHs ((SV *)cv);
                      }

                    PUSHs ((SV *)CvPADLIST(cv));
                    PUSHs ((SV *)cv);

                    get_padlist (cv); /* this is a monster */
                  }
              }
        ...
        if (top_si->si_type == PERLSI_MAIN)
          break;

        top_si = top_si->si_prev;
        ccstk = top_si->si_cxstack;
        cxix = top_si->si_cxix;
      }
 ...

 load_state(pTHX_ Coro__State c)
 ...
    /* now do the ugly restore mess */
    while ((cv = (CV *)POPs))
      {
        AV *padlist = (AV *)POPs;
  
        if (padlist)
          {
            put_padlist (cv); /* mark this padlist as available */
            CvPADLIST(cv) = padlist;
          }
  
        ++CvDEPTH(cv);
      }
!endblock

Der lustigste Teil verbirgt sich hinter:

 get_padlist (cv); /* this is a monster */

Denn, während man die neu erzeugten padlists einfach wegsichern kann,
muss die erste neu erzeugt werden, ein höchst umständlicher Vorgang, der
deshalb auch (mit einem Hash) gecached wird.

Damit war bewiesen, daß Coroutinen tatsächlich so viele Probleme machen,
wie ich befürchtet hatte.

H2: Das vorläufige Ende

Aber es kam noch schlimmer. Beispiel: Perl ruft eine XS-Funktion auf, und
diese wieder einen Perl-Callback. Dieser führt einen Coroutinenwechsel
durch und die neue Coroutinen macht ein C<return> - wohin? In die
XS-Funktion, die natürlich Ergebnisse auf dem Stack erwartet, die
natürlich nicht da sind.

An diesem Punkt habe ich erstmal aufgegeben. Die Aussicht, auch eine
portable Coroutinenimplementation für C zu finden, waren Null, sie werden
ja noch nicht einem in irgendwelchen Standards erwähnt (dachte ich).

Naja, selbst schreiben war angesagt - tatsächlich kann man, lediglich
mit UNIX95-Funktionen, portabel Coroutinen erzeugen. Leider ist mir
kein System bekannt, daß sich wirklich an den Standard hielte (von
Grausamkeiten wie IRIX mal ganz abgesehen, dessen Programmierer vom
Programmieren herzlich wenig Ahnung haben (siehe sigaltstack, das
vollkommen dokumentiert das vollkommen sinnlose macht)), aber die
Unterschiede sind gering. Sogar unter der eingeschränkten Win32-API
kann man durch direktes herumpoken in C<jmp_buf> relativ schmerzlos eine
Implementation bekommen.

Im Coro-Modul gibt es im Verzeichnis C<Coro/libcoro> seitdem eine
relativ portable, sehr kleine (366 Zeilen inkl. Dokumentation ;)
Coroutinenimplementation für C.

Das Coro-Modul erzeugt entweder für jede Coroutine in Perl eine Coroutine
in C, oder optional nur "on demand", d.h. wenn sich der C-Stackpointer
verändert hat, eine gefährliche, aber in der Praxis gut funktionierende
Heuristik.

H1: Teil 2: Implementation von Coroutinen und Continuations in Perl

H2: Die Perl-API

C<NEWPROCESS> und C<TRANSFER> werden vom C<Coro::State>-Modul implementiert.
C<NEWPROCESS> sieht in Perl so aus:

!block "perl"
 # eine "leere" Coroutine, bereit, gefüllt zu werden
 $main = new Coro::State;

 # eine neue Coroutine, zu der man wechseln kann
 $new = new Coro::State sub {
    # ... coroutine
 }, @args;
!endblock

Und C<TRANSFER> sieht so aus:

!block "perl"
 # etwas asymetrisch:
 $main->transfer($new);
 # oder symmetrischer
 Coro::State::transfer($main,$new);
!endblock

H2: Continuations

Nicht, daß ich das Modul viel benutzen würde, aber ich wollte zeigen,
daß es geht: Das C<Coro::Cont>-Modul exportiert zwei Funktionen, C<csub>,
mit dem sich neue Continuations erzeugen lassen und C<yield>, das so
ähnlich wie C<return> wirkt. Ausserdem werden Attribute unterstützt, so,
daß man Continuations so schreiben kann:

!block "perl"
 use Coro::Cont;

 sub generator : Cont {
    my $state = time;
    while() {
       $state = $state * 31231 % 65531;
       yield $state % $_[0];
    }
 }
!endblock

Beim ersten Aufruf wird der Zustand initialisiert, bei jedem weiteren
Aufruf wird eine (schlechte) Zufallszahl im Bereich C<0..$_[0]>
zurückgeliefert, wobei @_ sich jedesmal ändert. Das Attributsystem von
Perl5 ist ziemlich schwer zu benutzen (mehrere Module können es sich
nicht einfach teilen, Attribute sind automatisch global etc..), weshalb
ich darauf nicht näher eingehe ;)

Die Implementation ist einigermassen trickreich, da die Standardimplementation
von C<transfer> das Array C<@_> mitspeichert, es also nicht so einfach übergeben
werden kann. Deshalb kann man C<transfer> ein drittes Argument, eine Bitmaske
mit Flags, übergeben, die angibt, ob C<@_> oder C<$_> u.ä. Teil des
"Prozesszustandes" werden oder nicht.

C<csub> erzeugt zwei C<Coro::State>-Objekte, eines für den Aufrufer und eines
für die Continuation:

!block "perl"
 sub csub(&) {
    my $code = $_[0];
    my $prev = new Coro::State;

    my $coro = new Coro::State sub {
       # we do this superfluous switch just to
       # avoid the parameter passing problem
       # on the first call
       &yield;
       &$code while 1;
    };
!endblock

D.h. die Kode-Referenz wird in einer Schleife aufgerufen. Da die Parameter
beim ersten Aufruf der Coroutine etwas anders übergeben werden als
später bei C<yield> wird als erstes ein C<yield> ausgeführt, damit alle
Aufrufe identisch sind.

Als nächstes wird die neu erzeugte Coroutine {{einmal}} aufgerufen (damit
sie "yield"-en kann):

!block "perl"
   push @$$return, [$coro, $prev];
   &Coro::State::transfer($prev, $coro, 0);
!endblock

In der gobalen Variablen C<$return> befindet sich eine eine Referenz
auf ein Array, in dem die "Rücksprung"-Coroutinen gespeichetr sind,
d.h. C<Coro::Cont> macht fast den gleichen "Fehler" wie C<pp_entersub>,
aber C<$$return> ist nicht wirklich global (wie ich gleich zeige ;)

Als letztes wird eine Kode-Referenz zurückgegeben, die das Aufrufen der
Coroutine für uns erledigt:

!block "perl"
   return sub {
      push @$$return, [$coro, $prev];
      &Coro::State::transfer($prev, $coro, 0);
      wantarray ? @_ : $_[0];
   };
!endblock

Auch hier wird die "Rücksprungaddresse" für C<yield> in C<@$$return>
gespeichert und dann die Coroutine aufgerufen, die beim nächsten C<yield>
zurückkehrt. Die Argumente, die die Coroutine an C<yield> übergeben hat,
stehen immer noch in C<@_>.

Die Funktion C<yield> ist in XS implementiert, die
Prototyp-Implementation in Perl sah jedoch so aus:

!block "perl"
 sub yield(@) {
    &Coro::State::transfer(@{pop @$$return}, 0);
    wantarray ? @_ : $_[0];
 }
!endblock

Auch nichts überraschendes, es wird zum Aufrufer zurückgegeben. Beim
nächsten Aufruf wird das neue C<@_> zurückgegeben, d.h. der Aufruf
müsste lauten: C<@_ = yield ...>, und das ist der Grund, weshalb es
in XS implementiert wurde, denn in XS kann man das C<@_> des Aufrufers
verändern. Wäre nicht dieser Umstand. so würde auch C<yield> in reinem
Perl implementiert sein.

Das verbleibende Problem ist die globale Variable C<$return>. Tatsächlich
ist sie ein C<Coro::Specific>-Objekt und ist "Coroutinen"spezifisch, d.h.
kann in jeder Coroutine (hier meine ich ein C<Coro>-Objekt und nicht das
C<Coro::State>-Objekt) einen anderen Wert besitzen.

H2: C<Coro::Specific>

Mit C<Coro::State> kann man eigene Prozess-Abstraktionen basteln. Damit
C<Coro::Specific> funktioniert, muß man lediglich einen
coroutinen-/prozessspezifischen Hash in C<$Coro::current> speichern, und
genau das macht das C<Coro>-Modul.

C<Coro::Specific->new> gibt eine Referenz auf einen ge'tie'ten Scalar zurück, der
wiederum bei C<FETCH> und C<STORE> einen Skalar im Array
C<@{$Coro::current->{specific}}> verändert. Solange das C<Coro>-Modul nicht
geladen ist, istd as immer derselbe, danach ist er coroutinenspezifisch.

!block "perl"
 my $idx;

 sub new {
    my $var;
    tie $var, Coro::Specific::;
    \$var;
 }

 sub TIESCALAR {
    my $idx = $idx++;
    bless \$idx, $_[0];
 }

 sub FETCH {
    $Coro::current->{specific}[${$_[0]}];
 }

 sub STORE {
    $Coro::current->{specific}[${$_[0]}] = $_[1];
 }
!endblock

Auf diese Weise kann man in anderen Modulen ohne schlechtes Gewissen
C<Coro::Specific> verwenden, da weder C<Coro::State> noch C<Coro> geladen
sein müssen.

H2: Prozesse selbst gemacht

Der nächste Schritt, nach Continuations, Variablen und (primitiven)
Coroutinen sind richtige Prozesse. Diese werden im C<Coro>-Modul
implementiert, daß Prozesserzeugung, Kommunikation, Prioritäten etc.
anbietet.

Das sieht dann so aus:

!block "perl"
 use Coro:

 async {
    # ein neuer "Prozess"
 };

 my $coro = async {
    terminate;
 };

 $coro->prio(PRIO_MAX);
 $coro_>join;

 cede; # gib die CPU frei für andere Prozesse

 # usw.. hat ja "jeder" schon mal gesehen ;-]
!endblock

Die Implementation ist in einigen Teilen in XS, der Geschwindigkeit
wegen. Wenn das Modul geladen wird, erzeugt es zuerst einen
"Hauptprozess", der für das Hauptprogramm steht (das Hauptprogramm
korrekt auf eine Coroutine abzubilden ist sowieso ein sehr schwieriges
Unterfangen - welche Coroutine DESTROY't die anderen Coroutinen am
Programmende, wenn das Hauptprogramm nicht mehr existiert?) und sorgt für
die Übernahme des bisherigen C<@{$Coro::current->{specific}}>.

!block "perl"
 our $main = new Coro;

 # maybe some other module used Coro::Specific before...
 if ($current) {
     $main->{specific} = $current->{specific};
 }  

 our $current = $main;
!endblock

Dann folgt die Erzeugung eines Idle-Prozesses, der Rechenzeit verbrät wenn kein
Prozess mehr läuft:

!block "perl"
 our $idle = new Coro sub {
     print STDERR "FATAL: deadlock detected\n";
     exit(51);
 };
!endblock

Jaja, reingefallen. Wenn kein Prozeß mehr am laufen ist, haben wir einen
Deadlock, zumindest, solange man Signale außer acht läßt. Das ändert
sich, wenn man Events benutzt (z.B. mit C<Coro::Event>), weshalb der
Idle-Prozess auswechselbar ist.

Neue Prozesse werden mit C<async> oder C<Coro->new> erzeugt:

!block "perl"
 sub _newcoro {
    terminate &{+shift};
 }

 sub new {
    my $class = shift;
    bless {
       _coro_state => (new Coro::State $_[0] && \&_newcoro, @_),
    }, $class;
 }  

 sub async(&@) {
    my $pid = new Coro @_;
    $manager->ready; # this ensures that the stack is cloned from the manager
    $pid->ready;
    $pid;
 }
!endblock

Ein Prozess ist also wenig mehr als nackter Hash, in dessen
C<_coro_state>-Slot ein C<Coro::State>-Objekt gespeichert ist. Ähnlich
wie PDL sieht C<transfer> in diesem Slot nach einem C<Coro::State>-Objekt.

Interessanter ist, daß C<async> den C<$manager> in Bereitschaft versetzt
und nicht nur den neuen Prozess. Der einzige Grund dafür ist, daß so die
meisten Prozesse mit einem definierten Stackpointer erzeugt werden, so
daß derselbe C-Stack für alle Prozesse verwendet werden kann, zumindest
anfänglich.

Am Ende eines Prozesslebens steht ein C<terminate>, oder ein C<cancel>:

!block "perl"
 sub cancel {
    push @destroy, $_[0];
    $manager->ready;
    &schedule if $current == $_[0];
 }
!endblock

C<schedule> springt direkt in den Scheduler, der den nächsten
lauffähigen Prozess aus der Warteschlange nimmt und zum aktuellen
macht. Er ist (jaja, "the need for speed") in XS implementiert, sieht aber
in etwa (keine Prioritäten) so aus:

!block "perl"
 sub schedule {
    my $previous = $current;
    $current = shift @runqueue;
    Coro::State::transfer($current, $previous);
 }
!endblock

Der aktuelle Prozess wird nicht automatishc wieder aufgerufen, dazu muss
man ihn wieder mit der C<ready>-Methode in die Warteschlange setzen. Um
nur kurz andere Prozesse laufen zu lassen konnte man früher C<yield>
benutzen, aber das ging schon für Continuations drauf, und Damian Conway
fand das wichtiger, also musste ich einen neuen Namen finden:

!block "perl"
 sub cede {
    $current->ready;
    schedule;
 }
!endblock

Einen Prozess direkt zu zerstören, ist keine gute Idee. Zum einen könnte
er mehrfach in der C<ready>-Queue stehen, zum anderen sollte ein Prozess
sich selbst C<DESTROY>en können, aber da er sich dabei selbst den C-Stack
wegzieht, muss dies von einem anderen Prozess aus stattfinden. Der
Manager-Prozess stellt genau dies sicher (und verständig auch gleich
eventuell wartende Prozesse):

!block "perl"
 my @destroy;
 my $manager;
 $manager = new Coro sub {
    while() {
       # by overwriting the state object with the manager we destroy it
       # while still being able to schedule this coroutine (in case it has
       # been readied multiple times. this is harmless since the manager
       # can be called as many times as neccessary and will always
       # remove itself from the runqueue
       while (@destroy) {
          my $coro = pop @destroy;
          $coro->{status} ||= [];
          $_->ready for @{delete $coro->{join} || []};
          $coro->{_coro_state} = $manager->{_coro_state};
       }
       &schedule;
    }
 };
!endblock

H2: Signale, Semaphoren, Channels und Locks

Hat man Prozesse, die man erzeugen, anhalten, schedulen und wieder beenden
kann, so muss man sie koordinieren. Zum Beispiel mit C<Coro::Signal>'s:

!block "perl"
 sub send {
    if (@{$_[0][1]}) {
       (shift @{$_[0][1]})->ready;
    } else {
       $_[0][0] = 1;
    }
 }

 sub wait {
    if ($_[0][0]) {
       $_[0][0] = 0;
    } else {
       push @{$_[0][1]}, $Coro::current;
       Coro::schedule;
    }
 }
!endblock

Getreu dem Motto "Pseudo-Hashes müssen sterben!", etwas ungewöhnlich
ausgelegt, verwendet C<Coro::Signal> ein Array und keinen Hash. Das erste
element ist nur ein Flag, das angibt, ob das Signal gesendet wurde (falls
niemand darauf wartet). Das zweite Element ist ein Array von wartenden
Prozessen.

C<send> weckt den ersten wartenden Prozess auf oder - falls es keinen gibt
- setzt das Flag. Wenn man auf ein Signal wartet, wird zuerst geprüft, ob
es schon aufgetreten ist, ansonsten reiht sich der aktuelle Prozess in die
Warteschlange und legt sich schlafen.

H1: Teil 3: Die Aussenwelt

!block "perl"
!endblock

!block "perl"
!endblock

!block "perl"
!endblock


A1: Module

- Coro (Coroutinen)
- Event (der Event-Standard, nur leider unmaintained)
- Linux::AIO (asynchrone Ein-/Ausgabe)
- Convert::Scalar (für C<weaken>)
- HTTP::Date (code-reuse made easy with CPAN, hat mir sicherlich 5 Minuten gespart)
- Date::Parse (siehe HTTP::Date, ich liebe CPAN ;)
- BerkeleyDB (Caching der Directory-Listings und WHOIS-Requests)


Revision:	1.1
Committed:	Tue Jan 15 01:58:40 2002 UTC (24 years, 9 months ago) by root
Branch:	MAIN
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	!init OPT_STYLE="paper"
2
3			!define DOC_NAME "Coroutinen und Continuations mit dem Coro-Modul"
4			!define DOC_AUTHOR "Marc Lehmann <pcg@goof.com>"
5			!build_title
6
7			H1: Die Entstehung des Coro-Moduls
8
9			Continuations für Perl5 stehen seit ca. 1996 auf meinem "TODO"-Zettel,
10			aber da ich immer dachte, es wäre viel zu langsam (Kopieren des gesamten
11			Stacks oder schlimmer?) und kompliziert, um jemals implementiert zu
12			werden.
13
14			H1: Das Problem
15
16			Um Coroutinen zu implementieren, reicht es, zwei Primitiven zu schreiben
17			(die Namen stammen aus Modula-2, die Perl-Syntax sieht etwas anders aus):
18
19			NEWPROCESS(process,coderef)
20			TRANSFER(oldprocess,newprocess)
21
22			C<NEWPROCESS< erzeugt einen neuen "Prozess", wobei ein "Prozess" im
23			wesentlichen einen Aufrufstack (zum Schachteln von Funktionsaufrufen)
24			und einen Startpunkt (C<coderef>) besitzt. Diese Daten werden in einer
25			Struktur (C<process>) abgelegt.
26
27			Um einen solchen Prozess zu starten muß man die Kontrolle an ihn abgeben,
28			indem man C<TRANSFER> mit einer leeren C<process>-Struktur als erstes
29			Argument und einer gültigen (z.b. von C<NEWPROCESS>) C<process>-Struktur
30			als zweites Argument aufruft.
31
32			C<TRANSFER> sichert nun die Daten des {{aktuellen}} Prozesses in
33			C<oldprocess> und "springt" in den neuen.
34
35			Damit lassen sich Continuations und kooperatives und preemptives
36			Multitasking implementieren, wenn man es zu nutzen weiß.
37
38			H1: Teil 1: Implementation
39
40			H2: Erste Erfolge und erste Probleme
41
42			Im Juli 2001 war es dann so weit: in einem Anflug von Leichtsinn dachte
43			ich mir, "ein paar Pointer-Austauscher könnten doch zum Ziel führen".
44
45			(Es folgen einige Haarsträubende Implementationsdetails, wer will, kann
46			die überspringen und direkt zum interessanten Teil übergehen ;)
47
48			Und tatsächlich, wenige Stunden (und Zeilen) später hatte ich ein Modul,
49			daß die beiden obigen Primitiven implementiert. Es funktionierte sogar:
50
51			!block "C"
52			save_state(pTHX_ Coro__State c, int flags)
53			{
54			c->curstackinfo = PL_curstackinfo;
55			c->curstack = PL_curstack;
56			c->mainstack = PL_mainstack;
57			c->stack_sp = PL_stack_sp;
58			c->op = PL_op;
59			...
60			c->curcop = PL_curcop;
61			c->top_env = PL_top_env;
62			}
63
64			load_state(pTHX_ Coro__State c)
65			{
66			PL_curstackinfo = c->curstackinfo;
67			PL_curstack = c->curstack;
68			PL_mainstack = c->mainstack;
69			PL_stack_sp = c->stack_sp;
70			PL_op = c->op;
71			...
72			PL_curcop = c->curcop;
73			PL_top_env = c->top_env;
74			}
75			!endblock
76
77			Bis einmal zwei Coroutinen dieselbe Funktion aufriefen. Viele
78			Stunden später kam dann das "Aha! So macht Perl das also. Na so ein
79			Mist...". Leider reicht es nicht, einfach die vielen Stacks auszutauschen,
80			die Perl benutzt. Denn Perl modifiziert bei jedem Aufruf einer Funktion
81			die Funktion (genauer: den CV) selbst:
82
83			!block "C"
84			/* aus pp_entersub */
85			CvDEPTH(cv)++;
86			if (CvDEPTH(cv) < 2)
87			(void)SvREFCNT_inc(cv);
88			else { /* save temporaries on recursion? */
89			PERL_STACK_OVERFLOW_CHECK();
90			if (CvDEPTH(cv) > AvFILLp(padlist)) {
91			/* hier wird eine neue padlist erzeugt - 40 Zeilen Magie */
92			...
93			}
94			}
95			...
96			PL_curpad = AvARRAY((AV*)svp[CvDEPTH(cv)]);
97			!endblock
98
99			Da wurde mir auch klar, weshalb Threads so langsam sind, denn die müssen
100			unglaubliche Anstrengungen unternehmen, damit sich einzelne Threads nicht
101			in die Queue kommen. C<pp_entersub> ist alles andere als trivial, ein
102			Wunder, daß Perl so schnell ist.
103
104			Im wesentlichen geht es darum, für jede Rekursionsstufe eine C<padlist>
105			(in der werden lokale Variablen u.ä. gespeichert) zu erzeugen, wobei die
106			erste schon beim Kompilieren erzeugt wird.
107
108			Solange eine Coroutine nicht in eine Funktion springt, die schon rekursiv
109			aufgerufen wurde, ist das kein Problem, da CvDEPTH dann 1 ist und die
110			erste padlist leer. Andernfalls wird die Rekursionsstufe erhöht, auch
111			kein Problem. Wenn die erste Coroutine dann aber wieder aus der Funktion
112			zurückkehren will, gibt es ein Problem, denn das käme dem Problem
113			gleich, die n-te Rekursionsstufe zu beenden während die n+1-te nich immer
114			aktiv ist.
115
116			Die Lösung ist eklig, aber noch nicht unzumutbar langsam: Da ein
117			Perl-Modul nicht die Freiheit hat, C<pp_entersub> zu verändern (die
118			Perl-Thread-Implementation kann sich das leisten), muss der Aufrufstack
119			hinaufgewandert werden und manuell eine Art "Rücksprung" organisiert werden:
120
121			!block "C"
122			save_state(pTHX_ Coro__State c, int flags)
123			...
124			/* this loop was inspired by pp_caller */
125			for (;;)
126			{
127			while (cxix >= 0)
128			{
129			PERL_CONTEXT *cx = &ccstk[cxix--];
130
131			if (CxTYPE(cx) == CXt_SUB)
132			{
133			CV *cv = cx->blk_sub.cv;
134			if (CvDEPTH(cv))
135			{
136			EXTEND (SP, CvDEPTH(cv)*2);
137
138			while (--CvDEPTH(cv))
139			{
140			/* this tells the restore code to increment CvDEPTH */
141			PUSHs (Nullsv);
142			PUSHs ((SV *)cv);
143			}
144
145			PUSHs ((SV *)CvPADLIST(cv));
146			PUSHs ((SV *)cv);
147
148			get_padlist (cv); /* this is a monster */
149			}
150			}
151			...
152			if (top_si->si_type == PERLSI_MAIN)
153			break;
154
155			top_si = top_si->si_prev;
156			ccstk = top_si->si_cxstack;
157			cxix = top_si->si_cxix;
158			}
159			...
160
161			load_state(pTHX_ Coro__State c)
162			...
163			/* now do the ugly restore mess */
164			while ((cv = (CV *)POPs))
165			{
166			AV padlist = (AV )POPs;
167
168			if (padlist)
169			{
170			put_padlist (cv); /* mark this padlist as available */
171			CvPADLIST(cv) = padlist;
172			}
173
174			++CvDEPTH(cv);
175			}
176			!endblock
177
178			Der lustigste Teil verbirgt sich hinter:
179
180			get_padlist (cv); /* this is a monster */
181
182			Denn, während man die neu erzeugten padlists einfach wegsichern kann,
183			muss die erste neu erzeugt werden, ein höchst umständlicher Vorgang, der
184			deshalb auch (mit einem Hash) gecached wird.
185
186			Damit war bewiesen, daß Coroutinen tatsächlich so viele Probleme machen,
187			wie ich befürchtet hatte.
188
189			H2: Das vorläufige Ende
190
191			Aber es kam noch schlimmer. Beispiel: Perl ruft eine XS-Funktion auf, und
192			diese wieder einen Perl-Callback. Dieser führt einen Coroutinenwechsel
193			durch und die neue Coroutinen macht ein C<return> - wohin? In die
194			XS-Funktion, die natürlich Ergebnisse auf dem Stack erwartet, die
195			natürlich nicht da sind.
196
197			An diesem Punkt habe ich erstmal aufgegeben. Die Aussicht, auch eine
198			portable Coroutinenimplementation für C zu finden, waren Null, sie werden
199			ja noch nicht einem in irgendwelchen Standards erwähnt (dachte ich).
200
201			Naja, selbst schreiben war angesagt - tatsächlich kann man, lediglich
202			mit UNIX95-Funktionen, portabel Coroutinen erzeugen. Leider ist mir
203			kein System bekannt, daß sich wirklich an den Standard hielte (von
204			Grausamkeiten wie IRIX mal ganz abgesehen, dessen Programmierer vom
205			Programmieren herzlich wenig Ahnung haben (siehe sigaltstack, das
206			vollkommen dokumentiert das vollkommen sinnlose macht)), aber die
207			Unterschiede sind gering. Sogar unter der eingeschränkten Win32-API
208			kann man durch direktes herumpoken in C<jmp_buf> relativ schmerzlos eine
209			Implementation bekommen.
210
211			Im Coro-Modul gibt es im Verzeichnis C<Coro/libcoro> seitdem eine
212			relativ portable, sehr kleine (366 Zeilen inkl. Dokumentation ;)
213			Coroutinenimplementation für C.
214
215			Das Coro-Modul erzeugt entweder für jede Coroutine in Perl eine Coroutine
216			in C, oder optional nur "on demand", d.h. wenn sich der C-Stackpointer
217			verändert hat, eine gefährliche, aber in der Praxis gut funktionierende
218			Heuristik.
219
220			H1: Teil 2: Implementation von Coroutinen und Continuations in Perl
221
222			H2: Die Perl-API
223
224			C<NEWPROCESS> und C<TRANSFER> werden vom C<Coro::State>-Modul implementiert.
225			C<NEWPROCESS> sieht in Perl so aus:
226
227			!block "perl"
228			# eine "leere" Coroutine, bereit, gefüllt zu werden
229			$main = new Coro::State;
230
231			# eine neue Coroutine, zu der man wechseln kann
232			$new = new Coro::State sub {
233			# ... coroutine
234			}, @args;
235			!endblock
236
237			Und C<TRANSFER> sieht so aus:
238
239			!block "perl"
240			# etwas asymetrisch:
241			$main->transfer($new);
242			# oder symmetrischer
243			Coro::State::transfer($main,$new);
244			!endblock
245
246			H2: Continuations
247
248			Nicht, daß ich das Modul viel benutzen würde, aber ich wollte zeigen,
249			daß es geht: Das C<Coro::Cont>-Modul exportiert zwei Funktionen, C<csub>,
250			mit dem sich neue Continuations erzeugen lassen und C<yield>, das so
251			ähnlich wie C<return> wirkt. Ausserdem werden Attribute unterstützt, so,
252			daß man Continuations so schreiben kann:
253
254			!block "perl"
255			use Coro::Cont;
256
257			sub generator : Cont {
258			my $state = time;
259			while() {
260			$state = $state * 31231 % 65531;
261			yield $state % $_[0];
262			}
263			}
264			!endblock
265
266			Beim ersten Aufruf wird der Zustand initialisiert, bei jedem weiteren
267			Aufruf wird eine (schlechte) Zufallszahl im Bereich C<0..$_[0]>
268			zurückgeliefert, wobei @_ sich jedesmal ändert. Das Attributsystem von
269			Perl5 ist ziemlich schwer zu benutzen (mehrere Module können es sich
270			nicht einfach teilen, Attribute sind automatisch global etc..), weshalb
271			ich darauf nicht näher eingehe ;)
272
273			Die Implementation ist einigermassen trickreich, da die Standardimplementation
274			von C<transfer> das Array C<@_> mitspeichert, es also nicht so einfach übergeben
275			werden kann. Deshalb kann man C<transfer> ein drittes Argument, eine Bitmaske
276			mit Flags, übergeben, die angibt, ob C<@_> oder C<$_> u.ä. Teil des
277			"Prozesszustandes" werden oder nicht.
278
279			C<csub> erzeugt zwei C<Coro::State>-Objekte, eines für den Aufrufer und eines
280			für die Continuation:
281
282			!block "perl"
283			sub csub(&) {
284			my $code = $_[0];
285			my $prev = new Coro::State;
286
287			my $coro = new Coro::State sub {
288			# we do this superfluous switch just to
289			# avoid the parameter passing problem
290			# on the first call
291			&yield;
292			&$code while 1;
293			};
294			!endblock
295
296			D.h. die Kode-Referenz wird in einer Schleife aufgerufen. Da die Parameter
297			beim ersten Aufruf der Coroutine etwas anders übergeben werden als
298			später bei C<yield> wird als erstes ein C<yield> ausgeführt, damit alle
299			Aufrufe identisch sind.
300
301			Als nächstes wird die neu erzeugte Coroutine {{einmal}} aufgerufen (damit
302			sie "yield"-en kann):
303
304			!block "perl"
305			push @$$return, [$coro, $prev];
306			&Coro::State::transfer($prev, $coro, 0);
307			!endblock
308
309			In der gobalen Variablen C<$return> befindet sich eine eine Referenz
310			auf ein Array, in dem die "Rücksprung"-Coroutinen gespeichetr sind,
311			d.h. C<Coro::Cont> macht fast den gleichen "Fehler" wie C<pp_entersub>,
312			aber C<$$return> ist nicht wirklich global (wie ich gleich zeige ;)
313
314			Als letztes wird eine Kode-Referenz zurückgegeben, die das Aufrufen der
315			Coroutine für uns erledigt:
316
317			!block "perl"
318			return sub {
319			push @$$return, [$coro, $prev];
320			&Coro::State::transfer($prev, $coro, 0);
321			wantarray ? @_ : $_[0];
322			};
323			!endblock
324
325			Auch hier wird die "Rücksprungaddresse" für C<yield> in C<@$$return>
326			gespeichert und dann die Coroutine aufgerufen, die beim nächsten C<yield>
327			zurückkehrt. Die Argumente, die die Coroutine an C<yield> übergeben hat,
328			stehen immer noch in C<@_>.
329
330			Die Funktion C<yield> ist in XS implementiert, die
331			Prototyp-Implementation in Perl sah jedoch so aus:
332
333			!block "perl"
334			sub yield(@) {
335			&Coro::State::transfer(@{pop @$$return}, 0);
336			wantarray ? @_ : $_[0];
337			}
338			!endblock
339
340			Auch nichts überraschendes, es wird zum Aufrufer zurückgegeben. Beim
341			nächsten Aufruf wird das neue C<@_> zurückgegeben, d.h. der Aufruf
342			müsste lauten: C<@_ = yield ...>, und das ist der Grund, weshalb es
343			in XS implementiert wurde, denn in XS kann man das C<@_> des Aufrufers
344			verändern. Wäre nicht dieser Umstand. so würde auch C<yield> in reinem
345			Perl implementiert sein.
346
347			Das verbleibende Problem ist die globale Variable C<$return>. Tatsächlich
348			ist sie ein C<Coro::Specific>-Objekt und ist "Coroutinen"spezifisch, d.h.
349			kann in jeder Coroutine (hier meine ich ein C<Coro>-Objekt und nicht das
350			C<Coro::State>-Objekt) einen anderen Wert besitzen.
351
352			H2: C<Coro::Specific>
353
354			Mit C<Coro::State> kann man eigene Prozess-Abstraktionen basteln. Damit
355			C<Coro::Specific> funktioniert, muß man lediglich einen
356			coroutinen-/prozessspezifischen Hash in C<$Coro::current> speichern, und
357			genau das macht das C<Coro>-Modul.
358
359			C<Coro::Specific->new> gibt eine Referenz auf einen ge'tie'ten Scalar zurück, der
360			wiederum bei C<FETCH> und C<STORE> einen Skalar im Array
361			C<@{$Coro::current->{specific}}> verändert. Solange das C<Coro>-Modul nicht
362			geladen ist, istd as immer derselbe, danach ist er coroutinenspezifisch.
363
364			!block "perl"
365			my $idx;
366
367			sub new {
368			my $var;
369			tie $var, Coro::Specific::;
370			\$var;
371			}
372
373			sub TIESCALAR {
374			my $idx = $idx++;
375			bless \$idx, $_[0];
376			}
377
378			sub FETCH {
379			$Coro::current->{specific}[${$_[0]}];
380			}
381
382			sub STORE {
383			$Coro::current->{specific}[${$_[0]}] = $_[1];
384			}
385			!endblock
386
387			Auf diese Weise kann man in anderen Modulen ohne schlechtes Gewissen
388			C<Coro::Specific> verwenden, da weder C<Coro::State> noch C<Coro> geladen
389			sein müssen.
390
391			H2: Prozesse selbst gemacht
392
393			Der nächste Schritt, nach Continuations, Variablen und (primitiven)
394			Coroutinen sind richtige Prozesse. Diese werden im C<Coro>-Modul
395			implementiert, daß Prozesserzeugung, Kommunikation, Prioritäten etc.
396			anbietet.
397
398			Das sieht dann so aus:
399
400			!block "perl"
401			use Coro:
402
403			async {
404			# ein neuer "Prozess"
405			};
406
407			my $coro = async {
408			terminate;
409			};
410
411			$coro->prio(PRIO_MAX);
412			$coro_>join;
413
414			cede; # gib die CPU frei für andere Prozesse
415
416			# usw.. hat ja "jeder" schon mal gesehen ;-]
417			!endblock
418
419			Die Implementation ist in einigen Teilen in XS, der Geschwindigkeit
420			wegen. Wenn das Modul geladen wird, erzeugt es zuerst einen
421			"Hauptprozess", der für das Hauptprogramm steht (das Hauptprogramm
422			korrekt auf eine Coroutine abzubilden ist sowieso ein sehr schwieriges
423			Unterfangen - welche Coroutine DESTROY't die anderen Coroutinen am
424			Programmende, wenn das Hauptprogramm nicht mehr existiert?) und sorgt für
425			die Übernahme des bisherigen C<@{$Coro::current->{specific}}>.
426
427			!block "perl"
428			our $main = new Coro;
429
430			# maybe some other module used Coro::Specific before...
431			if ($current) {
432			$main->{specific} = $current->{specific};
433			}
434
435			our $current = $main;
436			!endblock
437
438			Dann folgt die Erzeugung eines Idle-Prozesses, der Rechenzeit verbrät wenn kein
439			Prozess mehr läuft:
440
441			!block "perl"
442			our $idle = new Coro sub {
443			print STDERR "FATAL: deadlock detected\n";
444			exit(51);
445			};
446			!endblock
447
448			Jaja, reingefallen. Wenn kein Prozeß mehr am laufen ist, haben wir einen
449			Deadlock, zumindest, solange man Signale außer acht läßt. Das ändert
450			sich, wenn man Events benutzt (z.B. mit C<Coro::Event>), weshalb der
451			Idle-Prozess auswechselbar ist.
452
453			Neue Prozesse werden mit C<async> oder C<Coro->new> erzeugt:
454
455			!block "perl"
456			sub _newcoro {
457			terminate &{+shift};
458			}
459
460			sub new {
461			my $class = shift;
462			bless {
463			_coro_state => (new Coro::State $_[0] && \&_newcoro, @_),
464			}, $class;
465			}
466
467			sub async(&@) {
468			my $pid = new Coro @_;
469			$manager->ready; # this ensures that the stack is cloned from the manager
470			$pid->ready;
471			$pid;
472			}
473			!endblock
474
475			Ein Prozess ist also wenig mehr als nackter Hash, in dessen
476			C<_coro_state>-Slot ein C<Coro::State>-Objekt gespeichert ist. Ähnlich
477			wie PDL sieht C<transfer> in diesem Slot nach einem C<Coro::State>-Objekt.
478
479			Interessanter ist, daß C<async> den C<$manager> in Bereitschaft versetzt
480			und nicht nur den neuen Prozess. Der einzige Grund dafür ist, daß so die
481			meisten Prozesse mit einem definierten Stackpointer erzeugt werden, so
482			daß derselbe C-Stack für alle Prozesse verwendet werden kann, zumindest
483			anfänglich.
484
485			Am Ende eines Prozesslebens steht ein C<terminate>, oder ein C<cancel>:
486
487			!block "perl"
488			sub cancel {
489			push @destroy, $_[0];
490			$manager->ready;
491			&schedule if $current == $_[0];
492			}
493			!endblock
494
495			C<schedule> springt direkt in den Scheduler, der den nächsten
496			lauffähigen Prozess aus der Warteschlange nimmt und zum aktuellen
497			macht. Er ist (jaja, "the need for speed") in XS implementiert, sieht aber
498			in etwa (keine Prioritäten) so aus:
499
500			!block "perl"
501			sub schedule {
502			my $previous = $current;
503			$current = shift @runqueue;
504			Coro::State::transfer($current, $previous);
505			}
506			!endblock
507
508			Der aktuelle Prozess wird nicht automatishc wieder aufgerufen, dazu muss
509			man ihn wieder mit der C<ready>-Methode in die Warteschlange setzen. Um
510			nur kurz andere Prozesse laufen zu lassen konnte man früher C<yield>
511			benutzen, aber das ging schon für Continuations drauf, und Damian Conway
512			fand das wichtiger, also musste ich einen neuen Namen finden:
513
514			!block "perl"
515			sub cede {
516			$current->ready;
517			schedule;
518			}
519			!endblock
520
521			Einen Prozess direkt zu zerstören, ist keine gute Idee. Zum einen könnte
522			er mehrfach in der C<ready>-Queue stehen, zum anderen sollte ein Prozess
523			sich selbst C<DESTROY>en können, aber da er sich dabei selbst den C-Stack
524			wegzieht, muss dies von einem anderen Prozess aus stattfinden. Der
525			Manager-Prozess stellt genau dies sicher (und verständig auch gleich
526			eventuell wartende Prozesse):
527
528			!block "perl"
529			my @destroy;
530			my $manager;
531			$manager = new Coro sub {
532			while() {
533			# by overwriting the state object with the manager we destroy it
534			# while still being able to schedule this coroutine (in case it has
535			# been readied multiple times. this is harmless since the manager
536			# can be called as many times as neccessary and will always
537			# remove itself from the runqueue
538			while (@destroy) {
539			my $coro = pop @destroy;
540			$coro->{status} \|\|= [];
541			$_->ready for @{delete $coro->{join} \|\| []};
542			$coro->{_coro_state} = $manager->{_coro_state};
543			}
544			&schedule;
545			}
546			};
547			!endblock
548
549			H2: Signale, Semaphoren, Channels und Locks
550
551			Hat man Prozesse, die man erzeugen, anhalten, schedulen und wieder beenden
552			kann, so muss man sie koordinieren. Zum Beispiel mit C<Coro::Signal>'s:
553
554			!block "perl"
555			sub send {
556			if (@{$_[0][1]}) {
557			(shift @{$_[0][1]})->ready;
558			} else {
559			$_[0][0] = 1;
560			}
561			}
562
563			sub wait {
564			if ($_[0][0]) {
565			$_[0][0] = 0;
566			} else {
567			push @{$_[0][1]}, $Coro::current;
568			Coro::schedule;
569			}
570			}
571			!endblock
572
573			Getreu dem Motto "Pseudo-Hashes müssen sterben!", etwas ungewöhnlich
574			ausgelegt, verwendet C<Coro::Signal> ein Array und keinen Hash. Das erste
575			element ist nur ein Flag, das angibt, ob das Signal gesendet wurde (falls
576			niemand darauf wartet). Das zweite Element ist ein Array von wartenden
577			Prozessen.
578
579			C<send> weckt den ersten wartenden Prozess auf oder - falls es keinen gibt
580			- setzt das Flag. Wenn man auf ein Signal wartet, wird zuerst geprüft, ob
581			es schon aufgetreten ist, ansonsten reiht sich der aktuelle Prozess in die
582			Warteschlange und legt sich schlafen.
583
584			H1: Teil 3: Die Aussenwelt
585
586			!block "perl"
587			!endblock
588
589			!block "perl"
590			!endblock
591
592			!block "perl"
593			!endblock
594
595
596
597
598			A1: Module
599
600			- Coro (Coroutinen)
601			- Event (der Event-Standard, nur leider unmaintained)
602			- Linux::AIO (asynchrone Ein-/Ausgabe)
603			- Convert::Scalar (für C<weaken>)
604			- HTTP::Date (code-reuse made easy with CPAN, hat mir sicherlich 5 Minuten gespart)
605			- Date::Parse (siehe HTTP::Date, ich liebe CPAN ;)
606			- BerkeleyDB (Caching der Directory-Listings und WHOIS-Requests)
607
608
609
610
611
612
613
614