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
19namespace 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.
28template<class T, size_t kSizeT>
29struct TableOfRecentCompares {
30  static const size_t kSize = kSizeT;
31  struct Pair {
32    T A, B;
33  };
34  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
40  Pair Get(size_t I) { return Table[I % kSize]; }
41
42  Pair Table[kSize];
43};
44
45class 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);
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();
55  void SetUseCounters(bool UC) { UseCounters = UC; }
56  void SetUseValueProfile(bool VP) { UseValueProfile = VP; }
57  void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
58  template <class Callback> size_t CollectFeatures(Callback CB);
59  bool UpdateValueProfileMap(ValueBitMap *MaxValueProfileMap) {
60    return UseValueProfile && MaxValueProfileMap->MergeFrom(ValueProfileMap);
61  }
62
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
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();
88  size_t GetNumPCs() const { return Min(kNumPCs, NumGuards + 1); }
89  uintptr_t GetPC(size_t Idx) {
90    assert(Idx < GetNumPCs());
91    return PCs[Idx];
92  }
93
94private:
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
118template <class Callback>
119size_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
154extern TracePC TPC;
155
156}  // namespace fuzzer
157
158#endif  // LLVM_FUZZER_TRACE_PC
159