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