1 /* ---------------------------------------------------------------------------
2 * (c) The GHC Team, 2003
6 * A Capability represent the token required to execute STG code,
7 * and all the state an OS thread/task needs to run Haskell code:
8 * its STG registers, a pointer to its TSO, a nursery etc. During
9 * STG execution, a pointer to the capabilitity is kept in a
12 * Only in an SMP build will there be multiple capabilities, for
13 * the threaded RTS and other non-threaded builds, there is only
14 * one global capability, namely MainCapability.
16 * --------------------------------------------------------------------------*/
18 #include "PosixSource.h"
22 #include "OSThreads.h"
23 #include "Capability.h"
24 #include "Schedule.h" /* to get at EMPTY_RUN_QUEUE() */
30 Capability MainCapability; /* for non-SMP, we have one global capability */
33 Capability *capabilities = NULL;
34 nat rts_n_free_capabilities;
36 #if defined(RTS_SUPPORTS_THREADS)
38 /* returning_worker_cond: when a worker thread returns from executing an
39 * external call, it needs to wait for an RTS Capability before passing
40 * on the result of the call to the Haskell thread that made it.
42 * returning_worker_cond is signalled in Capability.releaseCapability().
45 Condition returning_worker_cond = INIT_COND_VAR;
48 * To avoid starvation of threads blocked on worker_thread_cond,
49 * the task(s) that enter the Scheduler will check to see whether
50 * there are one or more worker threads blocked waiting on
51 * returning_worker_cond.
53 nat rts_n_waiting_workers = 0;
55 /* thread_ready_cond: when signalled, a thread has become runnable for a
58 * In the non-SMP case, it also implies that the thread that is woken up has
59 * exclusive access to the RTS and all its data structures (that are not
60 * locked by the Scheduler's mutex).
62 * thread_ready_cond is signalled whenever
63 * !noCapabilities && !EMPTY_RUN_QUEUE().
65 Condition thread_ready_cond = INIT_COND_VAR;
68 * To be able to make an informed decision about whether or not
69 * to create a new task when making an external call, keep track of
70 * the number of tasks currently blocked waiting on thread_ready_cond.
71 * (if > 0 => no need for a new task, just unblock an existing one).
73 * waitForWorkCapability() takes care of keeping it up-to-date;
74 * Task.startTask() uses its current value.
76 nat rts_n_waiting_tasks = 0;
81 * Free capability list.
83 Capability *free_capabilities;
86 * Maps OSThreadId to Capability *
88 HashTable *capability_hash;
92 #define UNUSED_IF_NOT_SMP
94 #define UNUSED_IF_NOT_SMP STG_UNUSED
98 #if defined(RTS_SUPPORTS_THREADS)
100 ANY_WORK_FOR_ME( Condition *cond )
102 // If the run queue is not empty, then we only wake up the guy who
103 // can run the thread at the head, even if there is some other
104 // reason for this task to run (eg. interrupted=rtsTrue).
105 if (!EMPTY_RUN_QUEUE()) {
106 if (run_queue_hd->main == NULL) {
107 return (cond == NULL);
109 return (&run_queue_hd->main->bound_thread_cond == cond);
113 return blackholes_need_checking
115 #if defined(RTS_USER_SIGNALS)
122 INLINE_HEADER rtsBool
125 return (!EMPTY_RUN_QUEUE()
127 || blackholes_need_checking
128 #if defined(RTS_USER_SIGNALS)
134 /* ----------------------------------------------------------------------------
136 ------------------------------------------------------------------------- */
139 initCapability( Capability *cap )
141 cap->r.rInHaskell = rtsFalse;
142 cap->f.stgGCEnter1 = (F_)__stg_gc_enter_1;
143 cap->f.stgGCFun = (F_)__stg_gc_fun;
146 /* ---------------------------------------------------------------------------
147 * Function: initCapabilities()
149 * Purpose: set up the Capability handling. For the SMP build,
150 * we keep a table of them, the size of which is
151 * controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
153 * ------------------------------------------------------------------------- */
155 initCapabilities( void )
160 n = RtsFlags.ParFlags.nNodes;
161 capabilities = stgMallocBytes(n * sizeof(Capability), "initCapabilities");
163 for (i = 0; i < n; i++) {
164 initCapability(&capabilities[i]);
165 capabilities[i].link = &capabilities[i+1];
167 capabilities[n-1].link = NULL;
169 free_capabilities = &capabilities[0];
170 rts_n_free_capabilities = n;
172 capability_hash = allocHashTable();
174 IF_DEBUG(scheduler, sched_belch("allocated %d capabilities", n));
176 capabilities = &MainCapability;
177 initCapability(&MainCapability);
178 rts_n_free_capabilities = 1;
181 #if defined(RTS_SUPPORTS_THREADS)
182 initCondition(&returning_worker_cond);
183 initCondition(&thread_ready_cond);
187 /* ----------------------------------------------------------------------------
188 grabCapability( Capability** )
190 (only externally visible when !RTS_SUPPORTS_THREADS. In the
191 threaded RTS, clients must use waitFor*Capability()).
192 ------------------------------------------------------------------------- */
194 #if defined(RTS_SUPPORTS_THREADS)
198 grabCapability( Capability** cap )
201 ASSERT(rts_n_free_capabilities > 0);
202 *cap = free_capabilities;
203 free_capabilities = (*cap)->link;
204 rts_n_free_capabilities--;
205 insertHashTable(capability_hash, osThreadId(), *cap);
207 # if defined(RTS_SUPPORTS_THREADS)
208 ASSERT(rts_n_free_capabilities == 1);
209 rts_n_free_capabilities = 0;
211 *cap = &MainCapability;
213 #if defined(RTS_SUPPORTS_THREADS)
214 IF_DEBUG(scheduler, sched_belch("worker: got capability"));
218 /* ----------------------------------------------------------------------------
219 * Function: myCapability(void)
221 * Purpose: Return the capability owned by the current thread.
222 * Should not be used if the current thread does not
224 * ------------------------------------------------------------------------- */
229 return lookupHashTable(capability_hash, osThreadId());
231 return &MainCapability;
235 /* ----------------------------------------------------------------------------
236 * Function: releaseCapability(Capability*)
238 * Purpose: Letting go of a capability. Causes a
239 * 'returning worker' thread or a 'waiting worker'
240 * to wake up, in that order.
241 * ------------------------------------------------------------------------- */
244 releaseCapability( Capability* cap UNUSED_IF_NOT_SMP )
246 // Precondition: sched_mutex is held.
247 #if defined(RTS_SUPPORTS_THREADS)
249 ASSERT(rts_n_free_capabilities == 0);
252 cap->link = free_capabilities;
253 free_capabilities = cap;
254 ASSERT(myCapability() == cap);
255 removeHashTable(capability_hash, osThreadId(), NULL);
257 // Check to see whether a worker thread can be given
258 // the go-ahead to return the result of an external call..
259 if (rts_n_waiting_workers > 0) {
260 // Decrement the counter here to avoid livelock where the
261 // thread that is yielding its capability will repeatedly
262 // signal returning_worker_cond.
263 rts_n_waiting_workers--;
264 signalCondition(&returning_worker_cond);
266 sched_belch("worker: released capability to returning worker"));
268 rts_n_free_capabilities++;
269 IF_DEBUG(scheduler, sched_belch("worker: released capability"));
276 #if defined(RTS_SUPPORTS_THREADS)
278 * When a native thread has completed the execution of an external
279 * call, it needs to communicate the result back. This is done
282 * - in resumeThread(), the thread calls waitForReturnCapability().
283 * - If no capabilities are readily available, waitForReturnCapability()
284 * increments a counter rts_n_waiting_workers, and blocks
285 * waiting for the condition returning_worker_cond to become
287 * - upon entry to the Scheduler, a worker thread checks the
288 * value of rts_n_waiting_workers. If > 0, the worker thread
289 * will yield its capability to let a returning worker thread
290 * proceed with returning its result -- this is done via
291 * yieldToReturningWorker().
292 * - the worker thread that yielded its capability then tries
293 * to re-grab a capability and re-enter the Scheduler.
296 /* ----------------------------------------------------------------------------
297 * waitForReturnCapability( Mutext *pMutex, Capability** )
299 * Purpose: when an OS thread returns from an external call,
300 * it calls grabReturnCapability() (via Schedule.resumeThread())
301 * to wait for permissions to enter the RTS & communicate the
302 * result of the external call back to the Haskell thread that
305 * ------------------------------------------------------------------------- */
308 waitForReturnCapability( Mutex* pMutex, Capability** pCap )
310 // Pre-condition: pMutex is held.
313 sched_belch("worker: returning; workers waiting: %d",
314 rts_n_waiting_workers));
316 if ( noCapabilities() ) {
317 rts_n_waiting_workers++;
318 context_switch = 1; // make sure it's our turn soon
319 waitCondition(&returning_worker_cond, pMutex);
321 *pCap = free_capabilities;
322 free_capabilities = (*pCap)->link;
323 ASSERT(pCap != NULL);
324 insertHashTable(capability_hash, osThreadId(), *pCap);
326 *pCap = &MainCapability;
327 ASSERT(rts_n_free_capabilities == 0);
330 grabCapability(pCap);
333 // Post-condition: pMutex is held, pCap points to a capability
334 // which is now held by the current thread.
339 /* ----------------------------------------------------------------------------
340 * yieldCapability( Mutex* pMutex, Capability** pCap )
341 * ------------------------------------------------------------------------- */
344 yieldCapability( Capability** pCap, Condition *cond )
346 // Pre-condition: pMutex is assumed held, the current thread
347 // holds the capability pointed to by pCap.
349 if ( rts_n_waiting_workers > 0 || !ANY_WORK_FOR_ME(cond)) {
351 if (rts_n_waiting_workers > 0) {
352 sched_belch("worker: giving up capability (returning wkr)");
353 } else if (!EMPTY_RUN_QUEUE()) {
354 sched_belch("worker: giving up capability (passing capability)");
356 sched_belch("worker: giving up capability (no threads to run)");
359 releaseCapability(*pCap);
363 // Post-condition: either:
365 // 1. *pCap is NULL, in which case the current thread does not
366 // hold a capability now, or
367 // 2. *pCap is not NULL, in which case the current thread still
368 // holds the capability.
374 /* ----------------------------------------------------------------------------
375 * waitForCapability( Mutex*, Capability**, Condition* )
377 * Purpose: wait for a Capability to become available. In
378 * the process of doing so, updates the number
379 * of tasks currently blocked waiting for a capability/more
380 * work. That counter is used when deciding whether or
381 * not to create a new worker thread when an external
383 * If pThreadCond is not NULL, a capability can be specifically
384 * passed to this thread.
385 * ------------------------------------------------------------------------- */
388 waitForCapability( Mutex* pMutex, Capability** pCap, Condition* pThreadCond )
390 // Pre-condition: pMutex is held.
392 while ( noCapabilities() || !ANY_WORK_FOR_ME(pThreadCond)) {
394 sched_belch("worker: wait for capability (cond: %p)",
397 if (pThreadCond != NULL) {
398 waitCondition(pThreadCond, pMutex);
399 IF_DEBUG(scheduler, sched_belch("worker: get passed capability"));
401 rts_n_waiting_tasks++;
402 waitCondition(&thread_ready_cond, pMutex);
403 rts_n_waiting_tasks--;
404 IF_DEBUG(scheduler, sched_belch("worker: get normal capability"));
407 grabCapability(pCap);
409 // Post-condition: pMutex is held and *pCap is held by the current thread
413 #endif /* RTS_SUPPORTS_THREADS */
415 /* ----------------------------------------------------------------------------
418 Signals that a thread has been placed on the run queue, so a worker
419 might need to be woken up to run it.
421 ToDo: should check whether the thread at the front of the queue is
422 bound, and if so wake up the appropriate worker.
423 -------------------------------------------------------------------------- */
425 threadRunnable ( void )
427 #if defined(RTS_SUPPORTS_THREADS)
428 if ( !noCapabilities() && ANY_WORK_TO_DO() ) {
429 if (!EMPTY_RUN_QUEUE() && run_queue_hd->main != NULL) {
430 signalCondition(&run_queue_hd->main->bound_thread_cond);
433 if (rts_n_waiting_tasks > 0) {
434 signalCondition(&thread_ready_cond);
436 startSchedulerTaskIfNecessary();
443 /* ----------------------------------------------------------------------------
446 Wake up... time to die.
447 -------------------------------------------------------------------------- */
451 #if defined(RTS_SUPPORTS_THREADS)
452 signalCondition(&thread_ready_cond);