1# Synchronization of multiple clock domains 2 3As per [6756fb05][6756fb05] Perfetto handles events using different 4clock domains. On top of the default set of builtin clock domains, new clock 5domains can be dynamically created at trace-time. 6 7Clock domains are allowed to drift from each other. 8At import time, Perfetto's [Trace Processor](/docs/analysis/trace-processor.md) is able 9to rebuild the clock graph and use that to re-synchronize events on a global 10trace time, as long as the [ClockSnapshot][clock_snapshot] packets are present in 11the trace. 12 13## Problem statement 14 15In a complex multi-producer scenario, different data source can emit events 16using different clock domains. 17 18Some examples: 19 20* On Linux/Android, Ftrace events are emitted using the `CLOCK_BOOTTIME` clock, 21 but the Android event log uses `CLOCK_REALTIME`. 22 Some other data sources can use `CLOCK_MONOTONIC`. 23 These clocks can drift over time from each other due to suspend/resume. 24 25* Graphics-related events are typically timestamped by the GPU, which can use a 26 hardware clock source that drifts from the system clock. 27 28At trace-time, the data sources might not be able to use `CLOCK_BOOTTIME` (or 29even when possible, doing so might be prohibitively expensive). 30 31To solve this, we allow events to be recorded with different clock domains and 32re-synchronize them at import time using clock snapshots. 33 34## Trace proto syntax 35 36Clock synchronization is based on two elements of the trace: 37 381. [The timestamp_clock_id field of TracePacket](#timestamp_clock_id) 392. [The ClockSnapshot trace packet](#clock_snapshot) 40 41### {#timestamp_clock_id} The timestamp_clock_id field of TracePacket 42 43```protobuf 44message TracePacket { 45 optional uint64 timestamp = 8; 46 47 // Specifies the ID of the clock used for the TracePacket |timestamp|. Can be 48 // one of the built-in types from ClockSnapshot::BuiltinClocks, or a 49 // producer-defined clock id. 50 // If unspecified it defaults to BuiltinClocks::BOOTTIME. 51 optional uint32 timestamp_clock_id = 58; 52 53``` 54 55This (optional) field determines the clock domain for the packet. 56If omitted it refers to the default clock domain of the trace 57(`CLOCK_BOOTTIME` for Linux/Android). 58It present, this field can be set to either: 59 60* One of the [builtin clocks defined in clock_snapshot.proto][builtin_clocks] 61 (e.g., `CLOCK_BOOTTIME`, `CLOCK_REALTIME`, `CLOCK_MONOTONIC`). These clocks 62 have an ID <= 63. 63* A custom sequence-scoped clock, with 64 <= ID < 128 64* A custom globally-scoped clock, with 128 <= ID < 2**32 65 66#### Builtin clocks 67Builtin clocks cover the most common case of data sources using one of the 68POSIX clocks (see `man clock_gettime`). These clocks are periodically 69snapshotted by the `traced` service. The producer doesn't need to do anything 70other than set the `timestamp_clock_id` field in order to emit events 71that use these clocks. 72 73#### Sequence-scoped clocks 74Sequence-scoped clocks are application-defined clock domains that are valid only 75within the sequence of TracePacket(s) written by the same `TraceWriter` 76(i.e. TracePacket that have the same `trusted_packet_sequence_id` field). 77In most cases this really means *"events emitted by the same data source on 78the same thread"*. 79 80This covers the most common use case of a clock domain that is used only within 81a data source and not shared across different data sources. 82The main advantage of sequence-scoped clocks is that avoids the ID 83disambiguation problem and JustWorks™ for the most simple case. 84 85In order to make use of a custom sequence-scoped clock domain a data source 86must: 87 88* Emit its packets with a `timestamp_clock_id` in the range [64, 127] 89* Emit at least once a [`ClockSnapshot`][clock_snapshot] packet. 90 91Such `ClockSnapshot`: 92 93* Must be emitted on the same sequence (i.e. by the same `TraceWriter`) that is 94 used to emit other `TracePacket`(s) that refer to such `timestamp_clock_id`. 95* Must be emitted before the custom clock is referred to by any `TracePacket` 96 written by the same `TraceWriter`. 97* Must contain a snapshot of: (i) the custom clock id [64, 127] and (ii) another 98 clock domain that can be resolved, at import time, against the default trace 99 clock domain (`CLOCK_BOOTTIME`) (see the [Operation section](#operation) 100 below). 101 102Collisions of `timestamp_clock_id` across two different `TraceWriter` sequences 103are okay. E.g., two data sources, unaware of each other, can both use clock ID 10464 to refer to two different clock domains. 105 106#### Globally-scoped clocks 107Globally-scoped clock domains work similarly to sequence-scoped clock domains, 108with the only difference that their scope is global and applies to all 109`TracePacket`(s) of the trace. 110 111The same `ClockSnapshot` rules as above apply. The only difference is that once 112a `ClockSnapshot` defines a clock domain with ID >= 128, that clock domain can 113be referred to by any `TracePacket` written by any `TraceWriter` sequence. 114 115Care must be taken to avoid collisions between global clock domains defined by 116different data sources unaware of each other. 117 118As such, it is **strongly discouraged** to just use the ID 128 (or any other 119arbitrarily chosen value). Instead the recommended pattern is: 120 121* Chose a fully qualified name for the clock domain 122 (e.g. `com.example.my_subsystem`) 123* Chose the clock ID as `HASH("com.example.my_subsystem") | 0x80000000` 124 where `HASH(x)` is the FNV-1a hash of the fully qualified clock domain name. 125 126### {#clock_snapshot} The ClockSnapshot trace packet 127 128The [`ClockSnapshot`][clock_snapshot] packet defines sync points between two or 129more clock domains. It conveys the notion *"at this point in time, the timestamp 130of the clock domains X,Y,Z was 1000, 2000, 3000."*. 131 132The trace importer ([Trace Processor](/docs/analysis/trace-processor.md)) uses this 133information to establish a mapping between these clock domain. For instance, 134to realize that 1042 on clock domain X == 3042 on clock domain Z. 135 136The `traced` service automatically emits `ClockSnapshot` packets for the builtin 137clock domains on a regular basis. 138 139A data source should emit `ClockSnapshot` packets only when using custom clock 140domains, either sequence-scoped or globally-scoped. 141 142It is *not* mandatory that the `ClockSnapshot` for a custom clock domain 143contains also a snapshot of `CLOCK_BOOTTIME` (although it is advisable to do 144so when possible). The Trace Processor can deal with multi-path clock domain 145resolution based on graph traversal (see the [Operation](#operation) section). 146 147## Operation 148 149At import time Trace Processor will attempt to convert the timestamp of each 150TracePacket down to the trace clock domain (`CLOCK_BOOTTIME`) using the 151`ClockSnapshot` packets seen until then using nearest neighbor approximation. 152 153For instance, assume that the trace contains `ClockSnapshot` for 154`CLOCK_BOOTTIME` and `CLOCK_MONOTONIC` as follows: 155 156```python 157CLOCK_MONOTONIC 1000 1100 1200 1900 ... 2000 2100 158CLOCK_BOOTTIME 2000 2100 2200 2900 ... 3500 3600 159``` 160 161In this example `CLOCK_MONOTONIC` is 1000 ns ahead of `CLOCK_BOOTTIME` until 162T=2900. Then the two clocks go out of sync (e.g. the device is suspended) and, 163on the next snapshot, the two clocks are 1500 ns apart. 164 165If a `TracePacket` with `timestamp_clock_id=CLOCK_MONOTONIC` and 166`timestamp=1104` is seen, the clock sync logic will: 167 1681. Find the latest snapshot for `CLOCK_MONOTONIC` <= 1104 (in the example above 169 the 2nd one with `CLOCK_MONOTONIC=1100`) 1702. Compute the clock domain conversion to `CLOCK_BOOTTIME` by applying the 171 delta (1104 - 1100) to the corresponding `CLOCK_BOOTTIME` snapshot 172 (2100, so 2100 + (1104 - 1100) -> 2104). 173 174The example above is rather simple, because the source clock domain (i.e. the 175one specified by the `timestamp_clock_id` field) and the target clock domain 176(i.e. the trace time, `CLOCK_BOTTIME`) are snapshotted within the same 177`ClockSnapshot` packets. 178 179Clock domain conversion is possible also in more complex scenarios where the 180two domains are not directly connected, as long as a path exist between the two. 181 182In this sense `ClockSnapshot` packets define edges of an acyclic graph that is 183queried to perform clock domain conversions. All types of clock domains can be 184used in the graph search. 185 186In the more general case, the clock domain conversion logic operates as follows: 187 188* The shortest path between the source and target clock domains is identified, 189 using a breadth first search in the graph. 190* For each clock domain of the path identified, the timestamp is converted using 191 the aforementioned nearest neighbor resolution. 192 193This allows to deal with complex scenarios as follows: 194 195```python 196CUSTOM_CLOCK 1000 3000 197CLOCK_MONOTONIC 1100 1200 3200 4000 198CLOCK_BOOTTIME 5200 9000 199``` 200 201In the example above, there is no snapshot that directly links `CUSTOM_CLOCK` 202and `CLOCK_BOOTTIME`. However there is an indirect path that allows a conversion 203via `CUSTOM_CLOCK -> CLOCK_MONOTONIC -> CLOCK_BOOTTIME`. 204 205This allows to synchronize a hypothetical `TracePacket` that has 206`timestamp_clock_id=CUSTOM_CLOCK` and `timestamp=3503` as follows: 207 208```python 209#Step 1 210CUSTOM_CLOCK = 3503 211Nearest snapshot: {CUSTOM_CLOCK:3000, CLOCK_MONOTONIC:3200} 212CLOCK_MONOTONIC = (3503 - 3000) + 3200 = 3703 213 214#Step 2 215CLOCK_MONOTONIC = 3703 216Nearest snapshot: {CLOCK_MONOTONIC:1200, CLOCK_BOOTTIME:5200} 217CLOCK_BOOTTIME = (3703 - 1200) + 5200 = 7703 218``` 219 220## Caveats 221 222Clock resolution between two domains (A,B) is allowed only as long as all the 223clock domains in the A -> B path are monotonic (or at least look so in the 224`ClockSnapshot` packets). 225If non-monotonicity is detected at import time, the clock domain is excluded as 226a source path in the graph search and is allowed only as a target path. 227 228For instance, imagine capturing a trace that has both `CLOCK_BOOTTIME` 229and `CLOCK_REALTIME` in the night when daylight saving is applied, when the 230real-time clock jumps back from 3AM to 2AM. 231 232Such a trace would contain several snapshots that break bijectivity between the 233two clock domains. In this case converting a `CLOCK_BOOTTIME` timestamp to 234`CLOCK_REALTIME` is always possible without ambiguities (eventually two distinct 235timestamps can be resolved against the same `CLOCK_REALTIME` timestamp). 236The opposite is not allowed, because `CLOCK_REALTIME` timestamps between 2AM 237and 3AM are ambiguous and could be resolved against two different 238`CLOCK_BOOTTIME` timestamps). 239 240[6756fb05]: https://android-review.googlesource.com/c/platform/external/perfetto/+/1101915/ 241[clock_snapshot]: https://android.googlesource.com/platform/external/perfetto/+/refs/heads/master/protos/perfetto/trace/clock_snapshot.proto 242[timestamp_clock_id]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/trace_packet.proto#68 243[builtin_clocks]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/clock_snapshot.proto#25 244