Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(96)

Side by Side Diff: net/quic/quic_received_packet_manager.cc

Issue 496133002: Optimize QUIC's EntropyTracker in QuicReceivedPacketManager by using a (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@enable_pacing_via_config_73685838
Patch Set: Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « net/quic/quic_received_packet_manager.h ('k') | net/quic/quic_received_packet_manager_test.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
OLDNEW
« no previous file with comments | « net/quic/quic_received_packet_manager.h ('k') | net/quic/quic_received_packet_manager_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698