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