FuzzerTracePC.h revision 360784 
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
21namespace 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.
30template<class T, size_t kSizeT>
31struct 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
48template <size_t kSizeT>
49struct 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
70class 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  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
131private:
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
181template <class Callback>
182// void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
183ATTRIBUTE_NO_SANITIZE_ALL
184size_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      for (size_t I = 0; I < Step; I++, Bundle >>= 8)
199        if (uint8_t V = Bundle & 0xff)
200          Handle8bitCounter(FirstFeature, P - Begin + I, V);
201
202  // Iterate by 1 byte until the end.
203  for (; P < End; P++)
204    if (uint8_t V = *P)
205      Handle8bitCounter(FirstFeature, P - Begin, V);
206  return End - Begin;
207}
208
209// Given a non-zero Counter returns a number in the range [0,7].
210template<class T>
211unsigned CounterToFeature(T Counter) {
212    // Returns a feature number by placing Counters into buckets as illustrated
213    // below.
214    //
215    // Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]
216    // Feature number:  0   1   2    3     4       5       6       7
217    //
218    // This is a heuristic taken from AFL (see
219    // http://lcamtuf.coredump.cx/afl/technical_details.txt).
220    //
221    // This implementation may change in the future so clients should
222    // not rely on it.
223    assert(Counter);
224    unsigned Bit = 0;
225    /**/ if (Counter >= 128) Bit = 7;
226    else if (Counter >= 32) Bit = 6;
227    else if (Counter >= 16) Bit = 5;
228    else if (Counter >= 8) Bit = 4;
229    else if (Counter >= 4) Bit = 3;
230    else if (Counter >= 3) Bit = 2;
231    else if (Counter >= 2) Bit = 1;
232    return Bit;
233}
234
235template <class Callback>  // void Callback(size_t Feature)
236ATTRIBUTE_NO_SANITIZE_ADDRESS
237ATTRIBUTE_NOINLINE
238void TracePC::CollectFeatures(Callback HandleFeature) const {
239  auto Handle8bitCounter = [&](size_t FirstFeature,
240                               size_t Idx, uint8_t Counter) {
241    if (UseCounters)
242      HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
243    else
244      HandleFeature(FirstFeature + Idx);
245  };
246
247  size_t FirstFeature = 0;
248
249  for (size_t i = 0; i < NumModules; i++) {
250    for (size_t r = 0; r < Modules[i].NumRegions; r++) {
251      if (!Modules[i].Regions[r].Enabled) continue;
252      FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,
253                                             Modules[i].Regions[r].Stop,
254                                             FirstFeature, Handle8bitCounter);
255    }
256  }
257
258  FirstFeature +=
259      8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),
260                             FirstFeature, Handle8bitCounter);
261
262  if (UseValueProfileMask) {
263    ValueProfileMap.ForEach([&](size_t Idx) {
264      HandleFeature(FirstFeature + Idx);
265    });
266    FirstFeature += ValueProfileMap.SizeInBits();
267  }
268
269  // Step function, grows similar to 8 * Log_2(A).
270  auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
271    if (!A) return A;
272    uint32_t Log2 = Log(A);
273    if (Log2 < 3) return A;
274    Log2 -= 3;
275    return (Log2 + 1) * 8 + ((A >> Log2) & 7);
276  };
277  assert(StackDepthStepFunction(1024) == 64);
278  assert(StackDepthStepFunction(1024 * 4) == 80);
279  assert(StackDepthStepFunction(1024 * 1024) == 144);
280
281  if (auto MaxStackOffset = GetMaxStackOffset())
282    HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
283}
284
285extern TracePC TPC;
286
287}  // namespace fuzzer
288
289#endif  // LLVM_FUZZER_TRACE_PC
290