Merge commit 'v2.6.27-rc8' into genirq
[linux-2.6] / 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
29 #include "../ccid.h"
30 #include "../dccp.h"
31 #include "ccid2.h"
32
33
34 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
35 static int ccid2_debug;
36 #define ccid2_pr_debug(format, a...)    DCCP_PR_DEBUG(ccid2_debug, format, ##a)
37
38 static 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
84 static 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
125 static 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
135 static 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 > 0xFFFF)               /* RFC 4340, 11.3 */
151                 val = 0xFFFF;
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
160 static 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
166 static void ccid2_start_rto_timer(struct sock *sk);
167
168 static void ccid2_hc_tx_rto_expire(unsigned long data)
169 {
170         struct sock *sk = (struct sock *)data;
171         struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
172         long s;
173
174         bh_lock_sock(sk);
175         if (sock_owned_by_user(sk)) {
176                 sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer,
177                                jiffies + HZ / 5);
178                 goto out;
179         }
180
181         ccid2_pr_debug("RTO_EXPIRE\n");
182
183         ccid2_hc_tx_check_sanity(hctx);
184
185         /* back-off timer */
186         hctx->ccid2hctx_rto <<= 1;
187
188         s = hctx->ccid2hctx_rto / HZ;
189         if (s > 60)
190                 hctx->ccid2hctx_rto = 60 * HZ;
191
192         ccid2_start_rto_timer(sk);
193
194         /* adjust pipe, cwnd etc */
195         hctx->ccid2hctx_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);
210 out:
211         bh_unlock_sock(sk);
212         sock_put(sk);
213 }
214
215 static 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
226 static 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  */
327 static 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
380 out_invalid_option:
381         DCCP_BUG("Invalid option - this should not happen (previous parsing)!");
382         return -1;
383 }
384
385 static 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
393 static 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
473 static 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
486 static 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
505 static 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
705 static 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
742 static 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
754 static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
755 {
756         const struct dccp_sock *dp = dccp_sk(sk);
757         struct ccid2_hc_rx_sock *hcrx = ccid2_hc_rx_sk(sk);
758
759         switch (DCCP_SKB_CB(skb)->dccpd_type) {
760         case DCCP_PKT_DATA:
761         case DCCP_PKT_DATAACK:
762                 hcrx->ccid2hcrx_data++;
763                 if (hcrx->ccid2hcrx_data >= dp->dccps_r_ack_ratio) {
764                         dccp_send_ack(sk);
765                         hcrx->ccid2hcrx_data = 0;
766                 }
767                 break;
768         }
769 }
770
771 static struct ccid_operations ccid2 = {
772         .ccid_id                = DCCPC_CCID2,
773         .ccid_name              = "TCP-like",
774         .ccid_owner             = THIS_MODULE,
775         .ccid_hc_tx_obj_size    = sizeof(struct ccid2_hc_tx_sock),
776         .ccid_hc_tx_init        = ccid2_hc_tx_init,
777         .ccid_hc_tx_exit        = ccid2_hc_tx_exit,
778         .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet,
779         .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent,
780         .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv,
781         .ccid_hc_rx_obj_size    = sizeof(struct ccid2_hc_rx_sock),
782         .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv,
783 };
784
785 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
786 module_param(ccid2_debug, bool, 0444);
787 MODULE_PARM_DESC(ccid2_debug, "Enable debug messages");
788 #endif
789
790 static __init int ccid2_module_init(void)
791 {
792         return ccid_register(&ccid2);
793 }
794 module_init(ccid2_module_init);
795
796 static __exit void ccid2_module_exit(void)
797 {
798         ccid_unregister(&ccid2);
799 }
800 module_exit(ccid2_module_exit);
801
802 MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>");
803 MODULE_DESCRIPTION("DCCP TCP-Like (CCID2) CCID");
804 MODULE_LICENSE("GPL");
805 MODULE_ALIAS("net-dccp-ccid-2");