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.
4
5 #include "net/quic/quic_sent_entropy_manager.h"
6
7 #include "base/logging.h"
8 #include "net/base/linked_hash_map.h"
9
10 using std::make_pair;
11 using std::max;
12 using std::min;
13
14 namespace net {
15
QuicSentEntropyManager()16 QuicSentEntropyManager::QuicSentEntropyManager() : map_offset_(1) {}
17
~QuicSentEntropyManager()18 QuicSentEntropyManager::~QuicSentEntropyManager() {}
19
GetPacketEntropy(QuicPacketSequenceNumber sequence_number) const20 QuicPacketEntropyHash QuicSentEntropyManager::GetPacketEntropy(
21 QuicPacketSequenceNumber sequence_number) const {
22 return packets_entropy_[sequence_number - map_offset_];
23 }
24
25 QuicPacketSequenceNumber
GetLargestPacketWithEntropy() const26 QuicSentEntropyManager::GetLargestPacketWithEntropy() const {
27 return map_offset_ + packets_entropy_.size() - 1;
28 }
29
30 QuicPacketSequenceNumber
GetSmallestPacketWithEntropy() const31 QuicSentEntropyManager::GetSmallestPacketWithEntropy() const {
32 return map_offset_;
33 }
34
UpdateCumulativeEntropy(QuicPacketSequenceNumber sequence_number,CumulativeEntropy * cumulative) const35 void QuicSentEntropyManager::UpdateCumulativeEntropy(
36 QuicPacketSequenceNumber sequence_number,
37 CumulativeEntropy* cumulative) const {
38 while (cumulative->sequence_number < sequence_number) {
39 ++cumulative->sequence_number;
40 cumulative->entropy ^= GetPacketEntropy(cumulative->sequence_number);
41 }
42 }
43
RecordPacketEntropyHash(QuicPacketSequenceNumber sequence_number,QuicPacketEntropyHash entropy_hash)44 void QuicSentEntropyManager::RecordPacketEntropyHash(
45 QuicPacketSequenceNumber sequence_number,
46 QuicPacketEntropyHash entropy_hash) {
47 if (!packets_entropy_.empty()) {
48 // Ensure packets always are recorded in order.
49 // Every packet's entropy is recorded, even if it's not sent, so there
50 // are not sequence number gaps.
51 DCHECK_EQ(GetLargestPacketWithEntropy() + 1, sequence_number);
52 }
53 packets_entropy_.push_back(entropy_hash);
54 DVLOG(2) << "Recorded sequence number " << sequence_number
55 << " with entropy hash: " << static_cast<int>(entropy_hash);
56 }
57
GetCumulativeEntropy(QuicPacketSequenceNumber sequence_number)58 QuicPacketEntropyHash QuicSentEntropyManager::GetCumulativeEntropy(
59 QuicPacketSequenceNumber sequence_number) {
60 DCHECK_LE(last_cumulative_entropy_.sequence_number, sequence_number);
61 DCHECK_GE(GetLargestPacketWithEntropy(), sequence_number);
62 // First the entropy for largest_observed sequence number should be updated.
63 UpdateCumulativeEntropy(sequence_number, &last_cumulative_entropy_);
64 return last_cumulative_entropy_.entropy;
65 }
66
IsValidEntropy(QuicPacketSequenceNumber largest_observed,const SequenceNumberSet & missing_packets,QuicPacketEntropyHash entropy_hash)67 bool QuicSentEntropyManager::IsValidEntropy(
68 QuicPacketSequenceNumber largest_observed,
69 const SequenceNumberSet& missing_packets,
70 QuicPacketEntropyHash entropy_hash) {
71 DCHECK_GE(largest_observed, last_valid_entropy_.sequence_number);
72 // Ensure the largest and smallest sequence numbers are in range.
73 if (largest_observed > GetLargestPacketWithEntropy()) {
74 return false;
75 }
76 if (!missing_packets.empty() &&
77 *missing_packets.begin() < GetSmallestPacketWithEntropy()) {
78 return false;
79 }
80 // First the entropy for largest_observed sequence number should be updated.
81 UpdateCumulativeEntropy(largest_observed, &last_valid_entropy_);
82
83 // Now XOR out all the missing entropies.
84 QuicPacketEntropyHash expected_entropy_hash = last_valid_entropy_.entropy;
85 for (SequenceNumberSet::const_iterator it = missing_packets.begin();
86 it != missing_packets.end(); ++it) {
87 expected_entropy_hash ^= GetPacketEntropy(*it);
88 }
89 DLOG_IF(WARNING, entropy_hash != expected_entropy_hash)
90 << "Invalid entropy hash: " << static_cast<int>(entropy_hash)
91 << " expected entropy hash: " << static_cast<int>(expected_entropy_hash);
92 return entropy_hash == expected_entropy_hash;
93 }
94
ClearEntropyBefore(QuicPacketSequenceNumber sequence_number)95 void QuicSentEntropyManager::ClearEntropyBefore(
96 QuicPacketSequenceNumber sequence_number) {
97 // Don't discard entropy before updating the cumulative entropy used to
98 // calculate EntropyHash and IsValidEntropy.
99 if (last_cumulative_entropy_.sequence_number < sequence_number) {
100 UpdateCumulativeEntropy(sequence_number, &last_cumulative_entropy_);
101 }
102 if (last_valid_entropy_.sequence_number < sequence_number) {
103 UpdateCumulativeEntropy(sequence_number, &last_valid_entropy_);
104 }
105 while (map_offset_ < sequence_number) {
106 packets_entropy_.pop_front();
107 ++map_offset_;
108 }
109 DVLOG(2) << "Cleared entropy before: " << sequence_number;
110 }
111
112 } // namespace net
113