| /* | |
| * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved. | |
| * | |
| * Use of this source code is governed by a BSD-style license | |
| * that can be found in the LICENSE file in the root of the source | |
| * tree. An additional intellectual property rights grant can be found | |
| * in the file PATENTS. All contributing project authors may | |
| * be found in the AUTHORS file in the root of the source tree. | |
| */ | |
| #include "call/receive_time_calculator.h" | |
| #include <algorithm> | |
| #include <cmath> | |
| #include <cstdint> | |
| #include <cstdlib> | |
| #include <optional> | |
| #include <vector> | |
| #include "api/field_trials.h" | |
| #include "rtc_base/random.h" | |
| #include "rtc_base/time_utils.h" | |
| #include "test/create_test_field_trials.h" | |
| #include "test/gtest.h" | |
| namespace webrtc { | |
| namespace test { | |
| namespace { | |
| class EmulatedClock { | |
| public: | |
| explicit EmulatedClock(int seed, float drift = 0.0f) | |
| : random_(seed), clock_us_(random_.Rand<uint32_t>()), drift_(drift) {} | |
| virtual ~EmulatedClock() = default; | |
| int64_t GetClockUs() const { return clock_us_; } | |
| protected: | |
| int64_t UpdateClock(int64_t time_us) { | |
| if (!last_query_us_) | |
| last_query_us_ = time_us; | |
| int64_t skip_us = time_us - *last_query_us_; | |
| accumulated_drift_us_ += skip_us * drift_; | |
| int64_t drift_correction_us = static_cast<int64_t>(accumulated_drift_us_); | |
| accumulated_drift_us_ -= drift_correction_us; | |
| clock_us_ += skip_us + drift_correction_us; | |
| last_query_us_ = time_us; | |
| return skip_us; | |
| } | |
| Random random_; | |
| private: | |
| int64_t clock_us_; | |
| std::optional<int64_t> last_query_us_; | |
| float drift_; | |
| float accumulated_drift_us_ = 0; | |
| }; | |
| class EmulatedMonotoneousClock : public EmulatedClock { | |
| public: | |
| explicit EmulatedMonotoneousClock(int seed) : EmulatedClock(seed) {} | |
| ~EmulatedMonotoneousClock() override = default; | |
| int64_t Query(int64_t time_us) { | |
| int64_t skip_us = UpdateClock(time_us); | |
| // In a stall | |
| if (stall_recovery_time_us_ > 0) { | |
| if (GetClockUs() > stall_recovery_time_us_) { | |
| stall_recovery_time_us_ = 0; | |
| return GetClockUs(); | |
| } else { | |
| return stall_recovery_time_us_; | |
| } | |
| } | |
| // Check if we enter a stall | |
| for (int k = 0; k < skip_us; ++k) { | |
| if (random_.Rand<double>() < kChanceOfStallPerUs) { | |
| int64_t stall_duration_us = | |
| static_cast<int64_t>(random_.Rand<float>() * kMaxStallDurationUs); | |
| stall_recovery_time_us_ = GetClockUs() + stall_duration_us; | |
| return stall_recovery_time_us_; | |
| } | |
| } | |
| return GetClockUs(); | |
| } | |
| void ForceStallUs() { | |
| int64_t stall_duration_us = | |
| static_cast<int64_t>(random_.Rand<float>() * kMaxStallDurationUs); | |
| stall_recovery_time_us_ = GetClockUs() + stall_duration_us; | |
| } | |
| bool Stalled() const { return stall_recovery_time_us_ > 0; } | |
| int64_t GetRemainingStall(int64_t /* time_us */) const { | |
| return stall_recovery_time_us_ > 0 ? stall_recovery_time_us_ - GetClockUs() | |
| : 0; | |
| } | |
| const int64_t kMaxStallDurationUs = kNumMicrosecsPerSec; | |
| private: | |
| const float kChanceOfStallPerUs = 5e-6f; | |
| int64_t stall_recovery_time_us_ = 0; | |
| }; | |
| class EmulatedNonMonotoneousClock : public EmulatedClock { | |
| public: | |
| EmulatedNonMonotoneousClock(int seed, int64_t duration_us, float drift = 0) | |
| : EmulatedClock(seed, drift) { | |
| Pregenerate(duration_us); | |
| } | |
| ~EmulatedNonMonotoneousClock() override = default; | |
| void Pregenerate(int64_t duration_us) { | |
| int64_t time_since_reset_us = kMinTimeBetweenResetsUs; | |
| int64_t clock_offset_us = 0; | |
| for (int64_t time_us = 0; time_us < duration_us; time_us += kResolutionUs) { | |
| int64_t skip_us = UpdateClock(time_us); | |
| time_since_reset_us += skip_us; | |
| int64_t reset_us = 0; | |
| if (time_since_reset_us >= kMinTimeBetweenResetsUs) { | |
| for (int k = 0; k < skip_us; ++k) { | |
| if (random_.Rand<double>() < kChanceOfResetPerUs) { | |
| reset_us = static_cast<int64_t>(2 * random_.Rand<float>() * | |
| kMaxAbsResetUs) - | |
| kMaxAbsResetUs; | |
| clock_offset_us += reset_us; | |
| time_since_reset_us = 0; | |
| break; | |
| } | |
| } | |
| } | |
| pregenerated_clock_.emplace_back(GetClockUs() + clock_offset_us); | |
| resets_us_.emplace_back(reset_us); | |
| } | |
| } | |
| int64_t Query(int64_t time_us) { | |
| size_t ixStart = | |
| (last_reset_query_time_us_ + (kResolutionUs >> 1)) / kResolutionUs + 1; | |
| size_t ixEnd = (time_us + (kResolutionUs >> 1)) / kResolutionUs; | |
| if (ixEnd >= pregenerated_clock_.size()) | |
| return -1; | |
| last_reset_size_us_ = 0; | |
| for (size_t ix = ixStart; ix <= ixEnd; ++ix) { | |
| if (resets_us_[ix] != 0) { | |
| last_reset_size_us_ = resets_us_[ix]; | |
| } | |
| } | |
| last_reset_query_time_us_ = time_us; | |
| return pregenerated_clock_[ixEnd]; | |
| } | |
| bool WasReset() const { return last_reset_size_us_ != 0; } | |
| bool WasNegativeReset() const { return last_reset_size_us_ < 0; } | |
| int64_t GetLastResetUs() const { return last_reset_size_us_; } | |
| private: | |
| const float kChanceOfResetPerUs = 1e-6f; | |
| const int64_t kMaxAbsResetUs = kNumMicrosecsPerSec; | |
| const int64_t kMinTimeBetweenResetsUs = 3 * kNumMicrosecsPerSec; | |
| const int64_t kResolutionUs = kNumMicrosecsPerMillisec; | |
| int64_t last_reset_query_time_us_ = 0; | |
| int64_t last_reset_size_us_ = 0; | |
| std::vector<int64_t> pregenerated_clock_; | |
| std::vector<int64_t> resets_us_; | |
| }; | |
| TEST(ClockRepair, NoClockDrift) { | |
| FieldTrials field_trials = CreateTestFieldTrials(); | |
| const int kSeeds = 10; | |
| const int kFirstSeed = 1; | |
| const int64_t kRuntimeUs = 10 * kNumMicrosecsPerSec; | |
| const float kDrift = 0.0f; | |
| const int64_t kMaxPacketInterarrivalUs = 50 * kNumMicrosecsPerMillisec; | |
| for (int seed = kFirstSeed; seed < kSeeds + kFirstSeed; ++seed) { | |
| EmulatedMonotoneousClock monotone_clock(seed); | |
| EmulatedNonMonotoneousClock non_monotone_clock( | |
| seed + 1, kRuntimeUs + kNumMicrosecsPerSec, kDrift); | |
| ReceiveTimeCalculator reception_time_tracker(field_trials); | |
| int64_t corrected_clock_0 = 0; | |
| int64_t reset_during_stall_tol_us = 0; | |
| bool initial_clock_stall = true; | |
| int64_t accumulated_upper_bound_tolerance_us = 0; | |
| int64_t accumulated_lower_bound_tolerance_us = 0; | |
| Random random(1); | |
| monotone_clock.ForceStallUs(); | |
| int64_t last_time_us = 0; | |
| bool add_tolerance_on_next_packet = false; | |
| int64_t monotone_noise_us = 1000; | |
| for (int64_t time_us = 0; time_us < kRuntimeUs; | |
| time_us += static_cast<int64_t>(random.Rand<float>() * | |
| kMaxPacketInterarrivalUs)) { | |
| int64_t socket_time_us = non_monotone_clock.Query(time_us); | |
| int64_t monotone_us = monotone_clock.Query(time_us) + | |
| 2 * random.Rand<float>() * monotone_noise_us - | |
| monotone_noise_us; | |
| int64_t system_time_us = non_monotone_clock.Query( | |
| time_us + monotone_clock.GetRemainingStall(time_us)); | |
| int64_t corrected_clock_us = reception_time_tracker.ReconcileReceiveTimes( | |
| socket_time_us, system_time_us, monotone_us); | |
| if (time_us == 0) | |
| corrected_clock_0 = corrected_clock_us; | |
| if (add_tolerance_on_next_packet) | |
| accumulated_lower_bound_tolerance_us -= (time_us - last_time_us); | |
| // Perfect repair cannot be achiveved if non-monotone clock resets during | |
| // a monotone clock stall. | |
| add_tolerance_on_next_packet = false; | |
| if (monotone_clock.Stalled() && non_monotone_clock.WasReset()) { | |
| reset_during_stall_tol_us = | |
| std::max(reset_during_stall_tol_us, time_us - last_time_us); | |
| if (non_monotone_clock.WasNegativeReset()) { | |
| add_tolerance_on_next_packet = true; | |
| } | |
| if (initial_clock_stall && !non_monotone_clock.WasNegativeReset()) { | |
| // Positive resets during an initial clock stall cannot be repaired | |
| // and error will propagate through rest of trace. | |
| accumulated_upper_bound_tolerance_us += | |
| std::abs(non_monotone_clock.GetLastResetUs()); | |
| } | |
| } else { | |
| reset_during_stall_tol_us = 0; | |
| initial_clock_stall = false; | |
| } | |
| int64_t err = corrected_clock_us - corrected_clock_0 - time_us; | |
| // Resets during stalls may lead to small errors temporarily. | |
| int64_t lower_tol_us = accumulated_lower_bound_tolerance_us - | |
| reset_during_stall_tol_us - monotone_noise_us - | |
| 2 * kNumMicrosecsPerMillisec; | |
| EXPECT_GE(err, lower_tol_us); | |
| int64_t upper_tol_us = accumulated_upper_bound_tolerance_us + | |
| monotone_noise_us + 2 * kNumMicrosecsPerMillisec; | |
| EXPECT_LE(err, upper_tol_us); | |
| last_time_us = time_us; | |
| } | |
| } | |
| } | |
| } // namespace | |
| } // namespace test | |
| } // namespace webrtc |