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