net/quic/quic_sent_entropy_manager.cc

   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