Index: lldb/docs/htr.rst =================================================================== --- /dev/null +++ lldb/docs/htr.rst @@ -0,0 +1,47 @@ +Hierarchical Trace Representation (HTR) +====================================== +The humongous amount of data processor traces like the ones obtained with Intel PT contain is not digestible to humans in its raw form. Given this, it is useful to summarize these massive traces by extracting useful information. Hierarchical Trace Representation (HTR) is the way lldb represents a summarized trace internally. HTR efficiently stores trace data and allows the trace data to be transformed in a way akin to compiler passes. + +Concepts +-------- +**Block:** One or more contiguous units of the trace. At minimum, the unit of a trace is the load address of an instruction. + +**Block Metadata:** Metadata associated with each *block*. For processor traces, some metadata examples are the number of instructions in the block or information on what functions are called in the block. + +**Layer:** The representation of trace data between passes. For Intel PT there are two types of layers: + + **Instruction Layer:** Composed of the oad addresses of the instructions in the trace. In an effort to save space, + metadata is only stored for instructions that are of interest, not every instruction in the trace. HTR contains a + single instruction layer. + + **Block Layer:** Composed of blocks - a block in *layer n* refers to a sequence of blocks in *layer n - 1*. A block in + *layer 1* refers to a sequence of instructions in *layer 0* (the instruction layer). Metadata is stored for each block in + a block layer. HTR contains one or more block layers. + +**Pass:** A transformation applied to a *layer* that generates a new *layer* that is a more summarized, consolidated representation of the trace data. +A pass merges instructions/blocks based on its specific purpose - for example, a pass designed to summarize a processor trace by function calls would merge all the blocks of a function into a single block representing the entire function.l + +The image below illusrates the transformation of a trace's representation (HTR) + +.. image:: media/htr-example.png + +Passes +------ +A *pass* is applied to a *layer* to extract useful information (summarization) and compress the trace representation into a new *layer*. The idea is to have a series of passes where each pass specializes in extracting certain information about the trace. Some examples of potential passes include: identifying functions, identifying loops, or a more general purpose such as identifying long sequences of instructions that are repeated (i.e. Basic Super Block). Below you will find a description of each pass currently implemented in lldb. + +**Basic Super Block Reduction** + +A “basic super block” is the longest sequence of blocks that always occur in the same order. (The concept is akin to “Basic Block'' in compiler theory, but refers to dynamic occurrences rather than CFG nodes). + +The image below shows the "basic super blocks" of the sequence. Each unique "basic super block" is marked with a different color + +.. image:: media/basic_super_block_pass.png + +*Procedure to find all super blocks:* + +- For each block, compute the number of distinct predecessor and successor blocks. + + - **Predecessor** - the block that occurs directly before (to the left of) the current block + - **Successor** - the block that occurs directly after (to the right of) the current block + +- A block with more than one distinct successor is always the start of a super block, the super block will continue until the next block with more than one distinct predecessor or successor. Index: lldb/include/lldb/Target/Trace.h =================================================================== --- lldb/include/lldb/Target/Trace.h +++ lldb/include/lldb/Target/Trace.h @@ -22,7 +22,6 @@ #include "lldb/lldb-private.h" namespace lldb_private { - /// \class Trace Trace.h "lldb/Target/Trace.h" /// A plug-in interface definition class for trace information. /// @@ -304,7 +303,6 @@ /// data kind -> size std::unordered_map m_live_process_data; }; - } // namespace lldb_private #endif // LLDB_TARGET_TRACE_H Index: lldb/include/lldb/lldb-enumerations.h =================================================================== --- lldb/include/lldb/lldb-enumerations.h +++ lldb/include/lldb/lldb-enumerations.h @@ -1138,7 +1138,6 @@ eSaveCoreFull = 1, eSaveCoreDirtyOnly = 2, }; - } // namespace lldb #endif // LLDB_LLDB_ENUMERATIONS_H Index: lldb/source/Plugins/TraceExporter/CMakeLists.txt =================================================================== --- lldb/source/Plugins/TraceExporter/CMakeLists.txt +++ lldb/source/Plugins/TraceExporter/CMakeLists.txt @@ -1 +1,2 @@ add_subdirectory(ctf) +add_subdirectory(common) Index: lldb/source/Plugins/TraceExporter/common/CMakeLists.txt =================================================================== --- /dev/null +++ lldb/source/Plugins/TraceExporter/common/CMakeLists.txt @@ -0,0 +1,7 @@ +add_lldb_library(lldbPluginTraceExporterCommon + TraceHTR.cpp + + LINK_LIBS + lldbCore + lldbTarget + ) Index: lldb/source/Plugins/TraceExporter/common/TraceHTR.h =================================================================== --- /dev/null +++ lldb/source/Plugins/TraceExporter/common/TraceHTR.h @@ -0,0 +1,409 @@ +//===-- TraceHTR.h --------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache +// License v2.0 with LLVM Exceptions.// See https://llvm.org/LICENSE.txt for +// license information.// SPDX-License-Identifier: Apache-2.0 WITH +// LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLDB_TARGET_TRACE_HTR_H +#define LLDB_TARGET_TRACE_HTR_H + +#include "lldb/Target/Thread.h" +#include "lldb/Target/Trace.h" + +#include +#include + +namespace lldb_private { + +/// Metadata associated with an HTR block +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class HTRBlockMetadata { +public: + /// Constructor for a block's metadata. + /// + /// \param[in] first_instruction_load_address + /// The load address of the block's first instruction. + /// + /// \param[in] num_instructions + /// The total number of instructions in the block. + /// + /// \param[in] func_calls + /// The map of a function name to the number of times it is called from + /// the block. + HTRBlockMetadata(lldb::addr_t first_instruction_load_address, + size_t num_instructions, + llvm::DenseMap &func_calls) + : m_first_instruction_load_address(first_instruction_load_address), + m_num_instructions(num_instructions), m_func_calls(func_calls) {} + + /// Merge two \a HTRBlockMetadata in place. + /// + /// \param[in][out] merged_metadata + /// Metadata that metadata_to_merge will be merged into. + /// + /// \param[in] metadata_to_merge + /// Metadata to merge into merged_metadata. + static void MergeMetadata(HTRBlockMetadata &merged_metadata, + HTRBlockMetadata const &metadata_to_merge); + /// Get the number of instructions in the block. + /// + /// \return + /// The number of instructions in the block. + size_t GetNumInstructions() const; + + /// Get the name of the most frequently called function from the block. + /// + /// \return + /// The name of the function that is called the most from this block or + /// None if no function is called from this block. + llvm::Optional GetMostFrequentlyCalledFunction() const; + + /// Get the load address of the first instruction in the block. + /// + /// \return + /// The load address of the first instruction in the block. + lldb::addr_t GetFirstInstructionLoadAddress() const; + + /// Get the function calls map for the block. + /// Function calls are identified in the instruction layer by finding 'call' + /// instructions and determining the function they are calling. As these + /// instructions are merged into blocks, we merge these different function + /// calls into a single map containing the function names to the number of + /// times it is called from this block. + /// + /// \return + /// The mapping of function name to the number of times it is called from + /// this block. + llvm::DenseMap const &GetFunctionCalls() const; + +private: + lldb::addr_t m_first_instruction_load_address; + size_t m_num_instructions; + llvm::DenseMap m_func_calls; +}; + +/// Block structure representing a sequence of trace "units" (ie instructions). +/// Sequences of blocks are merged to create a new, single block +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class HTRBlock { +public: + /// Constructor for a block of an HTR layer. + /// + /// \param[in] offset + /// The offset of the start of this block in the previous layer. + /// + /// \param[in] size + /// Number of blocks/instructions that make up this block in the previous + /// layer. + /// + /// \param[in] metadata + /// General metadata for this block. + HTRBlock(size_t offset, size_t size, HTRBlockMetadata metadata) + : m_offset(offset), m_size(size), m_metadata(metadata) {} + + /// Get the offset of the start of this block in the previous layer. + /// + /// \return + /// The offset of the block. + size_t GetOffset() const; + + /// Get the number of blocks/instructions that make up this block in the + /// previous layer. + /// + /// \return + /// The size of the block. + size_t GetSize() const; + + /// Get the metadata for this block. + /// + /// \return + /// The metadata of the block. + HTRBlockMetadata const &GetMetadata() const; + +private: + /// Offset in the previous layer + size_t m_offset; + /// Number of blocks/instructions that make up this block in the previous + /// layer + size_t m_size; + /// General metadata for this block + HTRBlockMetadata m_metadata; +}; + +/// HTR layer interface +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class IHTRLayer { +public: + /// Construct new HTR layer. + // + /// \param[in] id + /// The layer's id. + IHTRLayer(size_t id) : m_layer_id(id) {} + + /// Get the ID of the layer. + /// + /// \return + /// The layer ID of this layer. + size_t GetLayerId() const; + + /// Get the metadata of a unit (instruction or block) in the layer. + /// + /// \param[in] index + /// The position of the unit in the layer. + /// + /// \return + /// The metadata of the unit in the layer. + virtual HTRBlockMetadata GetMetadataByIndex(size_t index) const = 0; + + /// Get the total number of units (instruction or block) in this layer. + /// + /// \return + /// The total number of units in the layer. + virtual size_t GetNumUnits() const = 0; + + /// Creates a new block from the result of merging a contiguous sequence of + /// "units" (instructions or blocks depending on layer type) in this layer + /// This allows the implementation class to decide how to store/generate this + /// metadata. For example, in the case of the instruction layer we want to + /// lazily generate this metadata instead of storing it for each instruction. + /// + /// \param[in] start_unit_index + /// The index of the first unit to be merged. + /// + /// \param[in] num_units + /// The number of units to be merged. Must be >= 1, since merging 0 blocks + /// does not make sense. + /// + /// \return + /// A new block instance representing the merge of the specified units. + HTRBlock MergeUnits(size_t start_unit_index, size_t num_units); + + virtual ~IHTRLayer() = default; + +protected: + /// ID of the layer. + size_t m_layer_id; +}; + +/// "Base" layer of HTR representing the dynamic instructions of the trace. +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class HTRInstructionLayer : public IHTRLayer { +public: + /// Construct new instruction layer. + // + /// \param[in] id + /// The layer's id. + HTRInstructionLayer(size_t id) : IHTRLayer(id) {} + + size_t GetNumUnits() const override; + + HTRBlockMetadata GetMetadataByIndex(size_t index) const override; + + /// Get the dynamic instruction trace. + /// + /// \return + /// The dynamic instruction trace. + llvm::ArrayRef GetInstructionTrace() const; + + /// Add metadata for a 'call' instruction of the trace. + /// + /// \param[in] load_addr + /// The load address of the 'call' instruction. + /// + /// \param[in] func_name + /// The name of the function the 'call' instruction is calling if it can + /// be determined, None otherwise. + void AddCallInstructionMetadata(lldb::addr_t load_addr, + llvm::Optional func_name); + + /// Append the load address of an instruction to the dynamic instruction + /// trace. + /// + /// \param[in] load_addr + /// The load address of the instruction. + void AppendInstruction(lldb::addr_t load_addr); + +private: + // Dynamic instructions of trace are stored in chronological order. + std::vector m_instruction_trace; + // Only store metadata for instructions of interest (call instructions) + // If we stored metadata for each instruction this would be wasteful since + // most instructions don't contain useful metadata + + // This map contains the load address of all the call instructions. + // load address maps to the name of the function it calls (None if function + // name can't be determined) + std::unordered_map> m_call_isns; +}; + +/// HTR layer composed of blocks of the trace. +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class HTRBlockLayer : public IHTRLayer { +public: + /// Construct new block layer. + // + /// \param[in] id + /// The layer's id. + HTRBlockLayer(size_t id) : IHTRLayer(id) {} + + size_t GetNumUnits() const override; + + HTRBlockMetadata GetMetadataByIndex(size_t index) const override; + + /// Get an \a HTRBlock from its block id. + /// + /// \param[in] block_id + /// The id of the block to retrieve. + /// + /// \return + /// The \a HTRBlock with the specified id, nullptr if no there is no block + /// in the layer with the specified block id. + HTRBlock const *GetBlockById(size_t block_id) const; + + /// Get the block ID trace for this layer. + /// This block ID trace stores the block ID of each block that occured in the + /// trace and the block defs map maps block ID to the corresponding \a + /// HTRBlock. + /// + /// \return + /// The block ID trace for this layer. + llvm::ArrayRef GetBlockIdTrace() const; + + /// Appends a new block to the layer. + /// + /// \param[in] block_id + /// The block id of the new block. + /// + /// \param[in] block + /// The new \a HTRBlock to be appended to the layer. This block is moved + /// into the layer. + void AppendNewBlock(size_t block_id, HTRBlock &&block); + + /// Appends a repeated block to the layer. + /// + /// \param[in] block_id + /// The block id of the repeated block. + void AppendRepeatedBlock(size_t block_id); + +private: + /// Maps a unique Block ID to the corresponding HTRBlock + std::unordered_map m_block_defs; + /// Reduce memory footprint by just storing a trace of block IDs and use + /// m_block_defs to map a block_id to its corresponding HTRBlock + std::vector m_block_id_trace; +}; + +typedef std::unique_ptr HTRBlockLayerUP; +typedef std::unique_ptr + HTRInstructionLayerUP; + +/// Top-level HTR class +/// See lldb/docs/htr.rst for comprehensive HTR documentation +class TraceHTR { + +public: + /// Constructor for a trace's HTR. + /// + /// \param[in] thread + /// The thread the trace belongs to. + /// + /// \param[in] cursor + /// The trace cursor that gives access to the trace's contents. + TraceHTR(Thread &thread, TraceCursor &cursor); + + /// Executes passes on the HTR layers until no further + /// summarization/compression is achieved + void ExecutePasses(); + + /// Export HTR layers to the specified format and outfile. + /// + /// \param[in] outfile + /// The file that the exported HTR data will be written to. + /// + /// \return + /// Success if the export is successful, Error otherwise. + llvm::Error Export(std::string outfile); + + /// Get the block layers of this HTR. + /// + /// \return + /// The block layers of this HTR. + llvm::ArrayRef GetBlockLayers() const; + + /// Get the instruction layer of this HTR. + /// + /// \return + /// The instruction layer of this HTR. + HTRInstructionLayer const &GetInstructionLayer() const; + + /// Add a new block layer to this HTR. + /// + /// \param[in] + /// The new block layer to be added. + void AddNewBlockLayer(HTRBlockLayerUP &&block_layer); + +private: + // There is a single instruction layer per HTR + HTRInstructionLayerUP m_instruction_layer_up; + // There are one or more block layers per HTR + std::vector m_block_layer_ups; +}; + +// Serialization functions for exporting HTR to Chrome Trace Format +llvm::json::Value toJSON(const TraceHTR &htr); +llvm::json::Value toJSON(const HTRBlock &block); +llvm::json::Value toJSON(const HTRBlockMetadata &metadata); + +/// The HTR passes are defined below: + +/// Creates a new layer by merging the "basic super blocks" in the current layer +/// +/// A "basic super block" is the longest sequence of blocks that always occur in +/// the same order. (The concept is akin to “Basic Block" in compiler theory, +/// but refers to dynamic occurrences rather than CFG nodes) +/// +/// Procedure to find all basic super blocks: +// +/// - For each block, compute the number of distinct predecessor and +/// successor blocks. +/// Predecessor - the block that occurs directly before (to the left of) +/// the current block Successor - the block that occurs directly after +/// (to the right of) the current block +/// - A block with more than one distinct successor is always the start of a +/// super block, the super block will continue until the next block with +/// more than one distinct predecessor or successor. +/// +/// The implementation makes use of two terms - 'heads' and 'tails' known as +/// the 'endpoints' of a basic super block: +/// A 'head' is defined to be a block in the trace that doesn't have a +/// unique predecessor +/// A 'tail' is defined to be a block in the trace that doesn't have a +/// unique successor +/// +/// A basic super block is defined to be a sequence of blocks between two +/// endpoints +/// +/// A head represents the start of the next group, so the current group +/// ends at the block preceding the head and the next group begins with +/// this head block +/// +/// A tail represents the end of the current group, so the current group +/// ends with the tail block and the next group begins with the +/// following block. +/// +/// See lldb/docs/htr.rst for comprehensive HTR documentation +/// +/// \param[in] layer +/// The layer to execute the pass on. +/// +/// \return +/// A new layer instance representing the merge of blocks in the +/// previous layer +HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer); + +} // namespace lldb_private + +#endif // LLDB_TARGET_TRACE_HTR_H Index: lldb/source/Plugins/TraceExporter/common/TraceHTR.cpp =================================================================== --- /dev/null +++ lldb/source/Plugins/TraceExporter/common/TraceHTR.cpp @@ -0,0 +1,460 @@ +//===-- TraceHTR.cpp ------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "TraceHTR.h" + +#include "lldb/Symbol/Function.h" +#include "lldb/Target/Process.h" +#include "lldb/Target/Target.h" +#include "llvm/Support/JSON.h" +#include +#include + +using namespace lldb_private; +using namespace lldb; + +size_t HTRBlockMetadata::GetNumInstructions() const { + return m_num_instructions; +} + +llvm::Optional +HTRBlockMetadata::GetMostFrequentlyCalledFunction() const { + size_t max_ncalls = 0; + llvm::Optional max_name = llvm::None; + for (const auto &[name, ncalls] : m_func_calls) { + if (ncalls > max_ncalls) { + max_ncalls = ncalls; + max_name = name.GetStringRef(); + } + } + return max_name; +} + +llvm::DenseMap const & +HTRBlockMetadata::GetFunctionCalls() const { + return m_func_calls; +} + +lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const { + return m_first_instruction_load_address; +} + +size_t HTRBlock::GetOffset() const { return m_offset; } + +size_t HTRBlock::GetSize() const { return m_size; } + +HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; } + +llvm::ArrayRef TraceHTR::GetBlockLayers() const { + return m_block_layer_ups; +} + +HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const { + return *m_instruction_layer_up; +} + +void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) { + m_block_layer_ups.emplace_back(std::move(block_layer)); +} + +size_t IHTRLayer::GetLayerId() const { return m_layer_id; } + +void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) { + m_block_id_trace.emplace_back(block_id); + m_block_defs.emplace(block_id, block); +} + +void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) { + m_block_id_trace.emplace_back(block_id); +} + +llvm::ArrayRef HTRInstructionLayer::GetInstructionTrace() const { + return m_instruction_trace; +} + +void HTRInstructionLayer::AddCallInstructionMetadata( + lldb::addr_t load_addr, llvm::Optional func_name) { + m_call_isns.emplace(load_addr, func_name); +} + +void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) { + m_instruction_trace.emplace_back(load_addr); +} + +HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const { + auto block_it = m_block_defs.find(block_id); + if (block_it == m_block_defs.end()) + return nullptr; + else + return &block_it->second; +} + +llvm::ArrayRef HTRBlockLayer::GetBlockIdTrace() const { + return m_block_id_trace; +} + +size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); } + +HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const { + lldb::addr_t instruction_load_address = m_instruction_trace[index]; + llvm::DenseMap func_calls; + + auto func_name_it = m_call_isns.find(instruction_load_address); + if (func_name_it != m_call_isns.end()) { + if (llvm::Optional func_name = func_name_it->second) { + func_calls[*func_name] = 1; + } + } + return {instruction_load_address, 1, func_calls}; +} + +size_t HTRInstructionLayer::GetNumUnits() const { + return m_instruction_trace.size(); +} + +HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const { + size_t block_id = m_block_id_trace[index]; + HTRBlock block = m_block_defs.find(block_id)->second; + return block.GetMetadata(); +} + +TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor) + : m_instruction_layer_up(std::make_unique(0)) { + + // Move cursor to the first instruction in the trace + cursor.SetForwards(true); + cursor.Seek(0, TraceCursor::SeekType::Set); + + Target &target = thread.GetProcess()->GetTarget(); + auto function_name_from_load_address = + [&](lldb::addr_t load_address) -> llvm::Optional { + lldb_private::Address pc_addr; + SymbolContext sc; + if (target.ResolveLoadAddress(load_address, pc_addr) && + pc_addr.CalculateSymbolContext(&sc)) + return sc.GetFunctionName() + ? llvm::Optional(sc.GetFunctionName()) + : llvm::None; + else + return llvm::None; + }; + + bool more_data_in_trace = true; + while (more_data_in_trace) { + if (cursor.IsError()) { + // Append a load address of 0 for all instructions that an error occured + // while decoding. + // TODO: Make distinction between errors by storing the error messages. + // Currently, all errors are treated the same. + m_instruction_layer_up->AppendInstruction(0); + more_data_in_trace = cursor.Next(); + } else { + lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress(); + lldb::TraceInstructionControlFlowType current_instruction_type = + cursor.GetInstructionControlFlowType(); + + m_instruction_layer_up->AppendInstruction( + current_instruction_load_address); + more_data_in_trace = cursor.Next(); + if (current_instruction_type & + lldb::eTraceInstructionControlFlowTypeCall) { + if (more_data_in_trace && !cursor.IsError()) { + m_instruction_layer_up->AddCallInstructionMetadata( + current_instruction_load_address, + function_name_from_load_address(cursor.GetLoadAddress())); + } else { + // Next instruction is not known - pass None to indicate the name + // of the function being called is not known + m_instruction_layer_up->AddCallInstructionMetadata( + current_instruction_load_address, llvm::None); + } + } + } + } +} + +void HTRBlockMetadata::MergeMetadata( + HTRBlockMetadata &merged_metadata, + HTRBlockMetadata const &metadata_to_merge) { + merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions; + for (const auto &[name, num_calls] : metadata_to_merge.m_func_calls) { + merged_metadata.m_func_calls[name] += num_calls; + } +} + +HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) { + // TODO: make this function take `end_unit_index` as a parameter instead of + // unit and merge the range [start_unit_indx, end_unit_index] inclusive. + HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index); + for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) { + // merge the new metadata into merged_metadata + HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i)); + } + return {start_unit_index, num_units, merged_metadata}; +} + +void TraceHTR::ExecutePasses() { + auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) { + return l1.GetNumUnits() == l2.GetNumUnits(); + }; + HTRBlockLayerUP current_block_layer_up = + BasicSuperBlockMerge(*m_instruction_layer_up); + HTRBlockLayer ¤t_block_layer = *current_block_layer_up; + if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up)) + return; + + AddNewBlockLayer(std::move(current_block_layer_up)); + while (true) { + HTRBlockLayerUP new_block_layer_up = + BasicSuperBlockMerge(current_block_layer); + if (are_passes_done(current_block_layer, *new_block_layer_up)) + return; + + current_block_layer = *new_block_layer_up; + AddNewBlockLayer(std::move(new_block_layer_up)); + } +} + +llvm::Error TraceHTR::Export(std::string outfile) { + std::error_code ec; + llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text); + if (ec) { + return llvm::make_error( + "unable to open destination file: " + outfile, os.error()); + } else { + os << toJSON(*this); + os.close(); + if (os.has_error()) { + return llvm::make_error( + "unable to write to destination file: " + outfile, os.error()); + } + } + return llvm::Error::success(); +} + +HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) { + std::unique_ptr new_block_layer = + std::make_unique(layer.GetLayerId() + 1); + + if (layer.GetNumUnits()) { + // Future Improvement: split this into two functions - one for finding heads + // and tails, one for merging/creating the next layer A 'head' is defined to + // be a block whose occurrences in the trace do not have a unique preceding + // block. + std::unordered_set heads; + + // The load address of the first instruction of a block is the unique ID for + // that block (i.e. blocks with the same first instruction load address are + // the same block) + + // Future Improvement: no need to store all its preceding block ids, all we + // care about is that there is more than one preceding block id, so an enum + // could be used + std::unordered_map> head_map; + lldb::addr_t prev_id = + layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress(); + size_t num_units = layer.GetNumUnits(); + // This excludes the first unit since it has no previous unit + for (size_t i = 1; i < num_units; i++) { + lldb::addr_t current_id = + layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); + head_map[current_id].insert(prev_id); + prev_id = current_id; + } + for (const auto &[id, predecessor_set] : head_map) { + // ID of 0 represents an error - errors can't be heads or tails + if (id && predecessor_set.size() > 1) + heads.insert(id); + } + + // Future Improvement: identify heads and tails in the same loop + // A 'tail' is defined to be a block whose occurrences in the trace do + // not have a unique succeeding block. + std::unordered_set tails; + std::unordered_map> tail_map; + + // This excludes the last unit since it has no next unit + for (size_t i = 0; i < num_units - 1; i++) { + lldb::addr_t current_id = + layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); + lldb::addr_t next_id = + layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress(); + tail_map[current_id].insert(next_id); + } + + // Mark last block as tail so the algorithm stops gracefully + lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1) + .GetFirstInstructionLoadAddress(); + tails.insert(last_id); + for (const auto &[id, successor_set] : tail_map) { + // ID of 0 represents an error - errors can't be heads or tails + if (id && successor_set.size() > 1) + tails.insert(id); + } + + // Need to keep track of size of string since things we push are variable + // length + size_t superblock_size = 0; + // Each super block always has the same first unit (we call this the + // super block head) This gurantee allows us to use the super block head as + // the unique key mapping to the super block it begins + llvm::Optional superblock_head = llvm::None; + auto construct_next_layer = [&](size_t merge_start, size_t n) -> void { + if (!superblock_head) + return; + if (new_block_layer->GetBlockById(*superblock_head)) { + new_block_layer->AppendRepeatedBlock(*superblock_head); + } else { + HTRBlock new_block = layer.MergeUnits(merge_start, n); + new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block)); + } + }; + + for (size_t i = 0; i < num_units; i++) { + lldb::addr_t unit_id = + layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); + auto isHead = heads.count(unit_id) > 0; + auto isTail = tails.count(unit_id) > 0; + + if (isHead && isTail) { + // Head logic + if (superblock_size) { // this handles (tail, head) adjacency - + // otherwise an empty + // block is created + // End previous super block + construct_next_layer(i - superblock_size, superblock_size); + } + // Current id is first in next super block since it's a head + superblock_head = unit_id; + superblock_size = 1; + + // Tail logic + construct_next_layer(i - superblock_size + 1, superblock_size); + // Reset the block_head since the prev super block has come to and end + superblock_head = llvm::None; + superblock_size = 0; + } else if (isHead) { + if (superblock_size) { // this handles (tail, head) adjacency - + // otherwise an empty + // block is created + // End previous super block + construct_next_layer(i - superblock_size, superblock_size); + } + // Current id is first in next super block since it's a head + superblock_head = unit_id; + superblock_size = 1; + } else if (isTail) { + if (!superblock_head) + superblock_head = unit_id; + superblock_size++; + + // End previous super block + construct_next_layer(i - superblock_size + 1, superblock_size); + // Reset the block_head since the prev super block has come to and end + superblock_head = llvm::None; + superblock_size = 0; + } else { + if (!superblock_head) + superblock_head = unit_id; + superblock_size++; + } + } + } + return new_block_layer; +} + +llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) { + std::vector layers_as_json; + for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size(); + i++) { + size_t layer_id = htr.GetInstructionLayer().GetLayerId(); + HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i); + lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress(); + + std::string display_name; + + std::stringstream stream; + stream << "0x" << std::hex << load_address; + std::string load_address_hex_string(stream.str()); + display_name.assign(load_address_hex_string); + + layers_as_json.emplace_back(llvm::json::Object{ + {"name", display_name}, + {"ph", "B"}, + {"ts", (int64_t)i}, + + {"pid", (int64_t)layer_id}, + {"tid", (int64_t)layer_id}, + }); + + layers_as_json.emplace_back(llvm::json::Object{ + {"ph", "E"}, + {"ts", (int64_t)i + 1}, + {"pid", (int64_t)layer_id}, + {"tid", (int64_t)layer_id}, + }); + } + + for (const auto &layer : htr.GetBlockLayers()) { + size_t start_ts = 0; + std::vector block_id_trace = layer->GetBlockIdTrace(); + for (size_t i = 0; i < block_id_trace.size(); i++) { + size_t id = block_id_trace[i]; + // Guranteed that this ID is valid, so safe to dereference here. + HTRBlock block = *layer->GetBlockById(id); + llvm::json::Value block_json = toJSON(block); + size_t layer_id = layer->GetLayerId(); + + HTRBlockMetadata metadata = block.GetMetadata(); + + size_t end_ts = start_ts + metadata.GetNumInstructions(); + + llvm::Optional most_freq_func = + metadata.GetMostFrequentlyCalledFunction(); + std::stringstream stream; + stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress(); + std::string offset_hex_string(stream.str()); + std::string display_name = + most_freq_func ? offset_hex_string + ": " + most_freq_func->str() + : offset_hex_string; + + layers_as_json.emplace_back(llvm::json::Object{ + {"name", display_name}, + {"ph", "B"}, + {"ts", (int64_t)start_ts}, + {"pid", (int64_t)layer_id}, + {"tid", (int64_t)layer_id}, + }); + + layers_as_json.emplace_back(llvm::json::Object{ + {"ph", "E"}, + {"ts", (int64_t)end_ts}, + {"pid", (int64_t)layer_id}, + {"tid", (int64_t)layer_id}, + {"args", block_json}, + }); + start_ts = end_ts; + } + } + return layers_as_json; +} + +llvm::json::Value lldb_private::toJSON(const HTRBlock &block) { + return llvm::json::Value( + llvm::json::Object{{"Metadata", block.GetMetadata()}}); +} + +llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) { + std::vector function_calls; + for (const auto &[name, n_calls] : metadata.GetFunctionCalls()) + function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls)); + + return llvm::json::Value(llvm::json::Object{ + {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()}, + {"Functions", function_calls}}); +} Index: lldb/source/Plugins/TraceExporter/ctf/CMakeLists.txt =================================================================== --- lldb/source/Plugins/TraceExporter/ctf/CMakeLists.txt +++ lldb/source/Plugins/TraceExporter/ctf/CMakeLists.txt @@ -10,6 +10,7 @@ lldbCore lldbSymbol lldbTarget + lldbPluginTraceExporterCommon LINK_COMPONENTS Support ) Index: lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.h =================================================================== --- lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.h +++ lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.h @@ -30,6 +30,7 @@ llvm::ArrayRef GetDefinitions() override; llvm::Optional m_thread_index; + std::string m_file; }; CommandObjectThreadTraceExportCTF(CommandInterpreter &interpreter) @@ -39,7 +40,8 @@ "thread trace export ctf []", lldb::eCommandRequiresProcess | lldb::eCommandTryTargetAPILock | lldb::eCommandProcessMustBeLaunched | - lldb::eCommandProcessMustBePaused), + lldb::eCommandProcessMustBePaused | + lldb::eCommandProcessMustBeTraced), m_options() {} Options *GetOptions() override { return &m_options; } Index: lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp =================================================================== --- lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp +++ lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp @@ -8,7 +8,10 @@ #include "CommandObjectThreadTraceExportCTF.h" +#include "../common/TraceHTR.h" #include "lldb/Host/OptionParser.h" +#include "lldb/Target/Process.h" +#include "lldb/Target/Trace.h" using namespace lldb; using namespace lldb_private; @@ -27,6 +30,10 @@ const int short_option = m_getopt_table[option_idx].val; switch (short_option) { + case 'f': { + m_file.assign(std::string(option_arg)); + break; + } case 't': { int64_t thread_index; if (option_arg.empty() || option_arg.getAsInteger(0, thread_index) || @@ -45,6 +52,7 @@ void CommandObjectThreadTraceExportCTF::CommandOptions::OptionParsingStarting( ExecutionContext *execution_context) { + m_file.clear(); m_thread_index = None; } @@ -55,12 +63,30 @@ bool CommandObjectThreadTraceExportCTF::DoExecute(Args &command, CommandReturnObject &result) { - Stream &s = result.GetOutputStream(); - // TODO: create an actual instance of the exporter and invoke it - if (m_options.m_thread_index) - s.Printf("got thread index %d\n", (int)m_options.m_thread_index.getValue()); - else - s.Printf("didn't get a thread index\n"); + const TraceSP &trace_sp = m_exe_ctx.GetTargetSP()->GetTrace(); + Process *process = m_exe_ctx.GetProcessPtr(); + Thread *thread = m_options.m_thread_index + ? process->GetThreadList() + .FindThreadByIndexID(*m_options.m_thread_index) + .get() + : GetDefaultThread(); - return result.Succeeded(); + if (thread == nullptr) { + const uint32_t num_threads = process->GetThreadList().GetSize(); + size_t tid = m_options.m_thread_index ? *m_options.m_thread_index + : LLDB_INVALID_THREAD_ID; + result.AppendErrorWithFormat( + "Thread index %lu is out of range (valid values are 0 - %u).\n", tid, + num_threads); + return false; + } else { + TraceHTR htr(*thread, *trace_sp->GetCursor(*thread)); + htr.ExecutePasses(); + if (llvm::Error err = htr.Export(m_options.m_file)) { + result.AppendErrorWithFormat("%s\n", toString(std::move(err)).c_str()); + return false; + } else { + return true; + } + } } Index: lldb/source/Plugins/TraceExporter/ctf/TraceExporterCTFOptions.td =================================================================== --- lldb/source/Plugins/TraceExporter/ctf/TraceExporterCTFOptions.td +++ lldb/source/Plugins/TraceExporter/ctf/TraceExporterCTFOptions.td @@ -6,4 +6,8 @@ Arg<"ThreadIndex">, Desc<"Export the trace for the specified thread index. Otherwise, the " "currently selected thread will be used.">; + def thread_trace_export_file: Option<"file", "f">, Required, + Group<1>, + Arg<"Filename">, + Desc<"Path of the file to export the trace data">; } Index: lldb/test/API/commands/trace/TestTraceExport.py =================================================================== --- /dev/null +++ lldb/test/API/commands/trace/TestTraceExport.py @@ -0,0 +1,112 @@ +from collections import defaultdict +import lldb +import json +from intelpt_testcase import * +from lldbsuite.test.lldbtest import * +from lldbsuite.test import lldbutil +from lldbsuite.test.decorators import * +import os + +class TestTraceExport(TraceIntelPTTestCaseBase): + + mydir = TestBase.compute_mydir(__file__) + + def testErrorMessages(self): + ctf_test_file = self.getBuildArtifact("ctf-test.json") + # We first check the output when there are no targets + self.expect(f"thread trace export ctf --file {ctf_test_file}", + substrs=["error: invalid target, create a target using the 'target create' command"], + error=True) + + # We now check the output when there's a non-running target + self.expect("target create " + + os.path.join(self.getSourceDir(), "intelpt-trace", "a.out")) + + self.expect(f"thread trace export ctf --file {ctf_test_file}", + substrs=["error: invalid process"], + error=True) + + # Now we check the output when there's a running target without a trace + self.expect("b main") + self.expect("run") + + self.expect(f"thread trace export ctf --file {ctf_test_file}", + substrs=["error: Process is not being traced"], + error=True) + + def testExportCreatesFile(self): + self.expect("trace load -v " + + os.path.join(self.getSourceDir(), "intelpt-trace", "trace.json"), + substrs=["intel-pt"]) + + ctf_test_file = self.getBuildArtifact("ctf-test.json") + + if os.path.exists(ctf_test_file): + remove_file(ctf_test_file) + self.expect(f"thread trace export ctf --file {ctf_test_file}") + self.assertTrue(os.path.exists(ctf_test_file)) + + + def testHtrBasicSuperBlockPass(self): + ''' + Test the BasicSuperBlock pass of HTR + + TODO: Once the "trace save" command is implemented, gather Intel PT + trace of this program and load it like the other tests instead of + manually executing the commands to trace the program. + ''' + self.expect(f"target create {os.path.join(self.getSourceDir(), 'intelpt-trace', 'export_ctf_test_program.out')}") + self.expect("b main") + self.expect("r") + self.expect("b exit") + self.expect("thread trace start") + self.expect("c") + + ctf_test_file = self.getBuildArtifact("ctf-test.json") + + if os.path.exists(ctf_test_file): + remove_file(ctf_test_file) + self.expect(f"thread trace export ctf --file {ctf_test_file}") + self.assertTrue(os.path.exists(ctf_test_file)) + + + with open(ctf_test_file) as f: + data = json.load(f) + + num_units_by_layer = defaultdict(int) + index_of_first_layer_1_block = None + for i, event in enumerate(data): + layer_id = event.get('pid') + if layer_id == 1 and index_of_first_layer_1_block is None: + index_of_first_layer_1_block = i + if layer_id is not None and event['ph'] == 'B': + num_units_by_layer[layer_id] += 1 + + # Check that there are two layers + self.assertTrue(0 in num_units_by_layer and 1 in num_units_by_layer) + # Check that each layer has the correct total number of blocks + self.assertTrue(num_units_by_layer[0] == 1630) + self.assertTrue(num_units_by_layer[1] == 383) + + + expected_block_names = [ + '0x4005f0', + '0x4005fe', + '0x400606: iterative_handle_request_by_id(int, int)', + '0x4005a7', + '0x4005af', + '0x4005b9: fast_handle_request(int)', + '0x4005d5: log_response(int)', + ] + # There are two events per block, a beginning and an end. This means we must increment data_index by 2, so we only encounter the beginning event of each block. + data_index = index_of_first_layer_1_block + expected_index = 0 + while expected_index < len(expected_block_names): + self.assertTrue(data[data_index]['name'] == expected_block_names[expected_index]) + self.assertTrue(data[data_index]['name'] == expected_block_names[expected_index]) + data_index += 2 + expected_index += 1 + + + + Index: lldb/test/API/commands/trace/intelpt-trace/export_ctf_test_program.cpp =================================================================== --- /dev/null +++ lldb/test/API/commands/trace/intelpt-trace/export_ctf_test_program.cpp @@ -0,0 +1,34 @@ +void log_response(int reqest_response) { + // fake logging logic +} + +int slow_handle_request(int id) { + // "slow" request handling logic + for (int i = 0; i < 10; i++) + id += 2; + return id; +} + +int fast_handle_request(int id) { + // "fast" request handling logic + return id + 2; +} + +void iterative_handle_request_by_id(int id, int reps) { + int response; + for (int i = 0; i < reps; i++) { + if (i % 2 == 0) + response = fast_handle_request(id); + else + response = slow_handle_request(id); + log_response(response); + } +} + +int main() { + int n_requests = 10; + for (int id = 0; id < n_requests; id++) { + iterative_handle_request_by_id(id, 3); + } + return 0; +}