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