1// Copyright (c) 2012 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_connection.h"
6
7#include <algorithm>
8
9#include "base/logging.h"
10#include "base/stl_util.h"
11#include "net/quic/crypto/quic_decrypter.h"
12#include "net/quic/crypto/quic_encrypter.h"
13#include "net/quic/quic_utils.h"
14
15using base::hash_map;
16using base::hash_set;
17using base::StringPiece;
18using std::list;
19using std::make_pair;
20using std::min;
21using std::max;
22using std::vector;
23using std::set;
24using std::string;
25
26namespace net {
27namespace {
28
29// The largest gap in packets we'll accept without closing the connection.
30// This will likely have to be tuned.
31const QuicPacketSequenceNumber kMaxPacketGap = 5000;
32
33// We want to make sure if we get a large nack packet, we don't queue up too
34// many packets at once.  10 is arbitrary.
35const int kMaxRetransmissionsPerAck = 10;
36
37// TCP retransmits after 2 nacks.  We allow for a third in case of out-of-order
38// delivery.
39// TODO(ianswett): Change to match TCP's rule of retransmitting once an ack
40// at least 3 sequence numbers larger arrives.
41const size_t kNumberOfNacksBeforeRetransmission = 3;
42
43// The maxiumum number of packets we'd like to queue.  We may end up queueing
44// more in the case of many control frames.
45// 6 is arbitrary.
46const int kMaxPacketsToSerializeAtOnce = 6;
47
48// Limit the number of packets we send per retransmission-alarm so we
49// eventually cede.  10 is arbitrary.
50const size_t kMaxPacketsPerRetransmissionAlarm = 10;
51
52// Limit the number of FEC groups to two.  If we get enough out of order packets
53// that this becomes limiting, we can revisit.
54const size_t kMaxFecGroups = 2;
55
56// Limit the number of undecryptable packets we buffer in
57// expectation of the CHLO/SHLO arriving.
58const size_t kMaxUndecryptablePackets = 10;
59
60bool Near(QuicPacketSequenceNumber a, QuicPacketSequenceNumber b) {
61  QuicPacketSequenceNumber delta = (a > b) ? a - b : b - a;
62  return delta <= kMaxPacketGap;
63}
64
65
66// An alarm that is scheduled to send an ack if a timeout occurs.
67class AckAlarm : public QuicAlarm::Delegate {
68 public:
69  explicit AckAlarm(QuicConnection* connection)
70      : connection_(connection) {
71  }
72
73  virtual QuicTime OnAlarm() OVERRIDE {
74    connection_->SendAck();
75    return QuicTime::Zero();
76  }
77
78 private:
79  QuicConnection* connection_;
80};
81
82// This alarm will be scheduled any time a data-bearing packet is sent out.
83// When the alarm goes off, the connection checks to see if the oldest packets
84// have been acked, and retransmit them if they have not.
85class RetransmissionAlarm : public QuicAlarm::Delegate {
86 public:
87  explicit RetransmissionAlarm(QuicConnection* connection)
88      : connection_(connection) {
89  }
90
91  virtual QuicTime OnAlarm() OVERRIDE {
92    return connection_->OnRetransmissionTimeout();
93  }
94
95 private:
96  QuicConnection* connection_;
97};
98
99// An alarm that is scheduled when the sent scheduler requires a
100// a delay before sending packets and fires when the packet may be sent.
101class SendAlarm : public QuicAlarm::Delegate {
102 public:
103  explicit SendAlarm(QuicConnection* connection)
104      : connection_(connection) {
105  }
106
107  virtual QuicTime OnAlarm() OVERRIDE {
108    connection_->OnCanWrite();
109    // Never reschedule the alarm, since OnCanWrite does that.
110    return QuicTime::Zero();
111  }
112
113 private:
114  QuicConnection* connection_;
115};
116
117class TimeoutAlarm : public QuicAlarm::Delegate {
118 public:
119  explicit TimeoutAlarm(QuicConnection* connection)
120      : connection_(connection) {
121  }
122
123  virtual QuicTime OnAlarm() OVERRIDE {
124    connection_->CheckForTimeout();
125    // Never reschedule the alarm, since CheckForTimeout does that.
126    return QuicTime::Zero();
127  }
128
129 private:
130  QuicConnection* connection_;
131};
132
133}  // namespace
134
135#define ENDPOINT (is_server_ ? "Server: " : " Client: ")
136
137QuicConnection::QuicConnection(QuicGuid guid,
138                               IPEndPoint address,
139                               QuicConnectionHelperInterface* helper,
140                               bool is_server,
141                               QuicVersion version)
142    : framer_(version,
143              helper->GetClock()->ApproximateNow(),
144              is_server),
145      helper_(helper),
146      encryption_level_(ENCRYPTION_NONE),
147      clock_(helper->GetClock()),
148      random_generator_(helper->GetRandomGenerator()),
149      guid_(guid),
150      peer_address_(address),
151      largest_seen_packet_with_ack_(0),
152      handling_retransmission_timeout_(false),
153      write_blocked_(false),
154      ack_alarm_(helper->CreateAlarm(new AckAlarm(this))),
155      retransmission_alarm_(helper->CreateAlarm(new RetransmissionAlarm(this))),
156      send_alarm_(helper->CreateAlarm(new SendAlarm(this))),
157      timeout_alarm_(helper->CreateAlarm(new TimeoutAlarm(this))),
158      debug_visitor_(NULL),
159      packet_creator_(guid_, &framer_, random_generator_, is_server),
160      packet_generator_(this, NULL, &packet_creator_),
161      idle_network_timeout_(
162          QuicTime::Delta::FromSeconds(kDefaultInitialTimeoutSecs)),
163      overall_connection_timeout_(QuicTime::Delta::Infinite()),
164      creation_time_(clock_->ApproximateNow()),
165      time_of_last_received_packet_(clock_->ApproximateNow()),
166      time_of_last_sent_packet_(clock_->ApproximateNow()),
167      congestion_manager_(clock_, kTCP),
168      version_negotiation_state_(START_NEGOTIATION),
169      max_packets_per_retransmission_alarm_(kMaxPacketsPerRetransmissionAlarm),
170      is_server_(is_server),
171      connected_(true),
172      received_truncated_ack_(false),
173      send_ack_in_response_to_packet_(false),
174      address_migrating_(false) {
175  helper_->SetConnection(this);
176  timeout_alarm_->Set(clock_->ApproximateNow().Add(idle_network_timeout_));
177  framer_.set_visitor(this);
178  framer_.set_received_entropy_calculator(&received_packet_manager_);
179
180  /*
181  if (FLAGS_fake_packet_loss_percentage > 0) {
182    int32 seed = RandomBase::WeakSeed32();
183    LOG(INFO) << ENDPOINT << "Seeding packet loss with " << seed;
184    random_.reset(new MTRandom(seed));
185  }
186  */
187}
188
189QuicConnection::~QuicConnection() {
190  STLDeleteElements(&undecryptable_packets_);
191  STLDeleteValues(&unacked_packets_);
192  STLDeleteValues(&group_map_);
193  for (QueuedPacketList::iterator it = queued_packets_.begin();
194       it != queued_packets_.end(); ++it) {
195    delete it->packet;
196  }
197}
198
199bool QuicConnection::SelectMutualVersion(
200    const QuicVersionVector& available_versions) {
201  // Try to find the highest mutual version by iterating over supported
202  // versions, starting with the highest, and breaking out of the loop once we
203  // find a matching version in the provided available_versions vector.
204  for (size_t i = 0; i < arraysize(kSupportedQuicVersions); ++i) {
205    const QuicVersion& version = kSupportedQuicVersions[i];
206    if (std::find(available_versions.begin(), available_versions.end(),
207                  version) != available_versions.end()) {
208      framer_.set_version(version);
209      return true;
210    }
211  }
212
213  return false;
214}
215
216void QuicConnection::OnError(QuicFramer* framer) {
217  // Packets that we cannot decrypt are dropped.
218  // TODO(rch): add stats to measure this.
219  if (!connected_ || framer->error() == QUIC_DECRYPTION_FAILURE) {
220    return;
221  }
222  SendConnectionClose(framer->error());
223}
224
225void QuicConnection::OnPacket() {
226  DCHECK(last_stream_frames_.empty() &&
227         last_goaway_frames_.empty() &&
228         last_rst_frames_.empty() &&
229         last_ack_frames_.empty() &&
230         last_congestion_frames_.empty());
231}
232
233void QuicConnection::OnPublicResetPacket(
234    const QuicPublicResetPacket& packet) {
235  if (debug_visitor_) {
236    debug_visitor_->OnPublicResetPacket(packet);
237  }
238  CloseConnection(QUIC_PUBLIC_RESET, true);
239}
240
241bool QuicConnection::OnProtocolVersionMismatch(QuicVersion received_version) {
242  // TODO(satyamshekhar): Implement no server state in this mode.
243  if (!is_server_) {
244    LOG(DFATAL) << ENDPOINT << "Framer called OnProtocolVersionMismatch. "
245                << "Closing connection.";
246    CloseConnection(QUIC_INTERNAL_ERROR, false);
247    return false;
248  }
249  DCHECK_NE(version(), received_version);
250
251  if (debug_visitor_) {
252    debug_visitor_->OnProtocolVersionMismatch(received_version);
253  }
254
255  switch (version_negotiation_state_) {
256    case START_NEGOTIATION:
257      if (!framer_.IsSupportedVersion(received_version)) {
258        SendVersionNegotiationPacket();
259        version_negotiation_state_ = NEGOTIATION_IN_PROGRESS;
260        return false;
261      }
262      break;
263
264    case NEGOTIATION_IN_PROGRESS:
265      if (!framer_.IsSupportedVersion(received_version)) {
266        // Drop packets which can't be parsed due to version mismatch.
267        return false;
268      }
269      break;
270
271    case NEGOTIATED_VERSION:
272      // Might be old packets that were sent by the client before the version
273      // was negotiated. Drop these.
274      return false;
275
276    default:
277      DCHECK(false);
278  }
279
280  version_negotiation_state_ = NEGOTIATED_VERSION;
281
282  // Store the new version.
283  framer_.set_version(received_version);
284
285  // TODO(satyamshekhar): Store the sequence number of this packet and close the
286  // connection if we ever received a packet with incorrect version and whose
287  // sequence number is greater.
288  return true;
289}
290
291// Handles version negotiation for client connection.
292void QuicConnection::OnVersionNegotiationPacket(
293    const QuicVersionNegotiationPacket& packet) {
294  if (is_server_) {
295    LOG(DFATAL) << ENDPOINT << "Framer parsed VersionNegotiationPacket."
296                << " Closing connection.";
297    CloseConnection(QUIC_INTERNAL_ERROR, false);
298    return;
299  }
300  if (debug_visitor_) {
301    debug_visitor_->OnVersionNegotiationPacket(packet);
302  }
303
304  if (version_negotiation_state_ != START_NEGOTIATION) {
305    // Possibly a duplicate version negotiation packet.
306    return;
307  }
308
309  if (std::find(packet.versions.begin(),
310                packet.versions.end(), version()) !=
311      packet.versions.end()) {
312    DLOG(WARNING) << ENDPOINT << "The server already supports our version. "
313                  << "It should have accepted our connection.";
314    // Just drop the connection.
315    CloseConnection(QUIC_INVALID_VERSION_NEGOTIATION_PACKET, false);
316    return;
317  }
318
319  if (!SelectMutualVersion(packet.versions)) {
320    SendConnectionCloseWithDetails(QUIC_INVALID_VERSION,
321                                   "no common version found");
322    return;
323  }
324
325  version_negotiation_state_ = NEGOTIATION_IN_PROGRESS;
326  RetransmitUnackedPackets(ALL_PACKETS);
327}
328
329void QuicConnection::OnRevivedPacket() {
330}
331
332bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) {
333  if (debug_visitor_) {
334    debug_visitor_->OnPacketHeader(header);
335  }
336
337  if (!ProcessValidatedPacket()) {
338    return false;
339  }
340
341  // Will be decrement below if we fall through to return true;
342  ++stats_.packets_dropped;
343
344  if (header.public_header.guid != guid_) {
345    DLOG(INFO) << ENDPOINT << "Ignoring packet from unexpected GUID: "
346               << header.public_header.guid << " instead of " << guid_;
347    return false;
348  }
349
350  if (!Near(header.packet_sequence_number,
351            last_header_.packet_sequence_number)) {
352    DLOG(INFO) << ENDPOINT << "Packet " << header.packet_sequence_number
353               << " out of bounds.  Discarding";
354    SendConnectionCloseWithDetails(QUIC_INVALID_PACKET_HEADER,
355                                   "Packet sequence number out of bounds");
356    return false;
357  }
358
359  // If this packet has already been seen, or that the sender
360  // has told us will not be retransmitted, then stop processing the packet.
361  if (!received_packet_manager_.IsAwaitingPacket(
362          header.packet_sequence_number)) {
363    return false;
364  }
365
366  if (version_negotiation_state_ != NEGOTIATED_VERSION) {
367    if (is_server_) {
368      if (!header.public_header.version_flag) {
369        DLOG(WARNING) << ENDPOINT << "Got packet without version flag before "
370                      << "version negotiated.";
371        // Packets should have the version flag till version negotiation is
372        // done.
373        CloseConnection(QUIC_INVALID_VERSION, false);
374        return false;
375      } else {
376        DCHECK_EQ(1u, header.public_header.versions.size());
377        DCHECK_EQ(header.public_header.versions[0], version());
378        version_negotiation_state_ = NEGOTIATED_VERSION;
379      }
380    } else {
381      DCHECK(!header.public_header.version_flag);
382      // If the client gets a packet without the version flag from the server
383      // it should stop sending version since the version negotiation is done.
384      packet_creator_.StopSendingVersion();
385      version_negotiation_state_ = NEGOTIATED_VERSION;
386    }
387  }
388
389  DCHECK_EQ(NEGOTIATED_VERSION, version_negotiation_state_);
390
391  --stats_.packets_dropped;
392  DVLOG(1) << ENDPOINT << "Received packet header: " << header;
393  last_header_ = header;
394  DCHECK(connected_);
395  return true;
396}
397
398void QuicConnection::OnFecProtectedPayload(StringPiece payload) {
399  DCHECK_EQ(IN_FEC_GROUP, last_header_.is_in_fec_group);
400  DCHECK_NE(0u, last_header_.fec_group);
401  QuicFecGroup* group = GetFecGroup();
402  if (group != NULL) {
403    group->Update(last_header_, payload);
404  }
405}
406
407bool QuicConnection::OnStreamFrame(const QuicStreamFrame& frame) {
408  DCHECK(connected_);
409  if (debug_visitor_) {
410    debug_visitor_->OnStreamFrame(frame);
411  }
412  last_stream_frames_.push_back(frame);
413  return true;
414}
415
416bool QuicConnection::OnAckFrame(const QuicAckFrame& incoming_ack) {
417  DCHECK(connected_);
418  if (debug_visitor_) {
419    debug_visitor_->OnAckFrame(incoming_ack);
420  }
421  DVLOG(1) << ENDPOINT << "OnAckFrame: " << incoming_ack;
422
423  if (last_header_.packet_sequence_number <= largest_seen_packet_with_ack_) {
424    DLOG(INFO) << ENDPOINT << "Received an old ack frame: ignoring";
425    return true;
426  }
427
428  if (!ValidateAckFrame(incoming_ack)) {
429    SendConnectionClose(QUIC_INVALID_ACK_DATA);
430    return false;
431  }
432  last_ack_frames_.push_back(incoming_ack);
433  return connected_;
434}
435
436void QuicConnection::ProcessAckFrame(const QuicAckFrame& incoming_ack) {
437  largest_seen_packet_with_ack_ = last_header_.packet_sequence_number;
438
439  received_truncated_ack_ =
440      incoming_ack.received_info.missing_packets.size() >=
441      QuicFramer::GetMaxUnackedPackets(last_header_);
442
443  received_packet_manager_.UpdatePacketInformationReceivedByPeer(incoming_ack);
444  received_packet_manager_.UpdatePacketInformationSentByPeer(incoming_ack);
445  // Possibly close any FecGroups which are now irrelevant.
446  CloseFecGroupsBefore(incoming_ack.sent_info.least_unacked + 1);
447
448  sent_entropy_manager_.ClearEntropyBefore(
449      received_packet_manager_.least_packet_awaited_by_peer() - 1);
450
451  SequenceNumberSet acked_packets;
452  HandleAckForSentPackets(incoming_ack, &acked_packets);
453  HandleAckForSentFecPackets(incoming_ack, &acked_packets);
454  if (acked_packets.size() > 0) {
455    visitor_->OnAck(acked_packets);
456  }
457  congestion_manager_.OnIncomingAckFrame(incoming_ack,
458                                         time_of_last_received_packet_);
459}
460
461bool QuicConnection::OnCongestionFeedbackFrame(
462    const QuicCongestionFeedbackFrame& feedback) {
463  DCHECK(connected_);
464  if (debug_visitor_) {
465    debug_visitor_->OnCongestionFeedbackFrame(feedback);
466  }
467  last_congestion_frames_.push_back(feedback);
468  return connected_;
469}
470
471bool QuicConnection::ValidateAckFrame(const QuicAckFrame& incoming_ack) {
472  if (incoming_ack.received_info.largest_observed >
473      packet_creator_.sequence_number()) {
474    DLOG(ERROR) << ENDPOINT << "Peer's observed unsent packet:"
475                << incoming_ack.received_info.largest_observed << " vs "
476                << packet_creator_.sequence_number();
477    // We got an error for data we have not sent.  Error out.
478    return false;
479  }
480
481  if (incoming_ack.received_info.largest_observed <
482          received_packet_manager_.peer_largest_observed_packet()) {
483    DLOG(ERROR) << ENDPOINT << "Peer's largest_observed packet decreased:"
484                << incoming_ack.received_info.largest_observed << " vs "
485                << received_packet_manager_.peer_largest_observed_packet();
486    // A new ack has a diminished largest_observed value.  Error out.
487    // If this was an old packet, we wouldn't even have checked.
488    return false;
489  }
490
491  // We can't have too many unacked packets, or our ack frames go over
492  // kMaxPacketSize.
493  DCHECK_LE(incoming_ack.received_info.missing_packets.size(),
494            QuicFramer::GetMaxUnackedPackets(last_header_));
495
496  if (incoming_ack.sent_info.least_unacked <
497      received_packet_manager_.peer_least_packet_awaiting_ack()) {
498    DLOG(ERROR) << ENDPOINT << "Peer's sent low least_unacked: "
499                << incoming_ack.sent_info.least_unacked << " vs "
500                << received_packet_manager_.peer_least_packet_awaiting_ack();
501    // We never process old ack frames, so this number should only increase.
502    return false;
503  }
504
505  if (incoming_ack.sent_info.least_unacked >
506      last_header_.packet_sequence_number) {
507    DLOG(ERROR) << ENDPOINT << "Peer sent least_unacked:"
508                << incoming_ack.sent_info.least_unacked
509                << " greater than the enclosing packet sequence number:"
510                << last_header_.packet_sequence_number;
511    return false;
512  }
513
514  if (!incoming_ack.received_info.missing_packets.empty() &&
515      *incoming_ack.received_info.missing_packets.rbegin() >
516      incoming_ack.received_info.largest_observed) {
517    DLOG(ERROR) << ENDPOINT << "Peer sent missing packet: "
518                << *incoming_ack.received_info.missing_packets.rbegin()
519                << " greater than largest observed: "
520                << incoming_ack.received_info.largest_observed;
521    return false;
522  }
523
524  if (!incoming_ack.received_info.missing_packets.empty() &&
525      *incoming_ack.received_info.missing_packets.begin() <
526      received_packet_manager_.least_packet_awaited_by_peer()) {
527    DLOG(ERROR) << ENDPOINT << "Peer sent missing packet: "
528                << *incoming_ack.received_info.missing_packets.begin()
529                << "smaller than least_packet_awaited_by_peer_: "
530                << received_packet_manager_.least_packet_awaited_by_peer();
531    return false;
532  }
533
534  if (!sent_entropy_manager_.IsValidEntropy(
535          incoming_ack.received_info.largest_observed,
536          incoming_ack.received_info.missing_packets,
537          incoming_ack.received_info.entropy_hash)) {
538    DLOG(ERROR) << ENDPOINT << "Peer sent invalid entropy.";
539    return false;
540  }
541
542  return true;
543}
544
545void QuicConnection::HandleAckForSentPackets(const QuicAckFrame& incoming_ack,
546                                             SequenceNumberSet* acked_packets) {
547  int retransmitted_packets = 0;
548  // Go through the packets we have not received an ack for and see if this
549  // incoming_ack shows they've been seen by the peer.
550  UnackedPacketMap::iterator it = unacked_packets_.begin();
551  while (it != unacked_packets_.end()) {
552    QuicPacketSequenceNumber sequence_number = it->first;
553    if (sequence_number >
554        received_packet_manager_.peer_largest_observed_packet()) {
555      // These are very new sequence_numbers.
556      break;
557    }
558    RetransmittableFrames* unacked = it->second;
559    if (!IsAwaitingPacket(incoming_ack.received_info, sequence_number)) {
560      // Packet was acked, so remove it from our unacked packet list.
561      DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
562      acked_packets->insert(sequence_number);
563      delete unacked;
564      unacked_packets_.erase(it++);
565      retransmission_map_.erase(sequence_number);
566    } else {
567      // This is a packet which we planned on retransmitting and has not been
568      // seen at the time of this ack being sent out.  See if it's our new
569      // lowest unacked packet.
570      DVLOG(1) << ENDPOINT << "still missing packet " << sequence_number;
571      ++it;
572      // The peer got packets after this sequence number.  This is an explicit
573      // nack.
574      RetransmissionMap::iterator retransmission_it =
575          retransmission_map_.find(sequence_number);
576      ++(retransmission_it->second.number_nacks);
577      if (retransmission_it->second.number_nacks >=
578             kNumberOfNacksBeforeRetransmission &&
579          retransmitted_packets < kMaxRetransmissionsPerAck) {
580        ++retransmitted_packets;
581        DVLOG(1) << ENDPOINT << "Trying to retransmit packet "
582                 << sequence_number
583                 << " as it has been nacked 3 or more times.";
584        // RetransmitPacket will retransmit with a new sequence_number.
585        RetransmitPacket(sequence_number);
586      }
587    }
588  }
589}
590
591void QuicConnection::HandleAckForSentFecPackets(
592    const QuicAckFrame& incoming_ack, SequenceNumberSet* acked_packets) {
593  UnackedPacketMap::iterator it = unacked_fec_packets_.begin();
594  while (it != unacked_fec_packets_.end()) {
595    QuicPacketSequenceNumber sequence_number = it->first;
596    if (sequence_number >
597        received_packet_manager_.peer_largest_observed_packet()) {
598      break;
599    }
600    if (!IsAwaitingPacket(incoming_ack.received_info, sequence_number)) {
601      DVLOG(1) << ENDPOINT << "Got an ack for fec packet: " << sequence_number;
602      acked_packets->insert(sequence_number);
603      unacked_fec_packets_.erase(it++);
604    } else {
605      DVLOG(1) << ENDPOINT << "Still missing ack for fec packet: "
606               << sequence_number;
607      ++it;
608    }
609  }
610}
611
612void QuicConnection::OnFecData(const QuicFecData& fec) {
613  DCHECK_EQ(IN_FEC_GROUP, last_header_.is_in_fec_group);
614  DCHECK_NE(0u, last_header_.fec_group);
615  QuicFecGroup* group = GetFecGroup();
616  if (group != NULL) {
617    group->UpdateFec(last_header_.packet_sequence_number,
618                     last_header_.entropy_flag, fec);
619  }
620}
621
622bool QuicConnection::OnRstStreamFrame(const QuicRstStreamFrame& frame) {
623  DCHECK(connected_);
624  if (debug_visitor_) {
625    debug_visitor_->OnRstStreamFrame(frame);
626  }
627  DLOG(INFO) << ENDPOINT << "Stream reset with error "
628             << QuicUtils::StreamErrorToString(frame.error_code);
629  last_rst_frames_.push_back(frame);
630  return connected_;
631}
632
633bool QuicConnection::OnConnectionCloseFrame(
634    const QuicConnectionCloseFrame& frame) {
635  DCHECK(connected_);
636  if (debug_visitor_) {
637    debug_visitor_->OnConnectionCloseFrame(frame);
638  }
639  DLOG(INFO) << ENDPOINT << "Connection closed with error "
640             << QuicUtils::ErrorToString(frame.error_code)
641             << " " << frame.error_details;
642  CloseConnection(frame.error_code, true);
643  DCHECK(!connected_);
644  return false;
645}
646
647bool QuicConnection::OnGoAwayFrame(const QuicGoAwayFrame& frame) {
648  DCHECK(connected_);
649  DLOG(INFO) << ENDPOINT << "Go away received with error "
650             << QuicUtils::ErrorToString(frame.error_code)
651             << " and reason:" << frame.reason_phrase;
652  last_goaway_frames_.push_back(frame);
653  return connected_;
654}
655
656void QuicConnection::OnPacketComplete() {
657  // Don't do anything if this packet closed the connection.
658  if (!connected_) {
659    ClearLastFrames();
660    return;
661  }
662
663  DLOG(INFO) << ENDPOINT << (last_packet_revived_ ? "Revived" : "Got")
664             << " packet " << last_header_.packet_sequence_number
665             << " with " << last_ack_frames_.size() << " acks, "
666             << last_congestion_frames_.size() << " congestions, "
667             << last_goaway_frames_.size() << " goaways, "
668             << last_rst_frames_.size() << " rsts, "
669             << last_stream_frames_.size()
670             << " stream frames for " << last_header_.public_header.guid;
671  if (!last_packet_revived_) {
672    congestion_manager_.RecordIncomingPacket(
673        last_size_, last_header_.packet_sequence_number,
674        time_of_last_received_packet_, last_packet_revived_);
675  }
676
677  // Must called before ack processing, because processing acks removes entries
678  // from unacket_packets_, increasing the least_unacked.
679  const bool last_packet_should_instigate_ack = ShouldLastPacketInstigateAck();
680
681  if ((last_stream_frames_.empty() ||
682       visitor_->OnPacket(self_address_, peer_address_,
683                          last_header_, last_stream_frames_))) {
684    received_packet_manager_.RecordPacketReceived(
685        last_header_, time_of_last_received_packet_);
686  }
687
688  // Process stream resets, then acks, then congestion feedback.
689  for (size_t i = 0; i < last_goaway_frames_.size(); ++i) {
690    visitor_->OnGoAway(last_goaway_frames_[i]);
691  }
692  for (size_t i = 0; i < last_rst_frames_.size(); ++i) {
693    visitor_->OnRstStream(last_rst_frames_[i]);
694  }
695  for (size_t i = 0; i < last_ack_frames_.size(); ++i) {
696    ProcessAckFrame(last_ack_frames_[i]);
697  }
698  for (size_t i = 0; i < last_congestion_frames_.size(); ++i) {
699    congestion_manager_.OnIncomingQuicCongestionFeedbackFrame(
700        last_congestion_frames_[i], time_of_last_received_packet_);
701  }
702
703  MaybeSendInResponseToPacket(last_packet_should_instigate_ack);
704
705  ClearLastFrames();
706}
707
708void QuicConnection::ClearLastFrames() {
709  last_stream_frames_.clear();
710  last_goaway_frames_.clear();
711  last_rst_frames_.clear();
712  last_ack_frames_.clear();
713  last_congestion_frames_.clear();
714}
715
716QuicAckFrame* QuicConnection::CreateAckFrame() {
717  QuicAckFrame* outgoing_ack = new QuicAckFrame();
718  received_packet_manager_.UpdateReceivedPacketInfo(
719      &(outgoing_ack->received_info), clock_->ApproximateNow());
720  UpdateSentPacketInfo(&(outgoing_ack->sent_info));
721  DVLOG(1) << ENDPOINT << "Creating ack frame: " << *outgoing_ack;
722  return outgoing_ack;
723}
724
725QuicCongestionFeedbackFrame* QuicConnection::CreateFeedbackFrame() {
726  return new QuicCongestionFeedbackFrame(outgoing_congestion_feedback_);
727}
728
729bool QuicConnection::ShouldLastPacketInstigateAck() {
730  if (!last_stream_frames_.empty() ||
731      !last_goaway_frames_.empty() ||
732      !last_rst_frames_.empty()) {
733    return true;
734  }
735
736  // If the peer is still waiting for a packet that we are no
737  // longer planning to send, we should send an ack to raise
738  // the high water mark.
739  if (!last_ack_frames_.empty() &&
740      !last_ack_frames_.back().received_info.missing_packets.empty() &&
741      !unacked_packets_.empty()) {
742    if (unacked_packets_.begin()->first >
743        *last_ack_frames_.back().received_info.missing_packets.begin()) {
744      return true;
745    }
746  }
747
748  return false;
749}
750
751void QuicConnection::MaybeSendInResponseToPacket(
752    bool last_packet_should_instigate_ack) {
753  // TODO(ianswett): Better merge these two blocks to queue up an ack if
754  // necessary, then either only send the ack or bundle it with other data.
755  if (!last_ack_frames_.empty()) {
756    // Now the we have received an ack, we might be able to send packets which
757    // are queued locally, or drain streams which are blocked.
758    QuicTime::Delta delay = congestion_manager_.TimeUntilSend(
759        time_of_last_received_packet_, NOT_RETRANSMISSION,
760        HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE);
761    if (delay.IsZero()) {
762      send_alarm_->Cancel();
763      WriteIfNotBlocked();
764    } else if (!delay.IsInfinite()) {
765      send_alarm_->Cancel();
766      send_alarm_->Set(time_of_last_received_packet_.Add(delay));
767    }
768  }
769
770  if (!last_packet_should_instigate_ack) {
771    return;
772  }
773
774  if (send_ack_in_response_to_packet_) {
775    SendAck();
776  } else if (!last_stream_frames_.empty()) {
777    // TODO(alyssar) this case should really be "if the packet contained any
778    // non-ack frame", rather than "if the packet contained a stream frame"
779    if (!ack_alarm_->IsSet()) {
780      ack_alarm_->Set(clock_->ApproximateNow().Add(
781          congestion_manager_.DefaultRetransmissionTime()));
782    }
783  }
784  send_ack_in_response_to_packet_ = !send_ack_in_response_to_packet_;
785}
786
787void QuicConnection::SendVersionNegotiationPacket() {
788  QuicVersionVector supported_versions;
789  for (size_t i = 0; i < arraysize(kSupportedQuicVersions); ++i) {
790    supported_versions.push_back(kSupportedQuicVersions[i]);
791  }
792  QuicEncryptedPacket* encrypted =
793      packet_creator_.SerializeVersionNegotiationPacket(supported_versions);
794  // TODO(satyamshekhar): implement zero server state negotiation.
795  int error;
796  helper_->WritePacketToWire(*encrypted, &error);
797  delete encrypted;
798}
799
800QuicConsumedData QuicConnection::SendStreamData(QuicStreamId id,
801                                                StringPiece data,
802                                                QuicStreamOffset offset,
803                                                bool fin) {
804  return packet_generator_.ConsumeData(id, data, offset, fin);
805}
806
807void QuicConnection::SendRstStream(QuicStreamId id,
808                                   QuicRstStreamErrorCode error) {
809  packet_generator_.AddControlFrame(
810      QuicFrame(new QuicRstStreamFrame(id, error)));
811}
812
813const QuicConnectionStats& QuicConnection::GetStats() {
814  // Update rtt and estimated bandwidth.
815  stats_.rtt = congestion_manager_.SmoothedRtt().ToMicroseconds();
816  stats_.estimated_bandwidth =
817      congestion_manager_.BandwidthEstimate().ToBytesPerSecond();
818  return stats_;
819}
820
821void QuicConnection::ProcessUdpPacket(const IPEndPoint& self_address,
822                                      const IPEndPoint& peer_address,
823                                      const QuicEncryptedPacket& packet) {
824  if (!connected_) {
825    return;
826  }
827  if (debug_visitor_) {
828    debug_visitor_->OnPacketReceived(self_address, peer_address, packet);
829  }
830  last_packet_revived_ = false;
831  last_size_ = packet.length();
832
833  address_migrating_ = false;
834
835  if (peer_address_.address().empty()) {
836    peer_address_ = peer_address;
837  }
838  if (self_address_.address().empty()) {
839    self_address_ = self_address;
840  }
841
842  if (!(peer_address == peer_address_ && self_address == self_address_)) {
843    address_migrating_ = true;
844  }
845
846  stats_.bytes_received += packet.length();
847  ++stats_.packets_received;
848
849  if (!framer_.ProcessPacket(packet)) {
850    // If we are unable to decrypt this packet, it might be
851    // because the CHLO or SHLO packet was lost.
852    if (encryption_level_ != ENCRYPTION_FORWARD_SECURE &&
853        framer_.error() == QUIC_DECRYPTION_FAILURE &&
854        undecryptable_packets_.size() < kMaxUndecryptablePackets) {
855      QueueUndecryptablePacket(packet);
856    }
857    DVLOG(1) << ENDPOINT << "Unable to process packet.  Last packet processed: "
858             << last_header_.packet_sequence_number;
859    return;
860  }
861  MaybeProcessUndecryptablePackets();
862  MaybeProcessRevivedPacket();
863}
864
865bool QuicConnection::OnCanWrite() {
866  write_blocked_ = false;
867  return DoWrite();
868}
869
870bool QuicConnection::WriteIfNotBlocked() {
871  if (write_blocked_) {
872    return false;
873  }
874  return DoWrite();
875}
876
877bool QuicConnection::DoWrite() {
878  DCHECK(!write_blocked_);
879  WriteQueuedPackets();
880
881  // Sending queued packets may have caused the socket to become write blocked,
882  // or the congestion manager to prohibit sending.  If we've sent everything
883  // we had queued and we're still not blocked, let the visitor know it can
884  // write more.
885  if (CanWrite(NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA,
886               NOT_HANDSHAKE)) {
887    packet_generator_.StartBatchOperations();
888    bool all_bytes_written = visitor_->OnCanWrite();
889    packet_generator_.FinishBatchOperations();
890
891    // After the visitor writes, it may have caused the socket to become write
892    // blocked or the congestion manager to prohibit sending, so check again.
893    if (!write_blocked_ && !all_bytes_written &&
894        CanWrite(NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA,
895                 NOT_HANDSHAKE)) {
896      // We're not write blocked, but some stream didn't write out all of its
897      // bytes.  Register for 'immediate' resumption so we'll keep writing after
898      // other quic connections have had a chance to use the socket.
899      send_alarm_->Cancel();
900      send_alarm_->Set(clock_->ApproximateNow());
901    }
902  }
903
904  return !write_blocked_;
905}
906
907bool QuicConnection::ProcessValidatedPacket() {
908  if (address_migrating_) {
909    SendConnectionCloseWithDetails(
910        QUIC_ERROR_MIGRATING_ADDRESS,
911        "Address migration is not yet a supported feature");
912    return false;
913  }
914  time_of_last_received_packet_ = clock_->Now();
915  DVLOG(1) << ENDPOINT << "time of last received packet: "
916           << time_of_last_received_packet_.ToDebuggingValue();
917  return true;
918}
919
920bool QuicConnection::WriteQueuedPackets() {
921  DCHECK(!write_blocked_);
922
923  size_t num_queued_packets = queued_packets_.size() + 1;
924  QueuedPacketList::iterator packet_iterator = queued_packets_.begin();
925  while (!write_blocked_ && packet_iterator != queued_packets_.end()) {
926    // Ensure that from one iteration of this loop to the next we
927    // succeeded in sending a packet so we don't infinitely loop.
928    // TODO(rch): clean up and close the connection if we really hit this.
929    DCHECK_LT(queued_packets_.size(), num_queued_packets);
930    num_queued_packets = queued_packets_.size();
931    if (WritePacket(packet_iterator->encryption_level,
932                    packet_iterator->sequence_number,
933                    packet_iterator->packet,
934                    packet_iterator->retransmittable,
935                    NO_FORCE)) {
936      packet_iterator = queued_packets_.erase(packet_iterator);
937    } else {
938      // Continue, because some queued packets may still be writable.
939      // This can happen if a retransmit send fail.
940      ++packet_iterator;
941    }
942  }
943
944  return !write_blocked_;
945}
946
947bool QuicConnection::MaybeRetransmitPacketForRTO(
948    QuicPacketSequenceNumber sequence_number) {
949  DCHECK_EQ(ContainsKey(unacked_packets_, sequence_number),
950            ContainsKey(retransmission_map_, sequence_number));
951
952  if (!ContainsKey(unacked_packets_, sequence_number)) {
953    DVLOG(2) << ENDPOINT << "alarm fired for " << sequence_number
954             << " but it has been acked or already retransmitted with"
955             << " different sequence number.";
956    // So no extra delay is added for this packet.
957    return true;
958  }
959
960  RetransmissionMap::iterator retransmission_it =
961      retransmission_map_.find(sequence_number);
962  // If the packet hasn't been acked and we're getting truncated acks, ignore
963  // any RTO for packets larger than the peer's largest observed packet; it may
964  // have been received by the peer and just wasn't acked due to the ack frame
965  // running out of space.
966  if (received_truncated_ack_ && sequence_number >
967      received_packet_manager_.peer_largest_observed_packet() &&
968      // We allow retransmission of already retransmitted packets so that we
969      // retransmit packets that were retransmissions of the packet with
970      // sequence number < the largest observed field of the truncated ack.
971      retransmission_it->second.number_retransmissions == 0) {
972    return false;
973  } else {
974    ++stats_.rto_count;
975    RetransmitPacket(sequence_number);
976    return true;
977  }
978}
979
980void QuicConnection::RetransmitUnackedPackets(
981    RetransmissionType retransmission_type) {
982  if (unacked_packets_.empty()) {
983    return;
984  }
985  UnackedPacketMap::iterator next_it = unacked_packets_.begin();
986  QuicPacketSequenceNumber end_sequence_number =
987      unacked_packets_.rbegin()->first;
988  do {
989    UnackedPacketMap::iterator current_it = next_it;
990    ++next_it;
991
992    if (retransmission_type == ALL_PACKETS ||
993        current_it->second->encryption_level() == ENCRYPTION_INITIAL) {
994      // TODO(satyamshekhar): Think about congestion control here.
995      // Specifically, about the retransmission count of packets being sent
996      // proactively to achieve 0 (minimal) RTT.
997      RetransmitPacket(current_it->first);
998    }
999  } while (next_it != unacked_packets_.end() &&
1000           next_it->first <= end_sequence_number);
1001}
1002
1003void QuicConnection::RetransmitPacket(
1004    QuicPacketSequenceNumber sequence_number) {
1005  UnackedPacketMap::iterator unacked_it =
1006      unacked_packets_.find(sequence_number);
1007  RetransmissionMap::iterator retransmission_it =
1008      retransmission_map_.find(sequence_number);
1009  // There should always be an entry corresponding to |sequence_number| in
1010  // both |retransmission_map_| and |unacked_packets_|. Retransmissions due to
1011  // RTO for sequence numbers that are already acked or retransmitted are
1012  // ignored by MaybeRetransmitPacketForRTO.
1013  DCHECK(unacked_it != unacked_packets_.end());
1014  DCHECK(retransmission_it != retransmission_map_.end());
1015  RetransmittableFrames* unacked = unacked_it->second;
1016  // TODO(pwestin): Need to fix potential issue with FEC and a 1 packet
1017  // congestion window see b/8331807 for details.
1018  congestion_manager_.AbandoningPacket(sequence_number);
1019
1020  // Re-packetize the frames with a new sequence number for retransmission.
1021  // Retransmitted data packets do not use FEC, even when it's enabled.
1022  SerializedPacket serialized_packet =
1023      packet_creator_.SerializeAllFrames(unacked->frames());
1024  RetransmissionInfo retransmission_info(serialized_packet.sequence_number);
1025  retransmission_info.number_retransmissions =
1026      retransmission_it->second.number_retransmissions + 1;
1027  // Remove info with old sequence number.
1028  unacked_packets_.erase(unacked_it);
1029  retransmission_map_.erase(retransmission_it);
1030  DVLOG(1) << ENDPOINT << "Retransmitting unacked packet " << sequence_number
1031           << " as " << serialized_packet.sequence_number;
1032  DCHECK(unacked_packets_.empty() ||
1033         unacked_packets_.rbegin()->first < serialized_packet.sequence_number);
1034  unacked_packets_.insert(make_pair(serialized_packet.sequence_number,
1035                                    unacked));
1036  retransmission_map_.insert(make_pair(serialized_packet.sequence_number,
1037                                       retransmission_info));
1038  SendOrQueuePacket(unacked->encryption_level(),
1039                    serialized_packet.sequence_number,
1040                    serialized_packet.packet,
1041                    serialized_packet.entropy_hash,
1042                    HAS_RETRANSMITTABLE_DATA);
1043}
1044
1045bool QuicConnection::CanWrite(Retransmission retransmission,
1046                              HasRetransmittableData retransmittable,
1047                              IsHandshake handshake) {
1048  // TODO(ianswett): If the packet is a retransmit, the current send alarm may
1049  // be too long.
1050  if (write_blocked_ || send_alarm_->IsSet()) {
1051    return false;
1052  }
1053
1054  QuicTime now = clock_->Now();
1055  QuicTime::Delta delay = congestion_manager_.TimeUntilSend(
1056      now, retransmission, retransmittable, handshake);
1057  if (delay.IsInfinite()) {
1058    return false;
1059  }
1060
1061  // If the scheduler requires a delay, then we can not send this packet now.
1062  if (!delay.IsZero()) {
1063    send_alarm_->Cancel();
1064    send_alarm_->Set(now.Add(delay));
1065    return false;
1066  }
1067  return true;
1068}
1069
1070bool QuicConnection::IsRetransmission(
1071    QuicPacketSequenceNumber sequence_number) {
1072  RetransmissionMap::iterator it = retransmission_map_.find(sequence_number);
1073  return it != retransmission_map_.end() &&
1074      it->second.number_retransmissions > 0;
1075}
1076
1077void QuicConnection::SetupRetransmission(
1078    QuicPacketSequenceNumber sequence_number,
1079    EncryptionLevel level) {
1080  RetransmissionMap::iterator it = retransmission_map_.find(sequence_number);
1081  if (it == retransmission_map_.end()) {
1082    DVLOG(1) << ENDPOINT << "Will not retransmit packet " << sequence_number;
1083    return;
1084  }
1085
1086  RetransmissionInfo retransmission_info = it->second;
1087  // TODO(rch): consider using a much smaller retransmisison_delay
1088  // for the ENCRYPTION_NONE packets.
1089  size_t effective_retransmission_count =
1090      level == ENCRYPTION_NONE ? 0 : retransmission_info.number_retransmissions;
1091  QuicTime::Delta retransmission_delay =
1092      congestion_manager_.GetRetransmissionDelay(
1093          unacked_packets_.size(),
1094          effective_retransmission_count);
1095
1096  retransmission_timeouts_.push(RetransmissionTime(
1097      sequence_number,
1098      clock_->ApproximateNow().Add(retransmission_delay),
1099      false));
1100
1101  // Do not set the retransmisson alarm if we're already handling the
1102  // retransmission alarm because the retransmission alarm will be reset when
1103  // OnRetransmissionTimeout completes.
1104  if (!handling_retransmission_timeout_ && !retransmission_alarm_->IsSet()) {
1105    retransmission_alarm_->Set(
1106        clock_->ApproximateNow().Add(retransmission_delay));
1107  }
1108  // TODO(satyamshekhar): restore packet reordering with Ian's TODO in
1109  // SendStreamData().
1110}
1111
1112void QuicConnection::SetupAbandonFecTimer(
1113    QuicPacketSequenceNumber sequence_number) {
1114  DCHECK(ContainsKey(unacked_fec_packets_, sequence_number));
1115  QuicTime::Delta retransmission_delay =
1116      QuicTime::Delta::FromMilliseconds(
1117          congestion_manager_.DefaultRetransmissionTime().ToMilliseconds() * 3);
1118  retransmission_timeouts_.push(RetransmissionTime(
1119      sequence_number,
1120      clock_->ApproximateNow().Add(retransmission_delay),
1121      true));
1122}
1123
1124void QuicConnection::DropPacket(QuicPacketSequenceNumber sequence_number) {
1125  UnackedPacketMap::iterator unacked_it =
1126      unacked_packets_.find(sequence_number);
1127  // Packet was not meant to be retransmitted.
1128  if (unacked_it == unacked_packets_.end()) {
1129    DCHECK(!ContainsKey(retransmission_map_, sequence_number));
1130    return;
1131  }
1132  // Delete the unacked packet.
1133  delete unacked_it->second;
1134  unacked_packets_.erase(unacked_it);
1135  retransmission_map_.erase(sequence_number);
1136  return;
1137}
1138
1139bool QuicConnection::WritePacket(EncryptionLevel level,
1140                                 QuicPacketSequenceNumber sequence_number,
1141                                 QuicPacket* packet,
1142                                 HasRetransmittableData retransmittable,
1143                                 Force forced) {
1144  if (!connected_) {
1145    DLOG(INFO) << ENDPOINT
1146               << "Not sending packet as connection is disconnected.";
1147    delete packet;
1148    // Returning true because we deleted the packet and the caller shouldn't
1149    // delete it again.
1150    return true;
1151  }
1152
1153  if (encryption_level_ == ENCRYPTION_FORWARD_SECURE &&
1154      level == ENCRYPTION_NONE) {
1155    // Drop packets that are NULL encrypted since the peer won't accept them
1156    // anymore.
1157    DLOG(INFO) << ENDPOINT << "Dropped packet: " << sequence_number
1158               << " since the packet is NULL encrypted.";
1159    DropPacket(sequence_number);
1160    delete packet;
1161    return true;
1162  }
1163
1164  Retransmission retransmission = IsRetransmission(sequence_number) ?
1165      IS_RETRANSMISSION : NOT_RETRANSMISSION;
1166  IsHandshake handshake = level == ENCRYPTION_NONE ? IS_HANDSHAKE
1167                                                   : NOT_HANDSHAKE;
1168
1169  // If we are not forced and we can't write, then simply return false;
1170  if (forced == NO_FORCE &&
1171      !CanWrite(retransmission, retransmittable, handshake)) {
1172    return false;
1173  }
1174
1175  scoped_ptr<QuicEncryptedPacket> encrypted(
1176      framer_.EncryptPacket(level, sequence_number, *packet));
1177  DLOG(INFO) << ENDPOINT << "Sending packet number " << sequence_number
1178             << " : " << (packet->is_fec_packet() ? "FEC " :
1179                 (retransmittable == HAS_RETRANSMITTABLE_DATA
1180                      ? "data bearing " : " ack only "))
1181             << ", encryption level: "
1182             << QuicUtils::EncryptionLevelToString(level)
1183             << ", length:" << packet->length();
1184  DVLOG(2) << ENDPOINT << "packet(" << sequence_number << "): " << std::endl
1185           << QuicUtils::StringToHexASCIIDump(packet->AsStringPiece());
1186
1187  DCHECK(encrypted->length() <= kMaxPacketSize)
1188      << "Packet " << sequence_number << " will not be read; too large: "
1189      << packet->length() << " " << encrypted->length() << " "
1190      << " forced: " << (forced == FORCE ? "yes" : "no");
1191
1192  int error;
1193  QuicTime now = clock_->Now();
1194  if (!retransmission) {
1195    time_of_last_sent_packet_ = now;
1196  }
1197  DVLOG(1) << ENDPOINT << "time of last sent packet: "
1198           << now.ToDebuggingValue();
1199  if (WritePacketToWire(sequence_number, level, *encrypted, &error) == -1) {
1200    if (helper_->IsWriteBlocked(error)) {
1201      // TODO(satyashekhar): It might be more efficient (fewer system calls), if
1202      // all connections share this variable i.e this becomes a part of
1203      // PacketWriterInterface.
1204      write_blocked_ = true;
1205      // If the socket buffers the the data, then the packet should not
1206      // be queued and sent again, which would result in an unnecessary
1207      // duplicate packet being sent.
1208      return helper_->IsWriteBlockedDataBuffered();
1209    }
1210    // We can't send an error as the socket is presumably borked.
1211    CloseConnection(QUIC_PACKET_WRITE_ERROR, false);
1212    return false;
1213  }
1214
1215  // Set the retransmit alarm only when we have sent the packet to the client
1216  // and not when it goes to the pending queue, otherwise we will end up adding
1217  // an entry to retransmission_timeout_ every time we attempt a write.
1218  if (retransmittable == HAS_RETRANSMITTABLE_DATA) {
1219    SetupRetransmission(sequence_number, level);
1220  } else if (packet->is_fec_packet()) {
1221    SetupAbandonFecTimer(sequence_number);
1222  }
1223
1224  congestion_manager_.SentPacket(sequence_number, now, packet->length(),
1225                                 retransmission);
1226
1227  stats_.bytes_sent += encrypted->length();
1228  ++stats_.packets_sent;
1229
1230  if (retransmission == IS_RETRANSMISSION) {
1231    stats_.bytes_retransmitted += encrypted->length();
1232    ++stats_.packets_retransmitted;
1233  }
1234
1235  delete packet;
1236  return true;
1237}
1238
1239int QuicConnection::WritePacketToWire(QuicPacketSequenceNumber sequence_number,
1240                                      EncryptionLevel level,
1241                                      const QuicEncryptedPacket& packet,
1242                                      int* error) {
1243  int bytes_written = helper_->WritePacketToWire(packet, error);
1244  if (debug_visitor_) {
1245    // WritePacketToWire returned -1, then |error| will be populated with
1246    // an error code, which we want to pass along to the visitor.
1247    debug_visitor_->OnPacketSent(sequence_number, level, packet,
1248                                 bytes_written == -1 ? *error : bytes_written);
1249  }
1250  return bytes_written;
1251}
1252
1253bool QuicConnection::OnSerializedPacket(
1254    const SerializedPacket& serialized_packet) {
1255  if (serialized_packet.retransmittable_frames != NULL) {
1256    DCHECK(unacked_packets_.empty() ||
1257           unacked_packets_.rbegin()->first <
1258               serialized_packet.sequence_number);
1259    // Retransmitted frames will be sent with the same encryption level as the
1260    // original.
1261    serialized_packet.retransmittable_frames->set_encryption_level(
1262        encryption_level_);
1263    unacked_packets_.insert(
1264        make_pair(serialized_packet.sequence_number,
1265                  serialized_packet.retransmittable_frames));
1266    // All unacked packets might be retransmitted.
1267    retransmission_map_.insert(
1268        make_pair(serialized_packet.sequence_number,
1269                  RetransmissionInfo(serialized_packet.sequence_number)));
1270  } else if (serialized_packet.packet->is_fec_packet()) {
1271    unacked_fec_packets_.insert(make_pair(
1272        serialized_packet.sequence_number,
1273        serialized_packet.retransmittable_frames));
1274  }
1275  return SendOrQueuePacket(encryption_level_,
1276                           serialized_packet.sequence_number,
1277                           serialized_packet.packet,
1278                           serialized_packet.entropy_hash,
1279                           serialized_packet.retransmittable_frames != NULL ?
1280                               HAS_RETRANSMITTABLE_DATA :
1281                               NO_RETRANSMITTABLE_DATA);
1282}
1283
1284bool QuicConnection::SendOrQueuePacket(EncryptionLevel level,
1285                                       QuicPacketSequenceNumber sequence_number,
1286                                       QuicPacket* packet,
1287                                       QuicPacketEntropyHash entropy_hash,
1288                                       HasRetransmittableData retransmittable) {
1289  sent_entropy_manager_.RecordPacketEntropyHash(sequence_number, entropy_hash);
1290  if (!WritePacket(level, sequence_number, packet, retransmittable, NO_FORCE)) {
1291    queued_packets_.push_back(QueuedPacket(sequence_number, packet, level,
1292                                           retransmittable));
1293    return false;
1294  }
1295  return true;
1296}
1297
1298bool QuicConnection::ShouldSimulateLostPacket() {
1299  // TODO(rch): enable this
1300  return false;
1301  /*
1302  return FLAGS_fake_packet_loss_percentage > 0 &&
1303      random_->Rand32() % 100 < FLAGS_fake_packet_loss_percentage;
1304  */
1305}
1306
1307void QuicConnection::UpdateSentPacketInfo(SentPacketInfo* sent_info) {
1308  if (!unacked_packets_.empty()) {
1309    sent_info->least_unacked = unacked_packets_.begin()->first;
1310  } else {
1311    // If there are no unacked packets, set the least unacked packet to
1312    // sequence_number() + 1 since that will be the sequence number of this
1313    // ack packet whenever it is sent.
1314    sent_info->least_unacked = packet_creator_.sequence_number() + 1;
1315  }
1316  sent_info->entropy_hash = sent_entropy_manager_.EntropyHash(
1317      sent_info->least_unacked - 1);
1318}
1319
1320void QuicConnection::SendAck() {
1321  ack_alarm_->Cancel();
1322
1323  // TODO(rch): delay this until the CreateFeedbackFrame
1324  // method is invoked.  This requires changes SetShouldSendAck
1325  // to be a no-arg method, and re-jiggering its implementation.
1326  bool send_feedback = false;
1327  if (congestion_manager_.GenerateCongestionFeedback(
1328          &outgoing_congestion_feedback_)) {
1329    DVLOG(1) << ENDPOINT << "Sending feedback "
1330             << outgoing_congestion_feedback_;
1331    send_feedback = true;
1332  }
1333
1334  packet_generator_.SetShouldSendAck(send_feedback);
1335}
1336
1337void QuicConnection::MaybeAbandonFecPacket(
1338    QuicPacketSequenceNumber sequence_number) {
1339  if (!ContainsKey(unacked_fec_packets_, sequence_number)) {
1340    DVLOG(2) << ENDPOINT << "no need to abandon fec packet: "
1341             << sequence_number << "; it's already acked'";
1342    return;
1343  }
1344  congestion_manager_.AbandoningPacket(sequence_number);
1345  // TODO(satyashekhar): Should this decrease the congestion window?
1346}
1347
1348QuicTime QuicConnection::OnRetransmissionTimeout() {
1349  // This guards against registering the alarm later than we should.
1350  //
1351  // If we have packet A and B in the list and we call
1352  // MaybeRetransmitPacketForRTO on A, that may trigger a call to
1353  // SetRetransmissionAlarm if A is retransmitted as C.  In that case we
1354  // don't want to register the alarm under SetRetransmissionAlarm; we
1355  // want to set it to the RTO of B when we return from this function.
1356  handling_retransmission_timeout_ = true;
1357
1358  for (size_t i = 0; i < max_packets_per_retransmission_alarm_ &&
1359           !retransmission_timeouts_.empty(); ++i) {
1360    RetransmissionTime retransmission_time = retransmission_timeouts_.top();
1361    DCHECK(retransmission_time.scheduled_time.IsInitialized());
1362    if (retransmission_time.scheduled_time > clock_->ApproximateNow()) {
1363      break;
1364    }
1365    retransmission_timeouts_.pop();
1366
1367    if (retransmission_time.for_fec) {
1368      MaybeAbandonFecPacket(retransmission_time.sequence_number);
1369      continue;
1370    } else if (
1371        !MaybeRetransmitPacketForRTO(retransmission_time.sequence_number)) {
1372      DLOG(INFO) << ENDPOINT << "MaybeRetransmitPacketForRTO failed: "
1373                 << "adding an extra delay for "
1374                 << retransmission_time.sequence_number;
1375      retransmission_time.scheduled_time = clock_->ApproximateNow().Add(
1376          congestion_manager_.DefaultRetransmissionTime());
1377      retransmission_timeouts_.push(retransmission_time);
1378    }
1379  }
1380
1381  handling_retransmission_timeout_ = false;
1382
1383  if (retransmission_timeouts_.empty()) {
1384    return QuicTime::Zero();
1385  }
1386
1387  // We have packets remaining.  Return the absolute RTO of the oldest packet
1388  // on the list.
1389  return retransmission_timeouts_.top().scheduled_time;
1390}
1391
1392void QuicConnection::SetEncrypter(EncryptionLevel level,
1393                                  QuicEncrypter* encrypter) {
1394  framer_.SetEncrypter(level, encrypter);
1395}
1396
1397const QuicEncrypter* QuicConnection::encrypter(EncryptionLevel level) const {
1398  return framer_.encrypter(level);
1399}
1400
1401void QuicConnection::SetDefaultEncryptionLevel(
1402    EncryptionLevel level) {
1403  encryption_level_ = level;
1404}
1405
1406void QuicConnection::SetDecrypter(QuicDecrypter* decrypter) {
1407  framer_.SetDecrypter(decrypter);
1408}
1409
1410void QuicConnection::SetAlternativeDecrypter(QuicDecrypter* decrypter,
1411                                             bool latch_once_used) {
1412  framer_.SetAlternativeDecrypter(decrypter, latch_once_used);
1413}
1414
1415const QuicDecrypter* QuicConnection::decrypter() const {
1416  return framer_.decrypter();
1417}
1418
1419const QuicDecrypter* QuicConnection::alternative_decrypter() const {
1420  return framer_.alternative_decrypter();
1421}
1422
1423void QuicConnection::QueueUndecryptablePacket(
1424    const QuicEncryptedPacket& packet) {
1425  DVLOG(1) << ENDPOINT << "Queueing undecryptable packet.";
1426  char* data = new char[packet.length()];
1427  memcpy(data, packet.data(), packet.length());
1428  undecryptable_packets_.push_back(
1429      new QuicEncryptedPacket(data, packet.length(), true));
1430}
1431
1432void QuicConnection::MaybeProcessUndecryptablePackets() {
1433  if (undecryptable_packets_.empty() ||
1434      encryption_level_ == ENCRYPTION_NONE) {
1435    return;
1436  }
1437
1438  while (connected_ && !undecryptable_packets_.empty()) {
1439    DVLOG(1) << ENDPOINT << "Attempting to process undecryptable packet";
1440    QuicEncryptedPacket* packet = undecryptable_packets_.front();
1441    if (!framer_.ProcessPacket(*packet) &&
1442        framer_.error() == QUIC_DECRYPTION_FAILURE) {
1443      DVLOG(1) << ENDPOINT << "Unable to process undecryptable packet...";
1444      break;
1445    }
1446    DVLOG(1) << ENDPOINT << "Processed undecryptable packet!";
1447    delete packet;
1448    undecryptable_packets_.pop_front();
1449  }
1450
1451  // Once forward secure encryption is in use, there will be no
1452  // new keys installed and hence any undecryptable packets will
1453  // never be able to be decrypted.
1454  if (encryption_level_ == ENCRYPTION_FORWARD_SECURE) {
1455    STLDeleteElements(&undecryptable_packets_);
1456  }
1457}
1458
1459void QuicConnection::MaybeProcessRevivedPacket() {
1460  QuicFecGroup* group = GetFecGroup();
1461  if (!connected_ || group == NULL || !group->CanRevive()) {
1462    return;
1463  }
1464  QuicPacketHeader revived_header;
1465  char revived_payload[kMaxPacketSize];
1466  size_t len = group->Revive(&revived_header, revived_payload, kMaxPacketSize);
1467  revived_header.public_header.guid = guid_;
1468  revived_header.public_header.version_flag = false;
1469  revived_header.public_header.reset_flag = false;
1470  revived_header.fec_flag = false;
1471  revived_header.is_in_fec_group = NOT_IN_FEC_GROUP;
1472  revived_header.fec_group = 0;
1473  group_map_.erase(last_header_.fec_group);
1474  delete group;
1475
1476  last_packet_revived_ = true;
1477  if (debug_visitor_) {
1478    debug_visitor_->OnRevivedPacket(revived_header,
1479                                    StringPiece(revived_payload, len));
1480  }
1481
1482  ++stats_.packets_revived;
1483  framer_.ProcessRevivedPacket(&revived_header,
1484                               StringPiece(revived_payload, len));
1485}
1486
1487QuicFecGroup* QuicConnection::GetFecGroup() {
1488  QuicFecGroupNumber fec_group_num = last_header_.fec_group;
1489  if (fec_group_num == 0) {
1490    return NULL;
1491  }
1492  if (group_map_.count(fec_group_num) == 0) {
1493    if (group_map_.size() >= kMaxFecGroups) {  // Too many groups
1494      if (fec_group_num < group_map_.begin()->first) {
1495        // The group being requested is a group we've seen before and deleted.
1496        // Don't recreate it.
1497        return NULL;
1498      }
1499      // Clear the lowest group number.
1500      delete group_map_.begin()->second;
1501      group_map_.erase(group_map_.begin());
1502    }
1503    group_map_[fec_group_num] = new QuicFecGroup();
1504  }
1505  return group_map_[fec_group_num];
1506}
1507
1508void QuicConnection::SendConnectionClose(QuicErrorCode error) {
1509  SendConnectionCloseWithDetails(error, string());
1510}
1511
1512void QuicConnection::SendConnectionClosePacket(QuicErrorCode error,
1513                                               const string& details) {
1514  DLOG(INFO) << ENDPOINT << "Force closing with error "
1515             << QuicUtils::ErrorToString(error) << " (" << error << ") "
1516             << details;
1517  QuicConnectionCloseFrame frame;
1518  frame.error_code = error;
1519  frame.error_details = details;
1520  UpdateSentPacketInfo(&frame.ack_frame.sent_info);
1521  received_packet_manager_.UpdateReceivedPacketInfo(
1522      &frame.ack_frame.received_info, clock_->ApproximateNow());
1523
1524  SerializedPacket serialized_packet =
1525      packet_creator_.SerializeConnectionClose(&frame);
1526
1527  // We need to update the sent entropy hash for all sent packets.
1528  sent_entropy_manager_.RecordPacketEntropyHash(
1529      serialized_packet.sequence_number,
1530      serialized_packet.entropy_hash);
1531
1532  if (!WritePacket(encryption_level_,
1533                   serialized_packet.sequence_number,
1534                   serialized_packet.packet,
1535                   serialized_packet.retransmittable_frames != NULL ?
1536                       HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA,
1537                   FORCE)) {
1538    delete serialized_packet.packet;
1539  }
1540}
1541
1542void QuicConnection::SendConnectionCloseWithDetails(QuicErrorCode error,
1543                                                    const string& details) {
1544  if (!write_blocked_) {
1545    SendConnectionClosePacket(error, details);
1546  }
1547  CloseConnection(error, false);
1548}
1549
1550void QuicConnection::CloseConnection(QuicErrorCode error, bool from_peer) {
1551  DCHECK(connected_);
1552  connected_ = false;
1553  visitor_->ConnectionClose(error, from_peer);
1554}
1555
1556void QuicConnection::SendGoAway(QuicErrorCode error,
1557                                QuicStreamId last_good_stream_id,
1558                                const string& reason) {
1559  DLOG(INFO) << ENDPOINT << "Going away with error "
1560             << QuicUtils::ErrorToString(error)
1561             << " (" << error << ")";
1562  packet_generator_.AddControlFrame(
1563      QuicFrame(new QuicGoAwayFrame(error, last_good_stream_id, reason)));
1564}
1565
1566void QuicConnection::CloseFecGroupsBefore(
1567    QuicPacketSequenceNumber sequence_number) {
1568  FecGroupMap::iterator it = group_map_.begin();
1569  while (it != group_map_.end()) {
1570    // If this is the current group or the group doesn't protect this packet
1571    // we can ignore it.
1572    if (last_header_.fec_group == it->first ||
1573        !it->second->ProtectsPacketsBefore(sequence_number)) {
1574      ++it;
1575      continue;
1576    }
1577    QuicFecGroup* fec_group = it->second;
1578    DCHECK(!fec_group->CanRevive());
1579    FecGroupMap::iterator next = it;
1580    ++next;
1581    group_map_.erase(it);
1582    delete fec_group;
1583    it = next;
1584  }
1585}
1586
1587bool QuicConnection::HasQueuedData() const {
1588  return !queued_packets_.empty() || packet_generator_.HasQueuedFrames();
1589}
1590
1591void QuicConnection::SetIdleNetworkTimeout(QuicTime::Delta timeout) {
1592  if (timeout < idle_network_timeout_) {
1593    idle_network_timeout_ = timeout;
1594    CheckForTimeout();
1595  } else {
1596     idle_network_timeout_ = timeout;
1597  }
1598}
1599
1600void QuicConnection::SetOverallConnectionTimeout(QuicTime::Delta timeout) {
1601  if (timeout < overall_connection_timeout_) {
1602    overall_connection_timeout_ = timeout;
1603    CheckForTimeout();
1604  } else {
1605    overall_connection_timeout_ = timeout;
1606  }
1607}
1608
1609bool QuicConnection::CheckForTimeout() {
1610  QuicTime now = clock_->ApproximateNow();
1611  QuicTime time_of_last_packet = std::max(time_of_last_received_packet_,
1612                                          time_of_last_sent_packet_);
1613
1614  // |delta| can be < 0 as |now| is approximate time but |time_of_last_packet|
1615  // is accurate time. However, this should not change the behavior of
1616  // timeout handling.
1617  QuicTime::Delta delta = now.Subtract(time_of_last_packet);
1618  DVLOG(1) << ENDPOINT << "last packet "
1619           << time_of_last_packet.ToDebuggingValue()
1620           << " now:" << now.ToDebuggingValue()
1621           << " delta:" << delta.ToMicroseconds()
1622           << " network_timeout: " << idle_network_timeout_.ToMicroseconds();
1623  if (delta >= idle_network_timeout_) {
1624    DVLOG(1) << ENDPOINT << "Connection timedout due to no network activity.";
1625    SendConnectionClose(QUIC_CONNECTION_TIMED_OUT);
1626    return true;
1627  }
1628
1629  // Next timeout delta.
1630  QuicTime::Delta timeout = idle_network_timeout_.Subtract(delta);
1631
1632  if (!overall_connection_timeout_.IsInfinite()) {
1633    QuicTime::Delta connected_time = now.Subtract(creation_time_);
1634    DVLOG(1) << ENDPOINT << "connection time: "
1635             << connected_time.ToMilliseconds() << " overall timeout: "
1636             << overall_connection_timeout_.ToMilliseconds();
1637    if (connected_time >= overall_connection_timeout_) {
1638      DVLOG(1) << ENDPOINT <<
1639          "Connection timedout due to overall connection timeout.";
1640      SendConnectionClose(QUIC_CONNECTION_TIMED_OUT);
1641      return true;
1642    }
1643
1644    // Take the min timeout.
1645    QuicTime::Delta connection_timeout =
1646        overall_connection_timeout_.Subtract(connected_time);
1647    if (connection_timeout < timeout) {
1648      timeout = connection_timeout;
1649    }
1650  }
1651
1652  timeout_alarm_->Cancel();
1653  timeout_alarm_->Set(clock_->ApproximateNow().Add(timeout));
1654  return false;
1655}
1656
1657}  // namespace net
1658