| /* Copyright (c) 2008-2010, Google Inc. |
| * All rights reserved. |
| * |
| * 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. |
| * * Neither the name of Google Inc. nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * 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 |
| * OWNER 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. |
| */ |
| |
| // This file is part of ThreadSanitizer, a dynamic data race detector. |
| // Author: Konstantin Serebryany. |
| // Information about one TRACE (single-entry-multiple-exit region of code). |
| #ifndef TS_TRACE_INFO_ |
| #define TS_TRACE_INFO_ |
| |
| #include "ts_util.h" |
| // Information about one Memory Operation. |
| // |
| // A memory access is represented by mop[idx] = {pc,size,is_write} |
| // which is computed at instrumentation time and {actual_address} computed |
| // at run-time. The instrumentation insn looks like |
| // tleb[idx] = actual_address |
| // The create_sblock field tells if we want to remember the stack trace |
| // which corresponds to this Mop (i.e. create an SBLOCK). |
| struct MopInfo { |
| public: |
| MopInfo(uintptr_t pc, size_t size, bool is_write, bool create_sblock) { |
| DCHECK(sizeof(*this) == 8); |
| pc_ = pc; |
| if (size > 16) size = 16; // some instructions access more than 16 bytes. |
| size_minus1_ = size - 1; |
| is_write_ = is_write; |
| create_sblock_ = create_sblock; |
| |
| DCHECK(size != 0); |
| DCHECK(this->size() == size); |
| DCHECK(this->is_write() == is_write); |
| DCHECK(this->create_sblock() == create_sblock); |
| } |
| |
| MopInfo() { |
| DCHECK(sizeof(*this) == 8); |
| memset(this, 0, sizeof(*this)); |
| } |
| |
| uintptr_t pc() { return pc_; }; |
| size_t size() { return size_minus1_ + 1; } |
| bool is_write() { return is_write_; } |
| bool create_sblock() { return create_sblock_; } |
| |
| private: |
| uint64_t pc_ :58; // 48 bits is enough for pc, even on x86-64. |
| uint64_t create_sblock_ :1; |
| uint64_t is_write_ :1; |
| uint64_t size_minus1_ :4; // 0..15 |
| }; |
| |
| // ---------------- Lite Race ------------------ |
| // Experimental! |
| // |
| // The idea was first introduced in LiteRace: |
| // http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf |
| // Instead of analyzing all memory accesses, we do sampling. |
| // For each trace (single-enry muliple-exit region) we maintain a counter of |
| // executions. If a trace has been executed more than a certain threshold, we |
| // start skipping this trace sometimes. |
| // The LiteRace paper suggests several strategies for sampling, including |
| // thread-local counters. Having thread local counters for all threads is too |
| // expensive, so we have kLiteRaceNumTids arrays of counters and use |
| // the array (tid % 8). |
| // |
| // sampling_rate indicates the level of sampling. |
| // 0 means no sampling. |
| // 1 means handle *almost* all accesses. |
| // ... |
| // 31 means very aggressive sampling (skip a lot of accesses). |
| |
| // |
| // Note: ANNOTATE_PUBLISH_MEMORY() does not work with sampling... :( |
| |
| struct LiteRaceCounters { |
| uint32_t counter; |
| int32_t num_to_skip; |
| }; |
| |
| struct TraceInfoPOD { |
| enum { kLiteRaceNumTids = 8 }; |
| enum { kLiteRaceStorageSize = 8 }; |
| typedef LiteRaceCounters LiteRaceStorage[kLiteRaceNumTids][kLiteRaceStorageSize]; |
| |
| size_t n_mops_; |
| size_t pc_; |
| size_t counter_; |
| LiteRaceStorage *literace_storage; |
| int32_t storage_index; |
| MopInfo mops_[1]; |
| }; |
| |
| // An instance of this class is created for each TRACE (SEME region) |
| // during instrumentation. |
| class TraceInfo : public TraceInfoPOD { |
| public: |
| static TraceInfo *NewTraceInfo(size_t n_mops, uintptr_t pc); |
| void DeleteTraceInfo(TraceInfo *trace_info) { |
| delete [] (uintptr_t*)trace_info; |
| } |
| MopInfo *GetMop(size_t i) { |
| DCHECK(i < n_mops_); |
| return &mops_[i]; |
| } |
| |
| size_t n_mops() const { return n_mops_; } |
| size_t pc() const { return pc_; } |
| size_t &counter() { return counter_; } |
| MopInfo *mops() { return mops_; } |
| |
| static void PrintTraceProfile(); |
| |
| INLINE bool LiteRaceSkipTraceQuickCheck(uintptr_t tid_modulo_num) { |
| DCHECK(tid_modulo_num < kLiteRaceNumTids); |
| // Check how may accesses are left to skip. Racey, but ok. |
| LiteRaceCounters *counters = |
| &((*literace_storage)[tid_modulo_num][storage_index]); |
| int32_t num_to_skip = --counters->num_to_skip; |
| if (num_to_skip > 0) { |
| return true; |
| } |
| return false; |
| } |
| |
| INLINE void LiteRaceUpdate(uintptr_t tid_modulo_num, uint32_t sampling_rate) { |
| DCHECK(sampling_rate < 32); |
| DCHECK(sampling_rate > 0); |
| LiteRaceCounters *counters = |
| &((*literace_storage)[tid_modulo_num][storage_index]); |
| uint32_t cur_counter = counters->counter; |
| // The bigger the counter the bigger the number of skipped accesses. |
| int32_t next_num_to_skip = (cur_counter >> (32 - sampling_rate)) + 1; |
| counters->num_to_skip = next_num_to_skip; |
| counters->counter = cur_counter + next_num_to_skip; |
| |
| } |
| |
| // TODO(glider): get rid of this. |
| INLINE void LLVMLiteRaceUpdate(uintptr_t tid_modulo_num, |
| uint32_t sampling_rate) { |
| LiteRaceUpdate(tid_modulo_num, sampling_rate); |
| } |
| |
| // This is all racey, but ok. |
| INLINE bool LiteRaceSkipTrace(uint32_t tid_modulo_num, |
| uint32_t sampling_rate) { |
| if (LiteRaceSkipTraceQuickCheck(tid_modulo_num)) return true; |
| LiteRaceUpdate(tid_modulo_num, sampling_rate); |
| return false; |
| } |
| |
| INLINE bool LiteRaceSkipTraceRealTid(uint32_t tid, uint32_t sampling_rate) { |
| return LiteRaceSkipTrace(tid % kLiteRaceNumTids, sampling_rate); |
| } |
| |
| private: |
| static size_t id_counter_; |
| static vector<TraceInfo*> *g_all_traces; |
| |
| TraceInfo() : TraceInfoPOD() { } |
| }; |
| |
| // end. {{{1 |
| #endif // TS_TRACE_INFO_ |
| // vim:shiftwidth=2:softtabstop=2:expandtab:tw=80 |