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(a: Size, b: 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(B: nullptr, S: 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(X: 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(X: 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