blob: c2612492f47cc95952914f0b1442fee10473b428 [file] [log] [blame]
/*
* 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.
*/
#ifndef SRC_TRACE_PROCESSOR_CLOCK_TRACKER_H_
#define SRC_TRACE_PROCESSOR_CLOCK_TRACKER_H_
#include <stdint.h>
#include <array>
#include <map>
#include <set>
#include <vector>
#include "perfetto/base/logging.h"
#include "perfetto/ext/base/optional.h"
namespace perfetto {
namespace trace_processor {
class TraceProcessorContext;
// This class handles synchronization of timestamps across different clock
// domains. This includes multi-hop conversions from two clocks A and D, e.g.
// A->B -> B->C -> C->D, even if we never saw a snapshot that contains A and D
// at the same time.
// The API is fairly simple (but the inner operation is not):
// - AddSnapshot(map<clock_id, timestamp>): pushes a set of clocks that have
// been snapshotted at the same time (within technical limits).
// - Convert(src_clock_id, src_timestamp, target_clock_id):
// converts a timestamp between two clock domains.
//
// Concepts:
// - Snapshot hash:
// As new snapshots are pushed via AddSnapshot() we compute a snapshot hash.
// Such hash is the hash(clock_ids) (only IDs, not their timestamps) and is
// used to find other snapshots that involve the same clock domains.
// Two clock snapshots have the same hash iff they snapshot the same set of
// clocks (the order of clocks is irrelevant).
// This hash is used to efficiently go from the clock graph pathfinder to the
// time-series obtained by appending the various snapshots.
// - Snapshot id:
// A simple monotonic counter that is incremented on each AddSnapshot() call.
//
// Data structures:
// - For each clock domain:
// - For each snapshot hash:
// - A logic vector of (snapshot_id, timestamp) tuples (physically stored
// as two vectors of the same length instead of a vector of pairs).
// This allows to efficiently binary search timestamps within a clock domain
// that were obtained through a particular snapshot.
//
// - A graph of edges (source_clock, target_clock) -> snapshot hash.
//
// Operation:
// Upon each AddSnapshot() call, we incrementally build an unweighted, directed
// graph, which has clock domains as nodes.
// The graph is timestamp-oblivious. As long as we see one snapshot that
// connects two clocks, we assume we'll always be able to convert between them.
// This graph is queried by the Convert() function to figure out the shortest
// path between clock domain, possibly involving hopping through snapshots of
// different type (i.e. different hash).
//
// Example:
// We see a snapshot, with hash S1, for clocks (A,B,C). We build the edges in
// the graph: A->B, B->C, A->C (and the symmetrical ones). In other words we
// keep track of the fact that we can convert between any of them using S1.
// Later we get another snapshot containing (C,E), this snapshot will have a
// different hash (S2, because Hash(C,E) != Hash(A,B,C)) and will add the edges
// C->E, E->C [via S2] to the graph.
// At this point when we are asked to convert a timestamp from A to E, or
// viceversa, we use a simple BFS to figure out a conversion path that is:
// A->C [via S1] + C->E [via S2].
//
// Visually:
// Assume we make the following calls:
// - AddSnapshot(A:10, B:100)
// - AddSnapshot(A:20, C:2000)
// - AddSnapshot(B:400, C:5000)
// - AddSnapshot(A:30, B:300)
// And assume Hash(A,B) = S1, H(A,C) = S2, H(B,C) = S3
// The vectors in the tracker will look as follows:
// Clock A:
// S1 {t:10, id:1} {t:30, id:4}
// S2 | {t:20, id:2} |
// | | |
// Clock B: | | |
// S1 {t:100, id:1} | {t:300, id:4}
// S3 | {t:400, id:3}
// | |
// Clock C: | |
// S2 {t: 2000, id: 2} |
// S3 {t:5000, id:3}
class ClockTracker {
public:
using ClockId = uint64_t;
// IDs in the range [64, 128) are reserved for sequence-scoped clock ids.
// They can't be passed directly in ClockTracker calls and must be resolved
// to 64-bit global clock ids by calling SeqScopedClockIdToGlobal().
static bool IsReservedSeqScopedClockId(ClockId clock_id) {
return clock_id >= 64 && clock_id < 128;
}
// Converts a sequence-scoped clock ids to a global clock id that can be
// passed as argument to ClockTracker functions.
static ClockId SeqScopedClockIdToGlobal(uint32_t seq_id, uint32_t clock_id) {
PERFETTO_DCHECK(IsReservedSeqScopedClockId(clock_id));
return (static_cast<uint64_t>(seq_id) << 32) | clock_id;
}
// Returns whether |global_clock_id| represents a sequence-scoped clock, i.e.
// a ClockId returned by SeqScopedClockIdToGlobal().
static bool ClockIsSeqScoped(ClockId global_clock_id) {
// If the id is > 2**32, this is a sequence-scoped clock id translated into
// the global namespace.
return (global_clock_id >> 32) > 0;
}
explicit ClockTracker(TraceProcessorContext*);
virtual ~ClockTracker();
// Clock description and its value in a snapshot.
struct ClockValue {
ClockValue(ClockId id, int64_t ts) : clock_id(id), absolute_timestamp(ts) {}
ClockValue(ClockId id, int64_t ts, int64_t unit, bool incremental)
: clock_id(id),
absolute_timestamp(ts),
unit_multiplier_ns(unit),
is_incremental(incremental) {}
ClockId clock_id;
int64_t absolute_timestamp;
int64_t unit_multiplier_ns = 1;
bool is_incremental = false;
};
// Appends a new snapshot for the given clock domains.
// This is typically called by the code that reads the ClockSnapshot packet.
void AddSnapshot(const std::vector<ClockValue>&);
base::Optional<int64_t> Convert(ClockId src_clock_id,
int64_t src_timestamp,
ClockId target_clock_id);
base::Optional<int64_t> ToTraceTime(ClockId clock_id, int64_t timestamp) {
if (clock_id == trace_time_clock_id_)
return timestamp;
return Convert(clock_id, timestamp, trace_time_clock_id_);
}
void SetTraceTimeClock(ClockId clock_id) {
PERFETTO_DCHECK(!IsReservedSeqScopedClockId(clock_id));
trace_time_clock_id_ = clock_id;
}
private:
using SnapshotHash = uint32_t;
// 0th argument is the source clock, 1st argument is the target clock.
using ClockGraphEdge = std::tuple<ClockId, ClockId, SnapshotHash>;
// A value-type object that carries the information about the path between
// two clock domains. It's used by the BFS algorithm.
struct ClockPath {
static constexpr size_t kMaxLen = 4;
ClockPath() = default;
ClockPath(const ClockPath&) = default;
// Constructs an invalid path with just a source node.
explicit ClockPath(ClockId clock_id) : last(clock_id) {}
// Constructs a path by appending a node to |prefix|.
// If |prefix| = [A,B] and clock_id = C, then |this| = [A,B,C].
ClockPath(const ClockPath& prefix, ClockId clock_id, SnapshotHash hash) {
PERFETTO_DCHECK(prefix.len < kMaxLen);
len = prefix.len + 1;
path = prefix.path;
path[prefix.len] = ClockGraphEdge{prefix.last, clock_id, hash};
last = clock_id;
}
bool valid() const { return len > 0; }
const ClockGraphEdge& at(uint32_t i) const {
PERFETTO_DCHECK(i < len);
return path[i];
}
uint32_t len = 0;
ClockId last = 0;
std::array<ClockGraphEdge, kMaxLen> path; // Deliberately uninitialized.
};
struct ClockSnapshots {
// Invariant: both vectors have the same length.
std::vector<uint32_t> snapshot_ids;
std::vector<int64_t> timestamps_ns;
};
struct ClockDomain {
// One time-series for each hash.
std::map<SnapshotHash, ClockSnapshots> snapshots;
// Multiplier for timestamps given in this domain.
int64_t unit_multiplier_ns = 1;
// Whether this clock domain encodes timestamps as deltas. This is only
// supported on sequence-local domains.
bool is_incremental = false;
// If |is_incremental| is true, this stores the most recent absolute
// timestamp in nanoseconds.
int64_t last_timestamp_ns = 0;
// Treats |timestamp| as delta timestamp if the clock uses incremental
// encoding, and as absolute timestamp otherwise.
int64_t ToNs(int64_t timestamp) {
if (!is_incremental)
return timestamp * unit_multiplier_ns;
int64_t delta_ns = timestamp * unit_multiplier_ns;
last_timestamp_ns += delta_ns;
return last_timestamp_ns;
}
const ClockSnapshots& GetSnapshot(uint32_t hash) const {
auto it = snapshots.find(hash);
PERFETTO_DCHECK(it != snapshots.end());
return it->second;
}
};
ClockTracker(const ClockTracker&) = delete;
ClockTracker& operator=(const ClockTracker&) = delete;
ClockPath FindPath(ClockId src, ClockId target);
ClockDomain* GetClock(ClockId clock_id) {
auto it = clocks_.find(clock_id);
PERFETTO_DCHECK(it != clocks_.end());
return &it->second;
}
TraceProcessorContext* const context_;
ClockId trace_time_clock_id_ = 0;
std::map<ClockId, ClockDomain> clocks_;
std::set<ClockGraphEdge> graph_;
std::set<ClockId> non_monotonic_clocks_;
uint32_t cur_snapshot_id_ = 0;
};
} // namespace trace_processor
} // namespace perfetto
#endif // SRC_TRACE_PROCESSOR_CLOCK_TRACKER_H_