llvm/lib/XRay/BlockVerifier.cpp

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