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
13namespace llvm {
14namespace xray {
15namespace {
16
17constexpr unsigned long long mask(BlockVerifier::State S) {
18 return 1uLL << static_cast<std::size_t>(S);
19}
20
21constexpr std::size_t number(BlockVerifier::State S) {
22 return static_cast<std::size_t>(S);
23}
24
25StringRef 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
56struct Transition {
57 BlockVerifier::State From;
58 std::bitset<number(S: BlockVerifier::State::StateMax)> ToStates;
59};
60
61} // namespace
62
63Error BlockVerifier::transition(State To) {
64 using ToSet = std::bitset<number(S: State::StateMax)>;
65 static constexpr std::array<const Transition, number(S: State::StateMax)>
66 TransitionTable{._M_elems: {{.From: State::Unknown,
67 .ToStates: {mask(S: State::BufferExtents) | mask(S: State::NewBuffer)}},
68
69 {.From: State::BufferExtents, .ToStates: {mask(S: State::NewBuffer)}},
70
71 {.From: State::NewBuffer, .ToStates: {mask(S: State::WallClockTime)}},
72
73 {.From: State::WallClockTime,
74 .ToStates: {mask(S: State::PIDEntry) | mask(S: State::NewCPUId)}},
75
76 {.From: State::PIDEntry, .ToStates: {mask(S: State::NewCPUId)}},
77
78 {.From: State::NewCPUId,
79 .ToStates: {mask(S: State::NewCPUId) | mask(S: State::TSCWrap) |
80 mask(S: State::CustomEvent) | mask(S: State::Function) |
81 mask(S: State::EndOfBuffer) | mask(S: State::TypedEvent)}},
82
83 {.From: State::TSCWrap,
84 .ToStates: {mask(S: State::TSCWrap) | mask(S: State::NewCPUId) |
85 mask(S: State::CustomEvent) | mask(S: State::Function) |
86 mask(S: State::EndOfBuffer) | mask(S: State::TypedEvent)}},
87
88 {.From: State::CustomEvent,
89 .ToStates: {mask(S: State::CustomEvent) | mask(S: State::TSCWrap) |
90 mask(S: State::NewCPUId) | mask(S: State::Function) |
91 mask(S: State::EndOfBuffer) | mask(S: State::TypedEvent)}},
92
93 {.From: State::TypedEvent,
94 .ToStates: {mask(S: State::TypedEvent) | mask(S: State::TSCWrap) |
95 mask(S: State::NewCPUId) | mask(S: State::Function) |
96 mask(S: State::EndOfBuffer) | mask(S: State::CustomEvent)}},
97
98 {.From: State::Function,
99 .ToStates: {mask(S: State::Function) | mask(S: State::TSCWrap) |
100 mask(S: State::NewCPUId) | mask(S: State::CustomEvent) |
101 mask(S: State::CallArg) | mask(S: State::EndOfBuffer) |
102 mask(S: State::TypedEvent)}},
103
104 {.From: State::CallArg,
105 .ToStates: {mask(S: State::CallArg) | mask(S: State::Function) |
106 mask(S: State::TSCWrap) | mask(S: State::NewCPUId) |
107 mask(S: State::CustomEvent) | mask(S: State::EndOfBuffer) |
108 mask(S: State::TypedEvent)}},
109
110 {.From: State::EndOfBuffer, .ToStates: {}}}};
111
112 if (CurrentRecord >= State::StateMax)
113 return createStringError(
114 EC: std::make_error_code(e: std::errc::executable_format_error),
115 Fmt: "BUG (BlockVerifier): Cannot find transition table entry for %s, "
116 "transitioning to %s.",
117 Vals: recordToString(R: CurrentRecord).data(), Vals: recordToString(R: 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(S: CurrentRecord)];
125 auto &Destinations = Mapping.ToStates;
126 assert(Mapping.From == CurrentRecord &&
127 "BUG: Wrong index for record mapping.");
128 if ((Destinations & ToSet(mask(S: To))) == 0)
129 return createStringError(
130 EC: std::make_error_code(e: std::errc::executable_format_error),
131 Fmt: "BlockVerifier: Invalid transition from %s to %s.",
132 Vals: recordToString(R: CurrentRecord).data(), Vals: recordToString(R: To).data());
133
134 CurrentRecord = To;
135 return Error::success();
136} // namespace xray
137
138Error BlockVerifier::visit(BufferExtents &) {
139 return transition(To: State::BufferExtents);
140}
141
142Error BlockVerifier::visit(WallclockRecord &) {
143 return transition(To: State::WallClockTime);
144}
145
146Error BlockVerifier::visit(NewCPUIDRecord &) {
147 return transition(To: State::NewCPUId);
148}
149
150Error BlockVerifier::visit(TSCWrapRecord &) {
151 return transition(To: State::TSCWrap);
152}
153
154Error BlockVerifier::visit(CustomEventRecord &) {
155 return transition(To: State::CustomEvent);
156}
157
158Error BlockVerifier::visit(CustomEventRecordV5 &) {
159 return transition(To: State::CustomEvent);
160}
161
162Error BlockVerifier::visit(TypedEventRecord &) {
163 return transition(To: State::TypedEvent);
164}
165
166Error BlockVerifier::visit(CallArgRecord &) {
167 return transition(To: State::CallArg);
168}
169
170Error BlockVerifier::visit(PIDRecord &) { return transition(To: State::PIDEntry); }
171
172Error BlockVerifier::visit(NewBufferRecord &) {
173 return transition(To: State::NewBuffer);
174}
175
176Error BlockVerifier::visit(EndBufferRecord &) {
177 return transition(To: State::EndOfBuffer);
178}
179
180Error BlockVerifier::visit(FunctionRecord &) {
181 return transition(To: State::Function);
182}
183
184Error 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 EC: std::make_error_code(e: std::errc::executable_format_error),
198 Fmt: "BlockVerifier: Invalid terminal condition %s, malformed block.",
199 Vals: recordToString(R: CurrentRecord).data());
200 }
201}
202
203void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
204
205} // namespace xray
206} // namespace llvm
207