contrib/llvm/lib/XRay/BlockVerifier.cpp

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