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