doc: Add serial to list of ci file reserved words
[charm.git] / src / QuickThreads / README
1 This is a source code distribution for QuickThreads.  QuickThreads is a
2 toolkit for building threads packages; it is described in detail in the
3 University of Washington CS&E Technical report #93-05-06, available via
4 anonymous ftp from `ftp.cs.washington.edu' (128.95.1.4, as of Oct. '94)
5 in `tr/1993/05/UW-CSE-93-05-06.PS.Z'.
6
7 This distribution shows basic ideas in QuickThreads and elaborates
8 with example implementations for a gaggle of machines.  As of
9 October '94 those machines included:
10
11         80386 faimly
12         88000 faimily
13         DEC AXP (Alpha) family
14         HP-PA family
15         KSR
16         MIPS family
17         SPARC V8 family
18         VAX family
19
20 In May 1997, a setjmp-based version which is likely to compile on
21 many platforms has been added.
22
23 Be aware: that there is no varargs code for the KSR, or the setjmp
24 version.
25
26 The HP-PA port was designed to work with both HP workstations
27 and Convex SPP computers. It was generously provided by Uwe Reder
28 <uereder@cip.informatik.uni-erlangen.de>. It is part of the ELiTE
29 (Erlangen Lightweight Thread Environment) project directed by 
30 Frank Bellosa <bellosa@informatik.uni-erlangen.de> at the Operating 
31 Systems Department of the University of Erlangen (Germany).
32
33 Other contributors include: Weihaw Chuang, Richard O'Keefe,
34 Laurent Perron, John Polstra, Shinji Suzuki, Assar Westerlund,
35 thanks also to Peter Buhr and Dirk Grunwald.
36
37
38 Here is a brief summary:
39
40 QuickThreads is a toolkit for building threads packages.  It is my hope
41 that you'll find it easier to use QuickThreads normally than to take it
42 and modify the raw cswap code to fit your application.  The idea behind
43 QuickThreads is that it should make it easy for you to write & retarget
44 threads packages.  If you want the routine `t_create' to create threads
45 and `t_block' to suspend threads, you write them using the QuickThreads
46 `primitive' operations `QT_SP', `QT_INIT', and `QT_BLOCK', that perform
47 machine-dependent initialization and blocking, plus code you supply for
48 performing the portable operatons.  For example, you might write:
49
50         t_create (func, arg)
51         {
52           stk = malloc (STKSIZE);
53           stackbase = QT_SP (stk, STKSIZE);
54           sp = QT_INIT (stakcbase, func, arg);
55           qput (runq, sp);
56         }
57
58 Threads block by doing something like:
59
60         t_block()
61         {
62           sp_next = qget (runq);
63           QT_BLOCK (helper, runq, sp_next);
64           // wake up again here
65         }
66
67         // called by QT_BLOCK after the old thread has blocked,
68         // puts the old thread on the queue `onq'.
69         helper (sp_old, onq)
70         {
71           qput (onq, sp_old);
72         }
73
74 (Of course) it's actually a bit more complex than that, but the general
75 idea is that you write portable code to allocate stacks and enqueue and
76 dequeue threads.  Than, to get your threads package up and running on a
77 different machine, you just reconfigure QuickThreads and recompile, and
78 that's it.
79
80 The QuickThreads `distribution' includes a sample threads package (look
81 at stp.{c,h}) that is written in terms of QuickThreads operations.  The
82 TR mentioned above explains the simple threads package in detail.
83
84 If you do use QuickThreads, I'd like to hear both about what worked for
85 you and what didn't work, problems you had, insights gleaned, etc.
86
87 Let me know what you think.
88
89 David Keppel <pardo@cs.washington.edu>
90
91
92 -------------------------------------------------------------------------------
93
94 Date: Tue, 11 Jan 94 13:23:11 -0800
95 From: "pardo@cs.washington.edu" <pardo@meitner.cs.washington.edu>
96
97 >[What's needed to get `qt' on an i860-based machine?]
98
99 Almost certainly "some assembly required" (pun accepted).
100
101 To write a cswap port, you need to understand the context switching
102 model.  Turn to figure 2 in the QT TR.  Here's about what the assembly
103 code looks like to implement that:
104
105         qt_cswap:
106                 adjust stack pointer
107                 save callee-save registers on to old's stack
108                 argument register <- old sp
109                 sp <- new sp
110                 (*helper)(args...)
111                 restore callee-save registers from new's stack
112                 unadjust stack pointer
113                 return
114
115 Once more in slow motion:
116
117         - `old' thread calls context switch routine (new, a0, a1, h)
118         - cswap routine saves registers that have useful values
119         - cswap routine switches to new stack
120         - cswap routine calls helper function (*h)(old, a0, a1)
121         - when helper returns, cswap routine restores registers
122           that were saved the last time `new' was suspended
123         - cswap routine returns to whatever `new' routine called the
124           context switch routine
125
126 There's a few tricks here.  First, how do you start a thread running
127 for the very first time?  Answer is: fake some stuff on the stack
128 so it *looks* like it was called from the middle of some routine.
129 When the new thread is restarted, it is treated like any other
130 thread.  It just so happens that it's never really run before, but
131 you can't tell that because the saved state makes it look like like
132 it's been run.  The return pc is set to point at a little stub of
133 assembly code that loads up registers with the right values and
134 then calls `only'.
135
136 Second, I advise you to forget about varargs routines (at least
137 until you get single-arg routines up and running).
138
139 Third, on most machines `qt_abort' is the same as `qt_cswap' except
140 that it need not save any callee-save registers.
141
142 Fourth, `qt_cswap' needs to save and restore any floating-point
143 registers that are callee-save (see your processor handbook).  On
144 some machines, *no* floating-point registers are callee-save, so
145 `qt_cswap' is exactly the same as the integer-only cswap routine.
146
147 I suggest staring at the MIPS code for a few minutes.  It's "mostly"
148 generic RISC code, so it gets a lot of the flavor across without
149 getting too bogged down in little nitty details.
150
151
152
153 Now for a bit more detail:  The stack is laid out to hold callee-save
154 registers.  On many machines, I implemented fp cswap as save fp
155 regs, call integer cswap, and when integer cswap returns (when the
156 thread wakes up again), restore fp regs.
157
158 For thread startup, I figure out some callee-save registers that
159 I use to hold parameters to the startup routine (`only').  When
160 the thread is being started it doesn't have any saved registers
161 that need to be restored, but I go ahead and let the integer context
162 switch routine restore some registers then "return" to the stub
163 code.  The stub code then copies the "callee save" registers to
164 argument registers and calls the startup routine.  That keeps the
165 stub code pretty darn simple.
166
167 For each machine I need to know the machine's procedure calling
168 convention before I write a port.  I figure out how many callee-save
169 registers are there and allocate enough stack space for those
170 registers.  I also figure out how parameters are passed, since I
171 will need to call the helper function.  On most RISC machines, I
172 just need to put the old sp in the 0'th arg register and then call
173 indirect through the 3rd arg register; the 1st and 2nd arg registers
174 are already set up correctly.  Likewise, I don't touch the return
175 value register between the helper's return and the context switch
176 routine's return.
177
178 I have a bunch of macros set up to do the stack initialization.
179 The easiest way to debug this stuff is to go ahead and write a C
180 routine to do stack initialization.  Once you're happy with it you
181 can turn it in to a macro.
182
183 In general there's a lot of ugly macros, but most of them do simple
184 things like return constants, etc.  Any time you're looking at it
185 and it looks confusing you just need to remember "this is actually
186 simple code, the only tricky thing is calling the helper between
187 the stack switch and the new thread's register restore."
188
189
190 You will almost certainly need to write the assembly code fragment
191 that starts a thread.  You might be able to do a lot of the context
192 switch code with `setjmp' and `longjmp', if they *happen* to have
193 the "right" implementation.  But getting all the details right (the
194 helper can return a value to the new thread's cswap routine caller)
195 is probaby trickier than writing code that does the minimum and
196 thus doesn't have any extra instructions (or generality) to cause
197 problems.
198
199 I don't know of any ports besides those included with the source
200 code distribution.   If you send me a port I will hapily add it to
201 the distribution.
202
203 Let me know as you have questions and/or comments.
204
205         ;-D on  ( Now *that*'s a switch... )  Pardo