1 //===- FuzzerTracePC.h - Internal header for the Fuzzer ---------*- C++ -* ===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // fuzzer::TracePC 9 //===----------------------------------------------------------------------===// 10 11 #ifndef LLVM_FUZZER_TRACE_PC 12 #define LLVM_FUZZER_TRACE_PC 13 14 #include "FuzzerDefs.h" 15 #include "FuzzerDictionary.h" 16 #include "FuzzerValueBitMap.h" 17 18 #include <set> 19 #include <unordered_map> 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 void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop); 73 void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop); 74 void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); 75 template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2); 76 size_t GetTotalPCCoverage(); 77 void SetUseCounters(bool UC) { UseCounters = UC; } 78 void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; } 79 void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; } 80 void SetPrintNewFuncs(size_t P) { NumPrintNewFuncs = P; } 81 void UpdateObservedPCs(); 82 template <class Callback> void CollectFeatures(Callback CB) const; 83 84 void ResetMaps() { 85 ValueProfileMap.Reset(); 86 ClearExtraCounters(); 87 ClearInlineCounters(); 88 } 89 90 void ClearInlineCounters(); 91 92 void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); 93 void PrintFeatureSet(); 94 95 void PrintModuleInfo(); 96 97 void PrintCoverage(); 98 99 template<class CallBack> 100 void IterateCoveredFunctions(CallBack CB); 101 102 void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2, 103 size_t n, bool StopAtZero); 104 105 TableOfRecentCompares<uint32_t, 32> TORC4; 106 TableOfRecentCompares<uint64_t, 32> TORC8; 107 TableOfRecentCompares<Word, 32> TORCW; 108 MemMemTable<1024> MMT; 109 110 void RecordInitialStack(); 111 uintptr_t GetMaxStackOffset() const; 112 113 template<class CallBack> 114 void ForEachObservedPC(CallBack CB) { 115 for (auto PC : ObservedPCs) 116 CB(PC); 117 } 118 119 void SetFocusFunction(const std::string &FuncName); 120 bool ObservedFocusFunction(); 121 122 void ProtectLazyCounters(); 123 bool UnprotectLazyCounters(void *CounterPtr); 124 125 struct PCTableEntry { 126 uintptr_t PC, PCFlags; 127 }; 128 129 uintptr_t PCTableEntryIdx(const PCTableEntry *TE); 130 const PCTableEntry *PCTableEntryByIdx(uintptr_t Idx); 131 static uintptr_t GetNextInstructionPc(uintptr_t PC); 132 bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; } 133 134 private: 135 bool UseCounters = false; 136 uint32_t UseValueProfileMask = false; 137 bool DoPrintNewPCs = false; 138 size_t NumPrintNewFuncs = 0; 139 140 // Module represents the array of 8-bit counters split into regions 141 // such that every region, except maybe the first and the last one, is one 142 // full page. 143 struct Module { 144 struct Region { 145 uint8_t *Start, *Stop; 146 bool Enabled; 147 bool OneFullPage; 148 }; 149 Region *Regions; 150 size_t NumRegions; 151 uint8_t *Start() { return Regions[0].Start; } 152 uint8_t *Stop() { return Regions[NumRegions - 1].Stop; } 153 size_t Size() { return Stop() - Start(); } 154 size_t Idx(uint8_t *P) { 155 assert(P >= Start() && P < Stop()); 156 return P - Start(); 157 } 158 }; 159 160 Module Modules[4096]; 161 size_t NumModules; // linker-initialized. 162 size_t NumInline8bitCounters; 163 164 template <class Callback> 165 void IterateCounterRegions(Callback CB) { 166 for (size_t m = 0; m < NumModules; m++) 167 for (size_t r = 0; r < Modules[m].NumRegions; r++) 168 CB(Modules[m].Regions[r]); 169 } 170 171 struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096]; 172 size_t NumPCTables; 173 size_t NumPCsInPCTables; 174 175 Set<const PCTableEntry*> ObservedPCs; 176 std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs; // PC => Counter. 177 178 uint8_t *FocusFunctionCounterPtr = nullptr; 179 180 ValueBitMap ValueProfileMap; 181 uintptr_t InitialStack; 182 }; 183 184 template <class Callback> 185 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value); 186 ATTRIBUTE_NO_SANITIZE_ALL 187 size_t ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End, 188 size_t FirstFeature, Callback Handle8bitCounter) { 189 typedef uintptr_t LargeType; 190 const size_t Step = sizeof(LargeType) / sizeof(uint8_t); 191 const size_t StepMask = Step - 1; 192 auto P = Begin; 193 // Iterate by 1 byte until either the alignment boundary or the end. 194 for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++) 195 if (uint8_t V = *P) 196 Handle8bitCounter(FirstFeature, P - Begin, V); 197 198 // Iterate by Step bytes at a time. 199 for (; P < End; P += Step) 200 if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P)) 201 for (size_t I = 0; I < Step; I++, Bundle >>= 8) 202 if (uint8_t V = Bundle & 0xff) 203 Handle8bitCounter(FirstFeature, P - Begin + I, V); 204 205 // Iterate by 1 byte until the end. 206 for (; P < End; P++) 207 if (uint8_t V = *P) 208 Handle8bitCounter(FirstFeature, P - Begin, V); 209 return End - Begin; 210 } 211 212 // Given a non-zero Counter returns a number in the range [0,7]. 213 template<class T> 214 unsigned CounterToFeature(T Counter) { 215 // Returns a feature number by placing Counters into buckets as illustrated 216 // below. 217 // 218 // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+] 219 // Feature number: 0 1 2 3 4 5 6 7 220 // 221 // This is a heuristic taken from AFL (see 222 // http://lcamtuf.coredump.cx/afl/technical_details.txt). 223 // 224 // This implementation may change in the future so clients should 225 // not rely on it. 226 assert(Counter); 227 unsigned Bit = 0; 228 /**/ if (Counter >= 128) Bit = 7; 229 else if (Counter >= 32) Bit = 6; 230 else if (Counter >= 16) Bit = 5; 231 else if (Counter >= 8) Bit = 4; 232 else if (Counter >= 4) Bit = 3; 233 else if (Counter >= 3) Bit = 2; 234 else if (Counter >= 2) Bit = 1; 235 return Bit; 236 } 237 238 template <class Callback> // void Callback(size_t Feature) 239 ATTRIBUTE_NO_SANITIZE_ADDRESS 240 ATTRIBUTE_NOINLINE 241 void TracePC::CollectFeatures(Callback HandleFeature) const { 242 auto Handle8bitCounter = [&](size_t FirstFeature, 243 size_t Idx, uint8_t Counter) { 244 if (UseCounters) 245 HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter)); 246 else 247 HandleFeature(FirstFeature + Idx); 248 }; 249 250 size_t FirstFeature = 0; 251 252 for (size_t i = 0; i < NumModules; i++) { 253 for (size_t r = 0; r < Modules[i].NumRegions; r++) { 254 if (!Modules[i].Regions[r].Enabled) continue; 255 FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start, 256 Modules[i].Regions[r].Stop, 257 FirstFeature, Handle8bitCounter); 258 } 259 } 260 261 FirstFeature += 262 8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), 263 FirstFeature, Handle8bitCounter); 264 265 if (UseValueProfileMask) { 266 ValueProfileMap.ForEach([&](size_t Idx) { 267 HandleFeature(FirstFeature + Idx); 268 }); 269 FirstFeature += ValueProfileMap.SizeInBits(); 270 } 271 272 // Step function, grows similar to 8 * Log_2(A). 273 auto StackDepthStepFunction = [](uint32_t A) -> uint32_t { 274 if (!A) return A; 275 uint32_t Log2 = Log(A); 276 if (Log2 < 3) return A; 277 Log2 -= 3; 278 return (Log2 + 1) * 8 + ((A >> Log2) & 7); 279 }; 280 assert(StackDepthStepFunction(1024) == 64); 281 assert(StackDepthStepFunction(1024 * 4) == 80); 282 assert(StackDepthStepFunction(1024 * 1024) == 144); 283 284 if (auto MaxStackOffset = GetMaxStackOffset()) 285 HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)); 286 } 287 288 extern TracePC TPC; 289 290 } // namespace fuzzer 291 292 #endif // LLVM_FUZZER_TRACE_PC 293