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 16 QuicSentEntropyManager::QuicSentEntropyManager() : map_offset_(1) {} 17 18 QuicSentEntropyManager::~QuicSentEntropyManager() {} 19 20 QuicPacketEntropyHash QuicSentEntropyManager::GetPacketEntropy( 21 QuicPacketSequenceNumber sequence_number) const { 22 return packets_entropy_[sequence_number - map_offset_]; 23 } 24 25 QuicPacketSequenceNumber 26 QuicSentEntropyManager::GetLargestPacketWithEntropy() const { 27 return map_offset_ + packets_entropy_.size() - 1; 28 } 29 30 QuicPacketSequenceNumber 31 QuicSentEntropyManager::GetSmallestPacketWithEntropy() const { 32 return map_offset_; 33 } 34 35 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 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 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 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 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