blob: 38ef54ece794112cc9dad815c24b49513c70d3aa [file] [log] [blame]
/*
* 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 <iostream>
#include <tuple>
#include <vector>
#include "absl/memory/memory.h"
#include "absl/types/optional.h"
#include "rtc_base/random.h"
#include "rtc_base/timeutils.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_;
absl::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() = 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 = rtc::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() = 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 = rtc::kNumMicrosecsPerSec;
const int64_t kMinTimeBetweenResetsUs = 3 * rtc::kNumMicrosecsPerSec;
const int64_t kResolutionUs = rtc::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) {
const int kSeeds = 10;
const int kFirstSeed = 1;
const int64_t kRuntimeUs = 10 * rtc::kNumMicrosecsPerSec;
const float kDrift = 0.0f;
const int64_t kMaxPacketInterarrivalUs = 50 * rtc::kNumMicrosecsPerMillisec;
for (int seed = kFirstSeed; seed < kSeeds + kFirstSeed; ++seed) {
EmulatedMonotoneousClock monotone_clock(seed);
EmulatedNonMonotoneousClock non_monotone_clock(
seed + 1, kRuntimeUs + rtc::kNumMicrosecsPerSec, kDrift);
ReceiveTimeCalculator reception_time_tracker;
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 * rtc::kNumMicrosecsPerMillisec;
EXPECT_GE(err, lower_tol_us);
int64_t upper_tol_us = accumulated_upper_bound_tolerance_us +
monotone_noise_us +
2 * rtc::kNumMicrosecsPerMillisec;
EXPECT_LE(err, upper_tol_us);
last_time_us = time_us;
}
}
}
} // namespace
} // namespace test
} // namespace webrtc