tipc: Remove internal linked list of node objects
[linux-2.6.git] / net / tipc / node.c
1 /*
2  * net/tipc/node.c: TIPC node management routines
3  *
4  * Copyright (c) 2000-2006, Ericsson AB
5  * Copyright (c) 2005-2006, 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 "config.h"
39 #include "node.h"
40 #include "port.h"
41 #include "name_distr.h"
42
43 static void node_lost_contact(struct tipc_node *n_ptr);
44 static void node_established_contact(struct tipc_node *n_ptr);
45
46 static DEFINE_SPINLOCK(node_create_lock);
47
48 u32 tipc_own_tag = 0;
49
50 /**
51  * tipc_node_create - create neighboring node
52  *
53  * Currently, this routine is called by neighbor discovery code, which holds
54  * net_lock for reading only.  We must take node_create_lock to ensure a node
55  * isn't created twice if two different bearers discover the node at the same
56  * time.  (It would be preferable to switch to holding net_lock in write mode,
57  * but this is a non-trivial change.)
58  */
59
60 struct tipc_node *tipc_node_create(u32 addr)
61 {
62         struct tipc_node *n_ptr;
63         u32 n_num;
64
65         spin_lock_bh(&node_create_lock);
66
67         n_ptr = tipc_node_find(addr);
68         if (n_ptr) {
69                 spin_unlock_bh(&node_create_lock);
70                 return n_ptr;
71         }
72
73         n_ptr = kzalloc(sizeof(*n_ptr), GFP_ATOMIC);
74         if (!n_ptr) {
75                 spin_unlock_bh(&node_create_lock);
76                 warn("Node creation failed, no memory\n");
77                 return NULL;
78         }
79
80         n_ptr->addr = addr;
81         spin_lock_init(&n_ptr->lock);
82         INIT_LIST_HEAD(&n_ptr->nsub);
83
84         n_num = tipc_node(addr);
85         tipc_net.nodes[n_num] = n_ptr;
86         if (n_num > tipc_net.highest_node)
87                 tipc_net.highest_node = n_num;
88
89         spin_unlock_bh(&node_create_lock);
90         return n_ptr;
91 }
92
93 void tipc_node_delete(struct tipc_node *n_ptr)
94 {
95         u32 n_num;
96
97         if (!n_ptr)
98                 return;
99
100         dbg("node %x deleted\n", n_ptr->addr);
101         n_num = tipc_node(n_ptr->addr);
102         tipc_net.nodes[n_num] = NULL;
103         kfree(n_ptr);
104
105         while (!tipc_net.nodes[tipc_net.highest_node])
106                 if (--tipc_net.highest_node == 0)
107                         break;
108 }
109
110
111 /**
112  * tipc_node_link_up - handle addition of link
113  *
114  * Link becomes active (alone or shared) or standby, depending on its priority.
115  */
116
117 void tipc_node_link_up(struct tipc_node *n_ptr, struct link *l_ptr)
118 {
119         struct link **active = &n_ptr->active_links[0];
120
121         n_ptr->working_links++;
122
123         info("Established link <%s> on network plane %c\n",
124              l_ptr->name, l_ptr->b_ptr->net_plane);
125
126         if (!active[0]) {
127                 dbg(" link %x into %x/%x\n", l_ptr, &active[0], &active[1]);
128                 active[0] = active[1] = l_ptr;
129                 node_established_contact(n_ptr);
130                 return;
131         }
132         if (l_ptr->priority < active[0]->priority) {
133                 info("New link <%s> becomes standby\n", l_ptr->name);
134                 return;
135         }
136         tipc_link_send_duplicate(active[0], l_ptr);
137         if (l_ptr->priority == active[0]->priority) {
138                 active[0] = l_ptr;
139                 return;
140         }
141         info("Old link <%s> becomes standby\n", active[0]->name);
142         if (active[1] != active[0])
143                 info("Old link <%s> becomes standby\n", active[1]->name);
144         active[0] = active[1] = l_ptr;
145 }
146
147 /**
148  * node_select_active_links - select active link
149  */
150
151 static void node_select_active_links(struct tipc_node *n_ptr)
152 {
153         struct link **active = &n_ptr->active_links[0];
154         u32 i;
155         u32 highest_prio = 0;
156
157         active[0] = active[1] = NULL;
158
159         for (i = 0; i < MAX_BEARERS; i++) {
160                 struct link *l_ptr = n_ptr->links[i];
161
162                 if (!l_ptr || !tipc_link_is_up(l_ptr) ||
163                     (l_ptr->priority < highest_prio))
164                         continue;
165
166                 if (l_ptr->priority > highest_prio) {
167                         highest_prio = l_ptr->priority;
168                         active[0] = active[1] = l_ptr;
169                 } else {
170                         active[1] = l_ptr;
171                 }
172         }
173 }
174
175 /**
176  * tipc_node_link_down - handle loss of link
177  */
178
179 void tipc_node_link_down(struct tipc_node *n_ptr, struct link *l_ptr)
180 {
181         struct link **active;
182
183         n_ptr->working_links--;
184
185         if (!tipc_link_is_active(l_ptr)) {
186                 info("Lost standby link <%s> on network plane %c\n",
187                      l_ptr->name, l_ptr->b_ptr->net_plane);
188                 return;
189         }
190         info("Lost link <%s> on network plane %c\n",
191                 l_ptr->name, l_ptr->b_ptr->net_plane);
192
193         active = &n_ptr->active_links[0];
194         if (active[0] == l_ptr)
195                 active[0] = active[1];
196         if (active[1] == l_ptr)
197                 active[1] = active[0];
198         if (active[0] == l_ptr)
199                 node_select_active_links(n_ptr);
200         if (tipc_node_is_up(n_ptr))
201                 tipc_link_changeover(l_ptr);
202         else
203                 node_lost_contact(n_ptr);
204 }
205
206 int tipc_node_has_active_links(struct tipc_node *n_ptr)
207 {
208         return n_ptr->active_links[0] != NULL;
209 }
210
211 int tipc_node_has_redundant_links(struct tipc_node *n_ptr)
212 {
213         return n_ptr->working_links > 1;
214 }
215
216 int tipc_node_is_up(struct tipc_node *n_ptr)
217 {
218         return tipc_node_has_active_links(n_ptr);
219 }
220
221 struct tipc_node *tipc_node_attach_link(struct link *l_ptr)
222 {
223         struct tipc_node *n_ptr = tipc_node_find(l_ptr->addr);
224
225         if (!n_ptr)
226                 n_ptr = tipc_node_create(l_ptr->addr);
227         if (n_ptr) {
228                 u32 bearer_id = l_ptr->b_ptr->identity;
229                 char addr_string[16];
230
231                 if (n_ptr->link_cnt >= 2) {
232                         err("Attempt to create third link to %s\n",
233                             tipc_addr_string_fill(addr_string, n_ptr->addr));
234                         return NULL;
235                 }
236
237                 if (!n_ptr->links[bearer_id]) {
238                         n_ptr->links[bearer_id] = l_ptr;
239                         tipc_net.links++;
240                         n_ptr->link_cnt++;
241                         return n_ptr;
242                 }
243                 err("Attempt to establish second link on <%s> to %s\n",
244                     l_ptr->b_ptr->publ.name,
245                     tipc_addr_string_fill(addr_string, l_ptr->addr));
246         }
247         return NULL;
248 }
249
250 void tipc_node_detach_link(struct tipc_node *n_ptr, struct link *l_ptr)
251 {
252         n_ptr->links[l_ptr->b_ptr->identity] = NULL;
253         tipc_net.links--;
254         n_ptr->link_cnt--;
255 }
256
257 /*
258  * Routing table management - five cases to handle:
259  *
260  * 1: A link towards a zone/cluster external node comes up.
261  *    => Send a multicast message updating routing tables of all
262  *    system nodes within own cluster that the new destination
263  *    can be reached via this node.
264  *    (node.establishedContact()=>cluster.multicastNewRoute())
265  *
266  * 2: A link towards a slave node comes up.
267  *    => Send a multicast message updating routing tables of all
268  *    system nodes within own cluster that the new destination
269  *    can be reached via this node.
270  *    (node.establishedContact()=>cluster.multicastNewRoute())
271  *    => Send a  message to the slave node about existence
272  *    of all system nodes within cluster:
273  *    (node.establishedContact()=>cluster.sendLocalRoutes())
274  *
275  * 3: A new cluster local system node becomes available.
276  *    => Send message(s) to this particular node containing
277  *    information about all cluster external and slave
278  *     nodes which can be reached via this node.
279  *    (node.establishedContact()==>network.sendExternalRoutes())
280  *    (node.establishedContact()==>network.sendSlaveRoutes())
281  *    => Send messages to all directly connected slave nodes
282  *    containing information about the existence of the new node
283  *    (node.establishedContact()=>cluster.multicastNewRoute())
284  *
285  * 4: The link towards a zone/cluster external node or slave
286  *    node goes down.
287  *    => Send a multcast message updating routing tables of all
288  *    nodes within cluster that the new destination can not any
289  *    longer be reached via this node.
290  *    (node.lostAllLinks()=>cluster.bcastLostRoute())
291  *
292  * 5: A cluster local system node becomes unavailable.
293  *    => Remove all references to this node from the local
294  *    routing tables. Note: This is a completely node
295  *    local operation.
296  *    (node.lostAllLinks()=>network.removeAsRouter())
297  *    => Send messages to all directly connected slave nodes
298  *    containing information about loss of the node
299  *    (node.establishedContact()=>cluster.multicastLostRoute())
300  *
301  */
302
303 static void node_established_contact(struct tipc_node *n_ptr)
304 {
305         dbg("node_established_contact:-> %x\n", n_ptr->addr);
306         tipc_k_signal((Handler)tipc_named_node_up, n_ptr->addr);
307
308         /* Syncronize broadcast acks */
309         n_ptr->bclink.acked = tipc_bclink_get_last_sent();
310
311         if (n_ptr->bclink.supported) {
312                 tipc_nmap_add(&tipc_bcast_nmap, n_ptr->addr);
313                 if (n_ptr->addr < tipc_own_addr)
314                         tipc_own_tag++;
315         }
316 }
317
318 static void node_cleanup_finished(unsigned long node_addr)
319 {
320         struct tipc_node *n_ptr;
321
322         read_lock_bh(&tipc_net_lock);
323         n_ptr = tipc_node_find(node_addr);
324         if (n_ptr) {
325                 tipc_node_lock(n_ptr);
326                 n_ptr->cleanup_required = 0;
327                 tipc_node_unlock(n_ptr);
328         }
329         read_unlock_bh(&tipc_net_lock);
330 }
331
332 static void node_lost_contact(struct tipc_node *n_ptr)
333 {
334         struct tipc_node_subscr *ns, *tns;
335         char addr_string[16];
336         u32 i;
337
338         /* Clean up broadcast reception remains */
339         n_ptr->bclink.gap_after = n_ptr->bclink.gap_to = 0;
340         while (n_ptr->bclink.deferred_head) {
341                 struct sk_buff* buf = n_ptr->bclink.deferred_head;
342                 n_ptr->bclink.deferred_head = buf->next;
343                 buf_discard(buf);
344         }
345         if (n_ptr->bclink.defragm) {
346                 buf_discard(n_ptr->bclink.defragm);
347                 n_ptr->bclink.defragm = NULL;
348         }
349
350         if (n_ptr->bclink.supported) {
351                 tipc_bclink_acknowledge(n_ptr,
352                                         mod(n_ptr->bclink.acked + 10000));
353                 tipc_nmap_remove(&tipc_bcast_nmap, n_ptr->addr);
354                 if (n_ptr->addr < tipc_own_addr)
355                         tipc_own_tag--;
356         }
357
358         info("Lost contact with %s\n",
359              tipc_addr_string_fill(addr_string, n_ptr->addr));
360
361         /* Abort link changeover */
362         for (i = 0; i < MAX_BEARERS; i++) {
363                 struct link *l_ptr = n_ptr->links[i];
364                 if (!l_ptr)
365                         continue;
366                 l_ptr->reset_checkpoint = l_ptr->next_in_no;
367                 l_ptr->exp_msg_count = 0;
368                 tipc_link_reset_fragments(l_ptr);
369         }
370
371         /* Notify subscribers */
372         list_for_each_entry_safe(ns, tns, &n_ptr->nsub, nodesub_list) {
373                 ns->node = NULL;
374                 list_del_init(&ns->nodesub_list);
375                 tipc_k_signal((Handler)ns->handle_node_down,
376                               (unsigned long)ns->usr_handle);
377         }
378
379         /* Prevent re-contact with node until all cleanup is done */
380
381         n_ptr->cleanup_required = 1;
382         tipc_k_signal((Handler)node_cleanup_finished, n_ptr->addr);
383 }
384
385 struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space)
386 {
387         u32 domain;
388         struct sk_buff *buf;
389         struct tipc_node *n_ptr;
390         struct tipc_node_info node_info;
391         u32 payload_size;
392         u32 n_num;
393
394         if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
395                 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
396
397         domain = ntohl(*(__be32 *)TLV_DATA(req_tlv_area));
398         if (!tipc_addr_domain_valid(domain))
399                 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
400                                                    " (network address)");
401
402         read_lock_bh(&tipc_net_lock);
403         if (!tipc_net.nodes) {
404                 read_unlock_bh(&tipc_net_lock);
405                 return tipc_cfg_reply_none();
406         }
407
408         /* For now, get space for all other nodes */
409
410         payload_size = TLV_SPACE(sizeof(node_info)) *
411                 (tipc_net.highest_node - 1);
412         if (payload_size > 32768u) {
413                 read_unlock_bh(&tipc_net_lock);
414                 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
415                                                    " (too many nodes)");
416         }
417         buf = tipc_cfg_reply_alloc(payload_size);
418         if (!buf) {
419                 read_unlock_bh(&tipc_net_lock);
420                 return NULL;
421         }
422
423         /* Add TLVs for all nodes in scope */
424
425         for (n_num = 1; n_num <= tipc_net.highest_node; n_num++) {
426                 n_ptr = tipc_net.nodes[n_num];
427                 if (!n_ptr || !tipc_in_scope(domain, n_ptr->addr))
428                         continue;
429                 node_info.addr = htonl(n_ptr->addr);
430                 node_info.up = htonl(tipc_node_is_up(n_ptr));
431                 tipc_cfg_append_tlv(buf, TIPC_TLV_NODE_INFO,
432                                     &node_info, sizeof(node_info));
433         }
434
435         read_unlock_bh(&tipc_net_lock);
436         return buf;
437 }
438
439 struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space)
440 {
441         u32 domain;
442         struct sk_buff *buf;
443         struct tipc_node *n_ptr;
444         struct tipc_link_info link_info;
445         u32 payload_size;
446         u32 n_num;
447
448         if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
449                 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
450
451         domain = ntohl(*(__be32 *)TLV_DATA(req_tlv_area));
452         if (!tipc_addr_domain_valid(domain))
453                 return tipc_cfg_reply_error_string(TIPC_CFG_INVALID_VALUE
454                                                    " (network address)");
455
456         if (tipc_mode != TIPC_NET_MODE)
457                 return tipc_cfg_reply_none();
458
459         read_lock_bh(&tipc_net_lock);
460
461         /* Get space for all unicast links + multicast link */
462
463         payload_size = TLV_SPACE(sizeof(link_info)) * (tipc_net.links + 1);
464         if (payload_size > 32768u) {
465                 read_unlock_bh(&tipc_net_lock);
466                 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
467                                                    " (too many links)");
468         }
469         buf = tipc_cfg_reply_alloc(payload_size);
470         if (!buf) {
471                 read_unlock_bh(&tipc_net_lock);
472                 return NULL;
473         }
474
475         /* Add TLV for broadcast link */
476
477         link_info.dest = htonl(tipc_own_addr & 0xfffff00);
478         link_info.up = htonl(1);
479         strlcpy(link_info.str, tipc_bclink_name, TIPC_MAX_LINK_NAME);
480         tipc_cfg_append_tlv(buf, TIPC_TLV_LINK_INFO, &link_info, sizeof(link_info));
481
482         /* Add TLVs for any other links in scope */
483
484         for (n_num = 1; n_num <= tipc_net.highest_node; n_num++) {
485                 u32 i;
486
487                 n_ptr = tipc_net.nodes[n_num];
488                 if (!n_ptr || !tipc_in_scope(domain, n_ptr->addr))
489                         continue;
490                 tipc_node_lock(n_ptr);
491                 for (i = 0; i < MAX_BEARERS; i++) {
492                         if (!n_ptr->links[i])
493                                 continue;
494                         link_info.dest = htonl(n_ptr->addr);
495                         link_info.up = htonl(tipc_link_is_up(n_ptr->links[i]));
496                         strcpy(link_info.str, n_ptr->links[i]->name);
497                         tipc_cfg_append_tlv(buf, TIPC_TLV_LINK_INFO,
498                                             &link_info, sizeof(link_info));
499                 }
500                 tipc_node_unlock(n_ptr);
501         }
502
503         read_unlock_bh(&tipc_net_lock);
504         return buf;
505 }