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