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