This is an automated email from the ASF dual-hosted git repository. alexey pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/kudu.git
commit 12922d8d89416f362c55945d8e50797776731ee2 Author: Alexey Serbin <[email protected]> AuthorDate: Sun Sep 29 17:42:43 2019 -0700 [clock] add unit tests for FindIntersection() function This patch factors out the FindIntersection() function from the BuiltInNtp class and adds unit tests to cover its functionality. The FindIntersection() algorithm implements a version of the Marzullo's algorithm: https://www.eecis.udel.edu/~mills/ntp/html/select.html Change-Id: I7ba41889360f55320631d24ec8d0a65ba657ef40 Reviewed-on: http://gerrit.cloudera.org:8080/14327 Tested-by: Alexey Serbin <[email protected]> Reviewed-by: Adar Dembo <[email protected]> --- src/kudu/clock/CMakeLists.txt | 1 + src/kudu/clock/builtin_ntp-internal.cc | 94 +++++++++ src/kudu/clock/builtin_ntp-internal.h | 59 ++++++ src/kudu/clock/builtin_ntp.cc | 73 +------ src/kudu/clock/builtin_ntp.h | 23 +-- src/kudu/clock/ntp-test.cc | 345 +++++++++++++++++++++++++++++++++ 6 files changed, 511 insertions(+), 84 deletions(-) diff --git a/src/kudu/clock/CMakeLists.txt b/src/kudu/clock/CMakeLists.txt index dc08c96..52204a4 100644 --- a/src/kudu/clock/CMakeLists.txt +++ b/src/kudu/clock/CMakeLists.txt @@ -17,6 +17,7 @@ set(CLOCK_SRCS builtin_ntp.cc + builtin_ntp-internal.cc hybrid_clock.cc logical_clock.cc mock_ntp.cc diff --git a/src/kudu/clock/builtin_ntp-internal.cc b/src/kudu/clock/builtin_ntp-internal.cc new file mode 100644 index 0000000..f555c04 --- /dev/null +++ b/src/kudu/clock/builtin_ntp-internal.cc @@ -0,0 +1,94 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you 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 "kudu/clock/builtin_ntp-internal.h" + +#include <algorithm> +#include <cstdint> +#include <memory> +#include <string> +#include <utility> +#include <vector> + +#include <glog/logging.h> + +#include "kudu/gutil/strings/substitute.h" +#include "kudu/util/net/sockaddr.h" + +using std::vector; +using std::pair; +using std::vector; +using strings::Substitute; + +namespace kudu { +namespace clock { +namespace internal { + +Interval FindIntersection( + const vector<RecordedResponse>& responses, + int64_t reftime, + int clock_skew_ppm) { + vector<pair<int64_t, int>> interval_endpoints; + for (const auto& r : responses) { + int64_t wall = reftime + r.offset_us; + int64_t error = r.error_us + (reftime - r.monotime) * clock_skew_ppm / 1e6; + DCHECK_GE(reftime, r.monotime); + DCHECK_GE(error, 0); + interval_endpoints.emplace_back(wall - error, -1); + interval_endpoints.emplace_back(wall + error, 1); + VLOG(2) << Substitute("correctness interval ($0, $1) from $2", + wall - error, wall + error, r.addr.ToString()); + } + + if (responses.size() == 1) { + // Short-circuiting the search since the algorithm below doesn't handle + // single interval. + CHECK_EQ(2, interval_endpoints.size()); + return std::make_pair(interval_endpoints[0].first, + interval_endpoints[1].first); + } + + std::sort(interval_endpoints.begin(), interval_endpoints.end()); + + int best = 1; // for an intersection, at least 2 intervals are needed + int count_overlap = 0; + Interval best_interval = kIntervalNone; + for (int i = 1; i < interval_endpoints.size(); i++) { + const auto& cur = interval_endpoints[i - 1]; + const auto& next = interval_endpoints[i]; + count_overlap -= cur.second; + // TODO(aserbin): in the layouts like the following, which interval is + // better to choose? Right now, the first is chosen, + // but maybe it's better to randomize the choice to avoid + // bias or simply choose some wider interval which covers + // both intersections intervals? + // + // source A : <----> + // source B : <---> + // source C : <--------------> + // intersection : <====> <===> + if (count_overlap > best) { + best = count_overlap; + best_interval = std::make_pair(cur.first, next.first); + } + } + return best_interval; +} + +} // namespace internal +} // namespace clock +} // namespace kudu diff --git a/src/kudu/clock/builtin_ntp-internal.h b/src/kudu/clock/builtin_ntp-internal.h new file mode 100644 index 0000000..75e53f2 --- /dev/null +++ b/src/kudu/clock/builtin_ntp-internal.h @@ -0,0 +1,59 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you 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. +#pragma once + +#include <cstdint> +#include <utility> +#include <vector> + +#include "kudu/util/net/sockaddr.h" + +namespace kudu { +namespace clock { +namespace internal { + +// Representation of time interval: the first pair component is the +// left/earlier point, the second is right/later point. +typedef std::pair<int64_t, int64_t> Interval; + +// A special interval meaning 'an empty interval'. +static const Interval kIntervalNone = { -1, -1 }; + +// A time measurement recorded after receiving a response from an NTP server. +struct RecordedResponse { + // The time at which the response was recorded. + int64_t monotime; + // The calculated estimated offset between our monotime and the server's wall-clock time. + int64_t offset_us; + // The estimated maximum error between our time and the server's time. + int64_t error_us; + // The server which provided the response. + Sockaddr addr; + // The server's transmit timestamp. + uint64_t tx_timestamp; +}; + +// Build an intersection interval given the set of correctness intervals +// and reference local time. +Interval FindIntersection( + const std::vector<RecordedResponse>& responses, + int64_t reftime, + int clock_skew_ppm); + +} // namespace internal +} // namespace clock +} // namespace kudu diff --git a/src/kudu/clock/builtin_ntp.cc b/src/kudu/clock/builtin_ntp.cc index f206fef..f6d19bd 100644 --- a/src/kudu/clock/builtin_ntp.cc +++ b/src/kudu/clock/builtin_ntp.cc @@ -22,7 +22,6 @@ #include <sys/socket.h> #include <sys/types.h> -#include <algorithm> #include <cerrno> #include <cstdint> #include <cstring> @@ -36,6 +35,7 @@ #include <gflags/gflags.h> #include <glog/logging.h> +#include "kudu/clock/builtin_ntp-internal.h" #include "kudu/gutil/port.h" #include "kudu/gutil/strings/join.h" #include "kudu/gutil/strings/strcat.h" @@ -102,9 +102,11 @@ DEFINE_string(builtin_ntp_client_bind_address, "0.0.0.0", "using ephemeral ports (i.e. port 0)'."); TAG_FLAG(builtin_ntp_client_bind_address, experimental); +using kudu::clock::internal::Interval; +using kudu::clock::internal::kIntervalNone; +using kudu::clock::internal::RecordedResponse; using std::deque; using std::lock_guard; -using std::pair; using std::string; using std::unique_ptr; using std::vector; @@ -316,20 +318,6 @@ struct BuiltInNtp::PendingRequest { static_assert(sizeof(NtpPacket) == 48, "unexpected size of NtpPacket"); }; -// A time measurement recorded after receiving a response from an NTP server. -struct BuiltInNtp::RecordedResponse { - // The server which provided the response. - Sockaddr addr; - // The server's transmit timestamp. - uint64_t tx_timestamp; - // The time at which the response was recorded. - int64_t monotime; - // The calculated estimated offset between our monotime and the server's wall-clock time. - int64_t offset_us; - // The estimated maximum error between our time and the server's time. - int64_t error_us; -}; - class BuiltInNtp::ServerState { public: explicit ServerState(HostPort host) : @@ -486,8 +474,6 @@ class BuiltInNtp::ServerState { size_t o_pkt_total_num_; // number of NTP requests sent }; -const BuiltInNtp::Interval BuiltInNtp::kIntervalNone = { -1, -1 }; - BuiltInNtp::BuiltInNtp() : rng_(GetRandomSeed32()) { } @@ -562,55 +548,6 @@ void BuiltInNtp::DumpDiagnostics(vector<string>* log) const { LOG_STRING(INFO, log) << diag; } -BuiltInNtp::Interval BuiltInNtp::FindIntersection( - const vector<RecordedResponse>& responses, int64_t reftime) { - vector<pair<int64_t, int>> interval_endpoints; - for (const auto& r : responses) { - int64_t wall = reftime + r.offset_us; - int64_t error = r.error_us + (reftime - r.monotime) * kSkewPpm / 1e6; - DCHECK_GE(reftime, r.monotime); - DCHECK_GE(error, 0); - interval_endpoints.emplace_back(wall - error, -1); - interval_endpoints.emplace_back(wall + error, 1); - VLOG(2) << Substitute("correctness interval ($0, $1) from $2", - wall - error, wall + error, r.addr.ToString()); - } - - if (responses.size() == 1) { - // Short-circuiting the search since the algorithm below doesn't handle - // single interval. - CHECK_EQ(2, interval_endpoints.size()); - return std::make_pair(interval_endpoints[0].first, - interval_endpoints[1].first); - } - - std::sort(interval_endpoints.begin(), interval_endpoints.end()); - - int best = 1; // for an intersection, at least 2 intervals are needed - int count_overlap = 0; - Interval best_interval = kIntervalNone; - for (int i = 1; i < interval_endpoints.size(); i++) { - const auto& cur = interval_endpoints[i - 1]; - const auto& next = interval_endpoints[i]; - count_overlap -= cur.second; - // TODO(aserbin): in the layouts like the following, which interval is - // better to choose? Right now, the first is chosen, - // but maybe it's better to randomize the choice to avoid - // bias or simply choose some wider interval which covers - // both intersections intervals? - // - // source A : <----> - // source B : <---> - // source C : <--------------> - // intersection : <====> <===> - if (count_overlap > best) { - best = count_overlap; - best_interval = std::make_pair(cur.first, next.first); - } - } - return best_interval; -} - Status BuiltInNtp::InitImpl() { // TODO(KUDU-2937) implement 'iburst' mode and use it for initial time sync state_lock_.AssertAcquired(); @@ -1031,7 +968,7 @@ Status BuiltInNtp::CombineClocks() { RETURN_NOT_OK(FilterResponses(&responses)); const auto now = GetMonoTimeMicrosRaw(); - const Interval best_interval = FindIntersection(responses, now); + const Interval best_interval = FindIntersection(responses, now, kSkewPpm); VLOG(2) << Substitute("intersection interval: ($0, $1)", best_interval.first, best_interval.second); if (best_interval == kIntervalNone) { diff --git a/src/kudu/clock/builtin_ntp.h b/src/kudu/clock/builtin_ntp.h index 8e2cc97..68dcc91 100644 --- a/src/kudu/clock/builtin_ntp.h +++ b/src/kudu/clock/builtin_ntp.h @@ -20,7 +20,6 @@ #include <list> #include <memory> #include <string> -#include <utility> #include <vector> #include "kudu/clock/time_service.h" @@ -40,6 +39,10 @@ class Thread; namespace clock { +namespace internal { +struct RecordedResponse; +} // namespace internal + // This time service is based on a simplified NTP client implementation. // It's not RFC-compliant yet (RFC 5905). The most important missing pieces are: // * support of iburst/burst operation modes (see KUDU-2937) @@ -84,7 +87,6 @@ class BuiltInNtp : public TimeService { class ServerState; struct NtpPacket; struct PendingRequest; - struct RecordedResponse; // Information on the computed walltime. struct WalltimeSnapshot { @@ -100,21 +102,9 @@ class BuiltInNtp : public TimeService { bool is_synchronized; }; - // Representation of time interval: the first pair component is the - // left/earlier point, the second is right/later point. - typedef std::pair<int64_t, int64_t> Interval; - - // A special interval meaning 'an empty interval'. - static const Interval kIntervalNone; - // Upper estimate for a clock skew. static constexpr int kSkewPpm = 500; - // Build an intersection interval given the set of correctness intervals - // and reference local time. - static std::pair<int64_t, int64_t> FindIntersection( - const std::vector<RecordedResponse>& responses, int64_t reftime); - // Implementation of Init(). Status InitImpl(); @@ -154,11 +144,12 @@ class BuiltInNtp : public TimeService { const NtpPacket& response); // Record and process response received from NTP server. - void RecordResponse(ServerState* from_server, const RecordedResponse& rr); + void RecordResponse(ServerState* from_server, + const internal::RecordedResponse& rr); // Among all available responses, select the best ones to use in the clock // selection algorithm. - Status FilterResponses(std::vector<RecordedResponse>* filtered); + Status FilterResponses(std::vector<internal::RecordedResponse>* filtered); // Create NTP packet to send to a server. NtpPacket CreateClientPacket(); diff --git a/src/kudu/clock/ntp-test.cc b/src/kudu/clock/ntp-test.cc index 3476fad..8cf7ee8 100644 --- a/src/kudu/clock/ntp-test.cc +++ b/src/kudu/clock/ntp-test.cc @@ -22,12 +22,14 @@ #include <iterator> #include <memory> #include <string> +#include <utility> #include <vector> #include <gflags/gflags_declare.h> #include <glog/logging.h> #include <gtest/gtest.h> +#include "kudu/clock/builtin_ntp-internal.h" #include "kudu/clock/builtin_ntp.h" #include "kudu/clock/test/mini_chronyd.h" #include "kudu/clock/test/mini_chronyd_test_util.h" @@ -42,6 +44,10 @@ DECLARE_int32(ntp_initial_sync_wait_secs); DECLARE_string(builtin_ntp_servers); DECLARE_uint32(builtin_ntp_poll_interval_ms); +using kudu::clock::internal::FindIntersection; +using kudu::clock::internal::Interval; +using kudu::clock::internal::RecordedResponse; +using kudu::clock::internal::kIntervalNone; using std::back_inserter; using std::copy; using std::string; @@ -51,6 +57,345 @@ using std::vector; namespace kudu { namespace clock { +// Few scenarios for the intersection interval in case of a single NTP response. +// Being a trivial case with regard to the intersection logic itself, it's +// a good case to verify that the uncertainty of the intersection interval +// widens in accordance with the skew of the clock when current time drifts +// further away from the time when a sample of the reference clock was captured. +TEST(TimeIntervalsTest, SingleResponse) { + // Zero clock skew: this is something theoretical, but anyways. + // In case of zero clock skew, regardless of the difference between the + // capture time and current time, the result error is not widening, + // and the result interval is drifting along with current time. + { + // Zero error. + { + const vector<RecordedResponse> responses = { + { 0, 1, 0, }, + }; + + const auto res0 = FindIntersection(responses, 0, 0); + ASSERT_EQ(1, res0.first); + ASSERT_EQ(1, res0.second); + + const auto res1 = FindIntersection(responses, 100, 0); + ASSERT_EQ(101, res1.first); + ASSERT_EQ(101, res1.second); + } + + // Non-zero error. + { + const vector<RecordedResponse> responses = { + { 0, 10, 1, }, + }; + + const auto res0 = FindIntersection(responses, 0, 0); + ASSERT_EQ(9, res0.first); + ASSERT_EQ(11, res0.second); + + const auto res1 = FindIntersection(responses, 100, 0); + ASSERT_EQ(109, res1.first); + ASSERT_EQ(111, res1.second); + } + } + + // Non-zero clock skew. + // In case of non-zero clock skew, the intersection interval is widening when + // current time drifts apart from the capture time. The error of a captured + // sample adds constant delta to the error of result intersection interval. + { + // Zero error. + { + { + const vector<RecordedResponse> responses = { + { 0, 10, 0, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + ASSERT_EQ(10, res0.first); + ASSERT_EQ(10, res0.second); + + const auto res1 = FindIntersection(responses, 100, 1000000); + ASSERT_EQ(10, res1.first); + ASSERT_EQ(210, res1.second); + + const auto res2 = FindIntersection(responses, 100, 2000000); + ASSERT_EQ(-90, res2.first); + ASSERT_EQ(310, res2.second); + + const auto res3 = FindIntersection(responses, 200, 1000000); + ASSERT_EQ(10, res3.first); + ASSERT_EQ(410, res3.second); + } + } + + // Non-zero error. + { + { + const vector<RecordedResponse> responses = { + { 0, 10, 1, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + ASSERT_EQ(9, res0.first); + ASSERT_EQ(11, res0.second); + + const auto res1 = FindIntersection(responses, 100, 1000000); + ASSERT_EQ(9, res1.first); + ASSERT_EQ(211, res1.second); + + const auto res2 = FindIntersection(responses, 50, 2000000); + ASSERT_EQ(-41, res2.first); + ASSERT_EQ(161, res2.second); + } + } + } +} + +// A case where two samples of the reference clock were acquired. +TEST(TimeIntervalsTest, TwoResponses) { + // The same interval: a single point at the time of sample capture. + { + const vector<RecordedResponse> responses = { + { 0, 3, 0, }, + { 0, 3, 0, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + ASSERT_EQ(3, res0.first); + ASSERT_EQ(3, res0.second); + + const auto res1 = FindIntersection(responses, 1, 1000000); + // [3, 5] & [3, 5] + ASSERT_EQ(3, res1.first); + ASSERT_EQ(5, res1.second); + } + + // Single intersection point: the edge. + { + const vector<RecordedResponse> responses = { + { 0, 2, 1, }, + { 0, 5, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [1, 3] & [3, 7] + ASSERT_EQ(3, res0.first); + ASSERT_EQ(3, res0.second); + } + + // Embedded intervals with the same reported time but different errors. + { + const vector<RecordedResponse> responses = { + { 0, 10, 1, }, + { 0, 10, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [9, 11] & [8, 12] + ASSERT_EQ(9, res0.first); + ASSERT_EQ(11, res0.second); + + const auto res1 = FindIntersection(responses, 5, 1000000); + // [9, 21] & [8, 22] + ASSERT_EQ(9, res1.first); + ASSERT_EQ(21, res1.second); + } + + // Embedded intervals with the same reported time but different errors. + // The second interval represents a corner case of zero-error sample. + { + const vector<RecordedResponse> responses = { + { 0, 10, 1, }, + { 0, 10, 0, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [9, 11] & [10, 10] + ASSERT_EQ(10, res0.first); + ASSERT_EQ(10, res0.second); + + const auto res1 = FindIntersection(responses, 5, 1000000); + // [9, 21] & [10, 20] + ASSERT_EQ(10, res1.first); + ASSERT_EQ(20, res1.second); + } + + // Embedded intervals with different reported time. + { + const vector<RecordedResponse> responses = { + { 0, 1, 1, }, + { 0, 2, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [0, 2] & [0, 4] + ASSERT_EQ(0, res0.first); + ASSERT_EQ(2, res0.second); + + const auto res1 = FindIntersection(responses, 10, 1000000); + // [0, 22] & [0, 24] + ASSERT_EQ(0, res1.first); + ASSERT_EQ(22, res1.second); + } + + // Non-intersecting (as of time of capture) intervals. + { + const vector<RecordedResponse> responses = { + { 0, 1, 1, }, + { 0, 5, 1, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [0, 2] & [4, 6] + ASSERT_EQ(kIntervalNone, res0); + + const auto res1 = FindIntersection(responses, 5, 1000000); + // [0, 12] & [4, 16] + ASSERT_EQ(4, res1.first); + ASSERT_EQ(12, res1.second); + } +} + +// A case where three samples of the reference clock were acquired. +TEST(TimeIntervalsTest, ThreeResponses) { + // The same interval: a single point at the time of sample capture. + { + const vector<RecordedResponse> responses = { + { 0, 3, 0, }, + { 0, 3, 0, }, + { 0, 3, 0, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + ASSERT_EQ(3, res0.first); + ASSERT_EQ(3, res0.second); + + const auto res1 = FindIntersection(responses, 1, 1000000); + // [3, 5] & [3, 5] & [3, 5] + ASSERT_EQ(3, res1.first); + ASSERT_EQ(5, res1.second); + } + + // Non-intersecting (as of time of capture) intervals. + { + const vector<RecordedResponse> responses = { + { 0, 1, 1, }, + { 0, 4, 1, }, + { 0, 7, 1, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [0, 2] & [3, 5] & [6, 8] + ASSERT_EQ(kIntervalNone, res0); + + const auto res1 = FindIntersection(responses, 10, 1000000); + // [0, 22] & [3, 25] & [6, 28] + ASSERT_EQ(6, res1.first); + ASSERT_EQ(22, res1.second); + } + + // Embedded intervals with the same reported time but different errors. + // The second interval represents a corner case of zero-error sample. + { + const vector<RecordedResponse> responses = { + { 0, 10, 5, }, + { 0, 10, 1, }, + { 0, 10, 10, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [5, 15] & [9, 11] & [0, 20] + ASSERT_EQ(9, res0.first); + ASSERT_EQ(11, res0.second); + + const auto res1 = FindIntersection(responses, 10, 1000000); + // [5, 35] & [9, 31] & [0, 40] + ASSERT_EQ(9, res1.first); + ASSERT_EQ(31, res1.second); + } + + // Three 'chained' intervals that have a single intersection point at the time + // of samples capture. + { + const vector<RecordedResponse> responses = { + { 0, 4, 2, }, + { 0, 6, 2, }, + { 0, 8, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [2, 6] & [4, 8] & [6, 10] + ASSERT_EQ(6, res0.first); + ASSERT_EQ(6, res0.second); + + const auto res1 = FindIntersection(responses, 1, 1000000); + // [2, 8] & [4, 10] & [6, 12] + ASSERT_EQ(6, res1.first); + ASSERT_EQ(8, res1.second); + } + + // Three 'chained' intervals without a single intersection point. + // As of now, the first intersection interval (the earlier) is chosen. + { + const vector<RecordedResponse> responses = { + { 0, 3, 2, }, + { 0, 6, 2, }, + { 0, 9, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [1, 5] & [4, 8] & [7, 11] + ASSERT_EQ(4, res0.first); + ASSERT_EQ(5, res0.second); + } + + // Two intersections: first two points, then two intervals. As of now, + // the first (the earlier) is chosen. + { + const vector<RecordedResponse> responses = { + { 0, 3, 2, }, + { 0, 6, 2, }, + { 0, 9, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [1, 5] & [4, 8] & [7, 11] + ASSERT_EQ(4, res0.first); + ASSERT_EQ(5, res0.second); + } + + // One interval contains two other (no boundary intesections), so the total + // is two intervals. The first (the earliest) one is chosen as the result. + { + const vector<RecordedResponse> responses = { + { 0, 6, 6, }, + { 0, 2, 1, }, + { 0, 5, 1, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [0, 12] & [1, 3] & [4, 6] + ASSERT_EQ(1, res0.first); + ASSERT_EQ(3, res0.second); + } + + // One interval contains two other, but with boundary intesection, there is + // one common point among all three intervals. + { + const vector<RecordedResponse> responses = { + { 0, 4, 4, }, + { 0, 2, 2, }, + { 0, 6, 2, }, + }; + + const auto res0 = FindIntersection(responses, 0, 1000000); + // [0, 8] & [0, 4] & [4, 8] + ASSERT_EQ(4, res0.first); + ASSERT_EQ(4, res0.second); + } +} + #define WALLTIME_DIAG_FMT "%" PRId64 " +/- %8" PRId64 " us" // Test to verify functionality of the built-in NTP client by communicating
