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