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_ack_notifier_manager.h"
  10 #include "net/quic/quic_connection_stats.h"
  11 #include "net/quic/quic_flags.h"
  12 #include "net/quic/quic_utils_chromium.h"
  13
  14 using std::max;
  15
  16 namespace net {
  17
  18 QuicUnackedPacketMap::QuicUnackedPacketMap(
  19     AckNotifierManager* ack_notifier_manager)
  20     : largest_sent_packet_(0),
  21       largest_observed_(0),
  22       least_unacked_(1),
  23       bytes_in_flight_(0),
  24       pending_crypto_packet_count_(0),
  25       ack_notifier_manager_(ack_notifier_manager) {
  26 }
  27
  28 QuicUnackedPacketMap::~QuicUnackedPacketMap() {
  29   QuicPacketSequenceNumber index = least_unacked_;
  30   for (UnackedPacketMap::iterator it = unacked_packets_.begin();
  31        it != unacked_packets_.end(); ++it, ++index) {
  32     delete it->retransmittable_frames;
  33     // Only delete all_transmissions once, for the newest packet.
  34     if (it->all_transmissions != nullptr &&
  35         index == *it->all_transmissions->rbegin()) {
  36       delete it->all_transmissions;
  37     }
  38   }
  39 }
  40
  41 void QuicUnackedPacketMap::AddSentPacket(
  42     const SerializedPacket& packet,
  43     QuicPacketSequenceNumber old_sequence_number,
  44     TransmissionType transmission_type,
  45     QuicTime sent_time,
  46     QuicByteCount bytes_sent,
  47     bool set_in_flight) {
  48   QuicPacketSequenceNumber sequence_number = packet.sequence_number;
  49   LOG_IF(DFATAL, largest_sent_packet_ > sequence_number);
  50   DCHECK_GE(sequence_number, least_unacked_ + unacked_packets_.size());
  51   while (least_unacked_ + unacked_packets_.size() < sequence_number) {
  52     unacked_packets_.push_back(TransmissionInfo());
  53     unacked_packets_.back().is_unackable = true;
  54   }
  55
  56   TransmissionInfo info(packet.retransmittable_frames,
  57                         packet.sequence_number_length, transmission_type,
  58                         sent_time, bytes_sent, packet.is_fec_packet);
  59   if (old_sequence_number == 0) {
  60     if (packet.retransmittable_frames != nullptr &&
  61         packet.retransmittable_frames->HasCryptoHandshake() == IS_HANDSHAKE) {
  62       ++pending_crypto_packet_count_;
  63     }
  64   } else {
  65     TransferRetransmissionInfo(
  66         old_sequence_number, sequence_number, transmission_type, &info);
  67   }
  68
  69   largest_sent_packet_ = sequence_number;
  70   if (set_in_flight) {
  71     bytes_in_flight_ += 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 (!IsPacketUseless(least_unacked_, unacked_packets_.front())) {
  80       break;
  81     }
  82     PopLeastUnacked();
  83   }
  84 }
  85
  86 void QuicUnackedPacketMap::TransferRetransmissionInfo(
  87     QuicPacketSequenceNumber old_sequence_number,
  88     QuicPacketSequenceNumber new_sequence_number,
  89     TransmissionType transmission_type,
  90     TransmissionInfo* info) {
  91   DCHECK_GE(old_sequence_number, least_unacked_);
  92   DCHECK_LT(old_sequence_number, least_unacked_ + unacked_packets_.size());
  93   DCHECK_GE(new_sequence_number, least_unacked_ + unacked_packets_.size());
  94   DCHECK_NE(NOT_RETRANSMISSION, transmission_type);
  95
  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     PopLeastUnacked();
 169   }
 170 }
 171
 172 bool QuicUnackedPacketMap::HasRetransmittableFrames(
 173     QuicPacketSequenceNumber sequence_number) const {
 174   DCHECK_GE(sequence_number, least_unacked_);
 175   DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
 176   return unacked_packets_[sequence_number - least_unacked_]
 177              .retransmittable_frames != nullptr;
 178 }
 179
 180 void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
 181                                       QuicPacketCount min_nacks) {
 182   DCHECK_GE(sequence_number, least_unacked_);
 183   DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
 184   unacked_packets_[sequence_number - least_unacked_].nack_count =
 185       max(min_nacks,
 186           unacked_packets_[sequence_number - least_unacked_].nack_count);
 187 }
 188
 189 void QuicUnackedPacketMap::RemoveRetransmittability(
 190     QuicPacketSequenceNumber sequence_number) {
 191   DCHECK_GE(sequence_number, least_unacked_);
 192   DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
 193   TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
 194   SequenceNumberList* all_transmissions = info->all_transmissions;
 195   if (all_transmissions == nullptr) {
 196     MaybeRemoveRetransmittableFrames(info);
 197     return;
 198   }
 199   // TODO(ianswett): Consider adding a check to ensure there are retransmittable
 200   // frames associated with this packet.
 201   for (QuicPacketSequenceNumber sequence_number : *all_transmissions) {
 202     TransmissionInfo* transmission_info =
 203         &unacked_packets_[sequence_number - least_unacked_];
 204     MaybeRemoveRetransmittableFrames(transmission_info);
 205     transmission_info->all_transmissions = nullptr;
 206   }
 207   delete all_transmissions;
 208 }
 209
 210 void QuicUnackedPacketMap::RemoveAckability(TransmissionInfo* info) {
 211   DCHECK(info->retransmittable_frames == nullptr);
 212   info->is_unackable = true;
 213   SequenceNumberList* all_transmissions = info->all_transmissions;
 214   if (all_transmissions == nullptr) {
 215     return;
 216   }
 217   for (QuicPacketSequenceNumber sequence_number : *all_transmissions) {
 218     TransmissionInfo* transmission_info =
 219         &unacked_packets_[sequence_number - least_unacked_];
 220     transmission_info->all_transmissions = nullptr;
 221     transmission_info->is_unackable = true;
 222   }
 223   delete all_transmissions;
 224 }
 225
 226 void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
 227     TransmissionInfo* transmission_info) {
 228   if (transmission_info->retransmittable_frames != nullptr) {
 229     if (transmission_info->retransmittable_frames->HasCryptoHandshake()
 230             == IS_HANDSHAKE) {
 231       --pending_crypto_packet_count_;
 232     }
 233     delete transmission_info->retransmittable_frames;
 234     transmission_info->retransmittable_frames = nullptr;
 235   }
 236 }
 237
 238 void QuicUnackedPacketMap::IncreaseLargestObserved(
 239     QuicPacketSequenceNumber largest_observed) {
 240   DCHECK_LE(largest_observed_, largest_observed);
 241   largest_observed_ = largest_observed;
 242 }
 243
 244 bool QuicUnackedPacketMap::IsPacketUsefulForMeasuringRtt(
 245     QuicPacketSequenceNumber sequence_number,
 246     const TransmissionInfo& info) const {
 247   // Packet can be used for RTT measurement if it may yet be acked as the
 248   // largest observed packet by the receiver.
 249   return !info.is_unackable && sequence_number > largest_observed_;
 250 }
 251
 252 bool QuicUnackedPacketMap::IsPacketUsefulForCongestionControl(
 253     const TransmissionInfo& info) const {
 254   // Packet contributes to congestion control if it is considered inflight.
 255   return info.in_flight;
 256 }
 257
 258 bool QuicUnackedPacketMap::IsPacketUsefulForRetransmittableData(
 259     const TransmissionInfo& info) const {
 260   // Packet may have retransmittable frames, or the data may have been
 261   // retransmitted with a new sequence number.
 262   return info.retransmittable_frames != nullptr ||
 263          info.all_transmissions != nullptr;
 264 }
 265
 266 bool QuicUnackedPacketMap::IsPacketUseless(
 267     QuicPacketSequenceNumber sequence_number,
 268     const TransmissionInfo& info) const {
 269   return !IsPacketUsefulForMeasuringRtt(sequence_number, info) &&
 270          !IsPacketUsefulForCongestionControl(info) &&
 271          !IsPacketUsefulForRetransmittableData(info);
 272 }
 273
 274 bool QuicUnackedPacketMap::IsUnacked(
 275     QuicPacketSequenceNumber sequence_number) const {
 276   if (sequence_number < least_unacked_ ||
 277       sequence_number >= least_unacked_ + unacked_packets_.size()) {
 278     return false;
 279   }
 280   return !IsPacketUseless(sequence_number,
 281                           unacked_packets_[sequence_number - least_unacked_]);
 282 }
 283
 284 void QuicUnackedPacketMap::RemoveFromInFlight(
 285     QuicPacketSequenceNumber sequence_number) {
 286   DCHECK_GE(sequence_number, least_unacked_);
 287   DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
 288   TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
 289   if (info->in_flight) {
 290     LOG_IF(DFATAL, bytes_in_flight_ < info->bytes_sent);
 291     bytes_in_flight_ -= info->bytes_sent;
 292     info->in_flight = false;
 293   }
 294 }
 295
 296 void QuicUnackedPacketMap::CancelRetransmissionsForStream(
 297     QuicStreamId stream_id) {
 298   QuicPacketSequenceNumber sequence_number = least_unacked_;
 299   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 300        it != unacked_packets_.end(); ++it, ++sequence_number) {
 301     RetransmittableFrames* retransmittable_frames = it->retransmittable_frames;
 302     if (!retransmittable_frames) {
 303       continue;
 304     }
 305     retransmittable_frames->RemoveFramesForStream(stream_id);
 306     if (retransmittable_frames->frames().empty()) {
 307       RemoveRetransmittability(sequence_number);
 308     }
 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 size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const {
 340   size_t unacked_packet_count = 0;
 341   QuicPacketSequenceNumber sequence_number = least_unacked_;
 342   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 343        it != unacked_packets_.end(); ++it, ++sequence_number) {
 344     if (!IsPacketUseless(sequence_number, *it)) {
 345       ++unacked_packet_count;
 346     }
 347   }
 348   return unacked_packet_count;
 349 }
 350
 351 bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
 352   size_t num_in_flight = 0;
 353   for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
 354        it != unacked_packets_.rend(); ++it) {
 355     if (it->in_flight) {
 356       ++num_in_flight;
 357     }
 358     if (num_in_flight > 1) {
 359       return true;
 360     }
 361   }
 362   return false;
 363 }
 364
 365 bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
 366   return pending_crypto_packet_count_ > 0;
 367 }
 368
 369 bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
 370   for (UnackedPacketMap::const_reverse_iterator it =
 371            unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
 372     if (it->in_flight && it->retransmittable_frames) {
 373       return true;
 374     }
 375   }
 376   return false;
 377 }
 378
 379 QuicPacketSequenceNumber QuicUnackedPacketMap::GetLeastUnacked() const {
 380   return least_unacked_;
 381 }
 382
 383 void QuicUnackedPacketMap::PopLeastUnacked() {
 384   ack_notifier_manager_->OnPacketRemoved(least_unacked_);
 385
 386   unacked_packets_.pop_front();
 387   ++least_unacked_;
 388 }
 389
 390 }  // namespace net