1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
// 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(
CongestionFeedbackType congestion_type)
: 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()),
receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)) {
received_info_.largest_observed = 0;
received_info_.entropy_hash = 0;
}
QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
void QuicReceivedPacketManager::RecordPacketReceived(
QuicByteCount bytes,
const QuicPacketHeader& header,
QuicTime receipt_time,
bool revived) {
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);
// Don't update the receive algorithm for revived packets.
if (!revived) {
receive_algorithm_->RecordIncomingPacket(
bytes, sequence_number, receipt_time, revived);
}
}
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 received no packets.
received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
return;
}
if (approximate_now < time_largest_observed_) {
// Approximate now may well be "in the past".
received_info->delta_time_largest_observed = QuicTime::Delta::Zero();
return;
}
received_info->delta_time_largest_observed =
approximate_now.Subtract(time_largest_observed_);
}
void QuicReceivedPacketManager::RecordPacketEntropyHash(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
if (sequence_number < largest_sequence_number_) {
DVLOG(1) << "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);
}
bool QuicReceivedPacketManager::GenerateCongestionFeedback(
QuicCongestionFeedbackFrame* feedback) {
return receive_algorithm_->GenerateCongestionFeedback(feedback);
}
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
// received_info_.largest_observed, since no other entropy can be correctly
// calculated, because we're not storing the entropy for any prior packets.
// TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
// LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
LOG_IF(DFATAL, it == packets_entropy_.end())
<< "EntropyHash may be unknown. 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) {
DCHECK_LE(peer_least_unacked, received_info_.largest_observed);
if (peer_least_unacked < largest_sequence_number_) {
DVLOG(1) << "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_);
}
size_t QuicReceivedPacketManager::GetNumMissingPackets() {
return received_info_.missing_packets.size();
}
} // namespace net
|
