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 #endif
  73
  74 /* -----------------------------------------------------------------------------
  75    Initialisation
  76    -------------------------------------------------------------------------- */
  77 static
  78 void
  79 initCapability( Capability *cap )
  80 {
  81     cap->f.stgGCEnter1     = (F_)__stg_gc_enter_1;
  82     cap->f.stgGCFun        = (F_)__stg_gc_fun;
  83 }
  84
  85 #if defined(SMP)
  86 static void initCapabilities_(nat n);
  87 #endif
  88
  89 /*
  90  * Function:  initCapabilities()
  91  *
  92  * Purpose:   set up the Capability handling. For the SMP build,
  93  *            we keep a table of them, the size of which is
  94  *            controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
  95  *
  96  * Pre-conditions: no locks assumed held.
  97  */
  98 void
  99 initCapabilities()
 100 {
 101 #if defined(RTS_SUPPORTS_THREADS)
 102   initCondition(&returning_worker_cond);
 103   initCondition(&thread_ready_cond);
 104 #endif
 105
 106 #if defined(SMP)
 107   initCapabilities_(RtsFlags.ParFlags.nNodes);
 108 #else
 109   initCapability(&MainCapability);
 110   rts_n_free_capabilities = 1;
 111 #endif
 112
 113   return;
 114 }
 115
 116 #if defined(SMP)
 117 /* Free capability list. */
 118 static Capability *free_capabilities; /* Available capabilities for running threads */
 119 static Capability *returning_capabilities;
 120         /* Capabilities being passed to returning worker threads */
 121 #endif
 122
 123 /* -----------------------------------------------------------------------------
 124    Acquiring capabilities
 125    -------------------------------------------------------------------------- */
 126
 127 /*
 128  * Function:  grabCapability(Capability**)
 129  *
 130  * Purpose:   the act of grabbing a capability is easy; just
 131  *            remove one from the free capabilities list (which
 132  *            may just have one entry). In threaded builds, worker
 133  *            threads are prevented from doing so willy-nilly
 134  *            via the condition variables thread_ready_cond and
 135  *            returning_worker_cond.
 136  *
 137  */
 138 void grabCapability(Capability** cap)
 139 {
 140 #ifdef RTS_SUPPORTS_THREADS
 141   ASSERT(rts_n_free_capabilities > 0);
 142 #endif
 143 #if !defined(SMP)
 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 #ifdef RTS_SUPPORTS_THREADS
 153   IF_DEBUG(scheduler,
 154            fprintf(stderr,"worker thread (%p): got capability\n",
 155                    osThreadId()));
 156 #endif
 157 }
 158
 159 /*
 160  * Function:  releaseCapability(Capability*)
 161  *
 162  * Purpose:   Letting go of a capability. Causes a
 163  *            'returning worker' thread or a 'waiting worker'
 164  *            to wake up, in that order.
 165  *
 166  */
 167 void releaseCapability(Capability* cap
 168 #if !defined(SMP)
 169                        STG_UNUSED
 170 #endif
 171 )
 172 {       // Precondition: sched_mutex must be held
 173 #if defined(RTS_SUPPORTS_THREADS)
 174 #ifndef SMP
 175   ASSERT(rts_n_free_capabilities == 0);
 176 #endif
 177   /* Check to see whether a worker thread can be given
 178      the go-ahead to return the result of an external call..*/
 179   if (rts_n_waiting_workers > 0) {
 180     /* Decrement the counter here to avoid livelock where the
 181      * thread that is yielding its capability will repeatedly
 182      * signal returning_worker_cond.
 183      */
 184 #if defined(SMP)
 185         // SMP variant untested
 186     cap->link = returning_capabilities;
 187     returning_capabilities = cap;
 188 #else
 189 #endif
 190     rts_n_waiting_workers--;
 191     signalCondition(&returning_worker_cond);
 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,
 208            fprintf(stderr,"worker thread (%p): released capability\n",
 209                    osThreadId()));
 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 grabReturnCapability().
 221  *  - If no capabilities are readily available, grabReturnCapability()
 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  * Function: grabReturnCapability(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  * Pre-condition:  pMutex is held.
 244  * Post-condition: pMutex is still held and a capability has
 245  *                 been assigned to the worker thread.
 246  */
 247 void
 248 grabReturnCapability(Mutex* pMutex, Capability** pCap)
 249 {
 250   IF_DEBUG(scheduler,
 251            fprintf(stderr,"worker (%p): returning, waiting for lock.\n", osThreadId()));
 252   IF_DEBUG(scheduler,
 253            fprintf(stderr,"worker (%p): returning; workers waiting: %d\n",
 254                    osThreadId(), rts_n_waiting_workers));
 255   if ( noCapabilities() ) {
 256     rts_n_waiting_workers++;
 257     wakeBlockedWorkerThread();
 258     context_switch = 1; // make sure it's our turn soon
 259     waitCondition(&returning_worker_cond, pMutex);
 260 #if defined(SMP)
 261     *pCap = returning_capabilities;
 262     returning_capabilities = (*pCap)->link;
 263 #else
 264     *pCap = &MainCapability;
 265     ASSERT(rts_n_free_capabilities == 0);
 266     handleSignalsInThisThread();
 267 #endif
 268   } else {
 269     grabCapability(pCap);
 270   }
 271   return;
 272 }
 273
 274
 275 /* -----------------------------------------------------------------------------
 276    Yielding/waiting for capabilities
 277    -------------------------------------------------------------------------- */
 278
 279 /*
 280  * Function: yieldToReturningWorker(Mutex*,Capability*,Condition*)
 281  *
 282  * Purpose:  when, upon entry to the Scheduler, an OS worker thread
 283  *           spots that one or more threads are blocked waiting for
 284  *           permission to return back their result, it gives up
 285  *           its Capability.
 286  *           Immediately afterwards, it tries to reaquire the Capabilty
 287  *           using waitForWorkCapability.
 288  *
 289  *
 290  * Pre-condition:  pMutex is assumed held and the thread possesses
 291  *                 a Capability.
 292  * Post-condition: pMutex is held and the thread possesses
 293  *                 a Capability.
 294  */
 295 void
 296 yieldToReturningWorker(Mutex* pMutex, Capability** pCap, Condition* pThreadCond)
 297 {
 298   if ( rts_n_waiting_workers > 0 ) {
 299     IF_DEBUG(scheduler,
 300              fprintf(stderr,"worker thread (%p): giving up RTS token\n", osThreadId()));
 301     releaseCapability(*pCap);
 302         /* And wait for work */
 303     waitForWorkCapability(pMutex, pCap, pThreadCond);
 304     IF_DEBUG(scheduler,
 305              fprintf(stderr,"worker thread (%p): got back RTS token (after yieldToReturningWorker)\n",
 306                 osThreadId()));
 307   }
 308   return;
 309 }
 310
 311
 312 /*
 313  * Function: waitForWorkCapability(Mutex*, Capability**, Condition*)
 314  *
 315  * Purpose:  wait for a Capability to become available. In
 316  *           the process of doing so, updates the number
 317  *           of tasks currently blocked waiting for a capability/more
 318  *           work. That counter is used when deciding whether or
 319  *           not to create a new worker thread when an external
 320  *           call is made.
 321  *           If pThreadCond is not NULL, a capability can be specifically
 322  *           passed to this thread using passCapability.
 323  *
 324  * Pre-condition: pMutex is held.
 325  * Post-condition: pMutex is held and *pCap is held by the current thread
 326  */
 327
 328 static Condition *passTarget = NULL;
 329 static rtsBool passingCapability = rtsFalse;
 330
 331 void
 332 waitForWorkCapability(Mutex* pMutex, Capability** pCap, Condition* pThreadCond)
 333 {
 334 #ifdef SMP
 335   #error SMP version not implemented
 336 #endif
 337   IF_DEBUG(scheduler,
 338            fprintf(stderr,"worker thread (%p): wait for cap (cond: %p)\n",
 339               osThreadId(),pThreadCond));
 340   while ( noCapabilities() || (passingCapability && passTarget != pThreadCond)) {
 341     if(pThreadCond)
 342     {
 343       waitCondition(pThreadCond, pMutex);
 344       IF_DEBUG(scheduler,
 345                fprintf(stderr,"worker thread (%p): get passed capability\n",
 346                   osThreadId()));
 347     }
 348     else
 349     {
 350       rts_n_waiting_tasks++;
 351       waitCondition(&thread_ready_cond, pMutex);
 352       rts_n_waiting_tasks--;
 353       IF_DEBUG(scheduler,
 354                fprintf(stderr,"worker thread (%p): get normal capability\n",
 355                   osThreadId()));
 356     }
 357   }
 358   passingCapability = rtsFalse;
 359   grabCapability(pCap);
 360   return;
 361 }
 362
 363 /*
 364  * Function: passCapability(Mutex*, Capability*, Condition*)
 365  *
 366  * Purpose:  Let go of the capability and make sure the thread associated
 367  *           with the Condition pTargetThreadCond gets it next.
 368  *
 369  * Pre-condition: pMutex is held and cap is held by the current thread
 370  * Post-condition: pMutex is held; cap will be grabbed by the "target"
 371  *                 thread when pMutex is released.
 372  */
 373
 374 void
 375 passCapability(Mutex* pMutex, Capability* cap, Condition *pTargetThreadCond)
 376 {
 377 #ifdef SMP
 378   #error SMP version not implemented
 379 #endif
 380     rts_n_free_capabilities = 1;
 381     signalCondition(pTargetThreadCond);
 382     passTarget = pTargetThreadCond;
 383         passingCapability = rtsTrue;
 384     IF_DEBUG(scheduler,
 385              fprintf(stderr,"worker thread (%p): passCapability\n",
 386                 osThreadId()));
 387 }
 388
 389 /*
 390  * Function: passCapabilityToWorker(Mutex*, Capability*)
 391  *
 392  * Purpose:  Let go of the capability and make sure that a
 393  *           "plain" worker thread (not a bound thread) gets it next.
 394  *
 395  * Pre-condition: pMutex is held and cap is held by the current thread
 396  * Post-condition: pMutex is held; cap will be grabbed by the "target"
 397  *                 thread when pMutex is released.
 398  */
 399
 400 void
 401 passCapabilityToWorker(Mutex* pMutex, Capability* cap)
 402 {
 403 #ifdef SMP
 404   #error SMP version not implemented
 405 #endif
 406     rts_n_free_capabilities = 1;
 407     signalCondition(&thread_ready_cond);
 408     startSchedulerTaskIfNecessary();
 409     passTarget = NULL;
 410     passingCapability = rtsTrue;
 411     IF_DEBUG(scheduler,
 412              fprintf(stderr,"worker thread (%p): passCapabilityToWorker\n",
 413                 osThreadId()));
 414 }
 415
 416
 417
 418 #endif /* RTS_SUPPORTS_THREADS */
 419
 420 #if defined(SMP)
 421 /*
 422  * Function: initCapabilities_(nat)
 423  *
 424  * Purpose:  upon startup, allocate and fill in table
 425  *           holding 'n' Capabilities. Only for SMP, since
 426  *           it is the only build that supports multiple
 427  *           capabilities within the RTS.
 428  */
 429 static void
 430 initCapabilities_(nat n)
 431 {
 432   nat i;
 433   Capability *cap, *prev;
 434   cap  = NULL;
 435   prev = NULL;
 436   for (i = 0; i < n; i++) {
 437     cap = stgMallocBytes(sizeof(Capability), "initCapabilities");
 438     initCapability(cap);
 439     cap->link = prev;
 440     prev = cap;
 441   }
 442   free_capabilities = cap;
 443   rts_n_free_capabilities = n;
 444   returning_capabilities = NULL;
 445   IF_DEBUG(scheduler,fprintf(stderr,"scheduler: Allocated %d capabilities\n", n_free_capabilities););
 446 }
 447 #endif /* SMP */
 448