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