22  * sent for which we later expect to receive an ACK. It is essentially a simple
26  * We currently only allow packets to be appended to the list (i.e. the packet
28  * we should not currently need more general functionality such as a sorted list
45      * (inclusive). We do not allow packet numbers to be added to the history
52      * Packet number of the highest packet info structure we have yet appended
53      * to the list. This is usually one less than watermark, except when we have
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
173  * store a set of packet numbers which we have received but which we do not know
174  * for a fact that the transmitter knows we have received.
178  *   1. We receive a packet but have not sent an ACK yet, so the transmitter
179  *      does not know whether we have received it or not yet.
181  *   2. We receive a packet and send an ACK which is lost. We do not
183  *      that we have received the packet.
185  *   3. We receive a packet and send an ACK which is received by the
187  *      or responds with an ACK which is lost. The transmitter knows that we
188  *      have received the packet, but we do not know for sure that it knows,
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
193  *      its receipt of the ACK we sent, and we successfully receive that ACK, so
194  *      we know that the transmitter knows, that we received the original
197  * Only when we reach case (4) are we relieved of any need to track a given
198  * packet number we have received, because only in this case do we know for sure
199  * that the peer knows we have received the packet. Having reached case (4) we
201  * until we reach that point, we must keep track of the PN as not having been
202  * provably ACKed, as we may have to keep generating ACKs for the given PN not
203  * just until the transmitter receives one, but until we know that it has
206  * **Duplicate handling.** The above discusses the case where we have received a
207  * packet with a given PN but are at best unsure whether the sender knows we
208  * have received it or not. However, we must also handle the case where we have
216  * We must ensure we never process a duplicate PN. As such, each possible PN we
219  *   - We have never processed this PN before
220  *     (so if we receive such a PN, it can be processed)
222  *   - We have processed this PN but it has not yet been provably ACKed
224  *      if we receive such a PN again, it must be ignored)
226  *   - We have processed this PN and it has been provably ACKed
227  *     (if we receive such a PN again, it must be ignored)
229  * However, if we were to track this state for every PN ever used in the history
231  * the connection goes on (for example, we would have to store a set of every PN
256  * This allows us to bound the amount of state we must keep, and we adopt the
257  * suggested strategy quoted above to do so. We define a watermark PN below
264  *   - (A) The PN is above the watermark but we have not yet received it.
266  *         If we receive such a PN, we should process it and record the PN as
269  *   - (B) The PN is above the watermark and we have received it.
271  *         The PN should be included in any future ACK frame we generate.
272  *         If we receive such a PN again, we should ignore it.
276  *         We do not know whether a packet with the given PN was received or
277  *         not. To be safe, if we receive such a packet, it is not processed.
279  * Note that state (C) corresponds to both "we have processed this PN and it has
280  * been provably ACKed" logical state and a subset of the PNs in the "we have
283  * watermark). The reason we can merge these states and avoid tracking states
285  * states are functionally identical in terms of how we need to handle them: we
286  * don't need to do anything for PNs in either of these states, so we don't have
287  * to care about PNs in this state nor do we have to care about distinguishing
292  * the watermark must be immediately increased to exceed it (otherwise we would
309  * watermark, and we may subsequently reject those PNs as possibly being
310  * duplicates even though we have not actually received those PNs. Since we bump
318  * network, a PN we receive can only become provably ACKed after our own
319  * subsequently generated ACK frame is sent in a future TX packet, and then we
333  * For (a), we define a data structure which stores a logical set of PNs, which
334  * we use to keep track of which PNs we have received but which have not yet
344  * indistinguishable from a PN we have not yet received and risk us processing a
351  * We can query the logical set data structure for PNs which have been received
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
355  * given PN until that PN becomes provably ACKed and we finally remove it from
359  * which is used as a PN set. We use the following operations of the structure:
361  *   Insert Range: Used when we receive a new PN.
414  * Limit the number of ACK ranges we store to prevent resource consumption DoS
433      * Bump watermark to cover all PNs we removed to avoid accidental  in rx_pkt_history_trim_range_count()
488 /* The maximum number of times we allow PTO to be doubled. */
501     /* Polymorphic dependencies that we consume. */
518     /* Time at which we got our first RTT sample, or 0. */
548     /* Set to 1 when we think an ACK frame should be generated. */
562     /* Largest PN we have RX'd. */
569      * ECN event counters. Each time we receive a packet with a given ECN label,
577      * Number of ACK-eliciting packets since last ACK. We use this to defer
584      * The ACK frame coalescing deadline at which we should flush any unsent ACK
596      * The TX maximum ACK delay (the maximum amount of time we allow ourselves
689      * membership in the specified ack ranges. As an optimization, we use our  in ackm_detect_and_remove_newly_acked_pkts()
701          * Save prev value as it will be zeroed if we remove the packet from the  in ackm_detect_and_remove_newly_acked_pkts()
709                  * We have exhausted all ranges so stop here, even if there are  in ackm_detect_and_remove_newly_acked_pkts()
716                 /* We have matched this range. */  in ackm_detect_and_remove_newly_acked_pkts()
725                  * We have not reached this range yet in our list, so do not  in ackm_detect_and_remove_newly_acked_pkts()
731                  * We have moved beyond this range, so advance to the next range  in ackm_detect_and_remove_newly_acked_pkts()
782          * Save prev value as it will be zeroed if we remove the packet from the  in ackm_detect_and_remove_lost_pkts()
890          * particular timer is zero and we must not attempt to set it. Timer keeps  in ackm_get_pto_time_and_space()
891          * time since epoch (Jan 1 1970) and we must not set timer to past.  in ackm_get_pto_time_and_space()
974                  * If this is pseudo-loss (e.g. during connection retry) we do not  in ackm_on_pkts_lost()
989      * Persistent congestion can only be considered if we have gotten at least  in ackm_on_pkts_lost()
1018                  * This can fail, but it is monotonic; worst case we try again  in ackm_on_pkts_acked()
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()
1222      * We deliberately do most ECN processing in the ACKM rather than the  in ossl_ackm_on_rx_ack_frame()
1306      * TODO(QUIC FUTURE): We are allowed to send either one or two probe  in ackm_queue_probe()
1308      * Determine a strategy for when we should send two probe packets.  in ackm_queue_probe()
1380 /* Number of ACK-eliciting packets RX'd before we always emit an ACK. */
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
1394  *     packets might come in, but not enough did and we are now requesting
1421  * Returns 1 iff a PN (which we have just received) was previously reported as
1422  * implied missing (by us, in an ACK frame we previously generated).
1453      * we only return 1 when the missing PN condition is newly established.  in ackm_has_newly_missing()
1456      * history is beyond (and does not border) the highest PN we have yet  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()
1477 /* Explicitly flags that we want to generate an ACK frame. */
1506          *   - We have never yet generated an ACK frame, meaning that this  in ackm_on_rx_ack_eliciting()
1507          *     is the first ever packet received, which we should always  in ackm_on_rx_ack_eliciting()
1510          *   - We previously reported the PN that we have just received as  in ackm_on_rx_ack_eliciting()
1511          *     missing in a previous ACK frame (meaning that we should report  in ackm_on_rx_ack_eliciting()
1512          *     the fact that we now have it to the peer immediately), or  in ackm_on_rx_ack_eliciting()
1514          *   - We have exceeded the ACK-eliciting packet threshold count  in ackm_on_rx_ack_eliciting()
1518          *   - The PN we just received and added to our PN RX history  in ackm_on_rx_ack_eliciting()
1519          *     newly implies one or more missing PNs, in which case we should  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()
1536      * we are using the Initial or Handshake PN spaces.  in ackm_on_rx_ack_eliciting()
1563      * Record the largest PN we have RX'd and the time we received it.  in ossl_ackm_on_rx_packet()
1564      * We use this to calculate the ACK delay field of ACK frames.  in ossl_ackm_on_rx_packet()
1572      * If the PN we just received was previously implied missing by virtue of  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()
1580      * Add the packet number to our history list of PNs we have not yet provably  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()
1594     /* Update the ECN counters according to which ECN signal we got, if any. */  in ossl_ackm_on_rx_packet()
1620      * Copy out ranges from the PN set, starting at the end, until we reach our  in ackm_fill_rx_ack_ranges()