quic_received_packet_manager.cc revision bb1529ce867d8845a77ec7cdf3e3003ef1771a40 
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_received_packet_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
16QuicReceivedPacketManager::QuicReceivedPacketManager()
17    : packets_entropy_hash_(0),
18      largest_sequence_number_(0),
19      peer_largest_observed_packet_(0),
20      least_packet_awaited_by_peer_(1),
21      peer_least_packet_awaiting_ack_(0),
22      time_largest_observed_(QuicTime::Zero()) {
23  received_info_.largest_observed = 0;
24  received_info_.entropy_hash = 0;
25}
26
27QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
28
29void QuicReceivedPacketManager::RecordPacketReceived(
30    const QuicPacketHeader& header, QuicTime receipt_time) {
31  QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
32  DCHECK(IsAwaitingPacket(sequence_number));
33
34  InsertMissingPacketsBetween(
35      &received_info_,
36      max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
37      header.packet_sequence_number);
38
39  if (received_info_.largest_observed > header.packet_sequence_number) {
40    // We've gotten one of the out of order packets - remove it from our
41    // "missing packets" list.
42    DVLOG(1) << "Removing " << sequence_number << " from missing list";
43    received_info_.missing_packets.erase(sequence_number);
44  }
45  if (header.packet_sequence_number > received_info_.largest_observed) {
46    received_info_.largest_observed = header.packet_sequence_number;
47    time_largest_observed_ = receipt_time;
48  }
49  RecordPacketEntropyHash(sequence_number, header.entropy_hash);
50}
51
52bool QuicReceivedPacketManager::IsAwaitingPacket(
53    QuicPacketSequenceNumber sequence_number) {
54  return ::net::IsAwaitingPacket(received_info_, sequence_number);
55}
56
57void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
58    ReceivedPacketInfo* received_info, QuicTime approximate_now) {
59  *received_info = received_info_;
60  received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
61  if (time_largest_observed_ == QuicTime::Zero()) {
62    // We have not received any new higher sequence numbers since we sent our
63    // last ACK.
64    received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
65  } else {
66    received_info->delta_time_largest_observed =
67        approximate_now.Subtract(time_largest_observed_);
68
69    time_largest_observed_ = QuicTime::Zero();
70  }
71}
72
73void QuicReceivedPacketManager::RecordPacketEntropyHash(
74    QuicPacketSequenceNumber sequence_number,
75    QuicPacketEntropyHash entropy_hash) {
76  if (sequence_number < largest_sequence_number_) {
77    DLOG(INFO) << "Ignoring received packet entropy for sequence_number:"
78               << sequence_number << " less than largest_peer_sequence_number:"
79               << largest_sequence_number_;
80    return;
81  }
82  packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
83  packets_entropy_hash_ ^= entropy_hash;
84  DVLOG(2) << "setting cumulative received entropy hash to: "
85           << static_cast<int>(packets_entropy_hash_)
86           << " updated with sequence number " << sequence_number
87           << " entropy hash: " << static_cast<int>(entropy_hash);
88}
89
90QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
91    QuicPacketSequenceNumber sequence_number) const {
92  DCHECK_LE(sequence_number, received_info_.largest_observed);
93  DCHECK_GE(sequence_number, largest_sequence_number_);
94  if (sequence_number == received_info_.largest_observed) {
95    return packets_entropy_hash_;
96  }
97
98  ReceivedEntropyMap::const_iterator it =
99      packets_entropy_.upper_bound(sequence_number);
100  // When this map is empty we should only query entropy for
101  // |largest_received_sequence_number_|.
102  // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
103  // LOG_IF_EVERY_N_SEC(WARNING, it != packets_entropy_.end(), 10)
104  LOG_IF(WARNING, it != packets_entropy_.end())
105      << "largest_received: " << received_info_.largest_observed
106      << " sequence_number: " << sequence_number;
107
108  // TODO(satyamshekhar): Make this O(1).
109  QuicPacketEntropyHash hash = packets_entropy_hash_;
110  for (; it != packets_entropy_.end(); ++it) {
111    hash ^= it->second;
112  }
113  return hash;
114}
115
116void QuicReceivedPacketManager::RecalculateEntropyHash(
117    QuicPacketSequenceNumber peer_least_unacked,
118    QuicPacketEntropyHash entropy_hash) {
119  DLOG_IF(WARNING, peer_least_unacked > received_info_.largest_observed)
120      << "Prematurely updating the entropy manager before registering the "
121      << "entropy of the containing packet creates a temporary inconsistency.";
122  if (peer_least_unacked < largest_sequence_number_) {
123    DLOG(INFO) << "Ignoring received peer_least_unacked:" << peer_least_unacked
124               << " less than largest_peer_sequence_number:"
125               << largest_sequence_number_;
126    return;
127  }
128  largest_sequence_number_ = peer_least_unacked;
129  packets_entropy_hash_ = entropy_hash;
130  ReceivedEntropyMap::iterator it =
131      packets_entropy_.lower_bound(peer_least_unacked);
132  // TODO(satyamshekhar): Make this O(1).
133  for (; it != packets_entropy_.end(); ++it) {
134    packets_entropy_hash_ ^= it->second;
135  }
136  // Discard entropies before least unacked.
137  packets_entropy_.erase(
138      packets_entropy_.begin(),
139      packets_entropy_.lower_bound(
140          min(peer_least_unacked, received_info_.largest_observed)));
141}
142
143void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
144    const QuicAckFrame& incoming_ack) {
145  // ValidateAck should fail if largest_observed ever shrinks.
146  DCHECK_LE(peer_largest_observed_packet_,
147            incoming_ack.received_info.largest_observed);
148  peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed;
149
150  if (incoming_ack.received_info.missing_packets.empty()) {
151    least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
152  } else {
153    least_packet_awaited_by_peer_ =
154        *(incoming_ack.received_info.missing_packets.begin());
155  }
156}
157
158bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
159    QuicPacketSequenceNumber least_unacked) {
160  size_t missing_packets_count = received_info_.missing_packets.size();
161  received_info_.missing_packets.erase(
162      received_info_.missing_packets.begin(),
163      received_info_.missing_packets.lower_bound(least_unacked));
164  return missing_packets_count != received_info_.missing_packets.size();
165}
166
167void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
168    const QuicAckFrame& incoming_ack) {
169  // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
170  DCHECK_LE(peer_least_packet_awaiting_ack_,
171            incoming_ack.sent_info.least_unacked);
172  if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) {
173    bool missed_packets =
174        DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked);
175    if (missed_packets || incoming_ack.sent_info.least_unacked >
176            received_info_.largest_observed + 1) {
177      DVLOG(1) << "Updating entropy hashed since we missed packets";
178      // There were some missing packets that we won't ever get now. Recalculate
179      // the received entropy hash.
180      RecalculateEntropyHash(incoming_ack.sent_info.least_unacked,
181                             incoming_ack.sent_info.entropy_hash);
182    }
183    peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
184  }
185  DCHECK(received_info_.missing_packets.empty() ||
186         *received_info_.missing_packets.begin() >=
187             peer_least_packet_awaiting_ack_);
188}
189
190}  // namespace net
191