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 "link.h"
  40
  41 static void tipc_cltr_multicast(struct cluster *c_ptr, struct sk_buff *buf,
  42                                 u32 lower, u32 upper);
  43
  44 struct tipc_node **tipc_local_nodes = NULL;
  45 struct tipc_node_map tipc_cltr_bcast_nodes = {0,{0,}};
  46
  47 struct cluster *tipc_cltr_create(u32 addr)
  48 {
  49         struct cluster *c_ptr;
  50         int max_nodes;
  51
  52         c_ptr = kzalloc(sizeof(*c_ptr), GFP_ATOMIC);
  53         if (c_ptr == NULL) {
  54                 warn("Cluster creation failure, no memory\n");
  55                 return NULL;
  56         }
  57
  58         c_ptr->addr = tipc_addr(tipc_zone(addr), tipc_cluster(addr), 0);
  59         max_nodes = tipc_max_nodes + 1;
  60
  61         c_ptr->nodes = kcalloc(max_nodes + 1, sizeof(void*), GFP_ATOMIC);
  62         if (c_ptr->nodes == NULL) {
  63                 warn("Cluster creation failure, no memory for node area\n");
  64                 kfree(c_ptr);
  65                 return NULL;
  66         }
  67
  68         if (in_own_cluster(addr))
  69                 tipc_local_nodes = c_ptr->nodes;
  70         c_ptr->highest_node = 0;
  71
  72         tipc_net.clusters[1] = c_ptr;
  73         return c_ptr;
  74 }
  75
  76 void tipc_cltr_delete(struct cluster *c_ptr)
  77 {
  78         u32 n_num;
  79
  80         if (!c_ptr)
  81                 return;
  82         for (n_num = 1; n_num <= c_ptr->highest_node; n_num++) {
  83                 tipc_node_delete(c_ptr->nodes[n_num]);
  84         }
  85         kfree(c_ptr->nodes);
  86         kfree(c_ptr);
  87 }
  88
  89
  90 void tipc_cltr_attach_node(struct cluster *c_ptr, struct tipc_node *n_ptr)
  91 {
  92         u32 n_num = tipc_node(n_ptr->addr);
  93         u32 max_n_num = tipc_max_nodes;
  94
  95         assert(n_num > 0);
  96         assert(n_num <= max_n_num);
  97         assert(c_ptr->nodes[n_num] == NULL);
  98         c_ptr->nodes[n_num] = n_ptr;
  99         if (n_num > c_ptr->highest_node)
 100                 c_ptr->highest_node = n_num;
 101 }
 102
 103 /**
 104  * tipc_cltr_select_router - select router to a cluster
 105  *
 106  * Uses deterministic and fair algorithm.
 107  */
 108
 109 u32 tipc_cltr_select_router(struct cluster *c_ptr, u32 ref)
 110 {
 111         u32 n_num;
 112         u32 ulim = c_ptr->highest_node;
 113         u32 mask;
 114         u32 tstart;
 115
 116         assert(!in_own_cluster(c_ptr->addr));
 117         if (!ulim)
 118                 return 0;
 119
 120         /* Start entry must be random */
 121         mask = tipc_max_nodes;
 122         while (mask > ulim)
 123                 mask >>= 1;
 124         tstart = ref & mask;
 125         n_num = tstart;
 126
 127         /* Lookup upwards with wrap-around */
 128         do {
 129                 if (tipc_node_is_up(c_ptr->nodes[n_num]))
 130                         break;
 131         } while (++n_num <= ulim);
 132         if (n_num > ulim) {
 133                 n_num = 1;
 134                 do {
 135                         if (tipc_node_is_up(c_ptr->nodes[n_num]))
 136                                 break;
 137                 } while (++n_num < tstart);
 138                 if (n_num == tstart)
 139                         return 0;
 140         }
 141         assert(n_num <= ulim);
 142         return tipc_node_select_router(c_ptr->nodes[n_num], ref);
 143 }
 144
 145 /**
 146  * tipc_cltr_select_node - select destination node within a remote cluster
 147  *
 148  * Uses deterministic and fair algorithm.
 149  */
 150
 151 struct tipc_node *tipc_cltr_select_node(struct cluster *c_ptr, u32 selector)
 152 {
 153         u32 n_num;
 154         u32 mask = tipc_max_nodes;
 155         u32 start_entry;
 156
 157         assert(!in_own_cluster(c_ptr->addr));
 158         if (!c_ptr->highest_node)
 159                 return NULL;
 160
 161         /* Start entry must be random */
 162         while (mask > c_ptr->highest_node) {
 163                 mask >>= 1;
 164         }
 165         start_entry = (selector & mask) ? selector & mask : 1u;
 166         assert(start_entry <= c_ptr->highest_node);
 167
 168         /* Lookup upwards with wrap-around */
 169         for (n_num = start_entry; n_num <= c_ptr->highest_node; n_num++) {
 170                 if (tipc_node_has_active_links(c_ptr->nodes[n_num]))
 171                         return c_ptr->nodes[n_num];
 172         }
 173         for (n_num = 1; n_num < start_entry; n_num++) {
 174                 if (tipc_node_has_active_links(c_ptr->nodes[n_num]))
 175                         return c_ptr->nodes[n_num];
 176         }
 177         return NULL;
 178 }
 179
 180 /*
 181  *    Routing table management: See description in node.c
 182  */
 183
 184 static struct sk_buff *tipc_cltr_prepare_routing_msg(u32 data_size, u32 dest)
 185 {
 186         u32 size = INT_H_SIZE + data_size;
 187         struct sk_buff *buf = tipc_buf_acquire(size);
 188         struct tipc_msg *msg;
 189
 190         if (buf) {
 191                 msg = buf_msg(buf);
 192                 memset((char *)msg, 0, size);
 193                 tipc_msg_init(msg, ROUTE_DISTRIBUTOR, 0, INT_H_SIZE, dest);
 194         }
 195         return buf;
 196 }
 197
 198 void tipc_cltr_bcast_new_route(struct cluster *c_ptr, u32 dest,
 199                              u32 lower, u32 upper)
 200 {
 201         struct sk_buff *buf = tipc_cltr_prepare_routing_msg(0, c_ptr->addr);
 202         struct tipc_msg *msg;
 203
 204         if (buf) {
 205                 msg = buf_msg(buf);
 206                 msg_set_remote_node(msg, dest);
 207                 msg_set_type(msg, ROUTE_ADDITION);
 208                 tipc_cltr_multicast(c_ptr, buf, lower, upper);
 209         } else {
 210                 warn("Memory squeeze: broadcast of new route failed\n");
 211         }
 212 }
 213
 214 void tipc_cltr_bcast_lost_route(struct cluster *c_ptr, u32 dest,
 215                                 u32 lower, u32 upper)
 216 {
 217         struct sk_buff *buf = tipc_cltr_prepare_routing_msg(0, c_ptr->addr);
 218         struct tipc_msg *msg;
 219
 220         if (buf) {
 221                 msg = buf_msg(buf);
 222                 msg_set_remote_node(msg, dest);
 223                 msg_set_type(msg, ROUTE_REMOVAL);
 224                 tipc_cltr_multicast(c_ptr, buf, lower, upper);
 225         } else {
 226                 warn("Memory squeeze: broadcast of lost route failed\n");
 227         }
 228 }
 229
 230 void tipc_cltr_send_ext_routes(struct cluster *c_ptr, u32 dest)
 231 {
 232         struct sk_buff *buf;
 233         struct tipc_msg *msg;
 234         u32 highest = c_ptr->highest_node;
 235         u32 n_num;
 236         int send = 0;
 237
 238         if (in_own_cluster(c_ptr->addr))
 239                 return;
 240         assert(in_own_cluster(dest));
 241         highest = c_ptr->highest_node;
 242         buf = tipc_cltr_prepare_routing_msg(highest + 1, c_ptr->addr);
 243         if (buf) {
 244                 msg = buf_msg(buf);
 245                 msg_set_remote_node(msg, c_ptr->addr);
 246                 msg_set_type(msg, EXT_ROUTING_TABLE);
 247                 for (n_num = 1; n_num <= highest; n_num++) {
 248                         if (c_ptr->nodes[n_num] &&
 249                             tipc_node_has_active_links(c_ptr->nodes[n_num])) {
 250                                 send = 1;
 251                                 msg_set_dataoctet(msg, n_num);
 252                         }
 253                 }
 254                 if (send)
 255                         tipc_link_send(buf, dest, dest);
 256                 else
 257                         buf_discard(buf);
 258         } else {
 259                 warn("Memory squeeze: broadcast of external route failed\n");
 260         }
 261 }
 262
 263 void tipc_cltr_recv_routing_table(struct sk_buff *buf)
 264 {
 265         struct tipc_msg *msg = buf_msg(buf);
 266         struct cluster *c_ptr;
 267         struct tipc_node *n_ptr;
 268         unchar *node_table;
 269         u32 table_size;
 270         u32 router;
 271         u32 rem_node = msg_remote_node(msg);
 272         u32 z_num;
 273         u32 c_num;
 274         u32 n_num;
 275
 276         c_ptr = tipc_cltr_find(rem_node);
 277         if (!c_ptr) {
 278                 c_ptr = tipc_cltr_create(rem_node);
 279                 if (!c_ptr) {
 280                         buf_discard(buf);
 281                         return;
 282                 }
 283         }
 284
 285         node_table = buf->data + msg_hdr_sz(msg);
 286         table_size = msg_size(msg) - msg_hdr_sz(msg);
 287         router = msg_prevnode(msg);
 288         z_num = tipc_zone(rem_node);
 289         c_num = tipc_cluster(rem_node);
 290
 291         switch (msg_type(msg)) {
 292         case EXT_ROUTING_TABLE:
 293                 for (n_num = 1; n_num < table_size; n_num++) {
 294                         if (node_table[n_num]) {
 295                                 u32 addr = tipc_addr(z_num, c_num, n_num);
 296                                 n_ptr = c_ptr->nodes[n_num];
 297                                 if (!n_ptr) {
 298                                         n_ptr = tipc_node_create(addr);
 299                                 }
 300                                 if (n_ptr)
 301                                         tipc_node_add_router(n_ptr, router);
 302                         }
 303                 }
 304                 break;
 305         case SLAVE_ROUTING_TABLE:
 306                 assert(in_own_cluster(c_ptr->addr));
 307                 break;
 308         case ROUTE_ADDITION:
 309                 assert(!in_own_cluster(c_ptr->addr));
 310                 n_ptr = c_ptr->nodes[tipc_node(rem_node)];
 311                 if (!n_ptr)
 312                         n_ptr = tipc_node_create(rem_node);
 313                 if (n_ptr)
 314                         tipc_node_add_router(n_ptr, router);
 315                 break;
 316         case ROUTE_REMOVAL:
 317                 assert(!in_own_cluster(c_ptr->addr));
 318                 n_ptr = c_ptr->nodes[tipc_node(rem_node)];
 319                 if (n_ptr)
 320                         tipc_node_remove_router(n_ptr, router);
 321                 break;
 322         default:
 323                 assert(!"Illegal routing manager message received\n");
 324         }
 325         buf_discard(buf);
 326 }
 327
 328 void tipc_cltr_remove_as_router(struct cluster *c_ptr, u32 router)
 329 {
 330         u32 n_num;
 331
 332         if (in_own_cluster(c_ptr->addr))
 333                 return;
 334
 335         for (n_num = 1; n_num <= c_ptr->highest_node; n_num++) {
 336                 if (c_ptr->nodes[n_num]) {
 337                         tipc_node_remove_router(c_ptr->nodes[n_num], router);
 338                 }
 339         }
 340 }
 341
 342 /**
 343  * tipc_cltr_multicast - multicast message to local nodes
 344  */
 345
 346 static void tipc_cltr_multicast(struct cluster *c_ptr, struct sk_buff *buf,
 347                          u32 lower, u32 upper)
 348 {
 349         struct sk_buff *buf_copy;
 350         struct tipc_node *n_ptr;
 351         u32 n_num;
 352         u32 tstop;
 353
 354         assert(lower <= upper);
 355         assert((lower >= 1) && (lower <= tipc_max_nodes));
 356         assert((upper >= 1) && (upper <= tipc_max_nodes));
 357         assert(in_own_cluster(c_ptr->addr));
 358
 359         tstop = c_ptr->highest_node;
 360         if (tstop > upper)
 361                 tstop = upper;
 362         for (n_num = lower; n_num <= tstop; n_num++) {
 363                 n_ptr = c_ptr->nodes[n_num];
 364                 if (n_ptr && tipc_node_has_active_links(n_ptr)) {
 365                         buf_copy = skb_copy(buf, GFP_ATOMIC);
 366                         if (buf_copy == NULL)
 367                                 break;
 368                         msg_set_destnode(buf_msg(buf_copy), n_ptr->addr);
 369                         tipc_link_send(buf_copy, n_ptr->addr, n_ptr->addr);
 370                 }
 371         }
 372         buf_discard(buf);
 373 }
 374
 375 /**
 376  * tipc_cltr_broadcast - broadcast message to all nodes within cluster
 377  */
 378
 379 void tipc_cltr_broadcast(struct sk_buff *buf)
 380 {
 381         struct sk_buff *buf_copy;
 382         struct cluster *c_ptr;
 383         struct tipc_node *n_ptr;
 384         u32 n_num;
 385
 386         if (tipc_mode == TIPC_NET_MODE) {
 387                 c_ptr = tipc_cltr_find(tipc_own_addr);
 388                 assert(in_own_cluster(c_ptr->addr));    /* For now */
 389
 390                 /* Send to nodes */
 391                 for (n_num = 1; n_num <= c_ptr->highest_node; n_num++) {
 392                         n_ptr = c_ptr->nodes[n_num];
 393                         if (n_ptr && tipc_node_has_active_links(n_ptr)) {
 394                                 buf_copy = skb_copy(buf, GFP_ATOMIC);
 395                                 if (buf_copy == NULL)
 396                                         goto exit;
 397                                 msg_set_destnode(buf_msg(buf_copy),
 398                                                  n_ptr->addr);
 399                                 tipc_link_send(buf_copy, n_ptr->addr,
 400                                                n_ptr->addr);
 401                         }
 402                 }
 403         }
 404 exit:
 405         buf_discard(buf);
 406 }
 407
 408 int tipc_cltr_init(void)
 409 {
 410         return tipc_cltr_create(tipc_own_addr) ? 0 : -ENOMEM;
 411 }
 412