QUIC ACK Manager, Statistics Manager and Congestion Control API

This is the initial implementation of the ACK Manager for OpenSSL's QUIC
support, with supporting design documentation and tests.

Because the ACK Manager also depends on the Statistics Manager, it is
also implemented here. The Statistics Manager is quite simple, so this
does not amount to a large amount of extra code.

Because the ACK Manager depends on a congestion controller, it adds a
no-op congestion controller, which uses the previously workshopped
congestion control API.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Richard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18676)

5 files changed, 414 insertions, 0 deletions

diff --git a/include/internal/quic_ackm.h b/include/internal/quic_ackm.h
new file mode 100644
index 0000000000..1188e30177
--- /dev/null
+++ b/include/internal/quic_ackm.h
@@ -0,0 +1,206 @@
+/*
+ * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+#ifndef OSSL_QUIC_ACKM_H
+# define OSSL_QUIC_ACKM_H
+
+# include "internal/quic_statm.h"
+# include "internal/quic_cc.h"
+# include "internal/quic_types.h"
+# include "internal/quic_wire.h"
+# include "internal/time.h"
+
+typedef struct ossl_ackm_st OSSL_ACKM;
+
+OSSL_ACKM *ossl_ackm_new(OSSL_TIME (*now)(void *arg),
+                         void *now_arg,
+                         OSSL_STATM *statm,
+                         const OSSL_CC_METHOD *cc_method,
+                         OSSL_CC_DATA *cc_data);
+void ossl_ackm_free(OSSL_ACKM *ackm);
+
+void ossl_ackm_set_loss_detection_deadline_callback(OSSL_ACKM *ackm,
+                                                    void (*fn)(OSSL_TIME deadline,
+                                                               void *arg),
+                                                    void *arg);
+
+void ossl_ackm_set_ack_deadline_callback(OSSL_ACKM *ackm,
+                                         void (*fn)(OSSL_TIME deadline,
+                                                    int pkt_space,
+                                                    void *arg),
+                                         void *arg);
+
+typedef struct ossl_ackm_tx_pkt_st {
+    /* The packet number of the transmitted packet. */
+    QUIC_PN pkt_num;
+
+    /* The number of bytes in the packet which was sent. */
+    size_t num_bytes;
+
+    /* The time at which the packet was sent. */
+    OSSL_TIME time;
+
+    /*
+     * If the packet being described by this structure contains an ACK frame,
+     * this must be set to the largest PN ACK'd by that frame.
+     *
+     * Otherwise, it should be set to QUIC_PN_INVALID.
+     *
+     * This is necessary to bound the number of PNs we have to keep track of on
+     * the RX side (RFC 9000 s. 13.2.4). It allows older PN tracking information
+     * on the RX side to be discarded.
+     */
+    QUIC_PN largest_acked;
+
+    /*
+     * One of the QUIC_PN_SPACE_* values. This qualifies the pkt_num field
+     * into a packet number space.
+     */
+    unsigned int pkt_space :2;
+
+    /* 1 if the packet is in flight. */
+    unsigned int is_inflight :1;
+
+    /* 1 if the packet has one or more ACK-eliciting frames. */
+    unsigned int is_ack_eliciting :1;
+
+    /* 1 if the packet is a PTO probe. */
+    unsigned int is_pto_probe :1;
+
+    /* 1 if the packet is an MTU probe. */
+    unsigned int is_mtu_probe :1;
+
+    /* Callback called if frames in this packet are lost. arg is cb_arg. */
+    void (*on_lost)(void *arg);
+    /* Callback called if frames in this packet are acked. arg is cb_arg. */
+    void (*on_acked)(void *arg);
+    /*
+     * Callback called if frames in this packet are neither acked nor lost. arg
+     * is cb_arg.
+     */
+    void (*on_discarded)(void *arg);
+    void  *cb_arg;
+
+    /* 
+     * (Internal use fields; must be zero-initialized.)
+     *
+     * prev and next link us into the TX history list, anext is used to manifest
+     * a singly-linked list of newly-acknowledged packets, and lnext is used to
+     * manifest a singly-linked list of newly lost packets.
+     */
+    struct ossl_ackm_tx_pkt_st *prev;
+    struct ossl_ackm_tx_pkt_st *next;
+    struct ossl_ackm_tx_pkt_st *anext;
+    struct ossl_ackm_tx_pkt_st *lnext;
+} OSSL_ACKM_TX_PKT;
+
+int ossl_ackm_on_tx_packet(OSSL_ACKM *ackm, OSSL_ACKM_TX_PKT *pkt);
+int ossl_ackm_on_rx_datagram(OSSL_ACKM *ackm, size_t num_bytes);
+
+#define OSSL_ACKM_ECN_NONE      0
+#define OSSL_ACKM_ECN_ECT1      1
+#define OSSL_ACKM_ECN_ECT0      2
+#define OSSL_ACKM_ECN_ECNCE     3
+
+typedef struct ossl_ackm_rx_pkt_st {
+    /* The packet number of the received packet. */
+    QUIC_PN pkt_num;
+
+    /* The time at which the packet was received. */
+    OSSL_TIME time;
+
+    /*
+     * One of the QUIC_PN_SPACE_* values. This qualifies the pkt_num field
+     * into a packet number space.
+     */
+    unsigned int pkt_space :2;
+
+    /* 1 if the packet has one or more ACK-eliciting frames. */
+    unsigned int is_ack_eliciting :1;
+
+    /*
+     * One of the OSSL_ACKM_ECN_* values. This is the ECN labelling applied to
+     * the received packet. If unknown, use OSSL_ACKM_ECN_NONE.
+     */
+    unsigned int ecn :2;
+} OSSL_ACKM_RX_PKT;
+
+int ossl_ackm_on_rx_packet(OSSL_ACKM *ackm, const OSSL_ACKM_RX_PKT *pkt);
+
+int ossl_ackm_on_rx_ack_frame(OSSL_ACKM *ackm, const OSSL_QUIC_FRAME_ACK *ack,
+                              int pkt_space, OSSL_TIME rx_time);
+
+int ossl_ackm_on_pkt_space_discarded(OSSL_ACKM *ackm, int pkt_space);
+int ossl_ackm_on_handshake_confirmed(OSSL_ACKM *ackm);
+int ossl_ackm_on_timeout(OSSL_ACKM *ackm);
+
+OSSL_TIME ossl_ackm_get_loss_detection_deadline(OSSL_ACKM *ackm);
+
+/*
+ * Generates an ACK frame, regardless of whether the ACK manager thinks
+ * one should currently be sent.
+ *
+ * This clears the flag returned by ossl_ackm_is_ack_desired and the deadline
+ * returned by ossl_ackm_get_ack_deadline.
+ */
+const OSSL_QUIC_FRAME_ACK *ossl_ackm_get_ack_frame(OSSL_ACKM *ackm,
+                                                   int pkt_space);
+
+/*
+ * Returns the deadline after which an ACK frame should be generated by calling
+ * ossl_ackm_get_ack_frame, or OSSL_TIME_INFINITY if no deadline is currently
+ * applicable. If the deadline has already passed, this function may return that
+ * deadline, or may return OSSL_TIME_ZERO.
+ */
+OSSL_TIME ossl_ackm_get_ack_deadline(OSSL_ACKM *ackm, int pkt_space);
+
+/*
+ * Returns 1 if the ACK manager thinks an ACK frame ought to be generated and
+ * sent at this time. ossl_ackm_get_ack_frame will always provide an ACK frame
+ * whether or not this returns 1, so it is suggested that you call this function
+ * first to determine whether you need to generate an ACK frame.
+ *
+ * The return value of this function can change based on calls to
+ * ossl_ackm_on_rx_packet and based on the passage of time (see
+ * ossl_ackm_get_ack_deadline).
+ */
+int ossl_ackm_is_ack_desired(OSSL_ACKM *ackm, int pkt_space);
+
+/*
+ * Returns 1 if the given RX PN is 'processable'. A processable PN is one that
+ * is not either
+ *
+ *   - duplicate, meaning that we have already been passed such a PN in a call
+ *     to ossl_ackm_on_rx_packet; or
+ *
+ *   - written off, meaning that the PN is so old we have stopped tracking state
+ *     for it (meaning that we cannot tell whether it is a duplicate and cannot
+ *     process it safely).
+ *
+ * This should be called for a packet before attempting to process its contents.
+ * Failure to do so may result in processing a duplicated packet in violation of
+ * the RFC.
+ *
+ * The return value of this function transitions from 1 to 0 for a given PN once
+ * that PN is passed to ossl_ackm_on_rx_packet, thus thus function must be used
+ * before calling ossl_ackm_on_rx_packet.
+ */
+int ossl_ackm_is_rx_pn_processable(OSSL_ACKM *ackm, QUIC_PN pn, int pkt_space);
+
+typedef struct ossl_ackm_probe_info_st {
+    uint32_t handshake;
+    uint32_t padded_initial;
+    uint32_t pto[QUIC_PN_SPACE_NUM];
+} OSSL_ACKM_PROBE_INFO;
+
+int ossl_ackm_get_probe_request(OSSL_ACKM *ackm, int clear,
+                                OSSL_ACKM_PROBE_INFO *info);
+
+int ossl_ackm_get_largest_unacked(OSSL_ACKM *ackm, int pkt_space, QUIC_PN *pn);
+
+#endif
diff --git a/include/internal/quic_cc.h b/include/internal/quic_cc.h
new file mode 100644
index 0000000000..298d9c5890
--- /dev/null
+++ b/include/internal/quic_cc.h
@@ -0,0 +1,150 @@
+/*
+ * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+#ifndef OSSL_QUIC_CC_H
+# define OSSL_QUIC_CC_H
+
+#include "openssl/params.h"
+#include "internal/time.h"
+
+typedef struct ossl_cc_data_st *OSSL_CC_DATA;
+
+typedef struct ossl_cc_method_st {
+    void *dummy;
+
+    /*
+     * Create a new OSSL_CC_DATA object to handle the congestion control
+     * calculations.
+     *
+     * |settings| are mandatory settings that will cause the
+     * new() call to fail if they are not understood).
+     * |options| are optional settings that will not
+     * cause the new() call to fail if they are not understood.
+     * |changeables| contain additional parameters that the congestion
+     * control algorithms need that can be updated during the
+     * connection lifetime - for example size of the datagram payload.
+     * To avoid calling a function with OSSL_PARAM array every time
+     * these parameters are changed the addresses of these param
+     * values are considered permanent and the values can be updated
+     * any time.
+     */
+    OSSL_CC_DATA *(*new)(OSSL_PARAM *settings, OSSL_PARAM *options,
+                         OSSL_PARAM *changeables);
+
+    /*
+     * Release the OSSL_CC_DATA.
+     */
+    void (*free)(OSSL_CC_DATA *ccdata);
+
+    /*
+     * Reset the congestion control state.
+     * |flags| to support different level of reset (partial/full).
+     */
+    void (*reset)(OSSL_CC_DATA *ccdata, int flags);
+
+    /*
+     * Set number of packets exempted from CC - used for probing
+     * |numpackets| is a small value (2).
+     * Returns 0 on error, 1 otherwise.
+     */
+    int (*set_exemption)(OSSL_CC_DATA *ccdata, int numpackets);
+
+    /*
+     * Get current number of packets exempted from CC.
+     * Returns negative value on error, the number otherwise.
+     */
+    int (*get_exemption)(OSSL_CC_DATA *ccdata);
+
+    /*
+     * Returns 1 if sending is allowed, 0 otherwise.
+     */
+    int (*can_send)(OSSL_CC_DATA *ccdata);
+
+    /*
+     * Returns number of bytes allowed to be sent.
+     * |time_since_last_send| is time since last send operation
+     * in microseconds.
+     * |time_valid| is 1 if the |time_since_last_send| holds
+     * a meaningful value, 0 otherwise.
+     */
+    size_t (*get_send_allowance)(OSSL_CC_DATA *ccdata,
+                                 OSSL_TIME time_since_last_send,
+                                 int time_valid);
+
+    /*
+     * Returns the maximum number of bytes allowed to be in flight.
+     */
+    size_t (*get_bytes_in_flight_max)(OSSL_CC_DATA *ccdata);
+
+    /*
+     * To be called when a packet with retransmittable data was sent.
+     * |num_retransmittable_bytes| is the number of bytes sent
+     * in the packet that are retransmittable.
+     * Returns 1 on success, 0 otherwise.
+     */
+    int (*on_data_sent)(OSSL_CC_DATA *ccdata,
+                        size_t num_retransmittable_bytes);
+
+    /*
+     * To be called when retransmittable data was invalidated.
+     * I.E. they are not considered in-flight anymore but
+     * are neither acknowledged nor lost. In particular used when
+     * 0RTT data was rejected.
+     * |num_retransmittable_bytes| is the number of bytes
+     * of the invalidated data.
+     * Returns 1 if sending is unblocked (can_send returns 1), 0
+     * otherwise.
+     */
+    int (*on_data_invalidated)(OSSL_CC_DATA *ccdata,
+                               size_t num_retransmittable_bytes);
+
+    /*
+     * To be called when sent data was acked.
+     * |time_now| is current time in microseconds.
+     * |largest_pn_acked| is the largest packet number of the acked
+     * packets.
+     * |num_retransmittable_bytes| is the number of retransmittable
+     * packet bytes that were newly acked.
+     * Returns 1 if sending is unblocked (can_send returns 1), 0
+     * otherwise.
+     */
+    int (*on_data_acked)(OSSL_CC_DATA *ccdata,
+                         OSSL_TIME time_now,
+                         uint64_t last_pn_acked,
+                         size_t num_retransmittable_bytes);
+
+    /*
+     * To be called when sent data is considered lost.
+     * |largest_pn_lost| is the largest packet number of the lost
+     * packets.
+     * |largest_pn_sent| is the largest packet number sent on this
+     * connection.
+     * |num_retransmittable_bytes| is the number of retransmittable
+     * packet bytes that are newly considered lost.
+     * |persistent_congestion| is 1 if the congestion is considered
+     * persistent (see RFC 9002 Section 7.6), 0 otherwise.
+     */
+    void (*on_data_lost)(OSSL_CC_DATA *ccdata,
+                         uint64_t largest_pn_lost,
+                         uint64_t largest_pn_sent,
+                         size_t num_retransmittable_bytes,
+                         int persistent_congestion);
+
+    /*
+     * To be called when all lost data from the previous call to
+     * on_data_lost() was actually acknowledged.
+     * This reverts the size of the congestion window to the state
+     * before the on_data_lost() call.
+     * Returns 1 if sending is unblocked, 0 otherwise.
+     */
+    int (*on_spurious_congestion_event)(OSSL_CC_DATA *ccdata);
+} OSSL_CC_METHOD;
+
+extern const OSSL_CC_METHOD ossl_cc_dummy_method;
+
+#endif
diff --git a/include/internal/quic_statm.h b/include/internal/quic_statm.h
new file mode 100644
index 0000000000..b551130007
--- /dev/null
+++ b/include/internal/quic_statm.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#ifndef OSSL_QUIC_STATS_H
+# define OSSL_QUIC_STATS_H
+
+# include <openssl/ssl.h>
+# include "internal/time.h"
+
+typedef struct ossl_statm_st {
+    OSSL_TIME smoothed_rtt, latest_rtt, min_rtt, rtt_variance, max_ack_delay;
+    char      have_first_sample;
+} OSSL_STATM;
+
+typedef struct ossl_rtt_info_st {
+    /* As defined in RFC 9002. */
+    OSSL_TIME smoothed_rtt, latest_rtt, rtt_variance, min_rtt, max_ack_delay;
+} OSSL_RTT_INFO;
+
+int ossl_statm_init(OSSL_STATM *statm);
+
+void ossl_statm_destroy(OSSL_STATM *statm);
+
+void ossl_statm_get_rtt_info(OSSL_STATM *statm, OSSL_RTT_INFO *rtt_info);
+
+void ossl_statm_update_rtt(OSSL_STATM *statm,
+                           OSSL_TIME ack_delay,
+                           OSSL_TIME override_latest_rtt);
+
+void ossl_statm_set_max_ack_delay(OSSL_STATM *statm, OSSL_TIME max_ack_delay);
+
+#endif
diff --git a/include/internal/quic_types.h b/include/internal/quic_types.h
index 6787de9c11..bd37019d21 100644
--- a/include/internal/quic_types.h
+++ b/include/internal/quic_types.h
@@ -12,6 +12,12 @@
 
 # include <openssl/ssl.h>
 
+/* QUIC packet number spaces. */
+#define QUIC_PN_SPACE_INITIAL       0
+#define QUIC_PN_SPACE_HANDSHAKE     1
+#define QUIC_PN_SPACE_APP           2
+#define QUIC_PN_SPACE_NUM           3
+
 /* QUIC packet number representation. */
 typedef uint64_t QUIC_PN;
 # define QUIC_PN_INVALID            UINT64_MAX
diff --git a/include/internal/time.h b/include/internal/time.h
index 6a7a05aae5..5cc55b3f51 100644
--- a/include/internal/time.h
+++ b/include/internal/time.h
@@ -98,6 +98,20 @@ int ossl_time_compare(OSSL_TIME a, OSSL_TIME b)
     return 0;
 }
 
+/* Returns true if an OSSL_TIME is OSSL_TIME_ZERO. */
+static ossl_unused ossl_inline
+int ossl_time_is_zero(OSSL_TIME t)
+{
+    return t == OSSL_TIME_ZERO;
+}
+
+/* Returns true if an OSSL_TIME is OSSL_TIME_INFINITY. */
+static ossl_unused ossl_inline
+int ossl_time_is_infinity(OSSL_TIME t)
+{
+    return t == OSSL_TIME_INFINITY;
+}
+
 /*
  * Arithmetic operations on times.
  * These operations are saturating, in that an overflow or underflow returns