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