1 // Copyright 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "net/quic/quic_received_packet_manager.h" 6 7 #include "base/logging.h" 8 #include "base/stl_util.h" 9 #include "net/base/linked_hash_map.h" 10 #include "net/quic/quic_connection_stats.h" 11 12 using std::make_pair; 13 using std::max; 14 using std::min; 15 16 namespace net { 17 18 namespace { 19 20 // The maximum number of packets to ack immediately after a missing packet for 21 // fast retransmission to kick in at the sender. This limit is created to 22 // reduce the number of acks sent that have no benefit for fast retransmission. 23 // Set to the number of nacks needed for fast retransmit plus one for protection 24 // against an ack loss 25 const size_t kMaxPacketsAfterNewMissing = 4; 26 27 } 28 29 QuicReceivedPacketManager::EntropyTracker::EntropyTracker() 30 : packets_entropy_hash_(0), 31 first_gap_(1), 32 largest_observed_(0) { 33 } 34 35 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {} 36 37 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash( 38 QuicPacketSequenceNumber sequence_number) const { 39 DCHECK_LE(sequence_number, largest_observed_); 40 if (sequence_number == largest_observed_) { 41 return packets_entropy_hash_; 42 } 43 44 DCHECK_GE(sequence_number, first_gap_); 45 ReceivedEntropyMap::const_iterator it = 46 packets_entropy_.upper_bound(sequence_number); 47 // When this map is empty we should only query entropy for 48 // largest_observed_, since no other entropy can be correctly 49 // calculated, because we're not storing the entropy for any prior packets. 50 // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium. 51 // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10) 52 LOG_IF(DFATAL, it == packets_entropy_.end()) 53 << "EntropyHash may be unknown. largest_received: " 54 << largest_observed_ 55 << " sequence_number: " << sequence_number; 56 57 // TODO(satyamshekhar): Make this O(1). 58 QuicPacketEntropyHash hash = packets_entropy_hash_; 59 for (; it != packets_entropy_.end(); ++it) { 60 hash ^= it->second; 61 } 62 return hash; 63 } 64 65 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash( 66 QuicPacketSequenceNumber sequence_number, 67 QuicPacketEntropyHash entropy_hash) { 68 if (sequence_number < first_gap_) { 69 DVLOG(1) << "Ignoring received packet entropy for sequence_number:" 70 << sequence_number << " less than largest_peer_sequence_number:" 71 << first_gap_; 72 return; 73 } 74 75 if (sequence_number > largest_observed_) { 76 largest_observed_ = sequence_number; 77 } 78 79 packets_entropy_hash_ ^= entropy_hash; 80 DVLOG(2) << "setting cumulative received entropy hash to: " 81 << static_cast<int>(packets_entropy_hash_) 82 << " updated with sequence number " << sequence_number 83 << " entropy hash: " << static_cast<int>(entropy_hash); 84 85 packets_entropy_.insert(make_pair(sequence_number, entropy_hash)); 86 AdvanceFirstGapAndGarbageCollectEntropyMap(); 87 } 88 89 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo( 90 QuicPacketSequenceNumber sequence_number, 91 QuicPacketEntropyHash entropy_hash) { 92 DCHECK_LE(sequence_number, largest_observed_); 93 if (sequence_number < first_gap_) { 94 DVLOG(1) << "Ignoring set entropy at:" << sequence_number 95 << " less than first_gap_:" << first_gap_; 96 return; 97 } 98 // Compute the current entropy based on the hash. 99 packets_entropy_hash_ = entropy_hash; 100 ReceivedEntropyMap::iterator it = 101 packets_entropy_.lower_bound(sequence_number); 102 // TODO(satyamshekhar): Make this O(1). 103 for (; it != packets_entropy_.end(); ++it) { 104 packets_entropy_hash_ ^= it->second; 105 } 106 // Update first_gap_ and discard old entropies. 107 first_gap_ = sequence_number; 108 packets_entropy_.erase( 109 packets_entropy_.begin(), 110 packets_entropy_.lower_bound(sequence_number)); 111 112 // Garbage collect entries from the beginning of the map. 113 AdvanceFirstGapAndGarbageCollectEntropyMap(); 114 } 115 116 void QuicReceivedPacketManager::EntropyTracker:: 117 AdvanceFirstGapAndGarbageCollectEntropyMap() { 118 while (!packets_entropy_.empty()) { 119 ReceivedEntropyMap::iterator it = packets_entropy_.begin(); 120 if (it->first != first_gap_) { 121 DCHECK_GT(it->first, first_gap_); 122 break; 123 } 124 packets_entropy_.erase(it); 125 ++first_gap_; 126 } 127 } 128 129 QuicReceivedPacketManager::QuicReceivedPacketManager( 130 CongestionFeedbackType congestion_type, 131 QuicConnectionStats* stats) 132 : peer_largest_observed_packet_(0), 133 least_packet_awaited_by_peer_(1), 134 peer_least_packet_awaiting_ack_(0), 135 time_largest_observed_(QuicTime::Zero()), 136 receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)), 137 stats_(stats) { 138 received_info_.largest_observed = 0; 139 received_info_.entropy_hash = 0; 140 } 141 142 QuicReceivedPacketManager::~QuicReceivedPacketManager() {} 143 144 void QuicReceivedPacketManager::RecordPacketReceived( 145 QuicByteCount bytes, 146 const QuicPacketHeader& header, 147 QuicTime receipt_time) { 148 QuicPacketSequenceNumber sequence_number = header.packet_sequence_number; 149 DCHECK(IsAwaitingPacket(sequence_number)); 150 151 InsertMissingPacketsBetween( 152 &received_info_, 153 max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_), 154 sequence_number); 155 156 if (received_info_.largest_observed > sequence_number) { 157 // We've gotten one of the out of order packets - remove it from our 158 // "missing packets" list. 159 DVLOG(1) << "Removing " << sequence_number << " from missing list"; 160 received_info_.missing_packets.erase(sequence_number); 161 162 // Record how out of order stats. 163 ++stats_->packets_reordered; 164 uint32 sequence_gap = received_info_.largest_observed - sequence_number; 165 stats_->max_sequence_reordering = 166 max(stats_->max_sequence_reordering, sequence_gap); 167 uint32 reordering_time_us = 168 receipt_time.Subtract(time_largest_observed_).ToMicroseconds(); 169 stats_->max_time_reordering_us = max(stats_->max_time_reordering_us, 170 reordering_time_us); 171 } 172 if (sequence_number > received_info_.largest_observed) { 173 received_info_.largest_observed = sequence_number; 174 time_largest_observed_ = receipt_time; 175 } 176 entropy_tracker_.RecordPacketEntropyHash(sequence_number, 177 header.entropy_hash); 178 179 receive_algorithm_->RecordIncomingPacket( 180 bytes, sequence_number, receipt_time); 181 } 182 183 void QuicReceivedPacketManager::RecordPacketRevived( 184 QuicPacketSequenceNumber sequence_number) { 185 LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number)); 186 received_info_.revived_packets.insert(sequence_number); 187 } 188 189 bool QuicReceivedPacketManager::IsMissing( 190 QuicPacketSequenceNumber sequence_number) { 191 return ContainsKey(received_info_.missing_packets, sequence_number); 192 } 193 194 bool QuicReceivedPacketManager::IsAwaitingPacket( 195 QuicPacketSequenceNumber sequence_number) { 196 return ::net::IsAwaitingPacket(received_info_, sequence_number); 197 } 198 199 void QuicReceivedPacketManager::UpdateReceivedPacketInfo( 200 ReceivedPacketInfo* received_info, 201 QuicTime approximate_now) { 202 *received_info = received_info_; 203 received_info->entropy_hash = EntropyHash(received_info_.largest_observed); 204 205 if (time_largest_observed_ == QuicTime::Zero()) { 206 // We have received no packets. 207 received_info->delta_time_largest_observed = QuicTime::Delta::Infinite(); 208 return; 209 } 210 211 if (approximate_now < time_largest_observed_) { 212 // Approximate now may well be "in the past". 213 received_info->delta_time_largest_observed = QuicTime::Delta::Zero(); 214 return; 215 } 216 217 received_info->delta_time_largest_observed = 218 approximate_now.Subtract(time_largest_observed_); 219 } 220 221 bool QuicReceivedPacketManager::GenerateCongestionFeedback( 222 QuicCongestionFeedbackFrame* feedback) { 223 return receive_algorithm_->GenerateCongestionFeedback(feedback); 224 } 225 226 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash( 227 QuicPacketSequenceNumber sequence_number) const { 228 return entropy_tracker_.EntropyHash(sequence_number); 229 } 230 231 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer( 232 const ReceivedPacketInfo& received_info) { 233 // ValidateAck should fail if largest_observed ever shrinks. 234 DCHECK_LE(peer_largest_observed_packet_, received_info.largest_observed); 235 peer_largest_observed_packet_ = received_info.largest_observed; 236 237 if (received_info.missing_packets.empty()) { 238 least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1; 239 } else { 240 least_packet_awaited_by_peer_ = *(received_info.missing_packets.begin()); 241 } 242 } 243 244 bool QuicReceivedPacketManager::DontWaitForPacketsBefore( 245 QuicPacketSequenceNumber least_unacked) { 246 received_info_.revived_packets.erase( 247 received_info_.revived_packets.begin(), 248 received_info_.revived_packets.lower_bound(least_unacked)); 249 size_t missing_packets_count = received_info_.missing_packets.size(); 250 received_info_.missing_packets.erase( 251 received_info_.missing_packets.begin(), 252 received_info_.missing_packets.lower_bound(least_unacked)); 253 return missing_packets_count != received_info_.missing_packets.size(); 254 } 255 256 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer( 257 const QuicStopWaitingFrame& stop_waiting) { 258 // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks. 259 DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked); 260 if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) { 261 bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked); 262 if (missed_packets) { 263 DVLOG(1) << "Updating entropy hashed since we missed packets"; 264 // There were some missing packets that we won't ever get now. Recalculate 265 // the received entropy hash. 266 entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked, 267 stop_waiting.entropy_hash); 268 } 269 peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked; 270 } 271 DCHECK(received_info_.missing_packets.empty() || 272 *received_info_.missing_packets.begin() >= 273 peer_least_packet_awaiting_ack_); 274 } 275 276 bool QuicReceivedPacketManager::HasMissingPackets() { 277 return !received_info_.missing_packets.empty(); 278 } 279 280 bool QuicReceivedPacketManager::HasNewMissingPackets() { 281 return HasMissingPackets() && 282 (received_info_.largest_observed - 283 *received_info_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing; 284 } 285 286 } // namespace net 287
