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 #ifndef SRC_TRACE_PROCESSOR_IMPORTERS_COMMON_CLOCK_TRACKER_H_ 18 #define SRC_TRACE_PROCESSOR_IMPORTERS_COMMON_CLOCK_TRACKER_H_ 19 20 #include <inttypes.h> 21 #include <stdint.h> 22 23 #include <array> 24 #include <map> 25 #include <random> 26 #include <set> 27 #include <vector> 28 29 #include "perfetto/base/logging.h" 30 #include "perfetto/ext/base/optional.h" 31 32 namespace perfetto { 33 namespace trace_processor { 34 35 class TraceProcessorContext; 36 37 // This class handles synchronization of timestamps across different clock 38 // domains. This includes multi-hop conversions from two clocks A and D, e.g. 39 // A->B -> B->C -> C->D, even if we never saw a snapshot that contains A and D 40 // at the same time. 41 // The API is fairly simple (but the inner operation is not): 42 // - AddSnapshot(map<clock_id, timestamp>): pushes a set of clocks that have 43 // been snapshotted at the same time (within technical limits). 44 // - Convert(src_clock_id, src_timestamp, target_clock_id): 45 // converts a timestamp between two clock domains. 46 // 47 // Concepts: 48 // - Snapshot hash: 49 // As new snapshots are pushed via AddSnapshot() we compute a snapshot hash. 50 // Such hash is the hash(clock_ids) (only IDs, not their timestamps) and is 51 // used to find other snapshots that involve the same clock domains. 52 // Two clock snapshots have the same hash iff they snapshot the same set of 53 // clocks (the order of clocks is irrelevant). 54 // This hash is used to efficiently go from the clock graph pathfinder to the 55 // time-series obtained by appending the various snapshots. 56 // - Snapshot id: 57 // A simple monotonic counter that is incremented on each AddSnapshot() call. 58 // 59 // Data structures: 60 // - For each clock domain: 61 // - For each snapshot hash: 62 // - A logic vector of (snapshot_id, timestamp) tuples (physically stored 63 // as two vectors of the same length instead of a vector of pairs). 64 // This allows to efficiently binary search timestamps within a clock domain 65 // that were obtained through a particular snapshot. 66 // 67 // - A graph of edges (source_clock, target_clock) -> snapshot hash. 68 // 69 // Operation: 70 // Upon each AddSnapshot() call, we incrementally build an unweighted, directed 71 // graph, which has clock domains as nodes. 72 // The graph is timestamp-oblivious. As long as we see one snapshot that 73 // connects two clocks, we assume we'll always be able to convert between them. 74 // This graph is queried by the Convert() function to figure out the shortest 75 // path between clock domain, possibly involving hopping through snapshots of 76 // different type (i.e. different hash). 77 // 78 // Example: 79 80 // We see a snapshot, with hash S1, for clocks (A,B,C). We build the edges in 81 // the graph: A->B, B->C, A->C (and the symmetrical ones). In other words we 82 // keep track of the fact that we can convert between any of them using S1. 83 // Later we get another snapshot containing (C,E), this snapshot will have a 84 // different hash (S2, because Hash(C,E) != Hash(A,B,C)) and will add the edges 85 // C->E, E->C [via S2] to the graph. 86 // At this point when we are asked to convert a timestamp from A to E, or 87 // viceversa, we use a simple BFS to figure out a conversion path that is: 88 // A->C [via S1] + C->E [via S2]. 89 // 90 // Visually: 91 // Assume we make the following calls: 92 // - AddSnapshot(A:10, B:100) 93 // - AddSnapshot(A:20, C:2000) 94 // - AddSnapshot(B:400, C:5000) 95 // - AddSnapshot(A:30, B:300) 96 97 // And assume Hash(A,B) = S1, H(A,C) = S2, H(B,C) = S3 98 // The vectors in the tracker will look as follows: 99 // Clock A: 100 // S1 {t:10, id:1} {t:30, id:4} 101 // S2 | {t:20, id:2} | 102 // | | | 103 // Clock B: | | | 104 // S1 {t:100, id:1} | {t:300, id:4} 105 // S3 | {t:400, id:3} 106 // | | 107 // Clock C: | | 108 // S2 {t: 2000, id: 2} | 109 // S3 {t:5000, id:3} 110 111 class ClockTracker { 112 public: 113 using ClockId = uint64_t; 114 115 // IDs in the range [64, 128) are reserved for sequence-scoped clock ids. 116 // They can't be passed directly in ClockTracker calls and must be resolved 117 // to 64-bit global clock ids by calling SeqScopedClockIdToGlobal(). IsReservedSeqScopedClockId(ClockId clock_id)118 static bool IsReservedSeqScopedClockId(ClockId clock_id) { 119 return clock_id >= 64 && clock_id < 128; 120 } 121 122 // Converts a sequence-scoped clock ids to a global clock id that can be 123 // passed as argument to ClockTracker functions. SeqScopedClockIdToGlobal(uint32_t seq_id,uint32_t clock_id)124 static ClockId SeqScopedClockIdToGlobal(uint32_t seq_id, uint32_t clock_id) { 125 PERFETTO_DCHECK(IsReservedSeqScopedClockId(clock_id)); 126 return (static_cast<uint64_t>(seq_id) << 32) | clock_id; 127 } 128 129 // Returns whether |global_clock_id| represents a sequence-scoped clock, i.e. 130 // a ClockId returned by SeqScopedClockIdToGlobal(). ClockIsSeqScoped(ClockId global_clock_id)131 static bool ClockIsSeqScoped(ClockId global_clock_id) { 132 // If the id is > 2**32, this is a sequence-scoped clock id translated into 133 // the global namespace. 134 return (global_clock_id >> 32) > 0; 135 } 136 137 explicit ClockTracker(TraceProcessorContext*); 138 virtual ~ClockTracker(); 139 140 // Clock description and its value in a snapshot. 141 struct ClockValue { ClockValueClockValue142 ClockValue(ClockId id, int64_t ts) : clock_id(id), absolute_timestamp(ts) {} ClockValueClockValue143 ClockValue(ClockId id, int64_t ts, int64_t unit, bool incremental) 144 : clock_id(id), 145 absolute_timestamp(ts), 146 unit_multiplier_ns(unit), 147 is_incremental(incremental) {} 148 149 ClockId clock_id; 150 int64_t absolute_timestamp; 151 int64_t unit_multiplier_ns = 1; 152 bool is_incremental = false; 153 }; 154 155 // Appends a new snapshot for the given clock domains. 156 // This is typically called by the code that reads the ClockSnapshot packet. 157 // Returns the internal snapshot id of this set of clocks. 158 uint32_t AddSnapshot(const std::vector<ClockValue>&); 159 160 // Converts a timestamp between two clock domains. Tries to use the cache 161 // first (only for single-path resolutions), then falls back on path finding 162 // as described in the header. Convert(ClockId src_clock_id,int64_t src_timestamp,ClockId target_clock_id)163 base::Optional<int64_t> Convert(ClockId src_clock_id, 164 int64_t src_timestamp, 165 ClockId target_clock_id) { 166 if (PERFETTO_LIKELY(!cache_lookups_disabled_for_testing_)) { 167 for (const auto& ce : cache_) { 168 if (ce.src != src_clock_id || ce.target != target_clock_id) 169 continue; 170 int64_t ns = ce.src_domain->ToNs(src_timestamp); 171 if (ns >= ce.min_ts_ns && ns < ce.max_ts_ns) 172 return ns + ce.translation_ns; 173 } 174 } 175 return ConvertSlowpath(src_clock_id, src_timestamp, target_clock_id); 176 } 177 178 base::Optional<int64_t> ConvertSlowpath(ClockId src_clock_id, 179 int64_t src_timestamp, 180 ClockId target_clock_id); 181 ToTraceTime(ClockId clock_id,int64_t timestamp)182 base::Optional<int64_t> ToTraceTime(ClockId clock_id, int64_t timestamp) { 183 trace_time_clock_id_used_for_conversion_ = true; 184 if (clock_id == trace_time_clock_id_) 185 return timestamp; 186 return Convert(clock_id, timestamp, trace_time_clock_id_); 187 } 188 SetTraceTimeClock(ClockId clock_id)189 void SetTraceTimeClock(ClockId clock_id) { 190 PERFETTO_DCHECK(!IsReservedSeqScopedClockId(clock_id)); 191 if (trace_time_clock_id_used_for_conversion_ && 192 trace_time_clock_id_ != clock_id) { 193 PERFETTO_ELOG("Not updating trace time clock from %" PRIu64 " to %" PRIu64 194 " because the old clock was already used for timestamp " 195 "conversion - ClockSnapshot too late in trace?", 196 trace_time_clock_id_, clock_id); 197 return; 198 } 199 trace_time_clock_id_ = clock_id; 200 } 201 set_cache_lookups_disabled_for_testing(bool v)202 void set_cache_lookups_disabled_for_testing(bool v) { 203 cache_lookups_disabled_for_testing_ = v; 204 } 205 206 private: 207 using SnapshotHash = uint32_t; 208 209 // 0th argument is the source clock, 1st argument is the target clock. 210 using ClockGraphEdge = std::tuple<ClockId, ClockId, SnapshotHash>; 211 212 // A value-type object that carries the information about the path between 213 // two clock domains. It's used by the BFS algorithm. 214 struct ClockPath { 215 static constexpr size_t kMaxLen = 4; 216 ClockPath() = default; 217 ClockPath(const ClockPath&) = default; 218 219 // Constructs an invalid path with just a source node. ClockPathClockPath220 explicit ClockPath(ClockId clock_id) : last(clock_id) {} 221 222 // Constructs a path by appending a node to |prefix|. 223 // If |prefix| = [A,B] and clock_id = C, then |this| = [A,B,C]. ClockPathClockPath224 ClockPath(const ClockPath& prefix, ClockId clock_id, SnapshotHash hash) { 225 PERFETTO_DCHECK(prefix.len < kMaxLen); 226 len = prefix.len + 1; 227 path = prefix.path; 228 path[prefix.len] = ClockGraphEdge{prefix.last, clock_id, hash}; 229 last = clock_id; 230 } 231 validClockPath232 bool valid() const { return len > 0; } atClockPath233 const ClockGraphEdge& at(uint32_t i) const { 234 PERFETTO_DCHECK(i < len); 235 return path[i]; 236 } 237 238 uint32_t len = 0; 239 ClockId last = 0; 240 std::array<ClockGraphEdge, kMaxLen> path; // Deliberately uninitialized. 241 }; 242 243 struct ClockSnapshots { 244 // Invariant: both vectors have the same length. 245 std::vector<uint32_t> snapshot_ids; 246 std::vector<int64_t> timestamps_ns; 247 }; 248 249 struct ClockDomain { 250 // One time-series for each hash. 251 std::map<SnapshotHash, ClockSnapshots> snapshots; 252 253 // Multiplier for timestamps given in this domain. 254 int64_t unit_multiplier_ns = 1; 255 256 // Whether this clock domain encodes timestamps as deltas. This is only 257 // supported on sequence-local domains. 258 bool is_incremental = false; 259 260 // If |is_incremental| is true, this stores the most recent absolute 261 // timestamp in nanoseconds. 262 int64_t last_timestamp_ns = 0; 263 264 // Treats |timestamp| as delta timestamp if the clock uses incremental 265 // encoding, and as absolute timestamp otherwise. ToNsClockDomain266 int64_t ToNs(int64_t timestamp) { 267 if (!is_incremental) 268 return timestamp * unit_multiplier_ns; 269 270 int64_t delta_ns = timestamp * unit_multiplier_ns; 271 last_timestamp_ns += delta_ns; 272 return last_timestamp_ns; 273 } 274 GetSnapshotClockDomain275 const ClockSnapshots& GetSnapshot(uint32_t hash) const { 276 auto it = snapshots.find(hash); 277 PERFETTO_DCHECK(it != snapshots.end()); 278 return it->second; 279 } 280 }; 281 282 // Holds data for cached entries. At the moment only single-path resolution 283 // are cached. 284 struct CachedClockPath { 285 ClockId src; 286 ClockId target; 287 ClockDomain* src_domain; 288 int64_t min_ts_ns; 289 int64_t max_ts_ns; 290 int64_t translation_ns; 291 }; 292 293 ClockTracker(const ClockTracker&) = delete; 294 ClockTracker& operator=(const ClockTracker&) = delete; 295 296 ClockPath FindPath(ClockId src, ClockId target); 297 GetClock(ClockId clock_id)298 ClockDomain* GetClock(ClockId clock_id) { 299 auto it = clocks_.find(clock_id); 300 PERFETTO_DCHECK(it != clocks_.end()); 301 return &it->second; 302 } 303 304 TraceProcessorContext* const context_; 305 ClockId trace_time_clock_id_ = 0; 306 std::map<ClockId, ClockDomain> clocks_; 307 std::set<ClockGraphEdge> graph_; 308 std::set<ClockId> non_monotonic_clocks_; 309 std::array<CachedClockPath, 2> cache_{}; 310 bool cache_lookups_disabled_for_testing_ = false; 311 std::minstd_rand rnd_; // For cache eviction. 312 uint32_t cur_snapshot_id_ = 0; 313 bool trace_time_clock_id_used_for_conversion_ = false; 314 }; 315 316 } // namespace trace_processor 317 } // namespace perfetto 318 319 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_COMMON_CLOCK_TRACKER_H_ 320