src/net/quic/quic_received_packet_manager.h

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