Capability.c 10.6 KB
Newer Older
sof's avatar
sof committed
1 2
/* ---------------------------------------------------------------------------
 *
sof's avatar
sof committed
3
 * (c) The GHC Team, 2002
sof's avatar
sof committed
4 5 6
 *
 * Capabilities
 *
sof's avatar
sof committed
7 8
 * A Capability represent the token required to execute STG code,
 * and all the state an OS thread/task needs to run Haskell code:
sof's avatar
sof committed
9
 * its STG registers, a pointer to its TSO, a nursery etc. During
sof's avatar
sof committed
10
 * STG execution, a pointer to the capabilitity is kept in a
sof's avatar
sof committed
11 12
 * register (BaseReg).
 *
sof's avatar
sof committed
13 14 15
 * Only in an SMP build will there be multiple capabilities, for
 * the threaded RTS and other non-threaded builds, there is only
 * one global capability, namely MainCapability.
sof's avatar
sof committed
16 17 18 19 20
 * 
 * --------------------------------------------------------------------------*/
#include "PosixSource.h"
#include "Rts.h"
#include "RtsUtils.h"
sof's avatar
sof committed
21
#include "OSThreads.h"
sof's avatar
sof committed
22
#include "Capability.h"
sof's avatar
sof committed
23
#include "Schedule.h"  /* to get at EMPTY_RUN_QUEUE() */
24
#include "Signals.h" /* to get at handleSignalsInThisThread() */
sof's avatar
sof committed
25

sof's avatar
sof committed
26 27 28
#if !defined(SMP)
Capability MainCapability;     /* for non-SMP, we have one global capability */
#endif
sof's avatar
sof committed
29

30
nat rts_n_free_capabilities;
sof's avatar
sof committed
31

sof's avatar
sof committed
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
#if defined(RTS_SUPPORTS_THREADS)
/* returning_worker_cond: when a worker thread returns from executing an
 * external call, it needs to wait for an RTS Capability before passing
 * on the result of the call to the Haskell thread that made it.
 * 
 * returning_worker_cond is signalled in Capability.releaseCapability().
 *
 */
Condition returning_worker_cond = INIT_COND_VAR;

/*
 * To avoid starvation of threads blocked on worker_thread_cond,
 * the task(s) that enter the Scheduler will check to see whether
 * there are one or more worker threads blocked waiting on
 * returning_worker_cond.
sof's avatar
sof committed
47
 */
48
nat rts_n_waiting_workers = 0;
sof's avatar
sof committed
49 50 51 52 53 54 55 56

/* thread_ready_cond: when signalled, a thread has become runnable for a
 * task to execute.
 *
 * In the non-SMP case, it also implies that the thread that is woken up has
 * exclusive access to the RTS and all its data structures (that are not
 * locked by the Scheduler's mutex).
 *
57
 * thread_ready_cond is signalled whenever noCapabilities doesn't hold.
sof's avatar
sof committed
58 59
 *
 */
sof's avatar
sof committed
60
Condition thread_ready_cond = INIT_COND_VAR;
sof's avatar
sof committed
61

sof's avatar
sof committed
62 63 64 65 66 67
/*
 * To be able to make an informed decision about whether or not 
 * to create a new task when making an external call, keep track of
 * the number of tasks currently blocked waiting on thread_ready_cond.
 * (if > 0 => no need for a new task, just unblock an existing one).
 *
sof's avatar
sof committed
68 69
 * waitForWorkCapability() takes care of keeping it up-to-date;
 * Task.startTask() uses its current value.
sof's avatar
sof committed
70 71 72 73 74 75 76
 */
nat rts_n_waiting_tasks = 0;
#endif

/* -----------------------------------------------------------------------------
   Initialisation
   -------------------------------------------------------------------------- */
sof's avatar
sof committed
77
static
sof's avatar
sof committed
78 79 80 81
void
initCapability( Capability *cap )
{
    cap->f.stgGCEnter1     = (F_)__stg_gc_enter_1;
82
    cap->f.stgGCFun        = (F_)__stg_gc_fun;
sof's avatar
sof committed
83 84
}

sof's avatar
sof committed
85
#if defined(SMP)
sof's avatar
sof committed
86 87 88 89
static void initCapabilities_(nat n);
#endif

/* 
sof's avatar
sof committed
90 91 92 93 94 95 96
 * Function:  initCapabilities()
 *
 * Purpose:   set up the Capability handling. For the SMP build,
 *            we keep a table of them, the size of which is
 *            controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
 *
 * Pre-conditions: no locks assumed held.
sof's avatar
sof committed
97 98 99 100
 */
void
initCapabilities()
{
sof's avatar
sof committed
101
#if defined(RTS_SUPPORTS_THREADS)
sof's avatar
sof committed
102
  initCondition(&returning_worker_cond);
sof's avatar
sof committed
103
  initCondition(&thread_ready_cond);
sof's avatar
sof committed
104 105
#endif

sof's avatar
sof committed
106 107 108 109
#if defined(SMP)
  initCapabilities_(RtsFlags.ParFlags.nNodes);
#else
  initCapability(&MainCapability);
sof's avatar
sof committed
110
  rts_n_free_capabilities = 1;
sof's avatar
sof committed
111 112 113 114 115
#endif

  return;
}

sof's avatar
sof committed
116
#if defined(SMP)
sof's avatar
sof committed
117
/* Free capability list. */
sof's avatar
sof committed
118
static Capability *free_capabilities; /* Available capabilities for running threads */
119 120
static Capability *returning_capabilities; 
	/* Capabilities being passed to returning worker threads */
sof's avatar
sof committed
121
#endif
sof's avatar
sof committed
122

sof's avatar
sof committed
123 124 125 126
/* -----------------------------------------------------------------------------
   Acquiring capabilities
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
127 128 129 130 131 132 133
/*
 * Function:  grabCapability(Capability**)
 * 
 * Purpose:   the act of grabbing a capability is easy; just 
 *            remove one from the free capabilities list (which
 *            may just have one entry). In threaded builds, worker
 *            threads are prevented from doing so willy-nilly
sof's avatar
sof committed
134
 *            via the condition variables thread_ready_cond and
sof's avatar
sof committed
135 136 137
 *            returning_worker_cond.
 *
 */ 
sof's avatar
sof committed
138 139
void grabCapability(Capability** cap)
{
140
#ifdef RTS_SUPPORTS_THREADS
141
  ASSERT(rts_n_free_capabilities > 0);
142
#endif
sof's avatar
sof committed
143
#if !defined(SMP)
sof's avatar
sof committed
144
  rts_n_free_capabilities = 0;
sof's avatar
sof committed
145
  *cap = &MainCapability;
146
  handleSignalsInThisThread();
sof's avatar
sof committed
147
#else
sof's avatar
sof committed
148 149 150
  *cap = free_capabilities;
  free_capabilities = (*cap)->link;
  rts_n_free_capabilities--;
sof's avatar
sof committed
151
#endif
sof's avatar
sof committed
152 153
}

sof's avatar
sof committed
154
/*
sof's avatar
sof committed
155 156
 * Function:  releaseCapability(Capability*)
 *
sof's avatar
sof committed
157 158 159
 * Purpose:   Letting go of a capability. Causes a
 *            'returning worker' thread or a 'waiting worker'
 *            to wake up, in that order.
sof's avatar
sof committed
160 161 162 163 164 165 166
 *
 */
void releaseCapability(Capability* cap
#if !defined(SMP)
		       STG_UNUSED
#endif
)
167
{	// Precondition: sched_mutex must be held
sof's avatar
sof committed
168
#if defined(RTS_SUPPORTS_THREADS)
169 170 171
#ifndef SMP
  ASSERT(rts_n_free_capabilities == 0);
#endif
sof's avatar
sof committed
172 173 174
  /* Check to see whether a worker thread can be given
     the go-ahead to return the result of an external call..*/
  if (rts_n_waiting_workers > 0) {
sof's avatar
sof committed
175 176 177
    /* Decrement the counter here to avoid livelock where the
     * thread that is yielding its capability will repeatedly
     * signal returning_worker_cond.
sof's avatar
sof committed
178
     */
179 180 181 182 183 184
#if defined(SMP)
	// SMP variant untested
    cap->link = returning_capabilities;
    returning_capabilities = cap;
#else
#endif
sof's avatar
sof committed
185
    rts_n_waiting_workers--;
sof's avatar
sof committed
186
    signalCondition(&returning_worker_cond);
187 188 189 190 191 192 193 194 195
  } else /*if ( !EMPTY_RUN_QUEUE() )*/ {
#if defined(SMP)
    cap->link = free_capabilities;
    free_capabilities = cap;
    rts_n_free_capabilities++;
#else
    rts_n_free_capabilities = 1;
#endif
    /* Signal that a capability is available */
sof's avatar
sof committed
196 197 198
    signalCondition(&thread_ready_cond);
  }
#endif
199
 return;
sof's avatar
sof committed
200 201
}

sof's avatar
sof committed
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
#if defined(RTS_SUPPORTS_THREADS)
/*
 * When a native thread has completed the execution of an external
 * call, it needs to communicate the result back. This is done
 * as follows:
 *
 *  - in resumeThread(), the thread calls grabReturnCapability().
 *  - If no capabilities are readily available, grabReturnCapability()
 *    increments a counter rts_n_waiting_workers, and blocks
 *    waiting for the condition returning_worker_cond to become
 *    signalled.
 *  - upon entry to the Scheduler, a worker thread checks the
 *    value of rts_n_waiting_workers. If > 0, the worker thread
 *    will yield its capability to let a returning worker thread
 *    proceed with returning its result -- this is done via
sof's avatar
sof committed
217
 *    yieldToReturningWorker().
sof's avatar
sof committed
218 219 220 221 222 223 224 225
 *  - the worker thread that yielded its capability then tries
 *    to re-grab a capability and re-enter the Scheduler.
 */

/*
 * Function: grabReturnCapability(Capability**)
 *
 * Purpose:  when an OS thread returns from an external call,
sof's avatar
sof committed
226
 * it calls grabReturnCapability() (via Schedule.resumeThread())
sof's avatar
sof committed
227
 * to wait for permissions to enter the RTS & communicate the
sof's avatar
sof committed
228
 * result of the external call back to the Haskell thread that
sof's avatar
sof committed
229 230
 * made it.
 *
sof's avatar
sof committed
231 232
 * Pre-condition:  pMutex is held.
 * Post-condition: pMutex is still held and a capability has
sof's avatar
sof committed
233 234 235
 *                 been assigned to the worker thread.
 */
void
sof's avatar
sof committed
236
grabReturnCapability(Mutex* pMutex, Capability** pCap)
sof's avatar
sof committed
237 238
{
  IF_DEBUG(scheduler,
sof's avatar
sof committed
239
	   fprintf(stderr,"worker (%ld): returning, waiting for lock.\n", osThreadId()));
sof's avatar
sof committed
240
  IF_DEBUG(scheduler,
sof's avatar
sof committed
241 242
	   fprintf(stderr,"worker (%ld): returning; workers waiting: %d\n",
		   osThreadId(), rts_n_waiting_workers));
243 244 245 246
  if ( noCapabilities() ) {
    rts_n_waiting_workers++;
    wakeBlockedWorkerThread();
    context_switch = 1;	// make sure it's our turn soon
sof's avatar
sof committed
247
    waitCondition(&returning_worker_cond, pMutex);
248 249 250 251 252 253 254 255 256 257
#if defined(SMP)
    *pCap = returning_capabilities;
    returning_capabilities = (*pCap)->link;
#else
    *pCap = &MainCapability;
    ASSERT(rts_n_free_capabilities == 0);
    handleSignalsInThisThread();
#endif
  } else {
    grabCapability(pCap);
sof's avatar
sof committed
258 259 260 261
  }
  return;
}

sof's avatar
sof committed
262 263 264 265 266

/* -----------------------------------------------------------------------------
   Yielding/waiting for capabilities
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
267
/*
sof's avatar
sof committed
268
 * Function: yieldToReturningWorker(Mutex*,Capability*)
sof's avatar
sof committed
269 270 271 272 273 274
 *
 * Purpose:  when, upon entry to the Scheduler, an OS worker thread
 *           spots that one or more threads are blocked waiting for
 *           permission to return back their result, it gives up
 *           its Capability. 
 *
sof's avatar
sof committed
275
 * Pre-condition:  pMutex is assumed held and the thread possesses
sof's avatar
sof committed
276
 *                 a Capability.
277
 * Post-condition: pMutex is held and the Capability has
sof's avatar
sof committed
278 279 280
 *                 been given back.
 */
void
sof's avatar
sof committed
281
yieldToReturningWorker(Mutex* pMutex, Capability** pCap)
sof's avatar
sof committed
282
{
283
  if ( rts_n_waiting_workers > 0 ) {
sof's avatar
sof committed
284
    IF_DEBUG(scheduler,
285
	     fprintf(stderr,"worker thread (%p): giving up RTS token\n", osThreadId()));
sof's avatar
sof committed
286
    releaseCapability(*pCap);
287
        /* And wait for work */
sof's avatar
sof committed
288
    waitForWorkCapability(pMutex, pCap, rtsFalse);
289 290 291
    IF_DEBUG(scheduler,
	     fprintf(stderr,"worker thread (%p): got back RTS token (after yieldToReturningWorker)\n",
	     	osThreadId()));
sof's avatar
sof committed
292 293
  }
  return;
sof's avatar
sof committed
294 295
}

sof's avatar
sof committed
296 297 298 299 300 301 302 303 304 305 306 307

/*
 * Function: waitForWorkCapability(Mutex*, Capability**, rtsBool)
 *
 * Purpose:  wait for a Capability to become available. In
 *           the process of doing so, updates the number
 *           of tasks currently blocked waiting for a capability/more
 *           work. That counter is used when deciding whether or
 *           not to create a new worker thread when an external
 *           call is made.
 *
 * Pre-condition: pMutex is held.
308
 * Post-condition: pMutex is held and *pCap is held by the current thread
sof's avatar
sof committed
309 310 311 312 313 314 315 316 317 318 319 320
 */
void 
waitForWorkCapability(Mutex* pMutex, Capability** pCap, rtsBool runnable)
{
  while ( noCapabilities() || (runnable && EMPTY_RUN_QUEUE()) ) {
    rts_n_waiting_tasks++;
    waitCondition(&thread_ready_cond, pMutex);
    rts_n_waiting_tasks--;
  }
  grabCapability(pCap);
  return;
}
321

sof's avatar
sof committed
322 323
#endif /* RTS_SUPPORTS_THREADS */

sof's avatar
sof committed
324
#if defined(SMP)
sof's avatar
sof committed
325 326 327 328 329 330 331 332
/*
 * Function: initCapabilities_(nat)
 *
 * Purpose:  upon startup, allocate and fill in table
 *           holding 'n' Capabilities. Only for SMP, since
 *           it is the only build that supports multiple
 *           capabilities within the RTS.
 */
sof's avatar
sof committed
333 334
static void
initCapabilities_(nat n)
sof's avatar
sof committed
335 336 337 338 339 340 341 342 343 344 345 346 347
{
  nat i;
  Capability *cap, *prev;
  cap  = NULL;
  prev = NULL;
  for (i = 0; i < n; i++) {
    cap = stgMallocBytes(sizeof(Capability), "initCapabilities");
    initCapability(cap);
    cap->link = prev;
    prev = cap;
  }
  free_capabilities = cap;
  rts_n_free_capabilities = n;
348
  returning_capabilities = NULL;
sof's avatar
sof committed
349 350 351 352
  IF_DEBUG(scheduler,fprintf(stderr,"scheduler: Allocated %d capabilities\n", n_free_capabilities););
}
#endif /* SMP */