path: root/lib/ngtcp2_rtb.h

/*
 * ngtcp2
 *
 * Copyright (c) 2017 ngtcp2 contributors
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#ifndef NGTCP2_RTB_H
#define NGTCP2_RTB_H

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif /* HAVE_CONFIG_H */

#include <ngtcp2/ngtcp2.h>

#include "ngtcp2_pkt.h"
#include "ngtcp2_ksl.h"
#include "ngtcp2_pq.h"
#include "ngtcp2_objalloc.h"

typedef struct ngtcp2_conn ngtcp2_conn;
typedef struct ngtcp2_pktns ngtcp2_pktns;
typedef struct ngtcp2_log ngtcp2_log;
typedef struct ngtcp2_qlog ngtcp2_qlog;
typedef struct ngtcp2_strm ngtcp2_strm;
typedef struct ngtcp2_rst ngtcp2_rst;
typedef struct ngtcp2_cc ngtcp2_cc;

/* NGTCP2_FRAME_CHAIN_BINDER_FLAG_NONE indicates that no flag is
   set. */
#define NGTCP2_FRAME_CHAIN_BINDER_FLAG_NONE 0x00u
/* NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK indicates that an information
   which a frame carries has been acknowledged. */
#define NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK 0x01u

/*
 * ngtcp2_frame_chain_binder binds 2 or more of ngtcp2_frame_chain to
 * share the acknowledgement state.  In general, all
 * ngtcp2_frame_chains bound to the same binder must have the same
 * information.
 */
typedef struct ngtcp2_frame_chain_binder {
  size_t refcount;
  /* flags is bitwise OR of zero or more of
     NGTCP2_FRAME_CHAIN_BINDER_FLAG_*. */
  uint32_t flags;
} ngtcp2_frame_chain_binder;

int ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder **pbinder,
                                  const ngtcp2_mem *mem);

typedef struct ngtcp2_frame_chain ngtcp2_frame_chain;

/*
 * ngtcp2_frame_chain chains frames in a single packet.
 */
struct ngtcp2_frame_chain {
  union {
    struct {
      ngtcp2_frame_chain *next;
      ngtcp2_frame_chain_binder *binder;
      ngtcp2_frame fr;
    };

    ngtcp2_opl_entry oplent;
  };
};

ngtcp2_objalloc_def(frame_chain, ngtcp2_frame_chain, oplent);

/*
 * ngtcp2_bind_frame_chains binds two frame chains |a| and |b| using
 * new or existing ngtcp2_frame_chain_binder.  |a| might have non-NULL
 * a->binder.  |b| must not have non-NULL b->binder.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGTCP2_ERR_NOMEM
 *     Out of memory
 */
int ngtcp2_bind_frame_chains(ngtcp2_frame_chain *a, ngtcp2_frame_chain *b,
                             const ngtcp2_mem *mem);

/* NGTCP2_MAX_STREAM_DATACNT is the maximum number of ngtcp2_vec that
   a ngtcp2_stream can include. */
#define NGTCP2_MAX_STREAM_DATACNT 256

/* NGTCP2_MAX_CRYPTO_DATACNT is the maximum number of ngtcp2_vec that
   a ngtcp2_crypto can include. */
#define NGTCP2_MAX_CRYPTO_DATACNT 8

/*
 * ngtcp2_frame_chain_new allocates ngtcp2_frame_chain object and
 * assigns its pointer to |*pfrc|.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGTCP2_ERR_NOMEM
 *     Out of memory.
 */
int ngtcp2_frame_chain_new(ngtcp2_frame_chain **pfrc, const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_objalloc_new behaves like
 * ngtcp2_frame_chain_new, but it uses |objalloc| to allocate the object.
 */
int ngtcp2_frame_chain_objalloc_new(ngtcp2_frame_chain **pfrc,
                                    ngtcp2_objalloc *objalloc);

/*
 * ngtcp2_frame_chain_extralen_new works like ngtcp2_frame_chain_new,
 * but it allocates extra memory |extralen| in order to extend
 * ngtcp2_frame.
 */
int ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain **pfrc, size_t extralen,
                                    const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_stream_datacnt_objalloc_new works like
 * ngtcp2_frame_chain_new, but it allocates enough data to store
 * additional |datacnt| - 1 ngtcp2_vec object after ngtcp2_stream
 * object.  If no additional space is required,
 * ngtcp2_frame_chain_objalloc_new is called internally.
 */
int ngtcp2_frame_chain_stream_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc,
                                                   size_t datacnt,
                                                   ngtcp2_objalloc *objalloc,
                                                   const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_crypto_datacnt_objalloc_new works like
 * ngtcp2_frame_chain_new, but it allocates enough data to store
 * additional |datacnt| - 1 ngtcp2_vec object after ngtcp2_crypto
 * object.  If no additional space is required,
 * ngtcp2_frame_chain_objalloc_new is called internally.
 */
int ngtcp2_frame_chain_crypto_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc,
                                                   size_t datacnt,
                                                   ngtcp2_objalloc *objalloc,
                                                   const ngtcp2_mem *mem);

int ngtcp2_frame_chain_new_token_objalloc_new(ngtcp2_frame_chain **pfrc,
                                              const ngtcp2_vec *token,
                                              ngtcp2_objalloc *objalloc,
                                              const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_del deallocates |frc|.  It also deallocates the
 * memory pointed by |frc|.
 */
void ngtcp2_frame_chain_del(ngtcp2_frame_chain *frc, const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_objalloc_del adds |frc| to |objalloc| for reuse.
 * It might just delete |frc| depending on the frame type and the size
 * of |frc|.
 */
void ngtcp2_frame_chain_objalloc_del(ngtcp2_frame_chain *frc,
                                     ngtcp2_objalloc *objalloc,
                                     const ngtcp2_mem *mem);

/*
 * ngtcp2_frame_chain_init initializes |frc|.
 */
void ngtcp2_frame_chain_init(ngtcp2_frame_chain *frc);

/*
 * ngtcp2_frame_chain_list_objalloc_del adds all ngtcp2_frame_chain
 * linked from |frc| to |objalloc| for reuse.  Depending on the frame type
 * and its size, ngtcp2_frame_chain might be deleted instead.
 */
void ngtcp2_frame_chain_list_objalloc_del(ngtcp2_frame_chain *frc,
                                          ngtcp2_objalloc *objalloc,
                                          const ngtcp2_mem *mem);

/* NGTCP2_RTB_ENTRY_FLAG_NONE indicates that no flag is set. */
#define NGTCP2_RTB_ENTRY_FLAG_NONE 0x00u
/* NGTCP2_RTB_ENTRY_FLAG_PROBE indicates that the entry includes a
   probe packet. */
#define NGTCP2_RTB_ENTRY_FLAG_PROBE 0x01u
/* NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE indicates that the entry
   includes a frame which must be retransmitted until it is
   acknowledged.  In most cases, this flag is used along with
   NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING and
   NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING. */
#define NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE 0x02u
/* NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING indicates that the entry
   elicits acknowledgement. */
#define NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING 0x04u
/* NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED indicates that the packet has
   been reclaimed on PTO.  It is not marked lost yet and still
   consumes congestion window. */
#define NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED 0x08u
/* NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED indicates that the entry
   has been marked lost and, optionally, scheduled to retransmit. */
#define NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED 0x10u
/* NGTCP2_RTB_ENTRY_FLAG_ECN indicates that the entry is included in a
   UDP datagram with ECN marking. */
#define NGTCP2_RTB_ENTRY_FLAG_ECN 0x20u
/* NGTCP2_RTB_ENTRY_FLAG_DATAGRAM indicates that the entry includes
   DATAGRAM frame. */
#define NGTCP2_RTB_ENTRY_FLAG_DATAGRAM 0x40u
/* NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE indicates that the entry includes
   a PMTUD probe packet. */
#define NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE 0x80u
/* NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING indicates that the entry
   includes a packet which elicits PTO probe packets. */
#define NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING 0x100u

typedef struct ngtcp2_rtb_entry ngtcp2_rtb_entry;

/*
 * ngtcp2_rtb_entry is an object stored in ngtcp2_rtb.  It corresponds
 * to the one packet which is waiting for its ACK.
 */
struct ngtcp2_rtb_entry {
  union {
    struct {
      ngtcp2_rtb_entry *next;

      struct {
        int64_t pkt_num;
        uint8_t type;
        uint8_t flags;
      } hd;
      ngtcp2_frame_chain *frc;
      /* ts is the time point when a packet included in this entry is sent
         to a peer. */
      ngtcp2_tstamp ts;
      /* lost_ts is the time when this entry is marked lost. */
      ngtcp2_tstamp lost_ts;
      /* pktlen is the length of QUIC packet */
      size_t pktlen;
      struct {
        uint64_t delivered;
        ngtcp2_tstamp delivered_ts;
        ngtcp2_tstamp first_sent_ts;
        uint64_t tx_in_flight;
        uint64_t lost;
        int is_app_limited;
      } rst;
      /* flags is bitwise-OR of zero or more of
         NGTCP2_RTB_ENTRY_FLAG_*. */
      uint16_t flags;
    };

    ngtcp2_opl_entry oplent;
  };
};

ngtcp2_objalloc_def(rtb_entry, ngtcp2_rtb_entry, oplent);

/*
 * ngtcp2_rtb_entry_new allocates ngtcp2_rtb_entry object, and assigns
 * its pointer to |*pent|.
 */
int ngtcp2_rtb_entry_objalloc_new(ngtcp2_rtb_entry **pent,
                                  const ngtcp2_pkt_hd *hd,
                                  ngtcp2_frame_chain *frc, ngtcp2_tstamp ts,
                                  size_t pktlen, uint16_t flags,
                                  ngtcp2_objalloc *objalloc);

/*
 * ngtcp2_rtb_entry_objalloc_del adds |ent| to |objalloc| for reuse.
 * ngtcp2_frame_chain linked from ent->frc are also added to
 * |frc_objalloc| depending on their frame type and size.
 */
void ngtcp2_rtb_entry_objalloc_del(ngtcp2_rtb_entry *ent,
                                   ngtcp2_objalloc *objalloc,
                                   ngtcp2_objalloc *frc_objalloc,
                                   const ngtcp2_mem *mem);

/*
 * ngtcp2_rtb tracks sent packets, and its ACK timeout for
 * retransmission.
 */
typedef struct ngtcp2_rtb {
  ngtcp2_objalloc *frc_objalloc;
  ngtcp2_objalloc *rtb_entry_objalloc;
  /* ents includes ngtcp2_rtb_entry sorted by decreasing order of
     packet number. */
  ngtcp2_ksl ents;
  /* crypto is CRYPTO stream. */
  ngtcp2_strm *crypto;
  ngtcp2_rst *rst;
  ngtcp2_cc *cc;
  ngtcp2_log *log;
  ngtcp2_qlog *qlog;
  const ngtcp2_mem *mem;
  /* largest_acked_tx_pkt_num is the largest packet number
     acknowledged by the peer. */
  int64_t largest_acked_tx_pkt_num;
  /* num_ack_eliciting is the number of ACK eliciting entries. */
  size_t num_ack_eliciting;
  /* num_retransmittable is the number of packets which contain frames
     that must be retransmitted on loss. */
  size_t num_retransmittable;
  /* num_pto_eliciting is the number of packets that elicit PTO probe
     packets. */
  size_t num_pto_eliciting;
  /* probe_pkt_left is the number of probe packet to send */
  size_t probe_pkt_left;
  /* pktns_id is the identifier of packet number space. */
  ngtcp2_pktns_id pktns_id;
  /* cc_pkt_num is the smallest packet number that is contributed to
     ngtcp2_conn_stat.bytes_in_flight. */
  int64_t cc_pkt_num;
  /* cc_bytes_in_flight is the number of in-flight bytes that is
     contributed to ngtcp2_conn_stat.bytes_in_flight.  It only
     includes the bytes after congestion state is reset. */
  uint64_t cc_bytes_in_flight;
  /* persistent_congestion_start_ts is the time when persistent
     congestion evaluation is started.  It happens roughly after
     handshake is confirmed. */
  ngtcp2_tstamp persistent_congestion_start_ts;
  /* num_lost_pkts is the number entries in ents which has
     NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED flag set. */
  size_t num_lost_pkts;
  /* num_lost_pmtud_pkts is the number of entries in ents which have
     both NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED and
     NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE flags set. */
  size_t num_lost_pmtud_pkts;
} ngtcp2_rtb;

/*
 * ngtcp2_rtb_init initializes |rtb|.
 */
void ngtcp2_rtb_init(ngtcp2_rtb *rtb, ngtcp2_pktns_id pktns_id,
                     ngtcp2_strm *crypto, ngtcp2_rst *rst, ngtcp2_cc *cc,
                     ngtcp2_log *log, ngtcp2_qlog *qlog,
                     ngtcp2_objalloc *rtb_entry_objalloc,
                     ngtcp2_objalloc *frc_objalloc, const ngtcp2_mem *mem);

/*
 * ngtcp2_rtb_free deallocates resources allocated for |rtb|.
 */
void ngtcp2_rtb_free(ngtcp2_rtb *rtb);

/*
 * ngtcp2_rtb_add adds |ent| to |rtb|.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGTCP2_ERR_NOMEM
 *     Out of memory
 */
int ngtcp2_rtb_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
                   ngtcp2_conn_stat *cstat);

/*
 * ngtcp2_rtb_head returns the iterator which points to the entry
 * which has the largest packet number.  If there is no entry,
 * returned value satisfies ngtcp2_ksl_it_end(&it) != 0.
 */
ngtcp2_ksl_it ngtcp2_rtb_head(ngtcp2_rtb *rtb);

/*
 * ngtcp2_rtb_recv_ack removes acked ngtcp2_rtb_entry from |rtb|.
 * |pkt_num| is a packet number which includes |fr|.  |pkt_ts| is the
 * timestamp when packet is received.  |ts| should be the current
 * time.  Usually they are the same, but for buffered packets,
 * |pkt_ts| would be earlier than |ts|.
 *
 * This function returns the number of newly acknowledged packets if
 * it succeeds, or one of the following negative error codes:
 *
 * NGTCP2_ERR_CALLBACK_FAILURE
 *     User callback failed
 * NGTCP2_ERR_NOMEM
 *     Out of memory
 */
ngtcp2_ssize ngtcp2_rtb_recv_ack(ngtcp2_rtb *rtb, const ngtcp2_ack *fr,
                                 ngtcp2_conn_stat *cstat, ngtcp2_conn *conn,
                                 ngtcp2_pktns *pktns, ngtcp2_tstamp pkt_ts,
                                 ngtcp2_tstamp ts);

/*
 * ngtcp2_rtb_detect_lost_pkt detects lost packets and prepends the
 * frames contained them to |*pfrc|.  Even when this function fails,
 * some frames might be prepended to |*pfrc| and the caller should
 * handle them.
 */
int ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
                               ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat,
                               ngtcp2_tstamp ts);

/*
 * ngtcp2_rtb_remove_expired_lost_pkt removes expired lost packet.
 */
void ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_duration pto,
                                        ngtcp2_tstamp ts);

/*
 * ngtcp2_rtb_lost_pkt_ts returns the earliest time when the still
 * retained packet was lost.  It returns UINT64_MAX if no such packet
 * exists.
 */
ngtcp2_tstamp ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb *rtb);

/*
 * ngtcp2_rtb_remove_all removes all packets from |rtb| and prepends
 * all frames to |*pfrc|.  Even when this function fails, some frames
 * might be prepended to |*pfrc| and the caller should handle them.
 */
int ngtcp2_rtb_remove_all(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
                          ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat);

/*
 * ngtcp2_rtb_remove_early_data removes all entries for 0RTT packets.
 */
void ngtcp2_rtb_remove_early_data(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat);

/*
 * ngtcp2_rtb_empty returns nonzero if |rtb| have no entry.
 */
int ngtcp2_rtb_empty(ngtcp2_rtb *rtb);

/*
 * ngtcp2_rtb_reset_cc_state resets congestion state in |rtb|.
 * |cc_pkt_num| is the next outbound packet number which is sent under
 * new congestion state.
 */
void ngtcp2_rtb_reset_cc_state(ngtcp2_rtb *rtb, int64_t cc_pkt_num);

/*
 * ngtcp2_rtb_remove_expired_lost_pkt ensures that the number of lost
 * packets at most |n|.
 */
void ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb *rtb, size_t n);

/*
 * ngtcp2_rtb_reclaim_on_pto reclaims up to |num_pkts| packets which
 * are in-flight and not marked lost to send them in PTO probe.  The
 * reclaimed frames are chained to |*pfrc|.
 *
 * This function returns the number of packets reclaimed if it
 * succeeds, or one of the following negative error codes:
 *
 * NGTCP2_ERR_NOMEM
 *     Out of memory
 */
ngtcp2_ssize ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
                                       ngtcp2_pktns *pktns, size_t num_pkts);

#endif /* NGTCP2_RTB_H */