diff options
Diffstat (limited to '')
| -rw-r--r-- | lib/ngtcp2_rtb.c | 1673 |
1 files changed, 1673 insertions, 0 deletions
diff --git a/lib/ngtcp2_rtb.c b/lib/ngtcp2_rtb.c new file mode 100644 index 0000000..18db04b --- /dev/null +++ b/lib/ngtcp2_rtb.c @@ -0,0 +1,1673 @@ +/* + * 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. + */ +#include "ngtcp2_rtb.h" + +#include <assert.h> +#include <string.h> + +#include "ngtcp2_macro.h" +#include "ngtcp2_conn.h" +#include "ngtcp2_log.h" +#include "ngtcp2_vec.h" +#include "ngtcp2_cc.h" +#include "ngtcp2_rcvry.h" +#include "ngtcp2_rst.h" +#include "ngtcp2_unreachable.h" + +int ngtcp2_frame_chain_new(ngtcp2_frame_chain **pfrc, const ngtcp2_mem *mem) { + *pfrc = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_frame_chain)); + if (*pfrc == NULL) { + return NGTCP2_ERR_NOMEM; + } + + ngtcp2_frame_chain_init(*pfrc); + + return 0; +} + +int ngtcp2_frame_chain_objalloc_new(ngtcp2_frame_chain **pfrc, + ngtcp2_objalloc *objalloc) { + *pfrc = ngtcp2_objalloc_frame_chain_get(objalloc); + if (*pfrc == NULL) { + return NGTCP2_ERR_NOMEM; + } + + ngtcp2_frame_chain_init(*pfrc); + + return 0; +} + +int ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain **pfrc, size_t extralen, + const ngtcp2_mem *mem) { + *pfrc = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_frame_chain) + extralen); + if (*pfrc == NULL) { + return NGTCP2_ERR_NOMEM; + } + + ngtcp2_frame_chain_init(*pfrc); + + return 0; +} + +int ngtcp2_frame_chain_stream_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc, + size_t datacnt, + ngtcp2_objalloc *objalloc, + const ngtcp2_mem *mem) { + size_t need, avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_stream); + + if (datacnt > 1) { + need = sizeof(ngtcp2_vec) * (datacnt - 1); + + if (need > avail) { + return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem); + } + } + + return ngtcp2_frame_chain_objalloc_new(pfrc, objalloc); +} + +int ngtcp2_frame_chain_crypto_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc, + size_t datacnt, + ngtcp2_objalloc *objalloc, + const ngtcp2_mem *mem) { + size_t need, avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_crypto); + + if (datacnt > 1) { + need = sizeof(ngtcp2_vec) * (datacnt - 1); + + if (need > avail) { + return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem); + } + } + + return ngtcp2_frame_chain_objalloc_new(pfrc, objalloc); +} + +int ngtcp2_frame_chain_new_token_objalloc_new(ngtcp2_frame_chain **pfrc, + const ngtcp2_vec *token, + ngtcp2_objalloc *objalloc, + const ngtcp2_mem *mem) { + size_t avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_new_token); + int rv; + uint8_t *p; + ngtcp2_frame *fr; + + if (token->len > avail) { + rv = ngtcp2_frame_chain_extralen_new(pfrc, token->len - avail, mem); + } else { + rv = ngtcp2_frame_chain_objalloc_new(pfrc, objalloc); + } + if (rv != 0) { + return rv; + } + + fr = &(*pfrc)->fr; + fr->type = NGTCP2_FRAME_NEW_TOKEN; + + p = (uint8_t *)fr + sizeof(ngtcp2_new_token); + memcpy(p, token->base, token->len); + + ngtcp2_vec_init(&fr->new_token.token, p, token->len); + + return 0; +} + +void ngtcp2_frame_chain_del(ngtcp2_frame_chain *frc, const ngtcp2_mem *mem) { + ngtcp2_frame_chain_binder *binder; + + if (frc == NULL) { + return; + } + + binder = frc->binder; + if (binder && --binder->refcount == 0) { + ngtcp2_mem_free(mem, binder); + } + + ngtcp2_mem_free(mem, frc); +} + +void ngtcp2_frame_chain_objalloc_del(ngtcp2_frame_chain *frc, + ngtcp2_objalloc *objalloc, + const ngtcp2_mem *mem) { + ngtcp2_frame_chain_binder *binder; + + if (frc == NULL) { + return; + } + + switch (frc->fr.type) { + case NGTCP2_FRAME_STREAM: + if (frc->fr.stream.datacnt && + sizeof(ngtcp2_vec) * (frc->fr.stream.datacnt - 1) > + sizeof(ngtcp2_frame) - sizeof(ngtcp2_stream)) { + ngtcp2_frame_chain_del(frc, mem); + + return; + } + + break; + case NGTCP2_FRAME_CRYPTO: + if (frc->fr.crypto.datacnt && + sizeof(ngtcp2_vec) * (frc->fr.crypto.datacnt - 1) > + sizeof(ngtcp2_frame) - sizeof(ngtcp2_crypto)) { + ngtcp2_frame_chain_del(frc, mem); + + return; + } + + break; + case NGTCP2_FRAME_NEW_TOKEN: + if (frc->fr.new_token.token.len > + sizeof(ngtcp2_frame) - sizeof(ngtcp2_new_token)) { + ngtcp2_frame_chain_del(frc, mem); + + return; + } + + break; + } + + binder = frc->binder; + if (binder && --binder->refcount == 0) { + ngtcp2_mem_free(mem, binder); + } + + frc->binder = NULL; + + ngtcp2_objalloc_frame_chain_release(objalloc, frc); +} + +void ngtcp2_frame_chain_init(ngtcp2_frame_chain *frc) { + frc->next = NULL; + frc->binder = NULL; +} + +void ngtcp2_frame_chain_list_objalloc_del(ngtcp2_frame_chain *frc, + ngtcp2_objalloc *objalloc, + const ngtcp2_mem *mem) { + ngtcp2_frame_chain *next; + + for (; frc; frc = next) { + next = frc->next; + + ngtcp2_frame_chain_objalloc_del(frc, objalloc, mem); + } +} + +int ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder **pbinder, + const ngtcp2_mem *mem) { + *pbinder = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_frame_chain_binder)); + if (*pbinder == NULL) { + return NGTCP2_ERR_NOMEM; + } + + return 0; +} + +int ngtcp2_bind_frame_chains(ngtcp2_frame_chain *a, ngtcp2_frame_chain *b, + const ngtcp2_mem *mem) { + ngtcp2_frame_chain_binder *binder; + int rv; + + assert(b->binder == NULL); + + if (a->binder == NULL) { + rv = ngtcp2_frame_chain_binder_new(&binder, mem); + if (rv != 0) { + return rv; + } + + a->binder = binder; + ++a->binder->refcount; + } + + b->binder = a->binder; + ++b->binder->refcount; + + return 0; +} + +static void rtb_entry_init(ngtcp2_rtb_entry *ent, const ngtcp2_pkt_hd *hd, + ngtcp2_frame_chain *frc, ngtcp2_tstamp ts, + size_t pktlen, uint16_t flags) { + memset(ent, 0, sizeof(*ent)); + + ent->hd.pkt_num = hd->pkt_num; + ent->hd.type = hd->type; + ent->hd.flags = hd->flags; + ent->frc = frc; + ent->ts = ts; + ent->lost_ts = UINT64_MAX; + ent->pktlen = pktlen; + ent->flags = flags; + ent->next = NULL; +} + +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) { + *pent = ngtcp2_objalloc_rtb_entry_get(objalloc); + if (*pent == NULL) { + return NGTCP2_ERR_NOMEM; + } + + rtb_entry_init(*pent, hd, frc, ts, pktlen, flags); + + return 0; +} + +void ngtcp2_rtb_entry_objalloc_del(ngtcp2_rtb_entry *ent, + ngtcp2_objalloc *objalloc, + ngtcp2_objalloc *frc_objalloc, + const ngtcp2_mem *mem) { + ngtcp2_frame_chain_list_objalloc_del(ent->frc, frc_objalloc, mem); + + ent->frc = NULL; + + ngtcp2_objalloc_rtb_entry_release(objalloc, ent); +} + +static int greater(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) { + return *(int64_t *)lhs > *(int64_t *)rhs; +} + +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) { + rtb->rtb_entry_objalloc = rtb_entry_objalloc; + rtb->frc_objalloc = frc_objalloc; + ngtcp2_ksl_init(&rtb->ents, greater, sizeof(int64_t), mem); + rtb->crypto = crypto; + rtb->rst = rst; + rtb->cc = cc; + rtb->log = log; + rtb->qlog = qlog; + rtb->mem = mem; + rtb->largest_acked_tx_pkt_num = -1; + rtb->num_ack_eliciting = 0; + rtb->num_retransmittable = 0; + rtb->num_pto_eliciting = 0; + rtb->probe_pkt_left = 0; + rtb->pktns_id = pktns_id; + rtb->cc_pkt_num = 0; + rtb->cc_bytes_in_flight = 0; + rtb->persistent_congestion_start_ts = UINT64_MAX; + rtb->num_lost_pkts = 0; + rtb->num_lost_pmtud_pkts = 0; +} + +void ngtcp2_rtb_free(ngtcp2_rtb *rtb) { + ngtcp2_ksl_it it; + + if (rtb == NULL) { + return; + } + + it = ngtcp2_ksl_begin(&rtb->ents); + + for (; !ngtcp2_ksl_it_end(&it); ngtcp2_ksl_it_next(&it)) { + ngtcp2_rtb_entry_objalloc_del(ngtcp2_ksl_it_get(&it), + rtb->rtb_entry_objalloc, rtb->frc_objalloc, + rtb->mem); + } + + ngtcp2_ksl_free(&rtb->ents); +} + +static void rtb_on_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, + ngtcp2_conn_stat *cstat) { + ngtcp2_rst_on_pkt_sent(rtb->rst, ent, cstat); + + assert(rtb->cc_pkt_num <= ent->hd.pkt_num); + + cstat->bytes_in_flight += ent->pktlen; + rtb->cc_bytes_in_flight += ent->pktlen; + + ngtcp2_rst_update_app_limited(rtb->rst, cstat); + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) { + ++rtb->num_ack_eliciting; + } + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) { + ++rtb->num_retransmittable; + } + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) { + ++rtb->num_pto_eliciting; + } +} + +static size_t rtb_on_remove(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, + ngtcp2_conn_stat *cstat) { + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) { + assert(rtb->num_lost_pkts); + --rtb->num_lost_pkts; + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + assert(rtb->num_lost_pmtud_pkts); + --rtb->num_lost_pmtud_pkts; + } + + return 0; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) { + assert(rtb->num_ack_eliciting); + --rtb->num_ack_eliciting; + } + + if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) && + !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED)) { + assert(rtb->num_retransmittable); + --rtb->num_retransmittable; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) { + assert(rtb->num_pto_eliciting); + --rtb->num_pto_eliciting; + } + + if (rtb->cc_pkt_num <= ent->hd.pkt_num) { + assert(cstat->bytes_in_flight >= ent->pktlen); + cstat->bytes_in_flight -= ent->pktlen; + + assert(rtb->cc_bytes_in_flight >= ent->pktlen); + rtb->cc_bytes_in_flight -= ent->pktlen; + + /* If PMTUD packet is lost, we do not report the lost bytes to the + caller in order to ignore loss of PMTUD packet. */ + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + return 0; + } + + return ent->pktlen; + } + + return 0; +} + +/* NGTCP2_RECLAIM_FLAG_NONE indicates that no flag is set. */ +#define NGTCP2_RECLAIM_FLAG_NONE 0x00u +/* NGTCP2_RECLAIM_FLAG_ON_LOSS indicates that frames are reclaimed + because of the packet loss.*/ +#define NGTCP2_RECLAIM_FLAG_ON_LOSS 0x01u + +/* + * rtb_reclaim_frame queues unacknowledged frames included in |ent| + * for retransmission. The re-queued frames are not deleted from + * |ent|. It returns the number of frames queued. |flags| is bitwise + * OR of 0 or more of NGTCP2_RECLAIM_FLAG_*. + */ +static ngtcp2_ssize rtb_reclaim_frame(ngtcp2_rtb *rtb, uint8_t flags, + ngtcp2_conn *conn, ngtcp2_pktns *pktns, + ngtcp2_rtb_entry *ent) { + ngtcp2_frame_chain *frc, *nfrc, **pfrc = &pktns->tx.frq; + ngtcp2_frame *fr; + ngtcp2_strm *strm; + ngtcp2_range gap, range; + size_t num_reclaimed = 0; + int rv; + int streamfrq_empty; + + assert(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE); + + /* TODO Reconsider the order of pfrc */ + for (frc = ent->frc; frc; frc = frc->next) { + fr = &frc->fr; + /* Check that a late ACK acknowledged this frame. */ + if (frc->binder && + (frc->binder->flags & NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK)) { + continue; + } + switch (frc->fr.type) { + case NGTCP2_FRAME_STREAM: + strm = ngtcp2_conn_find_stream(conn, fr->stream.stream_id); + if (strm == NULL) { + continue; + } + + gap = ngtcp2_strm_get_unacked_range_after(strm, fr->stream.offset); + + range.begin = fr->stream.offset; + range.end = fr->stream.offset + + ngtcp2_vec_len(fr->stream.data, fr->stream.datacnt); + range = ngtcp2_range_intersect(&range, &gap); + if (ngtcp2_range_len(&range) == 0) { + if (!fr->stream.fin) { + /* 0 length STREAM frame with offset == 0 must be + retransmitted if no non-empty data is sent to this stream + and no data in this stream is acknowledged. */ + if (fr->stream.offset != 0 || fr->stream.datacnt != 0 || + strm->tx.offset || (strm->flags & NGTCP2_STRM_FLAG_ANY_ACKED)) { + continue; + } + } else if (strm->flags & NGTCP2_STRM_FLAG_FIN_ACKED) { + continue; + } + } + + if ((flags & NGTCP2_RECLAIM_FLAG_ON_LOSS) && + ent->hd.pkt_num != strm->tx.last_lost_pkt_num) { + strm->tx.last_lost_pkt_num = ent->hd.pkt_num; + ++strm->tx.loss_count; + } + + rv = ngtcp2_frame_chain_stream_datacnt_objalloc_new( + &nfrc, fr->stream.datacnt, rtb->frc_objalloc, rtb->mem); + if (rv != 0) { + return rv; + } + + nfrc->fr = *fr; + ngtcp2_vec_copy(nfrc->fr.stream.data, fr->stream.data, + fr->stream.datacnt); + + streamfrq_empty = ngtcp2_strm_streamfrq_empty(strm); + rv = ngtcp2_strm_streamfrq_push(strm, nfrc); + if (rv != 0) { + ngtcp2_frame_chain_objalloc_del(nfrc, rtb->frc_objalloc, rtb->mem); + return rv; + } + if (!ngtcp2_strm_is_tx_queued(strm)) { + strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn); + rv = ngtcp2_conn_tx_strmq_push(conn, strm); + if (rv != 0) { + return rv; + } + } + if (streamfrq_empty) { + ++conn->tx.strmq_nretrans; + } + + ++num_reclaimed; + + continue; + case NGTCP2_FRAME_CRYPTO: + /* Don't resend CRYPTO frame if the whole region it contains has + been acknowledged */ + gap = ngtcp2_strm_get_unacked_range_after(rtb->crypto, fr->crypto.offset); + + range.begin = fr->crypto.offset; + range.end = fr->crypto.offset + + ngtcp2_vec_len(fr->crypto.data, fr->crypto.datacnt); + range = ngtcp2_range_intersect(&range, &gap); + if (ngtcp2_range_len(&range) == 0) { + continue; + } + + rv = ngtcp2_frame_chain_crypto_datacnt_objalloc_new( + &nfrc, fr->crypto.datacnt, rtb->frc_objalloc, rtb->mem); + if (rv != 0) { + return rv; + } + + nfrc->fr = *fr; + ngtcp2_vec_copy(nfrc->fr.crypto.data, fr->crypto.data, + fr->crypto.datacnt); + + rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL, + &nfrc->fr.crypto.offset, nfrc); + if (rv != 0) { + assert(ngtcp2_err_is_fatal(rv)); + ngtcp2_frame_chain_objalloc_del(nfrc, rtb->frc_objalloc, rtb->mem); + return rv; + } + + ++num_reclaimed; + + continue; + case NGTCP2_FRAME_NEW_TOKEN: + rv = ngtcp2_frame_chain_new_token_objalloc_new( + &nfrc, &fr->new_token.token, rtb->frc_objalloc, rtb->mem); + if (rv != 0) { + return rv; + } + + rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem); + if (rv != 0) { + return rv; + } + + break; + case NGTCP2_FRAME_DATAGRAM: + case NGTCP2_FRAME_DATAGRAM_LEN: + continue; + default: + rv = ngtcp2_frame_chain_objalloc_new(&nfrc, rtb->frc_objalloc); + if (rv != 0) { + return rv; + } + + nfrc->fr = *fr; + + rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem); + if (rv != 0) { + return rv; + } + + break; + } + + ++num_reclaimed; + + nfrc->next = *pfrc; + *pfrc = nfrc; + pfrc = &nfrc->next; + } + + return (ngtcp2_ssize)num_reclaimed; +} + +/* + * conn_process_lost_datagram calls ngtcp2_lost_datagram callback for + * lost DATAGRAM frames. + */ +static int conn_process_lost_datagram(ngtcp2_conn *conn, + ngtcp2_rtb_entry *ent) { + ngtcp2_frame_chain *frc; + int rv; + + for (frc = ent->frc; frc; frc = frc->next) { + switch (frc->fr.type) { + case NGTCP2_FRAME_DATAGRAM: + case NGTCP2_FRAME_DATAGRAM_LEN: + assert(conn->callbacks.lost_datagram); + + rv = conn->callbacks.lost_datagram(conn, frc->fr.datagram.dgram_id, + conn->user_data); + if (rv != 0) { + return NGTCP2_ERR_CALLBACK_FAILURE; + } + break; + } + } + + return 0; +} + +static int rtb_on_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it, + ngtcp2_rtb_entry *ent, ngtcp2_conn_stat *cstat, + ngtcp2_conn *conn, ngtcp2_pktns *pktns, + ngtcp2_tstamp ts) { + int rv; + ngtcp2_ssize reclaimed; + ngtcp2_cc *cc = rtb->cc; + ngtcp2_cc_pkt pkt; + + ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags, + ent->ts); + + if (rtb->qlog) { + ngtcp2_qlog_pkt_lost(rtb->qlog, ent); + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + ++rtb->num_lost_pmtud_pkts; + } else if (rtb->cc->on_pkt_lost) { + cc->on_pkt_lost(cc, cstat, + ngtcp2_cc_pkt_init(&pkt, ent->hd.pkt_num, ent->pktlen, + rtb->pktns_id, ent->ts, ent->rst.lost, + ent->rst.tx_in_flight, + ent->rst.is_app_limited), + ts); + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED) { + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "pkn=%" PRId64 " has already been reclaimed on PTO", + ent->hd.pkt_num); + assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)); + assert(UINT64_MAX == ent->lost_ts); + + ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED; + ent->lost_ts = ts; + + ++rtb->num_lost_pkts; + + ngtcp2_ksl_it_next(it); + + return 0; + } + + if (conn->callbacks.lost_datagram && + (ent->flags & NGTCP2_RTB_ENTRY_FLAG_DATAGRAM)) { + rv = conn_process_lost_datagram(conn, ent); + if (rv != 0) { + return rv; + } + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) { + assert(ent->frc); + assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)); + assert(UINT64_MAX == ent->lost_ts); + + reclaimed = + rtb_reclaim_frame(rtb, NGTCP2_RECLAIM_FLAG_ON_LOSS, conn, pktns, ent); + if (reclaimed < 0) { + return (int)reclaimed; + } + } + + ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED; + ent->lost_ts = ts; + + ++rtb->num_lost_pkts; + + ngtcp2_ksl_it_next(it); + + return 0; +} + +int ngtcp2_rtb_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, + ngtcp2_conn_stat *cstat) { + int rv; + + rv = ngtcp2_ksl_insert(&rtb->ents, NULL, &ent->hd.pkt_num, ent); + if (rv != 0) { + return rv; + } + + rtb_on_add(rtb, ent, cstat); + + return 0; +} + +ngtcp2_ksl_it ngtcp2_rtb_head(ngtcp2_rtb *rtb) { + return ngtcp2_ksl_begin(&rtb->ents); +} + +static void rtb_remove(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it, + ngtcp2_rtb_entry **pent, ngtcp2_rtb_entry *ent, + ngtcp2_conn_stat *cstat) { + int rv; + (void)rv; + + rv = ngtcp2_ksl_remove_hint(&rtb->ents, it, it, &ent->hd.pkt_num); + assert(0 == rv); + rtb_on_remove(rtb, ent, cstat); + + assert(ent->next == NULL); + + ngtcp2_list_insert(ent, pent); +} + +static void conn_ack_crypto_data(ngtcp2_conn *conn, ngtcp2_pktns *pktns, + uint64_t datalen) { + ngtcp2_buf_chain **pbufchain, *bufchain; + size_t left; + + for (pbufchain = &pktns->crypto.tx.data; *pbufchain;) { + left = ngtcp2_buf_len(&(*pbufchain)->buf); + if (left > datalen) { + (*pbufchain)->buf.pos += datalen; + return; + } + + bufchain = *pbufchain; + *pbufchain = bufchain->next; + + ngtcp2_mem_free(conn->mem, bufchain); + + datalen -= left; + + if (datalen == 0) { + return; + } + } + + assert(datalen == 0); + + return; +} + +static int rtb_process_acked_pkt(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, + ngtcp2_conn *conn) { + ngtcp2_frame_chain *frc; + uint64_t prev_stream_offset, stream_offset; + ngtcp2_strm *strm; + int rv; + uint64_t datalen; + ngtcp2_strm *crypto = rtb->crypto; + ngtcp2_pktns *pktns = NULL; + + if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) && conn->pmtud && + conn->pmtud->tx_pkt_num <= ent->hd.pkt_num) { + ngtcp2_pmtud_probe_success(conn->pmtud, ent->pktlen); + + conn->dcid.current.max_udp_payload_size = + ngtcp2_max(conn->dcid.current.max_udp_payload_size, ent->pktlen); + + if (ngtcp2_pmtud_finished(conn->pmtud)) { + ngtcp2_conn_stop_pmtud(conn); + } + } + + for (frc = ent->frc; frc; frc = frc->next) { + if (frc->binder) { + frc->binder->flags |= NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK; + } + + switch (frc->fr.type) { + case NGTCP2_FRAME_STREAM: + strm = ngtcp2_conn_find_stream(conn, frc->fr.stream.stream_id); + if (strm == NULL) { + break; + } + + strm->flags |= NGTCP2_STRM_FLAG_ANY_ACKED; + + if (frc->fr.stream.fin) { + strm->flags |= NGTCP2_STRM_FLAG_FIN_ACKED; + } + + prev_stream_offset = ngtcp2_strm_get_acked_offset(strm); + rv = ngtcp2_strm_ack_data( + strm, frc->fr.stream.offset, + ngtcp2_vec_len(frc->fr.stream.data, frc->fr.stream.datacnt)); + if (rv != 0) { + return rv; + } + + if (conn->callbacks.acked_stream_data_offset) { + stream_offset = ngtcp2_strm_get_acked_offset(strm); + datalen = stream_offset - prev_stream_offset; + if (datalen == 0 && !frc->fr.stream.fin) { + break; + } + + rv = conn->callbacks.acked_stream_data_offset( + conn, strm->stream_id, prev_stream_offset, datalen, conn->user_data, + strm->stream_user_data); + if (rv != 0) { + return NGTCP2_ERR_CALLBACK_FAILURE; + } + } + + rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm); + if (rv != 0) { + return rv; + } + break; + case NGTCP2_FRAME_CRYPTO: + prev_stream_offset = ngtcp2_strm_get_acked_offset(crypto); + rv = ngtcp2_strm_ack_data( + crypto, frc->fr.crypto.offset, + ngtcp2_vec_len(frc->fr.crypto.data, frc->fr.crypto.datacnt)); + if (rv != 0) { + return rv; + } + + stream_offset = ngtcp2_strm_get_acked_offset(crypto); + datalen = stream_offset - prev_stream_offset; + if (datalen == 0) { + break; + } + + switch (rtb->pktns_id) { + case NGTCP2_PKTNS_ID_INITIAL: + pktns = conn->in_pktns; + break; + case NGTCP2_PKTNS_ID_HANDSHAKE: + pktns = conn->hs_pktns; + break; + case NGTCP2_PKTNS_ID_APPLICATION: + pktns = &conn->pktns; + break; + default: + ngtcp2_unreachable(); + } + + conn_ack_crypto_data(conn, pktns, datalen); + + break; + case NGTCP2_FRAME_RESET_STREAM: + strm = ngtcp2_conn_find_stream(conn, frc->fr.reset_stream.stream_id); + if (strm == NULL) { + break; + } + strm->flags |= NGTCP2_STRM_FLAG_RST_ACKED; + rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm); + if (rv != 0) { + return rv; + } + break; + case NGTCP2_FRAME_RETIRE_CONNECTION_ID: + ngtcp2_conn_untrack_retired_dcid_seq(conn, + frc->fr.retire_connection_id.seq); + break; + case NGTCP2_FRAME_DATAGRAM: + case NGTCP2_FRAME_DATAGRAM_LEN: + if (!conn->callbacks.ack_datagram) { + break; + } + + rv = conn->callbacks.ack_datagram(conn, frc->fr.datagram.dgram_id, + conn->user_data); + if (rv != 0) { + return NGTCP2_ERR_CALLBACK_FAILURE; + } + break; + } + } + return 0; +} + +static void rtb_on_pkt_acked(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, + ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) { + ngtcp2_cc *cc = rtb->cc; + ngtcp2_cc_pkt pkt; + + ngtcp2_rst_update_rate_sample(rtb->rst, ent, ts); + + cc->on_pkt_acked(cc, cstat, + ngtcp2_cc_pkt_init(&pkt, ent->hd.pkt_num, ent->pktlen, + rtb->pktns_id, ent->ts, ent->rst.lost, + ent->rst.tx_in_flight, + ent->rst.is_app_limited), + ts); + + if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE) && + (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING)) { + cstat->pto_count = 0; + } +} + +static void conn_verify_ecn(ngtcp2_conn *conn, ngtcp2_pktns *pktns, + ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, + const ngtcp2_ack *fr, size_t ecn_acked, + ngtcp2_tstamp largest_acked_sent_ts, + ngtcp2_tstamp ts) { + if (conn->tx.ecn.state == NGTCP2_ECN_STATE_FAILED) { + return; + } + + if ((ecn_acked && fr->type == NGTCP2_FRAME_ACK) || + (fr->type == NGTCP2_FRAME_ACK_ECN && + (pktns->rx.ecn.ack.ect0 > fr->ecn.ect0 || + pktns->rx.ecn.ack.ect1 > fr->ecn.ect1 || + pktns->rx.ecn.ack.ce > fr->ecn.ce || + (fr->ecn.ect0 - pktns->rx.ecn.ack.ect0) + + (fr->ecn.ce - pktns->rx.ecn.ack.ce) < + ecn_acked || + fr->ecn.ect0 > pktns->tx.ecn.ect0 || fr->ecn.ect1))) { + ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON, + "path is not ECN capable"); + conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED; + return; + } + + if (conn->tx.ecn.state != NGTCP2_ECN_STATE_CAPABLE && ecn_acked) { + ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON, "path is ECN capable"); + conn->tx.ecn.state = NGTCP2_ECN_STATE_CAPABLE; + } + + if (fr->type == NGTCP2_FRAME_ACK_ECN) { + if (largest_acked_sent_ts != UINT64_MAX && + fr->ecn.ce > pktns->rx.ecn.ack.ce) { + cc->congestion_event(cc, cstat, largest_acked_sent_ts, ts); + } + + pktns->rx.ecn.ack.ect0 = fr->ecn.ect0; + pktns->rx.ecn.ack.ect1 = fr->ecn.ect1; + pktns->rx.ecn.ack.ce = fr->ecn.ce; + } +} + +static int rtb_detect_lost_pkt(ngtcp2_rtb *rtb, uint64_t *ppkt_lost, + ngtcp2_conn *conn, ngtcp2_pktns *pktns, + ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts); + +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_entry *ent; + int64_t largest_ack = fr->largest_ack, min_ack; + size_t i; + int rv; + ngtcp2_ksl_it it; + ngtcp2_ssize num_acked = 0; + ngtcp2_tstamp largest_pkt_sent_ts = UINT64_MAX; + ngtcp2_tstamp largest_acked_sent_ts = UINT64_MAX; + int64_t pkt_num; + ngtcp2_cc *cc = rtb->cc; + ngtcp2_rtb_entry *acked_ent = NULL; + int ack_eliciting_pkt_acked = 0; + size_t ecn_acked = 0; + int verify_ecn = 0; + ngtcp2_cc_ack cc_ack = {0}; + size_t num_lost_pkts = rtb->num_lost_pkts - rtb->num_lost_pmtud_pkts; + + cc_ack.prior_bytes_in_flight = cstat->bytes_in_flight; + cc_ack.rtt = UINT64_MAX; + + if (conn && (conn->flags & NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED) && + (conn->flags & NGTCP2_CONN_FLAG_KEY_UPDATE_INITIATOR) && + largest_ack >= conn->pktns.crypto.tx.ckm->pkt_num) { + conn->flags &= (uint32_t) ~(NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED | + NGTCP2_CONN_FLAG_KEY_UPDATE_INITIATOR); + conn->crypto.key_update.confirmed_ts = ts; + + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_CRY, "key update confirmed"); + } + + if (rtb->largest_acked_tx_pkt_num < largest_ack) { + rtb->largest_acked_tx_pkt_num = largest_ack; + verify_ecn = 1; + } + + /* Assume that ngtcp2_pkt_validate_ack(fr) returns 0 */ + it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack); + if (ngtcp2_ksl_it_end(&it)) { + if (conn && verify_ecn) { + conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked, + largest_acked_sent_ts, ts); + } + return 0; + } + + min_ack = largest_ack - (int64_t)fr->first_ack_range; + + for (; !ngtcp2_ksl_it_end(&it);) { + pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it); + + assert(pkt_num <= largest_ack); + + if (pkt_num < min_ack) { + break; + } + + ent = ngtcp2_ksl_it_get(&it); + + if (largest_ack == pkt_num) { + largest_pkt_sent_ts = ent->ts; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) { + ack_eliciting_pkt_acked = 1; + } + + rtb_remove(rtb, &it, &acked_ent, ent, cstat); + ++num_acked; + } + + for (i = 0; i < fr->rangecnt;) { + largest_ack = min_ack - (int64_t)fr->ranges[i].gap - 2; + min_ack = largest_ack - (int64_t)fr->ranges[i].len; + + it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack); + if (ngtcp2_ksl_it_end(&it)) { + break; + } + + for (; !ngtcp2_ksl_it_end(&it);) { + pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it); + if (pkt_num < min_ack) { + break; + } + ent = ngtcp2_ksl_it_get(&it); + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) { + ack_eliciting_pkt_acked = 1; + } + + rtb_remove(rtb, &it, &acked_ent, ent, cstat); + ++num_acked; + } + + ++i; + } + + if (largest_pkt_sent_ts != UINT64_MAX && ack_eliciting_pkt_acked) { + cc_ack.rtt = pkt_ts - largest_pkt_sent_ts; + + rv = ngtcp2_conn_update_rtt(conn, cc_ack.rtt, fr->ack_delay_unscaled, ts); + if (rv == 0 && cc->new_rtt_sample) { + cc->new_rtt_sample(cc, cstat, ts); + } + } + + if (conn) { + for (ent = acked_ent; ent; ent = acked_ent) { + if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num && + (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN)) { + ++ecn_acked; + } + + assert(largest_acked_sent_ts == UINT64_MAX || + largest_acked_sent_ts <= ent->ts); + + largest_acked_sent_ts = ent->ts; + + rv = rtb_process_acked_pkt(rtb, ent, conn); + if (rv != 0) { + goto fail; + } + + if (ent->hd.pkt_num >= rtb->cc_pkt_num) { + assert(cc_ack.pkt_delivered <= ent->rst.delivered); + + cc_ack.bytes_delivered += ent->pktlen; + cc_ack.pkt_delivered = ent->rst.delivered; + } + + rtb_on_pkt_acked(rtb, ent, cstat, ts); + acked_ent = ent->next; + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + } + + if (verify_ecn) { + conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked, + largest_acked_sent_ts, ts); + } + } else { + /* For unit tests */ + for (ent = acked_ent; ent; ent = acked_ent) { + rtb_on_pkt_acked(rtb, ent, cstat, ts); + acked_ent = ent->next; + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + } + } + + if (rtb->cc->on_spurious_congestion && num_lost_pkts && + rtb->num_lost_pkts - rtb->num_lost_pmtud_pkts == 0) { + rtb->cc->on_spurious_congestion(cc, cstat, ts); + } + + ngtcp2_rst_on_ack_recv(rtb->rst, cstat, cc_ack.pkt_delivered); + + if (conn && num_acked > 0) { + rv = rtb_detect_lost_pkt(rtb, &cc_ack.bytes_lost, conn, pktns, cstat, ts); + if (rv != 0) { + return rv; + } + } + + rtb->rst->lost += cc_ack.bytes_lost; + + cc_ack.largest_acked_sent_ts = largest_acked_sent_ts; + cc->on_ack_recv(cc, cstat, &cc_ack, ts); + + return num_acked; + +fail: + for (ent = acked_ent; ent; ent = acked_ent) { + acked_ent = ent->next; + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + } + + return rv; +} + +static int rtb_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat, + const ngtcp2_rtb_entry *ent, ngtcp2_duration loss_delay, + size_t pkt_thres, ngtcp2_tstamp ts) { + ngtcp2_tstamp loss_time; + + if (ent->ts + loss_delay <= ts || + rtb->largest_acked_tx_pkt_num >= ent->hd.pkt_num + (int64_t)pkt_thres) { + return 1; + } + + loss_time = cstat->loss_time[rtb->pktns_id]; + + if (loss_time == UINT64_MAX) { + loss_time = ent->ts + loss_delay; + } else { + loss_time = ngtcp2_min(loss_time, ent->ts + loss_delay); + } + + cstat->loss_time[rtb->pktns_id] = loss_time; + + return 0; +} + +/* + * rtb_compute_pkt_loss_delay computes loss delay. + */ +static ngtcp2_duration compute_pkt_loss_delay(const ngtcp2_conn_stat *cstat) { + /* 9/8 is kTimeThreshold */ + ngtcp2_duration loss_delay = + ngtcp2_max(cstat->latest_rtt, cstat->smoothed_rtt) * 9 / 8; + return ngtcp2_max(loss_delay, NGTCP2_GRANULARITY); +} + +/* + * conn_all_ecn_pkt_lost returns nonzero if all ECN QUIC packets are + * lost during validation period. + */ +static int conn_all_ecn_pkt_lost(ngtcp2_conn *conn) { + ngtcp2_pktns *in_pktns = conn->in_pktns; + ngtcp2_pktns *hs_pktns = conn->hs_pktns; + ngtcp2_pktns *pktns = &conn->pktns; + + return (!in_pktns || in_pktns->tx.ecn.validation_pkt_sent == + in_pktns->tx.ecn.validation_pkt_lost) && + (!hs_pktns || hs_pktns->tx.ecn.validation_pkt_sent == + hs_pktns->tx.ecn.validation_pkt_lost) && + pktns->tx.ecn.validation_pkt_sent == pktns->tx.ecn.validation_pkt_lost; +} + +static int rtb_detect_lost_pkt(ngtcp2_rtb *rtb, uint64_t *ppkt_lost, + ngtcp2_conn *conn, ngtcp2_pktns *pktns, + ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) { + ngtcp2_rtb_entry *ent; + ngtcp2_duration loss_delay; + ngtcp2_ksl_it it; + ngtcp2_tstamp latest_ts, oldest_ts; + int64_t last_lost_pkt_num; + ngtcp2_duration loss_window, congestion_period; + ngtcp2_cc *cc = rtb->cc; + int rv; + uint64_t pkt_thres = + rtb->cc_bytes_in_flight / cstat->max_tx_udp_payload_size / 2; + size_t ecn_pkt_lost = 0; + ngtcp2_tstamp start_ts; + ngtcp2_duration pto = ngtcp2_conn_compute_pto(conn, pktns); + uint64_t bytes_lost = 0; + ngtcp2_duration max_ack_delay; + + pkt_thres = ngtcp2_max(pkt_thres, NGTCP2_PKT_THRESHOLD); + pkt_thres = ngtcp2_min(pkt_thres, 256); + cstat->loss_time[rtb->pktns_id] = UINT64_MAX; + loss_delay = compute_pkt_loss_delay(cstat); + + it = ngtcp2_ksl_lower_bound(&rtb->ents, &rtb->largest_acked_tx_pkt_num); + for (; !ngtcp2_ksl_it_end(&it); ngtcp2_ksl_it_next(&it)) { + ent = ngtcp2_ksl_it_get(&it); + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) { + break; + } + + if (rtb_pkt_lost(rtb, cstat, ent, loss_delay, (size_t)pkt_thres, ts)) { + /* All entries from ent are considered to be lost. */ + latest_ts = oldest_ts = ent->ts; + last_lost_pkt_num = ent->hd.pkt_num; + max_ack_delay = conn->remote.transport_params + ? conn->remote.transport_params->max_ack_delay + : 0; + + congestion_period = + (cstat->smoothed_rtt + + ngtcp2_max(4 * cstat->rttvar, NGTCP2_GRANULARITY) + max_ack_delay) * + NGTCP2_PERSISTENT_CONGESTION_THRESHOLD; + + start_ts = ngtcp2_max(rtb->persistent_congestion_start_ts, + cstat->first_rtt_sample_ts); + + for (; !ngtcp2_ksl_it_end(&it);) { + ent = ngtcp2_ksl_it_get(&it); + + if (last_lost_pkt_num == ent->hd.pkt_num + 1 && ent->ts >= start_ts) { + last_lost_pkt_num = ent->hd.pkt_num; + oldest_ts = ent->ts; + } else { + last_lost_pkt_num = -1; + } + + if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)) { + if (rtb->pktns_id != NGTCP2_PKTNS_ID_APPLICATION || + last_lost_pkt_num == -1 || + latest_ts - oldest_ts >= congestion_period) { + break; + } + ngtcp2_ksl_it_next(&it); + continue; + } + + if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num && + (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN)) { + ++ecn_pkt_lost; + } + + bytes_lost += rtb_on_remove(rtb, ent, cstat); + rv = rtb_on_pkt_lost(rtb, &it, ent, cstat, conn, pktns, ts); + if (rv != 0) { + return rv; + } + } + + /* If only PMTUD packets are lost, do not trigger congestion + event. */ + if (bytes_lost == 0) { + break; + } + + switch (conn->tx.ecn.state) { + case NGTCP2_ECN_STATE_TESTING: + if (conn->tx.ecn.validation_start_ts == UINT64_MAX) { + break; + } + if (ts - conn->tx.ecn.validation_start_ts < 3 * pto) { + pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost; + assert(pktns->tx.ecn.validation_pkt_sent >= + pktns->tx.ecn.validation_pkt_lost); + break; + } + conn->tx.ecn.state = NGTCP2_ECN_STATE_UNKNOWN; + /* fall through */ + case NGTCP2_ECN_STATE_UNKNOWN: + pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost; + assert(pktns->tx.ecn.validation_pkt_sent >= + pktns->tx.ecn.validation_pkt_lost); + if (conn_all_ecn_pkt_lost(conn)) { + conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED; + } + break; + default: + break; + } + + cc->congestion_event(cc, cstat, latest_ts, ts); + + loss_window = latest_ts - oldest_ts; + /* Persistent congestion situation is only evaluated for app + * packet number space and for the packets sent after handshake + * is confirmed. During handshake, there is not much packets + * sent and also people seem to do lots of effort not to trigger + * persistent congestion there, then it is a lot easier to just + * not enable it during handshake. + */ + if (rtb->pktns_id == NGTCP2_PKTNS_ID_APPLICATION && loss_window > 0) { + if (loss_window >= congestion_period) { + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "persistent congestion loss_window=%" PRIu64 + " congestion_period=%" PRIu64, + loss_window, congestion_period); + + /* Reset min_rtt, srtt, and rttvar here. Next new RTT + sample will be used to recalculate these values. */ + cstat->min_rtt = UINT64_MAX; + cstat->smoothed_rtt = conn->local.settings.initial_rtt; + cstat->rttvar = conn->local.settings.initial_rtt / 2; + cstat->first_rtt_sample_ts = UINT64_MAX; + + cc->on_persistent_congestion(cc, cstat, ts); + } + } + + break; + } + } + + ngtcp2_rtb_remove_excessive_lost_pkt(rtb, (size_t)pkt_thres); + + if (ppkt_lost) { + *ppkt_lost = bytes_lost; + } + + return 0; +} + +int ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_conn *conn, + ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat, + ngtcp2_tstamp ts) { + return rtb_detect_lost_pkt(rtb, /* ppkt_lost = */ NULL, conn, pktns, cstat, + ts); +} + +void ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb *rtb, size_t n) { + ngtcp2_ksl_it it = ngtcp2_ksl_end(&rtb->ents); + ngtcp2_rtb_entry *ent; + int rv; + (void)rv; + + for (; rtb->num_lost_pkts > n;) { + assert(ngtcp2_ksl_it_end(&it)); + ngtcp2_ksl_it_prev(&it); + ent = ngtcp2_ksl_it_get(&it); + + assert(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED); + + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "removing stale lost pkn=%" PRId64, ent->hd.pkt_num); + + --rtb->num_lost_pkts; + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + --rtb->num_lost_pmtud_pkts; + } + + rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num); + assert(0 == rv); + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + } +} + +void ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_duration pto, + ngtcp2_tstamp ts) { + ngtcp2_ksl_it it; + ngtcp2_rtb_entry *ent; + int rv; + (void)rv; + + if (ngtcp2_ksl_len(&rtb->ents) == 0) { + return; + } + + it = ngtcp2_ksl_end(&rtb->ents); + + for (;;) { + assert(ngtcp2_ksl_it_end(&it)); + + ngtcp2_ksl_it_prev(&it); + ent = ngtcp2_ksl_it_get(&it); + + if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) || + ts - ent->lost_ts < pto) { + return; + } + + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "removing stale lost pkn=%" PRId64, ent->hd.pkt_num); + + --rtb->num_lost_pkts; + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + --rtb->num_lost_pmtud_pkts; + } + + rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num); + assert(0 == rv); + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + + if (ngtcp2_ksl_len(&rtb->ents) == 0) { + return; + } + } +} + +ngtcp2_tstamp ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb *rtb) { + ngtcp2_ksl_it it; + ngtcp2_rtb_entry *ent; + + if (ngtcp2_ksl_len(&rtb->ents) == 0) { + return UINT64_MAX; + } + + it = ngtcp2_ksl_end(&rtb->ents); + ngtcp2_ksl_it_prev(&it); + ent = ngtcp2_ksl_it_get(&it); + + if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)) { + return UINT64_MAX; + } + + return ent->lost_ts; +} + +static int rtb_on_pkt_lost_resched_move(ngtcp2_rtb *rtb, ngtcp2_conn *conn, + ngtcp2_pktns *pktns, + ngtcp2_rtb_entry *ent) { + ngtcp2_frame_chain **pfrc, *frc; + ngtcp2_stream *sfr; + ngtcp2_strm *strm; + int rv; + int streamfrq_empty; + + ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags, + ent->ts); + + if (rtb->qlog) { + ngtcp2_qlog_pkt_lost(rtb->qlog, ent); + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE) { + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "pkn=%" PRId64 + " is a probe packet, no retransmission is necessary", + ent->hd.pkt_num); + return 0; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "pkn=%" PRId64 + " is a PMTUD probe packet, no retransmission is necessary", + ent->hd.pkt_num); + return 0; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) { + --rtb->num_lost_pkts; + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) { + --rtb->num_lost_pmtud_pkts; + } + + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "pkn=%" PRId64 + " was declared lost and has already been retransmitted", + ent->hd.pkt_num); + return 0; + } + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED) { + ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV, + "pkn=%" PRId64 " has already been reclaimed on PTO", + ent->hd.pkt_num); + return 0; + } + + if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) && + (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_DATAGRAM) || + !conn->callbacks.lost_datagram)) { + /* PADDING only (or PADDING + ACK ) packets will have NULL + ent->frc. */ + return 0; + } + + pfrc = &ent->frc; + + for (; *pfrc;) { + switch ((*pfrc)->fr.type) { + case NGTCP2_FRAME_STREAM: + frc = *pfrc; + + *pfrc = frc->next; + frc->next = NULL; + sfr = &frc->fr.stream; + + strm = ngtcp2_conn_find_stream(conn, sfr->stream_id); + if (!strm) { + ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem); + break; + } + streamfrq_empty = ngtcp2_strm_streamfrq_empty(strm); + rv = ngtcp2_strm_streamfrq_push(strm, frc); + if (rv != 0) { + ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem); + return rv; + } + if (!ngtcp2_strm_is_tx_queued(strm)) { + strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn); + rv = ngtcp2_conn_tx_strmq_push(conn, strm); + if (rv != 0) { + return rv; + } + } + if (streamfrq_empty) { + ++conn->tx.strmq_nretrans; + } + break; + case NGTCP2_FRAME_CRYPTO: + frc = *pfrc; + + *pfrc = frc->next; + frc->next = NULL; + + rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL, + &frc->fr.crypto.offset, frc); + if (rv != 0) { + assert(ngtcp2_err_is_fatal(rv)); + ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem); + return rv; + } + break; + case NGTCP2_FRAME_DATAGRAM: + case NGTCP2_FRAME_DATAGRAM_LEN: + frc = *pfrc; + + if (conn->callbacks.lost_datagram) { + rv = conn->callbacks.lost_datagram(conn, frc->fr.datagram.dgram_id, + conn->user_data); + if (rv != 0) { + return NGTCP2_ERR_CALLBACK_FAILURE; + } + } + + *pfrc = (*pfrc)->next; + + ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem); + break; + default: + pfrc = &(*pfrc)->next; + } + } + + *pfrc = pktns->tx.frq; + pktns->tx.frq = ent->frc; + ent->frc = NULL; + + return 0; +} + +int ngtcp2_rtb_remove_all(ngtcp2_rtb *rtb, ngtcp2_conn *conn, + ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat) { + ngtcp2_rtb_entry *ent; + ngtcp2_ksl_it it; + int rv; + + it = ngtcp2_ksl_begin(&rtb->ents); + + for (; !ngtcp2_ksl_it_end(&it);) { + ent = ngtcp2_ksl_it_get(&it); + + rtb_on_remove(rtb, ent, cstat); + rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num); + assert(0 == rv); + + rv = rtb_on_pkt_lost_resched_move(rtb, conn, pktns, ent); + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + if (rv != 0) { + return rv; + } + } + + return 0; +} + +void ngtcp2_rtb_remove_early_data(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat) { + ngtcp2_rtb_entry *ent; + ngtcp2_ksl_it it; + int rv; + (void)rv; + + it = ngtcp2_ksl_begin(&rtb->ents); + + for (; !ngtcp2_ksl_it_end(&it);) { + ent = ngtcp2_ksl_it_get(&it); + + if (ent->hd.type != NGTCP2_PKT_0RTT) { + ngtcp2_ksl_it_next(&it); + continue; + } + + rtb_on_remove(rtb, ent, cstat); + rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num); + assert(0 == rv); + + ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc, + rtb->frc_objalloc, rtb->mem); + } +} + +int ngtcp2_rtb_empty(ngtcp2_rtb *rtb) { + return ngtcp2_ksl_len(&rtb->ents) == 0; +} + +void ngtcp2_rtb_reset_cc_state(ngtcp2_rtb *rtb, int64_t cc_pkt_num) { + rtb->cc_pkt_num = cc_pkt_num; + rtb->cc_bytes_in_flight = 0; +} + +ngtcp2_ssize ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb *rtb, ngtcp2_conn *conn, + ngtcp2_pktns *pktns, size_t num_pkts) { + ngtcp2_ksl_it it; + ngtcp2_rtb_entry *ent; + ngtcp2_ssize reclaimed; + size_t atmost = num_pkts; + + it = ngtcp2_ksl_end(&rtb->ents); + for (; !ngtcp2_ksl_it_begin(&it) && num_pkts >= 1;) { + ngtcp2_ksl_it_prev(&it); + ent = ngtcp2_ksl_it_get(&it); + + if ((ent->flags & (NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED | + NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED)) || + !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE)) { + continue; + } + + assert(ent->frc); + + reclaimed = + rtb_reclaim_frame(rtb, NGTCP2_RECLAIM_FLAG_NONE, conn, pktns, ent); + if (reclaimed < 0) { + return reclaimed; + } + + /* Mark reclaimed even if reclaimed == 0 so that we can skip it in + the next run. */ + ent->flags |= NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED; + + assert(rtb->num_retransmittable); + --rtb->num_retransmittable; + + if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) { + ent->flags &= (uint16_t)~NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING; + assert(rtb->num_pto_eliciting); + --rtb->num_pto_eliciting; + } + + if (reclaimed) { + --num_pkts; + } + } + + return (ngtcp2_ssize)(atmost - num_pkts); +} |