ghc/rts/Capability.c

   1 /* ---------------------------------------------------------------------------
   2  * (c) The GHC Team, 2003
   3  *
   4  * Capabilities
   5  *
   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
  10  * register (BaseReg).
  11  *
  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.
  15  *
  16  * --------------------------------------------------------------------------*/
  17
  18 #include "PosixSource.h"
  19 #include "Rts.h"
  20 #include "RtsUtils.h"
  21 #include "RtsFlags.h"
  22 #include "OSThreads.h"
  23 #include "Capability.h"
  24 #include "Schedule.h"  /* to get at EMPTY_RUN_QUEUE() */
  25 #include "Signals.h" /* to get at handleSignalsInThisThread() */
  26
  27 #if !defined(SMP)
  28 Capability MainCapability;     /* for non-SMP, we have one global capability */
  29 #endif
  30
  31 #if defined(RTS_SUPPORTS_THREADS)
  32
  33 nat rts_n_free_capabilities;
  34
  35 /* returning_worker_cond: when a worker thread returns from executing an
  36  * external call, it needs to wait for an RTS Capability before passing
  37  * on the result of the call to the Haskell thread that made it.
  38  *
  39  * returning_worker_cond is signalled in Capability.releaseCapability().
  40  *
  41  */
  42 Condition returning_worker_cond = INIT_COND_VAR;
  43
  44 /*
  45  * To avoid starvation of threads blocked on worker_thread_cond,
  46  * the task(s) that enter the Scheduler will check to see whether
  47  * there are one or more worker threads blocked waiting on
  48  * returning_worker_cond.
  49  */
  50 nat rts_n_waiting_workers = 0;
  51
  52 /* thread_ready_cond: when signalled, a thread has become runnable for a
  53  * task to execute.
  54  *
  55  * In the non-SMP case, it also implies that the thread that is woken up has
  56  * exclusive access to the RTS and all its data structures (that are not
  57  * locked by the Scheduler's mutex).
  58  *
  59  * thread_ready_cond is signalled whenever noCapabilities doesn't hold.
  60  *
  61  */
  62 Condition thread_ready_cond = INIT_COND_VAR;
  63
  64 /*
  65  * To be able to make an informed decision about whether or not
  66  * to create a new task when making an external call, keep track of
  67  * the number of tasks currently blocked waiting on thread_ready_cond.
  68  * (if > 0 => no need for a new task, just unblock an existing one).
  69  *
  70  * waitForWorkCapability() takes care of keeping it up-to-date;
  71  * Task.startTask() uses its current value.
  72  */
  73 nat rts_n_waiting_tasks = 0;
  74
  75 static Condition *passTarget = NULL;
  76 static rtsBool passingCapability = rtsFalse;
  77 #endif
  78
  79 #ifdef SMP
  80 #define UNUSED_IF_NOT_SMP
  81 #else
  82 #define UNUSED_IF_NOT_SMP STG_UNUSED
  83 #endif
  84
  85 /* ----------------------------------------------------------------------------
  86    Initialisation
  87    ------------------------------------------------------------------------- */
  88
  89 static void
  90 initCapability( Capability *cap )
  91 {
  92     cap->f.stgGCEnter1     = (F_)__stg_gc_enter_1;
  93     cap->f.stgGCFun        = (F_)__stg_gc_fun;
  94 }
  95
  96 #if defined(SMP)
  97 static void initCapabilities_(nat n);
  98 #endif
  99
 100 /* ---------------------------------------------------------------------------
 101  * Function:  initCapabilities()
 102  *
 103  * Purpose:   set up the Capability handling. For the SMP build,
 104  *            we keep a table of them, the size of which is
 105  *            controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
 106  *
 107  * ------------------------------------------------------------------------- */
 108 void
 109 initCapabilities( void )
 110 {
 111 #if defined(SMP)
 112   initCapabilities_(RtsFlags.ParFlags.nNodes);
 113 #else
 114   initCapability(&MainCapability);
 115 #endif
 116
 117 #if defined(RTS_SUPPORTS_THREADS)
 118   initCondition(&returning_worker_cond);
 119   initCondition(&thread_ready_cond);
 120   rts_n_free_capabilities = 1;
 121 #endif
 122
 123   return;
 124 }
 125
 126 #if defined(SMP)
 127 /* Free capability list. */
 128 static Capability *free_capabilities; /* Available capabilities for running threads */
 129 static Capability *returning_capabilities;
 130         /* Capabilities being passed to returning worker threads */
 131 #endif
 132
 133 /* ----------------------------------------------------------------------------
 134    grabCapability( Capability** )
 135
 136    (only externally visible when !RTS_SUPPORTS_THREADS.  In the
 137    threaded RTS, clients must use waitFor*Capability()).
 138    ------------------------------------------------------------------------- */
 139
 140 #if defined(RTS_SUPPORTS_THREADS)
 141 static
 142 #endif
 143 void
 144 grabCapability( Capability** cap )
 145 {
 146 #if !defined(SMP)
 147 #if defined(RTS_SUPPORTS_THREADS)
 148   ASSERT(rts_n_free_capabilities == 1);
 149   rts_n_free_capabilities = 0;
 150 #endif
 151   *cap = &MainCapability;
 152   handleSignalsInThisThread();
 153 #else
 154   *cap = free_capabilities;
 155   free_capabilities = (*cap)->link;
 156   rts_n_free_capabilities--;
 157 #endif
 158 #if defined(RTS_SUPPORTS_THREADS)
 159   IF_DEBUG(scheduler, sched_belch("worker: got capability"));
 160 #endif
 161 }
 162
 163 /* ----------------------------------------------------------------------------
 164  * Function:  releaseCapability(Capability*)
 165  *
 166  * Purpose:   Letting go of a capability. Causes a
 167  *            'returning worker' thread or a 'waiting worker'
 168  *            to wake up, in that order.
 169  * ------------------------------------------------------------------------- */
 170
 171 void
 172 releaseCapability( Capability* cap UNUSED_IF_NOT_SMP )
 173 {
 174     // Precondition: sched_mutex is held.
 175 #if defined(RTS_SUPPORTS_THREADS)
 176 #ifndef SMP
 177     ASSERT(rts_n_free_capabilities == 0);
 178 #endif
 179     // Check to see whether a worker thread can be given
 180     // the go-ahead to return the result of an external call..
 181     if (rts_n_waiting_workers > 0) {
 182         // Decrement the counter here to avoid livelock where the
 183         // thread that is yielding its capability will repeatedly
 184         // signal returning_worker_cond.
 185
 186 #if defined(SMP)
 187         // SMP variant untested
 188         cap->link = returning_capabilities;
 189         returning_capabilities = cap;
 190 #endif
 191
 192         rts_n_waiting_workers--;
 193         signalCondition(&returning_worker_cond);
 194         IF_DEBUG(scheduler, sched_belch("worker: released capability to returning worker"));
 195     } else if (passingCapability) {
 196         if (passTarget == NULL) {
 197             signalCondition(&thread_ready_cond);
 198             startSchedulerTaskIfNecessary();
 199         } else {
 200             signalCondition(passTarget);
 201         }
 202         rts_n_free_capabilities = 1;
 203         IF_DEBUG(scheduler, sched_belch("worker: released capability, passing it"));
 204
 205     } else {
 206 #if defined(SMP)
 207         cap->link = free_capabilities;
 208         free_capabilities = cap;
 209         rts_n_free_capabilities++;
 210 #else
 211         rts_n_free_capabilities = 1;
 212 #endif
 213         // Signal that a capability is available
 214         if (rts_n_waiting_tasks > 0) {
 215             signalCondition(&thread_ready_cond);
 216         }
 217         startSchedulerTaskIfNecessary();
 218         IF_DEBUG(scheduler, sched_belch("worker: released capability"));
 219     }
 220 #endif
 221     return;
 222 }
 223
 224 #if defined(RTS_SUPPORTS_THREADS)
 225 /*
 226  * When a native thread has completed the execution of an external
 227  * call, it needs to communicate the result back. This is done
 228  * as follows:
 229  *
 230  *  - in resumeThread(), the thread calls waitForReturnCapability().
 231  *  - If no capabilities are readily available, waitForReturnCapability()
 232  *    increments a counter rts_n_waiting_workers, and blocks
 233  *    waiting for the condition returning_worker_cond to become
 234  *    signalled.
 235  *  - upon entry to the Scheduler, a worker thread checks the
 236  *    value of rts_n_waiting_workers. If > 0, the worker thread
 237  *    will yield its capability to let a returning worker thread
 238  *    proceed with returning its result -- this is done via
 239  *    yieldToReturningWorker().
 240  *  - the worker thread that yielded its capability then tries
 241  *    to re-grab a capability and re-enter the Scheduler.
 242  */
 243
 244 /* ----------------------------------------------------------------------------
 245  * waitForReturnCapability( Mutext *pMutex, Capability** )
 246  *
 247  * Purpose:  when an OS thread returns from an external call,
 248  * it calls grabReturnCapability() (via Schedule.resumeThread())
 249  * to wait for permissions to enter the RTS & communicate the
 250  * result of the external call back to the Haskell thread that
 251  * made it.
 252  *
 253  * ------------------------------------------------------------------------- */
 254
 255 void
 256 waitForReturnCapability( Mutex* pMutex, Capability** pCap )
 257 {
 258     // Pre-condition: pMutex is held.
 259
 260     IF_DEBUG(scheduler,
 261              sched_belch("worker: returning; workers waiting: %d",
 262                          rts_n_waiting_workers));
 263
 264     if ( noCapabilities() || passingCapability ) {
 265         rts_n_waiting_workers++;
 266         wakeBlockedWorkerThread();
 267         context_switch = 1;     // make sure it's our turn soon
 268         waitCondition(&returning_worker_cond, pMutex);
 269 #if defined(SMP)
 270         *pCap = returning_capabilities;
 271         returning_capabilities = (*pCap)->link;
 272 #else
 273         *pCap = &MainCapability;
 274         ASSERT(rts_n_free_capabilities == 0);
 275         handleSignalsInThisThread();
 276 #endif
 277     } else {
 278         grabCapability(pCap);
 279     }
 280
 281     // Post-condition: pMutex is held, pCap points to a capability
 282     // which is now held by the current thread.
 283     return;
 284 }
 285
 286
 287 /* ----------------------------------------------------------------------------
 288  * yieldCapability( Mutex* pMutex, Capability** pCap )
 289  * ------------------------------------------------------------------------- */
 290
 291 void
 292 yieldCapability( Capability** pCap )
 293 {
 294     // Pre-condition:  pMutex is assumed held, the current thread
 295     // holds the capability pointed to by pCap.
 296
 297     if ( rts_n_waiting_workers > 0 || passingCapability ) {
 298         IF_DEBUG(scheduler, sched_belch("worker: giving up capability"));
 299         releaseCapability(*pCap);
 300         *pCap = NULL;
 301     }
 302
 303     // Post-condition:  pMutex is assumed held, and either:
 304     //
 305     //  1. *pCap is NULL, in which case the current thread does not
 306     //     hold a capability now, or
 307     //  2. *pCap is not NULL, in which case the current thread still
 308     //     holds the capability.
 309     //
 310     return;
 311 }
 312
 313
 314 /* ----------------------------------------------------------------------------
 315  * waitForCapability( Mutex*, Capability**, Condition* )
 316  *
 317  * Purpose:  wait for a Capability to become available. In
 318  *           the process of doing so, updates the number
 319  *           of tasks currently blocked waiting for a capability/more
 320  *           work. That counter is used when deciding whether or
 321  *           not to create a new worker thread when an external
 322  *           call is made.
 323  *           If pThreadCond is not NULL, a capability can be specifically
 324  *           passed to this thread using passCapability.
 325  * ------------------------------------------------------------------------- */
 326
 327 void
 328 waitForCapability( Mutex* pMutex, Capability** pCap, Condition* pThreadCond )
 329 {
 330     // Pre-condition: pMutex is held.
 331
 332     while ( noCapabilities() ||
 333             (passingCapability && passTarget != pThreadCond)) {
 334         IF_DEBUG(scheduler,
 335                  sched_belch("worker: wait for capability (cond: %p)",
 336                              pThreadCond));
 337
 338         if (pThreadCond != NULL) {
 339             waitCondition(pThreadCond, pMutex);
 340             IF_DEBUG(scheduler, sched_belch("worker: get passed capability"));
 341         } else {
 342             rts_n_waiting_tasks++;
 343             waitCondition(&thread_ready_cond, pMutex);
 344             rts_n_waiting_tasks--;
 345             IF_DEBUG(scheduler, sched_belch("worker: get normal capability"));
 346         }
 347     }
 348     passingCapability = rtsFalse;
 349     grabCapability(pCap);
 350
 351     // Post-condition: pMutex is held and *pCap is held by the current thread
 352     return;
 353 }
 354
 355 /* ----------------------------------------------------------------------------
 356    passCapability, passCapabilityToWorker
 357    ------------------------------------------------------------------------- */
 358
 359 void
 360 passCapability( Condition *pTargetThreadCond )
 361 {
 362     // Pre-condition: pMutex is held and cap is held by the current thread
 363
 364     passTarget = pTargetThreadCond;
 365     passingCapability = rtsTrue;
 366     IF_DEBUG(scheduler, sched_belch("worker: passCapability"));
 367
 368     // Post-condition: pMutex is held; cap is still held, but will be
 369     //                 passed to the target thread when next released.
 370 }
 371
 372 void
 373 passCapabilityToWorker( void )
 374 {
 375     // Pre-condition: pMutex is held and cap is held by the current thread
 376
 377     passTarget = NULL;
 378     passingCapability = rtsTrue;
 379     IF_DEBUG(scheduler, sched_belch("worker: passCapabilityToWorker"));
 380
 381     // Post-condition: pMutex is held; cap is still held, but will be
 382     //                 passed to a worker thread when next released.
 383 }
 384
 385 #endif /* RTS_SUPPORTS_THREADS */
 386
 387 /* ------------------------------------------------------------------------- */
 388
 389 #if defined(SMP)
 390 /*
 391  * Function: initCapabilities_(nat)
 392  *
 393  * Purpose:  upon startup, allocate and fill in table
 394  *           holding 'n' Capabilities. Only for SMP, since
 395  *           it is the only build that supports multiple
 396  *           capabilities within the RTS.
 397  */
 398 static void
 399 initCapabilities_(nat n)
 400 {
 401   nat i;
 402   Capability *cap, *prev;
 403   cap  = NULL;
 404   prev = NULL;
 405   for (i = 0; i < n; i++) {
 406     cap = stgMallocBytes(sizeof(Capability), "initCapabilities");
 407     initCapability(cap);
 408     cap->link = prev;
 409     prev = cap;
 410   }
 411   free_capabilities = cap;
 412   rts_n_free_capabilities = n;
 413   returning_capabilities = NULL;
 414   IF_DEBUG(scheduler,
 415            sched_belch("allocated %d capabilities", n_free_capabilities));
 416 }
 417 #endif /* SMP */
 418