libcilkrts/runtime/scheduler.h

   1 /* scheduler.h                  -*-C++-*-
   2  *
   3  *************************************************************************
   4  *
   5  *  @copyright
   6  *  Copyright (C) 2009-2013, Intel Corporation
   7  *  All rights reserved.
   8  *
   9  *  @copyright
  10  *  Redistribution and use in source and binary forms, with or without
  11  *  modification, are permitted provided that the following conditions
  12  *  are met:
  13  *
  14  *    * Redistributions of source code must retain the above copyright
  15  *      notice, this list of conditions and the following disclaimer.
  16  *    * Redistributions in binary form must reproduce the above copyright
  17  *      notice, this list of conditions and the following disclaimer in
  18  *      the documentation and/or other materials provided with the
  19  *      distribution.
  20  *    * Neither the name of Intel Corporation nor the names of its
  21  *      contributors may be used to endorse or promote products derived
  22  *      from this software without specific prior written permission.
  23  *
  24  *  @copyright
  25  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  *  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  30  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  31  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  32  *  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  33  *  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
  35  *  WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  36  *  POSSIBILITY OF SUCH DAMAGE.
  37  **************************************************************************/
  38
  39 /**
  40  * @file scheduler.h
  41  *
  42  * @brief scheduler.h declares routines for the Intel Cilk Plus scheduler,
  43  * making it the heart of the Intel Cilk Plus implementation.
  44  */
  45
  46 #ifndef INCLUDED_SCHEDULER_DOT_H
  47 #define INCLUDED_SCHEDULER_DOT_H
  48
  49 #include <cilk/common.h>
  50 #include <internal/abi.h>
  51
  52 #include "rts-common.h"
  53 #include "full_frame.h"
  54 #include "reducer_impl.h"
  55 #include "global_state.h"
  56
  57 #ifdef CILK_RECORD_REPLAY
  58 #include "record-replay.h"
  59 #endif
  60
  61 __CILKRTS_BEGIN_EXTERN_C
  62
  63
  64 /**
  65  * @brief Flag to disable parallel reductions.
  66  *
  67  * Set to 0 to allow parallel reductions.
  68  */
  69 #define DISABLE_PARALLEL_REDUCERS 0
  70
  71 /**
  72  * @brief Debugging level for parallel reductions.
  73  *
  74  * Print debugging messages and assertions for parallel reducers. 0 is
  75  * no debugging.  A higher value generates more output.
  76  */
  77 #define REDPAR_DEBUG 0
  78
  79 /**
  80  * @brief Lock the worker mutex to allow exclusive access to the
  81  * values in the @c __cilkrts_worker and local_state structures.
  82  *
  83  * @pre @c w->l->do_not_steal must not be set.  Essentially this
  84  * condition asserts that the worker is not locked recursively.
  85  *
  86  * @param w The worker to lock.
  87  */
  88 COMMON_PORTABLE
  89 void __cilkrts_worker_lock(__cilkrts_worker *w);
  90
  91 /**
  92  * @brief Unlock the worker mutex.
  93  *
  94  * @pre @c w->l->do_not_steal must be set.  Essentially this condition
  95  * asserts that the worker has been previously locked.
  96  *
  97  * @param w The worker to unlock.
  98  */
  99 COMMON_PORTABLE
 100 void __cilkrts_worker_unlock(__cilkrts_worker *w);
 101
 102 /**
 103  * @brief Push the next full frame to be made active in this worker
 104  * and increment its join counter.
 105  *
 106  * __cilkrts_push_next_frame and pop_next_frame work on a one-element queue.
 107  * This queue is used to communicate across the runtime from the code that
 108  * wants to activate a frame to the code that can actually begin execution
 109  * on that frame.  They are asymetrical in that push increments the join
 110  * counter but pop does not decrement it.  Rather, a single push/pop
 111  * combination makes a frame active and increments its join counter once.
 112  *
 113  * @note A system worker may chose to push work onto a user worker if
 114  * the work is the continuation from a sync which only the user worker
 115  * may complete.
 116  *
 117  * @param w The worker which the frame is to be pushed onto.
 118  * @param ff The full_frame which is to be continued by the worker.
 119  */
 120 COMMON_PORTABLE
 121 void __cilkrts_push_next_frame(__cilkrts_worker *w,
 122                                full_frame *ff);
 123
 124 /**
 125  * @brief Sync on this worker.
 126  *
 127  * If this worker is the last to reach the sync, execution may resume
 128  * on this worker after the sync.
 129  *
 130  * If this worker is not the last spawned child to reach the sync,
 131  * then execution is suspended and the worker will re-enter the
 132  * scheduling loop, looking for work it can steal.
 133  *
 134  * This function will jump into the runtime to switch to the scheduling
 135  * stack to implement most of its logic.
 136  *
 137  * @param w The worker which is executing the sync.
 138  * @param sf The __cilkrts_stack_frame containing the sync.
 139  */
 140 COMMON_PORTABLE
 141 NORETURN __cilkrts_c_sync(__cilkrts_worker *w,
 142                           __cilkrts_stack_frame *sf);
 143
 144 /**
 145  * @brief Worker @c w completely promotes its own deque, simulating the case
 146  * where the whole deque is stolen.
 147  *
 148  * We use this mechanism to force the allocation of new storage for
 149  * reducers for race-detection purposes.
 150  *
 151  * This method is called from the reducer lookup logic when
 152  * @c g->force_reduce is set.
 153  *
 154  * @warning Use of "force_reduce" is known to have bugs when run with
 155  * more than 1 worker.
 156  *
 157  * @param w The worker which is to have all entries in its deque
 158  * promoted to full frames.
 159  */
 160 COMMON_PORTABLE
 161 void __cilkrts_promote_own_deque(__cilkrts_worker *w);
 162
 163 /**
 164  * Called when a spawned function attempts to return and
 165  * __cilkrts_undo_detach() fails. This can happen for two reasons:
 166  *
 167  * @li If another worker is considering stealing our parent, it bumps the
 168  * exception pointer while it did so, which will cause __cilkrts_undo_detach()
 169  * to fail. If the other worker didn't complete the steal of our parent, we
 170  * still may be able to return to it, either because the steal attempt failed,
 171  * or we won the race for the tail pointer.
 172  *
 173  * @li If the function's parent has been stolen then we cannot return. Instead
 174  * we'll longjmp into the runtime to switch onto the scheduling stack to
 175  * execute do_return_from_spawn() and determine what to do.  Either this
 176  * worker is the last one to the sync, in which case we need to jump to the
 177  * sync, or this worker is not the last one to the sync, in which case we'll
 178  * abandon this work and jump to the scheduling loop to search for more work
 179  * we can steal.
 180  *
 181  * @param w The worker which attempting to return from a spawn to
 182  * a stolen parent.
 183  * @param returning_sf The stack frame which is returning.
 184  */
 185 COMMON_PORTABLE
 186 void __cilkrts_c_THE_exception_check(__cilkrts_worker *w,
 187                                      __cilkrts_stack_frame *returning_sf);
 188
 189 /**
 190  * @brief Return an exception to an stolen parent.
 191  *
 192  * Used by the gcc implementation of exceptions to return an exception
 193  * to a stolen parent
 194  *
 195  * @param w The worker which attempting to return from a spawn with an
 196  * exception to a stolen parent.
 197  * @param returning_sf The stack frame which is returning.
 198  */
 199 COMMON_PORTABLE
 200 NORETURN __cilkrts_exception_from_spawn(__cilkrts_worker *w,
 201                                         __cilkrts_stack_frame *returning_sf);
 202
 203 /**
 204  * @brief Used by the Windows implementations of exceptions to migrate an exception
 205  * across fibers.
 206  *
 207  * Call this function when an exception has been thrown and has to
 208  * traverse across a steal.  The exception has already been wrapped
 209  * up, so all that remains is to longjmp() into the continuation,
 210  * sync, and re-raise it.
 211  *
 212  * @param sf The __cilkrts_stack_frame for the frame that is attempting to
 213  * return an exception to a stolen parent.
 214  */
 215 void __cilkrts_migrate_exception (__cilkrts_stack_frame *sf);
 216
 217 /**
 218  * @brief Return from a call, not a spawn, where this frame has ever
 219  * been stolen.
 220  *
 221  * @param w The worker that is returning from a frame which was ever stolen.
 222  */
 223 COMMON_PORTABLE
 224 void __cilkrts_return(__cilkrts_worker *w);
 225
 226 /**
 227  * @brief Special return from the initial frame.
 228  *
 229  * This method will be called from @c __cilkrts_leave_frame if
 230  * @c CILK_FRAME_LAST is set.
 231  *
 232  * This function will do the things necessary to cleanup, and unbind the
 233  * thread from the Intel Cilk Plus runtime.  If this is the last user
 234  * worker unbinding from the runtime, all system worker threads will be
 235  * suspended.
 236  *
 237  * @pre @c w must be the currently executing worker, and must be a user
 238  * worker.
 239  *
 240  * @param w The worker that's returning from the initial frame.
 241  */
 242 COMMON_PORTABLE
 243 void __cilkrts_c_return_from_initial(__cilkrts_worker *w);
 244
 245 /**
 246  * @brief Used by exception handling code to pop an entry from the
 247  * worker's deque.
 248  *
 249  * @param w Worker to pop the entry from
 250  *
 251  * @return __cilkrts_stack_frame of parent call
 252  * @return NULL if the deque is empty
 253  */
 254 COMMON_PORTABLE
 255 __cilkrts_stack_frame *__cilkrts_pop_tail(__cilkrts_worker *w);
 256
 257 /**
 258  * @brief Modifies the worker's protected_tail to prevent frames from
 259  * being stolen.
 260  *
 261  * The Dekker protocol has been extended to only steal if head+1 is also
 262  * less than protected_tail.
 263  *
 264  * @param w The worker to be modified.
 265  * @param new_protected_tail The new setting for protected_tail, or NULL if the
 266  * entire deque is to be protected
 267  *
 268  * @return Previous value of protected tail.
 269  */
 270 COMMON_PORTABLE
 271 __cilkrts_stack_frame *volatile *__cilkrts_disallow_stealing(
 272     __cilkrts_worker *w,
 273     __cilkrts_stack_frame *volatile *new_protected_tail);
 274
 275 /**
 276  * @brief Restores the protected tail to a previous state, possibly
 277  * allowing frames to be stolen.
 278  *
 279  * @param w The worker to be modified.
 280  * @param saved_protected_tail A previous setting for protected_tail that is
 281  * to be restored
 282  */
 283 COMMON_PORTABLE
 284 void __cilkrts_restore_stealing(
 285     __cilkrts_worker *w,
 286     __cilkrts_stack_frame *volatile *saved_protected_tail);
 287
 288 /**
 289  * @brief Initialize a @c __cilkrts_worker.
 290  *
 291  * @note The memory for the worker must have been allocated outside
 292  * this call.
 293  *
 294  * @param g The global_state_t.
 295  * @param self The index into the global_state's array of workers for this
 296  * worker, or -1 if this worker was allocated from the heap and cannot be
 297  * stolen from.
 298  * @param w The worker to be initialized.
 299  *
 300  * @return The initialized __cilkrts_worker.
 301  */
 302 COMMON_PORTABLE
 303 __cilkrts_worker *make_worker(global_state_t *g,
 304                               int self,
 305                               __cilkrts_worker *w);
 306
 307 /**
 308  * @brief Free up any resources allocated for a worker.
 309  *
 310  * @note The memory for the @c __cilkrts_worker itself must be
 311  * deallocated outside this call.
 312  *
 313  * @param w The worker to be destroyed.
 314  */
 315 COMMON_PORTABLE
 316 void destroy_worker (__cilkrts_worker *w);
 317
 318 /**
 319  * @brief Initialize the runtime.
 320  *
 321  * If necessary, allocates and initializes the global state.  If
 322  * necessary, unsuspends the system workers.
 323  *
 324  * @param start Specifies whether the workers are to be unsuspended if
 325  * they are suspended.  Allows __cilkrts_init() to start up the runtime without
 326  * releasing the system threads.
 327  */
 328 COMMON_PORTABLE
 329 void __cilkrts_init_internal(int start);
 330
 331 /**
 332  * @brief Part of the sequence to shutdown the runtime.
 333  *
 334  * Specifically, this call frees the @c global_state_t for the runtime.
 335  *
 336  * @param g The global_state_t.
 337  */
 338 COMMON_PORTABLE
 339 void __cilkrts_deinit_internal(global_state_t *g);
 340
 341 /**
 342  * Obsolete.  We no longer need to import or export reducer maps.
 343  */
 344 COMMON_PORTABLE
 345 cilkred_map *__cilkrts_xchg_reducer(
 346     __cilkrts_worker *w, cilkred_map *newmap) cilk_nothrow;
 347
 348 /**
 349  * @brief Called when a user thread is bound to the runtime.
 350  *
 351  * If this action increments the count of bound user threads from 0 to
 352  * 1, the system worker threads are unsuspended.
 353  *
 354  * If this action increments the count of bound user threads from 0 to
 355  * 1, the system worker threads are unsuspended.
 356  *
 357  * @pre Global lock must be held.
 358  * @param g The runtime global state.
 359  */
 360 COMMON_PORTABLE
 361 void __cilkrts_enter_cilk(global_state_t *g);
 362
 363 /**
 364  * @brief Called when a user thread is unbound from the runtime.
 365  *
 366  * If this action decrements the count of bound user threads to 0, the
 367  * system worker threads are suspended.
 368  *
 369  *
 370  * @pre  Global lock must be held.
 371  *
 372  * @param g The runtime global state.
 373  */
 374 COMMON_PORTABLE
 375 void __cilkrts_leave_cilk(global_state_t *g);
 376
 377
 378 /**
 379  * @brief cilk_fiber_proc that runs the main scheduler loop on a
 380  * user worker.
 381  *
 382  * @pre  fiber's owner field should be set to the correct __cilkrts_worker
 383  * @pre  fiber must be a user worker.
 384  *
 385  * @param fiber    The scheduling fiber object.
 386  */
 387 void scheduler_fiber_proc_for_user_worker(cilk_fiber *fiber);
 388
 389
 390 /**
 391  * @brief Prints out Cilk runtime statistics.
 392  *
 393  * @param g The runtime global state.
 394  *
 395  * This method is useful only for debugging purposes.  No guarantees
 396  * are made as to the validity of this data. :)
 397  */
 398 COMMON_PORTABLE
 399 void __cilkrts_dump_stats_to_stderr(global_state_t *g);
 400
 401 #ifdef CILK_RECORD_REPLAY
 402 COMMON_PORTABLE
 403 char * walk_pedigree_nodes(char *p, const __cilkrts_pedigree *pnode);
 404
 405 /**
 406  * @brief Used by exception handling code to simulate the popping of
 407  * an entry from the worker's deque.
 408  *
 409  * @param w Worker whose deque we want to check
 410  *
 411  * @return @c __cilkrts_stack_frame of parent call
 412  * @return NULL if the deque is empty
 413  */
 414 COMMON_PORTABLE
 415 __cilkrts_stack_frame *simulate_pop_tail(__cilkrts_worker *w);
 416
 417 #endif
 418
 419 __CILKRTS_END_EXTERN_C
 420
 421 #endif // ! defined(INCLUDED_SCHEDULER_DOT_H)