Ben Murdoch | 2385ea3 | 2013-08-06 11:01:04 +0100 | [diff] [blame] | 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 | |
| 10 | using std::make_pair; |
| 11 | using std::max; |
| 12 | using std::min; |
| 13 | |
| 14 | namespace net { |
| 15 | |
| 16 | QuicReceivedPacketManager::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 | |
| 27 | QuicReceivedPacketManager::~QuicReceivedPacketManager() {} |
| 28 | |
| 29 | void 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 | |
| 52 | bool QuicReceivedPacketManager::IsAwaitingPacket( |
| 53 | QuicPacketSequenceNumber sequence_number) { |
| 54 | return ::net::IsAwaitingPacket(received_info_, sequence_number); |
| 55 | } |
| 56 | |
| 57 | void 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 | |
| 73 | void 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 | |
| 90 | QuicPacketEntropyHash 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_|. |
Ben Murdoch | bb1529c | 2013-08-08 10:24:53 +0100 | [diff] [blame^] | 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) |
Ben Murdoch | 2385ea3 | 2013-08-06 11:01:04 +0100 | [diff] [blame] | 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 | |
| 116 | void 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 | |
| 143 | void 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 | |
| 158 | bool 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 | |
| 167 | void 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 |