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