aboutsummaryrefslogtreecommitdiffstats
path: root/net/tipc/cluster.c
diff options
context:
space:
mode:
authorPer Liden <per.liden@nospam.ericsson.com>2006-01-02 13:04:38 -0500
committerDavid S. Miller <davem@sunset.davemloft.net>2006-01-12 17:06:31 -0500
commitb97bf3fd8f6a16966d4f18983b2c40993ff937d4 (patch)
tree59959f8a0f3087455efdcb430846686f303c5991 /net/tipc/cluster.c
parent58cba4650a7a414eabd2b40cc9d8e45fcdf192d9 (diff)
[TIPC] Initial merge
TIPC (Transparent Inter Process Communication) is a protocol designed for intra cluster communication. For more information see http://tipc.sourceforge.net Signed-off-by: Per Liden <per.liden@nospam.ericsson.com>
Diffstat (limited to 'net/tipc/cluster.c')
-rw-r--r--net/tipc/cluster.c573
1 files changed, 573 insertions, 0 deletions
diff --git a/net/tipc/cluster.c b/net/tipc/cluster.c
new file mode 100644
index 000000000000..d7d0f5f17e00
--- /dev/null
+++ b/net/tipc/cluster.c
@@ -0,0 +1,573 @@
1/*
2 * net/tipc/cluster.c: TIPC cluster management routines
3 *
4 * Copyright (c) 2003-2005, Ericsson Research Canada
5 * Copyright (c) 2005, Wind River Systems
6 * Copyright (c) 2005-2006, Ericsson AB
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions are met:
11 *
12 * Redistributions of source code must retain the above copyright notice, this
13 * list of conditions and the following disclaimer.
14 * Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
17 * Neither the names of the copyright holders nor the names of its
18 * contributors may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 */
33
34#include "core.h"
35#include "cluster.h"
36#include "addr.h"
37#include "node_subscr.h"
38#include "link.h"
39#include "node.h"
40#include "net.h"
41#include "msg.h"
42#include "bearer.h"
43
44void cluster_multicast(struct cluster *c_ptr, struct sk_buff *buf,
45 u32 lower, u32 upper);
46struct sk_buff *cluster_prepare_routing_msg(u32 data_size, u32 dest);
47
48struct node **local_nodes = 0;
49struct node_map cluster_bcast_nodes = {0,{0,}};
50u32 highest_allowed_slave = 0;
51
52struct cluster *cluster_create(u32 addr)
53{
54 struct _zone *z_ptr;
55 struct cluster *c_ptr;
56 int max_nodes;
57 int alloc;
58
59 c_ptr = (struct cluster *)kmalloc(sizeof(*c_ptr), GFP_ATOMIC);
60 if (c_ptr == NULL)
61 return 0;
62 memset(c_ptr, 0, sizeof(*c_ptr));
63
64 c_ptr->addr = tipc_addr(tipc_zone(addr), tipc_cluster(addr), 0);
65 if (in_own_cluster(addr))
66 max_nodes = LOWEST_SLAVE + tipc_max_slaves;
67 else
68 max_nodes = tipc_max_nodes + 1;
69 alloc = sizeof(void *) * (max_nodes + 1);
70 c_ptr->nodes = (struct node **)kmalloc(alloc, GFP_ATOMIC);
71 if (c_ptr->nodes == NULL) {
72 kfree(c_ptr);
73 return 0;
74 }
75 memset(c_ptr->nodes, 0, alloc);
76 if (in_own_cluster(addr))
77 local_nodes = c_ptr->nodes;
78 c_ptr->highest_slave = LOWEST_SLAVE - 1;
79 c_ptr->highest_node = 0;
80
81 z_ptr = zone_find(tipc_zone(addr));
82 if (z_ptr == NULL) {
83 z_ptr = zone_create(addr);
84 }
85 if (z_ptr != NULL) {
86 zone_attach_cluster(z_ptr, c_ptr);
87 c_ptr->owner = z_ptr;
88 }
89 else {
90 kfree(c_ptr);
91 c_ptr = 0;
92 }
93
94 return c_ptr;
95}
96
97void cluster_delete(struct cluster *c_ptr)
98{
99 u32 n_num;
100
101 if (!c_ptr)
102 return;
103 for (n_num = 1; n_num <= c_ptr->highest_node; n_num++) {
104 node_delete(c_ptr->nodes[n_num]);
105 }
106 for (n_num = LOWEST_SLAVE; n_num <= c_ptr->highest_slave; n_num++) {
107 node_delete(c_ptr->nodes[n_num]);
108 }
109 kfree(c_ptr->nodes);
110 kfree(c_ptr);
111}
112
113u32 cluster_next_node(struct cluster *c_ptr, u32 addr)
114{
115 struct node *n_ptr;
116 u32 n_num = tipc_node(addr) + 1;
117
118 if (!c_ptr)
119 return addr;
120 for (; n_num <= c_ptr->highest_node; n_num++) {
121 n_ptr = c_ptr->nodes[n_num];
122 if (n_ptr && node_has_active_links(n_ptr))
123 return n_ptr->addr;
124 }
125 for (n_num = 1; n_num < tipc_node(addr); n_num++) {
126 n_ptr = c_ptr->nodes[n_num];
127 if (n_ptr && node_has_active_links(n_ptr))
128 return n_ptr->addr;
129 }
130 return 0;
131}
132
133void cluster_attach_node(struct cluster *c_ptr, struct node *n_ptr)
134{
135 u32 n_num = tipc_node(n_ptr->addr);
136 u32 max_n_num = tipc_max_nodes;
137
138 if (in_own_cluster(n_ptr->addr))
139 max_n_num = highest_allowed_slave;
140 assert(n_num > 0);
141 assert(n_num <= max_n_num);
142 assert(c_ptr->nodes[n_num] == 0);
143 c_ptr->nodes[n_num] = n_ptr;
144 if (n_num > c_ptr->highest_node)
145 c_ptr->highest_node = n_num;
146}
147
148/**
149 * cluster_select_router - select router to a cluster
150 *
151 * Uses deterministic and fair algorithm.
152 */
153
154u32 cluster_select_router(struct cluster *c_ptr, u32 ref)
155{
156 u32 n_num;
157 u32 ulim = c_ptr->highest_node;
158 u32 mask;
159 u32 tstart;
160
161 assert(!in_own_cluster(c_ptr->addr));
162 if (!ulim)
163 return 0;
164
165 /* Start entry must be random */
166 mask = tipc_max_nodes;
167 while (mask > ulim)
168 mask >>= 1;
169 tstart = ref & mask;
170 n_num = tstart;
171
172 /* Lookup upwards with wrap-around */
173 do {
174 if (node_is_up(c_ptr->nodes[n_num]))
175 break;
176 } while (++n_num <= ulim);
177 if (n_num > ulim) {
178 n_num = 1;
179 do {
180 if (node_is_up(c_ptr->nodes[n_num]))
181 break;
182 } while (++n_num < tstart);
183 if (n_num == tstart)
184 return 0;
185 }
186 assert(n_num <= ulim);
187 return node_select_router(c_ptr->nodes[n_num], ref);
188}
189
190/**
191 * cluster_select_node - select destination node within a remote cluster
192 *
193 * Uses deterministic and fair algorithm.
194 */
195
196struct node *cluster_select_node(struct cluster *c_ptr, u32 selector)
197{
198 u32 n_num;
199 u32 mask = tipc_max_nodes;
200 u32 start_entry;
201
202 assert(!in_own_cluster(c_ptr->addr));
203 if (!c_ptr->highest_node)
204 return 0;
205
206 /* Start entry must be random */
207 while (mask > c_ptr->highest_node) {
208 mask >>= 1;
209 }
210 start_entry = (selector & mask) ? selector & mask : 1u;
211 assert(start_entry <= c_ptr->highest_node);
212
213 /* Lookup upwards with wrap-around */
214 for (n_num = start_entry; n_num <= c_ptr->highest_node; n_num++) {
215 if (node_has_active_links(c_ptr->nodes[n_num]))
216 return c_ptr->nodes[n_num];
217 }
218 for (n_num = 1; n_num < start_entry; n_num++) {
219 if (node_has_active_links(c_ptr->nodes[n_num]))
220 return c_ptr->nodes[n_num];
221 }
222 return 0;
223}
224
225/*
226 * Routing table management: See description in node.c
227 */
228
229struct sk_buff *cluster_prepare_routing_msg(u32 data_size, u32 dest)
230{
231 u32 size = INT_H_SIZE + data_size;
232 struct sk_buff *buf = buf_acquire(size);
233 struct tipc_msg *msg;
234
235 if (buf) {
236 msg = buf_msg(buf);
237 memset((char *)msg, 0, size);
238 msg_init(msg, ROUTE_DISTRIBUTOR, 0, TIPC_OK, INT_H_SIZE, dest);
239 }
240 return buf;
241}
242
243void cluster_bcast_new_route(struct cluster *c_ptr, u32 dest,
244 u32 lower, u32 upper)
245{
246 struct sk_buff *buf = cluster_prepare_routing_msg(0, c_ptr->addr);
247 struct tipc_msg *msg;
248
249 if (buf) {
250 msg = buf_msg(buf);
251 msg_set_remote_node(msg, dest);
252 msg_set_type(msg, ROUTE_ADDITION);
253 cluster_multicast(c_ptr, buf, lower, upper);
254 } else {
255 warn("Memory squeeze: broadcast of new route failed\n");
256 }
257}
258
259void cluster_bcast_lost_route(struct cluster *c_ptr, u32 dest,
260 u32 lower, u32 upper)
261{
262 struct sk_buff *buf = cluster_prepare_routing_msg(0, c_ptr->addr);
263 struct tipc_msg *msg;
264
265 if (buf) {
266 msg = buf_msg(buf);
267 msg_set_remote_node(msg, dest);
268 msg_set_type(msg, ROUTE_REMOVAL);
269 cluster_multicast(c_ptr, buf, lower, upper);
270 } else {
271 warn("Memory squeeze: broadcast of lost route failed\n");
272 }
273}
274
275void cluster_send_slave_routes(struct cluster *c_ptr, u32 dest)
276{
277 struct sk_buff *buf;
278 struct tipc_msg *msg;
279 u32 highest = c_ptr->highest_slave;
280 u32 n_num;
281 int send = 0;
282
283 assert(!is_slave(dest));
284 assert(in_own_cluster(dest));
285 assert(in_own_cluster(c_ptr->addr));
286 if (highest <= LOWEST_SLAVE)
287 return;
288 buf = cluster_prepare_routing_msg(highest - LOWEST_SLAVE + 1,
289 c_ptr->addr);
290 if (buf) {
291 msg = buf_msg(buf);
292 msg_set_remote_node(msg, c_ptr->addr);
293 msg_set_type(msg, SLAVE_ROUTING_TABLE);
294 for (n_num = LOWEST_SLAVE; n_num <= highest; n_num++) {
295 if (c_ptr->nodes[n_num] &&
296 node_has_active_links(c_ptr->nodes[n_num])) {
297 send = 1;
298 msg_set_dataoctet(msg, n_num);
299 }
300 }
301 if (send)
302 link_send(buf, dest, dest);
303 else
304 buf_discard(buf);
305 } else {
306 warn("Memory squeeze: broadcast of lost route failed\n");
307 }
308}
309
310void cluster_send_ext_routes(struct cluster *c_ptr, u32 dest)
311{
312 struct sk_buff *buf;
313 struct tipc_msg *msg;
314 u32 highest = c_ptr->highest_node;
315 u32 n_num;
316 int send = 0;
317
318 if (in_own_cluster(c_ptr->addr))
319 return;
320 assert(!is_slave(dest));
321 assert(in_own_cluster(dest));
322 highest = c_ptr->highest_node;
323 buf = cluster_prepare_routing_msg(highest + 1, c_ptr->addr);
324 if (buf) {
325 msg = buf_msg(buf);
326 msg_set_remote_node(msg, c_ptr->addr);
327 msg_set_type(msg, EXT_ROUTING_TABLE);
328 for (n_num = 1; n_num <= highest; n_num++) {
329 if (c_ptr->nodes[n_num] &&
330 node_has_active_links(c_ptr->nodes[n_num])) {
331 send = 1;
332 msg_set_dataoctet(msg, n_num);
333 }
334 }
335 if (send)
336 link_send(buf, dest, dest);
337 else
338 buf_discard(buf);
339 } else {
340 warn("Memory squeeze: broadcast of external route failed\n");
341 }
342}
343
344void cluster_send_local_routes(struct cluster *c_ptr, u32 dest)
345{
346 struct sk_buff *buf;
347 struct tipc_msg *msg;
348 u32 highest = c_ptr->highest_node;
349 u32 n_num;
350 int send = 0;
351
352 assert(is_slave(dest));
353 assert(in_own_cluster(c_ptr->addr));
354 buf = cluster_prepare_routing_msg(highest, c_ptr->addr);
355 if (buf) {
356 msg = buf_msg(buf);
357 msg_set_remote_node(msg, c_ptr->addr);
358 msg_set_type(msg, LOCAL_ROUTING_TABLE);
359 for (n_num = 1; n_num <= highest; n_num++) {
360 if (c_ptr->nodes[n_num] &&
361 node_has_active_links(c_ptr->nodes[n_num])) {
362 send = 1;
363 msg_set_dataoctet(msg, n_num);
364 }
365 }
366 if (send)
367 link_send(buf, dest, dest);
368 else
369 buf_discard(buf);
370 } else {
371 warn("Memory squeeze: broadcast of local route failed\n");
372 }
373}
374
375void cluster_recv_routing_table(struct sk_buff *buf)
376{
377 struct tipc_msg *msg = buf_msg(buf);
378 struct cluster *c_ptr;
379 struct node *n_ptr;
380 unchar *node_table;
381 u32 table_size;
382 u32 router;
383 u32 rem_node = msg_remote_node(msg);
384 u32 z_num;
385 u32 c_num;
386 u32 n_num;
387
388 c_ptr = cluster_find(rem_node);
389 if (!c_ptr) {
390 c_ptr = cluster_create(rem_node);
391 if (!c_ptr) {
392 buf_discard(buf);
393 return;
394 }
395 }
396
397 node_table = buf->data + msg_hdr_sz(msg);
398 table_size = msg_size(msg) - msg_hdr_sz(msg);
399 router = msg_prevnode(msg);
400 z_num = tipc_zone(rem_node);
401 c_num = tipc_cluster(rem_node);
402
403 switch (msg_type(msg)) {
404 case LOCAL_ROUTING_TABLE:
405 assert(is_slave(tipc_own_addr));
406 case EXT_ROUTING_TABLE:
407 for (n_num = 1; n_num < table_size; n_num++) {
408 if (node_table[n_num]) {
409 u32 addr = tipc_addr(z_num, c_num, n_num);
410 n_ptr = c_ptr->nodes[n_num];
411 if (!n_ptr) {
412 n_ptr = node_create(addr);
413 }
414 if (n_ptr)
415 node_add_router(n_ptr, router);
416 }
417 }
418 break;
419 case SLAVE_ROUTING_TABLE:
420 assert(!is_slave(tipc_own_addr));
421 assert(in_own_cluster(c_ptr->addr));
422 for (n_num = 1; n_num < table_size; n_num++) {
423 if (node_table[n_num]) {
424 u32 slave_num = n_num + LOWEST_SLAVE;
425 u32 addr = tipc_addr(z_num, c_num, slave_num);
426 n_ptr = c_ptr->nodes[slave_num];
427 if (!n_ptr) {
428 n_ptr = node_create(addr);
429 }
430 if (n_ptr)
431 node_add_router(n_ptr, router);
432 }
433 }
434 break;
435 case ROUTE_ADDITION:
436 if (!is_slave(tipc_own_addr)) {
437 assert(!in_own_cluster(c_ptr->addr)
438 || is_slave(rem_node));
439 } else {
440 assert(in_own_cluster(c_ptr->addr)
441 && !is_slave(rem_node));
442 }
443 n_ptr = c_ptr->nodes[tipc_node(rem_node)];
444 if (!n_ptr)
445 n_ptr = node_create(rem_node);
446 if (n_ptr)
447 node_add_router(n_ptr, router);
448 break;
449 case ROUTE_REMOVAL:
450 if (!is_slave(tipc_own_addr)) {
451 assert(!in_own_cluster(c_ptr->addr)
452 || is_slave(rem_node));
453 } else {
454 assert(in_own_cluster(c_ptr->addr)
455 && !is_slave(rem_node));
456 }
457 n_ptr = c_ptr->nodes[tipc_node(rem_node)];
458 if (n_ptr)
459 node_remove_router(n_ptr, router);
460 break;
461 default:
462 assert(!"Illegal routing manager message received\n");
463 }
464 buf_discard(buf);
465}
466
467void cluster_remove_as_router(struct cluster *c_ptr, u32 router)
468{
469 u32 start_entry;
470 u32 tstop;
471 u32 n_num;
472
473 if (is_slave(router))
474 return; /* Slave nodes can not be routers */
475
476 if (in_own_cluster(c_ptr->addr)) {
477 start_entry = LOWEST_SLAVE;
478 tstop = c_ptr->highest_slave;
479 } else {
480 start_entry = 1;
481 tstop = c_ptr->highest_node;
482 }
483
484 for (n_num = start_entry; n_num <= tstop; n_num++) {
485 if (c_ptr->nodes[n_num]) {
486 node_remove_router(c_ptr->nodes[n_num], router);
487 }
488 }
489}
490
491/**
492 * cluster_multicast - multicast message to local nodes
493 */
494
495void cluster_multicast(struct cluster *c_ptr, struct sk_buff *buf,
496 u32 lower, u32 upper)
497{
498 struct sk_buff *buf_copy;
499 struct node *n_ptr;
500 u32 n_num;
501 u32 tstop;
502
503 assert(lower <= upper);
504 assert(((lower >= 1) && (lower <= tipc_max_nodes)) ||
505 ((lower >= LOWEST_SLAVE) && (lower <= highest_allowed_slave)));
506 assert(((upper >= 1) && (upper <= tipc_max_nodes)) ||
507 ((upper >= LOWEST_SLAVE) && (upper <= highest_allowed_slave)));
508 assert(in_own_cluster(c_ptr->addr));
509
510 tstop = is_slave(upper) ? c_ptr->highest_slave : c_ptr->highest_node;
511 if (tstop > upper)
512 tstop = upper;
513 for (n_num = lower; n_num <= tstop; n_num++) {
514 n_ptr = c_ptr->nodes[n_num];
515 if (n_ptr && node_has_active_links(n_ptr)) {
516 buf_copy = skb_copy(buf, GFP_ATOMIC);
517 if (buf_copy == NULL)
518 break;
519 msg_set_destnode(buf_msg(buf_copy), n_ptr->addr);
520 link_send(buf_copy, n_ptr->addr, n_ptr->addr);
521 }
522 }
523 buf_discard(buf);
524}
525
526/**
527 * cluster_broadcast - broadcast message to all nodes within cluster
528 */
529
530void cluster_broadcast(struct sk_buff *buf)
531{
532 struct sk_buff *buf_copy;
533 struct cluster *c_ptr;
534 struct node *n_ptr;
535 u32 n_num;
536 u32 tstart;
537 u32 tstop;
538 u32 node_type;
539
540 if (tipc_mode == TIPC_NET_MODE) {
541 c_ptr = cluster_find(tipc_own_addr);
542 assert(in_own_cluster(c_ptr->addr)); /* For now */
543
544 /* Send to standard nodes, then repeat loop sending to slaves */
545 tstart = 1;
546 tstop = c_ptr->highest_node;
547 for (node_type = 1; node_type <= 2; node_type++) {
548 for (n_num = tstart; n_num <= tstop; n_num++) {
549 n_ptr = c_ptr->nodes[n_num];
550 if (n_ptr && node_has_active_links(n_ptr)) {
551 buf_copy = skb_copy(buf, GFP_ATOMIC);
552 if (buf_copy == NULL)
553 goto exit;
554 msg_set_destnode(buf_msg(buf_copy),
555 n_ptr->addr);
556 link_send(buf_copy, n_ptr->addr,
557 n_ptr->addr);
558 }
559 }
560 tstart = LOWEST_SLAVE;
561 tstop = c_ptr->highest_slave;
562 }
563 }
564exit:
565 buf_discard(buf);
566}
567
568int cluster_init(void)
569{
570 highest_allowed_slave = LOWEST_SLAVE + tipc_max_slaves;
571 return cluster_create(tipc_own_addr) ? TIPC_OK : -ENOMEM;
572}
573