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
|
// Copyright (c) 2012 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_packet_entropy_manager.h"
#include "base/logging.h"
#include "net/base/linked_hash_map.h"
using std::make_pair;
using std::max;
namespace net {
QuicPacketEntropyManager::QuicPacketEntropyManager()
: sent_packets_entropy_hash_(0),
received_packets_entropy_hash_(0),
largest_received_sequence_number_(0) {}
QuicPacketEntropyManager::~QuicPacketEntropyManager() {}
void QuicPacketEntropyManager::RecordReceivedPacketEntropyHash(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
largest_received_sequence_number_ =
max<QuicPacketSequenceNumber>(largest_received_sequence_number_,
sequence_number);
received_packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
received_packets_entropy_hash_ ^= entropy_hash;
DVLOG(2) << "setting cumulative received entropy hash to: "
<< static_cast<int>(received_packets_entropy_hash_)
<< " updated with sequence number " << sequence_number
<< " entropy hash: " << static_cast<int>(entropy_hash);
}
void QuicPacketEntropyManager::RecordSentPacketEntropyHash(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
// TODO(satyamshekhar): Check this logic again when/if we enable packet
// reordering.
sent_packets_entropy_hash_ ^= entropy_hash;
sent_packets_entropy_.insert(
make_pair(sequence_number,
make_pair(entropy_hash, sent_packets_entropy_hash_)));
DVLOG(2) << "setting cumulative sent entropy hash to: "
<< static_cast<int>(sent_packets_entropy_hash_)
<< " updated with sequence number " << sequence_number
<< " entropy hash: " << static_cast<int>(entropy_hash);
}
QuicPacketEntropyHash QuicPacketEntropyManager::ReceivedEntropyHash(
QuicPacketSequenceNumber sequence_number) const {
if (sequence_number == largest_received_sequence_number_) {
return received_packets_entropy_hash_;
}
ReceivedEntropyMap::const_iterator it =
received_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 != received_packets_entropy_.end())
<< "largest_received: " << largest_received_sequence_number_
<< " sequence_number: " << sequence_number;
// TODO(satyamshekhar): Make this O(1).
QuicPacketEntropyHash hash = received_packets_entropy_hash_;
for (; it != received_packets_entropy_.end(); ++it) {
hash ^= it->second;
}
return hash;
}
QuicPacketEntropyHash QuicPacketEntropyManager::SentEntropyHash(
QuicPacketSequenceNumber sequence_number) const {
SentEntropyMap::const_iterator it =
sent_packets_entropy_.find(sequence_number);
if (it == sent_packets_entropy_.end()) {
// Should only happen when we have not received ack for any packet.
DCHECK_EQ(0u, sequence_number);
return 0;
}
return it->second.second;
}
void QuicPacketEntropyManager::RecalculateReceivedEntropyHash(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
received_packets_entropy_hash_ = entropy_hash;
ReceivedEntropyMap::iterator it =
received_packets_entropy_.lower_bound(sequence_number);
// TODO(satyamshekhar): Make this O(1).
for (; it != received_packets_entropy_.end(); ++it) {
received_packets_entropy_hash_ ^= it->second;
}
}
bool QuicPacketEntropyManager::IsValidEntropy(
QuicPacketSequenceNumber sequence_number,
const SequenceNumberSet& missing_packets,
QuicPacketEntropyHash entropy_hash) const {
SentEntropyMap::const_iterator entropy_it =
sent_packets_entropy_.find(sequence_number);
if (entropy_it == sent_packets_entropy_.end()) {
DCHECK_EQ(0u, sequence_number);
// Close connection if something goes wrong.
return 0 == sequence_number;
}
QuicPacketEntropyHash expected_entropy_hash = entropy_it->second.second;
for (SequenceNumberSet::const_iterator it = missing_packets.begin();
it != missing_packets.end(); ++it) {
entropy_it = sent_packets_entropy_.find(*it);
DCHECK(entropy_it != sent_packets_entropy_.end());
expected_entropy_hash ^= entropy_it->second.first;
}
DLOG_IF(WARNING, entropy_hash != expected_entropy_hash)
<< "Invalid entropy hash: " << static_cast<int>(entropy_hash)
<< " expected entropy hash: " << static_cast<int>(expected_entropy_hash);
return entropy_hash == expected_entropy_hash;
}
void QuicPacketEntropyManager::ClearSentEntropyBefore(
QuicPacketSequenceNumber sequence_number) {
if (sent_packets_entropy_.empty()) {
return;
}
SentEntropyMap::iterator it = sent_packets_entropy_.begin();
while (it->first < sequence_number) {
sent_packets_entropy_.erase(it);
it = sent_packets_entropy_.begin();
DCHECK(it != sent_packets_entropy_.end());
}
DVLOG(2) << "Cleared entropy before: "
<< sent_packets_entropy_.begin()->first;
}
void QuicPacketEntropyManager::ClearReceivedEntropyBefore(
QuicPacketSequenceNumber sequence_number) {
// This might clear the received_packets_entropy_ map if the current packet
// is peer_least_packet_awaiting_ack_ and it doesn't have entropy flag set.
received_packets_entropy_.erase(
received_packets_entropy_.begin(),
received_packets_entropy_.lower_bound(sequence_number));
}
} // namespace net
|
