1 // Copyright 2014 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_unacked_packet_map.h" 6 7 #include "base/logging.h" 8 #include "base/stl_util.h" 9 #include "net/quic/quic_connection_stats.h" 10 #include "net/quic/quic_utils_chromium.h" 11 12 using std::max; 13 14 namespace net { 15 16 QuicUnackedPacketMap::QuicUnackedPacketMap() 17 : largest_sent_packet_(0), 18 largest_observed_(0), 19 least_unacked_(1), 20 bytes_in_flight_(0), 21 pending_crypto_packet_count_(0) { 22 } 23 24 QuicUnackedPacketMap::~QuicUnackedPacketMap() { 25 QuicPacketSequenceNumber index = least_unacked_; 26 for (UnackedPacketMap::iterator it = unacked_packets_.begin(); 27 it != unacked_packets_.end(); ++it, ++index) { 28 delete it->retransmittable_frames; 29 // Only delete all_transmissions once, for the newest packet. 30 if (it->all_transmissions != NULL && 31 index == *it->all_transmissions->rbegin()) { 32 delete it->all_transmissions; 33 } 34 } 35 } 36 37 // TODO(ianswett): Combine this method with OnPacketSent once packets are always 38 // sent in order and the connection tracks RetransmittableFrames for longer. 39 void QuicUnackedPacketMap::AddPacket( 40 const SerializedPacket& serialized_packet) { 41 DCHECK_GE(serialized_packet.sequence_number, 42 least_unacked_ + unacked_packets_.size()); 43 while (least_unacked_ + unacked_packets_.size() < 44 serialized_packet.sequence_number) { 45 unacked_packets_.push_back(TransmissionInfo()); 46 unacked_packets_.back().is_unackable = true; 47 } 48 unacked_packets_.push_back( 49 TransmissionInfo(serialized_packet.retransmittable_frames, 50 serialized_packet.sequence_number_length)); 51 if (serialized_packet.retransmittable_frames != NULL && 52 serialized_packet.retransmittable_frames->HasCryptoHandshake() 53 == IS_HANDSHAKE) { 54 ++pending_crypto_packet_count_; 55 } 56 } 57 58 void QuicUnackedPacketMap::RemoveObsoletePackets() { 59 while (!unacked_packets_.empty()) { 60 if (!IsPacketRemovable(least_unacked_, unacked_packets_.front())) { 61 break; 62 } 63 unacked_packets_.pop_front(); 64 ++least_unacked_; 65 } 66 } 67 68 void QuicUnackedPacketMap::OnRetransmittedPacket( 69 QuicPacketSequenceNumber old_sequence_number, 70 QuicPacketSequenceNumber new_sequence_number, 71 TransmissionType transmission_type) { 72 DCHECK_GE(old_sequence_number, least_unacked_); 73 DCHECK_LT(old_sequence_number, least_unacked_ + unacked_packets_.size()); 74 DCHECK_GE(new_sequence_number, least_unacked_ + unacked_packets_.size()); 75 while (least_unacked_ + unacked_packets_.size() < new_sequence_number) { 76 unacked_packets_.push_back(TransmissionInfo()); 77 unacked_packets_.back().is_unackable = true; 78 } 79 80 // TODO(ianswett): Discard and lose the packet lazily instead of immediately. 81 TransmissionInfo* transmission_info = 82 &unacked_packets_.at(old_sequence_number - least_unacked_); 83 RetransmittableFrames* frames = transmission_info->retransmittable_frames; 84 LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no " 85 << "retransmittable frames: " 86 << old_sequence_number; 87 88 // We keep the old packet in the unacked packet list until it, or one of 89 // the retransmissions of it are acked. 90 transmission_info->retransmittable_frames = NULL; 91 // Only keep one transmission older than largest observed, because only the 92 // most recent is expected to possibly be a spurious retransmission. 93 while (transmission_info->all_transmissions != NULL && 94 transmission_info->all_transmissions->size() > 1 && 95 *(++transmission_info->all_transmissions->begin()) 96 < largest_observed_) { 97 QuicPacketSequenceNumber old_transmission = 98 *transmission_info->all_transmissions->begin(); 99 TransmissionInfo* old_info = 100 &unacked_packets_[old_transmission - least_unacked_]; 101 // Don't remove old packets if they're still in flight. 102 if (old_info->in_flight) { 103 break; 104 } 105 old_info->all_transmissions->pop_front(); 106 // This will cause the packet be removed in RemoveObsoletePackets. 107 old_info->all_transmissions = NULL; 108 } 109 // Don't link old transmissions to new ones when version or 110 // encryption changes. 111 if (transmission_type == ALL_INITIAL_RETRANSMISSION || 112 transmission_type == ALL_UNACKED_RETRANSMISSION) { 113 RemoveAckability(transmission_info); 114 } else { 115 if (transmission_info->all_transmissions == NULL) { 116 transmission_info->all_transmissions = new SequenceNumberList(); 117 transmission_info->all_transmissions->push_back(old_sequence_number); 118 } 119 transmission_info->all_transmissions->push_back(new_sequence_number); 120 } 121 unacked_packets_.push_back( 122 TransmissionInfo(frames, 123 transmission_info->sequence_number_length, 124 transmission_type, 125 transmission_info->all_transmissions)); 126 RemoveObsoletePackets(); 127 } 128 129 void QuicUnackedPacketMap::ClearAllPreviousRetransmissions() { 130 while (!unacked_packets_.empty() && least_unacked_ < largest_observed_) { 131 // If this packet is in flight, or has retransmittable data, then there is 132 // no point in clearing out any further packets, because they would not 133 // affect the high water mark. 134 TransmissionInfo* info = &unacked_packets_.front(); 135 if (info->in_flight || info->retransmittable_frames != NULL) { 136 break; 137 } 138 139 if (info->all_transmissions != NULL) { 140 if (info->all_transmissions->size() < 2) { 141 LOG(DFATAL) << "all_transmissions must be NULL or have multiple " 142 << "elements. size:" << info->all_transmissions->size(); 143 delete info->all_transmissions; 144 } else { 145 info->all_transmissions->pop_front(); 146 if (info->all_transmissions->size() == 1) { 147 // Set the newer transmission's 'all_transmissions' entry to NULL. 148 QuicPacketSequenceNumber new_transmission = 149 info->all_transmissions->front(); 150 TransmissionInfo* new_info = 151 &unacked_packets_.at(new_transmission - least_unacked_); 152 delete new_info->all_transmissions; 153 new_info->all_transmissions = NULL; 154 } 155 } 156 } 157 unacked_packets_.pop_front(); 158 ++least_unacked_; 159 } 160 } 161 162 bool QuicUnackedPacketMap::HasRetransmittableFrames( 163 QuicPacketSequenceNumber sequence_number) const { 164 DCHECK_GE(sequence_number, least_unacked_); 165 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 166 return unacked_packets_[ 167 sequence_number - least_unacked_].retransmittable_frames != NULL; 168 } 169 170 void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number, 171 size_t min_nacks) { 172 DCHECK_GE(sequence_number, least_unacked_); 173 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 174 unacked_packets_[sequence_number - least_unacked_].nack_count = 175 max(min_nacks, 176 unacked_packets_[sequence_number - least_unacked_].nack_count); 177 } 178 179 void QuicUnackedPacketMap::RemoveRetransmittability( 180 QuicPacketSequenceNumber sequence_number) { 181 DCHECK_GE(sequence_number, least_unacked_); 182 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 183 TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; 184 SequenceNumberList* all_transmissions = info->all_transmissions; 185 if (all_transmissions == NULL) { 186 MaybeRemoveRetransmittableFrames(info); 187 return; 188 } 189 // TODO(ianswett): Consider adding a check to ensure there are retransmittable 190 // frames associated with this packet. 191 for (SequenceNumberList::const_iterator it = all_transmissions->begin(); 192 it != all_transmissions->end(); ++it) { 193 TransmissionInfo* transmission_info = 194 &unacked_packets_[*it - least_unacked_]; 195 MaybeRemoveRetransmittableFrames(transmission_info); 196 transmission_info->all_transmissions = NULL; 197 } 198 delete all_transmissions; 199 } 200 201 void QuicUnackedPacketMap::RemoveAckability(TransmissionInfo* info) { 202 DCHECK(info->retransmittable_frames == NULL); 203 info->is_unackable = true; 204 SequenceNumberList* all_transmissions = info->all_transmissions; 205 if (all_transmissions == NULL) { 206 return; 207 } 208 for (SequenceNumberList::const_iterator it = all_transmissions->begin(); 209 it != all_transmissions->end(); ++it) { 210 TransmissionInfo* transmission_info = 211 &unacked_packets_[*it - least_unacked_]; 212 transmission_info->all_transmissions = NULL; 213 transmission_info->is_unackable = true; 214 } 215 delete all_transmissions; 216 } 217 218 void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames( 219 TransmissionInfo* transmission_info) { 220 if (transmission_info->retransmittable_frames != NULL) { 221 if (transmission_info->retransmittable_frames->HasCryptoHandshake() 222 == IS_HANDSHAKE) { 223 --pending_crypto_packet_count_; 224 } 225 delete transmission_info->retransmittable_frames; 226 transmission_info->retransmittable_frames = NULL; 227 } 228 } 229 230 void QuicUnackedPacketMap::IncreaseLargestObserved( 231 QuicPacketSequenceNumber largest_observed) { 232 DCHECK_LE(largest_observed_, largest_observed); 233 largest_observed_ = largest_observed; 234 } 235 236 bool QuicUnackedPacketMap::IsPacketUseless( 237 QuicPacketSequenceNumber sequence_number, 238 const TransmissionInfo& info) const { 239 return (info.is_unackable || sequence_number <= largest_observed_) && 240 !info.in_flight && 241 info.retransmittable_frames == NULL && 242 info.all_transmissions == NULL; 243 } 244 245 bool QuicUnackedPacketMap::IsPacketRemovable( 246 QuicPacketSequenceNumber sequence_number, 247 const TransmissionInfo& info) const { 248 return (info.is_unackable || 249 sequence_number <= largest_observed_ || 250 unacked_packets_.size() > kMaxTcpCongestionWindow) && 251 !info.in_flight && 252 info.retransmittable_frames == NULL && 253 info.all_transmissions == NULL; 254 } 255 256 bool QuicUnackedPacketMap::IsUnacked( 257 QuicPacketSequenceNumber sequence_number) const { 258 if (sequence_number < least_unacked_ || 259 sequence_number >= least_unacked_ + unacked_packets_.size()) { 260 return false; 261 } 262 return !IsPacketUseless(sequence_number, 263 unacked_packets_[sequence_number - least_unacked_]); 264 } 265 266 void QuicUnackedPacketMap::RemoveFromInFlight( 267 QuicPacketSequenceNumber sequence_number) { 268 DCHECK_GE(sequence_number, least_unacked_); 269 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 270 TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; 271 if (info->in_flight) { 272 LOG_IF(DFATAL, bytes_in_flight_ < info->bytes_sent); 273 bytes_in_flight_ -= info->bytes_sent; 274 info->in_flight = false; 275 } 276 } 277 278 bool QuicUnackedPacketMap::HasUnackedPackets() const { 279 return !unacked_packets_.empty(); 280 } 281 282 bool QuicUnackedPacketMap::HasInFlightPackets() const { 283 return bytes_in_flight_ > 0; 284 } 285 286 const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo( 287 QuicPacketSequenceNumber sequence_number) const { 288 return unacked_packets_[sequence_number - least_unacked_]; 289 } 290 291 QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const { 292 UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); 293 while (it != unacked_packets_.rend()) { 294 if (it->in_flight) { 295 LOG_IF(DFATAL, it->sent_time == QuicTime::Zero()) 296 << "Sent time can never be zero for a packet in flight."; 297 return it->sent_time; 298 } 299 ++it; 300 } 301 LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets."; 302 return QuicTime::Zero(); 303 } 304 305 QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const { 306 UnackedPacketMap::const_iterator it = unacked_packets_.begin(); 307 while (it != unacked_packets_.end() && !it->in_flight) { 308 ++it; 309 } 310 if (it == unacked_packets_.end()) { 311 LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets."; 312 return QuicTime::Zero(); 313 } 314 return it->sent_time; 315 } 316 317 size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const { 318 size_t unacked_packet_count = 0; 319 QuicPacketSequenceNumber sequence_number = least_unacked_; 320 for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); 321 it != unacked_packets_.end(); ++it, ++sequence_number) { 322 if (!IsPacketUseless(sequence_number, *it)) { 323 ++unacked_packet_count; 324 } 325 } 326 return unacked_packet_count; 327 } 328 329 bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const { 330 size_t num_in_flight = 0; 331 for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); 332 it != unacked_packets_.rend(); ++it) { 333 if (it->in_flight) { 334 ++num_in_flight; 335 } 336 if (num_in_flight > 1) { 337 return true; 338 } 339 } 340 return false; 341 } 342 343 bool QuicUnackedPacketMap::HasPendingCryptoPackets() const { 344 return pending_crypto_packet_count_ > 0; 345 } 346 347 bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const { 348 for (UnackedPacketMap::const_reverse_iterator it = 349 unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { 350 if (it->in_flight && it->retransmittable_frames) { 351 return true; 352 } 353 } 354 return false; 355 } 356 357 QuicPacketSequenceNumber 358 QuicUnackedPacketMap::GetLeastUnacked() const { 359 return least_unacked_; 360 } 361 362 void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number, 363 QuicTime sent_time, 364 QuicByteCount bytes_sent, 365 bool set_in_flight) { 366 DCHECK_GE(sequence_number, least_unacked_); 367 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 368 TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; 369 DCHECK(!info->in_flight); 370 371 DCHECK_LT(largest_sent_packet_, sequence_number); 372 largest_sent_packet_ = max(sequence_number, largest_sent_packet_); 373 info->sent_time = sent_time; 374 if (set_in_flight) { 375 bytes_in_flight_ += bytes_sent; 376 info->bytes_sent = bytes_sent; 377 info->in_flight = true; 378 } 379 } 380 381 void QuicUnackedPacketMap::RestoreInFlight( 382 QuicPacketSequenceNumber sequence_number) { 383 DCHECK_GE(sequence_number, least_unacked_); 384 DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); 385 TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; 386 DCHECK(!info->in_flight); 387 DCHECK_NE(0u, info->bytes_sent); 388 DCHECK(info->sent_time.IsInitialized()); 389 390 bytes_in_flight_ += info->bytes_sent; 391 info->in_flight = true; 392 } 393 394 } // namespace net 395