implementation.tex

\abschnitt{possible implementation strategies}\label{implementations}

\zs{This proposal does \so{NOT} seek to standardize any particular implementation or
impose any specific calling convention!}

Modern \bfs{micro-processors} are \bfs{register machines}; the content of
processor registers represents the execution context of the program at a given
point in time.

\bfs{Operating systems} maintain for each process all relevant data (execution
context, other hardware registers etc.) in the process table. The operating system's
\bfs{CPU scheduler} periodically suspends and resumes processes in order to
share CPU time between multiple processes. When a process is suspended, its
execution context (processor registers, instruction pointer, stack pointer, ...)
is stored in the associated process table entry. On resumption, the CPU
scheduler loads the execution context into the CPU and the process continues
execution.

The CPU scheduler does a \bfs{full context switch}. Besides preserving
the execution context (complete CPU state), the cache must be invalidated and
the memory map modified.

A kernel-level context switch is several orders of magnitude slower than a
context switch at user-level\cite{Tanenbaum2009}.

\uabschnitt{hypothetical fiber preserving complete CPU state} This strategy tries to
preserve the complete CPU state, e.g. all CPU registers. This requires that the
implementation identifies the concrete micro-processor type and supported processor
features. For instance the x86-architecture has several flavours of extensions
such as MMX, SSE1-4, AVX1-2, AVX-512.

Depending on the detected processor features, implementations of certain
functionality must be switched on or off. The CPU scheduler in the operating system
uses such information for context switching between processes.

A fiber implementation using this strategy requires such a detection mechanism
too (equivalent to swapper/\cpp{system_32()} in the Linux kernel).

Aside from the complexity of such detection mechanisms, preserving the complete
CPU state for each fiber switch is expensive.

\zs{A context switch facility that preserves the complete CPU state like an
operating system is possible but impractical for user-land.}

\uabschnitt{fiber switch using the calling convention}\label{callingconvention}
For \fiber, not all registers need be preserved because the context
switch is effected by a visible function call. It need not be completely transparent like
an operating-system context switch; it only needs to be as transparent as a call
to any other function. The calling convention -- the part of the ABI that
specifies how a function's arguments and return values are passed -- determines
which subset of micro-processor registers must be preserved by the called
subroutine.

The \bfs{calling convention}\cite{SYSVABI} of \bfs{SYSV ABI} for \bfs{x86\_64}
architecture determines that general purpose registers R12, R13, R14, R15, RBX
and RBP must be preserved by the sub-routine - the first arguments are passed
to functions via RDI, RSI, RDX, RCX, R8 and R9 and return values are stored in
RAX, RDX.

So on that platform, the \resume implementation preserves the \bfs{general
purpose registers} (R12-R15, RBX and RBP) specified by the calling convention.
In addition, the \bfs{stack pointer} and \bfs{instruction pointer} are
preserved and exchanged too -- thus, from the point of view of calling
code, \resume behaves like an ordinary function call.

In other words, \resume acts on the level of a simple function invocation --
with the same performance characteristics (in terms of CPU cycles).

This technique is used in \bcontext\cite{bcontext} which acts as building block
for (e.g.) \fbfibers\xspace and \bbquantum; see section \nameref{low_level}.

\uabschnitt{in-place substitution at compile time} During code generation,
a compiler-based implementation could inject the assembler code responsible
for the fiber switch directly into each function that calls \resume. That would save
an extra indirection (JMP + PUSH/MOV of certain registers used to
invoke \resume).

\uabschnitt{CPU state on the stack} Because each fiber must preserve CPU
registers at suspension and load those registers at resumption, some storage
is required.

Instead of allocating extra memory for each fiber, an implementation can use
the stack by simply advancing the stack pointer at suspension and pushing the
CPU registers (CPU state) onto the stack owned by the suspending fiber. When
the fiber is resumed, the values are popped from the stack and loaded into the
appropriate registers.

This strategy works because only a running fiber creates new stack frames
(moving the stack pointer). While a fiber is suspended, it is safe to keep the
CPU state on its stack.

Using the stack as storage for the CPU state has the additional advantage
that \fiber need not itself contain the stored CPU state: it need only contain
a pointer to the stack location.

Section \nameref{synthesizing} describes how global variables are avoided
by synthesizing a \fiber from the active fiber (execution context) and passing
this synthesized \fiber (representing the now-suspended fiber) into the resumed
fiber. Using the stack as storage makes this mechanism very easy to
implement.\footnote{The implementation of \bcontext\cite{bcontext} utilizes this
technique.}
Inside \resume the code pushes the relevant CPU registers onto the stack, and
from the resulting stack address creates a new \fiber. This instance is then
passed (or returned) into the resumed fiber (see \nameref{synthesizing}).

\zs{Using the active fiber's stack as storage for the CPU state is efficient because no
additional allocations or deallocations are required.}

\abschnitt{\exfns}\label{exc_scope}

Both \exfns must report exceptions solely on the current fiber.
Reporting exceptions thrown on any other fiber would make them
unreliable in practice.

A straightforward implementation could make \allresume save and restore the
data underlying \exfns as part of saving and restoring the rest of the fiber
state. Since \exfns data is necessarily thread-local, the likely cost would be
a TLS access on every \anyresume call.

Alternatively, \fiber's constructor could update an internal associative
container whose key is the high end of the new fiber stack area. \exfns could
call \cpp{upper\_bound()}, passing the current stack pointer, to discover
which stack is current. This would shift the cost from every context switch
to \exfns calls.

The examples in \nameref{exlife}, \nameref{throw} and
\nameref{exfns} have been floated to illustrate problems that can
arise when \exfns are not specific to the current fiber.

In those small examples, the problematic code is obvious. But the power of
fibers is that a function need not know whether some function it calls (or
some indirect callee thereof) will resume another fiber. It's not practical
simply to forbid coders from switching fibers within a catch block.

In St. Louis in June 2024, EWG requested\cite{stlouisnotes} implementation
experience with fiber-specific exception state.

In Wrocław in November 2024,\cite{wroclawnotes} we presented
\href{https://github.com/secondlife/3p-boost/blob/nat/exstate/patches/libs/context/0001-switch-exception-state.patch}{a small patch}
to the Boost.Context reference implementation. With that patch, all three
exception state test programs behave correctly when built with libstdc++ on
Windows and Linux. Microsoft questioned whether fiber-specific exception state
is implementable in MSVC, and EWG agreed to take up this matter in Hagenberg.

On February 14, 2025, Gor Nishanov stated\cite{onwindows} that a Windows
Fibers implementation of \fiber would be possible, while expressing concern
about potential performance.