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   unacked_packets_[new_sequence_number] =
  78       TransmissionInfo(frames,
  79                        new_sequence_number,
  80                        transmission_info->sequence_number_length,
  81                        transmission_type,
  82                        transmission_info->all_transmissions);
  83 }
  84
  85 void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
  86   UnackedPacketMap::iterator it = unacked_packets_.begin();
  87   while (it != unacked_packets_.end() && num_to_clear > 0) {
  88     QuicPacketSequenceNumber sequence_number = it->first;
  89     // If this packet is in flight, or has retransmittable data, then there is
  90     // no point in clearing out any further packets, because they would not
  91     // affect the high water mark.
  92     if (it->second.in_flight || it->second.retransmittable_frames != NULL) {
  93       break;
  94     }
  95
  96     it->second.all_transmissions->erase(sequence_number);
  97     LOG_IF(DFATAL, it->second.all_transmissions->empty())
  98         << "Previous retransmissions must have a newer transmission.";
  99     ++it;
 100     unacked_packets_.erase(sequence_number);
 101     --num_to_clear;
 102   }
 103 }
 104
 105 bool QuicUnackedPacketMap::HasRetransmittableFrames(
 106     QuicPacketSequenceNumber sequence_number) const {
 107   const TransmissionInfo* transmission_info =
 108       FindOrNull(unacked_packets_, sequence_number);
 109   if (transmission_info == NULL) {
 110     return false;
 111   }
 112
 113   return transmission_info->retransmittable_frames != NULL;
 114 }
 115
 116 void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
 117                                       size_t min_nacks) {
 118   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 119   if (it == unacked_packets_.end()) {
 120     LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
 121                 << sequence_number;
 122     return;
 123   }
 124
 125   it->second.nack_count = max(min_nacks, it->second.nack_count);
 126 }
 127
 128 void QuicUnackedPacketMap::RemoveRetransmittability(
 129     QuicPacketSequenceNumber sequence_number) {
 130   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 131   if (it == unacked_packets_.end()) {
 132     DVLOG(1) << "packet is not in unacked_packets: " << sequence_number;
 133     return;
 134   }
 135   SequenceNumberSet* all_transmissions = it->second.all_transmissions;
 136   // TODO(ianswett): Consider optimizing this for lone packets.
 137   // TODO(ianswett): Consider adding a check to ensure there are retransmittable
 138   // frames associated with this packet.
 139   for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin();
 140        it != all_transmissions->rend(); ++it) {
 141     TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it);
 142     if (transmission_info == NULL) {
 143       LOG(DFATAL) << "All transmissions in all_transmissions must be present "
 144                   << "in the unacked packet map.";
 145       continue;
 146     }
 147     MaybeRemoveRetransmittableFrames(transmission_info);
 148     if (*it <= largest_observed_ && !transmission_info->in_flight) {
 149       unacked_packets_.erase(*it);
 150     } else {
 151       transmission_info->all_transmissions = new SequenceNumberSet();
 152       transmission_info->all_transmissions->insert(*it);
 153     }
 154   }
 155
 156   delete all_transmissions;
 157 }
 158
 159 void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
 160     TransmissionInfo* transmission_info) {
 161   if (transmission_info->retransmittable_frames != NULL) {
 162     if (transmission_info->retransmittable_frames->HasCryptoHandshake()
 163             == IS_HANDSHAKE) {
 164       --pending_crypto_packet_count_;
 165     }
 166     delete transmission_info->retransmittable_frames;
 167     transmission_info->retransmittable_frames = NULL;
 168   }
 169 }
 170
 171 void QuicUnackedPacketMap::IncreaseLargestObserved(
 172     QuicPacketSequenceNumber largest_observed) {
 173   DCHECK_LT(largest_observed_, largest_observed);
 174   largest_observed_ = largest_observed;
 175   UnackedPacketMap::iterator it = unacked_packets_.begin();
 176   while (it != unacked_packets_.end() && it->first <= largest_observed_) {
 177     if (!IsPacketUseless(it)) {
 178       ++it;
 179       continue;
 180     }
 181     delete it->second.all_transmissions;
 182     QuicPacketSequenceNumber sequence_number = it->first;
 183     ++it;
 184     unacked_packets_.erase(sequence_number);
 185   }
 186 }
 187
 188 bool QuicUnackedPacketMap::IsPacketUseless(
 189     UnackedPacketMap::const_iterator it) const {
 190   return it->first <= largest_observed_ &&
 191       !it->second.in_flight &&
 192       it->second.retransmittable_frames == NULL &&
 193       it->second.all_transmissions->size() == 1;
 194 }
 195
 196 bool QuicUnackedPacketMap::IsUnacked(
 197     QuicPacketSequenceNumber sequence_number) const {
 198   return ContainsKey(unacked_packets_, sequence_number);
 199 }
 200
 201 void QuicUnackedPacketMap::RemoveFromInFlight(
 202     QuicPacketSequenceNumber sequence_number) {
 203   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 204   if (it == unacked_packets_.end()) {
 205     LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: "
 206                 << sequence_number;
 207     return;
 208   }
 209   if (it->second.in_flight) {
 210     LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
 211     bytes_in_flight_ -= it->second.bytes_sent;
 212     it->second.in_flight = false;
 213   }
 214   if (IsPacketUseless(it)) {
 215     delete it->second.all_transmissions;
 216     unacked_packets_.erase(it);
 217   }
 218 }
 219
 220 bool QuicUnackedPacketMap::HasUnackedPackets() const {
 221   return !unacked_packets_.empty();
 222 }
 223
 224 bool QuicUnackedPacketMap::HasInFlightPackets() const {
 225   return bytes_in_flight_ > 0;
 226 }
 227
 228 const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
 229     QuicPacketSequenceNumber sequence_number) const {
 230   return unacked_packets_.find(sequence_number)->second;
 231 }
 232
 233 QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
 234   UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
 235   while (it != unacked_packets_.rend()) {
 236     if (it->second.in_flight) {
 237       LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero())
 238           << "Sent time can never be zero for a packet in flight.";
 239       return it->second.sent_time;
 240     }
 241     ++it;
 242   }
 243   LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
 244   return QuicTime::Zero();
 245 }
 246
 247 QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
 248   UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 249   while (it != unacked_packets_.end() && !it->second.in_flight) {
 250     ++it;
 251   }
 252   if (it == unacked_packets_.end()) {
 253     LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
 254     return QuicTime::Zero();
 255   }
 256   return it->second.sent_time;
 257 }
 258
 259 size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
 260   return unacked_packets_.size();
 261 }
 262
 263 bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
 264   size_t num_in_flight = 0;
 265   for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
 266        it != unacked_packets_.rend(); ++it) {
 267     if (it->second.in_flight) {
 268       ++num_in_flight;
 269     }
 270     if (num_in_flight > 1) {
 271       return true;
 272     }
 273   }
 274   return false;
 275 }
 276
 277 bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
 278   return pending_crypto_packet_count_ > 0;
 279 }
 280
 281 bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
 282   for (UnackedPacketMap::const_reverse_iterator it =
 283            unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
 284     if (it->second.in_flight && it->second.retransmittable_frames) {
 285       return true;
 286     }
 287   }
 288   return false;
 289 }
 290
 291 QuicPacketSequenceNumber
 292 QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
 293   if (unacked_packets_.empty()) {
 294     // If there are no unacked packets, return 0.
 295     return 0;
 296   }
 297
 298   return unacked_packets_.begin()->first;
 299 }
 300
 301 void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
 302                                    QuicTime sent_time,
 303                                    QuicByteCount bytes_sent,
 304                                    bool set_in_flight) {
 305   DCHECK_LT(0u, sequence_number);
 306   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 307   if (it == unacked_packets_.end()) {
 308     LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
 309                 << sequence_number;
 310     return;
 311   }
 312   DCHECK(!it->second.in_flight);
 313
 314   largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
 315   it->second.sent_time = sent_time;
 316   if (set_in_flight) {
 317     bytes_in_flight_ += bytes_sent;
 318     it->second.bytes_sent = bytes_sent;
 319     it->second.in_flight = true;
 320   }
 321 }
 322
 323 void QuicUnackedPacketMap::RestoreInFlight(
 324     QuicPacketSequenceNumber sequence_number) {
 325   DCHECK_LT(0u, sequence_number);
 326   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 327   if (it == unacked_packets_.end()) {
 328     LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
 329                 << sequence_number;
 330     return;
 331   }
 332   DCHECK(!it->second.in_flight);
 333   DCHECK_NE(0u, it->second.bytes_sent);
 334   DCHECK(it->second.sent_time.IsInitialized());
 335
 336   bytes_in_flight_ += it->second.bytes_sent;
 337   it->second.in_flight = true;
 338 }
 339
 340 }  // namespace net