solution_gp_ub.tex

\abschnitt{solution: avoiding non-const global variables and
undefined behaviour}\label{solution_gpub}

\zs{The \emph{avoid non-const global variables} guideline has an important
impact on the design of the \fiber API!}

\uabschnitt{synthesizing the suspended fiber}\label{synthesizing}
The problem of global variables or the need for a static member function
returning the active fiber can be avoided by \bfs{synthesizing} the
\bfs{suspended fiber} and passing it into the resumed fiber (as parameter when the
fiber is first started, or returned from \resume).
\cppfl{synthesized_foo}

In the pseudo-code above the fiber \cpp{f} is started by invoking its member
function \resume at line 7. This operation suspends \cpp{foo}, empties
instance \cpp{f} and synthesizes a new \fiber\xspace \cpp{m} that is passed as parameter
to the lambda of \cpp{f} (line 2).

Invoking \cpp{m.resume()} (line 3) suspends the lambda, empties \cpp{m} and
synthesizes a \fiber that is returned by \cpp{f.resume()} at line 7. The
synthesized \fiber is assigned to \cpp{f}. Instance \cpp{f} now represents the
suspended fiber running the lambda (suspended at line 3). Control is
transferred from line 3 (lambda) to line 7 (\cpp{foo()}).

Call \cpp{f.resume()} at line 8 empties \cpp{f} and suspends \cpp{foo()}
again. A \fiber representing the suspended \cpp{foo()} is synthesized, returned
from \cpp{m.resume()} and assigned to \cpp{m} at line 3. Control
is transferred back to the lambda and instance \cpp{m} represents the suspended
\cpp{foo()}.

Function \cpp{foo()} is resumed at line 4 by executing \cpp{m.resume()} so that
control returns at line 8 and so on ...

Class \cpp{symmetric\_coroutine<>::yield\_type} from N3985\cite{N3985} is
\bfs{not} equivalent to the synthesized \fiber.

\cpp{symmetric\_coroutine<>::yield\_type} does not represent the suspended context,
instead it is a special representation of the same coroutine. Thus \main or
the current thread's \entryfn can \bfs{not} be represented by \cpp{yield\_type}
(see next section \nameref{representation}).

Because \cpp{symmetric\_coroutine<>::yield\_type()} yields back to the starting
point, i.e. invocation of\\
\cpp{symmetric\_coroutine<>::call\_type::operator()()},
both instances (\cpp{call\_type} as well as \cpp{yield\_type}) must be preserved.
Additionally the caller must be kept alive until the called coroutine terminates
or UB happens at resumption.

\zs{This API is specified in terms of passing the suspended \fiber. A higher
level layer can hide that by using private variables.}

\uabschnitt{representing \emph{main()} and thread's \entryfn as fiber}\label{representation}
As shown in the previous section a synthesized instance of \fiber is passed
into the resumed fiber.

\cppf{synthesized_main}

The mechanism presented in this proposal describes switching between stacks: each
fiber has its own stack. The stacks of \main and explicitly-launched threads
are not excluded; these can be used as targets too.

\bfs{Thus every program can be considered to consist of fibers -- some
created by the OS (\main stack; each thread's initial stack) and some created
explicitly by the code.}

This is a nice feature because it allows (the stacks of) \main and each
thread's \entryfn to be represented as fibers. A \fiber
representing \main or a thread's \entryfn can be handled like an
explicitly created \fiber: it can passed to and returned from functions or
stored in a container.

In the code snippet above the suspended \main is represented by instance
\cpp{m} and could be stored in containers or managed just like \cpp{f}
by a scheduling algorithm.

\zs{The proposed fiber API allows representing and handling \main and the
current thread's \entryfn by an instance of \fiber in the same way as
explicitly created fibers.}

\uabschnitt{fiber returns (terminates)} When a fiber returns (terminates), what
should happen next? Which fiber should be resumed next? The only way to avoid
internal global variables that point to \main is to explicitly return a non-empty
\fiber instance that will be resumed after the active fiber terminates.
\cppfl{terminating_fiber}

In line 5 the fiber is started by invoking \resume on instance \cpp{f}. \main
is suspended and an instance of type \fiber is synthesized and passed as
parameter \cpp{m} to the lambda at line 2. The fiber terminates by returning
\cpp{m}. Control is transferred to \main (returning from \cpp{f.resume()} at
line 5) while fiber \cpp{f} is destroyed.

In a more advanced example another \fiber is used as return value instead of the
passed in synthesized fiber.
\cppfl{terminating_fiber_complex}

At line 13 fiber \cpp{f2} is resumed and the lambda is entered at line 8. The
synthesized \fiber\xspace \cpp{f} (representing suspended \main) is passed as a
parameter \cpp{f} and stored in \cpp{m} (captured by the lambda) at line 10.
This is necessary in order to prevent destructing \cpp{f} when the lambda
returns. Fiber \cpp{f2} uses \cpp{f1}, that was also captured by the lambda, as
return value. Fiber \cpp{f2} terminates while fiber \cpp{f1} is resumed (entered
the first time). The synthesized \fiber\xspace \cpp{f} passed into the lambda at line 3
represents the terminated fiber \cpp{f2} (e.g. the calling fiber). Thus instance
\cpp{f} is empty as the assert statement verifies at line 5. Fiber \cpp{f1} uses
the captured \fiber\xspace \cpp{m} as return value (line 6). Control is returned to
\main, returning from \cpp{f2.resume()} at line 13.

\zs{The \entryfn passed to \fiber's constructor must have
signature `\cpp{fiber\_context(fiber\_context&&)}`. Using \fiber as the return
value from such a function avoids global variables.}

\uabschnitt{returning synthesized \fiber instance from \cpp{resume()}}\label{fiberreturn}
An instance of \fiber remains empty after return from \anyresume: the
synthesized fiber is returned, instead of implicitly updating the \fiber
instance on which \resume was called.

If the \fiber object were implicitly updated, the fiber would 
change its identity because each fiber is associated with a stack. Each stack
contains a chain of function calls (call stack). If this association were
implicitly modified, unexpected behaviour happens.

The example below demonstrates the problem:
\cppfl{return_from_resume_inplace}

In this pseudo-code the \fiber object is implicitly updated.

The example creates a circle of fibers: each fiber prints its name and resumes
the next fiber (f1 -> f2 -> f3 -> f1 -> ...).

Fiber \cpp{f1} is started at line 27. The synthesized \fiber\xspace \cpp{main} passed 
to the resumed fiber is stored but not used: control flow cycles through the three
fibers.
The for-loop prints the name \emph{f1} and resumes fiber \cpp{f2}. Inside 
\cpp{f2}'s for-loop the name is printed and \cpp{f3} is resumed. Fiber \cpp{f3}
resumes fiber \cpp{f1} at line 7. Inside \cpp{f1} control returns from
\cpp{f2.resume()}. \cpp{f1} loops, prints out the name and invokes \cpp{f2.resume()}. But
this time fiber \cpp{f3} instead of \cpp{f2} is resumed. This is caused by the
fact the instance \cpp{f2} gets the synthesized \fiber of \cpp{f3} implicitly
assigned. Remember that at line 7 fiber \cpp{f3} gets suspended while \cpp{f1}
is resumed through \cpp{f1.resume()}.

This problem can be solved by returning the synthesized \fiber from \anyresume.
\cppf{return_from_resume_invalid}

In the example above the synthesized \fiber returned by each \resume call is
specifically move-assigned to a \fiber instance other than the one on which \resume
was called, to properly track the three fibers. (Of course this particular example
depends on static knowledge of the overall control flow. But the API does not, in
general, require that.)

\zs{The synthesized \fiber must be returned from \allresume
in order to prevent changing the identity of the fiber.}
\xspace\newline

If the overall control flow isn't known, member function \anyresumewith
(see section \nameref{resumewith}) can be used to assign the
synthesized \fiber to the correct \fiber instance (held by the caller).
\cppf{assign_resumewith}

Picture a higher-level framework in which every fiber can find its associated
\cpp{filament} instance, as well as others. Every context switch must be mediated by
passing \emph{the target} \cpp{filament} instance to \emph{the running fiber's}
\cpp{resume\_next()}.

Running fiber A has an associated \cpp{filament} instance \cpp{filamentA},
whose \fiber\xspace\cpp{filament::f\_} is empty -- because fiber A is running.

Desiring to switch to suspended fiber B (with associated
\cpp{filament} \cpp{filamentB}), running fiber A calls\\
\cpp{filamentA.resume\_next(filamentB)}.

\cpp{resume\_next()} calls \cpp{filamentB.f\_.resume\_with(<lambda>)}.
This empties \cpp{filamentB.f\_} -- because fiber B is now running.

The lambda binds \cpp{&filamentA} as \cpp{this}. Running on fiber B, it
receives a \fiber instance representing the newly-suspended fiber A as its
parameter \cpp{f}. It moves that \fiber instance to \cpp{filamentA.f\_}.

The lambda then returns a default-constructed (therefore empty) \fiber
instance. That empty instance is returned by the previously-suspended
\resumewith call in \cpp{filamentB.resume\_next()} -- which is fine because
\cpp{resume\_next()} drops it on the floor anyway.

Thus, the running fiber's associated \cpp{filament::f\_} is always empty,
whereas the \cpp{filament} associated with each suspended fiber is continually
updated with the \fiber instance representing that
fiber.\footnote{\bfiber\cite{bfiber} uses this pattern for resuming user-land
threads.}

\zs{It is not necessary to know the overall control flow. It is sufficient to
pass a reference/pointer of the \emph{caller} (fiber that gets suspended) to the
resumed fiber that move-assigns the synthesized \fiber to \emph{caller} (updating
the instance).}