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