ghc/rts/Capability.c

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