| /* record_replay.h -*-C++-*- |
| * |
| ************************************************************************* |
| * |
| * @copyright |
| * Copyright (C) 2012-2013, Intel Corporation |
| * All rights reserved. |
| * |
| * @copyright |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Intel Corporation nor the names of its |
| * contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * @copyright |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS |
| * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED |
| * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY |
| * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| * POSSIBILITY OF SUCH DAMAGE. |
| * |
| **************************************************************************/ |
| |
| /** |
| * @file record-replay.h |
| * |
| * @brief record-replay.h and .cpp encapsulate most of the functionality to |
| * record and play back a Cilk Plus application. |
| * |
| * Recording is directed by the setting of the CILK_RECORD_LOG environment |
| * variable. If it's defined, the value specifies the root we'll use to |
| * generate files for each worker using the following format string: |
| * "%s%d.cilklog", where the integer is the value of w->self. |
| * |
| * Replay is directed by the setting of the CILK_REPLAY_LOG environment |
| * variable, interpreted the same way as CILK_RECORD_LOG. If both |
| * CILK_RECORD_LOG and CILK_REPLAY_LOG are defined, a warning will be given |
| * and the attempt to record a log will be ignored. |
| * |
| * Recording is relatively straightforward. We write all information about a |
| * worker to a per-worker file. |
| * |
| * Each pedigree record consists of the following fields. All fields must be |
| * present in every record to make parsing easy. |
| * - Type - A string identifying the pedigree record. See the PED_TYPE_STR_ |
| * macros for the currently defined values. |
| * - Pedigree - A string of pedigree values, with underscores between |
| * adjacent values. |
| * - i1 - Record type-specific value. -1 if not used. |
| * - i2 - Record type-specific value. -1 if not used. |
| * |
| * WORKERS record - only written to the file for worker 0. Note that this is |
| * the first worker in the workers array. Worker 0 is the first system worker, |
| * *NOT* a user worker. |
| * - Type: "Workers" |
| * - Pedigree: Always "0" - ignored |
| * - i1: Number of workers (g->P) when we recorded the log. A mismatch when |
| * we attempt to replay the log will result in aborting the execution. |
| * - i2: Log version number - Specified by PED_VERSION in record-replay.cpp |
| * |
| * STEAL record - written after a successful steal. |
| * - Type: "Steal" |
| * - Pedigree: Pedigree of stolen frame |
| * - i1: Worker the frame was stolen from |
| * - i2: -1 |
| * |
| * SYNC record - written after a worker continues from a sync. |
| * - Type: "Sync" |
| * - Pedigree: Pedigree of sync. Note that this is the pedigree *before* |
| * the pedigree in incremented in setup_for_execution_pedigree(). |
| * - i1: -1 |
| * - i2: -1 |
| * |
| * ORPHANED record - saved on a return to a stolen parent. |
| * - Type: "Orphaned" |
| * - Pedigree: Pedigree of the parent frame *before* the pedigree is |
| * incremented by the return |
| * - i1: -1 |
| * - i2: -1 |
| * |
| * On replay, the data is loaded into a per-worker array, and the data is |
| * consumed in order as needed. |
| */ |
| |
| #ifndef INCLUDED_RECORD_REPLAY_DOT_H |
| #define INCLUDED_RECORD_REPLAY_DOT_H |
| |
| #include "cilk/common.h" |
| #include "global_state.h" |
| |
| /** |
| * Define CILK_RECORD_REPLAY to enable record/replay functionality. If |
| * CILK_RECORD_REPLAY is not defined, all of the record/replay functions in |
| * record-replay.h will be stubbed out. Since they're declared as inline, |
| * functions, the resulting build should have no performance impact due to |
| * the implementation or record/replay. |
| */ |
| #define CILK_RECORD_REPLAY 1 |
| |
| /** |
| * Define RECORD_ON_REPLAY=1 to write logs when we're replaying a log. This |
| * should only be needed when debugging the replay functionality. This should |
| * always be defined as 0 when record-replay.h is checked in. |
| */ |
| #define RECORD_ON_REPLAY 0 |
| |
| __CILKRTS_BEGIN_EXTERN_C |
| |
| #ifdef CILK_RECORD_REPLAY |
| // Declarations of internal record/replay functions. The inlined versions |
| // further down do some preliminary testing (like if we're not recording or |
| // replaying) and will stub out the functionality if we've compiled out the |
| // record/replay feature |
| int replay_match_sync_pedigree_internal(__cilkrts_worker *w); |
| void replay_wait_for_steal_if_parent_was_stolen_internal(__cilkrts_worker *w); |
| void replay_record_steal_internal(__cilkrts_worker *w, int32_t victim_id); |
| void replay_record_sync_internal(__cilkrts_worker *w); |
| void replay_record_orphaned_internal(__cilkrts_worker *w); |
| int replay_match_victim_pedigree_internal(__cilkrts_worker *w, __cilkrts_worker *victim); |
| void replay_advance_from_sync_internal (__cilkrts_worker *w); |
| int replay_get_next_recorded_victim_internal(__cilkrts_worker *w); |
| #endif // CILK_RECORD_REPLAY |
| |
| // Publically defined record/replay API |
| |
| /** |
| * If we're replaying a log, wait for our parent to be stolen if it was when |
| * the log was recorded. If record/replay is compiled out, this is a noop. |
| * |
| * @param w The __cilkrts_worker we're executing on. The worker's replay |
| * list will be checked for a ORPHANED record with a matching pedigree. If |
| * there is a match, the ORPHANED record will be consumed. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| void replay_wait_for_steal_if_parent_was_stolen(__cilkrts_worker *w) |
| { |
| // Only check if we're replaying a log |
| if (REPLAY_LOG == w->g->record_or_replay) |
| replay_wait_for_steal_if_parent_was_stolen_internal(w); |
| } |
| #else |
| __CILKRTS_INLINE |
| void replay_wait_for_steal_if_parent_was_stolen(__cilkrts_worker *w) |
| { |
| // If record/replay is disabled, we never wait |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Called from random_steal() to override the ID of the randomly chosen victim |
| * worker which this worker will attempt to steal from. Returns the worker id |
| * of the next victim this worker was recorded stealing from, or -1 if the |
| * next record in the log is not a STEAL. |
| * |
| * @note This call does NOT attempt to match the pedigree. That will be done |
| * by replay_match_victim_pedigree() after random_steal() has locked the victim |
| * worker. |
| * |
| * @param w The __cilkrts_worker we're executing on. The worker's replay log |
| * is checked for a STEAL record. If we've got one, the stolen worker ID is |
| * returned. |
| * @param id The randomly chosen victim worker ID. If we're not replaying a |
| * log, or if record/replay has been compiled out, this is the value that |
| * will be returned. |
| * |
| * @return id if we're not replaying a log |
| * @return -1 if the next record is not a STEAL |
| * @return recorded stolen worker ID if we've got a matching STEAL record |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| int replay_get_next_recorded_victim(__cilkrts_worker *w, int id) |
| { |
| // Only check if we're replaying a log |
| if (REPLAY_LOG == w->g->record_or_replay) |
| return replay_get_next_recorded_victim_internal(w); |
| else |
| return id; |
| } |
| #else |
| __CILKRTS_INLINE |
| int replay_get_next_recorded_victim(__cilkrts_worker *w, int id) |
| { |
| // Record/replay is disabled. Always return the original worker id |
| return id; |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Initialize per-worker data for record/replay. A noop if record/replay |
| * is disabled, or if we're not recording or replaying anything. |
| * |
| * If we're recording a log, this will ready us to create the per-worker |
| * logs. |
| * |
| * If we're replaying a log, this will read the logs into the per-worker |
| * structures. |
| * |
| * @param g Cilk runtime global state |
| */ |
| void replay_init_workers(global_state_t *g); |
| |
| /** |
| * Record a record on a successful steal. A noop if record/replay is |
| * diabled, or if we're not recording anything |
| * |
| * @param w The __cilkrts_worker we're executing on. The pedigree of |
| * the stolen frame will be walked to generate the STEAL record. |
| * |
| * @param victim_id The worker ID of the worker w stole from. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| void replay_record_steal(__cilkrts_worker *w, int32_t victim_id) |
| { |
| #if RECORD_ON_REPLAY |
| // If we're recording on replay, write the record if we're recording or |
| // replaying |
| if (RECORD_REPLAY_NONE == w->g->record_or_replay) |
| return; |
| #else |
| // Only write the record if we're recording |
| if (RECORD_LOG != w->g->record_or_replay) |
| return; |
| #endif |
| |
| replay_record_steal_internal(w, victim_id); |
| } |
| #else |
| __CILKRTS_INLINE |
| void replay_record_steal(__cilkrts_worker *w, int32_t victim_id) |
| { |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Record a record when continuing after a sync. A noop if record/replay is |
| * diabled, or if we're not recording anything, or if the sync was abandoned, |
| * meaning this isn't the worker that continues from the sync. |
| * |
| * @param w The __cilkrts_worker for we're executing on. The pedigree of |
| * the sync-ing frame will be walked to generate the SYNC record. |
| * |
| * @param continuing True if this worker will be continuing from the |
| * cilk_sync. A SYNC record will only be generated if continuing is true. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| void replay_record_sync(__cilkrts_worker *w, int continuing) |
| { |
| // If this was not the last worker to the syn, return |
| if (! continuing) |
| return; |
| |
| #if RECORD_ON_REPLAY |
| // If we're recording on replay, write the record if we're recording or |
| // replaying |
| if (RECORD_REPLAY_NONE == w->g->record_or_replay) |
| return; |
| #else |
| // Only write the record if we're recording |
| if (RECORD_LOG != w->g->record_or_replay) |
| return; |
| #endif |
| |
| replay_record_sync_internal(w); |
| } |
| #else |
| __CILKRTS_INLINE |
| void replay_record_sync(__cilkrts_worker *w, int abandoned) |
| { |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Record a record on a return to a stolen parent. A noop if record/replay is |
| * diabled, or if we're not recording anything. |
| * |
| * @param w The __cilkrts_worker for we're executing on. The pedigree of the |
| * frame that has discovered that its parent has been stolken will be walked |
| * to generate the ORPHANED record. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| void replay_record_orphaned(__cilkrts_worker *w) |
| { |
| #if RECORD_ON_REPLAY |
| // If we're recording on replay, write the record if we're recording or |
| // replaying |
| if (RECORD_REPLAY_NONE == w->g->record_or_replay) |
| return; |
| #else |
| // Only write the record if we're recording |
| if (RECORD_LOG != w->g->record_or_replay) |
| return; |
| #endif |
| |
| replay_record_orphaned_internal(w); |
| } |
| #else |
| __CILKRTS_INLINE |
| void replay_record_orphaned(__cilkrts_worker *w) |
| { |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Test whether the frame at the head of the victim matches the pedigree of |
| * the frame that was recorded being stolen. Called in random steal to verify |
| * that we're about to steal the correct frame. |
| * |
| * @param w The __cilkrts_worker for we're executing on. The current worker |
| * is needed to find the replay entry to be checked. |
| * |
| * @param victim The __cilkrts_worker for we're proposing to steal a frame |
| * from. The victim's head entry is |
| * is needed to find the replay entry to be checked. |
| * |
| * @return 0 if we're replaying a log and the victim's pedigree does NOT match |
| * the next frame the worker is expected to steal. |
| * |
| * @return 1 in all other cases to indicate that the steal attempt should |
| * continue |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| int replay_match_victim_pedigree(__cilkrts_worker *w, __cilkrts_worker *victim) |
| { |
| // We're not replaying a log. The victim is always acceptable |
| if (REPLAY_LOG != w->g->record_or_replay) |
| return 1; |
| |
| // Return 1 if the victim's pedigree matches the frame the worker stole |
| // when we recorded the log |
| return replay_match_victim_pedigree_internal(w, victim); |
| } |
| #else |
| __CILKRTS_INLINE |
| int replay_match_victim_pedigree(__cilkrts_worker *w, __cilkrts_worker *victim) |
| { |
| // Record/replay is disabled. The victim is always acceptable |
| return 1; |
| } |
| #endif // CILK_RECORD_REPLAY |
| |
| /** |
| * Test whether the current replay entry is a sync record matching the |
| * worker's pedigree. |
| * |
| * @param w The __cilkrts_worker for we're executing on. |
| * |
| * @return 1 if the current replay entry matches the current pedigree. |
| * @return 0 if there's no match, or if we're not replaying a log. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| int replay_match_sync_pedigree(__cilkrts_worker *w) |
| { |
| // If we're not replaying, assume no match |
| if (REPLAY_LOG != w->g->record_or_replay) |
| return 0; |
| |
| return replay_match_sync_pedigree_internal(w); |
| } |
| #else |
| __CILKRTS_INLINE |
| int replay_match_sync_pedigree(__cilkrts_worker *w) |
| { |
| // Record/replay is disabled. Assume no match |
| return 0; |
| } |
| #endif |
| |
| /** |
| * Marks a sync record seen, advancing to the next record in the replay list. |
| * |
| * This function will only advance to the next record if: |
| * - Record/replay hasn't been compiled out AND |
| * - We're replaying a log AND |
| * - A match was found AND |
| * - The sync is not being abandoned |
| * |
| * @param w The __cilkrts_worker for we're executing on. |
| * @param match_found The value returned by replay_match_sync_pedigree(). If |
| * match_found is false, nothing is done. |
| * @param continuing Flag indicating whether this worker will continue from |
| * the sync (it's the last worker to the sync) or if it will abandon the work |
| * and go to the scheduling loop to look for more work it can steal. |
| */ |
| #ifdef CILK_RECORD_REPLAY |
| __CILKRTS_INLINE |
| void replay_advance_from_sync(__cilkrts_worker *w, int match_found, int continuing) |
| { |
| // If we're replaying a log, and the current sync wasn't abandoned, and we |
| // found a match in the log, mark the sync record seen. |
| if ((REPLAY_LOG == w->g->record_or_replay) && match_found && continuing) |
| replay_advance_from_sync_internal(w); |
| } |
| #else |
| __CILKRTS_INLINE |
| void replay_advance_from_sync(__cilkrts_worker *w, int match_found, int continuing) |
| { |
| } |
| #endif |
| |
| /** |
| * Release any resources used to read or write a replay log. |
| * |
| * @param g Cilk runtime global state |
| */ |
| void replay_term(global_state_t *g); |
| |
| __CILKRTS_END_EXTERN_C |
| |
| #endif // ! defined(INCLUDED_RECORD_REPLAY_DOT_H) |