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(BlockVerifier::State::StateMax)> ToStates;
59};
60
61} // namespace
62
63Error 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
138Error BlockVerifier::visit(BufferExtents &) {
139  return transition(State::BufferExtents);
140}
141
142Error BlockVerifier::visit(WallclockRecord &) {
143  return transition(State::WallClockTime);
144}
145
146Error BlockVerifier::visit(NewCPUIDRecord &) {
147  return transition(State::NewCPUId);
148}
149
150Error BlockVerifier::visit(TSCWrapRecord &) {
151  return transition(State::TSCWrap);
152}
153
154Error BlockVerifier::visit(CustomEventRecord &) {
155  return transition(State::CustomEvent);
156}
157
158Error BlockVerifier::visit(CustomEventRecordV5 &) {
159  return transition(State::CustomEvent);
160}
161
162Error BlockVerifier::visit(TypedEventRecord &) {
163  return transition(State::TypedEvent);
164}
165
166Error BlockVerifier::visit(CallArgRecord &) {
167  return transition(State::CallArg);
168}
169
170Error BlockVerifier::visit(PIDRecord &) { return transition(State::PIDEntry); }
171
172Error BlockVerifier::visit(NewBufferRecord &) {
173  return transition(State::NewBuffer);
174}
175
176Error BlockVerifier::visit(EndBufferRecord &) {
177  return transition(State::EndOfBuffer);
178}
179
180Error BlockVerifier::visit(FunctionRecord &) {
181  return transition(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        std::make_error_code(std::errc::executable_format_error),
198        "BlockVerifier: Invalid terminal condition %s, malformed block.",
199        recordToString(CurrentRecord).data());
200  }
201}
202
203void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
204
205} // namespace xray
206} // namespace llvm
207