[XRay] Add a BlockVerifier visitor for FDR Records

Summary:
This patch implements a `BlockVerifier` type which enforces the
invariants of the log structure of FDR mode logs on a per-block basis.
This ensures that the data we encounter from an FDR mode log
semantically correct (i.e. that records follow the documented "grammar"
for FDR mode log records).

This is another part of the refactoring of D50441.

This is a slightly modified version of rL341628, avoiding the
`std::tuple<...>` constructor that is not constexpr in C++11.

Reviewers: mboerger, eizan

Subscribers: mgorny, hiraditya, llvm-commits

Differential Revision: https://reviews.llvm.org/D51723

llvm-svn: 341769

5 files changed, 398 insertions, 0 deletions

diff --git a/llvm/include/llvm/XRay/BlockVerifier.h b/llvm/include/llvm/XRay/BlockVerifier.h
new file mode 100644
index 00000000000..b43a435e93b
--- /dev/null
+++ b/llvm/include/llvm/XRay/BlockVerifier.h
@@ -0,0 +1,69 @@
+//===- BlockVerifier.h - FDR Block Verifier -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// An implementation of the RecordVisitor which verifies a sequence of records
+// associated with a block, following the FDR mode log format's specifications.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
+#define LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
+
+#include "llvm/XRay/FDRRecords.h"
+#include <array>
+#include <bitset>
+
+namespace llvm {
+namespace xray {
+
+class BlockVerifier : public RecordVisitor {
+public:
+  // We force State elements to be size_t, to be used as indices for containers.
+  enum class State : std::size_t {
+    Unknown,
+    BufferExtents,
+    NewBuffer,
+    WallClockTime,
+    PIDEntry,
+    NewCPUId,
+    TSCWrap,
+    CustomEvent,
+    Function,
+    CallArg,
+    EndOfBuffer,
+    StateMax,
+  };
+
+private:
+  // We keep track of the current record seen by the verifier.
+  State CurrentRecord = State::Unknown;
+
+  // Transitions the current record to the new record, records an error on
+  // invalid transitions.
+  Error transition(State To);
+
+public:
+  Error visit(BufferExtents &) override;
+  Error visit(WallclockRecord &) override;
+  Error visit(NewCPUIDRecord &) override;
+  Error visit(TSCWrapRecord &) override;
+  Error visit(CustomEventRecord &) override;
+  Error visit(CallArgRecord &) override;
+  Error visit(PIDRecord &) override;
+  Error visit(NewBufferRecord &) override;
+  Error visit(EndBufferRecord &) override;
+  Error visit(FunctionRecord &) override;
+
+  Error verify();
+  void reset();
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
diff --git a/llvm/lib/XRay/BlockVerifier.cpp b/llvm/lib/XRay/BlockVerifier.cpp
new file mode 100644
index 00000000000..3bd1190006d
--- /dev/null
+++ b/llvm/lib/XRay/BlockVerifier.cpp
@@ -0,0 +1,187 @@
+//===- BlockVerifier.cpp - FDR Block Verifier -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/XRay/BlockVerifier.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+namespace xray {
+namespace {
+
+constexpr unsigned long long mask(BlockVerifier::State S) {
+  return 1uLL << static_cast<std::size_t>(S);
+}
+
+constexpr std::size_t number(BlockVerifier::State S) {
+  return static_cast<std::size_t>(S);
+}
+
+StringRef recordToString(BlockVerifier::State R) {
+  switch (R) {
+  case BlockVerifier::State::BufferExtents:
+    return "BufferExtents";
+  case BlockVerifier::State::NewBuffer:
+    return "NewBuffer";
+  case BlockVerifier::State::WallClockTime:
+    return "WallClockTime";
+  case BlockVerifier::State::PIDEntry:
+    return "PIDEntry";
+  case BlockVerifier::State::NewCPUId:
+    return "NewCPUId";
+  case BlockVerifier::State::TSCWrap:
+    return "TSCWrap";
+  case BlockVerifier::State::CustomEvent:
+    return "CustomEvent";
+  case BlockVerifier::State::Function:
+    return "Function";
+  case BlockVerifier::State::CallArg:
+    return "CallArg";
+  case BlockVerifier::State::EndOfBuffer:
+    return "EndOfBuffer";
+  case BlockVerifier::State::StateMax:
+  case BlockVerifier::State::Unknown:
+    return "Unknown";
+  }
+  llvm_unreachable("Unkown state!");
+}
+
+struct Transition {
+  BlockVerifier::State From;
+  std::bitset<number(BlockVerifier::State::StateMax)> ToStates;
+};
+
+} // namespace
+
+Error BlockVerifier::transition(State To) {
+  using ToSet = std::bitset<number(State::StateMax)>;
+  static constexpr std::array<const Transition, number(State::StateMax)>
+      TransitionTable{{{State::Unknown,
+                        {mask(State::BufferExtents) | mask(State::NewBuffer)}},
+
+                       {State::BufferExtents, {mask(State::NewBuffer)}},
+
+                       {State::NewBuffer, {mask(State::WallClockTime)}},
+
+                       {State::WallClockTime,
+                        {mask(State::PIDEntry) | mask(State::NewCPUId)}},
+
+                       {State::PIDEntry, {mask(State::NewCPUId)}},
+
+                       {State::NewCPUId,
+                        {mask(State::NewCPUId) | mask(State::TSCWrap) |
+                         mask(State::CustomEvent) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::TSCWrap,
+                        {mask(State::TSCWrap) | mask(State::NewCPUId) |
+                         mask(State::CustomEvent) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::CustomEvent,
+                        {mask(State::CustomEvent) | mask(State::TSCWrap) |
+                         mask(State::NewCPUId) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::Function,
+                        {mask(State::Function) | mask(State::TSCWrap) |
+                         mask(State::NewCPUId) | mask(State::CustomEvent) |
+                         mask(State::CallArg) | mask(State::EndOfBuffer)}},
+
+                       {State::CallArg,
+                        {mask(State::CallArg) | mask(State::Function) |
+                         mask(State::TSCWrap) | mask(State::NewCPUId) |
+                         mask(State::CustomEvent) | mask(State::EndOfBuffer)}},
+
+                       {State::EndOfBuffer, {}}}};
+
+  if (CurrentRecord >= State::StateMax)
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BUG (BlockVerifier): Cannot find transition table entry for %s, "
+        "transitioning to %s.",
+        recordToString(CurrentRecord).data(), recordToString(To).data());
+
+  // If we're at an EndOfBuffer record, we ignore anything that follows that
+  // isn't a NewBuffer record.
+  if (CurrentRecord == State::EndOfBuffer && To != State::NewBuffer)
+    return Error::success();
+
+  auto &Mapping = TransitionTable[number(CurrentRecord)];
+  auto &From = Mapping.From;
+  auto &Destinations = Mapping.ToStates;
+  assert(From == CurrentRecord && "BUG: Wrong index for record mapping.");
+  if ((Destinations & ToSet(mask(To))) == 0)
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BlockVerifier: Invalid transition from %s to %s.",
+        recordToString(CurrentRecord).data(), recordToString(To).data());
+
+  CurrentRecord = To;
+  return Error::success();
+} // namespace xray
+
+Error BlockVerifier::visit(BufferExtents &) {
+  return transition(State::BufferExtents);
+}
+
+Error BlockVerifier::visit(WallclockRecord &) {
+  return transition(State::WallClockTime);
+}
+
+Error BlockVerifier::visit(NewCPUIDRecord &) {
+  return transition(State::NewCPUId);
+}
+
+Error BlockVerifier::visit(TSCWrapRecord &) {
+  return transition(State::TSCWrap);
+}
+
+Error BlockVerifier::visit(CustomEventRecord &) {
+  return transition(State::CustomEvent);
+}
+
+Error BlockVerifier::visit(CallArgRecord &) {
+  return transition(State::CallArg);
+}
+
+Error BlockVerifier::visit(PIDRecord &) { return transition(State::PIDEntry); }
+
+Error BlockVerifier::visit(NewBufferRecord &) {
+  return transition(State::NewBuffer);
+}
+
+Error BlockVerifier::visit(EndBufferRecord &) {
+  return transition(State::EndOfBuffer);
+}
+
+Error BlockVerifier::visit(FunctionRecord &) {
+  return transition(State::Function);
+}
+
+Error BlockVerifier::verify() {
+  // The known terminal conditions are the following:
+  switch (CurrentRecord) {
+  case State::EndOfBuffer:
+  case State::NewCPUId:
+  case State::CustomEvent:
+  case State::Function:
+  case State::CallArg:
+  case State::TSCWrap:
+    return Error::success();
+  default:
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BlockVerifier: Invalid terminal condition %s, malformed block.",
+        recordToString(CurrentRecord).data());
+  }
+}
+
+void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
+
+} // namespace xray
+} // namespace llvm
diff --git a/llvm/lib/XRay/CMakeLists.txt b/llvm/lib/XRay/CMakeLists.txt
index ab6e0373c9e..a37f2c12fbb 100644
--- a/llvm/lib/XRay/CMakeLists.txt
+++ b/llvm/lib/XRay/CMakeLists.txt
@@ -1,5 +1,6 @@
 add_llvm_library(LLVMXRay
   BlockIndexer.cpp
+  BlockVerifier.cpp
   FDRRecordProducer.cpp
   FDRRecords.cpp
   FDRTraceWriter.cpp
diff --git a/llvm/unittests/XRay/CMakeLists.txt b/llvm/unittests/XRay/CMakeLists.txt
index 5f2453388f4..6293c8e9dc7 100644
--- a/llvm/unittests/XRay/CMakeLists.txt
+++ b/llvm/unittests/XRay/CMakeLists.txt
@@ -1,11 +1,13 @@
 set(LLVM_LINK_COMPONENTS
   Support
   XRay
+  TestingSupport
   )
 
 add_llvm_unittest(XRayTests
   ProfileTest.cpp
   FDRBlockIndexerTest.cpp
+  FDRBlockVerifierTest.cpp
   FDRProducerConsumerTest.cpp
   FDRRecordPrinterTest.cpp
   FDRTraceWriterTest.cpp
diff --git a/llvm/unittests/XRay/FDRBlockVerifierTest.cpp b/llvm/unittests/XRay/FDRBlockVerifierTest.cpp
new file mode 100644
index 00000000000..bc95d1b9ca1
--- /dev/null
+++ b/llvm/unittests/XRay/FDRBlockVerifierTest.cpp
@@ -0,0 +1,139 @@
+//===- llvm/unittest/XRay/FDRBlockVerifierTest.cpp --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/Testing/Support/Error.h"
+#include "llvm/XRay/BlockIndexer.h"
+#include "llvm/XRay/BlockVerifier.h"
+#include "llvm/XRay/FDRLogBuilder.h"
+#include "llvm/XRay/FDRRecords.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace xray {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::Not;
+using ::testing::SizeIs;
+
+TEST(FDRBlockVerifierTest, ValidBlocksV3) {
+  auto Block0 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(1)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(1)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  auto Block1 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(1)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(1)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  auto Block2 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(2)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(2)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  BlockIndexer::Index Index;
+  BlockIndexer Indexer(Index);
+  for (auto B : {std::ref(Block0), std::ref(Block1), std::ref(Block2)}) {
+    for (auto &R : B.get())
+      ASSERT_FALSE(errorToBool(R->apply(Indexer)));
+    ASSERT_FALSE(errorToBool(Indexer.flush()));
+  }
+
+  BlockVerifier Verifier;
+  for (auto &ProcessThreadBlocks : Index) {
+    auto &Blocks = ProcessThreadBlocks.second;
+    for (auto &B : Blocks) {
+      for (auto *R : B.Records)
+        ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+      ASSERT_FALSE(errorToBool(Verifier.verify()));
+      Verifier.reset();
+    }
+  }
+}
+
+TEST(FDRBlockVerifierTest, MissingPIDRecord) {
+  auto Block = LogBuilder()
+                   .add<BufferExtents>(20)
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, MissingBufferExtents) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, IgnoreRecordsAfterEOB) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<EndBufferRecord>()
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, MalformedV2) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .add<NewBufferRecord>(2)
+                   .consume();
+  BlockVerifier Verifier;
+
+  ASSERT_THAT(Block, SizeIs(6u));
+  EXPECT_THAT_ERROR(Block[0]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[1]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[2]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[3]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[4]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[5]->apply(Verifier), Failed());
+}
+
+} // namespace
+} // namespace xray
+} // namespace llvm