123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433 |
- /* 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)
|