1 /* $KAME: dccp_tfrc.c,v 1.16 2006/03/01 17:34:08 nishida Exp $ */
2 /* $NetBSD: dccp_tfrc.c,v 1.4 2016/07/07 06:55:43 msaitoh Exp $ */
3
4 /*
5 * Copyright (c) 2003 Nils-Erik Mattsson
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. The name of the author may not be used to endorse or promote products
18 * derived from this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 *
31 * Id: dccp_tfrc.c,v 1.47 2003/05/28 17:36:15 nilmat-8 Exp
32 */
33
34 #include <sys/cdefs.h>
35 __KERNEL_RCSID(0, "$NetBSD: dccp_tfrc.c,v 1.4 2016/07/07 06:55:43 msaitoh Exp $");
36
37 #ifdef _KERNEL_OPT
38 #include "opt_dccp.h"
39 #endif
40
41 /*
42 * This implementation conforms to the drafts of DCCP dated Mars 2003.
43 * The options used are window counter, elapsed time, loss event rate
44 * and receive rate. No support for history discounting or oscillation
45 * prevention.
46 */
47
48 #include <sys/param.h>
49 #include <sys/systm.h>
50 #include <sys/domain.h>
51 #include <sys/kernel.h>
52 #include <sys/lock.h>
53 #include <sys/malloc.h>
54 #include <sys/mbuf.h>
55 #include <sys/proc.h>
56 #include <sys/protosw.h>
57 #include <sys/signalvar.h>
58 #include <sys/socket.h>
59 #include <sys/socketvar.h>
60 #include <sys/mutex.h>
61 #include <sys/sysctl.h>
62 #include <sys/syslog.h>
63 #include <sys/queue.h>
64 #include <sys/callout.h>
65
66 #include <net/if.h>
67
68 #include <netinet/in.h>
69 #include <netinet/in_systm.h>
70 #include <netinet/ip.h>
71
72 #include <netinet/in_pcb.h>
73 #include <netinet/in_var.h>
74 #include <netinet/ip_icmp.h>
75 #include <netinet/icmp_var.h>
76 #include <netinet/ip_var.h>
77
78 #include <netinet/dccp.h>
79 #include <netinet/dccp_var.h>
80 #include <netinet/dccp_tfrc.h>
81 #include <netinet/dccp_tfrc_lookup.h>
82
83 #define TFRCDEBUG
84 #if 0
85 #define TFRCDEBUGTIMERS
86 #define NOTFRCSENDER
87 #define NOTFRCRECV
88 #endif
89
90 #ifdef TFRCDEBUG
91 #ifdef __FreeBSD__
92 #define TFRC_DEBUG(args) log args
93 #else
94 #define TFRC_DEBUG(args) dccp_log args
95 #endif
96 #else
97 #define TFRC_DEBUG(args)
98 #endif
99
100 #ifdef TFRCDEBUGTIMERS
101 #ifdef __FreeBSD__
102 #define TFRC_DEBUG_TIME(args) log args
103 #else
104 #define TFRC_DEBUG_TIME(args) dccp_log args
105 #endif
106 #else
107 #define TFRC_DEBUG_TIME(args)
108 #endif
109
110 #if !defined(__FreeBSD__) || __FreeBSD_version < 500000
111 #define INP_INFO_LOCK_INIT(x,y)
112 #define INP_INFO_WLOCK(x)
113 #define INP_INFO_WUNLOCK(x)
114 #define INP_INFO_RLOCK(x)
115 #define INP_INFO_RUNLOCK(x)
116 #define INP_LOCK(x)
117 #define INP_UNLOCK(x)
118 #endif
119
120
121 /* Timeval operations */
122 const struct timeval delta_half = {0, TFRC_OPSYS_TIME_GRAN / 2};
123
124 /*
125 * Half time value struct (accurate to +- 0.5us)
126 * args: tvp - pointer to timeval structure
127 * Tested u:OK
128 */
129 #define HALFTIMEVAL(tvp) \
130 do { \
131 if ((tvp)->tv_sec & 1) \
132 (tvp)->tv_usec += 1000000; \
133 (tvp)->tv_sec = (tvp)->tv_sec >> 1; \
134 (tvp)->tv_usec = (tvp)->tv_usec >> 1; \
135 } while (0)
136
137 /* Sender side */
138
139 /* Calculate new t_ipi (inter packet interval) by
140 * t_ipi = s/X_inst;
141 * args: ccbp - pointer to sender ccb block
142 * Tested u:OK - Note: No check for x = 0 -> t_ipi = {0xFFF...,0xFFF}
143 */
144 #define CALCNEWTIPI(ccbp) \
145 do { \
146 struct fixpoint x1, y1; \
147 x1.num = ccbp->s; \
148 x1.denom = 1; \
149 fixpoint_div(&x1, &x1, &(ccbp)->x); \
150 y1.num = (ccbp)->t_ipi.tv_sec = fixpoint_getlong(&x1); \
151 y1.denom = 1; \
152 fixpoint_sub(&x1, &x1, &y1); \
153 y1.num = 1000000; \
154 y1.denom = 1; \
155 fixpoint_mul(&x1, &x1, &y1); \
156 (ccbp)->t_ipi.tv_usec = fixpoint_getlong(&x1); \
157 } while (0)
158
159 /* Calculate new delta by
160 * delta = min(t_ipi/2, t_gran/2);
161 * args: ccbp - pointer to sender ccb block
162 * Tested u:OK
163 */
164 #define CALCNEWDELTA(ccbp) \
165 do { \
166 (ccbp)->delta = delta_half; \
167 if ((ccbp)->t_ipi.tv_sec == 0 && \
168 (ccbp)->t_ipi.tv_usec < TFRC_OPSYS_TIME_GRAN) { \
169 (ccbp)->delta = (ccbp)->t_ipi; \
170 HALFTIMEVAL(&((ccbp)->delta)); \
171 } \
172 } while (0)
173
174 #ifdef TFRCDEBUG
175 #define PRINTFLOAT(x) TFRC_DEBUG((LOG_INFO, "%lld/%lld", (x)->num, (x)->denom));
176 #endif
177
178 const struct fixpoint tfrc_smallest_p = { 4LL, 1000000LL };
179
180 /* External declarations */
181 extern int dccp_get_option(char *, int, int, char *, int);
182
183 /* Forward declarations */
184 void tfrc_time_no_feedback(void *);
185 void tfrc_time_send(void *);
186 void tfrc_set_send_timer(struct tfrc_send_ccb *, struct timeval);
187 void tfrc_updateX(struct tfrc_send_ccb *, struct timeval);
188 const struct fixpoint *tfrc_calcX(u_int16_t, u_int32_t,
189 const struct fixpoint *);
190 void tfrc_send_term(void *);
191
192 static void normalize(long long *, long long *);
193 struct fixpoint *fixpoint_add(struct fixpoint *, const struct fixpoint *,
194 const struct fixpoint *);
195 struct fixpoint *fixpoint_sub(struct fixpoint *, const struct fixpoint *,
196 const struct fixpoint *);
197 int fixpoint_cmp(const struct fixpoint *, const struct fixpoint *);
198 struct fixpoint *fixpoint_mul(struct fixpoint *, const struct fixpoint *,
199 const struct fixpoint *);
200 struct fixpoint *fixpoint_div(struct fixpoint *, const struct fixpoint *,
201 const struct fixpoint *);
202 long fixpoint_getlong(const struct fixpoint *);
203
204 const struct fixpoint *flookup(const struct fixpoint *);
205 const struct fixpoint *tfrc_flookup_reverse(const struct fixpoint *);
206
207 /*
208 * Calculate the send rate according to TCP throughput eq.
209 * args: s - packet size (in bytes)
210 * R - Round trip time (in micro seconds)
211 * p - loss event rate (0<=p<=1)
212 * returns: calculated send rate (in bytes per second)
213 * Tested u:OK
214 */
215 __inline const struct fixpoint *
tfrc_calcX(u_int16_t s,u_int32_t r,const struct fixpoint * p)216 tfrc_calcX(u_int16_t s, u_int32_t r, const struct fixpoint *p)
217 {
218 static struct fixpoint x;
219
220 x.num = 1000000 * s;
221 x.denom = 1 * r;
222 fixpoint_div(&x, &x, p);
223 return &x;
224 }
225
226 /*
227 * Function called by the send timer (to send packet)
228 * args: cb - sender congestion control block
229 */
230 void
tfrc_time_send(void * ccb)231 tfrc_time_send(void *ccb)
232 {
233 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
234 int s;
235 /*struct inpcb *inp;*/
236
237 if (cb->state == TFRC_SSTATE_TERM) {
238 TFRC_DEBUG((LOG_INFO,
239 "TFRC - Send timer is ordered to terminate. (tfrc_time_send)\n"));
240 return;
241 }
242 if (callout_pending(&cb->ch_stimer)) {
243 TFRC_DEBUG((LOG_INFO,
244 "TFRC - Callout pending. (tfrc_time_send)\n"));
245 return;
246 }
247 /* aquire locks for dccp_output */
248 s = splsoftnet();
249 INP_INFO_RLOCK(&dccpbinfo);
250 /*inp = cb->pcb->d_inpcb;*/
251 INP_LOCK(inp);
252 INP_INFO_RUNLOCK(&dccpbinfo);
253
254 callout_stop(&cb->ch_stimer);
255
256 dccp_output(cb->pcb, 1);
257 /* make sure we schedule next send time */
258 tfrc_send_packet_sent(cb, 0, -1);
259
260 /* release locks */
261 INP_UNLOCK(inp);
262 splx(s);
263 }
264 /*
265 * Calculate and set when the send timer should expire
266 * args: cb - sender congestion control block
267 * t_now - timeval struct containing actual time
268 * Tested u:OK
269 */
270 void
tfrc_set_send_timer(struct tfrc_send_ccb * cb,struct timeval t_now)271 tfrc_set_send_timer(struct tfrc_send_ccb * cb, struct timeval t_now)
272 {
273 struct timeval t_temp;
274 long t_ticks;
275
276 /* set send timer to fire in t_ipi - (t_now-t_nom_old) or in other
277 * words after t_nom - t_now */
278 t_temp = cb->t_nom;
279 timersub(&t_temp, &t_now, &t_temp);
280
281 #ifdef TFRCDEBUG
282 if (t_temp.tv_sec < 0 || t_temp.tv_usec < 0)
283 panic("TFRC - scheduled a negative time! (tfrc_set_send_timer)");
284 #endif
285
286 t_ticks = (t_temp.tv_usec + 1000000 * t_temp.tv_sec) / (1000000 / hz);
287 if (t_ticks == 0) t_ticks = 1;
288
289 TFRC_DEBUG_TIME((LOG_INFO,
290 "TFRC scheduled send timer to expire in %ld ticks (hz=%lu)\n", t_ticks, (unsigned long)hz));
291
292 callout_reset(&cb->ch_stimer, t_ticks, tfrc_time_send, cb);
293 }
294
295 /*
296 * Update X by
297 * If (p > 0)
298 * x_calc = calcX(s,R,p);
299 * X = max(min(X_calc, 2*X_recv), s/t_mbi);
300 * Else
301 * If (t_now - tld >= R)
302 * X = max(min("2*X, 2*X_recv),s/R);
303 * tld = t_now;
304 * args: cb - sender congestion control block
305 * t_now - timeval struct containing actual time
306 * Tested u:OK
307 */
308 void
tfrc_updateX(struct tfrc_send_ccb * cb,struct timeval t_now)309 tfrc_updateX(struct tfrc_send_ccb * cb, struct timeval t_now)
310 {
311 struct fixpoint temp, temp2;
312 struct timeval t_temp, t_rtt = {0, 0};
313
314 /* to avoid large error in calcX */
315 if (fixpoint_cmp(&cb->p, &tfrc_smallest_p) >= 0) {
316 cb->x_calc = *tfrc_calcX(cb->s, cb->rtt, &cb->p);
317 temp = cb->x_recv;
318 temp.num *= 2;
319 if (fixpoint_cmp(&cb->x_calc, &temp) < 0)
320 temp = cb->x_calc;
321 cb->x = temp;
322 temp2.num = cb->s;
323 temp2.denom = TFRC_MAX_BACK_OFF_TIME;
324 if (fixpoint_cmp(&temp, &temp2) < 0)
325 cb->x = temp2;
326 normalize(&cb->x.num, &cb->x.denom);
327 TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
328 PRINTFLOAT(&cb->x);
329 TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_updateX, p>0)\n"));
330 } else {
331 t_rtt.tv_usec = cb->rtt % 1000000;
332 t_rtt.tv_sec = cb->rtt / 1000000;
333 t_temp = t_now;
334 timersub(&t_temp, &cb->t_ld, &t_temp);
335 if (timercmp(&t_temp, &t_rtt, >=)) {
336 temp = cb->x_recv;
337 temp.num *= 2;
338 temp2 = cb->x;
339 temp2.num *= 2;
340 if (fixpoint_cmp(&temp2, &temp) < 0)
341 temp = temp2;
342 cb->x.num = cb->s;
343 cb->x.denom = 1;
344 cb->x.num *= 1000000;
345 cb->x.denom *= cb->rtt;
346 if (fixpoint_cmp(&temp, &cb->x) > 0)
347 cb->x = temp;
348 normalize(&cb->x.num, &cb->x.denom);
349 cb->t_ld = t_now;
350 TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
351 PRINTFLOAT(&cb->x);
352 TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_updateX, p==0)\n"));
353 } else
354 TFRC_DEBUG((LOG_INFO, "TFRC didn't update send rate! (tfrc_updateX, p==0)\n"));
355 }
356 }
357
358 /*
359 * Function called by the no feedback timer
360 * args: cb - sender congestion control block
361 * Tested u:OK
362 */
363 void
tfrc_time_no_feedback(void * ccb)364 tfrc_time_no_feedback(void *ccb)
365 {
366 struct fixpoint v, w;
367 u_int32_t next_time_out = 1; /* remove init! */
368 struct timeval t_now;
369 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
370
371 mutex_enter(&(cb->mutex));
372
373 if (cb->state == TFRC_SSTATE_TERM) {
374 TFRC_DEBUG((LOG_INFO, "TFRC - No feedback timer is ordered to terminate\n"));
375 goto nf_release;
376 }
377 if (callout_pending(&(cb)->ch_nftimer)) {
378 TFRC_DEBUG((LOG_INFO, "TFRC - Callout pending, exiting...(tfrc_time_no_feedback)\n"));
379 goto nf_release;
380 }
381 switch (cb->state) {
382 case TFRC_SSTATE_NO_FBACK:
383 TFRC_DEBUG((LOG_INFO, "TFRC - no feedback timer expired, state NO_FBACK\n"));
384 /* half send rate */
385 cb->x.denom *= 2;
386 v.num = cb->s;
387 v.denom *= TFRC_MAX_BACK_OFF_TIME;
388 if (fixpoint_cmp(&cb->x, &v) < 0)
389 cb->x = v;
390
391 TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
392 PRINTFLOAT(&cb->x);
393 TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_time_no_feedback\n"));
394
395 /* reschedule next time out */
396
397 v.num = 2;
398 v.denom = 1;
399 w.num = cb->s;
400 w.denom = 1;
401 fixpoint_mul(&v, &v, &w);
402 fixpoint_div(&v, &v, &(cb->x));
403 v.num *= 1000000;
404 normalize(&v.num, &v.denom);
405 next_time_out = v.num / v.denom;
406 if (next_time_out < TFRC_INITIAL_TIMEOUT * 1000000)
407 next_time_out = TFRC_INITIAL_TIMEOUT * 1000000;
408 break;
409 case TFRC_SSTATE_FBACK:
410 /*
411 * Check if IDLE since last timeout and recv rate is less than
412 * 4 packets per RTT
413 */
414
415 v.num = cb->s;
416 v.num *= 4;
417 v.denom *= cb->rtt;
418 v.num *= 1000000;
419 normalize(&v.num, &v.denom);
420 if (!cb->idle || fixpoint_cmp(&cb->x_recv, &v) >= 0) {
421 TFRC_DEBUG((LOG_INFO, "TFRC - no feedback timer expired, state FBACK, not idle\n"));
422 /* Half sending rate */
423
424 /*
425 * If (X_calc > 2* X_recv) X_recv = max(X_recv/2,
426 * s/(2*t_mbi)); Else X_recv = X_calc/4;
427 */
428 v.num = TFRC_SMALLEST_P;
429 v.denom = 1;
430 if (fixpoint_cmp(&cb->p, &v) < 0 && cb->x_calc.num == 0)
431 panic("TFRC - X_calc is zero! (tfrc_time_no_feedback)\n");
432
433 /* check also if p i zero -> x_calc is infinity ?? */
434 w = cb->x_recv;
435 w.num *= 2;
436 if (fixpoint_cmp(&cb->p, &v) || fixpoint_cmp(&cb->x_calc, &w) > 0) {
437 cb->x_recv.denom *= 2;
438 w.num = cb->s;
439 w.denom *= (2 * TFRC_MAX_BACK_OFF_TIME);
440 if (fixpoint_cmp(&cb->x_recv, &w) < 0)
441 cb->x_recv = w;
442 } else
443 cb->x_recv.denom *= 4;
444 normalize(&cb->x_recv.num, &cb->x_recv.denom);
445
446 /* Update sending rate */
447 microtime(&t_now);
448 tfrc_updateX(cb, t_now);
449 }
450 /* Schedule no feedback timer to expire in max(4*R, 2*s/X) */
451 v.num = cb->s;
452 v.num *= 2;
453 fixpoint_div(&v, &v, &cb->x);
454 v.num *= 1000000;
455 next_time_out = v.num / v.denom;
456 if (next_time_out < cb->t_rto)
457 next_time_out = cb->t_rto;
458 break;
459 default:
460 panic("tfrc_no_feedback: Illegal state!");
461 break;
462 }
463
464 /* Set timer */
465
466 next_time_out = next_time_out / (1000000 / hz);
467 if (next_time_out == 0)
468 next_time_out = 1;
469
470 TFRC_DEBUG_TIME((LOG_INFO, "TFRC scheduled no feedback timer to expire in %u ticks (hz=%u)\n", next_time_out, hz));
471
472 callout_reset(&cb->ch_nftimer, next_time_out, tfrc_time_no_feedback, cb);
473
474 /* set idle flag */
475 cb->idle = 1;
476 nf_release:
477 mutex_exit(&(cb->mutex));
478 }
479
480 /*
481 * Removes ccb from memory
482 * args: ccb - ccb of sender
483 */
484 void
tfrc_send_term(void * ccb)485 tfrc_send_term(void *ccb)
486 {
487 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
488
489 if (ccb == 0)
490 panic("TFRC - Sender ccb is null! (free)");
491
492 /* free sender */
493
494 mutex_destroy(&(cb->mutex));
495
496 free(cb, M_PCB);
497 TFRC_DEBUG((LOG_INFO, "TFRC sender is destroyed\n"));
498 }
499
500 /* Functions declared in struct dccp_cc_sw */
501
502 /*
503 * Initialises the sender side
504 * args: pcb - dccp protocol control block
505 * returns: pointer to a tfrc_send_ccb struct on success, otherwise 0
506 * Tested u:OK
507 */
508 void *
tfrc_send_init(struct dccpcb * pcb)509 tfrc_send_init(struct dccpcb * pcb)
510 {
511 struct tfrc_send_ccb *ccb;
512
513 ccb = malloc(sizeof(struct tfrc_send_ccb), M_PCB, M_NOWAIT | M_ZERO);
514 if (ccb == 0) {
515 TFRC_DEBUG((LOG_INFO, "Unable to allocate memory for tfrc_send_ccb!\n"));
516 return 0;
517 }
518 /* init sender */
519
520 mutex_init(&(ccb->mutex), MUTEX_DEFAULT, IPL_SOFTNET);
521
522 ccb->pcb = pcb;
523 if (ccb->pcb->avgpsize >= TFRC_MIN_PACKET_SIZE && ccb->pcb->avgpsize <= TFRC_MAX_PACKET_SIZE)
524 ccb->s = (u_int16_t) ccb->pcb->avgpsize;
525 else
526 ccb->s = TFRC_STD_PACKET_SIZE;
527
528 TFRC_DEBUG((LOG_INFO, "TFRC - Sender is using packet size %u\n", ccb->s));
529
530 ccb->x.num = ccb->s; /* set transmissionrate to 1 packet per second */
531 ccb->x.denom = 1;
532
533 ccb->t_ld.tv_sec = -1;
534 ccb->t_ld.tv_usec = 0;
535
536 #ifdef TFRCDEBUG
537 ccb->t_last_win_count.tv_sec = -1;
538 #endif
539 callout_init(&ccb->ch_stimer, 0);
540 callout_init(&ccb->ch_nftimer, 0);
541
542 /* init packet history */
543 TAILQ_INIT(&(ccb->hist));
544
545 ccb->state = TFRC_SSTATE_NO_SENT;
546
547 TFRC_DEBUG((LOG_INFO, "TFRC sender initialised!\n"));
548 dccpstat.tfrcs_send_conn++;
549 return ccb;
550 }
551
552 /*
553 * Free the sender side
554 * args: ccb - ccb of sender
555 * Tested u:OK
556 */
557 void
tfrc_send_free(void * ccb)558 tfrc_send_free(void *ccb)
559 {
560 struct s_hist_entry *elm, *elm2;
561 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
562
563 TFRC_DEBUG((LOG_INFO, "TFRC send free called!\n"));
564
565 if (ccb == 0)
566 return;
567
568 /* uninit sender */
569
570 /* get mutex */
571 mutex_enter(&(cb->mutex));
572
573 cb->state = TFRC_SSTATE_TERM;
574 /* unschedule timers */
575 callout_stop(&cb->ch_stimer);
576 callout_stop(&cb->ch_nftimer);
577
578 /* Empty packet history */
579 elm = TAILQ_FIRST(&(cb->hist));
580 while (elm != NULL) {
581 elm2 = TAILQ_NEXT(elm, linfo);
582 free(elm, M_TEMP); /* M_TEMP ?? */
583 elm = elm2;
584 }
585 TAILQ_INIT(&(cb->hist));
586
587 mutex_exit(&(cb->mutex));
588
589 /* schedule the removal of ccb */
590 callout_reset(&cb->ch_stimer, TFRC_SEND_WAIT_TERM * hz, tfrc_send_term, cb);
591 }
592
593 /*
594 * Ask TFRC whether one can send a packet or not
595 * args: ccb - ccb block for current connection
596 * returns: 1 if ok, else 0.
597 */
598 int
tfrc_send_packet(void * ccb,long datasize)599 tfrc_send_packet(void *ccb, long datasize)
600 {
601 struct s_hist_entry *new_packet;
602 u_int8_t answer = 0;
603 u_int8_t win_count = 0;
604 u_int32_t uw_win_count = 0;
605 struct timeval t_now, t_temp;
606 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
607 #ifdef NOTFRCSENDER
608 return 1;
609 #endif
610
611 /* check if pure ACK or Terminating */
612 if (datasize == 0 || cb->state == TFRC_SSTATE_TERM) {
613 return 1;
614 } else if (cb->state == TFRC_SSTATE_TERM) {
615 TFRC_DEBUG((LOG_INFO, "TFRC - Asked to send packet when terminating!\n"));
616 return 0;
617 }
618 /* we have data to send */
619 mutex_enter(&(cb->mutex));
620
621 /* check to see if we already have allocated memory last time */
622 new_packet = TAILQ_FIRST(&(cb->hist));
623
624 if ((new_packet != NULL && new_packet->t_sent.tv_sec >= 0) || new_packet == NULL) {
625 /* check to see if we have memory to add to packet history */
626 new_packet = malloc(sizeof(struct s_hist_entry), M_TEMP, M_NOWAIT); /* M_TEMP?? */
627 if (new_packet == NULL) {
628 TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory to add packet to packet history (send refused)! (tfrc_send_packet)\n"));
629 answer = 0;
630 dccpstat.tfrcs_send_nomem++;
631 goto sp_release;
632 }
633 new_packet->t_sent.tv_sec = -1; /* mark as unsent */
634 TAILQ_INSERT_HEAD(&(cb->hist), new_packet, linfo);
635 }
636 switch (cb->state) {
637 case TFRC_SSTATE_NO_SENT:
638 TFRC_DEBUG((LOG_INFO, "TFRC - DCCP ask permission to send first data packet (tfrc_send_packet)\n"));
639 microtime(&(cb->t_nom)); /* set nominal send time for initial packet */
640 t_now = cb->t_nom;
641
642 /* init feedback timer */
643
644 callout_reset(&cb->ch_nftimer, TFRC_INITIAL_TIMEOUT * hz, tfrc_time_no_feedback, cb);
645 win_count = 0;
646 cb->t_last_win_count = t_now;
647 TFRC_DEBUG((LOG_INFO, "TFRC - Permission granted. Scheduled no feedback timer (initial) to expire in %u ticks (hz=%u) (tfrc_send_packet)\n", TFRC_INITIAL_TIMEOUT * hz, hz));
648 /* start send timer */
649
650 /* Calculate new t_ipi */
651 CALCNEWTIPI(cb);
652 timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
653 /* Calculate new delta */
654 CALCNEWDELTA(cb);
655 tfrc_set_send_timer(cb, t_now); /* if so schedule sendtimer */
656 cb->state = TFRC_SSTATE_NO_FBACK;
657 answer = 1;
658 break;
659 case TFRC_SSTATE_NO_FBACK:
660 case TFRC_SSTATE_FBACK:
661 if (!callout_pending(&cb->ch_stimer)) {
662 microtime(&t_now);
663
664 t_temp = t_now;
665 timeradd(&t_temp, &cb->delta, &t_temp);
666
667 if ((timercmp(&(t_temp), &(cb->t_nom), >))) {
668 /* Packet can be sent */
669
670 #ifdef TFRCDEBUG
671 if (cb->t_last_win_count.tv_sec == -1)
672 panic("TFRC - t_last_win_count unitialized (tfrc_send_packet)\n");
673 #endif
674 t_temp = t_now;
675 timersub(&t_temp, &(cb->t_last_win_count), &t_temp);
676
677 /* XXX calculate window counter */
678 if (cb->state == TFRC_SSTATE_NO_FBACK) {
679 /* Assume RTT = t_rto(initial)/4 */
680 uw_win_count = (t_temp.tv_sec + (t_temp.tv_usec / 1000000))
681 / TFRC_INITIAL_TIMEOUT / (4 * TFRC_WIN_COUNT_PER_RTT);
682 } else {
683 if (cb->rtt)
684 uw_win_count = (t_temp.tv_sec * 1000000 + t_temp.tv_usec)
685 / cb->rtt / TFRC_WIN_COUNT_PER_RTT;
686 else
687 uw_win_count = 0;
688 }
689 uw_win_count += cb->last_win_count;
690 win_count = uw_win_count % TFRC_WIN_COUNT_LIMIT;
691 answer = 1;
692 } else {
693 answer = 0;
694 }
695 } else {
696 answer = 0;
697 }
698 break;
699 default:
700 panic("tfrc_send_packet: Illegal state!");
701 break;
702 }
703
704 if (answer) {
705 cb->pcb->ccval = win_count;
706 new_packet->win_count = win_count;
707 }
708
709 sp_release:
710 mutex_exit(&(cb->mutex));
711 return answer;
712 }
713 /* Notify sender that a packet has been sent
714 * args: ccb - ccb block for current connection
715 * moreToSend - if there exists more packets to send
716 * dataSize - packet size
717 */
718 void
tfrc_send_packet_sent(void * ccb,int moreToSend,long datasize)719 tfrc_send_packet_sent(void *ccb, int moreToSend, long datasize)
720 {
721 struct timeval t_now, t_temp;
722 struct s_hist_entry *packet;
723 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
724
725 #ifdef NOTFRCSENDER
726 return;
727 #endif
728
729 if (cb->state == TFRC_SSTATE_TERM) {
730 TFRC_DEBUG((LOG_INFO, "TFRC - Packet sent when terminating!\n"));
731 return;
732 }
733 mutex_enter(&(cb->mutex));
734 microtime(&t_now);
735
736 /* check if we have sent a data packet */
737 if (datasize > 0) {
738 /* add send time to history */
739 packet = TAILQ_FIRST(&(cb->hist));
740 if (packet == NULL)
741 panic("TFRC - Packet does not exist in history! (tfrc_send_packet_sent)");
742 else if (packet != NULL && packet->t_sent.tv_sec >= 0)
743 panic("TFRC - No unsent packet in history! (tfrc_send_packet_sent)");
744 packet->t_sent = t_now;
745 packet->seq = cb->pcb->seq_snd;
746 /* check if win_count have changed */
747 if (packet->win_count != cb->last_win_count) {
748 cb->t_last_win_count = t_now;
749 cb->last_win_count = packet->win_count;
750 }
751 TFRC_DEBUG((LOG_INFO, "TFRC - Packet sent (%llu, %u, (%lu.%lu)",
752 packet->seq, packet->win_count, packet->t_sent.tv_sec, packet->t_sent.tv_usec));
753 cb->idle = 0;
754 }
755
756 /* if timer is running, do nothing */
757 if (callout_pending(&cb->ch_stimer)) {
758 goto sps_release;
759 }
760
761 switch (cb->state) {
762 case TFRC_SSTATE_NO_SENT:
763 /* if first was pure ack */
764 if (datasize == 0) {
765 goto sps_release;
766 } else
767 panic("TFRC - First packet sent is noted as a data packet in tfrc_send_packet_sent\n");
768 break;
769 case TFRC_SSTATE_NO_FBACK:
770 case TFRC_SSTATE_FBACK:
771 if (datasize <= 0) { /* we have ack (or simulate a sent
772 * packet which never can have
773 * moreToSend */
774 moreToSend = 0;
775 } else {
776 /* Calculate new t_ipi */
777 CALCNEWTIPI(cb);
778 timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
779 /* Calculate new delta */
780 CALCNEWDELTA(cb);
781 }
782
783 if (!moreToSend) {
784 /* loop until we find a send time in the future */
785 microtime(&t_now);
786 t_temp = t_now;
787 timeradd(&t_temp, &cb->delta, &t_temp);
788 while ((timercmp(&(t_temp), &(cb->t_nom), >))) {
789 /* Calculate new t_ipi */
790 CALCNEWTIPI(cb);
791 timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
792
793 /* Calculate new delta */
794 CALCNEWDELTA(cb);
795
796 microtime(&t_now);
797 t_temp = t_now;
798 timeradd(&t_temp, &cb->delta, &t_temp);
799 }
800 tfrc_set_send_timer(cb, t_now);
801 } else {
802 microtime(&t_now);
803 t_temp = t_now;
804 timeradd(&t_temp, &cb->delta, &t_temp);
805
806 /* Check if next packet can not be sent immediately */
807 if (!(timercmp(&(t_temp), &(cb->t_nom), >))) {
808 tfrc_set_send_timer(cb, t_now); /* if so schedule sendtimer */
809 }
810 }
811 break;
812 default:
813 panic("tfrc_send_packet_sent: Illegal state!");
814 break;
815 }
816
817 sps_release:
818 mutex_exit(&(cb->mutex));
819 }
820 /* Notify that a an ack package was received (i.e. a feedback packet)
821 * args: ccb - ccb block for current connection
822 */
823 void
tfrc_send_packet_recv(void * ccb,char * options,int optlen)824 tfrc_send_packet_recv(void *ccb, char *options, int optlen)
825 {
826 u_int32_t next_time_out;
827 struct timeval t_now;
828 struct fixpoint x,y;
829 int res;
830 u_int16_t t_elapsed = 0;
831 u_int32_t t_elapsed_l = 0;
832 u_int32_t pinv;
833 u_int32_t x_recv;
834
835 u_int32_t r_sample;
836
837 struct s_hist_entry *elm, *elm2;
838 struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
839
840 #ifdef NOTFRCSENDER
841 return;
842 #endif
843
844 if (cb->state == TFRC_SSTATE_TERM) {
845 TFRC_DEBUG((LOG_INFO, "TFRC - Sender received a packet when terminating!\n"));
846 return;
847 }
848 /* we are only interested in ACKs */
849 if (!(cb->pcb->type_rcv == DCCP_TYPE_ACK || cb->pcb->type_rcv == DCCP_TYPE_DATAACK))
850 return;
851
852 res = dccp_get_option(options, optlen, TFRC_OPT_LOSS_RATE, (char *) &pinv, 6);
853 if (res == 0) {
854 TFRC_DEBUG((LOG_INFO, "TFRC - Missing Loss rate option! (tfrc_send_packet_recv)\n"));
855 dccpstat.tfrcs_send_noopt++;
856 return;
857 }
858
859 res = dccp_get_option(options, optlen, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed_l, 6);
860 if (res == 0) {
861 /* try 2 bytes elapsed time */
862 res = dccp_get_option(options, optlen, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed, 4);
863 if (res == 0){
864 TFRC_DEBUG((LOG_INFO, "TFRC - Missing elapsed time option! (tfrc_send_packet_recv)\n"));
865 dccpstat.tfrcs_send_noopt++;
866 return;
867 }
868 }
869 res = dccp_get_option(options, optlen, TFRC_OPT_RECEIVE_RATE, (char *) &x_recv, 4);
870 if (res == 0) {
871 TFRC_DEBUG((LOG_INFO, "TFRC - Missing x_recv option! (tfrc_send_packet_recv)\n"));
872 dccpstat.tfrcs_send_noopt++;
873 return;
874 }
875 dccpstat.tfrcs_send_fbacks++;
876 /* change byte order */
877 if (t_elapsed)
878 t_elapsed = ntohs(t_elapsed);
879 else
880 t_elapsed_l = ntohl(t_elapsed_l);
881 x_recv = ntohl(x_recv);
882 pinv = ntohl(pinv);
883 if (pinv == 0xFFFFFFFF) pinv = 0;
884
885 if (t_elapsed)
886 TFRC_DEBUG((LOG_INFO, "TFRC - Receieved options on ack %llu: pinv=%u, t_elapsed=%u, x_recv=%u ! (tfrc_send_packet_recv)\n", cb->pcb->ack_rcv, pinv, t_elapsed, x_recv));
887 else
888 TFRC_DEBUG((LOG_INFO, "TFRC - Receieved options on ack %llu: pinv=%u, t_elapsed=%u, x_recv=%u ! (tfrc_send_packet_recv)\n", cb->pcb->ack_rcv, pinv, t_elapsed_l, x_recv));
889
890 mutex_enter(&(cb->mutex));
891
892 switch (cb->state) {
893 case TFRC_SSTATE_NO_FBACK:
894 case TFRC_SSTATE_FBACK:
895 /* Calculate new round trip sample by R_sample = (t_now -
896 * t_recvdata)-t_delay; */
897
898 /* get t_recvdata from history */
899 elm = TAILQ_FIRST(&(cb->hist));
900 while (elm != NULL) {
901 if (elm->seq == cb->pcb->ack_rcv)
902 break;
903 elm = TAILQ_NEXT(elm, linfo);
904 }
905
906 if (elm == NULL) {
907 TFRC_DEBUG((LOG_INFO,
908 "TFRC - Packet does not exist in history (seq=%llu)! (tfrc_send_packet_recv)", cb->pcb->ack_rcv));
909 goto sar_release;
910 }
911 /* Update RTT */
912 microtime(&t_now);
913 timersub(&t_now, &(elm->t_sent), &t_now);
914 r_sample = t_now.tv_sec * 1000000 + t_now.tv_usec;
915 if (t_elapsed)
916 r_sample = r_sample - ((u_int32_t) t_elapsed * 10); /* t_elapsed in us */
917 else
918 r_sample = r_sample - (t_elapsed_l * 10); /* t_elapsed in us */
919
920 /* Update RTT estimate by If (No feedback recv) R = R_sample;
921 * Else R = q*R+(1-q)*R_sample; */
922 if (cb->state == TFRC_SSTATE_NO_FBACK) {
923 cb->state = TFRC_SSTATE_FBACK;
924 cb->rtt = r_sample;
925 } else {
926 cb->rtt = (u_int32_t) (TFRC_RTT_FILTER_CONST * cb->rtt +
927 (1 - TFRC_RTT_FILTER_CONST) * r_sample);
928 }
929
930 TFRC_DEBUG((LOG_INFO, "TFRC - New RTT estimate %u (tfrc_send_packet_recv)\n", cb->rtt));
931
932 /* Update timeout interval */
933 cb->t_rto = 4 * cb->rtt;
934
935 /* Update receive rate */
936 x.num = x_recv;
937 y.num = 8;
938 x.denom = y.denom = 1;
939 fixpoint_div(&(cb)->x_recv, &x, &y);
940
941 /* Update loss event rate */
942 if (pinv == 0) {
943 cb->p.num = cb->p.denom = 0;
944 } else {
945 cb->p.num = 1.0;
946 cb->p.denom = pinv;
947 if (fixpoint_cmp(&cb->p, &tfrc_smallest_p) <= 0) {
948 cb->p.num = tfrc_smallest_p.num;
949 cb->p.denom = tfrc_smallest_p.denom;
950 TFRC_DEBUG((LOG_INFO, "TFRC - Smallest p used!\n"));
951 }
952 }
953
954 /* unschedule no feedback timer */
955 if (!callout_pending(&cb->ch_nftimer)) {
956 callout_stop(&cb->ch_nftimer);
957 }
958 /* Update sending rate */
959 microtime(&t_now);
960 tfrc_updateX(cb, t_now);
961
962 /* Update next send time */
963 timersub(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
964
965 /* Calculate new t_ipi */
966 CALCNEWTIPI(cb);
967 timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
968 /* Calculate new delta */
969 CALCNEWDELTA(cb);
970
971 if (callout_pending(&cb->ch_stimer)) {
972 callout_stop(&cb->ch_stimer);
973 }
974
975 #if 0 /* XXX do not send ack of ack so far */
976 dccp_output(cb->pcb, 1);
977 tfrc_send_packet_sent(cb, 0, -1); /* make sure we schedule next send time */
978 #endif
979
980 /* remove all packets older than the one acked from history */
981 /* elm points to acked package! */
982
983 elm2 = TAILQ_NEXT(elm, linfo);
984
985 while (elm2 != NULL) {
986 TAILQ_REMOVE(&(cb->hist), elm2, linfo);
987 free(elm2, M_TEMP);
988 elm2 = TAILQ_NEXT(elm, linfo);
989 }
990
991 /* Schedule no feedback timer to expire in max(4*R, 2*s/X) */
992 /* next_time_out = (u_int32_t) (2 * cb->s * 1000000 / cb->x); */
993
994 x.num = 2;
995 x.denom = 1;
996 y.num = cb->s;
997 y.denom = 1;
998 fixpoint_mul(&x, &x, &y);
999 fixpoint_div(&x, &x, &(cb->x));
1000 x.num *= 1000000;
1001 normalize(&x.num, &x.denom);
1002 next_time_out = x.num / x.denom;
1003
1004 if (next_time_out < cb->t_rto)
1005 next_time_out = cb->t_rto;
1006 TFRC_DEBUG_TIME((LOG_INFO,
1007 "TFRC - Scheduled no feedback timer to expire in %u ticks (%u us) (hz=%u)(tfrc_send_packet_recv)\n",
1008 next_time_out / (1000000 / hz), next_time_out, hz));
1009 next_time_out = next_time_out / (1000000 / hz);
1010 if (next_time_out == 0)
1011 next_time_out = 1;
1012
1013 callout_reset(&cb->ch_nftimer, next_time_out, tfrc_time_no_feedback, cb);
1014
1015 /* set idle flag */
1016 cb->idle = 1;
1017 break;
1018 default:
1019 panic("tfrc_send_packet_recv: Illegal state!");
1020 break;
1021 }
1022 sar_release:
1023 mutex_exit(&(cb->mutex));
1024 }
1025 /* Receiver side */
1026
1027 /* Forward declarations */
1028 long tfrc_calclmean(struct tfrc_recv_ccb *);
1029 void tfrc_recv_send_feedback(struct tfrc_recv_ccb *);
1030 int tfrc_recv_add_hist(struct tfrc_recv_ccb *, struct r_hist_entry *);
1031 void tfrc_recv_detectLoss(struct tfrc_recv_ccb *);
1032 u_int32_t tfrc_recv_calcFirstLI(struct tfrc_recv_ccb *);
1033 void tfrc_recv_updateLI(struct tfrc_recv_ccb *, long, u_int8_t);
1034
1035 /* Weights used to calculate loss event rate */
1036 /* const double tfrc_recv_w[] = { 1, 1, 1, 1, 0.8, 0.6, 0.4, 0.2}; */
1037 const struct fixpoint tfrc_recv_w[] = {{1,1}, {1,1}, {1,1}, {1,1}, {4,5}, {3,5}, {2,5}, {1,5}};
1038
1039 /* Find a data packet in history
1040 * args: cb - ccb of receiver
1041 * elm - pointer to element (variable)
1042 * num - number in history (variable)
1043 * returns: elm points to found packet, otherwise NULL
1044 * Tested u:OK
1045 */
1046 #define TFRC_RECV_FINDDATAPACKET(cb,elm,num) \
1047 do { \
1048 elm = TAILQ_FIRST(&((cb)->hist)); \
1049 while ((elm) != NULL) { \
1050 if ((elm)->type == DCCP_TYPE_DATA || (elm)->type == DCCP_TYPE_DATAACK) \
1051 (num)--; \
1052 if (num == 0) \
1053 break; \
1054 elm = TAILQ_NEXT((elm), linfo); \
1055 } \
1056 } while (0)
1057
1058 /* Find next data packet in history
1059 * args: cb - ccb of receiver
1060 * elm - pointer to element (variable)
1061 * returns: elm points to found packet, otherwise NULL
1062 * Tested u:OK
1063 */
1064 #define TFRC_RECV_NEXTDATAPACKET(cb,elm) \
1065 do { \
1066 if (elm != NULL) { \
1067 elm = TAILQ_NEXT(elm, linfo); \
1068 while ((elm) != NULL && (elm)->type != DCCP_TYPE_DATA && (elm)->type != DCCP_TYPE_DATAACK) { \
1069 elm = TAILQ_NEXT((elm), linfo); \
1070 } \
1071 } \
1072 } while (0)
1073
1074 /*
1075 * Calculate avarage loss Interval I_mean
1076 * args: cb - ccb of receiver
1077 * returns: avarage loss interval
1078 * Tested u:OK
1079 */
1080 long
tfrc_calclmean(struct tfrc_recv_ccb * cb)1081 tfrc_calclmean(struct tfrc_recv_ccb * cb)
1082 {
1083 struct li_hist_entry *elm;
1084 struct fixpoint l_tot;
1085 struct fixpoint l_tot0 = {0,0};
1086 struct fixpoint l_tot1 = {0,0};
1087 struct fixpoint W_tot = {0, 0};
1088 struct fixpoint tmp;
1089 int i;
1090 elm = TAILQ_FIRST(&(cb->li_hist));
1091
1092 for (i = 0; i < TFRC_RECV_IVAL_F_LENGTH; i++) {
1093 #ifdef TFRCDEBUG
1094 if (elm == 0)
1095 goto I_panic;
1096 #endif
1097
1098 /*
1099 I_tot0 = I_tot0 + (elm->interval * tfrc_recv_w[i]);
1100 W_tot = W_tot + tfrc_recv_w[i];
1101 */
1102 tmp.num = elm->interval;
1103 tmp.denom = 1;
1104 fixpoint_mul(&tmp, &tmp, &tfrc_recv_w[i]);
1105 fixpoint_add(&l_tot0, &l_tot0, &tmp);
1106 fixpoint_add(&W_tot, &W_tot, &tfrc_recv_w[i]);
1107
1108 elm = TAILQ_NEXT(elm, linfo);
1109 }
1110
1111 elm = TAILQ_FIRST(&(cb->li_hist));
1112 elm = TAILQ_NEXT(elm, linfo);
1113
1114 for (i = 1; i <= TFRC_RECV_IVAL_F_LENGTH; i++) {
1115 #ifdef TFRCDEBUG
1116 if (elm == 0)
1117 goto I_panic;
1118 #endif
1119 /*
1120 I_tot1 = I_tot1 + (elm->interval * tfrc_recv_w[i - 1]);
1121 */
1122 tmp.num = elm->interval;
1123 tmp.denom = 1;
1124 fixpoint_mul(&tmp, &tmp, &tfrc_recv_w[i-1]);
1125 fixpoint_add(&l_tot1, &l_tot1, &tmp);
1126
1127 elm = TAILQ_NEXT(elm, linfo);
1128 }
1129
1130 /* I_tot = max(I_tot0, I_tot1) */
1131 /*
1132 I_tot = I_tot0;
1133 if (I_tot0 < I_tot1)
1134 I_tot = I_tot1;
1135
1136 if (I_tot < W_tot)
1137 I_tot = W_tot;
1138 return (I_tot / W_tot);
1139 */
1140
1141 l_tot.num = l_tot0.num;
1142 l_tot.denom = l_tot0.denom;
1143 if (fixpoint_cmp(&l_tot0, &l_tot1) < 0){
1144 l_tot.num = l_tot1.num;
1145 l_tot.denom = l_tot1.denom;
1146 }
1147
1148 if (fixpoint_cmp(&l_tot, &W_tot) < 0){
1149 l_tot.num = W_tot.num;
1150 l_tot.denom = W_tot.denom;
1151 }
1152 fixpoint_div(&tmp, &l_tot, &W_tot);
1153 return(fixpoint_getlong(&tmp));
1154
1155 #ifdef TFRCDEBUG
1156 I_panic:
1157 panic("TFRC - Missing entry in interval history! (tfrc_calclmean)");
1158 #endif
1159 }
1160
1161 /*
1162 * Send a feedback packet
1163 * args: cb - ccb for receiver
1164 * Tested u:OK
1165 */
1166 void
tfrc_recv_send_feedback(struct tfrc_recv_ccb * cb)1167 tfrc_recv_send_feedback(struct tfrc_recv_ccb * cb)
1168 {
1169 u_int32_t x_recv, pinv;
1170 u_int32_t t_elapsed;
1171 struct r_hist_entry *elm;
1172 struct fixpoint x;
1173 struct timeval t_now, t_temp;
1174 int num;
1175
1176 x.num = 1;
1177 x.denom = 4000000000LL; /* -> 1/p > 4 000 000 000 */
1178 if (fixpoint_cmp(&cb->p, &x) < 0)
1179 /* if (cb->p < 0.00000000025) -> 1/p > 4 000 000 000 */
1180 pinv = 0xFFFFFFFF;
1181 else {
1182 /* pinv = (u_int32_t) (1.0 / cb->p); */
1183 x.num = 1;
1184 x.denom = 1;
1185 fixpoint_div(&x, &x, &(cb)->p);
1186 pinv = fixpoint_getlong(&x);
1187 }
1188
1189 switch (cb->state) {
1190 case TFRC_RSTATE_NO_DATA:
1191 x_recv = 0;
1192 break;
1193 case TFRC_RSTATE_DATA:
1194 /* Calculate x_recv */
1195 microtime(&t_temp);
1196 timersub(&t_temp, &cb->t_last_feedback, &t_temp);
1197
1198 x_recv = (u_int32_t) (cb->bytes_recv * 8 * 1000000) / (t_temp.tv_sec * 1000000 + t_temp.tv_usec);
1199
1200 break;
1201 default:
1202 panic("tfrc_recv_send_feedback: Illegal state!");
1203 break;
1204 }
1205
1206 /* Find largest win_count so far (data packet with highest seqnum so far) */
1207 num = 1;
1208 TFRC_RECV_FINDDATAPACKET(cb, elm, num);
1209
1210 if (elm == NULL)
1211 panic("No data packet in history! (tfrc_recv_send_feedback)");
1212
1213
1214 microtime(&t_now);
1215 timersub(&t_now, &elm->t_recv, &t_now);
1216 t_elapsed = (u_int32_t) (t_now.tv_sec * 100000 + t_now.tv_usec / 10);
1217
1218 /* change byte order */
1219 t_elapsed = htonl(t_elapsed);
1220 x_recv = htonl(x_recv);
1221 pinv = htonl(pinv);
1222
1223 /* add options from variables above */
1224 if (dccp_add_option(cb->pcb, TFRC_OPT_LOSS_RATE, (char *) &pinv, 4)
1225 || dccp_add_option(cb->pcb, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed, 4)
1226 || dccp_add_option(cb->pcb, TFRC_OPT_RECEIVE_RATE, (char *) &x_recv, 4)) {
1227 TFRC_DEBUG((LOG_INFO, "TFRC - Can't add options, aborting send feedback (tfrc_send_feedback)"));
1228 /* todo: remove options */
1229 dccpstat.tfrcs_recv_erropt++;
1230 return;
1231 }
1232 cb->pcb->ack_snd = elm->seq;
1233 cb->last_counter = elm->win_count;
1234 cb->seq_last_counter = elm->seq;
1235 microtime(&(cb->t_last_feedback));
1236 cb->bytes_recv = 0;
1237
1238 TFRC_DEBUG_TIME((LOG_INFO, "TFRC - Sending a feedback packet with (t_elapsed %u, pinv %x, x_recv %u, ack=%llu) (tfrc_recv_send_feedback)\n", ntohs(t_elapsed), ntohl(pinv), ntohl(x_recv), elm->seq));
1239
1240 dccpstat.tfrcs_recv_fbacks++;
1241 dccp_output(cb->pcb, 1);
1242 }
1243 /*
1244 * Calculate first loss interval
1245 * args: cb - ccb of the receiver
1246 * returns: loss interval
1247 * Tested u:OK
1248 */
1249 u_int32_t
tfrc_recv_calcFirstLI(struct tfrc_recv_ccb * cb)1250 tfrc_recv_calcFirstLI(struct tfrc_recv_ccb * cb)
1251 {
1252 struct r_hist_entry *elm, *elm2;
1253 struct timeval t_temp;
1254 int temp;
1255 struct fixpoint x_recv, fval, t_rtt, x;
1256 const struct fixpoint *fval2;
1257 int win_count;
1258
1259 temp = 1;
1260 TFRC_RECV_FINDDATAPACKET(cb, elm, temp);
1261
1262 if (elm == NULL)
1263 panic("Packet history contains no data packets! (tfrc_recv_calcFirstLI)\n");
1264 t_temp = elm->t_recv;
1265 win_count = elm->win_count;
1266 elm2 = elm;
1267 TFRC_RECV_NEXTDATAPACKET(cb, elm2);
1268 while (elm2 != NULL) {
1269 temp = win_count - (int) (elm2->win_count);
1270 if (temp < 0)
1271 temp = temp + TFRC_WIN_COUNT_LIMIT;
1272
1273 if (temp > 4)
1274 break;
1275 elm = elm2;
1276 TFRC_RECV_NEXTDATAPACKET(cb, elm2);
1277 }
1278
1279 if (elm2 == NULL) {
1280 TFRC_DEBUG((LOG_INFO, "TFRC - Could not find a win_count interval > 4 \n"));
1281 elm2 = elm;
1282 if (temp == 0) {
1283 TFRC_DEBUG((LOG_INFO, "TFRC - Could not find a win_count interval > 0. Defaulting to 1 (tfrc_recv_calcFirstLI)\n"));
1284 temp = 1;
1285 }
1286 }
1287 timersub(&t_temp, &elm2->t_recv, &t_temp);
1288 t_rtt.num = t_temp.tv_sec * 1000000 + t_temp.tv_usec;
1289 t_rtt.denom = 1000000;
1290
1291 if (t_rtt.num < 0 && t_rtt.denom < 0) {
1292 TFRC_DEBUG((LOG_INFO, "TFRC - Approximation of RTT is negative!\n"));
1293 t_rtt.num = -t_rtt.num;
1294 t_rtt.denom = -t_rtt.denom;
1295 }
1296
1297 TFRC_DEBUG((LOG_INFO, "TFRC - Approximated rtt to "));
1298 PRINTFLOAT(&t_rtt);
1299 TFRC_DEBUG((LOG_INFO, " s (tfrc_recv_calcFirstLI)\n"));
1300
1301 /* Calculate x_recv */
1302 microtime(&t_temp);
1303 timersub(&t_temp, &cb->t_last_feedback, &t_temp);
1304 /*
1305 x_recv = (((double) (cb->bytes_recv)) /
1306 (((double) t_temp.tv_sec) + ((double) t_temp.tv_usec) / 1000000.0));
1307 */
1308 x_recv.num = cb->bytes_recv * 1000000;
1309 x_recv.denom = t_temp.tv_sec * 1000000 + t_temp.tv_usec;
1310
1311 TFRC_DEBUG((LOG_INFO, "TFRC - Receive rate XXX"));
1312 PRINTFLOAT(&x_recv);
1313 TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_recv_calcFirstLI)\n"));
1314
1315 /* fval = ((double) (cb->s)) / (x_recv * t_rtt); */
1316 fval.num = cb->s;
1317 fval.denom = 1;
1318 fixpoint_div(&fval, &fval, &x_recv);
1319 fixpoint_div(&fval, &fval, &t_rtt);
1320
1321 TFRC_DEBUG((LOG_INFO, "TFRC - Fvalue to locate XXX"));
1322 PRINTFLOAT(&fval);
1323 TFRC_DEBUG((LOG_INFO, " (tfrc_recv_calcFirstLI)\n"));
1324 fval2 = tfrc_flookup_reverse(&fval);
1325 TFRC_DEBUG((LOG_INFO, "TFRC - Lookup gives p= XXX"));
1326 PRINTFLOAT(&fval);
1327 TFRC_DEBUG((LOG_INFO, " (tfrc_recv_calcFirstLI)\n"));
1328 if (fval2->num == 0 && fval2->denom == 0)
1329 return (u_int32_t) 0xFFFFFFFF;
1330 x.num = x.denom = 1;
1331 fixpoint_div(&x, &x, fval2);
1332 return (u_int32_t) (fixpoint_getlong(&x));
1333 }
1334 /* Add packet to recv history (sorted on seqnum)
1335 * Do not add packets that are already lost
1336 * args: cb - ccb of receiver
1337 * packet - packet to insert
1338 * returns: 1 if the packet was considered lost, 0 otherwise
1339 * Tested u:OK
1340 */
1341 int
tfrc_recv_add_hist(struct tfrc_recv_ccb * cb,struct r_hist_entry * packet)1342 tfrc_recv_add_hist(struct tfrc_recv_ccb * cb, struct r_hist_entry * packet)
1343 {
1344 struct r_hist_entry *elm, *elm2;
1345 u_int8_t num_later = 0, win_count;
1346 u_int32_t seq_num = packet->seq;
1347 int temp;
1348
1349 TFRC_DEBUG((LOG_INFO, "TFRC - Adding packet (seq=%llu,win_count=%u,type=%u,ndp=%u) to history! (tfrc_recv_add_hist)\n", packet->seq, packet->win_count, packet->type, packet->ndp));
1350
1351 if (TAILQ_EMPTY(&(cb->hist))) {
1352 TAILQ_INSERT_HEAD(&(cb->hist), packet, linfo);
1353 } else {
1354 elm = TAILQ_FIRST(&(cb->hist));
1355 if ((seq_num > elm->seq
1356 && seq_num - elm->seq < TFRC_RECV_NEW_SEQ_RANGE) ||
1357 (seq_num < elm->seq
1358 && elm->seq - seq_num > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {
1359 TAILQ_INSERT_HEAD(&(cb->hist), packet, linfo);
1360 } else {
1361 if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
1362 num_later = 1;
1363
1364 elm2 = TAILQ_NEXT(elm, linfo);
1365 while (elm2 != NULL) {
1366 if ((seq_num > elm2->seq
1367 && seq_num - elm2->seq < TFRC_RECV_NEW_SEQ_RANGE) ||
1368 (seq_num < elm2->seq
1369 && elm2->seq - seq_num > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {
1370 TAILQ_INSERT_AFTER(&(cb->hist), elm, packet, linfo);
1371 break;
1372 }
1373 elm = elm2;
1374 elm2 = TAILQ_NEXT(elm, linfo);
1375
1376 if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
1377 num_later++;
1378
1379 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1380 free(packet, M_TEMP);
1381 TFRC_DEBUG((LOG_INFO, "TFRC - Packet already lost! (tfrc_recv_add_hist)\n"));
1382 return 1;
1383 break;
1384 }
1385 }
1386
1387 if (elm2 == NULL && num_later < TFRC_RECV_NUM_LATE_LOSS) {
1388 TAILQ_INSERT_TAIL(&(cb->hist), packet, linfo);
1389 }
1390 }
1391 }
1392
1393 /* trim history (remove all packets after the NUM_LATE_LOSS+1 data
1394 * packets) */
1395 if (TAILQ_FIRST(&(cb->li_hist)) != NULL) {
1396 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1397 TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);
1398 if (elm != NULL) {
1399 elm2 = TAILQ_NEXT(elm, linfo);
1400 while (elm2 != NULL) {
1401 TAILQ_REMOVE(&(cb->hist), elm2, linfo);
1402 free(elm2, M_TEMP);
1403 elm2 = TAILQ_NEXT(elm, linfo);
1404 }
1405 }
1406 } else {
1407 /* we have no loss interval history so we need at least one
1408 * rtt:s of data packets to approximate rtt */
1409 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1410 TFRC_RECV_FINDDATAPACKET(cb, elm2, num_later);
1411 if (elm2 != NULL) {
1412 num_later = 1;
1413 TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);
1414 win_count = elm->win_count;
1415
1416 elm = elm2;
1417 TFRC_RECV_NEXTDATAPACKET(cb, elm2);
1418 while (elm2 != NULL) {
1419 temp = win_count - (int) (elm2->win_count);
1420 if (temp < 0)
1421 temp = temp + TFRC_WIN_COUNT_LIMIT;
1422
1423 if (temp > TFRC_WIN_COUNT_PER_RTT + 1) {
1424 /* we have found a packet older than
1425 * one rtt remove the rest */
1426 elm = TAILQ_NEXT(elm2, linfo);
1427
1428 while (elm != NULL) {
1429 TAILQ_REMOVE(&(cb->hist), elm, linfo);
1430 free(elm, M_TEMP);
1431 elm = TAILQ_NEXT(elm2, linfo);
1432 }
1433 break;
1434 }
1435 elm = elm2;
1436 TFRC_RECV_NEXTDATAPACKET(cb, elm2);
1437 }
1438 } /* end if (exist atleast 4 data packets) */
1439 }
1440
1441 return 0;
1442 }
1443 /*
1444 * Detect loss events and update loss interval history
1445 * args: cb - ccb of the receiver
1446 * Tested u:OK
1447 */
1448 void
tfrc_recv_detectLoss(struct tfrc_recv_ccb * cb)1449 tfrc_recv_detectLoss(struct tfrc_recv_ccb * cb)
1450 {
1451 struct r_hist_entry *bLoss, *aLoss, *elm, *elm2;
1452 u_int8_t num_later = TFRC_RECV_NUM_LATE_LOSS;
1453 long seq_temp = 0;
1454 long seq_loss = -1;
1455 u_int8_t win_loss = 0;
1456
1457 TFRC_RECV_FINDDATAPACKET(cb, bLoss, num_later);
1458
1459 if (bLoss == NULL) {
1460 /* not enough packets yet to cause the first loss event */
1461 } else { /* bloss != NULL */
1462 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1463 TFRC_RECV_FINDDATAPACKET(cb, aLoss, num_later);
1464 if (aLoss == NULL) {
1465 if (TAILQ_EMPTY(&(cb->li_hist))) {
1466 /* no loss event have occured yet */
1467
1468 /* todo: find a lost data packet by comparing
1469 * to initial seq num */
1470
1471 } else {
1472 panic("Less than 4 data packets in history (tfrc_recv_detecLossEvent)\n");
1473 }
1474 } else { /* aLoss != NULL */
1475 /* locate a lost data packet */
1476 elm = bLoss;
1477 elm2 = TAILQ_NEXT(elm, linfo);
1478 do {
1479 seq_temp = ((long) (elm->seq)) - ((long) elm2->seq);
1480
1481 if (seq_temp < 0)
1482 seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;
1483
1484 if (seq_temp != 1) {
1485 /* check no data packets */
1486 if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
1487 seq_temp = seq_temp - 1;
1488 if (seq_temp % DCCP_NDP_LIMIT != ((int) elm->ndp - (int) elm2->ndp + DCCP_NDP_LIMIT) % DCCP_NDP_LIMIT)
1489 seq_loss = (elm2->seq + 1) % DCCP_SEQ_NUM_LIMIT;
1490 }
1491 elm = elm2;
1492 elm2 = TAILQ_NEXT(elm2, linfo);
1493 } while (elm != aLoss);
1494
1495 if (seq_loss != -1) {
1496 win_loss = aLoss->win_count;
1497 }
1498 }
1499 } /* end if (bLoss == NULL) */
1500 tfrc_recv_updateLI(cb, seq_loss, win_loss);
1501 }
1502 /* Updates the loss interval history
1503 * cb - congestion control block
1504 * seq_loss - sequence number of lost packet (-1 for none)
1505 * win_loss - window counter for previous (from the lost packet view) packet
1506 * Tested u:OK
1507 */
1508 void
tfrc_recv_updateLI(struct tfrc_recv_ccb * cb,long seq_loss,u_int8_t win_loss)1509 tfrc_recv_updateLI(struct tfrc_recv_ccb * cb, long seq_loss, u_int8_t win_loss)
1510 {
1511 struct r_hist_entry *elm;
1512 struct li_hist_entry *li_elm, *li_elm2;
1513 u_int8_t num_later = TFRC_RECV_NUM_LATE_LOSS;
1514 long seq_temp = 0;
1515 int i;
1516 u_int8_t win_start;
1517 int debug_info = 0;
1518 if (seq_loss != -1) { /* we have found a packet loss! */
1519 dccpstat.tfrcs_recv_losts++;
1520 TFRC_DEBUG((LOG_INFO, "TFRC - seqloss=%i, winloss=%i\n", (int) seq_loss, (int) win_loss));
1521 if (TAILQ_EMPTY(&(cb->li_hist))) {
1522 debug_info = 1;
1523 /* first loss detected */
1524 TFRC_DEBUG((LOG_INFO, "TFRC - First loss event detected! (tfrc_recv_updateLI)\n"));
1525 /* create history */
1526 for (i = 0; i < TFRC_RECV_IVAL_F_LENGTH + 1; i++) {
1527 li_elm = malloc(sizeof(struct li_hist_entry),
1528 M_TEMP, M_NOWAIT | M_ZERO); /* M_TEMP?? */
1529 if (li_elm == NULL) {
1530 TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory for loss interval history!\n"));
1531 /* Empty loss interval history */
1532 li_elm = TAILQ_FIRST(&(cb->li_hist));
1533 while (li_elm != NULL) {
1534 li_elm2 = TAILQ_NEXT(li_elm, linfo);
1535 free(li_elm, M_TEMP); /* M_TEMP ?? */
1536 li_elm = li_elm2;
1537 }
1538 return;
1539 }
1540 TAILQ_INSERT_HEAD(&(cb->li_hist), li_elm, linfo);
1541 }
1542
1543 li_elm->seq = seq_loss;
1544 li_elm->win_count = win_loss;
1545
1546 li_elm = TAILQ_NEXT(li_elm, linfo);
1547 /* add approx interval */
1548 li_elm->interval = tfrc_recv_calcFirstLI(cb);
1549
1550 } else { /* we have a loss interval history */
1551 debug_info = 2;
1552 /* Check if the loss is in the same loss event as
1553 * interval start */
1554 win_start = (TAILQ_FIRST(&(cb->li_hist)))->win_count;
1555 if ((win_loss > win_start
1556 && win_loss - win_start > TFRC_WIN_COUNT_PER_RTT) ||
1557 (win_loss < win_start
1558 && win_start - win_loss < TFRC_WIN_COUNT_LIMIT - TFRC_WIN_COUNT_PER_RTT)) {
1559 /* new loss event detected */
1560 /* calculate last interval length */
1561 seq_temp = seq_loss - ((long) ((TAILQ_FIRST(&(cb->li_hist)))->seq));
1562 if (seq_temp < 0)
1563 seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;
1564
1565 (TAILQ_FIRST(&(cb->li_hist)))->interval = seq_temp;
1566
1567 TFRC_DEBUG((LOG_INFO, "TFRC - New loss event detected!, interval %i (tfrc_recv_updateLI)\n", (int) seq_temp));
1568 /* Remove oldest interval */
1569 li_elm = TAILQ_LAST(&(cb->li_hist), li_hist_head);
1570 TAILQ_REMOVE(&(cb->li_hist), li_elm, linfo);
1571
1572 /* Create the newest interval */
1573 li_elm->seq = seq_loss;
1574 li_elm->win_count = win_loss;
1575
1576 /* insert it into history */
1577 TAILQ_INSERT_HEAD(&(cb->li_hist), li_elm, linfo);
1578 } else
1579 TFRC_DEBUG((LOG_INFO, "TFRC - Loss belongs to previous loss event (tfrc_recv_updateLI)!\n"));
1580 }
1581 }
1582 if (TAILQ_FIRST(&(cb->li_hist)) != NULL) {
1583 /* calculate interval to last loss event */
1584 num_later = 1;
1585 TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);
1586
1587 seq_temp = ((long) (elm->seq)) -
1588 ((long) ((TAILQ_FIRST(&(cb->li_hist)))->seq));
1589 if (seq_temp < 0)
1590 seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;
1591
1592 (TAILQ_FIRST(&(cb->li_hist)))->interval = seq_temp;
1593 if (debug_info > 0) {
1594 TFRC_DEBUG((LOG_INFO, "TFRC - Highest data packet received %llu (tfrc_recv_updateLI)\n", elm->seq));
1595 }
1596 }
1597 }
1598
1599
1600 /* Functions declared in struct dccp_cc_sw */
1601 /* Initialises the receiver side
1602 * returns: pointer to a tfrc_recv_ccb struct on success, otherwise 0
1603 * Tested u:OK
1604 */
1605 void *
tfrc_recv_init(struct dccpcb * pcb)1606 tfrc_recv_init(struct dccpcb * pcb)
1607 {
1608 struct tfrc_recv_ccb *ccb;
1609
1610 ccb = malloc(sizeof(struct tfrc_recv_ccb), M_PCB, M_NOWAIT | M_ZERO);
1611 if (ccb == 0) {
1612 TFRC_DEBUG((LOG_INFO, "TFRC - Unable to allocate memory for tfrc_recv_ccb!\n"));
1613 return 0;
1614 }
1615 /* init recv here */
1616
1617 mutex_init(&(ccb->mutex), MUTEX_DEFAULT, IPL_SOFTNET);
1618
1619 ccb->pcb = pcb;
1620
1621 if (ccb->pcb->avgpsize >= TFRC_MIN_PACKET_SIZE && ccb->pcb->avgpsize <= TFRC_MAX_PACKET_SIZE)
1622 ccb->s = (u_int16_t) ccb->pcb->avgpsize;
1623 else
1624 ccb->s = TFRC_STD_PACKET_SIZE;
1625
1626 TFRC_DEBUG((LOG_INFO, "TFRC - Receiver is using packet size %u\n", ccb->s));
1627
1628 /* init packet history */
1629 TAILQ_INIT(&(ccb->hist));
1630
1631 /* init loss interval history */
1632 TAILQ_INIT(&(ccb->li_hist));
1633
1634 ccb->state = TFRC_RSTATE_NO_DATA;
1635 TFRC_DEBUG((LOG_INFO, "TFRC receiver initialised!\n"));
1636 dccpstat.tfrcs_recv_conn++;
1637 return ccb;
1638 }
1639 /* Free the receiver side
1640 * args: ccb - ccb of recevier
1641 * Tested u:OK
1642 */
1643 void
tfrc_recv_free(void * ccb)1644 tfrc_recv_free(void *ccb)
1645 {
1646 struct r_hist_entry *elm, *elm2;
1647 struct li_hist_entry *li_elm, *li_elm2;
1648 struct tfrc_recv_ccb *cb = (struct tfrc_recv_ccb *) ccb;
1649
1650 if (ccb == 0)
1651 panic("TFRC - Receiver ccb is null! (free)");
1652
1653 /* uninit recv here */
1654
1655 cb->state = TFRC_RSTATE_TERM;
1656 /* get mutex */
1657 mutex_enter(&(cb->mutex));
1658
1659 /* Empty packet history */
1660 elm = TAILQ_FIRST(&(cb->hist));
1661 while (elm != NULL) {
1662 elm2 = TAILQ_NEXT(elm, linfo);
1663 free(elm, M_TEMP); /* M_TEMP ?? */
1664 elm = elm2;
1665 }
1666 TAILQ_INIT(&(cb->hist));
1667
1668 /* Empty loss interval history */
1669 li_elm = TAILQ_FIRST(&(cb->li_hist));
1670 while (li_elm != NULL) {
1671 li_elm2 = TAILQ_NEXT(li_elm, linfo);
1672 free(li_elm, M_TEMP); /* M_TEMP ?? */
1673 li_elm = li_elm2;
1674 }
1675 TAILQ_INIT(&(cb->li_hist));
1676
1677 mutex_exit(&(cb->mutex));
1678 mutex_destroy(&(cb->mutex));
1679
1680 free(ccb, M_PCB);
1681
1682 TFRC_DEBUG((LOG_INFO, "TFRC receiver is destroyed\n"));
1683 }
1684
1685
1686 /*
1687 * Tell TFRC that a packet has been received
1688 * args: ccb - ccb block for current connection
1689 */
1690 void
tfrc_recv_packet_recv(void * ccb,char * options,int optlen)1691 tfrc_recv_packet_recv(void *ccb, char *options, int optlen)
1692 {
1693 struct r_hist_entry *packet;
1694 u_int8_t win_count = 0;
1695 struct fixpoint p_prev;
1696 int ins = 0;
1697 struct tfrc_recv_ccb *cb = (struct tfrc_recv_ccb *) ccb;
1698
1699 #ifdef NOTFRCRECV
1700 return;
1701 #endif
1702
1703 if (!(cb->state == TFRC_RSTATE_NO_DATA || cb->state == TFRC_RSTATE_DATA)) {
1704 panic("TFRC - Illegal state! (tfrc_recv_packet_recv)\n");
1705 return;
1706 }
1707 /* Check which type */
1708 switch (cb->pcb->type_rcv) {
1709 case DCCP_TYPE_ACK:
1710 if (cb->state == TFRC_RSTATE_NO_DATA)
1711 return;
1712 break;
1713 case DCCP_TYPE_DATA:
1714 case DCCP_TYPE_DATAACK:
1715 break;
1716 default:
1717 TFRC_DEBUG((LOG_INFO, "TFRC - Received not data/dataack/ack packet! (tfrc_recv_packet_recv)"));
1718 return;
1719 }
1720
1721 mutex_enter(&(cb->mutex));
1722
1723 /* Add packet to history */
1724
1725 packet = malloc(sizeof(struct r_hist_entry), M_TEMP, M_NOWAIT); /* M_TEMP?? */
1726 if (packet == NULL) {
1727 TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory to add received packet to history (consider it lost)! (tfrc_recv_packet_recv)"));
1728 dccpstat.tfrcs_recv_nomem++;
1729 goto rp_release;
1730 }
1731 microtime(&(packet->t_recv));
1732 packet->seq = cb->pcb->seq_rcv;
1733 packet->type = cb->pcb->type_rcv;
1734 packet->ndp = cb->pcb->ndp_rcv;
1735
1736 /* get window counter */
1737 win_count = cb->pcb->ccval;
1738 packet->win_count = win_count;
1739
1740 ins = tfrc_recv_add_hist(cb, packet);
1741
1742 /* check if we got a data packet */
1743 if (cb->pcb->type_rcv != DCCP_TYPE_ACK) {
1744
1745 switch (cb->state) {
1746 case TFRC_RSTATE_NO_DATA:
1747 TFRC_DEBUG((LOG_INFO, "TFRC - Send an inital feedback packet (tfrc_recv_packet_recv)\n"));
1748 tfrc_recv_send_feedback(cb);
1749 cb->state = TFRC_RSTATE_DATA;
1750 break;
1751 case TFRC_RSTATE_DATA:
1752 cb->bytes_recv = cb->bytes_recv + cb->pcb->len_rcv;
1753 if (!ins) {
1754 /* find loss event */
1755 tfrc_recv_detectLoss(cb);
1756 p_prev.num = cb->p.num;
1757 p_prev.denom = cb->p.denom;
1758
1759 /* Calculate loss event rate */
1760 if (!TAILQ_EMPTY(&(cb->li_hist))) {
1761 cb->p.num = 1;
1762 cb->p.denom = tfrc_calclmean(cb);
1763 }
1764 /* check send conditions then send */
1765
1766 if (fixpoint_cmp(&(cb)->p, &p_prev) > 0) {
1767 TFRC_DEBUG((LOG_INFO, "TFRC - Send a feedback packet because p>p_prev (tfrc_recv_packet_recv)\n"));
1768 tfrc_recv_send_feedback(cb);
1769 } else {
1770 if ((cb->pcb->seq_rcv > cb->seq_last_counter
1771 && cb->pcb->seq_rcv - cb->seq_last_counter < TFRC_RECV_NEW_SEQ_RANGE) ||
1772 (cb->pcb->seq_rcv < cb->seq_last_counter
1773 && cb->seq_last_counter - cb->pcb->seq_rcv > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {
1774
1775 /* the sequence number is
1776 * newer than seq_last_count */
1777 if ((win_count > cb->last_counter
1778 && win_count - cb->last_counter > TFRC_WIN_COUNT_PER_RTT) ||
1779 (win_count < cb->last_counter
1780 && cb->last_counter - win_count < TFRC_WIN_COUNT_LIMIT - TFRC_WIN_COUNT_PER_RTT)) {
1781
1782 TFRC_DEBUG((LOG_INFO, "TFRC - Send a feedback packet (%i)(win_count larger) (tfrc_recv_packet_recv)\n", (win_count - cb->last_counter + TFRC_WIN_COUNT_LIMIT) % TFRC_WIN_COUNT_LIMIT));
1783
1784 tfrc_recv_send_feedback(cb);
1785 }
1786 } /* end newer seqnum */
1787 } /* end p > p_prev */
1788
1789 }
1790 break;
1791 default:
1792 panic("tfrc_recv_packet_recv: Illegal state!");
1793 break;
1794 }
1795
1796 } /* end if not pure ack */
1797 rp_release:
1798 mutex_exit(&(cb->mutex));
1799 }
1800
1801
1802 /*
1803 * fixpoint routines
1804 */
1805 static void
normalize(long long * num,long long * denom)1806 normalize(long long *num, long long *denom)
1807 {
1808 static const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 0 };
1809 int i;
1810
1811 if (!*denom) return;
1812 if (*denom < 0) {
1813 *num *= (-1);
1814 *denom *= (-1);
1815 }
1816
1817 if (*num % *denom == 0) {
1818 *num /= *denom;
1819 *denom = 1;
1820 }
1821 for (i = 0; prime[i]; i++)
1822 while (*num % prime[i] == 0 && *denom % prime[i] == 0) {
1823 *num /= prime[i];
1824 *denom /= prime[i];
1825 }
1826 }
1827
1828 struct fixpoint *
fixpoint_add(struct fixpoint * x,const struct fixpoint * a,const struct fixpoint * b)1829 fixpoint_add(struct fixpoint *x, const struct fixpoint *a,
1830 const struct fixpoint *b)
1831 {
1832 long long num, denom;
1833
1834 num = a->num * b->denom + a->denom * b->num;
1835 denom = a->denom * b->denom;
1836 normalize(&num, &denom);
1837
1838 x->num = num;
1839 x->denom = denom;
1840 return (x);
1841 }
1842
1843 struct fixpoint *
fixpoint_sub(struct fixpoint * x,const struct fixpoint * a,const struct fixpoint * b)1844 fixpoint_sub(struct fixpoint *x, const struct fixpoint *a,
1845 const struct fixpoint *b)
1846 {
1847 long long num, denom;
1848
1849 if (!a->denom) {
1850 x->num = -1 * b->num;
1851 x->denom = -1 * b->denom;
1852 return (x);
1853 }
1854 if (!b->denom) {
1855 x->num = a->num;
1856 x->denom = a->denom;
1857 return (x);
1858 }
1859 num = a->num * b->denom - a->denom * b->num;
1860 denom = a->denom * b->denom;
1861 normalize(&num, &denom);
1862
1863 x->num = num;
1864 x->denom = denom;
1865 return (x);
1866 }
1867
1868 int
fixpoint_cmp(const struct fixpoint * a,const struct fixpoint * b)1869 fixpoint_cmp(const struct fixpoint *a, const struct fixpoint *b)
1870 {
1871 struct fixpoint x;
1872
1873 fixpoint_sub(&x, a, b);
1874 if (x.num > 0)
1875 return (1);
1876 else if (x.num < 0)
1877 return (-1);
1878 else
1879 return (0);
1880 }
1881
1882 struct fixpoint *
fixpoint_mul(struct fixpoint * x,const struct fixpoint * a,const struct fixpoint * b)1883 fixpoint_mul(struct fixpoint *x, const struct fixpoint *a,
1884 const struct fixpoint *b)
1885 {
1886 long long num, denom;
1887
1888 num = a->num * b->num;
1889 denom = a->denom * b->denom;
1890 normalize(&num, &denom);
1891
1892 x->num = num;
1893 x->denom = denom;
1894 return (x);
1895 }
1896
1897 struct fixpoint *
fixpoint_div(struct fixpoint * x,const struct fixpoint * a,const struct fixpoint * b)1898 fixpoint_div(struct fixpoint *x, const struct fixpoint *a,
1899 const struct fixpoint *b)
1900 {
1901 long long num, denom;
1902
1903 num = a->num * b->denom;
1904 denom = a->denom * b->num;
1905 normalize(&num, &denom);
1906
1907 x->num = num;
1908 x->denom = denom;
1909 return (x);
1910 }
1911
1912 long
fixpoint_getlong(const struct fixpoint * x)1913 fixpoint_getlong(const struct fixpoint *x)
1914 {
1915
1916 if (x->denom == 0)
1917 return (0);
1918 return (x->num / x->denom);
1919 }
1920
1921 const struct fixpoint flargex = { 2LL, 1000LL };
1922 const struct fixpoint fsmallx = { 1LL, 100000LL };
1923 const struct fixpoint fsmallstep = { 4LL, 1000000LL };
1924
1925 /*
1926 * FLOOKUP macro. NOTE! 0<=(int x)<=1
1927 * Tested u:OK
1928 */
1929 const struct fixpoint *
flookup(const struct fixpoint * x)1930 flookup(const struct fixpoint *x)
1931 {
1932 static const struct fixpoint y = { 250000, 1 };
1933 struct fixpoint z;
1934 int i;
1935
1936 if (fixpoint_cmp(x, &flargex) >= 0) {
1937 if (x->num == 0)
1938 return NULL;
1939 i = x->denom / x->num;
1940 #ifdef TFRCDEBUG
1941 if (i >= sizeof(flarge_table) / sizeof(flarge_table[0]))
1942 panic("flarge_table lookup failed");
1943 #endif
1944
1945 return &flarge_table[i];
1946 } else {
1947 fixpoint_mul(&z, x, &y);
1948 if (z.num == 0)
1949 return NULL;
1950 i = fixpoint_getlong(&z);
1951 #ifdef TFRCDEBUG
1952 if (i >= sizeof(fsmall_table) / sizeof(fsmall_table[0]))
1953 panic("fsmall_table lookup failed");
1954 #endif
1955
1956 return &fsmall_table[i];
1957 }
1958 }
1959
1960 /*
1961 * Inverse of the FLOOKUP above
1962 * args: fvalue - function value to match
1963 * returns: p closest to that value
1964 * Tested u:OK
1965 */
1966 const struct fixpoint *
tfrc_flookup_reverse(const struct fixpoint * fvalue)1967 tfrc_flookup_reverse(const struct fixpoint *fvalue)
1968 {
1969 static struct fixpoint x;
1970 int ctr;
1971
1972 if (fixpoint_cmp(fvalue, &flarge_table[1]) >= 0) {
1973 /* 1.0 */
1974 x.num = 1;
1975 x.denom = 1;
1976 return &x;
1977 } else if (fixpoint_cmp(fvalue, &flarge_table[sizeof(flarge_table) /
1978 sizeof(flarge_table[0]) - 1]) >= 0) {
1979 ctr = sizeof(flarge_table) / sizeof(flarge_table[0]) - 1;
1980 while (ctr > 1 && fixpoint_cmp(fvalue, &flarge_table[ctr]) >= 0)
1981 ctr--;
1982
1983 /* round to smallest */
1984 ctr = ctr + 1;
1985
1986 /* round to nearest */
1987 return &flarge_table[ctr];
1988 } else if (fixpoint_cmp(fvalue, &fsmall_table[0]) >= 0) {
1989 ctr = 0;
1990 while (ctr < sizeof(fsmall_table) / sizeof(fsmall_table[0]) &&
1991 fixpoint_cmp(fvalue, &fsmall_table[ctr]) > 0)
1992 ctr++;
1993 x = fsmallstep;
1994 x.num *= ctr;
1995 return &x;
1996 }
1997 return &fsmallstep;
1998 }
1999