2 * net/tipc/cluster.c: TIPC cluster management routines
4 * Copyright (c) 2000-2006, Ericsson AB
5 * Copyright (c) 2005, 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.
40 #include "node_subscr.h"
47 static void tipc_cltr_multicast(struct cluster
*c_ptr
, struct sk_buff
*buf
,
48 u32 lower
, u32 upper
);
49 static struct sk_buff
*tipc_cltr_prepare_routing_msg(u32 data_size
, u32 dest
);
51 struct node
**tipc_local_nodes
= NULL
;
52 struct node_map tipc_cltr_bcast_nodes
= {0,{0,}};
53 u32 tipc_highest_allowed_slave
= 0;
55 struct cluster
*tipc_cltr_create(u32 addr
)
58 struct cluster
*c_ptr
;
62 c_ptr
= (struct cluster
*)kmalloc(sizeof(*c_ptr
), GFP_ATOMIC
);
64 warn("Cluster creation failure, no memory\n");
67 memset(c_ptr
, 0, sizeof(*c_ptr
));
69 c_ptr
->addr
= tipc_addr(tipc_zone(addr
), tipc_cluster(addr
), 0);
70 if (in_own_cluster(addr
))
71 max_nodes
= LOWEST_SLAVE
+ tipc_max_slaves
;
73 max_nodes
= tipc_max_nodes
+ 1;
74 alloc
= sizeof(void *) * (max_nodes
+ 1);
76 c_ptr
->nodes
= (struct node
**)kmalloc(alloc
, GFP_ATOMIC
);
77 if (c_ptr
->nodes
== NULL
) {
78 warn("Cluster creation failure, no memory for node area\n");
82 memset(c_ptr
->nodes
, 0, alloc
);
84 if (in_own_cluster(addr
))
85 tipc_local_nodes
= c_ptr
->nodes
;
86 c_ptr
->highest_slave
= LOWEST_SLAVE
- 1;
87 c_ptr
->highest_node
= 0;
89 z_ptr
= tipc_zone_find(tipc_zone(addr
));
91 z_ptr
= tipc_zone_create(addr
);
99 tipc_zone_attach_cluster(z_ptr
, c_ptr
);
100 c_ptr
->owner
= z_ptr
;
104 void tipc_cltr_delete(struct cluster
*c_ptr
)
110 for (n_num
= 1; n_num
<= c_ptr
->highest_node
; n_num
++) {
111 tipc_node_delete(c_ptr
->nodes
[n_num
]);
113 for (n_num
= LOWEST_SLAVE
; n_num
<= c_ptr
->highest_slave
; n_num
++) {
114 tipc_node_delete(c_ptr
->nodes
[n_num
]);
120 u32
tipc_cltr_next_node(struct cluster
*c_ptr
, u32 addr
)
123 u32 n_num
= tipc_node(addr
) + 1;
127 for (; n_num
<= c_ptr
->highest_node
; n_num
++) {
128 n_ptr
= c_ptr
->nodes
[n_num
];
129 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
132 for (n_num
= 1; n_num
< tipc_node(addr
); n_num
++) {
133 n_ptr
= c_ptr
->nodes
[n_num
];
134 if (n_ptr
&& tipc_node_has_active_links(n_ptr
))
140 void tipc_cltr_attach_node(struct cluster
*c_ptr
, struct node
*n_ptr
)
142 u32 n_num
= tipc_node(n_ptr
->addr
);
143 u32 max_n_num
= tipc_max_nodes
;
145 if (in_own_cluster(n_ptr
->addr
))
146 max_n_num
= tipc_highest_allowed_slave
;
148 assert(n_num
<= max_n_num
);
149 assert(c_ptr
->nodes
[n_num
] == 0);
150 c_ptr
->nodes
[n_num
] = n_ptr
;
151 if (n_num
> c_ptr
->highest_node
)
152 c_ptr
->highest_node
= n_num
;
156 * tipc_cltr_select_router - select router to a cluster
158 * Uses deterministic and fair algorithm.
161 u32
tipc_cltr_select_router(struct cluster
*c_ptr
, u32 ref
)
164 u32 ulim
= c_ptr
->highest_node
;
168 assert(!in_own_cluster(c_ptr
->addr
));
172 /* Start entry must be random */
173 mask
= tipc_max_nodes
;
179 /* Lookup upwards with wrap-around */
181 if (tipc_node_is_up(c_ptr
->nodes
[n_num
]))
183 } while (++n_num
<= ulim
);
187 if (tipc_node_is_up(c_ptr
->nodes
[n_num
]))
189 } while (++n_num
< tstart
);
193 assert(n_num
<= ulim
);
194 return tipc_node_select_router(c_ptr
->nodes
[n_num
], ref
);
198 * tipc_cltr_select_node - select destination node within a remote cluster
200 * Uses deterministic and fair algorithm.
203 struct node
*tipc_cltr_select_node(struct cluster
*c_ptr
, u32 selector
)
206 u32 mask
= tipc_max_nodes
;
209 assert(!in_own_cluster(c_ptr
->addr
));
210 if (!c_ptr
->highest_node
)
213 /* Start entry must be random */
214 while (mask
> c_ptr
->highest_node
) {
217 start_entry
= (selector
& mask
) ? selector
& mask
: 1u;
218 assert(start_entry
<= c_ptr
->highest_node
);
220 /* Lookup upwards with wrap-around */
221 for (n_num
= start_entry
; n_num
<= c_ptr
->highest_node
; n_num
++) {
222 if (tipc_node_has_active_links(c_ptr
->nodes
[n_num
]))
223 return c_ptr
->nodes
[n_num
];
225 for (n_num
= 1; n_num
< start_entry
; n_num
++) {
226 if (tipc_node_has_active_links(c_ptr
->nodes
[n_num
]))
227 return c_ptr
->nodes
[n_num
];
233 * Routing table management: See description in node.c
236 static struct sk_buff
*tipc_cltr_prepare_routing_msg(u32 data_size
, u32 dest
)
238 u32 size
= INT_H_SIZE
+ data_size
;
239 struct sk_buff
*buf
= buf_acquire(size
);
240 struct tipc_msg
*msg
;
244 memset((char *)msg
, 0, size
);
245 msg_init(msg
, ROUTE_DISTRIBUTOR
, 0, TIPC_OK
, INT_H_SIZE
, dest
);
250 void tipc_cltr_bcast_new_route(struct cluster
*c_ptr
, u32 dest
,
251 u32 lower
, u32 upper
)
253 struct sk_buff
*buf
= tipc_cltr_prepare_routing_msg(0, c_ptr
->addr
);
254 struct tipc_msg
*msg
;
258 msg_set_remote_node(msg
, dest
);
259 msg_set_type(msg
, ROUTE_ADDITION
);
260 tipc_cltr_multicast(c_ptr
, buf
, lower
, upper
);
262 warn("Memory squeeze: broadcast of new route failed\n");
266 void tipc_cltr_bcast_lost_route(struct cluster
*c_ptr
, u32 dest
,
267 u32 lower
, u32 upper
)
269 struct sk_buff
*buf
= tipc_cltr_prepare_routing_msg(0, c_ptr
->addr
);
270 struct tipc_msg
*msg
;
274 msg_set_remote_node(msg
, dest
);
275 msg_set_type(msg
, ROUTE_REMOVAL
);
276 tipc_cltr_multicast(c_ptr
, buf
, lower
, upper
);
278 warn("Memory squeeze: broadcast of lost route failed\n");
282 void tipc_cltr_send_slave_routes(struct cluster
*c_ptr
, u32 dest
)
285 struct tipc_msg
*msg
;
286 u32 highest
= c_ptr
->highest_slave
;
290 assert(!is_slave(dest
));
291 assert(in_own_cluster(dest
));
292 assert(in_own_cluster(c_ptr
->addr
));
293 if (highest
<= LOWEST_SLAVE
)
295 buf
= tipc_cltr_prepare_routing_msg(highest
- LOWEST_SLAVE
+ 1,
299 msg_set_remote_node(msg
, c_ptr
->addr
);
300 msg_set_type(msg
, SLAVE_ROUTING_TABLE
);
301 for (n_num
= LOWEST_SLAVE
; n_num
<= highest
; n_num
++) {
302 if (c_ptr
->nodes
[n_num
] &&
303 tipc_node_has_active_links(c_ptr
->nodes
[n_num
])) {
305 msg_set_dataoctet(msg
, n_num
);
309 tipc_link_send(buf
, dest
, dest
);
313 warn("Memory squeeze: broadcast of lost route failed\n");
317 void tipc_cltr_send_ext_routes(struct cluster
*c_ptr
, u32 dest
)
320 struct tipc_msg
*msg
;
321 u32 highest
= c_ptr
->highest_node
;
325 if (in_own_cluster(c_ptr
->addr
))
327 assert(!is_slave(dest
));
328 assert(in_own_cluster(dest
));
329 highest
= c_ptr
->highest_node
;
330 buf
= tipc_cltr_prepare_routing_msg(highest
+ 1, c_ptr
->addr
);
333 msg_set_remote_node(msg
, c_ptr
->addr
);
334 msg_set_type(msg
, EXT_ROUTING_TABLE
);
335 for (n_num
= 1; n_num
<= highest
; n_num
++) {
336 if (c_ptr
->nodes
[n_num
] &&
337 tipc_node_has_active_links(c_ptr
->nodes
[n_num
])) {
339 msg_set_dataoctet(msg
, n_num
);
343 tipc_link_send(buf
, dest
, dest
);
347 warn("Memory squeeze: broadcast of external route failed\n");
351 void tipc_cltr_send_local_routes(struct cluster
*c_ptr
, u32 dest
)
354 struct tipc_msg
*msg
;
355 u32 highest
= c_ptr
->highest_node
;
359 assert(is_slave(dest
));
360 assert(in_own_cluster(c_ptr
->addr
));
361 buf
= tipc_cltr_prepare_routing_msg(highest
, c_ptr
->addr
);
364 msg_set_remote_node(msg
, c_ptr
->addr
);
365 msg_set_type(msg
, LOCAL_ROUTING_TABLE
);
366 for (n_num
= 1; n_num
<= highest
; n_num
++) {
367 if (c_ptr
->nodes
[n_num
] &&
368 tipc_node_has_active_links(c_ptr
->nodes
[n_num
])) {
370 msg_set_dataoctet(msg
, n_num
);
374 tipc_link_send(buf
, dest
, dest
);
378 warn("Memory squeeze: broadcast of local route failed\n");
382 void tipc_cltr_recv_routing_table(struct sk_buff
*buf
)
384 struct tipc_msg
*msg
= buf_msg(buf
);
385 struct cluster
*c_ptr
;
390 u32 rem_node
= msg_remote_node(msg
);
395 c_ptr
= tipc_cltr_find(rem_node
);
397 c_ptr
= tipc_cltr_create(rem_node
);
404 node_table
= buf
->data
+ msg_hdr_sz(msg
);
405 table_size
= msg_size(msg
) - msg_hdr_sz(msg
);
406 router
= msg_prevnode(msg
);
407 z_num
= tipc_zone(rem_node
);
408 c_num
= tipc_cluster(rem_node
);
410 switch (msg_type(msg
)) {
411 case LOCAL_ROUTING_TABLE
:
412 assert(is_slave(tipc_own_addr
));
413 case EXT_ROUTING_TABLE
:
414 for (n_num
= 1; n_num
< table_size
; n_num
++) {
415 if (node_table
[n_num
]) {
416 u32 addr
= tipc_addr(z_num
, c_num
, n_num
);
417 n_ptr
= c_ptr
->nodes
[n_num
];
419 n_ptr
= tipc_node_create(addr
);
422 tipc_node_add_router(n_ptr
, router
);
426 case SLAVE_ROUTING_TABLE
:
427 assert(!is_slave(tipc_own_addr
));
428 assert(in_own_cluster(c_ptr
->addr
));
429 for (n_num
= 1; n_num
< table_size
; n_num
++) {
430 if (node_table
[n_num
]) {
431 u32 slave_num
= n_num
+ LOWEST_SLAVE
;
432 u32 addr
= tipc_addr(z_num
, c_num
, slave_num
);
433 n_ptr
= c_ptr
->nodes
[slave_num
];
435 n_ptr
= tipc_node_create(addr
);
438 tipc_node_add_router(n_ptr
, router
);
443 if (!is_slave(tipc_own_addr
)) {
444 assert(!in_own_cluster(c_ptr
->addr
)
445 || is_slave(rem_node
));
447 assert(in_own_cluster(c_ptr
->addr
)
448 && !is_slave(rem_node
));
450 n_ptr
= c_ptr
->nodes
[tipc_node(rem_node
)];
452 n_ptr
= tipc_node_create(rem_node
);
454 tipc_node_add_router(n_ptr
, router
);
457 if (!is_slave(tipc_own_addr
)) {
458 assert(!in_own_cluster(c_ptr
->addr
)
459 || is_slave(rem_node
));
461 assert(in_own_cluster(c_ptr
->addr
)
462 && !is_slave(rem_node
));
464 n_ptr
= c_ptr
->nodes
[tipc_node(rem_node
)];
466 tipc_node_remove_router(n_ptr
, router
);
469 assert(!"Illegal routing manager message received\n");
474 void tipc_cltr_remove_as_router(struct cluster
*c_ptr
, u32 router
)
480 if (is_slave(router
))
481 return; /* Slave nodes can not be routers */
483 if (in_own_cluster(c_ptr
->addr
)) {
484 start_entry
= LOWEST_SLAVE
;
485 tstop
= c_ptr
->highest_slave
;
488 tstop
= c_ptr
->highest_node
;
491 for (n_num
= start_entry
; n_num
<= tstop
; n_num
++) {
492 if (c_ptr
->nodes
[n_num
]) {
493 tipc_node_remove_router(c_ptr
->nodes
[n_num
], router
);
499 * tipc_cltr_multicast - multicast message to local nodes
502 static void tipc_cltr_multicast(struct cluster
*c_ptr
, struct sk_buff
*buf
,
503 u32 lower
, u32 upper
)
505 struct sk_buff
*buf_copy
;
510 assert(lower
<= upper
);
511 assert(((lower
>= 1) && (lower
<= tipc_max_nodes
)) ||
512 ((lower
>= LOWEST_SLAVE
) && (lower
<= tipc_highest_allowed_slave
)));
513 assert(((upper
>= 1) && (upper
<= tipc_max_nodes
)) ||
514 ((upper
>= LOWEST_SLAVE
) && (upper
<= tipc_highest_allowed_slave
)));
515 assert(in_own_cluster(c_ptr
->addr
));
517 tstop
= is_slave(upper
) ? c_ptr
->highest_slave
: c_ptr
->highest_node
;
520 for (n_num
= lower
; n_num
<= tstop
; n_num
++) {
521 n_ptr
= c_ptr
->nodes
[n_num
];
522 if (n_ptr
&& tipc_node_has_active_links(n_ptr
)) {
523 buf_copy
= skb_copy(buf
, GFP_ATOMIC
);
524 if (buf_copy
== NULL
)
526 msg_set_destnode(buf_msg(buf_copy
), n_ptr
->addr
);
527 tipc_link_send(buf_copy
, n_ptr
->addr
, n_ptr
->addr
);
534 * tipc_cltr_broadcast - broadcast message to all nodes within cluster
537 void tipc_cltr_broadcast(struct sk_buff
*buf
)
539 struct sk_buff
*buf_copy
;
540 struct cluster
*c_ptr
;
547 if (tipc_mode
== TIPC_NET_MODE
) {
548 c_ptr
= tipc_cltr_find(tipc_own_addr
);
549 assert(in_own_cluster(c_ptr
->addr
)); /* For now */
551 /* Send to standard nodes, then repeat loop sending to slaves */
553 tstop
= c_ptr
->highest_node
;
554 for (node_type
= 1; node_type
<= 2; node_type
++) {
555 for (n_num
= tstart
; n_num
<= tstop
; n_num
++) {
556 n_ptr
= c_ptr
->nodes
[n_num
];
557 if (n_ptr
&& tipc_node_has_active_links(n_ptr
)) {
558 buf_copy
= skb_copy(buf
, GFP_ATOMIC
);
559 if (buf_copy
== NULL
)
561 msg_set_destnode(buf_msg(buf_copy
),
563 tipc_link_send(buf_copy
, n_ptr
->addr
,
567 tstart
= LOWEST_SLAVE
;
568 tstop
= c_ptr
->highest_slave
;
575 int tipc_cltr_init(void)
577 tipc_highest_allowed_slave
= LOWEST_SLAVE
+ tipc_max_slaves
;
578 return tipc_cltr_create(tipc_own_addr
) ? TIPC_OK
: -ENOMEM
;