From owner-svn-src-all@freebsd.org Mon Mar 26 19:53:37 2018 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 0E781F65D21; Mon, 26 Mar 2018 19:53:37 +0000 (UTC) (envelope-from sbruno@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id B91B2702E5; Mon, 26 Mar 2018 19:53:36 +0000 (UTC) (envelope-from sbruno@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id B3DA911800; Mon, 26 Mar 2018 19:53:36 +0000 (UTC) (envelope-from sbruno@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w2QJraSg001148; Mon, 26 Mar 2018 19:53:36 GMT (envelope-from sbruno@FreeBSD.org) Received: (from sbruno@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w2QJraXx001144; Mon, 26 Mar 2018 19:53:36 GMT (envelope-from sbruno@FreeBSD.org) Message-Id: <201803261953.w2QJraXx001144@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: sbruno set sender to sbruno@FreeBSD.org using -f From: Sean Bruno Date: Mon, 26 Mar 2018 19:53:36 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r331567 - head/sys/netinet/cc X-SVN-Group: head X-SVN-Commit-Author: sbruno X-SVN-Commit-Paths: head/sys/netinet/cc X-SVN-Commit-Revision: 331567 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Mar 2018 19:53:37 -0000 Author: sbruno Date: Mon Mar 26 19:53:36 2018 New Revision: 331567 URL: https://svnweb.freebsd.org/changeset/base/331567 Log: CC Cubic: fix underflow for cubic_cwnd() Singed calculations in cubic_cwnd() can result in negative cwnd value which is then cast to an unsigned value. Values less than 1 mss are generally bad for other parts of the code, also fixed. Submitted by: Jason Eggleston Sponsored by: Limelight Networks Differential Revision: https://reviews.freebsd.org/D14141 Modified: head/sys/netinet/cc/cc.h head/sys/netinet/cc/cc_cubic.c head/sys/netinet/cc/cc_cubic.h Modified: head/sys/netinet/cc/cc.h ============================================================================== --- head/sys/netinet/cc/cc.h Mon Mar 26 19:53:02 2018 (r331566) +++ head/sys/netinet/cc/cc.h Mon Mar 26 19:53:36 2018 (r331567) @@ -102,6 +102,8 @@ struct cc_var { #define CCF_ACKNOW 0x0008 /* Will this ack be sent now? */ #define CCF_IPHDR_CE 0x0010 /* Does this packet set CE bit? */ #define CCF_TCPHDR_CWR 0x0020 /* Does this packet set CWR bit? */ +#define CCF_MAX_CWND 0x0040 /* Have we reached maximum cwnd? */ +#define CCF_CHG_MAX_CWND 0x0080 /* Cubic max_cwnd changed, for K */ /* ACK types passed to the ack_received() hook. */ #define CC_ACK 0x0001 /* Regular in sequence ACK. */ Modified: head/sys/netinet/cc/cc_cubic.c ============================================================================== --- head/sys/netinet/cc/cc_cubic.c Mon Mar 26 19:53:02 2018 (r331566) +++ head/sys/netinet/cc/cc_cubic.c Mon Mar 26 19:53:36 2018 (r331567) @@ -88,6 +88,8 @@ struct cubic { unsigned long max_cwnd; /* cwnd at the previous congestion event. */ unsigned long prev_max_cwnd; + /* Cached value for t_maxseg when K was computed */ + uint32_t k_maxseg; /* Number of congestion events. */ uint32_t num_cong_events; /* Minimum observed rtt in ticks. */ @@ -124,6 +126,9 @@ cubic_ack_received(struct cc_var *ccv, uint16_t type) cubic_data = ccv->cc_data; cubic_record_rtt(ccv); + if (ccv->flags & CCF_MAX_CWND) + return; + /* * Regular ACK and we're not in cong/fast recovery and we're cwnd * limited and we're either not doing ABC or are slow starting or are @@ -151,6 +156,12 @@ cubic_ack_received(struct cc_var *ccv, uint16_t type) cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, CCV(ccv, t_maxseg)); + if (ccv->flags & CCF_CHG_MAX_CWND || cubic_data->k_maxseg != CCV(ccv, t_maxseg)) { + cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, t_maxseg)); + cubic_data->k_maxseg = CCV(ccv, t_maxseg); + ccv->flags &= ~(CCF_MAX_CWND|CCF_CHG_MAX_CWND); + } + w_cubic_next = cubic_cwnd(ticks_since_cong + cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, CCV(ccv, t_maxseg), cubic_data->K); @@ -162,13 +173,18 @@ cubic_ack_received(struct cc_var *ccv, uint16_t type) * TCP-friendly region, follow tf * cwnd growth. */ - CCV(ccv, snd_cwnd) = w_tf; + CCV(ccv, snd_cwnd) = ulmin(w_tf, TCP_MAXWIN << CCV(ccv, snd_scale)); else if (CCV(ccv, snd_cwnd) < w_cubic_next) { /* * Concave or convex region, follow CUBIC * cwnd growth. */ + if (w_cubic_next >= TCP_MAXWIN << CCV(ccv, snd_scale)) { + w_cubic_next = TCP_MAXWIN << CCV(ccv, snd_scale); + ccv->flags |= CCF_MAX_CWND; + } + w_cubic_next = ulmin(w_cubic_next, TCP_MAXWIN << CCV(ccv, snd_scale)); if (V_tcp_do_rfc3465) CCV(ccv, snd_cwnd) = w_cubic_next; else @@ -186,8 +202,10 @@ cubic_ack_received(struct cc_var *ccv, uint16_t type) * max_cwnd. */ if (cubic_data->num_cong_events == 0 && - cubic_data->max_cwnd < CCV(ccv, snd_cwnd)) + cubic_data->max_cwnd < CCV(ccv, snd_cwnd)) { cubic_data->max_cwnd = CCV(ccv, snd_cwnd); + ccv->flags |= CCF_CHG_MAX_CWND; + } } } } @@ -238,6 +256,7 @@ cubic_cong_signal(struct cc_var *ccv, uint32_t type) cubic_data->num_cong_events++; cubic_data->prev_max_cwnd = cubic_data->max_cwnd; cubic_data->max_cwnd = CCV(ccv, snd_cwnd); + ccv->flags |= CCF_CHG_MAX_CWND; } ENTER_RECOVERY(CCV(ccv, t_flags)); } @@ -250,6 +269,8 @@ cubic_cong_signal(struct cc_var *ccv, uint32_t type) cubic_data->prev_max_cwnd = cubic_data->max_cwnd; cubic_data->max_cwnd = CCV(ccv, snd_cwnd); cubic_data->t_last_cong = ticks; + ccv->flags |= CCF_CHG_MAX_CWND; + ccv->flags &= ~CCF_MAX_CWND; CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); ENTER_CONGRECOVERY(CCV(ccv, t_flags)); } @@ -266,6 +287,7 @@ cubic_cong_signal(struct cc_var *ccv, uint32_t type) if (CCV(ccv, t_rxtshift) >= 2) { cubic_data->num_cong_events++; cubic_data->t_last_cong = ticks; + ccv->flags &= ~CCF_MAX_CWND; } break; } @@ -284,6 +306,7 @@ cubic_conn_init(struct cc_var *ccv) * get used. */ cubic_data->max_cwnd = CCV(ccv, snd_cwnd); + ccv->flags |= CCF_CHG_MAX_CWND; } static int @@ -308,9 +331,11 @@ cubic_post_recovery(struct cc_var *ccv) pipe = 0; /* Fast convergence heuristic. */ - if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) + if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) { cubic_data->max_cwnd = (cubic_data->max_cwnd * CUBIC_FC_FACTOR) >> CUBIC_SHIFT; + ccv->flags |= CCF_CHG_MAX_CWND; + } if (IN_FASTRECOVERY(CCV(ccv, t_flags))) { /* @@ -333,6 +358,7 @@ cubic_post_recovery(struct cc_var *ccv) cubic_data->max_cwnd) >> CUBIC_SHIFT)); } cubic_data->t_last_cong = ticks; + ccv->flags &= ~CCF_MAX_CWND; /* Calculate the average RTT between congestion epochs. */ if (cubic_data->epoch_ack_count > 0 && @@ -343,7 +369,6 @@ cubic_post_recovery(struct cc_var *ccv) cubic_data->epoch_ack_count = 0; cubic_data->sum_rtt_ticks = 0; - cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, t_maxseg)); } /* Modified: head/sys/netinet/cc/cc_cubic.h ============================================================================== --- head/sys/netinet/cc/cc_cubic.h Mon Mar 26 19:53:02 2018 (r331566) +++ head/sys/netinet/cc/cc_cubic.h Mon Mar 26 19:53:36 2018 (r331567) @@ -41,6 +41,8 @@ #ifndef _NETINET_CC_CUBIC_H_ #define _NETINET_CC_CUBIC_H_ +#include + /* Number of bits of precision for fixed point math calcs. */ #define CUBIC_SHIFT 8 @@ -162,8 +164,6 @@ cubic_k(unsigned long wmax_pkts) /* * Compute the new cwnd value using an implementation of eqn 1 from the I-D. * Thanks to Kip Macy for help debugging this function. - * - * XXXLAS: Characterise bounds for overflow. */ static __inline unsigned long cubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss, int64_t K) @@ -175,6 +175,15 @@ cubic_cwnd(int ticks_since_cong, unsigned long wmax, u /* t - K, with CUBIC_SHIFT worth of precision. */ cwnd = ((int64_t)(ticks_since_cong << CUBIC_SHIFT) - (K * hz)) / hz; + /* moved this calculation up because it cannot overflow or underflow */ + cwnd *= CUBIC_C_FACTOR * smss; + + if (cwnd > 2097151) /* 2^21 cubed is long max */ + return INT_MAX; + + if (cwnd < -2097152) /* -2^21 cubed is long min */ + return smss; + /* (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */ cwnd *= (cwnd * cwnd); @@ -183,8 +192,17 @@ cubic_cwnd(int ticks_since_cong, unsigned long wmax, u * The down shift by CUBIC_SHIFT_4 is because cwnd has 4 lots of * CUBIC_SHIFT included in the value. 3 from the cubing of cwnd above, * and an extra from multiplying through by CUBIC_C_FACTOR. + * + * The original formula was this: + * cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax; + * + * CUBIC_C_FACTOR and smss factors were moved up to an earlier + * calculation to simplify overflow and underflow detection. */ - cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax; + cwnd = (cwnd >> CUBIC_SHIFT_4) + wmax; + + if (cwnd < 0) + return 1; return ((unsigned long)cwnd); }