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