c5fcb029bc5596c218f4b9e7a3709285f1af0e68
[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 \subsection{forkIO and forkOS}
370
371 \begin{quote}
372 \begin{verbatim}
373 forkIO :: IO () -> IO ThreadId
374 forkOS :: IO () -> IO ThreadId
375 \end{verbatim}
376 \end{quote}
377
378 As described in the formal semantics above.
379
380 This document does not specify the meaning of the @ThreadId@ return value. The
381 definition of what constitutes one Haskell thread used for the return value
382 need not agree with the definition used for describing the formal semantics.
383 Questions like ``are thread ids preserved across foreign calls and call-backs''
384 are outside the scope of this document.
385
386 \subsection{isCurrentThreadBound}
387
388 \begin{quote}
389 \begin{verbatim}
390 isCurrentThreadBound :: IO Bool
391 \end{verbatim}
392 \end{quote}
393
394 ... should return @True@ if and only if it is safe to use foreign calls that
395 rely on thread-local state. That means it will return True when executed from a
396 bound Haskell thread. It may also return @True@ for threads that are not bound
397 according to the above semantics if the run time system is implemented in such
398 a way that thread-local-state can be used from all threads, e.g. using a 1-1
399 relationship between Haskell threads and OS threads.
400
401 This primitive is intended to make use of forkOS unnecessary when a bound
402 thread is already available; consider the following utility function:
403
404 \begin{quote}
405 \begin{verbatim}
406 runInBoundThread :: IO a -> IO a
407
408 runInBoundThread action = do
409 bound <- isCurrentThreadBound
410 if bound
411 then action
412 else do
413 mv <- newEmptyMVar
414 forkOS (action >>= putMVar mv)
415 takeMVar mv
416 \end{verbatim}
417 \end{quote}
418
419 \subsection{forkProcess}
420
421 \begin{quote}
422 \begin{verbatim}
423 forkProcess :: IO (Maybe ProcessID)
424 \end{verbatim}
425 \end{quote}
426
427 The primitive @forkProcess@ is available in the module @System.Posix.Process@
428 on Posix platforms only.
429 It's semantics are anologous to POSIX @fork@; it returns a process
430 id to the parent, and @Nothing@ to the child. Only the Haskell thread that
431 @forkProcess@ was called from is duplicated in the child process; it
432 will be the only thread in the child process.
433
434 If @forkProcess@ is called from a bound Haskell thread, the duplicated Haskell
435 thread in the child process will again be bound and all the thread-local
436 state will be preserved.
437
438 If @forkProcess@ is called from an unbound Haskell thread, the duplicated
439 Haskell thread in the child process will be unbound.
440
441 \paragraph{Issues:}
442 \begin{itemize}
443 \item Under what circumstances should the forked process terminate?
444 \item The action @forkProcessAll@ from the same module should be removed, as
445 it seems to be unimplementable in the presence of multiple OS threads.
446 \end{itemize}
447
448 \end{document}