libcilkrts/runtime/full_frame.h

   1 /* full_frame.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 #ifndef INCLUDED_FULL_FRAME_DOT_H
  40 #define INCLUDED_FULL_FRAME_DOT_H
  41
  42
  43 #include "rts-common.h"
  44 #include "worker_mutex.h"
  45
  46 #include <cilk/common.h>
  47 #include <internal/abi.h>
  48 #include <stddef.h>
  49 #include "cilk_fiber.h"
  50
  51 __CILKRTS_BEGIN_EXTERN_C
  52
  53 /** Magic numbers for full_frame, used for debugging */
  54 typedef unsigned long long ff_magic_t;
  55
  56 /* COMMON_SYSDEP */ struct pending_exception_info;  /* opaque */
  57
  58 /*************************************************************
  59   Full frames
  60 *************************************************************/
  61
  62 /**
  63  * @file full_frame.h
  64  * @brief A full frame includes additional information such as a join
  65  * counter and parent frame.
  66  * @defgroup FullFrames Full Frames
  67  * A full frame includes additional information such as a join
  68  * counter and parent frame.
  69  * @{
  70  */
  71
  72 /**
  73  * Convenience typedef so we don't have to specify "struct full_frame"
  74  * all over the code.  Putting it before the structure definition allows
  75  * us to use the typedef within the structure itself
  76  */
  77 typedef struct full_frame full_frame;
  78
  79 /**
  80  * @brief A full frame includes additional information such as a join
  81  * counter and parent frame.
  82  *
  83  * The frame at the top of a worker's stack is promoted into a "full"
  84  * frame, which carries additional information, such as join counter
  85  * and parent frame.  Full frames can be suspended at a sync, in which
  86  * case they lie somewhere in memory and do not belong to any
  87  * worker.
  88  *
  89  * Full frames are in contrast to the entries in the worker's deque which
  90  * are only represented by a pointer to their __cilkrts_stack_frame.
  91  *
  92  * At any instant, we say that a full frame ff is either "suspended",
  93  * or "owned" by some worker w.
  94  *
  95  * More precisely, we say that a worker w owns a frame ff under one of
  96  * the following conditions:
  97  *
  98  *  1. Creation: Worker w has just created ff, but not yet linked ff
  99  *     into the tree of full frames.  This situation can occur when a
 100  *     worker is unrolling a call stack to promote a
 101  *     __cilkrts_stack_frame to a full_frame.
 102  *  2. Executing frame: We have w->l->frame_ff == ff, i.e,. ff is the
 103  *     currently executing frame for w.
 104  *  3. Next frame: We have w->l->next_frame_ff == ff, i.e,. ff is the
 105  *     next frame that w is about to execute.
 106  *  4. Resume execution: Worker w has popped ff from
 107  *     w->l->next_frame_ff, and is about to resume execution of ff.
 108  *  5. Dying leaf: Worker w has finished executing a frame ff
 109  *     that is a leaf the tree of full frames, and is in the process
 110  *     of unlinking "ff" from the tree.
 111  *
 112  * Otherwise, the frame ff is suspended, and has no owner.
 113  * Note that work-stealing changes the owner of a full frame from the
 114  * victim to the thief.
 115  *
 116  * Using this notion of ownership, we classify the fields of a full
 117  * frame into one of several categories:
 118  *
 119  *  1. Local:
 120  *     These fields are accessed only by the owner of the full frame.
 121  *     Because a frame can have only one owner at a time, these fields
 122  *     can be modified without any (additional) locking or
 123  *     synchronization, assuming the correct synchronization for
 124  *     changing the ownership of full frame (e.g., on a successful
 125  *     steal) is already in place.
 126  *
 127  *  2. Constant (i.e., read-only):
 128  *     This field is constant for the lifetime of the full frame.
 129  *     No locks are needed to access this field.
 130  *     Technically, a field could be read-only and local, but we assume
 131  *     it is shared.
 132  *
 133  *  3. Self-locked:
 134  *     To access this field in the frame ff, a worker should acquire
 135  *     the lock on ff.
 136  *     A self-locked field is conceptually "shared" between the worker
 137  *     that owns frame ff (which is a child) and the worker that
 138  *     owns the frame ff->parent (which is the parent of ff).
 139  *
 140  *  4. Parent-locked:
 141  *     To access this field in the frame ff, a worker should
 142  *     acquire the lock on ff->parent.
 143  *     A parent-locked field is conceptually "shared" between the worker
 144  *     that owns frame ff, and a worker that is either owns the
 145  *     parent frame (ff->parent) or owns a sibling frame of ff (i.e.,
 146  *     any child of ff->parent).
 147  *
 148  *  5. Synchronization
 149  *     A field used explicitly for synchronization (i.e., locks).
 150  */
 151
 152 /* COMMON_PORTABLE */
 153 struct full_frame
 154 {
 155     /**
 156      * Value to detect writes off the beginning of a full_frame.
 157      */
 158 #   define FULL_FRAME_MAGIC_0 ((ff_magic_t)0x361e710b9597d553ULL)
 159
 160     /**
 161      * Field to detect writes off the beginning of a full_frame.  Must be
 162      * FULL_FRAME_MAGIC_0.
 163      * [constant]
 164      */
 165     ff_magic_t full_frame_magic_0;
 166
 167     /**
 168      * Used to serialize access to this full_frame
 169      * [synchronization]
 170      */
 171     struct mutex lock;
 172
 173     /**
 174      * Count of outstanding children running in parallel
 175      * [self-locked]
 176      */
 177     int join_counter;
 178
 179     /**
 180      * If TRUE: frame was called by the parent.
 181      * If FALSE: frame was spawned by parent.
 182      * [constant]
 183      */
 184     int is_call_child;
 185
 186     /**
 187      * TRUE if this frame is the loot of a simulated steal.
 188      *
 189      * This situation never happens in normal execution.  However,
 190      * when running under cilkscreen, a worker may promote frames and
 191      * then immediately suspend them, in order to simulate an
 192      * execution on an infinite number of processors where all spawns
 193      * are stolen.  In this case, the frame is marked as the loot of a fake
 194      * steal.
 195      * [local]
 196      */
 197     int simulated_stolen;
 198
 199     /**
 200      * Caller of this full_frame
 201      * [constant]
 202      */
 203     full_frame *parent;
 204
 205     /**
 206      * Doubly-linked list of children.  The serial execution order is
 207      * by definition from left to right.  Because of how we do work
 208      * stealing, the parent is always to the right of all its
 209      * children.
 210      *
 211      * For a frame ff, we lock the ff->parent to follow the sibling
 212      * links for ff.
 213      *
 214      * [parent-locked]
 215      */
 216     full_frame *left_sibling;
 217
 218     /**
 219      * @copydoc left_sibling
 220      */
 221     full_frame *right_sibling;
 222
 223     /**
 224      * Pointer to rightmost child
 225      *
 226      * [self-locked]
 227      */
 228     full_frame *rightmost_child;
 229
 230     /**
 231      * Call stack associated with this frame.
 232      * Set and reset in make_unrunnable and make_runnable
 233      *
 234      * [self-locked]
 235      */
 236     __cilkrts_stack_frame *call_stack;
 237
 238     /**
 239      * Accumulated reducers of children
 240      *
 241      * [self-locked]
 242      */
 243     struct cilkred_map *children_reducer_map;
 244
 245     /**
 246      * Accumulated reducers of right siblings that have already
 247      * terminated
 248      *
 249      * [parent-locked]
 250      */
 251     struct cilkred_map *right_reducer_map;
 252
 253     /**
 254      * Exception that needs to be pass to our parent
 255      *
 256      * [local]
 257      *
 258      * TBD: verify that the exception code satisfies this requirement.
 259      */
 260     struct pending_exception_info *pending_exception;
 261
 262     /**
 263      * Exception from one of our children
 264      *
 265      * [self-locked]
 266      */
 267     struct pending_exception_info *child_pending_exception;
 268
 269     /**
 270      * Exception from any right siblings
 271      *
 272      * [parent-locked]
 273      */
 274     struct pending_exception_info *right_pending_exception;
 275
 276     /**
 277      * Stack pointer to restore on sync.
 278      * [local]
 279      */
 280     char *sync_sp;
 281
 282 #ifdef _WIN32
 283     /**
 284      * Stack pointer to restore on exception.
 285      * [local]
 286      */
 287     char *exception_sp;
 288
 289     /**
 290      * Exception trylevel at steal
 291      * [local]
 292      *
 293      * TBD: this field is set but not read?
 294      */
 295     unsigned long trylevel;
 296
 297     /**
 298      * Exception registration head pointer to restore on sync.
 299      * [local]
 300      */
 301     unsigned long registration;
 302 #endif
 303
 304     /**
 305      * Size of frame to match sync sp
 306      * [local]
 307      * TBD: obsolete field only used in debugging?
 308      */
 309     ptrdiff_t frame_size;
 310
 311     /**
 312      * Allocated fibers that need to be freed.  The fibers work
 313      * like a reducer.  The leftmost frame may have @c fiber_self
 314      * null and owner non-null.
 315      *
 316      * [local]
 317      * TBD: verify exception code satisfies this requirement.
 318      */
 319     cilk_fiber *fiber_self;
 320
 321     /**
 322      * Allocated fibers that need to be freed.  The fibers work
 323      * like a reducer.  The leftmost frame may have @c fiber_self
 324      * null and owner non-null.
 325      *
 326      * [self-locked]
 327      */
 328     cilk_fiber *fiber_child;
 329
 330     /**
 331      * If the sync_master is set, this function can only be sync'd by the team
 332      * leader, who first entered Cilk.  This is set by the first worker to steal
 333      * from the user worker.
 334      *
 335      * [self-locked]
 336      */
 337     __cilkrts_worker *sync_master;
 338
 339     /**
 340      * Value to detect writes off the end of a full_frame.
 341      */
 342 #   define FULL_FRAME_MAGIC_1 ((ff_magic_t)0x189986dcc7aee1caULL)
 343
 344     /**
 345      * Field to detect writes off the end of a full_frame.  Must be
 346      * FULL_FRAME_MAGIC_1.
 347      *
 348      * [constant]
 349      */
 350     ff_magic_t full_frame_magic_1;
 351 };
 352
 353 /* The functions __cilkrts_put_stack and __cilkrts_take_stack keep track of
 354  * changes in the stack's depth between when the point at which a frame is
 355  * stolen and when it is resumed at a sync.  A stolen frame typically goes
 356  * through the following phase changes:
 357  *
 358  *   1. Suspend frame while stealing it.
 359  *   2. Resume stolen frame at begining of continuation
 360  *   3. Suspend stolen frame at a sync
 361  *   4. Resume frame (no longer marked stolen) after the sync
 362  *
 363  * When the frame is suspended (steps 1 and 3), __cilkrts_put_stack is called to
 364  * establish the stack pointer for the sync.  When the frame is resumed (steps
 365  * 2 and 4), __cilkrts_take_stack is called to indicate the stack pointer
 366  * (which may be on a different stack) at
 367  * the point of resume.  If the stack pointer changes between steps 2 and 3,
 368  * e.g., as a result of pushing 4 bytes onto the stack,
 369  * the offset is reflected in the value of ff->sync_sp after step 3 relative to
 370  * its value after step 1 (e.g., the value of ff->sync_sp after step 3 would be
 371  * 4 less than its value after step 1, for a down-growing stack).
 372  *
 373  * Imp detail: The actual call chains for each of these phase-change events is:
 374  *
 375  *   1. unroll_call_stack -> make_unrunnable  -> __cilkrts_put_stack
 376  *   2. do_work           -> __cilkrts_resume -> __cilkrts_take_stack
 377  *   3. do_sync -> disown -> make_runnable    -> __cilkrts_put_stack
 378  *   4. __cilkrts_resume                      -> __cilkrts_take_stack
 379  *
 380  * (The above is a changeable implementation detail.  The resume, sequence, in
 381  * particular, is more complex on some operating systems.)
 382  */
 383
 384 /**
 385  * @brief Records the stack pointer within the @c sf stack frame as the
 386  * current stack pointer at the point of suspending full frame @c ff.
 387  *
 388  * @pre @c ff->sync_sp must be either null or contain the result of a prior call to
 389  *      @c __cilkrts_take_stack().
 390  * @pre If @c ff->sync_sp is not null, then @c SP(sf) must refer to the same stack as
 391  *      the @c sp argument to the prior call to @c __cilkrts_take_stack().
 392  *
 393
 394  * @post If @c ff->sync_sp was null before the call, then @c
 395  *       ff->sync_sp will be set to @c SP(sf).
 396  * @post Otherwise, @c ff->sync_sp will be restored to the value it had just prior
 397  *       to the last call to @c __cilkrts_take_stack(), except offset by any change
 398  *       in the stack pointer between the call to @c __cilkrts_take_stack() and
 399  *       this call to @c __cilkrts_put_stack().
 400  *
 401  * @param ff The full frame that is being suspended.
 402  * @param sf The @c __cilkrts_stack_frame that is being suspended.  The stack
 403  *   pointer will be taken from the jmpbuf contained within this
 404  *   @c __cilkrts_stack_frame.
 405  */
 406 COMMON_PORTABLE void __cilkrts_put_stack(full_frame *ff,
 407                                          __cilkrts_stack_frame *sf);
 408
 409 /**
 410  * @brief Records the stack pointer @c sp as the stack pointer at the point of
 411  * resuming execution on full frame @c ff.
 412  *
 413  * The value of @c sp may be on a different stack than the original
 414  * value recorded for the stack pointer using __cilkrts_put_stack().
 415  *
 416  * @pre  @c ff->sync_sp must contain a value set by @c __cilkrts_put_stack().
 417  *
 418  * @post @c ff->sync_sp contains an *integer* value used to compute a change in the
 419  *       stack pointer upon the next call to @c __cilkrts_take_stack().
 420  * @post If @c sp equals @c ff->sync_sp, then @c ff->sync_sp is set to null.
 421  *
 422  * @param ff The full frame that is being resumed.
 423  * @param sp The stack pointer for the stack the function is being resumed on.
 424  */
 425 COMMON_PORTABLE void __cilkrts_take_stack(full_frame *ff, void *sp);
 426
 427 /*
 428  * @brief Adjust the stack for to deallocate a Variable Length Array
 429  *
 430  * @param ff The full frame that is being adjusted.
 431  * @param size The size of the array being deallocated from the stack
 432  */
 433 COMMON_PORTABLE void __cilkrts_adjust_stack(full_frame *ff, size_t size);
 434
 435 /**
 436  * @brief Allocates and initailizes a full_frame.
 437  *
 438  * @param w The memory for the full_frame will be allocated out of the
 439  * worker's pool.
 440  * @param sf The @c __cilkrts_stack_frame which will be saved as the call_stack
 441  * for this full_frame.
 442  *
 443  * @return The newly allocated and initialized full_frame.
 444  */
 445 COMMON_PORTABLE
 446 full_frame *__cilkrts_make_full_frame(__cilkrts_worker *w,
 447                                       __cilkrts_stack_frame *sf);
 448
 449 /**
 450  * @brief Deallocates a full_frame.
 451  *
 452  * @param w The memory for the full_frame will be returned to the worker's pool.
 453  * @param ff The full_frame to be deallocated.
 454  */
 455 COMMON_PORTABLE
 456 void __cilkrts_destroy_full_frame(__cilkrts_worker *w, full_frame *ff);
 457
 458 /**
 459  * @brief Performs sanity checks to check the integrity of a full_frame.
 460  *
 461  * @param ff The full_frame to be validated.
 462  */
 463 COMMON_PORTABLE void validate_full_frame(full_frame *ff);
 464
 465 /**
 466  * @brief Locks the mutex contained in a full_frame.
 467  *
 468  * The full_frame is validated before the runtime attempts to lock it.
 469  *
 470  * @post @c ff->lock will be owned by @c w.
 471  *
 472  * @param w  The worker that will own the full_frame.  If the runtime is
 473  * collecting stats, the intervals will be attributed to the worker.
 474  * @param ff The full_frame containing the mutex to be locked.
 475  */
 476 COMMON_PORTABLE void __cilkrts_frame_lock(__cilkrts_worker *w,
 477                                           full_frame *ff);
 478
 479 /**
 480  * @brief Unlocks the mutex contained in a full_frame.
 481  *
 482  * @pre @c ff->lock must must be owned by @c w.
 483  *
 484  * @param w  The worker that currently owns the full_frame.
 485  * @param ff The full_frame containing the mutex to be unlocked.
 486  */
 487 COMMON_PORTABLE void __cilkrts_frame_unlock(__cilkrts_worker *w,
 488                                             full_frame *ff);
 489 /** @} */
 490
 491 __CILKRTS_END_EXTERN_C
 492
 493 #endif // ! defined(INCLUDED_FULL_FRAME_DOT_H)