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 // Manages the packet entropy calculation for both sent and received packets 6 // for a connection. 7 8 #ifndef NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_ 9 #define NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_ 10 11 #include "net/quic/congestion_control/receive_algorithm_interface.h" 12 #include "net/quic/quic_framer.h" 13 #include "net/quic/quic_protocol.h" 14 15 namespace net { 16 17 namespace test { 18 class EntropyTrackerPeer; 19 class QuicConnectionPeer; 20 class QuicReceivedPacketManagerPeer; 21 } // namespace test 22 23 struct QuicConnectionStats; 24 25 // Records all received packets by a connection and tracks their entropy. 26 // Also calculates the correct entropy for the framer when it truncates an ack 27 // frame being serialized. 28 class NET_EXPORT_PRIVATE QuicReceivedPacketManager : 29 public QuicReceivedEntropyHashCalculatorInterface { 30 public: 31 class NET_EXPORT_PRIVATE EntropyTracker { 32 public: 33 EntropyTracker(); 34 ~EntropyTracker(); 35 36 // Compute the XOR of the entropy of all received packets up to 37 // and including sequence_number. 38 // Requires that either: 39 // sequence_number == largest_observed_ 40 // or: 41 // sequence_number > first_gap_ && 42 // sequence_number < largest_observed_ && 43 // sequence_number in packets_entropy_ 44 QuicPacketEntropyHash EntropyHash( 45 QuicPacketSequenceNumber sequence_number) const; 46 47 // Record the received entropy hash against |sequence_number|. 48 // Performs garbage collection to advance first_gap_ if 49 // sequence_number == first_gap_. 50 void RecordPacketEntropyHash(QuicPacketSequenceNumber sequence_number, 51 QuicPacketEntropyHash entropy_hash); 52 53 // Sets the entropy hash up to but not including a sequence number based 54 // on the hash provided by a StopWaiting frame. Clears older packet 55 // entropy entries and performs garbage collection up to the first gap. 56 void SetCumulativeEntropyUpTo(QuicPacketSequenceNumber sequence_number, 57 QuicPacketEntropyHash entropy_hash); 58 59 private: 60 friend class test::EntropyTrackerPeer; 61 62 typedef std::map<QuicPacketSequenceNumber, 63 QuicPacketEntropyHash> ReceivedEntropyMap; 64 65 // Recomputes first_gap_ and removes packets_entropy_ entries that are no 66 // longer needed to compute EntropyHash. 67 void AdvanceFirstGapAndGarbageCollectEntropyMap(); 68 69 // TODO(satyamshekhar): Can be optimized using an interval set like data 70 // structure. 71 // Map of received sequence numbers to their corresponding entropy. 72 // Stores an entry for every received packet whose sequence_number is larger 73 // than first_gap_. Packets without the entropy bit set have an entropy 74 // value of 0. 75 // TODO(ianswett): When the entropy flag is off, the entropy 76 // should not be 0. 77 ReceivedEntropyMap packets_entropy_; 78 79 // Cumulative hash of entropy of all received packets. 80 QuicPacketEntropyHash packets_entropy_hash_; 81 82 // Sequence number of the first packet that we do not know the entropy of. 83 // If there are no gaps in the received packet sequence, 84 // packets_entropy_ will be empty and first_gap_ will be equal to 85 // 'largest_observed_ + 1' since that's the first packet for which 86 // entropy is unknown. If there are gaps, packets_entropy_ will 87 // contain entries for all received packets with sequence_number > 88 // first_gap_. 89 QuicPacketSequenceNumber first_gap_; 90 91 // Sequence number of the largest observed packet. 92 QuicPacketSequenceNumber largest_observed_; 93 94 DISALLOW_COPY_AND_ASSIGN(EntropyTracker); 95 }; 96 97 explicit QuicReceivedPacketManager(CongestionFeedbackType congestion_type, 98 QuicConnectionStats* stats); 99 virtual ~QuicReceivedPacketManager(); 100 101 // Updates the internal state concerning which packets have been received. 102 // bytes: the packet size in bytes including Quic Headers. 103 // header: the packet header. 104 // timestamp: the arrival time of the packet. 105 void RecordPacketReceived(QuicByteCount bytes, 106 const QuicPacketHeader& header, 107 QuicTime receipt_time); 108 109 void RecordPacketRevived(QuicPacketSequenceNumber sequence_number); 110 111 // Checks whether |sequence_number| is missing and less than largest observed. 112 bool IsMissing(QuicPacketSequenceNumber sequence_number); 113 114 // Checks if we're still waiting for the packet with |sequence_number|. 115 bool IsAwaitingPacket(QuicPacketSequenceNumber sequence_number); 116 117 // Update the |received_info| for an outgoing ack. 118 void UpdateReceivedPacketInfo(ReceivedPacketInfo* received_info, 119 QuicTime approximate_now); 120 121 // Should be called before sending an ACK packet, to decide if we need 122 // to attach a QuicCongestionFeedbackFrame block. 123 // Returns false if no QuicCongestionFeedbackFrame block is needed. 124 // Otherwise fills in feedback and returns true. 125 virtual bool GenerateCongestionFeedback( 126 QuicCongestionFeedbackFrame* feedback); 127 128 // QuicReceivedEntropyHashCalculatorInterface 129 // Called by QuicFramer, when the outgoing ack gets truncated, to recalculate 130 // the received entropy hash for the truncated ack frame. 131 virtual QuicPacketEntropyHash EntropyHash( 132 QuicPacketSequenceNumber sequence_number) const OVERRIDE; 133 134 // Updates internal state based on |received_info|. 135 void UpdatePacketInformationReceivedByPeer( 136 const ReceivedPacketInfo& received_nfo); 137 // Updates internal state based on |stop_waiting|. 138 void UpdatePacketInformationSentByPeer( 139 const QuicStopWaitingFrame& stop_waiting); 140 141 // Returns whether the peer is missing packets. 142 bool HasMissingPackets(); 143 144 // Returns true when there are new missing packets to be reported within 3 145 // packets of the largest observed. 146 bool HasNewMissingPackets(); 147 148 QuicPacketSequenceNumber peer_largest_observed_packet() { 149 return peer_largest_observed_packet_; 150 } 151 152 QuicPacketSequenceNumber least_packet_awaited_by_peer() { 153 return least_packet_awaited_by_peer_; 154 } 155 156 QuicPacketSequenceNumber peer_least_packet_awaiting_ack() { 157 return peer_least_packet_awaiting_ack_; 158 } 159 160 private: 161 friend class test::QuicConnectionPeer; 162 friend class test::QuicReceivedPacketManagerPeer; 163 164 // Deletes all missing packets before least unacked. The connection won't 165 // process any packets with sequence number before |least_unacked| that it 166 // received after this call. Returns true if there were missing packets before 167 // |least_unacked| unacked, false otherwise. 168 bool DontWaitForPacketsBefore(QuicPacketSequenceNumber least_unacked); 169 170 // Tracks entropy hashes of received packets. 171 EntropyTracker entropy_tracker_; 172 173 // Track some peer state so we can do less bookkeeping. 174 // Largest sequence number that the peer has observed. Mostly received, 175 // missing in case of truncated acks. 176 QuicPacketSequenceNumber peer_largest_observed_packet_; 177 // Least sequence number which the peer is still waiting for. 178 QuicPacketSequenceNumber least_packet_awaited_by_peer_; 179 // Least sequence number of the the packet sent by the peer for which it 180 // hasn't received an ack. 181 QuicPacketSequenceNumber peer_least_packet_awaiting_ack_; 182 183 // Received packet information used to produce acks. 184 ReceivedPacketInfo received_info_; 185 186 // The time we received the largest_observed sequence number, or zero if 187 // no sequence numbers have been received since UpdateReceivedPacketInfo. 188 // Needed for calculating delta_time_largest_observed. 189 QuicTime time_largest_observed_; 190 191 scoped_ptr<ReceiveAlgorithmInterface> receive_algorithm_; 192 193 QuicConnectionStats* stats_; 194 195 DISALLOW_COPY_AND_ASSIGN(QuicReceivedPacketManager); 196 }; 197 198 } // namespace net 199 200 #endif // NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_ 201