net/dccp/ccids/ccid2.c

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