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.
43 #include "node_subscr.h"
47 #include "name_distr.h"
49 void node_print(struct print_buf
*buf
, struct tipc_node
*n_ptr
, char *str
);
50 static void node_lost_contact(struct tipc_node
*n_ptr
);
51 static void node_established_contact(struct tipc_node
*n_ptr
);
53 /* sorted list of nodes within cluster */
54 static struct tipc_node
*tipc_nodes
= NULL
;
56 static DEFINE_SPINLOCK(node_create_lock
);
61 * tipc_node_create - create neighboring node
63 * Currently, this routine is called by neighbor discovery code, which holds
64 * net_lock for reading only. We must take node_create_lock to ensure a node
65 * isn't created twice if two different bearers discover the node at the same
66 * time. (It would be preferable to switch to holding net_lock in write mode,
67 * but this is a non-trivial change.)
70 struct tipc_node
*tipc_node_create(u32 addr
)
72 struct cluster
*c_ptr
;
73 struct tipc_node
*n_ptr
;
74 struct tipc_node
**curr_node
;
76 spin_lock_bh(&node_create_lock
);
78 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
79 if (addr
< n_ptr
->addr
)
81 if (addr
== n_ptr
->addr
) {
82 spin_unlock_bh(&node_create_lock
);
87 n_ptr
= kzalloc(sizeof(*n_ptr
),GFP_ATOMIC
);
89 spin_unlock_bh(&node_create_lock
);
90 warn("Node creation failed, no memory\n");
94 c_ptr
= tipc_cltr_find(addr
);
96 c_ptr
= tipc_cltr_create(addr
);
99 spin_unlock_bh(&node_create_lock
);
105 spin_lock_init(&n_ptr
->lock
);
106 INIT_LIST_HEAD(&n_ptr
->nsub
);
107 n_ptr
->owner
= c_ptr
;
108 tipc_cltr_attach_node(c_ptr
, n_ptr
);
109 n_ptr
->last_router
= -1;
111 /* Insert node into ordered list */
112 for (curr_node
= &tipc_nodes
; *curr_node
;
113 curr_node
= &(*curr_node
)->next
) {
114 if (addr
< (*curr_node
)->addr
) {
115 n_ptr
->next
= *curr_node
;
119 (*curr_node
) = n_ptr
;
120 spin_unlock_bh(&node_create_lock
);
124 void tipc_node_delete(struct tipc_node
*n_ptr
)
129 dbg("node %x deleted\n", n_ptr
->addr
);
135 * tipc_node_link_up - handle addition of link
137 * Link becomes active (alone or shared) or standby, depending on its priority.
140 void tipc_node_link_up(struct tipc_node
*n_ptr
, struct link
*l_ptr
)
142 struct link
**active
= &n_ptr
->active_links
[0];
144 n_ptr
->working_links
++;
146 info("Established link <%s> on network plane %c\n",
147 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
150 dbg(" link %x into %x/%x\n", l_ptr
, &active
[0], &active
[1]);
151 active
[0] = active
[1] = l_ptr
;
152 node_established_contact(n_ptr
);
155 if (l_ptr
->priority
< active
[0]->priority
) {
156 info("New link <%s> becomes standby\n", l_ptr
->name
);
159 tipc_link_send_duplicate(active
[0], l_ptr
);
160 if (l_ptr
->priority
== active
[0]->priority
) {
164 info("Old link <%s> becomes standby\n", active
[0]->name
);
165 if (active
[1] != active
[0])
166 info("Old link <%s> becomes standby\n", active
[1]->name
);
167 active
[0] = active
[1] = l_ptr
;
171 * node_select_active_links - select active link
174 static void node_select_active_links(struct tipc_node
*n_ptr
)
176 struct link
**active
= &n_ptr
->active_links
[0];
178 u32 highest_prio
= 0;
180 active
[0] = active
[1] = NULL
;
182 for (i
= 0; i
< MAX_BEARERS
; i
++) {
183 struct link
*l_ptr
= n_ptr
->links
[i
];
185 if (!l_ptr
|| !tipc_link_is_up(l_ptr
) ||
186 (l_ptr
->priority
< highest_prio
))
189 if (l_ptr
->priority
> highest_prio
) {
190 highest_prio
= l_ptr
->priority
;
191 active
[0] = active
[1] = l_ptr
;
199 * tipc_node_link_down - handle loss of link
202 void tipc_node_link_down(struct tipc_node
*n_ptr
, struct link
*l_ptr
)
204 struct link
**active
;
206 n_ptr
->working_links
--;
208 if (!tipc_link_is_active(l_ptr
)) {
209 info("Lost standby link <%s> on network plane %c\n",
210 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
213 info("Lost link <%s> on network plane %c\n",
214 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
216 active
= &n_ptr
->active_links
[0];
217 if (active
[0] == l_ptr
)
218 active
[0] = active
[1];
219 if (active
[1] == l_ptr
)
220 active
[1] = active
[0];
221 if (active
[0] == l_ptr
)
222 node_select_active_links(n_ptr
);
223 if (tipc_node_is_up(n_ptr
))
224 tipc_link_changeover(l_ptr
);
226 node_lost_contact(n_ptr
);
229 int tipc_node_has_active_links(struct tipc_node
*n_ptr
)
231 return n_ptr
->active_links
[0] != NULL
;
234 int tipc_node_has_redundant_links(struct tipc_node
*n_ptr
)
236 return n_ptr
->working_links
> 1;
239 static int tipc_node_has_active_routes(struct tipc_node
*n_ptr
)
241 return n_ptr
&& (n_ptr
->last_router
>= 0);
244 int tipc_node_is_up(struct tipc_node
*n_ptr
)
246 return tipc_node_has_active_links(n_ptr
) || tipc_node_has_active_routes(n_ptr
);
249 struct tipc_node
*tipc_node_attach_link(struct link
*l_ptr
)
251 struct tipc_node
*n_ptr
= tipc_node_find(l_ptr
->addr
);
254 n_ptr
= tipc_node_create(l_ptr
->addr
);
256 u32 bearer_id
= l_ptr
->b_ptr
->identity
;
257 char addr_string
[16];
259 if (n_ptr
->link_cnt
>= 2) {
260 err("Attempt to create third link to %s\n",
261 tipc_addr_string_fill(addr_string
, n_ptr
->addr
));
265 if (!n_ptr
->links
[bearer_id
]) {
266 n_ptr
->links
[bearer_id
] = l_ptr
;
267 tipc_net
.zones
[tipc_zone(l_ptr
->addr
)]->links
++;
271 err("Attempt to establish second link on <%s> to %s\n",
272 l_ptr
->b_ptr
->publ
.name
,
273 tipc_addr_string_fill(addr_string
, l_ptr
->addr
));
278 void tipc_node_detach_link(struct tipc_node
*n_ptr
, struct link
*l_ptr
)
280 n_ptr
->links
[l_ptr
->b_ptr
->identity
] = NULL
;
281 tipc_net
.zones
[tipc_zone(l_ptr
->addr
)]->links
--;
286 * Routing table management - five cases to handle:
288 * 1: A link towards a zone/cluster external node comes up.
289 * => Send a multicast message updating routing tables of all
290 * system nodes within own cluster that the new destination
291 * can be reached via this node.
292 * (node.establishedContact()=>cluster.multicastNewRoute())
294 * 2: A link towards a slave node comes up.
295 * => Send a multicast message updating routing tables of all
296 * system nodes within own cluster that the new destination
297 * can be reached via this node.
298 * (node.establishedContact()=>cluster.multicastNewRoute())
299 * => Send a message to the slave node about existence
300 * of all system nodes within cluster:
301 * (node.establishedContact()=>cluster.sendLocalRoutes())
303 * 3: A new cluster local system node becomes available.
304 * => Send message(s) to this particular node containing
305 * information about all cluster external and slave
306 * nodes which can be reached via this node.
307 * (node.establishedContact()==>network.sendExternalRoutes())
308 * (node.establishedContact()==>network.sendSlaveRoutes())
309 * => Send messages to all directly connected slave nodes
310 * containing information about the existence of the new node
311 * (node.establishedContact()=>cluster.multicastNewRoute())
313 * 4: The link towards a zone/cluster external node or slave
315 * => Send a multcast message updating routing tables of all
316 * nodes within cluster that the new destination can not any
317 * longer be reached via this node.
318 * (node.lostAllLinks()=>cluster.bcastLostRoute())
320 * 5: A cluster local system node becomes unavailable.
321 * => Remove all references to this node from the local
322 * routing tables. Note: This is a completely node
324 * (node.lostAllLinks()=>network.removeAsRouter())
325 * => Send messages to all directly connected slave nodes
326 * containing information about loss of the node
327 * (node.establishedContact()=>cluster.multicastLostRoute())
331 static void node_established_contact(struct tipc_node
*n_ptr
)
333 struct cluster
*c_ptr
;
335 dbg("node_established_contact:-> %x\n", n_ptr
->addr
);
336 if (!tipc_node_has_active_routes(n_ptr
) && in_own_cluster(n_ptr
->addr
)) {
337 tipc_k_signal((Handler
)tipc_named_node_up
, n_ptr
->addr
);
340 /* Syncronize broadcast acks */
341 n_ptr
->bclink
.acked
= tipc_bclink_get_last_sent();
343 if (is_slave(tipc_own_addr
))
345 if (!in_own_cluster(n_ptr
->addr
)) {
346 /* Usage case 1 (see above) */
347 c_ptr
= tipc_cltr_find(tipc_own_addr
);
349 c_ptr
= tipc_cltr_create(tipc_own_addr
);
351 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, 1,
356 c_ptr
= n_ptr
->owner
;
357 if (is_slave(n_ptr
->addr
)) {
358 /* Usage case 2 (see above) */
359 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, 1, tipc_max_nodes
);
360 tipc_cltr_send_local_routes(c_ptr
, n_ptr
->addr
);
364 if (n_ptr
->bclink
.supported
) {
365 tipc_nmap_add(&tipc_cltr_bcast_nodes
, n_ptr
->addr
);
366 if (n_ptr
->addr
< tipc_own_addr
)
370 /* Case 3 (see above) */
371 tipc_net_send_external_routes(n_ptr
->addr
);
372 tipc_cltr_send_slave_routes(c_ptr
, n_ptr
->addr
);
373 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, LOWEST_SLAVE
,
374 tipc_highest_allowed_slave
);
377 static void node_cleanup_finished(unsigned long node_addr
)
379 struct tipc_node
*n_ptr
;
381 read_lock_bh(&tipc_net_lock
);
382 n_ptr
= tipc_node_find(node_addr
);
384 tipc_node_lock(n_ptr
);
385 n_ptr
->cleanup_required
= 0;
386 tipc_node_unlock(n_ptr
);
388 read_unlock_bh(&tipc_net_lock
);
391 static void node_lost_contact(struct tipc_node
*n_ptr
)
393 struct cluster
*c_ptr
;
394 struct tipc_node_subscr
*ns
, *tns
;
395 char addr_string
[16];
398 /* Clean up broadcast reception remains */
399 n_ptr
->bclink
.gap_after
= n_ptr
->bclink
.gap_to
= 0;
400 while (n_ptr
->bclink
.deferred_head
) {
401 struct sk_buff
* buf
= n_ptr
->bclink
.deferred_head
;
402 n_ptr
->bclink
.deferred_head
= buf
->next
;
405 if (n_ptr
->bclink
.defragm
) {
406 buf_discard(n_ptr
->bclink
.defragm
);
407 n_ptr
->bclink
.defragm
= NULL
;
409 if (in_own_cluster(n_ptr
->addr
) && n_ptr
->bclink
.supported
) {
410 tipc_bclink_acknowledge(n_ptr
, mod(n_ptr
->bclink
.acked
+ 10000));
413 /* Update routing tables */
414 if (is_slave(tipc_own_addr
)) {
415 tipc_net_remove_as_router(n_ptr
->addr
);
417 if (!in_own_cluster(n_ptr
->addr
)) {
418 /* Case 4 (see above) */
419 c_ptr
= tipc_cltr_find(tipc_own_addr
);
420 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
, 1,
423 /* Case 5 (see above) */
424 c_ptr
= tipc_cltr_find(n_ptr
->addr
);
425 if (is_slave(n_ptr
->addr
)) {
426 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
, 1,
429 if (n_ptr
->bclink
.supported
) {
430 tipc_nmap_remove(&tipc_cltr_bcast_nodes
,
432 if (n_ptr
->addr
< tipc_own_addr
)
435 tipc_net_remove_as_router(n_ptr
->addr
);
436 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
,
438 tipc_highest_allowed_slave
);
442 if (tipc_node_has_active_routes(n_ptr
))
445 info("Lost contact with %s\n",
446 tipc_addr_string_fill(addr_string
, n_ptr
->addr
));
448 /* Abort link changeover */
449 for (i
= 0; i
< MAX_BEARERS
; i
++) {
450 struct link
*l_ptr
= n_ptr
->links
[i
];
453 l_ptr
->reset_checkpoint
= l_ptr
->next_in_no
;
454 l_ptr
->exp_msg_count
= 0;
455 tipc_link_reset_fragments(l_ptr
);
458 /* Notify subscribers */
459 list_for_each_entry_safe(ns
, tns
, &n_ptr
->nsub
, nodesub_list
) {
461 list_del_init(&ns
->nodesub_list
);
462 tipc_k_signal((Handler
)ns
->handle_node_down
,
463 (unsigned long)ns
->usr_handle
);
466 /* Prevent re-contact with node until all cleanup is done */
468 n_ptr
->cleanup_required
= 1;
469 tipc_k_signal((Handler
)node_cleanup_finished
, n_ptr
->addr
);
473 * tipc_node_select_next_hop - find the next-hop node for a message
475 * Called by when cluster local lookup has failed.
478 struct tipc_node
*tipc_node_select_next_hop(u32 addr
, u32 selector
)
480 struct tipc_node
*n_ptr
;
483 if (!tipc_addr_domain_valid(addr
))
486 /* Look for direct link to destination processsor */
487 n_ptr
= tipc_node_find(addr
);
488 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
491 /* Cluster local system nodes *must* have direct links */
492 if (!is_slave(addr
) && in_own_cluster(addr
))
495 /* Look for cluster local router with direct link to node */
496 router_addr
= tipc_node_select_router(n_ptr
, selector
);
498 return tipc_node_select(router_addr
, selector
);
500 /* Slave nodes can only be accessed within own cluster via a
501 known router with direct link -- if no router was found,give up */
505 /* Inter zone/cluster -- find any direct link to remote cluster */
506 addr
= tipc_addr(tipc_zone(addr
), tipc_cluster(addr
), 0);
507 n_ptr
= tipc_net_select_remote_node(addr
, selector
);
508 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
511 /* Last resort -- look for any router to anywhere in remote zone */
512 router_addr
= tipc_net_select_router(addr
, selector
);
514 return tipc_node_select(router_addr
, selector
);
520 * tipc_node_select_router - select router to reach specified node
522 * Uses a deterministic and fair algorithm for selecting router node.
525 u32
tipc_node_select_router(struct tipc_node
*n_ptr
, u32 ref
)
535 if (n_ptr
->last_router
< 0)
537 ulim
= ((n_ptr
->last_router
+ 1) * 32) - 1;
539 /* Start entry must be random */
540 mask
= tipc_max_nodes
;
546 /* Lookup upwards with wrap-around */
548 if (((n_ptr
->routers
[r
/ 32]) >> (r
% 32)) & 1)
550 } while (++r
<= ulim
);
554 if (((n_ptr
->routers
[r
/ 32]) >> (r
% 32)) & 1)
556 } while (++r
< start
);
559 assert(r
&& (r
<= ulim
));
560 return tipc_addr(own_zone(), own_cluster(), r
);
563 void tipc_node_add_router(struct tipc_node
*n_ptr
, u32 router
)
565 u32 r_num
= tipc_node(router
);
567 n_ptr
->routers
[r_num
/ 32] =
568 ((1 << (r_num
% 32)) | n_ptr
->routers
[r_num
/ 32]);
569 n_ptr
->last_router
= tipc_max_nodes
/ 32;
570 while ((--n_ptr
->last_router
>= 0) &&
571 !n_ptr
->routers
[n_ptr
->last_router
]);
574 void tipc_node_remove_router(struct tipc_node
*n_ptr
, u32 router
)
576 u32 r_num
= tipc_node(router
);
578 if (n_ptr
->last_router
< 0)
579 return; /* No routes */
581 n_ptr
->routers
[r_num
/ 32] =
582 ((~(1 << (r_num
% 32))) & (n_ptr
->routers
[r_num
/ 32]));
583 n_ptr
->last_router
= tipc_max_nodes
/ 32;
584 while ((--n_ptr
->last_router
>= 0) &&
585 !n_ptr
->routers
[n_ptr
->last_router
]);
587 if (!tipc_node_is_up(n_ptr
))
588 node_lost_contact(n_ptr
);
591 struct sk_buff
*tipc_node_get_nodes(const void *req_tlv_area
, int req_tlv_space
)
595 struct tipc_node
*n_ptr
;
596 struct tipc_node_info node_info
;
599 if (!TLV_CHECK(req_tlv_area
, req_tlv_space
, TIPC_TLV_NET_ADDR
))
600 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR
);
602 domain
= ntohl(*(__be32
*)TLV_DATA(req_tlv_area
));
603 if (!tipc_addr_domain_valid(domain
))
604 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
605 " (network address)");
607 read_lock_bh(&tipc_net_lock
);
609 read_unlock_bh(&tipc_net_lock
);
610 return tipc_cfg_reply_none();
613 /* For now, get space for all other nodes
614 (will need to modify this when slave nodes are supported */
616 payload_size
= TLV_SPACE(sizeof(node_info
)) * (tipc_max_nodes
- 1);
617 if (payload_size
> 32768u) {
618 read_unlock_bh(&tipc_net_lock
);
619 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
620 " (too many nodes)");
622 buf
= tipc_cfg_reply_alloc(payload_size
);
624 read_unlock_bh(&tipc_net_lock
);
628 /* Add TLVs for all nodes in scope */
630 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
631 if (!tipc_in_scope(domain
, n_ptr
->addr
))
633 node_info
.addr
= htonl(n_ptr
->addr
);
634 node_info
.up
= htonl(tipc_node_is_up(n_ptr
));
635 tipc_cfg_append_tlv(buf
, TIPC_TLV_NODE_INFO
,
636 &node_info
, sizeof(node_info
));
639 read_unlock_bh(&tipc_net_lock
);
643 struct sk_buff
*tipc_node_get_links(const void *req_tlv_area
, int req_tlv_space
)
647 struct tipc_node
*n_ptr
;
648 struct tipc_link_info link_info
;
651 if (!TLV_CHECK(req_tlv_area
, req_tlv_space
, TIPC_TLV_NET_ADDR
))
652 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR
);
654 domain
= ntohl(*(__be32
*)TLV_DATA(req_tlv_area
));
655 if (!tipc_addr_domain_valid(domain
))
656 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
657 " (network address)");
659 if (tipc_mode
!= TIPC_NET_MODE
)
660 return tipc_cfg_reply_none();
662 read_lock_bh(&tipc_net_lock
);
664 /* Get space for all unicast links + multicast link */
666 payload_size
= TLV_SPACE(sizeof(link_info
)) *
667 (tipc_net
.zones
[tipc_zone(tipc_own_addr
)]->links
+ 1);
668 if (payload_size
> 32768u) {
669 read_unlock_bh(&tipc_net_lock
);
670 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
671 " (too many links)");
673 buf
= tipc_cfg_reply_alloc(payload_size
);
675 read_unlock_bh(&tipc_net_lock
);
679 /* Add TLV for broadcast link */
681 link_info
.dest
= htonl(tipc_own_addr
& 0xfffff00);
682 link_info
.up
= htonl(1);
683 strlcpy(link_info
.str
, tipc_bclink_name
, TIPC_MAX_LINK_NAME
);
684 tipc_cfg_append_tlv(buf
, TIPC_TLV_LINK_INFO
, &link_info
, sizeof(link_info
));
686 /* Add TLVs for any other links in scope */
688 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
691 if (!tipc_in_scope(domain
, n_ptr
->addr
))
693 tipc_node_lock(n_ptr
);
694 for (i
= 0; i
< MAX_BEARERS
; i
++) {
695 if (!n_ptr
->links
[i
])
697 link_info
.dest
= htonl(n_ptr
->addr
);
698 link_info
.up
= htonl(tipc_link_is_up(n_ptr
->links
[i
]));
699 strcpy(link_info
.str
, n_ptr
->links
[i
]->name
);
700 tipc_cfg_append_tlv(buf
, TIPC_TLV_LINK_INFO
,
701 &link_info
, sizeof(link_info
));
703 tipc_node_unlock(n_ptr
);
706 read_unlock_bh(&tipc_net_lock
);