Update description of forkProcess; add descriptions for
[haskell-report.git] / ffi / threads.tex
1 \documentclass[a4paper,twoside]{article}
2
3 \usepackage{a4wide}
4
5 \usepackage{proof}
6 \usepackage{code}
7 \usepackage{url}
8 \usepackage{version}
9
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}
19
20 \excludeversion{DRAFT}
21
22 \newcommand{\clearemptydoublepage}{%
23 \newpage{\pagestyle{empty}\cleardoublepage}}
24
25
26 \newcommand{\NS}{{\cal N}}
27 % NS: set of native threads
28 \newcommand{\HS}{{\cal H}}
29 % HS: set of Haskell threads
30 \newcommand{\hcall}{H}
31 \newcommand{\fcall}[2]{F^{#1}~#2}
32 \newcommand{\ret}[1]{RET~#1}
33
34 \newcommand{\bound}[1]{B(#1)}
35 \newcommand{\forkio}[1]{ForkIO(#1)}
36 \begin{document}
37 \pagestyle{headings}
38
39 \title{%
40 The Concurrent Haskell Foreign Function Interface 1.0\\
41 An Addendum to the Haskell 98 FFI Report%
42 }
43
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}
62
63
64 \clearemptydoublepage
65 \pagenumbering{roman}
66 \tableofcontents
67
68 \clearemptydoublepage
69
70 \makeatactive
71
72 %\section*{Preface}
73 %
74
75 \pagenumbering{arabic}
76
77 \section{Introduction}
78
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.
83
84 Concurrent Haskell itself does not require operating system thread primitives\footnote{for
85 example @pthread\_create@ on POSIX systems or @CreateThread@ on Win32}
86 to be used. Today's Concurrent Haskell implementations do in fact use their own
87 scheduler loop and run all Concurrent Haskell threads in just one OS thread.
88
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.
92
93 The functionality described in this addendum facilitates interoperation with foreign
94 languages without sacrificing performance.
95
96 \subsection{Definitions}
97
98 Throughout this document, the term \emph{Haskell thread} will be used to refer to the
99 entity that is visible to Haskell programs. Every Haskell IO action runs in a Haskell thread,
100 and you can create new Haskell threads using @forkIO@.
101
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.
106
107 A Haskell run-time system is responsible for managing the relationship between OS threads
108 and Haskell thread. Every Haskell thread has to be run by an OS thread to do anything at all.
109
110 \section{Problems}
111
112 This section outlines the problems with Haskell implementations that use a single OS thread
113 for executing all Haskell threads.
114
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,
118 the Haskell run-time system is not in control, and therefore all other Haskell threads are
119 blocked.
120
121 This severely limits the usefulness of Concurrent Haskell when used together with the FFI.
122
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.
126
127 \subsection{Thread-local state}
128 OS threads can be uniquely identified by their thread id and by their thread-local state.
129 To libraries that make use of this, it does matter from which OS thread they are called from.
130
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).
137
138 When a Haskell implementation uses only one OS thread to schedule several Haskell
139 threads, only one of these may access a library that uses thread-local state at any given
140 time, as all Haskell threads will share the same OS-thread-local state.
141
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
144 all Haskell threads to a different OS thread at any time. While this behaviour sounds
145 far-fetched, it is a good way to preserve GHC's good multithreading performance.
146
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.
152
153 \section{Requirements}
154
155 The following requirements were used as guidelines for developing the solution to the
156 above problems:
157
158 \begin{itemize}
159 \item Safe Foreign calls (i.e. calls not marked as unsafe) should not cause
160 other threads to block.
161
162 \item Libraries that rely on thread-local state should be usable from Haskell.
163
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.
167
168 Using a library like OpenGL from Haskell would not be practical otherwise.
169
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).
174
175 This requirement is what makes this whole document necessary in the first place.
176 Using exactly one OS thread for every Haskell thread solves the problems by sacrificing
177 some performance.
178
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
182 between Haskell threads and OS threads.
183
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.
188
189 \end{itemize}
190
191 \newpage
192 \section{Informal semantics}
193
194 Here's the basic idea:
195 \begin{description}
196 \item[Haskell threads and OS threads.] \mbox{}\\
197 \begin{itemize}
198 \item Every Haskell thread is \emph{either} unbound, \emph{or} bound to a exactly one OS thread.
199
200 \item At most one Haskell thread may be bound to one OS thread.
201 In particular, @forkIO@ forks a new unbound Haskell thread.
202
203 \item A Haskell thread, bound to a new OS thread, can be created with @forkOS@.
204
205 \end{itemize}
206
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.
212 \item A foreign call made by a Haskell thread is (guaranteed to be) made by its bound OS thread, if
213 any.
214
215 \item If a @safe@ foreign call blocks, then no Haskell threads block. (Remember, every OS thread
216 has at most one Haskell thread bound to it.)
217
218 \item A foreign call \emph{into Haskell} (via @foreign export@ or @foreign import wrapper@) is
219 run by a Haskell thread bound to the OS thread that made the call.
220 \end{itemize}
221
222
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}
229
230
231 \section{Formal semantics}
232
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,
249 the thread is willing to execute a Haskell thread.
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.
254
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''.
258
259 The syntax of a Haskell thread is this:
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}.
278
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$.
283
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.
286
287 \subsection{Evolution}
288
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 $$
357
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.
362
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}
366
367 \section{Primitives}
368
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@.
372
373 \subsection{rtsSupportsBoundThreads}
374
375 \begin{quote}
376 \begin{verbatim}
377 rtsSupportsBoundThreads :: Bool
378 \end{verbatim}
379 \end{quote}
380
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.
384
385 Note that an implementation which uses a simple 1:1 correspondence between
386 Haskell threads and OS threads will define @rtsSupportsBoundThreads@ to be
387 @True@.
388
389 \subsection{forkIO and forkOS}
390
391 \begin{quote}
392 \begin{verbatim}
393 forkIO :: IO () -> IO ThreadId
394 forkOS :: IO () -> IO ThreadId
395 \end{verbatim}
396 \end{quote}
397
398 As described in the formal semantics above.
399
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.
405
406 \subsection{isCurrentThreadBound}
407
408 \begin{quote}
409 \begin{verbatim}
410 isCurrentThreadBound :: IO Bool
411 \end{verbatim}
412 \end{quote}
413
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
416 bound Haskell thread. It may also return @True@ for threads that are not bound
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
419 relationship between Haskell threads and OS threads.
420
421 This primitive is intended to make use of forkOS unnecessary when a bound
422 thread is already available; take a look at @runInBoundThread@ below.
423
424 \subsection{forkProcess}
425
426 \begin{quote}
427 \begin{verbatim}
428 forkProcess :: IO () -> IO ProcessID
429 \end{verbatim}
430 \end{quote}
431
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.
439
440 \section{Utility Functions}
441
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.
445
446 \subsection{runInBoundThread}
447 \begin{quote}
448 \begin{verbatim}
449 runInBoundThread :: IO a -> IO a
450 \end{verbatim}
451 \end{quote}
452
453 Run the IO computation passed as the first argument. If the calling thread
454 is not bound, a bound thread is created temporarily. @runInBoundThread@
455 doesn't finish until the IO computation finishes.
456
457 \begin{quote}
458 \begin{verbatim}
459 runInBoundThread action = do
460 bound <- isCurrentThreadBound
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}
469
470
471 \subsection{runInUnboundThread}
472
473 \begin{quote}
474 \begin{verbatim}
475 runInUnboundThread :: IO a -> IO a
476 \end{verbatim}
477 \end{quote}
478
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.
482
483 \begin{quote}
484 \begin{verbatim}
485 runInUnboundThread action = do
486 bound <- isCurrentThreadBound
487 if bound
488 then do
489 mv <- newEmptyMVar
490 forkIO (action >>= putMVar mv)
491 takeMVar mv
492 else action
493 \end{verbatim}
494 \end{quote}
495
496 \end{document}