/* * 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 #endif /* HAVE_CONFIG_H */ #include #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 uint8_t *token, size_t tokenlen, 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 */