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

   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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // fuzzer::TracePC
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef LLVM_FUZZER_TRACE_PC
  12 #define LLVM_FUZZER_TRACE_PC
  13
  14 #include "FuzzerDefs.h"
  15 #include "FuzzerDictionary.h"
  16 #include "FuzzerValueBitMap.h"
  17
  18 #include <set>
  19 #include <unordered_map>
  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   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> void 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();
  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   void ProtectLazyCounters();
 123   bool UnprotectLazyCounters(void *CounterPtr);
 124
 125   struct PCTableEntry {
 126     uintptr_t PC, PCFlags;
 127   };
 128
 129   uintptr_t PCTableEntryIdx(const PCTableEntry *TE);
 130   const PCTableEntry *PCTableEntryByIdx(uintptr_t Idx);
 131   static uintptr_t GetNextInstructionPc(uintptr_t PC);
 132   bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; }
 133
 134 private:
 135   bool UseCounters = false;
 136   uint32_t UseValueProfileMask = false;
 137   bool DoPrintNewPCs = false;
 138   size_t NumPrintNewFuncs = 0;
 139
 140   // Module represents the array of 8-bit counters split into regions
 141   // such that every region, except maybe the first and the last one, is one
 142   // full page.
 143   struct Module {
 144     struct Region {
 145       uint8_t *Start, *Stop;
 146       bool Enabled;
 147       bool OneFullPage;
 148     };
 149     Region *Regions;
 150     size_t NumRegions;
 151     uint8_t *Start() { return Regions[0].Start; }
 152     uint8_t *Stop()  { return Regions[NumRegions - 1].Stop; }
 153     size_t Size()   { return Stop() - Start(); }
 154     size_t  Idx(uint8_t *P) {
 155       assert(P >= Start() && P < Stop());
 156       return P - Start();
 157     }
 158   };
 159
 160   Module Modules[4096];
 161   size_t NumModules;  // linker-initialized.
 162   size_t NumInline8bitCounters;
 163
 164   template <class Callback>
 165   void IterateCounterRegions(Callback CB) {
 166     for (size_t m = 0; m < NumModules; m++)
 167       for (size_t r = 0; r < Modules[m].NumRegions; r++)
 168         CB(Modules[m].Regions[r]);
 169   }
 170
 171   struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];
 172   size_t NumPCTables;
 173   size_t NumPCsInPCTables;
 174
 175   Set<const PCTableEntry*> ObservedPCs;
 176   std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs;  // PC => Counter.
 177
 178   uint8_t *FocusFunctionCounterPtr = nullptr;
 179
 180   ValueBitMap ValueProfileMap;
 181   uintptr_t InitialStack;
 182 };
 183
 184 template <class Callback>
 185 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
 186 ATTRIBUTE_NO_SANITIZE_ALL
 187 size_t ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
 188                         size_t FirstFeature, Callback Handle8bitCounter) {
 189   typedef uintptr_t LargeType;
 190   const size_t Step = sizeof(LargeType) / sizeof(uint8_t);
 191   const size_t StepMask = Step - 1;
 192   auto P = Begin;
 193   // Iterate by 1 byte until either the alignment boundary or the end.
 194   for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)
 195     if (uint8_t V = *P)
 196       Handle8bitCounter(FirstFeature, P - Begin, V);
 197
 198   // Iterate by Step bytes at a time.
 199   for (; P < End; P += Step)
 200     if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P))
 201       for (size_t I = 0; I < Step; I++, Bundle >>= 8)
 202         if (uint8_t V = Bundle & 0xff)
 203           Handle8bitCounter(FirstFeature, P - Begin + I, V);
 204
 205   // Iterate by 1 byte until the end.
 206   for (; P < End; P++)
 207     if (uint8_t V = *P)
 208       Handle8bitCounter(FirstFeature, P - Begin, V);
 209   return End - Begin;
 210 }
 211
 212 // Given a non-zero Counter returns a number in the range [0,7].
 213 template<class T>
 214 unsigned CounterToFeature(T Counter) {
 215     // Returns a feature number by placing Counters into buckets as illustrated
 216     // below.
 217     //
 218     // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]
 219     // Feature number:  0   1   2    3     4       5       6       7
 220     //
 221     // This is a heuristic taken from AFL (see
 222     // http://lcamtuf.coredump.cx/afl/technical_details.txt).
 223     //
 224     // This implementation may change in the future so clients should
 225     // not rely on it.
 226     assert(Counter);
 227     unsigned Bit = 0;
 228     /**/ if (Counter >= 128) Bit = 7;
 229     else if (Counter >= 32) Bit = 6;
 230     else if (Counter >= 16) Bit = 5;
 231     else if (Counter >= 8) Bit = 4;
 232     else if (Counter >= 4) Bit = 3;
 233     else if (Counter >= 3) Bit = 2;
 234     else if (Counter >= 2) Bit = 1;
 235     return Bit;
 236 }
 237
 238 template <class Callback>  // void Callback(size_t Feature)
 239 ATTRIBUTE_NO_SANITIZE_ADDRESS
 240 ATTRIBUTE_NOINLINE
 241 void TracePC::CollectFeatures(Callback HandleFeature) const {
 242   auto Handle8bitCounter = [&](size_t FirstFeature,
 243                                size_t Idx, uint8_t Counter) {
 244     if (UseCounters)
 245       HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
 246     else
 247       HandleFeature(FirstFeature + Idx);
 248   };
 249
 250   size_t FirstFeature = 0;
 251
 252   for (size_t i = 0; i < NumModules; i++) {
 253     for (size_t r = 0; r < Modules[i].NumRegions; r++) {
 254       if (!Modules[i].Regions[r].Enabled) continue;
 255       FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,
 256                                              Modules[i].Regions[r].Stop,
 257                                              FirstFeature, Handle8bitCounter);
 258     }
 259   }
 260
 261   FirstFeature +=
 262       8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),
 263                              FirstFeature, Handle8bitCounter);
 264
 265   if (UseValueProfileMask) {
 266     ValueProfileMap.ForEach([&](size_t Idx) {
 267       HandleFeature(FirstFeature + Idx);
 268     });
 269     FirstFeature += ValueProfileMap.SizeInBits();
 270   }
 271
 272   // Step function, grows similar to 8 * Log_2(A).
 273   auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
 274     if (!A) return A;
 275     uint32_t Log2 = Log(A);
 276     if (Log2 < 3) return A;
 277     Log2 -= 3;
 278     return (Log2 + 1) * 8 + ((A >> Log2) & 7);
 279   };
 280   assert(StackDepthStepFunction(1024) == 64);
 281   assert(StackDepthStepFunction(1024 * 4) == 80);
 282   assert(StackDepthStepFunction(1024 * 1024) == 144);
 283
 284   if (auto MaxStackOffset = GetMaxStackOffset())
 285     HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
 286 }
 287
 288 extern TracePC TPC;
 289
 290 }  // namespace fuzzer
 291
 292 #endif  // LLVM_FUZZER_TRACE_PC