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
10using std::make_pair;
11using std::max;
12using std::min;
13
14namespace net {
15
16QuicSentEntropyManager::QuicSentEntropyManager() : map_offset_(1) {}
17
18QuicSentEntropyManager::~QuicSentEntropyManager() {}
19
20QuicPacketEntropyHash QuicSentEntropyManager::GetPacketEntropy(
21    QuicPacketSequenceNumber sequence_number) const {
22  return packets_entropy_[sequence_number - map_offset_];
23}
24
25QuicPacketSequenceNumber
26QuicSentEntropyManager::GetLargestPacketWithEntropy() const {
27  return map_offset_ + packets_entropy_.size() - 1;
28}
29
30QuicPacketSequenceNumber
31QuicSentEntropyManager::GetSmallestPacketWithEntropy() const {
32  return map_offset_;
33}
34
35void 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
44void 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
58QuicPacketEntropyHash 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
67bool 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
95void 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