2 * Connection oriented routing
3 * Copyright (C) 2007-2008 Michael Blizek
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 #include <asm/byteorder.h>
25 /* not sent over the network - internal meaning only */
26 #define MSGTYPE_PONG 1
28 #define MSGTYPE_CONNECT 3
29 #define MSGTYPE_CONNECT_SUCCESS 4
30 #define MSGTYPE_RESET_CONN 5
31 #define MSGTYPE_CONNDATA 6
36 struct control_msg_out
{
37 struct list_head lh
; /* either neighbor or control_retrans_packet */
46 unsigned long time_enqueued
; /* jiffies */
77 struct control_retrans
{
83 unsigned long timeout
;
85 struct list_head msgs
;
87 struct htab_entry htab_entry
;
88 struct list_head timeout_list
;
91 struct kmem_cache
*controlmsg_slab
;
92 struct kmem_cache
*controlretrans_slab
;
94 static struct htable retransmits
;
96 static void add_control_msg(struct control_msg_out
*msg
, struct neighbor
*nb
);
98 struct control_msg_out
*alloc_control_msg(void)
100 struct control_msg_out
*cm
= kmem_cache_alloc(controlmsg_slab
,
102 if (unlikely(cm
== 0))
104 cm
->lh
.next
= LIST_POISON1
;
105 cm
->lh
.prev
= LIST_POISON2
;
109 void free_control_msg(struct control_msg_out
*cm
)
111 kmem_cache_free(controlmsg_slab
, cm
);
114 static void free_control_retrans(struct kref
*ref
)
116 struct control_retrans
*cr
= container_of(ref
, struct control_retrans
,
119 while (list_empty(&(cr
->msgs
))) {
120 struct control_msg_out
*cm
= container_of(cr
->msgs
.next
,
121 struct control_msg_out
, lh
);
123 free_control_msg(cm
);
126 kref_put(&(cr
->nb
->ref
), neighbor_free
);
127 kmem_cache_free(controlretrans_slab
, cr
);
130 struct retransmit_matchparam
{
135 static __u32
rm_to_key(struct retransmit_matchparam
*rm
)
137 return ((__u32
) rm
->nb
) ^ rm
->seqno
;
140 static void set_retrans_timeout(struct control_retrans
*cr
, struct neighbor
*nb
)
142 cr
->timeout
= jiffies
+ msecs_to_jiffies(300 +
143 ((__u32
) atomic_read(&(nb
->latency
)))/1000);
146 void retransmit_timerfunc(unsigned long arg
)
148 unsigned long iflags
;
150 struct neighbor
*nb
= (struct neighbor
*) arg
;
155 spin_lock_irqsave( &(nb
->state_lock
), iflags
);
157 spin_unlock_irqrestore( &(nb
->state_lock
), iflags
);
160 struct control_retrans
*cr
= 0;
161 struct retransmit_matchparam rm
;
163 spin_lock_irqsave( &(nb
->retrans_lock
), iflags
);
165 if (list_empty(&(nb
->retrans_list
))) {
166 nb
->retrans_timer_running
= 0;
171 cr
= container_of(nb
->retrans_list
.next
,
172 struct control_retrans
, timeout_list
);
174 BUG_ON(cr
->nb
!= nb
);
176 rm
.seqno
= cr
->seqno
;
179 if (nbstate
== NEIGHBOR_STATE_KILLED
) {
180 spin_unlock_irqrestore( &(nb
->retrans_lock
), iflags
);
182 htable_delete(&retransmits
, rm_to_key(&rm
), &rm
,
183 free_control_retrans
);
184 kref_put(&(cr
->ref
), free_control_retrans
);
189 if (time_after(cr
->timeout
, jiffies
)) {
190 list_add(&(cr
->timeout_list
), &(nb
->retrans_list
));
191 mod_timer(&(nb
->retrans_timer
), cr
->timeout
);
195 if (unlikely(htable_delete(&retransmits
, rm_to_key(&rm
), &rm
,
196 free_control_retrans
)))
199 spin_unlock_irqrestore( &(nb
->retrans_lock
), iflags
);
201 while (list_empty(&(cr
->msgs
))) {
202 struct control_msg_out
*cm
= container_of(cr
->msgs
.next
,
203 struct control_msg_out
, lh
);
205 add_control_msg(cm
, cr
->nb
);
208 kref_put(&(cr
->ref
), free_control_retrans
);
211 spin_unlock_irqrestore( &(nb
->retrans_lock
), iflags
);
214 kref_put(&(nb
->ref
), neighbor_free
);
217 static void schedule_retransmit(struct control_retrans
*cr
, struct neighbor
*nb
)
219 unsigned long iflags
;
221 struct retransmit_matchparam rm
;
224 rm
.seqno
= cr
->seqno
;
227 set_retrans_timeout(cr
, nb
);
229 spin_lock_irqsave( &(nb
->retrans_lock
), iflags
);
230 htable_insert(&retransmits
, (char *) cr
, rm_to_key(&rm
));
231 first
= list_empty(&(nb
->retrans_list
));
232 list_add_tail(&(cr
->timeout_list
), &(nb
->retrans_list
));
234 if (first
&& nb
->retrans_timer_running
== 0) {
235 mod_timer(&(nb
->retrans_timer
), cr
->timeout
);
236 nb
->retrans_timer_running
= 1;
237 kref_get(&(nb
->ref
));
240 spin_unlock_irqrestore( &(nb
->retrans_lock
), iflags
);
243 void kern_ack_rcvd(struct neighbor
*nb
, __u32 seqno
)
245 unsigned long iflags
;
247 struct control_retrans
*cr
= 0;
248 struct retransmit_matchparam rm
;
253 spin_lock_irqsave( &(nb
->retrans_lock
), iflags
);
255 cr
= (struct control_retrans
*) htable_get(&retransmits
, rm_to_key(&rm
),
259 printk(KERN_ERR
"bogus/duplicate ack received");
263 if (unlikely(htable_delete(&retransmits
, rm_to_key(&rm
), &rm
,
264 free_control_retrans
)))
267 BUG_ON(cr
->nb
!= nb
);
269 list_add_tail(&(cr
->timeout_list
), &(nb
->retrans_list
));
272 spin_unlock_irqrestore( &(nb
->retrans_lock
), iflags
);
275 static void padding(struct sk_buff
*skb
, int length
)
277 char *dst
= skb_put(skb
, length
);
279 memset(dst
, KP_PADDING
, length
);
282 static int add_ack(struct sk_buff
*skb
, struct control_retrans
*cr
,
283 struct control_msg_out
*cm
, int spaceleft
)
287 if (unlikely(spaceleft
< 9))
290 dst
= skb_put(skb
, 9);
294 put_u32(dst
+ 1, cm
->msg
.ack
.conn_id
, 1);
295 put_u32(dst
+ 5, cm
->msg
.ack
.seqno
, 1);
297 list_add_tail(&(cm
->lh
), &(cr
->msgs
));
302 static int add_ping(struct sk_buff
*skb
, __u32 cookie
,
307 if (unlikely(spaceleft
< 5))
310 dst
= skb_put(skb
, 5);
314 put_u32(dst
+ 1, cookie
, 0);
319 static int add_pong(struct sk_buff
*skb
, struct control_retrans
*cr
,
320 struct control_msg_out
*cm
, int spaceleft
)
324 if (unlikely(spaceleft
< 9))
327 dst
= skb_put(skb
, 9);
331 put_u32(dst
+ 1, cm
->msg
.pong
.cookie
, 0);
332 put_u32(dst
+ 5, 1000 * jiffies_to_msecs(jiffies
-
333 cm
->msg
.pong
.time_enqueued
), 1);
335 list_add_tail(&(cm
->lh
), &(cr
->msgs
));
340 static int add_connect(struct sk_buff
*skb
, struct control_retrans
*cr
,
341 struct control_msg_out
*cm
, int spaceleft
)
345 if (unlikely(spaceleft
< 5))
348 dst
= skb_put(skb
, 5);
352 put_u32(dst
+ 1, cm
->msg
.connect
.conn_id
, 1);
354 list_add_tail(&(cm
->lh
), &(cr
->msgs
));
359 static int add_connect_success(struct sk_buff
*skb
, struct control_retrans
*cr
,
360 struct control_msg_out
*cm
, int spaceleft
)
364 if (unlikely(spaceleft
< 9))
367 dst
= skb_put(skb
, 9);
370 dst
[0] = KP_CONNECT_SUCCESS
;
371 put_u32(dst
+ 1, cm
->msg
.connect_success
.rcvd_conn_id
, 1);
372 put_u32(dst
+ 5, cm
->msg
.connect_success
.gen_conn_id
, 1);
374 list_add_tail(&(cm
->lh
), &(cr
->msgs
));
379 static int add_reset_conn(struct sk_buff
*skb
, struct control_retrans
*cr
,
380 struct control_msg_out
*cm
, int spaceleft
)
384 if (unlikely(spaceleft
< 5))
387 dst
= skb_put(skb
, 5);
390 dst
[0] = KP_RESET_CONN
;
391 put_u32(dst
+ 1, cm
->msg
.reset
.conn_id
, 1);
393 list_add_tail(&(cm
->lh
), &(cr
->msgs
));
398 static int add_conndata(struct sk_buff
*skb
, struct control_msg_out
*cm
,
403 int totallen
= cm
->msg
.conn_data
.datalen
+ 11;
404 int putlen
= min(totallen
, spaceleft
);
405 int dataputlen
= putlen
- 11;
407 if (dataputlen
< 1 || (spaceleft
< 25 && spaceleft
< totallen
))
410 dst
= skb_put(skb
, putlen
);
413 dst
[0] = KP_CONN_DATA
;
414 put_u32(dst
+ 1, cm
->msg
.conn_data
.conn_id
, 1);
415 put_u32(dst
+ 5, cm
->msg
.conn_data
.seqno
, 1);
416 put_u16(dst
+ 9, dataputlen
, 1);
418 memcpy(dst
+ 11, cm
->msg
.conn_data
.data
, dataputlen
);
420 cm
->msg
.conn_data
.datalen
-= dataputlen
;
421 cm
->msg
.conn_data
.data
+= dataputlen
;
423 if (cm
->msg
.conn_data
.datalen
== 0) {
424 kfree(cm
->msg
.conn_data
.data_orig
);
425 free_control_msg(cm
);
427 send_conndata(cm
, cm
->nb
, cm
->msg
.conn_data
.conn_id
,
428 cm
->msg
.conn_data
.seqno
,
429 cm
->msg
.conn_data
.data_orig
,
430 cm
->msg
.conn_data
.data
,
431 cm
->msg
.conn_data
.datalen
);
437 static int add_message(struct sk_buff
*skb
, struct control_retrans
*cr
,
438 struct control_msg_out
*cm
, int spaceleft
)
442 return add_ack(skb
, cr
, cm
, spaceleft
);
444 return add_pong(skb
, cr
, cm
, spaceleft
);
445 case MSGTYPE_CONNECT
:
446 return add_connect(skb
, cr
, cm
, spaceleft
);
447 case MSGTYPE_CONNECT_SUCCESS
:
448 return add_connect_success(skb
, cr
, cm
, spaceleft
);
449 case MSGTYPE_RESET_CONN
:
450 return add_reset_conn(skb
, cr
, cm
, spaceleft
);
451 case MSGTYPE_CONNDATA
:
452 return add_conndata(skb
, cm
, spaceleft
);
460 static void _send_messages(struct neighbor
*nb
, struct sk_buff
*skb
,
461 struct control_retrans
*cr
, int spaceleft
, int pongsonly
)
466 mutex_lock(&(nb
->cmsg_lock
));
467 while (!list_empty(&(nb
->ucontrol_msgs_out
)) || (!pongsonly
&&
468 !list_empty(&(nb
->control_msgs_out
)))) {
471 int urgent
= !list_empty(&(nb
->ucontrol_msgs_out
));
473 struct control_msg_out
*cm
;
477 cm
= container_of(nb
->ucontrol_msgs_out
.next
,
478 struct control_msg_out
, lh
);
480 cm
= container_of(nb
->control_msgs_out
.next
,
481 struct control_msg_out
, lh
);
485 nb
->ucmlength
-= cm
->length
;
487 nb
->cmlength
-= cm
->length
;
488 if (cm
->type
!= MSGTYPE_ACK
|| cm
->msg
.ack
.conn_id
!= 0)
490 mutex_unlock(&(nb
->cmsg_lock
));
491 rc
= add_message(skb
, cr
, cm
, spaceleft
- length
);
492 mutex_lock(&(nb
->cmsg_lock
));
496 list_add(&(cm
->lh
), &(nb
->ucontrol_msgs_out
));
497 nb
->ucmlength
+= cm
->length
;
499 list_add(&(cm
->lh
), &(nb
->control_msgs_out
));
500 nb
->cmlength
+= cm
->length
;
511 mutex_unlock(&(nb
->cmsg_lock
));
513 padding(skb
, spaceleft
- length
);
515 schedule_retransmit(cr
, nb
);
520 static void send_messages(struct neighbor
*nb
, int allmsgs
)
522 int targetmss
= mss(nb
);
526 int pingdelay1
= 1000;
527 int pingdelay2
= 400;
529 int nbstate
= get_neigh_state(nb
);
531 mutex_lock(&(nb
->cmsg_lock
));
533 BUG_ON(list_empty(&(nb
->control_msgs_out
)) && (nb
->cmlength
!= 0));
534 BUG_ON((list_empty(&(nb
->control_msgs_out
)) == 0) &&
535 (nb
->cmlength
== 0));
536 BUG_ON(list_empty(&(nb
->ucontrol_msgs_out
)) && (nb
->ucmlength
!= 0));
537 BUG_ON((list_empty(&(nb
->ucontrol_msgs_out
)) == 0) &&
538 (nb
->ucmlength
== 0));
540 pingok
= time_to_send_ping(nb
);
543 ping
= time_after_eq(jiffies
, nb
->last_ping_time
+
544 msecs_to_jiffies(pingdelay1
));
546 while ((((nbstate
== NEIGHBOR_STATE_ACTIVE
&&
547 !list_empty(&(nb
->control_msgs_out
))) ||
548 !list_empty(&(nb
->ucontrol_msgs_out
))
549 ) && ( (nbstate
== NEIGHBOR_STATE_ACTIVE
?
550 nb
->cmlength
: 0) + nb
->ucmlength
>= targetmss
||
551 allmsgs
)) || (pingok
&& ping
)) {
552 __u32 seqno
= atomic_add_return(1, &(nb
->kpacket_seqno
));
554 struct control_retrans
*cr
;
555 int size
= targetmss
;
558 if (pingok
&& nb
->noping_cnt
> 3)
560 if (pingok
&& time_before_eq(nb
->last_ping_time
+
561 msecs_to_jiffies(pingdelay2
), jiffies
))
565 length
= nb
->ucmlength
+ (ping
!= 0 ? 5 : 0) + (likely(
566 nbstate
== NEIGHBOR_STATE_ACTIVE
) ?
570 mutex_unlock(&(nb
->cmsg_lock
));
571 skb
= create_packet(nb
, size
, GFP_KERNEL
, 0, seqno
);
572 if (unlikely(skb
== 0)) {
573 printk(KERN_ERR
"cor: send_messages: cannot allocate "
574 "skb (out of memory?)");
578 cr
= kmem_cache_alloc(controlretrans_slab
, GFP_KERNEL
);
579 if (unlikely(cr
== 0)) {
581 printk(KERN_ERR
"cor: send_messages: cannot allocate "
582 "control_retrans (out of memory?)");
585 memset(cr
, 0, sizeof(struct control_retrans
));
586 kref_init(&(cr
->ref
));
589 INIT_LIST_HEAD(&(cr
->msgs
));
592 __u32 pingcookie
= add_ping_req(nb
);
593 int rc
= add_ping(skb
, pingcookie
, size
);
596 nb
->last_ping_time
= jiffies
;
600 _send_messages(nb
, skb
, cr
, size
, nbstate
!= NEIGHBOR_STATE_ACTIVE
);
602 mutex_lock(&(nb
->cmsg_lock
));
604 mutex_unlock(&(nb
->cmsg_lock
));
607 BUG_ON(nb
->cmlength
< 0);
610 static void controlmsg_timerfunc(struct work_struct
*work
)
612 struct neighbor
*nb
= container_of(to_delayed_work(work
),
613 struct neighbor
, cmsg_timer
);
614 __u64 jiffies
= get_jiffies_64();
616 mutex_lock(&(nb
->cmsg_lock
));
618 if (nb
->timeout
> jiffies
) {
619 INIT_DELAYED_WORK(&(nb
->cmsg_timer
), controlmsg_timerfunc
);
620 schedule_delayed_work(&(nb
->cmsg_timer
), nb
->timeout
- jiffies
);
621 mutex_unlock(&(nb
->cmsg_lock
));
625 mutex_unlock(&(nb
->cmsg_lock
));
627 send_messages(nb
, 1);
628 schedule_controlmsg_timerfunc(nb
);
629 kref_put(&(nb
->ref
), neighbor_free
);
632 void schedule_controlmsg_timerfunc(struct neighbor
*nb
)
634 int target_delay_ms
= 100;
635 int target_delay_jiffies
= msecs_to_jiffies(target_delay_ms
);
636 __u64 jiffies
= get_jiffies_64();
639 int state
= get_neigh_state(nb
);
641 if (unlikely(state
== NEIGHBOR_STATE_KILLED
))
644 mutex_lock(&(nb
->cmsg_lock
));
645 nb
->timeout
+= target_delay_jiffies
;
647 delay
= nb
->timeout
- jiffies
;
650 nb
->timeout
= jiffies
;
653 INIT_DELAYED_WORK(&(nb
->cmsg_timer
), controlmsg_timerfunc
);
654 schedule_delayed_work(&(nb
->cmsg_timer
), delay
);
655 mutex_unlock(&(nb
->cmsg_lock
));
656 kref_get(&(nb
->ref
));
659 static void add_control_msg(struct control_msg_out
*msg
, struct neighbor
*nb
)
661 int nbstate
= get_neigh_state(nb
);
664 BUG_ON(msg
->lh
.next
!= LIST_POISON1
|| msg
->lh
.prev
!= LIST_POISON2
);
666 mutex_lock(&(nb
->cmsg_lock
));
669 if (unlikely(msg
->type
== MSGTYPE_PONG
|| (msg
->type
== MSGTYPE_ACK
&&
670 msg
->msg
.ack
.conn_id
== 0))) {
671 nb
->ucmlength
+= msg
->length
;
672 list_add_tail(&(msg
->lh
), &(nb
->ucontrol_msgs_out
));
674 nb
->cmlength
+= msg
->length
;
675 list_add_tail(&(msg
->lh
), &(nb
->control_msgs_out
));
678 if (unlikely((nbstate
== NEIGHBOR_STATE_ACTIVE
? nb
->cmlength
: 0) +
679 nb
->ucmlength
>= mss(nb
)))
680 send_messages(nb
, 0);
682 mutex_unlock(&(nb
->cmsg_lock
));
685 void send_pong(struct control_msg_out
*cm
, struct neighbor
*nb
, __u32 cookie
)
687 cm
->type
= MSGTYPE_PONG
;
688 cm
->msg
.pong
.cookie
= cookie
;
689 cm
->msg
.pong
.time_enqueued
= jiffies
;
691 add_control_msg(cm
, nb
);
694 void send_reset_conn(struct control_msg_out
*cm
, struct neighbor
*nb
,
697 cm
->type
= MSGTYPE_RESET_CONN
;
698 cm
->msg
.reset
.conn_id
= conn_id
;
700 add_control_msg(cm
, nb
);
703 void send_ack(struct control_msg_out
*cm
, struct neighbor
*nb
, __u32 conn_id
,
706 cm
->type
= MSGTYPE_ACK
;
707 cm
->msg
.ack
.conn_id
= conn_id
;
708 cm
->msg
.ack
.seqno
= seqno
;
710 add_control_msg(cm
, nb
);
713 void send_connect_success(struct control_msg_out
*cm
, struct neighbor
*nb
,
714 __u32 rcvd_conn_id
, __u32 gen_conn_id
)
716 cm
->type
= MSGTYPE_CONNECT_SUCCESS
;
717 cm
->msg
.connect_success
.rcvd_conn_id
= rcvd_conn_id
;
718 cm
->msg
.connect_success
.gen_conn_id
= gen_conn_id
;
720 add_control_msg(cm
, nb
);
723 void send_connect_nb(struct control_msg_out
*cm
, struct neighbor
*nb
,
726 cm
->type
= MSGTYPE_CONNECT
;
727 cm
->msg
.connect
.conn_id
= conn_id
;
729 add_control_msg(cm
, nb
);
732 void send_conndata(struct control_msg_out
*cm
, struct neighbor
*nb
,
733 __u32 conn_id
, __u32 seqno
, char *data_orig
, char *data
,
736 cm
->type
= MSGTYPE_CONNDATA
;
737 cm
->msg
.conn_data
.conn_id
= conn_id
;
738 cm
->msg
.conn_data
.seqno
= seqno
;
739 cm
->msg
.conn_data
.data_orig
= data_orig
;
740 cm
->msg
.conn_data
.data
= data
;
741 cm
->msg
.conn_data
.datalen
= datalen
;
742 cm
->length
= 11 + datalen
;
743 add_control_msg(cm
, nb
);
746 static int matches_connretrans(void *htentry
, void *searcheditem
)
748 struct control_retrans
*cr
= (struct control_retrans
*) htentry
;
749 struct retransmit_matchparam
*rm
= (struct retransmit_matchparam
*)
752 return rm
->nb
== cr
->nb
&& rm
->seqno
== cr
->seqno
;
755 void __init
cor_kgen_init(void)
757 controlmsg_slab
= kmem_cache_create("cor_controlmsg",
758 sizeof(struct control_msg_out
), 8, 0, 0);
759 controlretrans_slab
= kmem_cache_create("cor_controlretransmsg",
760 sizeof(struct control_retrans
), 8, 0, 0);
761 htable_init(&retransmits
, matches_connretrans
,
762 offsetof(struct control_retrans
, htab_entry
),
763 offsetof(struct control_retrans
, ref
));