summaryrefslogtreecommitdiffstats
path: root/lib/ngtcp2_rtb.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/ngtcp2_rtb.h466
1 files changed, 466 insertions, 0 deletions
diff --git a/lib/ngtcp2_rtb.h b/lib/ngtcp2_rtb.h
new file mode 100644
index 0000000..a97805d
--- /dev/null
+++ b/lib/ngtcp2_rtb.h
@@ -0,0 +1,466 @@
+/*
+ * 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 */