2 * net/dccp/ccids/ccid2.c
4 * Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk>
6 * Changes to meet Linux coding standards, and DCCP infrastructure fixes.
8 * Copyright (c) 2006 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
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.
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.
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.
26 * This implementation should follow RFC 4341
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)
38 static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock
*hctx
)
42 struct ccid2_seq
*seqp
= hctx
->ccid2hctx_seqh
;
44 /* there is data in the chain */
45 if (seqp
!= hctx
->ccid2hctx_seqt
) {
46 seqp
= seqp
->ccid2s_prev
;
48 if (!seqp
->ccid2s_acked
)
51 while (seqp
!= hctx
->ccid2hctx_seqt
) {
52 struct ccid2_seq
*prev
= seqp
->ccid2s_prev
;
55 if (!prev
->ccid2s_acked
)
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
,
68 BUG_ON(pipe
!= hctx
->ccid2hctx_pipe
);
69 ccid2_pr_debug("len of chain=%d\n", len
);
72 seqp
= seqp
->ccid2s_prev
;
74 } while (seqp
!= hctx
->ccid2hctx_seqh
);
76 ccid2_pr_debug("total len=%d\n", len
);
77 BUG_ON(len
!= hctx
->ccid2hctx_seqbufc
* CCID2_SEQBUF_LEN
);
80 #define ccid2_pr_debug(format, a...)
81 #define ccid2_hc_tx_check_sanity(hctx)
84 static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock
*hctx
)
86 struct ccid2_seq
*seqp
;
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
*)))
94 /* allocate buffer and initialize linked list */
95 seqp
= kmalloc(CCID2_SEQBUF_LEN
* sizeof(struct ccid2_seq
), gfp_any());
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
];
103 seqp
[CCID2_SEQBUF_LEN
- 1].ccid2s_next
= seqp
;
104 seqp
->ccid2s_prev
= &seqp
[CCID2_SEQBUF_LEN
- 1];
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
;
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
;
114 hctx
->ccid2hctx_seqt
->ccid2s_prev
= &seqp
[CCID2_SEQBUF_LEN
- 1];
115 seqp
[CCID2_SEQBUF_LEN
- 1].ccid2s_next
= hctx
->ccid2hctx_seqt
;
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
++;
125 static int ccid2_hc_tx_send_packet(struct sock
*sk
, struct sk_buff
*skb
)
127 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
129 ccid2_pr_debug("pipe=%d cwnd=%d\n", hctx
->ccid2hctx_pipe
,
130 hctx
->ccid2hctx_cwnd
);
132 if (hctx
->ccid2hctx_pipe
< hctx
->ccid2hctx_cwnd
) {
133 /* OK we can send... make sure previous packet was sent off */
134 if (!hctx
->ccid2hctx_sendwait
) {
135 hctx
->ccid2hctx_sendwait
= 1;
140 return 1; /* XXX CCID should dequeue when ready instead of polling */
143 static void ccid2_change_l_ack_ratio(struct sock
*sk
, u32 val
)
145 struct dccp_sock
*dp
= dccp_sk(sk
);
146 u32 max_ratio
= DIV_ROUND_UP(ccid2_hc_tx_sk(sk
)->ccid2hctx_cwnd
, 2);
149 * Ensure that Ack Ratio does not exceed ceil(cwnd/2), which is (2) from
150 * RFC 4341, 6.1.2. We ignore the statement that Ack Ratio 2 is always
151 * acceptable since this causes starvation/deadlock whenever cwnd < 2.
152 * The same problem arises when Ack Ratio is 0 (ie. Ack Ratio disabled).
154 if (val
== 0 || val
> max_ratio
) {
155 DCCP_WARN("Limiting Ack Ratio (%u) to %u\n", val
, max_ratio
);
158 if (val
> 0xFFFF) /* RFC 4340, 11.3 */
161 if (val
== dp
->dccps_l_ack_ratio
)
164 ccid2_pr_debug("changing local ack ratio to %u\n", val
);
165 dp
->dccps_l_ack_ratio
= val
;
168 static void ccid2_change_cwnd(struct ccid2_hc_tx_sock
*hctx
, u32 val
)
170 hctx
->ccid2hctx_cwnd
= val
? : 1;
171 ccid2_pr_debug("changed cwnd to %u\n", hctx
->ccid2hctx_cwnd
);
174 static void ccid2_change_srtt(struct ccid2_hc_tx_sock
*hctx
, long val
)
176 ccid2_pr_debug("change SRTT to %ld\n", val
);
177 hctx
->ccid2hctx_srtt
= val
;
180 static void ccid2_change_pipe(struct ccid2_hc_tx_sock
*hctx
, long val
)
182 hctx
->ccid2hctx_pipe
= val
;
185 static void ccid2_start_rto_timer(struct sock
*sk
);
187 static void ccid2_hc_tx_rto_expire(unsigned long data
)
189 struct sock
*sk
= (struct sock
*)data
;
190 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
194 if (sock_owned_by_user(sk
)) {
195 sk_reset_timer(sk
, &hctx
->ccid2hctx_rtotimer
,
200 ccid2_pr_debug("RTO_EXPIRE\n");
202 ccid2_hc_tx_check_sanity(hctx
);
205 hctx
->ccid2hctx_rto
<<= 1;
207 s
= hctx
->ccid2hctx_rto
/ HZ
;
209 hctx
->ccid2hctx_rto
= 60 * HZ
;
211 ccid2_start_rto_timer(sk
);
213 /* adjust pipe, cwnd etc */
214 ccid2_change_pipe(hctx
, 0);
215 hctx
->ccid2hctx_ssthresh
= hctx
->ccid2hctx_cwnd
>> 1;
216 if (hctx
->ccid2hctx_ssthresh
< 2)
217 hctx
->ccid2hctx_ssthresh
= 2;
218 ccid2_change_cwnd(hctx
, 1);
220 /* clear state about stuff we sent */
221 hctx
->ccid2hctx_seqt
= hctx
->ccid2hctx_seqh
;
222 hctx
->ccid2hctx_ssacks
= 0;
223 hctx
->ccid2hctx_acks
= 0;
224 hctx
->ccid2hctx_sent
= 0;
226 /* clear ack ratio state. */
227 hctx
->ccid2hctx_rpseq
= 0;
228 hctx
->ccid2hctx_rpdupack
= -1;
229 ccid2_change_l_ack_ratio(sk
, 1);
230 ccid2_hc_tx_check_sanity(hctx
);
236 static void ccid2_start_rto_timer(struct sock
*sk
)
238 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
240 ccid2_pr_debug("setting RTO timeout=%ld\n", hctx
->ccid2hctx_rto
);
242 BUG_ON(timer_pending(&hctx
->ccid2hctx_rtotimer
));
243 sk_reset_timer(sk
, &hctx
->ccid2hctx_rtotimer
,
244 jiffies
+ hctx
->ccid2hctx_rto
);
247 static void ccid2_hc_tx_packet_sent(struct sock
*sk
, int more
, unsigned int len
)
249 struct dccp_sock
*dp
= dccp_sk(sk
);
250 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
251 struct ccid2_seq
*next
;
254 ccid2_hc_tx_check_sanity(hctx
);
256 BUG_ON(!hctx
->ccid2hctx_sendwait
);
257 hctx
->ccid2hctx_sendwait
= 0;
258 ccid2_change_pipe(hctx
, hctx
->ccid2hctx_pipe
+ 1);
259 BUG_ON(hctx
->ccid2hctx_pipe
< 0);
261 /* There is an issue. What if another packet is sent between
262 * packet_send() and packet_sent(). Then the sequence number would be
268 hctx
->ccid2hctx_seqh
->ccid2s_seq
= seq
;
269 hctx
->ccid2hctx_seqh
->ccid2s_acked
= 0;
270 hctx
->ccid2hctx_seqh
->ccid2s_sent
= jiffies
;
272 next
= hctx
->ccid2hctx_seqh
->ccid2s_next
;
273 /* check if we need to alloc more space */
274 if (next
== hctx
->ccid2hctx_seqt
) {
275 if (ccid2_hc_tx_alloc_seq(hctx
)) {
276 DCCP_CRIT("packet history - out of memory!");
277 /* FIXME: find a more graceful way to bail out */
280 next
= hctx
->ccid2hctx_seqh
->ccid2s_next
;
281 BUG_ON(next
== hctx
->ccid2hctx_seqt
);
283 hctx
->ccid2hctx_seqh
= next
;
285 ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx
->ccid2hctx_cwnd
,
286 hctx
->ccid2hctx_pipe
);
288 hctx
->ccid2hctx_sent
++;
291 * FIXME: The code below is broken and the variables have been removed
292 * from the socket struct. The `ackloss' variable was always set to 0,
293 * and with arsent there are several problems:
294 * (i) it doesn't just count the number of Acks, but all sent packets;
295 * (ii) it is expressed in # of packets, not # of windows, so the
296 * comparison below uses the wrong formula: Appendix A of RFC 4341
297 * comes up with the number K = cwnd / (R^2 - R) of consecutive windows
298 * of data with no lost or marked Ack packets. If arsent were the # of
299 * consecutive Acks received without loss, then Ack Ratio needs to be
300 * decreased by 1 when
301 * arsent >= K * cwnd / R = cwnd^2 / (R^3 - R^2)
302 * where cwnd / R is the number of Acks received per window of data
303 * (cf. RFC 4341, App. A). The problems are that
304 * - arsent counts other packets as well;
305 * - the comparison uses a formula different from RFC 4341;
306 * - computing a cubic/quadratic equation each time is too complicated.
307 * Hence a different algorithm is needed.
310 /* Ack Ratio. Need to maintain a concept of how many windows we sent */
311 hctx
->ccid2hctx_arsent
++;
312 /* We had an ack loss in this window... */
313 if (hctx
->ccid2hctx_ackloss
) {
314 if (hctx
->ccid2hctx_arsent
>= hctx
->ccid2hctx_cwnd
) {
315 hctx
->ccid2hctx_arsent
= 0;
316 hctx
->ccid2hctx_ackloss
= 0;
319 /* No acks lost up to now... */
320 /* decrease ack ratio if enough packets were sent */
321 if (dp
->dccps_l_ack_ratio
> 1) {
322 /* XXX don't calculate denominator each time */
323 int denom
= dp
->dccps_l_ack_ratio
* dp
->dccps_l_ack_ratio
-
324 dp
->dccps_l_ack_ratio
;
326 denom
= hctx
->ccid2hctx_cwnd
* hctx
->ccid2hctx_cwnd
/ denom
;
328 if (hctx
->ccid2hctx_arsent
>= denom
) {
329 ccid2_change_l_ack_ratio(sk
, dp
->dccps_l_ack_ratio
- 1);
330 hctx
->ccid2hctx_arsent
= 0;
333 /* we can't increase ack ratio further [1] */
334 hctx
->ccid2hctx_arsent
= 0; /* or maybe set it to cwnd*/
339 /* setup RTO timer */
340 if (!timer_pending(&hctx
->ccid2hctx_rtotimer
))
341 ccid2_start_rto_timer(sk
);
343 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
344 ccid2_pr_debug("pipe=%d\n", hctx
->ccid2hctx_pipe
);
345 ccid2_pr_debug("Sent: seq=%llu\n", (unsigned long long)seq
);
347 struct ccid2_seq
*seqp
= hctx
->ccid2hctx_seqt
;
349 while (seqp
!= hctx
->ccid2hctx_seqh
) {
350 ccid2_pr_debug("out seq=%llu acked=%d time=%lu\n",
351 (unsigned long long)seqp
->ccid2s_seq
,
352 seqp
->ccid2s_acked
, seqp
->ccid2s_sent
);
353 seqp
= seqp
->ccid2s_next
;
356 ccid2_pr_debug("=========\n");
357 ccid2_hc_tx_check_sanity(hctx
);
361 /* XXX Lame code duplication!
362 * returns -1 if none was found.
363 * else returns the next offset to use in the function call.
365 static int ccid2_ackvector(struct sock
*sk
, struct sk_buff
*skb
, int offset
,
366 unsigned char **vec
, unsigned char *veclen
)
368 const struct dccp_hdr
*dh
= dccp_hdr(skb
);
369 unsigned char *options
= (unsigned char *)dh
+ dccp_hdr_len(skb
);
370 unsigned char *opt_ptr
;
371 const unsigned char *opt_end
= (unsigned char *)dh
+
372 (dh
->dccph_doff
* 4);
373 unsigned char opt
, len
;
374 unsigned char *value
;
379 if (opt_ptr
>= opt_end
)
382 while (opt_ptr
!= opt_end
) {
387 /* Check if this isn't a single byte option */
388 if (opt
> DCCPO_MAX_RESERVED
) {
389 if (opt_ptr
== opt_end
)
390 goto out_invalid_option
;
394 goto out_invalid_option
;
396 * Remove the type and len fields, leaving
397 * just the value size
403 if (opt_ptr
> opt_end
)
404 goto out_invalid_option
;
408 case DCCPO_ACK_VECTOR_0
:
409 case DCCPO_ACK_VECTOR_1
:
412 return offset
+ (opt_ptr
- options
);
419 DCCP_BUG("Invalid option - this should not happen (previous parsing)!");
423 static void ccid2_hc_tx_kill_rto_timer(struct sock
*sk
)
425 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
427 sk_stop_timer(sk
, &hctx
->ccid2hctx_rtotimer
);
428 ccid2_pr_debug("deleted RTO timer\n");
431 static inline void ccid2_new_ack(struct sock
*sk
,
432 struct ccid2_seq
*seqp
,
433 unsigned int *maxincr
)
435 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
438 if (hctx
->ccid2hctx_cwnd
< hctx
->ccid2hctx_ssthresh
) {
439 hctx
->ccid2hctx_acks
= 0;
441 /* We can increase cwnd at most maxincr [ack_ratio/2] */
443 /* increase every 2 acks */
444 hctx
->ccid2hctx_ssacks
++;
445 if (hctx
->ccid2hctx_ssacks
== 2) {
446 ccid2_change_cwnd(hctx
, hctx
->ccid2hctx_cwnd
+1);
447 hctx
->ccid2hctx_ssacks
= 0;
448 *maxincr
= *maxincr
- 1;
451 /* increased cwnd enough for this single ack */
452 hctx
->ccid2hctx_ssacks
= 0;
455 hctx
->ccid2hctx_ssacks
= 0;
456 hctx
->ccid2hctx_acks
++;
458 if (hctx
->ccid2hctx_acks
>= hctx
->ccid2hctx_cwnd
) {
459 ccid2_change_cwnd(hctx
, hctx
->ccid2hctx_cwnd
+ 1);
460 hctx
->ccid2hctx_acks
= 0;
465 if (hctx
->ccid2hctx_srtt
== -1 ||
466 time_after(jiffies
, hctx
->ccid2hctx_lastrtt
+ hctx
->ccid2hctx_srtt
)) {
467 unsigned long r
= (long)jiffies
- (long)seqp
->ccid2s_sent
;
470 /* first measurement */
471 if (hctx
->ccid2hctx_srtt
== -1) {
472 ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n",
474 (unsigned long long)seqp
->ccid2s_seq
);
475 ccid2_change_srtt(hctx
, r
);
476 hctx
->ccid2hctx_rttvar
= r
>> 1;
479 long tmp
= hctx
->ccid2hctx_srtt
- r
;
486 hctx
->ccid2hctx_rttvar
*= 3;
487 hctx
->ccid2hctx_rttvar
>>= 2;
488 hctx
->ccid2hctx_rttvar
+= tmp
;
491 srtt
= hctx
->ccid2hctx_srtt
;
496 ccid2_change_srtt(hctx
, srtt
);
498 s
= hctx
->ccid2hctx_rttvar
<< 2;
499 /* clock granularity is 1 when based on jiffies */
502 hctx
->ccid2hctx_rto
= hctx
->ccid2hctx_srtt
+ s
;
504 /* must be at least a second */
505 s
= hctx
->ccid2hctx_rto
/ HZ
;
506 /* DCCP doesn't require this [but I like it cuz my code sux] */
509 hctx
->ccid2hctx_rto
= HZ
;
513 hctx
->ccid2hctx_rto
= HZ
* 60;
515 hctx
->ccid2hctx_lastrtt
= jiffies
;
517 ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n",
518 hctx
->ccid2hctx_srtt
, hctx
->ccid2hctx_rttvar
,
519 hctx
->ccid2hctx_rto
, HZ
, r
);
520 hctx
->ccid2hctx_sent
= 0;
523 /* we got a new ack, so re-start RTO timer */
524 ccid2_hc_tx_kill_rto_timer(sk
);
525 ccid2_start_rto_timer(sk
);
528 static void ccid2_hc_tx_dec_pipe(struct sock
*sk
)
530 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
532 ccid2_change_pipe(hctx
, hctx
->ccid2hctx_pipe
-1);
533 BUG_ON(hctx
->ccid2hctx_pipe
< 0);
535 if (hctx
->ccid2hctx_pipe
== 0)
536 ccid2_hc_tx_kill_rto_timer(sk
);
539 static void ccid2_congestion_event(struct sock
*sk
, struct ccid2_seq
*seqp
)
541 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
543 if (time_before(seqp
->ccid2s_sent
, hctx
->ccid2hctx_last_cong
)) {
544 ccid2_pr_debug("Multiple losses in an RTT---treating as one\n");
548 hctx
->ccid2hctx_last_cong
= jiffies
;
550 ccid2_change_cwnd(hctx
, hctx
->ccid2hctx_cwnd
>> 1);
551 hctx
->ccid2hctx_ssthresh
= hctx
->ccid2hctx_cwnd
;
552 if (hctx
->ccid2hctx_ssthresh
< 2)
553 hctx
->ccid2hctx_ssthresh
= 2;
555 /* Avoid spurious timeouts resulting from Ack Ratio > cwnd */
556 if (dccp_sk(sk
)->dccps_l_ack_ratio
> hctx
->ccid2hctx_cwnd
)
557 ccid2_change_l_ack_ratio(sk
, hctx
->ccid2hctx_cwnd
);
560 static void ccid2_hc_tx_packet_recv(struct sock
*sk
, struct sk_buff
*skb
)
562 struct dccp_sock
*dp
= dccp_sk(sk
);
563 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
565 struct ccid2_seq
*seqp
;
566 unsigned char *vector
;
567 unsigned char veclen
;
570 unsigned int maxincr
= 0;
572 ccid2_hc_tx_check_sanity(hctx
);
573 /* check reverse path congestion */
574 seqno
= DCCP_SKB_CB(skb
)->dccpd_seq
;
576 /* XXX this whole "algorithm" is broken. Need to fix it to keep track
577 * of the seqnos of the dupacks so that rpseq and rpdupack are correct
580 /* need to bootstrap */
581 if (hctx
->ccid2hctx_rpdupack
== -1) {
582 hctx
->ccid2hctx_rpdupack
= 0;
583 hctx
->ccid2hctx_rpseq
= seqno
;
585 /* check if packet is consecutive */
586 if (dccp_delta_seqno(hctx
->ccid2hctx_rpseq
, seqno
) == 1)
587 hctx
->ccid2hctx_rpseq
= seqno
;
588 /* it's a later packet */
589 else if (after48(seqno
, hctx
->ccid2hctx_rpseq
)) {
590 hctx
->ccid2hctx_rpdupack
++;
592 /* check if we got enough dupacks */
593 if (hctx
->ccid2hctx_rpdupack
>=
594 hctx
->ccid2hctx_numdupack
) {
595 hctx
->ccid2hctx_rpdupack
= -1; /* XXX lame */
596 hctx
->ccid2hctx_rpseq
= 0;
598 ccid2_change_l_ack_ratio(sk
, 2 * dp
->dccps_l_ack_ratio
);
603 /* check forward path congestion */
604 /* still didn't send out new data packets */
605 if (hctx
->ccid2hctx_seqh
== hctx
->ccid2hctx_seqt
)
608 switch (DCCP_SKB_CB(skb
)->dccpd_type
) {
610 case DCCP_PKT_DATAACK
:
616 ackno
= DCCP_SKB_CB(skb
)->dccpd_ack_seq
;
617 if (after48(ackno
, hctx
->ccid2hctx_high_ack
))
618 hctx
->ccid2hctx_high_ack
= ackno
;
620 seqp
= hctx
->ccid2hctx_seqt
;
621 while (before48(seqp
->ccid2s_seq
, ackno
)) {
622 seqp
= seqp
->ccid2s_next
;
623 if (seqp
== hctx
->ccid2hctx_seqh
) {
624 seqp
= hctx
->ccid2hctx_seqh
->ccid2s_prev
;
629 /* If in slow-start, cwnd can increase at most Ack Ratio / 2 packets for
630 * this single ack. I round up.
633 maxincr
= dp
->dccps_l_ack_ratio
>> 1;
636 /* go through all ack vectors */
637 while ((offset
= ccid2_ackvector(sk
, skb
, offset
,
638 &vector
, &veclen
)) != -1) {
639 /* go through this ack vector */
641 const u8 rl
= *vector
& DCCP_ACKVEC_LEN_MASK
;
642 u64 ackno_end_rl
= SUB48(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
651 while (after48(seqp
->ccid2s_seq
, ackno
)) {
652 if (seqp
== hctx
->ccid2hctx_seqt
) {
656 seqp
= seqp
->ccid2s_prev
;
661 /* check all seqnos in the range of the vector
664 while (between48(seqp
->ccid2s_seq
,ackno_end_rl
,ackno
)) {
665 const u8 state
= *vector
&
666 DCCP_ACKVEC_STATE_MASK
;
668 /* new packet received or marked */
669 if (state
!= DCCP_ACKVEC_STATE_NOT_RECEIVED
&&
670 !seqp
->ccid2s_acked
) {
672 DCCP_ACKVEC_STATE_ECN_MARKED
) {
673 ccid2_congestion_event(sk
,
676 ccid2_new_ack(sk
, seqp
,
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
);
684 if (seqp
== hctx
->ccid2hctx_seqt
) {
688 seqp
= seqp
->ccid2s_prev
;
693 ackno
= SUB48(ackno_end_rl
, 1);
700 /* The state about what is acked should be correct now
701 * Check for NUMDUPACK
703 seqp
= hctx
->ccid2hctx_seqt
;
704 while (before48(seqp
->ccid2s_seq
, hctx
->ccid2hctx_high_ack
)) {
705 seqp
= seqp
->ccid2s_next
;
706 if (seqp
== hctx
->ccid2hctx_seqh
) {
707 seqp
= hctx
->ccid2hctx_seqh
->ccid2s_prev
;
713 if (seqp
->ccid2s_acked
) {
715 if (done
== hctx
->ccid2hctx_numdupack
)
718 if (seqp
== hctx
->ccid2hctx_seqt
)
720 seqp
= seqp
->ccid2s_prev
;
723 /* If there are at least 3 acknowledgements, anything unacknowledged
724 * below the last sequence number is considered lost
726 if (done
== hctx
->ccid2hctx_numdupack
) {
727 struct ccid2_seq
*last_acked
= seqp
;
729 /* check for lost packets */
731 if (!seqp
->ccid2s_acked
) {
732 ccid2_pr_debug("Packet lost: %llu\n",
733 (unsigned long long)seqp
->ccid2s_seq
);
734 /* XXX need to traverse from tail -> head in
735 * order to detect multiple congestion events in
738 ccid2_congestion_event(sk
, seqp
);
739 ccid2_hc_tx_dec_pipe(sk
);
741 if (seqp
== hctx
->ccid2hctx_seqt
)
743 seqp
= seqp
->ccid2s_prev
;
746 hctx
->ccid2hctx_seqt
= last_acked
;
749 /* trim acked packets in tail */
750 while (hctx
->ccid2hctx_seqt
!= hctx
->ccid2hctx_seqh
) {
751 if (!hctx
->ccid2hctx_seqt
->ccid2s_acked
)
754 hctx
->ccid2hctx_seqt
= hctx
->ccid2hctx_seqt
->ccid2s_next
;
757 ccid2_hc_tx_check_sanity(hctx
);
760 static int ccid2_hc_tx_init(struct ccid
*ccid
, struct sock
*sk
)
762 struct ccid2_hc_tx_sock
*hctx
= ccid_priv(ccid
);
763 struct dccp_sock
*dp
= dccp_sk(sk
);
766 /* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */
767 hctx
->ccid2hctx_ssthresh
= ~0;
768 hctx
->ccid2hctx_numdupack
= 3;
771 * RFC 4341, 5: "The cwnd parameter is initialized to at most four
772 * packets for new connections, following the rules from [RFC3390]".
773 * We need to convert the bytes of RFC3390 into the packets of RFC 4341.
775 hctx
->ccid2hctx_cwnd
= min(4U, max(2U, 4380U / dp
->dccps_mss_cache
));
777 /* Make sure that Ack Ratio is enabled and within bounds. */
778 max_ratio
= DIV_ROUND_UP(hctx
->ccid2hctx_cwnd
, 2);
779 if (dp
->dccps_l_ack_ratio
== 0 || dp
->dccps_l_ack_ratio
> max_ratio
)
780 dp
->dccps_l_ack_ratio
= max_ratio
;
782 /* XXX init ~ to window size... */
783 if (ccid2_hc_tx_alloc_seq(hctx
))
786 hctx
->ccid2hctx_rto
= 3 * HZ
;
787 ccid2_change_srtt(hctx
, -1);
788 hctx
->ccid2hctx_rttvar
= -1;
789 hctx
->ccid2hctx_rpdupack
= -1;
790 hctx
->ccid2hctx_last_cong
= jiffies
;
791 setup_timer(&hctx
->ccid2hctx_rtotimer
, ccid2_hc_tx_rto_expire
,
794 ccid2_hc_tx_check_sanity(hctx
);
798 static void ccid2_hc_tx_exit(struct sock
*sk
)
800 struct ccid2_hc_tx_sock
*hctx
= ccid2_hc_tx_sk(sk
);
803 ccid2_hc_tx_kill_rto_timer(sk
);
805 for (i
= 0; i
< hctx
->ccid2hctx_seqbufc
; i
++)
806 kfree(hctx
->ccid2hctx_seqbuf
[i
]);
807 hctx
->ccid2hctx_seqbufc
= 0;
810 static void ccid2_hc_rx_packet_recv(struct sock
*sk
, struct sk_buff
*skb
)
812 const struct dccp_sock
*dp
= dccp_sk(sk
);
813 struct ccid2_hc_rx_sock
*hcrx
= ccid2_hc_rx_sk(sk
);
815 switch (DCCP_SKB_CB(skb
)->dccpd_type
) {
817 case DCCP_PKT_DATAACK
:
818 hcrx
->ccid2hcrx_data
++;
819 if (hcrx
->ccid2hcrx_data
>= dp
->dccps_r_ack_ratio
) {
821 hcrx
->ccid2hcrx_data
= 0;
827 static struct ccid_operations ccid2
= {
828 .ccid_id
= DCCPC_CCID2
,
829 .ccid_name
= "ccid2",
830 .ccid_owner
= THIS_MODULE
,
831 .ccid_hc_tx_obj_size
= sizeof(struct ccid2_hc_tx_sock
),
832 .ccid_hc_tx_init
= ccid2_hc_tx_init
,
833 .ccid_hc_tx_exit
= ccid2_hc_tx_exit
,
834 .ccid_hc_tx_send_packet
= ccid2_hc_tx_send_packet
,
835 .ccid_hc_tx_packet_sent
= ccid2_hc_tx_packet_sent
,
836 .ccid_hc_tx_packet_recv
= ccid2_hc_tx_packet_recv
,
837 .ccid_hc_rx_obj_size
= sizeof(struct ccid2_hc_rx_sock
),
838 .ccid_hc_rx_packet_recv
= ccid2_hc_rx_packet_recv
,
841 #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
842 module_param(ccid2_debug
, bool, 0444);
843 MODULE_PARM_DESC(ccid2_debug
, "Enable debug messages");
846 static __init
int ccid2_module_init(void)
848 return ccid_register(&ccid2
);
850 module_init(ccid2_module_init
);
852 static __exit
void ccid2_module_exit(void)
854 ccid_unregister(&ccid2
);
856 module_exit(ccid2_module_exit
);
858 MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>");
859 MODULE_DESCRIPTION("DCCP TCP-Like (CCID2) CCID");
860 MODULE_LICENSE("GPL");
861 MODULE_ALIAS("net-dccp-ccid-2");