]> git.proxmox.com Git - mirror_ubuntu-hirsute-kernel.git/blob - net/dccp/ccids/ccid3.c
projects / mirror_ubuntu-hirsute-kernel.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
[DCCP]: Initial implementation
[mirror_ubuntu-hirsute-kernel.git] / net / dccp / ccids / ccid3.c
1 /*
2 * net/dccp/ccids/ccid3.c
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 "../ccid.h"
38 #include "../dccp.h"
39 #include "ccid3.h"
40
41 #ifdef CCID3_DEBUG
42 extern int ccid3_debug;
43
44 #define ccid3_pr_debug(format, a...) \
45 do { if (ccid3_debug) \
46 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
47 } while (0)
48 #else
49 #define ccid3_pr_debug(format, a...)
50 #endif
51
52 #define TFRC_MIN_PACKET_SIZE 16
53 #define TFRC_STD_PACKET_SIZE 256
54 #define TFRC_MAX_PACKET_SIZE 65535
55
56 #define USEC_IN_SEC 1000000
57
58 #define TFRC_INITIAL_TIMEOUT (2 * USEC_IN_SEC)
59 /* two seconds as per CCID3 spec 11 */
60
61 #define TFRC_OPSYS_HALF_TIME_GRAN (USEC_IN_SEC / (2 * HZ))
62 /* above is in usecs - half the scheduling granularity as per RFC3448 4.6 */
63
64 #define TFRC_WIN_COUNT_PER_RTT 4
65 #define TFRC_WIN_COUNT_LIMIT 16
66
67 #define TFRC_MAX_BACK_OFF_TIME 64
68 /* above is in seconds */
69
70 #define TFRC_SMALLEST_P 40
71
72 #define TFRC_RECV_IVAL_F_LENGTH 8 /* length(w[]) */
73
74 /* Number of later packets received before one is considered lost */
75 #define TFRC_RECV_NUM_LATE_LOSS 3
76
77 enum ccid3_options {
78 TFRC_OPT_LOSS_EVENT_RATE = 192,
79 TFRC_OPT_LOSS_INTERVALS = 193,
80 TFRC_OPT_RECEIVE_RATE = 194,
81 };
82
83 static int ccid3_debug;
84
85 static kmem_cache_t *ccid3_tx_hist_slab;
86 static kmem_cache_t *ccid3_rx_hist_slab;
87 static kmem_cache_t *ccid3_loss_interval_hist_slab;
88
89 static inline struct ccid3_tx_hist_entry *ccid3_tx_hist_entry_new(int prio)
90 {
91 struct ccid3_tx_hist_entry *entry = kmem_cache_alloc(ccid3_tx_hist_slab, prio);
92
93 if (entry != NULL)
94 entry->ccid3htx_sent = 0;
95
96 return entry;
97 }
98
99 static inline void ccid3_tx_hist_entry_delete(struct ccid3_tx_hist_entry *entry)
100 {
101 if (entry != NULL)
102 kmem_cache_free(ccid3_tx_hist_slab, entry);
103 }
104
105 static inline struct ccid3_rx_hist_entry *ccid3_rx_hist_entry_new(struct sock *sk,
106 struct sk_buff *skb,
107 int prio)
108 {
109 struct ccid3_rx_hist_entry *entry = kmem_cache_alloc(ccid3_rx_hist_slab, prio);
110
111 if (entry != NULL) {
112 const struct dccp_hdr *dh = dccp_hdr(skb);
113
114 entry->ccid3hrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
115 entry->ccid3hrx_win_count = dh->dccph_ccval;
116 entry->ccid3hrx_type = dh->dccph_type;
117 entry->ccid3hrx_ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp;
118 do_gettimeofday(&(entry->ccid3hrx_tstamp));
119 }
120
121 return entry;
122 }
123
124 static inline void ccid3_rx_hist_entry_delete(struct ccid3_rx_hist_entry *entry)
125 {
126 if (entry != NULL)
127 kmem_cache_free(ccid3_rx_hist_slab, entry);
128 }
129
130 static void ccid3_rx_history_delete(struct list_head *hist)
131 {
132 struct ccid3_rx_hist_entry *entry, *next;
133
134 list_for_each_entry_safe(entry, next, hist, ccid3hrx_node) {
135 list_del_init(&entry->ccid3hrx_node);
136 kmem_cache_free(ccid3_rx_hist_slab, entry);
137 }
138 }
139
140 static inline struct ccid3_loss_interval_hist_entry *ccid3_loss_interval_hist_entry_new(int prio)
141 {
142 return kmem_cache_alloc(ccid3_loss_interval_hist_slab, prio);
143 }
144
145 static inline void ccid3_loss_interval_hist_entry_delete(struct ccid3_loss_interval_hist_entry *entry)
146 {
147 if (entry != NULL)
148 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
149 }
150
151 static void ccid3_loss_interval_history_delete(struct list_head *hist)
152 {
153 struct ccid3_loss_interval_hist_entry *entry, *next;
154
155 list_for_each_entry_safe(entry, next, hist, ccid3lih_node) {
156 list_del_init(&entry->ccid3lih_node);
157 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
158 }
159 }
160
161 static int ccid3_init(struct sock *sk)
162 {
163 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
164 return 0;
165 }
166
167 static void ccid3_exit(struct sock *sk)
168 {
169 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
170 }
171
172 /* TFRC sender states */
173 enum ccid3_hc_tx_states {
174 TFRC_SSTATE_NO_SENT = 1,
175 TFRC_SSTATE_NO_FBACK,
176 TFRC_SSTATE_FBACK,
177 TFRC_SSTATE_TERM,
178 };
179
180 #ifdef CCID3_DEBUG
181 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
182 {
183 static char *ccid3_state_names[] = {
184 [TFRC_SSTATE_NO_SENT] = "NO_SENT",
185 [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
186 [TFRC_SSTATE_FBACK] = "FBACK",
187 [TFRC_SSTATE_TERM] = "TERM",
188 };
189
190 return ccid3_state_names[state];
191 }
192 #endif
193
194 static inline void ccid3_hc_tx_set_state(struct sock *sk, enum ccid3_hc_tx_states state)
195 {
196 struct dccp_sock *dp = dccp_sk(sk);
197 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
198 enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
199
200 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
201 dccp_role(sk), sk, ccid3_tx_state_name(oldstate), ccid3_tx_state_name(state));
202 WARN_ON(state == oldstate);
203 hctx->ccid3hctx_state = state;
204 }
205
206 static void timeval_sub(struct timeval large, struct timeval small, struct timeval *result) {
207
208 result->tv_sec = large.tv_sec-small.tv_sec;
209 if (large.tv_usec < small.tv_usec) {
210 (result->tv_sec)--;
211 result->tv_usec = USEC_IN_SEC+large.tv_usec-small.tv_usec;
212 } else
213 result->tv_usec = large.tv_usec-small.tv_usec;
214 }
215
216 static inline void timeval_fix(struct timeval *tv) {
217 if (tv->tv_usec >= USEC_IN_SEC) {
218 tv->tv_sec++;
219 tv->tv_usec -= USEC_IN_SEC;
220 }
221 }
222
223 /* returns the difference in usecs between timeval passed in and current time */
224 static inline u32 now_delta(struct timeval tv) {
225 struct timeval now;
226
227 do_gettimeofday(&now);
228 return ((now.tv_sec-tv.tv_sec)*1000000+now.tv_usec-tv.tv_usec);
229 }
230
231 #define CALCX_ARRSIZE 500
232
233 #define CALCX_SPLIT 50000
234 /* equivalent to 0.05 */
235
236 static const u32 calcx_lookup[CALCX_ARRSIZE][2] = {
237 { 37172 , 8172 },
238 { 53499 , 11567 },
239 { 66664 , 14180 },
240 { 78298 , 16388 },
241 { 89021 , 18339 },
242 { 99147 , 20108 },
243 { 108858 , 21738 },
244 { 118273 , 23260 },
245 { 127474 , 24693 },
246 { 136520 , 26052 },
247 { 145456 , 27348 },
248 { 154316 , 28589 },
249 { 163130 , 29783 },
250 { 171919 , 30935 },
251 { 180704 , 32049 },
252 { 189502 , 33130 },
253 { 198328 , 34180 },
254 { 207194 , 35202 },
255 { 216114 , 36198 },
256 { 225097 , 37172 },
257 { 234153 , 38123 },
258 { 243294 , 39055 },
259 { 252527 , 39968 },
260 { 261861 , 40864 },
261 { 271305 , 41743 },
262 { 280866 , 42607 },
263 { 290553 , 43457 },
264 { 300372 , 44293 },
265 { 310333 , 45117 },
266 { 320441 , 45929 },
267 { 330705 , 46729 },
268 { 341131 , 47518 },
269 { 351728 , 48297 },
270 { 362501 , 49066 },
271 { 373460 , 49826 },
272 { 384609 , 50577 },
273 { 395958 , 51320 },
274 { 407513 , 52054 },
275 { 419281 , 52780 },
276 { 431270 , 53499 },
277 { 443487 , 54211 },
278 { 455940 , 54916 },
279 { 468635 , 55614 },
280 { 481581 , 56306 },
281 { 494785 , 56991 },
282 { 508254 , 57671 },
283 { 521996 , 58345 },
284 { 536019 , 59014 },
285 { 550331 , 59677 },
286 { 564939 , 60335 },
287 { 579851 , 60988 },
288 { 595075 , 61636 },
289 { 610619 , 62279 },
290 { 626491 , 62918 },
291 { 642700 , 63553 },
292 { 659253 , 64183 },
293 { 676158 , 64809 },
294 { 693424 , 65431 },
295 { 711060 , 66050 },
296 { 729073 , 66664 },
297 { 747472 , 67275 },
298 { 766266 , 67882 },
299 { 785464 , 68486 },
300 { 805073 , 69087 },
301 { 825103 , 69684 },
302 { 845562 , 70278 },
303 { 866460 , 70868 },
304 { 887805 , 71456 },
305 { 909606 , 72041 },
306 { 931873 , 72623 },
307 { 954614 , 73202 },
308 { 977839 , 73778 },
309 { 1001557 , 74352 },
310 { 1025777 , 74923 },
311 { 1050508 , 75492 },
312 { 1075761 , 76058 },
313 { 1101544 , 76621 },
314 { 1127867 , 77183 },
315 { 1154739 , 77741 },
316 { 1182172 , 78298 },
317 { 1210173 , 78852 },
318 { 1238753 , 79405 },
319 { 1267922 , 79955 },
320 { 1297689 , 80503 },
321 { 1328066 , 81049 },
322 { 1359060 , 81593 },
323 { 1390684 , 82135 },
324 { 1422947 , 82675 },
325 { 1455859 , 83213 },
326 { 1489430 , 83750 },
327 { 1523671 , 84284 },
328 { 1558593 , 84817 },
329 { 1594205 , 85348 },
330 { 1630518 , 85878 },
331 { 1667543 , 86406 },
332 { 1705290 , 86932 },
333 { 1743770 , 87457 },
334 { 1782994 , 87980 },
335 { 1822973 , 88501 },
336 { 1863717 , 89021 },
337 { 1905237 , 89540 },
338 { 1947545 , 90057 },
339 { 1990650 , 90573 },
340 { 2034566 , 91087 },
341 { 2079301 , 91600 },
342 { 2124869 , 92111 },
343 { 2171279 , 92622 },
344 { 2218543 , 93131 },
345 { 2266673 , 93639 },
346 { 2315680 , 94145 },
347 { 2365575 , 94650 },
348 { 2416371 , 95154 },
349 { 2468077 , 95657 },
350 { 2520707 , 96159 },
351 { 2574271 , 96660 },
352 { 2628782 , 97159 },
353 { 2684250 , 97658 },
354 { 2740689 , 98155 },
355 { 2798110 , 98651 },
356 { 2856524 , 99147 },
357 { 2915944 , 99641 },
358 { 2976382 , 100134 },
359 { 3037850 , 100626 },
360 { 3100360 , 101117 },
361 { 3163924 , 101608 },
362 { 3228554 , 102097 },
363 { 3294263 , 102586 },
364 { 3361063 , 103073 },
365 { 3428966 , 103560 },
366 { 3497984 , 104045 },
367 { 3568131 , 104530 },
368 { 3639419 , 105014 },
369 { 3711860 , 105498 },
370 { 3785467 , 105980 },
371 { 3860253 , 106462 },
372 { 3936229 , 106942 },
373 { 4013410 , 107422 },
374 { 4091808 , 107902 },
375 { 4171435 , 108380 },
376 { 4252306 , 108858 },
377 { 4334431 , 109335 },
378 { 4417825 , 109811 },
379 { 4502501 , 110287 },
380 { 4588472 , 110762 },
381 { 4675750 , 111236 },
382 { 4764349 , 111709 },
383 { 4854283 , 112182 },
384 { 4945564 , 112654 },
385 { 5038206 , 113126 },
386 { 5132223 , 113597 },
387 { 5227627 , 114067 },
388 { 5324432 , 114537 },
389 { 5422652 , 115006 },
390 { 5522299 , 115474 },
391 { 5623389 , 115942 },
392 { 5725934 , 116409 },
393 { 5829948 , 116876 },
394 { 5935446 , 117342 },
395 { 6042439 , 117808 },
396 { 6150943 , 118273 },
397 { 6260972 , 118738 },
398 { 6372538 , 119202 },
399 { 6485657 , 119665 },
400 { 6600342 , 120128 },
401 { 6716607 , 120591 },
402 { 6834467 , 121053 },
403 { 6953935 , 121514 },
404 { 7075025 , 121976 },
405 { 7197752 , 122436 },
406 { 7322131 , 122896 },
407 { 7448175 , 123356 },
408 { 7575898 , 123815 },
409 { 7705316 , 124274 },
410 { 7836442 , 124733 },
411 { 7969291 , 125191 },
412 { 8103877 , 125648 },
413 { 8240216 , 126105 },
414 { 8378321 , 126562 },
415 { 8518208 , 127018 },
416 { 8659890 , 127474 },
417 { 8803384 , 127930 },
418 { 8948702 , 128385 },
419 { 9095861 , 128840 },
420 { 9244875 , 129294 },
421 { 9395760 , 129748 },
422 { 9548529 , 130202 },
423 { 9703198 , 130655 },
424 { 9859782 , 131108 },
425 { 10018296 , 131561 },
426 { 10178755 , 132014 },
427 { 10341174 , 132466 },
428 { 10505569 , 132917 },
429 { 10671954 , 133369 },
430 { 10840345 , 133820 },
431 { 11010757 , 134271 },
432 { 11183206 , 134721 },
433 { 11357706 , 135171 },
434 { 11534274 , 135621 },
435 { 11712924 , 136071 },
436 { 11893673 , 136520 },
437 { 12076536 , 136969 },
438 { 12261527 , 137418 },
439 { 12448664 , 137867 },
440 { 12637961 , 138315 },
441 { 12829435 , 138763 },
442 { 13023101 , 139211 },
443 { 13218974 , 139658 },
444 { 13417071 , 140106 },
445 { 13617407 , 140553 },
446 { 13819999 , 140999 },
447 { 14024862 , 141446 },
448 { 14232012 , 141892 },
449 { 14441465 , 142339 },
450 { 14653238 , 142785 },
451 { 14867346 , 143230 },
452 { 15083805 , 143676 },
453 { 15302632 , 144121 },
454 { 15523842 , 144566 },
455 { 15747453 , 145011 },
456 { 15973479 , 145456 },
457 { 16201939 , 145900 },
458 { 16432847 , 146345 },
459 { 16666221 , 146789 },
460 { 16902076 , 147233 },
461 { 17140429 , 147677 },
462 { 17381297 , 148121 },
463 { 17624696 , 148564 },
464 { 17870643 , 149007 },
465 { 18119154 , 149451 },
466 { 18370247 , 149894 },
467 { 18623936 , 150336 },
468 { 18880241 , 150779 },
469 { 19139176 , 151222 },
470 { 19400759 , 151664 },
471 { 19665007 , 152107 },
472 { 19931936 , 152549 },
473 { 20201564 , 152991 },
474 { 20473907 , 153433 },
475 { 20748982 , 153875 },
476 { 21026807 , 154316 },
477 { 21307399 , 154758 },
478 { 21590773 , 155199 },
479 { 21876949 , 155641 },
480 { 22165941 , 156082 },
481 { 22457769 , 156523 },
482 { 22752449 , 156964 },
483 { 23049999 , 157405 },
484 { 23350435 , 157846 },
485 { 23653774 , 158287 },
486 { 23960036 , 158727 },
487 { 24269236 , 159168 },
488 { 24581392 , 159608 },
489 { 24896521 , 160049 },
490 { 25214642 , 160489 },
491 { 25535772 , 160929 },
492 { 25859927 , 161370 },
493 { 26187127 , 161810 },
494 { 26517388 , 162250 },
495 { 26850728 , 162690 },
496 { 27187165 , 163130 },
497 { 27526716 , 163569 },
498 { 27869400 , 164009 },
499 { 28215234 , 164449 },
500 { 28564236 , 164889 },
501 { 28916423 , 165328 },
502 { 29271815 , 165768 },
503 { 29630428 , 166208 },
504 { 29992281 , 166647 },
505 { 30357392 , 167087 },
506 { 30725779 , 167526 },
507 { 31097459 , 167965 },
508 { 31472452 , 168405 },
509 { 31850774 , 168844 },
510 { 32232445 , 169283 },
511 { 32617482 , 169723 },
512 { 33005904 , 170162 },
513 { 33397730 , 170601 },
514 { 33792976 , 171041 },
515 { 34191663 , 171480 },
516 { 34593807 , 171919 },
517 { 34999428 , 172358 },
518 { 35408544 , 172797 },
519 { 35821174 , 173237 },
520 { 36237335 , 173676 },
521 { 36657047 , 174115 },
522 { 37080329 , 174554 },
523 { 37507197 , 174993 },
524 { 37937673 , 175433 },
525 { 38371773 , 175872 },
526 { 38809517 , 176311 },
527 { 39250924 , 176750 },
528 { 39696012 , 177190 },
529 { 40144800 , 177629 },
530 { 40597308 , 178068 },
531 { 41053553 , 178507 },
532 { 41513554 , 178947 },
533 { 41977332 , 179386 },
534 { 42444904 , 179825 },
535 { 42916290 , 180265 },
536 { 43391509 , 180704 },
537 { 43870579 , 181144 },
538 { 44353520 , 181583 },
539 { 44840352 , 182023 },
540 { 45331092 , 182462 },
541 { 45825761 , 182902 },
542 { 46324378 , 183342 },
543 { 46826961 , 183781 },
544 { 47333531 , 184221 },
545 { 47844106 , 184661 },
546 { 48358706 , 185101 },
547 { 48877350 , 185541 },
548 { 49400058 , 185981 },
549 { 49926849 , 186421 },
550 { 50457743 , 186861 },
551 { 50992759 , 187301 },
552 { 51531916 , 187741 },
553 { 52075235 , 188181 },
554 { 52622735 , 188622 },
555 { 53174435 , 189062 },
556 { 53730355 , 189502 },
557 { 54290515 , 189943 },
558 { 54854935 , 190383 },
559 { 55423634 , 190824 },
560 { 55996633 , 191265 },
561 { 56573950 , 191706 },
562 { 57155606 , 192146 },
563 { 57741621 , 192587 },
564 { 58332014 , 193028 },
565 { 58926806 , 193470 },
566 { 59526017 , 193911 },
567 { 60129666 , 194352 },
568 { 60737774 , 194793 },
569 { 61350361 , 195235 },
570 { 61967446 , 195677 },
571 { 62589050 , 196118 },
572 { 63215194 , 196560 },
573 { 63845897 , 197002 },
574 { 64481179 , 197444 },
575 { 65121061 , 197886 },
576 { 65765563 , 198328 },
577 { 66414705 , 198770 },
578 { 67068508 , 199213 },
579 { 67726992 , 199655 },
580 { 68390177 , 200098 },
581 { 69058085 , 200540 },
582 { 69730735 , 200983 },
583 { 70408147 , 201426 },
584 { 71090343 , 201869 },
585 { 71777343 , 202312 },
586 { 72469168 , 202755 },
587 { 73165837 , 203199 },
588 { 73867373 , 203642 },
589 { 74573795 , 204086 },
590 { 75285124 , 204529 },
591 { 76001380 , 204973 },
592 { 76722586 , 205417 },
593 { 77448761 , 205861 },
594 { 78179926 , 206306 },
595 { 78916102 , 206750 },
596 { 79657310 , 207194 },
597 { 80403571 , 207639 },
598 { 81154906 , 208084 },
599 { 81911335 , 208529 },
600 { 82672880 , 208974 },
601 { 83439562 , 209419 },
602 { 84211402 , 209864 },
603 { 84988421 , 210309 },
604 { 85770640 , 210755 },
605 { 86558080 , 211201 },
606 { 87350762 , 211647 },
607 { 88148708 , 212093 },
608 { 88951938 , 212539 },
609 { 89760475 , 212985 },
610 { 90574339 , 213432 },
611 { 91393551 , 213878 },
612 { 92218133 , 214325 },
613 { 93048107 , 214772 },
614 { 93883493 , 215219 },
615 { 94724314 , 215666 },
616 { 95570590 , 216114 },
617 { 96422343 , 216561 },
618 { 97279594 , 217009 },
619 { 98142366 , 217457 },
620 { 99010679 , 217905 },
621 { 99884556 , 218353 },
622 { 100764018 , 218801 },
623 { 101649086 , 219250 },
624 { 102539782 , 219698 },
625 { 103436128 , 220147 },
626 { 104338146 , 220596 },
627 { 105245857 , 221046 },
628 { 106159284 , 221495 },
629 { 107078448 , 221945 },
630 { 108003370 , 222394 },
631 { 108934074 , 222844 },
632 { 109870580 , 223294 },
633 { 110812910 , 223745 },
634 { 111761087 , 224195 },
635 { 112715133 , 224646 },
636 { 113675069 , 225097 },
637 { 114640918 , 225548 },
638 { 115612702 , 225999 },
639 { 116590442 , 226450 },
640 { 117574162 , 226902 },
641 { 118563882 , 227353 },
642 { 119559626 , 227805 },
643 { 120561415 , 228258 },
644 { 121569272 , 228710 },
645 { 122583219 , 229162 },
646 { 123603278 , 229615 },
647 { 124629471 , 230068 },
648 { 125661822 , 230521 },
649 { 126700352 , 230974 },
650 { 127745083 , 231428 },
651 { 128796039 , 231882 },
652 { 129853241 , 232336 },
653 { 130916713 , 232790 },
654 { 131986475 , 233244 },
655 { 133062553 , 233699 },
656 { 134144966 , 234153 },
657 { 135233739 , 234608 },
658 { 136328894 , 235064 },
659 { 137430453 , 235519 },
660 { 138538440 , 235975 },
661 { 139652876 , 236430 },
662 { 140773786 , 236886 },
663 { 141901190 , 237343 },
664 { 143035113 , 237799 },
665 { 144175576 , 238256 },
666 { 145322604 , 238713 },
667 { 146476218 , 239170 },
668 { 147636442 , 239627 },
669 { 148803298 , 240085 },
670 { 149976809 , 240542 },
671 { 151156999 , 241000 },
672 { 152343890 , 241459 },
673 { 153537506 , 241917 },
674 { 154737869 , 242376 },
675 { 155945002 , 242835 },
676 { 157158929 , 243294 },
677 { 158379673 , 243753 },
678 { 159607257 , 244213 },
679 { 160841704 , 244673 },
680 { 162083037 , 245133 },
681 { 163331279 , 245593 },
682 { 164586455 , 246054 },
683 { 165848586 , 246514 },
684 { 167117696 , 246975 },
685 { 168393810 , 247437 },
686 { 169676949 , 247898 },
687 { 170967138 , 248360 },
688 { 172264399 , 248822 },
689 { 173568757 , 249284 },
690 { 174880235 , 249747 },
691 { 176198856 , 250209 },
692 { 177524643 , 250672 },
693 { 178857621 , 251136 },
694 { 180197813 , 251599 },
695 { 181545242 , 252063 },
696 { 182899933 , 252527 },
697 { 184261908 , 252991 },
698 { 185631191 , 253456 },
699 { 187007807 , 253920 },
700 { 188391778 , 254385 },
701 { 189783129 , 254851 },
702 { 191181884 , 255316 },
703 { 192588065 , 255782 },
704 { 194001698 , 256248 },
705 { 195422805 , 256714 },
706 { 196851411 , 257181 },
707 { 198287540 , 257648 },
708 { 199731215 , 258115 },
709 { 201182461 , 258582 },
710 { 202641302 , 259050 },
711 { 204107760 , 259518 },
712 { 205581862 , 259986 },
713 { 207063630 , 260454 },
714 { 208553088 , 260923 },
715 { 210050262 , 261392 },
716 { 211555174 , 261861 },
717 { 213067849 , 262331 },
718 { 214588312 , 262800 },
719 { 216116586 , 263270 },
720 { 217652696 , 263741 },
721 { 219196666 , 264211 },
722 { 220748520 , 264682 },
723 { 222308282 , 265153 },
724 { 223875978 , 265625 },
725 { 225451630 , 266097 },
726 { 227035265 , 266569 },
727 { 228626905 , 267041 },
728 { 230226576 , 267514 },
729 { 231834302 , 267986 },
730 { 233450107 , 268460 },
731 { 235074016 , 268933 },
732 { 236706054 , 269407 },
733 { 238346244 , 269881 },
734 { 239994613 , 270355 },
735 { 241651183 , 270830 },
736 { 243315981 , 271305 }
737 };
738
739 /* Calculate the send rate as per section 3.1 of RFC3448
740
741 Returns send rate in bytes per second
742
743 Integer maths and lookups are used as not allowed floating point in kernel
744
745 The function for Xcalc as per section 3.1 of RFC3448 is:
746
747 X = s
748 -------------------------------------------------------------
749 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
750
751 where
752 X is the trasmit rate in bytes/second
753 s is the packet size in bytes
754 R is the round trip time in seconds
755 p is the loss event rate, between 0 and 1.0, of the number of loss events
756 as a fraction of the number of packets transmitted
757 t_RTO is the TCP retransmission timeout value in seconds
758 b is the number of packets acknowledged by a single TCP acknowledgement
759
760 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
761
762 X = s
763 -----------------------------------------------------------------------
764 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
765
766
767 which we can break down into:
768
769 X = s
770 --------
771 R * f(p)
772
773 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
774
775 Function parameters:
776 s - bytes
777 R - RTT in usecs
778 p - loss rate (decimal fraction multiplied by 1,000,000)
779
780 Returns Xcalc in bytes per second
781
782 DON'T alter this code unless you run test cases against it as the code
783 has been manipulated to stop underflow/overlow.
784
785 */
786 static u32 ccid3_calc_x(u16 s, u32 R, u32 p)
787 {
788 int index;
789 u32 f;
790 u64 tmp1, tmp2;
791
792 if (p < CALCX_SPLIT)
793 index = (p / (CALCX_SPLIT / CALCX_ARRSIZE)) - 1;
794 else
795 index = (p / (1000000 / CALCX_ARRSIZE)) - 1;
796
797 if (index < 0)
798 /* p should be 0 unless there is a bug in my code */
799 index = 0;
800
801 if (R == 0)
802 R = 1; /* RTT can't be zero or else divide by zero */
803
804 BUG_ON(index >= CALCX_ARRSIZE);
805
806 if (p >= CALCX_SPLIT)
807 f = calcx_lookup[index][0];
808 else
809 f = calcx_lookup[index][1];
810
811 tmp1 = ((u64)s * 100000000);
812 tmp2 = ((u64)R * (u64)f);
813 do_div(tmp2,10000);
814 do_div(tmp1,tmp2);
815 /* don't alter above math unless you test due to overflow on 32 bit */
816
817 return (u32)tmp1;
818 }
819
820 /* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */
821 static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx)
822 {
823 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK)
824 return;
825 /* if no feedback spec says t_ipi is 1 second (set elsewhere and then
826 * doubles after every no feedback timer (separate function) */
827
828 if (hctx->ccid3hctx_x < 10) {
829 ccid3_pr_debug("ccid3_calc_new_t_ipi - ccid3hctx_x < 10\n");
830 hctx->ccid3hctx_x = 10;
831 }
832 hctx->ccid3hctx_t_ipi = (hctx->ccid3hctx_s * 100000)
833 / (hctx->ccid3hctx_x / 10);
834 /* reason for above maths with 10 in there is to avoid 32 bit
835 * overflow for jumbo packets */
836
837 }
838
839 /* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
840 static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx)
841 {
842 hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2, TFRC_OPSYS_HALF_TIME_GRAN);
843
844 }
845
846 /*
847 * Update X by
848 * If (p > 0)
849 * x_calc = calcX(s, R, p);
850 * X = max(min(X_calc, 2 * X_recv), s / t_mbi);
851 * Else
852 * If (now - tld >= R)
853 * X = max(min(2 * X, 2 * X_recv), s / R);
854 * tld = now;
855 */
856 static void ccid3_hc_tx_update_x(struct sock *sk)
857 {
858 struct dccp_sock *dp = dccp_sk(sk);
859 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
860
861 if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) { /* to avoid large error in calcX */
862 hctx->ccid3hctx_x_calc = ccid3_calc_x(hctx->ccid3hctx_s,
863 hctx->ccid3hctx_rtt,
864 hctx->ccid3hctx_p);
865 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc, 2 * hctx->ccid3hctx_x_recv),
866 hctx->ccid3hctx_s / TFRC_MAX_BACK_OFF_TIME);
867 } else if (now_delta(hctx->ccid3hctx_t_ld) >= hctx->ccid3hctx_rtt) {
868 u32 rtt = hctx->ccid3hctx_rtt;
869 if (rtt < 10) {
870 rtt = 10;
871 } /* avoid divide by zero below */
872
873 hctx->ccid3hctx_x = max_t(u32, min_t(u32, 2 * hctx->ccid3hctx_x_recv, 2 * hctx->ccid3hctx_x),
874 (hctx->ccid3hctx_s * 100000) / (rtt / 10));
875 /* Using 100000 and 10 to avoid 32 bit overflow for jumbo frames */
876 do_gettimeofday(&hctx->ccid3hctx_t_ld);
877 }
878
879 if (hctx->ccid3hctx_x == 0) {
880 ccid3_pr_debug("ccid3hctx_x = 0!\n");
881 hctx->ccid3hctx_x = 1;
882 }
883 }
884
885 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
886 {
887 struct sock *sk = (struct sock *)data;
888 struct dccp_sock *dp = dccp_sk(sk);
889 unsigned long next_tmout = 0;
890 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
891 u32 rtt;
892
893 bh_lock_sock(sk);
894 if (sock_owned_by_user(sk)) {
895 /* Try again later. */
896 /* XXX: set some sensible MIB */
897 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, jiffies + HZ / 5);
898 goto out;
899 }
900
901 ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
902 ccid3_tx_state_name(hctx->ccid3hctx_state));
903
904 if (hctx->ccid3hctx_x < 10) {
905 ccid3_pr_debug("TFRC_SSTATE_NO_FBACK ccid3hctx_x < 10\n");
906 hctx->ccid3hctx_x = 10;
907 }
908
909 switch (hctx->ccid3hctx_state) {
910 case TFRC_SSTATE_TERM:
911 goto out;
912 case TFRC_SSTATE_NO_FBACK:
913 /* Halve send rate */
914 hctx->ccid3hctx_x /= 2;
915 if (hctx->ccid3hctx_x < (hctx->ccid3hctx_s / TFRC_MAX_BACK_OFF_TIME))
916 hctx->ccid3hctx_x = hctx->ccid3hctx_s / TFRC_MAX_BACK_OFF_TIME;
917
918 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d bytes/s\n",
919 dccp_role(sk), sk, ccid3_tx_state_name(hctx->ccid3hctx_state),
920 hctx->ccid3hctx_x);
921 next_tmout = max_t(u32, 2 * (hctx->ccid3hctx_s * 100000)
922 / (hctx->ccid3hctx_x / 10), TFRC_INITIAL_TIMEOUT);
923 /* do above maths with 100000 and 10 to prevent overflow on 32 bit */
924 /* FIXME - not sure above calculation is correct. See section 5 of CCID3 11
925 * should adjust tx_t_ipi and double that to achieve it really */
926 break;
927 case TFRC_SSTATE_FBACK:
928 /* Check if IDLE since last timeout and recv rate is less than 4 packets per RTT */
929 rtt = hctx->ccid3hctx_rtt;
930 if (rtt < 10)
931 rtt = 10;
932 /* stop divide by zero below */
933 if (!hctx->ccid3hctx_idle || (hctx->ccid3hctx_x_recv >=
934 4 * (hctx->ccid3hctx_s * 100000) / (rtt / 10))) {
935 ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n", dccp_role(sk), sk,
936 ccid3_tx_state_name(hctx->ccid3hctx_state));
937 /* Halve sending rate */
938
939 /* If (X_calc > 2 * X_recv)
940 * X_recv = max(X_recv / 2, s / (2 * t_mbi));
941 * Else
942 * X_recv = X_calc / 4;
943 */
944 BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P && hctx->ccid3hctx_x_calc == 0);
945
946 /* check also if p is zero -> x_calc is infinity? */
947 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P ||
948 hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv)
949 hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2,
950 hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME));
951 else
952 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
953
954 /* Update sending rate */
955 ccid3_hc_tx_update_x(sk);
956 }
957 if (hctx->ccid3hctx_x == 0) {
958 ccid3_pr_debug("TFRC_SSTATE_FBACK ccid3hctx_x = 0!\n");
959 hctx->ccid3hctx_x = 10;
960 }
961 /* Schedule no feedback timer to expire in max(4 * R, 2 * s / X) */
962 next_tmout = max_t(u32, inet_csk(sk)->icsk_rto,
963 2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x / 10));
964 break;
965 default:
966 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
967 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
968 dump_stack();
969 goto out;
970 }
971
972 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
973 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
974 hctx->ccid3hctx_idle = 1;
975 out:
976 bh_unlock_sock(sk);
977 sock_put(sk);
978 }
979
980 static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb,
981 int len, long *delay)
982 {
983 struct dccp_sock *dp = dccp_sk(sk);
984 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
985 struct ccid3_tx_hist_entry *new_packet = NULL;
986 struct timeval now;
987 int rc = -ENOTCONN;
988
989 // ccid3_pr_debug("%s, sk=%p, skb=%p, len=%d\n", dccp_role(sk), sk, skb, len);
990 /*
991 * check if pure ACK or Terminating */
992 /* XXX: We only call this function for DATA and DATAACK, on, these packets can have
993 * zero length, but why the comment about "pure ACK"?
994 */
995 if (hctx == NULL || len == 0 || hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
996 goto out;
997
998 /* See if last packet allocated was not sent */
999 if (!list_empty(&hctx->ccid3hctx_hist))
1000 new_packet = list_entry(hctx->ccid3hctx_hist.next,
1001 struct ccid3_tx_hist_entry, ccid3htx_node);
1002
1003 if (new_packet == NULL || new_packet->ccid3htx_sent) {
1004 new_packet = ccid3_tx_hist_entry_new(SLAB_ATOMIC);
1005
1006 rc = -ENOBUFS;
1007 if (new_packet == NULL) {
1008 ccid3_pr_debug("%s, sk=%p, not enough mem to add "
1009 "to history, send refused\n", dccp_role(sk), sk);
1010 goto out;
1011 }
1012
1013 list_add(&new_packet->ccid3htx_node, &hctx->ccid3hctx_hist);
1014 }
1015
1016 do_gettimeofday(&now);
1017
1018 switch (hctx->ccid3hctx_state) {
1019 case TFRC_SSTATE_NO_SENT:
1020 ccid3_pr_debug("%s, sk=%p, first packet(%llu)\n", dccp_role(sk), sk,
1021 dp->dccps_gss);
1022
1023 hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer;
1024 hctx->ccid3hctx_no_feedback_timer.data = (unsigned long)sk;
1025 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT));
1026 hctx->ccid3hctx_last_win_count = 0;
1027 hctx->ccid3hctx_t_last_win_count = now;
1028 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
1029 hctx->ccid3hctx_t_ipi = TFRC_INITIAL_TIMEOUT;
1030
1031 /* Set nominal send time for initial packet */
1032 hctx->ccid3hctx_t_nom = now;
1033 (hctx->ccid3hctx_t_nom).tv_usec += hctx->ccid3hctx_t_ipi;
1034 timeval_fix(&(hctx->ccid3hctx_t_nom));
1035 ccid3_calc_new_delta(hctx);
1036 rc = 0;
1037 break;
1038 case TFRC_SSTATE_NO_FBACK:
1039 case TFRC_SSTATE_FBACK:
1040 *delay = (now_delta(hctx->ccid3hctx_t_nom) - hctx->ccid3hctx_delta);
1041 ccid3_pr_debug("send_packet delay=%ld\n",*delay);
1042 *delay /= -1000;
1043 /* divide by -1000 is to convert to ms and get sign right */
1044 rc = *delay > 0 ? -EAGAIN : 0;
1045 break;
1046 default:
1047 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1048 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1049 dump_stack();
1050 rc = -EINVAL;
1051 break;
1052 }
1053
1054 /* Can we send? if so add options and add to packet history */
1055 if (rc == 0)
1056 new_packet->ccid3htx_win_count = DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1057 out:
1058 return rc;
1059 }
1060
1061 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
1062 {
1063 struct dccp_sock *dp = dccp_sk(sk);
1064 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1065 struct ccid3_tx_hist_entry *packet = NULL;
1066 struct timeval now;
1067
1068 // ccid3_pr_debug("%s, sk=%p, more=%d, len=%d\n", dccp_role(sk), sk, more, len);
1069 BUG_ON(hctx == NULL);
1070
1071 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1072 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
1073 dccp_role(sk), sk);
1074 return;
1075 }
1076
1077 do_gettimeofday(&now);
1078
1079 /* check if we have sent a data packet */
1080 if (len > 0) {
1081 unsigned long quarter_rtt;
1082
1083 if (list_empty(&hctx->ccid3hctx_hist)) {
1084 printk(KERN_CRIT "%s: packet doesn't exists in history!\n", __FUNCTION__);
1085 return;
1086 }
1087 packet = list_entry(hctx->ccid3hctx_hist.next, struct ccid3_tx_hist_entry, ccid3htx_node);
1088 if (packet->ccid3htx_sent) {
1089 printk(KERN_CRIT "%s: no unsent packet in history!\n", __FUNCTION__);
1090 return;
1091 }
1092 packet->ccid3htx_tstamp = now;
1093 packet->ccid3htx_seqno = dp->dccps_gss;
1094 // ccid3_pr_debug("%s, sk=%p, seqno=%llu inserted!\n", dccp_role(sk), sk, packet->ccid3htx_seqno);
1095
1096 /*
1097 * Check if win_count have changed */
1098 /* COMPLIANCE_BEGIN
1099 * Algorithm in "8.1. Window Counter Valuer" in draft-ietf-dccp-ccid3-11.txt
1100 */
1101 quarter_rtt = now_delta(hctx->ccid3hctx_t_last_win_count) / (hctx->ccid3hctx_rtt / 4);
1102 if (quarter_rtt > 0) {
1103 hctx->ccid3hctx_t_last_win_count = now;
1104 hctx->ccid3hctx_last_win_count = (hctx->ccid3hctx_last_win_count +
1105 min_t(unsigned long, quarter_rtt, 5)) % 16;
1106 ccid3_pr_debug("%s, sk=%p, window changed from %u to %u!\n",
1107 dccp_role(sk), sk,
1108 packet->ccid3htx_win_count,
1109 hctx->ccid3hctx_last_win_count);
1110 }
1111 /* COMPLIANCE_END */
1112 #if 0
1113 ccid3_pr_debug("%s, sk=%p, packet sent (%llu,%u)\n",
1114 dccp_role(sk), sk,
1115 packet->ccid3htx_seqno,
1116 packet->ccid3htx_win_count);
1117 #endif
1118 hctx->ccid3hctx_idle = 0;
1119 packet->ccid3htx_sent = 1;
1120 } else
1121 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1122 dccp_role(sk), sk, dp->dccps_gss);
1123
1124 switch (hctx->ccid3hctx_state) {
1125 case TFRC_SSTATE_NO_SENT:
1126 /* if first wasn't pure ack */
1127 if (len != 0)
1128 printk(KERN_CRIT "%s: %s, First packet sent is noted as a data packet\n",
1129 __FUNCTION__, dccp_role(sk));
1130 return;
1131 case TFRC_SSTATE_NO_FBACK:
1132 case TFRC_SSTATE_FBACK:
1133 if (len > 0) {
1134 hctx->ccid3hctx_t_nom = now;
1135 ccid3_calc_new_t_ipi(hctx);
1136 ccid3_calc_new_delta(hctx);
1137 (hctx->ccid3hctx_t_nom).tv_usec += hctx->ccid3hctx_t_ipi;
1138 timeval_fix(&(hctx->ccid3hctx_t_nom));
1139 }
1140 break;
1141 default:
1142 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1143 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1144 dump_stack();
1145 break;
1146 }
1147 }
1148
1149 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1150 {
1151 struct dccp_sock *dp = dccp_sk(sk);
1152 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1153 struct ccid3_options_received *opt_recv;
1154 struct ccid3_tx_hist_entry *entry, *next, *packet;
1155 unsigned long next_tmout;
1156 u16 t_elapsed;
1157 u32 pinv;
1158 u32 x_recv;
1159 u32 r_sample;
1160 #if 0
1161 ccid3_pr_debug("%s, sk=%p(%s), skb=%p(%s)\n",
1162 dccp_role(sk), sk, dccp_state_name(sk->sk_state),
1163 skb, dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1164 #endif
1165 if (hctx == NULL)
1166 return;
1167
1168 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1169 ccid3_pr_debug("%s, sk=%p, received a packet when terminating!\n", dccp_role(sk), sk);
1170 return;
1171 }
1172
1173 /* we are only interested in ACKs */
1174 if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
1175 DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
1176 return;
1177
1178 opt_recv = &hctx->ccid3hctx_options_received;
1179
1180 t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
1181 x_recv = opt_recv->ccid3or_receive_rate;
1182 pinv = opt_recv->ccid3or_loss_event_rate;
1183
1184 switch (hctx->ccid3hctx_state) {
1185 case TFRC_SSTATE_NO_SENT:
1186 /* FIXME: what to do here? */
1187 return;
1188 case TFRC_SSTATE_NO_FBACK:
1189 case TFRC_SSTATE_FBACK:
1190 /* Calculate new round trip sample by
1191 * R_sample = (now - t_recvdata) - t_delay */
1192 /* get t_recvdata from history */
1193 packet = NULL;
1194 list_for_each_entry_safe(entry, next, &hctx->ccid3hctx_hist, ccid3htx_node)
1195 if (entry->ccid3htx_seqno == DCCP_SKB_CB(skb)->dccpd_ack_seq) {
1196 packet = entry;
1197 break;
1198 }
1199
1200 if (packet == NULL) {
1201 ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't exist in history!\n",
1202 dccp_role(sk), sk, DCCP_SKB_CB(skb)->dccpd_ack_seq,
1203 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1204 return;
1205 }
1206
1207 /* Update RTT */
1208 r_sample = now_delta(packet->ccid3htx_tstamp);
1209 /* FIXME: */
1210 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1211
1212 /* Update RTT estimate by
1213 * If (No feedback recv)
1214 * R = R_sample;
1215 * Else
1216 * R = q * R + (1 - q) * R_sample;
1217 *
1218 * q is a constant, RFC 3448 recomments 0.9
1219 */
1220 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
1221 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
1222 hctx->ccid3hctx_rtt = r_sample;
1223 } else
1224 hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 + r_sample / 10;
1225
1226 /*
1227 * XXX: this is to avoid a division by zero in ccid3_hc_tx_packet_sent
1228 * implemention of the new window count.
1229 */
1230 if (hctx->ccid3hctx_rtt < 4)
1231 hctx->ccid3hctx_rtt = 4;
1232
1233 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, r_sample=%us\n",
1234 dccp_role(sk), sk,
1235 hctx->ccid3hctx_rtt,
1236 r_sample);
1237
1238 /* Update timeout interval */
1239 inet_csk(sk)->icsk_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt, USEC_IN_SEC);
1240
1241 /* Update receive rate */
1242 hctx->ccid3hctx_x_recv = x_recv; /* x_recv in bytes per second */
1243
1244 /* Update loss event rate */
1245 if (pinv == ~0 || pinv == 0)
1246 hctx->ccid3hctx_p = 0;
1247 else {
1248 hctx->ccid3hctx_p = 1000000 / pinv;
1249
1250 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
1251 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
1252 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n", dccp_role(sk), sk);
1253 }
1254 }
1255
1256 /* unschedule no feedback timer */
1257 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1258
1259 /* Update sending rate */
1260 ccid3_hc_tx_update_x(sk);
1261
1262 /* Update next send time */
1263 if (hctx->ccid3hctx_t_ipi > (hctx->ccid3hctx_t_nom).tv_usec) {
1264 (hctx->ccid3hctx_t_nom).tv_usec += USEC_IN_SEC;
1265 (hctx->ccid3hctx_t_nom).tv_sec--;
1266 }
1267 /* FIXME - if no feedback then t_ipi can go > 1 second */
1268 (hctx->ccid3hctx_t_nom).tv_usec -= hctx->ccid3hctx_t_ipi;
1269 ccid3_calc_new_t_ipi(hctx);
1270 (hctx->ccid3hctx_t_nom).tv_usec += hctx->ccid3hctx_t_ipi;
1271 timeval_fix(&(hctx->ccid3hctx_t_nom));
1272 ccid3_calc_new_delta(hctx);
1273
1274 /* remove all packets older than the one acked from history */
1275 #if 0
1276 FIXME!
1277 list_for_each_entry_safe_continue(entry, next, &hctx->ccid3hctx_hist, ccid3htx_node) {
1278 list_del_init(&entry->ccid3htx_node);
1279 ccid3_tx_hist_entry_delete(entry);
1280 }
1281 #endif
1282 if (hctx->ccid3hctx_x < 10) {
1283 ccid3_pr_debug("ccid3_hc_tx_packet_recv hctx->ccid3hctx_x < 10\n");
1284 hctx->ccid3hctx_x = 10;
1285 }
1286 /* to prevent divide by zero below */
1287
1288 /* Schedule no feedback timer to expire in max(4 * R, 2 * s / X) */
1289 next_tmout = max(inet_csk(sk)->icsk_rto,
1290 2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x/10));
1291 /* maths with 100000 and 10 is to prevent overflow with 32 bit */
1292
1293 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to expire in %lu jiffies (%luus)\n",
1294 dccp_role(sk), sk, usecs_to_jiffies(next_tmout), next_tmout);
1295
1296 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1297 jiffies + max_t(u32,1,usecs_to_jiffies(next_tmout)));
1298
1299 /* set idle flag */
1300 hctx->ccid3hctx_idle = 1;
1301 break;
1302 default:
1303 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1304 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1305 dump_stack();
1306 break;
1307 }
1308 }
1309
1310 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1311 {
1312 const struct dccp_sock *dp = dccp_sk(sk);
1313 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1314
1315 if (hctx == NULL || !(sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN))
1316 return;
1317
1318 DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1319 }
1320
1321 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1322 unsigned char len, u16 idx, unsigned char *value)
1323 {
1324 int rc = 0;
1325 struct dccp_sock *dp = dccp_sk(sk);
1326 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1327 struct ccid3_options_received *opt_recv;
1328
1329 if (hctx == NULL)
1330 return 0;
1331
1332 opt_recv = &hctx->ccid3hctx_options_received;
1333
1334 if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
1335 opt_recv->ccid3or_seqno = dp->dccps_gsr;
1336 opt_recv->ccid3or_loss_event_rate = ~0;
1337 opt_recv->ccid3or_loss_intervals_idx = 0;
1338 opt_recv->ccid3or_loss_intervals_len = 0;
1339 opt_recv->ccid3or_receive_rate = 0;
1340 }
1341
1342 switch (option) {
1343 case TFRC_OPT_LOSS_EVENT_RATE:
1344 if (len != 4) {
1345 ccid3_pr_debug("%s, sk=%p, invalid len for TFRC_OPT_LOSS_EVENT_RATE\n",
1346 dccp_role(sk), sk);
1347 rc = -EINVAL;
1348 } else {
1349 opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1350 ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1351 dccp_role(sk), sk,
1352 opt_recv->ccid3or_loss_event_rate);
1353 }
1354 break;
1355 case TFRC_OPT_LOSS_INTERVALS:
1356 opt_recv->ccid3or_loss_intervals_idx = idx;
1357 opt_recv->ccid3or_loss_intervals_len = len;
1358 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
1359 dccp_role(sk), sk,
1360 opt_recv->ccid3or_loss_intervals_idx,
1361 opt_recv->ccid3or_loss_intervals_len);
1362 break;
1363 case TFRC_OPT_RECEIVE_RATE:
1364 if (len != 4) {
1365 ccid3_pr_debug("%s, sk=%p, invalid len for TFRC_OPT_RECEIVE_RATE\n",
1366 dccp_role(sk), sk);
1367 rc = -EINVAL;
1368 } else {
1369 opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1370 ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1371 dccp_role(sk), sk,
1372 opt_recv->ccid3or_receive_rate);
1373 }
1374 break;
1375 }
1376
1377 return rc;
1378 }
1379
1380 static int ccid3_hc_tx_init(struct sock *sk)
1381 {
1382 struct dccp_sock *dp = dccp_sk(sk);
1383 struct ccid3_hc_tx_sock *hctx;
1384
1385 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1386
1387 hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx), gfp_any());
1388 if (hctx == NULL)
1389 return -ENOMEM;
1390
1391 memset(hctx, 0, sizeof(*hctx));
1392
1393 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1394 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1395 hctx->ccid3hctx_s = (u16)dp->dccps_avg_packet_size;
1396 else
1397 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1398
1399 hctx->ccid3hctx_x = hctx->ccid3hctx_s; /* set transmission rate to 1 packet per second */
1400 hctx->ccid3hctx_rtt = 4; /* See ccid3_hc_tx_packet_sent win_count calculatation */
1401 inet_csk(sk)->icsk_rto = USEC_IN_SEC;
1402 hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
1403 INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
1404 init_timer(&hctx->ccid3hctx_no_feedback_timer);
1405
1406 return 0;
1407 }
1408
1409 static void ccid3_hc_tx_exit(struct sock *sk)
1410 {
1411 struct dccp_sock *dp = dccp_sk(sk);
1412 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1413 struct ccid3_tx_hist_entry *entry, *next;
1414
1415 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1416 BUG_ON(hctx == NULL);
1417
1418 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1419 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1420
1421 /* Empty packet history */
1422 list_for_each_entry_safe(entry, next, &hctx->ccid3hctx_hist, ccid3htx_node) {
1423 list_del_init(&entry->ccid3htx_node);
1424 ccid3_tx_hist_entry_delete(entry);
1425 }
1426
1427 kfree(dp->dccps_hc_tx_ccid_private);
1428 dp->dccps_hc_tx_ccid_private = NULL;
1429 }
1430
1431 /*
1432 * RX Half Connection methods
1433 */
1434
1435 /* TFRC receiver states */
1436 enum ccid3_hc_rx_states {
1437 TFRC_RSTATE_NO_DATA = 1,
1438 TFRC_RSTATE_DATA,
1439 TFRC_RSTATE_TERM = 127,
1440 };
1441
1442 #ifdef CCID3_DEBUG
1443 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1444 {
1445 static char *ccid3_rx_state_names[] = {
1446 [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1447 [TFRC_RSTATE_DATA] = "DATA",
1448 [TFRC_RSTATE_TERM] = "TERM",
1449 };
1450
1451 return ccid3_rx_state_names[state];
1452 }
1453 #endif
1454
1455 static inline void ccid3_hc_rx_set_state(struct sock *sk, enum ccid3_hc_rx_states state)
1456 {
1457 struct dccp_sock *dp = dccp_sk(sk);
1458 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1459 enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
1460
1461 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
1462 dccp_role(sk), sk, ccid3_rx_state_name(oldstate), ccid3_rx_state_name(state));
1463 WARN_ON(state == oldstate);
1464 hcrx->ccid3hcrx_state = state;
1465 }
1466
1467 static int ccid3_hc_rx_add_hist(struct sock *sk, struct ccid3_rx_hist_entry *packet)
1468 {
1469 struct dccp_sock *dp = dccp_sk(sk);
1470 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1471 struct ccid3_rx_hist_entry *entry, *next;
1472 u8 num_later = 0;
1473
1474 if (list_empty(&hcrx->ccid3hcrx_hist))
1475 list_add(&packet->ccid3hrx_node, &hcrx->ccid3hcrx_hist);
1476 else {
1477 u64 seqno = packet->ccid3hrx_seqno;
1478 struct ccid3_rx_hist_entry *iter = list_entry(hcrx->ccid3hcrx_hist.next,
1479 struct ccid3_rx_hist_entry,
1480 ccid3hrx_node);
1481 if (after48(seqno, iter->ccid3hrx_seqno))
1482 list_add(&packet->ccid3hrx_node, &hcrx->ccid3hcrx_hist);
1483 else {
1484 if (iter->ccid3hrx_type == DCCP_PKT_DATA ||
1485 iter->ccid3hrx_type == DCCP_PKT_DATAACK)
1486 num_later = 1;
1487
1488 list_for_each_entry_continue(iter, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1489 if (after48(seqno, iter->ccid3hrx_seqno)) {
1490 list_add(&packet->ccid3hrx_node, &iter->ccid3hrx_node);
1491 goto trim_history;
1492 }
1493
1494 if (iter->ccid3hrx_type == DCCP_PKT_DATA ||
1495 iter->ccid3hrx_type == DCCP_PKT_DATAACK)
1496 num_later++;
1497
1498 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1499 ccid3_rx_hist_entry_delete(packet);
1500 ccid3_pr_debug("%s, sk=%p, packet(%llu) already lost!\n",
1501 dccp_role(sk), sk, seqno);
1502 return 1;
1503 }
1504 }
1505
1506 if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1507 list_add_tail(&packet->ccid3hrx_node, &hcrx->ccid3hcrx_hist);
1508 /* FIXME: else what? should we destroy the packet like above? */
1509 }
1510 }
1511
1512 trim_history:
1513 /* Trim history (remove all packets after the NUM_LATE_LOSS + 1 data packets) */
1514 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1515
1516 if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1517 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1518 if (num_later == 0) {
1519 list_del_init(&entry->ccid3hrx_node);
1520 ccid3_rx_hist_entry_delete(entry);
1521 } else if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1522 entry->ccid3hrx_type == DCCP_PKT_DATAACK)
1523 --num_later;
1524 }
1525 } else {
1526 int step = 0;
1527 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1528 int tmp;
1529 /*
1530 * We have no loss interval history so we need at least one
1531 * rtt:s of data packets to approximate rtt.
1532 */
1533 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1534 if (num_later == 0) {
1535 switch (step) {
1536 case 0:
1537 step = 1;
1538 /* OK, find next data packet */
1539 num_later = 1;
1540 break;
1541 case 1:
1542 step = 2;
1543 /* OK, find next data packet */
1544 num_later = 1;
1545 win_count = entry->ccid3hrx_win_count;
1546 break;
1547 case 2:
1548 tmp = win_count - entry->ccid3hrx_win_count;
1549 if (tmp < 0)
1550 tmp += TFRC_WIN_COUNT_LIMIT;
1551 if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1552 /* we have found a packet older than one rtt
1553 * remove the rest */
1554 step = 3;
1555 } else /* OK, find next data packet */
1556 num_later = 1;
1557 break;
1558 case 3:
1559 list_del_init(&entry->ccid3hrx_node);
1560 ccid3_rx_hist_entry_delete(entry);
1561 break;
1562 }
1563 } else if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1564 entry->ccid3hrx_type == DCCP_PKT_DATAACK)
1565 --num_later;
1566 }
1567 }
1568
1569 return 0;
1570 }
1571
1572 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1573 {
1574 struct dccp_sock *dp = dccp_sk(sk);
1575 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1576 struct ccid3_rx_hist_entry *entry, *packet;
1577
1578 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1579
1580 switch (hcrx->ccid3hcrx_state) {
1581 case TFRC_RSTATE_NO_DATA:
1582 hcrx->ccid3hcrx_x_recv = 0;
1583 break;
1584 case TFRC_RSTATE_DATA: {
1585 u32 delta = now_delta(hcrx->ccid3hcrx_tstamp_last_feedback);
1586
1587 if (delta == 0)
1588 delta = 1; /* to prevent divide by zero */
1589 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv * USEC_IN_SEC) / delta;
1590 }
1591 break;
1592 default:
1593 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1594 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1595 dump_stack();
1596 return;
1597 }
1598
1599 packet = NULL;
1600 list_for_each_entry(entry, &hcrx->ccid3hcrx_hist, ccid3hrx_node)
1601 if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1602 entry->ccid3hrx_type == DCCP_PKT_DATAACK) {
1603 packet = entry;
1604 break;
1605 }
1606
1607 if (packet == NULL) {
1608 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
1609 __FUNCTION__, dccp_role(sk), sk);
1610 dump_stack();
1611 return;
1612 }
1613
1614 do_gettimeofday(&(hcrx->ccid3hcrx_tstamp_last_feedback));
1615 hcrx->ccid3hcrx_last_counter = packet->ccid3hrx_win_count;
1616 hcrx->ccid3hcrx_seqno_last_counter = packet->ccid3hrx_seqno;
1617 hcrx->ccid3hcrx_bytes_recv = 0;
1618
1619 /* Convert to multiples of 10us */
1620 hcrx->ccid3hcrx_elapsed_time = now_delta(packet->ccid3hrx_tstamp) / 10;
1621 if (hcrx->ccid3hcrx_p == 0)
1622 hcrx->ccid3hcrx_pinv = ~0;
1623 else
1624 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1625 dccp_send_ack(sk);
1626 }
1627
1628 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1629 {
1630 const struct dccp_sock *dp = dccp_sk(sk);
1631 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1632
1633 if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN))
1634 return;
1635
1636 if (hcrx->ccid3hcrx_elapsed_time != 0 && !dccp_packet_without_ack(skb))
1637 dccp_insert_option_elapsed_time(sk, skb, hcrx->ccid3hcrx_elapsed_time);
1638
1639 if (DCCP_SKB_CB(skb)->dccpd_type != DCCP_PKT_DATA) {
1640 const u32 x_recv = htonl(hcrx->ccid3hcrx_x_recv);
1641 const u32 pinv = htonl(hcrx->ccid3hcrx_pinv);
1642
1643 dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE, &pinv, sizeof(pinv));
1644 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE, &x_recv, sizeof(x_recv));
1645 }
1646
1647 DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1648 }
1649
1650 /* Weights used to calculate loss event rate */
1651 /*
1652 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
1653 * when we use it.
1654 */
1655 const int ccid3_hc_rx_w[TFRC_RECV_IVAL_F_LENGTH] = { 4, 4, 4, 4, 3, 2, 1, 1, };
1656
1657 /*
1658 * args: fvalue - function value to match
1659 * returns: p closest to that value
1660 *
1661 * both fvalue and p are multiplied by 1,000,000 to use ints
1662 */
1663 u32 calcx_reverse_lookup(u32 fvalue) {
1664 int ctr = 0;
1665 int small;
1666
1667 if (fvalue < calcx_lookup[0][1])
1668 return 0;
1669 if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1670 small = 1;
1671 else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1672 return 1000000;
1673 else
1674 small = 0;
1675 while (fvalue > calcx_lookup[ctr][small])
1676 ctr++;
1677 if (small)
1678 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1679 else
1680 return (1000000 * ctr / CALCX_ARRSIZE) ;
1681 }
1682
1683 /* calculate first loss interval
1684 *
1685 * returns estimated loss interval in usecs */
1686
1687 static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
1688 {
1689 struct dccp_sock *dp = dccp_sk(sk);
1690 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1691 struct ccid3_rx_hist_entry *entry, *next, *tail = NULL;
1692 u32 rtt, delta, x_recv, fval, p, tmp2;
1693 struct timeval tstamp, tmp_tv;
1694 int interval = 0;
1695 int win_count = 0;
1696 int step = 0;
1697 u64 tmp1;
1698
1699 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1700 if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1701 entry->ccid3hrx_type == DCCP_PKT_DATAACK) {
1702 tail = entry;
1703
1704 switch (step) {
1705 case 0:
1706 tstamp = entry->ccid3hrx_tstamp;
1707 win_count = entry->ccid3hrx_win_count;
1708 step = 1;
1709 break;
1710 case 1:
1711 interval = win_count - entry->ccid3hrx_win_count;
1712 if (interval < 0)
1713 interval += TFRC_WIN_COUNT_LIMIT;
1714 if (interval > 4)
1715 goto found;
1716 break;
1717 }
1718 }
1719 }
1720
1721 if (step == 0) {
1722 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no data packets!\n",
1723 __FUNCTION__, dccp_role(sk), sk);
1724 return ~0;
1725 }
1726
1727 if (interval == 0) {
1728 ccid3_pr_debug("%s, sk=%p, Could not find a win_count interval > 0. Defaulting to 1\n",
1729 dccp_role(sk), sk);
1730 interval = 1;
1731 }
1732 found:
1733 timeval_sub(tstamp,tail->ccid3hrx_tstamp,&tmp_tv);
1734 rtt = (tmp_tv.tv_sec * USEC_IN_SEC + tmp_tv.tv_usec) * 4 / interval;
1735 ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
1736 dccp_role(sk), sk, rtt);
1737 if (rtt == 0)
1738 rtt = 1;
1739
1740 delta = now_delta(hcrx->ccid3hcrx_tstamp_last_feedback);
1741 if (delta == 0)
1742 delta = 1;
1743
1744 x_recv = (hcrx->ccid3hcrx_bytes_recv * USEC_IN_SEC) / delta;
1745
1746 tmp1 = (u64)x_recv * (u64)rtt;
1747 do_div(tmp1,10000000);
1748 tmp2 = (u32)tmp1;
1749 fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
1750 /* do not alter order above or you will get overflow on 32 bit */
1751 p = calcx_reverse_lookup(fval);
1752 ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied loss rate=%u\n",\
1753 dccp_role(sk), sk, x_recv, p);
1754
1755 if (p == 0)
1756 return ~0;
1757 else
1758 return 1000000 / p;
1759 }
1760
1761 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1762 {
1763 struct dccp_sock *dp = dccp_sk(sk);
1764 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1765 struct ccid3_loss_interval_hist_entry *li_entry;
1766
1767 if (seq_loss != DCCP_MAX_SEQNO + 1) {
1768 ccid3_pr_debug("%s, sk=%p, seq_loss=%llu, win_loss=%u, packet loss detected\n",
1769 dccp_role(sk), sk, seq_loss, win_loss);
1770
1771 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1772 struct ccid3_loss_interval_hist_entry *li_tail = NULL;
1773 int i;
1774
1775 ccid3_pr_debug("%s, sk=%p, first loss event detected, creating history\n", dccp_role(sk), sk);
1776 for (i = 0; i <= TFRC_RECV_IVAL_F_LENGTH; ++i) {
1777 li_entry = ccid3_loss_interval_hist_entry_new(SLAB_ATOMIC);
1778 if (li_entry == NULL) {
1779 ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
1780 ccid3_pr_debug("%s, sk=%p, not enough mem for creating history\n",
1781 dccp_role(sk), sk);
1782 return;
1783 }
1784 if (li_tail == NULL)
1785 li_tail = li_entry;
1786 list_add(&li_entry->ccid3lih_node, &hcrx->ccid3hcrx_loss_interval_hist);
1787 }
1788
1789 li_entry->ccid3lih_seqno = seq_loss;
1790 li_entry->ccid3lih_win_count = win_loss;
1791
1792 li_tail->ccid3lih_interval = ccid3_hc_rx_calc_first_li(sk);
1793 }
1794 }
1795 /* FIXME: find end of interval */
1796 }
1797
1798 static void ccid3_hc_rx_detect_loss(struct sock *sk)
1799 {
1800 struct dccp_sock *dp = dccp_sk(sk);
1801 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1802 struct ccid3_rx_hist_entry *entry, *a_next, *b_next, *packet;
1803 struct ccid3_rx_hist_entry *a_loss = NULL;
1804 struct ccid3_rx_hist_entry *b_loss = NULL;
1805 u64 seq_loss = DCCP_MAX_SEQNO + 1;
1806 u8 win_loss = 0;
1807 u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1808
1809 list_for_each_entry_safe(entry, b_next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1810 if (num_later == 0) {
1811 b_loss = entry;
1812 break;
1813 } else if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1814 entry->ccid3hrx_type == DCCP_PKT_DATAACK)
1815 --num_later;
1816 }
1817
1818 if (b_loss == NULL)
1819 goto out_update_li;
1820
1821 a_next = b_next;
1822 num_later = 1;
1823 #if 0
1824 FIXME MERGE GIT!
1825 list_for_each_entry_safe_continue(entry, a_next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1826 if (num_later == 0) {
1827 a_loss = entry;
1828 break;
1829 } else if (entry->ccid3hrx_type == DCCP_PKT_DATA ||
1830 entry->ccid3hrx_type == DCCP_PKT_DATAACK)
1831 --num_later;
1832 }
1833 #endif
1834
1835 if (a_loss == NULL) {
1836 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1837 /* no loss event have occured yet */
1838 ccid3_pr_debug("%s, sk=%p, TODO: find a lost data "
1839 "packet by comparing to initial seqno\n",
1840 dccp_role(sk), sk);
1841 goto out_update_li;
1842 } else {
1843 pr_info("%s: %s, sk=%p, ERROR! Less than 4 data packets in history",
1844 __FUNCTION__, dccp_role(sk), sk);
1845 return;
1846 }
1847 }
1848
1849 /* Locate a lost data packet */
1850 entry = packet = b_loss;
1851 #if 0
1852 FIXME MERGE GIT!
1853 list_for_each_entry_safe_continue(entry, b_next, &hcrx->ccid3hcrx_hist, ccid3hrx_node) {
1854 u64 delta = dccp_delta_seqno(entry->ccid3hrx_seqno, packet->ccid3hrx_seqno);
1855
1856 if (delta != 0) {
1857 if (packet->ccid3hrx_type == DCCP_PKT_DATA ||
1858 packet->ccid3hrx_type == DCCP_PKT_DATAACK)
1859 --delta;
1860 /*
1861 * FIXME: check this, probably this % usage is because
1862 * in earlier drafts the ndp count was just 8 bits
1863 * long, but now it cam be up to 24 bits long.
1864 */
1865 #if 0
1866 if (delta % DCCP_NDP_LIMIT !=
1867 (packet->ccid3hrx_ndp - entry->ccid3hrx_ndp) % DCCP_NDP_LIMIT)
1868 #endif
1869 if (delta != packet->ccid3hrx_ndp - entry->ccid3hrx_ndp) {
1870 seq_loss = entry->ccid3hrx_seqno;
1871 dccp_inc_seqno(&seq_loss);
1872 }
1873 }
1874 packet = entry;
1875 if (packet == a_loss)
1876 break;
1877 }
1878 #endif
1879
1880 if (seq_loss != DCCP_MAX_SEQNO + 1)
1881 win_loss = a_loss->ccid3hrx_win_count;
1882
1883 out_update_li:
1884 ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1885 }
1886
1887 static u32 ccid3_hc_rx_calc_i_mean(struct sock *sk)
1888 {
1889 struct dccp_sock *dp = dccp_sk(sk);
1890 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1891 struct ccid3_loss_interval_hist_entry *li_entry, *li_next;
1892 int i = 0;
1893 u32 i_tot;
1894 u32 i_tot0 = 0;
1895 u32 i_tot1 = 0;
1896 u32 w_tot = 0;
1897
1898 list_for_each_entry_safe(li_entry, li_next, &hcrx->ccid3hcrx_loss_interval_hist, ccid3lih_node) {
1899 if (i < TFRC_RECV_IVAL_F_LENGTH) {
1900 i_tot0 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i];
1901 w_tot += ccid3_hc_rx_w[i];
1902 }
1903
1904 if (i != 0)
1905 i_tot1 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i - 1];
1906
1907 if (++i > TFRC_RECV_IVAL_F_LENGTH)
1908 break;
1909 }
1910
1911 if (i != TFRC_RECV_IVAL_F_LENGTH) {
1912 pr_info("%s: %s, sk=%p, ERROR! Missing entry in interval history!\n",
1913 __FUNCTION__, dccp_role(sk), sk);
1914 return 0;
1915 }
1916
1917 i_tot = max(i_tot0, i_tot1);
1918
1919 /* FIXME: Why do we do this? -Ian McDonald */
1920 if (i_tot * 4 < w_tot)
1921 i_tot = w_tot * 4;
1922
1923 return i_tot * 4 / w_tot;
1924 }
1925
1926 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1927 {
1928 struct dccp_sock *dp = dccp_sk(sk);
1929 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1930 struct ccid3_rx_hist_entry *packet;
1931 struct timeval now;
1932 u8 win_count;
1933 u32 p_prev;
1934 int ins;
1935 #if 0
1936 ccid3_pr_debug("%s, sk=%p(%s), skb=%p(%s)\n",
1937 dccp_role(sk), sk, dccp_state_name(sk->sk_state),
1938 skb, dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1939 #endif
1940 if (hcrx == NULL)
1941 return;
1942
1943 BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
1944 hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
1945
1946 switch (DCCP_SKB_CB(skb)->dccpd_type) {
1947 case DCCP_PKT_ACK:
1948 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1949 return;
1950 case DCCP_PKT_DATAACK:
1951 if (dp->dccps_options_received.dccpor_timestamp_echo == 0)
1952 break;
1953 p_prev = hcrx->ccid3hcrx_rtt;
1954 do_gettimeofday(&now);
1955 /* hcrx->ccid3hcrx_rtt = now - dp->dccps_options_received.dccpor_timestamp_echo -
1956 usecs_to_jiffies(dp->dccps_options_received.dccpor_elapsed_time * 10);
1957 FIXME - I think above code is broken - have to look at options more, will also need
1958 to fix pr_debug below */
1959 if (p_prev != hcrx->ccid3hcrx_rtt)
1960 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%lu jiffies, tstamp_echo=%u, elapsed time=%u\n",
1961 dccp_role(sk), sk, hcrx->ccid3hcrx_rtt,
1962 dp->dccps_options_received.dccpor_timestamp_echo,
1963 dp->dccps_options_received.dccpor_elapsed_time);
1964 break;
1965 case DCCP_PKT_DATA:
1966 break;
1967 default:
1968 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1969 dccp_role(sk), sk,
1970 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1971 return;
1972 }
1973
1974 packet = ccid3_rx_hist_entry_new(sk, skb, SLAB_ATOMIC);
1975 if (packet == NULL) {
1976 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet to history (consider it lost)!",
1977 dccp_role(sk), sk);
1978 return;
1979 }
1980
1981 win_count = packet->ccid3hrx_win_count;
1982
1983 ins = ccid3_hc_rx_add_hist(sk, packet);
1984
1985 if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1986 return;
1987
1988 switch (hcrx->ccid3hcrx_state) {
1989 case TFRC_RSTATE_NO_DATA:
1990 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial feedback\n",
1991 dccp_role(sk), sk, dccp_state_name(sk->sk_state), skb);
1992 ccid3_hc_rx_send_feedback(sk);
1993 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
1994 return;
1995 case TFRC_RSTATE_DATA:
1996 hcrx->ccid3hcrx_bytes_recv += skb->len - dccp_hdr(skb)->dccph_doff * 4;
1997 if (ins == 0) {
1998 do_gettimeofday(&now);
1999 if ((now_delta(hcrx->ccid3hcrx_tstamp_last_ack)) >= hcrx->ccid3hcrx_rtt) {
2000 hcrx->ccid3hcrx_tstamp_last_ack = now;
2001 ccid3_hc_rx_send_feedback(sk);
2002 }
2003 return;
2004 }
2005 break;
2006 default:
2007 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
2008 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
2009 dump_stack();
2010 return;
2011 }
2012
2013 /* Dealing with packet loss */
2014 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, data loss! Reacting...\n",
2015 dccp_role(sk), sk, dccp_state_name(sk->sk_state), skb);
2016
2017 ccid3_hc_rx_detect_loss(sk);
2018 p_prev = hcrx->ccid3hcrx_p;
2019
2020 /* Calculate loss event rate */
2021 if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist))
2022 /* Scaling up by 1000000 as fixed decimal */
2023 hcrx->ccid3hcrx_p = 1000000 / ccid3_hc_rx_calc_i_mean(sk);
2024
2025 if (hcrx->ccid3hcrx_p > p_prev) {
2026 ccid3_hc_rx_send_feedback(sk);
2027 return;
2028 }
2029 }
2030
2031 static int ccid3_hc_rx_init(struct sock *sk)
2032 {
2033 struct dccp_sock *dp = dccp_sk(sk);
2034 struct ccid3_hc_rx_sock *hcrx;
2035
2036 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2037
2038 hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx), gfp_any());
2039 if (hcrx == NULL)
2040 return -ENOMEM;
2041
2042 memset(hcrx, 0, sizeof(*hcrx));
2043
2044 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
2045 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
2046 hcrx->ccid3hcrx_s = (u16)dp->dccps_avg_packet_size;
2047 else
2048 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
2049
2050 hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
2051 INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
2052 INIT_LIST_HEAD(&hcrx->ccid3hcrx_loss_interval_hist);
2053
2054 return 0;
2055 }
2056
2057 static void ccid3_hc_rx_exit(struct sock *sk)
2058 {
2059 struct dccp_sock *dp = dccp_sk(sk);
2060 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2061
2062 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2063
2064 if (hcrx == NULL)
2065 return;
2066
2067 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
2068
2069 /* Empty packet history */
2070 ccid3_rx_history_delete(&hcrx->ccid3hcrx_hist);
2071
2072 /* Empty loss interval history */
2073 ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
2074
2075 kfree(dp->dccps_hc_rx_ccid_private);
2076 dp->dccps_hc_rx_ccid_private = NULL;
2077 }
2078
2079 static struct ccid ccid3 = {
2080 .ccid_id = 3,
2081 .ccid_name = "ccid3",
2082 .ccid_owner = THIS_MODULE,
2083 .ccid_init = ccid3_init,
2084 .ccid_exit = ccid3_exit,
2085 .ccid_hc_tx_init = ccid3_hc_tx_init,
2086 .ccid_hc_tx_exit = ccid3_hc_tx_exit,
2087 .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet,
2088 .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent,
2089 .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv,
2090 .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
2091 .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options,
2092 .ccid_hc_rx_init = ccid3_hc_rx_init,
2093 .ccid_hc_rx_exit = ccid3_hc_rx_exit,
2094 .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
2095 .ccid_hc_rx_packet_recv = ccid3_hc_rx_packet_recv,
2096 };
2097
2098 module_param(ccid3_debug, int, 0444);
2099 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
2100
2101 static __init int ccid3_module_init(void)
2102 {
2103 int rc = -ENOMEM;
2104
2105 ccid3_tx_hist_slab = kmem_cache_create("dccp_ccid3_tx_history",
2106 sizeof(struct ccid3_tx_hist_entry), 0,
2107 SLAB_HWCACHE_ALIGN, NULL, NULL);
2108 if (ccid3_tx_hist_slab == NULL)
2109 goto out;
2110
2111 ccid3_rx_hist_slab = kmem_cache_create("dccp_ccid3_rx_history",
2112 sizeof(struct ccid3_rx_hist_entry), 0,
2113 SLAB_HWCACHE_ALIGN, NULL, NULL);
2114 if (ccid3_rx_hist_slab == NULL)
2115 goto out_free_tx_history;
2116
2117 ccid3_loss_interval_hist_slab = kmem_cache_create("dccp_ccid3_loss_interval_history",
2118 sizeof(struct ccid3_loss_interval_hist_entry), 0,
2119 SLAB_HWCACHE_ALIGN, NULL, NULL);
2120 if (ccid3_loss_interval_hist_slab == NULL)
2121 goto out_free_rx_history;
2122
2123 rc = ccid_register(&ccid3);
2124 if (rc != 0)
2125 goto out_free_loss_interval_history;
2126
2127 out:
2128 return rc;
2129 out_free_loss_interval_history:
2130 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2131 ccid3_loss_interval_hist_slab = NULL;
2132 out_free_rx_history:
2133 kmem_cache_destroy(ccid3_rx_hist_slab);
2134 ccid3_rx_hist_slab = NULL;
2135 out_free_tx_history:
2136 kmem_cache_destroy(ccid3_tx_hist_slab);
2137 ccid3_tx_hist_slab = NULL;
2138 goto out;
2139 }
2140 module_init(ccid3_module_init);
2141
2142 static __exit void ccid3_module_exit(void)
2143 {
2144 ccid_unregister(&ccid3);
2145
2146 if (ccid3_tx_hist_slab != NULL) {
2147 kmem_cache_destroy(ccid3_tx_hist_slab);
2148 ccid3_tx_hist_slab = NULL;
2149 }
2150 if (ccid3_rx_hist_slab != NULL) {
2151 kmem_cache_destroy(ccid3_rx_hist_slab);
2152 ccid3_rx_hist_slab = NULL;
2153 }
2154 if (ccid3_loss_interval_hist_slab != NULL) {
2155 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2156 ccid3_loss_interval_hist_slab = NULL;
2157 }
2158 }
2159 module_exit(ccid3_module_exit);
2160
2161 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz> & Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
2162 MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
2163 MODULE_LICENSE("GPL");
2164 MODULE_ALIAS("net-dccp-ccid-3");
Ubuntu Hirsute Linux kernel mirror