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