# Synchronization of multiple clock domains As per [6756fb05][6756fb05] Perfetto handles events using different clock domains. On top of the default set of builtin clock domains, new clock domains can be dynamically created at trace-time. Clock domains are allowed to drift from each other. At import time, Perfetto's [Trace Processor](/docs/analysis/trace-processor.md) is able to rebuild the clock graph and use that to re-synchronize events on a global trace time, as long as the [ClockSnapshot][clock_snapshot] packets are present in the trace. ## Problem statement In a complex multi-producer scenario, different data source can emit events using different clock domains. Some examples: * On Linux/Android, Ftrace events are emitted using the `CLOCK_BOOTTIME` clock, but the Android event log uses `CLOCK_REALTIME`. Some other data sources can use `CLOCK_MONOTONIC`. These clocks can drift over time from each other due to suspend/resume. * Graphics-related events are typically timestamped by the GPU, which can use a hardware clock source that drifts from the system clock. At trace-time, the data sources might not be able to use `CLOCK_BOOTTIME` (or even when possible, doing so might be prohibitively expensive). To solve this, we allow events to be recorded with different clock domains and re-synchronize them at import time using clock snapshots. ## Trace proto syntax Clock synchronization is based on two elements of the trace: 1. [The timestamp_clock_id field of TracePacket](#timestamp_clock_id) 2. [The ClockSnapshot trace packet](#clock_snapshot) ### {#timestamp_clock_id} The timestamp_clock_id field of TracePacket ```protobuf message TracePacket { optional uint64 timestamp = 8; // Specifies the ID of the clock used for the TracePacket |timestamp|. Can be // one of the built-in types from ClockSnapshot::BuiltinClocks, or a // producer-defined clock id. // If unspecified it defaults to BuiltinClocks::BOOTTIME. optional uint32 timestamp_clock_id = 58; ``` This (optional) field determines the clock domain for the packet. If omitted it refers to the default clock domain of the trace (`CLOCK_BOOTTIME` for Linux/Android). It present, this field can be set to either: * One of the [builtin clocks defined in clock_snapshot.proto][builtin_clocks] (e.g., `CLOCK_BOOTTIME`, `CLOCK_REALTIME`, `CLOCK_MONOTONIC`). These clocks have an ID <= 63. * A custom sequence-scoped clock, with 64 <= ID < 128 * A custom globally-scoped clock, with 128 <= ID < 2**32 #### Builtin clocks Builtin clocks cover the most common case of data sources using one of the POSIX clocks (see `man clock_gettime`). These clocks are periodically snapshotted by the `traced` service. The producer doesn't need to do anything other than set the `timestamp_clock_id` field in order to emit events that use these clocks. #### Sequence-scoped clocks Sequence-scoped clocks are application-defined clock domains that are valid only within the sequence of TracePacket(s) written by the same `TraceWriter` (i.e. TracePacket that have the same `trusted_packet_sequence_id` field). In most cases this really means *"events emitted by the same data source on the same thread"*. This covers the most common use case of a clock domain that is used only within a data source and not shared across different data sources. The main advantage of sequence-scoped clocks is that avoids the ID disambiguation problem and JustWorks™ for the most simple case. In order to make use of a custom sequence-scoped clock domain a data source must: * Emit its packets with a `timestamp_clock_id` in the range [64, 127] * Emit at least once a [`ClockSnapshot`][clock_snapshot] packet. Such `ClockSnapshot`: * Must be emitted on the same sequence (i.e. by the same `TraceWriter`) that is used to emit other `TracePacket`(s) that refer to such `timestamp_clock_id`. * Must be emitted before the custom clock is referred to by any `TracePacket` written by the same `TraceWriter`. * Must contain a snapshot of: (i) the custom clock id [64, 127] and (ii) another clock domain that can be resolved, at import time, against the default trace clock domain (`CLOCK_BOOTTIME`) (see the [Operation section](#operation) below). Collisions of `timestamp_clock_id` across two different `TraceWriter` sequences are okay. E.g., two data sources, unaware of each other, can both use clock ID 64 to refer to two different clock domains. #### Globally-scoped clocks Globally-scoped clock domains work similarly to sequence-scoped clock domains, with the only difference that their scope is global and applies to all `TracePacket`(s) of the trace. The same `ClockSnapshot` rules as above apply. The only difference is that once a `ClockSnapshot` defines a clock domain with ID >= 128, that clock domain can be referred to by any `TracePacket` written by any `TraceWriter` sequence. Care must be taken to avoid collisions between global clock domains defined by different data sources unaware of each other. As such, it is **strongly discouraged** to just use the ID 128 (or any other arbitrarily chosen value). Instead the recommended pattern is: * Chose a fully qualified name for the clock domain (e.g. `com.example.my_subsystem`) * Chose the clock ID as `HASH("com.example.my_subsystem") | 0x80000000` where `HASH(x)` is the FNV-1a hash of the fully qualified clock domain name. ### {#clock_snapshot} The ClockSnapshot trace packet The [`ClockSnapshot`][clock_snapshot] packet defines sync points between two or more clock domains. It conveys the notion *"at this point in time, the timestamp of the clock domains X,Y,Z was 1000, 2000, 3000."*. The trace importer ([Trace Processor](/docs/analysis/trace-processor.md)) uses this information to establish a mapping between these clock domain. For instance, to realize that 1042 on clock domain X == 3042 on clock domain Z. The `traced` service automatically emits `ClockSnapshot` packets for the builtin clock domains on a regular basis. A data source should emit `ClockSnapshot` packets only when using custom clock domains, either sequence-scoped or globally-scoped. It is *not* mandatory that the `ClockSnapshot` for a custom clock domain contains also a snapshot of `CLOCK_BOOTTIME` (although it is advisable to do so when possible). The Trace Processor can deal with multi-path clock domain resolution based on graph traversal (see the [Operation](#operation) section). ## Operation At import time Trace Processor will attempt to convert the timestamp of each TracePacket down to the trace clock domain (`CLOCK_BOOTTIME`) using the `ClockSnapshot` packets seen until then using nearest neighbor approximation. For instance, assume that the trace contains `ClockSnapshot` for `CLOCK_BOOTTIME` and `CLOCK_MONOTONIC` as follows: ```python CLOCK_MONOTONIC 1000 1100 1200 1900 ... 2000 2100 CLOCK_BOOTTIME 2000 2100 2200 2900 ... 3500 3600 ``` In this example `CLOCK_MONOTONIC` is 1000 ns ahead of `CLOCK_BOOTTIME` until T=2900. Then the two clocks go out of sync (e.g. the device is suspended) and, on the next snapshot, the two clocks are 1500 ns apart. If a `TracePacket` with `timestamp_clock_id=CLOCK_MONOTONIC` and `timestamp=1104` is seen, the clock sync logic will: 1. Find the latest snapshot for `CLOCK_MONOTONIC` <= 1104 (in the example above the 2nd one with `CLOCK_MONOTONIC=1100`) 2. Compute the clock domain conversion to `CLOCK_BOOTTIME` by applying the delta (1104 - 1100) to the corresponding `CLOCK_BOOTTIME` snapshot (2100, so 2100 + (1104 - 1100) -> 2104). The example above is rather simple, because the source clock domain (i.e. the one specified by the `timestamp_clock_id` field) and the target clock domain (i.e. the trace time, `CLOCK_BOTTIME`) are snapshotted within the same `ClockSnapshot` packets. Clock domain conversion is possible also in more complex scenarios where the two domains are not directly connected, as long as a path exist between the two. In this sense `ClockSnapshot` packets define edges of an acyclic graph that is queried to perform clock domain conversions. All types of clock domains can be used in the graph search. In the more general case, the clock domain conversion logic operates as follows: * The shortest path between the source and target clock domains is identified, using a breadth first search in the graph. * For each clock domain of the path identified, the timestamp is converted using the aforementioned nearest neighbor resolution. This allows to deal with complex scenarios as follows: ```python CUSTOM_CLOCK 1000 3000 CLOCK_MONOTONIC 1100 1200 3200 4000 CLOCK_BOOTTIME 5200 9000 ``` In the example above, there is no snapshot that directly links `CUSTOM_CLOCK` and `CLOCK_BOOTTIME`. However there is an indirect path that allows a conversion via `CUSTOM_CLOCK -> CLOCK_MONOTONIC -> CLOCK_BOOTTIME`. This allows to synchronize a hypothetical `TracePacket` that has `timestamp_clock_id=CUSTOM_CLOCK` and `timestamp=3503` as follows: ```python #Step 1 CUSTOM_CLOCK = 3503 Nearest snapshot: {CUSTOM_CLOCK:3000, CLOCK_MONOTONIC:3200} CLOCK_MONOTONIC = (3503 - 3000) + 3200 = 3703 #Step 2 CLOCK_MONOTONIC = 3703 Nearest snapshot: {CLOCK_MONOTONIC:1200, CLOCK_BOOTTIME:5200} CLOCK_BOOTTIME = (3703 - 1200) + 5200 = 7703 ``` ## Caveats Clock resolution between two domains (A,B) is allowed only as long as all the clock domains in the A -> B path are monotonic (or at least look so in the `ClockSnapshot` packets). If non-monotonicity is detected at import time, the clock domain is excluded as a source path in the graph search and is allowed only as a target path. For instance, imagine capturing a trace that has both `CLOCK_BOOTTIME` and `CLOCK_REALTIME` in the night when daylight saving is applied, when the real-time clock jumps back from 3AM to 2AM. Such a trace would contain several snapshots that break bijectivity between the two clock domains. In this case converting a `CLOCK_BOOTTIME` timestamp to `CLOCK_REALTIME` is always possible without ambiguities (eventually two distinct timestamps can be resolved against the same `CLOCK_REALTIME` timestamp). The opposite is not allowed, because `CLOCK_REALTIME` timestamps between 2AM and 3AM are ambiguous and could be resolved against two different `CLOCK_BOOTTIME` timestamps). [6756fb05]: https://android-review.googlesource.com/c/platform/external/perfetto/+/1101915/ [clock_snapshot]: https://android.googlesource.com/platform/external/perfetto/+/refs/heads/master/protos/perfetto/trace/clock_snapshot.proto [timestamp_clock_id]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/trace_packet.proto#68 [builtin_clocks]: https://android.googlesource.com/platform/external/perfetto/+/3e7ca4f5893f7d762ec24a2eac9a47343b226c6c/protos/perfetto/trace/clock_snapshot.proto#25