1 /* 2 * net/dccp/ccids/ccid2.c 3 * 4 * Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk> 5 * 6 * Changes to meet Linux coding standards, and DCCP infrastructure fixes. 7 * 8 * Copyright (c) 2006 Arnaldo Carvalho de Melo <acme@conectiva.com.br> 9 * 10 * This program is free software; you can redistribute it and/or modify 11 * it under the terms of the GNU General Public License as published by 12 * the Free Software Foundation; either version 2 of the License, or 13 * (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 23 */ 24 25 /* 26 * This implementation should follow RFC 4341 27 * 28 * BUGS: 29 * - sequence number wrapping 30 */ 31 32 #include "../ccid.h" 33 #include "../dccp.h" 34 #include "ccid2.h" 35 36 37 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG 38 static int ccid2_debug; 39 #define ccid2_pr_debug(format, a...) DCCP_PR_DEBUG(ccid2_debug, format, ##a) 40 41 static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx) 42 { 43 int len = 0; 44 int pipe = 0; 45 struct ccid2_seq *seqp = hctx->ccid2hctx_seqh; 46 47 /* there is data in the chain */ 48 if (seqp != hctx->ccid2hctx_seqt) { 49 seqp = seqp->ccid2s_prev; 50 len++; 51 if (!seqp->ccid2s_acked) 52 pipe++; 53 54 while (seqp != hctx->ccid2hctx_seqt) { 55 struct ccid2_seq *prev = seqp->ccid2s_prev; 56 57 len++; 58 if (!prev->ccid2s_acked) 59 pipe++; 60 61 /* packets are sent sequentially */ 62 BUG_ON(seqp->ccid2s_seq <= prev->ccid2s_seq); 63 BUG_ON(time_before(seqp->ccid2s_sent, 64 prev->ccid2s_sent)); 65 66 seqp = prev; 67 } 68 } 69 70 BUG_ON(pipe != hctx->ccid2hctx_pipe); 71 ccid2_pr_debug("len of chain=%d\n", len); 72 73 do { 74 seqp = seqp->ccid2s_prev; 75 len++; 76 } while (seqp != hctx->ccid2hctx_seqh); 77 78 ccid2_pr_debug("total len=%d\n", len); 79 BUG_ON(len != hctx->ccid2hctx_seqbufc * CCID2_SEQBUF_LEN); 80 } 81 #else 82 #define ccid2_pr_debug(format, a...) 83 #define ccid2_hc_tx_check_sanity(hctx) 84 #endif 85 86 static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hctx, int num, 87 gfp_t gfp) 88 { 89 struct ccid2_seq *seqp; 90 int i; 91 92 /* check if we have space to preserve the pointer to the buffer */ 93 if (hctx->ccid2hctx_seqbufc >= (sizeof(hctx->ccid2hctx_seqbuf) / 94 sizeof(struct ccid2_seq*))) 95 return -ENOMEM; 96 97 /* allocate buffer and initialize linked list */ 98 seqp = kmalloc(sizeof(*seqp) * num, gfp); 99 if (seqp == NULL) 100 return -ENOMEM; 101 102 for (i = 0; i < (num - 1); i++) { 103 seqp[i].ccid2s_next = &seqp[i + 1]; 104 seqp[i + 1].ccid2s_prev = &seqp[i]; 105 } 106 seqp[num - 1].ccid2s_next = seqp; 107 seqp->ccid2s_prev = &seqp[num - 1]; 108 109 /* This is the first allocation. Initiate the head and tail. */ 110 if (hctx->ccid2hctx_seqbufc == 0) 111 hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqt = seqp; 112 else { 113 /* link the existing list with the one we just created */ 114 hctx->ccid2hctx_seqh->ccid2s_next = seqp; 115 seqp->ccid2s_prev = hctx->ccid2hctx_seqh; 116 117 hctx->ccid2hctx_seqt->ccid2s_prev = &seqp[num - 1]; 118 seqp[num - 1].ccid2s_next = hctx->ccid2hctx_seqt; 119 } 120 121 /* store the original pointer to the buffer so we can free it */ 122 hctx->ccid2hctx_seqbuf[hctx->ccid2hctx_seqbufc] = seqp; 123 hctx->ccid2hctx_seqbufc++; 124 125 return 0; 126 } 127 128 static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) 129 { 130 struct ccid2_hc_tx_sock *hctx; 131 132 switch (DCCP_SKB_CB(skb)->dccpd_type) { 133 case 0: /* XXX data packets from userland come through like this */ 134 case DCCP_PKT_DATA: 135 case DCCP_PKT_DATAACK: 136 break; 137 /* No congestion control on other packets */ 138 default: 139 return 0; 140 } 141 142 hctx = ccid2_hc_tx_sk(sk); 143 144 ccid2_pr_debug("pipe=%d cwnd=%d\n", hctx->ccid2hctx_pipe, 145 hctx->ccid2hctx_cwnd); 146 147 if (hctx->ccid2hctx_pipe < hctx->ccid2hctx_cwnd) { 148 /* OK we can send... make sure previous packet was sent off */ 149 if (!hctx->ccid2hctx_sendwait) { 150 hctx->ccid2hctx_sendwait = 1; 151 return 0; 152 } 153 } 154 155 return 1; /* XXX CCID should dequeue when ready instead of polling */ 156 } 157 158 static void ccid2_change_l_ack_ratio(struct sock *sk, int val) 159 { 160 struct dccp_sock *dp = dccp_sk(sk); 161 /* 162 * XXX I don't really agree with val != 2. If cwnd is 1, ack ratio 163 * should be 1... it shouldn't be allowed to become 2. 164 * -sorbo. 165 */ 166 if (val != 2) { 167 const struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 168 int max = hctx->ccid2hctx_cwnd / 2; 169 170 /* round up */ 171 if (hctx->ccid2hctx_cwnd & 1) 172 max++; 173 174 if (val > max) 175 val = max; 176 } 177 178 ccid2_pr_debug("changing local ack ratio to %d\n", val); 179 WARN_ON(val <= 0); 180 dp->dccps_l_ack_ratio = val; 181 } 182 183 static void ccid2_change_cwnd(struct ccid2_hc_tx_sock *hctx, int val) 184 { 185 if (val == 0) 186 val = 1; 187 188 /* XXX do we need to change ack ratio? */ 189 ccid2_pr_debug("change cwnd to %d\n", val); 190 191 BUG_ON(val < 1); 192 hctx->ccid2hctx_cwnd = val; 193 } 194 195 static void ccid2_change_srtt(struct ccid2_hc_tx_sock *hctx, long val) 196 { 197 ccid2_pr_debug("change SRTT to %ld\n", val); 198 hctx->ccid2hctx_srtt = val; 199 } 200 201 static void ccid2_change_pipe(struct ccid2_hc_tx_sock *hctx, long val) 202 { 203 hctx->ccid2hctx_pipe = val; 204 } 205 206 static void ccid2_start_rto_timer(struct sock *sk); 207 208 static void ccid2_hc_tx_rto_expire(unsigned long data) 209 { 210 struct sock *sk = (struct sock *)data; 211 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 212 long s; 213 214 bh_lock_sock(sk); 215 if (sock_owned_by_user(sk)) { 216 sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer, 217 jiffies + HZ / 5); 218 goto out; 219 } 220 221 ccid2_pr_debug("RTO_EXPIRE\n"); 222 223 ccid2_hc_tx_check_sanity(hctx); 224 225 /* back-off timer */ 226 hctx->ccid2hctx_rto <<= 1; 227 228 s = hctx->ccid2hctx_rto / HZ; 229 if (s > 60) 230 hctx->ccid2hctx_rto = 60 * HZ; 231 232 ccid2_start_rto_timer(sk); 233 234 /* adjust pipe, cwnd etc */ 235 ccid2_change_pipe(hctx, 0); 236 hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd >> 1; 237 if (hctx->ccid2hctx_ssthresh < 2) 238 hctx->ccid2hctx_ssthresh = 2; 239 ccid2_change_cwnd(hctx, 1); 240 241 /* clear state about stuff we sent */ 242 hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh; 243 hctx->ccid2hctx_ssacks = 0; 244 hctx->ccid2hctx_acks = 0; 245 hctx->ccid2hctx_sent = 0; 246 247 /* clear ack ratio state. */ 248 hctx->ccid2hctx_arsent = 0; 249 hctx->ccid2hctx_ackloss = 0; 250 hctx->ccid2hctx_rpseq = 0; 251 hctx->ccid2hctx_rpdupack = -1; 252 ccid2_change_l_ack_ratio(sk, 1); 253 ccid2_hc_tx_check_sanity(hctx); 254 out: 255 bh_unlock_sock(sk); 256 sock_put(sk); 257 } 258 259 static void ccid2_start_rto_timer(struct sock *sk) 260 { 261 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 262 263 ccid2_pr_debug("setting RTO timeout=%ld\n", hctx->ccid2hctx_rto); 264 265 BUG_ON(timer_pending(&hctx->ccid2hctx_rtotimer)); 266 sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer, 267 jiffies + hctx->ccid2hctx_rto); 268 } 269 270 static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) 271 { 272 struct dccp_sock *dp = dccp_sk(sk); 273 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 274 struct ccid2_seq *next; 275 u64 seq; 276 277 ccid2_hc_tx_check_sanity(hctx); 278 279 BUG_ON(!hctx->ccid2hctx_sendwait); 280 hctx->ccid2hctx_sendwait = 0; 281 ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe + 1); 282 BUG_ON(hctx->ccid2hctx_pipe < 0); 283 284 /* There is an issue. What if another packet is sent between 285 * packet_send() and packet_sent(). Then the sequence number would be 286 * wrong. 287 * -sorbo. 288 */ 289 seq = dp->dccps_gss; 290 291 hctx->ccid2hctx_seqh->ccid2s_seq = seq; 292 hctx->ccid2hctx_seqh->ccid2s_acked = 0; 293 hctx->ccid2hctx_seqh->ccid2s_sent = jiffies; 294 295 next = hctx->ccid2hctx_seqh->ccid2s_next; 296 /* check if we need to alloc more space */ 297 if (next == hctx->ccid2hctx_seqt) { 298 int rc; 299 300 ccid2_pr_debug("allocating more space in history\n"); 301 rc = ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_KERNEL); 302 BUG_ON(rc); /* XXX what do we do? */ 303 304 next = hctx->ccid2hctx_seqh->ccid2s_next; 305 BUG_ON(next == hctx->ccid2hctx_seqt); 306 } 307 hctx->ccid2hctx_seqh = next; 308 309 ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd, 310 hctx->ccid2hctx_pipe); 311 312 hctx->ccid2hctx_sent++; 313 314 /* Ack Ratio. Need to maintain a concept of how many windows we sent */ 315 hctx->ccid2hctx_arsent++; 316 /* We had an ack loss in this window... */ 317 if (hctx->ccid2hctx_ackloss) { 318 if (hctx->ccid2hctx_arsent >= hctx->ccid2hctx_cwnd) { 319 hctx->ccid2hctx_arsent = 0; 320 hctx->ccid2hctx_ackloss = 0; 321 } 322 } else { 323 /* No acks lost up to now... */ 324 /* decrease ack ratio if enough packets were sent */ 325 if (dp->dccps_l_ack_ratio > 1) { 326 /* XXX don't calculate denominator each time */ 327 int denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio - 328 dp->dccps_l_ack_ratio; 329 330 denom = hctx->ccid2hctx_cwnd * hctx->ccid2hctx_cwnd / denom; 331 332 if (hctx->ccid2hctx_arsent >= denom) { 333 ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio - 1); 334 hctx->ccid2hctx_arsent = 0; 335 } 336 } else { 337 /* we can't increase ack ratio further [1] */ 338 hctx->ccid2hctx_arsent = 0; /* or maybe set it to cwnd*/ 339 } 340 } 341 342 /* setup RTO timer */ 343 if (!timer_pending(&hctx->ccid2hctx_rtotimer)) 344 ccid2_start_rto_timer(sk); 345 346 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG 347 ccid2_pr_debug("pipe=%d\n", hctx->ccid2hctx_pipe); 348 ccid2_pr_debug("Sent: seq=%llu\n", (unsigned long long)seq); 349 do { 350 struct ccid2_seq *seqp = hctx->ccid2hctx_seqt; 351 352 while (seqp != hctx->ccid2hctx_seqh) { 353 ccid2_pr_debug("out seq=%llu acked=%d time=%lu\n", 354 (unsigned long long)seqp->ccid2s_seq, 355 seqp->ccid2s_acked, seqp->ccid2s_sent); 356 seqp = seqp->ccid2s_next; 357 } 358 } while (0); 359 ccid2_pr_debug("=========\n"); 360 ccid2_hc_tx_check_sanity(hctx); 361 #endif 362 } 363 364 /* XXX Lame code duplication! 365 * returns -1 if none was found. 366 * else returns the next offset to use in the function call. 367 */ 368 static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset, 369 unsigned char **vec, unsigned char *veclen) 370 { 371 const struct dccp_hdr *dh = dccp_hdr(skb); 372 unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb); 373 unsigned char *opt_ptr; 374 const unsigned char *opt_end = (unsigned char *)dh + 375 (dh->dccph_doff * 4); 376 unsigned char opt, len; 377 unsigned char *value; 378 379 BUG_ON(offset < 0); 380 options += offset; 381 opt_ptr = options; 382 if (opt_ptr >= opt_end) 383 return -1; 384 385 while (opt_ptr != opt_end) { 386 opt = *opt_ptr++; 387 len = 0; 388 value = NULL; 389 390 /* Check if this isn't a single byte option */ 391 if (opt > DCCPO_MAX_RESERVED) { 392 if (opt_ptr == opt_end) 393 goto out_invalid_option; 394 395 len = *opt_ptr++; 396 if (len < 3) 397 goto out_invalid_option; 398 /* 399 * Remove the type and len fields, leaving 400 * just the value size 401 */ 402 len -= 2; 403 value = opt_ptr; 404 opt_ptr += len; 405 406 if (opt_ptr > opt_end) 407 goto out_invalid_option; 408 } 409 410 switch (opt) { 411 case DCCPO_ACK_VECTOR_0: 412 case DCCPO_ACK_VECTOR_1: 413 *vec = value; 414 *veclen = len; 415 return offset + (opt_ptr - options); 416 } 417 } 418 419 return -1; 420 421 out_invalid_option: 422 DCCP_BUG("Invalid option - this should not happen (previous parsing)!"); 423 return -1; 424 } 425 426 static void ccid2_hc_tx_kill_rto_timer(struct sock *sk) 427 { 428 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 429 430 sk_stop_timer(sk, &hctx->ccid2hctx_rtotimer); 431 ccid2_pr_debug("deleted RTO timer\n"); 432 } 433 434 static inline void ccid2_new_ack(struct sock *sk, 435 struct ccid2_seq *seqp, 436 unsigned int *maxincr) 437 { 438 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 439 440 /* slow start */ 441 if (hctx->ccid2hctx_cwnd < hctx->ccid2hctx_ssthresh) { 442 hctx->ccid2hctx_acks = 0; 443 444 /* We can increase cwnd at most maxincr [ack_ratio/2] */ 445 if (*maxincr) { 446 /* increase every 2 acks */ 447 hctx->ccid2hctx_ssacks++; 448 if (hctx->ccid2hctx_ssacks == 2) { 449 ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd+1); 450 hctx->ccid2hctx_ssacks = 0; 451 *maxincr = *maxincr - 1; 452 } 453 } else { 454 /* increased cwnd enough for this single ack */ 455 hctx->ccid2hctx_ssacks = 0; 456 } 457 } else { 458 hctx->ccid2hctx_ssacks = 0; 459 hctx->ccid2hctx_acks++; 460 461 if (hctx->ccid2hctx_acks >= hctx->ccid2hctx_cwnd) { 462 ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd + 1); 463 hctx->ccid2hctx_acks = 0; 464 } 465 } 466 467 /* update RTO */ 468 if (hctx->ccid2hctx_srtt == -1 || 469 time_after(jiffies, hctx->ccid2hctx_lastrtt + hctx->ccid2hctx_srtt)) { 470 unsigned long r = (long)jiffies - (long)seqp->ccid2s_sent; 471 int s; 472 473 /* first measurement */ 474 if (hctx->ccid2hctx_srtt == -1) { 475 ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n", 476 r, jiffies, 477 (unsigned long long)seqp->ccid2s_seq); 478 ccid2_change_srtt(hctx, r); 479 hctx->ccid2hctx_rttvar = r >> 1; 480 } else { 481 /* RTTVAR */ 482 long tmp = hctx->ccid2hctx_srtt - r; 483 long srtt; 484 485 if (tmp < 0) 486 tmp *= -1; 487 488 tmp >>= 2; 489 hctx->ccid2hctx_rttvar *= 3; 490 hctx->ccid2hctx_rttvar >>= 2; 491 hctx->ccid2hctx_rttvar += tmp; 492 493 /* SRTT */ 494 srtt = hctx->ccid2hctx_srtt; 495 srtt *= 7; 496 srtt >>= 3; 497 tmp = r >> 3; 498 srtt += tmp; 499 ccid2_change_srtt(hctx, srtt); 500 } 501 s = hctx->ccid2hctx_rttvar << 2; 502 /* clock granularity is 1 when based on jiffies */ 503 if (!s) 504 s = 1; 505 hctx->ccid2hctx_rto = hctx->ccid2hctx_srtt + s; 506 507 /* must be at least a second */ 508 s = hctx->ccid2hctx_rto / HZ; 509 /* DCCP doesn't require this [but I like it cuz my code sux] */ 510 #if 1 511 if (s < 1) 512 hctx->ccid2hctx_rto = HZ; 513 #endif 514 /* max 60 seconds */ 515 if (s > 60) 516 hctx->ccid2hctx_rto = HZ * 60; 517 518 hctx->ccid2hctx_lastrtt = jiffies; 519 520 ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n", 521 hctx->ccid2hctx_srtt, hctx->ccid2hctx_rttvar, 522 hctx->ccid2hctx_rto, HZ, r); 523 hctx->ccid2hctx_sent = 0; 524 } 525 526 /* we got a new ack, so re-start RTO timer */ 527 ccid2_hc_tx_kill_rto_timer(sk); 528 ccid2_start_rto_timer(sk); 529 } 530 531 static void ccid2_hc_tx_dec_pipe(struct sock *sk) 532 { 533 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 534 535 ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe-1); 536 BUG_ON(hctx->ccid2hctx_pipe < 0); 537 538 if (hctx->ccid2hctx_pipe == 0) 539 ccid2_hc_tx_kill_rto_timer(sk); 540 } 541 542 static void ccid2_congestion_event(struct ccid2_hc_tx_sock *hctx, 543 struct ccid2_seq *seqp) 544 { 545 if (time_before(seqp->ccid2s_sent, hctx->ccid2hctx_last_cong)) { 546 ccid2_pr_debug("Multiple losses in an RTT---treating as one\n"); 547 return; 548 } 549 550 hctx->ccid2hctx_last_cong = jiffies; 551 552 ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd >> 1); 553 hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd; 554 if (hctx->ccid2hctx_ssthresh < 2) 555 hctx->ccid2hctx_ssthresh = 2; 556 } 557 558 static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) 559 { 560 struct dccp_sock *dp = dccp_sk(sk); 561 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 562 u64 ackno, seqno; 563 struct ccid2_seq *seqp; 564 unsigned char *vector; 565 unsigned char veclen; 566 int offset = 0; 567 int done = 0; 568 unsigned int maxincr = 0; 569 570 ccid2_hc_tx_check_sanity(hctx); 571 /* check reverse path congestion */ 572 seqno = DCCP_SKB_CB(skb)->dccpd_seq; 573 574 /* XXX this whole "algorithm" is broken. Need to fix it to keep track 575 * of the seqnos of the dupacks so that rpseq and rpdupack are correct 576 * -sorbo. 577 */ 578 /* need to bootstrap */ 579 if (hctx->ccid2hctx_rpdupack == -1) { 580 hctx->ccid2hctx_rpdupack = 0; 581 hctx->ccid2hctx_rpseq = seqno; 582 } else { 583 /* check if packet is consecutive */ 584 if ((hctx->ccid2hctx_rpseq + 1) == seqno) 585 hctx->ccid2hctx_rpseq++; 586 /* it's a later packet */ 587 else if (after48(seqno, hctx->ccid2hctx_rpseq)) { 588 hctx->ccid2hctx_rpdupack++; 589 590 /* check if we got enough dupacks */ 591 if (hctx->ccid2hctx_rpdupack >= 592 hctx->ccid2hctx_numdupack) { 593 hctx->ccid2hctx_rpdupack = -1; /* XXX lame */ 594 hctx->ccid2hctx_rpseq = 0; 595 596 ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio << 1); 597 } 598 } 599 } 600 601 /* check forward path congestion */ 602 /* still didn't send out new data packets */ 603 if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) 604 return; 605 606 switch (DCCP_SKB_CB(skb)->dccpd_type) { 607 case DCCP_PKT_ACK: 608 case DCCP_PKT_DATAACK: 609 break; 610 default: 611 return; 612 } 613 614 ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq; 615 if (after48(ackno, hctx->ccid2hctx_high_ack)) 616 hctx->ccid2hctx_high_ack = ackno; 617 618 seqp = hctx->ccid2hctx_seqt; 619 while (before48(seqp->ccid2s_seq, ackno)) { 620 seqp = seqp->ccid2s_next; 621 if (seqp == hctx->ccid2hctx_seqh) { 622 seqp = hctx->ccid2hctx_seqh->ccid2s_prev; 623 break; 624 } 625 } 626 627 /* If in slow-start, cwnd can increase at most Ack Ratio / 2 packets for 628 * this single ack. I round up. 629 * -sorbo. 630 */ 631 maxincr = dp->dccps_l_ack_ratio >> 1; 632 maxincr++; 633 634 /* go through all ack vectors */ 635 while ((offset = ccid2_ackvector(sk, skb, offset, 636 &vector, &veclen)) != -1) { 637 /* go through this ack vector */ 638 while (veclen--) { 639 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; 640 u64 ackno_end_rl; 641 642 dccp_set_seqno(&ackno_end_rl, ackno - rl); 643 ccid2_pr_debug("ackvec start:%llu end:%llu\n", 644 (unsigned long long)ackno, 645 (unsigned long long)ackno_end_rl); 646 /* if the seqno we are analyzing is larger than the 647 * current ackno, then move towards the tail of our 648 * seqnos. 649 */ 650 while (after48(seqp->ccid2s_seq, ackno)) { 651 if (seqp == hctx->ccid2hctx_seqt) { 652 done = 1; 653 break; 654 } 655 seqp = seqp->ccid2s_prev; 656 } 657 if (done) 658 break; 659 660 /* check all seqnos in the range of the vector 661 * run length 662 */ 663 while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) { 664 const u8 state = *vector & 665 DCCP_ACKVEC_STATE_MASK; 666 667 /* new packet received or marked */ 668 if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED && 669 !seqp->ccid2s_acked) { 670 if (state == 671 DCCP_ACKVEC_STATE_ECN_MARKED) { 672 ccid2_congestion_event(hctx, 673 seqp); 674 } else 675 ccid2_new_ack(sk, seqp, 676 &maxincr); 677 678 seqp->ccid2s_acked = 1; 679 ccid2_pr_debug("Got ack for %llu\n", 680 (unsigned long long)seqp->ccid2s_seq); 681 ccid2_hc_tx_dec_pipe(sk); 682 } 683 if (seqp == hctx->ccid2hctx_seqt) { 684 done = 1; 685 break; 686 } 687 seqp = seqp->ccid2s_next; 688 } 689 if (done) 690 break; 691 692 693 dccp_set_seqno(&ackno, ackno_end_rl - 1); 694 vector++; 695 } 696 if (done) 697 break; 698 } 699 700 /* The state about what is acked should be correct now 701 * Check for NUMDUPACK 702 */ 703 seqp = hctx->ccid2hctx_seqt; 704 while (before48(seqp->ccid2s_seq, hctx->ccid2hctx_high_ack)) { 705 seqp = seqp->ccid2s_next; 706 if (seqp == hctx->ccid2hctx_seqh) { 707 seqp = hctx->ccid2hctx_seqh->ccid2s_prev; 708 break; 709 } 710 } 711 done = 0; 712 while (1) { 713 if (seqp->ccid2s_acked) { 714 done++; 715 if (done == hctx->ccid2hctx_numdupack) 716 break; 717 } 718 if (seqp == hctx->ccid2hctx_seqt) 719 break; 720 seqp = seqp->ccid2s_prev; 721 } 722 723 /* If there are at least 3 acknowledgements, anything unacknowledged 724 * below the last sequence number is considered lost 725 */ 726 if (done == hctx->ccid2hctx_numdupack) { 727 struct ccid2_seq *last_acked = seqp; 728 729 /* check for lost packets */ 730 while (1) { 731 if (!seqp->ccid2s_acked) { 732 ccid2_pr_debug("Packet lost: %llu\n", 733 (unsigned long long)seqp->ccid2s_seq); 734 /* XXX need to traverse from tail -> head in 735 * order to detect multiple congestion events in 736 * one ack vector. 737 */ 738 ccid2_congestion_event(hctx, seqp); 739 ccid2_hc_tx_dec_pipe(sk); 740 } 741 if (seqp == hctx->ccid2hctx_seqt) 742 break; 743 seqp = seqp->ccid2s_prev; 744 } 745 746 hctx->ccid2hctx_seqt = last_acked; 747 } 748 749 /* trim acked packets in tail */ 750 while (hctx->ccid2hctx_seqt != hctx->ccid2hctx_seqh) { 751 if (!hctx->ccid2hctx_seqt->ccid2s_acked) 752 break; 753 754 hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next; 755 } 756 757 ccid2_hc_tx_check_sanity(hctx); 758 } 759 760 static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) 761 { 762 struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid); 763 764 ccid2_change_cwnd(hctx, 1); 765 /* Initialize ssthresh to infinity. This means that we will exit the 766 * initial slow-start after the first packet loss. This is what we 767 * want. 768 */ 769 hctx->ccid2hctx_ssthresh = ~0; 770 hctx->ccid2hctx_numdupack = 3; 771 hctx->ccid2hctx_seqbufc = 0; 772 773 /* XXX init ~ to window size... */ 774 if (ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_ATOMIC) != 0) 775 return -ENOMEM; 776 777 hctx->ccid2hctx_sent = 0; 778 hctx->ccid2hctx_rto = 3 * HZ; 779 ccid2_change_srtt(hctx, -1); 780 hctx->ccid2hctx_rttvar = -1; 781 hctx->ccid2hctx_lastrtt = 0; 782 hctx->ccid2hctx_rpdupack = -1; 783 hctx->ccid2hctx_last_cong = jiffies; 784 hctx->ccid2hctx_high_ack = 0; 785 786 hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire; 787 hctx->ccid2hctx_rtotimer.data = (unsigned long)sk; 788 init_timer(&hctx->ccid2hctx_rtotimer); 789 790 ccid2_hc_tx_check_sanity(hctx); 791 return 0; 792 } 793 794 static void ccid2_hc_tx_exit(struct sock *sk) 795 { 796 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); 797 int i; 798 799 ccid2_hc_tx_kill_rto_timer(sk); 800 801 for (i = 0; i < hctx->ccid2hctx_seqbufc; i++) 802 kfree(hctx->ccid2hctx_seqbuf[i]); 803 hctx->ccid2hctx_seqbufc = 0; 804 } 805 806 static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) 807 { 808 const struct dccp_sock *dp = dccp_sk(sk); 809 struct ccid2_hc_rx_sock *hcrx = ccid2_hc_rx_sk(sk); 810 811 switch (DCCP_SKB_CB(skb)->dccpd_type) { 812 case DCCP_PKT_DATA: 813 case DCCP_PKT_DATAACK: 814 hcrx->ccid2hcrx_data++; 815 if (hcrx->ccid2hcrx_data >= dp->dccps_r_ack_ratio) { 816 dccp_send_ack(sk); 817 hcrx->ccid2hcrx_data = 0; 818 } 819 break; 820 } 821 } 822 823 static struct ccid_operations ccid2 = { 824 .ccid_id = DCCPC_CCID2, 825 .ccid_name = "ccid2", 826 .ccid_owner = THIS_MODULE, 827 .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), 828 .ccid_hc_tx_init = ccid2_hc_tx_init, 829 .ccid_hc_tx_exit = ccid2_hc_tx_exit, 830 .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet, 831 .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent, 832 .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv, 833 .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock), 834 .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv, 835 }; 836 837 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG 838 module_param(ccid2_debug, int, 0444); 839 MODULE_PARM_DESC(ccid2_debug, "Enable debug messages"); 840 #endif 841 842 static __init int ccid2_module_init(void) 843 { 844 return ccid_register(&ccid2); 845 } 846 module_init(ccid2_module_init); 847 848 static __exit void ccid2_module_exit(void) 849 { 850 ccid_unregister(&ccid2); 851 } 852 module_exit(ccid2_module_exit); 853 854 MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>"); 855 MODULE_DESCRIPTION("DCCP TCP-Like (CCID2) CCID"); 856 MODULE_LICENSE("GPL"); 857 MODULE_ALIAS("net-dccp-ccid-2"); 858