]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - sys/netinet/cc/cc_htcp.c
Merge llvm, clang, lld, lldb, compiler-rt and libc++ r308421, and update
[FreeBSD/FreeBSD.git] / sys / netinet / cc / cc_htcp.c
1 /*-
2  * Copyright (c) 2007-2008
3  *      Swinburne University of Technology, Melbourne, Australia
4  * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
5  * Copyright (c) 2010 The FreeBSD Foundation
6  * All rights reserved.
7  *
8  * This software was developed at the Centre for Advanced Internet
9  * Architectures, Swinburne University of Technology, by Lawrence Stewart and
10  * James Healy, made possible in part by a grant from the Cisco University
11  * Research Program Fund at Community Foundation Silicon Valley.
12  *
13  * Portions of this software were developed at the Centre for Advanced
14  * Internet Architectures, Swinburne University of Technology, Melbourne,
15  * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions
19  * are met:
20  * 1. Redistributions of source code must retain the above copyright
21  *    notice, this list of conditions and the following disclaimer.
22  * 2. Redistributions in binary form must reproduce the above copyright
23  *    notice, this list of conditions and the following disclaimer in the
24  *    documentation and/or other materials provided with the distribution.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36  * SUCH DAMAGE.
37  */
38
39 /*
40  * An implementation of the H-TCP congestion control algorithm for FreeBSD,
41  * based on the Internet Draft "draft-leith-tcp-htcp-06.txt" by Leith and
42  * Shorten. Originally released as part of the NewTCP research project at
43  * Swinburne University of Technology's Centre for Advanced Internet
44  * Architectures, Melbourne, Australia, which was made possible in part by a
45  * grant from the Cisco University Research Program Fund at Community Foundation
46  * Silicon Valley. More details are available at:
47  *   http://caia.swin.edu.au/urp/newtcp/
48  */
49
50 #include <sys/cdefs.h>
51 __FBSDID("$FreeBSD$");
52
53 #include <sys/param.h>
54 #include <sys/kernel.h>
55 #include <sys/limits.h>
56 #include <sys/malloc.h>
57 #include <sys/module.h>
58 #include <sys/socket.h>
59 #include <sys/socketvar.h>
60 #include <sys/sysctl.h>
61 #include <sys/systm.h>
62
63 #include <net/vnet.h>
64
65 #include <netinet/tcp.h>
66 #include <netinet/tcp_seq.h>
67 #include <netinet/tcp_timer.h>
68 #include <netinet/tcp_var.h>
69 #include <netinet/cc/cc.h>
70 #include <netinet/cc/cc_module.h>
71
72 /* Fixed point math shifts. */
73 #define HTCP_SHIFT 8
74 #define HTCP_ALPHA_INC_SHIFT 4
75
76 #define HTCP_INIT_ALPHA 1
77 #define HTCP_DELTA_L hz         /* 1 sec in ticks. */
78 #define HTCP_MINBETA 128        /* 0.5 << HTCP_SHIFT. */
79 #define HTCP_MAXBETA 204        /* ~0.8 << HTCP_SHIFT. */
80 #define HTCP_MINROWE 26         /* ~0.1 << HTCP_SHIFT. */
81 #define HTCP_MAXROWE 512        /* 2 << HTCP_SHIFT. */
82
83 /* RTT_ref (ms) used in the calculation of alpha if RTT scaling is enabled. */
84 #define HTCP_RTT_REF 100
85
86 /* Don't trust SRTT until this many samples have been taken. */
87 #define HTCP_MIN_RTT_SAMPLES 8
88
89 /*
90  * HTCP_CALC_ALPHA performs a fixed point math calculation to determine the
91  * value of alpha, based on the function defined in the HTCP spec.
92  *
93  * i.e. 1 + 10(delta - delta_l) + ((delta - delta_l) / 2) ^ 2
94  *
95  * "diff" is passed in to the macro as "delta - delta_l" and is expected to be
96  * in units of ticks.
97  *
98  * The joyousnous of fixed point maths means our function implementation looks a
99  * little funky...
100  *
101  * In order to maintain some precision in the calculations, a fixed point shift
102  * HTCP_ALPHA_INC_SHIFT is used to ensure the integer divisions don't
103  * truncate the results too badly.
104  *
105  * The "16" value is the "1" term in the alpha function shifted up by
106  * HTCP_ALPHA_INC_SHIFT
107  *
108  * The "160" value is the "10" multiplier in the alpha function multiplied by
109  * 2^HTCP_ALPHA_INC_SHIFT
110  *
111  * Specifying these as constants reduces the computations required. After
112  * up-shifting all the terms in the function and performing the required
113  * calculations, we down-shift the final result by HTCP_ALPHA_INC_SHIFT to
114  * ensure it is back in the correct range.
115  *
116  * The "hz" terms are required as kernels can be configured to run with
117  * different tick timers, which we have to adjust for in the alpha calculation
118  * (which originally was defined in terms of seconds).
119  *
120  * We also have to be careful to constrain the value of diff such that it won't
121  * overflow whilst performing the calculation. The middle term i.e. (160 * diff)
122  * / hz is the limiting factor in the calculation. We must constrain diff to be
123  * less than the max size of an int divided by the constant 160 figure
124  * i.e. diff < INT_MAX / 160
125  *
126  * NB: Changing HTCP_ALPHA_INC_SHIFT will require you to MANUALLY update the
127  * constants used in this function!
128  */
129 #define HTCP_CALC_ALPHA(diff) \
130 ((\
131         (16) + \
132         ((160 * (diff)) / hz) + \
133         (((diff) / hz) * (((diff) << HTCP_ALPHA_INC_SHIFT) / (4 * hz))) \
134 ) >> HTCP_ALPHA_INC_SHIFT)
135
136 static void     htcp_ack_received(struct cc_var *ccv, uint16_t type);
137 static void     htcp_cb_destroy(struct cc_var *ccv);
138 static int      htcp_cb_init(struct cc_var *ccv);
139 static void     htcp_cong_signal(struct cc_var *ccv, uint32_t type);
140 static int      htcp_mod_init(void);
141 static void     htcp_post_recovery(struct cc_var *ccv);
142 static void     htcp_recalc_alpha(struct cc_var *ccv);
143 static void     htcp_recalc_beta(struct cc_var *ccv);
144 static void     htcp_record_rtt(struct cc_var *ccv);
145 static void     htcp_ssthresh_update(struct cc_var *ccv);
146
147 struct htcp {
148         /* cwnd before entering cong recovery. */
149         unsigned long   prev_cwnd;
150         /* cwnd additive increase parameter. */
151         int             alpha;
152         /* cwnd multiplicative decrease parameter. */
153         int             beta;
154         /* Largest rtt seen for the flow. */
155         int             maxrtt;
156         /* Shortest rtt seen for the flow. */
157         int             minrtt;
158         /* Time of last congestion event in ticks. */
159         int             t_last_cong;
160 };
161
162 static int htcp_rtt_ref;
163 /*
164  * The maximum number of ticks the value of diff can reach in
165  * htcp_recalc_alpha() before alpha will stop increasing due to overflow.
166  * See comment above HTCP_CALC_ALPHA for more info.
167  */
168 static int htcp_max_diff = INT_MAX / ((1 << HTCP_ALPHA_INC_SHIFT) * 10);
169
170 /* Per-netstack vars. */
171 static VNET_DEFINE(u_int, htcp_adaptive_backoff) = 0;
172 static VNET_DEFINE(u_int, htcp_rtt_scaling) = 0;
173 #define V_htcp_adaptive_backoff    VNET(htcp_adaptive_backoff)
174 #define V_htcp_rtt_scaling    VNET(htcp_rtt_scaling)
175
176 static MALLOC_DEFINE(M_HTCP, "htcp data",
177     "Per connection data required for the HTCP congestion control algorithm");
178
179 struct cc_algo htcp_cc_algo = {
180         .name = "htcp",
181         .ack_received = htcp_ack_received,
182         .cb_destroy = htcp_cb_destroy,
183         .cb_init = htcp_cb_init,
184         .cong_signal = htcp_cong_signal,
185         .mod_init = htcp_mod_init,
186         .post_recovery = htcp_post_recovery,
187 };
188
189 static void
190 htcp_ack_received(struct cc_var *ccv, uint16_t type)
191 {
192         struct htcp *htcp_data;
193
194         htcp_data = ccv->cc_data;
195         htcp_record_rtt(ccv);
196
197         /*
198          * Regular ACK and we're not in cong/fast recovery and we're cwnd
199          * limited and we're either not doing ABC or are slow starting or are
200          * doing ABC and we've sent a cwnd's worth of bytes.
201          */
202         if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
203             (ccv->flags & CCF_CWND_LIMITED) && (!V_tcp_do_rfc3465 ||
204             CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh) ||
205             (V_tcp_do_rfc3465 && ccv->flags & CCF_ABC_SENTAWND))) {
206                 htcp_recalc_beta(ccv);
207                 htcp_recalc_alpha(ccv);
208                 /*
209                  * Use the logic in NewReno ack_received() for slow start and
210                  * for the first HTCP_DELTA_L ticks after either the flow starts
211                  * or a congestion event (when alpha equals 1).
212                  */
213                 if (htcp_data->alpha == 1 ||
214                     CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh))
215                         newreno_cc_algo.ack_received(ccv, type);
216                 else {
217                         if (V_tcp_do_rfc3465) {
218                                 /* Increment cwnd by alpha segments. */
219                                 CCV(ccv, snd_cwnd) += htcp_data->alpha *
220                                     CCV(ccv, t_maxseg);
221                                 ccv->flags &= ~CCF_ABC_SENTAWND;
222                         } else
223                                 /*
224                                  * Increment cwnd by alpha/cwnd segments to
225                                  * approximate an increase of alpha segments
226                                  * per RTT.
227                                  */
228                                 CCV(ccv, snd_cwnd) += (((htcp_data->alpha <<
229                                     HTCP_SHIFT) / (CCV(ccv, snd_cwnd) /
230                                     CCV(ccv, t_maxseg))) * CCV(ccv, t_maxseg))
231                                     >> HTCP_SHIFT;
232                 }
233         }
234 }
235
236 static void
237 htcp_cb_destroy(struct cc_var *ccv)
238 {
239
240         if (ccv->cc_data != NULL)
241                 free(ccv->cc_data, M_HTCP);
242 }
243
244 static int
245 htcp_cb_init(struct cc_var *ccv)
246 {
247         struct htcp *htcp_data;
248
249         htcp_data = malloc(sizeof(struct htcp), M_HTCP, M_NOWAIT);
250
251         if (htcp_data == NULL)
252                 return (ENOMEM);
253
254         /* Init some key variables with sensible defaults. */
255         htcp_data->alpha = HTCP_INIT_ALPHA;
256         htcp_data->beta = HTCP_MINBETA;
257         htcp_data->maxrtt = TCPTV_SRTTBASE;
258         htcp_data->minrtt = TCPTV_SRTTBASE;
259         htcp_data->prev_cwnd = 0;
260         htcp_data->t_last_cong = ticks;
261
262         ccv->cc_data = htcp_data;
263
264         return (0);
265 }
266
267 /*
268  * Perform any necessary tasks before we enter congestion recovery.
269  */
270 static void
271 htcp_cong_signal(struct cc_var *ccv, uint32_t type)
272 {
273         struct htcp *htcp_data;
274         uint32_t cwin;
275         u_int mss;
276
277         htcp_data = ccv->cc_data;
278         cwin = CCV(ccv, snd_cwnd);
279         mss = CCV(ccv, t_maxseg);
280
281         switch (type) {
282         case CC_NDUPACK:
283                 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
284                         if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
285                                 /*
286                                  * Apply hysteresis to maxrtt to ensure
287                                  * reductions in the RTT are reflected in our
288                                  * measurements.
289                                  */
290                                 htcp_data->maxrtt = (htcp_data->minrtt +
291                                     (htcp_data->maxrtt - htcp_data->minrtt) *
292                                     95) / 100;
293                                 htcp_ssthresh_update(ccv);
294                                 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
295                                 htcp_data->t_last_cong = ticks;
296                                 htcp_data->prev_cwnd = cwin;
297                         }
298                         ENTER_RECOVERY(CCV(ccv, t_flags));
299                 }
300                 break;
301
302         case CC_ECN:
303                 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
304                         /*
305                          * Apply hysteresis to maxrtt to ensure reductions in
306                          * the RTT are reflected in our measurements.
307                          */
308                         htcp_data->maxrtt = (htcp_data->minrtt + (htcp_data->maxrtt -
309                             htcp_data->minrtt) * 95) / 100;
310                         htcp_ssthresh_update(ccv);
311                         CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
312                         htcp_data->t_last_cong = ticks;
313                         htcp_data->prev_cwnd = cwin;
314                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
315                 }
316                 break;
317
318         case CC_RTO:
319                 /*
320                  * Grab the current time and record it so we know when the
321                  * most recent congestion event was. Only record it when the
322                  * timeout has fired more than once, as there is a reasonable
323                  * chance the first one is a false alarm and may not indicate
324                  * congestion.
325                  */
326                 if (CCV(ccv, t_rxtshift) >= 2)
327                         htcp_data->t_last_cong = ticks;
328                 CCV(ccv, snd_ssthresh) =
329                     max((CCV(ccv, snd_max) - CCV(ccv, snd_una)) / 2 / mss, 2)
330                         * mss;
331                 CCV(ccv, snd_cwnd) = mss;
332                 break;
333         }
334 }
335
336 static int
337 htcp_mod_init(void)
338 {
339
340         htcp_cc_algo.after_idle = newreno_cc_algo.after_idle;
341
342         /*
343          * HTCP_RTT_REF is defined in ms, and t_srtt in the tcpcb is stored in
344          * units of TCP_RTT_SCALE*hz. Scale HTCP_RTT_REF to be in the same units
345          * as t_srtt.
346          */
347         htcp_rtt_ref = (HTCP_RTT_REF * TCP_RTT_SCALE * hz) / 1000;
348
349         return (0);
350 }
351
352 /*
353  * Perform any necessary tasks before we exit congestion recovery.
354  */
355 static void
356 htcp_post_recovery(struct cc_var *ccv)
357 {
358         int pipe;
359         struct htcp *htcp_data;
360
361         pipe = 0;
362         htcp_data = ccv->cc_data;
363
364         if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
365                 /*
366                  * If inflight data is less than ssthresh, set cwnd
367                  * conservatively to avoid a burst of data, as suggested in the
368                  * NewReno RFC. Otherwise, use the HTCP method.
369                  *
370                  * XXXLAS: Find a way to do this without needing curack
371                  */
372                 if (V_tcp_do_rfc6675_pipe)
373                         pipe = tcp_compute_pipe(ccv->ccvc.tcp);
374                 else
375                         pipe = CCV(ccv, snd_max) - ccv->curack;
376                 
377                 if (pipe < CCV(ccv, snd_ssthresh))
378                         CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
379                 else
380                         CCV(ccv, snd_cwnd) = max(1, ((htcp_data->beta *
381                             htcp_data->prev_cwnd / CCV(ccv, t_maxseg))
382                             >> HTCP_SHIFT)) * CCV(ccv, t_maxseg);
383         }
384 }
385
386 static void
387 htcp_recalc_alpha(struct cc_var *ccv)
388 {
389         struct htcp *htcp_data;
390         int alpha, diff, now;
391
392         htcp_data = ccv->cc_data;
393         now = ticks;
394
395         /*
396          * If ticks has wrapped around (will happen approximately once every 49
397          * days on a machine with the default kern.hz=1000) and a flow straddles
398          * the wrap point, our alpha calcs will be completely wrong. We cut our
399          * losses and restart alpha from scratch by setting t_last_cong = now -
400          * HTCP_DELTA_L.
401          *
402          * This does not deflate our cwnd at all. It simply slows the rate cwnd
403          * is growing by until alpha regains the value it held prior to taking
404          * this drastic measure.
405          */
406         if (now < htcp_data->t_last_cong)
407                 htcp_data->t_last_cong = now - HTCP_DELTA_L;
408
409         diff = now - htcp_data->t_last_cong - HTCP_DELTA_L;
410
411         /* Cap alpha if the value of diff would overflow HTCP_CALC_ALPHA(). */
412         if (diff < htcp_max_diff) {
413                 /*
414                  * If it has been more than HTCP_DELTA_L ticks since congestion,
415                  * increase alpha according to the function defined in the spec.
416                  */
417                 if (diff > 0) {
418                         alpha = HTCP_CALC_ALPHA(diff);
419
420                         /*
421                          * Adaptive backoff fairness adjustment:
422                          * 2 * (1 - beta) * alpha_raw
423                          */
424                         if (V_htcp_adaptive_backoff)
425                                 alpha = max(1, (2 * ((1 << HTCP_SHIFT) -
426                                     htcp_data->beta) * alpha) >> HTCP_SHIFT);
427
428                         /*
429                          * RTT scaling: (RTT / RTT_ref) * alpha
430                          * alpha will be the raw value from HTCP_CALC_ALPHA() if
431                          * adaptive backoff is off, or the adjusted value if
432                          * adaptive backoff is on.
433                          */
434                         if (V_htcp_rtt_scaling)
435                                 alpha = max(1, (min(max(HTCP_MINROWE,
436                                     (CCV(ccv, t_srtt) << HTCP_SHIFT) /
437                                     htcp_rtt_ref), HTCP_MAXROWE) * alpha)
438                                     >> HTCP_SHIFT);
439
440                 } else
441                         alpha = 1;
442
443                 htcp_data->alpha = alpha;
444         }
445 }
446
447 static void
448 htcp_recalc_beta(struct cc_var *ccv)
449 {
450         struct htcp *htcp_data;
451
452         htcp_data = ccv->cc_data;
453
454         /*
455          * TCPTV_SRTTBASE is the initialised value of each connection's SRTT, so
456          * we only calc beta if the connection's SRTT has been changed from its
457          * initial value. beta is bounded to ensure it is always between
458          * HTCP_MINBETA and HTCP_MAXBETA.
459          */
460         if (V_htcp_adaptive_backoff && htcp_data->minrtt != TCPTV_SRTTBASE &&
461             htcp_data->maxrtt != TCPTV_SRTTBASE)
462                 htcp_data->beta = min(max(HTCP_MINBETA,
463                     (htcp_data->minrtt << HTCP_SHIFT) / htcp_data->maxrtt),
464                     HTCP_MAXBETA);
465         else
466                 htcp_data->beta = HTCP_MINBETA;
467 }
468
469 /*
470  * Record the minimum and maximum RTT seen for the connection. These are used in
471  * the calculation of beta if adaptive backoff is enabled.
472  */
473 static void
474 htcp_record_rtt(struct cc_var *ccv)
475 {
476         struct htcp *htcp_data;
477
478         htcp_data = ccv->cc_data;
479
480         /* XXXLAS: Should there be some hysteresis for minrtt? */
481
482         /*
483          * Record the current SRTT as our minrtt if it's the smallest we've seen
484          * or minrtt is currently equal to its initialised value. Ignore SRTT
485          * until a min number of samples have been taken.
486          */
487         if ((CCV(ccv, t_srtt) < htcp_data->minrtt ||
488             htcp_data->minrtt == TCPTV_SRTTBASE) &&
489             (CCV(ccv, t_rttupdated) >= HTCP_MIN_RTT_SAMPLES))
490                 htcp_data->minrtt = CCV(ccv, t_srtt);
491
492         /*
493          * Record the current SRTT as our maxrtt if it's the largest we've
494          * seen. Ignore SRTT until a min number of samples have been taken.
495          */
496         if (CCV(ccv, t_srtt) > htcp_data->maxrtt
497             && CCV(ccv, t_rttupdated) >= HTCP_MIN_RTT_SAMPLES)
498                 htcp_data->maxrtt = CCV(ccv, t_srtt);
499 }
500
501 /*
502  * Update the ssthresh in the event of congestion.
503  */
504 static void
505 htcp_ssthresh_update(struct cc_var *ccv)
506 {
507         struct htcp *htcp_data;
508
509         htcp_data = ccv->cc_data;
510
511         /*
512          * On the first congestion event, set ssthresh to cwnd * 0.5, on
513          * subsequent congestion events, set it to cwnd * beta.
514          */
515         if (CCV(ccv, snd_ssthresh) == TCP_MAXWIN << TCP_MAX_WINSHIFT)
516                 CCV(ccv, snd_ssthresh) = ((u_long)CCV(ccv, snd_cwnd) *
517                     HTCP_MINBETA) >> HTCP_SHIFT;
518         else {
519                 htcp_recalc_beta(ccv);
520                 CCV(ccv, snd_ssthresh) = ((u_long)CCV(ccv, snd_cwnd) *
521                     htcp_data->beta) >> HTCP_SHIFT;
522         }
523
524         /* Align ssthresh to MSS boundary */
525         CCV(ccv, snd_ssthresh) = (CCV(ccv, snd_ssthresh) / CCV(ccv, t_maxseg))
526             * CCV(ccv, t_maxseg);
527 }
528
529
530 SYSCTL_DECL(_net_inet_tcp_cc_htcp);
531 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, htcp, CTLFLAG_RW,
532     NULL, "H-TCP related settings");
533 SYSCTL_UINT(_net_inet_tcp_cc_htcp, OID_AUTO, adaptive_backoff,
534     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(htcp_adaptive_backoff), 0,
535     "enable H-TCP adaptive backoff");
536 SYSCTL_UINT(_net_inet_tcp_cc_htcp, OID_AUTO, rtt_scaling,
537     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(htcp_rtt_scaling), 0,
538     "enable H-TCP RTT scaling");
539
540 DECLARE_CC_MODULE(htcp, &htcp_cc_algo);