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