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