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:

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

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:

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:

Such ClockSnapshot:

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:

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:

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:

This allows to deal with complex scenarios as follows:

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:

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