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 contain a snapshot of: (i) the custom clock id [64, 127] and (ii) another 96 clock domain that can be resolved, at import time, against the default trace 97 clock domain (`CLOCK_BOOTTIME`) (see the [Operation section](#operation) 98 below). 99 100Collisions of `timestamp_clock_id` across two different `TraceWriter` sequences 101are okay. E.g., two data sources, unaware of each other, can both use clock ID 10264 to refer to two different clock domains. 103 104#### Globally-scoped clocks 105Globally-scoped clock domains work similarly to sequence-scoped clock domains, 106with the only difference that their scope is global and applies to all 107`TracePacket`(s) of the trace. 108 109The same `ClockSnapshot` rules as above apply. The only difference is that once 110a `ClockSnapshot` defines a clock domain with ID >= 128, that clock domain can 111be referred to by any `TracePacket` written by any `TraceWriter` sequence. 112 113Care must be taken to avoid collisions between global clock domains defined by 114different data sources unaware of each other. 115 116As such, it is **strongly discouraged** to just use the ID 128 (or any other 117arbitrarily chosen value). Instead the recommended pattern is: 118 119* Chose a fully qualified name for the clock domain 120 (e.g. `com.example.my_subsystem`) 121* Chose the clock ID as `HASH("com.example.my_subsystem") | 0x80000000` 122 where `HASH(x)` is the FNV-1a hash of the fully qualified clock domain name. 123 124### {#clock_snapshot} The ClockSnapshot trace packet 125 126The [`ClockSnapshot`][clock_snapshot] packet defines sync points between two or 127more clock domains. It conveys the notion *"at this point in time, the timestamp 128of the clock domains X,Y,Z was 1000, 2000, 3000."*. 129 130The trace importer ([Trace Processor](/docs/analysis/trace-processor.md)) uses this 131information to establish a mapping between these clock domain. For instance, 132to realize that 1042 on clock domain X == 3042 on clock domain Z. 133 134The `traced` service automatically emits `ClockSnapshot` packets for the builtin 135clock domains on a regular basis. 136 137A data source should emit `ClockSnapshot` packets only when using custom clock 138domains, either sequence-scoped or globally-scoped. 139 140It is *not* mandatory that the `ClockSnapshot` for a custom clock domain 141contains also a snapshot of `CLOCK_BOOTTIME` (although it is advisable to do 142so when possible). The Trace Processor can deal with multi-path clock domain 143resolution based on graph traversal (see the [Operation](#operation) section). 144 145## Operation 146 147At import time Trace Processor will attempt to convert the timestamp of each 148TracePacket down to the trace clock domain (`CLOCK_BOOTTIME`) using the 149`ClockSnapshot` packets seen until then using nearest neighbor approximation. 150 151For instance, assume that the trace contains `ClockSnapshot` for 152`CLOCK_BOOTTIME` and `CLOCK_MONOTONIC` as follows: 153 154```python 155CLOCK_MONOTONIC 1000 1100 1200 1900 ... 2000 2100 156CLOCK_BOOTTIME 2000 2100 2200 2900 ... 3500 3600 157``` 158 159In this example `CLOCK_MONOTONIC` is 1000 ns ahead of `CLOCK_BOOTTIME` until 160T=2900. Then the two clocks go out of sync (e.g. the device is suspended) and, 161on the next snapshot, the two clocks are 1500 ns apart. 162 163If a `TracePacket` with `timestamp_clock_id=CLOCK_MONOTONIC` and 164`timestamp=1104` is seen, the clock sync logic will: 165 1661. Find the latest snapshot for `CLOCK_MONOTONIC` <= 1104 (in the example above 167 the 2nd one with `CLOCK_MONOTONIC=1100`) 1682. Compute the clock domain conversion to `CLOCK_BOOTTIME` by applying the 169 delta (1104 - 1100) to the corresponding `CLOCK_BOOTTIME` snapshot 170 (2100, so 2100 + (1104 - 1100) -> 2104). 171 172The example above is rather simple, because the source clock domain (i.e. the 173one specified by the `timestamp_clock_id` field) and the target clock domain 174(i.e. the trace time, `CLOCK_BOTTIME`) are snapshotted within the same 175`ClockSnapshot` packets. 176 177Clock domain conversion is possible also in more complex scenarios where the 178two domains are not directly connected, as long as a path exist between the two. 179 180In this sense `ClockSnapshot` packets define edges of an acyclic graph that is 181queried to perform clock domain conversions. All types of clock domains can be 182used in the graph search. 183 184In the more general case, the clock domain conversion logic operates as follows: 185 186* The shortest path between the source and target clock domains is identified, 187 using a breadth first search in the graph. 188* For each clock domain of the path identified, the timestamp is converted using 189 the aforementioned nearest neighbor resolution. 190 191This allows to deal with complex scenarios as follows: 192 193```python 194CUSTOM_CLOCK 1000 3000 195CLOCK_MONOTONIC 1100 1200 3200 4000 196CLOCK_BOOTTIME 5200 9000 197``` 198 199In the example above, there is no snapshot that directly links `CUSTOM_CLOCK` 200and `CLOCK_BOOTTIME`. However there is an indirect path that allows a conversion 201via `CUSTOM_CLOCK -> CLOCK_MONOTONIC -> CLOCK_BOOTTIME`. 202 203This allows to synchronize a hypothetical `TracePacket` that has 204`timestamp_clock_id=CUSTOM_CLOCK` and `timestamp=3503` as follows: 205 206```python 207#Step 1 208CUSTOM_CLOCK = 3503 209Nearest snapshot: {CUSTOM_CLOCK:3000, CLOCK_MONOTONIC:3200} 210CLOCK_MONOTONIC = (3503 - 3000) + 3200 = 3703 211 212#Step 2 213CLOCK_MONOTONIC = 3703 214Nearest snapshot: {CLOCK_MONOTONIC:1200, CLOCK_BOOTTIME:5200} 215CLOCK_BOOTTIME = (3703 - 1200) + 5200 = 7703 216``` 217 218## Caveats 219 220Clock resolution between two domains (A,B) is allowed only as long as all the 221clock domains in the A -> B path are monotonic (or at least look so in the 222`ClockSnapshot` packets). 223If non-monotonicity is detected at import time, the clock domain is excluded as 224a source path in the graph search and is allowed only as a target path. 225 226For instance, imagine capturing a trace that has both `CLOCK_BOOTTIME` 227and `CLOCK_REALTIME` in the night when daylight saving is applied, when the 228real-time clock jumps back from 3AM to 2AM. 229 230Such a trace would contain several snapshots that break bijectivity between the 231two clock domains. In this case converting a `CLOCK_BOOTTIME` timestamp to 232`CLOCK_REALTIME` is always possible without ambiguities (eventually two distinct 233timestamps can be resolved against the same `CLOCK_REALTIME` timestamp). 234The opposite is not allowed, because `CLOCK_REALTIME` timestamps between 2AM 235and 3AM are ambiguous and could be resolved against two different 236`CLOCK_BOOTTIME` timestamps). 237 238[6756fb05]: https://android-review.googlesource.com/c/platform/external/perfetto/+/1101915/ 239[clock_snapshot]: https://android.googlesource.com/platform/external/perfetto/+/refs/heads/main/protos/perfetto/trace/clock_snapshot.proto 240[timestamp_clock_id]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/trace_packet.proto#68 241[builtin_clocks]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/clock_snapshot.proto#25 242