tcp_congctl.c revision 1.6 1 1.6 rpaulo /* $NetBSD: tcp_congctl.c,v 1.6 2006/10/15 17:45:06 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.6 rpaulo __KERNEL_RCSID(0, "$NetBSD: tcp_congctl.c,v 1.6 2006/10/15 17:45:06 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.6 rpaulo static void tcp_reno_congestion_exp(struct tcpcb *tp);
209 1.1 rpaulo
210 1.1 rpaulo static int tcp_newreno_fast_retransmit(struct tcpcb *, struct tcphdr *);
211 1.1 rpaulo static void tcp_newreno_fast_retransmit_newack(struct tcpcb *,
212 1.1 rpaulo struct tcphdr *);
213 1.1 rpaulo static void tcp_newreno_newack(struct tcpcb *, struct tcphdr *);
214 1.1 rpaulo
215 1.1 rpaulo
216 1.1 rpaulo static void tcp_congctl_fillnames(void);
217 1.1 rpaulo
218 1.1 rpaulo extern int tcprexmtthresh;
219 1.1 rpaulo
220 1.1 rpaulo MALLOC_DEFINE(M_TCPCONGCTL, "tcpcongctl", "TCP congestion control structures");
221 1.1 rpaulo
222 1.1 rpaulo /*
223 1.1 rpaulo * Used to list the available congestion control algorithms.
224 1.1 rpaulo */
225 1.1 rpaulo struct tcp_congctlent {
226 1.1 rpaulo TAILQ_ENTRY(tcp_congctlent) congctl_ent;
227 1.1 rpaulo char congctl_name[TCPCC_MAXLEN];
228 1.1 rpaulo struct tcp_congctl *congctl_ctl;
229 1.1 rpaulo };
230 1.1 rpaulo TAILQ_HEAD(, tcp_congctlent) tcp_congctlhd;
231 1.1 rpaulo
232 1.1 rpaulo struct simplelock tcp_congctl_slock;
233 1.1 rpaulo
234 1.1 rpaulo void
235 1.1 rpaulo tcp_congctl_init(void)
236 1.1 rpaulo {
237 1.1 rpaulo int r;
238 1.1 rpaulo
239 1.1 rpaulo TAILQ_INIT(&tcp_congctlhd);
240 1.1 rpaulo simple_lock_init(&tcp_congctl_slock);
241 1.1 rpaulo
242 1.1 rpaulo /* Base algorithms. */
243 1.1 rpaulo r = tcp_congctl_register("reno", &tcp_reno_ctl);
244 1.1 rpaulo KASSERT(r == 0);
245 1.1 rpaulo r = tcp_congctl_register("newreno", &tcp_newreno_ctl);
246 1.1 rpaulo KASSERT(r == 0);
247 1.1 rpaulo
248 1.1 rpaulo /* NewReno is the default. */
249 1.1 rpaulo #ifndef TCP_CONGCTL_DEFAULT
250 1.1 rpaulo #define TCP_CONGCTL_DEFAULT "newreno"
251 1.1 rpaulo #endif
252 1.1 rpaulo
253 1.1 rpaulo r = tcp_congctl_select(NULL, TCP_CONGCTL_DEFAULT);
254 1.1 rpaulo KASSERT(r == 0);
255 1.1 rpaulo }
256 1.1 rpaulo
257 1.1 rpaulo /*
258 1.1 rpaulo * Register a congestion algorithm and select it if we have none.
259 1.1 rpaulo */
260 1.1 rpaulo int
261 1.1 rpaulo tcp_congctl_register(const char *name, struct tcp_congctl *tcc)
262 1.1 rpaulo {
263 1.1 rpaulo struct tcp_congctlent *ntcc, *tccp;
264 1.1 rpaulo
265 1.1 rpaulo TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
266 1.1 rpaulo if (!strcmp(name, tccp->congctl_name)) {
267 1.1 rpaulo /* name already registered */
268 1.1 rpaulo return EEXIST;
269 1.1 rpaulo }
270 1.1 rpaulo
271 1.1 rpaulo ntcc = malloc(sizeof(*ntcc), M_TCPCONGCTL, M_WAITOK);
272 1.1 rpaulo
273 1.1 rpaulo strlcpy(ntcc->congctl_name, name, sizeof(ntcc->congctl_name) - 1);
274 1.1 rpaulo ntcc->congctl_ctl = tcc;
275 1.1 rpaulo
276 1.1 rpaulo TAILQ_INSERT_TAIL(&tcp_congctlhd, ntcc, congctl_ent);
277 1.1 rpaulo tcp_congctl_fillnames();
278 1.1 rpaulo
279 1.1 rpaulo if (TAILQ_FIRST(&tcp_congctlhd) == ntcc)
280 1.1 rpaulo tcp_congctl_select(NULL, name);
281 1.1 rpaulo
282 1.1 rpaulo return 0;
283 1.1 rpaulo }
284 1.1 rpaulo
285 1.1 rpaulo int
286 1.1 rpaulo tcp_congctl_unregister(const char *name)
287 1.1 rpaulo {
288 1.1 rpaulo struct tcp_congctlent *tccp, *rtccp;
289 1.1 rpaulo unsigned int size;
290 1.1 rpaulo
291 1.1 rpaulo rtccp = NULL;
292 1.1 rpaulo size = 0;
293 1.1 rpaulo TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent) {
294 1.1 rpaulo if (!strcmp(name, tccp->congctl_name))
295 1.1 rpaulo rtccp = tccp;
296 1.1 rpaulo size++;
297 1.1 rpaulo }
298 1.1 rpaulo
299 1.1 rpaulo if (!rtccp)
300 1.1 rpaulo return ENOENT;
301 1.1 rpaulo
302 1.1 rpaulo if (size <= 1 || tcp_congctl_global == rtccp->congctl_ctl ||
303 1.1 rpaulo rtccp->congctl_ctl->refcnt)
304 1.1 rpaulo return EBUSY;
305 1.1 rpaulo
306 1.1 rpaulo TAILQ_REMOVE(&tcp_congctlhd, rtccp, congctl_ent);
307 1.1 rpaulo free(rtccp, M_TCPCONGCTL);
308 1.1 rpaulo tcp_congctl_fillnames();
309 1.1 rpaulo
310 1.1 rpaulo return 0;
311 1.1 rpaulo }
312 1.1 rpaulo
313 1.1 rpaulo /*
314 1.1 rpaulo * Select a congestion algorithm by name.
315 1.1 rpaulo */
316 1.1 rpaulo int
317 1.1 rpaulo tcp_congctl_select(struct tcpcb *tp, const char *name)
318 1.1 rpaulo {
319 1.1 rpaulo struct tcp_congctlent *tccp;
320 1.1 rpaulo
321 1.1 rpaulo KASSERT(name);
322 1.1 rpaulo
323 1.1 rpaulo TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
324 1.1 rpaulo if (!strcmp(name, tccp->congctl_name)) {
325 1.1 rpaulo if (tp) {
326 1.1 rpaulo simple_lock(&tcp_congctl_slock);
327 1.1 rpaulo tp->t_congctl->refcnt--;
328 1.1 rpaulo tp->t_congctl = tccp->congctl_ctl;
329 1.1 rpaulo tp->t_congctl->refcnt++;
330 1.1 rpaulo simple_unlock(&tcp_congctl_slock);
331 1.1 rpaulo } else {
332 1.1 rpaulo tcp_congctl_global = tccp->congctl_ctl;
333 1.1 rpaulo strlcpy(tcp_congctl_global_name,
334 1.1 rpaulo tccp->congctl_name,
335 1.1 rpaulo sizeof(tcp_congctl_global_name) - 1);
336 1.1 rpaulo }
337 1.1 rpaulo return 0;
338 1.1 rpaulo }
339 1.1 rpaulo
340 1.1 rpaulo return EINVAL;
341 1.1 rpaulo }
342 1.1 rpaulo
343 1.1 rpaulo /*
344 1.1 rpaulo * Returns the name of a congestion algorithm.
345 1.1 rpaulo */
346 1.1 rpaulo const char *
347 1.1 rpaulo tcp_congctl_bystruct(const struct tcp_congctl *tcc)
348 1.1 rpaulo {
349 1.1 rpaulo struct tcp_congctlent *tccp;
350 1.1 rpaulo
351 1.1 rpaulo KASSERT(tcc);
352 1.1 rpaulo
353 1.1 rpaulo TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent)
354 1.1 rpaulo if (tccp->congctl_ctl == tcc)
355 1.1 rpaulo return tccp->congctl_name;
356 1.1 rpaulo
357 1.1 rpaulo return NULL;
358 1.1 rpaulo }
359 1.1 rpaulo
360 1.1 rpaulo static void
361 1.1 rpaulo tcp_congctl_fillnames(void)
362 1.1 rpaulo {
363 1.1 rpaulo struct tcp_congctlent *tccp;
364 1.1 rpaulo const char *delim = " ";
365 1.1 rpaulo
366 1.1 rpaulo tcp_congctl_avail[0] = '\0';
367 1.1 rpaulo TAILQ_FOREACH(tccp, &tcp_congctlhd, congctl_ent) {
368 1.1 rpaulo strlcat(tcp_congctl_avail, tccp->congctl_name,
369 1.1 rpaulo sizeof(tcp_congctl_avail) - 1);
370 1.1 rpaulo if (TAILQ_NEXT(tccp, congctl_ent))
371 1.1 rpaulo strlcat(tcp_congctl_avail, delim,
372 1.1 rpaulo sizeof(tcp_congctl_avail) - 1);
373 1.1 rpaulo }
374 1.1 rpaulo
375 1.1 rpaulo }
376 1.1 rpaulo
377 1.1 rpaulo /* ------------------------------------------------------------------------ */
378 1.1 rpaulo
379 1.6 rpaulo /*
380 1.6 rpaulo * TCP/Reno congestion control.
381 1.6 rpaulo */
382 1.6 rpaulo static void
383 1.1 rpaulo tcp_reno_congestion_exp(struct tcpcb *tp)
384 1.1 rpaulo {
385 1.1 rpaulo u_int win;
386 1.1 rpaulo
387 1.1 rpaulo /*
388 1.1 rpaulo * Halve the congestion window and reduce the
389 1.1 rpaulo * slow start threshold.
390 1.1 rpaulo */
391 1.1 rpaulo win = min(tp->snd_wnd, tp->snd_cwnd) / 2 / tp->t_segsz;
392 1.1 rpaulo if (win < 2)
393 1.1 rpaulo win = 2;
394 1.1 rpaulo
395 1.1 rpaulo tp->snd_ssthresh = win * tp->t_segsz;
396 1.1 rpaulo tp->snd_recover = tp->snd_max;
397 1.1 rpaulo tp->snd_cwnd = tp->snd_ssthresh;
398 1.1 rpaulo
399 1.1 rpaulo if (TCP_ECN_ALLOWED(tp))
400 1.1 rpaulo tp->t_flags |= TF_ECN_SND_CWR;
401 1.1 rpaulo }
402 1.1 rpaulo
403 1.1 rpaulo
404 1.6 rpaulo
405 1.1 rpaulo static int
406 1.1 rpaulo tcp_reno_fast_retransmit(struct tcpcb *tp, struct tcphdr *th)
407 1.1 rpaulo {
408 1.1 rpaulo tcp_seq onxt;
409 1.1 rpaulo
410 1.1 rpaulo onxt = tp->snd_nxt;
411 1.1 rpaulo tcp_reno_congestion_exp(tp);
412 1.1 rpaulo tp->t_partialacks = 0;
413 1.1 rpaulo TCP_TIMER_DISARM(tp, TCPT_REXMT);
414 1.1 rpaulo tp->t_rtttime = 0;
415 1.1 rpaulo if (TCP_SACK_ENABLED(tp)) {
416 1.1 rpaulo tp->t_dupacks = tcprexmtthresh;
417 1.1 rpaulo tp->sack_newdata = tp->snd_nxt;
418 1.1 rpaulo tp->snd_cwnd = tp->t_segsz;
419 1.1 rpaulo (void) tcp_output(tp);
420 1.1 rpaulo return 0;
421 1.1 rpaulo }
422 1.1 rpaulo tp->snd_nxt = th->th_ack;
423 1.1 rpaulo tp->snd_cwnd = tp->t_segsz;
424 1.1 rpaulo (void) tcp_output(tp);
425 1.1 rpaulo tp->snd_cwnd = tp->snd_ssthresh + tp->t_segsz * tp->t_dupacks;
426 1.1 rpaulo if (SEQ_GT(onxt, tp->snd_nxt))
427 1.1 rpaulo tp->snd_nxt = onxt;
428 1.1 rpaulo
429 1.1 rpaulo return 0;
430 1.1 rpaulo }
431 1.1 rpaulo
432 1.1 rpaulo static void
433 1.1 rpaulo tcp_reno_slow_retransmit(struct tcpcb *tp)
434 1.1 rpaulo {
435 1.1 rpaulo u_int win;
436 1.1 rpaulo
437 1.1 rpaulo /*
438 1.1 rpaulo * Close the congestion window down to one segment
439 1.1 rpaulo * (we'll open it by one segment for each ack we get).
440 1.1 rpaulo * Since we probably have a window's worth of unacked
441 1.1 rpaulo * data accumulated, this "slow start" keeps us from
442 1.1 rpaulo * dumping all that data as back-to-back packets (which
443 1.1 rpaulo * might overwhelm an intermediate gateway).
444 1.1 rpaulo *
445 1.1 rpaulo * There are two phases to the opening: Initially we
446 1.1 rpaulo * open by one mss on each ack. This makes the window
447 1.1 rpaulo * size increase exponentially with time. If the
448 1.1 rpaulo * window is larger than the path can handle, this
449 1.1 rpaulo * exponential growth results in dropped packet(s)
450 1.1 rpaulo * almost immediately. To get more time between
451 1.1 rpaulo * drops but still "push" the network to take advantage
452 1.1 rpaulo * of improving conditions, we switch from exponential
453 1.1 rpaulo * to linear window opening at some threshhold size.
454 1.1 rpaulo * For a threshhold, we use half the current window
455 1.1 rpaulo * size, truncated to a multiple of the mss.
456 1.1 rpaulo *
457 1.1 rpaulo * (the minimum cwnd that will give us exponential
458 1.1 rpaulo * growth is 2 mss. We don't allow the threshhold
459 1.1 rpaulo * to go below this.)
460 1.1 rpaulo */
461 1.1 rpaulo
462 1.1 rpaulo win = min(tp->snd_wnd, tp->snd_cwnd) / 2 / tp->t_segsz;
463 1.1 rpaulo if (win < 2)
464 1.1 rpaulo win = 2;
465 1.1 rpaulo /* Loss Window MUST be one segment. */
466 1.1 rpaulo tp->snd_cwnd = tp->t_segsz;
467 1.1 rpaulo tp->snd_ssthresh = win * tp->t_segsz;
468 1.1 rpaulo tp->t_partialacks = -1;
469 1.1 rpaulo tp->t_dupacks = 0;
470 1.1 rpaulo }
471 1.1 rpaulo
472 1.1 rpaulo static void
473 1.5 christos tcp_reno_fast_retransmit_newack(struct tcpcb *tp, struct tcphdr *th __unused)
474 1.1 rpaulo {
475 1.1 rpaulo if (tp->t_partialacks < 0) {
476 1.1 rpaulo /*
477 1.1 rpaulo * We were not in fast recovery. Reset the duplicate ack
478 1.1 rpaulo * counter.
479 1.1 rpaulo */
480 1.1 rpaulo tp->t_dupacks = 0;
481 1.1 rpaulo } else {
482 1.1 rpaulo /*
483 1.1 rpaulo * Clamp the congestion window to the crossover point and
484 1.1 rpaulo * exit fast recovery.
485 1.1 rpaulo */
486 1.1 rpaulo if (tp->snd_cwnd > tp->snd_ssthresh)
487 1.1 rpaulo tp->snd_cwnd = tp->snd_ssthresh;
488 1.1 rpaulo tp->t_partialacks = -1;
489 1.1 rpaulo tp->t_dupacks = 0;
490 1.1 rpaulo }
491 1.1 rpaulo }
492 1.1 rpaulo
493 1.1 rpaulo static void
494 1.5 christos tcp_reno_newack(struct tcpcb *tp, struct tcphdr *th __unused)
495 1.1 rpaulo {
496 1.1 rpaulo /*
497 1.1 rpaulo * When new data is acked, open the congestion window.
498 1.1 rpaulo * If the window gives us less than ssthresh packets
499 1.1 rpaulo * in flight, open exponentially (segsz per packet).
500 1.1 rpaulo * Otherwise open linearly: segsz per window
501 1.3 yamt * (segsz^2 / cwnd per packet).
502 1.1 rpaulo */
503 1.4 rpaulo
504 1.4 rpaulo u_int cw = tp->snd_cwnd;
505 1.4 rpaulo u_int incr = tp->t_segsz;
506 1.4 rpaulo
507 1.4 rpaulo if (cw >= tp->snd_ssthresh)
508 1.1 rpaulo incr = incr * incr / cw;
509 1.4 rpaulo
510 1.4 rpaulo tp->snd_cwnd = min(cw + incr, TCP_MAXWIN << tp->snd_scale);
511 1.1 rpaulo }
512 1.1 rpaulo
513 1.1 rpaulo struct tcp_congctl tcp_reno_ctl = {
514 1.1 rpaulo .fast_retransmit = tcp_reno_fast_retransmit,
515 1.1 rpaulo .slow_retransmit = tcp_reno_slow_retransmit,
516 1.1 rpaulo .fast_retransmit_newack = tcp_reno_fast_retransmit_newack,
517 1.1 rpaulo .newack = tcp_reno_newack,
518 1.6 rpaulo .cong_exp = tcp_reno_congestion_exp,
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 /*
614 1.4 rpaulo * If we are still in fast recovery (meaning we are using
615 1.4 rpaulo * NewReno and we have only received partial acks), do not
616 1.4 rpaulo * inflate the window yet.
617 1.1 rpaulo */
618 1.4 rpaulo if (tp->t_partialacks < 0)
619 1.4 rpaulo tcp_reno_newack(tp, th);
620 1.1 rpaulo }
621 1.1 rpaulo
622 1.1 rpaulo
623 1.1 rpaulo struct tcp_congctl tcp_newreno_ctl = {
624 1.1 rpaulo .fast_retransmit = tcp_newreno_fast_retransmit,
625 1.1 rpaulo .slow_retransmit = tcp_reno_slow_retransmit,
626 1.1 rpaulo .fast_retransmit_newack = tcp_newreno_fast_retransmit_newack,
627 1.1 rpaulo .newack = tcp_newreno_newack,
628 1.6 rpaulo .cong_exp = tcp_reno_congestion_exp,
629 1.1 rpaulo };
630 1.1 rpaulo
631 1.1 rpaulo
632