Update from https://crrev.com/306655

net/quic/congestion_control/send_algorithm_simulator.cc

 // Copyright 2014 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/congestion_control/send_algorithm_simulator.h"
 
 #include <limits>
 
 #include "base/logging.h"
 #include "base/rand_util.h"
 #include "net/quic/crypto/quic_random.h"
 
 using std::list;
 using std::make_pair;
 using std::max;
 using std::min;
 using std::vector;
 
 namespace net {
 
 namespace {
 
 const QuicByteCount kPacketSize = 1200;
 
 }  // namespace
 
 SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
                                        RttStats* rtt_stats)
+    : Sender(send_algorithm, rtt_stats, QuicTime::Delta::Zero()) {}
+
+SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
+                                       RttStats* rtt_stats,
+                                       QuicTime::Delta additional_rtt)
     : send_algorithm(send_algorithm),
       rtt_stats(rtt_stats),
+      additional_rtt(additional_rtt),
       last_sent(0),
       last_acked(0),
       next_acked(1),
       max_cwnd(0),
       min_cwnd(100000),
       max_cwnd_drop(0),
       last_cwnd(0),
       last_transfer_bandwidth(QuicBandwidth::Zero()),
       last_transfer_loss_rate(0) {}
 
+SendAlgorithmSimulator::Transfer::Transfer(Sender* sender,
+                                           QuicByteCount num_bytes,
+                                           QuicTime start_time,
+                                           string name)
+    : sender(sender),
+      num_bytes(num_bytes),
+      bytes_acked(0),
+      bytes_lost(0),
+      bytes_in_flight(0),
+      start_time(start_time),
+      name(name) {}
+
 SendAlgorithmSimulator::SendAlgorithmSimulator(
     MockClock* clock,
     QuicBandwidth bandwidth,
     QuicTime::Delta rtt)
     : clock_(clock),
       lose_next_ack_(false),
       forward_loss_rate_(0),
       reverse_loss_rate_(0),
       loss_correlation_(0),
       bandwidth_(bandwidth),
       rtt_(rtt),
       buffer_size_(1000000),
       delayed_ack_timer_(QuicTime::Delta::FromMilliseconds(100)) {
   uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
   DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
   simple_random_.set_seed(seed);
 }
 
 SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
 
 void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) {
-  AddTransfer(sender, num_bytes, clock_->Now());
+  AddTransfer(sender, num_bytes, clock_->Now(),
+              StringPrintf("#%zu", pending_transfers_.size()));
 }
 
 void SendAlgorithmSimulator::AddTransfer(
-    Sender* sender, size_t num_bytes, QuicTime start_time) {
-  pending_transfers_.push_back(Transfer(sender, num_bytes, start_time));
+    Sender* sender, size_t num_bytes, QuicTime start_time, string name) {
+  pending_transfers_.push_back(Transfer(sender, num_bytes, start_time, name));
   // Record initial stats from when the transfer begins.
   pending_transfers_.back().sender->RecordStats();
 }
 
 void SendAlgorithmSimulator::TransferBytes() {
   TransferBytes(kuint64max, QuicTime::Delta::Infinite());
 }
 
 void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes,
                                            QuicTime::Delta max_time) {
@@ skipping 17 matching lines @@
       SendDataNow(&pending_transfers_.front());
     } else if (ack_event.time_delta < send_event.time_delta) {
       DVLOG(1) << "Handling ack of largest observed:"
                << ack_event.transfer->sender->next_acked << ", advancing time:"
                << ack_event.time_delta.ToMicroseconds() << "us";
       // Ack data all the data up to ack time and lose any missing sequence
       // numbers.
       clock_->AdvanceTime(ack_event.time_delta);
       HandlePendingAck(ack_event.transfer);
     } else {
-      DVLOG(1) << "Sending, advancing time:"
-               << send_event.time_delta.ToMicroseconds() << "us";
+      DVLOG(1) << "Sending transfer '" << send_event.transfer->name
+               << "', advancing time:" << send_event.time_delta.ToMicroseconds()
+               << "us";
       clock_->AdvanceTime(send_event.time_delta);
       SendDataNow(send_event.transfer);
       bytes_sent += kPacketSize;
     }
   }
 }
 
 SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextSendEvent() {
   QuicTime::Delta next_send_time = QuicTime::Delta::Infinite();
   Transfer* transfer = nullptr;
   for (vector<Transfer>::iterator it = pending_transfers_.begin();
        it != pending_transfers_.end(); ++it) {
     // If we've already sent enough bytes, wait for them to be acked.
     if (it->bytes_acked + it->bytes_in_flight >= it->num_bytes) {
       continue;
     }
     // If the flow hasn't started, use the start time.
     QuicTime::Delta transfer_send_time = it->start_time.Subtract(clock_->Now());
     if (clock_->Now() >= it->start_time) {
       transfer_send_time =
           it->sender->send_algorithm->TimeUntilSend(
               clock_->Now(), it->bytes_in_flight, HAS_RETRANSMITTABLE_DATA);
     }
     if (transfer_send_time < next_send_time) {
       next_send_time = transfer_send_time;
       transfer = &(*it);
     }
   }
   DVLOG(1) << "NextSendTime returning delta(ms):"
-           << next_send_time.ToMilliseconds();
+           << next_send_time.ToMilliseconds() << ", transfer '"
+           << transfer->name;
   return PacketEvent(next_send_time, transfer);
 }
 
 // NextAck takes into account packet loss in both forward and reverse
 // direction, as well as correlated losses.  And it assumes the receiver acks
 // every other packet when there is no loss.
 SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextAckEvent() {
   if (sent_packets_.empty()) {
     DVLOG(1) << "No outstanding packets to ack for any transfer.";
     return PacketEvent(QuicTime::Delta::Infinite(), nullptr);
@@ skipping 59 matching lines @@
     }
     *next_acked = it->sequence_number;
     ack_delay = it->ack_time.Subtract(clock_->Now());
     if (HasRecentLostPackets(transfer, *next_acked) ||
         (*next_acked - last_acked) >= 2) {
       break;
     }
     ack_delay = ack_delay.Add(delayed_ack_timer_);
   }
 
-  DVLOG(1) << "FindNextAcked found next_acked_:"
-           << transfer->sender->next_acked
+  DVLOG(1) << "FindNextAck found next_acked_:" << transfer->sender->next_acked
            << " last_acked:" << transfer->sender->last_acked
-           << " ack_delay(ms):" << ack_delay.ToMilliseconds();
+           << " ack_time(ms):" << ack_delay.ToMilliseconds();
   return ack_delay;
 }
 
 bool SendAlgorithmSimulator::HasRecentLostPackets(
     const Transfer* transfer, QuicPacketSequenceNumber next_acked) const {
   QuicPacketSequenceNumber last_packet = transfer->sender->last_acked;
   for (list<SentPacket>::const_iterator it = sent_packets_.begin();
        it != sent_packets_.end() && it->sequence_number < next_acked; ++it) {
     if (transfer != it->transfer) {
       continue;
@@ skipping 11 matching lines @@
   }
   return false;
 }
 
 void SendAlgorithmSimulator::HandlePendingAck(Transfer* transfer) {
   Sender* sender  = transfer->sender;
   DCHECK_LT(sender->last_acked, sender->next_acked);
   SendAlgorithmInterface::CongestionVector acked_packets;
   SendAlgorithmInterface::CongestionVector lost_packets;
   DVLOG(1) << "Acking packets from:" << sender->last_acked
-             << " to " << sender->next_acked
-             << " bytes_in_flight:" << transfer->bytes_in_flight
-             << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
+           << " to " << sender->next_acked
+           << " bytes_in_flight:" << transfer->bytes_in_flight
+           << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
   // Some entries may be missing from the sent_packets_ array, if they were
   // dropped due to buffer overruns.
   SentPacket largest_observed;
   list<SentPacket>::iterator it = sent_packets_.begin();
   while (sender->last_acked < sender->next_acked) {
     ++sender->last_acked;
     TransmissionInfo info = TransmissionInfo();
     info.bytes_sent = kPacketSize;
     info.in_flight = true;
     // Find the next SentPacket for this transfer.
@@ skipping 11 matching lines @@
     if (it->lost) {
       lost_packets.push_back(make_pair(sender->last_acked, info));
     } else {
       acked_packets.push_back(make_pair(sender->last_acked, info));
     }
     // This packet has been acked or lost, remove it from sent_packets_.
     largest_observed = *it;
     sent_packets_.erase(it++);
   }
 
-  DCHECK(largest_observed.ack_time.IsInitialized());
+  DCHECK(!largest_observed.lost);
   DVLOG(1) << "Updating RTT from send_time:"
            << largest_observed.send_time.ToDebuggingValue() << " to ack_time:"
            << largest_observed.ack_time.ToDebuggingValue();
   QuicTime::Delta measured_rtt =
       largest_observed.ack_time.Subtract(largest_observed.send_time);
   DCHECK_GE(measured_rtt.ToMicroseconds(), rtt_.ToMicroseconds());
   sender->rtt_stats->UpdateRtt(measured_rtt,
                                QuicTime::Delta::Zero(),
                                clock_->Now());
   sender->send_algorithm->OnCongestionEvent(
@@ skipping 24 matching lines @@
         break;
       }
     }
   }
 }
 
 void SendAlgorithmSimulator::SendDataNow(Transfer* transfer) {
   Sender* sender  = transfer->sender;
   ++sender->last_sent;
   DVLOG(1) << "Sending packet:" << sender->last_sent
+           << " name:" << transfer->name
            << " bytes_in_flight:" << transfer->bytes_in_flight
+           << " cwnd:" << sender->send_algorithm->GetCongestionWindow()
            << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
   sender->send_algorithm->OnPacketSent(
       clock_->Now(), transfer->bytes_in_flight,
       sender->last_sent, kPacketSize, HAS_RETRANSMITTABLE_DATA);
   // Lose the packet immediately if the buffer is full.
   if (sent_packets_.size() * kPacketSize < buffer_size_) {
     // TODO(ianswett): This buffer simulation is an approximation.
     // An ack time of zero means loss.
     bool packet_lost =
         forward_loss_rate_ * kuint64max > simple_random_.RandUint64();
     // Handle correlated loss.
     if (!sent_packets_.empty() && sent_packets_.back().lost &&
         loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
       packet_lost = true;
     }
     DVLOG(1) << "losing packet:" << sender->last_sent
-             << " due to random loss.";
+             << " name:" << transfer->name << " due to random loss.";
 
     // If the number of bytes in flight are less than the bdp, there's
     // no buffering delay.  Bytes lost from the buffer are not counted.
     QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
-    QuicTime ack_time = clock_->Now().Add(rtt_);
+    QuicTime ack_time = clock_->Now().Add(rtt_).Add(sender->additional_rtt);
     if (kPacketSize > bdp) {
       ack_time = ack_time.Add(bandwidth_.TransferTime(kPacketSize - bdp));
     }
     QuicTime queue_ack_time = sent_packets_.empty() ? QuicTime::Zero() :
         sent_packets_.back().ack_time.Add(bandwidth_.TransferTime(kPacketSize));
     ack_time = QuicTime::Max(ack_time, queue_ack_time);
     sent_packets_.push_back(SentPacket(
         sender->last_sent, clock_->Now(), ack_time, packet_lost, transfer));
   } else {
     DVLOG(1) << "losing packet:" << sender->last_sent
-             << " because the buffer was full.";
+             << " name:" << transfer->name << " because the buffer was full.";
   }
   transfer->bytes_in_flight += kPacketSize;
 }
 
 // Advance the time by |delta| without sending anything.
 void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
   clock_->AdvanceTime(delta);
 }
 
 }  // namespace net