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