22  * sent for which we later expect to receive an ACK. It is essentially a simple
171  * **Background.** The RX side of the ACK manager must track packets we have
172  * received for which we have to generate ACK frames. Broadly, this means we
178  *   1. We receive a packet but have not sent an ACK yet, so the transmitter
181  *   2. We receive a packet and send an ACK which is lost. We do not
182  *      immediately know that the ACK was lost and the transmitter does not know
185  *   3. We receive a packet and send an ACK which is received by the
186  *      transmitter. The transmitter does not immediately respond with an ACK,
187  *      or responds with an ACK which is lost. The transmitter knows that we
189  *      because the ACK we sent could have been lost.
191  *   4. We receive a packet and send an ACK which is received by the
192  *      transmitter. The transmitter subsequently sends us an ACK which confirms
193  *      its receipt of the ACK we sent, and we successfully receive that ACK, so
200  * will never again need to generate an ACK containing the PN in question, but
223  *     (and should therefore be in any future ACK frame generated;
243  *   "A receiver MUST retain an ACK Range unless it can ensure that it will not
271  *         The PN should be included in any future ACK frame we generate.
293  * keep reporting it in future ACK frames).
298  *   "When a packet containing an ACK frame is sent, the Largest Acknowledged
299  *    field in that frame can be saved. When a packet containing an ACK frame is
301  *    equal to the Largest Acknowledged field in the sent ACK frame."
304  * ACK frame is itself ACK'd, PNs referenced in that ACK frame become provably
308  * and previous ACK frames. Thus, some unreceived PNs may be moved below the
319  * subsequently generated ACK frame is sent in a future TX packet, and then we
327  * **Data structure.** Our state for the RX handling side of the ACK manager, as
335  * been provably ACKed, and thus will later need to generate an ACK frame for.
352  * but which have not been provably ACKed when we want to generate ACK frames.
353  * Since ACK frames can be lost and/or we might not know that the peer has
354  * successfully received them, we might generate multiple ACK frames covering a
376  * provably ACKed. This occurs when an ACK frame is received by the TX side of
377  * the ACK manager; thus, there is necessary interaction between the TX and RX
378  * sides of the ACK manager.
381  * side of the ACK manager, it may optionally have a Largest Acked value set on
382  * it. The user of the ACK manager should do this if the packet being
383  * transmitted contains an ACK frame, by setting the field to the Largest Acked
386  * used to update the state of the RX side of the ACK manager by bumping the
414  * Limit the number of ACK ranges we store to prevent resource consumption DoS
477  * ACK Manager Implementation
479  * Implementation of the ACK manager proper.
482 /* Constants used by the ACK manager; see RFC 9002. */
491 /* Default maximum amount of time to leave an ACK-eliciting packet un-ACK'd. */
523      * and removed again once ack'd/lost/discarded.
529      * ack-eliciting, and removed again once ack'd/lost/discarded.
548     /* Set to 1 when we think an ACK frame should be generated. */
551     /* Set to 1 if an ACK frame has ever been generated. */
557     /* Generated ACK frames for each PN space. */
558     OSSL_QUIC_FRAME_ACK     ack[QUIC_PN_SPACE_NUM];  member
577      * Number of ACK-eliciting packets since last ACK. We use this to defer
578      * emitting ACK frames until a threshold number of ACK-eliciting packets
584      * The ACK frame coalescing deadline at which we should flush any unsent ACK
590      * The RX maximum ACK delay (the maximum amount of time our peer might
591      * wait to send us an ACK after receiving an ACK-eliciting packet).
596      * The TX maximum ACK delay (the maximum amount of time we allow ourselves
597      * to wait before generating an ACK after receiving an ACK-eliciting
637 /* Does the newly-acknowledged list contain any ack-eliciting packet? */
647 /* Return number of ACK-eliciting bytes in flight across all PN spaces. */
666  * Given a logical representation of an ACK frame 'ack', create a singly-linked
667  * list of the newly ACK'd frames; that is, of frames which are matched by the
668  * list of PN ranges contained in the ACK frame. The packet structures in the
673                                                                  const OSSL_QUIC_FRAME_ACK *ack,  in ackm_detect_and_remove_newly_acked_pkts()  argument
680     assert(ack->num_ack_ranges > 0);  in ackm_detect_and_remove_newly_acked_pkts()
686      * ack->ack_ranges is a list of packet number ranges in descending order.  in ackm_detect_and_remove_newly_acked_pkts()
689      * membership in the specified ack ranges. As an optimization, we use our  in ackm_detect_and_remove_newly_acked_pkts()
691      * the ACK ranges given include nonexistent packets.  in ackm_detect_and_remove_newly_acked_pkts()
695     pkt = tx_pkt_history_by_pkt_num(h, ack->ack_ranges[0].end);  in ackm_detect_and_remove_newly_acked_pkts()
707             if (ridx >= ack->num_ack_ranges) {  in ackm_detect_and_remove_newly_acked_pkts()
715             if (range_contains(&ack->ack_ranges[ridx], pkt->pkt_num)) {  in ackm_detect_and_remove_newly_acked_pkts()
723             } else if (pkt->pkt_num > ack->ack_ranges[ridx].end) {  in ackm_detect_and_remove_newly_acked_pkts()
734                 assert(pkt->pkt_num < ack->ack_ranges[ridx].start);  in ackm_detect_and_remove_newly_acked_pkts()
888          * Only re-arm timer if stack has sent at least one ACK eliciting frame.  in ackm_get_pto_time_and_space()
889          * If stack has sent no ACK eliciting frame at given encryption level then  in ackm_get_pto_time_and_space()
1111     /* Does not make any sense for a non-in-flight packet to be ACK-eliciting. */  in ossl_ackm_on_tx_packet()
1140 static void ackm_process_ecn(OSSL_ACKM *ackm, const OSSL_QUIC_FRAME_ACK *ack,  in ackm_process_ecn()  argument
1151     if (ack->ecnce > ackm->peer_ecnce[pkt_space]) {  in ackm_process_ecn()
1152         ackm->peer_ecnce[pkt_space] = ack->ecnce;  in ackm_process_ecn()
1155         pkt = tx_pkt_history_by_pkt_num(h, ack->ack_ranges[0].end);  in ackm_process_ecn()
1164 int ossl_ackm_on_rx_ack_frame(OSSL_ACKM *ackm, const OSSL_QUIC_FRAME_ACK *ack,  in ossl_ackm_on_rx_ack_frame()  argument
1171         ackm->largest_acked_pkt[pkt_space] = ack->ack_ranges[0].end;  in ossl_ackm_on_rx_ack_frame()
1175                                ack->ack_ranges[0].end);  in ossl_ackm_on_rx_ack_frame()
1178      * If we get an ACK in the handshake space, address validation is completed.  in ossl_ackm_on_rx_ack_frame()
1179      * Make sure we update the timer, even if no packets were ACK'd.  in ossl_ackm_on_rx_ack_frame()
1190     na_pkts = ackm_detect_and_remove_newly_acked_pkts(ackm, ack, pkt_space);  in ossl_ackm_on_rx_ack_frame()
1200      * one ACK-eliciting packet was newly acked.  in ossl_ackm_on_rx_ack_frame()
1204     if (na_pkts->pkt_num == ack->ack_ranges[0].end &&  in ossl_ackm_on_rx_ack_frame()
1210         /* Enforce maximum ACK delay. */  in ossl_ackm_on_rx_ack_frame()
1211         ack_delay = ack->delay_time;  in ossl_ackm_on_rx_ack_frame()
1226     if (ack->ecn_present)  in ossl_ackm_on_rx_ack_frame()
1227         ackm_process_ecn(ackm, ack, pkt_space);  in ossl_ackm_on_rx_ack_frame()
1380 /* Number of ACK-eliciting packets RX'd before we always emit an ACK. */
1384  * Return 1 if emission of an ACK frame is currently desired.
1388  *   - We have flagged that we want to send an ACK frame
1391  *   - We have exceeded the ACK flush deadline, meaning that
1392  *     we have received at least one ACK-eliciting packet, but held off on
1393  *     sending an ACK frame immediately in the hope that more ACK-eliciting
1395  *     transmission of an ACK frame anyway.
1407  * Returns 1 if an ACK frame matches a given packet number.
1409 static int ack_contains(const OSSL_QUIC_FRAME_ACK *ack, QUIC_PN pkt_num)  in ack_contains()  argument
1413     for (i = 0; i < ack->num_ack_ranges; ++i)  in ack_contains()
1414         if (range_contains(&ack->ack_ranges[i], pkt_num))  in ack_contains()
1422  * implied missing (by us, in an ACK frame we previously generated).
1428      * generated ACK frame, but is not matched by the frame.  in ackm_is_missing()
1430     return ackm->ack[pkt_space].num_ack_ranges > 0  in ackm_is_missing()
1431         && pkt_num <= ackm->ack[pkt_space].ack_ranges[0].end  in ackm_is_missing()
1432         && !ack_contains(&ackm->ack[pkt_space], pkt_num);  in ackm_is_missing()
1457      * reported in any ACK frame. Thus there is a gap of at least one PN between  in ackm_has_newly_missing()
1458      * the PNs we have ACK'd previously and the PN we have just received.  in ackm_has_newly_missing()
1460     return ackm->ack[pkt_space].num_ack_ranges > 0  in ackm_has_newly_missing()
1464             > ackm->ack[pkt_space].ack_ranges[0].end + 1;  in ackm_has_newly_missing()
1477 /* Explicitly flags that we want to generate an ACK frame. */
1493         /* ACK generation already requested so nothing to do. */  in ackm_on_rx_ack_eliciting()
1506          *   - We have never yet generated an ACK frame, meaning that this  in ackm_on_rx_ack_eliciting()
1511          *     missing in a previous ACK frame (meaning that we should report  in ackm_on_rx_ack_eliciting()
1514          *   - We have exceeded the ACK-eliciting packet threshold count  in ackm_on_rx_ack_eliciting()
1515          *     for the purposes of ACK coalescing, so request transmission  in ackm_on_rx_ack_eliciting()
1516          *     of an ACK frame, or  in ackm_on_rx_ack_eliciting()
1520          *     inform the peer by sending an ACK frame immediately.  in ackm_on_rx_ack_eliciting()
1522          * We do not test the ACK flush deadline here because it is tested  in ackm_on_rx_ack_eliciting()
1530      * Not emitting an ACK yet.  in ackm_on_rx_ack_eliciting()
1532      * Update the ACK flush deadline.  in ackm_on_rx_ack_eliciting()
1534      * RFC 9000 s. 13.2.1: "An endpoint MUST acknowledge all ack-eliciting  in ackm_on_rx_ack_eliciting()
1535      * Initial and Handshake packets immediately"; don't delay ACK generation if  in ackm_on_rx_ack_eliciting()
1564      * We use this to calculate the ACK delay field of ACK frames.  in ossl_ackm_on_rx_packet()
1573      * being omitted from a previous ACK frame generated, we skip any packet  in ossl_ackm_on_rx_packet()
1574      * count thresholds or coalescing delays and emit a new ACK frame  in ossl_ackm_on_rx_packet()
1587      * Receiving this packet may or may not cause us to emit an ACK frame.  in ossl_ackm_on_rx_packet()
1588      * We may not emit an ACK frame yet if we have not yet received a threshold  in ossl_ackm_on_rx_packet()
1613                                     OSSL_QUIC_FRAME_ACK *ack)  in ackm_fill_rx_ack_ranges()  argument
1630     ack->ack_ranges     = ackm->ack_ranges[pkt_space];  in ackm_fill_rx_ack_ranges()
1631     ack->num_ack_ranges = i;  in ackm_fill_rx_ack_ranges()
1637     OSSL_QUIC_FRAME_ACK *ack = &ackm->ack[pkt_space];  in ossl_ackm_get_ack_frame()  local
1640     ackm_fill_rx_ack_ranges(ackm, pkt_space, ack);  in ossl_ackm_get_ack_frame()
1645         ack->delay_time =  in ossl_ackm_get_ack_frame()
1648         ack->delay_time = ossl_time_zero();  in ossl_ackm_get_ack_frame()
1650     ack->ect0              = ackm->rx_ect0[pkt_space];  in ossl_ackm_get_ack_frame()
1651     ack->ect1              = ackm->rx_ect1[pkt_space];  in ossl_ackm_get_ack_frame()
1652     ack->ecnce             = ackm->rx_ecnce[pkt_space];  in ossl_ackm_get_ack_frame()
1653     ack->ecn_present       = 1;  in ossl_ackm_get_ack_frame()
1660     return ack;  in ossl_ackm_get_ack_frame()