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