retransmit bugfixes, ping timing
[cor_2_6_31.git] / net / cor / common.c
blob7acce1a11d611038a6cdb69b711e93955a65774b
1 /*
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
18 * 02110-1301, USA.
21 #include <linux/mutex.h>
23 #include "cor.h"
25 DEFINE_MUTEX(cor_bindnodes);
26 DEFINE_SPINLOCK(conn_free);
28 DEFINE_MUTEX(connid_gen);
30 LIST_HEAD(openports);
33 struct cell_hdr{
34 spinlock_t lock;
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,
51 1923,
52 2048, 2181, 2323, 2474, 2635, 2806, 2989, 3183, 3390, 3611,
53 3846,
54 4096, 4362, 4646, 4948, 5270, 5613, 5978, 6367, 6781, 7222,
55 7692,
56 8192, 8725, 9292, 9897, 10540, 11226, 11956, 12734, 13562,
57 14444, 15383,
58 16384, 17450, 18585, 19793, 21081, 22452, 23912, 25467, 27124,
59 28888, 30767,
60 32768, 34899, 37169, 39587, 42161, 44904, 47824, 50935, 54248,
61 57776, 61534,
62 65536, 69799, 74338, 79173, 84323, 89807, 95648, 101870, 108495,
63 115552, 123068,
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,
78 15752647,
79 16777216, 17868424, 19030606, 20268378, 21586655, 22990674,
80 24486013, 26078610, 27774791, 29581294,
81 31505293,
82 33554432, 35736849, 38061212, 40536755, 43173310, 45981349,
83 48972026, 52157220, 55549582, 59162588,
84 63010587,
85 67108864, 71473698, 76122425, 81073510, 86346620, 91962698,
86 97944052, 104314440, 111099165, 118325175,
87 126021174,
88 134217728, 142947395, 152244850, 162147020, 172693239,
89 183925396, 195888104, 208628880, 222198329,
90 236650351, 252042347,
91 268435456, 285894791, 304489699, 324294041, 345386479,
92 367850791, 391776208, 417257759, 444396658,
93 473300701, 504084694,
94 536870912, 571789581};
96 __u8 enc_window(__u32 window_bytes)
98 int i;
99 BUG_ON(window_sizes[255] != 571789581);
100 for (i=1;i<256;i++) {
101 if (window_sizes[i] > window_bytes)
102 break;
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 *)
117 ) * 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));
134 return (char **)
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,
159 void *searcheditem)
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) );
168 while (1) {
169 if (*element == 0)
170 break;
171 if (searcheditem != 0 && ht->matches(*element, searcheditem))
172 break;
173 element = next_element(ht, *element);
176 return element;
179 char *htable_get(struct htable *ht, __u32 key, void *searcheditem)
181 unsigned long iflags;
182 char *element;
184 if (unlikely(ht->htable == 0))
185 return 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);
194 return element;
197 int htable_delete(struct htable *ht, __u32 key,
198 void *searcheditem, void (*free) (struct kref *ref))
200 unsigned long iflags;
201 char **element;
202 char **next;
203 int rc = 0;
205 if (unlikely(ht->htable == 0))
206 return 1;
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 */
215 rc = 1;
216 goto out;
219 next = next_element(ht, *element);
220 kref_put(element_kref(ht, *element), free);
221 *element = *next;
223 out:
224 unlock_element(ht, key);
225 local_irq_restore(iflags);
227 return rc;
230 void htable_insert(struct htable *ht, char *newelement, __u32 key)
232 unsigned long iflags;
233 char **element;
235 if (unlikely(ht->htable == 0))
236 return;
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)
257 int num_cells;
258 int j;
260 BUG_ON(0 == ht);
262 ht->htable = kmalloc(PAGE_SIZE, GFP_KERNEL);
263 if (unlikely(ht->htable == 0)) {
264 printk(KERN_CRIT "cor: error allocating htable (out of "
265 "memory?)");
266 return;
268 memset(ht->htable, 0, PAGE_SIZE);
269 ht->cell_size = 256;
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)
294 __u32 conn_id;
295 int i;
297 BUG_ON(sconn->sourcetype != SOURCE_IN);
299 mutex_lock(&connid_gen);
300 for(i=0;i<16;i++) {
301 struct conn *tmp;
303 conn_id = 0;
304 get_random_bytes((char *) &conn_id, sizeof(conn_id));
306 if (unlikely(conn_id == 0))
307 continue;
309 tmp = get_conn(conn_id);
310 if (unlikely(tmp != 0)) {
311 kref_put(&(tmp->ref), free_conn);
312 continue;
315 goto found;
317 mutex_unlock(&connid_gen);
319 return 1;
321 found:
322 sconn->source.in.conn_id = conn_id;
323 htable_insert(&connid_table, (char *) sconn, conn_id);
324 mutex_unlock(&connid_gen);
325 return 0;
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)
342 goto out;
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);
364 out:
365 spin_unlock_irqrestore(&conn_free, iflags);
367 if (reversedir != 0)
368 free_conn(&(reversedir->ref));
372 * rconn ==> the connection we received the commend from
373 * ==> init rconn->target.out + rconn->reversedir->source.in
374 * rc == 0 ==> ok
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);
385 BUG_ON(sconn == 0);
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)))
405 return 1;
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));
417 /* neighbor lists */
418 kref_get(&(rconn->ref));
419 kref_get(&(sconn->ref));
421 return 0;
424 void conn_init_sock_source(struct conn *conn)
426 BUG_ON(conn == 0);
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)
434 BUG_ON(conn == 0);
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))
447 goto out_err0;
449 sconn = kmem_cache_alloc(conn_slab, allocflags);
450 if (unlikely(sconn == 0))
451 goto out_err1;
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));
481 return rconn;
483 out_err1:
484 kmem_cache_free(conn_slab, rconn);
485 out_err0:
486 return 0;
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;
501 curr = curr->next;
504 return 0;
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);
514 listener->bn = 0;
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);
522 reset_conn(rconn);
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)
539 goto out;
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;
549 bn->port = port;
551 /* kref is not actually used */
552 listener->sockstate = SOCKSTATE_LISTENER;
553 listener->bn = bn;
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);
560 out:
561 mutex_unlock(&cor_bindnodes);
563 return listener;
567 * rc == 0 connected
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;
575 int rc = 0;
577 mutex_lock(&cor_bindnodes);
579 listener = get_connlistener(port);
580 if (listener == 0) {
581 rc = 2;
582 goto out;
585 mutex_lock(&(listener->lock));
587 if (unlikely(listener->queue_len >= listener->queue_maxlen)) {
588 if (listener->queue_maxlen <= 0)
589 rc = 2;
590 else
591 rc = 3;
593 goto out2;
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));
606 out2:
607 mutex_unlock(&(listener->lock));
609 out:
610 mutex_unlock(&cor_bindnodes);
611 return rc;
615 * rc == 0 connected
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)
625 int rc = 0;
626 struct control_msg_out *cm;
627 struct neighbor *nb = find_neigh(addrtypelen, addrtype, addrlen, addr);
628 if (nb == 0)
629 return 3;
630 if (unlikely(conn_init_out(rconn, nb))) {
631 rc = 4;
632 goto neigh_kref;
635 cm = alloc_control_msg();
636 if (unlikely(cm == 0)) {
637 rc = 5;
638 goto neigh_kref;
641 send_connect_nb(cm, nb, rconn->reversedir->source.in.conn_id);
643 neigh_kref:
644 kref_put(&(nb->ref), neighbor_free);
646 return rc;
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
655 int krefput = 1;
656 int isreset = atomic_cmpxchg(&(conn->isreset), 0, 2);
657 if (isreset == 1)
658 isreset = atomic_cmpxchg(&(conn->isreset), 1, 2);
660 if (isreset == 2 || isreset == 3)
661 return 0;
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));
671 krefput++;
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));
690 krefput++;
692 if (isreset == 0 && conn->target.out.conn_id != 0) {
693 struct control_msg_out *cm = alloc_control_msg();
694 if (likely(cm != 0))
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));
708 return krefput;
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 */
718 while (put1 > 0) {
719 kref_put(&(conn->ref), free_conn);
720 put1--;
723 while (put2 > 0) {
724 kref_put(&(conn->reversedir->ref), free_conn);
725 put2--;
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)
739 int rc;
741 struct conn c;
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);
764 forward_init();
766 cor_kgen_init();
768 rc = cor_snd_init();
769 if (unlikely(rc != 0))
770 return rc;
772 rc = cor_neighbor_init();
773 if (unlikely(rc != 0))
774 return rc;
776 rc = cor_rcv_init();
777 if (unlikely(rc != 0))
778 return rc;
780 return 0;
783 module_init(cor_common_init);
784 MODULE_LICENSE("GPL");