xref: /external/chromium_org/net/quic/quic_sent_entropy_manager.cc

// 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(
    QuicPacketSequenceNumber sequence_number) const {
  return packets_entropy_[sequence_number - map_offset_];
}

QuicPacketSequenceNumber
QuicSentEntropyManager::GetLargestPacketWithEntropy() const {
  return map_offset_ + packets_entropy_.size() - 1;
}

QuicPacketSequenceNumber
QuicSentEntropyManager::GetSmallestPacketWithEntropy() const {
  return map_offset_;
}

void QuicSentEntropyManager::UpdateCumulativeEntropy(
    QuicPacketSequenceNumber sequence_number,
    CumulativeEntropy* cumulative) const {
  while (cumulative->sequence_number < sequence_number) {
    ++cumulative->sequence_number;
    cumulative->entropy ^= GetPacketEntropy(cumulative->sequence_number);
  }
}

void QuicSentEntropyManager::RecordPacketEntropyHash(
    QuicPacketSequenceNumber sequence_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 sequence number gaps.
    DCHECK_EQ(GetLargestPacketWithEntropy() + 1, sequence_number);
  }
  packets_entropy_.push_back(entropy_hash);
  DVLOG(2) << "Recorded sequence number " << sequence_number
           << " with entropy hash: " << static_cast<int>(entropy_hash);
}

QuicPacketEntropyHash QuicSentEntropyManager::GetCumulativeEntropy(
    QuicPacketSequenceNumber sequence_number) {
  DCHECK_LE(last_cumulative_entropy_.sequence_number, sequence_number);
  DCHECK_GE(GetLargestPacketWithEntropy(), sequence_number);
  // First the entropy for largest_observed sequence number should be updated.
  UpdateCumulativeEntropy(sequence_number, &last_cumulative_entropy_);
  return last_cumulative_entropy_.entropy;
}

bool QuicSentEntropyManager::IsValidEntropy(
    QuicPacketSequenceNumber largest_observed,
    const SequenceNumberSet& missing_packets,
    QuicPacketEntropyHash entropy_hash) {
  DCHECK_GE(largest_observed, last_valid_entropy_.sequence_number);
  // Ensure the largest and smallest sequence numbers are in range.
  if (largest_observed > GetLargestPacketWithEntropy()) {
    return false;
  }
  if (!missing_packets.empty() &&
      *missing_packets.begin() < GetSmallestPacketWithEntropy()) {
    return false;
  }
  // First the entropy for largest_observed sequence 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 (SequenceNumberSet::const_iterator it = missing_packets.begin();
       it != missing_packets.end(); ++it) {
    expected_entropy_hash ^= GetPacketEntropy(*it);
  }
  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(
    QuicPacketSequenceNumber sequence_number) {
  // Don't discard entropy before updating the cumulative entropy used to
  // calculate EntropyHash and IsValidEntropy.
  if (last_cumulative_entropy_.sequence_number < sequence_number) {
    UpdateCumulativeEntropy(sequence_number, &last_cumulative_entropy_);
  }
  if (last_valid_entropy_.sequence_number < sequence_number) {
    UpdateCumulativeEntropy(sequence_number, &last_valid_entropy_);
  }
  while (map_offset_ < sequence_number) {
    packets_entropy_.pop_front();
    ++map_offset_;
  }
  DVLOG(2) << "Cleared entropy before: " << sequence_number;
}

}  // namespace net