Synchronization of multiple clock domains

As per 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 is able to rebuild the clock graph and use that to re-synchronize events on a global trace time, as long as the ClockSnapshot 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
2. The ClockSnapshot trace packet

The timestamp_clock_id field of TracePacket

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 (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 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 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.

The ClockSnapshot trace packet

The ClockSnapshot 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) 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 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:

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:

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:

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).