?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
do not preallocate cor_connid_reuse_item
[cor.git] / net / cor / neigh.c
blob52b62d62e5de0becb31d8caa12318849829f57ce
1 /**
2 * Connection oriented routing
3 * Copyright (C) 2007-2021 Michael Blizek
4 *
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.
9 *
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.
14 *
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.
19 */
20
21 #include <linux/delay.h>
22 #include "cor.h"
23
24
25 static DEFINE_SPINLOCK(cor_neighbor_list_lock);
26 static LIST_HEAD(cor_nb_list);
27 static struct kmem_cache *cor_nb_slab;
28 atomic_t cor_num_neighs;
29
30 static DEFINE_SPINLOCK(cor_connid_gen);
31
32
33 void cor_neighbor_free(struct kref *ref)
34 {
35 struct cor_neighbor *nb = container_of(ref, struct cor_neighbor, ref);
36
37 WARN_ONCE(list_empty(&(nb->cmsg_queue_pong)) == 0,
38 "cor_neighbor_free(): nb->cmsg_queue_pong is not empty");
39 WARN_ONCE(list_empty(&(nb->cmsg_queue_ack_fast)) == 0,
40 "cor_neighbor_free(): nb->cmsg_queue_ack_fast is not empty");
41 WARN_ONCE(list_empty(&(nb->cmsg_queue_ack_slow)) == 0,
42 "cor_neighbor_free(): nb->cmsg_queue_ack_slow is not empty");
43 WARN_ONCE(list_empty(&(nb->cmsg_queue_ackconn_urgent)) == 0,
44 "cor_neighbor_free(): nb->cmsg_queue_ackconn_urgent is not empty");
45 WARN_ONCE(list_empty(&(nb->cmsg_queue_ackconn_lowlat)) == 0,
46 "cor_neighbor_free(): nb->cmsg_queue_ackconn_lowlat is not empty");
47 WARN_ONCE(list_empty(&(nb->cmsg_queue_ackconn_highlat)) == 0,
48 "cor_neighbor_free(): nb->cmsg_queue_ackconn_highlat is not empty");
49 WARN_ONCE(list_empty(&(nb->cmsg_queue_conndata_lowlat)) == 0,
50 "cor_neighbor_free(): nb->cmsg_queue_conndata_lowlat is not empty");
51 WARN_ONCE(list_empty(&(nb->cmsg_queue_conndata_highlat)) == 0,
52 "cor_neighbor_free(): nb->cmsg_queue_conndata_highlat is not empty");
53 WARN_ONCE(list_empty(&(nb->cmsg_queue_other)) == 0,
54 "cor_neighbor_free(): nb->cmsg_queue_other is not empty");
55 WARN_ONCE(nb->pending_conn_resets_rb.rb_node != 0,
56 "cor_neighbor_free(): nb->pending_conn_resets_rb is not empty");
57 WARN_ONCE(nb->rb_kp.in_queue != RB_INQUEUE_FALSE,
58 "cor_neighbor_free(): nb->rb_kp.in_queue is not RB_INQUEUE_FALSE");
59 WARN_ONCE(nb->rb_cr.in_queue != RB_INQUEUE_FALSE,
60 "cor_neighbor_free(): nb->rb_cr.in_queue is not RB_INQUEUE_FALSE");
61 WARN_ONCE(nb->rb.in_queue != RB_INQUEUE_FALSE,
62 "cor_neighbor_free(): nb->rb.in_queue is not RB_INQUEUE_FALSE");
63 WARN_ONCE(list_empty(&(nb->conns_waiting.lh)) == 0,
64 "cor_neighbor_free(): nb->conns_waiting.lh is not empty");
65 WARN_ONCE(list_empty(&(nb->conns_waiting.lh_nextpass)) == 0,
66 "cor_neighbor_free(): nb->conns_waiting.lh_nextpass is not empty");
67 WARN_ONCE(nb->str_timer_pending != 0,
68 "cor_neighbor_free(): nb->str_timer_pending is not 0");
69 WARN_ONCE(nb->connid_rb.rb_node != 0,
70 "cor _neighbor_free(): nb->connid_rb is not empty");
71 WARN_ONCE(nb->connid_reuse_rb.rb_node != 0,
72 "cor_neighbor_free(): nb->connid_reuse_rb is not empty");
73 WARN_ONCE(list_empty(&(nb->connid_reuse_list)) == 0,
74 "cor_neighbor_free(): nb->connid_reuse_list is not empty");
75 WARN_ONCE(nb->kp_retransmits_rb.rb_node != 0,
76 "cor_neighbor_free(): nb->kp_retransmits_rb is not empty");
77 WARN_ONCE(list_empty(&(nb->snd_conn_idle_list)) == 0,
78 "cor_neighbor_free(): nb->snd_conn_idle_list is not empty");
79 WARN_ONCE(list_empty(&(nb->snd_conn_busy_list)) == 0,
80 "cor_neighbor_free(): nb->snd_conn_busy_list is not empty");
81 WARN_ONCE(list_empty(&(nb->retrans_fast_list)) == 0,
82 "cor_neighbor_free(): nb->retrans_fast_list is not empty");
83 WARN_ONCE(list_empty(&(nb->retrans_slow_list)) == 0,
84 "cor_neighbor_free(): nb->retrans_slow_list is not empty");
85 WARN_ONCE(list_empty(&(nb->retrans_conn_lowlatency_list)) == 0,
86 "cor_neighbor_free(): nb->retrans_conn_lowlatency_list is not empty");
87 WARN_ONCE(list_empty(&(nb->retrans_conn_highlatency_list)) == 0,
88 "cor_neighbor_free(): nb->retrans_conn_highlatency_list is not empty");
89
90 /* printk(KERN_ERR "neighbor free\n"); */
91 BUG_ON(nb->nb_list.next != LIST_POISON1);
92 BUG_ON(nb->nb_list.prev != LIST_POISON2);
93 if (nb->addr != 0)
94 kfree(nb->addr);
95 nb->addr = 0;
96 if (nb->dev != 0)
97 dev_put(nb->dev);
98 nb->dev = 0;
99 if (nb->queue != 0)
100 kref_put(&(nb->queue->ref), cor_free_qos);
101 nb->queue = 0;
102 kmem_cache_free(cor_nb_slab, nb);
103 atomic_dec(&cor_num_neighs);
104 }
105
106 static void cor_stall_timer(struct work_struct *work);
107
108 static void _cor_reset_neighbor(struct work_struct *work);
109
110 static struct cor_neighbor *cor_alloc_neighbor(gfp_t allocflags)
111 {
112 struct cor_neighbor *nb;
113 __u64 seqno;
114
115 if (atomic_inc_return(&cor_num_neighs) >= MAX_NEIGHBORS) {
116 atomic_dec(&cor_num_neighs);
117 return 0;
118 }
119
120 nb = kmem_cache_alloc(cor_nb_slab, allocflags);
121 if (unlikely(nb == 0))
122 return 0;
123
124 memset(nb, 0, sizeof(struct cor_neighbor));
125
126 kref_init(&(nb->ref));
127 atomic_set(&(nb->sessionid_rcv_needed), 1);
128 atomic_set(&(nb->sessionid_snd_needed), 1);
129 timer_setup(&(nb->cmsg_timer), cor_controlmsg_timerfunc, 0);
130 spin_lock_init(&(nb->cmsg_lock));
131 INIT_LIST_HEAD(&(nb->cmsg_queue_pong));
132 INIT_LIST_HEAD(&(nb->cmsg_queue_ack_fast));
133 INIT_LIST_HEAD(&(nb->cmsg_queue_ack_slow));
134 INIT_LIST_HEAD(&(nb->cmsg_queue_ackconn_urgent));
135 INIT_LIST_HEAD(&(nb->cmsg_queue_ackconn_lowlat));
136 INIT_LIST_HEAD(&(nb->cmsg_queue_ackconn_highlat));
137 INIT_LIST_HEAD(&(nb->cmsg_queue_conndata_lowlat));
138 INIT_LIST_HEAD(&(nb->cmsg_queue_conndata_highlat));
139 INIT_LIST_HEAD(&(nb->cmsg_queue_other));
140 atomic_set(&(nb->cmsg_pongs_retrans_cnt), 0);
141 atomic_set(&(nb->cmsg_othercnt), 0);
142 atomic_set(&(nb->cmsg_bulk_readds), 0);
143 atomic_set(&(nb->cmsg_delay_conndata), 0);
144 atomic_set(&(nb->rcvmtu_sendneeded), 1);
145 nb->last_ping_time = jiffies;
146 atomic_set(&(nb->latency_retrans_us), PING_GUESSLATENCY_MS*1000);
147 atomic_set(&(nb->latency_advertised_us), PING_GUESSLATENCY_MS*1000);
148 atomic_set(&(nb->max_remote_ack_fast_delay_us), 1000000);
149 atomic_set(&(nb->max_remote_ack_slow_delay_us), 1000000);
150 atomic_set(&(nb->max_remote_ackconn_lowlat_delay_us), 1000000);
151 atomic_set(&(nb->max_remote_ackconn_highlat_delay_us), 1000000);
152 atomic_set(&(nb->max_remote_pong_delay_us), 1000000);
153 atomic_set(&(nb->remote_rcvmtu), 128);
154 spin_lock_init(&(nb->conns_waiting.lock));
155 INIT_LIST_HEAD(&(nb->conns_waiting.lh));
156 INIT_LIST_HEAD(&(nb->conns_waiting.lh_nextpass));
157 spin_lock_init(&(nb->nbcongwin.lock));
158 atomic64_set(&(nb->nbcongwin.data_intransit), 0);
159 atomic64_set(&(nb->nbcongwin.cwin), 0);
160 spin_lock_init(&(nb->state_lock));
161 nb->state = NEIGHBOR_STATE_INITIAL;
162 nb->state_time.initial_state_since = jiffies;
163 INIT_DELAYED_WORK(&(nb->stalltimeout_timer), cor_stall_timer);
164 spin_lock_init(&(nb->connid_lock));
165 spin_lock_init(&(nb->connid_reuse_lock));
166 INIT_LIST_HEAD(&(nb->connid_reuse_list));
167 get_random_bytes((char *) &seqno, sizeof(seqno));
168 nb->kpacket_seqno = seqno;
169 atomic64_set(&(nb->priority_sum), 0);
170 spin_lock_init(&(nb->conn_list_lock));
171 INIT_LIST_HEAD(&(nb->snd_conn_idle_list));
172 INIT_LIST_HEAD(&(nb->snd_conn_busy_list));
173 spin_lock_init(&(nb->retrans_lock));
174 INIT_LIST_HEAD(&(nb->retrans_fast_list));
175 INIT_LIST_HEAD(&(nb->retrans_slow_list));
176 spin_lock_init(&(nb->retrans_conn_lock));
177 INIT_LIST_HEAD(&(nb->retrans_conn_lowlatency_list));
178 INIT_LIST_HEAD(&(nb->retrans_conn_highlatency_list));
179 INIT_WORK(&(nb->reset_neigh_work), _cor_reset_neighbor);
180
181 return nb;
182 }
183
184 int cor_is_from_nb(struct sk_buff *skb, struct cor_neighbor *nb)
185 {
186 int rc;
187
188 char source_hw[MAX_ADDR_LEN];
189 memset(source_hw, 0, MAX_ADDR_LEN);
190 if (skb->dev->header_ops != 0 &&
191 skb->dev->header_ops->parse != 0)
192 skb->dev->header_ops->parse(skb, source_hw);
193
194 rc = (skb->dev == nb->dev && memcmp(nb->mac, source_hw,
195 MAX_ADDR_LEN) == 0);
196 return rc;
197 }
198
199 struct cor_neighbor *_cor_get_neigh_by_mac(struct net_device *dev,
200 char *source_hw)
201 {
202 struct list_head *currlh;
203 struct cor_neighbor *ret = 0;
204
205 spin_lock_bh(&cor_neighbor_list_lock);
206
207 currlh = cor_nb_list.next;
208 while (currlh != &cor_nb_list) {
209 struct cor_neighbor *curr = container_of(currlh,
210 struct cor_neighbor, nb_list);
211
212 BUG_ON(curr->in_nb_list == 0);
213
214 if (curr->dev == dev && memcmp(curr->mac, source_hw,
215 MAX_ADDR_LEN) == 0) {
216 ret = curr;
217 cor_nb_kref_get(ret, "stack");
218 break;
219 }
220
221 currlh = currlh->next;
222 }
223
224 spin_unlock_bh(&cor_neighbor_list_lock);
225
226 if (ret != 0 && unlikely(cor_get_neigh_state(ret) ==
227 NEIGHBOR_STATE_KILLED)) {
228 cor_nb_kref_put(ret, "stack");
229 return 0;
230 } else {
231 return ret;
232 }
233 }
234
235 struct cor_neighbor *cor_get_neigh_by_mac(struct sk_buff *skb)
236 {
237 char source_hw[MAX_ADDR_LEN];
238 memset(source_hw, 0, MAX_ADDR_LEN);
239 if (skb->dev->header_ops != 0 &&
240 skb->dev->header_ops->parse != 0)
241 skb->dev->header_ops->parse(skb, source_hw);
242
243 return _cor_get_neigh_by_mac(skb->dev, source_hw);
244 }
245
246 struct cor_neighbor *cor_find_neigh(char *addr, __u16 addrlen)
247 {
248 struct list_head *currlh;
249 struct cor_neighbor *ret = 0;
250
251 if (addr == 0 || addrlen == 0)
252 return 0;
253
254 spin_lock_bh(&cor_neighbor_list_lock);
255
256 currlh = cor_nb_list.next;
257 while (currlh != &cor_nb_list) {
258 struct cor_neighbor *curr = container_of(currlh,
259 struct cor_neighbor, nb_list);
260
261 BUG_ON(curr->in_nb_list == 0);
262
263 if (curr->addr != 0 && curr->addrlen != 0 &&
264 curr->addrlen == addrlen &&
265 memcmp(curr->addr, addr, addrlen) == 0) {
266 ret = curr;
267 cor_nb_kref_get(ret, "stack");
268
269 goto out;
270 }
271
272 currlh = currlh->next;
273 }
274
275 out:
276 spin_unlock_bh(&cor_neighbor_list_lock);
277
278 if (ret != 0 && unlikely(cor_get_neigh_state(ret) ==
279 NEIGHBOR_STATE_KILLED)) {
280 cor_nb_kref_put(ret, "stack");
281 return 0;
282 } else {
283 return ret;
284 }
285 }
286
287 void cor_resend_rcvmtu(struct net_device *dev)
288 {
289 struct list_head *currlh;
290
291 spin_lock_bh(&cor_neighbor_list_lock);
292
293 currlh = cor_nb_list.next;
294 while (currlh != &cor_nb_list) {
295 struct cor_neighbor *nb = container_of(currlh,
296 struct cor_neighbor, nb_list);
297
298 unsigned long iflags;
299
300 if (nb->dev != dev)
301 goto cont;
302
303 cor_send_rcvmtu(nb);
304
305 spin_lock_irqsave(&(nb->state_lock), iflags);
306
307 if (nb->rcvmtu_allowed_countdown != 0)
308 nb->rcvmtu_delayed_send_needed = 1;
309 nb->rcvmtu_allowed_countdown = 3;
310
311 spin_unlock_irqrestore(&(nb->state_lock), iflags);
312
313 cont:
314 currlh = currlh->next;
315 }
316
317 spin_unlock_bh(&cor_neighbor_list_lock);
318 }
319
320 __u32 cor_generate_neigh_list(char *buf, __u32 buflen)
321 {
322 struct list_head *currlh;
323
324 __u32 cnt = 0;
325
326 __u32 buf_offset = 4;
327
328 int rc;
329
330 /*
331 * The variable length header rowcount need to be generated after the
332 * data. This is done by reserving the maximum space they could take. If
333 * they end up being smaller, the data is moved so that there is no gap.
334 */
335
336 BUG_ON(buf == 0);
337 BUG_ON(buflen < buf_offset);
338
339 /* num_fields */
340 rc = cor_encode_len(buf + buf_offset, buflen - buf_offset, 2);
341 BUG_ON(rc <= 0);
342 buf_offset += rc;
343
344 /* addr field */
345 BUG_ON(buflen < buf_offset + 2);
346 cor_put_u16(buf + buf_offset, LIST_NEIGH_FIELD_ADDR);
347 buf_offset += 2;
348
349 rc = cor_encode_len(buf + buf_offset, buflen - buf_offset, 0);
350 BUG_ON(rc <= 0);
351 buf_offset += rc;
352
353 /* latency field */
354 BUG_ON(buflen < buf_offset + 2);
355 cor_put_u16(buf + buf_offset, LIST_NEIGH_FIELD_LATENCY);
356 buf_offset += 2;
357
358 rc = cor_encode_len(buf + buf_offset, buflen - buf_offset, 1);
359 BUG_ON(rc <= 0);
360 buf_offset += rc;
361
362 spin_lock_bh(&cor_neighbor_list_lock);
363
364 currlh = cor_nb_list.next;
365 while (currlh != &cor_nb_list) {
366 struct cor_neighbor *curr = container_of(currlh,
367 struct cor_neighbor, nb_list);
368 int state;
369
370 BUG_ON(curr->in_nb_list == 0);
371
372 state = cor_get_neigh_state(curr);
373
374 if (state != NEIGHBOR_STATE_ACTIVE)
375 goto cont;
376
377 BUG_ON((curr->addr == 0) != (curr->addrlen == 0));
378 if (curr->addr == 0 || curr->addrlen == 0)
379 goto cont;
380
381 if (unlikely(buflen < buf_offset + 4 + curr->addrlen + 1))
382 break;
383
384 /* fieldlen */
385 rc = cor_encode_len(buf + buf_offset, buflen - buf_offset,
386 curr->addrlen);
387 BUG_ON(rc <= 0);
388 buf_offset += rc;
389
390 BUG_ON(curr->addrlen > buflen - buf_offset);
391 memcpy(buf + buf_offset, curr->addr, curr->addrlen); /* addr */
392 buf_offset += curr->addrlen;
393
394 buf[buf_offset] = cor_enc_log_64_11(atomic_read(
395 &(curr->latency_advertised_us)));
396 buf_offset += 1;
397
398 BUG_ON(buf_offset > buflen);
399
400 cnt++;
401
402 cont:
403 currlh = currlh->next;
404 }
405
406 spin_unlock_bh(&cor_neighbor_list_lock);
407
408 rc = cor_encode_len(buf, 4, cnt);
409 BUG_ON(rc <= 0);
410 BUG_ON(rc > 4);
411
412 if (likely(rc < 4))
413 memmove(buf + ((__u32) rc), buf+4, buf_offset);
414
415 return buf_offset - 4 + ((__u32) rc);
416 }
417
418 static void cor_reset_all_conns(struct cor_neighbor *nb)
419 {
420 while (1) {
421 unsigned long iflags;
422 struct cor_conn *trgt_out;
423 struct cor_conn *src_in;
424 struct cor_conn_bidir *cnb;
425 int rc;
426
427 spin_lock_irqsave(&(nb->conn_list_lock), iflags);
428
429 if (!list_empty(&(nb->snd_conn_busy_list))) {
430 trgt_out = container_of(nb->snd_conn_busy_list.next,
431 struct cor_conn, trgt.out.nb_list);
432 } else if (!list_empty(&(nb->snd_conn_idle_list))) {
433 trgt_out = container_of(nb->snd_conn_idle_list.next,
434 struct cor_conn, trgt.out.nb_list);
435 } else {
436 spin_unlock_irqrestore(&(nb->conn_list_lock), iflags);
437 break;
438 }
439
440 cor_conn_kref_get(trgt_out, "stack");
441
442 spin_unlock_irqrestore(&(nb->conn_list_lock), iflags);
443
444 src_in = cor_get_conn_reversedir(trgt_out);
445 cnb = cor_get_conn_bidir(trgt_out);
446
447 spin_lock_bh(&(cnb->cli.rcv_lock));
448 spin_lock_bh(&(cnb->srv.rcv_lock));
449
450 if (unlikely(unlikely(src_in->sourcetype != SOURCE_IN) ||
451 unlikely(src_in->src.in.nb != nb))) {
452 rc = 1;
453 goto unlock;
454 }
455
456 rc = cor_send_reset_conn(nb, trgt_out->trgt.out.conn_id, 1);
457
458 if (unlikely(rc != 0))
459 goto unlock;
460
461 if (trgt_out->isreset == 0)
462 trgt_out->isreset = 1;
463
464 unlock:
465 spin_unlock_bh(&(cnb->srv.rcv_lock));
466 spin_unlock_bh(&(cnb->cli.rcv_lock));
467
468 if (rc == 0) {
469 cor_reset_conn(src_in);
470 cor_conn_kref_put(src_in, "stack");
471 } else {
472 cor_conn_kref_put(src_in, "stack");
473 cor_nb_kref_get(nb, "stalltimeout_timer");
474 schedule_delayed_work(&(nb->stalltimeout_timer), HZ);
475 break;
476 }
477 }
478 }
479
480 static void cor_delete_connid_reuse_items(struct cor_neighbor *nb);
481
482 static void _cor_reset_neighbor(struct work_struct *work)
483 {
484 struct cor_neighbor *nb = container_of(work, struct cor_neighbor,
485 reset_neigh_work);
486
487 cor_reset_all_conns(nb);
488 cor_delete_connid_reuse_items(nb);
489
490 spin_lock_bh(&cor_neighbor_list_lock);
491 if (nb->in_nb_list != 0) {
492 list_del(&(nb->nb_list));
493 nb->in_nb_list = 0;
494 cor_nb_kref_put_bug(nb, "neigh_list");
495 }
496 spin_unlock_bh(&cor_neighbor_list_lock);
497
498 cor_nb_kref_put(nb, "reset_neigh_work");
499 }
500
501 static void cor_reset_neighbor(struct cor_neighbor *nb, int use_workqueue)
502 {
503 unsigned long iflags;
504
505 spin_lock_irqsave(&(nb->state_lock), iflags);
506 /* if (nb->state != NEIGHBOR_STATE_KILLED) {
507 printk(KERN_ERR "cor_reset_neighbor\n");
508 show_stack(0, 0);
509 } */
510 nb->state = NEIGHBOR_STATE_KILLED;
511 spin_unlock_irqrestore(&(nb->state_lock), iflags);
512
513
514 if (use_workqueue) {
515 schedule_work(&(nb->reset_neigh_work));
516 cor_nb_kref_get(nb, "reset_neigh_work");
517 } else {
518 int krefput = 0;
519 cor_reset_all_conns(nb);
520 cor_delete_connid_reuse_items(nb);
521
522 spin_lock_bh(&cor_neighbor_list_lock);
523 if (nb->in_nb_list != 0) {
524 list_del(&(nb->nb_list));
525 nb->in_nb_list = 0;
526 krefput = 1;
527 }
528 spin_unlock_bh(&cor_neighbor_list_lock);
529
530 if (krefput)
531 cor_nb_kref_put(nb, "neigh_list");
532 }
533 }
534
535 void cor_reset_neighbors(struct net_device *dev)
536 {
537 struct list_head *currlh;
538
539 restart:
540 spin_lock_bh(&cor_neighbor_list_lock);
541
542 currlh = cor_nb_list.next;
543 while (currlh != &cor_nb_list) {
544 unsigned long iflags;
545 struct cor_neighbor *currnb = container_of(currlh,
546 struct cor_neighbor, nb_list);
547 __u8 state;
548
549 BUG_ON(currnb->in_nb_list == 0);
550
551 if (dev != 0 && currnb->dev != dev)
552 goto cont;
553
554 spin_lock_irqsave(&(currnb->state_lock), iflags);
555 state = currnb->state;
556 spin_unlock_irqrestore(&(currnb->state_lock), iflags);
557
558 if (state != NEIGHBOR_STATE_KILLED) {
559 spin_unlock_bh(&cor_neighbor_list_lock);
560 cor_reset_neighbor(currnb, 0);
561 goto restart;
562 }
563
564 cont:
565 currlh = currlh->next;
566 }
567
568 spin_unlock_bh(&cor_neighbor_list_lock);
569 }
570
571 static void cor_stall_timer(struct work_struct *work)
572 {
573 struct cor_neighbor *nb = container_of(to_delayed_work(work),
574 struct cor_neighbor, stalltimeout_timer);
575
576 int stall_time_ms;
577 __u8 nbstate;
578
579 unsigned long iflags;
580
581 spin_lock_irqsave(&(nb->state_lock), iflags);
582 nbstate = nb->state;
583 spin_unlock_irqrestore(&(nb->state_lock), iflags);
584
585 if (nbstate == NEIGHBOR_STATE_STALLED) {
586 stall_time_ms = jiffies_to_msecs(jiffies -
587 nb->state_time.last_roundtrip);
588
589 if (stall_time_ms < NB_KILL_TIME_MS) {
590 schedule_delayed_work(&(nb->stalltimeout_timer),
591 msecs_to_jiffies(NB_KILL_TIME_MS -
592 stall_time_ms));
593 return;
594 }
595
596 cor_reset_neighbor(nb, 1);
597 }
598
599 nb->str_timer_pending = 0;
600 cor_nb_kref_put(nb, "stalltimeout_timer");
601 }
602
603 int cor_get_neigh_state(struct cor_neighbor *nb)
604 {
605 int ret;
606 unsigned long iflags;
607 int stall_time_ms;
608
609 BUG_ON(nb == 0);
610
611 spin_lock_irqsave(&(nb->state_lock), iflags);
612
613 stall_time_ms = jiffies_to_msecs(jiffies -
614 nb->state_time.last_roundtrip);
615
616 WARN_ONCE(likely(nb->state == NEIGHBOR_STATE_ACTIVE) && unlikely(
617 jiffies_to_msecs(jiffies - nb->last_ping_time) >
618 PING_FORCETIME_ACTIVEIDLE_MS * 4) &&
619 nb->ping_intransit == 0,
620 "We have stopped sending pings to a neighbor!?");
621
622 if (likely(nb->state == NEIGHBOR_STATE_ACTIVE) &&
623 unlikely(stall_time_ms > NB_STALL_TIME_MS) && (
624 nb->ping_intransit >= NB_STALL_MINPINGS ||
625 nb->ping_intransit >= PING_COOKIES_PER_NEIGH)) {
626 nb->state = NEIGHBOR_STATE_STALLED;
627 nb->ping_success = 0;
628 if (nb->str_timer_pending == 0) {
629 nb->str_timer_pending = 1;
630 cor_nb_kref_get(nb, "stalltimeout_timer");
631
632 schedule_delayed_work(&(nb->stalltimeout_timer),
633 msecs_to_jiffies(NB_KILL_TIME_MS -
634 stall_time_ms));
635 }
636
637 /* printk(KERN_ERR "changed to stalled\n"); */
638 BUG_ON(nb->ping_intransit > PING_COOKIES_PER_NEIGH);
639 } else if (unlikely(nb->state == NEIGHBOR_STATE_INITIAL) &&
640 time_after(jiffies, nb->state_time.initial_state_since +
641 INITIAL_TIME_LIMIT_SEC * HZ)) {
642 spin_unlock_irqrestore(&(nb->state_lock), iflags);
643 cor_reset_neighbor(nb, 1);
644 return NEIGHBOR_STATE_KILLED;
645 }
646
647 ret = nb->state;
648
649 spin_unlock_irqrestore(&(nb->state_lock), iflags);
650
651 return ret;
652 }
653
654 static struct cor_ping_cookie *cor_find_cookie(struct cor_neighbor *nb,
655 __u32 cookie)
656 {
657 int i;
658
659 for(i=0;i<PING_COOKIES_PER_NEIGH;i++) {
660 if (nb->cookies[i].cookie == cookie)
661 return &(nb->cookies[i]);
662 }
663 return 0;
664 }
665
666 static void cor_reset_cookie(struct cor_neighbor *nb, struct cor_ping_cookie *c)
667 {
668 if (c->cookie == 0)
669 return;
670
671 if (nb->cookie_unsent != c->cookie)
672 nb->ping_intransit--;
673
674 c->cookie = 0;
675 }
676
677 static __u32 sqrt(__u64 x)
678 {
679 int i;
680 __u64 y = 65536;
681
682 if (unlikely(x <= 1))
683 return 0;
684
685 for (i=0;i<20;i++) {
686 y = y/2 + div64_u64(x/2, y);
687 if (unlikely(y == 0))
688 y = 1;
689 }
690
691 if (unlikely(y > U32_MAX))
692 y = U32_MAX;
693
694 return (__u32) y;
695 }
696
697 static __u32 cor_calc_newlatency(struct cor_neighbor *nb_statelocked,
698 __u32 oldlatency_us, __s64 newlatency_ns)
699 {
700 __s64 oldlatency = oldlatency_us * 1000LL;
701 __s64 newlatency;
702
703 if (unlikely(unlikely(nb_statelocked->state == NEIGHBOR_STATE_INITIAL)&&
704 nb_statelocked->ping_success < 16))
705 newlatency = div64_s64(
706 oldlatency * nb_statelocked->ping_success +
707 newlatency_ns,
708 nb_statelocked->ping_success + 1);
709 else
710 newlatency = (oldlatency * 15 + newlatency_ns) / 16;
711
712 newlatency = div_s64(newlatency + 500, 1000);
713
714 if (unlikely(newlatency < 0))
715 newlatency = 0;
716 if (unlikely(newlatency > U32_MAX))
717 newlatency = U32_MAX;
718
719 return (__u32) newlatency;
720 }
721
722 static void cor_update_nb_latency(struct cor_neighbor *nb_statelocked,
723 struct cor_ping_cookie *c, __u32 respdelay)
724 {
725 ktime_t now = ktime_get();
726
727 __s64 pinglatency_retrans_ns = ktime_to_ns(now) -
728 ktime_to_ns(c->time_sent) - respdelay * 1000LL;
729 __s64 pinglatency_advertised_ns = ktime_to_ns(now) -
730 ktime_to_ns(c->time_created) - respdelay * 1000LL;
731
732 __u32 oldlatency_retrans_us =
733 atomic_read(&(nb_statelocked->latency_retrans_us));
734
735 __u32 newlatency_retrans_us = cor_calc_newlatency(nb_statelocked,
736 oldlatency_retrans_us, pinglatency_retrans_ns);
737
738 atomic_set(&(nb_statelocked->latency_retrans_us),
739 newlatency_retrans_us);
740
741 if (unlikely(unlikely(nb_statelocked->state == NEIGHBOR_STATE_INITIAL)&&
742 nb_statelocked->ping_success < 16)) {
743 nb_statelocked->latency_variance_retrans_us =
744 ((__u64) newlatency_retrans_us) *
745 newlatency_retrans_us;
746 atomic_set(&(nb_statelocked->latency_stddev_retrans_us), sqrt(
747 nb_statelocked->latency_variance_retrans_us));
748 } else if (pinglatency_retrans_ns > oldlatency_retrans_us *
749 ((__s64) 1000)) {
750 __s64 newdiff = div_s64(pinglatency_retrans_ns -
751 oldlatency_retrans_us * ((__s64) 1000), 1000);
752 __u32 newdiff32 = (__u32) (unlikely(newdiff >= U32_MAX) ?
753 U32_MAX : newdiff);
754 __u64 newvar = ((__u64) newdiff32) * newdiff32;
755
756 __u64 oldval = nb_statelocked->latency_variance_retrans_us;
757
758 if (unlikely(unlikely(newvar > (1LL << 55)) || unlikely(
759 oldval > (1LL << 55)))) {
760 nb_statelocked->latency_variance_retrans_us =
761 (oldval / 16) * 15 + newvar/16;
762 } else {
763 nb_statelocked->latency_variance_retrans_us =
764 (oldval * 15 + newvar) / 16;
765 }
766
767 atomic_set(&(nb_statelocked->latency_stddev_retrans_us), sqrt(
768 nb_statelocked->latency_variance_retrans_us));
769 }
770
771 atomic_set(&(nb_statelocked->latency_advertised_us),
772 cor_calc_newlatency(nb_statelocked,
773 atomic_read(&(nb_statelocked->latency_advertised_us)),
774 pinglatency_advertised_ns));
775
776 nb_statelocked->last_roundtrip_end = now;
777 }
778
779 static void cor_connid_used_pingsuccess(struct cor_neighbor *nb);
780
781 void cor_ping_resp(struct cor_neighbor *nb, __u32 cookie, __u32 respdelay)
782 {
783 unsigned long iflags;
784
785 struct cor_ping_cookie *c;
786 int i;
787 int stalledresume = 0;
788
789 int call_connidreuse = 0;
790 int call_send_rcvmtu = 0;
791
792 if (unlikely(cookie == 0))
793 return;
794
795 spin_lock_irqsave(&(nb->state_lock), iflags);
796
797 c = cor_find_cookie(nb, cookie);
798
799 if (unlikely(c == 0))
800 goto out;
801
802 atomic_set(&(nb->sessionid_snd_needed), 0);
803
804 call_connidreuse = ktime_before_eq(nb->last_roundtrip_end,
805 c->time_created);
806
807 cor_update_nb_latency(nb, c, respdelay);
808
809 nb->ping_success++;
810
811 cor_reset_cookie(nb, c);
812
813 for(i=0;i<PING_COOKIES_PER_NEIGH;i++) {
814 if (nb->cookies[i].cookie != 0 && ktime_before(
815 nb->cookies[i].time_created, c->time_created)) {
816 nb->cookies[i].pongs++;
817 if (nb->cookies[i].pongs >= PING_PONGLIMIT) {
818 cor_reset_cookie(nb, &(nb->cookies[i]));
819 }
820 }
821 }
822
823 if (unlikely(nb->state == NEIGHBOR_STATE_INITIAL ||
824 nb->state == NEIGHBOR_STATE_STALLED)) {
825 call_connidreuse = 0;
826
827 if ((nb->state == NEIGHBOR_STATE_INITIAL &&
828 nb->ping_success >= PING_SUCCESS_CNT_INIT) || (
829 nb->state == NEIGHBOR_STATE_STALLED &&
830 nb->ping_success >= PING_SUCCESS_CNT_STALLED)) {
831 stalledresume = (nb->state == NEIGHBOR_STATE_STALLED);
832 nb->state = NEIGHBOR_STATE_ACTIVE;
833 /* printk(KERN_ERR "changed to active\n"); */
834 }
835 }
836
837 if (likely(nb->state == NEIGHBOR_STATE_ACTIVE) ||
838 nb->state == NEIGHBOR_STATE_STALLED)
839 nb->state_time.last_roundtrip = c->jiffies_sent;
840
841 if (c == &(nb->cookies[0]) &&
842 unlikely(nb->rcvmtu_allowed_countdown != 0)) {
843 nb->rcvmtu_allowed_countdown--;
844
845 if (unlikely(nb->rcvmtu_allowed_countdown == 0 &&
846 nb->rcvmtu_delayed_send_needed != 0)) {
847 nb->rcvmtu_allowed_countdown = 3;
848 nb->rcvmtu_delayed_send_needed = 0;
849 call_send_rcvmtu = 1;
850 }
851 }
852
853 out:
854 spin_unlock_irqrestore(&(nb->state_lock), iflags);
855
856 if (call_connidreuse)
857 cor_connid_used_pingsuccess(nb);
858
859 if (unlikely(call_send_rcvmtu))
860 cor_send_rcvmtu(nb);
861
862 if (unlikely(stalledresume)) {
863 spin_lock_bh(&(nb->retrans_conn_lock));
864 cor_reschedule_conn_retrans_timer(nb);
865 spin_unlock_bh(&(nb->retrans_conn_lock));
866
867 cor_qos_enqueue(nb->queue, &(nb->rb), 0, ns_to_ktime(0),
868 QOS_CALLER_NEIGHBOR, 1);
869 }
870 }
871
872 __u32 cor_add_ping_req(struct cor_neighbor *nb, unsigned long *last_ping_time)
873 {
874 unsigned long iflags;
875 struct cor_ping_cookie *c;
876 __u32 i;
877
878 __u32 cookie;
879
880 ktime_t now = ktime_get();
881
882 spin_lock_irqsave(&(nb->state_lock), iflags);
883
884 if (nb->cookie_unsent != 0) {
885 c = cor_find_cookie(nb, nb->cookie_unsent);
886 if (c != 0)
887 goto unsent;
888 c = 0;
889 nb->cookie_unsent = 0;
890 }
891
892 c = cor_find_cookie(nb, 0);
893 if (c != 0)
894 goto found;
895
896 get_random_bytes((char *) &i, sizeof(i));
897 i = (i % PING_COOKIES_PER_NEIGH);
898 c = &(nb->cookies[i]);
899 cor_reset_cookie(nb, c);
900
901 found:
902 nb->lastcookie++;
903 if (unlikely(nb->lastcookie == 0))
904 nb->lastcookie++;
905 c->cookie = nb->lastcookie;
906 c->time_created = now;
907
908 unsent:
909 c->pongs = 0;
910 c->time_sent = now;
911 c->jiffies_sent = jiffies;
912 cookie = c->cookie;
913
914 nb->ping_intransit++;
915
916 *last_ping_time = nb->last_ping_time;
917 nb->last_ping_time = c->jiffies_sent;
918
919 spin_unlock_irqrestore(&(nb->state_lock), iflags);
920
921 BUG_ON(cookie == 0);
922
923 return cookie;
924 }
925
926 void cor_ping_sent(struct cor_neighbor *nb, __u32 cookie)
927 {
928 unsigned long iflags;
929
930 BUG_ON(cookie == 0);
931
932 spin_lock_irqsave(&(nb->state_lock), iflags);
933
934 if (nb->cookie_unsent == cookie)
935 nb->cookie_unsent = 0;
936
937 spin_unlock_irqrestore(&(nb->state_lock), iflags);
938 }
939
940 void cor_unadd_ping_req(struct cor_neighbor *nb, __u32 cookie,
941 unsigned long last_ping_time, int congested)
942 {
943 unsigned long iflags;
944
945 struct cor_ping_cookie *c;
946
947 BUG_ON(cookie == 0);
948
949 spin_lock_irqsave(&(nb->state_lock), iflags);
950
951 if (congested) {
952 BUG_ON(nb->cookie_unsent != 0 && nb->cookie_unsent != cookie);
953 nb->cookie_unsent = cookie;
954 }
955
956 c = cor_find_cookie(nb, cookie);
957 if (likely(c != 0)) {
958 if (congested == 0)
959 c->cookie = 0;
960 nb->ping_intransit--;
961 }
962
963 nb->last_ping_time = last_ping_time;
964
965 spin_unlock_irqrestore(&(nb->state_lock), iflags);
966 }
967
968 static int cor_get_ping_forcetime_ms(struct cor_neighbor *nb)
969 {
970 unsigned long iflags;
971 int fast;
972 int idle;
973
974 if (unlikely(cor_get_neigh_state(nb) != NEIGHBOR_STATE_ACTIVE))
975 return PING_FORCETIME_MS;
976
977 spin_lock_irqsave(&(nb->state_lock), iflags);
978 fast = ((nb->ping_success < PING_ACTIVE_FASTINITIAL_COUNT) ||
979 (nb->ping_intransit > 0));
980 if (unlikely(nb->rcvmtu_delayed_send_needed != 0)) {
981 BUG_ON(nb->rcvmtu_allowed_countdown == 0);
982 fast = 1;
983 }
984 spin_unlock_irqrestore(&(nb->state_lock), iflags);
985
986 if (fast)
987 return PING_FORCETIME_ACTIVE_FAST_MS;
988
989 spin_lock_irqsave(&(nb->conn_list_lock), iflags);
990 idle = list_empty(&(nb->snd_conn_idle_list)) &&
991 list_empty(&(nb->snd_conn_busy_list));
992 spin_unlock_irqrestore(&(nb->conn_list_lock), iflags);
993
994 if (idle)
995 return PING_FORCETIME_ACTIVEIDLE_MS;
996 else
997 return PING_FORCETIME_ACTIVE_MS;
998 }
999
1000 static __u32 cor_get_ping_mindelay_ms(struct cor_neighbor *nb_statelocked)
1001 {
1002 __u32 latency_us = ((__u32) atomic_read(
1003 &(nb_statelocked->latency_advertised_us)));
1004 __u32 max_remote_pong_delay_us = ((__u32) atomic_read(
1005 &(nb_statelocked->max_remote_pong_delay_us)));
1006 __u32 mindelay_ms;
1007
1008 if (latency_us < PING_GUESSLATENCY_MS * 1000)
1009 latency_us = PING_GUESSLATENCY_MS * 1000;
1010
1011 if (unlikely(nb_statelocked->state != NEIGHBOR_STATE_ACTIVE))
1012 mindelay_ms = latency_us/1000;
1013 else
1014 mindelay_ms = ((latency_us/2 +
1015 max_remote_pong_delay_us/2)/500);
1016
1017 if (likely(nb_statelocked->ping_intransit < PING_COOKIES_THROTTLESTART))
1018 return mindelay_ms;
1019
1020 mindelay_ms = mindelay_ms * (1 + 9 * (nb_statelocked->ping_intransit *
1021 nb_statelocked->ping_intransit /
1022 (PING_COOKIES_PER_NEIGH * PING_COOKIES_PER_NEIGH)));
1023
1024 return mindelay_ms;
1025 }
1026
1027 /**
1028 * Check whether we want to send a ping now:
1029 * 0... Do not send ping.
1030 * 1... Send ping now, but only if it can be merged with other messages. This
1031 * can happen way before the time requested by cor_get_next_ping_time().
1032 * 2... Send ping now, even if a packet has to be created just for the ping
1033 * alone.
1034 */
1035 int cor_time_to_send_ping(struct cor_neighbor *nb)
1036 {
1037 unsigned long iflags;
1038 int rc = TIMETOSENDPING_YES;
1039
1040 __u32 ms_since_last_ping;
1041
1042 __u32 forcetime = cor_get_ping_forcetime_ms(nb);
1043 __u32 mindelay;
1044
1045 spin_lock_irqsave(&(nb->state_lock), iflags);
1046
1047 ms_since_last_ping = jiffies_to_msecs(jiffies - nb->last_ping_time);
1048
1049 mindelay = cor_get_ping_mindelay_ms(nb);
1050
1051 if (forcetime < (mindelay * 3))
1052 forcetime = mindelay * 3;
1053 else if (forcetime > (mindelay * 3))
1054 mindelay = forcetime/3;
1055
1056 if (ms_since_last_ping < mindelay || ms_since_last_ping < (forcetime/4))
1057 rc = TIMETOSENDPING_NO;
1058 else if (ms_since_last_ping >= forcetime)
1059 rc = TIMETOSENDPING_FORCE;
1060
1061 spin_unlock_irqrestore(&(nb->state_lock), iflags);
1062
1063 return rc;
1064 }
1065
1066 unsigned long cor_get_next_ping_time(struct cor_neighbor *nb)
1067 {
1068 unsigned long iflags;
1069
1070 __u32 forcetime = cor_get_ping_forcetime_ms(nb);
1071 __u32 mindelay;
1072
1073 spin_lock_irqsave(&(nb->state_lock), iflags);
1074 mindelay = cor_get_ping_mindelay_ms(nb);
1075 spin_unlock_irqrestore(&(nb->state_lock), iflags);
1076
1077 if (forcetime < (mindelay * 3))
1078 forcetime = mindelay * 3;
1079
1080 return nb->last_ping_time + msecs_to_jiffies(forcetime);
1081 }
1082
1083 void cor_add_neighbor(struct cor_neighbor_discdata *nb_dd)
1084 {
1085 struct cor_neighbor *nb;
1086 struct list_head *currlh;
1087
1088 nb = cor_alloc_neighbor(GFP_KERNEL);
1089 if (unlikely(nb == 0))
1090 return;
1091
1092 nb->queue = cor_get_queue(nb_dd->dev);
1093 if (nb->queue == 0) {
1094 kmem_cache_free(cor_nb_slab, nb);
1095 atomic_dec(&cor_num_neighs);
1096 return;
1097 }
1098
1099 dev_hold(nb_dd->dev);
1100 nb->dev = nb_dd->dev;
1101
1102 memcpy(nb->mac, nb_dd->mac, MAX_ADDR_LEN);
1103
1104 nb->addr = nb_dd->addr;
1105 nb->addrlen = nb_dd->addrlen;
1106
1107 nb_dd->nb_allocated = 1;
1108 nb_dd->addr = 0;
1109 nb_dd->addrlen = 0;
1110
1111 spin_lock_bh(&cor_neighbor_list_lock);
1112
1113 BUG_ON((nb->addr == 0) != (nb->addrlen == 0));
1114
1115 if (cor_is_clientmode() && (nb->addr == 0|| nb->addrlen == 0))
1116 goto already_present;
1117
1118 currlh = cor_nb_list.next;
1119 while (currlh != &cor_nb_list) {
1120 struct cor_neighbor *curr = container_of(currlh,
1121 struct cor_neighbor, nb_list);
1122
1123 BUG_ON((curr->addr == 0) != (curr->addrlen == 0));
1124
1125 if (curr->dev == nb->dev &&
1126 memcmp(curr->mac, nb->mac, MAX_ADDR_LEN) == 0)
1127 goto already_present;
1128
1129 if (curr->addr != 0 && curr->addrlen != 0 &&
1130 nb->addr != 0 && nb->addrlen != 0 &&
1131 curr->addrlen == nb->addrlen &&
1132 memcmp(curr->addr, nb->addr, curr->addrlen) ==0)
1133 goto already_present;
1134
1135 currlh = currlh->next;
1136 }
1137
1138 /* printk(KERN_ERR "add_neigh\n"); */
1139
1140 spin_lock_bh(&cor_local_addr_lock);
1141 nb->sessionid = cor_local_addr_sessionid ^ nb_dd->sessionid;
1142 spin_unlock_bh(&cor_local_addr_lock);
1143
1144 timer_setup(&(nb->retrans_timer), cor_retransmit_timerfunc, 0);
1145
1146 timer_setup(&(nb->retrans_conn_timer), cor_retransmit_conn_timerfunc, 0);
1147
1148 spin_lock_bh(&(nb->cmsg_lock));
1149 nb->last_ping_time = jiffies;
1150 cor_schedule_controlmsg_timer(nb);
1151 spin_unlock_bh(&(nb->cmsg_lock));
1152
1153 list_add_tail(&(nb->nb_list), &cor_nb_list);
1154 nb->in_nb_list = 1;
1155 cor_nb_kref_get(nb, "neigh_list");
1156 cor_nb_kref_put_bug(nb, "alloc");
1157
1158 if (0) {
1159 already_present:
1160 kmem_cache_free(cor_nb_slab, nb);
1161 atomic_dec(&cor_num_neighs);
1162 }
1163
1164 spin_unlock_bh(&cor_neighbor_list_lock);
1165 }
1166
1167 struct cor_conn *cor_get_conn(struct cor_neighbor *nb, __u32 conn_id)
1168 {
1169 unsigned long iflags;
1170
1171 struct rb_node * n = 0;
1172 struct cor_conn *ret = 0;
1173
1174 spin_lock_irqsave(&(nb->connid_lock), iflags);
1175
1176 n = nb->connid_rb.rb_node;
1177
1178 while (likely(n != 0) && ret == 0) {
1179 struct cor_conn *src_in_o = container_of(n, struct cor_conn,
1180 src.in.rbn);
1181
1182 BUG_ON(src_in_o->sourcetype != SOURCE_IN);
1183
1184 if (conn_id < src_in_o->src.in.conn_id)
1185 n = n->rb_left;
1186 else if (conn_id > src_in_o->src.in.conn_id)
1187 n = n->rb_right;
1188 else
1189 ret = src_in_o;
1190 }
1191
1192 if (ret != 0)
1193 cor_conn_kref_get(ret, "stack");
1194
1195 spin_unlock_irqrestore(&(nb->connid_lock), iflags);
1196
1197 return ret;
1198 }
1199
1200 int cor_insert_connid(struct cor_neighbor *nb, struct cor_conn *src_in_ll)
1201 {
1202 int rc = 0;
1203
1204 unsigned long iflags;
1205
1206 __u32 conn_id = src_in_ll->src.in.conn_id;
1207
1208 struct rb_root *root;
1209 struct rb_node **p;
1210 struct rb_node *parent = 0;
1211
1212 BUG_ON(src_in_ll->sourcetype != SOURCE_IN);
1213
1214 spin_lock_irqsave(&(nb->connid_lock), iflags);
1215
1216 root = &(nb->connid_rb);
1217 p = &(root->rb_node);
1218
1219 while ((*p) != 0) {
1220 struct cor_conn *src_in_o = container_of(*p, struct cor_conn,
1221 src.in.rbn);
1222
1223 BUG_ON(src_in_o->sourcetype != SOURCE_IN);
1224
1225 parent = *p;
1226 if (unlikely(conn_id == src_in_o->src.in.conn_id)) {
1227 goto duplicate;
1228 } else if (conn_id < src_in_o->src.in.conn_id) {
1229 p = &(*p)->rb_left;
1230 } else if (conn_id > src_in_o->src.in.conn_id) {
1231 p = &(*p)->rb_right;
1232 } else {
1233 BUG();
1234 }
1235 }
1236
1237 cor_conn_kref_get(src_in_ll, "connid table");
1238 rb_link_node(&(src_in_ll->src.in.rbn), parent, p);
1239 rb_insert_color(&(src_in_ll->src.in.rbn), root);
1240
1241 if (0) {
1242 duplicate:
1243 rc = 1;
1244 }
1245
1246 spin_unlock_irqrestore(&(nb->connid_lock), iflags);
1247
1248 return rc;
1249 }
1250
1251 static struct cor_connid_reuse_item *cor_get_connid_reuseitem(
1252 struct cor_neighbor *nb, __u32 conn_id)
1253 {
1254 unsigned long iflags;
1255
1256 struct rb_node *n = 0;
1257 struct cor_connid_reuse_item *ret = 0;
1258
1259 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1260
1261 n = nb->connid_reuse_rb.rb_node;
1262
1263 while (likely(n != 0) && ret == 0) {
1264 struct cor_connid_reuse_item *cir = container_of(n,
1265 struct cor_connid_reuse_item, rbn);
1266
1267 BUG_ON(cir->conn_id == 0);
1268
1269 if (conn_id < cir->conn_id)
1270 n = n->rb_left;
1271 else if (conn_id > cir->conn_id)
1272 n = n->rb_right;
1273 else
1274 ret = cir;
1275 }
1276
1277 if (ret != 0)
1278 kref_get(&(ret->ref));
1279
1280 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1281
1282 return ret;
1283 }
1284
1285 /* nb->connid_reuse_lock must be held by the caller */
1286 static void _cor_insert_connid_reuse_insertrb(struct cor_neighbor *nb,
1287 struct cor_connid_reuse_item *ins)
1288 {
1289 struct rb_root *root;
1290 struct rb_node **p;
1291 struct rb_node *parent = 0;
1292
1293 BUG_ON(ins->conn_id == 0);
1294
1295 root = &(nb->connid_reuse_rb);
1296 p = &(root->rb_node);
1297
1298 while ((*p) != 0) {
1299 struct cor_connid_reuse_item *curr = container_of(*p,
1300 struct cor_connid_reuse_item, rbn);
1301
1302 BUG_ON(curr->conn_id == 0);
1303
1304 parent = *p;
1305 if (unlikely(ins->conn_id == curr->conn_id)) {
1306 BUG();
1307 } else if (ins->conn_id < curr->conn_id) {
1308 p = &(*p)->rb_left;
1309 } else if (ins->conn_id > curr->conn_id) {
1310 p = &(*p)->rb_right;
1311 } else {
1312 BUG();
1313 }
1314 }
1315
1316 kref_get(&(ins->ref));
1317 rb_link_node(&(ins->rbn), parent, p);
1318 rb_insert_color(&(ins->rbn), root);
1319 }
1320
1321 void cor_insert_connid_reuse(struct cor_neighbor *nb, __u32 conn_id)
1322 {
1323 unsigned long iflags;
1324
1325 struct cor_connid_reuse_item *cir = kmem_cache_alloc(
1326 cor_connid_reuse_slab, GFP_ATOMIC);
1327
1328 if (unlikely(cir == 0)) {
1329 BUILD_BUG_ON(CONNID_REUSE_RTTS > 255);
1330
1331 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1332 nb->connid_reuse_oom_countdown = CONNID_REUSE_RTTS;
1333 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1334
1335 return;
1336 }
1337
1338 memset(cir, 0, sizeof(struct cor_connid_reuse_item));
1339
1340 kref_init(&(cir->ref));
1341 cir->conn_id = conn_id;
1342
1343 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1344
1345 cir->pingcnt = nb->connid_reuse_pingcnt;
1346
1347 _cor_insert_connid_reuse_insertrb(nb, cir);
1348 list_add_tail(&(cir->lh), &(nb->connid_reuse_list));
1349
1350 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1351 }
1352
1353 static void cor_free_connid_reuse(struct kref *ref)
1354 {
1355 struct cor_connid_reuse_item *cir = container_of(ref,
1356 struct cor_connid_reuse_item, ref);
1357
1358 kmem_cache_free(cor_connid_reuse_slab, cir);
1359 }
1360
1361 static void cor_delete_connid_reuse_items(struct cor_neighbor *nb)
1362 {
1363 unsigned long iflags;
1364 struct cor_connid_reuse_item *cri;
1365
1366 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1367
1368 while (list_empty(&(nb->connid_reuse_list)) == 0) {
1369 cri = container_of(nb->connid_reuse_list.next,
1370 struct cor_connid_reuse_item, lh);
1371
1372 rb_erase(&(cri->rbn), &(nb->connid_reuse_rb));
1373 kref_put(&(cri->ref), cor_kreffree_bug);
1374
1375 list_del(&(cri->lh));
1376 kref_put(&(cri->ref), cor_free_connid_reuse);
1377 }
1378
1379 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1380 }
1381
1382 static void cor_connid_used_pingsuccess(struct cor_neighbor *nb)
1383 {
1384 unsigned long iflags;
1385 struct cor_connid_reuse_item *cri;
1386
1387 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1388
1389 nb->connid_reuse_pingcnt++;
1390 while (list_empty(&(nb->connid_reuse_list)) == 0) {
1391 cri = container_of(nb->connid_reuse_list.next,
1392 struct cor_connid_reuse_item, lh);
1393 if ((cri->pingcnt + CONNID_REUSE_RTTS -
1394 nb->connid_reuse_pingcnt) < 32768)
1395 break;
1396
1397 rb_erase(&(cri->rbn), &(nb->connid_reuse_rb));
1398 kref_put(&(cri->ref), cor_kreffree_bug);
1399
1400 list_del(&(cri->lh));
1401 kref_put(&(cri->ref), cor_free_connid_reuse);
1402 }
1403
1404 if (unlikely(nb->connid_reuse_oom_countdown != 0))
1405 nb->connid_reuse_oom_countdown--;
1406
1407
1408 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1409 }
1410
1411 static int cor_connid_used(struct cor_neighbor *nb, __u32 conn_id)
1412 {
1413 struct cor_conn *cn;
1414 struct cor_connid_reuse_item *cir;
1415
1416 cn = cor_get_conn(nb, conn_id);
1417 if (unlikely(cn != 0)) {
1418 cor_conn_kref_put(cn, "stack");
1419 return 1;
1420 }
1421
1422 cir = cor_get_connid_reuseitem(nb, conn_id);
1423 if (unlikely(cir != 0)) {
1424 kref_put(&(cir->ref), cor_free_connid_reuse);
1425 return 1;
1426 }
1427
1428 return 0;
1429 }
1430
1431 int cor_connid_alloc(struct cor_neighbor *nb, struct cor_conn *src_in_ll)
1432 {
1433 unsigned long iflags;
1434 struct cor_conn *trgt_out_ll = cor_get_conn_reversedir(src_in_ll);
1435 __u32 conn_id;
1436 int i;
1437
1438 BUG_ON(src_in_ll->sourcetype != SOURCE_IN);
1439 BUG_ON(trgt_out_ll->targettype != TARGET_OUT);
1440
1441 spin_lock_irqsave(&cor_connid_gen, iflags);
1442 for (i=0;i<16;i++) {
1443 conn_id = 0;
1444 get_random_bytes((char *) &conn_id, sizeof(conn_id));
1445 conn_id = (conn_id & ~(1 << 31));
1446
1447 if (unlikely(conn_id == 0))
1448 continue;
1449
1450 if (unlikely(cor_connid_used(nb, conn_id)))
1451 continue;
1452
1453 goto found;
1454 }
1455 spin_unlock_irqrestore(&cor_connid_gen, iflags);
1456
1457 return 1;
1458
1459 found:
1460 spin_lock_irqsave(&(nb->connid_reuse_lock), iflags);
1461 if (unlikely(nb->connid_reuse_oom_countdown != 0)) {
1462 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1463 return 1;
1464 }
1465 spin_unlock_irqrestore(&(nb->connid_reuse_lock), iflags);
1466
1467
1468 src_in_ll->src.in.conn_id = conn_id;
1469 trgt_out_ll->trgt.out.conn_id = cor_get_connid_reverse(conn_id);
1470 if (unlikely(cor_insert_connid(nb, src_in_ll) != 0)) {
1471 BUG();
1472 }
1473 spin_unlock_irqrestore(&cor_connid_gen, iflags);
1474 return 0;
1475 }
1476
1477 int __init cor_neighbor_init(void)
1478 {
1479 cor_nb_slab = kmem_cache_create("cor_neighbor",
1480 sizeof(struct cor_neighbor), 8, 0, 0);
1481 if (unlikely(cor_nb_slab == 0))
1482 return -ENOMEM;
1483
1484 atomic_set(&cor_num_neighs, 0);
1485
1486 return 0;
1487 }
1488
1489 void __exit cor_neighbor_exit2(void)
1490 {
1491 BUG_ON(atomic_read(&cor_num_neighs) != 0);
1492
1493 kmem_cache_destroy(cor_nb_slab);
1494 cor_nb_slab = 0;
1495 }
1496
1497 MODULE_LICENSE("GPL");
connection oriented routing