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