net/quic/quic_sent_packet_manager.cc

   1 // Copyright 2013 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_sent_packet_manager.h"
   6
   7 #include "base/logging.h"
   8 #include "base/stl_util.h"
   9 #include "net/quic/quic_ack_notifier_manager.h"
  10
  11 using std::make_pair;
  12
  13 // TODO(rtenneti): Remove this.
  14 // Do not flip this flag until the flakiness of the
  15 // net/tools/quic/end_to_end_test is fixed.
  16 // If true, then QUIC connections will track the retransmission history of a
  17 // packet so that an ack of a previous transmission will ack the data of all
  18 // other transmissions.
  19 bool FLAGS_track_retransmission_history = false;
  20
  21 namespace net {
  22
  23 #define ENDPOINT (is_server_ ? "Server: " : " Client: ")
  24
  25 QuicSentPacketManager::HelperInterface::~HelperInterface() {
  26 }
  27
  28 QuicSentPacketManager::QuicSentPacketManager(bool is_server,
  29                                              HelperInterface* helper)
  30     : is_server_(is_server),
  31       helper_(helper) {
  32 }
  33
  34 QuicSentPacketManager::~QuicSentPacketManager() {
  35   for (UnackedPacketMap::iterator it = unacked_packets_.begin();
  36        it != unacked_packets_.end(); ++it) {
  37     delete it->second.retransmittable_frames;
  38   }
  39   while (!previous_transmissions_map_.empty()) {
  40     SequenceNumberSet* previous_transmissions =
  41         previous_transmissions_map_.begin()->second;
  42     for (SequenceNumberSet::const_iterator it = previous_transmissions->begin();
  43          it != previous_transmissions->end(); ++it) {
  44       DCHECK(ContainsKey(previous_transmissions_map_, *it));
  45       previous_transmissions_map_.erase(*it);
  46     }
  47     delete previous_transmissions;
  48   }
  49 }
  50
  51 void QuicSentPacketManager::OnSerializedPacket(
  52     const SerializedPacket& serialized_packet, QuicTime serialized_time) {
  53   if (serialized_packet.packet->is_fec_packet()) {
  54     DCHECK(!serialized_packet.retransmittable_frames);
  55     unacked_fec_packets_.insert(make_pair(
  56         serialized_packet.sequence_number, serialized_time));
  57     return;
  58   }
  59
  60   if (serialized_packet.retransmittable_frames == NULL) {
  61     // Don't track ack/congestion feedback packets.
  62     return;
  63   }
  64
  65   ack_notifier_manager_.OnSerializedPacket(serialized_packet);
  66
  67   DCHECK(unacked_packets_.empty() ||
  68          unacked_packets_.rbegin()->first < serialized_packet.sequence_number);
  69   unacked_packets_[serialized_packet.sequence_number] =
  70       TransmissionInfo(serialized_packet.retransmittable_frames,
  71                        serialized_packet.sequence_number_length);
  72 }
  73
  74 void QuicSentPacketManager::OnRetransmittedPacket(
  75     QuicPacketSequenceNumber old_sequence_number,
  76     QuicPacketSequenceNumber new_sequence_number) {
  77   DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
  78   DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
  79   DCHECK(unacked_packets_.empty() ||
  80          unacked_packets_.rbegin()->first < new_sequence_number);
  81
  82   pending_retransmissions_.erase(old_sequence_number);
  83
  84   RetransmittableFrames* frames =
  85       unacked_packets_[old_sequence_number].retransmittable_frames;
  86   DCHECK(frames);
  87
  88   // A notifier may be waiting to hear about ACKs for the original sequence
  89   // number. Inform them that the sequence number has changed.
  90   ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
  91                                              new_sequence_number);
  92
  93   // We keep the old packet in the unacked packet list until it, or one of
  94   // the retransmissions of it are acked.
  95   unacked_packets_[old_sequence_number].retransmittable_frames = NULL;
  96   unacked_packets_[new_sequence_number] =
  97       TransmissionInfo(frames, GetSequenceNumberLength(old_sequence_number));
  98
  99   // Keep track of all sequence numbers that this packet
 100   // has been transmitted as.
 101   SequenceNumberSet* previous_transmissions;
 102   PreviousTransmissionMap::iterator it =
 103       previous_transmissions_map_.find(old_sequence_number);
 104   if (it == previous_transmissions_map_.end()) {
 105     // This is the first retransmission of this packet, so create a new entry.
 106     previous_transmissions = new SequenceNumberSet;
 107     previous_transmissions_map_[old_sequence_number] = previous_transmissions;
 108     previous_transmissions->insert(old_sequence_number);
 109   } else {
 110     // Otherwise, use the existing entry.
 111     previous_transmissions = it->second;
 112   }
 113   previous_transmissions->insert(new_sequence_number);
 114   previous_transmissions_map_[new_sequence_number] = previous_transmissions;
 115
 116   DCHECK(HasRetransmittableFrames(new_sequence_number));
 117 }
 118
 119 void QuicSentPacketManager::OnIncomingAck(
 120     const ReceivedPacketInfo& received_info,
 121     bool is_truncated_ack) {
 122   HandleAckForSentPackets(received_info, is_truncated_ack);
 123   HandleAckForSentFecPackets(received_info);
 124 }
 125
 126 void QuicSentPacketManager::DiscardUnackedPacket(
 127     QuicPacketSequenceNumber sequence_number) {
 128   MarkPacketReceivedByPeer(sequence_number);
 129 }
 130
 131 void QuicSentPacketManager::HandleAckForSentPackets(
 132     const ReceivedPacketInfo& received_info,
 133     bool is_truncated_ack) {
 134   // Go through the packets we have not received an ack for and see if this
 135   // incoming_ack shows they've been seen by the peer.
 136   UnackedPacketMap::iterator it = unacked_packets_.begin();
 137   while (it != unacked_packets_.end()) {
 138     QuicPacketSequenceNumber sequence_number = it->first;
 139     if (sequence_number > received_info.largest_observed) {
 140       // These are very new sequence_numbers.
 141       break;
 142     }
 143
 144     if (IsAwaitingPacket(received_info, sequence_number)) {
 145       ++it;
 146       continue;
 147     }
 148
 149     // Packet was acked, so remove it from our unacked packet list.
 150     DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
 151     // If data is associated with the most recent transmission of this
 152     // packet, then inform the caller.
 153     it = MarkPacketReceivedByPeer(sequence_number);
 154
 155     // The AckNotifierManager is informed of every ACKed sequence number.
 156     ack_notifier_manager_.OnPacketAcked(sequence_number);
 157   }
 158
 159   // If we have received a trunacted ack, then we need to
 160   // clear out some previous transmissions to allow the peer
 161   // to actually ACK new packets.
 162   if (is_truncated_ack) {
 163     size_t num_to_clear = received_info.missing_packets.size() / 2;
 164     UnackedPacketMap::iterator it = unacked_packets_.begin();
 165     while (it != unacked_packets_.end() && num_to_clear > 0) {
 166       QuicPacketSequenceNumber sequence_number = it->first;
 167       ++it;
 168       // If this is not a previous transmission then there is no point
 169       // in clearing out any further packets, because it will not
 170       // affect the high water mark.
 171       if (!IsPreviousTransmission(sequence_number)) {
 172         break;
 173       }
 174
 175       DCHECK(ContainsKey(previous_transmissions_map_, sequence_number));
 176       DCHECK(!HasRetransmittableFrames(sequence_number));
 177       unacked_packets_.erase(sequence_number);
 178       SequenceNumberSet* previous_transmissions =
 179           previous_transmissions_map_[sequence_number];
 180       previous_transmissions_map_.erase(sequence_number);
 181       previous_transmissions->erase(sequence_number);
 182       if (previous_transmissions->size() == 1) {
 183         previous_transmissions_map_.erase(*previous_transmissions->begin());
 184         delete previous_transmissions;
 185       }
 186       --num_to_clear;
 187     }
 188   }
 189 }
 190
 191 bool QuicSentPacketManager::HasRetransmittableFrames(
 192     QuicPacketSequenceNumber sequence_number) const {
 193   if (!ContainsKey(unacked_packets_, sequence_number)) {
 194     return false;
 195   }
 196
 197   return unacked_packets_.find(
 198       sequence_number)->second.retransmittable_frames != NULL;
 199 }
 200
 201 bool QuicSentPacketManager::MarkForRetransmission(
 202     QuicPacketSequenceNumber sequence_number,
 203     TransmissionType transmission_type) {
 204   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 205   if (!HasRetransmittableFrames(sequence_number)) {
 206     return false;
 207   }
 208   // If it's already in the retransmission map, don't add it again, just let
 209   // the prior retransmission request win out.
 210   if (ContainsKey(pending_retransmissions_, sequence_number)) {
 211     return true;
 212   }
 213
 214   pending_retransmissions_[sequence_number] = transmission_type;
 215   return true;
 216 }
 217
 218 bool QuicSentPacketManager::HasPendingRetransmissions() const {
 219   return !pending_retransmissions_.empty();
 220 }
 221
 222 QuicSentPacketManager::PendingRetransmission
 223     QuicSentPacketManager::NextPendingRetransmission() {
 224   DCHECK(!pending_retransmissions_.empty());
 225   QuicPacketSequenceNumber sequence_number =
 226       pending_retransmissions_.begin()->first;
 227   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 228   DCHECK(unacked_packets_[sequence_number].retransmittable_frames);
 229
 230   return PendingRetransmission(sequence_number,
 231                                pending_retransmissions_.begin()->second,
 232                                GetRetransmittableFrames(sequence_number),
 233                                GetSequenceNumberLength(sequence_number));
 234 }
 235
 236 bool QuicSentPacketManager::IsPreviousTransmission(
 237     QuicPacketSequenceNumber sequence_number) const {
 238   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 239
 240   PreviousTransmissionMap::const_iterator it =
 241       previous_transmissions_map_.find(sequence_number);
 242   if (it == previous_transmissions_map_.end()) {
 243     return false;
 244   }
 245
 246   SequenceNumberSet* previous_transmissions = it->second;
 247   DCHECK(!previous_transmissions->empty());
 248   return *previous_transmissions->rbegin() != sequence_number;
 249 }
 250
 251 QuicPacketSequenceNumber QuicSentPacketManager::GetMostRecentTransmission(
 252     QuicPacketSequenceNumber sequence_number) const {
 253   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 254
 255   PreviousTransmissionMap::const_iterator it =
 256       previous_transmissions_map_.find(sequence_number);
 257   if (it == previous_transmissions_map_.end()) {
 258     return sequence_number;
 259   }
 260
 261   SequenceNumberSet* previous_transmissions =
 262       previous_transmissions_map_.find(sequence_number)->second;
 263   DCHECK(!previous_transmissions->empty());
 264   return *previous_transmissions->rbegin();
 265 }
 266
 267 QuicSentPacketManager::UnackedPacketMap::iterator
 268 QuicSentPacketManager::MarkPacketReceivedByPeer(
 269     QuicPacketSequenceNumber sequence_number) {
 270   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 271   UnackedPacketMap::iterator next_unacked =
 272       unacked_packets_.find(sequence_number);
 273   ++next_unacked;
 274
 275   // If this packet has never been retransmitted, then simply drop it.
 276   if (!ContainsKey(previous_transmissions_map_, sequence_number)) {
 277     DiscardPacket(sequence_number);
 278     return next_unacked;
 279   }
 280
 281   SequenceNumberSet* previous_transmissions =
 282     previous_transmissions_map_.find(sequence_number)->second;
 283   SequenceNumberSet::reverse_iterator previous_transmissions_it
 284       = previous_transmissions->rbegin();
 285   DCHECK(previous_transmissions_it != previous_transmissions->rend());
 286
 287   QuicPacketSequenceNumber new_packet = *previous_transmissions_it;
 288   bool is_new_packet = new_packet == sequence_number;
 289   if (is_new_packet) {
 290     DiscardPacket(new_packet);
 291   } else {
 292     if (next_unacked->first == new_packet) {
 293       ++next_unacked;
 294     }
 295     // If we have received an ack for a previous transmission of a packet,
 296     // we want to keep the "new" transmission of the packet unacked,
 297     // but prevent the data from being retransmitted.
 298     delete unacked_packets_[new_packet].retransmittable_frames;
 299     unacked_packets_[new_packet].retransmittable_frames = NULL;
 300     pending_retransmissions_.erase(new_packet);
 301   }
 302   previous_transmissions_map_.erase(new_packet);
 303
 304   // Clear out information all previous transmissions.
 305   ++previous_transmissions_it;
 306   while (previous_transmissions_it != previous_transmissions->rend()) {
 307     QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it;
 308     ++previous_transmissions_it;
 309     DCHECK(ContainsKey(previous_transmissions_map_, previous_transmission));
 310     previous_transmissions_map_.erase(previous_transmission);
 311     if (next_unacked != unacked_packets_.end() &&
 312         next_unacked->first == previous_transmission) {
 313       ++next_unacked;
 314     }
 315     DiscardPacket(previous_transmission);
 316   }
 317
 318   delete previous_transmissions;
 319
 320   next_unacked = unacked_packets_.begin();
 321   while (next_unacked != unacked_packets_.end() &&
 322          next_unacked->first < sequence_number) {
 323         ++next_unacked;
 324       }
 325   return next_unacked;
 326 }
 327
 328 void QuicSentPacketManager::DiscardPacket(
 329     QuicPacketSequenceNumber sequence_number) {
 330   UnackedPacketMap::iterator unacked_it =
 331       unacked_packets_.find(sequence_number);
 332   // Packet was not meant to be retransmitted.
 333   if (unacked_it == unacked_packets_.end()) {
 334     return;
 335   }
 336
 337   // Delete the retransmittable frames.
 338   delete unacked_it->second.retransmittable_frames;
 339   unacked_packets_.erase(unacked_it);
 340   pending_retransmissions_.erase(sequence_number);
 341   return;
 342 }
 343
 344 void QuicSentPacketManager::HandleAckForSentFecPackets(
 345     const ReceivedPacketInfo& received_info) {
 346   UnackedFecPacketMap::iterator it = unacked_fec_packets_.begin();
 347   while (it != unacked_fec_packets_.end()) {
 348     QuicPacketSequenceNumber sequence_number = it->first;
 349     if (sequence_number > received_info.largest_observed) {
 350       break;
 351     }
 352
 353     if (!IsAwaitingPacket(received_info, sequence_number)) {
 354       DVLOG(1) << ENDPOINT << "Got an ack for fec packet: " << sequence_number;
 355       unacked_fec_packets_.erase(it++);
 356     } else {
 357       // TODO(rch): treat these packets more consistently.  They should
 358       // be subject to NACK and RTO based loss.  (Thought obviously, they
 359       // should not be retransmitted.)
 360       DVLOG(1) << ENDPOINT << "Still missing ack for fec packet: "
 361                << sequence_number;
 362       ++it;
 363     }
 364   }
 365 }
 366
 367 void QuicSentPacketManager::DiscardFecPacket(
 368     QuicPacketSequenceNumber sequence_number) {
 369   DCHECK(ContainsKey(unacked_fec_packets_, sequence_number));
 370   unacked_fec_packets_.erase(sequence_number);
 371 }
 372
 373 bool QuicSentPacketManager::IsRetransmission(
 374     QuicPacketSequenceNumber sequence_number) const {
 375   DCHECK(HasRetransmittableFrames(sequence_number));
 376   return HasRetransmittableFrames(sequence_number) &&
 377       ContainsKey(previous_transmissions_map_, sequence_number);
 378 }
 379
 380 bool QuicSentPacketManager::IsUnacked(
 381     QuicPacketSequenceNumber sequence_number) const {
 382   return ContainsKey(unacked_packets_, sequence_number);
 383 }
 384
 385 bool QuicSentPacketManager::IsFecUnacked(
 386     QuicPacketSequenceNumber sequence_number) const {
 387   return ContainsKey(unacked_fec_packets_, sequence_number);
 388 }
 389
 390 const RetransmittableFrames& QuicSentPacketManager::GetRetransmittableFrames(
 391     QuicPacketSequenceNumber sequence_number) const {
 392   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 393
 394   return *unacked_packets_.find(sequence_number)->second.retransmittable_frames;
 395 }
 396
 397 QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength(
 398     QuicPacketSequenceNumber sequence_number) const {
 399   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 400
 401   return unacked_packets_.find(sequence_number)->second.sequence_number_length;
 402 }
 403
 404 QuicTime QuicSentPacketManager::GetFecSentTime(
 405     QuicPacketSequenceNumber sequence_number) const {
 406   DCHECK(ContainsKey(unacked_fec_packets_, sequence_number));
 407
 408   return unacked_fec_packets_.find(sequence_number)->second;
 409 }
 410
 411 bool QuicSentPacketManager::HasUnackedPackets() const {
 412   return !unacked_packets_.empty();
 413 }
 414
 415 size_t QuicSentPacketManager::GetNumRetransmittablePackets() const {
 416   size_t num_unacked_packets = 0;
 417   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 418        it != unacked_packets_.end(); ++it) {
 419     QuicPacketSequenceNumber sequence_number = it->first;
 420     if (HasRetransmittableFrames(sequence_number)) {
 421       ++num_unacked_packets;
 422     }
 423   }
 424   return num_unacked_packets;
 425 }
 426
 427 bool QuicSentPacketManager::HasUnackedFecPackets() const {
 428   return !unacked_fec_packets_.empty();
 429 }
 430
 431 QuicPacketSequenceNumber
 432 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
 433   if (unacked_packets_.empty()) {
 434     // If there are no unacked packets, set the least unacked packet to
 435     // the sequence number of the next packet sent.
 436     return helper_->GetNextPacketSequenceNumber();
 437   }
 438
 439   return unacked_packets_.begin()->first;
 440 }
 441
 442 QuicPacketSequenceNumber
 443 QuicSentPacketManager::GetLeastUnackedFecPacket() const {
 444   if (unacked_fec_packets_.empty()) {
 445     // If there are no unacked packets, set the least unacked packet to
 446     // the sequence number of the next packet sent.
 447     return helper_->GetNextPacketSequenceNumber();
 448   }
 449
 450   return unacked_fec_packets_.begin()->first;
 451 }
 452
 453 SequenceNumberSet QuicSentPacketManager::GetUnackedPackets() const {
 454   SequenceNumberSet unacked_packets;
 455   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 456        it != unacked_packets_.end(); ++it) {
 457     unacked_packets.insert(it->first);
 458   }
 459   return unacked_packets;
 460 }
 461
 462 }  // namespace net