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