299 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8// fuzzer::TracePC9//===----------------------------------------------------------------------===//10 11#ifndef LLVM_FUZZER_TRACE_PC12#define LLVM_FUZZER_TRACE_PC13 14#include "FuzzerDefs.h"15#include "FuzzerDictionary.h"16#include "FuzzerValueBitMap.h"17 18#include <set>19#include <unordered_map>20 21namespace fuzzer {22 23// TableOfRecentCompares (TORC) remembers the most recently performed24// comparisons of type T.25// We record the arguments of CMP instructions in this table unconditionally26// because it seems cheaper this way than to compute some expensive27// conditions inside __sanitizer_cov_trace_cmp*.28// After the unit has been executed we may decide to use the contents of29// this table to populate a Dictionary.30template<class T, size_t kSizeT>31struct TableOfRecentCompares {32 static const size_t kSize = kSizeT;33 struct Pair {34 T A, B;35 };36 ATTRIBUTE_NO_SANITIZE_ALL37 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 48template <size_t kSizeT>49struct 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 auto 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 70class 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> size_t 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(bool PrintAllCounters);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 struct PCTableEntry {123 uintptr_t PC, PCFlags;124 };125 126 uintptr_t PCTableEntryIdx(const PCTableEntry *TE);127 const PCTableEntry *PCTableEntryByIdx(uintptr_t Idx);128 static uintptr_t GetNextInstructionPc(uintptr_t PC);129 bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; }130 131private:132 bool UseCounters = false;133 uint32_t UseValueProfileMask = false;134 bool DoPrintNewPCs = false;135 size_t NumPrintNewFuncs = 0;136 137 // Module represents the array of 8-bit counters split into regions138 // such that every region, except maybe the first and the last one, is one139 // full page.140 struct Module {141 struct Region {142 uint8_t *Start, *Stop;143 bool Enabled;144 bool OneFullPage;145 };146 Region *Regions;147 size_t NumRegions;148 uint8_t *Start() { return Regions[0].Start; }149 uint8_t *Stop() { return Regions[NumRegions - 1].Stop; }150 size_t Size() { return Stop() - Start(); }151 size_t Idx(uint8_t *P) {152 assert(P >= Start() && P < Stop());153 return P - Start();154 }155 };156 157 Module Modules[4096];158 size_t NumModules; // linker-initialized.159 size_t NumInline8bitCounters;160 161 template <class Callback>162 void IterateCounterRegions(Callback CB) {163 for (size_t m = 0; m < NumModules; m++)164 for (size_t r = 0; r < Modules[m].NumRegions; r++)165 CB(Modules[m].Regions[r]);166 }167 168 struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];169 size_t NumPCTables;170 size_t NumPCsInPCTables;171 172 std::set<const PCTableEntry *> ObservedPCs;173 std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs; // PC => Counter.174 175 uint8_t *FocusFunctionCounterPtr = nullptr;176 177 ValueBitMap ValueProfileMap;178 uintptr_t InitialStack;179};180 181template <class Callback>182// void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);183ATTRIBUTE_NO_SANITIZE_ALL184size_t ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,185 size_t FirstFeature, Callback Handle8bitCounter) {186 typedef uintptr_t LargeType;187 const size_t Step = sizeof(LargeType) / sizeof(uint8_t);188 const size_t StepMask = Step - 1;189 auto P = Begin;190 // Iterate by 1 byte until either the alignment boundary or the end.191 for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)192 if (uint8_t V = *P)193 Handle8bitCounter(FirstFeature, P - Begin, V);194 195 // Iterate by Step bytes at a time.196 for (; P + Step <= End; P += Step)197 if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P)) {198 Bundle = HostToLE(Bundle);199 for (size_t I = 0; I < Step; I++, Bundle >>= 8)200 if (uint8_t V = Bundle & 0xff)201 Handle8bitCounter(FirstFeature, P - Begin + I, V);202 }203 204 // Iterate by 1 byte until the end.205 for (; P < End; P++)206 if (uint8_t V = *P)207 Handle8bitCounter(FirstFeature, P - Begin, V);208 return End - Begin;209}210 211// Given a non-zero Counter returns a number in the range [0,7].212template<class T>213unsigned CounterToFeature(T Counter) {214 // Returns a feature number by placing Counters into buckets as illustrated215 // below.216 //217 // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]218 // Feature number: 0 1 2 3 4 5 6 7219 //220 // This is a heuristic taken from AFL (see221 // http://lcamtuf.coredump.cx/afl/technical_details.txt).222 //223 // This implementation may change in the future so clients should224 // not rely on it.225 assert(Counter);226 unsigned Bit = 0;227 /**/ if (Counter >= 128) Bit = 7;228 else if (Counter >= 32) Bit = 6;229 else if (Counter >= 16) Bit = 5;230 else if (Counter >= 8) Bit = 4;231 else if (Counter >= 4) Bit = 3;232 else if (Counter >= 3) Bit = 2;233 else if (Counter >= 2) Bit = 1;234 return Bit;235}236 237template <class Callback> // void Callback(uint32_t Feature)238ATTRIBUTE_NO_SANITIZE_ADDRESS ATTRIBUTE_NOINLINE size_t239TracePC::CollectFeatures(Callback HandleFeature) const {240 auto Handle8bitCounter = [&](size_t FirstFeature,241 size_t Idx, uint8_t Counter) {242 if (UseCounters)243 HandleFeature(static_cast<uint32_t>(FirstFeature + Idx * 8 +244 CounterToFeature(Counter)));245 else246 HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));247 };248 249 size_t FirstFeature = 0;250 251 for (size_t i = 0; i < NumModules; i++) {252 for (size_t r = 0; r < Modules[i].NumRegions; r++) {253 if (!Modules[i].Regions[r].Enabled) continue;254 FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,255 Modules[i].Regions[r].Stop,256 FirstFeature, Handle8bitCounter);257 }258 }259 260 FirstFeature +=261 8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),262 FirstFeature, Handle8bitCounter);263 264 if (UseValueProfileMask) {265 ValueProfileMap.ForEach([&](size_t Idx) {266 HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));267 });268 FirstFeature += ValueProfileMap.SizeInBits();269 }270 271 // Step function, grows similar to 8 * Log_2(A).272 auto StackDepthStepFunction = [](size_t A) -> size_t {273 if (!A)274 return A;275 auto Log2 = Log(A);276 if (Log2 < 3)277 return A;278 Log2 -= 3;279 return (Log2 + 1) * 8 + ((A >> Log2) & 7);280 };281 assert(StackDepthStepFunction(1024) == 64);282 assert(StackDepthStepFunction(1024 * 4) == 80);283 assert(StackDepthStepFunction(1024 * 1024) == 144);284 285 if (auto MaxStackOffset = GetMaxStackOffset()) {286 HandleFeature(static_cast<uint32_t>(287 FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)));288 FirstFeature += StackDepthStepFunction(std::numeric_limits<size_t>::max());289 }290 291 return FirstFeature;292}293 294extern TracePC TPC;295 296} // namespace fuzzer297 298#endif // LLVM_FUZZER_TRACE_PC299