Roll src/third_party/skia 5cc0f6c:01d3319
[chromium-blink-merge.git] / net / quic / quic_received_packet_manager.cc
blobf5e2c36e8838fb9a9531035cf12969d451c474ba
1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "net/quic/quic_received_packet_manager.h"
7 #include <limits>
8 #include <utility>
10 #include "base/logging.h"
11 #include "base/stl_util.h"
12 #include "net/base/linked_hash_map.h"
13 #include "net/quic/crypto/crypto_protocol.h"
14 #include "net/quic/quic_connection_stats.h"
16 using std::make_pair;
17 using std::max;
18 using std::min;
19 using std::numeric_limits;
21 namespace net {
23 namespace {
25 // The maximum number of packets to ack immediately after a missing packet for
26 // fast retransmission to kick in at the sender. This limit is created to
27 // reduce the number of acks sent that have no benefit for fast retransmission.
28 // Set to the number of nacks needed for fast retransmit plus one for protection
29 // against an ack loss
30 const size_t kMaxPacketsAfterNewMissing = 4;
34 QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
35 : packets_entropy_hash_(0),
36 first_gap_(1),
37 largest_observed_(0) {
40 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
42 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
43 QuicPacketSequenceNumber sequence_number) const {
44 DCHECK_LE(sequence_number, largest_observed_);
45 if (sequence_number == largest_observed_) {
46 return packets_entropy_hash_;
49 DCHECK_GE(sequence_number, first_gap_);
50 DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
51 QuicPacketEntropyHash hash = packets_entropy_hash_;
52 ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
53 for (QuicPacketSequenceNumber i = 0;
54 i < (largest_observed_ - sequence_number); ++i, ++it) {
55 hash ^= it->first;
57 return hash;
60 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
61 QuicPacketSequenceNumber sequence_number,
62 QuicPacketEntropyHash entropy_hash) {
63 if (sequence_number < first_gap_) {
64 DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
65 << sequence_number << " less than largest_peer_sequence_number:"
66 << first_gap_;
67 return;
69 // RecordPacketEntropyHash is only intended to be called once per packet.
70 DCHECK(sequence_number > largest_observed_ ||
71 !packets_entropy_[sequence_number - first_gap_].second);
73 packets_entropy_hash_ ^= entropy_hash;
75 // Optimize the typical case of no gaps.
76 if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
77 ++first_gap_;
78 largest_observed_ = sequence_number;
79 return;
81 if (sequence_number > largest_observed_) {
82 for (QuicPacketSequenceNumber i = 0;
83 i < (sequence_number - largest_observed_ - 1); ++i) {
84 packets_entropy_.push_back(make_pair(0, false));
86 packets_entropy_.push_back(make_pair(entropy_hash, true));
87 largest_observed_ = sequence_number;
88 } else {
89 packets_entropy_[sequence_number - first_gap_] =
90 make_pair(entropy_hash, true);
91 AdvanceFirstGapAndGarbageCollectEntropyMap();
94 DVLOG(2) << "setting cumulative received entropy hash to: "
95 << static_cast<int>(packets_entropy_hash_)
96 << " updated with sequence number " << sequence_number
97 << " entropy hash: " << static_cast<int>(entropy_hash);
100 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
101 QuicPacketSequenceNumber sequence_number,
102 QuicPacketEntropyHash entropy_hash) {
103 DCHECK_LE(sequence_number, largest_observed_);
104 if (sequence_number < first_gap_) {
105 DVLOG(1) << "Ignoring set entropy at:" << sequence_number
106 << " less than first_gap_:" << first_gap_;
107 return;
109 while (first_gap_ < sequence_number) {
110 ++first_gap_;
111 if (!packets_entropy_.empty()) {
112 packets_entropy_.pop_front();
115 // Compute the current entropy by XORing in all entropies received including
116 // and since sequence_number.
117 packets_entropy_hash_ = entropy_hash;
118 for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
119 it != packets_entropy_.end(); ++it) {
120 packets_entropy_hash_ ^= it->first;
123 // Garbage collect entries from the beginning of the map.
124 AdvanceFirstGapAndGarbageCollectEntropyMap();
127 void QuicReceivedPacketManager::EntropyTracker::
128 AdvanceFirstGapAndGarbageCollectEntropyMap() {
129 while (!packets_entropy_.empty() && packets_entropy_.front().second) {
130 ++first_gap_;
131 packets_entropy_.pop_front();
135 QuicReceivedPacketManager::QuicReceivedPacketManager(QuicConnectionStats* stats)
136 : peer_least_packet_awaiting_ack_(0),
137 time_largest_observed_(QuicTime::Zero()),
138 stats_(stats) {
139 ack_frame_.largest_observed = 0;
140 ack_frame_.entropy_hash = 0;
143 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
145 void QuicReceivedPacketManager::RecordPacketReceived(
146 QuicByteCount bytes,
147 const QuicPacketHeader& header,
148 QuicTime receipt_time) {
149 QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
150 DCHECK(IsAwaitingPacket(sequence_number));
152 InsertMissingPacketsBetween(
153 &ack_frame_,
154 max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_),
155 sequence_number);
157 if (ack_frame_.largest_observed > sequence_number) {
158 // We've gotten one of the out of order packets - remove it from our
159 // "missing packets" list.
160 DVLOG(1) << "Removing " << sequence_number << " from missing list";
161 ack_frame_.missing_packets.erase(sequence_number);
163 // Record how out of order stats.
164 ++stats_->packets_reordered;
165 stats_->max_sequence_reordering =
166 max(stats_->max_sequence_reordering,
167 ack_frame_.largest_observed - sequence_number);
168 int64 reordering_time_us =
169 receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
170 stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
171 reordering_time_us);
173 if (sequence_number > ack_frame_.largest_observed) {
174 ack_frame_.largest_observed = sequence_number;
175 time_largest_observed_ = receipt_time;
177 entropy_tracker_.RecordPacketEntropyHash(sequence_number,
178 header.entropy_hash);
180 received_packet_times_.push_back(
181 std::make_pair(sequence_number, receipt_time));
183 ack_frame_.revived_packets.erase(sequence_number);
186 void QuicReceivedPacketManager::RecordPacketRevived(
187 QuicPacketSequenceNumber sequence_number) {
188 LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
189 ack_frame_.revived_packets.insert(sequence_number);
192 bool QuicReceivedPacketManager::IsMissing(
193 QuicPacketSequenceNumber sequence_number) {
194 return ContainsKey(ack_frame_.missing_packets, sequence_number);
197 bool QuicReceivedPacketManager::IsAwaitingPacket(
198 QuicPacketSequenceNumber sequence_number) {
199 return ::net::IsAwaitingPacket(ack_frame_, sequence_number);
202 namespace {
203 struct isTooLarge {
204 explicit isTooLarge(QuicPacketSequenceNumber n) : largest_observed_(n) {}
205 QuicPacketSequenceNumber largest_observed_;
207 // Return true if the packet in p is too different from largest_observed_
208 // to express.
209 bool operator() (
210 const std::pair<QuicPacketSequenceNumber, QuicTime>& p) const {
211 return largest_observed_ - p.first >= numeric_limits<uint8>::max();
214 } // namespace
216 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
217 QuicAckFrame* ack_frame, QuicTime approximate_now) {
218 *ack_frame = ack_frame_;
219 ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
221 if (time_largest_observed_ == QuicTime::Zero()) {
222 // We have received no packets.
223 ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
224 return;
227 // Ensure the delta is zero if approximate now is "in the past".
228 ack_frame->delta_time_largest_observed =
229 approximate_now < time_largest_observed_ ?
230 QuicTime::Delta::Zero() :
231 approximate_now.Subtract(time_largest_observed_);
233 // Remove all packets that are too far from largest_observed to express.
234 received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
236 ack_frame->received_packet_times.clear();
237 ack_frame->received_packet_times.swap(received_packet_times_);
240 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
241 QuicPacketSequenceNumber sequence_number) const {
242 return entropy_tracker_.EntropyHash(sequence_number);
245 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
246 QuicPacketSequenceNumber least_unacked) {
247 ack_frame_.revived_packets.erase(
248 ack_frame_.revived_packets.begin(),
249 ack_frame_.revived_packets.lower_bound(least_unacked));
250 size_t missing_packets_count = ack_frame_.missing_packets.size();
251 ack_frame_.missing_packets.erase(
252 ack_frame_.missing_packets.begin(),
253 ack_frame_.missing_packets.lower_bound(least_unacked));
254 return missing_packets_count != ack_frame_.missing_packets.size();
257 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
258 const QuicStopWaitingFrame& stop_waiting) {
259 // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
260 DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
261 if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
262 bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
263 if (missed_packets) {
264 DVLOG(1) << "Updating entropy hashed since we missed packets";
265 // There were some missing packets that we won't ever get now. Recalculate
266 // the received entropy hash.
267 entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
268 stop_waiting.entropy_hash);
270 peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
272 DCHECK(ack_frame_.missing_packets.empty() ||
273 *ack_frame_.missing_packets.begin() >=
274 peer_least_packet_awaiting_ack_);
277 bool QuicReceivedPacketManager::HasNewMissingPackets() const {
278 return !ack_frame_.missing_packets.empty() &&
279 (ack_frame_.largest_observed -
280 *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
283 size_t QuicReceivedPacketManager::NumTrackedPackets() const {
284 return entropy_tracker_.size();
287 } // namespace net