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 nat rts_n_free_capabilities;
  32
  33 #if defined(RTS_SUPPORTS_THREADS)
  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
  60  *      !noCapabilities && !EMPTY_RUN_QUEUE().
  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 #if defined(SMP)
  80 /*
  81  * Free capability list.
  82  */
  83 Capability *free_capabilities;
  84 #endif
  85
  86 #ifdef SMP
  87 #define UNUSED_IF_NOT_SMP
  88 #else
  89 #define UNUSED_IF_NOT_SMP STG_UNUSED
  90 #endif
  91
  92 #if defined(RTS_USER_SIGNALS)
  93 #define ANY_WORK_TO_DO() (!EMPTY_RUN_QUEUE() || interrupted || blackholes_need_checking || signals_pending())
  94 #else
  95 #define ANY_WORK_TO_DO() (!EMPTY_RUN_QUEUE() || interrupted || blackholes_need_checking)
  96 #endif
  97
  98 /* ----------------------------------------------------------------------------
  99    Initialisation
 100    ------------------------------------------------------------------------- */
 101
 102 static void
 103 initCapability( Capability *cap )
 104 {
 105     cap->f.stgGCEnter1     = (F_)__stg_gc_enter_1;
 106     cap->f.stgGCFun        = (F_)__stg_gc_fun;
 107 }
 108
 109 /* -----------------------------------------------------------------------------
 110  * Function: initCapabilities_(nat)
 111  *
 112  * Purpose:  upon startup, allocate and fill in table
 113  *           holding 'n' Capabilities. Only for SMP, since
 114  *           it is the only build that supports multiple
 115  *           capabilities within the RTS.
 116  * -------------------------------------------------------------------------- */
 117 #if defined(SMP)
 118 static void
 119 initCapabilities_(nat n)
 120 {
 121   nat i;
 122   Capability *cap, *prev;
 123   cap  = NULL;
 124   prev = NULL;
 125   for (i = 0; i < n; i++) {
 126     cap = stgMallocBytes(sizeof(Capability), "initCapabilities");
 127     initCapability(cap);
 128     cap->link = prev;
 129     prev = cap;
 130   }
 131   free_capabilities = cap;
 132   rts_n_free_capabilities = n;
 133   IF_DEBUG(scheduler,
 134            sched_belch("allocated %d capabilities", rts_n_free_capabilities));
 135 }
 136 #endif /* SMP */
 137
 138 /* ---------------------------------------------------------------------------
 139  * Function:  initCapabilities()
 140  *
 141  * Purpose:   set up the Capability handling. For the SMP build,
 142  *            we keep a table of them, the size of which is
 143  *            controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
 144  *
 145  * ------------------------------------------------------------------------- */
 146 void
 147 initCapabilities( void )
 148 {
 149 #if defined(SMP)
 150   initCapabilities_(RtsFlags.ParFlags.nNodes);
 151 #else
 152   initCapability(&MainCapability);
 153 #endif
 154
 155 #if defined(RTS_SUPPORTS_THREADS)
 156   initCondition(&returning_worker_cond);
 157   initCondition(&thread_ready_cond);
 158 #endif
 159
 160   rts_n_free_capabilities = 1;
 161 }
 162
 163 /* ----------------------------------------------------------------------------
 164    grabCapability( Capability** )
 165
 166    (only externally visible when !RTS_SUPPORTS_THREADS.  In the
 167    threaded RTS, clients must use waitFor*Capability()).
 168    ------------------------------------------------------------------------- */
 169
 170 #if defined(RTS_SUPPORTS_THREADS)
 171 static
 172 #endif
 173 void
 174 grabCapability( Capability** cap )
 175 {
 176 #if defined(SMP)
 177   ASSERT(rts_n_free_capabilities > 0);
 178   *cap = free_capabilities;
 179   free_capabilities = (*cap)->link;
 180   rts_n_free_capabilities--;
 181 #else
 182 # if defined(RTS_SUPPORTS_THREADS)
 183   ASSERT(rts_n_free_capabilities == 1);
 184   rts_n_free_capabilities = 0;
 185 # endif
 186   *cap = &MainCapability;
 187   handleSignalsInThisThread();
 188 #endif
 189 #if defined(RTS_SUPPORTS_THREADS)
 190   IF_DEBUG(scheduler, sched_belch("worker: got capability"));
 191 #endif
 192 }
 193
 194 /* ----------------------------------------------------------------------------
 195  * Function:  releaseCapability(Capability*)
 196  *
 197  * Purpose:   Letting go of a capability. Causes a
 198  *            'returning worker' thread or a 'waiting worker'
 199  *            to wake up, in that order.
 200  * ------------------------------------------------------------------------- */
 201
 202 void
 203 releaseCapability( Capability* cap UNUSED_IF_NOT_SMP )
 204 {
 205     // Precondition: sched_mutex is held.
 206 #if defined(RTS_SUPPORTS_THREADS)
 207 #if !defined(SMP)
 208     ASSERT(rts_n_free_capabilities == 0);
 209 #endif
 210     // Check to see whether a worker thread can be given
 211     // the go-ahead to return the result of an external call..
 212     if (rts_n_waiting_workers > 0) {
 213         // Decrement the counter here to avoid livelock where the
 214         // thread that is yielding its capability will repeatedly
 215         // signal returning_worker_cond.
 216
 217 #if defined(SMP)
 218         // SMP variant untested
 219         cap->link = free_capabilities;
 220         free_capabilities = cap;
 221 #endif
 222
 223         rts_n_waiting_workers--;
 224         signalCondition(&returning_worker_cond);
 225         IF_DEBUG(scheduler, sched_belch("worker: released capability to returning worker"));
 226     } else if (passingCapability) {
 227         if (passTarget == NULL) {
 228             signalCondition(&thread_ready_cond);
 229             startSchedulerTaskIfNecessary();
 230         } else {
 231             signalCondition(passTarget);
 232         }
 233         rts_n_free_capabilities = 1;
 234         IF_DEBUG(scheduler, sched_belch("worker: released capability, passing it"));
 235
 236     } else {
 237 #if defined(SMP)
 238         cap->link = free_capabilities;
 239         free_capabilities = cap;
 240         rts_n_free_capabilities++;
 241 #else
 242         rts_n_free_capabilities = 1;
 243 #endif
 244         // Signal that a capability is available
 245         if (rts_n_waiting_tasks > 0 && ANY_WORK_TO_DO()) {
 246             signalCondition(&thread_ready_cond);
 247         }
 248         startSchedulerTaskIfNecessary();
 249         IF_DEBUG(scheduler, sched_belch("worker: released capability"));
 250     }
 251 #endif
 252     return;
 253 }
 254
 255 #if defined(RTS_SUPPORTS_THREADS)
 256 /*
 257  * When a native thread has completed the execution of an external
 258  * call, it needs to communicate the result back. This is done
 259  * as follows:
 260  *
 261  *  - in resumeThread(), the thread calls waitForReturnCapability().
 262  *  - If no capabilities are readily available, waitForReturnCapability()
 263  *    increments a counter rts_n_waiting_workers, and blocks
 264  *    waiting for the condition returning_worker_cond to become
 265  *    signalled.
 266  *  - upon entry to the Scheduler, a worker thread checks the
 267  *    value of rts_n_waiting_workers. If > 0, the worker thread
 268  *    will yield its capability to let a returning worker thread
 269  *    proceed with returning its result -- this is done via
 270  *    yieldToReturningWorker().
 271  *  - the worker thread that yielded its capability then tries
 272  *    to re-grab a capability and re-enter the Scheduler.
 273  */
 274
 275 /* ----------------------------------------------------------------------------
 276  * waitForReturnCapability( Mutext *pMutex, Capability** )
 277  *
 278  * Purpose:  when an OS thread returns from an external call,
 279  * it calls grabReturnCapability() (via Schedule.resumeThread())
 280  * to wait for permissions to enter the RTS & communicate the
 281  * result of the external call back to the Haskell thread that
 282  * made it.
 283  *
 284  * ------------------------------------------------------------------------- */
 285
 286 void
 287 waitForReturnCapability( Mutex* pMutex, Capability** pCap )
 288 {
 289     // Pre-condition: pMutex is held.
 290
 291     IF_DEBUG(scheduler,
 292              sched_belch("worker: returning; workers waiting: %d",
 293                          rts_n_waiting_workers));
 294
 295     if ( noCapabilities() || passingCapability ) {
 296         rts_n_waiting_workers++;
 297         context_switch = 1;     // make sure it's our turn soon
 298         waitCondition(&returning_worker_cond, pMutex);
 299 #if defined(SMP)
 300         *pCap = free_capabilities;
 301         free_capabilities = (*pCap)->link;
 302         ASSERT(pCap != NULL);
 303 #else
 304         *pCap = &MainCapability;
 305         ASSERT(rts_n_free_capabilities == 0);
 306 #endif
 307         handleSignalsInThisThread();
 308     } else {
 309         grabCapability(pCap);
 310     }
 311
 312     // Post-condition: pMutex is held, pCap points to a capability
 313     // which is now held by the current thread.
 314     return;
 315 }
 316
 317
 318 /* ----------------------------------------------------------------------------
 319  * yieldCapability( Mutex* pMutex, Capability** pCap )
 320  * ------------------------------------------------------------------------- */
 321
 322 void
 323 yieldCapability( Capability** pCap )
 324 {
 325     // Pre-condition:  pMutex is assumed held, the current thread
 326     // holds the capability pointed to by pCap.
 327
 328     if ( rts_n_waiting_workers > 0 || passingCapability || !ANY_WORK_TO_DO()) {
 329         IF_DEBUG(scheduler,
 330                  if (rts_n_waiting_workers > 0) {
 331                      sched_belch("worker: giving up capability (returning wkr)");
 332                  } else if (passingCapability) {
 333                      sched_belch("worker: giving up capability (passing capability)");
 334                  } else {
 335                      sched_belch("worker: giving up capability (no threads to run)");
 336                  }
 337             );
 338         releaseCapability(*pCap);
 339         *pCap = NULL;
 340     }
 341
 342     // Post-condition:  either:
 343     //
 344     //  1. *pCap is NULL, in which case the current thread does not
 345     //     hold a capability now, or
 346     //  2. *pCap is not NULL, in which case the current thread still
 347     //     holds the capability.
 348     //
 349     return;
 350 }
 351
 352
 353 /* ----------------------------------------------------------------------------
 354  * waitForCapability( Mutex*, Capability**, Condition* )
 355  *
 356  * Purpose:  wait for a Capability to become available. In
 357  *           the process of doing so, updates the number
 358  *           of tasks currently blocked waiting for a capability/more
 359  *           work. That counter is used when deciding whether or
 360  *           not to create a new worker thread when an external
 361  *           call is made.
 362  *           If pThreadCond is not NULL, a capability can be specifically
 363  *           passed to this thread using passCapability.
 364  * ------------------------------------------------------------------------- */
 365
 366 void
 367 waitForCapability( Mutex* pMutex, Capability** pCap, Condition* pThreadCond )
 368 {
 369     // Pre-condition: pMutex is held.
 370
 371     while ( noCapabilities() ||
 372             (passingCapability && passTarget != pThreadCond) ||
 373             !ANY_WORK_TO_DO()) {
 374         IF_DEBUG(scheduler,
 375                  sched_belch("worker: wait for capability (cond: %p)",
 376                              pThreadCond));
 377
 378         if (pThreadCond != NULL) {
 379             waitCondition(pThreadCond, pMutex);
 380             IF_DEBUG(scheduler, sched_belch("worker: get passed capability"));
 381         } else {
 382             rts_n_waiting_tasks++;
 383             waitCondition(&thread_ready_cond, pMutex);
 384             rts_n_waiting_tasks--;
 385             IF_DEBUG(scheduler, sched_belch("worker: get normal capability"));
 386         }
 387     }
 388     passingCapability = rtsFalse;
 389     grabCapability(pCap);
 390
 391     // Post-condition: pMutex is held and *pCap is held by the current thread
 392     return;
 393 }
 394
 395 /* ----------------------------------------------------------------------------
 396    passCapability, passCapabilityToWorker
 397    ------------------------------------------------------------------------- */
 398
 399 void
 400 passCapability( Condition *pTargetThreadCond )
 401 {
 402     // Pre-condition: pMutex is held and cap is held by the current thread
 403
 404     passTarget = pTargetThreadCond;
 405     passingCapability = rtsTrue;
 406     IF_DEBUG(scheduler, sched_belch("worker: passCapability"));
 407
 408     // Post-condition: pMutex is held; cap is still held, but will be
 409     //                 passed to the target thread when next released.
 410 }
 411
 412 void
 413 passCapabilityToWorker( void )
 414 {
 415     // Pre-condition: pMutex is held and cap is held by the current thread
 416
 417     passTarget = NULL;
 418     passingCapability = rtsTrue;
 419     IF_DEBUG(scheduler, sched_belch("worker: passCapabilityToWorker"));
 420
 421     // Post-condition: pMutex is held; cap is still held, but will be
 422     //                 passed to a worker thread when next released.
 423 }
 424
 425 #endif /* RTS_SUPPORTS_THREADS */
 426
 427 /* ----------------------------------------------------------------------------
 428    threadRunnable()
 429
 430    Signals that a thread has been placed on the run queue, so a worker
 431    might need to be woken up to run it.
 432
 433    ToDo: should check whether the thread at the front of the queue is
 434    bound, and if so wake up the appropriate worker.
 435    -------------------------------------------------------------------------- */
 436
 437 void
 438 threadRunnable ( void )
 439 {
 440 #if defined(RTS_SUPPORTS_THREADS)
 441     if ( !noCapabilities() && ANY_WORK_TO_DO() && rts_n_waiting_tasks > 0 ) {
 442         signalCondition(&thread_ready_cond);
 443     }
 444     startSchedulerTaskIfNecessary();
 445 #endif
 446 }