blob: ab66b2b562f5218a8e98b43e1333ca118dac779b [file] [log] [blame]
/*
* Copyright (c) 2016 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 <algorithm>
#include <limits>
#include "modules/video_coding/nack_module.h"
#include "modules/utility/include/process_thread.h"
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"
namespace webrtc {
namespace {
const int kMaxPacketAge = 10000;
const int kMaxNackPackets = 1000;
const int kDefaultRttMs = 100;
const int kMaxNackRetries = 10;
const int kProcessFrequency = 50;
const int kProcessIntervalMs = 1000 / kProcessFrequency;
const int kMaxReorderedPackets = 128;
const int kNumReorderingBuckets = 10;
} // namespace
NackModule::NackInfo::NackInfo()
: seq_num(0), send_at_seq_num(0), sent_at_time(-1), retries(0) {}
NackModule::NackInfo::NackInfo(uint16_t seq_num, uint16_t send_at_seq_num)
: seq_num(seq_num),
send_at_seq_num(send_at_seq_num),
sent_at_time(-1),
retries(0) {}
NackModule::NackModule(Clock* clock,
NackSender* nack_sender,
KeyFrameRequestSender* keyframe_request_sender)
: clock_(clock),
nack_sender_(nack_sender),
keyframe_request_sender_(keyframe_request_sender),
reordering_histogram_(kNumReorderingBuckets, kMaxReorderedPackets),
initialized_(false),
rtt_ms_(kDefaultRttMs),
newest_seq_num_(0),
next_process_time_ms_(-1) {
RTC_DCHECK(clock_);
RTC_DCHECK(nack_sender_);
RTC_DCHECK(keyframe_request_sender_);
}
int NackModule::OnReceivedPacket(uint16_t seq_num, bool is_keyframe) {
rtc::CritScope lock(&crit_);
// TODO(philipel): When the packet includes information whether it is
// retransmitted or not, use that value instead. For
// now set it to true, which will cause the reordering
// statistics to never be updated.
bool is_retransmitted = true;
if (!initialized_) {
newest_seq_num_ = seq_num;
if (is_keyframe)
keyframe_list_.insert(seq_num);
initialized_ = true;
return 0;
}
// Since the |newest_seq_num_| is a packet we have actually received we know
// that packet has never been Nacked.
if (seq_num == newest_seq_num_)
return 0;
if (AheadOf(newest_seq_num_, seq_num)) {
// An out of order packet has been received.
auto nack_list_it = nack_list_.find(seq_num);
int nacks_sent_for_packet = 0;
if (nack_list_it != nack_list_.end()) {
nacks_sent_for_packet = nack_list_it->second.retries;
nack_list_.erase(nack_list_it);
}
if (!is_retransmitted)
UpdateReorderingStatistics(seq_num);
return nacks_sent_for_packet;
}
AddPacketsToNack(newest_seq_num_ + 1, seq_num);
newest_seq_num_ = seq_num;
// Keep track of new keyframes.
if (is_keyframe)
keyframe_list_.insert(seq_num);
// And remove old ones so we don't accumulate keyframes.
auto it = keyframe_list_.lower_bound(seq_num - kMaxPacketAge);
if (it != keyframe_list_.begin())
keyframe_list_.erase(keyframe_list_.begin(), it);
// Are there any nacks that are waiting for this seq_num.
std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
if (!nack_batch.empty())
nack_sender_->SendNack(nack_batch);
return 0;
}
int NackModule::OnReceivedPacket(const VCMPacket& packet) {
return OnReceivedPacket(
packet.seqNum,
packet.is_first_packet_in_frame && packet.frameType == kVideoFrameKey);
}
void NackModule::ClearUpTo(uint16_t seq_num) {
rtc::CritScope lock(&crit_);
nack_list_.erase(nack_list_.begin(), nack_list_.lower_bound(seq_num));
keyframe_list_.erase(keyframe_list_.begin(),
keyframe_list_.lower_bound(seq_num));
}
void NackModule::UpdateRtt(int64_t rtt_ms) {
rtc::CritScope lock(&crit_);
rtt_ms_ = rtt_ms;
}
void NackModule::Clear() {
rtc::CritScope lock(&crit_);
nack_list_.clear();
keyframe_list_.clear();
}
int64_t NackModule::TimeUntilNextProcess() {
return std::max<int64_t>(next_process_time_ms_ - clock_->TimeInMilliseconds(),
0);
}
void NackModule::Process() {
if (nack_sender_) {
std::vector<uint16_t> nack_batch;
{
rtc::CritScope lock(&crit_);
nack_batch = GetNackBatch(kTimeOnly);
}
if (!nack_batch.empty())
nack_sender_->SendNack(nack_batch);
}
// Update the next_process_time_ms_ in intervals to achieve
// the targeted frequency over time. Also add multiple intervals
// in case of a skip in time as to not make uneccessary
// calls to Process in order to catch up.
int64_t now_ms = clock_->TimeInMilliseconds();
if (next_process_time_ms_ == -1) {
next_process_time_ms_ = now_ms + kProcessIntervalMs;
} else {
next_process_time_ms_ = next_process_time_ms_ + kProcessIntervalMs +
(now_ms - next_process_time_ms_) /
kProcessIntervalMs * kProcessIntervalMs;
}
}
bool NackModule::RemovePacketsUntilKeyFrame() {
while (!keyframe_list_.empty()) {
auto it = nack_list_.lower_bound(*keyframe_list_.begin());
if (it != nack_list_.begin()) {
// We have found a keyframe that actually is newer than at least one
// packet in the nack list.
RTC_DCHECK(it != nack_list_.end());
nack_list_.erase(nack_list_.begin(), it);
return true;
}
// If this keyframe is so old it does not remove any packets from the list,
// remove it from the list of keyframes and try the next keyframe.
keyframe_list_.erase(keyframe_list_.begin());
}
return false;
}
void NackModule::AddPacketsToNack(uint16_t seq_num_start,
uint16_t seq_num_end) {
// Remove old packets.
auto it = nack_list_.lower_bound(seq_num_end - kMaxPacketAge);
nack_list_.erase(nack_list_.begin(), it);
// If the nack list is too large, remove packets from the nack list until
// the latest first packet of a keyframe. If the list is still too large,
// clear it and request a keyframe.
uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
while (RemovePacketsUntilKeyFrame() &&
nack_list_.size() + num_new_nacks > kMaxNackPackets) {
}
if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
nack_list_.clear();
RTC_LOG(LS_WARNING) << "NACK list full, clearing NACK"
" list and requesting keyframe.";
keyframe_request_sender_->RequestKeyFrame();
return;
}
}
for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5));
RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
nack_list_[seq_num] = nack_info;
}
}
std::vector<uint16_t> NackModule::GetNackBatch(NackFilterOptions options) {
bool consider_seq_num = options != kTimeOnly;
bool consider_timestamp = options != kSeqNumOnly;
int64_t now_ms = clock_->TimeInMilliseconds();
std::vector<uint16_t> nack_batch;
auto it = nack_list_.begin();
while (it != nack_list_.end()) {
if (consider_seq_num && it->second.sent_at_time == -1 &&
AheadOrAt(newest_seq_num_, it->second.send_at_seq_num)) {
nack_batch.emplace_back(it->second.seq_num);
++it->second.retries;
it->second.sent_at_time = now_ms;
if (it->second.retries >= kMaxNackRetries) {
RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
<< " removed from NACK list due to max retries.";
it = nack_list_.erase(it);
} else {
++it;
}
continue;
}
if (consider_timestamp && it->second.sent_at_time + rtt_ms_ <= now_ms) {
nack_batch.emplace_back(it->second.seq_num);
++it->second.retries;
it->second.sent_at_time = now_ms;
if (it->second.retries >= kMaxNackRetries) {
RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
<< " removed from NACK list due to max retries.";
it = nack_list_.erase(it);
} else {
++it;
}
continue;
}
++it;
}
return nack_batch;
}
void NackModule::UpdateReorderingStatistics(uint16_t seq_num) {
RTC_DCHECK(AheadOf(newest_seq_num_, seq_num));
uint16_t diff = ReverseDiff(newest_seq_num_, seq_num);
reordering_histogram_.Add(diff);
}
int NackModule::WaitNumberOfPackets(float probability) const {
if (reordering_histogram_.NumValues() == 0)
return 0;
return reordering_histogram_.InverseCdf(probability);
}
} // namespace webrtc