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