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