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