aboutsummaryrefslogtreecommitdiffstats
path: root/net/dccp/ccids
diff options
context:
space:
mode:
Diffstat (limited to 'net/dccp/ccids')
-rw-r--r--net/dccp/ccids/Kconfig29
-rw-r--r--net/dccp/ccids/Makefile5
-rw-r--r--net/dccp/ccids/ccid3.c1221
-rw-r--r--net/dccp/ccids/ccid3.h137
-rw-r--r--net/dccp/ccids/lib/Makefile3
-rw-r--r--net/dccp/ccids/lib/loss_interval.c144
-rw-r--r--net/dccp/ccids/lib/loss_interval.h61
-rw-r--r--net/dccp/ccids/lib/packet_history.c398
-rw-r--r--net/dccp/ccids/lib/packet_history.h199
-rw-r--r--net/dccp/ccids/lib/tfrc.h22
-rw-r--r--net/dccp/ccids/lib/tfrc_equation.c644
11 files changed, 2863 insertions, 0 deletions
diff --git a/net/dccp/ccids/Kconfig b/net/dccp/ccids/Kconfig
new file mode 100644
index 000000000000..7684d83946a4
--- /dev/null
+++ b/net/dccp/ccids/Kconfig
@@ -0,0 +1,29 @@
1menu "DCCP CCIDs Configuration (EXPERIMENTAL)"
2 depends on IP_DCCP && EXPERIMENTAL
3
4config IP_DCCP_CCID3
5 tristate "CCID3 (TFRC) (EXPERIMENTAL)"
6 depends on IP_DCCP
7 ---help---
8 CCID 3 denotes TCP-Friendly Rate Control (TFRC), an equation-based
9 rate-controlled congestion control mechanism. TFRC is designed to
10 be reasonably fair when competing for bandwidth with TCP-like flows,
11 where a flow is "reasonably fair" if its sending rate is generally
12 within a factor of two of the sending rate of a TCP flow under the
13 same conditions. However, TFRC has a much lower variation of
14 throughput over time compared with TCP, which makes CCID 3 more
15 suitable than CCID 2 for applications such streaming media where a
16 relatively smooth sending rate is of importance.
17
18 CCID 3 is further described in [CCID 3 PROFILE]. The TFRC
19 congestion control algorithms were initially described in RFC 3448.
20
21 This text was extracted from draft-ietf-dccp-spec-11.txt.
22
23 If in doubt, say M.
24
25config IP_DCCP_TFRC_LIB
26 depends on IP_DCCP_CCID3
27 def_tristate IP_DCCP_CCID3
28
29endmenu
diff --git a/net/dccp/ccids/Makefile b/net/dccp/ccids/Makefile
new file mode 100644
index 000000000000..956f79f50743
--- /dev/null
+++ b/net/dccp/ccids/Makefile
@@ -0,0 +1,5 @@
1obj-$(CONFIG_IP_DCCP_CCID3) += dccp_ccid3.o
2
3dccp_ccid3-y := ccid3.o
4
5obj-y += lib/
diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
new file mode 100644
index 000000000000..7bf3b3a91e97
--- /dev/null
+++ b/net/dccp/ccids/ccid3.c
@@ -0,0 +1,1221 @@
1/*
2 * net/dccp/ccids/ccid3.c
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
6 *
7 * An implementation of the DCCP protocol
8 *
9 * This code has been developed by the University of Waikato WAND
10 * research group. For further information please see http://www.wand.net.nz/
11 *
12 * This code also uses code from Lulea University, rereleased as GPL by its
13 * authors:
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
15 *
16 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
17 * and to make it work as a loadable module in the DCCP stack written by
18 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
19 *
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
21 *
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
35 */
36
37#include <linux/config.h>
38#include "../ccid.h"
39#include "../dccp.h"
40#include "lib/packet_history.h"
41#include "lib/loss_interval.h"
42#include "lib/tfrc.h"
43#include "ccid3.h"
44
45/*
46 * Reason for maths with 10 here is to avoid 32 bit overflow when a is big.
47 */
48static inline u32 usecs_div(const u32 a, const u32 b)
49{
50 const u32 tmp = a * (USEC_PER_SEC / 10);
51 return b > 20 ? tmp / (b / 10) : tmp;
52}
53
54static int ccid3_debug;
55
56#ifdef CCID3_DEBUG
57#define ccid3_pr_debug(format, a...) \
58 do { if (ccid3_debug) \
59 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
60 } while (0)
61#else
62#define ccid3_pr_debug(format, a...)
63#endif
64
65static struct dccp_tx_hist *ccid3_tx_hist;
66static struct dccp_rx_hist *ccid3_rx_hist;
67static struct dccp_li_hist *ccid3_li_hist;
68
69static int ccid3_init(struct sock *sk)
70{
71 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
72 return 0;
73}
74
75static void ccid3_exit(struct sock *sk)
76{
77 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
78}
79
80/* TFRC sender states */
81enum ccid3_hc_tx_states {
82 TFRC_SSTATE_NO_SENT = 1,
83 TFRC_SSTATE_NO_FBACK,
84 TFRC_SSTATE_FBACK,
85 TFRC_SSTATE_TERM,
86};
87
88#ifdef CCID3_DEBUG
89static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
90{
91 static char *ccid3_state_names[] = {
92 [TFRC_SSTATE_NO_SENT] = "NO_SENT",
93 [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
94 [TFRC_SSTATE_FBACK] = "FBACK",
95 [TFRC_SSTATE_TERM] = "TERM",
96 };
97
98 return ccid3_state_names[state];
99}
100#endif
101
102static inline void ccid3_hc_tx_set_state(struct sock *sk,
103 enum ccid3_hc_tx_states state)
104{
105 struct dccp_sock *dp = dccp_sk(sk);
106 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
107 enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
108
109 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
110 dccp_role(sk), sk, ccid3_tx_state_name(oldstate),
111 ccid3_tx_state_name(state));
112 WARN_ON(state == oldstate);
113 hctx->ccid3hctx_state = state;
114}
115
116/* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */
117static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx)
118{
119 /*
120 * If no feedback spec says t_ipi is 1 second (set elsewhere and then
121 * doubles after every no feedback timer (separate function)
122 */
123 if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK)
124 hctx->ccid3hctx_t_ipi = usecs_div(hctx->ccid3hctx_s,
125 hctx->ccid3hctx_x);
126}
127
128/* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
129static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx)
130{
131 hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
132 TFRC_OPSYS_HALF_TIME_GRAN);
133}
134
135/*
136 * Update X by
137 * If (p > 0)
138 * x_calc = calcX(s, R, p);
139 * X = max(min(X_calc, 2 * X_recv), s / t_mbi);
140 * Else
141 * If (now - tld >= R)
142 * X = max(min(2 * X, 2 * X_recv), s / R);
143 * tld = now;
144 */
145static void ccid3_hc_tx_update_x(struct sock *sk)
146{
147 struct dccp_sock *dp = dccp_sk(sk);
148 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
149
150 /* To avoid large error in calcX */
151 if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) {
152 hctx->ccid3hctx_x_calc = tfrc_calc_x(hctx->ccid3hctx_s,
153 hctx->ccid3hctx_rtt,
154 hctx->ccid3hctx_p);
155 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc,
156 2 * hctx->ccid3hctx_x_recv),
157 (hctx->ccid3hctx_s /
158 TFRC_MAX_BACK_OFF_TIME));
159 } else {
160 struct timeval now;
161
162 do_gettimeofday(&now);
163 if (timeval_delta(&now, &hctx->ccid3hctx_t_ld) >=
164 hctx->ccid3hctx_rtt) {
165 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_recv,
166 hctx->ccid3hctx_x) * 2,
167 usecs_div(hctx->ccid3hctx_s,
168 hctx->ccid3hctx_rtt));
169 hctx->ccid3hctx_t_ld = now;
170 }
171 }
172}
173
174static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
175{
176 struct sock *sk = (struct sock *)data;
177 struct dccp_sock *dp = dccp_sk(sk);
178 unsigned long next_tmout = 0;
179 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
180
181 bh_lock_sock(sk);
182 if (sock_owned_by_user(sk)) {
183 /* Try again later. */
184 /* XXX: set some sensible MIB */
185 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
186 jiffies + HZ / 5);
187 goto out;
188 }
189
190 ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
191 ccid3_tx_state_name(hctx->ccid3hctx_state));
192
193 switch (hctx->ccid3hctx_state) {
194 case TFRC_SSTATE_TERM:
195 goto out;
196 case TFRC_SSTATE_NO_FBACK:
197 /* Halve send rate */
198 hctx->ccid3hctx_x /= 2;
199 if (hctx->ccid3hctx_x < (hctx->ccid3hctx_s /
200 TFRC_MAX_BACK_OFF_TIME))
201 hctx->ccid3hctx_x = (hctx->ccid3hctx_s /
202 TFRC_MAX_BACK_OFF_TIME);
203
204 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d "
205 "bytes/s\n",
206 dccp_role(sk), sk,
207 ccid3_tx_state_name(hctx->ccid3hctx_state),
208 hctx->ccid3hctx_x);
209 next_tmout = max_t(u32, 2 * usecs_div(hctx->ccid3hctx_s,
210 hctx->ccid3hctx_x),
211 TFRC_INITIAL_TIMEOUT);
212 /*
213 * FIXME - not sure above calculation is correct. See section
214 * 5 of CCID3 11 should adjust tx_t_ipi and double that to
215 * achieve it really
216 */
217 break;
218 case TFRC_SSTATE_FBACK:
219 /*
220 * Check if IDLE since last timeout and recv rate is less than
221 * 4 packets per RTT
222 */
223 if (!hctx->ccid3hctx_idle ||
224 (hctx->ccid3hctx_x_recv >=
225 4 * usecs_div(hctx->ccid3hctx_s, hctx->ccid3hctx_rtt))) {
226 ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n",
227 dccp_role(sk), sk,
228 ccid3_tx_state_name(hctx->ccid3hctx_state));
229 /* Halve sending rate */
230
231 /* If (X_calc > 2 * X_recv)
232 * X_recv = max(X_recv / 2, s / (2 * t_mbi));
233 * Else
234 * X_recv = X_calc / 4;
235 */
236 BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P &&
237 hctx->ccid3hctx_x_calc == 0);
238
239 /* check also if p is zero -> x_calc is infinity? */
240 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P ||
241 hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv)
242 hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2,
243 hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME));
244 else
245 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
246
247 /* Update sending rate */
248 ccid3_hc_tx_update_x(sk);
249 }
250 /*
251 * Schedule no feedback timer to expire in
252 * max(4 * R, 2 * s / X)
253 */
254 next_tmout = max_t(u32, hctx->ccid3hctx_t_rto,
255 2 * usecs_div(hctx->ccid3hctx_s,
256 hctx->ccid3hctx_x));
257 break;
258 default:
259 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
260 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
261 dump_stack();
262 goto out;
263 }
264
265 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
266 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
267 hctx->ccid3hctx_idle = 1;
268out:
269 bh_unlock_sock(sk);
270 sock_put(sk);
271}
272
273static int ccid3_hc_tx_send_packet(struct sock *sk,
274 struct sk_buff *skb, int len)
275{
276 struct dccp_sock *dp = dccp_sk(sk);
277 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
278 struct dccp_tx_hist_entry *new_packet;
279 struct timeval now;
280 long delay;
281 int rc = -ENOTCONN;
282
283 /* Check if pure ACK or Terminating*/
284
285 /*
286 * XXX: We only call this function for DATA and DATAACK, on, these
287 * packets can have zero length, but why the comment about "pure ACK"?
288 */
289 if (hctx == NULL || len == 0 ||
290 hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
291 goto out;
292
293 /* See if last packet allocated was not sent */
294 new_packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
295 if (new_packet == NULL || new_packet->dccphtx_sent) {
296 new_packet = dccp_tx_hist_entry_new(ccid3_tx_hist,
297 SLAB_ATOMIC);
298
299 rc = -ENOBUFS;
300 if (new_packet == NULL) {
301 ccid3_pr_debug("%s, sk=%p, not enough mem to add "
302 "to history, send refused\n",
303 dccp_role(sk), sk);
304 goto out;
305 }
306
307 dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet);
308 }
309
310 do_gettimeofday(&now);
311
312 switch (hctx->ccid3hctx_state) {
313 case TFRC_SSTATE_NO_SENT:
314 ccid3_pr_debug("%s, sk=%p, first packet(%llu)\n",
315 dccp_role(sk), sk, dp->dccps_gss);
316
317 hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer;
318 hctx->ccid3hctx_no_feedback_timer.data = (unsigned long)sk;
319 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
320 jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT));
321 hctx->ccid3hctx_last_win_count = 0;
322 hctx->ccid3hctx_t_last_win_count = now;
323 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
324 hctx->ccid3hctx_t_ipi = TFRC_INITIAL_TIMEOUT;
325
326 /* Set nominal send time for initial packet */
327 hctx->ccid3hctx_t_nom = now;
328 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
329 hctx->ccid3hctx_t_ipi);
330 ccid3_calc_new_delta(hctx);
331 rc = 0;
332 break;
333 case TFRC_SSTATE_NO_FBACK:
334 case TFRC_SSTATE_FBACK:
335 delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
336 hctx->ccid3hctx_delta);
337 ccid3_pr_debug("send_packet delay=%ld\n", delay);
338 delay /= -1000;
339 /* divide by -1000 is to convert to ms and get sign right */
340 rc = delay > 0 ? delay : 0;
341 break;
342 default:
343 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
344 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
345 dump_stack();
346 rc = -EINVAL;
347 break;
348 }
349
350 /* Can we send? if so add options and add to packet history */
351 if (rc == 0)
352 new_packet->dccphtx_ccval =
353 DCCP_SKB_CB(skb)->dccpd_ccval =
354 hctx->ccid3hctx_last_win_count;
355out:
356 return rc;
357}
358
359static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
360{
361 struct dccp_sock *dp = dccp_sk(sk);
362 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
363 struct timeval now;
364
365 BUG_ON(hctx == NULL);
366
367 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
368 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
369 dccp_role(sk), sk);
370 return;
371 }
372
373 do_gettimeofday(&now);
374
375 /* check if we have sent a data packet */
376 if (len > 0) {
377 unsigned long quarter_rtt;
378 struct dccp_tx_hist_entry *packet;
379
380 packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
381 if (packet == NULL) {
382 printk(KERN_CRIT "%s: packet doesn't exists in "
383 "history!\n", __FUNCTION__);
384 return;
385 }
386 if (packet->dccphtx_sent) {
387 printk(KERN_CRIT "%s: no unsent packet in history!\n",
388 __FUNCTION__);
389 return;
390 }
391 packet->dccphtx_tstamp = now;
392 packet->dccphtx_seqno = dp->dccps_gss;
393 /*
394 * Check if win_count have changed
395 * Algorithm in "8.1. Window Counter Valuer" in
396 * draft-ietf-dccp-ccid3-11.txt
397 */
398 quarter_rtt = timeval_delta(&now, &hctx->ccid3hctx_t_last_win_count);
399 if (likely(hctx->ccid3hctx_rtt > 8))
400 quarter_rtt /= hctx->ccid3hctx_rtt / 4;
401
402 if (quarter_rtt > 0) {
403 hctx->ccid3hctx_t_last_win_count = now;
404 hctx->ccid3hctx_last_win_count = (hctx->ccid3hctx_last_win_count +
405 min_t(unsigned long, quarter_rtt, 5)) % 16;
406 ccid3_pr_debug("%s, sk=%p, window changed from "
407 "%u to %u!\n",
408 dccp_role(sk), sk,
409 packet->dccphtx_ccval,
410 hctx->ccid3hctx_last_win_count);
411 }
412
413 hctx->ccid3hctx_idle = 0;
414 packet->dccphtx_rtt = hctx->ccid3hctx_rtt;
415 packet->dccphtx_sent = 1;
416 } else
417 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
418 dccp_role(sk), sk, dp->dccps_gss);
419
420 switch (hctx->ccid3hctx_state) {
421 case TFRC_SSTATE_NO_SENT:
422 /* if first wasn't pure ack */
423 if (len != 0)
424 printk(KERN_CRIT "%s: %s, First packet sent is noted "
425 "as a data packet\n",
426 __FUNCTION__, dccp_role(sk));
427 return;
428 case TFRC_SSTATE_NO_FBACK:
429 case TFRC_SSTATE_FBACK:
430 if (len > 0) {
431 hctx->ccid3hctx_t_nom = now;
432 ccid3_calc_new_t_ipi(hctx);
433 ccid3_calc_new_delta(hctx);
434 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
435 hctx->ccid3hctx_t_ipi);
436 }
437 break;
438 default:
439 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
440 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
441 dump_stack();
442 break;
443 }
444}
445
446static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
447{
448 struct dccp_sock *dp = dccp_sk(sk);
449 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
450 struct ccid3_options_received *opt_recv;
451 struct dccp_tx_hist_entry *packet;
452 unsigned long next_tmout;
453 u32 t_elapsed;
454 u32 pinv;
455 u32 x_recv;
456 u32 r_sample;
457
458 if (hctx == NULL)
459 return;
460
461 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
462 ccid3_pr_debug("%s, sk=%p, received a packet when "
463 "terminating!\n", dccp_role(sk), sk);
464 return;
465 }
466
467 /* we are only interested in ACKs */
468 if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
469 DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
470 return;
471
472 opt_recv = &hctx->ccid3hctx_options_received;
473
474 t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
475 x_recv = opt_recv->ccid3or_receive_rate;
476 pinv = opt_recv->ccid3or_loss_event_rate;
477
478 switch (hctx->ccid3hctx_state) {
479 case TFRC_SSTATE_NO_SENT:
480 /* FIXME: what to do here? */
481 return;
482 case TFRC_SSTATE_NO_FBACK:
483 case TFRC_SSTATE_FBACK:
484 /* Calculate new round trip sample by
485 * R_sample = (now - t_recvdata) - t_delay */
486 /* get t_recvdata from history */
487 packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
488 DCCP_SKB_CB(skb)->dccpd_ack_seq);
489 if (packet == NULL) {
490 ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't "
491 "exist in history!\n",
492 dccp_role(sk), sk,
493 DCCP_SKB_CB(skb)->dccpd_ack_seq,
494 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
495 return;
496 }
497
498 /* Update RTT */
499 r_sample = timeval_now_delta(&packet->dccphtx_tstamp);
500 /* FIXME: */
501 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
502
503 /* Update RTT estimate by
504 * If (No feedback recv)
505 * R = R_sample;
506 * Else
507 * R = q * R + (1 - q) * R_sample;
508 *
509 * q is a constant, RFC 3448 recomments 0.9
510 */
511 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
512 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
513 hctx->ccid3hctx_rtt = r_sample;
514 } else
515 hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 +
516 r_sample / 10;
517
518 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, "
519 "r_sample=%us\n", dccp_role(sk), sk,
520 hctx->ccid3hctx_rtt, r_sample);
521
522 /* Update timeout interval */
523 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
524 USEC_PER_SEC);
525
526 /* Update receive rate */
527 hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */
528
529 /* Update loss event rate */
530 if (pinv == ~0 || pinv == 0)
531 hctx->ccid3hctx_p = 0;
532 else {
533 hctx->ccid3hctx_p = 1000000 / pinv;
534
535 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
536 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
537 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n",
538 dccp_role(sk), sk);
539 }
540 }
541
542 /* unschedule no feedback timer */
543 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
544
545 /* Update sending rate */
546 ccid3_hc_tx_update_x(sk);
547
548 /* Update next send time */
549 timeval_sub_usecs(&hctx->ccid3hctx_t_nom,
550 hctx->ccid3hctx_t_ipi);
551 ccid3_calc_new_t_ipi(hctx);
552 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
553 hctx->ccid3hctx_t_ipi);
554 ccid3_calc_new_delta(hctx);
555
556 /* remove all packets older than the one acked from history */
557 dccp_tx_hist_purge_older(ccid3_tx_hist,
558 &hctx->ccid3hctx_hist, packet);
559 /*
560 * As we have calculated new ipi, delta, t_nom it is possible that
561 * we now can send a packet, so wake up dccp_wait_for_ccids.
562 */
563 sk->sk_write_space(sk);
564
565 /*
566 * Schedule no feedback timer to expire in
567 * max(4 * R, 2 * s / X)
568 */
569 next_tmout = max(hctx->ccid3hctx_t_rto,
570 2 * usecs_div(hctx->ccid3hctx_s,
571 hctx->ccid3hctx_x));
572
573 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to "
574 "expire in %lu jiffies (%luus)\n",
575 dccp_role(sk), sk,
576 usecs_to_jiffies(next_tmout), next_tmout);
577
578 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
579 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
580
581 /* set idle flag */
582 hctx->ccid3hctx_idle = 1;
583 break;
584 default:
585 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
586 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
587 dump_stack();
588 break;
589 }
590}
591
592static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
593{
594 const struct dccp_sock *dp = dccp_sk(sk);
595 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
596
597 if (hctx == NULL || !(sk->sk_state == DCCP_OPEN ||
598 sk->sk_state == DCCP_PARTOPEN))
599 return;
600
601 DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
602}
603
604static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
605 unsigned char len, u16 idx,
606 unsigned char *value)
607{
608 int rc = 0;
609 struct dccp_sock *dp = dccp_sk(sk);
610 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
611 struct ccid3_options_received *opt_recv;
612
613 if (hctx == NULL)
614 return 0;
615
616 opt_recv = &hctx->ccid3hctx_options_received;
617
618 if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
619 opt_recv->ccid3or_seqno = dp->dccps_gsr;
620 opt_recv->ccid3or_loss_event_rate = ~0;
621 opt_recv->ccid3or_loss_intervals_idx = 0;
622 opt_recv->ccid3or_loss_intervals_len = 0;
623 opt_recv->ccid3or_receive_rate = 0;
624 }
625
626 switch (option) {
627 case TFRC_OPT_LOSS_EVENT_RATE:
628 if (len != 4) {
629 ccid3_pr_debug("%s, sk=%p, invalid len for "
630 "TFRC_OPT_LOSS_EVENT_RATE\n",
631 dccp_role(sk), sk);
632 rc = -EINVAL;
633 } else {
634 opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
635 ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
636 dccp_role(sk), sk,
637 opt_recv->ccid3or_loss_event_rate);
638 }
639 break;
640 case TFRC_OPT_LOSS_INTERVALS:
641 opt_recv->ccid3or_loss_intervals_idx = idx;
642 opt_recv->ccid3or_loss_intervals_len = len;
643 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
644 dccp_role(sk), sk,
645 opt_recv->ccid3or_loss_intervals_idx,
646 opt_recv->ccid3or_loss_intervals_len);
647 break;
648 case TFRC_OPT_RECEIVE_RATE:
649 if (len != 4) {
650 ccid3_pr_debug("%s, sk=%p, invalid len for "
651 "TFRC_OPT_RECEIVE_RATE\n",
652 dccp_role(sk), sk);
653 rc = -EINVAL;
654 } else {
655 opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
656 ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
657 dccp_role(sk), sk,
658 opt_recv->ccid3or_receive_rate);
659 }
660 break;
661 }
662
663 return rc;
664}
665
666static int ccid3_hc_tx_init(struct sock *sk)
667{
668 struct dccp_sock *dp = dccp_sk(sk);
669 struct ccid3_hc_tx_sock *hctx;
670
671 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
672
673 hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx),
674 gfp_any());
675 if (hctx == NULL)
676 return -ENOMEM;
677
678 memset(hctx, 0, sizeof(*hctx));
679
680 if (dp->dccps_packet_size >= TFRC_MIN_PACKET_SIZE &&
681 dp->dccps_packet_size <= TFRC_MAX_PACKET_SIZE)
682 hctx->ccid3hctx_s = dp->dccps_packet_size;
683 else
684 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
685
686 /* Set transmission rate to 1 packet per second */
687 hctx->ccid3hctx_x = hctx->ccid3hctx_s;
688 hctx->ccid3hctx_t_rto = USEC_PER_SEC;
689 hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
690 INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
691 init_timer(&hctx->ccid3hctx_no_feedback_timer);
692
693 return 0;
694}
695
696static void ccid3_hc_tx_exit(struct sock *sk)
697{
698 struct dccp_sock *dp = dccp_sk(sk);
699 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
700
701 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
702 BUG_ON(hctx == NULL);
703
704 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
705 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
706
707 /* Empty packet history */
708 dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
709
710 kfree(dp->dccps_hc_tx_ccid_private);
711 dp->dccps_hc_tx_ccid_private = NULL;
712}
713
714/*
715 * RX Half Connection methods
716 */
717
718/* TFRC receiver states */
719enum ccid3_hc_rx_states {
720 TFRC_RSTATE_NO_DATA = 1,
721 TFRC_RSTATE_DATA,
722 TFRC_RSTATE_TERM = 127,
723};
724
725#ifdef CCID3_DEBUG
726static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
727{
728 static char *ccid3_rx_state_names[] = {
729 [TFRC_RSTATE_NO_DATA] = "NO_DATA",
730 [TFRC_RSTATE_DATA] = "DATA",
731 [TFRC_RSTATE_TERM] = "TERM",
732 };
733
734 return ccid3_rx_state_names[state];
735}
736#endif
737
738static inline void ccid3_hc_rx_set_state(struct sock *sk,
739 enum ccid3_hc_rx_states state)
740{
741 struct dccp_sock *dp = dccp_sk(sk);
742 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
743 enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
744
745 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
746 dccp_role(sk), sk, ccid3_rx_state_name(oldstate),
747 ccid3_rx_state_name(state));
748 WARN_ON(state == oldstate);
749 hcrx->ccid3hcrx_state = state;
750}
751
752static void ccid3_hc_rx_send_feedback(struct sock *sk)
753{
754 struct dccp_sock *dp = dccp_sk(sk);
755 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
756 struct dccp_rx_hist_entry *packet;
757 struct timeval now;
758
759 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
760
761 do_gettimeofday(&now);
762
763 switch (hcrx->ccid3hcrx_state) {
764 case TFRC_RSTATE_NO_DATA:
765 hcrx->ccid3hcrx_x_recv = 0;
766 break;
767 case TFRC_RSTATE_DATA: {
768 const u32 delta = timeval_delta(&now,
769 &hcrx->ccid3hcrx_tstamp_last_feedback);
770
771 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
772 USEC_PER_SEC);
773 if (likely(delta > 1))
774 hcrx->ccid3hcrx_x_recv /= delta;
775 }
776 break;
777 default:
778 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
779 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
780 dump_stack();
781 return;
782 }
783
784 packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist);
785 if (packet == NULL) {
786 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
787 __FUNCTION__, dccp_role(sk), sk);
788 dump_stack();
789 return;
790 }
791
792 hcrx->ccid3hcrx_tstamp_last_feedback = now;
793 hcrx->ccid3hcrx_last_counter = packet->dccphrx_ccval;
794 hcrx->ccid3hcrx_seqno_last_counter = packet->dccphrx_seqno;
795 hcrx->ccid3hcrx_bytes_recv = 0;
796
797 /* Convert to multiples of 10us */
798 hcrx->ccid3hcrx_elapsed_time =
799 timeval_delta(&now, &packet->dccphrx_tstamp) / 10;
800 if (hcrx->ccid3hcrx_p == 0)
801 hcrx->ccid3hcrx_pinv = ~0;
802 else
803 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
804 dccp_send_ack(sk);
805}
806
807static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
808{
809 const struct dccp_sock *dp = dccp_sk(sk);
810 u32 x_recv, pinv;
811 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
812
813 if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN ||
814 sk->sk_state == DCCP_PARTOPEN))
815 return;
816
817 DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
818
819 if (dccp_packet_without_ack(skb))
820 return;
821
822 if (hcrx->ccid3hcrx_elapsed_time != 0)
823 dccp_insert_option_elapsed_time(sk, skb,
824 hcrx->ccid3hcrx_elapsed_time);
825 dccp_insert_option_timestamp(sk, skb);
826 x_recv = htonl(hcrx->ccid3hcrx_x_recv);
827 pinv = htonl(hcrx->ccid3hcrx_pinv);
828 dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
829 &pinv, sizeof(pinv));
830 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
831 &x_recv, sizeof(x_recv));
832}
833
834/* calculate first loss interval
835 *
836 * returns estimated loss interval in usecs */
837
838static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
839{
840 struct dccp_sock *dp = dccp_sk(sk);
841 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
842 struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
843 u32 rtt, delta, x_recv, fval, p, tmp2;
844 struct timeval tstamp = { 0, };
845 int interval = 0;
846 int win_count = 0;
847 int step = 0;
848 u64 tmp1;
849
850 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
851 dccphrx_node) {
852 if (dccp_rx_hist_entry_data_packet(entry)) {
853 tail = entry;
854
855 switch (step) {
856 case 0:
857 tstamp = entry->dccphrx_tstamp;
858 win_count = entry->dccphrx_ccval;
859 step = 1;
860 break;
861 case 1:
862 interval = win_count - entry->dccphrx_ccval;
863 if (interval < 0)
864 interval += TFRC_WIN_COUNT_LIMIT;
865 if (interval > 4)
866 goto found;
867 break;
868 }
869 }
870 }
871
872 if (step == 0) {
873 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no "
874 "data packets!\n",
875 __FUNCTION__, dccp_role(sk), sk);
876 return ~0;
877 }
878
879 if (interval == 0) {
880 ccid3_pr_debug("%s, sk=%p, Could not find a win_count "
881 "interval > 0. Defaulting to 1\n",
882 dccp_role(sk), sk);
883 interval = 1;
884 }
885found:
886 rtt = timeval_delta(&tstamp, &tail->dccphrx_tstamp) * 4 / interval;
887 ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
888 dccp_role(sk), sk, rtt);
889 if (rtt == 0)
890 rtt = 1;
891
892 delta = timeval_now_delta(&hcrx->ccid3hcrx_tstamp_last_feedback);
893 x_recv = hcrx->ccid3hcrx_bytes_recv * USEC_PER_SEC;
894 if (likely(delta > 1))
895 x_recv /= delta;
896
897 tmp1 = (u64)x_recv * (u64)rtt;
898 do_div(tmp1,10000000);
899 tmp2 = (u32)tmp1;
900 fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
901 /* do not alter order above or you will get overflow on 32 bit */
902 p = tfrc_calc_x_reverse_lookup(fval);
903 ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied "
904 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
905
906 if (p == 0)
907 return ~0;
908 else
909 return 1000000 / p;
910}
911
912static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
913{
914 struct dccp_sock *dp = dccp_sk(sk);
915 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
916
917 if (seq_loss != DCCP_MAX_SEQNO + 1 &&
918 list_empty(&hcrx->ccid3hcrx_li_hist)) {
919 struct dccp_li_hist_entry *li_tail;
920
921 li_tail = dccp_li_hist_interval_new(ccid3_li_hist,
922 &hcrx->ccid3hcrx_li_hist,
923 seq_loss, win_loss);
924 if (li_tail == NULL)
925 return;
926 li_tail->dccplih_interval = ccid3_hc_rx_calc_first_li(sk);
927 }
928 /* FIXME: find end of interval */
929}
930
931static void ccid3_hc_rx_detect_loss(struct sock *sk)
932{
933 struct dccp_sock *dp = dccp_sk(sk);
934 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
935 u8 win_loss;
936 const u64 seq_loss = dccp_rx_hist_detect_loss(&hcrx->ccid3hcrx_hist,
937 &hcrx->ccid3hcrx_li_hist,
938 &win_loss);
939
940 ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
941}
942
943static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
944{
945 struct dccp_sock *dp = dccp_sk(sk);
946 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
947 const struct dccp_options_received *opt_recv;
948 struct dccp_rx_hist_entry *packet;
949 struct timeval now;
950 u8 win_count;
951 u32 p_prev;
952 int ins;
953
954 if (hcrx == NULL)
955 return;
956
957 BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
958 hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
959
960 opt_recv = &dp->dccps_options_received;
961
962 switch (DCCP_SKB_CB(skb)->dccpd_type) {
963 case DCCP_PKT_ACK:
964 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
965 return;
966 case DCCP_PKT_DATAACK:
967 if (opt_recv->dccpor_timestamp_echo == 0)
968 break;
969 p_prev = hcrx->ccid3hcrx_rtt;
970 do_gettimeofday(&now);
971 hcrx->ccid3hcrx_rtt = timeval_usecs(&now) -
972 (opt_recv->dccpor_timestamp_echo -
973 opt_recv->dccpor_elapsed_time) * 10;
974 if (p_prev != hcrx->ccid3hcrx_rtt)
975 ccid3_pr_debug("%s, New RTT=%luus, elapsed time=%u\n",
976 dccp_role(sk), hcrx->ccid3hcrx_rtt,
977 opt_recv->dccpor_elapsed_time);
978 break;
979 case DCCP_PKT_DATA:
980 break;
981 default:
982 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
983 dccp_role(sk), sk,
984 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
985 return;
986 }
987
988 packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp,
989 skb, SLAB_ATOMIC);
990 if (packet == NULL) {
991 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet "
992 "to history (consider it lost)!",
993 dccp_role(sk), sk);
994 return;
995 }
996
997 win_count = packet->dccphrx_ccval;
998
999 ins = dccp_rx_hist_add_packet(ccid3_rx_hist, &hcrx->ccid3hcrx_hist,
1000 &hcrx->ccid3hcrx_li_hist, packet);
1001
1002 if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1003 return;
1004
1005 switch (hcrx->ccid3hcrx_state) {
1006 case TFRC_RSTATE_NO_DATA:
1007 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial "
1008 "feedback\n",
1009 dccp_role(sk), sk,
1010 dccp_state_name(sk->sk_state), skb);
1011 ccid3_hc_rx_send_feedback(sk);
1012 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
1013 return;
1014 case TFRC_RSTATE_DATA:
1015 hcrx->ccid3hcrx_bytes_recv += skb->len -
1016 dccp_hdr(skb)->dccph_doff * 4;
1017 if (ins != 0)
1018 break;
1019
1020 do_gettimeofday(&now);
1021 if (timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) >=
1022 hcrx->ccid3hcrx_rtt) {
1023 hcrx->ccid3hcrx_tstamp_last_ack = now;
1024 ccid3_hc_rx_send_feedback(sk);
1025 }
1026 return;
1027 default:
1028 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1029 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1030 dump_stack();
1031 return;
1032 }
1033
1034 /* Dealing with packet loss */
1035 ccid3_pr_debug("%s, sk=%p(%s), data loss! Reacting...\n",
1036 dccp_role(sk), sk, dccp_state_name(sk->sk_state));
1037
1038 ccid3_hc_rx_detect_loss(sk);
1039 p_prev = hcrx->ccid3hcrx_p;
1040
1041 /* Calculate loss event rate */
1042 if (!list_empty(&hcrx->ccid3hcrx_li_hist))
1043 /* Scaling up by 1000000 as fixed decimal */
1044 hcrx->ccid3hcrx_p = 1000000 / dccp_li_hist_calc_i_mean(&hcrx->ccid3hcrx_li_hist);
1045
1046 if (hcrx->ccid3hcrx_p > p_prev) {
1047 ccid3_hc_rx_send_feedback(sk);
1048 return;
1049 }
1050}
1051
1052static int ccid3_hc_rx_init(struct sock *sk)
1053{
1054 struct dccp_sock *dp = dccp_sk(sk);
1055 struct ccid3_hc_rx_sock *hcrx;
1056
1057 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1058
1059 hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx),
1060 gfp_any());
1061 if (hcrx == NULL)
1062 return -ENOMEM;
1063
1064 memset(hcrx, 0, sizeof(*hcrx));
1065
1066 if (dp->dccps_packet_size >= TFRC_MIN_PACKET_SIZE &&
1067 dp->dccps_packet_size <= TFRC_MAX_PACKET_SIZE)
1068 hcrx->ccid3hcrx_s = dp->dccps_packet_size;
1069 else
1070 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
1071
1072 hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
1073 INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
1074 INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist);
1075 /*
1076 * XXX this seems to be paranoid, need to think more about this, for
1077 * now start with something different than zero. -acme
1078 */
1079 hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
1080 return 0;
1081}
1082
1083static void ccid3_hc_rx_exit(struct sock *sk)
1084{
1085 struct dccp_sock *dp = dccp_sk(sk);
1086 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1087
1088 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1089
1090 if (hcrx == NULL)
1091 return;
1092
1093 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
1094
1095 /* Empty packet history */
1096 dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
1097
1098 /* Empty loss interval history */
1099 dccp_li_hist_purge(ccid3_li_hist, &hcrx->ccid3hcrx_li_hist);
1100
1101 kfree(dp->dccps_hc_rx_ccid_private);
1102 dp->dccps_hc_rx_ccid_private = NULL;
1103}
1104
1105static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
1106{
1107 const struct dccp_sock *dp = dccp_sk(sk);
1108 const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1109
1110 if (hcrx == NULL)
1111 return;
1112
1113 info->tcpi_ca_state = hcrx->ccid3hcrx_state;
1114 info->tcpi_options |= TCPI_OPT_TIMESTAMPS;
1115 info->tcpi_rcv_rtt = hcrx->ccid3hcrx_rtt;
1116}
1117
1118static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
1119{
1120 const struct dccp_sock *dp = dccp_sk(sk);
1121 const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1122
1123 if (hctx == NULL)
1124 return;
1125
1126 info->tcpi_rto = hctx->ccid3hctx_t_rto;
1127 info->tcpi_rtt = hctx->ccid3hctx_rtt;
1128}
1129
1130static struct ccid ccid3 = {
1131 .ccid_id = 3,
1132 .ccid_name = "ccid3",
1133 .ccid_owner = THIS_MODULE,
1134 .ccid_init = ccid3_init,
1135 .ccid_exit = ccid3_exit,
1136 .ccid_hc_tx_init = ccid3_hc_tx_init,
1137 .ccid_hc_tx_exit = ccid3_hc_tx_exit,
1138 .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet,
1139 .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent,
1140 .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv,
1141 .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
1142 .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options,
1143 .ccid_hc_rx_init = ccid3_hc_rx_init,
1144 .ccid_hc_rx_exit = ccid3_hc_rx_exit,
1145 .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
1146 .ccid_hc_rx_packet_recv = ccid3_hc_rx_packet_recv,
1147 .ccid_hc_rx_get_info = ccid3_hc_rx_get_info,
1148 .ccid_hc_tx_get_info = ccid3_hc_tx_get_info,
1149};
1150
1151module_param(ccid3_debug, int, 0444);
1152MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
1153
1154static __init int ccid3_module_init(void)
1155{
1156 int rc = -ENOBUFS;
1157
1158 ccid3_rx_hist = dccp_rx_hist_new("ccid3");
1159 if (ccid3_rx_hist == NULL)
1160 goto out;
1161
1162 ccid3_tx_hist = dccp_tx_hist_new("ccid3");
1163 if (ccid3_tx_hist == NULL)
1164 goto out_free_rx;
1165
1166 ccid3_li_hist = dccp_li_hist_new("ccid3");
1167 if (ccid3_li_hist == NULL)
1168 goto out_free_tx;
1169
1170 rc = ccid_register(&ccid3);
1171 if (rc != 0)
1172 goto out_free_loss_interval_history;
1173out:
1174 return rc;
1175
1176out_free_loss_interval_history:
1177 dccp_li_hist_delete(ccid3_li_hist);
1178 ccid3_li_hist = NULL;
1179out_free_tx:
1180 dccp_tx_hist_delete(ccid3_tx_hist);
1181 ccid3_tx_hist = NULL;
1182out_free_rx:
1183 dccp_rx_hist_delete(ccid3_rx_hist);
1184 ccid3_rx_hist = NULL;
1185 goto out;
1186}
1187module_init(ccid3_module_init);
1188
1189static __exit void ccid3_module_exit(void)
1190{
1191#ifdef CONFIG_IP_DCCP_UNLOAD_HACK
1192 /*
1193 * Hack to use while developing, so that we get rid of the control
1194 * sock, that is what keeps a refcount on dccp.ko -acme
1195 */
1196 extern void dccp_ctl_sock_exit(void);
1197
1198 dccp_ctl_sock_exit();
1199#endif
1200 ccid_unregister(&ccid3);
1201
1202 if (ccid3_tx_hist != NULL) {
1203 dccp_tx_hist_delete(ccid3_tx_hist);
1204 ccid3_tx_hist = NULL;
1205 }
1206 if (ccid3_rx_hist != NULL) {
1207 dccp_rx_hist_delete(ccid3_rx_hist);
1208 ccid3_rx_hist = NULL;
1209 }
1210 if (ccid3_li_hist != NULL) {
1211 dccp_li_hist_delete(ccid3_li_hist);
1212 ccid3_li_hist = NULL;
1213 }
1214}
1215module_exit(ccid3_module_exit);
1216
1217MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, "
1218 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
1219MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
1220MODULE_LICENSE("GPL");
1221MODULE_ALIAS("net-dccp-ccid-3");
diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h
new file mode 100644
index 000000000000..ee8cbace6630
--- /dev/null
+++ b/net/dccp/ccids/ccid3.h
@@ -0,0 +1,137 @@
1/*
2 * net/dccp/ccids/ccid3.h
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 *
6 * An implementation of the DCCP protocol
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 * or e-mail Ian McDonald - iam4@cs.waikato.ac.nz
11 *
12 * This code also uses code from Lulea University, rereleased as GPL by its
13 * authors:
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
15 *
16 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
17 * and to make it work as a loadable module in the DCCP stack written by
18 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
19 *
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
21 *
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
35 */
36#ifndef _DCCP_CCID3_H_
37#define _DCCP_CCID3_H_
38
39#include <linux/config.h>
40#include <linux/list.h>
41#include <linux/time.h>
42#include <linux/types.h>
43
44#define TFRC_MIN_PACKET_SIZE 16
45#define TFRC_STD_PACKET_SIZE 256
46#define TFRC_MAX_PACKET_SIZE 65535
47
48/* Two seconds as per CCID3 spec */
49#define TFRC_INITIAL_TIMEOUT (2 * USEC_PER_SEC)
50
51/* In usecs - half the scheduling granularity as per RFC3448 4.6 */
52#define TFRC_OPSYS_HALF_TIME_GRAN (USEC_PER_SEC / (2 * HZ))
53
54/* In seconds */
55#define TFRC_MAX_BACK_OFF_TIME 64
56
57#define TFRC_SMALLEST_P 40
58
59enum ccid3_options {
60 TFRC_OPT_LOSS_EVENT_RATE = 192,
61 TFRC_OPT_LOSS_INTERVALS = 193,
62 TFRC_OPT_RECEIVE_RATE = 194,
63};
64
65struct ccid3_options_received {
66 u64 ccid3or_seqno:48,
67 ccid3or_loss_intervals_idx:16;
68 u16 ccid3or_loss_intervals_len;
69 u32 ccid3or_loss_event_rate;
70 u32 ccid3or_receive_rate;
71};
72
73/** struct ccid3_hc_tx_sock - CCID3 sender half connection sock
74 *
75 * @ccid3hctx_state - Sender state
76 * @ccid3hctx_x - Current sending rate
77 * @ccid3hctx_x_recv - Receive rate
78 * @ccid3hctx_x_calc - Calculated send (?) rate
79 * @ccid3hctx_s - Packet size
80 * @ccid3hctx_rtt - Estimate of current round trip time in usecs
81 * @@ccid3hctx_p - Current loss event rate (0-1) scaled by 1000000
82 * @ccid3hctx_last_win_count - Last window counter sent
83 * @ccid3hctx_t_last_win_count - Timestamp of earliest packet
84 * with last_win_count value sent
85 * @ccid3hctx_no_feedback_timer - Handle to no feedback timer
86 * @ccid3hctx_idle - FIXME
87 * @ccid3hctx_t_ld - Time last doubled during slow start
88 * @ccid3hctx_t_nom - Nominal send time of next packet
89 * @ccid3hctx_t_ipi - Interpacket (send) interval
90 * @ccid3hctx_delta - Send timer delta
91 * @ccid3hctx_hist - Packet history
92 */
93struct ccid3_hc_tx_sock {
94 u32 ccid3hctx_x;
95 u32 ccid3hctx_x_recv;
96 u32 ccid3hctx_x_calc;
97 u16 ccid3hctx_s;
98 u32 ccid3hctx_rtt;
99 u32 ccid3hctx_p;
100 u8 ccid3hctx_state;
101 u8 ccid3hctx_last_win_count;
102 u8 ccid3hctx_idle;
103 struct timeval ccid3hctx_t_last_win_count;
104 struct timer_list ccid3hctx_no_feedback_timer;
105 struct timeval ccid3hctx_t_ld;
106 struct timeval ccid3hctx_t_nom;
107 u32 ccid3hctx_t_rto;
108 u32 ccid3hctx_t_ipi;
109 u32 ccid3hctx_delta;
110 struct list_head ccid3hctx_hist;
111 struct ccid3_options_received ccid3hctx_options_received;
112};
113
114struct ccid3_hc_rx_sock {
115 u64 ccid3hcrx_seqno_last_counter:48,
116 ccid3hcrx_state:8,
117 ccid3hcrx_last_counter:4;
118 unsigned long ccid3hcrx_rtt;
119 u32 ccid3hcrx_p;
120 u32 ccid3hcrx_bytes_recv;
121 struct timeval ccid3hcrx_tstamp_last_feedback;
122 struct timeval ccid3hcrx_tstamp_last_ack;
123 struct list_head ccid3hcrx_hist;
124 struct list_head ccid3hcrx_li_hist;
125 u16 ccid3hcrx_s;
126 u32 ccid3hcrx_pinv;
127 u32 ccid3hcrx_elapsed_time;
128 u32 ccid3hcrx_x_recv;
129};
130
131#define ccid3_hc_tx_field(s,field) (s->dccps_hc_tx_ccid_private == NULL ? 0 : \
132 ((struct ccid3_hc_tx_sock *)s->dccps_hc_tx_ccid_private)->ccid3hctx_##field)
133
134#define ccid3_hc_rx_field(s,field) (s->dccps_hc_rx_ccid_private == NULL ? 0 : \
135 ((struct ccid3_hc_rx_sock *)s->dccps_hc_rx_ccid_private)->ccid3hcrx_##field)
136
137#endif /* _DCCP_CCID3_H_ */
diff --git a/net/dccp/ccids/lib/Makefile b/net/dccp/ccids/lib/Makefile
new file mode 100644
index 000000000000..5f940a6cbaca
--- /dev/null
+++ b/net/dccp/ccids/lib/Makefile
@@ -0,0 +1,3 @@
1obj-$(CONFIG_IP_DCCP_TFRC_LIB) += dccp_tfrc_lib.o
2
3dccp_tfrc_lib-y := loss_interval.o packet_history.o tfrc_equation.o
diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c
new file mode 100644
index 000000000000..4c01a54143ad
--- /dev/null
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -0,0 +1,144 @@
1/*
2 * net/dccp/ccids/lib/loss_interval.c
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 */
13
14#include <linux/config.h>
15#include <linux/module.h>
16
17#include "loss_interval.h"
18
19struct dccp_li_hist *dccp_li_hist_new(const char *name)
20{
21 struct dccp_li_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
22 static const char dccp_li_hist_mask[] = "li_hist_%s";
23 char *slab_name;
24
25 if (hist == NULL)
26 goto out;
27
28 slab_name = kmalloc(strlen(name) + sizeof(dccp_li_hist_mask) - 1,
29 GFP_ATOMIC);
30 if (slab_name == NULL)
31 goto out_free_hist;
32
33 sprintf(slab_name, dccp_li_hist_mask, name);
34 hist->dccplih_slab = kmem_cache_create(slab_name,
35 sizeof(struct dccp_li_hist_entry),
36 0, SLAB_HWCACHE_ALIGN,
37 NULL, NULL);
38 if (hist->dccplih_slab == NULL)
39 goto out_free_slab_name;
40out:
41 return hist;
42out_free_slab_name:
43 kfree(slab_name);
44out_free_hist:
45 kfree(hist);
46 hist = NULL;
47 goto out;
48}
49
50EXPORT_SYMBOL_GPL(dccp_li_hist_new);
51
52void dccp_li_hist_delete(struct dccp_li_hist *hist)
53{
54 const char* name = kmem_cache_name(hist->dccplih_slab);
55
56 kmem_cache_destroy(hist->dccplih_slab);
57 kfree(name);
58 kfree(hist);
59}
60
61EXPORT_SYMBOL_GPL(dccp_li_hist_delete);
62
63void dccp_li_hist_purge(struct dccp_li_hist *hist, struct list_head *list)
64{
65 struct dccp_li_hist_entry *entry, *next;
66
67 list_for_each_entry_safe(entry, next, list, dccplih_node) {
68 list_del_init(&entry->dccplih_node);
69 kmem_cache_free(hist->dccplih_slab, entry);
70 }
71}
72
73EXPORT_SYMBOL_GPL(dccp_li_hist_purge);
74
75/* Weights used to calculate loss event rate */
76/*
77 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
78 * when we use it.
79 */
80static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = {
81 4, 4, 4, 4, 3, 2, 1, 1,
82};
83
84u32 dccp_li_hist_calc_i_mean(struct list_head *list)
85{
86 struct dccp_li_hist_entry *li_entry, *li_next;
87 int i = 0;
88 u32 i_tot;
89 u32 i_tot0 = 0;
90 u32 i_tot1 = 0;
91 u32 w_tot = 0;
92
93 list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
94 if (i < DCCP_LI_HIST_IVAL_F_LENGTH) {
95 i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
96 w_tot += dccp_li_hist_w[i];
97 }
98
99 if (i != 0)
100 i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];
101
102 if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
103 break;
104 }
105
106 if (i != DCCP_LI_HIST_IVAL_F_LENGTH)
107 return 0;
108
109 i_tot = max(i_tot0, i_tot1);
110
111 /* FIXME: Why do we do this? -Ian McDonald */
112 if (i_tot * 4 < w_tot)
113 i_tot = w_tot * 4;
114
115 return i_tot * 4 / w_tot;
116}
117
118EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean);
119
120struct dccp_li_hist_entry *dccp_li_hist_interval_new(struct dccp_li_hist *hist,
121 struct list_head *list,
122 const u64 seq_loss,
123 const u8 win_loss)
124{
125 struct dccp_li_hist_entry *tail = NULL, *entry;
126 int i;
127
128 for (i = 0; i <= DCCP_LI_HIST_IVAL_F_LENGTH; ++i) {
129 entry = dccp_li_hist_entry_new(hist, SLAB_ATOMIC);
130 if (entry == NULL) {
131 dccp_li_hist_purge(hist, list);
132 return NULL;
133 }
134 if (tail == NULL)
135 tail = entry;
136 list_add(&entry->dccplih_node, list);
137 }
138
139 entry->dccplih_seqno = seq_loss;
140 entry->dccplih_win_count = win_loss;
141 return tail;
142}
143
144EXPORT_SYMBOL_GPL(dccp_li_hist_interval_new);
diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h
new file mode 100644
index 000000000000..13ad47ba1420
--- /dev/null
+++ b/net/dccp/ccids/lib/loss_interval.h
@@ -0,0 +1,61 @@
1#ifndef _DCCP_LI_HIST_
2#define _DCCP_LI_HIST_
3/*
4 * net/dccp/ccids/lib/loss_interval.h
5 *
6 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
7 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
8 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
9 *
10 * This program is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the Free
12 * Software Foundation; either version 2 of the License, or (at your option)
13 * any later version.
14 */
15
16#include <linux/config.h>
17#include <linux/list.h>
18#include <linux/slab.h>
19#include <linux/time.h>
20
21#define DCCP_LI_HIST_IVAL_F_LENGTH 8
22
23struct dccp_li_hist {
24 kmem_cache_t *dccplih_slab;
25};
26
27extern struct dccp_li_hist *dccp_li_hist_new(const char *name);
28extern void dccp_li_hist_delete(struct dccp_li_hist *hist);
29
30struct dccp_li_hist_entry {
31 struct list_head dccplih_node;
32 u64 dccplih_seqno:48,
33 dccplih_win_count:4;
34 u32 dccplih_interval;
35};
36
37static inline struct dccp_li_hist_entry *
38 dccp_li_hist_entry_new(struct dccp_li_hist *hist,
39 const unsigned int __nocast prio)
40{
41 return kmem_cache_alloc(hist->dccplih_slab, prio);
42}
43
44static inline void dccp_li_hist_entry_delete(struct dccp_li_hist *hist,
45 struct dccp_li_hist_entry *entry)
46{
47 if (entry != NULL)
48 kmem_cache_free(hist->dccplih_slab, entry);
49}
50
51extern void dccp_li_hist_purge(struct dccp_li_hist *hist,
52 struct list_head *list);
53
54extern u32 dccp_li_hist_calc_i_mean(struct list_head *list);
55
56extern struct dccp_li_hist_entry *
57 dccp_li_hist_interval_new(struct dccp_li_hist *hist,
58 struct list_head *list,
59 const u64 seq_loss,
60 const u8 win_loss);
61#endif /* _DCCP_LI_HIST_ */
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
new file mode 100644
index 000000000000..d3f9d2053830
--- /dev/null
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -0,0 +1,398 @@
1/*
2 * net/dccp/packet_history.h
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 *
6 * An implementation of the DCCP protocol
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 * or e-mail Ian McDonald - iam4@cs.waikato.ac.nz
11 *
12 * This code also uses code from Lulea University, rereleased as GPL by its
13 * authors:
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
15 *
16 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
17 * and to make it work as a loadable module in the DCCP stack written by
18 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
19 *
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
21 *
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
35 */
36
37#include <linux/config.h>
38#include <linux/module.h>
39#include <linux/string.h>
40
41#include "packet_history.h"
42
43struct dccp_rx_hist *dccp_rx_hist_new(const char *name)
44{
45 struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
46 static const char dccp_rx_hist_mask[] = "rx_hist_%s";
47 char *slab_name;
48
49 if (hist == NULL)
50 goto out;
51
52 slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1,
53 GFP_ATOMIC);
54 if (slab_name == NULL)
55 goto out_free_hist;
56
57 sprintf(slab_name, dccp_rx_hist_mask, name);
58 hist->dccprxh_slab = kmem_cache_create(slab_name,
59 sizeof(struct dccp_rx_hist_entry),
60 0, SLAB_HWCACHE_ALIGN,
61 NULL, NULL);
62 if (hist->dccprxh_slab == NULL)
63 goto out_free_slab_name;
64out:
65 return hist;
66out_free_slab_name:
67 kfree(slab_name);
68out_free_hist:
69 kfree(hist);
70 hist = NULL;
71 goto out;
72}
73
74EXPORT_SYMBOL_GPL(dccp_rx_hist_new);
75
76void dccp_rx_hist_delete(struct dccp_rx_hist *hist)
77{
78 const char* name = kmem_cache_name(hist->dccprxh_slab);
79
80 kmem_cache_destroy(hist->dccprxh_slab);
81 kfree(name);
82 kfree(hist);
83}
84
85EXPORT_SYMBOL_GPL(dccp_rx_hist_delete);
86
87void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
88{
89 struct dccp_rx_hist_entry *entry, *next;
90
91 list_for_each_entry_safe(entry, next, list, dccphrx_node) {
92 list_del_init(&entry->dccphrx_node);
93 kmem_cache_free(hist->dccprxh_slab, entry);
94 }
95}
96
97EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
98
99struct dccp_rx_hist_entry *
100 dccp_rx_hist_find_data_packet(const struct list_head *list)
101{
102 struct dccp_rx_hist_entry *entry, *packet = NULL;
103
104 list_for_each_entry(entry, list, dccphrx_node)
105 if (entry->dccphrx_type == DCCP_PKT_DATA ||
106 entry->dccphrx_type == DCCP_PKT_DATAACK) {
107 packet = entry;
108 break;
109 }
110
111 return packet;
112}
113
114EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet);
115
116int dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
117 struct list_head *rx_list,
118 struct list_head *li_list,
119 struct dccp_rx_hist_entry *packet)
120{
121 struct dccp_rx_hist_entry *entry, *next, *iter;
122 u8 num_later = 0;
123
124 iter = dccp_rx_hist_head(rx_list);
125 if (iter == NULL)
126 dccp_rx_hist_add_entry(rx_list, packet);
127 else {
128 const u64 seqno = packet->dccphrx_seqno;
129
130 if (after48(seqno, iter->dccphrx_seqno))
131 dccp_rx_hist_add_entry(rx_list, packet);
132 else {
133 if (dccp_rx_hist_entry_data_packet(iter))
134 num_later = 1;
135
136 list_for_each_entry_continue(iter, rx_list,
137 dccphrx_node) {
138 if (after48(seqno, iter->dccphrx_seqno)) {
139 dccp_rx_hist_add_entry(&iter->dccphrx_node,
140 packet);
141 goto trim_history;
142 }
143
144 if (dccp_rx_hist_entry_data_packet(iter))
145 num_later++;
146
147 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
148 dccp_rx_hist_entry_delete(hist, packet);
149 return 1;
150 }
151 }
152
153 if (num_later < TFRC_RECV_NUM_LATE_LOSS)
154 dccp_rx_hist_add_entry(rx_list, packet);
155 /*
156 * FIXME: else what? should we destroy the packet
157 * like above?
158 */
159 }
160 }
161
162trim_history:
163 /*
164 * Trim history (remove all packets after the NUM_LATE_LOSS + 1
165 * data packets)
166 */
167 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
168
169 if (!list_empty(li_list)) {
170 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
171 if (num_later == 0) {
172 list_del_init(&entry->dccphrx_node);
173 dccp_rx_hist_entry_delete(hist, entry);
174 } else if (dccp_rx_hist_entry_data_packet(entry))
175 --num_later;
176 }
177 } else {
178 int step = 0;
179 u8 win_count = 0; /* Not needed, but lets shut up gcc */
180 int tmp;
181 /*
182 * We have no loss interval history so we need at least one
183 * rtt:s of data packets to approximate rtt.
184 */
185 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
186 if (num_later == 0) {
187 switch (step) {
188 case 0:
189 step = 1;
190 /* OK, find next data packet */
191 num_later = 1;
192 break;
193 case 1:
194 step = 2;
195 /* OK, find next data packet */
196 num_later = 1;
197 win_count = entry->dccphrx_ccval;
198 break;
199 case 2:
200 tmp = win_count - entry->dccphrx_ccval;
201 if (tmp < 0)
202 tmp += TFRC_WIN_COUNT_LIMIT;
203 if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
204 /*
205 * We have found a packet older
206 * than one rtt remove the rest
207 */
208 step = 3;
209 } else /* OK, find next data packet */
210 num_later = 1;
211 break;
212 case 3:
213 list_del_init(&entry->dccphrx_node);
214 dccp_rx_hist_entry_delete(hist, entry);
215 break;
216 }
217 } else if (dccp_rx_hist_entry_data_packet(entry))
218 --num_later;
219 }
220 }
221
222 return 0;
223}
224
225EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
226
227u64 dccp_rx_hist_detect_loss(struct list_head *rx_list,
228 struct list_head *li_list, u8 *win_loss)
229{
230 struct dccp_rx_hist_entry *entry, *next, *packet;
231 struct dccp_rx_hist_entry *a_loss = NULL;
232 struct dccp_rx_hist_entry *b_loss = NULL;
233 u64 seq_loss = DCCP_MAX_SEQNO + 1;
234 u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
235
236 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
237 if (num_later == 0) {
238 b_loss = entry;
239 break;
240 } else if (dccp_rx_hist_entry_data_packet(entry))
241 --num_later;
242 }
243
244 if (b_loss == NULL)
245 goto out;
246
247 num_later = 1;
248 list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) {
249 if (num_later == 0) {
250 a_loss = entry;
251 break;
252 } else if (dccp_rx_hist_entry_data_packet(entry))
253 --num_later;
254 }
255
256 if (a_loss == NULL) {
257 if (list_empty(li_list)) {
258 /* no loss event have occured yet */
259 LIMIT_NETDEBUG("%s: TODO: find a lost data packet by "
260 "comparing to initial seqno\n",
261 __FUNCTION__);
262 goto out;
263 } else {
264 LIMIT_NETDEBUG("%s: Less than 4 data pkts in history!",
265 __FUNCTION__);
266 goto out;
267 }
268 }
269
270 /* Locate a lost data packet */
271 entry = packet = b_loss;
272 list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) {
273 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
274 packet->dccphrx_seqno);
275
276 if (delta != 0) {
277 if (dccp_rx_hist_entry_data_packet(packet))
278 --delta;
279 /*
280 * FIXME: check this, probably this % usage is because
281 * in earlier drafts the ndp count was just 8 bits
282 * long, but now it cam be up to 24 bits long.
283 */
284#if 0
285 if (delta % DCCP_NDP_LIMIT !=
286 (packet->dccphrx_ndp -
287 entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
288#endif
289 if (delta != packet->dccphrx_ndp - entry->dccphrx_ndp) {
290 seq_loss = entry->dccphrx_seqno;
291 dccp_inc_seqno(&seq_loss);
292 }
293 }
294 packet = entry;
295 if (packet == a_loss)
296 break;
297 }
298out:
299 if (seq_loss != DCCP_MAX_SEQNO + 1)
300 *win_loss = a_loss->dccphrx_ccval;
301 else
302 *win_loss = 0; /* Paranoia */
303
304 return seq_loss;
305}
306
307EXPORT_SYMBOL_GPL(dccp_rx_hist_detect_loss);
308
309struct dccp_tx_hist *dccp_tx_hist_new(const char *name)
310{
311 struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
312 static const char dccp_tx_hist_mask[] = "tx_hist_%s";
313 char *slab_name;
314
315 if (hist == NULL)
316 goto out;
317
318 slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1,
319 GFP_ATOMIC);
320 if (slab_name == NULL)
321 goto out_free_hist;
322
323 sprintf(slab_name, dccp_tx_hist_mask, name);
324 hist->dccptxh_slab = kmem_cache_create(slab_name,
325 sizeof(struct dccp_tx_hist_entry),
326 0, SLAB_HWCACHE_ALIGN,
327 NULL, NULL);
328 if (hist->dccptxh_slab == NULL)
329 goto out_free_slab_name;
330out:
331 return hist;
332out_free_slab_name:
333 kfree(slab_name);
334out_free_hist:
335 kfree(hist);
336 hist = NULL;
337 goto out;
338}
339
340EXPORT_SYMBOL_GPL(dccp_tx_hist_new);
341
342void dccp_tx_hist_delete(struct dccp_tx_hist *hist)
343{
344 const char* name = kmem_cache_name(hist->dccptxh_slab);
345
346 kmem_cache_destroy(hist->dccptxh_slab);
347 kfree(name);
348 kfree(hist);
349}
350
351EXPORT_SYMBOL_GPL(dccp_tx_hist_delete);
352
353struct dccp_tx_hist_entry *
354 dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq)
355{
356 struct dccp_tx_hist_entry *packet = NULL, *entry;
357
358 list_for_each_entry(entry, list, dccphtx_node)
359 if (entry->dccphtx_seqno == seq) {
360 packet = entry;
361 break;
362 }
363
364 return packet;
365}
366
367EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry);
368
369void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist,
370 struct list_head *list,
371 struct dccp_tx_hist_entry *packet)
372{
373 struct dccp_tx_hist_entry *next;
374
375 list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) {
376 list_del_init(&packet->dccphtx_node);
377 dccp_tx_hist_entry_delete(hist, packet);
378 }
379}
380
381EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older);
382
383void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list)
384{
385 struct dccp_tx_hist_entry *entry, *next;
386
387 list_for_each_entry_safe(entry, next, list, dccphtx_node) {
388 list_del_init(&entry->dccphtx_node);
389 dccp_tx_hist_entry_delete(hist, entry);
390 }
391}
392
393EXPORT_SYMBOL_GPL(dccp_tx_hist_purge);
394
395MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, "
396 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
397MODULE_DESCRIPTION("DCCP TFRC library");
398MODULE_LICENSE("GPL");
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
new file mode 100644
index 000000000000..fb90a91aa93d
--- /dev/null
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -0,0 +1,199 @@
1/*
2 * net/dccp/packet_history.h
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 *
6 * An implementation of the DCCP protocol
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 * or e-mail Ian McDonald - iam4@cs.waikato.ac.nz
11 *
12 * This code also uses code from Lulea University, rereleased as GPL by its
13 * authors:
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
15 *
16 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
17 * and to make it work as a loadable module in the DCCP stack written by
18 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
19 *
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
21 *
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
35 */
36
37#ifndef _DCCP_PKT_HIST_
38#define _DCCP_PKT_HIST_
39
40#include <linux/config.h>
41#include <linux/list.h>
42#include <linux/slab.h>
43#include <linux/time.h>
44
45#include "../../dccp.h"
46
47/* Number of later packets received before one is considered lost */
48#define TFRC_RECV_NUM_LATE_LOSS 3
49
50#define TFRC_WIN_COUNT_PER_RTT 4
51#define TFRC_WIN_COUNT_LIMIT 16
52
53struct dccp_tx_hist_entry {
54 struct list_head dccphtx_node;
55 u64 dccphtx_seqno:48,
56 dccphtx_ccval:4,
57 dccphtx_sent:1;
58 u32 dccphtx_rtt;
59 struct timeval dccphtx_tstamp;
60};
61
62struct dccp_rx_hist_entry {
63 struct list_head dccphrx_node;
64 u64 dccphrx_seqno:48,
65 dccphrx_ccval:4,
66 dccphrx_type:4;
67 u32 dccphrx_ndp; /* In fact it is from 8 to 24 bits */
68 struct timeval dccphrx_tstamp;
69};
70
71struct dccp_tx_hist {
72 kmem_cache_t *dccptxh_slab;
73};
74
75extern struct dccp_tx_hist *dccp_tx_hist_new(const char *name);
76extern void dccp_tx_hist_delete(struct dccp_tx_hist *hist);
77
78struct dccp_rx_hist {
79 kmem_cache_t *dccprxh_slab;
80};
81
82extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
83extern void dccp_rx_hist_delete(struct dccp_rx_hist *hist);
84extern struct dccp_rx_hist_entry *
85 dccp_rx_hist_find_data_packet(const struct list_head *list);
86
87static inline struct dccp_tx_hist_entry *
88 dccp_tx_hist_entry_new(struct dccp_tx_hist *hist,
89 const unsigned int __nocast prio)
90{
91 struct dccp_tx_hist_entry *entry = kmem_cache_alloc(hist->dccptxh_slab,
92 prio);
93
94 if (entry != NULL)
95 entry->dccphtx_sent = 0;
96
97 return entry;
98}
99
100static inline void dccp_tx_hist_entry_delete(struct dccp_tx_hist *hist,
101 struct dccp_tx_hist_entry *entry)
102{
103 if (entry != NULL)
104 kmem_cache_free(hist->dccptxh_slab, entry);
105}
106
107extern struct dccp_tx_hist_entry *
108 dccp_tx_hist_find_entry(const struct list_head *list,
109 const u64 seq);
110
111static inline void dccp_tx_hist_add_entry(struct list_head *list,
112 struct dccp_tx_hist_entry *entry)
113{
114 list_add(&entry->dccphtx_node, list);
115}
116
117extern void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist,
118 struct list_head *list,
119 struct dccp_tx_hist_entry *next);
120
121extern void dccp_tx_hist_purge(struct dccp_tx_hist *hist,
122 struct list_head *list);
123
124static inline struct dccp_tx_hist_entry *
125 dccp_tx_hist_head(struct list_head *list)
126{
127 struct dccp_tx_hist_entry *head = NULL;
128
129 if (!list_empty(list))
130 head = list_entry(list->next, struct dccp_tx_hist_entry,
131 dccphtx_node);
132 return head;
133}
134
135static inline struct dccp_rx_hist_entry *
136 dccp_rx_hist_entry_new(struct dccp_rx_hist *hist,
137 const u32 ndp,
138 const struct sk_buff *skb,
139 const unsigned int __nocast prio)
140{
141 struct dccp_rx_hist_entry *entry = kmem_cache_alloc(hist->dccprxh_slab,
142 prio);
143
144 if (entry != NULL) {
145 const struct dccp_hdr *dh = dccp_hdr(skb);
146
147 entry->dccphrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
148 entry->dccphrx_ccval = dh->dccph_ccval;
149 entry->dccphrx_type = dh->dccph_type;
150 entry->dccphrx_ndp = ndp;
151 do_gettimeofday(&(entry->dccphrx_tstamp));
152 }
153
154 return entry;
155}
156
157static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist *hist,
158 struct dccp_rx_hist_entry *entry)
159{
160 if (entry != NULL)
161 kmem_cache_free(hist->dccprxh_slab, entry);
162}
163
164extern void dccp_rx_hist_purge(struct dccp_rx_hist *hist,
165 struct list_head *list);
166
167static inline void dccp_rx_hist_add_entry(struct list_head *list,
168 struct dccp_rx_hist_entry *entry)
169{
170 list_add(&entry->dccphrx_node, list);
171}
172
173static inline struct dccp_rx_hist_entry *
174 dccp_rx_hist_head(struct list_head *list)
175{
176 struct dccp_rx_hist_entry *head = NULL;
177
178 if (!list_empty(list))
179 head = list_entry(list->next, struct dccp_rx_hist_entry,
180 dccphrx_node);
181 return head;
182}
183
184static inline int
185 dccp_rx_hist_entry_data_packet(const struct dccp_rx_hist_entry *entry)
186{
187 return entry->dccphrx_type == DCCP_PKT_DATA ||
188 entry->dccphrx_type == DCCP_PKT_DATAACK;
189}
190
191extern int dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
192 struct list_head *rx_list,
193 struct list_head *li_list,
194 struct dccp_rx_hist_entry *packet);
195
196extern u64 dccp_rx_hist_detect_loss(struct list_head *rx_list,
197 struct list_head *li_list, u8 *win_loss);
198
199#endif /* _DCCP_PKT_HIST_ */
diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h
new file mode 100644
index 000000000000..130c4c40cfe3
--- /dev/null
+++ b/net/dccp/ccids/lib/tfrc.h
@@ -0,0 +1,22 @@
1#ifndef _TFRC_H_
2#define _TFRC_H_
3/*
4 * net/dccp/ccids/lib/tfrc.h
5 *
6 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
7 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
8 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
9 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
10 *
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
15 */
16
17#include <linux/types.h>
18
19extern u32 tfrc_calc_x(u16 s, u32 R, u32 p);
20extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue);
21
22#endif /* _TFRC_H_ */
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
new file mode 100644
index 000000000000..d2b5933b4510
--- /dev/null
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -0,0 +1,644 @@
1/*
2 * net/dccp/ccids/lib/tfrc_equation.c
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
7 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 */
14
15#include <linux/config.h>
16#include <linux/module.h>
17
18#include <asm/bug.h>
19#include <asm/div64.h>
20
21#include "tfrc.h"
22
23#define TFRC_CALC_X_ARRSIZE 500
24
25#define TFRC_CALC_X_SPLIT 50000
26/* equivalent to 0.05 */
27
28static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
29 { 37172, 8172 },
30 { 53499, 11567 },
31 { 66664, 14180 },
32 { 78298, 16388 },
33 { 89021, 18339 },
34 { 99147, 20108 },
35 { 108858, 21738 },
36 { 118273, 23260 },
37 { 127474, 24693 },
38 { 136520, 26052 },
39 { 145456, 27348 },
40 { 154316, 28589 },
41 { 163130, 29783 },
42 { 171919, 30935 },
43 { 180704, 32049 },
44 { 189502, 33130 },
45 { 198328, 34180 },
46 { 207194, 35202 },
47 { 216114, 36198 },
48 { 225097, 37172 },
49 { 234153, 38123 },
50 { 243294, 39055 },
51 { 252527, 39968 },
52 { 261861, 40864 },
53 { 271305, 41743 },
54 { 280866, 42607 },
55 { 290553, 43457 },
56 { 300372, 44293 },
57 { 310333, 45117 },
58 { 320441, 45929 },
59 { 330705, 46729 },
60 { 341131, 47518 },
61 { 351728, 48297 },
62 { 362501, 49066 },
63 { 373460, 49826 },
64 { 384609, 50577 },
65 { 395958, 51320 },
66 { 407513, 52054 },
67 { 419281, 52780 },
68 { 431270, 53499 },
69 { 443487, 54211 },
70 { 455940, 54916 },
71 { 468635, 55614 },
72 { 481581, 56306 },
73 { 494785, 56991 },
74 { 508254, 57671 },
75 { 521996, 58345 },
76 { 536019, 59014 },
77 { 550331, 59677 },
78 { 564939, 60335 },
79 { 579851, 60988 },
80 { 595075, 61636 },
81 { 610619, 62279 },
82 { 626491, 62918 },
83 { 642700, 63553 },
84 { 659253, 64183 },
85 { 676158, 64809 },
86 { 693424, 65431 },
87 { 711060, 66050 },
88 { 729073, 66664 },
89 { 747472, 67275 },
90 { 766266, 67882 },
91 { 785464, 68486 },
92 { 805073, 69087 },
93 { 825103, 69684 },
94 { 845562, 70278 },
95 { 866460, 70868 },
96 { 887805, 71456 },
97 { 909606, 72041 },
98 { 931873, 72623 },
99 { 954614, 73202 },
100 { 977839, 73778 },
101 { 1001557, 74352 },
102 { 1025777, 74923 },
103 { 1050508, 75492 },
104 { 1075761, 76058 },
105 { 1101544, 76621 },
106 { 1127867, 77183 },
107 { 1154739, 77741 },
108 { 1182172, 78298 },
109 { 1210173, 78852 },
110 { 1238753, 79405 },
111 { 1267922, 79955 },
112 { 1297689, 80503 },
113 { 1328066, 81049 },
114 { 1359060, 81593 },
115 { 1390684, 82135 },
116 { 1422947, 82675 },
117 { 1455859, 83213 },
118 { 1489430, 83750 },
119 { 1523671, 84284 },
120 { 1558593, 84817 },
121 { 1594205, 85348 },
122 { 1630518, 85878 },
123 { 1667543, 86406 },
124 { 1705290, 86932 },
125 { 1743770, 87457 },
126 { 1782994, 87980 },
127 { 1822973, 88501 },
128 { 1863717, 89021 },
129 { 1905237, 89540 },
130 { 1947545, 90057 },
131 { 1990650, 90573 },
132 { 2034566, 91087 },
133 { 2079301, 91600 },
134 { 2124869, 92111 },
135 { 2171279, 92622 },
136 { 2218543, 93131 },
137 { 2266673, 93639 },
138 { 2315680, 94145 },
139 { 2365575, 94650 },
140 { 2416371, 95154 },
141 { 2468077, 95657 },
142 { 2520707, 96159 },
143 { 2574271, 96660 },
144 { 2628782, 97159 },
145 { 2684250, 97658 },
146 { 2740689, 98155 },
147 { 2798110, 98651 },
148 { 2856524, 99147 },
149 { 2915944, 99641 },
150 { 2976382, 100134 },
151 { 3037850, 100626 },
152 { 3100360, 101117 },
153 { 3163924, 101608 },
154 { 3228554, 102097 },
155 { 3294263, 102586 },
156 { 3361063, 103073 },
157 { 3428966, 103560 },
158 { 3497984, 104045 },
159 { 3568131, 104530 },
160 { 3639419, 105014 },
161 { 3711860, 105498 },
162 { 3785467, 105980 },
163 { 3860253, 106462 },
164 { 3936229, 106942 },
165 { 4013410, 107422 },
166 { 4091808, 107902 },
167 { 4171435, 108380 },
168 { 4252306, 108858 },
169 { 4334431, 109335 },
170 { 4417825, 109811 },
171 { 4502501, 110287 },
172 { 4588472, 110762 },
173 { 4675750, 111236 },
174 { 4764349, 111709 },
175 { 4854283, 112182 },
176 { 4945564, 112654 },
177 { 5038206, 113126 },
178 { 5132223, 113597 },
179 { 5227627, 114067 },
180 { 5324432, 114537 },
181 { 5422652, 115006 },
182 { 5522299, 115474 },
183 { 5623389, 115942 },
184 { 5725934, 116409 },
185 { 5829948, 116876 },
186 { 5935446, 117342 },
187 { 6042439, 117808 },
188 { 6150943, 118273 },
189 { 6260972, 118738 },
190 { 6372538, 119202 },
191 { 6485657, 119665 },
192 { 6600342, 120128 },
193 { 6716607, 120591 },
194 { 6834467, 121053 },
195 { 6953935, 121514 },
196 { 7075025, 121976 },
197 { 7197752, 122436 },
198 { 7322131, 122896 },
199 { 7448175, 123356 },
200 { 7575898, 123815 },
201 { 7705316, 124274 },
202 { 7836442, 124733 },
203 { 7969291, 125191 },
204 { 8103877, 125648 },
205 { 8240216, 126105 },
206 { 8378321, 126562 },
207 { 8518208, 127018 },
208 { 8659890, 127474 },
209 { 8803384, 127930 },
210 { 8948702, 128385 },
211 { 9095861, 128840 },
212 { 9244875, 129294 },
213 { 9395760, 129748 },
214 { 9548529, 130202 },
215 { 9703198, 130655 },
216 { 9859782, 131108 },
217 { 10018296, 131561 },
218 { 10178755, 132014 },
219 { 10341174, 132466 },
220 { 10505569, 132917 },
221 { 10671954, 133369 },
222 { 10840345, 133820 },
223 { 11010757, 134271 },
224 { 11183206, 134721 },
225 { 11357706, 135171 },
226 { 11534274, 135621 },
227 { 11712924, 136071 },
228 { 11893673, 136520 },
229 { 12076536, 136969 },
230 { 12261527, 137418 },
231 { 12448664, 137867 },
232 { 12637961, 138315 },
233 { 12829435, 138763 },
234 { 13023101, 139211 },
235 { 13218974, 139658 },
236 { 13417071, 140106 },
237 { 13617407, 140553 },
238 { 13819999, 140999 },
239 { 14024862, 141446 },
240 { 14232012, 141892 },
241 { 14441465, 142339 },
242 { 14653238, 142785 },
243 { 14867346, 143230 },
244 { 15083805, 143676 },
245 { 15302632, 144121 },
246 { 15523842, 144566 },
247 { 15747453, 145011 },
248 { 15973479, 145456 },
249 { 16201939, 145900 },
250 { 16432847, 146345 },
251 { 16666221, 146789 },
252 { 16902076, 147233 },
253 { 17140429, 147677 },
254 { 17381297, 148121 },
255 { 17624696, 148564 },
256 { 17870643, 149007 },
257 { 18119154, 149451 },
258 { 18370247, 149894 },
259 { 18623936, 150336 },
260 { 18880241, 150779 },
261 { 19139176, 151222 },
262 { 19400759, 151664 },
263 { 19665007, 152107 },
264 { 19931936, 152549 },
265 { 20201564, 152991 },
266 { 20473907, 153433 },
267 { 20748982, 153875 },
268 { 21026807, 154316 },
269 { 21307399, 154758 },
270 { 21590773, 155199 },
271 { 21876949, 155641 },
272 { 22165941, 156082 },
273 { 22457769, 156523 },
274 { 22752449, 156964 },
275 { 23049999, 157405 },
276 { 23350435, 157846 },
277 { 23653774, 158287 },
278 { 23960036, 158727 },
279 { 24269236, 159168 },
280 { 24581392, 159608 },
281 { 24896521, 160049 },
282 { 25214642, 160489 },
283 { 25535772, 160929 },
284 { 25859927, 161370 },
285 { 26187127, 161810 },
286 { 26517388, 162250 },
287 { 26850728, 162690 },
288 { 27187165, 163130 },
289 { 27526716, 163569 },
290 { 27869400, 164009 },
291 { 28215234, 164449 },
292 { 28564236, 164889 },
293 { 28916423, 165328 },
294 { 29271815, 165768 },
295 { 29630428, 166208 },
296 { 29992281, 166647 },
297 { 30357392, 167087 },
298 { 30725779, 167526 },
299 { 31097459, 167965 },
300 { 31472452, 168405 },
301 { 31850774, 168844 },
302 { 32232445, 169283 },
303 { 32617482, 169723 },
304 { 33005904, 170162 },
305 { 33397730, 170601 },
306 { 33792976, 171041 },
307 { 34191663, 171480 },
308 { 34593807, 171919 },
309 { 34999428, 172358 },
310 { 35408544, 172797 },
311 { 35821174, 173237 },
312 { 36237335, 173676 },
313 { 36657047, 174115 },
314 { 37080329, 174554 },
315 { 37507197, 174993 },
316 { 37937673, 175433 },
317 { 38371773, 175872 },
318 { 38809517, 176311 },
319 { 39250924, 176750 },
320 { 39696012, 177190 },
321 { 40144800, 177629 },
322 { 40597308, 178068 },
323 { 41053553, 178507 },
324 { 41513554, 178947 },
325 { 41977332, 179386 },
326 { 42444904, 179825 },
327 { 42916290, 180265 },
328 { 43391509, 180704 },
329 { 43870579, 181144 },
330 { 44353520, 181583 },
331 { 44840352, 182023 },
332 { 45331092, 182462 },
333 { 45825761, 182902 },
334 { 46324378, 183342 },
335 { 46826961, 183781 },
336 { 47333531, 184221 },
337 { 47844106, 184661 },
338 { 48358706, 185101 },
339 { 48877350, 185541 },
340 { 49400058, 185981 },
341 { 49926849, 186421 },
342 { 50457743, 186861 },
343 { 50992759, 187301 },
344 { 51531916, 187741 },
345 { 52075235, 188181 },
346 { 52622735, 188622 },
347 { 53174435, 189062 },
348 { 53730355, 189502 },
349 { 54290515, 189943 },
350 { 54854935, 190383 },
351 { 55423634, 190824 },
352 { 55996633, 191265 },
353 { 56573950, 191706 },
354 { 57155606, 192146 },
355 { 57741621, 192587 },
356 { 58332014, 193028 },
357 { 58926806, 193470 },
358 { 59526017, 193911 },
359 { 60129666, 194352 },
360 { 60737774, 194793 },
361 { 61350361, 195235 },
362 { 61967446, 195677 },
363 { 62589050, 196118 },
364 { 63215194, 196560 },
365 { 63845897, 197002 },
366 { 64481179, 197444 },
367 { 65121061, 197886 },
368 { 65765563, 198328 },
369 { 66414705, 198770 },
370 { 67068508, 199213 },
371 { 67726992, 199655 },
372 { 68390177, 200098 },
373 { 69058085, 200540 },
374 { 69730735, 200983 },
375 { 70408147, 201426 },
376 { 71090343, 201869 },
377 { 71777343, 202312 },
378 { 72469168, 202755 },
379 { 73165837, 203199 },
380 { 73867373, 203642 },
381 { 74573795, 204086 },
382 { 75285124, 204529 },
383 { 76001380, 204973 },
384 { 76722586, 205417 },
385 { 77448761, 205861 },
386 { 78179926, 206306 },
387 { 78916102, 206750 },
388 { 79657310, 207194 },
389 { 80403571, 207639 },
390 { 81154906, 208084 },
391 { 81911335, 208529 },
392 { 82672880, 208974 },
393 { 83439562, 209419 },
394 { 84211402, 209864 },
395 { 84988421, 210309 },
396 { 85770640, 210755 },
397 { 86558080, 211201 },
398 { 87350762, 211647 },
399 { 88148708, 212093 },
400 { 88951938, 212539 },
401 { 89760475, 212985 },
402 { 90574339, 213432 },
403 { 91393551, 213878 },
404 { 92218133, 214325 },
405 { 93048107, 214772 },
406 { 93883493, 215219 },
407 { 94724314, 215666 },
408 { 95570590, 216114 },
409 { 96422343, 216561 },
410 { 97279594, 217009 },
411 { 98142366, 217457 },
412 { 99010679, 217905 },
413 { 99884556, 218353 },
414 { 100764018, 218801 },
415 { 101649086, 219250 },
416 { 102539782, 219698 },
417 { 103436128, 220147 },
418 { 104338146, 220596 },
419 { 105245857, 221046 },
420 { 106159284, 221495 },
421 { 107078448, 221945 },
422 { 108003370, 222394 },
423 { 108934074, 222844 },
424 { 109870580, 223294 },
425 { 110812910, 223745 },
426 { 111761087, 224195 },
427 { 112715133, 224646 },
428 { 113675069, 225097 },
429 { 114640918, 225548 },
430 { 115612702, 225999 },
431 { 116590442, 226450 },
432 { 117574162, 226902 },
433 { 118563882, 227353 },
434 { 119559626, 227805 },
435 { 120561415, 228258 },
436 { 121569272, 228710 },
437 { 122583219, 229162 },
438 { 123603278, 229615 },
439 { 124629471, 230068 },
440 { 125661822, 230521 },
441 { 126700352, 230974 },
442 { 127745083, 231428 },
443 { 128796039, 231882 },
444 { 129853241, 232336 },
445 { 130916713, 232790 },
446 { 131986475, 233244 },
447 { 133062553, 233699 },
448 { 134144966, 234153 },
449 { 135233739, 234608 },
450 { 136328894, 235064 },
451 { 137430453, 235519 },
452 { 138538440, 235975 },
453 { 139652876, 236430 },
454 { 140773786, 236886 },
455 { 141901190, 237343 },
456 { 143035113, 237799 },
457 { 144175576, 238256 },
458 { 145322604, 238713 },
459 { 146476218, 239170 },
460 { 147636442, 239627 },
461 { 148803298, 240085 },
462 { 149976809, 240542 },
463 { 151156999, 241000 },
464 { 152343890, 241459 },
465 { 153537506, 241917 },
466 { 154737869, 242376 },
467 { 155945002, 242835 },
468 { 157158929, 243294 },
469 { 158379673, 243753 },
470 { 159607257, 244213 },
471 { 160841704, 244673 },
472 { 162083037, 245133 },
473 { 163331279, 245593 },
474 { 164586455, 246054 },
475 { 165848586, 246514 },
476 { 167117696, 246975 },
477 { 168393810, 247437 },
478 { 169676949, 247898 },
479 { 170967138, 248360 },
480 { 172264399, 248822 },
481 { 173568757, 249284 },
482 { 174880235, 249747 },
483 { 176198856, 250209 },
484 { 177524643, 250672 },
485 { 178857621, 251136 },
486 { 180197813, 251599 },
487 { 181545242, 252063 },
488 { 182899933, 252527 },
489 { 184261908, 252991 },
490 { 185631191, 253456 },
491 { 187007807, 253920 },
492 { 188391778, 254385 },
493 { 189783129, 254851 },
494 { 191181884, 255316 },
495 { 192588065, 255782 },
496 { 194001698, 256248 },
497 { 195422805, 256714 },
498 { 196851411, 257181 },
499 { 198287540, 257648 },
500 { 199731215, 258115 },
501 { 201182461, 258582 },
502 { 202641302, 259050 },
503 { 204107760, 259518 },
504 { 205581862, 259986 },
505 { 207063630, 260454 },
506 { 208553088, 260923 },
507 { 210050262, 261392 },
508 { 211555174, 261861 },
509 { 213067849, 262331 },
510 { 214588312, 262800 },
511 { 216116586, 263270 },
512 { 217652696, 263741 },
513 { 219196666, 264211 },
514 { 220748520, 264682 },
515 { 222308282, 265153 },
516 { 223875978, 265625 },
517 { 225451630, 266097 },
518 { 227035265, 266569 },
519 { 228626905, 267041 },
520 { 230226576, 267514 },
521 { 231834302, 267986 },
522 { 233450107, 268460 },
523 { 235074016, 268933 },
524 { 236706054, 269407 },
525 { 238346244, 269881 },
526 { 239994613, 270355 },
527 { 241651183, 270830 },
528 { 243315981, 271305 }
529};
530
531/* Calculate the send rate as per section 3.1 of RFC3448
532
533Returns send rate in bytes per second
534
535Integer maths and lookups are used as not allowed floating point in kernel
536
537The function for Xcalc as per section 3.1 of RFC3448 is:
538
539X = s
540 -------------------------------------------------------------
541 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
542
543where
544X is the trasmit rate in bytes/second
545s is the packet size in bytes
546R is the round trip time in seconds
547p is the loss event rate, between 0 and 1.0, of the number of loss events
548 as a fraction of the number of packets transmitted
549t_RTO is the TCP retransmission timeout value in seconds
550b is the number of packets acknowledged by a single TCP acknowledgement
551
552we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
553
554X = s
555 -----------------------------------------------------------------------
556 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
557
558
559which we can break down into:
560
561X = s
562 --------
563 R * f(p)
564
565where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
566
567Function parameters:
568s - bytes
569R - RTT in usecs
570p - loss rate (decimal fraction multiplied by 1,000,000)
571
572Returns Xcalc in bytes per second
573
574DON'T alter this code unless you run test cases against it as the code
575has been manipulated to stop underflow/overlow.
576
577*/
578u32 tfrc_calc_x(u16 s, u32 R, u32 p)
579{
580 int index;
581 u32 f;
582 u64 tmp1, tmp2;
583
584 if (p < TFRC_CALC_X_SPLIT)
585 index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
586 else
587 index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
588
589 if (index < 0)
590 /* p should be 0 unless there is a bug in my code */
591 index = 0;
592
593 if (R == 0)
594 R = 1; /* RTT can't be zero or else divide by zero */
595
596 BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
597
598 if (p >= TFRC_CALC_X_SPLIT)
599 f = tfrc_calc_x_lookup[index][0];
600 else
601 f = tfrc_calc_x_lookup[index][1];
602
603 tmp1 = ((u64)s * 100000000);
604 tmp2 = ((u64)R * (u64)f);
605 do_div(tmp2, 10000);
606 do_div(tmp1, tmp2);
607 /* Don't alter above math unless you test due to overflow on 32 bit */
608
609 return (u32)tmp1;
610}
611
612EXPORT_SYMBOL_GPL(tfrc_calc_x);
613
614/*
615 * args: fvalue - function value to match
616 * returns: p closest to that value
617 *
618 * both fvalue and p are multiplied by 1,000,000 to use ints
619 */
620u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
621{
622 int ctr = 0;
623 int small;
624
625 if (fvalue < tfrc_calc_x_lookup[0][1])
626 return 0;
627
628 if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
629 small = 1;
630 else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
631 return 1000000;
632 else
633 small = 0;
634
635 while (fvalue > tfrc_calc_x_lookup[ctr][small])
636 ctr++;
637
638 if (small)
639 return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
640 else
641 return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
642}
643
644EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-28 19:07:13 -0500