Home | History | Annotate | Line # | Download | only in netinet
tcp_congctl.c revision 1.1
      1  1.1  rpaulo /*	$NetBSD: tcp_congctl.c,v 1.1 2006/10/09 16:27:07 rpaulo Exp $	*/
      2  1.1  rpaulo 
      3  1.1  rpaulo /*-
      4  1.1  rpaulo  * Copyright (c) 1997, 1998, 1999, 2001, 2005, 2006 The NetBSD Foundation, Inc.
      5  1.1  rpaulo  * All rights reserved.
      6  1.1  rpaulo  *
      7  1.1  rpaulo  * This code is derived from software contributed to The NetBSD Foundation
      8  1.1  rpaulo  * by Jason R. Thorpe and Kevin M. Lahey of the Numerical Aerospace Simulation
      9  1.1  rpaulo  * Facility, NASA Ames Research Center.
     10  1.1  rpaulo  * This code is derived from software contributed to The NetBSD Foundation
     11  1.1  rpaulo  * by Charles M. Hannum.
     12  1.1  rpaulo  * This code is derived from software contributed to The NetBSD Foundation
     13  1.1  rpaulo  * by Rui Paulo.
     14  1.1  rpaulo  *
     15  1.1  rpaulo  * Redistribution and use in source and binary forms, with or without
     16  1.1  rpaulo  * modification, are permitted provided that the following conditions
     17  1.1  rpaulo  * are met:
     18  1.1  rpaulo  * 1. Redistributions of source code must retain the above copyright
     19  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer.
     20  1.1  rpaulo  * 2. Redistributions in binary form must reproduce the above copyright
     21  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer in the
     22  1.1  rpaulo  *    documentation and/or other materials provided with the distribution.
     23  1.1  rpaulo  * 3. All advertising materials mentioning features or use of this software
     24  1.1  rpaulo  *    must display the following acknowledgement:
     25  1.1  rpaulo  *	This product includes software developed by the NetBSD
     26  1.1  rpaulo  *	Foundation, Inc. and its contributors.
     27  1.1  rpaulo  * 4. Neither the name of The NetBSD Foundation nor the names of its
     28  1.1  rpaulo  *    contributors may be used to endorse or promote products derived
     29  1.1  rpaulo  *    from this software without specific prior written permission.
     30  1.1  rpaulo  *
     31  1.1  rpaulo  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     32  1.1  rpaulo  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     33  1.1  rpaulo  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     34  1.1  rpaulo  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     35  1.1  rpaulo  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     36  1.1  rpaulo  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     37  1.1  rpaulo  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     38  1.1  rpaulo  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     39  1.1  rpaulo  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     40  1.1  rpaulo  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     41  1.1  rpaulo  * POSSIBILITY OF SUCH DAMAGE.
     42  1.1  rpaulo  */
     43  1.1  rpaulo 
     44  1.1  rpaulo /*
     45  1.1  rpaulo  * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
     46  1.1  rpaulo  * All rights reserved.
     47  1.1  rpaulo  *
     48  1.1  rpaulo  * Redistribution and use in source and binary forms, with or without
     49  1.1  rpaulo  * modification, are permitted provided that the following conditions
     50  1.1  rpaulo  * are met:
     51  1.1  rpaulo  * 1. Redistributions of source code must retain the above copyright
     52  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer.
     53  1.1  rpaulo  * 2. Redistributions in binary form must reproduce the above copyright
     54  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer in the
     55  1.1  rpaulo  *    documentation and/or other materials provided with the distribution.
     56  1.1  rpaulo  * 3. Neither the name of the project nor the names of its contributors
     57  1.1  rpaulo  *    may be used to endorse or promote products derived from this software
     58  1.1  rpaulo  *    without specific prior written permission.
     59  1.1  rpaulo  *
     60  1.1  rpaulo  * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
     61  1.1  rpaulo  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     62  1.1  rpaulo  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     63  1.1  rpaulo  * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
     64  1.1  rpaulo  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     65  1.1  rpaulo  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     66  1.1  rpaulo  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     67  1.1  rpaulo  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     68  1.1  rpaulo  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     69  1.1  rpaulo  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     70  1.1  rpaulo  * SUCH DAMAGE.
     71  1.1  rpaulo  */
     72  1.1  rpaulo 
     73  1.1  rpaulo /*
     74  1.1  rpaulo  *      @(#)COPYRIGHT   1.1 (NRL) 17 January 1995
     75  1.1  rpaulo  *
     76  1.1  rpaulo  * NRL grants permission for redistribution and use in source and binary
     77  1.1  rpaulo  * forms, with or without modification, of the software and documentation
     78  1.1  rpaulo  * created at NRL provided that the following conditions are met:
     79  1.1  rpaulo  *
     80  1.1  rpaulo  * 1. Redistributions of source code must retain the above copyright
     81  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer.
     82  1.1  rpaulo  * 2. Redistributions in binary form must reproduce the above copyright
     83  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer in the
     84  1.1  rpaulo  *    documentation and/or other materials provided with the distribution.
     85  1.1  rpaulo  * 3. All advertising materials mentioning features or use of this software
     86  1.1  rpaulo  *    must display the following acknowledgements:
     87  1.1  rpaulo  *      This product includes software developed by the University of
     88  1.1  rpaulo  *      California, Berkeley and its contributors.
     89  1.1  rpaulo  *      This product includes software developed at the Information
     90  1.1  rpaulo  *      Technology Division, US Naval Research Laboratory.
     91  1.1  rpaulo  * 4. Neither the name of the NRL nor the names of its contributors
     92  1.1  rpaulo  *    may be used to endorse or promote products derived from this software
     93  1.1  rpaulo  *    without specific prior written permission.
     94  1.1  rpaulo  *
     95  1.1  rpaulo  * THE SOFTWARE PROVIDED BY NRL IS PROVIDED BY NRL AND CONTRIBUTORS ``AS
     96  1.1  rpaulo  * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     97  1.1  rpaulo  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
     98  1.1  rpaulo  * PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL NRL OR
     99  1.1  rpaulo  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    100  1.1  rpaulo  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    101  1.1  rpaulo  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    102  1.1  rpaulo  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    103  1.1  rpaulo  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    104  1.1  rpaulo  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    105  1.1  rpaulo  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    106  1.1  rpaulo  *
    107  1.1  rpaulo  * The views and conclusions contained in the software and documentation
    108  1.1  rpaulo  * are those of the authors and should not be interpreted as representing
    109  1.1  rpaulo  * official policies, either expressed or implied, of the US Naval
    110  1.1  rpaulo  * Research Laboratory (NRL).
    111  1.1  rpaulo  */
    112  1.1  rpaulo 
    113  1.1  rpaulo /*
    114  1.1  rpaulo  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
    115  1.1  rpaulo  *	The Regents of the University of California.  All rights reserved.
    116  1.1  rpaulo  *
    117  1.1  rpaulo  * Redistribution and use in source and binary forms, with or without
    118  1.1  rpaulo  * modification, are permitted provided that the following conditions
    119  1.1  rpaulo  * are met:
    120  1.1  rpaulo  * 1. Redistributions of source code must retain the above copyright
    121  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer.
    122  1.1  rpaulo  * 2. Redistributions in binary form must reproduce the above copyright
    123  1.1  rpaulo  *    notice, this list of conditions and the following disclaimer in the
    124  1.1  rpaulo  *    documentation and/or other materials provided with the distribution.
    125  1.1  rpaulo  * 3. Neither the name of the University nor the names of its contributors
    126  1.1  rpaulo  *    may be used to endorse or promote products derived from this software
    127  1.1  rpaulo  *    without specific prior written permission.
    128  1.1  rpaulo  *
    129  1.1  rpaulo  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
    130  1.1  rpaulo  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    131  1.1  rpaulo  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    132  1.1  rpaulo  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
    133  1.1  rpaulo  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
    134  1.1  rpaulo  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
    135  1.1  rpaulo  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    136  1.1  rpaulo  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    137  1.1  rpaulo  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
    138  1.1  rpaulo  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    139  1.1  rpaulo  * SUCH DAMAGE.
    140  1.1  rpaulo  *
    141  1.1  rpaulo  *	@(#)tcp_input.c	8.12 (Berkeley) 5/24/95
    142  1.1  rpaulo  */
    143  1.1  rpaulo 
    144  1.1  rpaulo #include <sys/cdefs.h>
    145  1.1  rpaulo __KERNEL_RCSID(0, "$NetBSD: tcp_congctl.c,v 1.1 2006/10/09 16:27:07 rpaulo Exp $");
    146  1.1  rpaulo 
    147  1.1  rpaulo #include "opt_inet.h"
    148  1.1  rpaulo #include "opt_tcp_debug.h"
    149  1.1  rpaulo #include "opt_tcp_congctl.h"
    150  1.1  rpaulo 
    151  1.1  rpaulo #include <sys/param.h>
    152  1.1  rpaulo #include <sys/systm.h>
    153  1.1  rpaulo #include <sys/malloc.h>
    154  1.1  rpaulo #include <sys/mbuf.h>
    155  1.1  rpaulo #include <sys/protosw.h>
    156  1.1  rpaulo #include <sys/socket.h>
    157  1.1  rpaulo #include <sys/socketvar.h>
    158  1.1  rpaulo #include <sys/errno.h>
    159  1.1  rpaulo #include <sys/syslog.h>
    160  1.1  rpaulo #include <sys/pool.h>
    161  1.1  rpaulo #include <sys/domain.h>
    162  1.1  rpaulo #include <sys/kernel.h>
    163  1.1  rpaulo #include <sys/lock.h>
    164  1.1  rpaulo 
    165  1.1  rpaulo #include <net/if.h>
    166  1.1  rpaulo #include <net/route.h>
    167  1.1  rpaulo 
    168  1.1  rpaulo #include <netinet/in.h>
    169  1.1  rpaulo #include <netinet/in_systm.h>
    170  1.1  rpaulo #include <netinet/ip.h>
    171  1.1  rpaulo #include <netinet/in_pcb.h>
    172  1.1  rpaulo #include <netinet/in_var.h>
    173  1.1  rpaulo #include <netinet/ip_var.h>
    174  1.1  rpaulo 
    175  1.1  rpaulo #ifdef INET6
    176  1.1  rpaulo #ifndef INET
    177  1.1  rpaulo #include <netinet/in.h>
    178  1.1  rpaulo #endif
    179  1.1  rpaulo #include <netinet/ip6.h>
    180  1.1  rpaulo #include <netinet6/ip6_var.h>
    181  1.1  rpaulo #include <netinet6/in6_pcb.h>
    182  1.1  rpaulo #include <netinet6/ip6_var.h>
    183  1.1  rpaulo #include <netinet6/in6_var.h>
    184  1.1  rpaulo #include <netinet/icmp6.h>
    185  1.1  rpaulo #include <netinet6/nd6.h>
    186  1.1  rpaulo #endif
    187  1.1  rpaulo 
    188  1.1  rpaulo #include <netinet/tcp.h>
    189  1.1  rpaulo #include <netinet/tcp_fsm.h>
    190  1.1  rpaulo #include <netinet/tcp_seq.h>
    191  1.1  rpaulo #include <netinet/tcp_timer.h>
    192  1.1  rpaulo #include <netinet/tcp_var.h>
    193  1.1  rpaulo #include <netinet/tcpip.h>
    194  1.1  rpaulo #include <netinet/tcp_congctl.h>
    195  1.1  rpaulo #ifdef TCP_DEBUG
    196  1.1  rpaulo #include <netinet/tcp_debug.h>
    197  1.1  rpaulo #endif
    198  1.1  rpaulo 
    199  1.1  rpaulo /*
    200  1.1  rpaulo  * TODO:
    201  1.1  rpaulo  *   consider separating the actual implementations in another file.
    202  1.1  rpaulo  */
    203  1.1  rpaulo 
    204  1.1  rpaulo static int  tcp_reno_fast_retransmit(struct tcpcb *, struct tcphdr *);
    205  1.1  rpaulo static void tcp_reno_slow_retransmit(struct tcpcb *);
    206  1.1  rpaulo static void tcp_reno_fast_retransmit_newack(struct tcpcb *, struct tcphdr *);
    207  1.1  rpaulo static void tcp_reno_newack(struct tcpcb *, struct tcphdr *);
    208  1.1  rpaulo 
    209  1.1  rpaulo static int  tcp_newreno_fast_retransmit(struct tcpcb *, struct tcphdr *);
    210  1.1  rpaulo static void tcp_newreno_fast_retransmit_newack(struct tcpcb *,
    211  1.1  rpaulo 	struct tcphdr *);
    212  1.1  rpaulo static void tcp_newreno_newack(struct tcpcb *, struct tcphdr *);
    213  1.1  rpaulo 
    214  1.1  rpaulo 
    215  1.1  rpaulo static void tcp_congctl_fillnames(void);
    216  1.1  rpaulo 
    217  1.1  rpaulo extern int tcprexmtthresh;
    218  1.1  rpaulo 
    219  1.1  rpaulo MALLOC_DEFINE(M_TCPCONGCTL, "tcpcongctl", "TCP congestion control structures");
    220  1.1  rpaulo 
    221  1.1  rpaulo /*
    222  1.1  rpaulo  * Used to list the available congestion control algorithms.
    223  1.1  rpaulo  */
    224  1.1  rpaulo struct tcp_congctlent {
    225  1.1  rpaulo 	TAILQ_ENTRY(tcp_congctlent) congctl_ent;
    226  1.1  rpaulo 	char               congctl_name[TCPCC_MAXLEN];
    227  1.1  rpaulo 	struct tcp_congctl *congctl_ctl;
    228  1.1  rpaulo };
    229  1.1  rpaulo TAILQ_HEAD(, tcp_congctlent) tcp_congctlhd;
    230  1.1  rpaulo 
    231  1.1  rpaulo struct simplelock tcp_congctl_slock;
    232  1.1  rpaulo 
    233  1.1  rpaulo void
    234  1.1  rpaulo tcp_congctl_init(void)
    235  1.1  rpaulo {
    236  1.1  rpaulo 	int r;
    237  1.1  rpaulo 
    238  1.1  rpaulo 	TAILQ_INIT(&tcp_congctlhd);
    239  1.1  rpaulo 	simple_lock_init(&tcp_congctl_slock);
    240  1.1  rpaulo 
    241  1.1  rpaulo 	/* Base algorithms. */
    242  1.1  rpaulo 	r = tcp_congctl_register("reno", &tcp_reno_ctl);
    243  1.1  rpaulo 	KASSERT(r == 0);
    244  1.1  rpaulo 	r = tcp_congctl_register("newreno", &tcp_newreno_ctl);
    245  1.1  rpaulo 	KASSERT(r == 0);
    246  1.1  rpaulo 
    247  1.1  rpaulo 	/* NewReno is the default. */
    248  1.1  rpaulo #ifndef TCP_CONGCTL_DEFAULT
    249  1.1  rpaulo #define TCP_CONGCTL_DEFAULT "newreno"
    250  1.1  rpaulo #endif
    251  1.1  rpaulo 
    252  1.1  rpaulo 	r = tcp_congctl_select(NULL, TCP_CONGCTL_DEFAULT);
    253  1.1  rpaulo 	KASSERT(r == 0);
    254  1.1  rpaulo }
    255  1.1  rpaulo 
    256  1.1  rpaulo /*
    257  1.1  rpaulo  * Register a congestion algorithm and select it if we have none.
    258  1.1  rpaulo  */
    259  1.1  rpaulo int
    260  1.1  rpaulo tcp_congctl_register(const char *name, struct tcp_congctl *tcc)
    261  1.1  rpaulo {
    262  1.1  rpaulo 	struct tcp_congctlent *ntcc, *tccp;
    263  1.1  rpaulo 
    264  1.1  rpaulo 	TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
    265  1.1  rpaulo 		if (!strcmp(name, tccp->congctl_name)) {
    266  1.1  rpaulo 			/* name already registered */
    267  1.1  rpaulo 			return EEXIST;
    268  1.1  rpaulo 		}
    269  1.1  rpaulo 
    270  1.1  rpaulo 	ntcc = malloc(sizeof(*ntcc), M_TCPCONGCTL, M_WAITOK);
    271  1.1  rpaulo 
    272  1.1  rpaulo 	strlcpy(ntcc->congctl_name, name, sizeof(ntcc->congctl_name) - 1);
    273  1.1  rpaulo 	ntcc->congctl_ctl = tcc;
    274  1.1  rpaulo 
    275  1.1  rpaulo 	TAILQ_INSERT_TAIL(&tcp_congctlhd, ntcc, congctl_ent);
    276  1.1  rpaulo 	tcp_congctl_fillnames();
    277  1.1  rpaulo 
    278  1.1  rpaulo 	if (TAILQ_FIRST(&tcp_congctlhd) == ntcc)
    279  1.1  rpaulo 		tcp_congctl_select(NULL, name);
    280  1.1  rpaulo 
    281  1.1  rpaulo 	return 0;
    282  1.1  rpaulo }
    283  1.1  rpaulo 
    284  1.1  rpaulo int
    285  1.1  rpaulo tcp_congctl_unregister(const char *name)
    286  1.1  rpaulo {
    287  1.1  rpaulo 	struct tcp_congctlent *tccp, *rtccp;
    288  1.1  rpaulo 	unsigned int size;
    289  1.1  rpaulo 
    290  1.1  rpaulo 	rtccp = NULL;
    291  1.1  rpaulo 	size = 0;
    292  1.1  rpaulo 	TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent) {
    293  1.1  rpaulo 		if (!strcmp(name, tccp->congctl_name))
    294  1.1  rpaulo 			rtccp = tccp;
    295  1.1  rpaulo 		size++;
    296  1.1  rpaulo 	}
    297  1.1  rpaulo 
    298  1.1  rpaulo 	if (!rtccp)
    299  1.1  rpaulo 		return ENOENT;
    300  1.1  rpaulo 
    301  1.1  rpaulo 	if (size <= 1 || tcp_congctl_global == rtccp->congctl_ctl ||
    302  1.1  rpaulo 	    rtccp->congctl_ctl->refcnt)
    303  1.1  rpaulo 		return EBUSY;
    304  1.1  rpaulo 
    305  1.1  rpaulo 	TAILQ_REMOVE(&tcp_congctlhd, rtccp, congctl_ent);
    306  1.1  rpaulo 	free(rtccp, M_TCPCONGCTL);
    307  1.1  rpaulo 	tcp_congctl_fillnames();
    308  1.1  rpaulo 
    309  1.1  rpaulo 	return 0;
    310  1.1  rpaulo }
    311  1.1  rpaulo 
    312  1.1  rpaulo /*
    313  1.1  rpaulo  * Select a congestion algorithm by name.
    314  1.1  rpaulo  */
    315  1.1  rpaulo int
    316  1.1  rpaulo tcp_congctl_select(struct tcpcb *tp, const char *name)
    317  1.1  rpaulo {
    318  1.1  rpaulo 	struct tcp_congctlent *tccp;
    319  1.1  rpaulo 
    320  1.1  rpaulo 	KASSERT(name);
    321  1.1  rpaulo 
    322  1.1  rpaulo 	TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
    323  1.1  rpaulo 		if (!strcmp(name, tccp->congctl_name)) {
    324  1.1  rpaulo 			if (tp) {
    325  1.1  rpaulo 				simple_lock(&tcp_congctl_slock);
    326  1.1  rpaulo 				tp->t_congctl->refcnt--;
    327  1.1  rpaulo 				tp->t_congctl = tccp->congctl_ctl;
    328  1.1  rpaulo 				tp->t_congctl->refcnt++;
    329  1.1  rpaulo 				simple_unlock(&tcp_congctl_slock);
    330  1.1  rpaulo 			} else {
    331  1.1  rpaulo 				tcp_congctl_global = tccp->congctl_ctl;
    332  1.1  rpaulo 				strlcpy(tcp_congctl_global_name,
    333  1.1  rpaulo 				    tccp->congctl_name,
    334  1.1  rpaulo 				    sizeof(tcp_congctl_global_name) - 1);
    335  1.1  rpaulo 			}
    336  1.1  rpaulo 			return 0;
    337  1.1  rpaulo 		}
    338  1.1  rpaulo 
    339  1.1  rpaulo 	return EINVAL;
    340  1.1  rpaulo }
    341  1.1  rpaulo 
    342  1.1  rpaulo /*
    343  1.1  rpaulo  * Returns the name of a congestion algorithm.
    344  1.1  rpaulo  */
    345  1.1  rpaulo const char *
    346  1.1  rpaulo tcp_congctl_bystruct(const struct tcp_congctl *tcc)
    347  1.1  rpaulo {
    348  1.1  rpaulo 	struct tcp_congctlent *tccp;
    349  1.1  rpaulo 
    350  1.1  rpaulo 	KASSERT(tcc);
    351  1.1  rpaulo 
    352  1.1  rpaulo 	TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
    353  1.1  rpaulo 		if (tccp->congctl_ctl == tcc)
    354  1.1  rpaulo 			return tccp->congctl_name;
    355  1.1  rpaulo 
    356  1.1  rpaulo 	return NULL;
    357  1.1  rpaulo }
    358  1.1  rpaulo 
    359  1.1  rpaulo static void
    360  1.1  rpaulo tcp_congctl_fillnames(void)
    361  1.1  rpaulo {
    362  1.1  rpaulo 	struct tcp_congctlent *tccp;
    363  1.1  rpaulo 	const char *delim = " ";
    364  1.1  rpaulo 
    365  1.1  rpaulo 	tcp_congctl_avail[0] = '\0';
    366  1.1  rpaulo 	TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent) {
    367  1.1  rpaulo 		strlcat(tcp_congctl_avail, tccp->congctl_name,
    368  1.1  rpaulo 		    sizeof(tcp_congctl_avail) - 1);
    369  1.1  rpaulo 		if (TAILQ_NEXT(tccp, congctl_ent))
    370  1.1  rpaulo 			strlcat(tcp_congctl_avail, delim,
    371  1.1  rpaulo 			    sizeof(tcp_congctl_avail) - 1);
    372  1.1  rpaulo 	}
    373  1.1  rpaulo 
    374  1.1  rpaulo }
    375  1.1  rpaulo 
    376  1.1  rpaulo /* ------------------------------------------------------------------------ */
    377  1.1  rpaulo 
    378  1.1  rpaulo inline void
    379  1.1  rpaulo tcp_reno_congestion_exp(struct tcpcb *tp)
    380  1.1  rpaulo {
    381  1.1  rpaulo 	u_int win;
    382  1.1  rpaulo 
    383  1.1  rpaulo 	/*
    384  1.1  rpaulo 	 * Halve the congestion window and reduce the
    385  1.1  rpaulo 	 * slow start threshold.
    386  1.1  rpaulo 	 */
    387  1.1  rpaulo 	win = min(tp->snd_wnd, tp->snd_cwnd) / 2 / tp->t_segsz;
    388  1.1  rpaulo 	if (win < 2)
    389  1.1  rpaulo 		win = 2;
    390  1.1  rpaulo 
    391  1.1  rpaulo 	tp->snd_ssthresh = win * tp->t_segsz;
    392  1.1  rpaulo 	tp->snd_recover = tp->snd_max;
    393  1.1  rpaulo 	tp->snd_cwnd = tp->snd_ssthresh;
    394  1.1  rpaulo 
    395  1.1  rpaulo 	if (TCP_ECN_ALLOWED(tp))
    396  1.1  rpaulo 		tp->t_flags |= TF_ECN_SND_CWR;
    397  1.1  rpaulo }
    398  1.1  rpaulo 
    399  1.1  rpaulo 
    400  1.1  rpaulo /*
    401  1.1  rpaulo  * TCP/Reno congestion control.
    402  1.1  rpaulo  */
    403  1.1  rpaulo static int
    404  1.1  rpaulo tcp_reno_fast_retransmit(struct tcpcb *tp, struct tcphdr *th)
    405  1.1  rpaulo {
    406  1.1  rpaulo 	tcp_seq onxt;
    407  1.1  rpaulo 
    408  1.1  rpaulo 	onxt = tp->snd_nxt;
    409  1.1  rpaulo 	tcp_reno_congestion_exp(tp);
    410  1.1  rpaulo 	tp->t_partialacks = 0;
    411  1.1  rpaulo 	TCP_TIMER_DISARM(tp, TCPT_REXMT);
    412  1.1  rpaulo 	tp->t_rtttime = 0;
    413  1.1  rpaulo 	if (TCP_SACK_ENABLED(tp)) {
    414  1.1  rpaulo 		tp->t_dupacks = tcprexmtthresh;
    415  1.1  rpaulo 		tp->sack_newdata = tp->snd_nxt;
    416  1.1  rpaulo 		tp->snd_cwnd = tp->t_segsz;
    417  1.1  rpaulo 		(void) tcp_output(tp);
    418  1.1  rpaulo 		return 0;
    419  1.1  rpaulo 	}
    420  1.1  rpaulo 	tp->snd_nxt = th->th_ack;
    421  1.1  rpaulo 	tp->snd_cwnd = tp->t_segsz;
    422  1.1  rpaulo 	(void) tcp_output(tp);
    423  1.1  rpaulo 	tp->snd_cwnd = tp->snd_ssthresh + tp->t_segsz * tp->t_dupacks;
    424  1.1  rpaulo 	if (SEQ_GT(onxt, tp->snd_nxt))
    425  1.1  rpaulo 		tp->snd_nxt = onxt;
    426  1.1  rpaulo 
    427  1.1  rpaulo 	return 0;
    428  1.1  rpaulo }
    429  1.1  rpaulo 
    430  1.1  rpaulo static void
    431  1.1  rpaulo tcp_reno_slow_retransmit(struct tcpcb *tp)
    432  1.1  rpaulo {
    433  1.1  rpaulo 	u_int win;
    434  1.1  rpaulo 
    435  1.1  rpaulo 	/*
    436  1.1  rpaulo 	 * Close the congestion window down to one segment
    437  1.1  rpaulo 	 * (we'll open it by one segment for each ack we get).
    438  1.1  rpaulo 	 * Since we probably have a window's worth of unacked
    439  1.1  rpaulo 	 * data accumulated, this "slow start" keeps us from
    440  1.1  rpaulo 	 * dumping all that data as back-to-back packets (which
    441  1.1  rpaulo 	 * might overwhelm an intermediate gateway).
    442  1.1  rpaulo 	 *
    443  1.1  rpaulo 	 * There are two phases to the opening: Initially we
    444  1.1  rpaulo 	 * open by one mss on each ack.  This makes the window
    445  1.1  rpaulo 	 * size increase exponentially with time.  If the
    446  1.1  rpaulo 	 * window is larger than the path can handle, this
    447  1.1  rpaulo 	 * exponential growth results in dropped packet(s)
    448  1.1  rpaulo 	 * almost immediately.  To get more time between
    449  1.1  rpaulo 	 * drops but still "push" the network to take advantage
    450  1.1  rpaulo 	 * of improving conditions, we switch from exponential
    451  1.1  rpaulo 	 * to linear window opening at some threshhold size.
    452  1.1  rpaulo 	 * For a threshhold, we use half the current window
    453  1.1  rpaulo 	 * size, truncated to a multiple of the mss.
    454  1.1  rpaulo 	 *
    455  1.1  rpaulo 	 * (the minimum cwnd that will give us exponential
    456  1.1  rpaulo 	 * growth is 2 mss.  We don't allow the threshhold
    457  1.1  rpaulo 	 * to go below this.)
    458  1.1  rpaulo 	 */
    459  1.1  rpaulo 
    460  1.1  rpaulo 	win = min(tp->snd_wnd, tp->snd_cwnd) / 2 / tp->t_segsz;
    461  1.1  rpaulo 	if (win < 2)
    462  1.1  rpaulo 		win = 2;
    463  1.1  rpaulo 	/* Loss Window MUST be one segment. */
    464  1.1  rpaulo 	tp->snd_cwnd = tp->t_segsz;
    465  1.1  rpaulo 	tp->snd_ssthresh = win * tp->t_segsz;
    466  1.1  rpaulo 	tp->t_partialacks = -1;
    467  1.1  rpaulo 	tp->t_dupacks = 0;
    468  1.1  rpaulo }
    469  1.1  rpaulo 
    470  1.1  rpaulo static void
    471  1.1  rpaulo tcp_reno_fast_retransmit_newack(struct tcpcb *tp, struct tcphdr *th)
    472  1.1  rpaulo {
    473  1.1  rpaulo 	if (tp->t_partialacks < 0) {
    474  1.1  rpaulo 		/*
    475  1.1  rpaulo 		 * We were not in fast recovery.  Reset the duplicate ack
    476  1.1  rpaulo 		 * counter.
    477  1.1  rpaulo 		 */
    478  1.1  rpaulo 		tp->t_dupacks = 0;
    479  1.1  rpaulo 	} else {
    480  1.1  rpaulo 		/*
    481  1.1  rpaulo 		 * Clamp the congestion window to the crossover point and
    482  1.1  rpaulo 		 * exit fast recovery.
    483  1.1  rpaulo 		 */
    484  1.1  rpaulo 		if (tp->snd_cwnd > tp->snd_ssthresh)
    485  1.1  rpaulo 			tp->snd_cwnd = tp->snd_ssthresh;
    486  1.1  rpaulo 		tp->t_partialacks = -1;
    487  1.1  rpaulo 		tp->t_dupacks = 0;
    488  1.1  rpaulo 	}
    489  1.1  rpaulo }
    490  1.1  rpaulo 
    491  1.1  rpaulo static void
    492  1.1  rpaulo tcp_reno_newack(struct tcpcb *tp, struct tcphdr *th)
    493  1.1  rpaulo {
    494  1.1  rpaulo 	u_int cw;
    495  1.1  rpaulo 	u_int incr;
    496  1.1  rpaulo 
    497  1.1  rpaulo 	/*
    498  1.1  rpaulo 	 * When new data is acked, open the congestion window.
    499  1.1  rpaulo 	 * If the window gives us less than ssthresh packets
    500  1.1  rpaulo 	 * in flight, open exponentially (segsz per packet).
    501  1.1  rpaulo 	 * Otherwise open linearly: segsz per window
    502  1.1  rpaulo 	 * (segsz^2 / cwnd per packet), plus a constant
    503  1.1  rpaulo 	 * fraction of a packet (segsz/8) to help larger windows
    504  1.1  rpaulo 	 * open quickly enough.
    505  1.1  rpaulo 	 */
    506  1.1  rpaulo 	cw = tp->snd_cwnd;
    507  1.1  rpaulo 	incr = tp->t_segsz;
    508  1.1  rpaulo 	if (cw > tp->snd_ssthresh)
    509  1.1  rpaulo 		incr = incr * incr / cw;
    510  1.1  rpaulo 	if (SEQ_GEQ(th->th_ack, tp->snd_recover))
    511  1.1  rpaulo 		tp->snd_cwnd = min(cw + incr, TCP_MAXWIN << tp->snd_scale);
    512  1.1  rpaulo }
    513  1.1  rpaulo 
    514  1.1  rpaulo struct tcp_congctl tcp_reno_ctl = {
    515  1.1  rpaulo 	.fast_retransmit = tcp_reno_fast_retransmit,
    516  1.1  rpaulo 	.slow_retransmit = tcp_reno_slow_retransmit,
    517  1.1  rpaulo 	.fast_retransmit_newack = tcp_reno_fast_retransmit_newack,
    518  1.1  rpaulo 	.newack = tcp_reno_newack,
    519  1.1  rpaulo };
    520  1.1  rpaulo 
    521  1.1  rpaulo /*
    522  1.1  rpaulo  * TCP/NewReno Congestion control.
    523  1.1  rpaulo  */
    524  1.1  rpaulo static int
    525  1.1  rpaulo tcp_newreno_fast_retransmit(struct tcpcb *tp, struct tcphdr *th)
    526  1.1  rpaulo {
    527  1.1  rpaulo 	if (SEQ_LT(th->th_ack, tp->snd_high)) {
    528  1.1  rpaulo 		/*
    529  1.1  rpaulo 		 * False fast retransmit after timeout.
    530  1.1  rpaulo 		 * Do not enter fast recovery
    531  1.1  rpaulo 		 */
    532  1.1  rpaulo 		tp->t_dupacks = 0;
    533  1.1  rpaulo 		return 1;
    534  1.1  rpaulo 	} else {
    535  1.1  rpaulo 		/*
    536  1.1  rpaulo 		 * Fast retransmit is same as reno.
    537  1.1  rpaulo 		 */
    538  1.1  rpaulo 		return tcp_reno_fast_retransmit(tp, th);
    539  1.1  rpaulo 	}
    540  1.1  rpaulo 
    541  1.1  rpaulo 	return 0;
    542  1.1  rpaulo }
    543  1.1  rpaulo 
    544  1.1  rpaulo /*
    545  1.1  rpaulo  * Implement the NewReno response to a new ack, checking for partial acks in
    546  1.1  rpaulo  * fast recovery.
    547  1.1  rpaulo  */
    548  1.1  rpaulo static void
    549  1.1  rpaulo tcp_newreno_fast_retransmit_newack(struct tcpcb *tp, struct tcphdr *th)
    550  1.1  rpaulo {
    551  1.1  rpaulo 	if (tp->t_partialacks < 0) {
    552  1.1  rpaulo 		/*
    553  1.1  rpaulo 		 * We were not in fast recovery.  Reset the duplicate ack
    554  1.1  rpaulo 		 * counter.
    555  1.1  rpaulo 		 */
    556  1.1  rpaulo 		tp->t_dupacks = 0;
    557  1.1  rpaulo 	} else if (SEQ_LT(th->th_ack, tp->snd_recover)) {
    558  1.1  rpaulo 		/*
    559  1.1  rpaulo 		 * This is a partial ack.  Retransmit the first unacknowledged
    560  1.1  rpaulo 		 * segment and deflate the congestion window by the amount of
    561  1.1  rpaulo 		 * acknowledged data.  Do not exit fast recovery.
    562  1.1  rpaulo 		 */
    563  1.1  rpaulo 		tcp_seq onxt = tp->snd_nxt;
    564  1.1  rpaulo 		u_long ocwnd = tp->snd_cwnd;
    565  1.1  rpaulo 
    566  1.1  rpaulo 		/*
    567  1.1  rpaulo 		 * snd_una has not yet been updated and the socket's send
    568  1.1  rpaulo 		 * buffer has not yet drained off the ACK'd data, so we
    569  1.1  rpaulo 		 * have to leave snd_una as it was to get the correct data
    570  1.1  rpaulo 		 * offset in tcp_output().
    571  1.1  rpaulo 		 */
    572  1.1  rpaulo 		if (++tp->t_partialacks == 1)
    573  1.1  rpaulo 			TCP_TIMER_DISARM(tp, TCPT_REXMT);
    574  1.1  rpaulo 		tp->t_rtttime = 0;
    575  1.1  rpaulo 		tp->snd_nxt = th->th_ack;
    576  1.1  rpaulo 		/*
    577  1.1  rpaulo 		 * Set snd_cwnd to one segment beyond ACK'd offset.  snd_una
    578  1.1  rpaulo 		 * is not yet updated when we're called.
    579  1.1  rpaulo 		 */
    580  1.1  rpaulo 		tp->snd_cwnd = tp->t_segsz + (th->th_ack - tp->snd_una);
    581  1.1  rpaulo 		(void) tcp_output(tp);
    582  1.1  rpaulo 		tp->snd_cwnd = ocwnd;
    583  1.1  rpaulo 		if (SEQ_GT(onxt, tp->snd_nxt))
    584  1.1  rpaulo 			tp->snd_nxt = onxt;
    585  1.1  rpaulo 		/*
    586  1.1  rpaulo 		 * Partial window deflation.  Relies on fact that tp->snd_una
    587  1.1  rpaulo 		 * not updated yet.
    588  1.1  rpaulo 		 */
    589  1.1  rpaulo 		tp->snd_cwnd -= (th->th_ack - tp->snd_una - tp->t_segsz);
    590  1.1  rpaulo 	} else {
    591  1.1  rpaulo 		/*
    592  1.1  rpaulo 		 * Complete ack.  Inflate the congestion window to ssthresh
    593  1.1  rpaulo 		 * and exit fast recovery.
    594  1.1  rpaulo 		 *
    595  1.1  rpaulo 		 * Window inflation should have left us with approx.
    596  1.1  rpaulo 		 * snd_ssthresh outstanding data.  But in case we
    597  1.1  rpaulo 		 * would be inclined to send a burst, better to do
    598  1.1  rpaulo 		 * it via the slow start mechanism.
    599  1.1  rpaulo 		 */
    600  1.1  rpaulo 		if (SEQ_SUB(tp->snd_max, th->th_ack) < tp->snd_ssthresh)
    601  1.1  rpaulo 			tp->snd_cwnd = SEQ_SUB(tp->snd_max, th->th_ack)
    602  1.1  rpaulo 			    + tp->t_segsz;
    603  1.1  rpaulo 		else
    604  1.1  rpaulo 			tp->snd_cwnd = tp->snd_ssthresh;
    605  1.1  rpaulo 		tp->t_partialacks = -1;
    606  1.1  rpaulo 		tp->t_dupacks = 0;
    607  1.1  rpaulo 	}
    608  1.1  rpaulo }
    609  1.1  rpaulo 
    610  1.1  rpaulo static void
    611  1.1  rpaulo tcp_newreno_newack(struct tcpcb *tp, struct tcphdr *th)
    612  1.1  rpaulo {
    613  1.1  rpaulo 	u_int cw;
    614  1.1  rpaulo 	u_int incr;
    615  1.1  rpaulo 
    616  1.1  rpaulo 	/*
    617  1.1  rpaulo 	 * When new data is acked, open the congestion window.
    618  1.1  rpaulo 	 * If the window gives us less than ssthresh packets
    619  1.1  rpaulo 	 * in flight, open exponentially (segsz per packet).
    620  1.1  rpaulo 	 * Otherwise open linearly: segsz per window
    621  1.1  rpaulo 	 * (segsz^2 / cwnd per packet), plus a constant
    622  1.1  rpaulo 	 * fraction of a packet (segsz/8) to help larger windows
    623  1.1  rpaulo 	 * open quickly enough.
    624  1.1  rpaulo 	 */
    625  1.1  rpaulo 	cw = tp->snd_cwnd;
    626  1.1  rpaulo 	incr = tp->t_segsz;
    627  1.1  rpaulo 	if (cw > tp->snd_ssthresh)
    628  1.1  rpaulo 		incr = incr * incr / cw;
    629  1.1  rpaulo }
    630  1.1  rpaulo 
    631  1.1  rpaulo 
    632  1.1  rpaulo struct tcp_congctl tcp_newreno_ctl = {
    633  1.1  rpaulo 	.fast_retransmit = tcp_newreno_fast_retransmit,
    634  1.1  rpaulo 	.slow_retransmit = tcp_reno_slow_retransmit,
    635  1.1  rpaulo 	.fast_retransmit_newack = tcp_newreno_fast_retransmit_newack,
    636  1.1  rpaulo 	.newack = tcp_newreno_newack,
    637  1.1  rpaulo };
    638  1.1  rpaulo 
    639  1.1  rpaulo 
    640