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