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