• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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