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