2 * net/tipc/node.c: TIPC node management routines
4 * Copyright (c) 2000-2006, Ericsson AB
5 * Copyright (c) 2005-2006, Wind River Systems
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the names of the copyright holders nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
20 * Alternatively, this software may be distributed under the terms of the
21 * GNU General Public License ("GPL") version 2 as published by the Free
22 * Software Foundation.
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
28 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
32 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
41 #include "name_distr.h"
43 static void node_lost_contact(struct tipc_node *n_ptr);
44 static void node_established_contact(struct tipc_node *n_ptr);
46 /* sorted list of nodes within cluster */
47 static struct tipc_node *tipc_nodes = NULL;
49 static DEFINE_SPINLOCK(node_create_lock);
54 * tipc_node_create - create neighboring node
56 * Currently, this routine is called by neighbor discovery code, which holds
57 * net_lock for reading only. We must take node_create_lock to ensure a node
58 * isn't created twice if two different bearers discover the node at the same
59 * time. (It would be preferable to switch to holding net_lock in write mode,
60 * but this is a non-trivial change.)
63 struct tipc_node *tipc_node_create(u32 addr)
65 struct cluster *c_ptr;
66 struct tipc_node *n_ptr;
67 struct tipc_node **curr_node;
69 spin_lock_bh(&node_create_lock);
71 for (n_ptr = tipc_nodes; n_ptr; n_ptr = n_ptr->next) {
72 if (addr < n_ptr->addr)
74 if (addr == n_ptr->addr) {
75 spin_unlock_bh(&node_create_lock);
80 n_ptr = kzalloc(sizeof(*n_ptr),GFP_ATOMIC);
82 spin_unlock_bh(&node_create_lock);
83 warn("Node creation failed, no memory\n");
87 c_ptr = tipc_cltr_find(addr);
89 c_ptr = tipc_cltr_create(addr);
92 spin_unlock_bh(&node_create_lock);
98 spin_lock_init(&n_ptr->lock);
99 INIT_LIST_HEAD(&n_ptr->nsub);
100 n_ptr->owner = c_ptr;
101 tipc_cltr_attach_node(c_ptr, n_ptr);
102 n_ptr->last_router = -1;
104 /* Insert node into ordered list */
105 for (curr_node = &tipc_nodes; *curr_node;
106 curr_node = &(*curr_node)->next) {
107 if (addr < (*curr_node)->addr) {
108 n_ptr->next = *curr_node;
112 (*curr_node) = n_ptr;
113 spin_unlock_bh(&node_create_lock);
117 void tipc_node_delete(struct tipc_node *n_ptr)
122 dbg("node %x deleted\n", n_ptr->addr);
128 * tipc_node_link_up - handle addition of link
130 * Link becomes active (alone or shared) or standby, depending on its priority.
133 void tipc_node_link_up(struct tipc_node *n_ptr, struct link *l_ptr)
135 struct link **active = &n_ptr->active_links[0];
137 n_ptr->working_links++;
139 info("Established link <%s> on network plane %c\n",
140 l_ptr->name, l_ptr->b_ptr->net_plane);
143 dbg(" link %x into %x/%x\n", l_ptr, &active[0], &active[1]);
144 active[0] = active[1] = l_ptr;
145 node_established_contact(n_ptr);
148 if (l_ptr->priority < active[0]->priority) {
149 info("New link <%s> becomes standby\n", l_ptr->name);
152 tipc_link_send_duplicate(active[0], l_ptr);
153 if (l_ptr->priority == active[0]->priority) {
157 info("Old link <%s> becomes standby\n", active[0]->name);
158 if (active[1] != active[0])
159 info("Old link <%s> becomes standby\n", active[1]->name);
160 active[0] = active[1] = l_ptr;
164 * node_select_active_links - select active link
167 static void node_select_active_links(struct tipc_node *n_ptr)
169 struct link **active = &n_ptr->active_links[0];
171 u32 highest_prio = 0;
173 active[0] = active[1] = NULL;
175 for (i = 0; i < MAX_BEARERS; i++) {
176 struct link *l_ptr = n_ptr->links[i];
178 if (!l_ptr || !tipc_link_is_up(l_ptr) ||
179 (l_ptr->priority < highest_prio))
182 if (l_ptr->priority > highest_prio) {
183 highest_prio = l_ptr->priority;
184 active[0] = active[1] = l_ptr;
192 * tipc_node_link_down - handle loss of link
195 void tipc_node_link_down(struct tipc_node *n_ptr, struct link *l_ptr)
197 struct link **active;
199 n_ptr->working_links--;
201 if (!tipc_link_is_active(l_ptr)) {
202 info("Lost standby link <%s> on network plane %c\n",
203 l_ptr->name, l_ptr->b_ptr->net_plane);
206 info("Lost link <%s> on network plane %c\n",
207 l_ptr->name, l_ptr->b_ptr->net_plane);
209 active = &n_ptr->active_links[0];
210 if (active[0] == l_ptr)
211 active[0] = active[1];
212 if (active[1] == l_ptr)
213 active[1] = active[0];
214 if (active[0] == l_ptr)
215 node_select_active_links(n_ptr);
216 if (tipc_node_is_up(n_ptr))
217 tipc_link_changeover(l_ptr);
219 node_lost_contact(n_ptr);
222 int tipc_node_has_active_links(struct tipc_node *n_ptr)
224 return n_ptr->active_links[0] != NULL;
227 int tipc_node_has_redundant_links(struct tipc_node *n_ptr)
229 return n_ptr->working_links > 1;
232 static int tipc_node_has_active_routes(struct tipc_node *n_ptr)
234 return n_ptr && (n_ptr->last_router >= 0);
237 int tipc_node_is_up(struct tipc_node *n_ptr)
239 return tipc_node_has_active_links(n_ptr) || tipc_node_has_active_routes(n_ptr);
242 struct tipc_node *tipc_node_attach_link(struct link *l_ptr)
244 struct tipc_node *n_ptr = tipc_node_find(l_ptr->addr);
247 n_ptr = tipc_node_create(l_ptr->addr);
249 u32 bearer_id = l_ptr->b_ptr->identity;
250 char addr_string[16];
252 if (n_ptr->link_cnt >= 2) {
253 err("Attempt to create third link to %s\n",
254 tipc_addr_string_fill(addr_string, n_ptr->addr));
258 if (!n_ptr->links[bearer_id]) {
259 n_ptr->links[bearer_id] = l_ptr;
264 err("Attempt to establish second link on <%s> to %s\n",
265 l_ptr->b_ptr->publ.name,
266 tipc_addr_string_fill(addr_string, l_ptr->addr));
271 void tipc_node_detach_link(struct tipc_node *n_ptr, struct link *l_ptr)
273 n_ptr->links[l_ptr->b_ptr->identity] = NULL;
279 * Routing table management - five cases to handle:
281 * 1: A link towards a zone/cluster external node comes up.
282 * => Send a multicast message updating routing tables of all
283 * system nodes within own cluster that the new destination
284 * can be reached via this node.
285 * (node.establishedContact()=>cluster.multicastNewRoute())
287 * 2: A link towards a slave node comes up.
288 * => Send a multicast message updating routing tables of all
289 * system nodes within own cluster that the new destination
290 * can be reached via this node.
291 * (node.establishedContact()=>cluster.multicastNewRoute())
292 * => Send a message to the slave node about existence
293 * of all system nodes within cluster:
294 * (node.establishedContact()=>cluster.sendLocalRoutes())
296 * 3: A new cluster local system node becomes available.
297 * => Send message(s) to this particular node containing
298 * information about all cluster external and slave
299 * nodes which can be reached via this node.
300 * (node.establishedContact()==>network.sendExternalRoutes())
301 * (node.establishedContact()==>network.sendSlaveRoutes())
302 * => Send messages to all directly connected slave nodes
303 * containing information about the existence of the new node
304 * (node.establishedContact()=>cluster.multicastNewRoute())
306 * 4: The link towards a zone/cluster external node or slave
308 * => Send a multcast message updating routing tables of all
309 * nodes within cluster that the new destination can not any
310 * longer be reached via this node.
311 * (node.lostAllLinks()=>cluster.bcastLostRoute())
313 * 5: A cluster local system node becomes unavailable.
314 * => Remove all references to this node from the local
315 * routing tables. Note: This is a completely node
317 * (node.lostAllLinks()=>network.removeAsRouter())
318 * => Send messages to all directly connected slave nodes
319 * containing information about loss of the node
320 * (node.establishedContact()=>cluster.multicastLostRoute())
324 static void node_established_contact(struct tipc_node *n_ptr)
326 struct cluster *c_ptr;
328 dbg("node_established_contact:-> %x\n", n_ptr->addr);
329 if (!tipc_node_has_active_routes(n_ptr) && in_own_cluster(n_ptr->addr)) {
330 tipc_k_signal((Handler)tipc_named_node_up, n_ptr->addr);
333 /* Syncronize broadcast acks */
334 n_ptr->bclink.acked = tipc_bclink_get_last_sent();
336 if (!in_own_cluster(n_ptr->addr)) {
337 /* Usage case 1 (see above) */
338 c_ptr = tipc_cltr_find(tipc_own_addr);
340 c_ptr = tipc_cltr_create(tipc_own_addr);
342 tipc_cltr_bcast_new_route(c_ptr, n_ptr->addr, 1,
347 c_ptr = n_ptr->owner;
348 if (n_ptr->bclink.supported) {
349 tipc_nmap_add(&tipc_cltr_bcast_nodes, n_ptr->addr);
350 if (n_ptr->addr < tipc_own_addr)
354 /* Case 3 (see above) */
355 tipc_net_send_external_routes(n_ptr->addr);
358 static void node_cleanup_finished(unsigned long node_addr)
360 struct tipc_node *n_ptr;
362 read_lock_bh(&tipc_net_lock);
363 n_ptr = tipc_node_find(node_addr);
365 tipc_node_lock(n_ptr);
366 n_ptr->cleanup_required = 0;
367 tipc_node_unlock(n_ptr);
369 read_unlock_bh(&tipc_net_lock);
372 static void node_lost_contact(struct tipc_node *n_ptr)
374 struct cluster *c_ptr;
375 struct tipc_node_subscr *ns, *tns;
376 char addr_string[16];
379 /* Clean up broadcast reception remains */
380 n_ptr->bclink.gap_after = n_ptr->bclink.gap_to = 0;
381 while (n_ptr->bclink.deferred_head) {
382 struct sk_buff* buf = n_ptr->bclink.deferred_head;
383 n_ptr->bclink.deferred_head = buf->next;
386 if (n_ptr->bclink.defragm) {
387 buf_discard(n_ptr->bclink.defragm);
388 n_ptr->bclink.defragm = NULL;
390 if (in_own_cluster(n_ptr->addr) && n_ptr->bclink.supported) {
391 tipc_bclink_acknowledge(n_ptr, mod(n_ptr->bclink.acked + 10000));
394 /* Update routing tables */
395 if (!in_own_cluster(n_ptr->addr)) {
396 /* Case 4 (see above) */
397 c_ptr = tipc_cltr_find(tipc_own_addr);
398 tipc_cltr_bcast_lost_route(c_ptr, n_ptr->addr, 1,
401 /* Case 5 (see above) */
402 c_ptr = tipc_cltr_find(n_ptr->addr);
403 if (n_ptr->bclink.supported) {
404 tipc_nmap_remove(&tipc_cltr_bcast_nodes, n_ptr->addr);
405 if (n_ptr->addr < tipc_own_addr)
408 tipc_net_remove_as_router(n_ptr->addr);
410 if (tipc_node_has_active_routes(n_ptr))
413 info("Lost contact with %s\n",
414 tipc_addr_string_fill(addr_string, n_ptr->addr));
416 /* Abort link changeover */
417 for (i = 0; i < MAX_BEARERS; i++) {
418 struct link *l_ptr = n_ptr->links[i];
421 l_ptr->reset_checkpoint = l_ptr->next_in_no;
422 l_ptr->exp_msg_count = 0;
423 tipc_link_reset_fragments(l_ptr);
426 /* Notify subscribers */
427 list_for_each_entry_safe(ns, tns, &n_ptr->nsub, nodesub_list) {
429 list_del_init(&ns->nodesub_list);
430 tipc_k_signal((Handler)ns->handle_node_down,
431 (unsigned long)ns->usr_handle);
434 /* Prevent re-contact with node until all cleanup is done */
436 n_ptr->cleanup_required = 1;
437 tipc_k_signal((Handler)node_cleanup_finished, n_ptr->addr);
441 * tipc_node_select_next_hop - find the next-hop node for a message
443 * Called by when cluster local lookup has failed.
446 struct tipc_node *tipc_node_select_next_hop(u32 addr, u32 selector)
448 struct tipc_node *n_ptr;
451 if (!tipc_addr_domain_valid(addr))
454 /* Look for direct link to destination processsor */
455 n_ptr = tipc_node_find(addr);
456 if (n_ptr && tipc_node_has_active_links(n_ptr))
459 /* Cluster local system nodes *must* have direct links */
460 if (in_own_cluster(addr))
463 /* Look for cluster local router with direct link to node */
464 router_addr = tipc_node_select_router(n_ptr, selector);
466 return tipc_node_select(router_addr, selector);
468 /* Inter zone/cluster -- find any direct link to remote cluster */
469 addr = tipc_addr(tipc_zone(addr), tipc_cluster(addr), 0);
470 n_ptr = tipc_net_select_remote_node(addr, selector);
471 if (n_ptr && tipc_node_has_active_links(n_ptr))
474 /* Last resort -- look for any router to anywhere in remote zone */
475 router_addr = tipc_net_select_router(addr, selector);
477 return tipc_node_select(router_addr, selector);
483 * tipc_node_select_router - select router to reach specified node
485 * Uses a deterministic and fair algorithm for selecting router node.
488 u32 tipc_node_select_router(struct tipc_node *n_ptr, u32 ref)
498 if (n_ptr->last_router < 0)
500 ulim = ((n_ptr->last_router + 1) * 32) - 1;
502 /* Start entry must be random */
503 mask = tipc_max_nodes;
509 /* Lookup upwards with wrap-around */
511 if (((n_ptr->routers[r / 32]) >> (r % 32)) & 1)
513 } while (++r <= ulim);
517 if (((n_ptr->routers[r / 32]) >> (r % 32)) & 1)
519 } while (++r < start);
522 assert(r && (r <= ulim));
523 return tipc_addr(own_zone(), own_cluster(), r);
526 void tipc_node_add_router(struct tipc_node *n_ptr, u32 router)
528 u32 r_num = tipc_node(router);
530 n_ptr->routers[r_num / 32] =
531 ((1 << (r_num % 32)) | n_ptr->routers[r_num / 32]);
532 n_ptr->last_router = tipc_max_nodes / 32;
533 while ((--n_ptr->last_router >= 0) &&
534 !n_ptr->routers[n_ptr->last_router]);
537 void tipc_node_remove_router(struct tipc_node *n_ptr, u32 router)
539 u32 r_num = tipc_node(router);
541 if (n_ptr->last_router < 0)
542 return; /* No routes */
544 n_ptr->routers[r_num / 32] =
545 ((~(1 << (r_num % 32))) & (n_ptr->routers[r_num / 32]));
546 n_ptr->last_router = tipc_max_nodes / 32;
547 while ((--n_ptr->last_router >= 0) &&
548 !n_ptr->routers[n_ptr->last_router]);
550 if (!tipc_node_is_up(n_ptr))
551 node_lost_contact(n_ptr);
554 struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space)
558 struct tipc_node *n_ptr;
559 struct tipc_node_info node_info;
562 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
563 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
565 domain = ntohl(*(__be32 *)TLV_DATA(req_tlv_area));
566 if (!tipc_addr_domain_valid(domain))
567 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
568 " (network address)");
570 read_lock_bh(&tipc_net_lock);
572 read_unlock_bh(&tipc_net_lock);
573 return tipc_cfg_reply_none();
576 /* For now, get space for all other nodes */
578 payload_size = TLV_SPACE(sizeof(node_info)) * (tipc_max_nodes - 1);
579 if (payload_size > 32768u) {
580 read_unlock_bh(&tipc_net_lock);
581 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
582 " (too many nodes)");
584 buf = tipc_cfg_reply_alloc(payload_size);
586 read_unlock_bh(&tipc_net_lock);
590 /* Add TLVs for all nodes in scope */
592 for (n_ptr = tipc_nodes; n_ptr; n_ptr = n_ptr->next) {
593 if (!tipc_in_scope(domain, n_ptr->addr))
595 node_info.addr = htonl(n_ptr->addr);
596 node_info.up = htonl(tipc_node_is_up(n_ptr));
597 tipc_cfg_append_tlv(buf, TIPC_TLV_NODE_INFO,
598 &node_info, sizeof(node_info));
601 read_unlock_bh(&tipc_net_lock);
605 struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space)
609 struct tipc_node *n_ptr;
610 struct tipc_link_info link_info;
613 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
614 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
616 domain = ntohl(*(__be32 *)TLV_DATA(req_tlv_area));
617 if (!tipc_addr_domain_valid(domain))
618 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
619 " (network address)");
621 if (tipc_mode != TIPC_NET_MODE)
622 return tipc_cfg_reply_none();
624 read_lock_bh(&tipc_net_lock);
626 /* Get space for all unicast links + multicast link */
628 payload_size = TLV_SPACE(sizeof(link_info)) * (tipc_net.links + 1);
629 if (payload_size > 32768u) {
630 read_unlock_bh(&tipc_net_lock);
631 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
632 " (too many links)");
634 buf = tipc_cfg_reply_alloc(payload_size);
636 read_unlock_bh(&tipc_net_lock);
640 /* Add TLV for broadcast link */
642 link_info.dest = htonl(tipc_own_addr & 0xfffff00);
643 link_info.up = htonl(1);
644 strlcpy(link_info.str, tipc_bclink_name, TIPC_MAX_LINK_NAME);
645 tipc_cfg_append_tlv(buf, TIPC_TLV_LINK_INFO, &link_info, sizeof(link_info));
647 /* Add TLVs for any other links in scope */
649 for (n_ptr = tipc_nodes; n_ptr; n_ptr = n_ptr->next) {
652 if (!tipc_in_scope(domain, n_ptr->addr))
654 tipc_node_lock(n_ptr);
655 for (i = 0; i < MAX_BEARERS; i++) {
656 if (!n_ptr->links[i])
658 link_info.dest = htonl(n_ptr->addr);
659 link_info.up = htonl(tipc_link_is_up(n_ptr->links[i]));
660 strcpy(link_info.str, n_ptr->links[i]->name);
661 tipc_cfg_append_tlv(buf, TIPC_TLV_LINK_INFO,
662 &link_info, sizeof(link_info));
664 tipc_node_unlock(n_ptr);
667 read_unlock_bh(&tipc_net_lock);