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