| #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, |
| }; |
