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