kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ale...@apache.org
Subject [kudu] 02/03: [clock] add unit tests for FindIntersection() function
Date Tue, 01 Oct 2019 04:12:16 GMT
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 <alexey@apache.org>
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 <aserbin@cloudera.com>
    Reviewed-by: Adar Dembo <adar@cloudera.com>
---
 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


Mime
View raw message