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