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