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