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