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 class TracePC { 49 public: 50 static const size_t kNumPCs = 1 << 21; 51 // How many bits of PC are used from __sanitizer_cov_trace_pc. 52 static const size_t kTracePcBits = 18; 53 54 void HandleInit(uint32_t *start, uint32_t *stop); 55 void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); 56 template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2); 57 size_t GetTotalPCCoverage(); 58 void SetUseCounters(bool UC) { UseCounters = UC; } 59 void SetUseValueProfile(bool VP) { UseValueProfile = VP; } 60 void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; } 61 template <class Callback> void CollectFeatures(Callback CB) const; 62 63 void ResetMaps() { 64 ValueProfileMap.Reset(); 65 memset(Counters(), 0, GetNumPCs()); 66 ClearExtraCounters(); 67 } 68 69 void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); 70 void PrintFeatureSet(); 71 72 void PrintModuleInfo(); 73 74 void PrintCoverage(); 75 void DumpCoverage(); 76 77 void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2, 78 size_t n, bool StopAtZero); 79 80 TableOfRecentCompares<uint32_t, 32> TORC4; 81 TableOfRecentCompares<uint64_t, 32> TORC8; 82 TableOfRecentCompares<Word, 32> TORCW; 83 84 void PrintNewPCs(); 85 void InitializePrintNewPCs(); 86 size_t GetNumPCs() const { 87 return NumGuards == 0 ? (1 << kTracePcBits) : Min(kNumPCs, NumGuards + 1); 88 } 89 uintptr_t GetPC(size_t Idx) { 90 assert(Idx < GetNumPCs()); 91 return PCs()[Idx]; 92 } 93 94 private: 95 bool UseCounters = false; 96 bool UseValueProfile = false; 97 bool DoPrintNewPCs = false; 98 99 struct Module { 100 uint32_t *Start, *Stop; 101 }; 102 103 Module Modules[4096]; 104 size_t NumModules; // linker-initialized. 105 size_t NumGuards; // linker-initialized. 106 107 uint8_t *Counters() const; 108 uintptr_t *PCs() const; 109 110 std::set<uintptr_t> *PrintedPCs; 111 112 ValueBitMap ValueProfileMap; 113 }; 114 115 template <class Callback> // void Callback(size_t Idx, uint8_t Value); 116 ATTRIBUTE_NO_SANITIZE_ALL 117 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End, 118 size_t FirstFeature, Callback Handle8bitCounter) { 119 typedef uintptr_t LargeType; 120 const size_t Step = sizeof(LargeType) / sizeof(uint8_t); 121 assert(!(reinterpret_cast<uintptr_t>(Begin) % 64)); 122 for (auto P = Begin; P < End; P += Step) 123 if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P)) 124 for (size_t I = 0; I < Step; I++, Bundle >>= 8) 125 if (uint8_t V = Bundle & 0xff) 126 Handle8bitCounter(FirstFeature + P - Begin + I, V); 127 } 128 129 template <class Callback> // bool Callback(size_t Feature) 130 ATTRIBUTE_NO_SANITIZE_ALL 131 __attribute__((noinline)) 132 void TracePC::CollectFeatures(Callback HandleFeature) const { 133 uint8_t *Counters = this->Counters(); 134 size_t N = GetNumPCs(); 135 auto Handle8bitCounter = [&](size_t Idx, uint8_t Counter) { 136 assert(Counter); 137 unsigned Bit = 0; 138 /**/ if (Counter >= 128) Bit = 7; 139 else if (Counter >= 32) Bit = 6; 140 else if (Counter >= 16) Bit = 5; 141 else if (Counter >= 8) Bit = 4; 142 else if (Counter >= 4) Bit = 3; 143 else if (Counter >= 3) Bit = 2; 144 else if (Counter >= 2) Bit = 1; 145 HandleFeature(Idx * 8 + Bit); 146 }; 147 148 ForEachNonZeroByte(Counters, Counters + N, 0, Handle8bitCounter); 149 ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), N * 8, 150 Handle8bitCounter); 151 152 if (UseValueProfile) 153 ValueProfileMap.ForEach([&](size_t Idx) { 154 HandleFeature(N * 8 + Idx); 155 }); 156 } 157 158 extern TracePC TPC; 159 160 } // namespace fuzzer 161 162 #endif // LLVM_FUZZER_TRACE_PC 163