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       bytes_in_flight_(0),
     20       pending_crypto_packet_count_(0) {
     21 }
     22 
     23 QuicUnackedPacketMap::~QuicUnackedPacketMap() {
     24   for (UnackedPacketMap::iterator it = unacked_packets_.begin();
     25        it != unacked_packets_.end(); ++it) {
     26     delete it->second.retransmittable_frames;
     27     // Only delete all_transmissions once, for the newest packet.
     28     if (it->first == *it->second.all_transmissions->rbegin()) {
     29       delete it->second.all_transmissions;
     30     }
     31   }
     32 }
     33 
     34 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
     35 // sent in order and the connection tracks RetransmittableFrames for longer.
     36 void QuicUnackedPacketMap::AddPacket(
     37     const SerializedPacket& serialized_packet) {
     38   if (!unacked_packets_.empty()) {
     39     bool is_old_packet = unacked_packets_.rbegin()->first >=
     40         serialized_packet.sequence_number;
     41     LOG_IF(DFATAL, is_old_packet) << "Old packet serialized: "
     42                                   << serialized_packet.sequence_number
     43                                   << " vs: "
     44                                   << unacked_packets_.rbegin()->first;
     45   }
     46 
     47   unacked_packets_[serialized_packet.sequence_number] =
     48       TransmissionInfo(serialized_packet.retransmittable_frames,
     49                        serialized_packet.sequence_number,
     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::OnRetransmittedPacket(
     59     QuicPacketSequenceNumber old_sequence_number,
     60     QuicPacketSequenceNumber new_sequence_number,
     61     TransmissionType transmission_type) {
     62   DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
     63   DCHECK(unacked_packets_.empty() ||
     64          unacked_packets_.rbegin()->first < new_sequence_number);
     65 
     66   // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
     67   TransmissionInfo* transmission_info =
     68       FindOrNull(unacked_packets_, old_sequence_number);
     69   RetransmittableFrames* frames = transmission_info->retransmittable_frames;
     70   LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no "
     71                                  << "retransmittable frames: "
     72                                  << old_sequence_number;
     73 
     74   // We keep the old packet in the unacked packet list until it, or one of
     75   // the retransmissions of it are acked.
     76   transmission_info->retransmittable_frames = NULL;
     77   unacked_packets_[new_sequence_number] =
     78       TransmissionInfo(frames,
     79                        new_sequence_number,
     80                        transmission_info->sequence_number_length,
     81                        transmission_type,
     82                        transmission_info->all_transmissions);
     83 }
     84 
     85 void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
     86   UnackedPacketMap::iterator it = unacked_packets_.begin();
     87   while (it != unacked_packets_.end() && num_to_clear > 0) {
     88     QuicPacketSequenceNumber sequence_number = it->first;
     89     // If this packet is in flight, or has retransmittable data, then there is
     90     // no point in clearing out any further packets, because they would not
     91     // affect the high water mark.
     92     if (it->second.in_flight || it->second.retransmittable_frames != NULL) {
     93       break;
     94     }
     95 
     96     it->second.all_transmissions->erase(sequence_number);
     97     LOG_IF(DFATAL, it->second.all_transmissions->empty())
     98         << "Previous retransmissions must have a newer transmission.";
     99     ++it;
    100     unacked_packets_.erase(sequence_number);
    101     --num_to_clear;
    102   }
    103 }
    104 
    105 bool QuicUnackedPacketMap::HasRetransmittableFrames(
    106     QuicPacketSequenceNumber sequence_number) const {
    107   const TransmissionInfo* transmission_info =
    108       FindOrNull(unacked_packets_, sequence_number);
    109   if (transmission_info == NULL) {
    110     return false;
    111   }
    112 
    113   return transmission_info->retransmittable_frames != NULL;
    114 }
    115 
    116 void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
    117                                       size_t min_nacks) {
    118   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
    119   if (it == unacked_packets_.end()) {
    120     LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
    121                 << sequence_number;
    122     return;
    123   }
    124 
    125   it->second.nack_count = max(min_nacks, it->second.nack_count);
    126 }
    127 
    128 void QuicUnackedPacketMap::RemoveRetransmittability(
    129     QuicPacketSequenceNumber sequence_number) {
    130   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
    131   if (it == unacked_packets_.end()) {
    132     DVLOG(1) << "packet is not in unacked_packets: " << sequence_number;
    133     return;
    134   }
    135   SequenceNumberSet* all_transmissions = it->second.all_transmissions;
    136   // TODO(ianswett): Consider optimizing this for lone packets.
    137   // TODO(ianswett): Consider adding a check to ensure there are retransmittable
    138   // frames associated with this packet.
    139   for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin();
    140        it != all_transmissions->rend(); ++it) {
    141     TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it);
    142     if (transmission_info == NULL) {
    143       LOG(DFATAL) << "All transmissions in all_transmissions must be present "
    144                   << "in the unacked packet map.";
    145       continue;
    146     }
    147     MaybeRemoveRetransmittableFrames(transmission_info);
    148     if (*it <= largest_observed_ && !transmission_info->in_flight) {
    149       unacked_packets_.erase(*it);
    150     } else {
    151       transmission_info->all_transmissions = new SequenceNumberSet();
    152       transmission_info->all_transmissions->insert(*it);
    153     }
    154   }
    155 
    156   delete all_transmissions;
    157 }
    158 
    159 void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
    160     TransmissionInfo* transmission_info) {
    161   if (transmission_info->retransmittable_frames != NULL) {
    162     if (transmission_info->retransmittable_frames->HasCryptoHandshake()
    163             == IS_HANDSHAKE) {
    164       --pending_crypto_packet_count_;
    165     }
    166     delete transmission_info->retransmittable_frames;
    167     transmission_info->retransmittable_frames = NULL;
    168   }
    169 }
    170 
    171 void QuicUnackedPacketMap::IncreaseLargestObserved(
    172     QuicPacketSequenceNumber largest_observed) {
    173   DCHECK_LT(largest_observed_, largest_observed);
    174   largest_observed_ = largest_observed;
    175   UnackedPacketMap::iterator it = unacked_packets_.begin();
    176   while (it != unacked_packets_.end() && it->first <= largest_observed_) {
    177     if (!IsPacketUseless(it)) {
    178       ++it;
    179       continue;
    180     }
    181     delete it->second.all_transmissions;
    182     QuicPacketSequenceNumber sequence_number = it->first;
    183     ++it;
    184     unacked_packets_.erase(sequence_number);
    185   }
    186 }
    187 
    188 bool QuicUnackedPacketMap::IsPacketUseless(
    189     UnackedPacketMap::const_iterator it) const {
    190   return it->first <= largest_observed_ &&
    191       !it->second.in_flight &&
    192       it->second.retransmittable_frames == NULL &&
    193       it->second.all_transmissions->size() == 1;
    194 }
    195 
    196 bool QuicUnackedPacketMap::IsUnacked(
    197     QuicPacketSequenceNumber sequence_number) const {
    198   return ContainsKey(unacked_packets_, sequence_number);
    199 }
    200 
    201 void QuicUnackedPacketMap::RemoveFromInFlight(
    202     QuicPacketSequenceNumber sequence_number) {
    203   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
    204   if (it == unacked_packets_.end()) {
    205     LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: "
    206                 << sequence_number;
    207     return;
    208   }
    209   if (it->second.in_flight) {
    210     LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
    211     bytes_in_flight_ -= it->second.bytes_sent;
    212     it->second.in_flight = false;
    213   }
    214   if (IsPacketUseless(it)) {
    215     delete it->second.all_transmissions;
    216     unacked_packets_.erase(it);
    217   }
    218 }
    219 
    220 bool QuicUnackedPacketMap::HasUnackedPackets() const {
    221   return !unacked_packets_.empty();
    222 }
    223 
    224 bool QuicUnackedPacketMap::HasInFlightPackets() const {
    225   return bytes_in_flight_ > 0;
    226 }
    227 
    228 const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
    229     QuicPacketSequenceNumber sequence_number) const {
    230   return unacked_packets_.find(sequence_number)->second;
    231 }
    232 
    233 QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
    234   UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
    235   while (it != unacked_packets_.rend()) {
    236     if (it->second.in_flight) {
    237       LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero())
    238           << "Sent time can never be zero for a packet in flight.";
    239       return it->second.sent_time;
    240     }
    241     ++it;
    242   }
    243   LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
    244   return QuicTime::Zero();
    245 }
    246 
    247 QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
    248   UnackedPacketMap::const_iterator it = unacked_packets_.begin();
    249   while (it != unacked_packets_.end() && !it->second.in_flight) {
    250     ++it;
    251   }
    252   if (it == unacked_packets_.end()) {
    253     LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
    254     return QuicTime::Zero();
    255   }
    256   return it->second.sent_time;
    257 }
    258 
    259 size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
    260   return unacked_packets_.size();
    261 }
    262 
    263 bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
    264   size_t num_in_flight = 0;
    265   for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
    266        it != unacked_packets_.rend(); ++it) {
    267     if (it->second.in_flight) {
    268       ++num_in_flight;
    269     }
    270     if (num_in_flight > 1) {
    271       return true;
    272     }
    273   }
    274   return false;
    275 }
    276 
    277 bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
    278   return pending_crypto_packet_count_ > 0;
    279 }
    280 
    281 bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
    282   for (UnackedPacketMap::const_reverse_iterator it =
    283            unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
    284     if (it->second.in_flight && it->second.retransmittable_frames) {
    285       return true;
    286     }
    287   }
    288   return false;
    289 }
    290 
    291 QuicPacketSequenceNumber
    292 QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
    293   if (unacked_packets_.empty()) {
    294     // If there are no unacked packets, return 0.
    295     return 0;
    296   }
    297 
    298   return unacked_packets_.begin()->first;
    299 }
    300 
    301 void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
    302                                    QuicTime sent_time,
    303                                    QuicByteCount bytes_sent,
    304                                    bool set_in_flight) {
    305   DCHECK_LT(0u, sequence_number);
    306   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
    307   if (it == unacked_packets_.end()) {
    308     LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
    309                 << sequence_number;
    310     return;
    311   }
    312   DCHECK(!it->second.in_flight);
    313 
    314   largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
    315   it->second.sent_time = sent_time;
    316   if (set_in_flight) {
    317     bytes_in_flight_ += bytes_sent;
    318     it->second.bytes_sent = bytes_sent;
    319     it->second.in_flight = true;
    320   }
    321 }
    322 
    323 }  // namespace net
    324