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_|. 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 116 void QuicReceivedPacketManager::RecalculateEntropyHash( 117 QuicPacketSequenceNumber peer_least_unacked, 118 QuicPacketEntropyHash entropy_hash) { 119 DCHECK_LE(peer_least_unacked, received_info_.largest_observed); 120 if (peer_least_unacked < largest_sequence_number_) { 121 DLOG(INFO) << "Ignoring received peer_least_unacked:" << peer_least_unacked 122 << " less than largest_peer_sequence_number:" 123 << largest_sequence_number_; 124 return; 125 } 126 largest_sequence_number_ = peer_least_unacked; 127 packets_entropy_hash_ = entropy_hash; 128 ReceivedEntropyMap::iterator it = 129 packets_entropy_.lower_bound(peer_least_unacked); 130 // TODO(satyamshekhar): Make this O(1). 131 for (; it != packets_entropy_.end(); ++it) { 132 packets_entropy_hash_ ^= it->second; 133 } 134 // Discard entropies before least unacked. 135 packets_entropy_.erase( 136 packets_entropy_.begin(), 137 packets_entropy_.lower_bound( 138 min(peer_least_unacked, received_info_.largest_observed))); 139 } 140 141 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer( 142 const QuicAckFrame& incoming_ack) { 143 // ValidateAck should fail if largest_observed ever shrinks. 144 DCHECK_LE(peer_largest_observed_packet_, 145 incoming_ack.received_info.largest_observed); 146 peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed; 147 148 if (incoming_ack.received_info.missing_packets.empty()) { 149 least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1; 150 } else { 151 least_packet_awaited_by_peer_ = 152 *(incoming_ack.received_info.missing_packets.begin()); 153 } 154 } 155 156 bool QuicReceivedPacketManager::DontWaitForPacketsBefore( 157 QuicPacketSequenceNumber least_unacked) { 158 size_t missing_packets_count = received_info_.missing_packets.size(); 159 received_info_.missing_packets.erase( 160 received_info_.missing_packets.begin(), 161 received_info_.missing_packets.lower_bound(least_unacked)); 162 return missing_packets_count != received_info_.missing_packets.size(); 163 } 164 165 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer( 166 const QuicAckFrame& incoming_ack) { 167 // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks. 168 DCHECK_LE(peer_least_packet_awaiting_ack_, 169 incoming_ack.sent_info.least_unacked); 170 if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) { 171 bool missed_packets = 172 DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked); 173 if (missed_packets || incoming_ack.sent_info.least_unacked > 174 received_info_.largest_observed + 1) { 175 DVLOG(1) << "Updating entropy hashed since we missed packets"; 176 // There were some missing packets that we won't ever get now. Recalculate 177 // the received entropy hash. 178 RecalculateEntropyHash(incoming_ack.sent_info.least_unacked, 179 incoming_ack.sent_info.entropy_hash); 180 } 181 peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked; 182 } 183 DCHECK(received_info_.missing_packets.empty() || 184 *received_info_.missing_packets.begin() >= 185 peer_least_packet_awaiting_ack_); 186 } 187 188 } // namespace net 189