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   void HandleInit(uint32_t *Start, uint32_t *Stop);
  78   void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop);
  79   void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop);
  80   void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
  81   template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2);
  82   size_t GetTotalPCCoverage();
  83   void SetUseCounters(bool UC) { UseCounters = UC; }
  84   void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; }
  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   }
  97
  98   void ClearInlineCounters();
  99
 100   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
 101   void PrintFeatureSet();
 102
 103   void PrintModuleInfo();
 104
 105   void PrintCoverage();
 106   void DumpCoverage();
 107
 108   template<class CallBack>
 109   void IterateCoveredFunctions(CallBack CB);
 110
 111   void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
 112                          size_t n, bool StopAtZero);
 113
 114   TableOfRecentCompares<uint32_t, 32> TORC4;
 115   TableOfRecentCompares<uint64_t, 32> TORC8;
 116   TableOfRecentCompares<Word, 32> TORCW;
 117   MemMemTable<1024> MMT;
 118
 119   size_t GetNumPCs() const {
 120     return NumGuards == 0 ? (1 << kTracePcBits) : Min(kNumPCs, NumGuards + 1);
 121   }
 122   uintptr_t GetPC(size_t Idx) {
 123     assert(Idx < GetNumPCs());
 124     return PCs()[Idx];
 125   }
 126
 127   void RecordInitialStack();
 128   uintptr_t GetMaxStackOffset() const;
 129
 130   template<class CallBack>
 131   void ForEachObservedPC(CallBack CB) {
 132     for (auto PC : ObservedPCs)
 133       CB(PC);
 134   }
 135
 136   void SetFocusFunction(const std::string &FuncName);
 137   bool ObservedFocusFunction();
 138
 139 private:
 140   bool UseCounters = false;
 141   uint32_t UseValueProfileMask = false;
 142   bool DoPrintNewPCs = false;
 143   size_t NumPrintNewFuncs = 0;
 144
 145   struct Module {
 146     uint32_t *Start, *Stop;
 147   };
 148
 149   Module Modules[4096];
 150   size_t NumModules;  // linker-initialized.
 151   size_t NumGuards;  // linker-initialized.
 152
 153   struct { uint8_t *Start, *Stop; } ModuleCounters[4096];
 154   size_t NumModulesWithInline8bitCounters;  // linker-initialized.
 155   size_t NumInline8bitCounters;
 156
 157   struct PCTableEntry {
 158     uintptr_t PC, PCFlags;
 159   };
 160
 161   struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];
 162   size_t NumPCTables;
 163   size_t NumPCsInPCTables;
 164
 165   uint8_t *Counters() const;
 166   uintptr_t *PCs() const;
 167
 168   Set<uintptr_t> ObservedPCs;
 169   std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs;  // PC => Counter.
 170
 171   std::pair<size_t, size_t> FocusFunction = {-1, -1};  // Module and PC IDs.
 172
 173   ValueBitMap ValueProfileMap;
 174   uintptr_t InitialStack;
 175 };
 176
 177 template <class Callback>
 178 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
 179 ATTRIBUTE_NO_SANITIZE_ALL
 180 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
 181                         size_t FirstFeature, Callback Handle8bitCounter) {
 182   typedef uintptr_t LargeType;
 183   const size_t Step = sizeof(LargeType) / sizeof(uint8_t);
 184   const size_t StepMask = Step - 1;
 185   auto P = Begin;
 186   // Iterate by 1 byte until either the alignment boundary or the end.
 187   for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)
 188     if (uint8_t V = *P)
 189       Handle8bitCounter(FirstFeature, P - Begin, V);
 190
 191   // Iterate by Step bytes at a time.
 192   for (; P < End; P += Step)
 193     if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P))
 194       for (size_t I = 0; I < Step; I++, Bundle >>= 8)
 195         if (uint8_t V = Bundle & 0xff)
 196           Handle8bitCounter(FirstFeature, P - Begin + I, V);
 197
 198   // Iterate by 1 byte until the end.
 199   for (; P < End; P++)
 200     if (uint8_t V = *P)
 201       Handle8bitCounter(FirstFeature, P - Begin, V);
 202 }
 203
 204 // Given a non-zero Counter returns a number in the range [0,7].
 205 template<class T>
 206 unsigned CounterToFeature(T Counter) {
 207     // Returns a feature number by placing Counters into buckets as illustrated
 208     // below.
 209     //
 210     // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]
 211     // Feature number:  0   1   2    3     4       5       6       7
 212     //
 213     // This is a heuristic taken from AFL (see
 214     // http://lcamtuf.coredump.cx/afl/technical_details.txt).
 215     //
 216     // This implementation may change in the future so clients should
 217     // not rely on it.
 218     assert(Counter);
 219     unsigned Bit = 0;
 220     /**/ if (Counter >= 128) Bit = 7;
 221     else if (Counter >= 32) Bit = 6;
 222     else if (Counter >= 16) Bit = 5;
 223     else if (Counter >= 8) Bit = 4;
 224     else if (Counter >= 4) Bit = 3;
 225     else if (Counter >= 3) Bit = 2;
 226     else if (Counter >= 2) Bit = 1;
 227     return Bit;
 228 }
 229
 230 template <class Callback>  // void Callback(size_t Feature)
 231 ATTRIBUTE_NO_SANITIZE_ADDRESS
 232 __attribute__((noinline))
 233 void TracePC::CollectFeatures(Callback HandleFeature) const {
 234   uint8_t *Counters = this->Counters();
 235   size_t N = GetNumPCs();
 236   auto Handle8bitCounter = [&](size_t FirstFeature,
 237                                size_t Idx, uint8_t Counter) {
 238     if (UseCounters)
 239       HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
 240     else
 241       HandleFeature(FirstFeature + Idx);
 242   };
 243
 244   size_t FirstFeature = 0;
 245
 246   if (!NumInline8bitCounters) {
 247     ForEachNonZeroByte(Counters, Counters + N, FirstFeature, Handle8bitCounter);
 248     FirstFeature += N * 8;
 249   }
 250
 251   if (NumInline8bitCounters) {
 252     for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) {
 253       ForEachNonZeroByte(ModuleCounters[i].Start, ModuleCounters[i].Stop,
 254                          FirstFeature, Handle8bitCounter);
 255       FirstFeature += 8 * (ModuleCounters[i].Stop - ModuleCounters[i].Start);
 256     }
 257   }
 258
 259   ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature,
 260                      Handle8bitCounter);
 261   FirstFeature += (ExtraCountersEnd() - ExtraCountersBegin()) * 8;
 262
 263   if (UseValueProfileMask) {
 264     ValueProfileMap.ForEach([&](size_t Idx) {
 265       HandleFeature(FirstFeature + Idx);
 266     });
 267     FirstFeature += ValueProfileMap.SizeInBits();
 268   }
 269
 270   // Step function, grows similar to 8 * Log_2(A).
 271   auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
 272     if (!A) return A;
 273     uint32_t Log2 = Log(A);
 274     if (Log2 < 3) return A;
 275     Log2 -= 3;
 276     return (Log2 + 1) * 8 + ((A >> Log2) & 7);
 277   };
 278   assert(StackDepthStepFunction(1024) == 64);
 279   assert(StackDepthStepFunction(1024 * 4) == 80);
 280   assert(StackDepthStepFunction(1024 * 1024) == 144);
 281
 282   if (auto MaxStackOffset = GetMaxStackOffset())
 283     HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
 284 }
 285
 286 extern TracePC TPC;
 287
 288 }  // namespace fuzzer
 289
 290 #endif  // LLVM_FUZZER_TRACE_PC