diff options
Diffstat (limited to 'crypto/openssl/ssl/quic/cc_newreno.c')
| -rw-r--r-- | crypto/openssl/ssl/quic/cc_newreno.c | 485 |
1 files changed, 485 insertions, 0 deletions
diff --git a/crypto/openssl/ssl/quic/cc_newreno.c b/crypto/openssl/ssl/quic/cc_newreno.c new file mode 100644 index 000000000000..1fe37c276e58 --- /dev/null +++ b/crypto/openssl/ssl/quic/cc_newreno.c @@ -0,0 +1,485 @@ +#include "internal/quic_cc.h" +#include "internal/quic_types.h" +#include "internal/safe_math.h" + +OSSL_SAFE_MATH_UNSIGNED(u64, uint64_t) + +typedef struct ossl_cc_newreno_st { + /* Dependencies. */ + OSSL_TIME (*now_cb)(void *arg); + void *now_cb_arg; + + /* 'Constants' (which we allow to be configurable). */ + uint64_t k_init_wnd, k_min_wnd; + uint32_t k_loss_reduction_factor_num, k_loss_reduction_factor_den; + uint32_t persistent_cong_thresh; + + /* State. */ + size_t max_dgram_size; + uint64_t bytes_in_flight, cong_wnd, slow_start_thresh, bytes_acked; + OSSL_TIME cong_recovery_start_time; + + /* Unflushed state during multiple on-loss calls. */ + int processing_loss; /* 1 if not flushed */ + OSSL_TIME tx_time_of_last_loss; + + /* Diagnostic state. */ + int in_congestion_recovery; + + /* Diagnostic output locations. */ + size_t *p_diag_max_dgram_payload_len; + uint64_t *p_diag_cur_cwnd_size; + uint64_t *p_diag_min_cwnd_size; + uint64_t *p_diag_cur_bytes_in_flight; + uint32_t *p_diag_cur_state; +} OSSL_CC_NEWRENO; + +#define MIN_MAX_INIT_WND_SIZE 14720 /* RFC 9002 s. 7.2 */ + +/* TODO(QUIC FUTURE): Pacing support. */ + +static void newreno_set_max_dgram_size(OSSL_CC_NEWRENO *nr, + size_t max_dgram_size); +static void newreno_update_diag(OSSL_CC_NEWRENO *nr); + +static void newreno_reset(OSSL_CC_DATA *cc); + +static OSSL_CC_DATA *newreno_new(OSSL_TIME (*now_cb)(void *arg), + void *now_cb_arg) +{ + OSSL_CC_NEWRENO *nr; + + if ((nr = OPENSSL_zalloc(sizeof(*nr))) == NULL) + return NULL; + + nr->now_cb = now_cb; + nr->now_cb_arg = now_cb_arg; + + newreno_set_max_dgram_size(nr, QUIC_MIN_INITIAL_DGRAM_LEN); + newreno_reset((OSSL_CC_DATA *)nr); + + return (OSSL_CC_DATA *)nr; +} + +static void newreno_free(OSSL_CC_DATA *cc) +{ + OPENSSL_free(cc); +} + +static void newreno_set_max_dgram_size(OSSL_CC_NEWRENO *nr, + size_t max_dgram_size) +{ + size_t max_init_wnd; + int is_reduced = (max_dgram_size < nr->max_dgram_size); + + nr->max_dgram_size = max_dgram_size; + + max_init_wnd = 2 * max_dgram_size; + if (max_init_wnd < MIN_MAX_INIT_WND_SIZE) + max_init_wnd = MIN_MAX_INIT_WND_SIZE; + + nr->k_init_wnd = 10 * max_dgram_size; + if (nr->k_init_wnd > max_init_wnd) + nr->k_init_wnd = max_init_wnd; + + nr->k_min_wnd = 2 * max_dgram_size; + + if (is_reduced) + nr->cong_wnd = nr->k_init_wnd; + + newreno_update_diag(nr); +} + +static void newreno_reset(OSSL_CC_DATA *cc) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + nr->k_loss_reduction_factor_num = 1; + nr->k_loss_reduction_factor_den = 2; + nr->persistent_cong_thresh = 3; + + nr->cong_wnd = nr->k_init_wnd; + nr->bytes_in_flight = 0; + nr->bytes_acked = 0; + nr->slow_start_thresh = UINT64_MAX; + nr->cong_recovery_start_time = ossl_time_zero(); + + nr->processing_loss = 0; + nr->tx_time_of_last_loss = ossl_time_zero(); + nr->in_congestion_recovery = 0; +} + +static int newreno_set_input_params(OSSL_CC_DATA *cc, const OSSL_PARAM *params) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + const OSSL_PARAM *p; + size_t value; + + p = OSSL_PARAM_locate_const(params, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN); + if (p != NULL) { + if (!OSSL_PARAM_get_size_t(p, &value)) + return 0; + if (value < QUIC_MIN_INITIAL_DGRAM_LEN) + return 0; + + newreno_set_max_dgram_size(nr, value); + } + + return 1; +} + +static int bind_diag(OSSL_PARAM *params, const char *param_name, size_t len, + void **pp) +{ + const OSSL_PARAM *p = OSSL_PARAM_locate_const(params, param_name); + + *pp = NULL; + + if (p == NULL) + return 1; + + if (p->data_type != OSSL_PARAM_UNSIGNED_INTEGER + || p->data_size != len) + return 0; + + *pp = p->data; + return 1; +} + +static int newreno_bind_diagnostic(OSSL_CC_DATA *cc, OSSL_PARAM *params) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + size_t *new_p_max_dgram_payload_len; + uint64_t *new_p_cur_cwnd_size; + uint64_t *new_p_min_cwnd_size; + uint64_t *new_p_cur_bytes_in_flight; + uint32_t *new_p_cur_state; + + if (!bind_diag(params, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN, + sizeof(size_t), (void **)&new_p_max_dgram_payload_len) + || !bind_diag(params, OSSL_CC_OPTION_CUR_CWND_SIZE, + sizeof(uint64_t), (void **)&new_p_cur_cwnd_size) + || !bind_diag(params, OSSL_CC_OPTION_MIN_CWND_SIZE, + sizeof(uint64_t), (void **)&new_p_min_cwnd_size) + || !bind_diag(params, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT, + sizeof(uint64_t), (void **)&new_p_cur_bytes_in_flight) + || !bind_diag(params, OSSL_CC_OPTION_CUR_STATE, + sizeof(uint32_t), (void **)&new_p_cur_state)) + return 0; + + if (new_p_max_dgram_payload_len != NULL) + nr->p_diag_max_dgram_payload_len = new_p_max_dgram_payload_len; + + if (new_p_cur_cwnd_size != NULL) + nr->p_diag_cur_cwnd_size = new_p_cur_cwnd_size; + + if (new_p_min_cwnd_size != NULL) + nr->p_diag_min_cwnd_size = new_p_min_cwnd_size; + + if (new_p_cur_bytes_in_flight != NULL) + nr->p_diag_cur_bytes_in_flight = new_p_cur_bytes_in_flight; + + if (new_p_cur_state != NULL) + nr->p_diag_cur_state = new_p_cur_state; + + newreno_update_diag(nr); + return 1; +} + +static void unbind_diag(OSSL_PARAM *params, const char *param_name, + void **pp) +{ + const OSSL_PARAM *p = OSSL_PARAM_locate_const(params, param_name); + + if (p != NULL) + *pp = NULL; +} + +static int newreno_unbind_diagnostic(OSSL_CC_DATA *cc, OSSL_PARAM *params) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + unbind_diag(params, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN, + (void **)&nr->p_diag_max_dgram_payload_len); + unbind_diag(params, OSSL_CC_OPTION_CUR_CWND_SIZE, + (void **)&nr->p_diag_cur_cwnd_size); + unbind_diag(params, OSSL_CC_OPTION_MIN_CWND_SIZE, + (void **)&nr->p_diag_min_cwnd_size); + unbind_diag(params, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT, + (void **)&nr->p_diag_cur_bytes_in_flight); + unbind_diag(params, OSSL_CC_OPTION_CUR_STATE, + (void **)&nr->p_diag_cur_state); + return 1; +} + +static void newreno_update_diag(OSSL_CC_NEWRENO *nr) +{ + if (nr->p_diag_max_dgram_payload_len != NULL) + *nr->p_diag_max_dgram_payload_len = nr->max_dgram_size; + + if (nr->p_diag_cur_cwnd_size != NULL) + *nr->p_diag_cur_cwnd_size = nr->cong_wnd; + + if (nr->p_diag_min_cwnd_size != NULL) + *nr->p_diag_min_cwnd_size = nr->k_min_wnd; + + if (nr->p_diag_cur_bytes_in_flight != NULL) + *nr->p_diag_cur_bytes_in_flight = nr->bytes_in_flight; + + if (nr->p_diag_cur_state != NULL) { + if (nr->in_congestion_recovery) + *nr->p_diag_cur_state = 'R'; + else if (nr->cong_wnd < nr->slow_start_thresh) + *nr->p_diag_cur_state = 'S'; + else + *nr->p_diag_cur_state = 'A'; + } +} + +static int newreno_in_cong_recovery(OSSL_CC_NEWRENO *nr, OSSL_TIME tx_time) +{ + return ossl_time_compare(tx_time, nr->cong_recovery_start_time) <= 0; +} + +static void newreno_cong(OSSL_CC_NEWRENO *nr, OSSL_TIME tx_time) +{ + int err = 0; + + /* No reaction if already in a recovery period. */ + if (newreno_in_cong_recovery(nr, tx_time)) + return; + + /* Start a new recovery period. */ + nr->in_congestion_recovery = 1; + nr->cong_recovery_start_time = nr->now_cb(nr->now_cb_arg); + + /* slow_start_thresh = cong_wnd * loss_reduction_factor */ + nr->slow_start_thresh + = safe_muldiv_u64(nr->cong_wnd, + nr->k_loss_reduction_factor_num, + nr->k_loss_reduction_factor_den, + &err); + + if (err) + nr->slow_start_thresh = UINT64_MAX; + + nr->cong_wnd = nr->slow_start_thresh; + if (nr->cong_wnd < nr->k_min_wnd) + nr->cong_wnd = nr->k_min_wnd; +} + +static void newreno_flush(OSSL_CC_NEWRENO *nr, uint32_t flags) +{ + if (!nr->processing_loss) + return; + + newreno_cong(nr, nr->tx_time_of_last_loss); + + if ((flags & OSSL_CC_LOST_FLAG_PERSISTENT_CONGESTION) != 0) { + nr->cong_wnd = nr->k_min_wnd; + nr->cong_recovery_start_time = ossl_time_zero(); + } + + nr->processing_loss = 0; + newreno_update_diag(nr); +} + +static uint64_t newreno_get_tx_allowance(OSSL_CC_DATA *cc) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + if (nr->bytes_in_flight >= nr->cong_wnd) + return 0; + + return nr->cong_wnd - nr->bytes_in_flight; +} + +static OSSL_TIME newreno_get_wakeup_deadline(OSSL_CC_DATA *cc) +{ + if (newreno_get_tx_allowance(cc) > 0) { + /* We have TX allowance now so wakeup immediately */ + return ossl_time_zero(); + } else { + /* + * The NewReno congestion controller does not vary its state in time, + * only in response to stimulus. + */ + return ossl_time_infinite(); + } +} + +static int newreno_on_data_sent(OSSL_CC_DATA *cc, uint64_t num_bytes) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + nr->bytes_in_flight += num_bytes; + newreno_update_diag(nr); + return 1; +} + +static int newreno_is_cong_limited(OSSL_CC_NEWRENO *nr) +{ + uint64_t wnd_rem; + + /* We are congestion-limited if we are already at the congestion window. */ + if (nr->bytes_in_flight >= nr->cong_wnd) + return 1; + + wnd_rem = nr->cong_wnd - nr->bytes_in_flight; + + /* + * Consider ourselves congestion-limited if less than three datagrams' worth + * of congestion window remains to be spent, or if we are in slow start and + * have consumed half of our window. + */ + return (nr->cong_wnd < nr->slow_start_thresh && wnd_rem <= nr->cong_wnd / 2) + || wnd_rem <= 3 * nr->max_dgram_size; +} + +static int newreno_on_data_acked(OSSL_CC_DATA *cc, + const OSSL_CC_ACK_INFO *info) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + /* + * Packet has been acked. Firstly, remove it from the aggregate count of + * bytes in flight. + */ + nr->bytes_in_flight -= info->tx_size; + + /* + * We use acknowledgement of data as a signal that we are not at channel + * capacity and that it may be reasonable to increase the congestion window. + * However, acknowledgement is not a useful signal that there is further + * capacity if we are not actually saturating the congestion window that we + * already have (for example, if the application is not generating much data + * or we are limited by flow control). Therefore, we only expand the + * congestion window if we are consuming a significant fraction of the + * congestion window. + */ + if (!newreno_is_cong_limited(nr)) + goto out; + + /* + * We can handle acknowledgement of a packet in one of three ways + * depending on our current state: + * + * - Congestion Recovery: Do nothing. We don't start increasing + * the congestion window in response to acknowledgements until + * we are no longer in the Congestion Recovery state. + * + * - Slow Start: Increase the congestion window using the slow + * start scale. + * + * - Congestion Avoidance: Increase the congestion window using + * the congestion avoidance scale. + */ + if (newreno_in_cong_recovery(nr, info->tx_time)) { + /* Congestion recovery, do nothing. */ + } else if (nr->cong_wnd < nr->slow_start_thresh) { + /* When this condition is true we are in the Slow Start state. */ + nr->cong_wnd += info->tx_size; + nr->in_congestion_recovery = 0; + } else { + /* Otherwise, we are in the Congestion Avoidance state. */ + nr->bytes_acked += info->tx_size; + + /* + * Avoid integer division as per RFC 9002 s. B.5. / RFC3465 s. 2.1. + */ + if (nr->bytes_acked >= nr->cong_wnd) { + nr->bytes_acked -= nr->cong_wnd; + nr->cong_wnd += nr->max_dgram_size; + } + + nr->in_congestion_recovery = 0; + } + +out: + newreno_update_diag(nr); + return 1; +} + +static int newreno_on_data_lost(OSSL_CC_DATA *cc, + const OSSL_CC_LOSS_INFO *info) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + if (info->tx_size > nr->bytes_in_flight) + return 0; + + nr->bytes_in_flight -= info->tx_size; + + if (!nr->processing_loss) { + + if (ossl_time_compare(info->tx_time, nr->tx_time_of_last_loss) <= 0) + /* + * After triggering congestion due to a lost packet at time t, don't + * trigger congestion again due to any subsequently detected lost + * packet at a time s < t, as we've effectively already signalled + * congestion on loss of that and subsequent packets. + */ + goto out; + + nr->processing_loss = 1; + + /* + * Cancel any pending window increase in the Congestion Avoidance state. + */ + nr->bytes_acked = 0; + } + + nr->tx_time_of_last_loss + = ossl_time_max(nr->tx_time_of_last_loss, info->tx_time); + +out: + newreno_update_diag(nr); + return 1; +} + +static int newreno_on_data_lost_finished(OSSL_CC_DATA *cc, uint32_t flags) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + newreno_flush(nr, flags); + return 1; +} + +static int newreno_on_data_invalidated(OSSL_CC_DATA *cc, + uint64_t num_bytes) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + nr->bytes_in_flight -= num_bytes; + newreno_update_diag(nr); + return 1; +} + +static int newreno_on_ecn(OSSL_CC_DATA *cc, + const OSSL_CC_ECN_INFO *info) +{ + OSSL_CC_NEWRENO *nr = (OSSL_CC_NEWRENO *)cc; + + nr->processing_loss = 1; + nr->bytes_acked = 0; + nr->tx_time_of_last_loss = info->largest_acked_time; + newreno_flush(nr, 0); + return 1; +} + +const OSSL_CC_METHOD ossl_cc_newreno_method = { + newreno_new, + newreno_free, + newreno_reset, + newreno_set_input_params, + newreno_bind_diagnostic, + newreno_unbind_diagnostic, + newreno_get_tx_allowance, + newreno_get_wakeup_deadline, + newreno_on_data_sent, + newreno_on_data_acked, + newreno_on_data_lost, + newreno_on_data_lost_finished, + newreno_on_data_invalidated, + newreno_on_ecn, +}; |