// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Manages the packet entropy calculation for both sent and received packets
// for a connection.

#ifndef NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
#define NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_

#include <deque>

#include "net/quic/quic_config.h"
#include "net/quic/quic_framer.h"
#include "net/quic/quic_protocol.h"

namespace net {

namespace test {
class EntropyTrackerPeer;
class QuicConnectionPeer;
class QuicReceivedPacketManagerPeer;
}  // namespace test

struct QuicConnectionStats;

// Records all received packets by a connection and tracks their entropy.
// Also calculates the correct entropy for the framer when it truncates an ack
// frame being serialized.
class NET_EXPORT_PRIVATE QuicReceivedPacketManager :
    public QuicReceivedEntropyHashCalculatorInterface {
 public:
  class NET_EXPORT_PRIVATE EntropyTracker {
   public:
    EntropyTracker();
    ~EntropyTracker();

    // Compute the XOR of the entropy of all received packets up to
    // and including packet_number.
    // Requires that either:
    //   packet_number == largest_observed_
    // or:
    //   packet_number > first_gap_ &&
    //   packet_number < largest_observed_ &&
    //   packet_number in packets_entropy_
    QuicPacketEntropyHash EntropyHash(QuicPacketNumber packet_number) const;

    // Record the received entropy hash against |packet_number|.
    // Performs garbage collection to advance first_gap_ if
    // packet_number == first_gap_.
    void RecordPacketEntropyHash(QuicPacketNumber packet_number,
                                 QuicPacketEntropyHash entropy_hash);

    // Sets the entropy hash up to but not including a packet number based
    // on the hash provided by a StopWaiting frame.  Clears older packet
    // entropy entries and performs garbage collection up to the first gap.
    void SetCumulativeEntropyUpTo(QuicPacketNumber packet_number,
                                  QuicPacketEntropyHash entropy_hash);

    size_t size() const { return packets_entropy_.size(); }

   private:
    friend class test::EntropyTrackerPeer;

    // A deque indexed by packet number storing the packet's hash and whether
    // a hash was recorded for that packet number.
    typedef std::deque<std::pair<QuicPacketEntropyHash, bool>>
        ReceivedEntropyHashes;

    // Recomputes first_gap_ and removes packets_entropy_ entries that are no
    // longer needed to compute EntropyHash.
    void AdvanceFirstGapAndGarbageCollectEntropyMap();

    // Map of received packet numbers to their corresponding entropy.
    // Stores an entry for every received packet whose packet_number is larger
    // than first_gap_.  Packets without the entropy bit set have an entropy
    // value of 0.
    ReceivedEntropyHashes packets_entropy_;

    // Cumulative hash of entropy of all received packets.
    QuicPacketEntropyHash packets_entropy_hash_;

    // packet number of the first packet that we do not know the entropy of.
    // If there are no gaps in the received packet sequence,
    // packets_entropy_ will be empty and first_gap_ will be equal to
    // 'largest_observed_ + 1' since that's the first packet for which
    // entropy is unknown.  If there are gaps, packets_entropy_ will
    // contain entries for all received packets with packet_number >
    // first_gap_.
    QuicPacketNumber first_gap_;

    // packet number of the largest observed packet.
    QuicPacketNumber largest_observed_;

    DISALLOW_COPY_AND_ASSIGN(EntropyTracker);
  };

  explicit QuicReceivedPacketManager(QuicConnectionStats* stats);
  ~QuicReceivedPacketManager() override;

  // Updates the internal state concerning which packets have been received.
  // bytes: the packet size in bytes including Quic Headers.
  // header: the packet header.
  // timestamp: the arrival time of the packet.
  void RecordPacketReceived(QuicByteCount bytes,
                            const QuicPacketHeader& header,
                            QuicTime receipt_time);

  void RecordPacketRevived(QuicPacketNumber packet_number);

  // Checks whether |packet_number| is missing and less than largest observed.
  bool IsMissing(QuicPacketNumber packet_number);

  // Checks if we're still waiting for the packet with |packet_number|.
  bool IsAwaitingPacket(QuicPacketNumber packet_number);

  // Update the |ack_frame| for an outgoing ack.
  void UpdateReceivedPacketInfo(QuicAckFrame* ack_frame,
                                QuicTime approximate_now);

  // QuicReceivedEntropyHashCalculatorInterface
  // Called by QuicFramer, when the outgoing ack gets truncated, to recalculate
  // the received entropy hash for the truncated ack frame.
  QuicPacketEntropyHash EntropyHash(
      QuicPacketNumber packet_number) const override;

  // Updates internal state based on |stop_waiting|.
  void UpdatePacketInformationSentByPeer(
      const QuicStopWaitingFrame& stop_waiting);

  // Returns true when there are new missing packets to be reported within 3
  // packets of the largest observed.
  bool HasNewMissingPackets() const;

  // Returns the number of packets being tracked in the EntropyTracker.
  size_t NumTrackedPackets() const;

  QuicPacketNumber peer_least_packet_awaiting_ack() {
    return peer_least_packet_awaiting_ack_;
  }

  bool ack_frame_updated() const { return ack_frame_updated_; }

 private:
  friend class test::QuicConnectionPeer;
  friend class test::QuicReceivedPacketManagerPeer;

  // Deletes all missing packets before least unacked. The connection won't
  // process any packets with packet number before |least_unacked| that it
  // received after this call. Returns true if there were missing packets before
  // |least_unacked| unacked, false otherwise.
  bool DontWaitForPacketsBefore(QuicPacketNumber least_unacked);

  // Tracks entropy hashes of received packets.
  EntropyTracker entropy_tracker_;

  // Least packet number of the the packet sent by the peer for which it
  // hasn't received an ack.
  QuicPacketNumber peer_least_packet_awaiting_ack_;

  // Received packet information used to produce acks.
  QuicAckFrame ack_frame_;

  // True if |ack_frame_| has been updated since UpdateReceivedPacketInfo was
  // last called.
  bool ack_frame_updated_;

  // The time we received the largest_observed packet number, or zero if
  // no packet numbers have been received since UpdateReceivedPacketInfo.
  // Needed for calculating delta_time_largest_observed.
  QuicTime time_largest_observed_;

  QuicConnectionStats* stats_;

  DISALLOW_COPY_AND_ASSIGN(QuicReceivedPacketManager);
};

}  // namespace net

#endif  // NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_