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