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    auto 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> size_t 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
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  std::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 + Step <= 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].
212template<class T>
213unsigned 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
237template <class Callback> // void Callback(uint32_t Feature)
238ATTRIBUTE_NO_SANITIZE_ADDRESS ATTRIBUTE_NOINLINE size_t
239TracePC::CollectFeatures(Callback HandleFeature) const {
240  auto Handle8bitCounter = [&](size_t FirstFeature,
241                               size_t Idx, uint8_t Counter) {
242    if (UseCounters)
243      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx * 8 +
244                                          CounterToFeature(Counter)));
245    else
246      HandleFeature(static_cast<uint32_t>(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(static_cast<uint32_t>(FirstFeature + Idx));
267    });
268    FirstFeature += ValueProfileMap.SizeInBits();
269  }
270
271  // Step function, grows similar to 8 * Log_2(A).
272  auto StackDepthStepFunction = [](size_t A) -> size_t {
273    if (!A)
274      return A;
275    auto Log2 = Log(A);
276    if (Log2 < 3)
277      return A;
278    Log2 -= 3;
279    return (Log2 + 1) * 8 + ((A >> Log2) & 7);
280  };
281  assert(StackDepthStepFunction(1024) == 64);
282  assert(StackDepthStepFunction(1024 * 4) == 80);
283  assert(StackDepthStepFunction(1024 * 1024) == 144);
284
285  if (auto MaxStackOffset = GetMaxStackOffset()) {
286    HandleFeature(static_cast<uint32_t>(
287        FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)));
288    FirstFeature += StackDepthStepFunction(std::numeric_limits<size_t>::max());
289  }
290
291  return FirstFeature;
292}
293
294extern TracePC TPC;
295
296}  // namespace fuzzer
297
298#endif  // LLVM_FUZZER_TRACE_PC
299