\documentclass[10pt,letterpaper]{article} \usepackage{vmargin} \usepackage{multicol} \usepackage{times} \usepackage{epsfig} \usepackage{float} \usepackage{color} \usepackage{calc} \usepackage{alltt} \usepackage{verbatim} \usepackage{moreverb} \usepackage{fancyheadings} \usepackage{supertabular} \usepackage{colortbl} \usepackage{rotating} \floatstyle{boxed} \makeatletter \let\hangafter\@hangfrom \definecolor{dark}{rgb}{0.5,0.5,0.5} \definecolor{medium}{rgb}{0.7,0.7,0.7} \definecolor{light}{rgb}{0.95,0.95,0.95} \newcommand{\grayrow}{\rowcolor[gray]{0.8}} \setpapersize{USletter} \setmarginsrb{1.0in}{1.0in}{1.0in}{0.5in}{0pt}{0pt}{0.5in}{0.5in} %\renewcommand{\sfdefault}{phv} \renewcommand{\section}{\@startsection% {section}{1}{\z@}% {-3.5ex \@plus -1ex \@minus -.2ex}% {2.3ex \@plus.2ex}% {\normalfont\Large\bfseries}} \renewcommand{\subsection}{\@startsection% {subsection}{2}{\z@}% {-3.25ex\@plus -1ex \@minus -.2ex}% {1.5ex \@plus .2ex}% {\normalfont\large\bfseries}} \renewcommand{\subsubsection}{\@startsection% {subsubsection}{3}{\z@}% {-3.25ex\@plus -1ex \@minus -.2ex}% {1.5ex \@plus .2ex}% {\normalfont\normalsize}} \renewcommand{\paragraph}{\@startsection% {paragraph}{4}{\z@}% {3.25ex \@plus1ex \@minus.2ex}% {-1em}% {\normalfont\normalsize\bfseries}} \renewcommand{\subparagraph}{\@startsection% {subparagraph}{5}{\parindent}% {3.25ex \@plus1ex \@minus .2ex}% {-1em}% {\normalfont\normalsize}} \renewcommand{\labelitemi}{ \rule{6pt}{6pt} } \renewcommand{\labelitemii}{ \rule{5pt}{5pt} } \renewcommand{\labelitemiii}{ \rule{4pt}{4pt} } \renewcommand{\labelitemiv}{ \rule{3pt}{3pt} } \newcommand{\mypar}[1]{\medskip\noindent{\large\bfseries #1}\smallskip} \makeatother \pagestyle{fancy} \lhead{} \chead{} \rhead{} \headrulewidth=0pt \lfoot{} \cfoot{\thepage} \rfoot{} \begin{document} \begin{center} {\huge\bfseries Portable Multithreading}\\[1mm] {\large\bfseries The Signal Stack Trick For User-Space Thread Creation}\\[5mm] {\large Ralf S. Engelschall}\\[1mm] {\large\textit{Technische Universit\"at M\"unchen (TUM)}}\\[1mm] rse@engelschall.com, http://www.engelschall.com\\[8mm] %{\large June 18th, 2000} \end{center} \begin{abstract} \noindent This paper describes a pragmatic but portable fallback approach for creating and dispatching between the machine contexts of multiple threads of execution on Unix systems that lack a dedicated user-space context switching facility. Such a fallback approach for implementing machine contexts is a vital part of a user-space multithreading environment, if it has to achieve maximum portability across a wide range of Unix flavors. The approach is entirely based on standard Unix system facilities and ANSI-C language features and especially does not require any assembly code or platform specific tricks at all. The most interesting issue is the technique of creating the machine context for threads, which this paper explains in detail. The described approach closely follows the algorithm as implemented by the author for the popular user-space multithreading library \textit{GNU Portable Threads} (\textit{GNU Pth}, \cite{pth}) which this way quickly gained the status of one of the most portable user-space multithreading libraries. \medskip \noindent \textsf{\bfseries Keywords:} portability, multithreading, Unix, POSIX, SUSv2, ANSI-C, user-space, context creation, context switching, signal handler, stack, makecontext, switchcontext, sigaltstack, setjmp, longjmp. \medskip \noindent \textsf {\bfseries Publishing:} Early drafts of this paper were distributed with the GNU Pth distribution. The final release version was published on the USENIX Annual Technical Conference, June 18-23, 2000, San Diego, California, USA. \end{abstract} \medskip \columnsep=0.25in \begin{multicols}{2}[\section{Introduction}] \subsection{Multithreading} The paradigm of programming with multiple threads of execution (aka \textit{multithreading}) is already a very old one and dates back to the decades of programming with \textit{co-routines} \cite{co1,co2}. Paradoxically, the use of threads on Unix platforms did not become popular until the early 1990s. \mypar{Multithreading Advantages} \noindent Multithreading can provide many benefits for applications (good runtime concurrency, parallel programming techniques can be implemented more easily, the popular procedural programming style can be combined with multiple threads of execution, \textit{etc.}) but the most interesting ones are usually performance gains and reduced resource consumption. Because in contrast to multiprocess applications, multithreaded ones usually require less system resources (mainly memory) and their internal communication part can leverage from the shared address space. \mypar{Multithreading and Applications} \noindent Nevertheless there still exist just a few real applications in the free software world that use multithreading for their benefit, although their application domains are predestined for multithreading. For instance, the popular Apache webserver as of version 1.3 still uses a pre-forking process model for serving HTTP requests, although two experiments with multithreaded Apache variants in 1996 (with \textit{rsthreads} \cite{rsthreads}) and 1998 (with \textit{NSPR} \cite{nspr}) already showed great performance boosts. The same applies to many similar applications. The reason for this restraint mainly is that for a long time, multithreading facilities under Unix were rare. The situation became better after some vendors like \textit{Sun} and \textit{DEC} incorporated threading facilities into their Unix flavors and \textit{POSIX} standardized a threading \textit{Application Programming Interface} (API) (aka \textit{Pthreads} \cite{iso}). But an API and a few vendor implementations are not enough to fulfill the portability requirements of modern free software packages. Here stand-alone and really portable multithreading environments are needed. The author collected and evaluated over twenty (mostly user-space) available multithreading facilities for Unix systems (see Table 1), but only a few of them are freely available and showed to be really portable. And even the mostly portable ones suffered from the fact that they partly depend on assembly code or platform specific tricks usually related to the creation and dispatching of the individual threads. This means that the number of platforms they support is limited and applications which are based on these facilities are only portable to those platforms. This situation is not satisfactory, so application authors still avoid the use of multithreading if they want to (or have to) achieve maximum portability for their application. A pragmatic and mostly portable fallback technique for implementing user-space threads can facilitate wider use of multithreading in free software applications. \newcommand{\he}[1]{\begin{rotate}{45}\textbf{\small #1}\end{rotate}} \begin{figure*}[t] \noindent \fbox {\small \setlength{\tabcolsep}{2.5pt} \begin{tabular}{lllllllllllllllll} \rule{0pt}{26mm}% \textbf{Package} & \he{Genesis} & \he{Latest Version} & \he{Implementation Space} & \he{Thread Mapping} & \he{Active Development} & \he{Experimental State} & \he{Open Source} & \he{Pthread API} & \he{Pthread Shared Memory} & \he{Native API} & \he{Native API $\ge$ Pthread API} & \he{Native API is Pthread API} & \he{Preemptive Scheduling} & \he{Portability} & \he{Assembly Code} & \he{SysCall Wrap.} \\ \hline gnu-pth & 1999 & 1.3.5 & user & n:1 & yes & no & yes & yes & no & yes & yes & no & no & full/mcsc+sjlj & no & partly \\[-1pt] cmu-lwp & 1984 & 1.4 & user & n:1 & yes & no & yes & no & - & yes & yes & partly & no & semi/fixed:8 & yes & no \\[-1pt] fsu-pthread & 1992 & 3.13 & user & n:1 & no & no & yes & yes & no & no & - & - & yes & semi/fixed:6 & yes & yes \\[-1pt] mit-pthread & 1993 & 1.8.9 & user & n:1 & no & no & yes & yes & no & no & - & - & yes & semi/fixed:17 & yes & yes \\[-1pt] ptl & 1997 & 990622 & user & n:1 & no & no & yes & yes & no & no & - & - & yes & semi/fixed:10 & yes & yes \\[-1pt] linuxthreads & 1997 & 2.1.2 & user+kernel & 1:1 & yes & no & yes & yes & no & no & - & - & yes & semi/fixed:5 & yes & yes \\[-1pt] uthread & 1998 & 3.4 & user & n:1 & yes & no & yes & yes & no & no & - & - & yes & semi/fixed:2 & yes & yes \\[-1pt] cthread & 1991 & 991115 & user & n:1 & no & no & yes & no & - & yes & yes & no & no & semi/fixed:8 & yes & yes \\[-1pt] openthreads/qt & 1996 & 2.0 & user & n:1 & no & no & yes & no & - & yes & no & no & no & semi/fixed:9 & yes & no \\[-1pt] rt++/qt & 1996 & 1.0 & user & n:1 & no & no & yes & no & - & yes & yes & no & no & semi/fixed:9 & yes & no \\[-1pt] rsthreads & 1996 & 980331 & user & n:1 & no & yes & yes & no & - & yes & no & no & no & semi/fixed:9 & yes & no \\[-1pt] pcthread & 1996 & 1.0 & user & n:1 & no & yes & yes & yes & no & no & - & - & yes & semi/fixed:1 & yes & no \\[-1pt] bbthreads & 1996 & 0.3 & kernel & 1:1 & no & yes & yes & no & - & yes & no & - & yes & semi/fixed:1 & yes & no \\[-1pt] jkthreads & 1998 & 1.2 & kernel & 1:1 & no & yes & yes & no & - & yes & no & - & yes & semi/fixed:1 & yes & no \\[-1pt] nthreads & 1997 & 970604 & user & n:1 & no & yes & yes & no & - & yes & no & - & no & semi/fixed:9 & yes & partly \\[-1pt] rexthreads & 1993 & 930614 & user & n:1 & no & yes & yes & no & - & yes & no & - & no & semi/fixed:4 & yes & no \\[-1pt] coro & 1999 & 1.0.3 & user & n:1 & no & yes & yes & no & - & yes & no & - & no & semi/fixed:1 & yes & no \\[-1pt] greenthreads & 1995 & 1.2 & user & n:1 & no & no & no & no & - & yes & yes & - & yes & full/mcsc & no & no \\[-1pt] solaris-pthread & NN & 2.7 & user+kernel & n:m & yes & no & no & yes & yes & yes & yes & no & yes & NN & NN & yes \\[-1pt] tru64-pthread & NN & 5.0 & user+kernel & n:m & yes & no & no & yes & yes & no & no & no & yes & NN & NN & yes \\[-1pt] aix-pthread & NN & 4.3 & user+kernel & 1:1 & yes & no & no & yes & yes & no & no & no & yes & NN & NN & yes \\[-1pt] \end{tabular}\ \ \ \ \ \ \ }\\[4pt] \parbox{\linewidth}{\footnotesize\baselineskip=0pt \hangafter{\textbf{Table 1:}\quad}% Summary of evaluated multithreading packages and some of their determined characteristics. Notice that mostly all packages con\-tain assembly code and are just semi-portable, \textit{i.e.}, they support only a fixed set of platforms and do not automatically adjust for new ones. } \end{figure*} \mypar{Ingredients of a Thread} \noindent A Unix process has many ingredients, but the most important ones are its memory mapping table, the signal dispatching table, the signal mask, the set of file descriptors and the machine context. The machine context in turn consists of at least the CPU registers including the program counter and the stack pointer. In addition, there can be light-weight processes (LWP) or threads, which usually share all attributes with the underlying (heavy-weight) process except for the machine context. \mypar{Kernel-Space vs. User-Space} \noindent Those LWPs or threads, on a Unix platform classically can be implemented either in kernel-space or in user-space. When implemented in kernel-space, one usually calls them LWPs or kernel threads, otherwise (user-space) threads. If threads are implemented by the kernel, the thread context switches are performed by the kernel without notice by the application, similar to the dispatching of processes. If threads are implemented in user-space, the thread context switches are performed usually by an application library without notice by the kernel. Additionally, there exist hybrid threading approaches, where typically a user-space library binds one or more user-space threads to one or more kernel-space LWPs. \mypar{Thread Models} \noindent The vendor threading facilities under \textit{Sun Solaris}, \textit{IBM AIX}, \textit{DEC Tru64} (formerly \textit{DIGITAL UNIX} or \textit{OSF/1}) and \textit{SGI IRIX} use a \textbf{M:N} mapping \cite{str,aix}, \textit{i.e.}, \textbf{M} user-space threads are mapped onto \textbf{N} kernel-space LWPs. On the other hand, \textit{LinuxThreads} \cite{linuxthreads} under \textit{GNU/Linux} uses a \textbf{1:1} mapping and pure user-space implementations like \textit{GNU Pth}, \textit{FSU pthreads} or \textit{MIT pthreads}, \textit{etc.} use a \textbf{M:1} mapping \cite{pth,fsu,mit}. From now on we focus on such \textbf{M:1} user space threading approaches, where one or more user space threads are implemented inside a single kernel space process. The exercise is to implement this by using standardized Unix system and ANSI-C language facilities \textit{only}. \subsection{The Exercise} As we have mentioned, a thread shares its state with the underlying process except for the machine context. So the major task for a user-space threading system is to create and dispatch those machine contexts. In practice, the second major task it has to do is to ensure that no thread by accident blocks the whole process (and thereby all other threads). Instead when an operation would block, the threading library should suspend only the execution of the current thread and in the meantime dispatch the remaining threads. But this task is outside the scope of this paper (see \cite{bmv} for details about this task). We focus only on the aspect of machine context handling. \subsection{The Curse of Portability} Our goal of real portability for a threading system causes some non-trivial problems which have to be solved. The most obvious one is that dealing with machine contexts usually suffers from portability, because it is a highly CPU dependent task for which not every Unix flavor provides a standardized API. Although such an API would be not too hard for vendors to provide, because in principle it is just a matter of switching a few CPU registers (mainly the program counter and the stack pointer). \mypar{Assembly Code Considered Harmful} \noindent Additionally, we disallow the use of any assembly solutions or platform specific tricks, because then the threading system again would be only semi-portable, \textit{i.e.}, it can be ported to \textbf{N} platforms but on the \textbf{(N+1)}th platform one has to manually adjust or even extend it to work there, too. This is usually not acceptable, even if it also makes solving the problems harder. At least most of the known free software user-space threading systems \cite{fsu,mit,ptl2} do not restrict themself to this and therefore are just semi-portable. But real portability should be a major goal. \section{Problem Analysis} \subsection{The Task in Detail} Our task is simple in principle: provide an API and corresponding implementation for creating and dispatching machine contexts on which user-space threads can be implemented. \mypar{The Proposed API} \noindent In detail we propose the following \textit{Application Programmers Interface} (API) for the machine context handling: \begin{itemize} \item A data structure of type \texttt{mctx\_t} which holds the machine context. \item A function ``\textbf{void} \texttt{mctx\_crea\-te(}\texttt{mctx\_t} \texttt{*}\textit{mctx}, \textbf{void} \texttt{(*}\textit{sf\_addr}\texttt{)(}\textbf{void *}\texttt{),} \textbf{void} \texttt{*}\textit{sf\_arg}, \textbf{void} \texttt{*}\textit{sk\_addr}, \textbf{size\_t} \textit{sk\_size}\texttt{)}'' which creates and initializes a machine context structure in \textit{mctx} with a start function \textit{sf\_addr}, a start function argument \textit{sf\_arg}, and a stack starting at \textit{sk\_addr}, which is \textit{sk\_size} bytes in size. \item A function ``\textbf{void} \texttt{mctx\_save(}\texttt{mctx\_t} \texttt{*}\textit{mctx}\texttt{)}'' which saves the current machine context into the machine context structure \textit{mctx}. \item A function ``\textbf{void} \texttt{mctx\_restore(}\texttt{mctx\_t} \texttt{*}\textit{mctx}\texttt{)}'' which restores the new machine context from the machine context structure \textit{mctx}. This function does not return to the caller. Instead it does return at the location stored in \textit{mctx} (which is either \textit{sf\_addr} from a previous \texttt{mctx\_create} call or the location of a previous \texttt{mctx\_save} call). \item A function ``\textbf{void} \texttt{mctx\_switch(}\texttt{mctx\_t} \texttt{*}\textit{mctx\-\_old}, \texttt{mctx\_t} \texttt{*}\textit{mctx\_new}\texttt{)}'' which switches from the current machine context (saved to \textit{mctx\_old} for later use) to a new context (restored from \textit{mctx\_new}). This function returns only to the caller if \texttt{mctx\_restore} or \texttt{mctx\_switch} is again used on \textit{mctx\_old}. \end{itemize} \subsection{Technical Possibilities} Poking around in the references of the ANSI-C language reference and the Unix standards show the following functions on which an implementation can be based: \begin{itemize} \item There is the \texttt{ucontext}(3) facility with the functions \texttt{getcontext}(3), \texttt{makecontext}(3), \texttt{swapcontext}(3) and \texttt{setcontext}(3) which conform to the \textit{Single Unix Specification}, Version 2 (\textit{SUSv2} \cite{sus}, aka \textit{Unix95/98}). Unfortunately these are available on modern Unix platforms only. \item There are the \texttt{jmp\_buf} based functions \texttt{setjmp}(3) and \texttt{long\-jmp}(3) which conform to ISO 9899:1990 (ISO-C) and the \texttt{sigjmp\_buf} based \texttt{sigsetjmp}(3) and \texttt{sig\-long\-jmp}(3) functions which conform to IEEE Std\-1003.1-1988 (\textit{POSIX}), and \textit{Single Unix Specification}, Version 2 (\textit{SUSv2} \cite{sus}, aka \textit{Unix95/98}). The first two functions are available really on all Unix platforms, the last two are available only on some of them. On some platforms \texttt{setjmp}(3) and \texttt{longjmp}(3) save and restore also the signal mask (if one does not want this semantics, one has to call \texttt{\_setjmp}(3) and \texttt{\_longjmp}(3) there) while on others one has to explicitly use the superset functions \texttt{sigsetjmp}(3) and \texttt{siglongjmp}(3) for this. In our discussion we can assume that \texttt{setjmp}(3) and \texttt{longjmp}(3) save and restore the signal mask, because if this is not the case in practice, one easily can replace them with \texttt{sigsetjmp}(3) and \texttt{siglongjmp}(3) calls (if available) or (if not available) emulate the missing functionality manually with additional \texttt{sigprocmask}(2) calls (see \texttt{pth\_mctx.c} in \textit{GNU Pth} \cite{pth}). \item There is the function \texttt{sigaltstack}(2) which conforms to the \textit{Single Unix Specification}, Version 2 (\textit{SUSv2} \cite{sus}, aka \textit{Unix95/98}) and its ancestor function \texttt{sigstack}(2) from \textit{4.2BSD}. The last one exists only on \textit{BSD}-derived platforms, but the first function already exists on all current Unix platforms. \end{itemize} \subsection{Maximum Portability Solution} The maximum portable solution obviously is to use the standardized \texttt{makecontext}(3) function to create threads and \texttt{switchcontext}(3) or \texttt{getcontext}(3)/\texttt{setcontext}(3) to dispatch them. And actually these are the preferred functions modern user-space multithreading systems are using. We could easily implement our proposed API as following (all error checks omitted for better readability): {\small \baselineskip=9pt \begin{alltt} /* \textrm{\textit{\bfseries machine context data structure}} */ \textbf{typedef struct} mctx_st \{ ucontext_t uc; \} mctx_t; /* \textrm{\textit{\bfseries save machine context}} */ \textbf{#define} mctx_save(mctx) \(\backslash\) (\textbf{void})getcontext(&(mctx)->uc) /* \textrm{\textit{\bfseries restore machine context}} */ \textbf{#define} mctx_restore(mctx) \(\backslash\) (\textbf{void})setcontext(&(mctx)->uc) /* \textrm{\textit{\bfseries switch machine context}} */ \textbf{#define} mctx_switch(mctx_old,mctx_new) \(\backslash\) (\textbf{void})swapcontext(&((mctx_old)->uc), \(\backslash\) &((mctx_new)->uc)) /* \textrm{\textit{\bfseries create machine context}} */ \textbf{void} mctx_create( mctx_t *mctx, \textbf{void} (*sf_addr)(\textbf{void} *), \textbf{void} *sf_arg, \textbf{void} *sk_addr, size_t sk_size) \{ /* \textrm{\textit{\bfseries fetch current context}} */ getcontext(&(mctx->uc)); /* \textrm{\textit{\bfseries adjust to new context}} */ mctx->uc.uc_link = NULL; mctx->uc.uc_stack.ss_sp = sk_addr; mctx->uc.uc_stack.ss_size = sk_size; mctx->uc.uc_stack.ss_flags = 0; /* \textrm{\textit{\bfseries make new context}} */ makecontext(&(mctx->uc), sf_addr, 1, sf_arg); \textbf{return}; \} \end{alltt}} \noindent Unfortunately there are still lots of Unix platforms where this approach cannot be used, because the standardized \texttt{ucontext}(3) API is not provided by the vendor. Actually the platform test results for \textit{GNU Pth} (see Table 2 below) showed that only 7 of 21 successfully tested Unix flavors provided the standardized API (\texttt{makecontext}(3), \textit{etc.}). On all other platforms, \textit{GNU Pth} was forced to use the fallback approach of implementing the machine context as we will describe in the following. Obviously this fallback approach has to use the remaining technical possibilities (\texttt{sigsetjmp}(3), \textit{etc.}). \medskip \noindent \fbox {\parbox{7.8cm} {\footnotesize \noindent \medskip \begin{tabular}{l|l|l|l} {\bfseries Operating System} & {\bfseries Architecture(s)} & {\bfseries mcsc} & {\bfseries sjlj} \\ FreeBSD 2.x/3.x & Intel & no & yes \\ FreeBSD 3.x & Intel, Alpha & no & yes \\ NetBSD 1.3/1.4 & Intel, PPC, M68K & no & yes \\ OpenBSD 2.5/2.6 & Intel, SPARC & no & yes \\ BSDI 4.0 & Intel & no & yes \\ Linux 2.0.x glibc 1.x/2.0 & Intel, SPARC, PPC & no & yes \\ Linux 2.2.x glibc 2.0/2.1 & Intel, Alpha, ARM & no & yes \\ Sun SunOS 4.1.x & SPARC & no & yes \\ Sun Solaris 2.5/2.6/2.7 & SPARC & yes & yes \\ SCO UnixWare 2.x/7.x & Intel & yes & yes \\ SCO OpenServer 5.0.x & Intel & no & yes \\ IBM AIX 4.1/4.2/4.3 & RS6000, PPC & yes & yes \\ HP HPUX 9.10/10.20 & HPPA & no & yes \\ HP HPUX 11.0 & HPPA & yes & yes \\ SGI IRIX 5.3 & MIPS 32/64 & no & yes \\ SGI IRIX 6.2/6.5 & MIPS 32/64 & yes & yes \\ ISC 4.0 & Intel & no & yes \\ Apple MacOS X & PPC & no & yes \\ DEC OSF1/Tru64 4.0/5.0 & Alpha & yes & yes \\ SNI ReliantUNIX & MIPS & yes & yes \\ AmigaOS & M68K & no & yes \\ \end{tabular} \medskip \noindent {\tiny \begin{tabular}{ll} \end{tabular} } }}\\[4pt] \parbox{\linewidth}{\footnotesize\baselineskip=0pt \hangafter{\textbf{Table 2:}\quad}% Summary of operating system support. The level and type of support found on each tested operating system. \texttt{mcsc}: functional \texttt{makecontext}(3)/\-\texttt{switchcontext}(3), \texttt{sjlj}: functional \texttt{setjmp}(3)/\texttt{longjmp}(3) or \texttt{sig\-setjmp}(3)/\-\texttt{siglongjmp}(3). See file \texttt{PORTING} in \textit{GNU Pth} \cite{pth} for more details. } \subsection{Remaining Possibilities} Our problem can be divided into two parts, an easy one and a difficult one. \mypar{The Easy Part} \noindent That \texttt{setjmp}(3) and \texttt{longjmp}(3) can be used to implement user-space threads is commonly known \cite{ptl2,rsthreads,uthread}. Mostly all older portable user-space threading libraries are based on them, although some problems are known with these facilities (see below). So it becomes clear that we also have to use these functions and base our machine context (\texttt{mctx\_t}) on their \texttt{jmp\_buf} data structure. We immediately recognize that this way we have at least solved the dispatching problem, because our \texttt{mctx\_save}, \texttt{mctx\_restore} and \texttt{mctx\_switch} functions can be easily implemented with \texttt{setjmp}(3) and \texttt{longjmp}(3). \mypar{The Difficult Part} \noindent Nevertheless, the difficult problem of how to create the machine context remains. Even knowing that our machine context is \texttt{jmp\_buf} based is no advantage to us. A \texttt{jmp\_buf} has to be treated by us as an opaque data structure --- for portability reasons. The only operations we can perform on it are \texttt{setjmp}(3) and \texttt{longjmp}(3) calls, of course. Additionally, we are forced to use \texttt{sigaltstack}(3) for our stack manipulations, because it is the only portable function which actually deals with stacks. So it is clear that our implementation for \texttt{mctx\_\-create} has to play a few tricks to use a \texttt{jmp\_buf} for passing execution control to an arbitrary startup routine. And our approach has to be careful to ensure that it does not suffer from unexpected side-effects. It should be also obvious that we cannot again expect to find an easy solution (as for \texttt{mctx\_save}, \texttt{mctx\_restore} and \texttt{mctx\_switch}), because \texttt{setjmp}(3) and \texttt{sigaltstack}(3) cannot be trivially combined to form \texttt{mctx\_create}. \section{Implementation} As we have already discussed, our implementation contains an easy part (\texttt{mctx\_save}, \texttt{mctx\_restore} and \texttt{mctx\_switch}) and a difficult part (\texttt{mctx\_create}). Let us start with the easy part, whose implementation is obvious (all error checks again omitted for better readability): {\small \baselineskip=9pt \begin{alltt} /* \textrm{\textit{\bfseries machine context data structure}} */ \textbf{typedef struct} mctx_st \{ jmp_buf jb; \} mctx_t; /* \textrm{\textit{\bfseries save machine context}} */ \textbf{#define} mctx_save(mctx) \(\backslash\) (\textbf{void})setjmp((mctx)->jb) /* \textrm{\textit{\bfseries restore machine context}} */ \textbf{#define} mctx_restore(mctx) \(\backslash\) longjmp((mctx)->jb, 1) /* \textrm{\textit{\bfseries switch machine context}} */ \textbf{#define} mctx_switch(mctx_old,mctx_new) \(\backslash\) \textbf{if} (setjmp((mctx_old)->jb) == 0) \(\backslash\) longjmp((mctx_new)->jb, 1) /* \textrm{\textit{\bfseries create machine context}} */ \textbf{void} mctx_create( mctx_t *mctx, \textbf{void} (*sf_addr)(\textbf{void} *), \textbf{void} *sf_arg, \textbf{void} *sk_addr, size_t sk_size) \{ \textrm{\textit{\bfseries ...initialization of \texttt{mctx} to be filled in...}} \} \end{alltt}} \noindent There is one subtle but important point we should mention: The use of the C pre-processor \texttt{\#define} directive to implement \texttt{mctx\_save}, \texttt{mctx\_restore} and \texttt{mctx\_switch} is intentional. For technical reasons related to \texttt{setjmp}(3) semantics and \texttt{return} related stack behavior (which we will explain later in detail) we \textit{cannot} implement these three functions (at least not \texttt{mctx\_switch}) as C functions if we want to achieve maximum portability across all platforms. Instead they have to be implemented as pre-processor macros. \subsection{Algorithm Overview} The general idea for \texttt{mctx\_create} is to configure the given stack as a signal stack via \texttt{sigaltstack}(2), send the current process a signal to transfer execution control onto this stack, save the machine context there via \texttt{setjmp}(3), get rid of the signal handler scope and bootstrap into the startup routine. The real problem in this approach comes from the signal handler scope which implies various restrictions on Unix platforms (the signal handler scope often is just a flag in the process control block (PCB) which various system calls, like \texttt{sigaltstack}(2), check before allowing the operation -- but because it is part of the process state the kernel manages, the process cannot change it itself). As we will see, we have to perform a few tricks to get rid of it. The second main problem is: how do we prepare the calling of the start routine without immediately entering it? \subsection{Algorithm} The input to the \texttt{mctx\_create} function is the machine context structure \textit{mctx} which should be initialized, the thread startup function address \textit{sf\_addr}, the thread startup function argument \textit{sf\_arg} and a chunk of memory starting at \textit{sk\_addr} and \textit{sk\_size} bytes in size, which should become the threads stack. The following algorithm for \texttt{mctx\_create} is directly modeled after the implemented algorithm one can find in \textit{GNU Pth} \cite{pth}, which in turn was derived from techniques originally found in \textit{rsthreads} \cite{rsthreads}: \begin{enumerate} \item Preserve the current signal mask and block an arbitrary worker signal (we use \texttt{SIGUSR1}, but any signal can be used for this -- even an already used one). This worker signal is later temporarily required for the trampoline step. \item Preserve a possibly existing signal action for the worker signal and configure a trampoline function as the new temporary signal action. The signal delivery is configured to occur on an alternate signal stack (see next step). \item Preserve a possibly active alternate signal stack and configure the memory chunk starting at \textit{sk\_addr} as the new temporary alternate signal stack of length \textit{sk\_size}. \item Save parameters for the trampoline step (\textit{mctx}, \textit{sf\_addr}, \textit{sf\_arg}, \textit{etc.}) in global variables, send the current process the worker signal, temporarily unblock it and this way allow it to be delivered on the signal stack in order to transfer execution control to the trampoline function. \item After the trampoline function asynchronously entered, save its machine context in the \textit{mctx} structure and immediately return from it to terminate the signal handler scope. \item Restore the preserved alternate signal stack, preserved signal action and preserved signal mask for worker signal. This way an existing application configuration for the worker signal is restored. \item Save the current machine context of \texttt{mctx\_create}. This allows us to return to this point after the next trampoline step. \item Restore the previously saved machine context of the trampoline function (\textit{mctx}) to again transfer execution control onto the alternate stack, but this time without(!) signal handler scope. \item After reaching the trampoline function (\textit{mctx}) again, immediately bootstrap into a clean stack frame by just calling a second function. \item Set the new signal mask to be the same as the original signal mask which was active when \texttt{mctx\_create} was called. This is required because in the first trampoline step we usually had at least the worker signal blocked. \item Load the passed startup information (\textit{sf\_addr}, \textit{sf\_arg}) from \texttt{mctx\_create} into local (stack-based) variables. This is important because their values have to be preserved in machine context dependent memory until the created machine context is the first time restored by the application. \item Save the current machine context for later restoring by the calling application. \item Restore the previously saved machine context of \texttt{mctx\_create} to transfer execution control back to it. \item Return to the calling application. \end{enumerate} \noindent When the calling application now again switches into the established machine context \textit{mctx}, the thread starts running at routine \textit{sf\_addr} with argument \textit{sf\_arg}. Figure 1 illustrates the algorithm (the numbers refer to the algorithm steps listed above). \bigskip \noindent \psfig{file=rse-pmt.eps}\\[4pt] \parbox{\linewidth}{\footnotesize\baselineskip=0pt \hangafter{\textbf{Figure 1:}\quad}% Illustration of the machine context creation procedure. The thick solid lines and numeric marks correspond to the algorithm steps as described in section 3.2. The thick dotted lines show a possible further processing where a few context switches are performed to dispatch between the main thread and the new created thread. } \smallskip \subsection{Source Code} The corresponding ANSI-C code, which implements \texttt{mctx\_create}, is a little bit more complicated. But with the presented algorithm in mind, it is now straight-forward. {\small% \baselineskip=9pt \begin{alltt} \textbf{static} mctx_t mctx_caller; \textbf{static} sig_atomic_t mctx_called; \textbf{static} mctx_t *mctx_creat; \textbf{static} \textbf{void} (*mctx_creat_func)(\textbf{void} *); \textbf{static} \textbf{void} *mctx_creat_arg; \textbf{static} sigset_t mctx_creat_sigs; \textbf{void} mctx_create( mctx_t *mctx, \textbf{void} (*sf_addr)(\textbf{void} *), \textbf{void} *sf_arg, \textbf{void} *sk_addr, \textbf{size_t} sk_size) \{ \textbf{struct} sigaction sa; \textbf{struct} sigaction osa; \textbf{struct} sigaltstack ss; \textbf{struct} sigaltstack oss; sigset_t osigs; sigset_t sigs; /* \textrm{\textit{\bfseries Step 1:}} */ sigemptyset(&sigs); sigaddset(&sigs, SIGUSR1); sigprocmask(SIG_BLOCK, &sigs, &osigs); /* \textrm{\textit{\bfseries Step 2:}} */ memset((\textbf{void} *)&sa, 0, \textbf{sizeof}(\textbf{struct} sigaction)); sa.sa_handler = mctx_create_trampoline; sa.sa_flags = SA_ONSTACK; sigemptyset(&sa.sa_mask); sigaction(SIGUSR1, &sa, &osa); /* \textrm{\textit{\bfseries Step 3:}} */ ss.ss_sp = sk_addr; ss.ss_size = sk_size; ss.ss_flags = 0; sigaltstack(&ss, &oss); /* \textrm{\textit{\bfseries Step 4:}} */ mctx_creat = mctx; mctx_creat_func = sf_addr; mctx_creat_arg = sf_arg; mctx_creat_sigs = osigs; mctx_called = FALSE; kill(getpid(), SIGUSR1); sigfillset(&sigs); sigdelset(&sigs, SIGUSR1); \textbf{while} (!mctx_called) sigsuspend(&sigs); /* \textrm{\textit{\bfseries Step 6:}} */ sigaltstack(NULL, &ss); ss.ss_flags = SS_DISABLE; sigaltstack(&ss, NULL); if (!(oss.ss_flags & SS_DISABLE)) sigaltstack(&oss, NULL); sigaction(SIGUSR1, &osa, NULL); sigprocmask(SIG_SETMASK, &osigs, NULL); /* \textrm{\textit{\bfseries Step 7 \& Step 8:}} */ mctx_switch(&mctx_caller, mctx); /* \textrm{\textit{\bfseries Step 14:}} */ \textbf{return}; \} \textbf{void} mctx_create_trampoline(\textbf{int} sig) \{ /* \textrm{\textit{\bfseries Step 5:}} */ \textbf{if} (mctx_save(mctx_creat) == 0) \{ mctx_called = TRUE; \textbf{return}; \} /* \textrm{\textit{\bfseries Step 9:}} */ mctx_create_boot(); \} \textbf{void} mctx_create_boot(\textbf{void}) \{ \textbf{void} (*mctx_start_func)(\textbf{void} *); \textbf{void} *mctx_start_arg; /* \textrm{\textit{\bfseries Step 10:}} */ sigprocmask(SIG_SETMASK, &mctx_creat_sigs, NULL); /* \textrm{\textit{\bfseries Step 11:}} */ mctx_start_func = mctx_creat_func; mctx_start_arg = mctx_creat_arg; /* \textrm{\textit{\bfseries Step 12 \& Step 13:}} */ mctx_switch(mctx_creat, &mctx_caller); /* \textrm{\textit{\bfseries The thread ``magically'' starts... }} */ mctx_start_func(mctx_start_arg); /* NOTREACHED */ abort(); \} \end{alltt} } \subsection{Run-time Penalty} After this discussion of the implementation details, an obviously occuring question now is what the expected run-time penalty is. That is, what does our presented machine context implementation cost compared to a \texttt{ucontext}(3) based solution. From the already discussed details we can easily guess that our complex machine context creation procedure (\texttt{mctx\_create}) will be certainly noticeably slower than a solution based on a \texttt{ucontext}(3) facility. But a wild guess is not sufficing for a reasonable statement. So we have written a \textit{Simple Machine Context Benchmark} (SMCB \cite{smcb}) which was used to compare run-time costs of the \texttt{mctx\_create} and \texttt{mctx\_switch} functions if once implemented through the \textit{POSIX} \texttt{makecontext}(3)/\texttt{swapcontext}(3) functions (as shown in section 2.3), and once implemented with our based fallback implementation (for convenience reasons we directly used \texttt{sigjmp\_buf}, \texttt{sigsetjmp}(3) and \texttt{siglongjmp}(3) in the benchmark, because all tested platforms provided this). The results are shown Table 3 below. As one can derive from these evaluations, our signal stack trick to implement \texttt{mctx\_create} in practice is approximately 15 times slower than the \texttt{makecontext}(3) based variant. This cost should not be neglected. On the other hand, the \texttt{sigsetjmp}(3)/ \texttt{siglongjmp}(3) based \texttt{mctx\_switch} performs about as good as the \texttt{swapcontext}(3) based variant (the reason why on most of the tested platforms it is even slightly faster is not known -- but we guess it is related to a greater management overhead in the \texttt{ucontext}(3) facility, which is a superset of the functionality we require). Or in short: our presented fallback approach costs noticeable extra CPU cycles on thread creation time, but is as fast as the standardized solution under thread dispatching time. \bigskip \noindent \fbox {\parbox{7.8cm} {\footnotesize \noindent \medskip \ \ \ {\bfseries 10000 $\times$ mctx\_create (in seconds):}\\[1mm] \begin{tabular}{l|r|r|r} {\bfseries Platform} & {\bfseries mcsc} & {\bfseries sjlj} & {\bfseries overhead} \\ Sun Solaris 2.6 (SPARC) & 0.076 & 1.268 & 16.7 \\ DEC Tru64 5.0 (Alpha) & 0.019 & 0.235 & 12.4 \\ SGI IRIX 6.5 (MIPS) & 0.105 & 1.523 & 14.5 \\ SCO UnixWare 7.0 (Intel) & 0.204 & 3.827 & 18.8 \\ HP HP/UX 11.0 (HPPA) & 0.057 & 0.667 & 11.8 \\ \multicolumn{4}{r}{ {\bfseries Average: \quad 14.8}} \\ \end{tabular} \medskip \ \ \ {\bfseries 10000 $\times$ mctx\_switch (in seconds):}\\[1mm] \begin{tabular}{l|r|r|r} {\bfseries Platform} & {\bfseries mcsc} & {\bfseries sjlj} & {\bfseries overhead} \\ Sun Solaris 2.6 (SPARC) & 0.137 & 0.210 & 1.5 \\ DEC Tru64 5.0 (Alpha) & 0.034 & 0.022 & 0.6 \\ SGI IRIX 6.5 (MIPS) & 0.235 & 0.190 & 0.8 \\ SCO UnixWare 7.0 (Intel) & 0.440 & 0.398 & 0.9 \\ HP HP/UX 11.0 (HPPA) & 0.106 & 0.065 & 0.6 \\ \multicolumn{4}{r}{ {\bfseries Average: \quad 0.9}} \\ \end{tabular} }}\\[4pt] \parbox{\linewidth}{\footnotesize\baselineskip=0pt \hangafter{\textbf{Table 3:}\quad}% Summary of \textit{Simple Machine Context Benchmark} (SMCB, \cite{smcb}). The speed of machine context creation and switching found on each tested operating system. \textbf{mcsc}: functional \texttt{makecontext}(3) / \texttt{switchcontext}(3), \textbf{sjlj}: functional \texttt{sigsetjmp}(3)/\texttt{siglongjmp}(3). \textbf{overhead}: the overhead of using \textbf{sjlj} instead of \textbf{mcsc}. } \subsection{Remaining Issues} The presented algorithm and source code can be directly used in practice for implementing a minimal threading system or the concept of co-routines. Its big advantage is that if the operating system provides the required standardized primitives, we do not need to know anything at all about the machine we are running on --- everything just works. Nevertheless, there remain a few special issues we still have to discuss. \mypar{The Waggly longjmp(3) after Return} \noindent On some platforms, \texttt{longjmp}(3) may not be called after the function which called the \texttt{setjmp}(3) returned. When this is done, the stack frame situation is not guaranteed to be in a clean and consistent state. But this is exactly the mechanism we use in order to get rid of the signal handler scope in step 5. The only alternative would be to leave the signal handler via \texttt{longjmp}(3), but then we would have another problem, as experience showed. For instance, \textsc{Robert S. Thau}'s \textit{Really Simple Threads} (\textit{rsthreads}) \cite{rsthreads} was ported to several platforms and was used to run an experimental multithreaded version of the Apache webserver. \textsc{Thau}'s approach was similar to ours, but differed significantly in the way the signal handler is left. In particular, in an attempt to avoid the unsafe stack frame, it used a \texttt{longjmp}(3) call to leave the signal handler, rather than returning from it. But this approach does not work on some \textit{SysV}-derived kernels, as we already mentioned. The problem is that these kernels do not ``believe'' that the code is out of the signal-handling context, until the signal handler has returned --- and accordingly, refuse to allow readjustment of the signal stack until it has. But with the \textit{rsthreads} approach, the signal handler that created the first thread never returns, and when \textit{rsthreads} wants to create the second thread, these kernels refuse to readjust the signal stack, and we are stuck. So with portability in mind, we decided that it is better to get rid of the signal handler scope with the straight-forward ``\texttt{return}'' and instead fight the mentioned (simpler) problem of an unsafe stack frame. Fortunately, in practice this is not as problematic as it seems, because evaluations (for \textit{GNU Pth}) on a wide range of current Unix platforms showed that one can reach a safe stack frame again by just calling a function. That is the reason why our algorithm enters the second trampoline function in step 9. \mypar{The Uncooperative longjmp(3)} \noindent Even on operating systems which have working \textit{POSIX} functions, our approach may theoretically still not work, because \texttt{longjmp}(3) does not cooperate. For instance, on some platforms the standard \textit{libc} \texttt{longjmp}(3) branches to error-handling code if it detects that the caller tries to jump \textit{up} the stack, \textit{i.e.}, into a stack frame that has already returned. This is usually implemented by comparing the current stack pointer to the one in the \texttt{jmp\_buf} structure. That is why it is important for our algorithm to return from the signal handler and this way enter the (different) stack of the parent thread. In practice, the implementation in \textit{GNU Pth} showed that then one no longer suffers from those uncooperative \texttt{longjmp}(3) implementations, but one should keep this point in mind when reaching even more uncooperative variants on esoteric Unix platforms. If it still occurs, one can only try to resume the operation by using a possibly existing platform-specific error handling hook. \mypar{Garbage at Bottom of Stacks} \noindent There is a subtle side-effect of our implementation: there remains some garbage at the bottom of each thread stack. The reason is that if a signal is delivered, the operating system pushes some state onto the stack, which is restored later, when the signal handler returns. But although we return from the signal handler, we jump in again, and this time we enter not directly at the bottom of the stack, because of the \texttt{setjmp}(3) in the trampoline function. Since the operating system has to capture all CPU registers (including those that are ordinarily scratch registers or caller-save registers), there can be a fair amount of memory at the bottom of the established thread stack. For some systems this can be even up to 1 KB of garbage \cite{rsthreads}. But except for the additional memory consumption it does not hurt. We just have to keep in mind this additional stack consumption when deciding the stack size (\textit{sk\_size}). A reasonable stack size usually is between 16 and 32 KB. Less is neither reasonable nor always allowed (current Unix platforms usually require a stack to be at least 16 KB in size). \mypar{Stack Overflows} \noindent There is a noticeable difference between the initial \texttt{main}() thread and the explicitly spawned threads: the initial thread runs on the standard process stack. This stack automatically can grow under Unix, while the stacks of the spawned threads are fixed in size. So stack overflows can occur for the spawned threads. This implies that the parent has to make a reasonable guess of the threads stack space requirement already at spawning time. And there is no really portable solution to this problem, because even if the thread library's scheduler can detect the stack overflow, it cannot easily resize the stack. The reason is simply that the stack initialization goes hand in hand with the initialization of the start routine, as we discussed before. And this start routine has to be a real C function in order to \textit{call}. But once the thread is running, there no longer exists such an entry point. So, even if the scheduler would be able to give the thread a new enlarged stack, there is no chance to restart the thread on this new stack. Or more correct, there is no \textit{portable} way to achieve it. As with the previous problems, there is a non-portable solution. That is why our implementation did not deal with this issue. Instead in practice one usually lets the scheduler just detect the stack overflow and terminate the thread. This is done by using a red zone at the top of the stack which is marked with a magic value the scheduler checks between thread dispatching operations. Resizing solutions are only possible in semi-portable ways. One approach is to place the thread stacks into a memory mapped area (see \texttt{mmap}(2)) of the process address space and let the scheduler catch \texttt{SIGSEGV} signals. When such a signal occurs, because of a stack overflow in this area, the scheduler explicitly resizes the memory mapped area. This resizing can be done either by copying the stack contents into a new larger area which is then re-mapped to the old address or via an even more elegant way, as the vendor threading libraries of \textit{Sun Solaris}, \textit{FreeBSD} and \textit{DEC Tru64} do it: the thread stacks are allocated inside memory mapped areas which are already initially a few MB in (virtual) size and then one just relies on the virtual memory system's feature that only the actually consumed memory space is mapped. \mypar{Startup Routine Termination} \noindent There is a cruel \texttt{abort}(3) call at the end of our \texttt{mctx\_create\_boot} function. This means, if the startup routine would return, the process is aborted. That is obviously not reasonable, so why have we written it this way? If the thread returns from the startup routine, it should be cleanly terminated. But it cannot terminate itself (for instance, because it cannot free its own stack while running on it, \textit{etc.}). So the termination handling actually is the task of the thread library scheduler. As a consequence, the thread spawning function of a thread library should be not directly \texttt{mctx\_create}. Instead the thread spawning function should use an additional trampoline function as the higher-level startup routine. And this trampoline function performs a context switch back into the thread library scheduler before the lower-level startup routine would return. The scheduler then can safely remove the thread and its machine context. That is why the \texttt{abort}(3) call is never reached in practice (more details can be found in the implementations of \texttt{pth\_spawn} and \texttt{pth\_exit} in \texttt{pth\_lib.c} of \textit{GNU Pth} \cite{pth}) \mypar{The sigstack(2) Fallback Situation} \noindent Not all platforms provide the standardized \texttt{sigaltstack}(2). Instead they at least provide the \textit{4.2BSD} ancestor function \texttt{sigstack}(2). But one cannot trivially replace \texttt{sigaltstack}(2) by \texttt{sigstack}(2) in this situation, because in contrast to \texttt{sigaltstack}(2), the old \texttt{sigstack}(2) does not automatically handle the machine dependent direction of stack growth. Instead, the caller has to know the direction and always call \texttt{sigstack}(2) with the address of the bottom of the stack. So, in a real-world implementation one first has to determine the direction of stack growth in order to use \texttt{sigstack}(2) as a replacement for \texttt{sigaltstack}(2). Fortunately this is easier than it seems on the first look (for details see the macros \texttt{AC\_CHECK\_STACKGROWTH} and \texttt{AC\_CHECK\_STACKSETUP} in file \texttt{aclocal.m4} from \textit{GNU Pth} \cite{pth}). Alternatively if one can afford to waste memory, one can use an elegant trick: to set up a stack of size $N$, one allocates a chunk of memory (starting at address $A$) of size $N\times2$ and then calls \texttt{sigstack}(2) with the parameters \textit{sk\_addr=}$A+N$ and \textit{sk\_size=}$N$, \textit{i.e.}, one specifies the middle of the memory chunk as the stack base. \mypar{The Blind Alley of Brain-Dead Platforms} \noindent The world would not be as funny as it is, if really all Unix platforms would be fair to us. Instead, currently at least one platform exists which plays unfair: unfortunately, ancient versions of the popular \textit{GNU/Linux}. Although we will discover that it both provides \texttt{sigaltstack}(2) and \texttt{sigstack}(2), our approach won't work on \textit{Linux} kernels prior to version 2.2 and \textit{glibc} prior to version 2.1. Why? Because its \textit{libc} provides only stubs of these functions which always return just \texttt{-1} with \texttt{errno} set to \texttt{ENOSYS}. So, this definitely means that our nifty algorithm is useless there, because its central point \textit{is} \texttt{sigaltstack}(2)/\texttt{sigstack}(2). Nevertheless we do not need to give up. At least not, if we, for a single brain-dead platform, accept to break our general goal of not using any platform dependent code. So, what can we actually do here? All we have to do, is to fiddle around a little bit with the machine-dependent \texttt{jmp\_buf} ingredients (by poking around in \texttt{setjmp.h} or by disassembling \texttt{longjmp}(3) in the debugger). Usually one just has to do a \texttt{setjmp}(3) to get an initial state in the \texttt{jmp\_buf} structure and then manually adjust two of its fields: the program counter (usually a structure member with ``\texttt{pc}'' in the name) and the stack pointer (usually a structure member with ``\texttt{sp}'' in the name). That is all and can be acceptable for a real-world implementation which really wants to cover mostly \textit{all} platforms -- at least as long as the special treatment is needed just for one or two platforms. But one has to keep in mind that it at least breaks one of the initial goals and has to be treated as a last chance solution. \mypar{Functions sigsetjmp(3) and siglongjmp(3)} One certainly wants the \textit{POSIX} thread semantics where a thread has its own signal mask. As already mentioned, on some platforms \texttt{setjmp}(3) and \texttt{longjmp}(3) do not provide this and instead one has to explicitly call \texttt{sigsetjmp}(3) and \texttt{siglongjmp}(3) instead. There is only one snare: on some platforms \texttt{sigsetjmp}(3)/\texttt{siglongjmp}(3) save also information about the alternate signals stack. So here one has to make sure that although the thread dispatching later uses \texttt{sigsetjmp}(3)/\texttt{siglongjmp}(3), the thread creation step in \texttt{mctx\_create} still uses plain \texttt{setjmp}(3)/\texttt{longjmp}(3) calls for the trampoline trick. One just has to be careful because the \texttt{jmp\_buf} and \texttt{sigjmp\_buf} structures cannot be mixed between calls to the \texttt{sigsetjmp}(3)/\texttt{siglongjmp}(3) and \texttt{setjmp}(3)/\texttt{longjmp}(3). \mypar{More Machine Context Ingredients} \noindent Finally, for a real-world threading implementation one usually wants to put more state into the machine context structure \texttt{mctx\_t}. For instance to fulfill more \textit{POSIX} threading semantics, it is reasonable to also save and restore the global \texttt{errno} variable. All this can be easily achieved by extending the \texttt{mctx\_t} structure with additional fields and by making the \texttt{mctx\_save}, \texttt{mctx\_restore} and \texttt{mctx\_switch} functions to be aware of them. \subsection{Related Work} Beside \textit{GNU Pth} \cite{pth}, there are other multithreading libraries which use variants of the presented approach for implementing machine contexts in user-space. Most notably there are \textsc{Robert S. Thau}'s \textit{Really Simple Threads} (\textit{rsthreads}, \cite{rsthreads}) package which uses \texttt{sigaltstack}(2) in a very similar way for thread creation, and \textsc{Kota Abe}'s \textit{Portable Thread Library} (\textit{PTL}, \cite{ptl2}) which uses a \texttt{sigstack}(2) approach. But because their approaches handle the signal handler scope differently, they are not able to achieve the same amount of portability and this way do not work for instance on some System-V-derived platforms. \subsection{Summary \& Availability} We have presented a pragmatic and mostly portable fallback approach for implementing the machine context for user-space threads, based entirely on Unix system and ANSI-C language facilities. The approach was successfully tested in practice on a wide range of Unix flavors by \textit{GNU Pth} and should also adapt to the remaining Unix platforms as long as they adhere to the relevant standards. The \textit{GNU Pth} package is distributed under the GNU Library General Public License (LGPL 2.1) and freely available from \textit{http://www.gnu.org/software/pth/} and \textit{ftp://ftp.gnu.org/gnu/pth/}. \subsection{Acknowledgements} I would like to thank \textsc{Robert S. Thau}, \textsc{David Butenhof}, \textsc{Martin Kraemer}, \textsc{Eric Newton} and \textsc{Bruno Haible} for their comments which helped to write the initial version of this paper. Additionally, credit has to be given to \textsc{Christopher Small} and the USENIX reviewers for their invaluable feedback which allowed this paper to be extended, cleaned up and finally published at the USENIX Annual Technical Conference 2000. Finally, thanks go to all users of \textit{GNU Pth} for their feedback on the implementation, which helped in fine-tuning the presented approach. \hfill [\textsf{\small rse}] {\small%\baselineskip=10pt \begin{thebibliography}{XX} \bibitem{iso} \textit{POSIX 1003.1c Threading}, IEEE POSIX 1003.1c-1995, ISO/IEC 9945-1:1996 \bibitem{co1} \textsc{M.E. Conway}: \textit{Design of a separable transition-diagram compiler.}, Comm. ACM 6:7, 1963, p.396-408 \bibitem{co2} \textsc{E.W. Dijkstra}: \textit{Co-operating sequential processes}, in F. Genuys (Ed.), \textit{Programming Languages}, NATO Advanced Study Institute, Academic Press, London, 1965, p.42-112. \bibitem{nbf} \textsc{B. Nichols, D. Buttlar, J.P. Farrel}: \textit{Pthreads Programming - A POSIX Standard for Better Multiprocessing}, O'Reilly, 1996; ISBN 1-56592-115-1 \bibitem{lbe} \textsc{B. Lewis, D. J. Berg}: \textit{Threads Primer - A Guide To Multithreaded Programming}, Prentice Hall, 1996; ISBN 0-13-443698-9 \bibitem{ndi} \textsc{S. J. Norton, M. D. Dipasquale}: \textit{Thread Time - The Multithreaded Programming Guide}, Prentice Hall, 1997; ISBN 0-13-190067-6 \bibitem{drb} \textsc{D. R. Butenhof}: \textit{Programming with POSIX Threads}, Addison Wesley, 1997; ISBN 0-201-63392-2 \bibitem{spr} \textsc{S. Prasad}: \textit{Multithreading Programming Techniques}, McGraw-Hill, 1996; ISBN 0-079-12250-7 \bibitem{kss} \textsc{S. Kleinman, B. Smalders, D. Shah}: \textit{Programming with Threads}, Prentice Hall, 1995; ISBN 0-131-72389-8 \bibitem{cjn} \textsc{C.J. Northrup}: \textit{Programming With Unix Threads}, John Wiley \& Sons, 1996; ISBN 0-471-13751-0 \bibitem{bmv} \textsc{P. Barton-Davis, D. McNamee, R. Vaswani, E. Lazowska}: \textit{Adding Scheduler Activations to Mach 3.0}, University of Washington, 1992; Technical Report 92-08-03 \bibitem{lwp} \textsc{D. Stein, D. Shah}: \textit{Implementing Lightwight Threads}, SunSoft Inc., 1992 (published at USENIX'92). \bibitem{aup} \textsc{W.R.Stevens}: \textit{Advanced Programming in the Unix Environment}, Addison-Wesley, 1992; ISBN 0-201-56317-7 \bibitem{posix} \textsc{D. Lewine}: \textit{POSIX Programmer's Guide: Writing Portable Unix Programs}, O'Reilly \& Associates,Inc., 1994; ISBN 0-937175-73-0 \bibitem{osfaq} \textsc{Bryan O'Sullivan}: \textit{Frequently asked questions for comp.os.research}, 1995; http://www.serpentine.com/\verb|~|bos/os-faq/, ftp://rtfm.mit.edu/pub/usenet/comp.os\-.re\-search/ \bibitem{tfaq1} \textsc{Sun Microsystems, Inc}: \textit{Threads Frequently Asked Questions}, 1995, http://www\-.sun\-.com/\-workshop/\-threads/\-faq.html \bibitem{tfaq2} \textsc{Bryan O'Sullivan}: \textit{Frequently asked questions for comp.programming.threads}, 1997; http://www.serpentine.com/\verb|~|bos/threads-faq/. \bibitem{tfaq3} \textsc{Bil Lewis}: \textit{Frequently asked questions for comp.programming.threads}, 1999; http://\-www.lambdacs.com/\-newsgroup/\-FAQ\-.html \bibitem{mdg} \textsc{Numeric Quest Inc}: \textit{Multithreading - Definitions and Guidelines}; 1998; http://www.numeric-quest.com/lang/multi-frame.html \bibitem{sus} \textsc{The Open Group}: \textit{The Sing\-le Unix Speci\-fi\-cation, Version 2 - Threads}; 1997; http://www\-.opengroup\-.org/online\-pubs/007908799/xsh/threads.html \bibitem{str} \textsc{Sun Microsystems Inc}: \textit{SMI Thread Resources}; http://www.sun\-.com/\-workshop/\-threads \bibitem{fsu} \textsc{Frank Mueller}: \textit{FSU pthreads}; 1997; http://www\-.cs.fsu\-.edu/\-\verb|~|mueller/\-pthreads/ \bibitem{mit} \textsc{Chris Provenzano}: \textit{MIT pthreads}; 1993; http://www.mit\-.edu/people/\-pro\-ven/\-pthreads.html (old), http://www\-.human\-factor\-.com/\-pthreads/\-mit-pthreads.html (updated) \bibitem{ptl2} \textsc{Kota Abe}: \textit{Portable Threading Library} (PTL); 1999; http://www\-.media\-.osaka-cu\-.ac\-.jp/\verb|~|k-abe/PTL/ \bibitem{pth} \textsc{Ralf S. Engelschall}: \textit{GNU Portable Threads} (Pth); 1999; http://www\-.gnu\-.org/\-software/\-pth/, ftp://ftp\-.gnu\-.org/\-gnu/\-pth/ \bibitem{pcthreads} \textsc{Michael T. Peterson}: \textit{POSIX and DCE Threads For Linux} (PCThreads); 1995; http://members.aa\-.net/\verb|~|mtp/PCthreads.html \bibitem{rsthreads} \textsc{Robert S. Thau}: \textit{Really Simple Threads} (rsthreads); 1996; ftp://ftp.ai.mit.edu/pub/rst/ \bibitem{uthread} \textsc{John Birrell}: \textit{FreeBSD uthreads}; 1998; ftp://ftp.freebsd\-.org/pub/FreeBSD/\-FreeBSD-current/src/lib/libc\_r/uthread/ \bibitem{linuxthreads} \textsc{Xavier Leroy}: \textit{The LinuxThreads library}; 1999; http://\-pauillac\-.inria\-.fr/\verb|~|xleroy/\-linux\-threads/ \bibitem{aix} \textsc{IBM}: \textit{AIX Version 4.3 General Programming Concepts: Writing and Debugging Programs; Understanding Threads}; 1998; http://www\-.rs6000\-.ibm\-.com/\-doc\_link/\-en\_US/\-a\_doc\_lib/\-aixprggd/\-genprogc/\-understanding\-\_threads\-.htm \bibitem{nspr} \textit{Netscape Portable Runtime} (NSPR); http://\-www.mozilla.org/\-docs/\-refList/refNSPR/, http://\-lxr.mozilla.org/\-seamonkey/\-source/nsprpub/ \bibitem{smcb} \textsc{Ralf S. Engelschall}: \textit{Simple Machine Context Benchmark}; 2000; http://\-www.gnu.org\-/software/\-pth\-/smcb.tar.gz \end{thebibliography} } \end{multicols} \end{document}