Home | History | Annotate | Download | only in quic 
      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