aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2010-11-10 15:20:07 -0500
committerGerrit Renker <gerrit@erg.abdn.ac.uk>2010-11-10 15:20:07 -0500
commitf17a37c9b8c4b32c01e501a84fa6f30e344c6110 (patch)
tree7ff8e9a232aaddcd33c302c5c6a577af26634212 /net
parent973a34aa8593dbfe84386343c694f5beecb51d8a (diff)
dccp ccid-2: Ack Vector interface clean-up
This patch brings the Ack Vector interface up to date. Its main purpose is to lay the basis for the subsequent patches of this set, which will use the new data structure fields and routines. There are no real algorithmic changes, rather an adaptation: (1) Replaced the static Ack Vector size (2) with a #define so that it can be adapted (with low loss / Ack Ratio, a value of 1 works, so 2 seems to be sufficient for the moment) and added a solution so that computing the ECN nonce will continue to work - even with larger Ack Vectors. (2) Replaced the #defines for Ack Vector states with a complete enum. (3) Replaced #defines to compute Ack Vector length and state with general purpose routines (inlines), and updated code to use these. (4) Added a `tail' field (conversion to circular buffer in subsequent patch). (5) Updated the (outdated) documentation for Ack Vector struct. (6) All sequence number containers now trimmed to 48 bits. (7) Removal of unused bits: * removed dccpav_ack_nonce from struct dccp_ackvec, since this is already redundantly stored in the `dccpavr_ack_nonce' (of Ack Vector record); * removed Elapsed Time for Ack Vectors (it was nowhere used); * replaced semantics of dccpavr_sent_len with dccpavr_ack_runlen, since the code needs to be able to remember the old run length; * reduced the de-/allocation routines (redundant / duplicate tests). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ackvec.c178
-rw-r--r--net/dccp/ackvec.h103
-rw-r--r--net/dccp/ccids/ccid2.c13
-rw-r--r--net/dccp/input.c6
-rw-r--r--net/dccp/options.c1
5 files changed, 128 insertions, 173 deletions
diff --git a/net/dccp/ackvec.c b/net/dccp/ackvec.c
index 92a6fcb40d7d..17bf10f96057 100644
--- a/net/dccp/ackvec.c
+++ b/net/dccp/ackvec.c
@@ -1,7 +1,8 @@
1/* 1/*
2 * net/dccp/ackvec.c 2 * net/dccp/ackvec.c
3 * 3 *
4 * An implementation of the DCCP protocol 4 * An implementation of Ack Vectors for the DCCP protocol
5 * Copyright (c) 2007 University of Aberdeen, Scotland, UK
5 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net> 6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
6 * 7 *
7 * This program is free software; you can redistribute it and/or modify it 8 * This program is free software; you can redistribute it and/or modify it
@@ -23,24 +24,32 @@
23static struct kmem_cache *dccp_ackvec_slab; 24static struct kmem_cache *dccp_ackvec_slab;
24static struct kmem_cache *dccp_ackvec_record_slab; 25static struct kmem_cache *dccp_ackvec_record_slab;
25 26
26static struct dccp_ackvec_record *dccp_ackvec_record_new(void) 27struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
27{ 28{
28 struct dccp_ackvec_record *avr = 29 struct dccp_ackvec *av = kmem_cache_zalloc(dccp_ackvec_slab, priority);
29 kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); 30
31 if (av != NULL) {
32 av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1;
33 INIT_LIST_HEAD(&av->av_records);
34 }
35 return av;
36}
30 37
31 if (avr != NULL) 38static void dccp_ackvec_purge_records(struct dccp_ackvec *av)
32 INIT_LIST_HEAD(&avr->avr_node); 39{
40 struct dccp_ackvec_record *cur, *next;
33 41
34 return avr; 42 list_for_each_entry_safe(cur, next, &av->av_records, avr_node)
43 kmem_cache_free(dccp_ackvec_record_slab, cur);
44 INIT_LIST_HEAD(&av->av_records);
35} 45}
36 46
37static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr) 47void dccp_ackvec_free(struct dccp_ackvec *av)
38{ 48{
39 if (unlikely(avr == NULL)) 49 if (likely(av != NULL)) {
40 return; 50 dccp_ackvec_purge_records(av);
41 /* Check if deleting a linked record */ 51 kmem_cache_free(dccp_ackvec_slab, av);
42 WARN_ON(!list_empty(&avr->avr_node)); 52 }
43 kmem_cache_free(dccp_ackvec_record_slab, avr);
44} 53}
45 54
46static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, 55static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
@@ -68,24 +77,16 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
68 struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; 77 struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
69 /* Figure out how many options do we need to represent the ackvec */ 78 /* Figure out how many options do we need to represent the ackvec */
70 const u8 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); 79 const u8 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN);
71 u16 len = av->av_vec_len + 2 * nr_opts, i; 80 u16 len = av->av_vec_len + 2 * nr_opts;
72 u32 elapsed_time; 81 u8 i, nonce = 0;
73 const unsigned char *tail, *from; 82 const unsigned char *tail, *from;
74 unsigned char *to; 83 unsigned char *to;
75 struct dccp_ackvec_record *avr; 84 struct dccp_ackvec_record *avr;
76 suseconds_t delta;
77 85
78 if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) 86 if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
79 return -1; 87 return -1;
80 88
81 delta = ktime_us_delta(ktime_get_real(), av->av_time); 89 avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
82 elapsed_time = delta / 10;
83
84 if (elapsed_time != 0 &&
85 dccp_insert_option_elapsed_time(skb, elapsed_time))
86 return -1;
87
88 avr = dccp_ackvec_record_new();
89 if (avr == NULL) 90 if (avr == NULL)
90 return -1; 91 return -1;
91 92
@@ -94,7 +95,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
94 to = skb_push(skb, len); 95 to = skb_push(skb, len);
95 len = av->av_vec_len; 96 len = av->av_vec_len;
96 from = av->av_buf + av->av_buf_head; 97 from = av->av_buf + av->av_buf_head;
97 tail = av->av_buf + DCCP_MAX_ACKVEC_LEN; 98 tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
98 99
99 for (i = 0; i < nr_opts; ++i) { 100 for (i = 0; i < nr_opts; ++i) {
100 int copylen = len; 101 int copylen = len;
@@ -102,7 +103,13 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
102 if (len > DCCP_SINGLE_OPT_MAXLEN) 103 if (len > DCCP_SINGLE_OPT_MAXLEN)
103 copylen = DCCP_SINGLE_OPT_MAXLEN; 104 copylen = DCCP_SINGLE_OPT_MAXLEN;
104 105
105 *to++ = DCCPO_ACK_VECTOR_0; 106 /*
107 * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via
108 * its type; ack_nonce is the sum of all individual buf_nonce's.
109 */
110 nonce ^= av->av_buf_nonce[i];
111
112 *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i];
106 *to++ = copylen + 2; 113 *to++ = copylen + 2;
107 114
108 /* Check if buf_head wraps */ 115 /* Check if buf_head wraps */
@@ -123,75 +130,24 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
123 } 130 }
124 131
125 /* 132 /*
126 * From RFC 4340, A.2: 133 * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340.
127 *
128 * For each acknowledgement it sends, the HC-Receiver will add an
129 * acknowledgement record. ack_seqno will equal the HC-Receiver
130 * sequence number it used for the ack packet; ack_ptr will equal
131 * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
132 * equal buf_nonce.
133 */ 134 */
134 avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; 135 avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
135 avr->avr_ack_ptr = av->av_buf_head; 136 avr->avr_ack_ptr = av->av_buf_head;
136 avr->avr_ack_ackno = av->av_buf_ackno; 137 avr->avr_ack_ackno = av->av_buf_ackno;
137 avr->avr_ack_nonce = av->av_buf_nonce; 138 avr->avr_ack_nonce = nonce;
138 avr->avr_sent_len = av->av_vec_len; 139 avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head);
139 140
140 dccp_ackvec_insert_avr(av, avr); 141 dccp_ackvec_insert_avr(av, avr);
141 142
142 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " 143 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
143 "ack_ackno=%llu\n", 144 "ack_ackno=%llu\n",
144 dccp_role(sk), avr->avr_sent_len, 145 dccp_role(sk), avr->avr_ack_runlen,
145 (unsigned long long)avr->avr_ack_seqno, 146 (unsigned long long)avr->avr_ack_seqno,
146 (unsigned long long)avr->avr_ack_ackno); 147 (unsigned long long)avr->avr_ack_ackno);
147 return 0; 148 return 0;
148} 149}
149 150
150struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
151{
152 struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority);
153
154 if (av != NULL) {
155 av->av_buf_head = DCCP_MAX_ACKVEC_LEN - 1;
156 av->av_buf_ackno = UINT48_MAX + 1;
157 av->av_buf_nonce = 0;
158 av->av_time = ktime_set(0, 0);
159 av->av_vec_len = 0;
160 INIT_LIST_HEAD(&av->av_records);
161 }
162
163 return av;
164}
165
166void dccp_ackvec_free(struct dccp_ackvec *av)
167{
168 if (unlikely(av == NULL))
169 return;
170
171 if (!list_empty(&av->av_records)) {
172 struct dccp_ackvec_record *avr, *next;
173
174 list_for_each_entry_safe(avr, next, &av->av_records, avr_node) {
175 list_del_init(&avr->avr_node);
176 dccp_ackvec_record_delete(avr);
177 }
178 }
179
180 kmem_cache_free(dccp_ackvec_slab, av);
181}
182
183static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
184 const u32 index)
185{
186 return av->av_buf[index] & DCCP_ACKVEC_STATE_MASK;
187}
188
189static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
190 const u32 index)
191{
192 return av->av_buf[index] & DCCP_ACKVEC_LEN_MASK;
193}
194
195/* 151/*
196 * If several packets are missing, the HC-Receiver may prefer to enter multiple 152 * If several packets are missing, the HC-Receiver may prefer to enter multiple
197 * bytes with run length 0, rather than a single byte with a larger run length; 153 * bytes with run length 0, rather than a single byte with a larger run length;
@@ -204,7 +160,7 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
204 long gap; 160 long gap;
205 long new_head; 161 long new_head;
206 162
207 if (av->av_vec_len + packets > DCCP_MAX_ACKVEC_LEN) 163 if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN)
208 return -ENOBUFS; 164 return -ENOBUFS;
209 165
210 gap = packets - 1; 166 gap = packets - 1;
@@ -212,18 +168,18 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
212 168
213 if (new_head < 0) { 169 if (new_head < 0) {
214 if (gap > 0) { 170 if (gap > 0) {
215 memset(av->av_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED, 171 memset(av->av_buf, DCCPAV_NOT_RECEIVED,
216 gap + new_head + 1); 172 gap + new_head + 1);
217 gap = -new_head; 173 gap = -new_head;
218 } 174 }
219 new_head += DCCP_MAX_ACKVEC_LEN; 175 new_head += DCCPAV_MAX_ACKVEC_LEN;
220 } 176 }
221 177
222 av->av_buf_head = new_head; 178 av->av_buf_head = new_head;
223 179
224 if (gap > 0) 180 if (gap > 0)
225 memset(av->av_buf + av->av_buf_head + 1, 181 memset(av->av_buf + av->av_buf_head + 1,
226 DCCP_ACKVEC_STATE_NOT_RECEIVED, gap); 182 DCCPAV_NOT_RECEIVED, gap);
227 183
228 av->av_buf[av->av_buf_head] = state; 184 av->av_buf[av->av_buf_head] = state;
229 av->av_vec_len += packets; 185 av->av_vec_len += packets;
@@ -236,6 +192,8 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
236int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, 192int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
237 const u64 ackno, const u8 state) 193 const u64 ackno, const u8 state)
238{ 194{
195 u8 *cur_head = av->av_buf + av->av_buf_head,
196 *buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
239 /* 197 /*
240 * Check at the right places if the buffer is full, if it is, tell the 198 * Check at the right places if the buffer is full, if it is, tell the
241 * caller to start dropping packets till the HC-Sender acks our ACK 199 * caller to start dropping packets till the HC-Sender acks our ACK
@@ -260,7 +218,7 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
260 218
261 /* See if this is the first ackno being inserted */ 219 /* See if this is the first ackno being inserted */
262 if (av->av_vec_len == 0) { 220 if (av->av_vec_len == 0) {
263 av->av_buf[av->av_buf_head] = state; 221 *cur_head = state;
264 av->av_vec_len = 1; 222 av->av_vec_len = 1;
265 } else if (after48(ackno, av->av_buf_ackno)) { 223 } else if (after48(ackno, av->av_buf_ackno)) {
266 const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); 224 const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno);
@@ -269,10 +227,9 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
269 * Look if the state of this packet is the same as the 227 * Look if the state of this packet is the same as the
270 * previous ackno and if so if we can bump the head len. 228 * previous ackno and if so if we can bump the head len.
271 */ 229 */
272 if (delta == 1 && 230 if (delta == 1 && dccp_ackvec_state(cur_head) == state &&
273 dccp_ackvec_state(av, av->av_buf_head) == state && 231 dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN)
274 dccp_ackvec_len(av, av->av_buf_head) < DCCP_ACKVEC_LEN_MASK) 232 *cur_head += 1;
275 av->av_buf[av->av_buf_head]++;
276 else if (dccp_ackvec_set_buf_head_state(av, delta, state)) 233 else if (dccp_ackvec_set_buf_head_state(av, delta, state))
277 return -ENOBUFS; 234 return -ENOBUFS;
278 } else { 235 } else {
@@ -285,21 +242,17 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
285 * could reduce the complexity of this scan.) 242 * could reduce the complexity of this scan.)
286 */ 243 */
287 u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); 244 u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno);
288 u32 index = av->av_buf_head;
289 245
290 while (1) { 246 while (1) {
291 const u8 len = dccp_ackvec_len(av, index); 247 const u8 len = dccp_ackvec_runlen(cur_head);
292 const u8 av_state = dccp_ackvec_state(av, index);
293 /* 248 /*
294 * valid packets not yet in av_buf have a reserved 249 * valid packets not yet in av_buf have a reserved
295 * entry, with a len equal to 0. 250 * entry, with a len equal to 0.
296 */ 251 */
297 if (av_state == DCCP_ACKVEC_STATE_NOT_RECEIVED && 252 if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) {
298 len == 0 && delta == 0) { /* Found our
299 reserved seat! */
300 dccp_pr_debug("Found %llu reserved seat!\n", 253 dccp_pr_debug("Found %llu reserved seat!\n",
301 (unsigned long long)ackno); 254 (unsigned long long)ackno);
302 av->av_buf[index] = state; 255 *cur_head = state;
303 goto out; 256 goto out;
304 } 257 }
305 /* len == 0 means one packet */ 258 /* len == 0 means one packet */
@@ -307,13 +260,12 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
307 goto out_duplicate; 260 goto out_duplicate;
308 261
309 delta -= len + 1; 262 delta -= len + 1;
310 if (++index == DCCP_MAX_ACKVEC_LEN) 263 if (++cur_head == buf_end)
311 index = 0; 264 cur_head = av->av_buf;
312 } 265 }
313 } 266 }
314 267
315 av->av_buf_ackno = ackno; 268 av->av_buf_ackno = ackno;
316 av->av_time = ktime_get_real();
317out: 269out:
318 return 0; 270 return 0;
319 271
@@ -333,13 +285,13 @@ static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
333 if (av->av_buf_head <= avr->avr_ack_ptr) 285 if (av->av_buf_head <= avr->avr_ack_ptr)
334 av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; 286 av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head;
335 else 287 else
336 av->av_vec_len = DCCP_MAX_ACKVEC_LEN - 1 - 288 av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 -
337 av->av_buf_head + avr->avr_ack_ptr; 289 av->av_buf_head + avr->avr_ack_ptr;
338 290
339 /* free records */ 291 /* free records */
340 list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { 292 list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {
341 list_del_init(&avr->avr_node); 293 list_del(&avr->avr_node);
342 dccp_ackvec_record_delete(avr); 294 kmem_cache_free(dccp_ackvec_record_slab, avr);
343 } 295 }
344} 296}
345 297
@@ -357,7 +309,7 @@ void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
357 if (ackno == avr->avr_ack_seqno) { 309 if (ackno == avr->avr_ack_seqno) {
358 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " 310 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
359 "ack_ackno=%llu, ACKED!\n", 311 "ack_ackno=%llu, ACKED!\n",
360 dccp_role(sk), 1, 312 dccp_role(sk), avr->avr_ack_runlen,
361 (unsigned long long)avr->avr_ack_seqno, 313 (unsigned long long)avr->avr_ack_seqno,
362 (unsigned long long)avr->avr_ack_ackno); 314 (unsigned long long)avr->avr_ack_ackno);
363 dccp_ackvec_throw_record(av, avr); 315 dccp_ackvec_throw_record(av, avr);
@@ -387,7 +339,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
387 */ 339 */
388 avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); 340 avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node);
389 while (i--) { 341 while (i--) {
390 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; 342 const u8 rl = dccp_ackvec_runlen(vector);
391 u64 ackno_end_rl; 343 u64 ackno_end_rl;
392 344
393 dccp_set_seqno(&ackno_end_rl, *ackno - rl); 345 dccp_set_seqno(&ackno_end_rl, *ackno - rl);
@@ -404,8 +356,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
404 break; 356 break;
405found: 357found:
406 if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { 358 if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) {
407 const u8 state = *vector & DCCP_ACKVEC_STATE_MASK; 359 if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) {
408 if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) {
409 dccp_pr_debug("%s ACK vector 0, len=%d, " 360 dccp_pr_debug("%s ACK vector 0, len=%d, "
410 "ack_seqno=%llu, ack_ackno=%llu, " 361 "ack_seqno=%llu, ack_ackno=%llu, "
411 "ACKED!\n", 362 "ACKED!\n",
@@ -448,10 +399,9 @@ int __init dccp_ackvec_init(void)
448 if (dccp_ackvec_slab == NULL) 399 if (dccp_ackvec_slab == NULL)
449 goto out_err; 400 goto out_err;
450 401
451 dccp_ackvec_record_slab = 402 dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record",
452 kmem_cache_create("dccp_ackvec_record", 403 sizeof(struct dccp_ackvec_record),
453 sizeof(struct dccp_ackvec_record), 404 0, SLAB_HWCACHE_ALIGN, NULL);
454 0, SLAB_HWCACHE_ALIGN, NULL);
455 if (dccp_ackvec_record_slab == NULL) 405 if (dccp_ackvec_record_slab == NULL)
456 goto out_destroy_slab; 406 goto out_destroy_slab;
457 407
diff --git a/net/dccp/ackvec.h b/net/dccp/ackvec.h
index 7ea557b7c6b1..ebcbbc726cff 100644
--- a/net/dccp/ackvec.h
+++ b/net/dccp/ackvec.h
@@ -3,9 +3,9 @@
3/* 3/*
4 * net/dccp/ackvec.h 4 * net/dccp/ackvec.h
5 * 5 *
6 * An implementation of the DCCP protocol 6 * An implementation of Ack Vectors for the DCCP protocol
7 * Copyright (c) 2007 University of Aberdeen, Scotland, UK
7 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@mandriva.com> 8 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@mandriva.com>
8 *
9 * This program is free software; you can redistribute it and/or modify it 9 * This program is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License version 2 as 10 * under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation. 11 * published by the Free Software Foundation.
@@ -13,75 +13,84 @@
13 13
14#include <linux/dccp.h> 14#include <linux/dccp.h>
15#include <linux/compiler.h> 15#include <linux/compiler.h>
16#include <linux/ktime.h>
17#include <linux/list.h> 16#include <linux/list.h>
18#include <linux/types.h> 17#include <linux/types.h>
19 18
20/* We can spread an ack vector across multiple options */ 19/*
21#define DCCP_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * 2) 20 * Ack Vector buffer space is static, in multiples of %DCCP_SINGLE_OPT_MAXLEN,
21 * the maximum size of a single Ack Vector. Setting %DCCPAV_NUM_ACKVECS to 1
22 * will be sufficient for most cases of low Ack Ratios, using a value of 2 gives
23 * more headroom if Ack Ratio is higher or when the sender acknowledges slowly.
24 */
25#define DCCPAV_NUM_ACKVECS 2
26#define DCCPAV_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * DCCPAV_NUM_ACKVECS)
22 27
23/* Estimated minimum average Ack Vector length - used for updating MPS */ 28/* Estimated minimum average Ack Vector length - used for updating MPS */
24#define DCCPAV_MIN_OPTLEN 16 29#define DCCPAV_MIN_OPTLEN 16
25 30
26#define DCCP_ACKVEC_STATE_RECEIVED 0 31enum dccp_ackvec_states {
27#define DCCP_ACKVEC_STATE_ECN_MARKED (1 << 6) 32 DCCPAV_RECEIVED = 0x00,
28#define DCCP_ACKVEC_STATE_NOT_RECEIVED (3 << 6) 33 DCCPAV_ECN_MARKED = 0x40,
34 DCCPAV_RESERVED = 0x80,
35 DCCPAV_NOT_RECEIVED = 0xC0
36};
37#define DCCPAV_MAX_RUNLEN 0x3F
29 38
30#define DCCP_ACKVEC_STATE_MASK 0xC0 /* 11000000 */ 39static inline u8 dccp_ackvec_runlen(const u8 *cell)
31#define DCCP_ACKVEC_LEN_MASK 0x3F /* 00111111 */ 40{
41 return *cell & DCCPAV_MAX_RUNLEN;
42}
32 43
33/** struct dccp_ackvec - ack vector 44static inline u8 dccp_ackvec_state(const u8 *cell)
34 * 45{
35 * This data structure is the one defined in RFC 4340, Appendix A. 46 return *cell & ~DCCPAV_MAX_RUNLEN;
36 * 47}
37 * @av_buf_head - circular buffer head 48
38 * @av_buf_tail - circular buffer tail 49/** struct dccp_ackvec - Ack Vector main data structure
39 * @av_buf_ackno - ack # of the most recent packet acknowledgeable in the
40 * buffer (i.e. %av_buf_head)
41 * @av_buf_nonce - the one-bit sum of the ECN Nonces on all packets acked
42 * by the buffer with State 0
43 *
44 * Additionally, the HC-Receiver must keep some information about the
45 * Ack Vectors it has recently sent. For each packet sent carrying an
46 * Ack Vector, it remembers four variables:
47 * 50 *
48 * @av_records - list of dccp_ackvec_record 51 * This implements a fixed-size circular buffer within an array and is largely
49 * @av_ack_nonce - the one-bit sum of the ECN Nonces for all State 0. 52 * based on Appendix A of RFC 4340.
50 * 53 *
51 * @av_time - the time in usecs 54 * @av_buf: circular buffer storage area
52 * @av_buf - circular buffer of acknowledgeable packets 55 * @av_buf_head: head index; begin of live portion in @av_buf
56 * @av_buf_tail: tail index; first index _after_ the live portion in @av_buf
57 * @av_buf_ackno: highest seqno of acknowledgeable packet recorded in @av_buf
58 * @av_buf_nonce: ECN nonce sums, each covering subsequent segments of up to
59 * %DCCP_SINGLE_OPT_MAXLEN cells in the live portion of @av_buf
60 * @av_records: list of %dccp_ackvec_record (Ack Vectors sent previously)
61 * @av_veclen: length of the live portion of @av_buf
53 */ 62 */
54struct dccp_ackvec { 63struct dccp_ackvec {
55 u64 av_buf_ackno; 64 u8 av_buf[DCCPAV_MAX_ACKVEC_LEN];
56 struct list_head av_records;
57 ktime_t av_time;
58 u16 av_buf_head; 65 u16 av_buf_head;
66 u16 av_buf_tail;
67 u64 av_buf_ackno:48;
68 bool av_buf_nonce[DCCPAV_NUM_ACKVECS];
69 struct list_head av_records;
59 u16 av_vec_len; 70 u16 av_vec_len;
60 u8 av_buf_nonce;
61 u8 av_ack_nonce;
62 u8 av_buf[DCCP_MAX_ACKVEC_LEN];
63}; 71};
64 72
65/** struct dccp_ackvec_record - ack vector record 73/** struct dccp_ackvec_record - Records information about sent Ack Vectors
66 * 74 *
67 * ACK vector record as defined in Appendix A of spec. 75 * These list entries define the additional information which the HC-Receiver
76 * keeps about recently-sent Ack Vectors; again refer to RFC 4340, Appendix A.
68 * 77 *
69 * The list is sorted by avr_ack_seqno 78 * @avr_node: the list node in @av_records
79 * @avr_ack_seqno: sequence number of the packet the Ack Vector was sent on
80 * @avr_ack_ackno: the Ack number that this record/Ack Vector refers to
81 * @avr_ack_ptr: pointer into @av_buf where this record starts
82 * @avr_ack_runlen: run length of @avr_ack_ptr at the time of sending
83 * @avr_ack_nonce: the sum of @av_buf_nonce's at the time this record was sent
70 * 84 *
71 * @avr_node - node in av_records 85 * The list as a whole is sorted in descending order by @avr_ack_seqno.
72 * @avr_ack_seqno - sequence number of the packet this record was sent on
73 * @avr_ack_ackno - sequence number being acknowledged
74 * @avr_ack_ptr - pointer into av_buf where this record starts
75 * @avr_ack_nonce - av_ack_nonce at the time this record was sent
76 * @avr_sent_len - lenght of the record in av_buf
77 */ 86 */
78struct dccp_ackvec_record { 87struct dccp_ackvec_record {
79 struct list_head avr_node; 88 struct list_head avr_node;
80 u64 avr_ack_seqno; 89 u64 avr_ack_seqno:48;
81 u64 avr_ack_ackno; 90 u64 avr_ack_ackno:48;
82 u16 avr_ack_ptr; 91 u16 avr_ack_ptr;
83 u16 avr_sent_len; 92 u8 avr_ack_runlen;
84 u8 avr_ack_nonce; 93 u8 avr_ack_nonce:1;
85}; 94};
86 95
87struct sock; 96struct sock;
diff --git a/net/dccp/ccids/ccid2.c b/net/dccp/ccids/ccid2.c
index 6576eae9e779..cb1b4a0d1877 100644
--- a/net/dccp/ccids/ccid2.c
+++ b/net/dccp/ccids/ccid2.c
@@ -513,8 +513,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
513 &vector, &veclen)) != -1) { 513 &vector, &veclen)) != -1) {
514 /* go through this ack vector */ 514 /* go through this ack vector */
515 while (veclen--) { 515 while (veclen--) {
516 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; 516 u64 ackno_end_rl = SUB48(ackno, dccp_ackvec_runlen(vector));
517 u64 ackno_end_rl = SUB48(ackno, rl);
518 517
519 ccid2_pr_debug("ackvec start:%llu end:%llu\n", 518 ccid2_pr_debug("ackvec start:%llu end:%llu\n",
520 (unsigned long long)ackno, 519 (unsigned long long)ackno,
@@ -537,17 +536,15 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
537 * run length 536 * run length
538 */ 537 */
539 while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) { 538 while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) {
540 const u8 state = *vector & 539 const u8 state = dccp_ackvec_state(vector);
541 DCCP_ACKVEC_STATE_MASK;
542 540
543 /* new packet received or marked */ 541 /* new packet received or marked */
544 if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED && 542 if (state != DCCPAV_NOT_RECEIVED &&
545 !seqp->ccid2s_acked) { 543 !seqp->ccid2s_acked) {
546 if (state == 544 if (state == DCCPAV_ECN_MARKED)
547 DCCP_ACKVEC_STATE_ECN_MARKED) {
548 ccid2_congestion_event(sk, 545 ccid2_congestion_event(sk,
549 seqp); 546 seqp);
550 } else 547 else
551 ccid2_new_ack(sk, seqp, 548 ccid2_new_ack(sk, seqp,
552 &maxincr); 549 &maxincr);
553 550
diff --git a/net/dccp/input.c b/net/dccp/input.c
index 265985370fa1..c7aeeba859d4 100644
--- a/net/dccp/input.c
+++ b/net/dccp/input.c
@@ -378,8 +378,7 @@ int dccp_rcv_established(struct sock *sk, struct sk_buff *skb,
378 378
379 if (dp->dccps_hc_rx_ackvec != NULL && 379 if (dp->dccps_hc_rx_ackvec != NULL &&
380 dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, 380 dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk,
381 DCCP_SKB_CB(skb)->dccpd_seq, 381 DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED))
382 DCCP_ACKVEC_STATE_RECEIVED))
383 goto discard; 382 goto discard;
384 dccp_deliver_input_to_ccids(sk, skb); 383 dccp_deliver_input_to_ccids(sk, skb);
385 384
@@ -637,8 +636,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
637 636
638 if (dp->dccps_hc_rx_ackvec != NULL && 637 if (dp->dccps_hc_rx_ackvec != NULL &&
639 dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, 638 dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk,
640 DCCP_SKB_CB(skb)->dccpd_seq, 639 DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED))
641 DCCP_ACKVEC_STATE_RECEIVED))
642 goto discard; 640 goto discard;
643 641
644 dccp_deliver_input_to_ccids(sk, skb); 642 dccp_deliver_input_to_ccids(sk, skb);
diff --git a/net/dccp/options.c b/net/dccp/options.c
index cd3061813009..799c6f4547cd 100644
--- a/net/dccp/options.c
+++ b/net/dccp/options.c
@@ -340,6 +340,7 @@ static inline int dccp_elapsed_time_len(const u32 elapsed_time)
340 return elapsed_time == 0 ? 0 : elapsed_time <= 0xFFFF ? 2 : 4; 340 return elapsed_time == 0 ? 0 : elapsed_time <= 0xFFFF ? 2 : 4;
341} 341}
342 342
343/* FIXME: This function is currently not used anywhere */
343int dccp_insert_option_elapsed_time(struct sk_buff *skb, u32 elapsed_time) 344int dccp_insert_option_elapsed_time(struct sk_buff *skb, u32 elapsed_time)
344{ 345{
345 const int elapsed_time_len = dccp_elapsed_time_len(elapsed_time); 346 const int elapsed_time_len = dccp_elapsed_time_len(elapsed_time);