1 //===- FuzzerTracePC.h - Internal header for the Fuzzer ---------*- C++ -* ===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // fuzzer::TracePC 10 //===----------------------------------------------------------------------===// 11 12 #ifndef LLVM_FUZZER_TRACE_PC 13 #define LLVM_FUZZER_TRACE_PC 14 15 #include "FuzzerDefs.h" 16 #include "FuzzerDictionary.h" 17 #include "FuzzerValueBitMap.h" 18 19 #include <set> 20 21 namespace fuzzer { 22 23 // TableOfRecentCompares (TORC) remembers the most recently performed 24 // comparisons of type T. 25 // We record the arguments of CMP instructions in this table unconditionally 26 // because it seems cheaper this way than to compute some expensive 27 // conditions inside __sanitizer_cov_trace_cmp*. 28 // After the unit has been executed we may decide to use the contents of 29 // this table to populate a Dictionary. 30 template<class T, size_t kSizeT> 31 struct TableOfRecentCompares { 32 static const size_t kSize = kSizeT; 33 struct Pair { 34 T A, B; 35 }; 36 ATTRIBUTE_NO_SANITIZE_ALL 37 void Insert(size_t Idx, const T &Arg1, const T &Arg2) { 38 Idx = Idx % kSize; 39 Table[Idx].A = Arg1; 40 Table[Idx].B = Arg2; 41 } 42 43 Pair Get(size_t I) { return Table[I % kSize]; } 44 45 Pair Table[kSize]; 46 }; 47 48 template <size_t kSizeT> 49 struct MemMemTable { 50 static const size_t kSize = kSizeT; 51 Word MemMemWords[kSize]; 52 Word EmptyWord; 53 54 void Add(const uint8_t *Data, size_t Size) { 55 if (Size <= 2) return; 56 Size = std::min(Size, Word::GetMaxSize()); 57 size_t Idx = SimpleFastHash(Data, Size) % kSize; 58 MemMemWords[Idx].Set(Data, Size); 59 } 60 const Word &Get(size_t Idx) { 61 for (size_t i = 0; i < kSize; i++) { 62 const Word &W = MemMemWords[(Idx + i) % kSize]; 63 if (W.size()) return W; 64 } 65 EmptyWord.Set(nullptr, 0); 66 return EmptyWord; 67 } 68 }; 69 70 class TracePC { 71 public: 72 static const size_t kNumPCs = 1 << 21; 73 // How many bits of PC are used from __sanitizer_cov_trace_pc. 74 static const size_t kTracePcBits = 18; 75 76 void HandleInit(uint32_t *Start, uint32_t *Stop); 77 void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop); 78 void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop); 79 void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); 80 template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2); 81 size_t GetTotalPCCoverage(); 82 void SetUseCounters(bool UC) { UseCounters = UC; } 83 void SetUseClangCoverage(bool UCC) { UseClangCoverage = UCC; } 84 void SetUseValueProfile(bool VP) { UseValueProfile = VP; } 85 void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; } 86 void SetPrintNewFuncs(size_t P) { NumPrintNewFuncs = P; } 87 void UpdateObservedPCs(); 88 template <class Callback> void CollectFeatures(Callback CB) const; 89 90 void ResetMaps() { 91 ValueProfileMap.Reset(); 92 if (NumModules) 93 memset(Counters(), 0, GetNumPCs()); 94 ClearExtraCounters(); 95 ClearInlineCounters(); 96 if (UseClangCoverage) 97 ClearClangCounters(); 98 } 99 100 void ClearInlineCounters(); 101 102 void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); 103 void PrintFeatureSet(); 104 105 void PrintModuleInfo(); 106 107 void PrintCoverage(); 108 void DumpCoverage(); 109 110 void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2, 111 size_t n, bool StopAtZero); 112 113 TableOfRecentCompares<uint32_t, 32> TORC4; 114 TableOfRecentCompares<uint64_t, 32> TORC8; 115 TableOfRecentCompares<Word, 32> TORCW; 116 MemMemTable<1024> MMT; 117 118 size_t GetNumPCs() const { 119 return NumGuards == 0 ? (1 << kTracePcBits) : Min(kNumPCs, NumGuards + 1); 120 } 121 uintptr_t GetPC(size_t Idx) { 122 assert(Idx < GetNumPCs()); 123 return PCs()[Idx]; 124 } 125 126 void RecordInitialStack(); 127 uintptr_t GetMaxStackOffset() const; 128 129 template<class CallBack> 130 void ForEachObservedPC(CallBack CB) { 131 for (auto PC : ObservedPCs) 132 CB(PC); 133 } 134 135 private: 136 bool UseCounters = false; 137 bool UseValueProfile = false; 138 bool UseClangCoverage = false; 139 bool DoPrintNewPCs = false; 140 size_t NumPrintNewFuncs = 0; 141 142 struct Module { 143 uint32_t *Start, *Stop; 144 }; 145 146 Module Modules[4096]; 147 size_t NumModules; // linker-initialized. 148 size_t NumGuards; // linker-initialized. 149 150 struct { uint8_t *Start, *Stop; } ModuleCounters[4096]; 151 size_t NumModulesWithInline8bitCounters; // linker-initialized. 152 size_t NumInline8bitCounters; 153 154 struct PCTableEntry { 155 uintptr_t PC, PCFlags; 156 }; 157 158 struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096]; 159 size_t NumPCTables; 160 size_t NumPCsInPCTables; 161 162 uint8_t *Counters() const; 163 uintptr_t *PCs() const; 164 165 Set<uintptr_t> ObservedPCs; 166 Set<uintptr_t> ObservedFuncs; 167 168 ValueBitMap ValueProfileMap; 169 uintptr_t InitialStack; 170 }; 171 172 template <class Callback> 173 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value); 174 ATTRIBUTE_NO_SANITIZE_ALL 175 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End, 176 size_t FirstFeature, Callback Handle8bitCounter) { 177 typedef uintptr_t LargeType; 178 const size_t Step = sizeof(LargeType) / sizeof(uint8_t); 179 const size_t StepMask = Step - 1; 180 auto P = Begin; 181 // Iterate by 1 byte until either the alignment boundary or the end. 182 for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++) 183 if (uint8_t V = *P) 184 Handle8bitCounter(FirstFeature, P - Begin, V); 185 186 // Iterate by Step bytes at a time. 187 for (; P < End; P += Step) 188 if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P)) 189 for (size_t I = 0; I < Step; I++, Bundle >>= 8) 190 if (uint8_t V = Bundle & 0xff) 191 Handle8bitCounter(FirstFeature, P - Begin + I, V); 192 193 // Iterate by 1 byte until the end. 194 for (; P < End; P++) 195 if (uint8_t V = *P) 196 Handle8bitCounter(FirstFeature, P - Begin, V); 197 } 198 199 // Given a non-zero Counters returns a number in [0,7]. 200 template<class T> 201 unsigned CounterToFeature(T Counter) { 202 assert(Counter); 203 unsigned Bit = 0; 204 /**/ if (Counter >= 128) Bit = 7; 205 else if (Counter >= 32) Bit = 6; 206 else if (Counter >= 16) Bit = 5; 207 else if (Counter >= 8) Bit = 4; 208 else if (Counter >= 4) Bit = 3; 209 else if (Counter >= 3) Bit = 2; 210 else if (Counter >= 2) Bit = 1; 211 return Bit; 212 } 213 214 template <class Callback> // void Callback(size_t Feature) 215 ATTRIBUTE_NO_SANITIZE_ADDRESS 216 __attribute__((noinline)) 217 void TracePC::CollectFeatures(Callback HandleFeature) const { 218 uint8_t *Counters = this->Counters(); 219 size_t N = GetNumPCs(); 220 auto Handle8bitCounter = [&](size_t FirstFeature, 221 size_t Idx, uint8_t Counter) { 222 HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter)); 223 }; 224 225 size_t FirstFeature = 0; 226 227 if (!NumInline8bitCounters) { 228 ForEachNonZeroByte(Counters, Counters + N, FirstFeature, Handle8bitCounter); 229 FirstFeature += N * 8; 230 } 231 232 if (NumInline8bitCounters) { 233 for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) { 234 ForEachNonZeroByte(ModuleCounters[i].Start, ModuleCounters[i].Stop, 235 FirstFeature, Handle8bitCounter); 236 FirstFeature += 8 * (ModuleCounters[i].Stop - ModuleCounters[i].Start); 237 } 238 } 239 240 if (size_t NumClangCounters = ClangCountersEnd() - ClangCountersBegin()) { 241 auto P = ClangCountersBegin(); 242 for (size_t Idx = 0; Idx < NumClangCounters; Idx++) 243 if (auto Cnt = P[Idx]) 244 HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Cnt)); 245 FirstFeature += NumClangCounters; 246 } 247 248 ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature, 249 Handle8bitCounter); 250 FirstFeature += (ExtraCountersEnd() - ExtraCountersBegin()) * 8; 251 252 if (UseValueProfile) { 253 ValueProfileMap.ForEach([&](size_t Idx) { 254 HandleFeature(FirstFeature + Idx); 255 }); 256 FirstFeature += ValueProfileMap.SizeInBits(); 257 } 258 259 if (auto MaxStackOffset = GetMaxStackOffset()) 260 HandleFeature(FirstFeature + MaxStackOffset); 261 } 262 263 extern TracePC TPC; 264 265 } // namespace fuzzer 266 267 #endif // LLVM_FUZZER_TRACE_PC 268
