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
mask(BlockVerifier::State S)17 constexpr unsigned long long mask(BlockVerifier::State S) {
18 return 1uLL << static_cast<std::size_t>(S);
19 }
20
number(BlockVerifier::State S)21 constexpr std::size_t number(BlockVerifier::State S) {
22 return static_cast<std::size_t>(S);
23 }
24
recordToString(BlockVerifier::State R)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
transition(State To)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
visit(BufferExtents &)138 Error BlockVerifier::visit(BufferExtents &) {
139 return transition(State::BufferExtents);
140 }
141
visit(WallclockRecord &)142 Error BlockVerifier::visit(WallclockRecord &) {
143 return transition(State::WallClockTime);
144 }
145
visit(NewCPUIDRecord &)146 Error BlockVerifier::visit(NewCPUIDRecord &) {
147 return transition(State::NewCPUId);
148 }
149
visit(TSCWrapRecord &)150 Error BlockVerifier::visit(TSCWrapRecord &) {
151 return transition(State::TSCWrap);
152 }
153
visit(CustomEventRecord &)154 Error BlockVerifier::visit(CustomEventRecord &) {
155 return transition(State::CustomEvent);
156 }
157
visit(CustomEventRecordV5 &)158 Error BlockVerifier::visit(CustomEventRecordV5 &) {
159 return transition(State::CustomEvent);
160 }
161
visit(TypedEventRecord &)162 Error BlockVerifier::visit(TypedEventRecord &) {
163 return transition(State::TypedEvent);
164 }
165
visit(CallArgRecord &)166 Error BlockVerifier::visit(CallArgRecord &) {
167 return transition(State::CallArg);
168 }
169
visit(PIDRecord &)170 Error BlockVerifier::visit(PIDRecord &) { return transition(State::PIDEntry); }
171
visit(NewBufferRecord &)172 Error BlockVerifier::visit(NewBufferRecord &) {
173 return transition(State::NewBuffer);
174 }
175
visit(EndBufferRecord &)176 Error BlockVerifier::visit(EndBufferRecord &) {
177 return transition(State::EndOfBuffer);
178 }
179
visit(FunctionRecord &)180 Error BlockVerifier::visit(FunctionRecord &) {
181 return transition(State::Function);
182 }
183
verify()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
reset()203 void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
204
205 } // namespace xray
206 } // namespace llvm
207