libcilkrts/runtime/scheduler.h

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