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 "FuzzerValueBitMap.h"
17 #include <set>
18
19 namespace fuzzer {
20
21 // TableOfRecentCompares (TORC) remembers the most recently performed
22 // comparisons of type T.
23 // We record the arguments of CMP instructions in this table unconditionally
24 // because it seems cheaper this way than to compute some expensive
25 // conditions inside __sanitizer_cov_trace_cmp*.
26 // After the unit has been executed we may decide to use the contents of
27 // this table to populate a Dictionary.
28 template<class T, size_t kSizeT>
29 struct TableOfRecentCompares {
30 static const size_t kSize = kSizeT;
31 struct Pair {
32 T A, B;
33 };
InsertTableOfRecentCompares34 void Insert(size_t Idx, T Arg1, T Arg2) {
35 Idx = Idx % kSize;
36 Table[Idx].A = Arg1;
37 Table[Idx].B = Arg2;
38 }
39
GetTableOfRecentCompares40 Pair Get(size_t I) { return Table[I % kSize]; }
41
42 Pair Table[kSize];
43 };
44
45 class TracePC {
46 public:
47 static const size_t kFeatureSetSize = ValueBitMap::kNumberOfItems;
48
49 void HandleTrace(uint32_t *guard, uintptr_t PC);
50 void HandleInit(uint32_t *start, uint32_t *stop);
51 void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
HandleValueProfile(size_t Value)52 void HandleValueProfile(size_t Value) { ValueProfileMap.AddValue(Value); }
53 template <class T> void HandleCmp(void *PC, T Arg1, T Arg2);
54 size_t GetTotalPCCoverage();
SetUseCounters(bool UC)55 void SetUseCounters(bool UC) { UseCounters = UC; }
SetUseValueProfile(bool VP)56 void SetUseValueProfile(bool VP) { UseValueProfile = VP; }
SetPrintNewPCs(bool P)57 void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
58 template <class Callback> size_t CollectFeatures(Callback CB);
UpdateValueProfileMap(ValueBitMap * MaxValueProfileMap)59 bool UpdateValueProfileMap(ValueBitMap *MaxValueProfileMap) {
60 return UseValueProfile && MaxValueProfileMap->MergeFrom(ValueProfileMap);
61 }
62
ResetMaps()63 void ResetMaps() {
64 ValueProfileMap.Reset();
65 memset(Counters, 0, sizeof(Counters));
66 }
67
68 void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
69 void PrintFeatureSet();
70
71 void PrintModuleInfo();
72
73 void PrintCoverage();
74 void DumpCoverage();
75
76 void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
77 size_t n);
78 void AddValueForStrcmp(void *caller_pc, const char *s1, const char *s2,
79 size_t n);
80
UsingTracePcGuard()81 bool UsingTracePcGuard() const {return NumModules; }
82
83 static const size_t kTORCSize = 1 << 5;
84 TableOfRecentCompares<uint32_t, kTORCSize> TORC4;
85 TableOfRecentCompares<uint64_t, kTORCSize> TORC8;
86
87 void PrintNewPCs();
GetNumPCs()88 size_t GetNumPCs() const { return Min(kNumPCs, NumGuards + 1); }
GetPC(size_t Idx)89 uintptr_t GetPC(size_t Idx) {
90 assert(Idx < GetNumPCs());
91 return PCs[Idx];
92 }
93
94 private:
95 bool UseCounters = false;
96 bool UseValueProfile = false;
97 bool DoPrintNewPCs = false;
98
99 struct Module {
100 uint32_t *Start, *Stop;
101 };
102
103 Module Modules[4096];
104 size_t NumModules; // linker-initialized.
105 size_t NumGuards; // linker-initialized.
106
107 static const size_t kNumCounters = 1 << 14;
108 alignas(8) uint8_t Counters[kNumCounters];
109
110 static const size_t kNumPCs = 1 << 24;
111 uintptr_t PCs[kNumPCs];
112
113 std::set<uintptr_t> *PrintedPCs;
114
115 ValueBitMap ValueProfileMap;
116 };
117
118 template <class Callback>
CollectFeatures(Callback CB)119 size_t TracePC::CollectFeatures(Callback CB) {
120 if (!UsingTracePcGuard()) return 0;
121 size_t Res = 0;
122 const size_t Step = 8;
123 assert(reinterpret_cast<uintptr_t>(Counters) % Step == 0);
124 size_t N = Min(kNumCounters, NumGuards + 1);
125 N = (N + Step - 1) & ~(Step - 1); // Round up.
126 for (size_t Idx = 0; Idx < N; Idx += Step) {
127 uint64_t Bundle = *reinterpret_cast<uint64_t*>(&Counters[Idx]);
128 if (!Bundle) continue;
129 for (size_t i = Idx; i < Idx + Step; i++) {
130 uint8_t Counter = (Bundle >> ((i - Idx) * 8)) & 0xff;
131 if (!Counter) continue;
132 Counters[i] = 0;
133 unsigned Bit = 0;
134 /**/ if (Counter >= 128) Bit = 7;
135 else if (Counter >= 32) Bit = 6;
136 else if (Counter >= 16) Bit = 5;
137 else if (Counter >= 8) Bit = 4;
138 else if (Counter >= 4) Bit = 3;
139 else if (Counter >= 3) Bit = 2;
140 else if (Counter >= 2) Bit = 1;
141 size_t Feature = (i * 8 + Bit);
142 if (CB(Feature))
143 Res++;
144 }
145 }
146 if (UseValueProfile)
147 ValueProfileMap.ForEach([&](size_t Idx) {
148 if (CB(NumGuards * 8 + Idx))
149 Res++;
150 });
151 return Res;
152 }
153
154 extern TracePC TPC;
155
156 } // namespace fuzzer
157
158 #endif // LLVM_FUZZER_TRACE_PC
159