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