1 /*
2  * Copyright (C) 2021 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 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_flat_slice.h"
18 
19 #include <cstddef>
20 #include <cstdint>
21 #include <limits>
22 #include <memory>
23 #include <optional>
24 #include <string>
25 #include <unordered_map>
26 #include <vector>
27 
28 #include "perfetto/base/logging.h"
29 #include "perfetto/base/status.h"
30 #include "perfetto/ext/base/status_or.h"
31 #include "perfetto/trace_processor/basic_types.h"
32 #include "src/trace_processor/containers/string_pool.h"
33 #include "src/trace_processor/db/table.h"
34 #include "src/trace_processor/storage/trace_storage.h"
35 #include "src/trace_processor/tables/slice_tables_py.h"
36 #include "src/trace_processor/tables/track_tables_py.h"
37 #include "src/trace_processor/types/trace_processor_context.h"
38 
39 namespace perfetto::trace_processor {
40 
ExperimentalFlatSlice(TraceProcessorContext * context)41 ExperimentalFlatSlice::ExperimentalFlatSlice(TraceProcessorContext* context)
42     : context_(context) {}
43 
ComputeTable(const std::vector<SqlValue> & arguments)44 base::StatusOr<std::unique_ptr<Table>> ExperimentalFlatSlice::ComputeTable(
45     const std::vector<SqlValue>& arguments) {
46   PERFETTO_CHECK(arguments.size() == 2);
47   if (arguments[0].type != SqlValue::kLong) {
48     return base::ErrStatus("start timestamp must be an integer");
49   }
50   if (arguments[1].type != SqlValue::kLong) {
51     return base::ErrStatus("end timestamp must be an integer");
52   }
53   return std::unique_ptr<Table>(
54       ComputeFlatSliceTable(context_->storage->slice_table(),
55                             context_->storage->mutable_string_pool(),
56                             arguments[0].AsLong(), arguments[1].AsLong()));
57 }
58 
59 std::unique_ptr<tables::ExperimentalFlatSliceTable>
ComputeFlatSliceTable(const tables::SliceTable & slice,StringPool * pool,int64_t start_bound,int64_t end_bound)60 ExperimentalFlatSlice::ComputeFlatSliceTable(const tables::SliceTable& slice,
61                                              StringPool* pool,
62                                              int64_t start_bound,
63                                              int64_t end_bound) {
64   std::unique_ptr<tables::ExperimentalFlatSliceTable> out(
65       new tables::ExperimentalFlatSliceTable(pool));
66 
67   auto insert_slice = [&](uint32_t i, int64_t ts,
68                           tables::TrackTable::Id track_id) {
69     auto rr = slice[i];
70     tables::ExperimentalFlatSliceTable::Row row;
71     row.ts = ts;
72     row.dur = -1;
73     row.track_id = track_id;
74     row.category = rr.category();
75     row.name = rr.name();
76     row.arg_set_id = rr.arg_set_id();
77     row.source_id = rr.id();
78     row.start_bound = start_bound;
79     row.end_bound = end_bound;
80     return out->Insert(row).row;
81   };
82   auto insert_sentinel = [&](int64_t ts, TrackId track_id) {
83     tables::ExperimentalFlatSliceTable::Row row;
84     row.ts = ts;
85     row.dur = -1;
86     row.track_id = track_id;
87     row.category = kNullStringId;
88     row.name = kNullStringId;
89     row.arg_set_id = kInvalidArgSetId;
90     row.source_id = std::nullopt;
91     row.start_bound = start_bound;
92     row.end_bound = end_bound;
93     return out->Insert(row).row;
94   };
95 
96   auto terminate_slice = [&](uint32_t out_row, int64_t end_ts) {
97     auto rr = (*out)[out_row];
98     PERFETTO_DCHECK(rr.dur() == -1);
99     rr.set_dur(end_ts - rr.ts());
100   };
101 
102   struct ActiveSlice {
103     std::optional<uint32_t> source_row;
104     uint32_t out_row = std::numeric_limits<uint32_t>::max();
105 
106     bool is_sentinel() const { return !source_row; }
107   };
108   struct Track {
109     std::vector<uint32_t> parents;
110     ActiveSlice active;
111     bool initialized = false;
112   };
113   std::unordered_map<TrackId, Track> tracks;
114 
115   auto maybe_terminate_active_slice = [&](const Track& t, int64_t fin_ts) {
116     auto rr = slice[t.active.source_row.value()];
117     int64_t ts = rr.ts();
118     int64_t dur = rr.dur();
119     if (dur == -1 || ts + dur > fin_ts)
120       return false;
121 
122     terminate_slice(t.active.out_row, ts + dur);
123     return true;
124   };
125 
126   // Post-condition: |tracks[track_id].active| will always point to
127   // a slice which finishes after |fin_ts| and has a |dur| == -1 in
128   // |out|.
129   auto output_slices_before = [&](TrackId track_id, int64_t fin_ts) {
130     auto& t = tracks[track_id];
131 
132     // A sentinel slice cannot have parents.
133     PERFETTO_DCHECK(!t.active.is_sentinel() || t.parents.empty());
134 
135     // If we have a sentinel slice active, we have nothing to output.
136     if (t.active.is_sentinel())
137       return;
138 
139     // Try and terminate the current slice (if it ends before |fin_ts|)
140     // If we cannot terminate it, then we leave it as pending for the caller
141     // to terminate.
142     if (!maybe_terminate_active_slice(t, fin_ts))
143       return;
144 
145     // Next, add any parents as appropriate.
146     for (int64_t i = static_cast<int64_t>(t.parents.size()) - 1; i >= 0; --i) {
147       uint32_t source_row = t.parents[static_cast<size_t>(i)];
148       t.parents.pop_back();
149 
150       auto rr = (*out)[t.active.out_row];
151       int64_t active_ts = rr.ts();
152       int64_t active_dur = rr.dur();
153       PERFETTO_DCHECK(active_dur != -1);
154 
155       t.active.source_row = source_row;
156       t.active.out_row =
157           insert_slice(source_row, active_ts + active_dur, track_id);
158 
159       if (!maybe_terminate_active_slice(t, fin_ts))
160         break;
161     }
162 
163     if (!t.parents.empty())
164       return;
165 
166     // If the active slice is a sentinel, the check at the top of this function
167     // should have caught it; all code only adds slices from source.
168     PERFETTO_DCHECK(!t.active.is_sentinel());
169 
170     auto rr = (*out)[t.active.out_row];
171     int64_t ts = rr.ts();
172     int64_t dur = rr.dur();
173 
174     // If the active slice is unfinshed, we return that for the caller to
175     // terminate.
176     if (dur == -1)
177       return;
178 
179     // Otherwise, Add a sentinel slice after the end of the active slice.
180     t.active.source_row = std::nullopt;
181     t.active.out_row = insert_sentinel(ts + dur, track_id);
182   };
183 
184   for (auto it = slice.IterateRows(); it; ++it) {
185     // TODO(lalitm): this can be optimized using a O(logn) lower bound/filter.
186     // Not adding for now as a premature optimization but may be needed down the
187     // line.
188     int64_t ts = it.ts();
189     if (ts < start_bound)
190       continue;
191 
192     if (ts >= end_bound)
193       break;
194 
195     // Ignore instants as they don't factor into flat slice at all.
196     if (it.dur() == 0)
197       continue;
198 
199     TrackId track_id = it.track_id();
200     Track& track = tracks[track_id];
201 
202     // Initalize the track (if needed) by adding a sentinel slice starting at
203     // start_bound.
204     bool is_root = it.depth() == 0;
205     if (!track.initialized) {
206       // If we are unintialized and our start box picks up slices mid way
207       // through startup, wait until we reach a root slice.
208       if (!is_root)
209         continue;
210 
211       track.active.out_row = insert_sentinel(start_bound, track_id);
212       track.initialized = true;
213     }
214     output_slices_before(track_id, ts);
215     terminate_slice(track.active.out_row, ts);
216 
217     // We should have sentinel slices iff the slice is a root.
218     PERFETTO_DCHECK(track.active.is_sentinel() == is_root);
219 
220     // If our current slice has a parent, that must be the current active slice.
221     if (!is_root) {
222       track.parents.push_back(*track.active.source_row);
223     }
224 
225     // The depth of our slice should also match the depth of the parent stack
226     // (after adding the previous slice).
227     PERFETTO_DCHECK(track.parents.size() == it.depth());
228 
229     track.active.source_row = it.row_number().row_number();
230     track.active.out_row =
231         insert_slice(it.row_number().row_number(), ts, track_id);
232   }
233 
234   for (const auto& track : tracks) {
235     // If the track is not initialized, don't add anything.
236     if (!track.second.initialized)
237       continue;
238 
239     // First, terminate any hanging slices.
240     output_slices_before(track.first, end_bound);
241 
242     // Second, force terminate the final slice to the end bound.
243     terminate_slice(track.second.active.out_row, end_bound);
244   }
245 
246   return out;
247 }
248 
CreateSchema()249 Table::Schema ExperimentalFlatSlice::CreateSchema() {
250   return tables::ExperimentalFlatSliceTable::ComputeStaticSchema();
251 }
252 
TableName()253 std::string ExperimentalFlatSlice::TableName() {
254   return "experimental_flat_slice";
255 }
256 
EstimateRowCount()257 uint32_t ExperimentalFlatSlice::EstimateRowCount() {
258   return context_->storage->slice_table().row_count();
259 }
260 
261 }  // namespace perfetto::trace_processor
262