1 //===- BlockVerifier.cpp - FDR Block Verifier -----------------------------===//
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 #include "llvm/XRay/BlockVerifier.h"
10 #include "llvm/Support/Error.h"
11 
12 namespace llvm {
13 namespace xray {
14 namespace {
15 
16 constexpr unsigned long long mask(BlockVerifier::State S) {
17   return 1uLL << static_cast<std::size_t>(S);
18 }
19 
20 constexpr std::size_t number(BlockVerifier::State S) {
21   return static_cast<std::size_t>(S);
22 }
23 
24 StringRef recordToString(BlockVerifier::State R) {
25   switch (R) {
26   case BlockVerifier::State::BufferExtents:
27     return "BufferExtents";
28   case BlockVerifier::State::NewBuffer:
29     return "NewBuffer";
30   case BlockVerifier::State::WallClockTime:
31     return "WallClockTime";
32   case BlockVerifier::State::PIDEntry:
33     return "PIDEntry";
34   case BlockVerifier::State::NewCPUId:
35     return "NewCPUId";
36   case BlockVerifier::State::TSCWrap:
37     return "TSCWrap";
38   case BlockVerifier::State::CustomEvent:
39     return "CustomEvent";
40   case BlockVerifier::State::Function:
41     return "Function";
42   case BlockVerifier::State::CallArg:
43     return "CallArg";
44   case BlockVerifier::State::EndOfBuffer:
45     return "EndOfBuffer";
46   case BlockVerifier::State::TypedEvent:
47     return "TypedEvent";
48   case BlockVerifier::State::StateMax:
49   case BlockVerifier::State::Unknown:
50     return "Unknown";
51   }
52   llvm_unreachable("Unkown state!");
53 }
54 
55 struct Transition {
56   BlockVerifier::State From;
57   std::bitset<number(BlockVerifier::State::StateMax)> ToStates;
58 };
59 
60 } // namespace
61 
62 Error BlockVerifier::transition(State To) {
63   using ToSet = std::bitset<number(State::StateMax)>;
64   static constexpr std::array<const Transition, number(State::StateMax)>
65       TransitionTable{{{State::Unknown,
66                         {mask(State::BufferExtents) | mask(State::NewBuffer)}},
67 
68                        {State::BufferExtents, {mask(State::NewBuffer)}},
69 
70                        {State::NewBuffer, {mask(State::WallClockTime)}},
71 
72                        {State::WallClockTime,
73                         {mask(State::PIDEntry) | mask(State::NewCPUId)}},
74 
75                        {State::PIDEntry, {mask(State::NewCPUId)}},
76 
77                        {State::NewCPUId,
78                         {mask(State::NewCPUId) | mask(State::TSCWrap) |
79                          mask(State::CustomEvent) | mask(State::Function) |
80                          mask(State::EndOfBuffer) | mask(State::TypedEvent)}},
81 
82                        {State::TSCWrap,
83                         {mask(State::TSCWrap) | mask(State::NewCPUId) |
84                          mask(State::CustomEvent) | mask(State::Function) |
85                          mask(State::EndOfBuffer) | mask(State::TypedEvent)}},
86 
87                        {State::CustomEvent,
88                         {mask(State::CustomEvent) | mask(State::TSCWrap) |
89                          mask(State::NewCPUId) | mask(State::Function) |
90                          mask(State::EndOfBuffer) | mask(State::TypedEvent)}},
91 
92                        {State::TypedEvent,
93                         {mask(State::TypedEvent) | mask(State::TSCWrap) |
94                          mask(State::NewCPUId) | mask(State::Function) |
95                          mask(State::EndOfBuffer) | mask(State::CustomEvent)}},
96 
97                        {State::Function,
98                         {mask(State::Function) | mask(State::TSCWrap) |
99                          mask(State::NewCPUId) | mask(State::CustomEvent) |
100                          mask(State::CallArg) | mask(State::EndOfBuffer) |
101                          mask(State::TypedEvent)}},
102 
103                        {State::CallArg,
104                         {mask(State::CallArg) | mask(State::Function) |
105                          mask(State::TSCWrap) | mask(State::NewCPUId) |
106                          mask(State::CustomEvent) | mask(State::EndOfBuffer) |
107                          mask(State::TypedEvent)}},
108 
109                        {State::EndOfBuffer, {}}}};
110 
111   if (CurrentRecord >= State::StateMax)
112     return createStringError(
113         std::make_error_code(std::errc::executable_format_error),
114         "BUG (BlockVerifier): Cannot find transition table entry for %s, "
115         "transitioning to %s.",
116         recordToString(CurrentRecord).data(), recordToString(To).data());
117 
118   // If we're at an EndOfBuffer record, we ignore anything that follows that
119   // isn't a NewBuffer record.
120   if (CurrentRecord == State::EndOfBuffer && To != State::NewBuffer)
121     return Error::success();
122 
123   auto &Mapping = TransitionTable[number(CurrentRecord)];
124   auto &Destinations = Mapping.ToStates;
125   assert(Mapping.From == CurrentRecord &&
126          "BUG: Wrong index for record mapping.");
127   if ((Destinations & ToSet(mask(To))) == 0)
128     return createStringError(
129         std::make_error_code(std::errc::executable_format_error),
130         "BlockVerifier: Invalid transition from %s to %s.",
131         recordToString(CurrentRecord).data(), recordToString(To).data());
132 
133   CurrentRecord = To;
134   return Error::success();
135 } // namespace xray
136 
137 Error BlockVerifier::visit(BufferExtents &) {
138   return transition(State::BufferExtents);
139 }
140 
141 Error BlockVerifier::visit(WallclockRecord &) {
142   return transition(State::WallClockTime);
143 }
144 
145 Error BlockVerifier::visit(NewCPUIDRecord &) {
146   return transition(State::NewCPUId);
147 }
148 
149 Error BlockVerifier::visit(TSCWrapRecord &) {
150   return transition(State::TSCWrap);
151 }
152 
153 Error BlockVerifier::visit(CustomEventRecord &) {
154   return transition(State::CustomEvent);
155 }
156 
157 Error BlockVerifier::visit(CustomEventRecordV5 &) {
158   return transition(State::CustomEvent);
159 }
160 
161 Error BlockVerifier::visit(TypedEventRecord &) {
162   return transition(State::TypedEvent);
163 }
164 
165 Error BlockVerifier::visit(CallArgRecord &) {
166   return transition(State::CallArg);
167 }
168 
169 Error BlockVerifier::visit(PIDRecord &) { return transition(State::PIDEntry); }
170 
171 Error BlockVerifier::visit(NewBufferRecord &) {
172   return transition(State::NewBuffer);
173 }
174 
175 Error BlockVerifier::visit(EndBufferRecord &) {
176   return transition(State::EndOfBuffer);
177 }
178 
179 Error BlockVerifier::visit(FunctionRecord &) {
180   return transition(State::Function);
181 }
182 
183 Error BlockVerifier::verify() {
184   // The known terminal conditions are the following:
185   switch (CurrentRecord) {
186   case State::EndOfBuffer:
187   case State::NewCPUId:
188   case State::CustomEvent:
189   case State::TypedEvent:
190   case State::Function:
191   case State::CallArg:
192   case State::TSCWrap:
193     return Error::success();
194   default:
195     return createStringError(
196         std::make_error_code(std::errc::executable_format_error),
197         "BlockVerifier: Invalid terminal condition %s, malformed block.",
198         recordToString(CurrentRecord).data());
199   }
200 }
201 
202 void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
203 
204 } // namespace xray
205 } // namespace llvm
206