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) 422