Home | History | Annotate | Line # | Download | only in fuzzer 
      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   bool UpdateUnstableCounters(int UnstableMode);
    147   void UpdateAndApplyUnstableCounters(int UnstableMode);
    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
    311