net/quic/quic_unacked_packet_map.cc

   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       bytes_in_flight_(0),
  20       pending_crypto_packet_count_(0) {
  21 }
  22
  23 QuicUnackedPacketMap::~QuicUnackedPacketMap() {
  24   for (UnackedPacketMap::iterator it = unacked_packets_.begin();
  25        it != unacked_packets_.end(); ++it) {
  26     delete it->second.retransmittable_frames;
  27     // Only delete all_transmissions once, for the newest packet.
  28     if (it->first == *it->second.all_transmissions->rbegin()) {
  29       delete it->second.all_transmissions;
  30     }
  31   }
  32 }
  33
  34 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
  35 // sent in order and the connection tracks RetransmittableFrames for longer.
  36 void QuicUnackedPacketMap::AddPacket(
  37     const SerializedPacket& serialized_packet) {
  38   if (!unacked_packets_.empty()) {
  39     bool is_old_packet = unacked_packets_.rbegin()->first >=
  40         serialized_packet.sequence_number;
  41     LOG_IF(DFATAL, is_old_packet) << "Old packet serialized: "
  42                                   << serialized_packet.sequence_number
  43                                   << " vs: "
  44                                   << unacked_packets_.rbegin()->first;
  45   }
  46
  47   unacked_packets_[serialized_packet.sequence_number] =
  48       TransmissionInfo(serialized_packet.retransmittable_frames,
  49                        serialized_packet.sequence_number,
  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::OnRetransmittedPacket(
  59     QuicPacketSequenceNumber old_sequence_number,
  60     QuicPacketSequenceNumber new_sequence_number,
  61     TransmissionType transmission_type) {
  62   DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
  63   DCHECK(unacked_packets_.empty() ||
  64          unacked_packets_.rbegin()->first < new_sequence_number);
  65
  66   // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
  67   TransmissionInfo* transmission_info =
  68       FindOrNull(unacked_packets_, old_sequence_number);
  69   RetransmittableFrames* frames = transmission_info->retransmittable_frames;
  70   LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no "
  71                                  << "retransmittable frames: "
  72                                  << old_sequence_number;
  73
  74   // We keep the old packet in the unacked packet list until it, or one of
  75   // the retransmissions of it are acked.
  76   transmission_info->retransmittable_frames = NULL;
  77   // Only keep one transmission older than largest observed, because only the
  78   // most recent is expected to possibly be a spurious retransmission.
  79   if (transmission_info->all_transmissions->size() > 1 &&
  80       *(++transmission_info->all_transmissions->begin()) < largest_observed_) {
  81     QuicPacketSequenceNumber old_transmission =
  82         *transmission_info->all_transmissions->begin();
  83     TransmissionInfo* old_transmission_info =
  84         FindOrNull(unacked_packets_, old_transmission);
  85     // Don't remove old packets if they're still in flight.
  86     if (old_transmission_info == NULL || !old_transmission_info->in_flight) {
  87       transmission_info->all_transmissions->erase(old_transmission);
  88       unacked_packets_.erase(old_transmission);
  89     }
  90   }
  91   unacked_packets_[new_sequence_number] =
  92       TransmissionInfo(frames,
  93                        new_sequence_number,
  94                        transmission_info->sequence_number_length,
  95                        transmission_type,
  96                        transmission_info->all_transmissions);
  97 }
  98
  99 void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
 100   UnackedPacketMap::iterator it = unacked_packets_.begin();
 101   while (it != unacked_packets_.end() && num_to_clear > 0) {
 102     QuicPacketSequenceNumber sequence_number = it->first;
 103     // If this packet is in flight, or has retransmittable data, then there is
 104     // no point in clearing out any further packets, because they would not
 105     // affect the high water mark.
 106     if (it->second.in_flight || it->second.retransmittable_frames != NULL) {
 107       break;
 108     }
 109
 110     it->second.all_transmissions->erase(sequence_number);
 111     LOG_IF(DFATAL, it->second.all_transmissions->empty())
 112         << "Previous retransmissions must have a newer transmission.";
 113     ++it;
 114     unacked_packets_.erase(sequence_number);
 115     --num_to_clear;
 116   }
 117 }
 118
 119 bool QuicUnackedPacketMap::HasRetransmittableFrames(
 120     QuicPacketSequenceNumber sequence_number) const {
 121   const TransmissionInfo* transmission_info =
 122       FindOrNull(unacked_packets_, sequence_number);
 123   if (transmission_info == NULL) {
 124     return false;
 125   }
 126
 127   return transmission_info->retransmittable_frames != NULL;
 128 }
 129
 130 void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
 131                                       size_t min_nacks) {
 132   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 133   if (it == unacked_packets_.end()) {
 134     LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
 135                 << sequence_number;
 136     return;
 137   }
 138
 139   it->second.nack_count = max(min_nacks, it->second.nack_count);
 140 }
 141
 142 void QuicUnackedPacketMap::RemoveRetransmittability(
 143     QuicPacketSequenceNumber sequence_number) {
 144   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 145   if (it == unacked_packets_.end()) {
 146     DVLOG(1) << "packet is not in unacked_packets: " << sequence_number;
 147     return;
 148   }
 149   SequenceNumberSet* all_transmissions = it->second.all_transmissions;
 150   // TODO(ianswett): Consider optimizing this for lone packets.
 151   // TODO(ianswett): Consider adding a check to ensure there are retransmittable
 152   // frames associated with this packet.
 153   for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin();
 154        it != all_transmissions->rend(); ++it) {
 155     TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it);
 156     if (transmission_info == NULL) {
 157       LOG(DFATAL) << "All transmissions in all_transmissions must be present "
 158                   << "in the unacked packet map.";
 159       continue;
 160     }
 161     MaybeRemoveRetransmittableFrames(transmission_info);
 162     if (*it <= largest_observed_ && !transmission_info->in_flight) {
 163       unacked_packets_.erase(*it);
 164     } else {
 165       transmission_info->all_transmissions = new SequenceNumberSet();
 166       transmission_info->all_transmissions->insert(*it);
 167     }
 168   }
 169
 170   delete all_transmissions;
 171 }
 172
 173 void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
 174     TransmissionInfo* transmission_info) {
 175   if (transmission_info->retransmittable_frames != NULL) {
 176     if (transmission_info->retransmittable_frames->HasCryptoHandshake()
 177             == IS_HANDSHAKE) {
 178       --pending_crypto_packet_count_;
 179     }
 180     delete transmission_info->retransmittable_frames;
 181     transmission_info->retransmittable_frames = NULL;
 182   }
 183 }
 184
 185 void QuicUnackedPacketMap::IncreaseLargestObserved(
 186     QuicPacketSequenceNumber largest_observed) {
 187   DCHECK_LE(largest_observed_, largest_observed);
 188   largest_observed_ = largest_observed;
 189   UnackedPacketMap::iterator it = unacked_packets_.begin();
 190   while (it != unacked_packets_.end() && it->first <= largest_observed_) {
 191     if (!IsPacketUseless(it)) {
 192       ++it;
 193       continue;
 194     }
 195     delete it->second.all_transmissions;
 196     QuicPacketSequenceNumber sequence_number = it->first;
 197     ++it;
 198     unacked_packets_.erase(sequence_number);
 199   }
 200 }
 201
 202 bool QuicUnackedPacketMap::IsPacketUseless(
 203     UnackedPacketMap::const_iterator it) const {
 204   return it->first <= largest_observed_ &&
 205       !it->second.in_flight &&
 206       it->second.retransmittable_frames == NULL &&
 207       it->second.all_transmissions->size() == 1;
 208 }
 209
 210 bool QuicUnackedPacketMap::IsUnacked(
 211     QuicPacketSequenceNumber sequence_number) const {
 212   return ContainsKey(unacked_packets_, sequence_number);
 213 }
 214
 215 void QuicUnackedPacketMap::RemoveFromInFlight(
 216     QuicPacketSequenceNumber sequence_number) {
 217   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 218   if (it == unacked_packets_.end()) {
 219     LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: "
 220                 << sequence_number;
 221     return;
 222   }
 223   if (it->second.in_flight) {
 224     LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
 225     bytes_in_flight_ -= it->second.bytes_sent;
 226     it->second.in_flight = false;
 227   }
 228   if (IsPacketUseless(it)) {
 229     delete it->second.all_transmissions;
 230     unacked_packets_.erase(it);
 231   }
 232 }
 233
 234 bool QuicUnackedPacketMap::HasUnackedPackets() const {
 235   return !unacked_packets_.empty();
 236 }
 237
 238 bool QuicUnackedPacketMap::HasInFlightPackets() const {
 239   return bytes_in_flight_ > 0;
 240 }
 241
 242 const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
 243     QuicPacketSequenceNumber sequence_number) const {
 244   return unacked_packets_.find(sequence_number)->second;
 245 }
 246
 247 QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
 248   UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
 249   while (it != unacked_packets_.rend()) {
 250     if (it->second.in_flight) {
 251       LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero())
 252           << "Sent time can never be zero for a packet in flight.";
 253       return it->second.sent_time;
 254     }
 255     ++it;
 256   }
 257   LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
 258   return QuicTime::Zero();
 259 }
 260
 261 QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
 262   UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 263   while (it != unacked_packets_.end() && !it->second.in_flight) {
 264     ++it;
 265   }
 266   if (it == unacked_packets_.end()) {
 267     LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
 268     return QuicTime::Zero();
 269   }
 270   return it->second.sent_time;
 271 }
 272
 273 size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
 274   return unacked_packets_.size();
 275 }
 276
 277 bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
 278   size_t num_in_flight = 0;
 279   for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
 280        it != unacked_packets_.rend(); ++it) {
 281     if (it->second.in_flight) {
 282       ++num_in_flight;
 283     }
 284     if (num_in_flight > 1) {
 285       return true;
 286     }
 287   }
 288   return false;
 289 }
 290
 291 bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
 292   return pending_crypto_packet_count_ > 0;
 293 }
 294
 295 bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
 296   for (UnackedPacketMap::const_reverse_iterator it =
 297            unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
 298     if (it->second.in_flight && it->second.retransmittable_frames) {
 299       return true;
 300     }
 301   }
 302   return false;
 303 }
 304
 305 QuicPacketSequenceNumber
 306 QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
 307   if (unacked_packets_.empty()) {
 308     // If there are no unacked packets, return 0.
 309     return 0;
 310   }
 311
 312   return unacked_packets_.begin()->first;
 313 }
 314
 315 void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
 316                                    QuicTime sent_time,
 317                                    QuicByteCount bytes_sent,
 318                                    bool set_in_flight) {
 319   DCHECK_LT(0u, sequence_number);
 320   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 321   if (it == unacked_packets_.end()) {
 322     LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
 323                 << sequence_number;
 324     return;
 325   }
 326   DCHECK(!it->second.in_flight);
 327
 328   largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
 329   it->second.sent_time = sent_time;
 330   if (set_in_flight) {
 331     bytes_in_flight_ += bytes_sent;
 332     it->second.bytes_sent = bytes_sent;
 333     it->second.in_flight = true;
 334   }
 335 }
 336
 337 void QuicUnackedPacketMap::RestoreInFlight(
 338     QuicPacketSequenceNumber sequence_number) {
 339   DCHECK_LT(0u, sequence_number);
 340   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 341   if (it == unacked_packets_.end()) {
 342     LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
 343                 << sequence_number;
 344     return;
 345   }
 346   DCHECK(!it->second.in_flight);
 347   DCHECK_NE(0u, it->second.bytes_sent);
 348   DCHECK(it->second.sent_time.IsInitialized());
 349
 350   bytes_in_flight_ += it->second.bytes_sent;
 351   it->second.in_flight = true;
 352 }
 353
 354 }  // namespace net