libcilkrts/runtime/local_state.h

   1 /* local_state.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 local_state.h
  41  *
  42  * @brief The local_state structure contains additional OS-independent
  43  * information that's associated with a worker, but doesn't need to be visible
  44  * to the code generated by the compiler.
  45  */
  46
  47 #ifndef INCLUDED_LOCAL_STATE_DOT_H
  48 #define INCLUDED_LOCAL_STATE_DOT_H
  49
  50 #include <internal/abi.h>
  51 #include "worker_mutex.h"
  52 #include "global_state.h"
  53 #include "record-replay.h"
  54 #include "signal_node.h"
  55
  56 #include <setjmp.h>
  57 #include <stddef.h>
  58 #include <stdio.h>
  59
  60
  61 #ifndef _WIN32
  62 #   include <pthread.h>
  63 #endif
  64
  65 __CILKRTS_BEGIN_EXTERN_C
  66
  67 /* Opaque types. */
  68
  69 struct full_frame;
  70 struct free_list;
  71 struct pending_exception_info;
  72 /// Opaque type for replay entry.
  73 typedef struct replay_entry_t replay_entry_t;
  74
  75 /**
  76  * @brief Magic numbers for local_state, used for debugging
  77  */
  78 typedef unsigned long long ls_magic_t;
  79
  80 /**
  81  * @brief Scheduling stack function: A function that is decided on the program stack,
  82  * but that must be executed on the scheduling stack.
  83  */
  84 typedef void (*scheduling_stack_fcn_t) (__cilkrts_worker *w,
  85                                         struct full_frame *ff,
  86                                         __cilkrts_stack_frame *sf);
  87
  88 /**
  89  * @brief Type of this worker.
  90  **/
  91 typedef enum cilk_worker_type
  92 {
  93     WORKER_FREE,    ///< Unused worker - available to be bound to user threads
  94     WORKER_SYSTEM,  ///< Worker created by runtime - able to steal from any worker
  95     WORKER_USER     ///< User thread - able to steal only from team members
  96 } cilk_worker_type;
  97
  98
  99 /**
 100  * @brief The local_state structure contains additional OS-independent
 101  * information that's associated with a worker, but doesn't need to be
 102  * visible to the compiler.
 103  *
 104  * No compiler-generated code should need to know the layout of this
 105  * structure.
 106  *
 107  * The fields of this struct can be classified as either local or
 108  * shared.
 109  *
 110  *  Local: This field is only accessed by the thread bound to this
 111  *    worker struct.  Local fields can be freely accessed without
 112  *    acquiring locks.
 113  *
 114  *  Shared: This field may be accessed by multiple worker threads.
 115  *    Accesses to shared fields usually requires locks, except in
 116  *    special situations where one can prove that locks are
 117  *    unnecessary.
 118  *
 119  * The fields of this can also be classified as "read-only" if the
 120  * field does not change after it is initialized.  Otherwise, the
 121  * field is "read/write".  Read-only fields do not require locks to
 122  * access (ignoring the synchronization that might be needed for
 123  * initialization if this can occur in parallel).
 124  *
 125  * Finally, we explicitly classify some fields as "synchronization"
 126  * fields if they are used as part of a synchronization protocol in
 127  * the runtime.  These variables are generally shared and read/write.
 128  * Mostly, this category includes lock variables and other variables
 129  * that are involved in synchronization protocols (i.e., the THE
 130  * protocol).
 131  */
 132 struct local_state  /* COMMON_PORTABLE */
 133 {
 134     /** This value should be in the first field in any local_state */
 135 #   define WORKER_MAGIC_0 ((ls_magic_t)0xe0831a4a940c60b8ULL)
 136
 137     /**
 138      * Should be WORKER_MAGIC_0 or the local_state has been corrupted
 139      * This magic field is shared because it is read on lock acquisitions.
 140      *
 141      * [shared read-only]
 142      */
 143     ls_magic_t worker_magic_0;
 144
 145     /**
 146      * Mutex used to serialize access to the local_state
 147      * Synchronization field. [shared read/write]
 148      */
 149     struct mutex lock;
 150
 151     /**
 152      * Flag that indicates that the worker is interested in grabbing
 153      * LOCK, and thus thieves should leave the worker alone.
 154      * Written only by self, may be read by others.
 155      *
 156      * Synchronization field.  [shared read/write]
 157      */
 158     int do_not_steal;
 159
 160     /**
 161      * Lock that all thieves grab in order to compete for the right
 162      * to disturb this worker.
 163      *
 164      * Synchronization field. [shared read/write]
 165      */
 166     struct mutex steal_lock;
 167
 168     /**
 169      * Full frame that the worker is working on.
 170      *
 171      * While a worker w is executing, a thief may change
 172      * w->l->frame_ff (on a successful steal) after acquiring w's
 173      * lock.
 174      *
 175      * Unlocked accesses to w->l->frame_ff are safe (by w itself) when
 176      * w's deque is empty, or when stealing from w has been disabled.
 177      *
 178      * [shared read/write]
 179      */
 180     struct full_frame *frame_ff;
 181
 182     /**
 183      * Full frame that the worker will be working on next
 184      *
 185      * This field is normally local for a worker w.  Another worker v
 186      * may modify w->l->next_frame_ff, however, in the special case
 187      * when v is returning a frame to a user thread w since w is the
 188      * team leader.
 189      *
 190      * [shared read/write]
 191      */
 192     struct full_frame *next_frame_ff;
 193
 194     /**
 195      * This is set iff this is a WORKER_USER and there has been a steal.  It
 196      * points to the first frame that was stolen since the team was last fully
 197      * sync'd.  Only this worker may continue past a sync in this function.
 198      *
 199      * This field is set by a thief for a victim that is a user
 200      * thread, while holding the victim's lock.
 201      * It can be cleared without a lock by the worker that will
 202      * continue exuecting past the sync.
 203      *
 204      * [shared read/write]
 205      */
 206     struct full_frame *last_full_frame;
 207
 208     /**
 209      * Team on which this worker is a participant.  When a user worker enters,
 210      * its team is its own worker struct and it can never change teams.  When a
 211      * system worker steals, it adopts the team of its victim.
 212      *
 213      * When a system worker w steals, it reads victim->l->team and
 214      * joins this team.  w->l->team is constant until the next time w
 215      * returns control to the runtime.
 216      * We must acquire the worker lock to change w->l->team.
 217      *
 218      * @note This field is 64-byte aligned because it is the first in
 219      * the group of shared read-only fields.  We want this group to
 220      * fall on a different cache line from the previous group, which
 221      * is shared read-write.
 222      *
 223      * [shared read-only]
 224      */
 225     __attribute__((aligned(64)))
 226     __cilkrts_worker *team;
 227
 228     /**
 229      * Type of this worker
 230      *
 231      * This field changes only when a worker binds or unbinds.
 232      * Otherwise, the field is read-only while the worker is bound.
 233      *
 234      * [shared read-only]
 235      */
 236     cilk_worker_type type;
 237
 238     /**
 239      * Lazy task queue of this worker - an array of pointers to stack frames.
 240      *
 241      * Read-only because deques are a fixed size in the current
 242      * implementation.
 243      *
 244      * @note This field is 64-byte aligned because it is the first in
 245      * the group of local fields.  We want this group to fall on a
 246      * different cache line from the previous group, which is shared
 247      * read-only.
 248      *
 249      * [local read-only]
 250      */
 251     __attribute__((aligned(64)))
 252     __cilkrts_stack_frame **ltq;
 253
 254     /**
 255      * Pool of fibers waiting to be reused.
 256      * [local read/write]
 257      */
 258     cilk_fiber_pool fiber_pool;
 259
 260     /**
 261      * The fiber for the scheduling stacks.
 262      * [local read/write]
 263      */
 264     cilk_fiber* scheduling_fiber;
 265
 266     /**
 267      * Saved pointer to the leaf node in thread-local storage, when a
 268      * user thread is imported.  This pointer gets set to a
 269      * meaningful value when binding a user thread, and cleared on
 270      * unbind.
 271      *
 272      * [local read/write]
 273      */
 274     __cilkrts_pedigree* original_pedigree_leaf;
 275
 276     /**
 277      * State of the random number generator
 278      *
 279      * [local read/write]
 280      */
 281     unsigned rand_seed;
 282
 283     /**
 284      * Function to execute after transferring onto the scheduling stack.
 285      *
 286      * [local read/write]
 287      */
 288     scheduling_stack_fcn_t post_suspend;
 289
 290     /**
 291      * __cilkrts_stack_frame we suspended when we transferred onto the
 292      * scheduling stack.
 293      *
 294      * [local read/write]
 295      */
 296     __cilkrts_stack_frame *suspended_stack;
 297
 298     /**
 299      * cilk_fiber that should be freed after returning from a
 300      *  spawn with a stolen parent or after stalling at a sync.
 301
 302      *  We calculate the stack to free when executing a reduction on
 303      *  the user stack, but we can not actually release the stack
 304      *  until control longjmps onto a runtime scheduling stack.
 305      *
 306      * This field is used to pass information to the runtime across
 307      * the longjmp onto the scheduling stack.
 308      *
 309      * [local read/write]
 310      */
 311     cilk_fiber* fiber_to_free;
 312
 313     /**
 314      * Saved exception object for an exception that is being passed to
 315      * our parent
 316      *
 317      * [local read/write]
 318      */
 319     struct pending_exception_info *pending_exception;
 320
 321     /**
 322      * Buckets for the memory allocator
 323      *
 324      * [local read/write]
 325      */
 326     struct free_list *free_list[FRAME_MALLOC_NBUCKETS];
 327
 328     /**
 329      * Potential function for the memory allocator
 330      *
 331      * [local read/write]
 332      */
 333     size_t bucket_potential[FRAME_MALLOC_NBUCKETS];
 334
 335     /**
 336      * Support for statistics
 337      *
 338      * Useful only when CILK_PROFIlE is compiled in.
 339      * [local read/write]
 340      */
 341     statistics* stats;
 342
 343     /**
 344      * Count indicates number of failures since last successful steal.  This is
 345      * used by the scheduler to reduce contention on shared flags.
 346      *
 347      * [local read/write]
 348      */
 349     unsigned int steal_failure_count;
 350
 351     /**
 352      * 1 if work was stolen from another worker.  When true, this will flag
 353      * setup_for_execution_pedigree to increment the pedigree when we resume
 354      * execution to match the increment that would have been done on a return
 355      * from a spawn helper.
 356      *
 357      * [local read/write]
 358      */
 359     int work_stolen;
 360
 361     /**
 362      * File pointer for record or replay
 363      * Does FILE * work on Windows?
 364      * During record, the file will be opened in write-only mode.
 365      * During replay, the file will be opened in read-only mode.
 366      *
 367      * [local read/write]
 368      */
 369     FILE *record_replay_fptr;
 370
 371     /**
 372      * Root of array of replay entries - NULL if we're not replaying a log
 373      *
 374      * [local read/write]
 375      */
 376     replay_entry_t *replay_list_root;
 377
 378     /**
 379      * Current replay entry - NULL if we're not replaying a log
 380      *
 381      * [local read/write]
 382      */
 383     replay_entry_t *replay_list_entry;
 384
 385     /**
 386      * Separate the signal_node from other things in the local_state by the
 387      * sizeof a cache line for performance reasons.
 388      *
 389      * unused
 390      */
 391     char buf[64];
 392
 393     /**
 394      * Signal object for waking/sleeping the worker.  This should be a pointer
 395      * to avoid the possibility of caching problems.
 396      *
 397      * [shared read-only]
 398      */
 399      signal_node_t *signal_node;
 400
 401     /** This value should be in the last field in any local_state */
 402 #   define WORKER_MAGIC_1 ((ls_magic_t)0x16164afb0ea0dff9ULL)
 403
 404     /**
 405      * Should be WORKER_MAGIC_1 or the local_state has been corrupted
 406      * This magic field is shared because it is read on lock acquisitions.
 407      * [shared read-only]
 408      */
 409     ls_magic_t worker_magic_1;
 410 };
 411
 412 /**
 413  * Perform cleanup according to the function set before the longjmp().
 414  *
 415  * Call this after longjmp() has completed and the worker is back on a
 416  * scheduling stack.
 417  *
 418  * @param w __cilkrts_worker currently executing.
 419  */
 420 void run_scheduling_stack_fcn(__cilkrts_worker *w);
 421
 422 __CILKRTS_END_EXTERN_C
 423
 424 #endif // ! defined(INCLUDED_LOCAL_STATE_DOT_H)