Merge "Add reverse name lookup for channels"
diff --git a/aos/events/logging/boot_timestamp.h b/aos/events/logging/boot_timestamp.h
index 7eead2e..d0fde73 100644
--- a/aos/events/logging/boot_timestamp.h
+++ b/aos/events/logging/boot_timestamp.h
@@ -19,6 +19,11 @@
return {boot, duration + d};
}
+ BootDuration operator-() const { return {boot, -duration}; }
+ BootDuration operator-(monotonic_clock::duration d) const {
+ return {boot, duration - d};
+ }
+
bool operator==(const BootDuration &m2) const {
return boot == m2.boot && duration == m2.duration;
}
diff --git a/aos/events/logging/logger_test.cc b/aos/events/logging/logger_test.cc
index ec273a8..bb5b41e 100644
--- a/aos/events/logging/logger_test.cc
+++ b/aos/events/logging/logger_test.cc
@@ -4297,6 +4297,58 @@
ConfirmReadable(filenames);
}
+// Tests that we properly handle what used to be a time violation in one
+// direction. This can occur when one direction goes down after sending some
+// data, but the other keeps working. The down direction ends up resolving to a
+// straight line in the noncausal filter, where the direction which is still up
+// can cross that line. Really, time progressed along just fine but we assumed
+// that the offset was a line when it could have deviated by up to 1ms/second.
+TEST_P(MultinodeLoggerTest, OneDirectionTimeDrift) {
+ std::vector<std::string> filenames;
+
+ CHECK_EQ(pi1_index_, 0u);
+ CHECK_EQ(pi2_index_, 1u);
+
+ time_converter_.AddNextTimestamp(
+ distributed_clock::epoch(),
+ {BootTimestamp::epoch(), BootTimestamp::epoch()});
+
+ const chrono::nanoseconds before_disconnect_duration =
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(1000), chrono::milliseconds(1000)});
+
+ const chrono::nanoseconds test_duration =
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(1000), chrono::milliseconds(1000)}) +
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(10000),
+ chrono::milliseconds(10000) - chrono::milliseconds(5)}) +
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(10000),
+ chrono::milliseconds(10000) + chrono::milliseconds(5)});
+
+ const std::string kLogfile =
+ aos::testing::TestTmpDir() + "/multi_logfile2.1/";
+ util::UnlinkRecursive(kLogfile);
+
+ {
+ LoggerState pi2_logger = MakeLogger(pi2_);
+ pi2_logger.StartLogger(kLogfile);
+ event_loop_factory_.RunFor(before_disconnect_duration);
+
+ pi2_->Disconnect(pi1_->node());
+
+ event_loop_factory_.RunFor(test_duration);
+ pi2_->Connect(pi1_->node());
+
+ event_loop_factory_.RunFor(chrono::milliseconds(5000));
+ pi2_logger.AppendAllFilenames(&filenames);
+ }
+
+ const std::vector<LogFile> sorted_parts = SortParts(filenames);
+ ConfirmReadable(filenames);
+}
+
} // namespace testing
} // namespace logger
} // namespace aos
diff --git a/aos/network/multinode_timestamp_filter.cc b/aos/network/multinode_timestamp_filter.cc
index 87b9a81..b87d5b9 100644
--- a/aos/network/multinode_timestamp_filter.cc
+++ b/aos/network/multinode_timestamp_filter.cc
@@ -73,8 +73,8 @@
clock_offset_filter_for_node_[node_a]) {
// There's something in this direction, so we don't need to check the
// opposite direction to confirm we have observations.
- if (!filter.filter->timestamps_empty(base_clock_[node_a].boot,
- base_clock_[filter.b_index].boot)) {
+ if (!filter.filter->timestamps_empty(
+ base_clock_[node_a].boot, base_clock_[filter.b_index].boot)) {
continue;
}
@@ -97,8 +97,8 @@
for (const struct FilterPair &filter : clock_offset_filter_for_node_[i]) {
// There's nothing in this direction, so there will be nothing to
// validate.
- if (filter.filter->timestamps_empty(base_clock_[i].boot,
- base_clock_[filter.b_index].boot)) {
+ if (filter.filter->timestamps_empty(
+ base_clock_[i].boot, base_clock_[filter.b_index].boot)) {
// For a boot to exist, we need to have some observations between it and
// another boot. We wouldn't bother to build a problem to solve for
// this node otherwise. Confirm that is true so we at least get
@@ -113,9 +113,11 @@
continue;
}
const bool iteration = filter.filter->ValidateSolution(
- filter.pointer, solution[i], solution[filter.b_index]);
+ filter.b_filter, filter.pointer, solution[i],
+ solution[filter.b_index]);
if (!iteration) {
- filter.filter->ValidateSolution(filter.pointer, solution[i], 0.0,
+ filter.filter->ValidateSolution(filter.b_filter, filter.pointer,
+ solution[i], 0.0,
solution[filter.b_index], 0.0);
}
@@ -125,9 +127,12 @@
return success;
}
-Eigen::VectorXd TimestampProblem::Gradient(
- const Eigen::Ref<Eigen::VectorXd> time_offsets) {
- Eigen::VectorXd grad = Eigen::VectorXd::Zero(live_nodes_);
+TimestampProblem::Derivitives TimestampProblem::ComputeDerivitives(
+ const Eigen::Ref<Eigen::VectorXd> time_offsets) {
+ Derivitives result;
+ result.gradient = Eigen::VectorXd::Zero(live_nodes_);
+ result.hessian = Eigen::MatrixXd::Zero(live_nodes_, live_nodes_);
+
for (size_t i = 0; i < clock_offset_filter_for_node_.size(); ++i) {
for (struct FilterPair &filter : clock_offset_filter_for_node_[i]) {
// Especially when reboots are involved, it isn't guarenteed that there
@@ -164,51 +169,37 @@
const std::pair<NoncausalTimestampFilter::Pointer, double> offset_error =
filter.filter->OffsetError(
- filter.pointer, base_clock_[i], time_offsets(a_solution_index),
- base_clock_[filter.b_index], time_offsets(b_solution_index));
+ filter.b_filter, filter.pointer, base_clock_[i],
+ time_offsets(a_solution_index), base_clock_[filter.b_index],
+ time_offsets(b_solution_index));
const double error = 2.0 * (offset_error.second - kMinNetworkDelay);
filter.pointer = offset_error.first;
- grad(a_solution_index) += -error;
- grad(b_solution_index) += error;
- }
- }
- return grad;
-}
+ result.gradient(a_solution_index) += -error;
+ result.gradient(b_solution_index) += error;
-Eigen::MatrixXd TimestampProblem::Hessian(
- const Eigen::Ref<Eigen::VectorXd> /*time_offsets*/) const {
- Eigen::MatrixXd hessian = Eigen::MatrixXd::Zero(live_nodes_, live_nodes_);
-
- for (size_t i = 0; i < clock_offset_filter_for_node_.size(); ++i) {
- for (const struct FilterPair &filter : clock_offset_filter_for_node_[i]) {
// Reminder, our cost function has the following form.
// ((tb - (1 + ma) ta - ba)^2
// We are ignoring the slope when taking the derivative and applying the
// chain rule to keep the gradient smooth. This means that the Hessian is
// 2 for d^2 cost/dta^2 and d^2 cost/dtb^2
- const size_t a_solution_index = NodeToFullSolutionIndex(i);
- const size_t b_solution_index = NodeToFullSolutionIndex(filter.b_index);
- hessian(a_solution_index, a_solution_index) += 2;
- hessian(b_solution_index, a_solution_index) += -2;
- hessian(a_solution_index, b_solution_index) =
- hessian(b_solution_index, a_solution_index);
- hessian(b_solution_index, b_solution_index) += 2;
+ result.hessian(a_solution_index, a_solution_index) += 2;
+ result.hessian(b_solution_index, a_solution_index) += -2;
+ result.hessian(a_solution_index, b_solution_index) =
+ result.hessian(b_solution_index, a_solution_index);
+ result.hessian(b_solution_index, b_solution_index) += 2;
}
}
- return hessian;
+ return result;
}
std::tuple<Eigen::VectorXd, size_t> TimestampProblem::Newton(
const Eigen::Ref<Eigen::VectorXd> time_offsets,
const std::vector<logger::BootTimestamp> &points) {
CHECK_GT(live_nodes_, 0u) << ": No live nodes to solve for.";
- // TODO(austin): Each of the DCost functions does a binary search of the
- // timestamps list. By the time we have computed the gradient and Hessian,
- // we've done 5 binary searches for the same information.
- const Eigen::VectorXd grad = Gradient(time_offsets);
- const Eigen::MatrixXd hessian = Hessian(time_offsets);
+ const Derivitives derivitives = ComputeDerivitives(time_offsets);
+
const Eigen::MatrixXd constraint_jacobian =
Eigen::MatrixXd::Ones(1, live_nodes_) / static_cast<double>(live_nodes_);
// https://www.cs.purdue.edu/homes/jhonorio/16spring-cs52000-equality.pdf
@@ -274,13 +265,13 @@
Eigen::MatrixXd a;
a.resize(live_nodes_ + 1, live_nodes_ + 1);
- a.block(0, 0, live_nodes_, live_nodes_) = hessian;
+ a.block(0, 0, live_nodes_, live_nodes_) = derivitives.hessian;
a.block(0, live_nodes_, live_nodes_, 1) = constraint_jacobian.transpose();
a.block(live_nodes_, 0, 1, live_nodes_) = constraint_jacobian;
a(live_nodes_, live_nodes_) = 0.0;
Eigen::VectorXd b = Eigen::VectorXd::Zero(live_nodes_ + 1);
- b.block(0, 0, live_nodes_, 1) = -grad;
+ b.block(0, 0, live_nodes_, 1) = -derivitives.gradient;
// Now, we want to set b(live_nodes_) to be -time_offset for the earliest
// clock.
@@ -341,7 +332,8 @@
Eigen::MatrixXd::Ones(1, live_nodes_) /
static_cast<double>(live_nodes_);
Eigen::VectorXd adjusted_grad =
- Gradient(data) + step(live_nodes_) * constraint_jacobian.transpose();
+ ComputeDerivitives(data).gradient +
+ step(live_nodes_) * constraint_jacobian.transpose();
VLOG(2) << "Adjusted grad " << solution_number << " -> "
<< std::setprecision(12) << std::fixed << std::setfill(' ')
@@ -454,12 +446,12 @@
// report.
gradients[i].emplace_back(
std::string("- ") +
- filter.filter->DebugOffsetError(filter.pointer, base_clock_[i], 0.0,
- base_clock_[filter.b_index], 0.0, i,
- filter.b_index));
+ filter.filter->DebugOffsetError(
+ filter.b_filter, filter.pointer, base_clock_[i], 0.0,
+ base_clock_[filter.b_index], 0.0, i, filter.b_index));
gradients[filter.b_index].emplace_back(filter.filter->DebugOffsetError(
- filter.pointer, base_clock_[i], 0.0, base_clock_[filter.b_index],
- 0.0, i, filter.b_index));
+ filter.b_filter, filter.pointer, base_clock_[i], 0.0,
+ base_clock_[filter.b_index], 0.0, i, filter.b_index));
}
}
}
diff --git a/aos/network/multinode_timestamp_filter.h b/aos/network/multinode_timestamp_filter.h
index ea52b23..eff6179 100644
--- a/aos/network/multinode_timestamp_filter.h
+++ b/aos/network/multinode_timestamp_filter.h
@@ -101,10 +101,16 @@
return solution_node;
}
- // Returns the Hessian of the cost function at time_offsets.
- Eigen::MatrixXd Hessian(const Eigen::Ref<Eigen::VectorXd> time_offsets) const;
- // Returns the gradient of the cost function at time_offsets.
- Eigen::VectorXd Gradient(const Eigen::Ref<Eigen::VectorXd> time_offsets);
+ // The derivitives and other work products needed for constrained newtons
+ // method.
+ struct Derivitives {
+ Eigen::VectorXd gradient;
+ Eigen::MatrixXd hessian;
+ };
+
+ // Returns the gradient and Hessian of the cost function at time_offsets.
+ Derivitives ComputeDerivitives(
+ const Eigen::Ref<Eigen::VectorXd> time_offsets);
// Returns the newton step of the timestamp problem, and the node which was
// used for the equality constraint. The last term is the scalar on the
diff --git a/aos/network/multinode_timestamp_filter_test.cc b/aos/network/multinode_timestamp_filter_test.cc
index 49f20da..841ff4d 100644
--- a/aos/network/multinode_timestamp_filter_test.cc
+++ b/aos/network/multinode_timestamp_filter_test.cc
@@ -391,10 +391,10 @@
// Confirm that the error is almost equal for both directions. The solution
// is an integer solution, so there will be a little bit of error left over.
EXPECT_NEAR(
- a.OffsetError(NoncausalTimestampFilter::Pointer(),
+ a.OffsetError(nullptr, NoncausalTimestampFilter::Pointer(),
std::get<0>(result1)[0], 0.0, std::get<0>(result1)[1], 0.0)
.second -
- b.OffsetError(NoncausalTimestampFilter::Pointer(),
+ b.OffsetError(nullptr, NoncausalTimestampFilter::Pointer(),
std::get<0>(result1)[1], 0.0, std::get<0>(result1)[0],
0.0)
.second,
diff --git a/aos/network/timestamp_filter.cc b/aos/network/timestamp_filter.cc
index 1a7bc6d..de150c5 100644
--- a/aos/network/timestamp_filter.cc
+++ b/aos/network/timestamp_filter.cc
@@ -490,7 +490,8 @@
std::pair<Pointer, std::pair<std::tuple<BootTimestamp, BootDuration>,
std::tuple<BootTimestamp, BootDuration>>>
-NoncausalTimestampFilter::FindTimestamps(Pointer pointer, BootTimestamp ta_base,
+NoncausalTimestampFilter::FindTimestamps(const NoncausalTimestampFilter *other,
+ Pointer pointer, BootTimestamp ta_base,
double ta, size_t sample_boot) const {
CHECK_GE(ta, 0.0);
CHECK_LT(ta, 1.0);
@@ -498,7 +499,7 @@
// Since ta is less than an integer, and timestamps should be at least 1 ns
// apart, we can ignore ta if we make sure that the end of the segment is
// strictly > than ta_base.
- return FindTimestamps(pointer, ta_base, sample_boot);
+ return FindTimestamps(other, pointer, ta_base, sample_boot);
}
std::pair<
@@ -506,14 +507,68 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
NoncausalTimestampFilter::SingleFilter::FindTimestamps(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const {
CHECK_GE(ta, 0.0);
CHECK_LT(ta, 1.0);
// Since ta is less than an integer, and timestamps should be at least 1 ns
// apart, we can ignore ta if we make sure that the end of the segment is
// strictly > than ta_base.
- return FindTimestamps(pointer, ta_base);
+ return FindTimestamps(other, pointer, ta_base);
+}
+
+std::pair<
+ Pointer,
+ std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
+NoncausalTimestampFilter::InterpolateWithOtherFilter(
+ Pointer pointer, monotonic_clock::time_point ta,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1) {
+ // We have 2 timestamps bookending everything, and a list of points in the
+ // middle.
+ //
+ // There are really 3 cases. The time is before the hunk in the middle, after
+ // the hunk in the middle, or in the hunk in the middle.
+ if (ta <= std::get<0>(pointer.other_points_[0].second)) {
+ // We are before the hunk! Use the start point, and the beginning of the
+ // hunk.
+ t1 = pointer.other_points_[0].second;
+ CHECK_LE(
+ absl::int128(std::abs((std::get<1>(t1) - std::get<1>(t0)).count())) *
+ absl::int128(MaxVelocityRatio::den),
+ absl::int128((std::get<0>(t1) - std::get<0>(t0)).count()) *
+ absl::int128(MaxVelocityRatio::num))
+ << ": t0 " << TimeString(t0) << ", t1 " << TimeString(t1);
+ } else if (ta >
+ std::get<0>(pointer.other_points_[pointer.other_points_.size() - 1]
+ .second)) {
+ // We are after the hunk! Use the end point, and the end of the
+ // hunk.
+ t0 = pointer.other_points_[pointer.other_points_.size() - 1].second;
+ CHECK_LE(
+ absl::int128(std::abs((std::get<1>(t1) - std::get<1>(t0)).count())) *
+ absl::int128(MaxVelocityRatio::den),
+ absl::int128((std::get<0>(t1) - std::get<0>(t0)).count()) *
+ absl::int128(MaxVelocityRatio::num))
+ << ": t0 " << TimeString(t0) << ", t1 " << TimeString(t1);
+ } else {
+ // We are inside the hunk. Find the points bounding it.
+ CHECK_GT(pointer.other_points_.size(), 1u);
+
+ auto it = std::upper_bound(
+ pointer.other_points_.begin() + 1, pointer.other_points_.end() - 1, ta,
+ [](monotonic_clock::time_point ta,
+ std::pair<size_t, std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>>
+ t) { return ta < std::get<0>(t.second); });
+
+ t0 = (it - 1)->second;
+ t1 = it->second;
+ }
+ DCHECK_LT(std::get<0>(t0), std::get<0>(t1));
+ return std::make_pair(pointer, std::make_pair(t0, t1));
}
std::pair<
@@ -521,9 +576,13 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
NoncausalTimestampFilter::SingleFilter::FindTimestamps(
- Pointer pointer, monotonic_clock::time_point ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const {
CHECK_GT(timestamps_size(), 1u);
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0;
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1;
+
// boot_filter_ is non-null when the rest of the contents are valid. Make
// sure it's pointing to this filter, and the pointer is in bounds.
if (pointer.boot_filter_ != nullptr &&
@@ -557,13 +616,29 @@
<< std::get<1>(pointer.t1_).count() << "ns";
}
- std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0 =
- timestamp(pointer.index_);
+ t0 = timestamp(pointer.index_);
if (ta >= std::get<0>(t0)) {
- std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1 =
- timestamp(pointer.index_ + 1);
+ t1 = timestamp(pointer.index_ + 1);
if (ta < std::get<0>(t1)) {
- return std::make_pair(pointer, std::make_pair(t0, t1));
+ if (pointer.other_points_.empty()) {
+ return std::make_pair(pointer, std::make_pair(t0, t1));
+ }
+
+ // Er, we shouldn't be able to have a non-empty other_points_ without
+ // having other and points...
+ CHECK(other != nullptr);
+ CHECK(!other->timestamps_empty());
+
+ // TODO(austin): Is there a cheaper way to verify nothing has changed?
+ // Should we add a generation counter of some sort?
+ for (const auto &point : pointer.other_points_) {
+ const auto other_point = other->timestamps_[point.first];
+ CHECK(std::get<0>(other_point) + std::get<1>(other_point) ==
+ std::get<0>(point.second))
+ << ": Cache changed";
+ }
+
+ return InterpolateWithOtherFilter(pointer, ta, t0, t1);
}
}
}
@@ -581,11 +656,65 @@
const size_t index = std::distance(timestamps_.begin(), it);
pointer.index_ = index - 1;
- std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t0 =
- pointer.t0_ = timestamp(index - 1);
- std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1 =
- pointer.t1_ = timestamp(index);
+ t0 = timestamp(index - 1);
+ pointer.t0_ = t0;
+ t1 = timestamp(index);
+ pointer.t1_ = t1;
+ if (other != nullptr && !other->timestamps_empty()) {
+ // Ok, we now need to find all points within our range in the matched
+ // filter.
+ auto other_t0_it =
+ std::lower_bound(other->timestamps_.begin(), other->timestamps_.end(),
+ std::get<0>(pointer.t0_),
+ [](std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>
+ t,
+ monotonic_clock::time_point ta) {
+ return ta > std::get<0>(t) + std::get<1>(t);
+ });
+ auto other_t1_it = std::upper_bound(
+ other_t0_it, other->timestamps_.end(), std::get<0>(pointer.t1_),
+ [](monotonic_clock::time_point ta,
+ std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>
+ t) { return ta < std::get<0>(t) + std::get<1>(t); });
+
+ if (std::get<0>(*other_t0_it) + std::get<1>(*other_t0_it) <
+ std::get<0>(pointer.t1_)) {
+ pointer.other_points_.clear();
+
+ // Now, we've got a range. [other_t0_it, other_t1_it).
+ for (auto other_it = other_t0_it; other_it != other_t1_it; ++other_it) {
+ const std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>
+ flipped_point =
+ std::make_tuple(std::get<0>(*other_it) + std::get<1>(*other_it),
+ -std::get<1>(*other_it) - kMinNetworkDelay());
+
+ // If the new point from the opposite direction filter is below the
+ // interpolated value at that point, then the opposite direction point
+ // defines a new min and we should take it.
+ if (NoncausalTimestampFilter::InterpolateOffset(
+ pointer.t0_, pointer.t1_, std::get<0>(flipped_point)) >
+ std::get<1>(flipped_point)) {
+ // Add it to the list of points to consider.
+ pointer.other_points_.emplace_back(std::make_pair(
+ std::distance(other->timestamps_.begin(), other_it),
+ flipped_point));
+ }
+ }
+
+ if (pointer.other_points_.size() > 0) {
+ return InterpolateWithOtherFilter(pointer, ta, t0, t1);
+ }
+ }
+
+ // other_t0_it will always be > t0, even if it is at the end.
+ // 1) other_t0_it < t0
+ // 2) other_t0_it < t1
+ //
+ // t0_it will always be > x.
+ }
return std::make_pair(pointer, std::make_pair(t0, t1));
}
@@ -766,7 +895,8 @@
std::pair<Pointer, chrono::nanoseconds>
NoncausalTimestampFilter::SingleFilter::Offset(
- Pointer pointer, monotonic_clock::time_point ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const {
CHECK_GT(timestamps_size(), 0u);
if (IsOutsideSamples(ta, 0.)) {
// Special case when size = 1 or if we're asked to extrapolate to
@@ -781,7 +911,7 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta);
+ points = FindTimestamps(other, pointer, ta);
return std::make_pair(points.first,
NoncausalTimestampFilter::InterpolateOffset(
points.second.first, points.second.second, ta));
@@ -789,7 +919,8 @@
std::pair<Pointer, std::pair<chrono::nanoseconds, double>>
NoncausalTimestampFilter::SingleFilter::Offset(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const {
CHECK_GT(timestamps_size(), 0u) << node_names_;
if (IsOutsideSamples(ta_base, ta)) {
// Special case size = 1 or ta_base before first timestamp or
@@ -809,7 +940,7 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta_base, ta);
+ points = FindTimestamps(other, pointer, ta_base, ta);
CHECK_LT(std::get<0>(points.second.first), std::get<0>(points.second.second));
// Return both the integer and double portion together to save a timestamp
// lookup.
@@ -823,13 +954,14 @@
}
std::pair<Pointer, double> NoncausalTimestampFilter::SingleFilter::OffsetError(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
const std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> offset =
- Offset(pointer, ta_base, ta);
+ Offset(other, pointer, ta_base, ta);
// Compute the integer portion first, and the double portion second. Subtract
// the results of each. This handles large offsets without losing precision.
@@ -840,8 +972,9 @@
}
std::string NoncausalTimestampFilter::DebugOffsetError(
- Pointer pointer, BootTimestamp ta_base, double ta, BootTimestamp tb_base,
- double tb, size_t node_a, size_t node_b) const {
+ const NoncausalTimestampFilter *other, Pointer pointer,
+ BootTimestamp ta_base, double ta, BootTimestamp tb_base, double tb,
+ size_t node_a, size_t node_b) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
@@ -869,7 +1002,13 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>
- points = f->filter.FindTimestamps(pointer, ta_base.time, ta).second;
+ points = f->filter
+ .FindTimestamps(
+ other == nullptr
+ ? nullptr
+ : &other->filter(tb_base.boot, ta_base.boot)->filter,
+ pointer, ta_base.time, ta)
+ .second;
// As a reminder, our cost function is essentially:
// ((tb - ta - (ma ta + ba))^2
@@ -902,7 +1041,8 @@
}
bool NoncausalTimestampFilter::SingleFilter::ValidateSolution(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
@@ -927,6 +1067,7 @@
// We want to do offset + ta > tb, but we need to do it with minimal
// numerical precision problems.
+ // See below for why this is a >=
if (static_cast<double>((offset_base + ta_base - tb_base).count()) >=
tb - ta - offset_remainder) {
LOG(ERROR) << node_names_ << " "
@@ -945,12 +1086,13 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta_base, ta);
+ points = FindTimestamps(other, pointer, ta_base, ta);
const chrono::nanoseconds offset_base =
NoncausalTimestampFilter::InterpolateOffset(
points.second.first, points.second.second, ta_base, ta);
const double offset = NoncausalTimestampFilter::InterpolateOffsetRemainder(
points.second.first, points.second.second, ta_base, ta);
+ // See below for why this is a >=
if (static_cast<double>((offset_base + ta_base - tb_base).count()) >=
tb - offset - ta) {
LOG(ERROR) << node_names_ << " "
@@ -964,7 +1106,8 @@
}
bool NoncausalTimestampFilter::SingleFilter::ValidateSolution(
- Pointer pointer, aos::monotonic_clock::time_point ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta,
aos::monotonic_clock::time_point tb) const {
CHECK_GT(timestamps_size(), 0u);
if (ta < std::get<0>(timestamp(0)) && has_popped_) {
@@ -981,6 +1124,9 @@
const chrono::nanoseconds offset =
NoncausalTimestampFilter::ExtrapolateOffset(reference_timestamp.second,
ta);
+ // Note: this needs to be >=. The simulation code doesn't give us a good
+ // way to preserve order well enough to have causality preserved when things
+ // happen at the same point in time.
if (offset + ta >= tb) {
LOG(ERROR) << node_names_ << " " << TimeString(ta, offset)
<< " > solution time " << tb;
@@ -993,10 +1139,14 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta);
+ points = FindTimestamps(other, pointer, ta);
const chrono::nanoseconds offset =
NoncausalTimestampFilter::InterpolateOffset(points.second.first,
points.second.second, ta);
+
+ // Note: this needs to be >=. The simulation code doesn't give us a good
+ // way to preserve order well enough to have causality preserved when things
+ // happen at the same point in time.
if (offset + ta >= tb) {
LOG(ERROR) << node_names_ << " " << TimeString(ta, offset)
<< " > solution time " << tb;
diff --git a/aos/network/timestamp_filter.h b/aos/network/timestamp_filter.h
index d85154e..fd430ce 100644
--- a/aos/network/timestamp_filter.h
+++ b/aos/network/timestamp_filter.h
@@ -25,6 +25,9 @@
return static_cast<double>(MaxVelocityRatio::num) /
static_cast<double>(MaxVelocityRatio::den);
}
+inline constexpr std::chrono::nanoseconds kMinNetworkDelay() {
+ return std::chrono::nanoseconds(2);
+}
// This class handles filtering differences between clocks across a network.
//
@@ -304,38 +307,58 @@
std::make_tuple(monotonic_clock::min_time, std::chrono::nanoseconds(0));
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1_ =
std::make_tuple(monotonic_clock::min_time, std::chrono::nanoseconds(0));
+
+ // List of points and their associated times going the other way.
+ std::vector<std::pair<size_t, std::tuple<monotonic_clock::time_point,
+ std::chrono::nanoseconds>>>
+ other_points_;
};
// Returns the error between the offset in the provided timestamps, and the
// offset at ta. Also returns a pointer to the timestamps used for the
// lookup to be passed back in again for a more efficient second lookup.
- std::pair<Pointer, double> OffsetError(Pointer pointer,
+ std::pair<Pointer, double> OffsetError(const NoncausalTimestampFilter *other,
+ Pointer pointer,
logger::BootTimestamp ta_base,
double ta,
logger::BootTimestamp tb_base,
double tb) const {
const BootFilter *boot_filter = filter(pointer, ta_base.boot, tb_base.boot);
+ const SingleFilter *other_filter =
+ other == nullptr
+ ? nullptr
+ : other->maybe_single_filter(tb_base.boot, ta_base.boot);
std::pair<Pointer, double> result = boot_filter->filter.OffsetError(
- pointer, ta_base.time, ta, tb_base.time, tb);
+ other_filter, pointer, ta_base.time, ta, tb_base.time, tb);
result.first.boot_filter_ = boot_filter;
return result;
}
// Returns the string representation of 2 * OffsetError(ta, tb)
- std::string DebugOffsetError(Pointer pointer, logger::BootTimestamp ta_base,
+ std::string DebugOffsetError(const NoncausalTimestampFilter *other,
+ Pointer pointer, logger::BootTimestamp ta_base,
double ta, logger::BootTimestamp tb_base,
double tb, size_t node_a, size_t node_b) const;
// Confirms that the solution meets the constraints. Returns true on success.
- bool ValidateSolution(Pointer pointer, logger::BootTimestamp ta,
+ bool ValidateSolution(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta,
logger::BootTimestamp tb) const {
+ const SingleFilter *other_filter =
+ other == nullptr ? nullptr
+ : other->maybe_single_filter(tb.boot, ta.boot);
return filter(pointer, ta.boot, tb.boot)
- ->filter.ValidateSolution(pointer, ta.time, tb.time);
+ ->filter.ValidateSolution(other_filter, pointer, ta.time, tb.time);
}
- bool ValidateSolution(Pointer pointer, logger::BootTimestamp ta_base,
- double ta, logger::BootTimestamp tb_base,
- double tb) const {
+ bool ValidateSolution(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta,
+ logger::BootTimestamp tb_base, double tb) const {
+ const SingleFilter *other_filter =
+ other == nullptr
+ ? nullptr
+ : other->maybe_single_filter(tb_base.boot, ta_base.boot);
return filter(pointer, ta_base.boot, tb_base.boot)
- ->filter.ValidateSolution(pointer, ta_base.time, ta, tb_base.time, tb);
+ ->filter.ValidateSolution(other_filter, pointer, ta_base.time, ta,
+ tb_base.time, tb);
}
// Adds a new sample to our filtered timestamp list.
@@ -416,6 +439,10 @@
// Returns the next timestamp in the queue if available without incrementing
// the pointer. This, Consume, and FreezeUntil work together to allow
// tracking and freezing timestamps which have been combined externally.
+ //
+ // This doesn't report the virtual points added by the opposite filter
+ // because solving for them doesn't add any additional value. We will already
+ // be solving the other direction.
std::optional<std::tuple<logger::BootTimestamp, logger::BootDuration>>
Observe() const {
if (filters_.size() == 0u) {
@@ -478,20 +505,29 @@
// Public for testing.
// Returns the offset for the point in time, using the timestamps in the deque
// to form a polyline used to interpolate.
- logger::BootDuration Offset(Pointer pointer, logger::BootTimestamp ta,
+ logger::BootDuration Offset(const NoncausalTimestampFilter *other,
+ Pointer pointer, logger::BootTimestamp ta,
size_t sample_boot) const {
- return {
- sample_boot,
- filter(ta.boot, sample_boot)->filter.Offset(pointer, ta.time).second};
+ return {sample_boot,
+ filter(ta.boot, sample_boot)
+ ->filter
+ .Offset(other == nullptr
+ ? nullptr
+ : &other->filter(sample_boot, ta.boot)->filter,
+ pointer, ta.time)
+ .second};
}
- std::pair<logger::BootDuration, double> Offset(Pointer pointer,
- logger::BootTimestamp ta_base,
- double ta,
- size_t sample_boot) const {
+ std::pair<logger::BootDuration, double> Offset(
+ const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta, size_t sample_boot) const {
std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> result =
filter(ta_base.boot, sample_boot)
- ->filter.Offset(pointer, ta_base.time, ta);
+ ->filter.Offset(
+ other == nullptr
+ ? nullptr
+ : &other->filter(sample_boot, ta_base.boot)->filter,
+ pointer, ta_base.time, ta);
return std::make_pair(
logger::BootDuration{sample_boot, result.second.first},
result.second.second);
@@ -502,15 +538,18 @@
std::pair<Pointer,
std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
std::tuple<logger::BootTimestamp, logger::BootDuration>>>
- FindTimestamps(Pointer pointer, logger::BootTimestamp ta,
- size_t sample_boot) const {
+ FindTimestamps(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta, size_t sample_boot) const {
const BootFilter *boot_filter = filter(ta.boot, sample_boot);
std::pair<
Pointer,
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- result = boot_filter->filter.FindTimestamps(pointer, ta.time);
+ result = boot_filter->filter.FindTimestamps(
+ other == nullptr ? nullptr
+ : &other->filter(sample_boot, ta.boot)->filter,
+ pointer, ta.time);
result.first.boot_filter_ = boot_filter;
return std::make_pair(
result.first,
@@ -529,7 +568,8 @@
std::pair<Pointer,
std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
std::tuple<logger::BootTimestamp, logger::BootDuration>>>
- FindTimestamps(Pointer pointer, logger::BootTimestamp ta_base, double ta,
+ FindTimestamps(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta,
size_t sample_boot) const;
static std::chrono::nanoseconds InterpolateOffset(
@@ -585,14 +625,15 @@
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- FindTimestamps(Pointer pointer, monotonic_clock::time_point ta) const;
+ FindTimestamps(const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const;
std::pair<
Pointer,
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- FindTimestamps(Pointer pointer, monotonic_clock::time_point ta_base,
- double ta) const;
+ FindTimestamps(const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const;
// Check whether the given timestamp falls within our current samples
bool IsOutsideSamples(monotonic_clock::time_point ta_base, double ta) const;
@@ -603,11 +644,14 @@
GetReferenceTimestamp(monotonic_clock::time_point ta_base, double ta) const;
std::pair<Pointer, std::chrono::nanoseconds> Offset(
- Pointer pointer, monotonic_clock::time_point ta) const;
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const;
std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> Offset(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const;
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const;
std::pair<Pointer, double> OffsetError(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const;
bool has_unobserved_line() const;
@@ -675,9 +719,10 @@
}
// Confirms that the solution meets the constraints. Returns true on
// success.
- bool ValidateSolution(Pointer pointer, aos::monotonic_clock::time_point ta,
+ bool ValidateSolution(const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta,
aos::monotonic_clock::time_point tb) const;
- bool ValidateSolution(Pointer pointer,
+ bool ValidateSolution(const SingleFilter *other, Pointer pointer,
aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base,
double tb) const;
@@ -819,6 +864,21 @@
return result;
}
+ static std::pair<
+ Pointer,
+ std::pair<
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
+ InterpolateWithOtherFilter(
+ Pointer pointer, monotonic_clock::time_point ta,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t0,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1);
+
+ const SingleFilter *maybe_single_filter(int boota, int bootb) const {
+ const BootFilter *boot_filter = maybe_filter(boota, bootb);
+ return boot_filter == nullptr ? nullptr : &boot_filter->filter;
+ }
+
private:
std::vector<std::unique_ptr<BootFilter>> filters_;
diff --git a/aos/network/timestamp_filter_test.cc b/aos/network/timestamp_filter_test.cc
index bbfd437..5932e3d 100644
--- a/aos/network/timestamp_filter_test.cc
+++ b/aos/network/timestamp_filter_test.cc
@@ -956,110 +956,226 @@
filter.Sample(t2, o2);
filter.Sample(t3, o3);
- result = filter.FindTimestamps(Pointer(), e - chrono::microseconds(10), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e - chrono::microseconds(10), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e - chrono::microseconds(10), 0));
- result =
- filter.FindTimestamps(Pointer(), e - chrono::microseconds(10), 0.9, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e - chrono::microseconds(10), 0.9, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e - chrono::microseconds(10), 0.9, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e - chrono::microseconds(10), 0.9, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(0), 0);
+ result =
+ filter.FindTimestamps(nullptr, Pointer(), e + chrono::microseconds(0), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(0), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(0), 0.8, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(0), 0.8, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(0), 0.8, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(100), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(100), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(100), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(100), 0.7, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(100), 0.7, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(100), 0.7, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(100), 0.7, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(1000), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1000), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(1000), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(1000), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1000), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(1000), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(1000), 0.0, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(1500), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1500), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(1500), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(1500), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1500), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(1500), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(1500), 0.0, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(2000), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2000), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(2000), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(2000), 0.1, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2000), 0.1, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(2000), 0.1, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(2000), 0.1, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(2500), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2500), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(2500), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(2500), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2500), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(2500), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(2500), 0.0, 0));
+}
+
+// Tests that when we have a paired filter with overlapping lines, we properly
+// stay above the other filter.
+//
+// This is the case when we have a large outage one direction but not the other,
+// and the lines cross (time drifts, so the straight line assumption from the
+// side with the outage is not relevant.).
+TEST_F(NoncausalTimestampFilterTest, FindTimestampsWithOther) {
+ const BootTimestamp e{0, monotonic_clock::epoch()};
+ // Note: t1, t2, t3 need to be picked such that the slop is small so filter
+ // doesn't modify the timestamps.
+ const BootTimestamp t1_a = e + chrono::nanoseconds(0);
+ const BootDuration o1_a{0, chrono::nanoseconds(100)};
+ const BootTimestamp t2_a = e + chrono::microseconds(1000);
+ const BootDuration o2_a{0, chrono::nanoseconds(100)};
+
+ const BootTimestamp t1_b = e + chrono::nanoseconds(100);
+ const BootDuration o1_b{0, -chrono::nanoseconds(105)};
+ const BootTimestamp t2_b = e + chrono::microseconds(200);
+ const BootDuration o2_b{0, -chrono::nanoseconds(101)};
+ const BootTimestamp t3_b = e + chrono::microseconds(300);
+ const BootDuration o3_b{0, -chrono::nanoseconds(101)};
+
+ TestingNoncausalTimestampFilter filter_a(node_a, node_b);
+ TestingNoncausalTimestampFilter filter_b(node_b, node_a);
+
+ std::pair<Pointer,
+ std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
+ std::tuple<logger::BootTimestamp, logger::BootDuration>>>
+ result;
+
+ filter_a.Sample(t1_a, o1_a);
+ filter_a.Sample(t2_a, o2_a);
+
+ filter_b.Sample(t1_b, o1_b);
+ filter_b.Sample(t2_b, o2_b);
+ filter_b.Sample(t3_b, o3_b);
+
+ // Confirm the problem statement is reasonable... We've had enough trouble
+ // here in the past.
+ EXPECT_TRUE(
+ filter_a.ValidateSolution(&filter_b, Pointer(), t1_a, t1_a + o1_a + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_a.ValidateSolution(&filter_b, Pointer(), t2_a, t2_a + o2_a + chrono::nanoseconds(1)));
+
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t1_b, t1_b + o1_b + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t2_b, t2_b + o2_b + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t3_b, t3_b + o3_b + chrono::nanoseconds(1)));
+
+ // Before the start
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e - chrono::microseconds(10), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(t1_a, o1_a)),
+ ::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e - chrono::microseconds(10), 0));
+
+ // Before the first opposite point.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(10), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(t1_a, o1_a)),
+ ::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(10), 0));
+
+ // Between the two opposite points.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(250), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(250), 0));
+
+ // After the last opposite point.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(450), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(t2_a, o2_a))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(450), 0));
+
+ // And after the end.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(1100), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(t2_a, o2_a))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(1100), 0));
}
// Tests that Offset returns results indicative of it calling InterpolateOffset
@@ -1087,57 +1203,61 @@
filter.Sample(t1, o1);
// 1 point is handled properly.
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0), o1);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0.0, 0), std::make_pair(o1, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0), o1);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0.0, 0),
+ std::make_pair(o1, 0.0));
// Check if we ask for something away from point that we get an offset
// based on the MaxVelocity allowed
const double offset_pre = -(t1.time - e.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), e, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_pre)));
- EXPECT_EQ(filter.Offset(Pointer(), e, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0.0, 0),
std::make_pair(o1, offset_pre));
double offset_post = -(t2.time - t1.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_post)));
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0.0, 0),
std::make_pair(o1, offset_post));
filter.Sample(t2, o2);
filter.Sample(t3, o3);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0), o1);
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0), o2);
- EXPECT_EQ(filter.Offset(Pointer(), t3, 0), o3);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0), o1);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0), o2);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t3, 0), o3);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0.0, 0), std::make_pair(o1, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0.0, 0),
+ std::make_pair(o1, 0.0));
EXPECT_EQ(
- filter.Offset(Pointer(),
+ filter.Offset(nullptr, Pointer(),
e + (t2.time_since_epoch() + t1.time_since_epoch()) / 2,
0.0, 0),
std::make_pair(o1, (o2d - o1d) / 2.));
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0.0, 0), std::make_pair(o2, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0.0, 0),
+ std::make_pair(o2, 0.0));
EXPECT_EQ(
- filter.Offset(Pointer(),
+ filter.Offset(nullptr, Pointer(),
e + (t2.time_since_epoch() + t3.time_since_epoch()) / 2,
0.0, 0),
std::make_pair(o2, (o2d + o3d) / 2. - o2d));
- EXPECT_EQ(filter.Offset(Pointer(), t3, 0.0, 0), std::make_pair(o3, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t3, 0.0, 0),
+ std::make_pair(o3, 0.0));
// Check that we still get same answer for times before our sample data...
- EXPECT_EQ(filter.Offset(Pointer(), e, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_pre)));
- EXPECT_EQ(filter.Offset(Pointer(), e, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0.0, 0),
std::make_pair(o1, offset_pre));
// ... and after
offset_post = -(t4.time - t3.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), t4, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t4, 0),
(o3 + chrono::nanoseconds(static_cast<int64_t>(offset_post))));
- EXPECT_EQ(filter.Offset(Pointer(), t4, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t4, 0.0, 0),
std::make_pair(o3, offset_post));
}