1 /* Copyright (c) 2008-2010, Google Inc. 2 * All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Neither the name of Google Inc. nor the names of its 11 * contributors may be used to endorse or promote products derived from 12 * this software without specific prior written permission. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 // This file is part of ThreadSanitizer, a dynamic data race detector. 28 // Author: Konstantin Serebryany. 29 // Information about one TRACE (single-entry-multiple-exit region of code). 30 #ifndef TS_TRACE_INFO_ 31 #define TS_TRACE_INFO_ 32 33 #include "ts_util.h" 34 // Information about one Memory Operation. 35 // 36 // A memory access is represented by mop[idx] = {pc,size,is_write} 37 // which is computed at instrumentation time and {actual_address} computed 38 // at run-time. The instrumentation insn looks like 39 // tleb[idx] = actual_address 40 // The create_sblock field tells if we want to remember the stack trace 41 // which corresponds to this Mop (i.e. create an SBLOCK). 42 struct MopInfo { 43 public: MopInfoMopInfo44 MopInfo(uintptr_t pc, size_t size, bool is_write, bool create_sblock) { 45 DCHECK(sizeof(*this) == 8); 46 pc_ = pc; 47 if (size > 16) size = 16; // some instructions access more than 16 bytes. 48 size_minus1_ = size - 1; 49 is_write_ = is_write; 50 create_sblock_ = create_sblock; 51 52 DCHECK(size != 0); 53 DCHECK(this->size() == size); 54 DCHECK(this->is_write() == is_write); 55 DCHECK(this->create_sblock() == create_sblock); 56 } 57 MopInfoMopInfo58 MopInfo() { 59 DCHECK(sizeof(*this) == 8); 60 memset(this, 0, sizeof(*this)); 61 } 62 pcMopInfo63 uintptr_t pc() { return pc_; }; sizeMopInfo64 size_t size() { return size_minus1_ + 1; } is_writeMopInfo65 bool is_write() { return is_write_; } create_sblockMopInfo66 bool create_sblock() { return create_sblock_; } 67 68 private: 69 uint64_t pc_ :58; // 48 bits is enough for pc, even on x86-64. 70 uint64_t create_sblock_ :1; 71 uint64_t is_write_ :1; 72 uint64_t size_minus1_ :4; // 0..15 73 }; 74 75 // ---------------- Lite Race ------------------ 76 // Experimental! 77 // 78 // The idea was first introduced in LiteRace: 79 // http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf 80 // Instead of analyzing all memory accesses, we do sampling. 81 // For each trace (single-enry muliple-exit region) we maintain a counter of 82 // executions. If a trace has been executed more than a certain threshold, we 83 // start skipping this trace sometimes. 84 // The LiteRace paper suggests several strategies for sampling, including 85 // thread-local counters. Having thread local counters for all threads is too 86 // expensive, so we have kLiteRaceNumTids arrays of counters and use 87 // the array (tid % 8). 88 // 89 // sampling_rate indicates the level of sampling. 90 // 0 means no sampling. 91 // 1 means handle *almost* all accesses. 92 // ... 93 // 31 means very aggressive sampling (skip a lot of accesses). 94 95 // 96 // Note: ANNOTATE_PUBLISH_MEMORY() does not work with sampling... :( 97 98 struct LiteRaceCounters { 99 uint32_t counter; 100 int32_t num_to_skip; 101 }; 102 103 struct TraceInfoPOD { 104 enum { kLiteRaceNumTids = 8 }; 105 enum { kLiteRaceStorageSize = 8 }; 106 typedef LiteRaceCounters LiteRaceStorage[kLiteRaceNumTids][kLiteRaceStorageSize]; 107 108 size_t n_mops_; 109 size_t pc_; 110 size_t counter_; 111 LiteRaceStorage *literace_storage; 112 int32_t storage_index; 113 MopInfo mops_[1]; 114 }; 115 116 // An instance of this class is created for each TRACE (SEME region) 117 // during instrumentation. 118 class TraceInfo : public TraceInfoPOD { 119 public: 120 static TraceInfo *NewTraceInfo(size_t n_mops, uintptr_t pc); DeleteTraceInfo(TraceInfo * trace_info)121 void DeleteTraceInfo(TraceInfo *trace_info) { 122 delete [] (uintptr_t*)trace_info; 123 } GetMop(size_t i)124 MopInfo *GetMop(size_t i) { 125 DCHECK(i < n_mops_); 126 return &mops_[i]; 127 } 128 n_mops()129 size_t n_mops() const { return n_mops_; } pc()130 size_t pc() const { return pc_; } counter()131 size_t &counter() { return counter_; } mops()132 MopInfo *mops() { return mops_; } 133 134 static void PrintTraceProfile(); 135 LiteRaceSkipTraceQuickCheck(uintptr_t tid_modulo_num)136 INLINE bool LiteRaceSkipTraceQuickCheck(uintptr_t tid_modulo_num) { 137 DCHECK(tid_modulo_num < kLiteRaceNumTids); 138 // Check how may accesses are left to skip. Racey, but ok. 139 LiteRaceCounters *counters = 140 &((*literace_storage)[tid_modulo_num][storage_index]); 141 int32_t num_to_skip = --counters->num_to_skip; 142 if (num_to_skip > 0) { 143 return true; 144 } 145 return false; 146 } 147 LiteRaceUpdate(uintptr_t tid_modulo_num,uint32_t sampling_rate)148 INLINE void LiteRaceUpdate(uintptr_t tid_modulo_num, uint32_t sampling_rate) { 149 DCHECK(sampling_rate < 32); 150 DCHECK(sampling_rate > 0); 151 LiteRaceCounters *counters = 152 &((*literace_storage)[tid_modulo_num][storage_index]); 153 uint32_t cur_counter = counters->counter; 154 // The bigger the counter the bigger the number of skipped accesses. 155 int32_t next_num_to_skip = (cur_counter >> (32 - sampling_rate)) + 1; 156 counters->num_to_skip = next_num_to_skip; 157 counters->counter = cur_counter + next_num_to_skip; 158 159 } 160 161 // TODO(glider): get rid of this. LLVMLiteRaceUpdate(uintptr_t tid_modulo_num,uint32_t sampling_rate)162 INLINE void LLVMLiteRaceUpdate(uintptr_t tid_modulo_num, 163 uint32_t sampling_rate) { 164 LiteRaceUpdate(tid_modulo_num, sampling_rate); 165 } 166 167 // This is all racey, but ok. LiteRaceSkipTrace(uint32_t tid_modulo_num,uint32_t sampling_rate)168 INLINE bool LiteRaceSkipTrace(uint32_t tid_modulo_num, 169 uint32_t sampling_rate) { 170 if (LiteRaceSkipTraceQuickCheck(tid_modulo_num)) return true; 171 LiteRaceUpdate(tid_modulo_num, sampling_rate); 172 return false; 173 } 174 LiteRaceSkipTraceRealTid(uint32_t tid,uint32_t sampling_rate)175 INLINE bool LiteRaceSkipTraceRealTid(uint32_t tid, uint32_t sampling_rate) { 176 return LiteRaceSkipTrace(tid % kLiteRaceNumTids, sampling_rate); 177 } 178 179 private: 180 static size_t id_counter_; 181 static vector<TraceInfo*> *g_all_traces; 182 TraceInfo()183 TraceInfo() : TraceInfoPOD() { } 184 }; 185 186 // end. {{{1 187 #endif // TS_TRACE_INFO_ 188 // vim:shiftwidth=2:softtabstop=2:expandtab:tw=80 189