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