1 files changed, 188 insertions, 0 deletions
diff --git a/net/quic/quic_received_packet_manager.cc b/net/quic/quic_received_packet_manager.cc
index e69de29..f6f94cc 100644
--- a/net/quic/quic_received_packet_manager.cc
+++ b/net/quic/quic_received_packet_manager.cc
@@ -0,0 +1,188 @@
+// Copyright 2013 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_received_packet_manager.h"
+
+#include "base/logging.h"
+#include "net/base/linked_hash_map.h"
+
+using std::make_pair;
+using std::max;
+using std::min;
+
+namespace net {
+
+QuicReceivedPacketManager::QuicReceivedPacketManager()
+    : packets_entropy_hash_(0),
+      largest_sequence_number_(0),
+      peer_largest_observed_packet_(0),
+      least_packet_awaited_by_peer_(1),
+      peer_least_packet_awaiting_ack_(0),
+      time_largest_observed_(QuicTime::Zero()) {
+  received_info_.largest_observed = 0;
+  received_info_.entropy_hash = 0;
+}
+
+QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
+
+void QuicReceivedPacketManager::RecordPacketReceived(
+    const QuicPacketHeader& header, QuicTime receipt_time) {
+  QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
+  DCHECK(IsAwaitingPacket(sequence_number));
+
+  InsertMissingPacketsBetween(
+      &received_info_,
+      max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
+      header.packet_sequence_number);
+
+  if (received_info_.largest_observed > header.packet_sequence_number) {
+    // 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";
+    received_info_.missing_packets.erase(sequence_number);
+  }
+  if (header.packet_sequence_number > received_info_.largest_observed) {
+    received_info_.largest_observed = header.packet_sequence_number;
+    time_largest_observed_ = receipt_time;
+  }
+  RecordPacketEntropyHash(sequence_number, header.entropy_hash);
+}
+
+bool QuicReceivedPacketManager::IsAwaitingPacket(
+    QuicPacketSequenceNumber sequence_number) {
+  return ::net::IsAwaitingPacket(received_info_, sequence_number);
+}
+
+void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
+    ReceivedPacketInfo* received_info, QuicTime approximate_now) {
+  *received_info = received_info_;
+  received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
+  if (time_largest_observed_ == QuicTime::Zero()) {
+    // We have not received any new higher sequence numbers since we sent our
+    // last ACK.
+    received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
+  } else {
+    received_info->delta_time_largest_observed =
+        approximate_now.Subtract(time_largest_observed_);
+
+    time_largest_observed_ = QuicTime::Zero();
+  }
+}
+
+void QuicReceivedPacketManager::RecordPacketEntropyHash(
+    QuicPacketSequenceNumber sequence_number,
+    QuicPacketEntropyHash entropy_hash) {
+  if (sequence_number < largest_sequence_number_) {
+    DLOG(INFO) << "Ignoring received packet entropy for sequence_number:"
+               << sequence_number << " less than largest_peer_sequence_number:"
+               << largest_sequence_number_;
+    return;
+  }
+  packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
+  packets_entropy_hash_ ^= entropy_hash;
+  DVLOG(2) << "setting cumulative received entropy hash to: "
+           << static_cast<int>(packets_entropy_hash_)
+           << " updated with sequence number " << sequence_number
+           << " entropy hash: " << static_cast<int>(entropy_hash);
+}
+
+QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
+    QuicPacketSequenceNumber sequence_number) const {
+  DCHECK_LE(sequence_number, received_info_.largest_observed);
+  DCHECK_GE(sequence_number, largest_sequence_number_);
+  if (sequence_number == received_info_.largest_observed) {
+    return packets_entropy_hash_;
+  }
+
+  ReceivedEntropyMap::const_iterator it =
+      packets_entropy_.upper_bound(sequence_number);
+  // When this map is empty we should only query entropy for
+  // |largest_received_sequence_number_|.
+  LOG_IF(WARNING, it != packets_entropy_.end())
+      << "largest_received: " << received_info_.largest_observed
+      << " sequence_number: " << sequence_number;
+
+  // TODO(satyamshekhar): Make this O(1).
+  QuicPacketEntropyHash hash = packets_entropy_hash_;
+  for (; it != packets_entropy_.end(); ++it) {
+    hash ^= it->second;
+  }
+  return hash;
+}
+
+void QuicReceivedPacketManager::RecalculateEntropyHash(
+    QuicPacketSequenceNumber peer_least_unacked,
+    QuicPacketEntropyHash entropy_hash) {
+  DLOG_IF(WARNING, peer_least_unacked > received_info_.largest_observed)
+      << "Prematurely updating the entropy manager before registering the "
+      << "entropy of the containing packet creates a temporary inconsistency.";
+  if (peer_least_unacked < largest_sequence_number_) {
+    DLOG(INFO) << "Ignoring received peer_least_unacked:" << peer_least_unacked
+               << " less than largest_peer_sequence_number:"
+               << largest_sequence_number_;
+    return;
+  }
+  largest_sequence_number_ = peer_least_unacked;
+  packets_entropy_hash_ = entropy_hash;
+  ReceivedEntropyMap::iterator it =
+      packets_entropy_.lower_bound(peer_least_unacked);
+  // TODO(satyamshekhar): Make this O(1).
+  for (; it != packets_entropy_.end(); ++it) {
+    packets_entropy_hash_ ^= it->second;
+  }
+  // Discard entropies before least unacked.
+  packets_entropy_.erase(
+      packets_entropy_.begin(),
+      packets_entropy_.lower_bound(
+          min(peer_least_unacked, received_info_.largest_observed)));
+}
+
+void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
+    const QuicAckFrame& incoming_ack) {
+  // ValidateAck should fail if largest_observed ever shrinks.
+  DCHECK_LE(peer_largest_observed_packet_,
+            incoming_ack.received_info.largest_observed);
+  peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed;
+
+  if (incoming_ack.received_info.missing_packets.empty()) {
+    least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
+  } else {
+    least_packet_awaited_by_peer_ =
+        *(incoming_ack.received_info.missing_packets.begin());
+  }
+}
+
+bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
+    QuicPacketSequenceNumber least_unacked) {
+  size_t missing_packets_count = received_info_.missing_packets.size();
+  received_info_.missing_packets.erase(
+      received_info_.missing_packets.begin(),
+      received_info_.missing_packets.lower_bound(least_unacked));
+  return missing_packets_count != received_info_.missing_packets.size();
+}
+
+void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
+    const QuicAckFrame& incoming_ack) {
+  // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
+  DCHECK_LE(peer_least_packet_awaiting_ack_,
+            incoming_ack.sent_info.least_unacked);
+  if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) {
+    bool missed_packets =
+        DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked);
+    if (missed_packets || incoming_ack.sent_info.least_unacked >
+            received_info_.largest_observed + 1) {
+      DVLOG(1) << "Updating entropy hashed since we missed packets";
+      // There were some missing packets that we won't ever get now. Recalculate
+      // the received entropy hash.
+      RecalculateEntropyHash(incoming_ack.sent_info.least_unacked,
+                             incoming_ack.sent_info.entropy_hash);
+    }
+    peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
+  }
+  DCHECK(received_info_.missing_packets.empty() ||
+         *received_info_.missing_packets.begin() >=
+             peer_least_packet_awaiting_ack_);
+}
+
+}  // namespace net