1 \documentclass[a4paper,twoside]{article}
3 \usepackage{a4wide}
5 \usepackage{proof}
6 \usepackage{code}
7 \usepackage{url}
8 \usepackage{version}
10 %\sloppy
11 %\setlength{\parskip}{0.5\baselineskip plus 0.2\baselineskip minus 0.1\baselineskip}
12 %\setlength{\parsep}{\parskip}
13 %\setlength{\topsep}{0cm}
14 %\setlength{\parindent}{0cm}
15 %\renewcommand{\textfraction}{0}
16 %\renewcommand{\topfraction}{1}
17 %\renewcommand{\floatpagefraction}{0.8}
18 %\renewcommand{\dblfloatpagefraction}{0.8}
20 \excludeversion{DRAFT}
22 \newcommand{\clearemptydoublepage}{%
23 \newpage{\pagestyle{empty}\cleardoublepage}}
26 \newcommand{\NS}{{\cal N}}
27 % NS: set of native threads
28 \newcommand{\HS}{{\cal H}}
30 \newcommand{\hcall}{H}
31 \newcommand{\fcall}[2]{F^{#1}~#2}
32 \newcommand{\ret}[1]{RET~#1}
34 \newcommand{\bound}[1]{B(#1)}
35 \newcommand{\forkio}[1]{ForkIO(#1)}
36 \begin{document}
39 \title{%
40 The Concurrent Haskell Foreign Function Interface 1.0\\
42 }
44 \author{Wolfgang Thaller}
45 \date{}
46 \maketitle
47 \par\vfill
48 \noindent
49 Copyright (c) 2003 Wolfgang Thaller
50 \par\noindent
51 \emph{The authors intend this Report to belong to the entire Haskell
52 community, and so we grant permission to copy and distribute it for any
53 purpose, provided that it is reproduced in its entirety, including this
54 Notice. Modified versions of this Report may also be copied and distributed
55 for any purpose, provided that the modified version is clearly presented as
56 such, and that it does not claim to be a definition of the Concurrent Haskell
57 Foreign Function Interface.}
58 \par\bigskip\noindent
59 The master version of the Concurrent Haskell FFI Report is at \url{haskell.org}. Any
60 corrections or changes in the report are found there.
61 \thispagestyle{empty}
64 \clearemptydoublepage
65 \pagenumbering{roman}
66 \tableofcontents
68 \clearemptydoublepage
70 \makeatactive
72 %\section*{Preface}
73 %
75 \pagenumbering{arabic}
77 \section{Introduction}
79 This report intends to define the interaction of two extensions to Haskell 98, namely
80 the Foreign Function Interface and Concurrent Haskell. It is therefore an addendum
81 to both the Haskell 98 FFI report and the (yet unwritten) Concurrent Haskell report.
82 Familiarity with Haskell 98 and both extensions is assumed.
86 to be used. Today's Concurrent Haskell implementations do in fact use their own
89 This is significantly more efficient and sometimes also easier to implement than solutions
90 based on the OS primitives. However, there are problems with interfacing such an
91 implementation with libraries written in other languages.
93 The functionality described in this addendum facilitates interoperation with foreign
94 languages without sacrificing performance.
96 \subsection{Definitions}
98 Throughout this document, the term \emph{Haskell thread} will be used to refer to the
102 The term \emph{OS thread} will be used to refer to threads managed by the operating
103 system. All code that is run (both Haskell and foreign code) runs in an OS thread. New
104 OS threads are created using OS-specific primitives, like @pthread\_create@ on POSIX
105 systems and @CreateThread@ on Win32.
107 A Haskell run-time system is responsible for managing the relationship between OS threads
110 \section{Problems}
112 This section outlines the problems with Haskell implementations that use a single OS thread
115 \subsection{Blocking foreign calls}
116 If all Haskell scheduling is done in one OS thread, then there can be only one call to a
117 foreign imported function in progress at any one time. While a foreign call is in progress,
119 blocked.
121 This severely limits the usefulness of Concurrent Haskell when used together with the FFI.
123 For some time now, there has been an optional extension to the Glasgow Haskell Compiler,
124 the so-called Threaded RTS'', that allows non-blocking foreign calls to be made. However,
125 this solution makes the problem described in the next section even worse.
129 To libraries that make use of this, it does matter from which OS thread they are called from.
131 Thread-local state is used mostly to allow libraries that use global state variables as part of
132 their interface to be used from multiple (OS) threads concurrently. One important example of
133 this is OpenGL. OpenGL manages a lot of state variables for each rendering context''.
134 The current rendering context'' is not passed as a parameter to OpenGL functions; rather,
135 it is stored in a thread-local state variable. It is therefore possible to use OpenGL from two
136 separate OS threads to render into two separate contexts (two separate windows).
139 threads, only one of these may access a library that uses thread-local state at any given
142 GHC's threaded RTS made the problem worse: it doesn't execute a (foreign exported)
143 callback in the same OS thread as the (foreign) function that calls it, and it may move
145 far-fetched, it is a good way to preserve GHC's good multithreading performance.
147 Foreign libraries that set a thread-local state variable to a particular value will not find
148 the same value there when they are called from a different OS thread. For example,
149 programs that use OpenGL segfault because OpenGL functions are called from an OS
150 thread that does not have a current OpenGL context set. Similar problems arise with
151 Microsoft's Win32, and Apple's Carbon and Cocoa libraries.
153 \section{Requirements}
155 The following requirements were used as guidelines for developing the solution to the
156 above problems:
158 \begin{itemize}
159 \item Safe Foreign calls (i.e. calls not marked as unsafe) should not cause
162 \item Libraries that rely on thread-local state should be usable from Haskell.
164 \item The specification should be implementable in a way that allows a lot
165 of unsafe'' foreign calls to be made with no additional overhead. Unsafe calls to
166 libraries that rely on thread-local state must be possible.
168 Using a library like OpenGL from Haskell would not be practical otherwise.
170 \item The excellent performance of lightweight'' threads, that is, of using one OS thread
171 to execute all Haskell threads, should not be sacrificed. Performance should still
172 OK when using the new features with only a few threads (i.e. not more than commonly
173 used from multithreaded C programs).
175 This requirement is what makes this whole document necessary in the first place.
177 some performance.
179 \item The specification shouldn't explicitly require lightweight threads to exist.
180 The specification should be implementable in a simple
181 and obvious way in Haskell systems that always use a 1:1 correspondence
184 \item The specification shouldn't specify which particular OS thread
185 should be used to execute Haskell code. It should be possible to
186 implement it with e.g. a Haskell interpreter running in one OS thread
187 that just uses other OS threads for foreign calls.
189 \end{itemize}
191 \newpage
192 \section{Informal semantics}
194 Here's the basic idea:
195 \begin{description}
197 \begin{itemize}
205 \end{itemize}
207 \item[Foreign interface.] \mbox{}\\
208 \begin{itemize}
209 \item No @safe@ vs @threadsafe@ distinction\footnote{@threadsafe@'' has already
210 been removed from the current Release Candidate of the FFI addendum}. But we retain
211 the @safe@/@unsafe@ distinction.
213 any.
215 \item If a @safe@ foreign call blocks, then no Haskell threads block. (Remember, every OS thread
218 \item A foreign call \emph{into Haskell} (via @foreign export@ or @foreign import wrapper@) is
220 \end{itemize}
223 \item[Open questions and notes.] \mbox{}\\
224 \begin{itemize}
225 \item Notice that, there \emph{can} be a 1-1 mapping between Haskell threads
226 and OS threads. Furthermore, we can run efficiently on an SMP.
227 \end{itemize}
228 \end{description}
231 \section{Formal semantics}
233 The syntax of a native thread is this:
234 $$235 \begin{array}{lrcll} 236 \mbox{Native thread} & t & ::= & N[S] \\ 237 \\ 238 \mbox{Native thread stack} & S & ::= & \epsilon & \mbox{Empty}\\ 239 & & | & \hcall : S & \mbox{Executing Haskell} \\ 240 & & | & \fcall{si}{a_{bt}} : S & \mbox{Executing foreign code} \\ 241 & & | & \bullet & \mbox{Unknown}\\ 242 \\ 243 \mbox{Safety indicator} & si & ::= & u & \mbox{Unsafe} \\ 244 & & | & s & \mbox{Safe} 245 \end{array} 246$$
247 A native thread of form $N[S]$ has thread-id $N$, while $S$ is
248 an abstraction of its call stack. If $\hcall$ is on top of the stack,
250 If $\fcall{si}{h}$ is
251 on top of the stack, the thread is in the process of dealing with a call
252 to a foreign function, which will return its result to the Haskell thread
253 $h$. The safety-indicator $si$ is from the FFI spec.
255 A native thread of form $N[H]$ has a stack that exists only to serve Haskell
256 threads, and so can safely block inside a foreign call without mucking anything
257 else up. We might call them worker threads''.
260 $$261 \begin{array}{lrcll} 262 \mbox{Haskell thread} & h & ::= & (a)_{bt} \\ 263 \\ 264 \mbox{Bound thread id} & bt & ::= & \epsilon & \mbox{Not bound} \\ 265 & & | & N & \mbox{Bound to native thread N} \\ 266 \\ 267 \mbox{Haskell action} & a & ::= & p ~@>>@~ a & \mbox{Sequence} \\ 268 & & | & \ret & \mbox{Return from a call into Haskell} \\ 269 \\ 270 \mbox{Primitive action} & p & ::= & \tau & \mbox{Internal action} \\ 271 & & | & @forkIO@~a & \mbox{Fork a thread} \\ 272 & & | & @forkOS@~a & \mbox{Fork a native thread} \\ 273 & & | & \fcall{si}{f} & \mbox{Foreign call} 274 \end{array} 275$$
276 A Haskell thread $h$ of form $(a)_{N}$ has action $a$. The indicator
277 $N$ identifies the native thread $N$ to which the Haskell thread is \emph{bound}.
279 An action $a$ is a sequence of primitive actions, finishing with a
280 return of some kind. A primitive action is either some internal Haskell
281 thing (such as performing a bit of evaluation, or operating on an @MVar@),
282 or else it is a call to a foreign function $f$.
284 We do not model the data passed to, or returned from, a foreign call, nor
285 any details of what internal Haskell'' operations are.
287 \subsection{Evolution}
289 We describe how the system evolves in a very standard way, using
290 transition rules, of form
291 $$292 \NS ; \HS ~\Rightarrow~ \NS' ; \HS' 293$$
294 The structural rules are these:
295 $$296 \begin{array}{c} 297 \infer{\NS \cup \{t\} ; \HS ~\Rightarrow~ \NS' \cup \{t\}; \HS'} 298 {\NS ; \HS ~\Rightarrow~ \NS' ; \HS'} 299 \qquad 300 \infer{\NS ; \HS \cup \{h\} ~\Rightarrow~ \NS'; \HS' \cup \{h\}} 301 {\NS ; \HS ~\Rightarrow~ \NS' ; \HS'} 302 \end{array} 303$$
304 These standard rules allow us to write the interesting transitions with less clutter.
305 $$306 \begin{array}{rcll} 307 N[\hcall:S]; (\tau~@>>@~a)_{bt} 308 & \Rightarrow 309 & N[\hcall:S]; (a)_{bt} & (INT) \\ 310 \\ 311 N[\hcall:S]; (@forkIO@~b~@>>@~a)_{bt} 312 & \Rightarrow 313 & N[\hcall:S]; (a)_{bt}, (b)_\epsilon & (FORKIO) \\ 314 \\ 315 N[\hcall:S]; (\fcall{si}{f}~@>>@~a)_N 316 & \Rightarrow 317 & N[\fcall{si}{a_N}:\hcall:S]; & (FCALL1) \\ 318 N[\hcall]; (\fcall{si}{f}~@>>@~a)_\epsilon 319 & \Rightarrow 320 & N[\fcall{si}{a_\epsilon}:\hcall:S]; & (FCALL2) \\ 321 \\ 322 N[\fcall{si}{a_{bt}}:S]; 323 & \Rightarrow 324 & N[S]; a_{bt} & (FRET) \\ 325 \\ 326 N[\bullet]; 327 & \Rightarrow 328 & N[\hcall:\bullet]; (f ~@>>@~ \ret{})_{N} & (HCALL1) \\ 329 \\ 330 N[\fcall{s}{a} : S]; 331 & \Rightarrow 332 & N[\hcall : \fcall{s}{a} : S]; ~ (f ~@>>@~ \ret{})_{N} & (HCALL2) \\ 333 \\ 334 N[\hcall : S]; (\ret{})_N 335 & \Rightarrow 336 & N[S]; & (HRET) \\ 337 \\ 338 ; (\ret{})_\epsilon 339 & \Rightarrow 340 & ; & (HEND) \\ 341 \\ 342 (nothing) 343 & \Rightarrow 344 & N[\hcall]; & (WKR) \\ 345 & \multicolumn{2}{l}{\mbox{where N is fresh}} \\ 346 \\ 347 (nothing) 348 & \Rightarrow 349 & N[\bullet]; & (EXT) \\ 350 & \multicolumn{2}{l}{\mbox{where N is fresh}} \\ 351 \\ 352 N[S]; 353 & \Rightarrow 354 & (nothing) & (NEND) \\ 355 \end{array} 356$$
358 \begin{description}
359 %\item[FORKOS.] Note that we spawn a new OS thread $M[H,\bullet]$. The $\bullet$ prevents it
360 %participating in (FCALL2), which might block $M$ inside a foreign call; instead, $M$ must
361 %remain available to participate in (FCALL1), since no other OS thread can do so.
363 \item[WKR.] This rule models the birth of new worker OS threads, in case they should
364 all be blocked in a foreign call.
365 \end{description}
367 \section{Primitives}
369 The following primitives are exported from the module @Control.Concurrent@,
370 except for the @forkProcess@ function, which is only available on POSIX systems
371 and exported from @System.Posix.Process@.
375 \begin{quote}
376 \begin{verbatim}
378 \end{verbatim}
379 \end{quote}
381 Defined to be @True@ if multiple OS threads are supported as described in this
382 document. When @rtsSupportsBoundThreads@ is @False@, the function
383 @isCurrentThreadBound@ below will always return @False@, and @forkOS@ will fail.
385 Note that an implementation which uses a simple 1:1 correspondence between
387 @True@.
389 \subsection{forkIO and forkOS}
391 \begin{quote}
392 \begin{verbatim}
393 forkIO :: IO () -> IO ThreadId
394 forkOS :: IO () -> IO ThreadId
395 \end{verbatim}
396 \end{quote}
398 As described in the formal semantics above.
400 This document does not specify the meaning of the @ThreadId@ return value. The
401 definition of what constitutes one Haskell thread used for the return value
402 need not agree with the definition used for describing the formal semantics.
403 Questions like are thread ids preserved across foreign calls and call-backs''
404 are outside the scope of this document.
408 \begin{quote}
409 \begin{verbatim}
411 \end{verbatim}
412 \end{quote}
414 ... should return @True@ if and only if it is safe to use foreign calls that
415 rely on thread-local state. That means it will return True when executed from a
417 according to the above semantics if the run time system is implemented in such
418 a way that thread-local-state can be used from all threads, e.g. using a 1-1
421 This primitive is intended to make use of forkOS unnecessary when a bound
424 \subsection{forkProcess}
426 \begin{quote}
427 \begin{verbatim}
428 forkProcess :: IO () -> IO ProcessID
429 \end{verbatim}
430 \end{quote}
432 The primitive @forkProcess@ is available in the module @System.Posix.Process@
433 on Posix platforms only.
434 While it is based on the POSIX fork system call, it's semantics are slightly
435 different: It only returns to the parent; it doesn't return to the child process,
436 rather, the IO action passed as a parameter will be run as a bound thread in the
437 child process. No other threads will be copied to the child process. When the IO
438 action finishes, the child process will terminate.
440 \section{Utility Functions}
442 The following utility functions are exported from @Control.Concurrent@. They can
443 be implemented in terms of the primitives above; simple reference
444 implementations that ignore exception handling issues are provided below.
447 \begin{quote}
448 \begin{verbatim}
449 runInBoundThread :: IO a -> IO a
450 \end{verbatim}
451 \end{quote}
453 Run the IO computation passed as the first argument. If the calling thread
455 doesn't finish until the IO computation finishes.
457 \begin{quote}
458 \begin{verbatim}
461 if bound
462 then action
463 else do
464 mv <- newEmptyMVar
465 forkOS (action >>= putMVar mv)
466 takeMVar mv
467 \end{verbatim}
468 \end{quote}
473 \begin{quote}
474 \begin{verbatim}
475 runInUnboundThread :: IO a -> IO a
476 \end{verbatim}
477 \end{quote}
479 Run the IO computation passed as the first argument. If the calling thread
480 is bound, an unbound thread is created temporarily using @forkIO@.
481 @runInBoundThread@ doesn't finish until the IO computation finishes.
483 \begin{quote}
484 \begin{verbatim}