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
  25 #if !defined(SMP)
  26 Capability MainCapability;     /* for non-SMP, we have one global capability */
  27 #endif
  28
  29 nat rts_n_free_capabilities;
  30
  31 #if defined(RTS_SUPPORTS_THREADS)
  32 /* returning_worker_cond: when a worker thread returns from executing an
  33  * external call, it needs to wait for an RTS Capability before passing
  34  * on the result of the call to the Haskell thread that made it.
  35  *
  36  * returning_worker_cond is signalled in Capability.releaseCapability().
  37  *
  38  */
  39 Condition returning_worker_cond = INIT_COND_VAR;
  40
  41 /*
  42  * To avoid starvation of threads blocked on worker_thread_cond,
  43  * the task(s) that enter the Scheduler will check to see whether
  44  * there are one or more worker threads blocked waiting on
  45  * returning_worker_cond.
  46  */
  47 static nat rts_n_waiting_workers = 0;
  48
  49 /* thread_ready_cond: when signalled, a thread has become runnable for a
  50  * task to execute.
  51  *
  52  * In the non-SMP case, it also implies that the thread that is woken up has
  53  * exclusive access to the RTS and all its data structures (that are not
  54  * locked by the Scheduler's mutex).
  55  *
  56  * thread_ready_cond is signalled whenever COND_NO_THREADS_READY doesn't hold.
  57  *
  58  */
  59 Condition thread_ready_cond = INIT_COND_VAR;
  60 #if 0
  61 /* For documentation purposes only */
  62 #define COND_NO_THREADS_READY() (noCapabilities() || EMPTY_RUN_QUEUE())
  63 #endif
  64
  65 /*
  66  * To be able to make an informed decision about whether or not
  67  * to create a new task when making an external call, keep track of
  68  * the number of tasks currently blocked waiting on thread_ready_cond.
  69  * (if > 0 => no need for a new task, just unblock an existing one).
  70  *
  71  * waitForWorkCapability() takes care of keeping it up-to-date;
  72  * Task.startTask() uses its current value.
  73  */
  74 nat rts_n_waiting_tasks = 0;
  75 #endif
  76
  77 /* -----------------------------------------------------------------------------
  78    Initialisation
  79    -------------------------------------------------------------------------- */
  80 static
  81 void
  82 initCapability( Capability *cap )
  83 {
  84     cap->f.stgChk0         = (F_)__stg_chk_0;
  85     cap->f.stgChk1         = (F_)__stg_chk_1;
  86     cap->f.stgGCEnter1     = (F_)__stg_gc_enter_1;
  87     cap->f.stgUpdatePAP    = (F_)__stg_update_PAP;
  88 }
  89
  90 #if defined(SMP)
  91 static void initCapabilities_(nat n);
  92 #endif
  93
  94 /*
  95  * Function:  initCapabilities()
  96  *
  97  * Purpose:   set up the Capability handling. For the SMP build,
  98  *            we keep a table of them, the size of which is
  99  *            controlled by the user via the RTS flag RtsFlags.ParFlags.nNodes
 100  *
 101  * Pre-conditions: no locks assumed held.
 102  */
 103 void
 104 initCapabilities()
 105 {
 106 #if defined(RTS_SUPPORTS_THREADS)
 107   initCondition(&returning_worker_cond);
 108   initCondition(&thread_ready_cond);
 109 #endif
 110
 111 #if defined(SMP)
 112   initCapabilities_(RtsFlags.ParFlags.nNodes);
 113 #else
 114   initCapability(&MainCapability);
 115   rts_n_free_capabilities = 1;
 116 #endif
 117
 118   return;
 119 }
 120
 121 #if defined(SMP)
 122 /* Free capability list. */
 123 static Capability *free_capabilities; /* Available capabilities for running 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   rts_n_free_capabilities = 0;
 145   *cap = &MainCapability;
 146 #else
 147   *cap = free_capabilities;
 148   free_capabilities = (*cap)->link;
 149   rts_n_free_capabilities--;
 150 #endif
 151 }
 152
 153 /*
 154  * Function:  releaseCapability(Capability*)
 155  *
 156  * Purpose:   Letting go of a capability. Causes a
 157  *            'returning worker' thread or a 'waiting worker'
 158  *            to wake up, in that order.
 159  *
 160  */
 161 void releaseCapability(Capability* cap
 162 #if !defined(SMP)
 163                        STG_UNUSED
 164 #endif
 165 )
 166 {
 167 #if defined(SMP)
 168   cap->link = free_capabilities;
 169   free_capabilities = cap;
 170   rts_n_free_capabilities++;
 171 #else
 172   rts_n_free_capabilities = 1;
 173 #endif
 174
 175 #if defined(RTS_SUPPORTS_THREADS)
 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     rts_n_waiting_workers--;
 184     signalCondition(&returning_worker_cond);
 185   } else if ( !EMPTY_RUN_QUEUE() ) {
 186     /* Signal that work is available */
 187     signalCondition(&thread_ready_cond);
 188   }
 189 #endif
 190   return;
 191 }
 192
 193 #if defined(RTS_SUPPORTS_THREADS)
 194 /*
 195  * When a native thread has completed the execution of an external
 196  * call, it needs to communicate the result back. This is done
 197  * as follows:
 198  *
 199  *  - in resumeThread(), the thread calls grabReturnCapability().
 200  *  - If no capabilities are readily available, grabReturnCapability()
 201  *    increments a counter rts_n_waiting_workers, and blocks
 202  *    waiting for the condition returning_worker_cond to become
 203  *    signalled.
 204  *  - upon entry to the Scheduler, a worker thread checks the
 205  *    value of rts_n_waiting_workers. If > 0, the worker thread
 206  *    will yield its capability to let a returning worker thread
 207  *    proceed with returning its result -- this is done via
 208  *    yieldToReturningWorker().
 209  *  - the worker thread that yielded its capability then tries
 210  *    to re-grab a capability and re-enter the Scheduler.
 211  */
 212
 213 /*
 214  * Function: grabReturnCapability(Capability**)
 215  *
 216  * Purpose:  when an OS thread returns from an external call,
 217  * it calls grabReturnCapability() (via Schedule.resumeThread())
 218  * to wait for permissions to enter the RTS & communicate the
 219  * result of the external call back to the Haskell thread that
 220  * made it.
 221  *
 222  * Pre-condition:  pMutex is held.
 223  * Post-condition: pMutex is still held and a capability has
 224  *                 been assigned to the worker thread.
 225  */
 226 void
 227 grabReturnCapability(Mutex* pMutex, Capability** pCap)
 228 {
 229   IF_DEBUG(scheduler,
 230            fprintf(stderr,"worker (%ld): returning, waiting for lock.\n", osThreadId()));
 231   rts_n_waiting_workers++;
 232   IF_DEBUG(scheduler,
 233            fprintf(stderr,"worker (%ld): returning; workers waiting: %d\n",
 234                    osThreadId(), rts_n_waiting_workers));
 235   while ( noCapabilities() ) {
 236     waitCondition(&returning_worker_cond, pMutex);
 237   }
 238
 239   grabCapability(pCap);
 240   return;
 241 }
 242
 243
 244 /* -----------------------------------------------------------------------------
 245    Yielding/waiting for capabilities
 246    -------------------------------------------------------------------------- */
 247
 248 /*
 249  * Function: yieldToReturningWorker(Mutex*,Capability*)
 250  *
 251  * Purpose:  when, upon entry to the Scheduler, an OS worker thread
 252  *           spots that one or more threads are blocked waiting for
 253  *           permission to return back their result, it gives up
 254  *           its Capability.
 255  *
 256  * Pre-condition:  pMutex is assumed held and the thread possesses
 257  *                 a Capability.
 258  * Post-condition: pMutex isn't held and the Capability has
 259  *                 been given back.
 260  */
 261 void
 262 yieldToReturningWorker(Mutex* pMutex, Capability* cap)
 263 {
 264   if ( rts_n_waiting_workers > 0 && noCapabilities() ) {
 265     IF_DEBUG(scheduler,
 266              fprintf(stderr,"worker thread (%ld): giving up RTS token\n", osThreadId()));
 267     releaseCapability(cap);
 268     RELEASE_LOCK(pMutex);
 269     yieldThread();
 270     /* At this point, pMutex has been given up & we've
 271      * forced a thread context switch. Guaranteed to be
 272      * enough for the signalled worker thread to race
 273      * ahead of us?
 274      */
 275
 276     /* Re-grab the mutex */
 277     ACQUIRE_LOCK(pMutex);
 278     /* And wait for work */
 279     waitForWorkCapability(pMutex, cap, rtsFalse);
 280   }
 281   return;
 282 }
 283
 284
 285 /*
 286  * Function: waitForWorkCapability(Mutex*, Capability**, rtsBool)
 287  *
 288  * Purpose:  wait for a Capability to become available. In
 289  *           the process of doing so, updates the number
 290  *           of tasks currently blocked waiting for a capability/more
 291  *           work. That counter is used when deciding whether or
 292  *           not to create a new worker thread when an external
 293  *           call is made.
 294  *
 295  * Pre-condition: pMutex is held.
 296  */
 297 void
 298 waitForWorkCapability(Mutex* pMutex, Capability** pCap, rtsBool runnable)
 299 {
 300   while ( noCapabilities() || (runnable && EMPTY_RUN_QUEUE()) ) {
 301     rts_n_waiting_tasks++;
 302     waitCondition(&thread_ready_cond, pMutex);
 303     rts_n_waiting_tasks--;
 304   }
 305   grabCapability(pCap);
 306   return;
 307 }
 308 #endif /* RTS_SUPPORTS_THREADS */
 309
 310 #if defined(SMP)
 311 /*
 312  * Function: initCapabilities_(nat)
 313  *
 314  * Purpose:  upon startup, allocate and fill in table
 315  *           holding 'n' Capabilities. Only for SMP, since
 316  *           it is the only build that supports multiple
 317  *           capabilities within the RTS.
 318  */
 319 static void
 320 initCapabilities_(nat n)
 321 {
 322   nat i;
 323   Capability *cap, *prev;
 324   cap  = NULL;
 325   prev = NULL;
 326   for (i = 0; i < n; i++) {
 327     cap = stgMallocBytes(sizeof(Capability), "initCapabilities");
 328     initCapability(cap);
 329     cap->link = prev;
 330     prev = cap;
 331   }
 332   free_capabilities = cap;
 333   rts_n_free_capabilities = n;
 334   IF_DEBUG(scheduler,fprintf(stderr,"scheduler: Allocated %d capabilities\n", n_free_capabilities););
 335 }
 336 #endif /* SMP */
 337