| // 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_sent_entropy_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 { |
| |
| QuicSentEntropyManager::QuicSentEntropyManager() : map_offset_(1) {} |
| |
| QuicSentEntropyManager::~QuicSentEntropyManager() {} |
| |
| QuicPacketEntropyHash QuicSentEntropyManager::GetPacketEntropy( |
| QuicPacketNumber packet_number) const { |
| return packets_entropy_[packet_number - map_offset_]; |
| } |
| |
| QuicPacketNumber QuicSentEntropyManager::GetLargestPacketWithEntropy() const { |
| return map_offset_ + packets_entropy_.size() - 1; |
| } |
| |
| QuicPacketNumber QuicSentEntropyManager::GetSmallestPacketWithEntropy() const { |
| return map_offset_; |
| } |
| |
| void QuicSentEntropyManager::UpdateCumulativeEntropy( |
| QuicPacketNumber packet_number, |
| CumulativeEntropy* cumulative) const { |
| while (cumulative->packet_number < packet_number) { |
| ++cumulative->packet_number; |
| cumulative->entropy ^= GetPacketEntropy(cumulative->packet_number); |
| } |
| } |
| |
| void QuicSentEntropyManager::RecordPacketEntropyHash( |
| QuicPacketNumber packet_number, |
| QuicPacketEntropyHash entropy_hash) { |
| if (!packets_entropy_.empty()) { |
| // Ensure packets always are recorded in order. |
| // Every packet's entropy is recorded, even if it's not sent, so there |
| // are not packet number gaps. |
| DCHECK_EQ(GetLargestPacketWithEntropy() + 1, packet_number); |
| } |
| packets_entropy_.push_back(entropy_hash); |
| DVLOG(2) << "Recorded packet number " << packet_number |
| << " with entropy hash: " << static_cast<int>(entropy_hash); |
| } |
| |
| QuicPacketEntropyHash QuicSentEntropyManager::GetCumulativeEntropy( |
| QuicPacketNumber packet_number) { |
| DCHECK_LE(last_cumulative_entropy_.packet_number, packet_number); |
| DCHECK_GE(GetLargestPacketWithEntropy(), packet_number); |
| // First the entropy for largest_observed packet number should be updated. |
| UpdateCumulativeEntropy(packet_number, &last_cumulative_entropy_); |
| return last_cumulative_entropy_.entropy; |
| } |
| |
| bool QuicSentEntropyManager::IsValidEntropy( |
| QuicPacketNumber largest_observed, |
| const PacketNumberQueue& missing_packets, |
| QuicPacketEntropyHash entropy_hash) { |
| DCHECK_GE(largest_observed, last_valid_entropy_.packet_number); |
| // Ensure the largest and smallest packet numbers are in range. |
| if (largest_observed > GetLargestPacketWithEntropy()) { |
| return false; |
| } |
| if (!missing_packets.Empty() && |
| missing_packets.Min() < GetSmallestPacketWithEntropy()) { |
| return false; |
| } |
| // First the entropy for largest_observed packet number should be updated. |
| UpdateCumulativeEntropy(largest_observed, &last_valid_entropy_); |
| |
| // Now XOR out all the missing entropies. |
| QuicPacketEntropyHash expected_entropy_hash = last_valid_entropy_.entropy; |
| for (QuicPacketNumber packet : missing_packets) { |
| expected_entropy_hash ^= GetPacketEntropy(packet); |
| } |
| 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 QuicSentEntropyManager::ClearEntropyBefore( |
| QuicPacketNumber packet_number) { |
| // Don't discard entropy before updating the cumulative entropy used to |
| // calculate EntropyHash and IsValidEntropy. |
| if (last_cumulative_entropy_.packet_number < packet_number) { |
| UpdateCumulativeEntropy(packet_number, &last_cumulative_entropy_); |
| } |
| if (last_valid_entropy_.packet_number < packet_number) { |
| UpdateCumulativeEntropy(packet_number, &last_valid_entropy_); |
| } |
| while (map_offset_ < packet_number) { |
| packets_entropy_.pop_front(); |
| ++map_offset_; |
| } |
| DVLOG(2) << "Cleared entropy before: " << packet_number; |
| } |
| |
| } // namespace net |