1/* $KAME: dccp_tfrc.c,v 1.16 2006/03/01 17:34:08 nishida Exp $ */ 2/* $NetBSD: dccp_tfrc.c,v 1.12 2024/05/12 23:55:58 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.12 2024/05/12 23:55:58 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 */ 122const 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 178const struct fixpoint tfrc_smallest_p = { 4LL, 1000000LL }; 179 180/* External declarations */ 181extern int dccp_get_option(char *, int, int, char *, int); 182 183/* Forward declarations */ 184void tfrc_time_no_feedback(void *); 185void tfrc_time_send(void *); 186void tfrc_set_send_timer(struct tfrc_send_ccb *, struct timeval); 187void tfrc_updateX(struct tfrc_send_ccb *, struct timeval); 188const struct fixpoint *tfrc_calcX(u_int16_t, u_int32_t, 189 const struct fixpoint *); 190void tfrc_send_term(void *); 191 192static void normalize(long long *, long long *); 193struct fixpoint *fixpoint_add(struct fixpoint *, const struct fixpoint *, 194 const struct fixpoint *); 195struct fixpoint *fixpoint_sub(struct fixpoint *, const struct fixpoint *, 196 const struct fixpoint *); 197int fixpoint_cmp(const struct fixpoint *, const struct fixpoint *); 198struct fixpoint *fixpoint_mul(struct fixpoint *, const struct fixpoint *, 199 const struct fixpoint *); 200struct fixpoint *fixpoint_div(struct fixpoint *, const struct fixpoint *, 201 const struct fixpoint *); 202long fixpoint_getlong(const struct fixpoint *); 203 204const struct fixpoint *flookup(const struct fixpoint *); 205const 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 * 216tfrc_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 */ 230void 231tfrc_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 /* acquire 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 */ 270void 271tfrc_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 */ 308void 309tfrc_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 */ 363void 364tfrc_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; 476nf_release: 477 mutex_exit(&(cb->mutex)); 478} 479 480/* 481 * Removes ccb from memory 482 * args: ccb - ccb of sender 483 */ 484void 485tfrc_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 */ 508void * 509tfrc_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 */ 557void 558tfrc_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 */ 598int 599tfrc_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 uninitialized (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 709sp_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 */ 718void 719tfrc_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 817sps_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 */ 823void 824tfrc_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 - Received 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 - Received 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 } 1022sar_release: 1023 mutex_exit(&(cb->mutex)); 1024} 1025/* Receiver side */ 1026 1027/* Forward declarations */ 1028long tfrc_calclmean(struct tfrc_recv_ccb *); 1029void tfrc_recv_send_feedback(struct tfrc_recv_ccb *); 1030int tfrc_recv_add_hist(struct tfrc_recv_ccb *, struct r_hist_entry *); 1031void tfrc_recv_detectLoss(struct tfrc_recv_ccb *); 1032u_int32_t tfrc_recv_calcFirstLI(struct tfrc_recv_ccb *); 1033void 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}; */ 1037const 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 */ 1080long 1081tfrc_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 1156I_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 */ 1166void 1167tfrc_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 */ 1249u_int32_t 1250tfrc_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 */ 1341int 1342tfrc_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 */ 1448void 1449tfrc_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 occurred 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 */ 1508void 1509tfrc_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 */ 1605void * 1606tfrc_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 receiver 1641 * Tested u:OK 1642 */ 1643void 1644tfrc_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 */ 1690void 1691tfrc_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 initial 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 */ 1797rp_release: 1798 mutex_exit(&(cb->mutex)); 1799} 1800 1801 1802/* 1803 * fixpoint routines 1804 */ 1805static void 1806normalize(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 1828struct fixpoint * 1829fixpoint_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 1843struct fixpoint * 1844fixpoint_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 1868int 1869fixpoint_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 1882struct fixpoint * 1883fixpoint_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 1897struct fixpoint * 1898fixpoint_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 1912long 1913fixpoint_getlong(const struct fixpoint *x) 1914{ 1915 1916 if (x->denom == 0) 1917 return (0); 1918 return (x->num / x->denom); 1919} 1920 1921const struct fixpoint flargex = { 2LL, 1000LL }; 1922const struct fixpoint fsmallx = { 1LL, 100000LL }; 1923const struct fixpoint fsmallstep = { 4LL, 1000000LL }; 1924 1925/* 1926 * FLOOKUP macro. NOTE! 0<=(int x)<=1 1927 * Tested u:OK 1928 */ 1929const struct fixpoint * 1930flookup(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 */ 1966const struct fixpoint * 1967tfrc_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