blob: e0acd1ba4e88709f4c20240bbd892e1ab5e2b8c8 [file] [log] [blame]
Andrea Bittau2a91aa32006-03-20 17:41:47 -08001/*
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
Andrea Bittau2a91aa32006-03-20 17:41:47 -080030 */
31
Andrea Bittau2a91aa32006-03-20 17:41:47 -080032#include "../ccid.h"
33#include "../dccp.h"
34#include "ccid2.h"
35
36static int ccid2_debug;
37
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -080038#undef CCID2_DEBUG
Andrea Bittau2a91aa32006-03-20 17:41:47 -080039#ifdef CCID2_DEBUG
40#define ccid2_pr_debug(format, a...) \
41 do { if (ccid2_debug) \
42 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
43 } while (0)
44#else
45#define ccid2_pr_debug(format, a...)
46#endif
47
48static const int ccid2_seq_len = 128;
49
Andrea Bittau2a91aa32006-03-20 17:41:47 -080050#ifdef CCID2_DEBUG
51static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx)
52{
53 int len = 0;
Andrea Bittau2a91aa32006-03-20 17:41:47 -080054 int pipe = 0;
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -080055 struct ccid2_seq *seqp = hctx->ccid2hctx_seqh;
Andrea Bittau2a91aa32006-03-20 17:41:47 -080056
57 /* there is data in the chain */
58 if (seqp != hctx->ccid2hctx_seqt) {
59 seqp = seqp->ccid2s_prev;
60 len++;
61 if (!seqp->ccid2s_acked)
62 pipe++;
63
64 while (seqp != hctx->ccid2hctx_seqt) {
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -080065 struct ccid2_seq *prev = seqp->ccid2s_prev;
Andrea Bittau2a91aa32006-03-20 17:41:47 -080066
Andrea Bittau2a91aa32006-03-20 17:41:47 -080067 len++;
68 if (!prev->ccid2s_acked)
69 pipe++;
70
71 /* packets are sent sequentially */
72 BUG_ON(seqp->ccid2s_seq <= prev->ccid2s_seq);
Andrea Bittau29651cd2006-09-19 13:06:46 -070073 BUG_ON(time_before(seqp->ccid2s_sent,
74 prev->ccid2s_sent));
Andrea Bittau2a91aa32006-03-20 17:41:47 -080075 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);
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -080088 } while (seqp != hctx->ccid2hctx_seqh);
Andrea Bittau2a91aa32006-03-20 17:41:47 -080089
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
97static 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
Andrea Bittau446dec32006-09-19 13:10:11 -0700125 return 1; /* XXX CCID should dequeue when ready instead of polling */
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800126}
127
128static 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) {
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800137 const struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800138 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
153static 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
167static void ccid2_start_rto_timer(struct sock *sk);
168
169static 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
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800175 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);
215out:
216 bh_unlock_sock(sk);
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800217 sock_put(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800218}
219
220static 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
231static 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) {
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800271 hctx->ccid2hctx_arsent = 0;
272 hctx->ccid2hctx_ackloss = 0;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800273 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800274 } else {
275 /* No acks lost up to now... */
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800276 /* decrease ack ratio if enough packets were sent */
277 if (dp->dccps_l_ack_ratio > 1) {
278 /* XXX don't calculate denominator each time */
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800279 int denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio -
280 dp->dccps_l_ack_ratio;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800281
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800282 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 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800288 } else {
289 /* we can't increase ack ratio further [1] */
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800290 hctx->ccid2hctx_arsent = 0; /* or maybe set it to cwnd*/
291 }
292 }
293
294 /* setup RTO timer */
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800295 if (!timer_pending(&hctx->ccid2hctx_rtotimer))
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800296 ccid2_start_rto_timer(sk);
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800297
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800298#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 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800310 } while (0);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800311 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 */
320static 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);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800368 }
369 }
370
371 return -1;
372
373out_invalid_option:
374 BUG_ON(1); /* should never happen... options were previously parsed ! */
375 return -1;
376}
377
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800378static void ccid2_hc_tx_kill_rto_timer(struct sock *sk)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800379{
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800380 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");
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800384}
385
386static 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 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800405 } else {
406 /* increased cwnd enough for this single ack */
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800407 hctx->ccid2hctx_ssacks = 0;
408 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800409 } else {
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800410 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 ||
Andrea Bittau29651cd2006-09-19 13:06:46 -0700421 time_after(jiffies, hctx->ccid2hctx_lastrtt + hctx->ccid2hctx_srtt)) {
422 unsigned long r = (long)jiffies - (long)seqp->ccid2s_sent;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800423 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;
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800431 } else {
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800432 /* 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 */
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800474 ccid2_hc_tx_kill_rto_timer(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800475 ccid2_start_rto_timer(sk);
476}
477
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800478static void ccid2_hc_tx_dec_pipe(struct sock *sk)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800479{
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800480 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
481
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800482 hctx->ccid2hctx_pipe--;
483 BUG_ON(hctx->ccid2hctx_pipe < 0);
484
485 if (hctx->ccid2hctx_pipe == 0)
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800486 ccid2_hc_tx_kill_rto_timer(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800487}
488
489static 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;
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800514 } else {
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800515 /* check if packet is consecutive */
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800516 if ((hctx->ccid2hctx_rpseq + 1) == seqno)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800517 hctx->ccid2hctx_rpseq++;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800518 /* 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) {
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800525 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;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800542 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)) {
Andrea Bittau8e27e462006-09-19 13:05:35 -0700585 const u8 state = *vector &
586 DCCP_ACKVEC_STATE_MASK;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800587
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;
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800594 } else
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800595 ccid2_new_ack(sk, seqp,
596 &maxincr);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800597
598 seqp->ccid2s_acked = 1;
599 ccid2_pr_debug("Got ack for %llu\n",
600 seqp->ccid2s_seq);
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800601 ccid2_hc_tx_dec_pipe(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800602 }
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++;
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800628 if (done == hctx->ccid2hctx_numdupack)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800629 break;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800630 }
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800631 if (seqp == hctx->ccid2hctx_seqt)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800632 break;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800633 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;
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800646 ccid2_hc_tx_dec_pipe(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800647 }
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
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800675static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800676{
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800677 struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800678 int seqcount = ccid2_seq_len;
679 int i;
680
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800681 hctx->ccid2hctx_cwnd = 1;
Andrea Bittaud458c252006-09-19 13:07:20 -0700682 /* Initialize ssthresh to infinity. This means that we will exit the
683 * initial slow-start after the first packet loss. This is what we
684 * want.
685 */
686 hctx->ccid2hctx_ssthresh = ~0;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800687 hctx->ccid2hctx_numdupack = 3;
688
689 /* XXX init ~ to window size... */
690 hctx->ccid2hctx_seqbuf = kmalloc(sizeof(*hctx->ccid2hctx_seqbuf) *
691 seqcount, gfp_any());
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800692 if (hctx->ccid2hctx_seqbuf == NULL)
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800693 return -ENOMEM;
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800694
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800695 for (i = 0; i < (seqcount - 1); i++) {
696 hctx->ccid2hctx_seqbuf[i].ccid2s_next =
697 &hctx->ccid2hctx_seqbuf[i + 1];
698 hctx->ccid2hctx_seqbuf[i + 1].ccid2s_prev =
699 &hctx->ccid2hctx_seqbuf[i];
700 }
701 hctx->ccid2hctx_seqbuf[seqcount - 1].ccid2s_next =
702 hctx->ccid2hctx_seqbuf;
703 hctx->ccid2hctx_seqbuf->ccid2s_prev =
704 &hctx->ccid2hctx_seqbuf[seqcount - 1];
705
706 hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqbuf;
707 hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh;
708 hctx->ccid2hctx_sent = 0;
709 hctx->ccid2hctx_rto = 3 * HZ;
710 hctx->ccid2hctx_srtt = -1;
711 hctx->ccid2hctx_rttvar = -1;
712 hctx->ccid2hctx_lastrtt = 0;
713 hctx->ccid2hctx_rpdupack = -1;
714
715 hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire;
716 hctx->ccid2hctx_rtotimer.data = (unsigned long)sk;
717 init_timer(&hctx->ccid2hctx_rtotimer);
718
719 ccid2_hc_tx_check_sanity(hctx);
720 return 0;
721}
722
723static void ccid2_hc_tx_exit(struct sock *sk)
724{
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800725 struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800726
Andrea Bittau77ff72d2006-03-20 17:57:52 -0800727 ccid2_hc_tx_kill_rto_timer(sk);
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800728 kfree(hctx->ccid2hctx_seqbuf);
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800729 hctx->ccid2hctx_seqbuf = NULL;
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800730}
731
732static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
733{
734 const struct dccp_sock *dp = dccp_sk(sk);
735 struct ccid2_hc_rx_sock *hcrx = ccid2_hc_rx_sk(sk);
736
737 switch (DCCP_SKB_CB(skb)->dccpd_type) {
738 case DCCP_PKT_DATA:
739 case DCCP_PKT_DATAACK:
740 hcrx->ccid2hcrx_data++;
741 if (hcrx->ccid2hcrx_data >= dp->dccps_r_ack_ratio) {
742 dccp_send_ack(sk);
743 hcrx->ccid2hcrx_data = 0;
744 }
745 break;
746 }
747}
748
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800749static struct ccid_operations ccid2 = {
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800750 .ccid_id = 2,
751 .ccid_name = "ccid2",
752 .ccid_owner = THIS_MODULE,
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800753 .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock),
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800754 .ccid_hc_tx_init = ccid2_hc_tx_init,
755 .ccid_hc_tx_exit = ccid2_hc_tx_exit,
756 .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet,
757 .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent,
758 .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv,
Arnaldo Carvalho de Melo91f0ebf2006-03-20 19:21:44 -0800759 .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock),
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800760 .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv,
761};
762
763module_param(ccid2_debug, int, 0444);
764MODULE_PARM_DESC(ccid2_debug, "Enable debug messages");
765
766static __init int ccid2_module_init(void)
767{
768 return ccid_register(&ccid2);
769}
770module_init(ccid2_module_init);
771
772static __exit void ccid2_module_exit(void)
773{
774 ccid_unregister(&ccid2);
775}
776module_exit(ccid2_module_exit);
777
778MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>");
Arnaldo Carvalho de Meloc0c736d2006-03-20 22:05:37 -0800779MODULE_DESCRIPTION("DCCP TCP-Like (CCID2) CCID");
Andrea Bittau2a91aa32006-03-20 17:41:47 -0800780MODULE_LICENSE("GPL");
781MODULE_ALIAS("net-dccp-ccid-2");