Revert 171096

net/quic/quic_connection.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/quic_connection.h"
 
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/stl_util.h"
 #include "net/base/net_errors.h"
 #include "net/quic/congestion_control/quic_receipt_metrics_collector.h"
 #include "net/quic/congestion_control/quic_send_scheduler.h"
 #include "net/quic/quic_utils.h"
 
 using base::hash_map;
 using base::hash_set;
 using base::StringPiece;
 using std::list;
 using std::min;
 using std::vector;
 using std::set;
 
 namespace net {
 
 // An arbitrary number we'll probably want to tune.
-const QuicPacketSequenceNumber kMaxAckedPackets = 5000u;
+const QuicPacketSequenceNumber kMaxUnackedPackets = 5000u;
 
 // The amount of time we wait before resending a packet.
 const int64 kDefaultResendTimeMs = 500;
 
 bool Near(QuicPacketSequenceNumber a, QuicPacketSequenceNumber b) {
   QuicPacketSequenceNumber delta = (a > b) ? a - b : b - a;
-  return delta <= kMaxAckedPackets;
+  return delta <= kMaxUnackedPackets;
 }
 
 QuicConnection::QuicConnection(QuicGuid guid,
                                IPEndPoint address,
                                QuicConnectionHelperInterface* helper)
     : helper_(helper),
       framer_(QuicDecrypter::Create(kNULL), QuicEncrypter::Create(kNULL)),
       clock_(helper->GetClock()),
       guid_(guid),
       peer_address_(address),
@@ skipping 53 matching lines @@
 bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) {
   if (!Near(header.packet_sequence_number,
             last_header_.packet_sequence_number)) {
     DLOG(INFO) << "Packet out of bounds.  Discarding";
     return false;
   }
 
   ReceivedPacketInfo info = outgoing_ack_.received_info;
   // If this packet has already been seen, or that the sender
   // has told us will not be resent, then stop processing the packet.
-  if (info.ContainsAck(header.packet_sequence_number)) {
+  if (header.packet_sequence_number <= info.largest_received &&
+      info.missing_packets.count(header.packet_sequence_number) != 1) {
     return false;
   }
 
   last_header_ = header;
   return true;
 }
 
 void QuicConnection::OnFecProtectedPayload(StringPiece payload) {
   DCHECK_NE(0, last_header_.fec_group);
   QuicFecGroup* group = GetFecGroup();
@@ skipping 41 matching lines @@
 bool QuicConnection::ValidateAckFrame(const QuicAckFrame& incoming_ack) {
   if (incoming_ack.received_info.largest_received >
       packet_creator_.sequence_number()) {
     DLOG(ERROR) << "Client acked unsent packet:"
                 << incoming_ack.received_info.largest_received << " vs "
                 << packet_creator_.sequence_number();
     // We got an error for data we have not sent.  Error out.
     return false;
   }
 
-  // We can't have too many acked packets, or our ack frames go over
-  // kMaxPacketSize.
-  DCHECK_LT(incoming_ack.received_info.received_packet_times.size(),
-            kMaxAckedPackets);
+  // We can't have too many missing or retransmitting packets, or our ack
+  // frames go over kMaxPacketSize.
+  DCHECK_LT(incoming_ack.received_info.missing_packets.size(),
+            kMaxUnackedPackets);
+  DCHECK_LT(incoming_ack.sent_info.non_retransmiting.size(),
+            kMaxUnackedPackets);
 
   if (incoming_ack.sent_info.least_unacked != 0 &&
       incoming_ack.sent_info.least_unacked < least_packet_awaiting_ack_) {
     DLOG(INFO) << "Client sent low least_unacked";
     // We never process old ack frames, so this number should only increase.
     return false;
   }
 
   return true;
 }
 
 void QuicConnection::UpdatePacketInformationReceivedByPeer(
     const QuicAckFrame& incoming_ack) {
   QuicConnectionVisitorInterface::AckedPackets acked_packets;
 
   // Initialize the lowest unacked packet to the lower of the next outgoing
   // sequence number and the largest received packed in the incoming ack.
   QuicPacketSequenceNumber lowest_unacked = min(
       packet_creator_.sequence_number() + 1,
       incoming_ack.received_info.largest_received + 1);
 
   // Go through the packets we have not received an ack for and see if this
   // incoming_ack shows they've been seen by the peer.
   UnackedPacketMap::iterator it = unacked_packets_.begin();
   while (it != unacked_packets_.end()) {
-    if (incoming_ack.received_info.ContainsAck(it->first)) {
+    if ((it->first < incoming_ack.received_info.largest_received &&
+         !ContainsKey(incoming_ack.received_info.missing_packets, it->first)) ||
+        it->first == incoming_ack.received_info.largest_received) {
       // Packet was acked, so remove it from our unacked packet list.
       DVLOG(1) << "Got an ack for " << it->first;
       // TODO(rch): This is inefficient and should be sped up.
       // The acked packet might be queued (if a resend had been attempted).
       for (QueuedPacketList::iterator q = queued_packets_.begin();
            q != queued_packets_.end(); ++q) {
         if (q->sequence_number == it->first) {
           queued_packets_.erase(q);
           break;
         }
@@ skipping 14 matching lines @@
       ++it;
     }
   }
   if (acked_packets.size() > 0) {
     visitor_->OnAck(acked_packets);
   }
 
   // If we've gotten an ack for the lowest packet we were waiting on,
   // update that and the list of packets we advertise we will not resend.
   if (lowest_unacked > outgoing_ack_.sent_info.least_unacked) {
+    SequenceSet* non_retrans = &outgoing_ack_.sent_info.non_retransmiting;
+    // We don't need to advertise not-resending packets between the old
+    // and new values.
+    for (QuicPacketSequenceNumber i = outgoing_ack_.sent_info.least_unacked;
+         i < lowest_unacked; ++i) {
+      non_retrans->erase(i);
+    }
     // If all packets we sent have been acked, use the special value of 0
     if (lowest_unacked > packet_creator_.sequence_number()) {
       lowest_unacked = 0;
+      DCHECK_EQ(0u, non_retrans->size());
     }
     outgoing_ack_.sent_info.least_unacked = lowest_unacked;
   }
 }
 
 void QuicConnection::UpdatePacketInformationSentByPeer(
     const QuicAckFrame& incoming_ack) {
-  // Make sure we also don't ack any packets lower than the peer's
+  // Iteratate through the packets which will the peer will not resend and
+  // remove them from our missing list.
+  for (SequenceSet::const_iterator it =
+           incoming_ack.sent_info.non_retransmiting.begin();
+       it != incoming_ack.sent_info.non_retransmiting.end(); ++it) {
+    DVLOG(1) << "no longer expecting " << *it;
+    outgoing_ack_.received_info.missing_packets.erase(*it);
+  }
+
+  // Make sure we also don't expect any packets lower than the peer's
   // last-packet-awaiting-ack.
   if (incoming_ack.sent_info.least_unacked > least_packet_awaiting_ack_) {
-    outgoing_ack_.received_info.ClearAcksBefore(
-        incoming_ack.sent_info.least_unacked);
+    for (QuicPacketSequenceNumber i = least_packet_awaiting_ack_;
+         i < incoming_ack.sent_info.least_unacked; ++i) {
+      outgoing_ack_.received_info.missing_packets.erase(i);
+    }
     least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
   }
 
   // Possibly close any FecGroups which are now irrelevant
   CloseFecGroupsBefore(incoming_ack.sent_info.least_unacked + 1);
 }
 
 void QuicConnection::OnFecData(const QuicFecData& fec) {
   DCHECK_NE(0, last_header_.fec_group);
   QuicFecGroup* group = GetFecGroup();
@@ skipping 104 matching lines @@
     num_queued_packets = queued_packets_.size();
     QueuedPacket p = queued_packets_.front();
     queued_packets_.pop_front();
     SendPacket(p.sequence_number, p.packet, p.resend, false, p.retransmit);
   }
   return !write_blocked_;
 }
 
 void QuicConnection::AckPacket(const QuicPacketHeader& header) {
   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
-  outgoing_ack_.received_info.RecordAck(sequence_number, clock_->Now());
+  if (sequence_number > outgoing_ack_.received_info.largest_received) {
+    // We've got a new high sequence number.  Note any new intermediate missing
+    // packets, and update the last_ack data.
+    for (QuicPacketSequenceNumber i =
+             outgoing_ack_.received_info.largest_received + 1;
+         i < sequence_number; ++i) {
+      DVLOG(1) << "missing " << i;
+      outgoing_ack_.received_info.missing_packets.insert(i);
+    }
+    outgoing_ack_.received_info.largest_received = sequence_number;
+    outgoing_ack_.received_info.time_received = clock_->Now();
+  } else {
+    // We've gotten one of the out of order packets - remove it from our
+    // "missing packets" list.
+    DVLOG(1) << "Removing "  << sequence_number << " from missing list";
+    outgoing_ack_.received_info.missing_packets.erase(sequence_number);
+  }
   // TODO(alyssar) delay sending until we have data, or enough time has elapsed.
   if (frames_.size() > 0) {
     SendAck();
   }
 }
 
 void QuicConnection::MaybeResendPacket(
     QuicPacketSequenceNumber sequence_number) {
   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 
@@ skipping 40 matching lines @@
     }
   }
   if (should_resend) {
     helper_->SetResendAlarm(sequence_number, DefaultResendTime());
     // The second case should never happen in the real world, but does here
     // because we sometimes send out of order to validate corner cases.
     if (outgoing_ack_.sent_info.least_unacked == 0 ||
         sequence_number < outgoing_ack_.sent_info.least_unacked) {
       outgoing_ack_.sent_info.least_unacked = sequence_number;
     }
+  } else {
+    if (outgoing_ack_.sent_info.least_unacked != 0 &&
+        sequence_number > outgoing_ack_.sent_info.least_unacked) {
+      outgoing_ack_.sent_info.non_retransmiting.insert(sequence_number);
+    }
   }
 
   scoped_ptr<QuicEncryptedPacket> encrypted(framer_.EncryptPacket(*packet));
   int error;
   DLOG(INFO) << "Sending packet : "
              << (should_resend ? "data bearing " : " ack only ")
              << "packet " << sequence_number;
   int rv = helper_->WritePacketToWire(*encrypted, &error);
   if (rv == -1) {
     if (error == ERR_IO_PENDING) {
@@ skipping 109 matching lines @@
            << " delta:" << delta.ToMicroseconds();
   if (delta >= timeout_) {
     SendConnectionClose(QUIC_CONNECTION_TIMED_OUT);
     return true;
   }
   helper_->SetTimeoutAlarm(timeout_.Subtract(delta));
   return false;
 }
 
 }  // namespace net