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