1 /*
2 * Copyright (C) 2019 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/importers/common/args_tracker.h"
18
19 #include <algorithm>
20 #include <cstddef>
21 #include <cstdint>
22 #include <optional>
23 #include <tuple>
24
25 #include "perfetto/base/logging.h"
26 #include "perfetto/ext/base/small_vector.h"
27 #include "src/trace_processor/db/column.h"
28 #include "src/trace_processor/db/typed_column.h"
29 #include "src/trace_processor/importers/common/args_translation_table.h"
30 #include "src/trace_processor/storage/trace_storage.h"
31 #include "src/trace_processor/types/trace_processor_context.h"
32 #include "src/trace_processor/types/variadic.h"
33
34 namespace perfetto::trace_processor {
35
ArgsTracker(TraceProcessorContext * context)36 ArgsTracker::ArgsTracker(TraceProcessorContext* context) : context_(context) {}
37
~ArgsTracker()38 ArgsTracker::~ArgsTracker() {
39 Flush();
40 }
41
AddArg(ColumnLegacy * arg_set_id,uint32_t row,StringId flat_key,StringId key,Variadic value,UpdatePolicy update_policy)42 void ArgsTracker::AddArg(ColumnLegacy* arg_set_id,
43 uint32_t row,
44 StringId flat_key,
45 StringId key,
46 Variadic value,
47 UpdatePolicy update_policy) {
48 args_.emplace_back();
49
50 auto* rid_arg = &args_.back();
51 rid_arg->column = arg_set_id;
52 rid_arg->row = row;
53 rid_arg->flat_key = flat_key;
54 rid_arg->key = key;
55 rid_arg->value = value;
56 rid_arg->update_policy = update_policy;
57 }
58
Flush()59 void ArgsTracker::Flush() {
60 using Arg = GlobalArgsTracker::Arg;
61
62 if (args_.empty())
63 return;
64
65 // We need to ensure that the args with the same arg set (arg_set_id + row)
66 // and key are grouped together. This is important for joining the args from
67 // different events (e.g. trace event begin and trace event end might both
68 // have arguments).
69 //
70 // To achieve that (and do it quickly) we do two steps:
71 // - First, group all of the values within the same key together and compute
72 // the smallest index for each key.
73 // - Then we sort the args by column, row, smallest_index_for_key (to group
74 // keys) and index (to preserve the original ordering).
75
76 struct Entry {
77 size_t index;
78 StringId key;
79 size_t smallest_index_for_key = 0;
80
81 Entry(size_t i, StringId k) : index(i), key(k) {}
82 };
83
84 base::SmallVector<Entry, 16> entries;
85 for (const auto& arg : args_) {
86 entries.emplace_back(entries.size(), arg.key);
87 }
88
89 // Step 1: Compute the `smallest_index_for_key`.
90 std::sort(entries.begin(), entries.end(), [](const Entry& a, const Entry& b) {
91 return std::tie(a.key, a.index) < std::tie(b.key, b.index);
92 });
93
94 // As the data is sorted by (`key`, `index`) now, then the objects with the
95 // same key will be contiguous and within this block it will be sorted by
96 // index. That means that `smallest_index_for_key` for the entire block should
97 // be the value of the first index in the block.
98 entries[0].smallest_index_for_key = entries[0].index;
99 for (size_t i = 1; i < entries.size(); ++i) {
100 entries[i].smallest_index_for_key =
101 entries[i].key == entries[i - 1].key
102 ? entries[i - 1].smallest_index_for_key
103 : entries[i].index;
104 }
105
106 // Step 2: sort in the desired order: grouping by arg set first (column, row),
107 // then ensuring that the args with the same key are grouped together
108 // (smallest_index_for_key) and then preserving the original order within
109 // these group (index).
110 std::sort(
111 entries.begin(), entries.end(), [&](const Entry& a, const Entry& b) {
112 const Arg& first_arg = args_[a.index];
113 const Arg& second_arg = args_[b.index];
114 return std::tie(first_arg.column, first_arg.row,
115 a.smallest_index_for_key,
116 a.index) < std::tie(second_arg.column, second_arg.row,
117 b.smallest_index_for_key, b.index);
118 });
119
120 // Apply permutation of entries[].index to args.
121 base::SmallVector<Arg, 16> sorted_args;
122 for (auto& entry : entries) {
123 sorted_args.emplace_back(args_[entry.index]);
124 }
125
126 // Insert args.
127 for (uint32_t i = 0; i < args_.size();) {
128 const GlobalArgsTracker::Arg& arg = sorted_args[i];
129 auto* col = arg.column;
130 uint32_t row = arg.row;
131
132 uint32_t next_rid_idx = i + 1;
133 while (next_rid_idx < sorted_args.size() &&
134 col == sorted_args[next_rid_idx].column &&
135 row == sorted_args[next_rid_idx].row) {
136 next_rid_idx++;
137 }
138
139 ArgSetId set_id = context_->global_args_tracker->AddArgSet(
140 sorted_args.data(), i, next_rid_idx);
141 if (col->IsNullable()) {
142 TypedColumn<std::optional<uint32_t>>::FromColumn(col)->Set(row, set_id);
143 } else {
144 TypedColumn<uint32_t>::FromColumn(col)->Set(row, set_id);
145 }
146
147 i = next_rid_idx;
148 }
149 args_.clear();
150 }
151
ToCompactArgSet(const ColumnLegacy & column,uint32_t row_number)152 ArgsTracker::CompactArgSet ArgsTracker::ToCompactArgSet(
153 const ColumnLegacy& column,
154 uint32_t row_number) && {
155 CompactArgSet compact_args;
156 for (const auto& arg : args_) {
157 PERFETTO_DCHECK(arg.column == &column);
158 PERFETTO_DCHECK(arg.row == row_number);
159 compact_args.emplace_back(arg.ToCompactArg());
160 }
161 args_.clear();
162 return compact_args;
163 }
164
NeedsTranslation(const ArgsTranslationTable & table) const165 bool ArgsTracker::NeedsTranslation(const ArgsTranslationTable& table) const {
166 return std::any_of(
167 args_.begin(), args_.end(), [&table](const GlobalArgsTracker::Arg& arg) {
168 return table.NeedsTranslation(arg.flat_key, arg.key, arg.value.type);
169 });
170 }
171
BoundInserter(ArgsTracker * args_tracker,ColumnLegacy * arg_set_id_column,uint32_t row)172 ArgsTracker::BoundInserter::BoundInserter(ArgsTracker* args_tracker,
173 ColumnLegacy* arg_set_id_column,
174 uint32_t row)
175 : args_tracker_(args_tracker),
176 arg_set_id_column_(arg_set_id_column),
177 row_(row) {}
178
179 ArgsTracker::BoundInserter::~BoundInserter() = default;
180
181 } // namespace perfetto::trace_processor
182