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
  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   static const size_t kNumPCs = 1 << 21;
  73   // How many bits of PC are used from __sanitizer_cov_trace_pc.
  74   static const size_t kTracePcBits = 18;
  75
  76   void HandleInit(uint32_t *Start, uint32_t *Stop);
  77   void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop);
  78   void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
  79   template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2);
  80   size_t GetTotalPCCoverage();
  81   void SetUseCounters(bool UC) { UseCounters = UC; }
  82   void SetUseValueProfile(bool VP) { UseValueProfile = VP; }
  83   void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
  84   template <class Callback> void CollectFeatures(Callback CB) const;
  85
  86   void ResetMaps() {
  87     ValueProfileMap.Reset();
  88     memset(Counters(), 0, GetNumPCs());
  89     ClearExtraCounters();
  90   }
  91
  92   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
  93   void PrintFeatureSet();
  94
  95   void PrintModuleInfo();
  96
  97   void PrintCoverage();
  98   void DumpCoverage();
  99
 100   void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
 101                          size_t n, bool StopAtZero);
 102
 103   TableOfRecentCompares<uint32_t, 32> TORC4;
 104   TableOfRecentCompares<uint64_t, 32> TORC8;
 105   TableOfRecentCompares<Word, 32> TORCW;
 106   MemMemTable<1024> MMT;
 107
 108   void PrintNewPCs();
 109   void InitializePrintNewPCs();
 110   size_t GetNumPCs() const {
 111     return NumGuards == 0 ? (1 << kTracePcBits) : Min(kNumPCs, NumGuards + 1);
 112   }
 113   uintptr_t GetPC(size_t Idx) {
 114     assert(Idx < GetNumPCs());
 115     return PCs()[Idx];
 116   }
 117
 118 private:
 119   bool UseCounters = false;
 120   bool UseValueProfile = false;
 121   bool DoPrintNewPCs = false;
 122
 123   struct Module {
 124     uint32_t *Start, *Stop;
 125   };
 126
 127   Module Modules[4096];
 128   size_t NumModules;  // linker-initialized.
 129   size_t NumGuards;  // linker-initialized.
 130
 131   struct { uint8_t *Start, *Stop; } ModuleCounters[4096];
 132   size_t NumModulesWithInline8bitCounters;  // linker-initialized.
 133   size_t NumInline8bitCounters;
 134
 135   uint8_t *Counters() const;
 136   uintptr_t *PCs() const;
 137
 138   std::set<uintptr_t> *PrintedPCs;
 139
 140   ValueBitMap ValueProfileMap;
 141 };
 142
 143 template <class Callback> // void Callback(size_t Idx, uint8_t Value);
 144 ATTRIBUTE_NO_SANITIZE_ALL
 145 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
 146                         size_t FirstFeature, Callback Handle8bitCounter) {
 147   typedef uintptr_t LargeType;
 148   const size_t Step = sizeof(LargeType) / sizeof(uint8_t);
 149   const size_t StepMask = Step - 1;
 150   auto P = Begin;
 151   // Iterate by 1 byte until either the alignment boundary or the end.
 152   for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)
 153     if (uint8_t V = *P)
 154       Handle8bitCounter(FirstFeature + P - Begin, V);
 155
 156   // Iterate by Step bytes at a time.
 157   for (; P < End; P += Step)
 158     if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P))
 159       for (size_t I = 0; I < Step; I++, Bundle >>= 8)
 160         if (uint8_t V = Bundle & 0xff)
 161           Handle8bitCounter(FirstFeature + P - Begin + I, V);
 162
 163   // Iterate by 1 byte until the end.
 164   for (; P < End; P++)
 165     if (uint8_t V = *P)
 166       Handle8bitCounter(FirstFeature + P - Begin, V);
 167 }
 168
 169 template <class Callback>  // bool Callback(size_t Feature)
 170 ATTRIBUTE_NO_SANITIZE_ALL
 171 __attribute__((noinline))
 172 void TracePC::CollectFeatures(Callback HandleFeature) const {
 173   uint8_t *Counters = this->Counters();
 174   size_t N = GetNumPCs();
 175   auto Handle8bitCounter = [&](size_t Idx, uint8_t Counter) {
 176     assert(Counter);
 177     unsigned Bit = 0;
 178     /**/ if (Counter >= 128) Bit = 7;
 179     else if (Counter >= 32) Bit = 6;
 180     else if (Counter >= 16) Bit = 5;
 181     else if (Counter >= 8) Bit = 4;
 182     else if (Counter >= 4) Bit = 3;
 183     else if (Counter >= 3) Bit = 2;
 184     else if (Counter >= 2) Bit = 1;
 185     HandleFeature(Idx * 8 + Bit);
 186   };
 187
 188   size_t FirstFeature = 0;
 189   ForEachNonZeroByte(Counters, Counters + N, FirstFeature, Handle8bitCounter);
 190   FirstFeature += N * 8;
 191   for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) {
 192     ForEachNonZeroByte(ModuleCounters[i].Start, ModuleCounters[i].Stop,
 193                        FirstFeature, Handle8bitCounter);
 194     FirstFeature += 8 * (ModuleCounters[i].Stop - ModuleCounters[i].Start);
 195   }
 196
 197   ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature,
 198                      Handle8bitCounter);
 199
 200   if (UseValueProfile)
 201     ValueProfileMap.ForEach([&](size_t Idx) {
 202       HandleFeature(N * 8 + Idx);
 203     });
 204 }
 205
 206 extern TracePC TPC;
 207
 208 }  // namespace fuzzer
 209
 210 #endif  // LLVM_FUZZER_TRACE_PC