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
18namespace net {
19
20namespace test {
21class EntropyTrackerPeer;
22class QuicConnectionPeer;
23class QuicReceivedPacketManagerPeer;
24}  // namespace test
25
26struct 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.
31class 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   private:
63    friend class test::EntropyTrackerPeer;
64
65    // A deque indexed by sequence number storing the packet's hash and whether
66    // a hash was recorded for that sequence 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 sequence numbers to their corresponding entropy.
75    // Stores an entry for every received packet whose sequence_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    // Sequence 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 sequence_number >
89    // first_gap_.
90    QuicPacketSequenceNumber first_gap_;
91
92    // Sequence number of the largest observed packet.
93    QuicPacketSequenceNumber largest_observed_;
94
95    DISALLOW_COPY_AND_ASSIGN(EntropyTracker);
96  };
97
98  explicit QuicReceivedPacketManager(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 |ack_frame| for an outgoing ack.
118  void UpdateReceivedPacketInfo(QuicAckFrame* ack_frame,
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 |stop_waiting|.
135  void UpdatePacketInformationSentByPeer(
136      const QuicStopWaitingFrame& stop_waiting);
137
138  // Returns true when there are new missing packets to be reported within 3
139  // packets of the largest observed.
140  bool HasNewMissingPackets();
141
142  QuicPacketSequenceNumber peer_least_packet_awaiting_ack() {
143    return peer_least_packet_awaiting_ack_;
144  }
145
146 private:
147  friend class test::QuicConnectionPeer;
148  friend class test::QuicReceivedPacketManagerPeer;
149
150  // Deletes all missing packets before least unacked. The connection won't
151  // process any packets with sequence number before |least_unacked| that it
152  // received after this call. Returns true if there were missing packets before
153  // |least_unacked| unacked, false otherwise.
154  bool DontWaitForPacketsBefore(QuicPacketSequenceNumber least_unacked);
155
156  // Tracks entropy hashes of received packets.
157  EntropyTracker entropy_tracker_;
158
159  // Least sequence number of the the packet sent by the peer for which it
160  // hasn't received an ack.
161  QuicPacketSequenceNumber peer_least_packet_awaiting_ack_;
162
163  // Received packet information used to produce acks.
164  QuicAckFrame ack_frame_;
165
166  // The time we received the largest_observed sequence number, or zero if
167  // no sequence numbers have been received since UpdateReceivedPacketInfo.
168  // Needed for calculating delta_time_largest_observed.
169  QuicTime time_largest_observed_;
170
171  scoped_ptr<ReceiveAlgorithmInterface> receive_algorithm_;
172
173  QuicConnectionStats* stats_;
174
175  PacketTimeList received_packet_times_;
176
177  DISALLOW_COPY_AND_ASSIGN(QuicReceivedPacketManager);
178};
179
180}  // namespace net
181
182#endif  // NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
183