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