Root/net/tipc/cluster.c

1/*
2 * net/tipc/cluster.c: TIPC cluster management routines
3 *
4 * Copyright (c) 2000-2006, Ericsson AB
5 * Copyright (c) 2005, Wind River Systems
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
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.
19 *
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.
23 *
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.
35 */
36
37#include "core.h"
38#include "cluster.h"
39#include "addr.h"
40#include "node_subscr.h"
41#include "link.h"
42#include "node.h"
43#include "net.h"
44#include "msg.h"
45#include "bearer.h"
46
47static void tipc_cltr_multicast(struct cluster *c_ptr, struct sk_buff *buf,
48                u32 lower, u32 upper);
49static struct sk_buff *tipc_cltr_prepare_routing_msg(u32 data_size, u32 dest);
50
51struct tipc_node **tipc_local_nodes = NULL;
52struct tipc_node_map tipc_cltr_bcast_nodes = {0,{0,}};
53u32 tipc_highest_allowed_slave = 0;
54
55struct cluster *tipc_cltr_create(u32 addr)
56{
57    struct _zone *z_ptr;
58    struct cluster *c_ptr;
59    int max_nodes;
60
61    c_ptr = kzalloc(sizeof(*c_ptr), GFP_ATOMIC);
62    if (c_ptr == NULL) {
63        warn("Cluster creation failure, no memory\n");
64        return NULL;
65    }
66
67    c_ptr->addr = tipc_addr(tipc_zone(addr), tipc_cluster(addr), 0);
68    if (in_own_cluster(addr))
69        max_nodes = LOWEST_SLAVE + tipc_max_slaves;
70    else
71        max_nodes = tipc_max_nodes + 1;
72
73    c_ptr->nodes = kcalloc(max_nodes + 1, sizeof(void*), GFP_ATOMIC);
74    if (c_ptr->nodes == NULL) {
75        warn("Cluster creation failure, no memory for node area\n");
76        kfree(c_ptr);
77        return NULL;
78    }
79
80    if (in_own_cluster(addr))
81        tipc_local_nodes = c_ptr->nodes;
82    c_ptr->highest_slave = LOWEST_SLAVE - 1;
83    c_ptr->highest_node = 0;
84
85    z_ptr = tipc_zone_find(tipc_zone(addr));
86    if (!z_ptr) {
87        z_ptr = tipc_zone_create(addr);
88    }
89    if (!z_ptr) {
90        kfree(c_ptr->nodes);
91        kfree(c_ptr);
92        return NULL;
93    }
94
95    tipc_zone_attach_cluster(z_ptr, c_ptr);
96    c_ptr->owner = z_ptr;
97    return c_ptr;
98}
99
100void tipc_cltr_delete(struct cluster *c_ptr)
101{
102    u32 n_num;
103
104    if (!c_ptr)
105        return;
106    for (n_num = 1; n_num <= c_ptr->highest_node; n_num++) {
107        tipc_node_delete(c_ptr->nodes[n_num]);
108    }
109    for (n_num = LOWEST_SLAVE; n_num <= c_ptr->highest_slave; n_num++) {
110        tipc_node_delete(c_ptr->nodes[n_num]);
111    }
112    kfree(c_ptr->nodes);
113    kfree(c_ptr);
114}
115
116u32 tipc_cltr_next_node(struct cluster *c_ptr, u32 addr)
117{
118    struct tipc_node *n_ptr;
119    u32 n_num = tipc_node(addr) + 1;
120
121    if (!c_ptr)
122        return addr;
123    for (; n_num <= c_ptr->highest_node; n_num++) {
124        n_ptr = c_ptr->nodes[n_num];
125        if (n_ptr && tipc_node_has_active_links(n_ptr))
126            return n_ptr->addr;
127    }
128    for (n_num = 1; n_num < tipc_node(addr); n_num++) {
129        n_ptr = c_ptr->nodes[n_num];
130        if (n_ptr && tipc_node_has_active_links(n_ptr))
131            return n_ptr->addr;
132    }
133    return 0;
134}
135
136void tipc_cltr_attach_node(struct cluster *c_ptr, struct tipc_node *n_ptr)
137{
138    u32 n_num = tipc_node(n_ptr->addr);
139    u32 max_n_num = tipc_max_nodes;
140
141    if (in_own_cluster(n_ptr->addr))
142        max_n_num = tipc_highest_allowed_slave;
143    assert(n_num > 0);
144    assert(n_num <= max_n_num);
145    assert(c_ptr->nodes[n_num] == NULL);
146    c_ptr->nodes[n_num] = n_ptr;
147    if (n_num > c_ptr->highest_node)
148        c_ptr->highest_node = n_num;
149}
150
151/**
152 * tipc_cltr_select_router - select router to a cluster
153 *
154 * Uses deterministic and fair algorithm.
155 */
156
157u32 tipc_cltr_select_router(struct cluster *c_ptr, u32 ref)
158{
159    u32 n_num;
160    u32 ulim = c_ptr->highest_node;
161    u32 mask;
162    u32 tstart;
163
164    assert(!in_own_cluster(c_ptr->addr));
165    if (!ulim)
166        return 0;
167
168    /* Start entry must be random */
169    mask = tipc_max_nodes;
170    while (mask > ulim)
171        mask >>= 1;
172    tstart = ref & mask;
173    n_num = tstart;
174
175    /* Lookup upwards with wrap-around */
176    do {
177        if (tipc_node_is_up(c_ptr->nodes[n_num]))
178            break;
179    } while (++n_num <= ulim);
180    if (n_num > ulim) {
181        n_num = 1;
182        do {
183            if (tipc_node_is_up(c_ptr->nodes[n_num]))
184                break;
185        } while (++n_num < tstart);
186        if (n_num == tstart)
187            return 0;
188    }
189    assert(n_num <= ulim);
190    return tipc_node_select_router(c_ptr->nodes[n_num], ref);
191}
192
193/**
194 * tipc_cltr_select_node - select destination node within a remote cluster
195 *
196 * Uses deterministic and fair algorithm.
197 */
198
199struct tipc_node *tipc_cltr_select_node(struct cluster *c_ptr, u32 selector)
200{
201    u32 n_num;
202    u32 mask = tipc_max_nodes;
203    u32 start_entry;
204
205    assert(!in_own_cluster(c_ptr->addr));
206    if (!c_ptr->highest_node)
207        return NULL;
208
209    /* Start entry must be random */
210    while (mask > c_ptr->highest_node) {
211        mask >>= 1;
212    }
213    start_entry = (selector & mask) ? selector & mask : 1u;
214    assert(start_entry <= c_ptr->highest_node);
215
216    /* Lookup upwards with wrap-around */
217    for (n_num = start_entry; n_num <= c_ptr->highest_node; n_num++) {
218        if (tipc_node_has_active_links(c_ptr->nodes[n_num]))
219            return c_ptr->nodes[n_num];
220    }
221    for (n_num = 1; n_num < start_entry; n_num++) {
222        if (tipc_node_has_active_links(c_ptr->nodes[n_num]))
223            return c_ptr->nodes[n_num];
224    }
225    return NULL;
226}
227
228/*
229 * Routing table management: See description in node.c
230 */
231
232static struct sk_buff *tipc_cltr_prepare_routing_msg(u32 data_size, u32 dest)
233{
234    u32 size = INT_H_SIZE + data_size;
235    struct sk_buff *buf = buf_acquire(size);
236    struct tipc_msg *msg;
237
238    if (buf) {
239        msg = buf_msg(buf);
240        memset((char *)msg, 0, size);
241        tipc_msg_init(msg, ROUTE_DISTRIBUTOR, 0, INT_H_SIZE, dest);
242    }
243    return buf;
244}
245
246void tipc_cltr_bcast_new_route(struct cluster *c_ptr, u32 dest,
247                 u32 lower, u32 upper)
248{
249    struct sk_buff *buf = tipc_cltr_prepare_routing_msg(0, c_ptr->addr);
250    struct tipc_msg *msg;
251
252    if (buf) {
253        msg = buf_msg(buf);
254        msg_set_remote_node(msg, dest);
255        msg_set_type(msg, ROUTE_ADDITION);
256        tipc_cltr_multicast(c_ptr, buf, lower, upper);
257    } else {
258        warn("Memory squeeze: broadcast of new route failed\n");
259    }
260}
261
262void tipc_cltr_bcast_lost_route(struct cluster *c_ptr, u32 dest,
263                u32 lower, u32 upper)
264{
265    struct sk_buff *buf = tipc_cltr_prepare_routing_msg(0, c_ptr->addr);
266    struct tipc_msg *msg;
267
268    if (buf) {
269        msg = buf_msg(buf);
270        msg_set_remote_node(msg, dest);
271        msg_set_type(msg, ROUTE_REMOVAL);
272        tipc_cltr_multicast(c_ptr, buf, lower, upper);
273    } else {
274        warn("Memory squeeze: broadcast of lost route failed\n");
275    }
276}
277
278void tipc_cltr_send_slave_routes(struct cluster *c_ptr, u32 dest)
279{
280    struct sk_buff *buf;
281    struct tipc_msg *msg;
282    u32 highest = c_ptr->highest_slave;
283    u32 n_num;
284    int send = 0;
285
286    assert(!is_slave(dest));
287    assert(in_own_cluster(dest));
288    assert(in_own_cluster(c_ptr->addr));
289    if (highest <= LOWEST_SLAVE)
290        return;
291    buf = tipc_cltr_prepare_routing_msg(highest - LOWEST_SLAVE + 1,
292                        c_ptr->addr);
293    if (buf) {
294        msg = buf_msg(buf);
295        msg_set_remote_node(msg, c_ptr->addr);
296        msg_set_type(msg, SLAVE_ROUTING_TABLE);
297        for (n_num = LOWEST_SLAVE; n_num <= highest; n_num++) {
298            if (c_ptr->nodes[n_num] &&
299                tipc_node_has_active_links(c_ptr->nodes[n_num])) {
300                send = 1;
301                msg_set_dataoctet(msg, n_num);
302            }
303        }
304        if (send)
305            tipc_link_send(buf, dest, dest);
306        else
307            buf_discard(buf);
308    } else {
309        warn("Memory squeeze: broadcast of lost route failed\n");
310    }
311}
312
313void tipc_cltr_send_ext_routes(struct cluster *c_ptr, u32 dest)
314{
315    struct sk_buff *buf;
316    struct tipc_msg *msg;
317    u32 highest = c_ptr->highest_node;
318    u32 n_num;
319    int send = 0;
320
321    if (in_own_cluster(c_ptr->addr))
322        return;
323    assert(!is_slave(dest));
324    assert(in_own_cluster(dest));
325    highest = c_ptr->highest_node;
326    buf = tipc_cltr_prepare_routing_msg(highest + 1, c_ptr->addr);
327    if (buf) {
328        msg = buf_msg(buf);
329        msg_set_remote_node(msg, c_ptr->addr);
330        msg_set_type(msg, EXT_ROUTING_TABLE);
331        for (n_num = 1; n_num <= highest; n_num++) {
332            if (c_ptr->nodes[n_num] &&
333                tipc_node_has_active_links(c_ptr->nodes[n_num])) {
334                send = 1;
335                msg_set_dataoctet(msg, n_num);
336            }
337        }
338        if (send)
339            tipc_link_send(buf, dest, dest);
340        else
341            buf_discard(buf);
342    } else {
343        warn("Memory squeeze: broadcast of external route failed\n");
344    }
345}
346
347void tipc_cltr_send_local_routes(struct cluster *c_ptr, u32 dest)
348{
349    struct sk_buff *buf;
350    struct tipc_msg *msg;
351    u32 highest = c_ptr->highest_node;
352    u32 n_num;
353    int send = 0;
354
355    assert(is_slave(dest));
356    assert(in_own_cluster(c_ptr->addr));
357    buf = tipc_cltr_prepare_routing_msg(highest, c_ptr->addr);
358    if (buf) {
359        msg = buf_msg(buf);
360        msg_set_remote_node(msg, c_ptr->addr);
361        msg_set_type(msg, LOCAL_ROUTING_TABLE);
362        for (n_num = 1; n_num <= highest; n_num++) {
363            if (c_ptr->nodes[n_num] &&
364                tipc_node_has_active_links(c_ptr->nodes[n_num])) {
365                send = 1;
366                msg_set_dataoctet(msg, n_num);
367            }
368        }
369        if (send)
370            tipc_link_send(buf, dest, dest);
371        else
372            buf_discard(buf);
373    } else {
374        warn("Memory squeeze: broadcast of local route failed\n");
375    }
376}
377
378void tipc_cltr_recv_routing_table(struct sk_buff *buf)
379{
380    struct tipc_msg *msg = buf_msg(buf);
381    struct cluster *c_ptr;
382    struct tipc_node *n_ptr;
383    unchar *node_table;
384    u32 table_size;
385    u32 router;
386    u32 rem_node = msg_remote_node(msg);
387    u32 z_num;
388    u32 c_num;
389    u32 n_num;
390
391    c_ptr = tipc_cltr_find(rem_node);
392    if (!c_ptr) {
393        c_ptr = tipc_cltr_create(rem_node);
394        if (!c_ptr) {
395            buf_discard(buf);
396            return;
397        }
398    }
399
400    node_table = buf->data + msg_hdr_sz(msg);
401    table_size = msg_size(msg) - msg_hdr_sz(msg);
402    router = msg_prevnode(msg);
403    z_num = tipc_zone(rem_node);
404    c_num = tipc_cluster(rem_node);
405
406    switch (msg_type(msg)) {
407    case LOCAL_ROUTING_TABLE:
408        assert(is_slave(tipc_own_addr));
409    case EXT_ROUTING_TABLE:
410        for (n_num = 1; n_num < table_size; n_num++) {
411            if (node_table[n_num]) {
412                u32 addr = tipc_addr(z_num, c_num, n_num);
413                n_ptr = c_ptr->nodes[n_num];
414                if (!n_ptr) {
415                    n_ptr = tipc_node_create(addr);
416                }
417                if (n_ptr)
418                    tipc_node_add_router(n_ptr, router);
419            }
420        }
421        break;
422    case SLAVE_ROUTING_TABLE:
423        assert(!is_slave(tipc_own_addr));
424        assert(in_own_cluster(c_ptr->addr));
425        for (n_num = 1; n_num < table_size; n_num++) {
426            if (node_table[n_num]) {
427                u32 slave_num = n_num + LOWEST_SLAVE;
428                u32 addr = tipc_addr(z_num, c_num, slave_num);
429                n_ptr = c_ptr->nodes[slave_num];
430                if (!n_ptr) {
431                    n_ptr = tipc_node_create(addr);
432                }
433                if (n_ptr)
434                    tipc_node_add_router(n_ptr, router);
435            }
436        }
437        break;
438    case ROUTE_ADDITION:
439        if (!is_slave(tipc_own_addr)) {
440            assert(!in_own_cluster(c_ptr->addr) ||
441                   is_slave(rem_node));
442        } else {
443            assert(in_own_cluster(c_ptr->addr) &&
444                   !is_slave(rem_node));
445        }
446        n_ptr = c_ptr->nodes[tipc_node(rem_node)];
447        if (!n_ptr)
448            n_ptr = tipc_node_create(rem_node);
449        if (n_ptr)
450            tipc_node_add_router(n_ptr, router);
451        break;
452    case ROUTE_REMOVAL:
453        if (!is_slave(tipc_own_addr)) {
454            assert(!in_own_cluster(c_ptr->addr) ||
455                   is_slave(rem_node));
456        } else {
457            assert(in_own_cluster(c_ptr->addr) &&
458                   !is_slave(rem_node));
459        }
460        n_ptr = c_ptr->nodes[tipc_node(rem_node)];
461        if (n_ptr)
462            tipc_node_remove_router(n_ptr, router);
463        break;
464    default:
465        assert(!"Illegal routing manager message received\n");
466    }
467    buf_discard(buf);
468}
469
470void tipc_cltr_remove_as_router(struct cluster *c_ptr, u32 router)
471{
472    u32 start_entry;
473    u32 tstop;
474    u32 n_num;
475
476    if (is_slave(router))
477        return; /* Slave nodes can not be routers */
478
479    if (in_own_cluster(c_ptr->addr)) {
480        start_entry = LOWEST_SLAVE;
481        tstop = c_ptr->highest_slave;
482    } else {
483        start_entry = 1;
484        tstop = c_ptr->highest_node;
485    }
486
487    for (n_num = start_entry; n_num <= tstop; n_num++) {
488        if (c_ptr->nodes[n_num]) {
489            tipc_node_remove_router(c_ptr->nodes[n_num], router);
490        }
491    }
492}
493
494/**
495 * tipc_cltr_multicast - multicast message to local nodes
496 */
497
498static void tipc_cltr_multicast(struct cluster *c_ptr, struct sk_buff *buf,
499             u32 lower, u32 upper)
500{
501    struct sk_buff *buf_copy;
502    struct tipc_node *n_ptr;
503    u32 n_num;
504    u32 tstop;
505
506    assert(lower <= upper);
507    assert(((lower >= 1) && (lower <= tipc_max_nodes)) ||
508           ((lower >= LOWEST_SLAVE) && (lower <= tipc_highest_allowed_slave)));
509    assert(((upper >= 1) && (upper <= tipc_max_nodes)) ||
510           ((upper >= LOWEST_SLAVE) && (upper <= tipc_highest_allowed_slave)));
511    assert(in_own_cluster(c_ptr->addr));
512
513    tstop = is_slave(upper) ? c_ptr->highest_slave : c_ptr->highest_node;
514    if (tstop > upper)
515        tstop = upper;
516    for (n_num = lower; n_num <= tstop; n_num++) {
517        n_ptr = c_ptr->nodes[n_num];
518        if (n_ptr && tipc_node_has_active_links(n_ptr)) {
519            buf_copy = skb_copy(buf, GFP_ATOMIC);
520            if (buf_copy == NULL)
521                break;
522            msg_set_destnode(buf_msg(buf_copy), n_ptr->addr);
523            tipc_link_send(buf_copy, n_ptr->addr, n_ptr->addr);
524        }
525    }
526    buf_discard(buf);
527}
528
529/**
530 * tipc_cltr_broadcast - broadcast message to all nodes within cluster
531 */
532
533void tipc_cltr_broadcast(struct sk_buff *buf)
534{
535    struct sk_buff *buf_copy;
536    struct cluster *c_ptr;
537    struct tipc_node *n_ptr;
538    u32 n_num;
539    u32 tstart;
540    u32 tstop;
541    u32 node_type;
542
543    if (tipc_mode == TIPC_NET_MODE) {
544        c_ptr = tipc_cltr_find(tipc_own_addr);
545        assert(in_own_cluster(c_ptr->addr)); /* For now */
546
547        /* Send to standard nodes, then repeat loop sending to slaves */
548        tstart = 1;
549        tstop = c_ptr->highest_node;
550        for (node_type = 1; node_type <= 2; node_type++) {
551            for (n_num = tstart; n_num <= tstop; n_num++) {
552                n_ptr = c_ptr->nodes[n_num];
553                if (n_ptr && tipc_node_has_active_links(n_ptr)) {
554                    buf_copy = skb_copy(buf, GFP_ATOMIC);
555                    if (buf_copy == NULL)
556                        goto exit;
557                    msg_set_destnode(buf_msg(buf_copy),
558                             n_ptr->addr);
559                    tipc_link_send(buf_copy, n_ptr->addr,
560                               n_ptr->addr);
561                }
562            }
563            tstart = LOWEST_SLAVE;
564            tstop = c_ptr->highest_slave;
565        }
566    }
567exit:
568    buf_discard(buf);
569}
570
571int tipc_cltr_init(void)
572{
573    tipc_highest_allowed_slave = LOWEST_SLAVE + tipc_max_slaves;
574    return tipc_cltr_create(tipc_own_addr) ? 0 : -ENOMEM;
575}
576
577

Archive Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9



interactive