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 node
*n_ptr
, char *str
);
50 static void node_lost_contact(struct node
*n_ptr
);
51 static void node_established_contact(struct node
*n_ptr
);
53 struct node
*tipc_nodes
= NULL
; /* sorted list of nodes within cluster */
55 static DEFINE_SPINLOCK(node_create_lock
);
60 * tipc_node_create - create neighboring node
62 * Currently, this routine is called by neighbor discovery code, which holds
63 * net_lock for reading only. We must take node_create_lock to ensure a node
64 * isn't created twice if two different bearers discover the node at the same
65 * time. (It would be preferable to switch to holding net_lock in write mode,
66 * but this is a non-trivial change.)
69 struct node
*tipc_node_create(u32 addr
)
71 struct cluster
*c_ptr
;
73 struct node
**curr_node
;
75 spin_lock_bh(&node_create_lock
);
77 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
78 if (addr
< n_ptr
->addr
)
80 if (addr
== n_ptr
->addr
) {
81 spin_unlock_bh(&node_create_lock
);
86 n_ptr
= kzalloc(sizeof(*n_ptr
),GFP_ATOMIC
);
88 spin_unlock_bh(&node_create_lock
);
89 warn("Node creation failed, no memory\n");
93 c_ptr
= tipc_cltr_find(addr
);
95 c_ptr
= tipc_cltr_create(addr
);
98 spin_unlock_bh(&node_create_lock
);
104 spin_lock_init(&n_ptr
->lock
);
105 INIT_LIST_HEAD(&n_ptr
->nsub
);
106 n_ptr
->owner
= c_ptr
;
107 tipc_cltr_attach_node(c_ptr
, n_ptr
);
108 n_ptr
->last_router
= -1;
110 /* Insert node into ordered list */
111 for (curr_node
= &tipc_nodes
; *curr_node
;
112 curr_node
= &(*curr_node
)->next
) {
113 if (addr
< (*curr_node
)->addr
) {
114 n_ptr
->next
= *curr_node
;
118 (*curr_node
) = n_ptr
;
119 spin_unlock_bh(&node_create_lock
);
123 void tipc_node_delete(struct node
*n_ptr
)
129 /* Not needed because links are already deleted via tipc_bearer_stop() */
133 for (l_num
= 0; l_num
< MAX_BEARERS
; l_num
++) {
134 link_delete(n_ptr
->links
[l_num
]);
138 dbg("node %x deleted\n", n_ptr
->addr
);
144 * tipc_node_link_up - handle addition of link
146 * Link becomes active (alone or shared) or standby, depending on its priority.
149 void tipc_node_link_up(struct node
*n_ptr
, struct link
*l_ptr
)
151 struct link
**active
= &n_ptr
->active_links
[0];
153 n_ptr
->working_links
++;
155 info("Established link <%s> on network plane %c\n",
156 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
159 dbg(" link %x into %x/%x\n", l_ptr
, &active
[0], &active
[1]);
160 active
[0] = active
[1] = l_ptr
;
161 node_established_contact(n_ptr
);
164 if (l_ptr
->priority
< active
[0]->priority
) {
165 info("New link <%s> becomes standby\n", l_ptr
->name
);
168 tipc_link_send_duplicate(active
[0], l_ptr
);
169 if (l_ptr
->priority
== active
[0]->priority
) {
173 info("Old link <%s> becomes standby\n", active
[0]->name
);
174 if (active
[1] != active
[0])
175 info("Old link <%s> becomes standby\n", active
[1]->name
);
176 active
[0] = active
[1] = l_ptr
;
180 * node_select_active_links - select active link
183 static void node_select_active_links(struct node
*n_ptr
)
185 struct link
**active
= &n_ptr
->active_links
[0];
187 u32 highest_prio
= 0;
189 active
[0] = active
[1] = NULL
;
191 for (i
= 0; i
< MAX_BEARERS
; i
++) {
192 struct link
*l_ptr
= n_ptr
->links
[i
];
194 if (!l_ptr
|| !tipc_link_is_up(l_ptr
) ||
195 (l_ptr
->priority
< highest_prio
))
198 if (l_ptr
->priority
> highest_prio
) {
199 highest_prio
= l_ptr
->priority
;
200 active
[0] = active
[1] = l_ptr
;
208 * tipc_node_link_down - handle loss of link
211 void tipc_node_link_down(struct node
*n_ptr
, struct link
*l_ptr
)
213 struct link
**active
;
215 n_ptr
->working_links
--;
217 if (!tipc_link_is_active(l_ptr
)) {
218 info("Lost standby link <%s> on network plane %c\n",
219 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
222 info("Lost link <%s> on network plane %c\n",
223 l_ptr
->name
, l_ptr
->b_ptr
->net_plane
);
225 active
= &n_ptr
->active_links
[0];
226 if (active
[0] == l_ptr
)
227 active
[0] = active
[1];
228 if (active
[1] == l_ptr
)
229 active
[1] = active
[0];
230 if (active
[0] == l_ptr
)
231 node_select_active_links(n_ptr
);
232 if (tipc_node_is_up(n_ptr
))
233 tipc_link_changeover(l_ptr
);
235 node_lost_contact(n_ptr
);
238 int tipc_node_has_active_links(struct node
*n_ptr
)
241 ((n_ptr
->active_links
[0]) || (n_ptr
->active_links
[1])));
244 int tipc_node_has_redundant_links(struct node
*n_ptr
)
246 return (n_ptr
->working_links
> 1);
249 static int tipc_node_has_active_routes(struct node
*n_ptr
)
251 return (n_ptr
&& (n_ptr
->last_router
>= 0));
254 int tipc_node_is_up(struct node
*n_ptr
)
256 return (tipc_node_has_active_links(n_ptr
) || tipc_node_has_active_routes(n_ptr
));
259 struct node
*tipc_node_attach_link(struct link
*l_ptr
)
261 struct node
*n_ptr
= tipc_node_find(l_ptr
->addr
);
264 n_ptr
= tipc_node_create(l_ptr
->addr
);
266 u32 bearer_id
= l_ptr
->b_ptr
->identity
;
267 char addr_string
[16];
269 if (n_ptr
->link_cnt
>= 2) {
270 err("Attempt to create third link to %s\n",
271 addr_string_fill(addr_string
, n_ptr
->addr
));
275 if (!n_ptr
->links
[bearer_id
]) {
276 n_ptr
->links
[bearer_id
] = l_ptr
;
277 tipc_net
.zones
[tipc_zone(l_ptr
->addr
)]->links
++;
281 err("Attempt to establish second link on <%s> to %s \n",
282 l_ptr
->b_ptr
->publ
.name
,
283 addr_string_fill(addr_string
, l_ptr
->addr
));
288 void tipc_node_detach_link(struct node
*n_ptr
, struct link
*l_ptr
)
290 n_ptr
->links
[l_ptr
->b_ptr
->identity
] = NULL
;
291 tipc_net
.zones
[tipc_zone(l_ptr
->addr
)]->links
--;
296 * Routing table management - five cases to handle:
298 * 1: A link towards a zone/cluster external node comes up.
299 * => Send a multicast message updating routing tables of all
300 * system nodes within own cluster that the new destination
301 * can be reached via this node.
302 * (node.establishedContact()=>cluster.multicastNewRoute())
304 * 2: A link towards a slave node comes up.
305 * => Send a multicast message updating routing tables of all
306 * system nodes within own cluster that the new destination
307 * can be reached via this node.
308 * (node.establishedContact()=>cluster.multicastNewRoute())
309 * => Send a message to the slave node about existence
310 * of all system nodes within cluster:
311 * (node.establishedContact()=>cluster.sendLocalRoutes())
313 * 3: A new cluster local system node becomes available.
314 * => Send message(s) to this particular node containing
315 * information about all cluster external and slave
316 * nodes which can be reached via this node.
317 * (node.establishedContact()==>network.sendExternalRoutes())
318 * (node.establishedContact()==>network.sendSlaveRoutes())
319 * => Send messages to all directly connected slave nodes
320 * containing information about the existence of the new node
321 * (node.establishedContact()=>cluster.multicastNewRoute())
323 * 4: The link towards a zone/cluster external node or slave
325 * => Send a multcast message updating routing tables of all
326 * nodes within cluster that the new destination can not any
327 * longer be reached via this node.
328 * (node.lostAllLinks()=>cluster.bcastLostRoute())
330 * 5: A cluster local system node becomes unavailable.
331 * => Remove all references to this node from the local
332 * routing tables. Note: This is a completely node
334 * (node.lostAllLinks()=>network.removeAsRouter())
335 * => Send messages to all directly connected slave nodes
336 * containing information about loss of the node
337 * (node.establishedContact()=>cluster.multicastLostRoute())
341 static void node_established_contact(struct node
*n_ptr
)
343 struct cluster
*c_ptr
;
345 dbg("node_established_contact:-> %x\n", n_ptr
->addr
);
346 if (!tipc_node_has_active_routes(n_ptr
) && in_own_cluster(n_ptr
->addr
)) {
347 tipc_k_signal((Handler
)tipc_named_node_up
, n_ptr
->addr
);
350 /* Syncronize broadcast acks */
351 n_ptr
->bclink
.acked
= tipc_bclink_get_last_sent();
353 if (is_slave(tipc_own_addr
))
355 if (!in_own_cluster(n_ptr
->addr
)) {
356 /* Usage case 1 (see above) */
357 c_ptr
= tipc_cltr_find(tipc_own_addr
);
359 c_ptr
= tipc_cltr_create(tipc_own_addr
);
361 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, 1,
366 c_ptr
= n_ptr
->owner
;
367 if (is_slave(n_ptr
->addr
)) {
368 /* Usage case 2 (see above) */
369 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, 1, tipc_max_nodes
);
370 tipc_cltr_send_local_routes(c_ptr
, n_ptr
->addr
);
374 if (n_ptr
->bclink
.supported
) {
375 tipc_nmap_add(&tipc_cltr_bcast_nodes
, n_ptr
->addr
);
376 if (n_ptr
->addr
< tipc_own_addr
)
380 /* Case 3 (see above) */
381 tipc_net_send_external_routes(n_ptr
->addr
);
382 tipc_cltr_send_slave_routes(c_ptr
, n_ptr
->addr
);
383 tipc_cltr_bcast_new_route(c_ptr
, n_ptr
->addr
, LOWEST_SLAVE
,
384 tipc_highest_allowed_slave
);
387 static void node_lost_contact(struct node
*n_ptr
)
389 struct cluster
*c_ptr
;
390 struct node_subscr
*ns
, *tns
;
391 char addr_string
[16];
394 /* Clean up broadcast reception remains */
395 n_ptr
->bclink
.gap_after
= n_ptr
->bclink
.gap_to
= 0;
396 while (n_ptr
->bclink
.deferred_head
) {
397 struct sk_buff
* buf
= n_ptr
->bclink
.deferred_head
;
398 n_ptr
->bclink
.deferred_head
= buf
->next
;
401 if (n_ptr
->bclink
.defragm
) {
402 buf_discard(n_ptr
->bclink
.defragm
);
403 n_ptr
->bclink
.defragm
= NULL
;
405 if (in_own_cluster(n_ptr
->addr
) && n_ptr
->bclink
.supported
) {
406 tipc_bclink_acknowledge(n_ptr
, mod(n_ptr
->bclink
.acked
+ 10000));
409 /* Update routing tables */
410 if (is_slave(tipc_own_addr
)) {
411 tipc_net_remove_as_router(n_ptr
->addr
);
413 if (!in_own_cluster(n_ptr
->addr
)) {
414 /* Case 4 (see above) */
415 c_ptr
= tipc_cltr_find(tipc_own_addr
);
416 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
, 1,
419 /* Case 5 (see above) */
420 c_ptr
= tipc_cltr_find(n_ptr
->addr
);
421 if (is_slave(n_ptr
->addr
)) {
422 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
, 1,
425 if (n_ptr
->bclink
.supported
) {
426 tipc_nmap_remove(&tipc_cltr_bcast_nodes
,
428 if (n_ptr
->addr
< tipc_own_addr
)
431 tipc_net_remove_as_router(n_ptr
->addr
);
432 tipc_cltr_bcast_lost_route(c_ptr
, n_ptr
->addr
,
434 tipc_highest_allowed_slave
);
438 if (tipc_node_has_active_routes(n_ptr
))
441 info("Lost contact with %s\n",
442 addr_string_fill(addr_string
, n_ptr
->addr
));
444 /* Abort link changeover */
445 for (i
= 0; i
< MAX_BEARERS
; i
++) {
446 struct link
*l_ptr
= n_ptr
->links
[i
];
449 l_ptr
->reset_checkpoint
= l_ptr
->next_in_no
;
450 l_ptr
->exp_msg_count
= 0;
451 tipc_link_reset_fragments(l_ptr
);
454 /* Notify subscribers */
455 list_for_each_entry_safe(ns
, tns
, &n_ptr
->nsub
, nodesub_list
) {
457 list_del_init(&ns
->nodesub_list
);
458 tipc_k_signal((Handler
)ns
->handle_node_down
,
459 (unsigned long)ns
->usr_handle
);
464 * tipc_node_select_next_hop - find the next-hop node for a message
466 * Called by when cluster local lookup has failed.
469 struct node
*tipc_node_select_next_hop(u32 addr
, u32 selector
)
474 if (!tipc_addr_domain_valid(addr
))
477 /* Look for direct link to destination processsor */
478 n_ptr
= tipc_node_find(addr
);
479 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
482 /* Cluster local system nodes *must* have direct links */
483 if (!is_slave(addr
) && in_own_cluster(addr
))
486 /* Look for cluster local router with direct link to node */
487 router_addr
= tipc_node_select_router(n_ptr
, selector
);
489 return tipc_node_select(router_addr
, selector
);
491 /* Slave nodes can only be accessed within own cluster via a
492 known router with direct link -- if no router was found,give up */
496 /* Inter zone/cluster -- find any direct link to remote cluster */
497 addr
= tipc_addr(tipc_zone(addr
), tipc_cluster(addr
), 0);
498 n_ptr
= tipc_net_select_remote_node(addr
, selector
);
499 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
502 /* Last resort -- look for any router to anywhere in remote zone */
503 router_addr
= tipc_net_select_router(addr
, selector
);
505 return tipc_node_select(router_addr
, selector
);
511 * tipc_node_select_router - select router to reach specified node
513 * Uses a deterministic and fair algorithm for selecting router node.
516 u32
tipc_node_select_router(struct node
*n_ptr
, u32 ref
)
526 if (n_ptr
->last_router
< 0)
528 ulim
= ((n_ptr
->last_router
+ 1) * 32) - 1;
530 /* Start entry must be random */
531 mask
= tipc_max_nodes
;
537 /* Lookup upwards with wrap-around */
539 if (((n_ptr
->routers
[r
/ 32]) >> (r
% 32)) & 1)
541 } while (++r
<= ulim
);
545 if (((n_ptr
->routers
[r
/ 32]) >> (r
% 32)) & 1)
547 } while (++r
< start
);
550 assert(r
&& (r
<= ulim
));
551 return tipc_addr(own_zone(), own_cluster(), r
);
554 void tipc_node_add_router(struct node
*n_ptr
, u32 router
)
556 u32 r_num
= tipc_node(router
);
558 n_ptr
->routers
[r_num
/ 32] =
559 ((1 << (r_num
% 32)) | n_ptr
->routers
[r_num
/ 32]);
560 n_ptr
->last_router
= tipc_max_nodes
/ 32;
561 while ((--n_ptr
->last_router
>= 0) &&
562 !n_ptr
->routers
[n_ptr
->last_router
]);
565 void tipc_node_remove_router(struct node
*n_ptr
, u32 router
)
567 u32 r_num
= tipc_node(router
);
569 if (n_ptr
->last_router
< 0)
570 return; /* No routes */
572 n_ptr
->routers
[r_num
/ 32] =
573 ((~(1 << (r_num
% 32))) & (n_ptr
->routers
[r_num
/ 32]));
574 n_ptr
->last_router
= tipc_max_nodes
/ 32;
575 while ((--n_ptr
->last_router
>= 0) &&
576 !n_ptr
->routers
[n_ptr
->last_router
]);
578 if (!tipc_node_is_up(n_ptr
))
579 node_lost_contact(n_ptr
);
583 void node_print(struct print_buf
*buf
, struct node
*n_ptr
, char *str
)
587 tipc_printf(buf
, "\n\n%s", str
);
588 for (i
= 0; i
< MAX_BEARERS
; i
++) {
589 if (!n_ptr
->links
[i
])
591 tipc_printf(buf
, "Links[%u]: %x, ", i
, n_ptr
->links
[i
]);
593 tipc_printf(buf
, "Active links: [%x,%x]\n",
594 n_ptr
->active_links
[0], n_ptr
->active_links
[1]);
598 u32
tipc_available_nodes(const u32 domain
)
603 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
604 if (!in_scope(domain
, n_ptr
->addr
))
606 if (tipc_node_is_up(n_ptr
))
612 struct sk_buff
*tipc_node_get_nodes(const void *req_tlv_area
, int req_tlv_space
)
617 struct tipc_node_info node_info
;
620 if (!TLV_CHECK(req_tlv_area
, req_tlv_space
, TIPC_TLV_NET_ADDR
))
621 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR
);
623 domain
= ntohl(*(__be32
*)TLV_DATA(req_tlv_area
));
624 if (!tipc_addr_domain_valid(domain
))
625 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
626 " (network address)");
629 return tipc_cfg_reply_none();
631 /* For now, get space for all other nodes
632 (will need to modify this when slave nodes are supported */
634 payload_size
= TLV_SPACE(sizeof(node_info
)) * (tipc_max_nodes
- 1);
635 if (payload_size
> 32768u)
636 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
637 " (too many nodes)");
638 buf
= tipc_cfg_reply_alloc(payload_size
);
642 /* Add TLVs for all nodes in scope */
644 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
645 if (!in_scope(domain
, n_ptr
->addr
))
647 node_info
.addr
= htonl(n_ptr
->addr
);
648 node_info
.up
= htonl(tipc_node_is_up(n_ptr
));
649 tipc_cfg_append_tlv(buf
, TIPC_TLV_NODE_INFO
,
650 &node_info
, sizeof(node_info
));
656 struct sk_buff
*tipc_node_get_links(const void *req_tlv_area
, int req_tlv_space
)
661 struct tipc_link_info link_info
;
664 if (!TLV_CHECK(req_tlv_area
, req_tlv_space
, TIPC_TLV_NET_ADDR
))
665 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR
);
667 domain
= ntohl(*(__be32
*)TLV_DATA(req_tlv_area
));
668 if (!tipc_addr_domain_valid(domain
))
669 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
670 " (network address)");
672 if (tipc_mode
!= TIPC_NET_MODE
)
673 return tipc_cfg_reply_none();
675 /* Get space for all unicast links + multicast link */
677 payload_size
= TLV_SPACE(sizeof(link_info
)) *
678 (tipc_net
.zones
[tipc_zone(tipc_own_addr
)]->links
+ 1);
679 if (payload_size
> 32768u)
680 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
681 " (too many links)");
682 buf
= tipc_cfg_reply_alloc(payload_size
);
686 /* Add TLV for broadcast link */
688 link_info
.dest
= htonl(tipc_own_addr
& 0xfffff00);
689 link_info
.up
= htonl(1);
690 sprintf(link_info
.str
, tipc_bclink_name
);
691 tipc_cfg_append_tlv(buf
, TIPC_TLV_LINK_INFO
, &link_info
, sizeof(link_info
));
693 /* Add TLVs for any other links in scope */
695 for (n_ptr
= tipc_nodes
; n_ptr
; n_ptr
= n_ptr
->next
) {
698 if (!in_scope(domain
, n_ptr
->addr
))
700 for (i
= 0; i
< MAX_BEARERS
; i
++) {
701 if (!n_ptr
->links
[i
])
703 link_info
.dest
= htonl(n_ptr
->addr
);
704 link_info
.up
= htonl(tipc_link_is_up(n_ptr
->links
[i
]));
705 strcpy(link_info
.str
, n_ptr
->links
[i
]->name
);
706 tipc_cfg_append_tlv(buf
, TIPC_TLV_LINK_INFO
,
707 &link_info
, sizeof(link_info
));