This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit 7a06763b223b3993f87c77039f84555e1c4d8eed Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Fri Dec 16 21:12:50 2022 +0000

Avoid increasing the congestion window if it is not full.

Also provides some stickiness, so that once full, the congestion window is considered still full for the rest of an update cycle, or the entire congestion window.

In this way, we avoid increasing the congestion window if it is not fully utilized, but we can still back off in this case. This substantially reduces queue use in Shadow. --- src/core/or/congestion_control_st.h | 7 ++ src/core/or/congestion_control_vegas.c | 155 +++++++++++++++++++++++++++++---- 2 files changed, 143 insertions(+), 19 deletions(-)

diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index f88e1f4a9a..3fe693d989 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -160,9 +160,16 @@ struct congestion_control_t { */ uint64_t next_cc_event;

+ /** Counts down until we process a cwnd worth of SENDME acks. + * Used to track full cwnd status. */ + uint64_t next_cwnd_event; + /** Are we in slow start? */ bool in_slow_start;

+ /** Has the cwnd become full since last cwnd update? */ + bool cwnd_full; + /** Is the local channel blocked on us? That's a congestion signal */ bool blocked_chan;

diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index 54b89dad64..044689421e 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -50,6 +50,25 @@ #define VEGAS_DELTA_ONION_DFLT (9*OUTBUF_CELLS) #define VEGAS_SSCAP_ONION_DFLT (600)

+/** + * Number of sendme_incs between cwnd and inflight for cwnd to be + * still considered full */ +#define VEGAS_CWND_FULL_GAP_DFLT (1) +static int cc_vegas_cwnd_full_gap = VEGAS_CWND_FULL_GAP_DFLT; + +/** + * If the cwnd becomes less than this percent full at any point, + * we declare it not full immediately. + */ +#define VEGAS_CWND_FULL_MINPCT_DFLT (75) +static int cc_vegas_cwnd_full_minpct = VEGAS_CWND_FULL_MINPCT_DFLT; + +/** + * Param to decide when to reset the cwnd. + */ +#define VEGAS_CWND_FULL_PER_CWND_DFLT (1) +static int cc_cwnd_full_per_cwnd = VEGAS_CWND_FULL_PER_CWND_DFLT; + /** Moving average of the cc->cwnd from each circuit exiting slowstart. */ double cc_stats_vegas_exit_ss_cwnd_ma = 0; double cc_stats_vegas_exit_ss_bdp_ma = 0; @@ -173,6 +192,24 @@ congestion_control_vegas_set_params(congestion_control_t *cc, delta, 0, INT32_MAX); + + cc_vegas_cwnd_full_minpct = + networkstatus_get_param(NULL, "cc_cwnd_full_minpct", + VEGAS_CWND_FULL_MINPCT_DFLT, + 0, + 100); + + cc_vegas_cwnd_full_gap = + networkstatus_get_param(NULL, "cc_cwnd_full_gap", + VEGAS_CWND_FULL_GAP_DFLT, + 0, + INT32_MAX); + + cc_cwnd_full_per_cwnd = + networkstatus_get_param(NULL, "cc_cwnd_full_per_cwnd", + VEGAS_CWND_FULL_PER_CWND_DFLT, + 0, + 1); }

/** @@ -288,6 +325,62 @@ congestion_control_vegas_exit_slow_start(const circuit_t *circ, } }

+/** + * Returns true if the congestion window is considered full. + * + * We allow a number of sendme_incs gap in case buffering issues + * with edge conns cause the window to occasionally be not quite + * full. This can happen if several SENDMEs arrive before we + * return to the eventloop to fill the inbuf on edge connections. + */ +static inline bool +cwnd_is_full(const congestion_control_t *cc) +{ + if (cc->inflight + cc_vegas_cwnd_full_gap*cc->sendme_inc >= cc->cwnd) { + return true; + } else { + return false; + } +} + +/** + * Returns true if the congestion window is no longer full. + * + * This functions as a low watermark, below which we stop + * allowing cwnd increments. + */ +static inline bool +cwnd_is_nonfull(const congestion_control_t *cc) +{ + /* Use multiply form to avoid division */ + if (100*cc->inflight < cc_vegas_cwnd_full_minpct * cc->cwnd) { + return true; + } else { + return false; + } +} + +/** + * Decide if it is time to reset the cwnd_full status. + * + * If cc_cwnd_full_per_cwnd=1, we reset cwnd_full once per congestion + * window, ie: + * next_cwnd_event == SENDME_PER_CWND(cc) + * + * Otherwise, we reset cwnd_full whenever there is an update of + * the congestion window, ie: + * next_cc_event == CWND_UPDATE_RATE(cc) + */ +static inline bool +cwnd_full_reset(const congestion_control_t *cc) +{ + if (cc_cwnd_full_per_cwnd) { + return (cc->next_cwnd_event == SENDME_PER_CWND(cc)); + } else { + return (cc->next_cc_event == CWND_UPDATE_RATE(cc)); + } +} + /** * Process a SENDME and update the congestion window according to the * rules specified in TOR_VEGAS of Proposal #324. @@ -322,6 +415,10 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, if (cc->next_cc_event) cc->next_cc_event--;

+ /* Update ack counter until a full cwnd is processed */ + if (cc->next_cwnd_event) + cc->next_cwnd_event--; + /* Compute BDP and RTT. If we did not update, don't run the alg */ if (!congestion_control_update_circuit_estimates(cc, circ, layer_hint)) { cc->inflight = cc->inflight - cc->sendme_inc; @@ -335,26 +432,36 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, else queue_use = cc->cwnd - vegas_bdp(cc);

+ /* Update the full state */ + if (cwnd_is_full(cc)) + cc->cwnd_full = 1; + else if (cwnd_is_nonfull(cc)) + cc->cwnd_full = 0; + if (cc->in_slow_start) { if (queue_use < cc->vegas_params.gamma && !cc->blocked_chan) { - /* Get the "Limited Slow Start" increment */ - uint64_t inc = rfc3742_ss_inc(cc); - - // Check if inc is less than what we would do in steady-state - // avoidance - if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)) { - cc->cwnd += inc; - congestion_control_vegas_exit_slow_start(circ, cc); - - cc_stats_vegas_below_ss_inc_floor++; - - /* We exited slow start without being blocked */ - cc_stats_vegas_ss_csig_blocked_ma = - stats_update_running_avg(cc_stats_vegas_ss_csig_blocked_ma, - 0); - } else { - cc->cwnd += inc; - cc->next_cc_event = 1; // Technically irellevant, but for consistency + /* If the congestion window is not fully in use, skip any + * increment of cwnd in slow start */ + if (cc->cwnd_full) { + /* Get the "Limited Slow Start" increment */ + uint64_t inc = rfc3742_ss_inc(cc); + + // Check if inc is less than what we would do in steady-state + // avoidance + if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)) { + cc->cwnd += inc; + congestion_control_vegas_exit_slow_start(circ, cc); + + cc_stats_vegas_below_ss_inc_floor++; + + /* We exited slow start without being blocked */ + cc_stats_vegas_ss_csig_blocked_ma = + stats_update_running_avg(cc_stats_vegas_ss_csig_blocked_ma, + 0); + } else { + cc->cwnd += inc; + cc->next_cc_event = 1; // Technically irellevant, but for consistency + } } } else { uint64_t old_cwnd = cc->cwnd; @@ -444,7 +551,8 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, cc_stats_vegas_csig_delta_ma = stats_update_running_avg(cc_stats_vegas_csig_delta_ma, 0); - } else if (queue_use < cc->vegas_params.alpha) { + } else if (cc->cwnd_full && + queue_use < cc->vegas_params.alpha) { cc->cwnd += CWND_INC(cc);

/* Percentage counters: Add 100% alpha, 0 for other two */ @@ -494,6 +602,15 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, } }

+ /* Once per cwnd, reset the cwnd full state */ + if (cc->next_cwnd_event == 0) { + cc->next_cwnd_event = SENDME_PER_CWND(cc); + } + + /* Decide if enough time has passed to reset the cwnd utilization */ + if (cwnd_full_reset(cc)) + cc->cwnd_full = 0; + /* Update inflight with ack */ cc->inflight = cc->inflight - cc->sendme_inc;

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit b7759403bf3950e5f422c6d5e0276f0d0bb25e88 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Wed Dec 21 17:35:09 2022 +0000

Reduce size of congestion control next_*_event fields.

Since these are derived from the number of SENDMEs in a cwnd/cc update, and a cwnd should not exceed ~10k, there's plenty of room in uint16_t for them, even if the network gets significantly faster. --- src/core/or/congestion_control_nola.c | 4 ++-- src/core/or/congestion_control_st.h | 4 ++-- src/core/or/congestion_control_westwood.c | 4 ++-- 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/src/core/or/congestion_control_nola.c b/src/core/or/congestion_control_nola.c index 53bbf9e7b4..d8ad69a78c 100644 --- a/src/core/or/congestion_control_nola.c +++ b/src/core/or/congestion_control_nola.c @@ -108,7 +108,7 @@ congestion_control_nola_process_sendme(congestion_control_t *cc, "CC TOR_NOLA: Circuit %d " "CWND: %"PRIu64", " "INFL: %"PRIu64", " - "NCCE: %"PRIu64", " + "NCCE: %"PRIu16", " "SS: %d", CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, cc->cwnd, @@ -121,7 +121,7 @@ congestion_control_nola_process_sendme(congestion_control_t *cc, "CC TOR_NOLA: Circuit %"PRIu64":%d " "CWND: %"PRIu64", " "INFL: %"PRIu64", " - "NCCE: %"PRIu64", " + "NCCE: %"PRIu16", " "SS: %d", CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, CONST_TO_OR_CIRCUIT(circ)->p_circ_id, diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index 08bf70f73b..0cc4e43938 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -158,11 +158,11 @@ struct congestion_control_t { * It is also reset to 0 immediately whenever the circuit's orconn is * blocked, and when a previously blocked orconn is unblocked. */ - uint64_t next_cc_event; + uint16_t next_cc_event;

/** Counts down until we process a cwnd worth of SENDME acks. * Used to track full cwnd status. */ - uint64_t next_cwnd_event; + uint16_t next_cwnd_event;

/** Are we in slow start? */ bool in_slow_start; diff --git a/src/core/or/congestion_control_westwood.c b/src/core/or/congestion_control_westwood.c index e57a661b85..d28ddf3442 100644 --- a/src/core/or/congestion_control_westwood.c +++ b/src/core/or/congestion_control_westwood.c @@ -201,7 +201,7 @@ congestion_control_westwood_process_sendme(congestion_control_t *cc, "CC: TOR_WESTWOOD Circuit %d " "CWND: %"PRIu64", " "INFL: %"PRIu64", " - "NCCE: %"PRIu64", " + "NCCE: %"PRIu16", " "WRTT: %"PRIu64", " "WSIG: %"PRIu64", " "SS: %d", @@ -218,7 +218,7 @@ congestion_control_westwood_process_sendme(congestion_control_t *cc, "CC: TOR_WESTWOOD Circuit %"PRIu64":%d " "CWND: %"PRIu64", " "INFL: %"PRIu64", " - "NCCE: %"PRIu64", " + "NCCE: %"PRIu16", " "WRTT: %"PRIu64", " "WSIG: %"PRIu64", " "SS: %d",

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit 5745370666210e7d07889fed6a3008db9004807f Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Wed Dec 14 17:19:01 2022 +0000

Changes file for bug 40732 --- changes/bug40732 | 7 +++++++ 1 file changed, 7 insertions(+)

diff --git a/changes/bug40732 b/changes/bug40732 new file mode 100644 index 0000000000..f2388e7e8d --- /dev/null +++ b/changes/bug40732 @@ -0,0 +1,7 @@ + o Major bugfixes (congestion control): + - Avoid incrementing the congestion window when the window is not + fully in use. Thia prevents overshoot in cases where long periods + of low activity would allow our congestion window to grow, and + then get followed by a burst, which would cause queue overload. + Also improve the increment checks for RFC3742. Fixes bug 40732; + bugfix on 0.4.7.5-alpha.

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit f4499bb5e27a96e1558f99edb081de473c13c7a6 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Wed Dec 21 01:18:28 2022 +0000

Clean up next_cc_event handling. --- src/core/or/congestion_control_st.h | 2 +- src/core/or/congestion_control_vegas.c | 14 +++++--------- 2 files changed, 6 insertions(+), 10 deletions(-)

diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index 3fe693d989..08bf70f73b 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -231,7 +231,7 @@ static inline uint64_t CWND_UPDATE_RATE(const struct congestion_control_t *cc) * of acks */

if (cc->in_slow_start) { - return ((cc->cwnd + cc->sendme_inc/2)/cc->sendme_inc); + return 1; } else { return ((cc->cwnd + cc->cwnd_inc_rate*cc->sendme_inc/2) / (cc->cwnd_inc_rate*cc->sendme_inc)); diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index 044689421e..ae945e7e00 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -301,7 +301,6 @@ congestion_control_vegas_exit_slow_start(const circuit_t *circ, { congestion_control_vegas_log(circ, cc); cc->in_slow_start = 0; - cc->next_cc_event = CWND_UPDATE_RATE(cc); congestion_control_vegas_log(circ, cc);

/* Update metricsport metrics */ @@ -445,11 +444,11 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, if (cc->cwnd_full) { /* Get the "Limited Slow Start" increment */ uint64_t inc = rfc3742_ss_inc(cc); + cc->cwnd += inc;

// Check if inc is less than what we would do in steady-state // avoidance if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)) { - cc->cwnd += inc; congestion_control_vegas_exit_slow_start(circ, cc);

cc_stats_vegas_below_ss_inc_floor++; @@ -458,9 +457,6 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, cc_stats_vegas_ss_csig_blocked_ma = stats_update_running_avg(cc_stats_vegas_ss_csig_blocked_ma, 0); - } else { - cc->cwnd += inc; - cc->next_cc_event = 1; // Technically irellevant, but for consistency } } } else { @@ -581,9 +577,6 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, /* cwnd can never fall below 1 increment */ cc->cwnd = MAX(cc->cwnd, cc->cwnd_min);

- /* Schedule next update */ - cc->next_cc_event = CWND_UPDATE_RATE(cc); - congestion_control_vegas_log(circ, cc);

/* Update metrics */ @@ -602,10 +595,13 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, } }

- /* Once per cwnd, reset the cwnd full state */ + /* Reset event counters */ if (cc->next_cwnd_event == 0) { cc->next_cwnd_event = SENDME_PER_CWND(cc); } + if (cc->next_cc_event == 0) { + cc->next_cc_event = CWND_UPDATE_RATE(cc); + }

/* Decide if enough time has passed to reset the cwnd utilization */ if (cwnd_full_reset(cc))

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit 5ddd3a9069081c9a96d9beb1b0ef99f27636eef5 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Thu Dec 15 22:03:26 2022 +0000

Safety fixes to RFC3742 --- src/core/or/congestion_control_vegas.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index ae945e7e00..71ffde3061 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -283,8 +283,11 @@ rfc3742_ss_inc(const congestion_control_t *cc) // => K = 2*cwnd/max_ssthresh // cwnd += int(MSS/K); // => cwnd += MSS*max_ssthresh/(2*cwnd) - return ((uint64_t)cc->sendme_inc*cc->vegas_params.ss_cwnd_cap + cc->cwnd)/ - (2*cc->cwnd); + // Return at least 1 for inc. + return MAX( + ((uint64_t)cc->sendme_inc*cc->vegas_params.ss_cwnd_cap + cc->cwnd)/ + (2*cc->cwnd), + 1); } }

@@ -447,8 +450,10 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, cc->cwnd += inc;

// Check if inc is less than what we would do in steady-state - // avoidance - if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)) { + // avoidance. Note that this is likely never to happen + // in practice, but we keep this block and the metrics to make + // sure. + if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)*cc->cwnd_inc_rate) { congestion_control_vegas_exit_slow_start(circ, cc);

cc_stats_vegas_below_ss_inc_floor++;

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository tor.

commit c50496036b5eea150ce5019b06140b8065f992a2 Author: David Goulet dgoulet@torproject.org AuthorDate: Tue Jan 10 10:13:33 2023 -0500

cc: Rename function to avoid confusion

Signed-off-by: David Goulet dgoulet@torproject.org --- src/core/or/congestion_control_vegas.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index 71ffde3061..8f9c39cea6 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -336,7 +336,7 @@ congestion_control_vegas_exit_slow_start(const circuit_t *circ, * return to the eventloop to fill the inbuf on edge connections. */ static inline bool -cwnd_is_full(const congestion_control_t *cc) +cwnd_became_full(const congestion_control_t *cc) { if (cc->inflight + cc_vegas_cwnd_full_gap*cc->sendme_inc >= cc->cwnd) { return true; @@ -352,7 +352,7 @@ cwnd_is_full(const congestion_control_t *cc) * allowing cwnd increments. */ static inline bool -cwnd_is_nonfull(const congestion_control_t *cc) +cwnd_became_nonfull(const congestion_control_t *cc) { /* Use multiply form to avoid division */ if (100*cc->inflight < cc_vegas_cwnd_full_minpct * cc->cwnd) { @@ -435,9 +435,9 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, queue_use = cc->cwnd - vegas_bdp(cc);

/* Update the full state */ - if (cwnd_is_full(cc)) + if (cwnd_became_full(cc)) cc->cwnd_full = 1; - else if (cwnd_is_nonfull(cc)) + else if (cwnd_became_nonfull(cc)) cc->cwnd_full = 0;

if (cc->in_slow_start) {