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