Home | History | Annotate | Download | only in trace_processor 
      1 /*
      2  * Copyright (C) 2018 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef SRC_TRACE_PROCESSOR_SPAN_JOIN_OPERATOR_TABLE_H_
     18 #define SRC_TRACE_PROCESSOR_SPAN_JOIN_OPERATOR_TABLE_H_
     19 
     20 #include <sqlite3.h>
     21 #include <array>
     22 #include <deque>
     23 #include <limits>
     24 #include <map>
     25 #include <memory>
     26 #include <string>
     27 #include <unordered_map>
     28 #include <vector>
     29 
     30 #include "src/trace_processor/scoped_db.h"
     31 #include "src/trace_processor/table.h"
     32 
     33 namespace perfetto {
     34 namespace trace_processor {
     35 
     36 // Implements the SPAN JOIN operation between two tables on a particular column.
     37 //
     38 // Span:
     39 // A span is a row with a timestamp and a duration. It can is used to model
     40 // operations which run for a particular *span* of time.
     41 //
     42 // We draw spans like so (time on the x-axis):
     43 // start of span->[ time where opertion is running ]<- end of span
     44 //
     45 // Multiple spans can happen in parallel:
     46 // [      ]
     47 //    [        ]
     48 //   [                    ]
     49 //  [ ]
     50 //
     51 // The above for example, models scheduling activity on a 4-core computer for a
     52 // short period of time.
     53 //
     54 // Span join:
     55 // The span join operation can be thought of as the intersection of span tables.
     56 // That is, the join table has a span for each pair of spans in the child tables
     57 // where the spans overlap. Because many spans are possible in parallel, an
     58 // extra metadata column (labelled the "join column") is used to distinguish
     59 // between the spanned tables.
     60 //
     61 // For a given join key suppose these were the two span tables:
     62 // Table 1:   [        ]              [      ]         [ ]
     63 // Table 2:          [      ]            [  ]           [      ]
     64 // Output :          [ ]                 [  ]           []
     65 //
     66 // All other columns apart from timestamp (ts), duration (dur) and the join key
     67 // are passed through unchanged.
     68 class SpanJoinOperatorTable : public Table {
     69  public:
     70   // Columns of the span operator table.
     71   enum Column {
     72     kTimestamp = 0,
     73     kDuration = 1,
     74     kPartition = 2,
     75     // All other columns are dynamic depending on the joined tables.
     76   };
     77 
     78   enum class PartitioningType {
     79     kNoPartitioning = 0,
     80     kSamePartitioning = 1,
     81     kMixedPartitioning = 2
     82   };
     83 
     84   // Parsed version of a table descriptor.
     85   struct TableDescriptor {
     86     static base::Optional<TableDescriptor> Parse(
     87         const std::string& raw_descriptor);
     88 
     89     bool IsPartitioned() const { return !partition_col.empty(); }
     90 
     91     std::string name;
     92     std::string partition_col;
     93   };
     94 
     95   // Contains the definition of the child tables.
     96   class TableDefinition {
     97    public:
     98     TableDefinition() = default;
     99 
    100     TableDefinition(std::string name,
    101                     std::string partition_col,
    102                     std::vector<Table::Column> cols,
    103                     bool emit_shadow_slices,
    104                     uint32_t ts_idx,
    105                     uint32_t dur_idx,
    106                     uint32_t partition_idx);
    107 
    108     const std::string& name() const { return name_; }
    109     const std::string& partition_col() const { return partition_col_; }
    110     const std::vector<Table::Column>& columns() const { return cols_; }
    111 
    112     bool emit_shadow_slices() const { return emit_shadow_slices_; }
    113     uint32_t ts_idx() const { return ts_idx_; }
    114     uint32_t dur_idx() const { return dur_idx_; }
    115     uint32_t partition_idx() const { return partition_idx_; }
    116 
    117     bool IsPartitioned() const { return !partition_col_.empty(); }
    118 
    119    private:
    120     std::string name_;
    121     std::string partition_col_;
    122     std::vector<Table::Column> cols_;
    123     bool emit_shadow_slices_;
    124     uint32_t ts_idx_ = std::numeric_limits<uint32_t>::max();
    125     uint32_t dur_idx_ = std::numeric_limits<uint32_t>::max();
    126     uint32_t partition_idx_ = std::numeric_limits<uint32_t>::max();
    127   };
    128 
    129   class Query {
    130    public:
    131     struct StepRet {
    132       enum Code {
    133         kRow,
    134         kEof,
    135         kError,
    136       };
    137 
    138       StepRet(Code c, int e = SQLITE_OK) : code(c), err_code(e) {}
    139 
    140       bool is_row() const { return code == Code::kRow; }
    141       bool is_eof() const { return code == Code::kEof; }
    142       bool is_err() const { return code == Code::kError; }
    143 
    144       Code code = Code::kEof;
    145       int err_code = SQLITE_OK;
    146     };
    147 
    148     Query(SpanJoinOperatorTable*, const TableDefinition*, sqlite3* db);
    149     virtual ~Query();
    150 
    151     Query(Query&) = delete;
    152     Query& operator=(const Query&) = delete;
    153 
    154     Query(Query&&) noexcept = default;
    155     Query& operator=(Query&&) = default;
    156 
    157     int Initialize(const QueryConstraints& qc, sqlite3_value** argv);
    158 
    159     StepRet Step();
    160     StepRet StepToNextPartition();
    161     StepRet StepToPartition(int64_t target_partition);
    162     StepRet StepUntil(int64_t timestamp);
    163 
    164     void ReportSqliteResult(sqlite3_context* context, size_t index);
    165 
    166     int64_t ts_start() const { return ts_start_; }
    167     int64_t ts_end() const { return ts_end_; }
    168     int64_t partition() const { return partition_; }
    169 
    170     const TableDefinition* definition() const { return defn_; }
    171 
    172     bool Eof() const { return cursor_eof_ && mode_ == Mode::kRealSlice; }
    173     bool IsPartitioned() const { return defn_->IsPartitioned(); }
    174     bool IsRealSlice() const { return mode_ == Mode::kRealSlice; }
    175 
    176     bool IsFullPartitionShadowSlice() const {
    177       return mode_ == Mode::kShadowSlice && ts_start_ == 0 &&
    178              ts_end_ == std::numeric_limits<int64_t>::max();
    179     }
    180 
    181     int64_t CursorPartition() const {
    182       PERFETTO_DCHECK(defn_->IsPartitioned());
    183       auto partition_idx = static_cast<int>(defn_->partition_idx());
    184       return sqlite3_column_int64(stmt_.get(), partition_idx);
    185     }
    186 
    187    private:
    188     enum Mode {
    189       kRealSlice,
    190       kShadowSlice,
    191     };
    192 
    193     int PrepareRawStmt();
    194     std::string CreateSqlQuery(const std::vector<std::string>& cs) const;
    195 
    196     int64_t CursorTs() const {
    197       auto ts_idx = static_cast<int>(defn_->ts_idx());
    198       return sqlite3_column_int64(stmt_.get(), ts_idx);
    199     }
    200 
    201     int64_t CursorDur() const {
    202       auto dur_idx = static_cast<int>(defn_->dur_idx());
    203       return sqlite3_column_int64(stmt_.get(), dur_idx);
    204     }
    205 
    206     std::string sql_query_;
    207     ScopedStmt stmt_;
    208 
    209     int64_t ts_start_ = 0;
    210     int64_t ts_end_ = 0;
    211     int64_t partition_ = std::numeric_limits<int64_t>::lowest();
    212 
    213     bool cursor_eof_ = false;
    214     Mode mode_ = Mode::kRealSlice;
    215 
    216     const TableDefinition* defn_ = nullptr;
    217     sqlite3* db_ = nullptr;
    218     SpanJoinOperatorTable* table_ = nullptr;
    219   };
    220 
    221   // Base class for a cursor on the span table.
    222   class Cursor : public Table::Cursor {
    223    public:
    224     Cursor(SpanJoinOperatorTable*, sqlite3* db);
    225     ~Cursor() override = default;
    226 
    227     int Filter(const QueryConstraints& qc, sqlite3_value** argv) override;
    228     int Column(sqlite3_context* context, int N) override;
    229     int Next() override;
    230     int Eof() override;
    231 
    232    private:
    233     Cursor(Cursor&) = delete;
    234     Cursor& operator=(const Cursor&) = delete;
    235 
    236     Cursor(Cursor&&) noexcept = default;
    237     Cursor& operator=(Cursor&&) = default;
    238 
    239     bool IsOverlappingSpan();
    240     Query::StepRet StepUntilRealSlice();
    241 
    242     Query t1_;
    243     Query t2_;
    244     Query* next_stepped_ = nullptr;
    245 
    246     SpanJoinOperatorTable* table_;
    247   };
    248 
    249   SpanJoinOperatorTable(sqlite3*, const TraceStorage*);
    250 
    251   static void RegisterTable(sqlite3* db, const TraceStorage* storage);
    252 
    253   // Table implementation.
    254   base::Optional<Table::Schema> Init(int, const char* const*) override;
    255   std::unique_ptr<Table::Cursor> CreateCursor() override;
    256   int BestIndex(const QueryConstraints& qc, BestIndexInfo* info) override;
    257 
    258  private:
    259   // Identifier for a column by index in a given table.
    260   struct ColumnLocator {
    261     const TableDefinition* defn;
    262     size_t col_index;
    263   };
    264 
    265   bool IsLeftJoin() const { return name() == "span_left_join"; }
    266   bool IsOuterJoin() const { return name() == "span_outer_join"; }
    267 
    268   const std::string& partition_col() const {
    269     return t1_defn_.IsPartitioned() ? t1_defn_.partition_col()
    270                                     : t2_defn_.partition_col();
    271   }
    272 
    273   base::Optional<TableDefinition> CreateTableDefinition(
    274       const TableDescriptor& desc,
    275       bool emit_shadow_slices);
    276 
    277   std::vector<std::string> ComputeSqlConstraintsForDefinition(
    278       const TableDefinition& defn,
    279       const QueryConstraints& qc,
    280       sqlite3_value** argv);
    281 
    282   std::string GetNameForGlobalColumnIndex(const TableDefinition& defn,
    283                                           int global_column);
    284 
    285   void CreateSchemaColsForDefn(const TableDefinition& defn,
    286                                std::vector<Table::Column>* cols);
    287 
    288   TableDefinition t1_defn_;
    289   TableDefinition t2_defn_;
    290   PartitioningType partitioning_;
    291   std::unordered_map<size_t, ColumnLocator> global_index_to_column_locator_;
    292 
    293   sqlite3* const db_;
    294 };
    295 
    296 }  // namespace trace_processor
    297 }  // namespace perfetto
    298 
    299 #endif  // SRC_TRACE_PROCESSOR_SPAN_JOIN_OPERATOR_TABLE_H_
    300