diff options
Diffstat (limited to 'libcilkrts/runtime/record-replay.h')
| -rw-r--r-- | libcilkrts/runtime/record-replay.h | 427 |
1 files changed, 427 insertions, 0 deletions
diff --git a/libcilkrts/runtime/record-replay.h b/libcilkrts/runtime/record-replay.h new file mode 100644 index 00000000000..f65e667a8e1 --- /dev/null +++ b/libcilkrts/runtime/record-replay.h @@ -0,0 +1,427 @@ +/* record_replay.h -*-C++-*- + * + ************************************************************************* + * + * @copyright + * Copyright (C) 2012 + * Intel Corporation + * + * @copyright + * This file is part of the Intel Cilk Plus Library. This library is free + * software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the + * Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * @copyright + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * @copyright + * Under Section 7 of GPL version 3, you are granted additional + * permissions described in the GCC Runtime Library Exception, version + * 3.1, as published by the Free Software Foundation. + * + * @copyright + * You should have received a copy of the GNU General Public License and + * a copy of the GCC Runtime Library Exception along with this program; + * see the files COPYING3 and COPYING.RUNTIME respectively. If not, see + * <http://www.gnu.org/licenses/>. + * + **************************************************************************/ + +/** + * @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) |