ia64/linux-2.6.18-xen.hg

view net/dccp/ackvec.c @ 871:9cbcc9008446

xen/x86: don't initialize cpu_data[]'s apicid field on generic code

Afaict, this is not only redundant with the intialization done in
drivers/xen/core/smpboot.c, but actually results - at least for
secondary CPUs - in the Xen-specific value written to be later
overwritten with whatever the generic code determines (with no
guarantee that the two values are identical).

Signed-off-by: Jan Beulich <jbeulich@novell.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu May 14 10:09:15 2009 +0100 (2009-05-14)
parents 831230e53067
children
line source
1 /*
2 * net/dccp/ackvec.c
3 *
4 * An implementation of the DCCP protocol
5 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; version 2 of the License;
10 */
12 #include "ackvec.h"
13 #include "dccp.h"
15 #include <linux/dccp.h>
16 #include <linux/init.h>
17 #include <linux/errno.h>
18 #include <linux/kernel.h>
19 #include <linux/skbuff.h>
20 #include <linux/slab.h>
22 #include <net/sock.h>
24 static kmem_cache_t *dccp_ackvec_slab;
25 static kmem_cache_t *dccp_ackvec_record_slab;
27 static struct dccp_ackvec_record *dccp_ackvec_record_new(void)
28 {
29 struct dccp_ackvec_record *avr =
30 kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
32 if (avr != NULL)
33 INIT_LIST_HEAD(&avr->dccpavr_node);
35 return avr;
36 }
38 static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr)
39 {
40 if (unlikely(avr == NULL))
41 return;
42 /* Check if deleting a linked record */
43 WARN_ON(!list_empty(&avr->dccpavr_node));
44 kmem_cache_free(dccp_ackvec_record_slab, avr);
45 }
47 static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
48 struct dccp_ackvec_record *avr)
49 {
50 /*
51 * AVRs are sorted by seqno. Since we are sending them in order, we
52 * just add the AVR at the head of the list.
53 * -sorbo.
54 */
55 if (!list_empty(&av->dccpav_records)) {
56 const struct dccp_ackvec_record *head =
57 list_entry(av->dccpav_records.next,
58 struct dccp_ackvec_record,
59 dccpavr_node);
60 BUG_ON(before48(avr->dccpavr_ack_seqno,
61 head->dccpavr_ack_seqno));
62 }
64 list_add(&avr->dccpavr_node, &av->dccpav_records);
65 }
67 int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
68 {
69 struct dccp_sock *dp = dccp_sk(sk);
70 #ifdef CONFIG_IP_DCCP_DEBUG
71 const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
72 "CLIENT tx: " : "server tx: ";
73 #endif
74 struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
75 int len = av->dccpav_vec_len + 2;
76 struct timeval now;
77 u32 elapsed_time;
78 unsigned char *to, *from;
79 struct dccp_ackvec_record *avr;
81 if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
82 return -1;
84 dccp_timestamp(sk, &now);
85 elapsed_time = timeval_delta(&now, &av->dccpav_time) / 10;
87 if (elapsed_time != 0 &&
88 dccp_insert_option_elapsed_time(sk, skb, elapsed_time))
89 return -1;
91 avr = dccp_ackvec_record_new();
92 if (avr == NULL)
93 return -1;
95 DCCP_SKB_CB(skb)->dccpd_opt_len += len;
97 to = skb_push(skb, len);
98 *to++ = DCCPO_ACK_VECTOR_0;
99 *to++ = len;
101 len = av->dccpav_vec_len;
102 from = av->dccpav_buf + av->dccpav_buf_head;
104 /* Check if buf_head wraps */
105 if ((int)av->dccpav_buf_head + len > DCCP_MAX_ACKVEC_LEN) {
106 const u32 tailsize = DCCP_MAX_ACKVEC_LEN - av->dccpav_buf_head;
108 memcpy(to, from, tailsize);
109 to += tailsize;
110 len -= tailsize;
111 from = av->dccpav_buf;
112 }
114 memcpy(to, from, len);
115 /*
116 * From draft-ietf-dccp-spec-11.txt:
117 *
118 * For each acknowledgement it sends, the HC-Receiver will add an
119 * acknowledgement record. ack_seqno will equal the HC-Receiver
120 * sequence number it used for the ack packet; ack_ptr will equal
121 * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
122 * equal buf_nonce.
123 */
124 avr->dccpavr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
125 avr->dccpavr_ack_ptr = av->dccpav_buf_head;
126 avr->dccpavr_ack_ackno = av->dccpav_buf_ackno;
127 avr->dccpavr_ack_nonce = av->dccpav_buf_nonce;
128 avr->dccpavr_sent_len = av->dccpav_vec_len;
130 dccp_ackvec_insert_avr(av, avr);
132 dccp_pr_debug("%sACK Vector 0, len=%d, ack_seqno=%llu, "
133 "ack_ackno=%llu\n",
134 debug_prefix, avr->dccpavr_sent_len,
135 (unsigned long long)avr->dccpavr_ack_seqno,
136 (unsigned long long)avr->dccpavr_ack_ackno);
137 return 0;
138 }
140 struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
141 {
142 struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority);
144 if (av != NULL) {
145 av->dccpav_buf_head =
146 av->dccpav_buf_tail = DCCP_MAX_ACKVEC_LEN - 1;
147 av->dccpav_buf_ackno = DCCP_MAX_SEQNO + 1;
148 av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0;
149 av->dccpav_ack_ptr = 0;
150 av->dccpav_time.tv_sec = 0;
151 av->dccpav_time.tv_usec = 0;
152 av->dccpav_sent_len = av->dccpav_vec_len = 0;
153 INIT_LIST_HEAD(&av->dccpav_records);
154 }
156 return av;
157 }
159 void dccp_ackvec_free(struct dccp_ackvec *av)
160 {
161 if (unlikely(av == NULL))
162 return;
164 if (!list_empty(&av->dccpav_records)) {
165 struct dccp_ackvec_record *avr, *next;
167 list_for_each_entry_safe(avr, next, &av->dccpav_records,
168 dccpavr_node) {
169 list_del_init(&avr->dccpavr_node);
170 dccp_ackvec_record_delete(avr);
171 }
172 }
174 kmem_cache_free(dccp_ackvec_slab, av);
175 }
177 static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
178 const u8 index)
179 {
180 return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK;
181 }
183 static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
184 const u8 index)
185 {
186 return av->dccpav_buf[index] & DCCP_ACKVEC_LEN_MASK;
187 }
189 /*
190 * If several packets are missing, the HC-Receiver may prefer to enter multiple
191 * bytes with run length 0, rather than a single byte with a larger run length;
192 * this simplifies table updates if one of the missing packets arrives.
193 */
194 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
195 const unsigned int packets,
196 const unsigned char state)
197 {
198 unsigned int gap;
199 long new_head;
201 if (av->dccpav_vec_len + packets > DCCP_MAX_ACKVEC_LEN)
202 return -ENOBUFS;
204 gap = packets - 1;
205 new_head = av->dccpav_buf_head - packets;
207 if (new_head < 0) {
208 if (gap > 0) {
209 memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED,
210 gap + new_head + 1);
211 gap = -new_head;
212 }
213 new_head += DCCP_MAX_ACKVEC_LEN;
214 }
216 av->dccpav_buf_head = new_head;
218 if (gap > 0)
219 memset(av->dccpav_buf + av->dccpav_buf_head + 1,
220 DCCP_ACKVEC_STATE_NOT_RECEIVED, gap);
222 av->dccpav_buf[av->dccpav_buf_head] = state;
223 av->dccpav_vec_len += packets;
224 return 0;
225 }
227 /*
228 * Implements the draft-ietf-dccp-spec-11.txt Appendix A
229 */
230 int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
231 const u64 ackno, const u8 state)
232 {
233 /*
234 * Check at the right places if the buffer is full, if it is, tell the
235 * caller to start dropping packets till the HC-Sender acks our ACK
236 * vectors, when we will free up space in dccpav_buf.
237 *
238 * We may well decide to do buffer compression, etc, but for now lets
239 * just drop.
240 *
241 * From Appendix A:
242 *
243 * Of course, the circular buffer may overflow, either when the
244 * HC-Sender is sending data at a very high rate, when the
245 * HC-Receiver's acknowledgements are not reaching the HC-Sender,
246 * or when the HC-Sender is forgetting to acknowledge those acks
247 * (so the HC-Receiver is unable to clean up old state). In this
248 * case, the HC-Receiver should either compress the buffer (by
249 * increasing run lengths when possible), transfer its state to
250 * a larger buffer, or, as a last resort, drop all received
251 * packets, without processing them whatsoever, until its buffer
252 * shrinks again.
253 */
255 /* See if this is the first ackno being inserted */
256 if (av->dccpav_vec_len == 0) {
257 av->dccpav_buf[av->dccpav_buf_head] = state;
258 av->dccpav_vec_len = 1;
259 } else if (after48(ackno, av->dccpav_buf_ackno)) {
260 const u64 delta = dccp_delta_seqno(av->dccpav_buf_ackno,
261 ackno);
263 /*
264 * Look if the state of this packet is the same as the
265 * previous ackno and if so if we can bump the head len.
266 */
267 if (delta == 1 &&
268 dccp_ackvec_state(av, av->dccpav_buf_head) == state &&
269 (dccp_ackvec_len(av, av->dccpav_buf_head) <
270 DCCP_ACKVEC_LEN_MASK))
271 av->dccpav_buf[av->dccpav_buf_head]++;
272 else if (dccp_ackvec_set_buf_head_state(av, delta, state))
273 return -ENOBUFS;
274 } else {
275 /*
276 * A.1.2. Old Packets
277 *
278 * When a packet with Sequence Number S arrives, and
279 * S <= buf_ackno, the HC-Receiver will scan the table
280 * for the byte corresponding to S. (Indexing structures
281 * could reduce the complexity of this scan.)
282 */
283 u64 delta = dccp_delta_seqno(ackno, av->dccpav_buf_ackno);
284 u8 index = av->dccpav_buf_head;
286 while (1) {
287 const u8 len = dccp_ackvec_len(av, index);
288 const u8 state = dccp_ackvec_state(av, index);
289 /*
290 * valid packets not yet in dccpav_buf have a reserved
291 * entry, with a len equal to 0.
292 */
293 if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED &&
294 len == 0 && delta == 0) { /* Found our
295 reserved seat! */
296 dccp_pr_debug("Found %llu reserved seat!\n",
297 (unsigned long long)ackno);
298 av->dccpav_buf[index] = state;
299 goto out;
300 }
301 /* len == 0 means one packet */
302 if (delta < len + 1)
303 goto out_duplicate;
305 delta -= len + 1;
306 if (++index == DCCP_MAX_ACKVEC_LEN)
307 index = 0;
308 }
309 }
311 av->dccpav_buf_ackno = ackno;
312 dccp_timestamp(sk, &av->dccpav_time);
313 out:
314 return 0;
316 out_duplicate:
317 /* Duplicate packet */
318 dccp_pr_debug("Received a dup or already considered lost "
319 "packet: %llu\n", (unsigned long long)ackno);
320 return -EILSEQ;
321 }
323 #ifdef CONFIG_IP_DCCP_DEBUG
324 void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len)
325 {
326 if (!dccp_debug)
327 return;
329 printk("ACK vector len=%d, ackno=%llu |", len,
330 (unsigned long long)ackno);
332 while (len--) {
333 const u8 state = (*vector & DCCP_ACKVEC_STATE_MASK) >> 6;
334 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
336 printk("%d,%d|", state, rl);
337 ++vector;
338 }
340 printk("\n");
341 }
343 void dccp_ackvec_print(const struct dccp_ackvec *av)
344 {
345 dccp_ackvector_print(av->dccpav_buf_ackno,
346 av->dccpav_buf + av->dccpav_buf_head,
347 av->dccpav_vec_len);
348 }
349 #endif
351 static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
352 struct dccp_ackvec_record *avr)
353 {
354 struct dccp_ackvec_record *next;
356 av->dccpav_buf_tail = avr->dccpavr_ack_ptr - 1;
357 if (av->dccpav_buf_tail == 0)
358 av->dccpav_buf_tail = DCCP_MAX_ACKVEC_LEN - 1;
360 av->dccpav_vec_len -= avr->dccpavr_sent_len;
362 /* free records */
363 list_for_each_entry_safe_from(avr, next, &av->dccpav_records,
364 dccpavr_node) {
365 list_del_init(&avr->dccpavr_node);
366 dccp_ackvec_record_delete(avr);
367 }
368 }
370 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
371 const u64 ackno)
372 {
373 struct dccp_ackvec_record *avr;
375 /*
376 * If we traverse backwards, it should be faster when we have large
377 * windows. We will be receiving ACKs for stuff we sent a while back
378 * -sorbo.
379 */
380 list_for_each_entry_reverse(avr, &av->dccpav_records, dccpavr_node) {
381 if (ackno == avr->dccpavr_ack_seqno) {
382 #ifdef CONFIG_IP_DCCP_DEBUG
383 struct dccp_sock *dp = dccp_sk(sk);
384 const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
385 "CLIENT rx ack: " : "server rx ack: ";
386 #endif
387 dccp_pr_debug("%sACK packet 0, len=%d, ack_seqno=%llu, "
388 "ack_ackno=%llu, ACKED!\n",
389 debug_prefix, 1,
390 (unsigned long long)avr->dccpavr_ack_seqno,
391 (unsigned long long)avr->dccpavr_ack_ackno);
392 dccp_ackvec_throw_record(av, avr);
393 break;
394 }
395 }
396 }
398 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
399 struct sock *sk, u64 ackno,
400 const unsigned char len,
401 const unsigned char *vector)
402 {
403 unsigned char i;
404 struct dccp_ackvec_record *avr;
406 /* Check if we actually sent an ACK vector */
407 if (list_empty(&av->dccpav_records))
408 return;
410 i = len;
411 /*
412 * XXX
413 * I think it might be more efficient to work backwards. See comment on
414 * rcv_ackno. -sorbo.
415 */
416 avr = list_entry(av->dccpav_records.next, struct dccp_ackvec_record,
417 dccpavr_node);
418 while (i--) {
419 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
420 u64 ackno_end_rl;
422 dccp_set_seqno(&ackno_end_rl, ackno - rl);
424 /*
425 * If our AVR sequence number is greater than the ack, go
426 * forward in the AVR list until it is not so.
427 */
428 list_for_each_entry_from(avr, &av->dccpav_records,
429 dccpavr_node) {
430 if (!after48(avr->dccpavr_ack_seqno, ackno))
431 goto found;
432 }
433 /* End of the dccpav_records list, not found, exit */
434 break;
435 found:
436 if (between48(avr->dccpavr_ack_seqno, ackno_end_rl, ackno)) {
437 const u8 state = (*vector &
438 DCCP_ACKVEC_STATE_MASK) >> 6;
439 if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) {
440 #ifdef CONFIG_IP_DCCP_DEBUG
441 struct dccp_sock *dp = dccp_sk(sk);
442 const char *debug_prefix =
443 dp->dccps_role == DCCP_ROLE_CLIENT ?
444 "CLIENT rx ack: " : "server rx ack: ";
445 #endif
446 dccp_pr_debug("%sACK vector 0, len=%d, "
447 "ack_seqno=%llu, ack_ackno=%llu, "
448 "ACKED!\n",
449 debug_prefix, len,
450 (unsigned long long)
451 avr->dccpavr_ack_seqno,
452 (unsigned long long)
453 avr->dccpavr_ack_ackno);
454 dccp_ackvec_throw_record(av, avr);
455 break;
456 }
457 /*
458 * If it wasn't received, continue scanning... we might
459 * find another one.
460 */
461 }
463 dccp_set_seqno(&ackno, ackno_end_rl - 1);
464 ++vector;
465 }
466 }
468 int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
469 const u8 opt, const u8 *value, const u8 len)
470 {
471 if (len > DCCP_MAX_ACKVEC_LEN)
472 return -1;
474 /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
475 dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
476 DCCP_SKB_CB(skb)->dccpd_ack_seq,
477 len, value);
478 return 0;
479 }
481 static char dccp_ackvec_slab_msg[] __initdata =
482 KERN_CRIT "DCCP: Unable to create ack vectors slab caches\n";
484 int __init dccp_ackvec_init(void)
485 {
486 dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
487 sizeof(struct dccp_ackvec), 0,
488 SLAB_HWCACHE_ALIGN, NULL, NULL);
489 if (dccp_ackvec_slab == NULL)
490 goto out_err;
492 dccp_ackvec_record_slab =
493 kmem_cache_create("dccp_ackvec_record",
494 sizeof(struct dccp_ackvec_record),
495 0, SLAB_HWCACHE_ALIGN, NULL, NULL);
496 if (dccp_ackvec_record_slab == NULL)
497 goto out_destroy_slab;
499 return 0;
501 out_destroy_slab:
502 kmem_cache_destroy(dccp_ackvec_slab);
503 dccp_ackvec_slab = NULL;
504 out_err:
505 printk(dccp_ackvec_slab_msg);
506 return -ENOBUFS;
507 }
509 void dccp_ackvec_exit(void)
510 {
511 if (dccp_ackvec_slab != NULL) {
512 kmem_cache_destroy(dccp_ackvec_slab);
513 dccp_ackvec_slab = NULL;
514 }
515 if (dccp_ackvec_record_slab != NULL) {
516 kmem_cache_destroy(dccp_ackvec_record_slab);
517 dccp_ackvec_record_slab = NULL;
518 }
519 }