contrib/compiler-rt/lib/fuzzer/FuzzerTracePC.h

   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 #include <unordered_map>
  21
  22 namespace fuzzer {
  23
  24 // TableOfRecentCompares (TORC) remembers the most recently performed
  25 // comparisons of type T.
  26 // We record the arguments of CMP instructions in this table unconditionally
  27 // because it seems cheaper this way than to compute some expensive
  28 // conditions inside __sanitizer_cov_trace_cmp*.
  29 // After the unit has been executed we may decide to use the contents of
  30 // this table to populate a Dictionary.
  31 template<class T, size_t kSizeT>
  32 struct TableOfRecentCompares {
  33   static const size_t kSize = kSizeT;
  34   struct Pair {
  35     T A, B;
  36   };
  37   ATTRIBUTE_NO_SANITIZE_ALL
  38   void Insert(size_t Idx, const T &Arg1, const T &Arg2) {
  39     Idx = Idx % kSize;
  40     Table[Idx].A = Arg1;
  41     Table[Idx].B = Arg2;
  42   }
  43
  44   Pair Get(size_t I) { return Table[I % kSize]; }
  45
  46   Pair Table[kSize];
  47 };
  48
  49 template <size_t kSizeT>
  50 struct MemMemTable {
  51   static const size_t kSize = kSizeT;
  52   Word MemMemWords[kSize];
  53   Word EmptyWord;
  54
  55   void Add(const uint8_t *Data, size_t Size) {
  56     if (Size <= 2) return;
  57     Size = std::min(Size, Word::GetMaxSize());
  58     size_t Idx = SimpleFastHash(Data, Size) % kSize;
  59     MemMemWords[Idx].Set(Data, Size);
  60   }
  61   const Word &Get(size_t Idx) {
  62     for (size_t i = 0; i < kSize; i++) {
  63       const Word &W = MemMemWords[(Idx + i) % kSize];
  64       if (W.size()) return W;
  65     }
  66     EmptyWord.Set(nullptr, 0);
  67     return EmptyWord;
  68   }
  69 };
  70
  71 class TracePC {
  72  public:
  73   static const size_t kNumPCs = 1 << 21;
  74   // How many bits of PC are used from __sanitizer_cov_trace_pc.
  75   static const size_t kTracePcBits = 18;
  76
  77   enum HandleUnstableOptions {
  78     MinUnstable = 1,
  79     ZeroUnstable = 2,
  80   };
  81
  82   void HandleInit(uint32_t *Start, uint32_t *Stop);
  83   void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop);
  84   void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop);
  85   void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
  86   template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2);
  87   size_t GetTotalPCCoverage();
  88   void SetUseCounters(bool UC) { UseCounters = UC; }
  89   void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; }
  90   void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
  91   void SetPrintNewFuncs(size_t P) { NumPrintNewFuncs = P; }
  92   void UpdateObservedPCs();
  93   template <class Callback> void CollectFeatures(Callback CB) const;
  94
  95   void ResetMaps() {
  96     ValueProfileMap.Reset();
  97     if (NumModules)
  98       memset(Counters(), 0, GetNumPCs());
  99     ClearExtraCounters();
 100     ClearInlineCounters();
 101   }
 102
 103   void ClearInlineCounters();
 104
 105   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
 106   void PrintFeatureSet();
 107
 108   void PrintModuleInfo();
 109
 110   void PrintCoverage();
 111   void DumpCoverage();
 112   void PrintUnstableStats();
 113
 114   template<class CallBack>
 115   void IterateCoveredFunctions(CallBack CB);
 116
 117   void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
 118                          size_t n, bool StopAtZero);
 119
 120   TableOfRecentCompares<uint32_t, 32> TORC4;
 121   TableOfRecentCompares<uint64_t, 32> TORC8;
 122   TableOfRecentCompares<Word, 32> TORCW;
 123   MemMemTable<1024> MMT;
 124
 125   size_t GetNumPCs() const {
 126     return NumGuards == 0 ? (1 << kTracePcBits) : Min(kNumPCs, NumGuards + 1);
 127   }
 128   uintptr_t GetPC(size_t Idx) {
 129     assert(Idx < GetNumPCs());
 130     return PCs()[Idx];
 131   }
 132
 133   void RecordInitialStack();
 134   uintptr_t GetMaxStackOffset() const;
 135
 136   template<class CallBack>
 137   void ForEachObservedPC(CallBack CB) {
 138     for (auto PC : ObservedPCs)
 139       CB(PC);
 140   }
 141
 142   void SetFocusFunction(const std::string &FuncName);
 143   bool ObservedFocusFunction();
 144
 145   void InitializeUnstableCounters();
 146   void UpdateUnstableCounters(int UnstableMode);
 147   void ApplyUnstableCounters();
 148
 149 private:
 150   struct UnstableEdge {
 151     uint8_t Counter;
 152     bool IsUnstable;
 153   };
 154
 155   UnstableEdge UnstableCounters[kNumPCs];
 156
 157   bool UseCounters = false;
 158   uint32_t UseValueProfileMask = false;
 159   bool DoPrintNewPCs = false;
 160   size_t NumPrintNewFuncs = 0;
 161
 162   struct Module {
 163     uint32_t *Start, *Stop;
 164   };
 165
 166   Module Modules[4096];
 167   size_t NumModules;  // linker-initialized.
 168   size_t NumGuards;  // linker-initialized.
 169
 170   struct { uint8_t *Start, *Stop; } ModuleCounters[4096];
 171   size_t NumModulesWithInline8bitCounters;  // linker-initialized.
 172   size_t NumInline8bitCounters;
 173
 174   struct PCTableEntry {
 175     uintptr_t PC, PCFlags;
 176   };
 177
 178   struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];
 179   size_t NumPCTables;
 180   size_t NumPCsInPCTables;
 181
 182   uint8_t *Counters() const;
 183   uintptr_t *PCs() const;
 184
 185   Set<uintptr_t> ObservedPCs;
 186   std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs;  // PC => Counter.
 187
 188   template <class Callback>
 189   void IterateInline8bitCounters(Callback CB) const;
 190
 191   std::pair<size_t, size_t> FocusFunction = {-1, -1};  // Module and PC IDs.
 192
 193   ValueBitMap ValueProfileMap;
 194   uintptr_t InitialStack;
 195 };
 196
 197 template <class Callback>
 198 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
 199 ATTRIBUTE_NO_SANITIZE_ALL
 200 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
 201                         size_t FirstFeature, Callback Handle8bitCounter) {
 202   typedef uintptr_t LargeType;
 203   const size_t Step = sizeof(LargeType) / sizeof(uint8_t);
 204   const size_t StepMask = Step - 1;
 205   auto P = Begin;
 206   // Iterate by 1 byte until either the alignment boundary or the end.
 207   for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)
 208     if (uint8_t V = *P)
 209       Handle8bitCounter(FirstFeature, P - Begin, V);
 210
 211   // Iterate by Step bytes at a time.
 212   for (; P < End; P += Step)
 213     if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P))
 214       for (size_t I = 0; I < Step; I++, Bundle >>= 8)
 215         if (uint8_t V = Bundle & 0xff)
 216           Handle8bitCounter(FirstFeature, P - Begin + I, V);
 217
 218   // Iterate by 1 byte until the end.
 219   for (; P < End; P++)
 220     if (uint8_t V = *P)
 221       Handle8bitCounter(FirstFeature, P - Begin, V);
 222 }
 223
 224 // Given a non-zero Counter returns a number in the range [0,7].
 225 template<class T>
 226 unsigned CounterToFeature(T Counter) {
 227     // Returns a feature number by placing Counters into buckets as illustrated
 228     // below.
 229     //
 230     // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]
 231     // Feature number:  0   1   2    3     4       5       6       7
 232     //
 233     // This is a heuristic taken from AFL (see
 234     // http://lcamtuf.coredump.cx/afl/technical_details.txt).
 235     //
 236     // This implementation may change in the future so clients should
 237     // not rely on it.
 238     assert(Counter);
 239     unsigned Bit = 0;
 240     /**/ if (Counter >= 128) Bit = 7;
 241     else if (Counter >= 32) Bit = 6;
 242     else if (Counter >= 16) Bit = 5;
 243     else if (Counter >= 8) Bit = 4;
 244     else if (Counter >= 4) Bit = 3;
 245     else if (Counter >= 3) Bit = 2;
 246     else if (Counter >= 2) Bit = 1;
 247     return Bit;
 248 }
 249
 250 template <class Callback>  // void Callback(size_t Feature)
 251 ATTRIBUTE_NO_SANITIZE_ADDRESS
 252 __attribute__((noinline))
 253 void TracePC::CollectFeatures(Callback HandleFeature) const {
 254   uint8_t *Counters = this->Counters();
 255   size_t N = GetNumPCs();
 256   auto Handle8bitCounter = [&](size_t FirstFeature,
 257                                size_t Idx, uint8_t Counter) {
 258     if (UseCounters)
 259       HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
 260     else
 261       HandleFeature(FirstFeature + Idx);
 262   };
 263
 264   size_t FirstFeature = 0;
 265
 266   if (!NumInline8bitCounters) {
 267     ForEachNonZeroByte(Counters, Counters + N, FirstFeature, Handle8bitCounter);
 268     FirstFeature += N * 8;
 269   }
 270
 271   if (NumInline8bitCounters) {
 272     for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) {
 273       ForEachNonZeroByte(ModuleCounters[i].Start, ModuleCounters[i].Stop,
 274                          FirstFeature, Handle8bitCounter);
 275       FirstFeature += 8 * (ModuleCounters[i].Stop - ModuleCounters[i].Start);
 276     }
 277   }
 278
 279   ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature,
 280                      Handle8bitCounter);
 281   FirstFeature += (ExtraCountersEnd() - ExtraCountersBegin()) * 8;
 282
 283   if (UseValueProfileMask) {
 284     ValueProfileMap.ForEach([&](size_t Idx) {
 285       HandleFeature(FirstFeature + Idx);
 286     });
 287     FirstFeature += ValueProfileMap.SizeInBits();
 288   }
 289
 290   // Step function, grows similar to 8 * Log_2(A).
 291   auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
 292     if (!A) return A;
 293     uint32_t Log2 = Log(A);
 294     if (Log2 < 3) return A;
 295     Log2 -= 3;
 296     return (Log2 + 1) * 8 + ((A >> Log2) & 7);
 297   };
 298   assert(StackDepthStepFunction(1024) == 64);
 299   assert(StackDepthStepFunction(1024 * 4) == 80);
 300   assert(StackDepthStepFunction(1024 * 1024) == 144);
 301
 302   if (auto MaxStackOffset = GetMaxStackOffset())
 303     HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
 304 }
 305
 306 extern TracePC TPC;
 307
 308 }  // namespace fuzzer
 309
 310 #endif  // LLVM_FUZZER_TRACE_PC