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 <linux/mutex.h>
25 DEFINE_MUTEX(cor_bindnodes
);
26 DEFINE_SPINLOCK(conn_free
);
28 DEFINE_MUTEX(connid_gen
);
37 struct kmem_cache
*conn_slab
;
39 struct htable connid_table
;
41 struct kmem_cache
*bindnode_slab
;
42 struct kmem_cache
*connlistener_slab
;
44 /* see cor.h/KP_ACK_CONN */
45 static const __u32 window_sizes
[] = {0,
46 64, 68, 73, 77, 82, 88, 93, 99, 106, 113, 120,
47 128, 136, 145, 155, 165, 175, 187, 199, 212, 226, 240,
48 256, 273, 290, 309, 329, 351, 374, 398, 424, 451, 481,
49 512, 545, 581, 619, 659, 702, 747, 796, 848, 903, 961,
50 1024, 1091, 1162, 1237, 1318, 1403, 1495, 1592, 1695, 1805,
52 2048, 2181, 2323, 2474, 2635, 2806, 2989, 3183, 3390, 3611,
54 4096, 4362, 4646, 4948, 5270, 5613, 5978, 6367, 6781, 7222,
56 8192, 8725, 9292, 9897, 10540, 11226, 11956, 12734, 13562,
58 16384, 17450, 18585, 19793, 21081, 22452, 23912, 25467, 27124,
60 32768, 34899, 37169, 39587, 42161, 44904, 47824, 50935, 54248,
62 65536, 69799, 74338, 79173, 84323, 89807, 95648, 101870, 108495,
64 131072, 139597, 148677, 158347, 168646, 179615, 191297, 203739,
65 216991, 231104, 246135,
66 262144, 279194, 297353, 316693, 337291, 359229, 382594, 407478,
67 433981, 462208, 492270,
68 524288, 558388, 594706, 633387, 674583, 718459, 765188, 814957,
69 867962, 924415, 984540,
70 1048576, 1116777, 1189413, 1266774, 1349166, 1436917, 1530376,
71 1629913, 1735924, 1848831, 1969081,
72 2097152, 2233553, 2378826, 2533547, 2698332, 2873834, 3060752,
73 3259826, 3471849, 3697662, 3938162,
74 4194304, 4467106, 4757652, 5067094, 5396664, 5747669, 6121503,
75 6519652, 6943698, 7395323, 7876323,
76 8388608, 8934212, 9515303, 10134189, 10793327, 11495337,
77 12243006, 13039305, 13887396, 14790647,
79 16777216, 17868424, 19030606, 20268378, 21586655, 22990674,
80 24486013, 26078610, 27774791, 29581294,
82 33554432, 35736849, 38061212, 40536755, 43173310, 45981349,
83 48972026, 52157220, 55549582, 59162588,
85 67108864, 71473698, 76122425, 81073510, 86346620, 91962698,
86 97944052, 104314440, 111099165, 118325175,
88 134217728, 142947395, 152244850, 162147020, 172693239,
89 183925396, 195888104, 208628880, 222198329,
91 268435456, 285894791, 304489699, 324294041, 345386479,
92 367850791, 391776208, 417257759, 444396658,
94 536870912, 571789581};
96 __u8
enc_window(__u32 window_bytes
)
99 BUG_ON(window_sizes
[255] != 571789581);
100 for (i
=1;i
<256;i
++) {
101 if (window_sizes
[i
] > window_bytes
)
105 return (__u8
)(i
-1); /* round down */
108 __u32
dec_window(__u8 window
)
110 BUG_ON(window_sizes
[255] != 571789581);
111 return window_sizes
[window
];
114 static inline int hdr_size(void)
116 return ((sizeof(struct cell_hdr
) + sizeof(void *) - 1) / sizeof(void *)
120 static inline int elements_per_cell(int cell_size
)
122 return (cell_size
- hdr_size())/sizeof(void *);
125 static inline struct cell_hdr
*cell_addr(struct htable
*ht
, __u32 id
)
127 int idx
= (id
%ht
->htable_size
) / (elements_per_cell(ht
->cell_size
));
128 return (struct cell_hdr
*) (((char *)ht
->htable
) + ht
->cell_size
* idx
);
131 static inline char **element_addr(struct htable
*ht
, __u32 id
)
133 int idx
= (id
%ht
->htable_size
) % (elements_per_cell(ht
->cell_size
));
135 ( ((char *)cell_addr(ht
, id
)) +
136 hdr_size() + idx
*sizeof(void *) );
140 static inline char **next_element(struct htable
*ht
, char *element
)
142 return (char **)(element
+ ht
->entry_offset
);
145 static inline struct kref
*element_kref(struct htable
*ht
, char *element
)
147 return (struct kref
*)(element
+ ht
->kref_offset
);
151 static inline void unlock_element(struct htable
*ht
, __u32 key
)
153 struct cell_hdr
*hdr
= cell_addr(ht
, key
);
154 spin_unlock( &(hdr
->lock
) );
158 static char **get_element_nounlock(struct htable
*ht
, __u32 key
,
161 struct cell_hdr
*hdr
= cell_addr(ht
, key
);
162 char **element
= element_addr(ht
, key
);
164 BUG_ON(0 == element
);
166 spin_lock( &(hdr
->lock
) );
171 if (searcheditem
!= 0 && ht
->matches(*element
, searcheditem
))
173 element
= next_element(ht
, *element
);
179 char *htable_get(struct htable
*ht
, __u32 key
, void *searcheditem
)
181 unsigned long iflags
;
184 if (unlikely(ht
->htable
== 0))
187 local_irq_save(iflags
);
188 element
= *(get_element_nounlock(ht
, key
, searcheditem
));
189 if (likely(element
!= 0))
190 kref_get(element_kref(ht
, element
));
191 unlock_element(ht
, key
);
192 local_irq_restore(iflags
);
197 int htable_delete(struct htable
*ht
, __u32 key
,
198 void *searcheditem
, void (*free
) (struct kref
*ref
))
200 unsigned long iflags
;
205 if (unlikely(ht
->htable
== 0))
208 local_irq_save(iflags
);
210 element
= get_element_nounlock(ht
, key
, searcheditem
);
211 BUG_ON(0 == element
);
213 if (unlikely(*element
== 0)) {
214 /* key not in table */
219 next
= next_element(ht
, *element
);
220 kref_put(element_kref(ht
, *element
), free
);
224 unlock_element(ht
, key
);
225 local_irq_restore(iflags
);
230 void htable_insert(struct htable
*ht
, char *newelement
, __u32 key
)
232 unsigned long iflags
;
235 if (unlikely(ht
->htable
== 0))
238 BUG_ON(*next_element(ht
, newelement
) != 0);
239 local_irq_save(iflags
);
241 element
= get_element_nounlock(ht
, key
, 0);
243 BUG_ON(element
== 0);
244 BUG_ON(*element
!= 0);
246 *element
= newelement
;
247 kref_get(element_kref(ht
, newelement
));
249 unlock_element(ht
, key
);
250 local_irq_restore(iflags
);
254 void htable_init(struct htable
*ht
, int (*matches
)(void *htentry
,
255 void *searcheditem
), __u32 entry_offset
, __u32 kref_offset
)
262 ht
->htable
= kmalloc(PAGE_SIZE
, GFP_KERNEL
);
263 if (unlikely(ht
->htable
== 0)) {
264 printk(KERN_CRIT
"cor: error allocating htable (out of "
268 memset(ht
->htable
, 0, PAGE_SIZE
);
271 num_cells
= PAGE_SIZE
/ht
->cell_size
;
273 for (j
=0;j
<num_cells
;j
++) {
274 struct cell_hdr
*hdr
= (struct cell_hdr
*)
275 ( ((char *) ht
->htable
) + j
* ht
->cell_size
);
276 spin_lock_init(&(hdr
->lock
));
279 ht
->htable_size
= num_cells
* elements_per_cell(ht
->cell_size
);
280 ht
->num_elements
= 0;
282 ht
->matches
= matches
;
283 ht
->entry_offset
= entry_offset
;
284 ht
->kref_offset
= kref_offset
;
287 struct conn
*get_conn(__u32 conn_id
)
289 return (struct conn
*) htable_get(&connid_table
, conn_id
, &conn_id
);
292 static int connid_alloc(struct conn
*sconn
)
297 BUG_ON(sconn
->sourcetype
!= SOURCE_IN
);
299 mutex_lock(&connid_gen
);
304 get_random_bytes((char *) &conn_id
, sizeof(conn_id
));
306 if (unlikely(conn_id
== 0))
309 tmp
= get_conn(conn_id
);
310 if (unlikely(tmp
!= 0)) {
311 kref_put(&(tmp
->ref
), free_conn
);
317 mutex_unlock(&connid_gen
);
322 sconn
->source
.in
.conn_id
= conn_id
;
323 htable_insert(&connid_table
, (char *) sconn
, conn_id
);
324 mutex_unlock(&connid_gen
);
328 void free_conn(struct kref
*ref
)
330 unsigned long iflags
;
331 struct conn
*conn
= container_of(ref
, struct conn
, ref
);
332 struct conn
*reversedir
= 0;
334 BUG_ON(atomic_read(&(conn
->isreset
)) == 0);
336 spin_lock_irqsave(&conn_free
, iflags
);
338 if (conn
->reversedir
!= 0)
339 atomic_set(&(conn
->reversedir
->isreset
), 3);
341 if (atomic_read(&(conn
->isreset
)) != 3)
344 if (conn
->reversedir
!= 0) {
345 conn
->reversedir
->reversedir
= 0;
346 reversedir
= conn
->reversedir
;
347 conn
->reversedir
= 0;
350 if (conn
->sourcetype
== SOURCE_IN
) {
351 kref_put(&(conn
->source
.in
.nb
->ref
), neighbor_free
);
352 conn
->source
.in
.nb
= 0;
355 if (conn
->targettype
== TARGET_OUT
) {
356 kref_put(&(conn
->target
.out
.nb
->ref
), neighbor_free
);
357 conn
->target
.out
.nb
= 0;
360 databuf_free(&(conn
->buf
));
362 kmem_cache_free(conn_slab
, conn
);
365 spin_unlock_irqrestore(&conn_free
, iflags
);
368 free_conn(&(reversedir
->ref
));
372 * rconn ==> the connection we received the commend from
373 * ==> init rconn->target.out + rconn->reversedir->source.in
375 * rc == 1 ==> connid allocation failed
377 * NOTE: call to this func *must* be protected by rcv_lock
379 int conn_init_out(struct conn
*rconn
, struct neighbor
*nb
)
381 struct conn
*sconn
= rconn
->reversedir
;
382 __u32 stall_timeout_ms
= rconn
->target
.unconnected
.stall_timeout_ms
;
384 BUG_ON(rconn
->targettype
!= TARGET_UNCONNECTED
);
386 BUG_ON(sconn
->sourcetype
!= SOURCE_NONE
);
388 memset(&(rconn
->target
.out
), 0, sizeof(rconn
->target
.out
));
389 memset(&(sconn
->source
.in
), 0, sizeof(sconn
->source
.in
));
391 rconn
->targettype
= TARGET_OUT
;
392 sconn
->sourcetype
= SOURCE_IN
;
394 rconn
->target
.out
.nb
= nb
;
395 sconn
->source
.in
.nb
= nb
;
397 /* neighbor pointer */
398 kref_get(&(nb
->ref
));
399 kref_get(&(nb
->ref
));
401 rconn
->target
.out
.stall_timeout_ms
= stall_timeout_ms
;
402 skb_queue_head_init(&(sconn
->source
.in
.reorder_queue
));
404 if (unlikely(connid_alloc(sconn
)))
407 INIT_LIST_HEAD(&(rconn
->target
.out
.retrans_list
));
409 #warning todo add to connect_port
410 rconn
->buf
.first_offset
= 0 - rconn
->buf
.last_read_offset
;
412 mutex_lock(&(nb
->conn_list_lock
));
413 list_add_tail(&(sconn
->source
.in
.nb_list
), &(nb
->rcv_conn_list
));
414 list_add_tail(&(rconn
->target
.out
.nb_list
), &(nb
->snd_conn_list
));
415 mutex_unlock(&(nb
->conn_list_lock
));
418 kref_get(&(rconn
->ref
));
419 kref_get(&(sconn
->ref
));
424 void conn_init_sock_source(struct conn
*conn
)
427 conn
->sourcetype
= SOURCE_SOCK
;
428 memset(&(conn
->source
.sock
), 0, sizeof(conn
->source
.sock
));
429 init_waitqueue_head(&(conn
->source
.sock
.wait
));
432 void conn_init_sock_target(struct conn
*conn
)
435 conn
->targettype
= TARGET_SOCK
;
436 memset(&(conn
->target
.sock
), 0, sizeof(conn
->target
.sock
));
437 init_waitqueue_head(&(conn
->target
.sock
.wait
));
440 struct conn
* alloc_conn(gfp_t allocflags
)
442 struct conn
*rconn
= 0;
443 struct conn
*sconn
= 0;
445 rconn
= kmem_cache_alloc(conn_slab
, allocflags
);
446 if (unlikely(rconn
== 0))
449 sconn
= kmem_cache_alloc(conn_slab
, allocflags
);
450 if (unlikely(sconn
== 0))
453 memset(rconn
, 0, sizeof(struct conn
));
454 memset(sconn
, 0, sizeof(struct conn
));
456 rconn
->reversedir
= sconn
;
457 sconn
->reversedir
= rconn
;
459 kref_init(&(rconn
->ref
));
460 kref_init(&(sconn
->ref
));
462 rconn
->sockstate
= SOCKSTATE_CONN
;
463 sconn
->sockstate
= SOCKSTATE_CONN
;
465 rconn
->sourcetype
= SOURCE_NONE
;
466 sconn
->sourcetype
= SOURCE_NONE
;
467 rconn
->targettype
= TARGET_UNCONNECTED
;
468 sconn
->targettype
= TARGET_UNCONNECTED
;
470 mutex_init(&(rconn
->rcv_lock
));
471 mutex_init(&(sconn
->rcv_lock
));
473 rconn
->target
.unconnected
.stall_timeout_ms
=
474 CONN_STALL_DEFAULT_TIMEOUT_MS
;
475 sconn
->target
.unconnected
.stall_timeout_ms
=
476 CONN_STALL_DEFAULT_TIMEOUT_MS
;
478 databuf_init(&(rconn
->buf
));
479 databuf_init(&(sconn
->buf
));
484 kmem_cache_free(conn_slab
, rconn
);
489 static struct connlistener
*get_connlistener(__be64 port
)
491 struct list_head
*curr
= openports
.next
;
493 while (curr
!= &openports
) {
494 struct bindnode
*currnode
= ((struct bindnode
*)
495 (((char *)curr
) - offsetof(struct bindnode
, lh
)));
496 if (currnode
->port
== port
) {
497 BUG_ON(currnode
->owner
== 0);
498 return currnode
->owner
;
507 void close_port(struct connlistener
*listener
)
509 mutex_lock(&cor_bindnodes
);
511 if (listener
->bn
!= 0) {
512 list_del(&(listener
->bn
->lh
));
513 kmem_cache_free(bindnode_slab
, listener
->bn
);
517 while (list_empty(&(listener
->conn_queue
)) == 0) {
518 struct conn
*rconn
= container_of(listener
->conn_queue
.next
,
519 struct conn
, source
.sock
.cl_list
);
520 list_del(&(rconn
->source
.sock
.cl_list
));
521 atomic_cmpxchg(&(rconn
->reversedir
->isreset
), 0, 1);
523 kref_put(&(rconn
->ref
), free_conn
);
526 kmem_cache_free(connlistener_slab
, listener
);
528 mutex_unlock(&cor_bindnodes
);
531 struct connlistener
*open_port(__be64 port
)
534 struct bindnode
*bn
= 0;
535 struct connlistener
*listener
= 0;
537 mutex_lock(&cor_bindnodes
);
538 if (get_connlistener(port
) != 0)
542 bn
= kmem_cache_alloc(bindnode_slab
, GFP_KERNEL
);
543 listener
= kmem_cache_alloc(connlistener_slab
, GFP_KERNEL
);
545 memset(bn
, 0, sizeof(struct bindnode
));
546 memset(listener
, 0, sizeof(struct connlistener
));
548 bn
->owner
= listener
;
551 /* kref is not actually used */
552 listener
->sockstate
= SOCKSTATE_LISTENER
;
554 mutex_init(&(listener
->lock
));
555 INIT_LIST_HEAD(&(listener
->conn_queue
));
556 init_waitqueue_head(&(listener
->wait
));
558 list_add_tail((struct list_head
*) &(bn
->lh
), &openports
);
561 mutex_unlock(&cor_bindnodes
);
568 * rc == 2 port not open
569 * rc == 3 listener queue full
571 int connect_port(struct conn
*rconn
, __be64 port
)
574 struct connlistener
*listener
;
577 mutex_lock(&cor_bindnodes
);
579 listener
= get_connlistener(port
);
585 mutex_lock(&(listener
->lock
));
587 if (unlikely(listener
->queue_len
>= listener
->queue_maxlen
)) {
588 if (listener
->queue_maxlen
<= 0)
596 kref_get(&(rconn
->reversedir
->ref
));
598 conn_init_sock_target(rconn
);
599 conn_init_sock_source(rconn
->reversedir
);
601 list_add_tail(&(rconn
->reversedir
->source
.sock
.cl_list
),
602 &(listener
->conn_queue
));
603 listener
->queue_len
++;
604 wake_up_interruptible(&(listener
->wait
));
607 mutex_unlock(&(listener
->lock
));
610 mutex_unlock(&cor_bindnodes
);
616 * rc == 2 addrtype not found
617 * rc == 3 addr not found
618 * rc == 4 ==> connid allocation failed
619 * rc == 5 ==> control msg alloc failed
621 int connect_neigh(struct conn
*rconn
,
622 __u16 addrtypelen
, __u8
*addrtype
,
623 __u16 addrlen
, __u8
*addr
)
626 struct control_msg_out
*cm
;
627 struct neighbor
*nb
= find_neigh(addrtypelen
, addrtype
, addrlen
, addr
);
630 if (unlikely(conn_init_out(rconn
, nb
))) {
635 cm
= alloc_control_msg();
636 if (unlikely(cm
== 0)) {
641 send_connect_nb(cm
, nb
, rconn
->reversedir
->source
.in
.conn_id
);
644 kref_put(&(nb
->ref
), neighbor_free
);
649 static int _reset_conn(struct conn
*conn
)
652 * aktive conns have an additional ref to make sure that they are not
653 * freed when only one direction is referenced by the connid hashtable
656 int isreset
= atomic_cmpxchg(&(conn
->isreset
), 0, 2);
658 isreset
= atomic_cmpxchg(&(conn
->isreset
), 1, 2);
660 if (isreset
== 2 || isreset
== 3)
663 /* lock sourcetype/targettype */
664 mutex_lock(&(conn
->rcv_lock
));
666 if (conn
->sourcetype
== SOURCE_IN
) {
667 mutex_lock(&(conn
->source
.in
.nb
->conn_list_lock
));
668 list_del(&(conn
->source
.in
.nb_list
));
669 mutex_unlock(&(conn
->source
.in
.nb
->conn_list_lock
));
673 if (conn
->source
.in
.conn_id
!= 0) {
674 if (htable_delete(&connid_table
,
675 conn
->source
.in
.conn_id
,
676 &(conn
->source
.in
.conn_id
), free_conn
)){
677 printk(KERN_ERR
"error in _reset_conn: "
678 "htable_delete failed");
681 } else if (conn
->sourcetype
== SOURCE_SOCK
) {
682 wake_up_interruptible(&(conn
->source
.sock
.wait
));
685 if (conn
->targettype
== TARGET_OUT
) {
686 mutex_lock(&(conn
->target
.out
.nb
->conn_list_lock
));
687 list_del(&(conn
->target
.out
.nb_list
));
688 mutex_unlock(&(conn
->target
.out
.nb
->conn_list_lock
));
692 if (isreset
== 0 && conn
->target
.out
.conn_id
!= 0) {
693 struct control_msg_out
*cm
= alloc_control_msg();
695 send_reset_conn(cm
, conn
->target
.out
.nb
,
696 conn
->target
.out
.conn_id
);
699 cancel_retrans(conn
);
700 } else if (conn
->targettype
== TARGET_SOCK
) {
701 wake_up_interruptible(&(conn
->target
.sock
.wait
));
704 databuf_free(&(conn
->buf
));
706 mutex_unlock(&(conn
->rcv_lock
));
711 /* warning: do not hold the rcv_lock while calling this! */
712 void reset_conn(struct conn
*conn
)
714 int put1
= _reset_conn(conn
);
715 int put2
= _reset_conn(conn
->reversedir
);
717 /*free_conn may not be called, before both _reset_conn have finished */
719 kref_put(&(conn
->ref
), free_conn
);
724 kref_put(&(conn
->reversedir
->ref
), free_conn
);
729 static int matches_connid_in(void *htentry
, void *searcheditem
)
731 struct conn
*conn
= (struct conn
*) htentry
;
732 __u32 conn_id
= *((__u32
*) searcheditem
);
733 BUG_ON(conn
->sourcetype
!= SOURCE_IN
);
734 return (conn
->source
.in
.conn_id
== conn_id
);
737 static int __init
cor_common_init(void)
743 printk(KERN_ERR
"sizeof conn: %d", sizeof(c
));
744 printk(KERN_ERR
" conn.source: %d", sizeof(c
.source
));
745 printk(KERN_ERR
" conn.target: %d", sizeof(c
.target
));
746 printk(KERN_ERR
" conn.target.out: %d", sizeof(c
.target
.out
));
747 printk(KERN_ERR
" conn.buf: %d", sizeof(c
.buf
));
749 printk(KERN_ERR
" mutex: %d", sizeof(struct mutex
));
750 printk(KERN_ERR
" spinlock: %d", sizeof(spinlock_t
));
751 printk(KERN_ERR
" kref: %d", sizeof(struct kref
));
754 conn_slab
= kmem_cache_create("cor_conn", sizeof(struct conn
), 8, 0, 0);
755 htable_init(&connid_table
, matches_connid_in
,
756 offsetof(struct conn
, source
.in
.htab_entry
),
757 offsetof(struct conn
, ref
));
759 bindnode_slab
= kmem_cache_create("cor_bindnode",
760 sizeof(struct bindnode
), 8, 0, 0);
761 connlistener_slab
= kmem_cache_create("cor_connlistener",
762 sizeof(struct connlistener
), 8, 0, 0);
769 if (unlikely(rc
!= 0))
772 rc
= cor_neighbor_init();
773 if (unlikely(rc
!= 0))
777 if (unlikely(rc
!= 0))
783 module_init(cor_common_init
);
784 MODULE_LICENSE("GPL");