OLD | NEW |
1 // Copyright 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/quic_received_packet_manager.h" | 5 #include "net/quic/quic_received_packet_manager.h" |
6 | 6 |
7 #include "base/logging.h" | 7 #include "base/logging.h" |
8 #include "base/stl_util.h" | 8 #include "base/stl_util.h" |
9 #include "net/base/linked_hash_map.h" | 9 #include "net/base/linked_hash_map.h" |
10 #include "net/quic/quic_connection_stats.h" | 10 #include "net/quic/quic_connection_stats.h" |
(...skipping 24 matching lines...) Expand all Loading... |
35 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {} | 35 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {} |
36 | 36 |
37 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash( | 37 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash( |
38 QuicPacketSequenceNumber sequence_number) const { | 38 QuicPacketSequenceNumber sequence_number) const { |
39 DCHECK_LE(sequence_number, largest_observed_); | 39 DCHECK_LE(sequence_number, largest_observed_); |
40 if (sequence_number == largest_observed_) { | 40 if (sequence_number == largest_observed_) { |
41 return packets_entropy_hash_; | 41 return packets_entropy_hash_; |
42 } | 42 } |
43 | 43 |
44 DCHECK_GE(sequence_number, first_gap_); | 44 DCHECK_GE(sequence_number, first_gap_); |
45 ReceivedEntropyMap::const_iterator it = | 45 DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_); |
46 packets_entropy_.upper_bound(sequence_number); | |
47 // When this map is empty we should only query entropy for | |
48 // largest_observed_, since no other entropy can be correctly | |
49 // calculated, because we're not storing the entropy for any prior packets. | |
50 // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium. | |
51 // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10) | |
52 LOG_IF(DFATAL, it == packets_entropy_.end()) | |
53 << "EntropyHash may be unknown. largest_received: " | |
54 << largest_observed_ | |
55 << " sequence_number: " << sequence_number; | |
56 | |
57 // TODO(satyamshekhar): Make this O(1). | |
58 QuicPacketEntropyHash hash = packets_entropy_hash_; | 46 QuicPacketEntropyHash hash = packets_entropy_hash_; |
59 for (; it != packets_entropy_.end(); ++it) { | 47 ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin(); |
60 hash ^= it->second; | 48 for (QuicPacketSequenceNumber i = 0; |
| 49 i < (largest_observed_ - sequence_number); ++i, ++it) { |
| 50 hash ^= it->first; |
61 } | 51 } |
62 return hash; | 52 return hash; |
63 } | 53 } |
64 | 54 |
65 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash( | 55 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash( |
66 QuicPacketSequenceNumber sequence_number, | 56 QuicPacketSequenceNumber sequence_number, |
67 QuicPacketEntropyHash entropy_hash) { | 57 QuicPacketEntropyHash entropy_hash) { |
68 if (sequence_number < first_gap_) { | 58 if (sequence_number < first_gap_) { |
69 DVLOG(1) << "Ignoring received packet entropy for sequence_number:" | 59 DVLOG(1) << "Ignoring received packet entropy for sequence_number:" |
70 << sequence_number << " less than largest_peer_sequence_number:" | 60 << sequence_number << " less than largest_peer_sequence_number:" |
71 << first_gap_; | 61 << first_gap_; |
72 return; | 62 return; |
73 } | 63 } |
| 64 // RecordPacketEntropyHash is only intended to be called once per packet. |
| 65 DCHECK(sequence_number > largest_observed_ || |
| 66 !packets_entropy_[sequence_number - first_gap_].second); |
74 | 67 |
| 68 packets_entropy_hash_ ^= entropy_hash; |
| 69 |
| 70 // Optimize the typical case of no gaps. |
| 71 if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) { |
| 72 ++first_gap_; |
| 73 largest_observed_ = sequence_number; |
| 74 return; |
| 75 } |
75 if (sequence_number > largest_observed_) { | 76 if (sequence_number > largest_observed_) { |
| 77 for (QuicPacketSequenceNumber i = 0; |
| 78 i < (sequence_number - largest_observed_ - 1); ++i) { |
| 79 packets_entropy_.push_back(make_pair(0, false)); |
| 80 } |
| 81 packets_entropy_.push_back(make_pair(entropy_hash, true)); |
76 largest_observed_ = sequence_number; | 82 largest_observed_ = sequence_number; |
| 83 } else { |
| 84 packets_entropy_[sequence_number - first_gap_] = |
| 85 make_pair(entropy_hash, true); |
| 86 AdvanceFirstGapAndGarbageCollectEntropyMap(); |
77 } | 87 } |
78 | 88 |
79 packets_entropy_hash_ ^= entropy_hash; | |
80 DVLOG(2) << "setting cumulative received entropy hash to: " | 89 DVLOG(2) << "setting cumulative received entropy hash to: " |
81 << static_cast<int>(packets_entropy_hash_) | 90 << static_cast<int>(packets_entropy_hash_) |
82 << " updated with sequence number " << sequence_number | 91 << " updated with sequence number " << sequence_number |
83 << " entropy hash: " << static_cast<int>(entropy_hash); | 92 << " entropy hash: " << static_cast<int>(entropy_hash); |
84 | |
85 packets_entropy_.insert(make_pair(sequence_number, entropy_hash)); | |
86 AdvanceFirstGapAndGarbageCollectEntropyMap(); | |
87 } | 93 } |
88 | 94 |
89 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo( | 95 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo( |
90 QuicPacketSequenceNumber sequence_number, | 96 QuicPacketSequenceNumber sequence_number, |
91 QuicPacketEntropyHash entropy_hash) { | 97 QuicPacketEntropyHash entropy_hash) { |
92 DCHECK_LE(sequence_number, largest_observed_); | 98 DCHECK_LE(sequence_number, largest_observed_); |
93 if (sequence_number < first_gap_) { | 99 if (sequence_number < first_gap_) { |
94 DVLOG(1) << "Ignoring set entropy at:" << sequence_number | 100 DVLOG(1) << "Ignoring set entropy at:" << sequence_number |
95 << " less than first_gap_:" << first_gap_; | 101 << " less than first_gap_:" << first_gap_; |
96 return; | 102 return; |
97 } | 103 } |
98 // Compute the current entropy based on the hash. | 104 while (first_gap_ < sequence_number) { |
| 105 ++first_gap_; |
| 106 if (!packets_entropy_.empty()) { |
| 107 packets_entropy_.pop_front(); |
| 108 } |
| 109 } |
| 110 // Compute the current entropy by XORing in all entropies received including |
| 111 // and since sequence_number. |
99 packets_entropy_hash_ = entropy_hash; | 112 packets_entropy_hash_ = entropy_hash; |
100 ReceivedEntropyMap::iterator it = | 113 for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin(); |
101 packets_entropy_.lower_bound(sequence_number); | 114 it != packets_entropy_.end(); ++it) { |
102 // TODO(satyamshekhar): Make this O(1). | 115 packets_entropy_hash_ ^= it->first; |
103 for (; it != packets_entropy_.end(); ++it) { | |
104 packets_entropy_hash_ ^= it->second; | |
105 } | 116 } |
106 // Update first_gap_ and discard old entropies. | |
107 first_gap_ = sequence_number; | |
108 packets_entropy_.erase( | |
109 packets_entropy_.begin(), | |
110 packets_entropy_.lower_bound(sequence_number)); | |
111 | 117 |
112 // Garbage collect entries from the beginning of the map. | 118 // Garbage collect entries from the beginning of the map. |
113 AdvanceFirstGapAndGarbageCollectEntropyMap(); | 119 AdvanceFirstGapAndGarbageCollectEntropyMap(); |
114 } | 120 } |
115 | 121 |
116 void QuicReceivedPacketManager::EntropyTracker:: | 122 void QuicReceivedPacketManager::EntropyTracker:: |
117 AdvanceFirstGapAndGarbageCollectEntropyMap() { | 123 AdvanceFirstGapAndGarbageCollectEntropyMap() { |
118 while (!packets_entropy_.empty()) { | 124 while (!packets_entropy_.empty() && packets_entropy_.front().second) { |
119 ReceivedEntropyMap::iterator it = packets_entropy_.begin(); | |
120 if (it->first != first_gap_) { | |
121 DCHECK_GT(it->first, first_gap_); | |
122 break; | |
123 } | |
124 packets_entropy_.erase(it); | |
125 ++first_gap_; | 125 ++first_gap_; |
| 126 packets_entropy_.pop_front(); |
126 } | 127 } |
127 } | 128 } |
128 | 129 |
129 QuicReceivedPacketManager::QuicReceivedPacketManager( | 130 QuicReceivedPacketManager::QuicReceivedPacketManager( |
130 CongestionFeedbackType congestion_type, | 131 CongestionFeedbackType congestion_type, |
131 QuicConnectionStats* stats) | 132 QuicConnectionStats* stats) |
132 : peer_least_packet_awaiting_ack_(0), | 133 : peer_least_packet_awaiting_ack_(0), |
133 time_largest_observed_(QuicTime::Zero()), | 134 time_largest_observed_(QuicTime::Zero()), |
134 receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)), | 135 receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)), |
135 stats_(stats) { | 136 stats_(stats) { |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
252 entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked, | 253 entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked, |
253 stop_waiting.entropy_hash); | 254 stop_waiting.entropy_hash); |
254 } | 255 } |
255 peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked; | 256 peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked; |
256 } | 257 } |
257 DCHECK(ack_frame_.missing_packets.empty() || | 258 DCHECK(ack_frame_.missing_packets.empty() || |
258 *ack_frame_.missing_packets.begin() >= | 259 *ack_frame_.missing_packets.begin() >= |
259 peer_least_packet_awaiting_ack_); | 260 peer_least_packet_awaiting_ack_); |
260 } | 261 } |
261 | 262 |
262 bool QuicReceivedPacketManager::HasMissingPackets() { | |
263 return !ack_frame_.missing_packets.empty(); | |
264 } | |
265 | |
266 bool QuicReceivedPacketManager::HasNewMissingPackets() { | 263 bool QuicReceivedPacketManager::HasNewMissingPackets() { |
267 return HasMissingPackets() && | 264 return !ack_frame_.missing_packets.empty() && |
268 (ack_frame_.largest_observed - | 265 (ack_frame_.largest_observed - |
269 *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing; | 266 *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing; |
270 } | 267 } |
271 | 268 |
272 } // namespace net | 269 } // namespace net |
OLD | NEW |