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