src/trace_processor/clock_tracker.cc - third_party/perfetto - Git at Google

 /*
  * Copyright (C) 2019 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "src/trace_processor/clock_tracker.h"

 #include <inttypes.h>

 #include <algorithm>
 #include <queue>

 #include "perfetto/base/logging.h"
 #include "perfetto/ext/base/hash.h"
 #include "src/trace_processor/trace_processor_context.h"
 #include "src/trace_processor/trace_storage.h"

 #include "protos/perfetto/trace/clock_snapshot.pbzero.h"

 namespace perfetto {
 namespace trace_processor {

 using Clock = protos::pbzero::ClockSnapshot::Clock;

 ClockTracker::ClockTracker(TraceProcessorContext* ctx)
     : context_(ctx), trace_time_clock_id_(Clock::BOOTTIME) {}

 ClockTracker::~ClockTracker() = default;

 void ClockTracker::AddSnapshot(const std::map<ClockId, int64_t>& clocks) {
   const auto snapshot_id = cur_snapshot_id_++;

   // Compute the fingerprint of the snapshot by hashing all clock ids. This is
   // used by the clock pathfinding logic.
   base::Hash hasher;
   for (const auto& id_and_ts : clocks)
     hasher.Update(id_and_ts.first);
   const auto snapshot_hash = static_cast<SnapshotHash>(hasher.digest());

   // Add a new entry in each clock's snapshot vector.
   for (const auto& id_and_ts : clocks) {
     ClockId clock_id = id_and_ts.first;
     ClockDomain& clock = clocks_[clock_id];
     const int64_t timestamp_ns = clock.ToNs(id_and_ts.second);
     ClockSnapshots& vect = clock.snapshots[snapshot_hash];

     // Clock ids in the range [64, 128) are sequence-scoped and must be
     // translated to global ids via SeqScopedClockIdToGlobal() before calling
     // this function.
     PERFETTO_DCHECK(!IsReservedSeqScopedClockId(clock_id));

     // Snapshot IDs must be always monotonic.
     PERFETTO_DCHECK(vect.snapshot_ids.empty() ||
                     vect.snapshot_ids.back() < snapshot_id);

     if (!vect.timestamps_ns.empty() &&
         timestamp_ns <= vect.timestamps_ns.back()) {
       // Clock is not monotonic.

       if (clock_id == trace_time_clock_id_) {
         // The trace clock cannot be non-monotonic.
         PERFETTO_ELOG(
             "Clock sync error: the trace clock (id=%" PRIu64
             ") is not "
             "monotonic at snapshot %" PRIu32 ". %" PRId64 " not > %" PRId64 ".",
             clock_id, snapshot_id, timestamp_ns, vect.timestamps_ns.back());
         context_->storage->IncrementStats(stats::invalid_clock_snapshots);
         return;
       }

       // For the other clocks the best thing we can do is mark it as
       // non-monotonic and refuse to use it as a source clock in the resolution
       // graph. We can still use it as a target clock, but not viceversa.
       // The concrete example is the CLOCK_REALTIME going 1h backwards during
       // daylight saving. We can still answer the question "what was the
       // REALTIME timestamp when BOOTTIME was X?" but we can't answer the
       // opposite question because there can be two valid BOOTTIME(s) for the
       // same REALTIME instant because of the 1:many relationship.
       non_monotonic_clocks_.insert(clock_id);

       // Erase all edges from the graph that start from this clock (but keep the
       // ones that end on this clock).
       auto begin = graph_.lower_bound(ClockGraphEdge{clock_id, 0, 0});
       auto end = graph_.lower_bound(ClockGraphEdge{clock_id + 1, 0, 0});
       graph_.erase(begin, end);
     }
     vect.snapshot_ids.emplace_back(snapshot_id);
     vect.timestamps_ns.emplace_back(timestamp_ns);
   }

   // Create graph edges for all the possible tuples of clocks in this snapshot.
   // If the snapshot contains clock a, b, c, d create edges [ab, ac, ad, bc, bd,
   // cd] and the symmetrical ones [ba, ca, da, bc, db, dc].
   // This is to store the information: Clock A is syncable to Clock B via the
   // snapshots of type (hash).
   // Clocks that were previously marked as non-monotonic won't be added as
   // valid sources.
   for (auto it1 = clocks.begin(); it1 != clocks.end(); ++it1) {
     auto it2 = it1;
     ++it2;
     for (; it2 != clocks.end(); ++it2) {
       if (!non_monotonic_clocks_.count(it1->first))
         graph_.emplace(it1->first, it2->first, snapshot_hash);

       if (!non_monotonic_clocks_.count(it2->first))
         graph_.emplace(it2->first, it1->first, snapshot_hash);
     }
   }
 }

 // Finds the shortest clock resolution path in the graph that allows to
 // translate a timestamp from |src| to |target| clocks.
 // The return value looks like the following: "If you want to convert a
 // timestamp from clock C1 to C2 you need to first convert C1 -> C3 using the
 // snapshot hash A, then convert C3 -> C2 via snapshot hash B".
 ClockTracker::ClockPath ClockTracker::FindPath(ClockId src, ClockId target) {
   // This is a classic breadth-first search. Each node in the queue holds also
   // the full path to reach that node.
   // We assume the graph is acyclic, if it isn't the ClockPath::kMaxLen will
   // stop the search anyways.
   PERFETTO_CHECK(src != target);
   std::queue<ClockPath> queue;
   queue.emplace(src);

   while (!queue.empty()) {
     ClockPath cur_path = queue.front();
     queue.pop();

     const ClockId cur_clock_id = cur_path.last;
     if (cur_clock_id == target)
       return cur_path;

     if (cur_path.len >= ClockPath::kMaxLen)
       continue;

     // Expore all the adjacent clocks.
     // The lower_bound() below returns an iterator to the first edge that starts
     // on |cur_clock_id|. The edges are sorted by (src, target, hash).
     for (auto it = std::lower_bound(graph_.begin(), graph_.end(),
                                     ClockGraphEdge(cur_clock_id, 0, 0));
          it != graph_.end() && std::get<0>(*it) == cur_clock_id; ++it) {
       ClockId next_clock_id = std::get<1>(*it);
       SnapshotHash hash = std::get<2>(*it);
       queue.push(ClockPath(cur_path, next_clock_id, hash));
     }
   }
   return ClockPath();  // invalid path.
 }

 base::Optional<int64_t> ClockTracker::Convert(ClockId src_clock_id,
                                               int64_t src_timestamp,
                                               ClockId target_clock_id) {
   // TODO(primiano): optimization: I bet A simple LRU cache of the form
   // (src_clock_id, target_clock_id, latest_timestamp, translation_ns) might
   // speed up most conversion allowing to skip FindPath and the iterations.

   PERFETTO_DCHECK(!IsReservedSeqScopedClockId(src_clock_id));
   PERFETTO_DCHECK(!IsReservedSeqScopedClockId(target_clock_id));

   ClockPath path = FindPath(src_clock_id, target_clock_id);
   if (!path.valid()) {
     context_->storage->IncrementStats(stats::clock_sync_failure);
     return base::nullopt;
   }

   // Iterate trough the path found and translate timestamps onto the new clock
   // domain on each step, until the target domain is reached.
   int64_t ns = GetClock(src_clock_id).ToNs(src_timestamp);
   for (uint32_t i = 0; i < path.len; ++i) {
     const ClockGraphEdge edge = path.at(i);
     const ClockDomain& cur_clock = GetClock(std::get<0>(edge));
     const ClockDomain& next_clock = GetClock(std::get<1>(edge));
     const SnapshotHash hash = std::get<2>(edge);

     // Find the closest timestamp within the snapshots of the source clock.
     const ClockSnapshots& cur_snap = cur_clock.GetSnapshot(hash);
     const auto& ts_vec = cur_snap.timestamps_ns;
     auto it = std::upper_bound(ts_vec.begin(), ts_vec.end(), ns);
     if (it != ts_vec.begin())
       --it;

     // Now lookup the snapshot id that matches the closest timestamp.
     size_t index = static_cast<size_t>(std::distance(ts_vec.begin(), it));
     PERFETTO_DCHECK(index < ts_vec.size());
     PERFETTO_DCHECK(cur_snap.snapshot_ids.size() == ts_vec.size());
     uint32_t snapshot_id = cur_snap.snapshot_ids[index];

     // And use that to retrieve the corresponding time in the next clock domain.
     // The snapshot id must exist in the target clock domain. If it doesn't
     // either the hash logic or the pathfinding logic are bugged.
     const ClockSnapshots& next_snap = next_clock.GetSnapshot(hash);
     auto next_it = std::lower_bound(next_snap.snapshot_ids.begin(),
                                     next_snap.snapshot_ids.end(), snapshot_id);
     PERFETTO_DCHECK(next_it != next_snap.snapshot_ids.end() &&
                     *next_it == snapshot_id);
     size_t next_index = static_cast<size_t>(
         std::distance(next_snap.snapshot_ids.begin(), next_it));
     PERFETTO_DCHECK(next_index < next_snap.snapshot_ids.size());
     int64_t next_timestamp_ns = next_snap.timestamps_ns[next_index];

     // The translated timestamp is the relative delta of the source timestamp
     // from the closest snapshot found (ns - *it), plus the timestamp in
     // the new clock domain for the same snapshot id.
     ns = (ns - *it) + next_timestamp_ns;

     // The last clock in the path must be the target clock.
     PERFETTO_DCHECK(i < path.len - 1 || std::get<1>(edge) == target_clock_id);
   }

   return ns;
 }

 }  // namespace trace_processor
 }  // namespace perfetto
	/*
	* Copyright (C) 2019 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "src/trace_processor/clock_tracker.h"

	#include <inttypes.h>

	#include <algorithm>
	#include <queue>

	#include "perfetto/base/logging.h"
	#include "perfetto/ext/base/hash.h"
	#include "src/trace_processor/trace_processor_context.h"
	#include "src/trace_processor/trace_storage.h"

	#include "protos/perfetto/trace/clock_snapshot.pbzero.h"

	namespace perfetto {
	namespace trace_processor {

	using Clock = protos::pbzero::ClockSnapshot::Clock;

	ClockTracker::ClockTracker(TraceProcessorContext* ctx)
	: context_(ctx), trace_time_clock_id_(Clock::BOOTTIME) {}

	ClockTracker::~ClockTracker() = default;

	void ClockTracker::AddSnapshot(const std::map<ClockId, int64_t>& clocks) {
	const auto snapshot_id = cur_snapshot_id_++;

	// Compute the fingerprint of the snapshot by hashing all clock ids. This is
	// used by the clock pathfinding logic.
	base::Hash hasher;
	for (const auto& id_and_ts : clocks)
	hasher.Update(id_and_ts.first);
	const auto snapshot_hash = static_cast<SnapshotHash>(hasher.digest());

	// Add a new entry in each clock's snapshot vector.
	for (const auto& id_and_ts : clocks) {
	ClockId clock_id = id_and_ts.first;
	ClockDomain& clock = clocks_[clock_id];
	const int64_t timestamp_ns = clock.ToNs(id_and_ts.second);
	ClockSnapshots& vect = clock.snapshots[snapshot_hash];

	// Clock ids in the range [64, 128) are sequence-scoped and must be
	// translated to global ids via SeqScopedClockIdToGlobal() before calling
	// this function.
	PERFETTO_DCHECK(!IsReservedSeqScopedClockId(clock_id));

	// Snapshot IDs must be always monotonic.
	PERFETTO_DCHECK(vect.snapshot_ids.empty() \|\|
	vect.snapshot_ids.back() < snapshot_id);

	if (!vect.timestamps_ns.empty() &&
	timestamp_ns <= vect.timestamps_ns.back()) {
	// Clock is not monotonic.

	if (clock_id == trace_time_clock_id_) {
	// The trace clock cannot be non-monotonic.
	PERFETTO_ELOG(
	"Clock sync error: the trace clock (id=%" PRIu64
	") is not "
	"monotonic at snapshot %" PRIu32 ". %" PRId64 " not > %" PRId64 ".",
	clock_id, snapshot_id, timestamp_ns, vect.timestamps_ns.back());
	context_->storage->IncrementStats(stats::invalid_clock_snapshots);
	return;
	}

	// For the other clocks the best thing we can do is mark it as
	// non-monotonic and refuse to use it as a source clock in the resolution
	// graph. We can still use it as a target clock, but not viceversa.
	// The concrete example is the CLOCK_REALTIME going 1h backwards during
	// daylight saving. We can still answer the question "what was the
	// REALTIME timestamp when BOOTTIME was X?" but we can't answer the
	// opposite question because there can be two valid BOOTTIME(s) for the
	// same REALTIME instant because of the 1:many relationship.
	non_monotonic_clocks_.insert(clock_id);

	// Erase all edges from the graph that start from this clock (but keep the
	// ones that end on this clock).
	auto begin = graph_.lower_bound(ClockGraphEdge{clock_id, 0, 0});
	auto end = graph_.lower_bound(ClockGraphEdge{clock_id + 1, 0, 0});
	graph_.erase(begin, end);
	}
	vect.snapshot_ids.emplace_back(snapshot_id);
	vect.timestamps_ns.emplace_back(timestamp_ns);
	}

	// Create graph edges for all the possible tuples of clocks in this snapshot.
	// If the snapshot contains clock a, b, c, d create edges [ab, ac, ad, bc, bd,
	// cd] and the symmetrical ones [ba, ca, da, bc, db, dc].
	// This is to store the information: Clock A is syncable to Clock B via the
	// snapshots of type (hash).
	// Clocks that were previously marked as non-monotonic won't be added as
	// valid sources.
	for (auto it1 = clocks.begin(); it1 != clocks.end(); ++it1) {
	auto it2 = it1;
	++it2;
	for (; it2 != clocks.end(); ++it2) {
	if (!non_monotonic_clocks_.count(it1->first))
	graph_.emplace(it1->first, it2->first, snapshot_hash);

	if (!non_monotonic_clocks_.count(it2->first))
	graph_.emplace(it2->first, it1->first, snapshot_hash);
	}
	}
	}

	// Finds the shortest clock resolution path in the graph that allows to
	// translate a timestamp from \|src\| to \|target\| clocks.
	// The return value looks like the following: "If you want to convert a
	// timestamp from clock C1 to C2 you need to first convert C1 -> C3 using the
	// snapshot hash A, then convert C3 -> C2 via snapshot hash B".
	ClockTracker::ClockPath ClockTracker::FindPath(ClockId src, ClockId target) {
	// This is a classic breadth-first search. Each node in the queue holds also
	// the full path to reach that node.
	// We assume the graph is acyclic, if it isn't the ClockPath::kMaxLen will
	// stop the search anyways.
	PERFETTO_CHECK(src != target);
	std::queue<ClockPath> queue;
	queue.emplace(src);

	while (!queue.empty()) {
	ClockPath cur_path = queue.front();
	queue.pop();

	const ClockId cur_clock_id = cur_path.last;
	if (cur_clock_id == target)
	return cur_path;

	if (cur_path.len >= ClockPath::kMaxLen)
	continue;

	// Expore all the adjacent clocks.
	// The lower_bound() below returns an iterator to the first edge that starts
	// on \|cur_clock_id\|. The edges are sorted by (src, target, hash).
	for (auto it = std::lower_bound(graph_.begin(), graph_.end(),
	ClockGraphEdge(cur_clock_id, 0, 0));
	it != graph_.end() && std::get<0>(*it) == cur_clock_id; ++it) {
	ClockId next_clock_id = std::get<1>(*it);
	SnapshotHash hash = std::get<2>(*it);
	queue.push(ClockPath(cur_path, next_clock_id, hash));
	}
	}
	return ClockPath(); // invalid path.
	}

	base::Optional<int64_t> ClockTracker::Convert(ClockId src_clock_id,
	int64_t src_timestamp,
	ClockId target_clock_id) {
	// TODO(primiano): optimization: I bet A simple LRU cache of the form
	// (src_clock_id, target_clock_id, latest_timestamp, translation_ns) might
	// speed up most conversion allowing to skip FindPath and the iterations.

	PERFETTO_DCHECK(!IsReservedSeqScopedClockId(src_clock_id));
	PERFETTO_DCHECK(!IsReservedSeqScopedClockId(target_clock_id));

	ClockPath path = FindPath(src_clock_id, target_clock_id);
	if (!path.valid()) {
	context_->storage->IncrementStats(stats::clock_sync_failure);
	return base::nullopt;
	}

	// Iterate trough the path found and translate timestamps onto the new clock
	// domain on each step, until the target domain is reached.
	int64_t ns = GetClock(src_clock_id).ToNs(src_timestamp);
	for (uint32_t i = 0; i < path.len; ++i) {
	const ClockGraphEdge edge = path.at(i);
	const ClockDomain& cur_clock = GetClock(std::get<0>(edge));
	const ClockDomain& next_clock = GetClock(std::get<1>(edge));
	const SnapshotHash hash = std::get<2>(edge);

	// Find the closest timestamp within the snapshots of the source clock.
	const ClockSnapshots& cur_snap = cur_clock.GetSnapshot(hash);
	const auto& ts_vec = cur_snap.timestamps_ns;
	auto it = std::upper_bound(ts_vec.begin(), ts_vec.end(), ns);
	if (it != ts_vec.begin())
	--it;

	// Now lookup the snapshot id that matches the closest timestamp.
	size_t index = static_cast<size_t>(std::distance(ts_vec.begin(), it));
	PERFETTO_DCHECK(index < ts_vec.size());
	PERFETTO_DCHECK(cur_snap.snapshot_ids.size() == ts_vec.size());
	uint32_t snapshot_id = cur_snap.snapshot_ids[index];

	// And use that to retrieve the corresponding time in the next clock domain.
	// The snapshot id must exist in the target clock domain. If it doesn't
	// either the hash logic or the pathfinding logic are bugged.
	const ClockSnapshots& next_snap = next_clock.GetSnapshot(hash);
	auto next_it = std::lower_bound(next_snap.snapshot_ids.begin(),
	next_snap.snapshot_ids.end(), snapshot_id);
	PERFETTO_DCHECK(next_it != next_snap.snapshot_ids.end() &&
	*next_it == snapshot_id);
	size_t next_index = static_cast<size_t>(
	std::distance(next_snap.snapshot_ids.begin(), next_it));
	PERFETTO_DCHECK(next_index < next_snap.snapshot_ids.size());
	int64_t next_timestamp_ns = next_snap.timestamps_ns[next_index];

	// The translated timestamp is the relative delta of the source timestamp
	// from the closest snapshot found (ns - *it), plus the timestamp in
	// the new clock domain for the same snapshot id.
	ns = (ns - *it) + next_timestamp_ns;

	// The last clock in the path must be the target clock.
	PERFETTO_DCHECK(i < path.len - 1 \|\| std::get<1>(edge) == target_clock_id);
	}

	return ns;
	}

	} // namespace trace_processor
	} // namespace perfetto