Merge branch 'master' into mpr_rework
[oonf.git] / src-plugins / olsrv2 / olsrv2 / olsrv2_tc.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 /**
43  * @file
44  */
45
46 #include "common/avl.h"
47 #include "common/avl_comp.h"
48 #include "common/common_types.h"
49 #include "common/netaddr.h"
50 #include "subsystems/oonf_class.h"
51 #include "subsystems/oonf_rfc5444.h"
52 #include "subsystems/oonf_timer.h"
53
54 #include "nhdp/nhdp_domain.h"
55 #include "nhdp/nhdp.h"
56
57 #include "olsrv2/olsrv2_routing.h"
58 #include "olsrv2/olsrv2_tc.h"
59
60 /* prototypes */
61 static void _cb_tc_node_timeout(struct oonf_timer_instance *);
62 static bool _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup);
63
64 static void _cb_neighbor_change(void *ptr);
65 static void _cb_neighbor_remove(void *ptr);
66
67 /* classes for topology data */
68 static struct oonf_class _tc_node_class = {
69   .name = OLSRV2_CLASS_TC_NODE,
70   .size = sizeof(struct olsrv2_tc_node),
71 };
72
73 static struct oonf_class _tc_edge_class = {
74   .name = OLSRV2_CLASS_TC_EDGE,
75   .size = sizeof(struct olsrv2_tc_edge),
76 };
77
78 static struct oonf_class _tc_attached_class = {
79   .name = OLSRV2_CLASS_ATTACHED,
80   .size = sizeof(struct olsrv2_tc_attachment),
81 };
82
83 static struct oonf_class _tc_endpoint_class = {
84   .name = OLSRV2_CLASS_ENDPOINT,
85   .size = sizeof(struct olsrv2_tc_endpoint),
86 };
87
88 /* keep track of direct neighbors */
89 static struct oonf_class_extension _nhdp_neighbor_extension = {
90   .ext_name = "olsrv2_tc tracking",
91   .class_name = NHDP_CLASS_NEIGHBOR,
92   .cb_change = _cb_neighbor_change,
93   .cb_remove = _cb_neighbor_remove,
94 };
95
96 /* validity timer for tc nodes */
97 static struct oonf_timer_class _validity_info = {
98   .name = "olsrv2 tc node validity",
99   .callback = _cb_tc_node_timeout,
100 };
101
102 /* global trees for tc nodes and endpoints */
103 static struct avl_tree _tc_tree;
104 static struct avl_tree _tc_endpoint_tree;
105
106 /**
107  * Initialize tc database
108  */
109 void
110 olsrv2_tc_init(void) {
111   oonf_class_add(&_tc_node_class);
112   oonf_class_add(&_tc_edge_class);
113   oonf_class_add(&_tc_attached_class);
114   oonf_class_add(&_tc_endpoint_class);
115
116   oonf_class_extension_add(&_nhdp_neighbor_extension);
117
118   avl_init(&_tc_tree, avl_comp_netaddr, false);
119   avl_init(&_tc_endpoint_tree, os_routing_avl_cmp_route_key, true);
120 }
121
122 /**
123  * Cleanup tc database
124  */
125 void
126 olsrv2_tc_cleanup(void) {
127   struct olsrv2_tc_node *node, *n_it;
128   struct olsrv2_tc_edge *edge, *e_it;
129   struct olsrv2_tc_attachment *a_end, *ae_it;
130
131   avl_for_each_element(&_tc_tree, node, _originator_node) {
132     avl_for_each_element_safe(&node->_edges, edge, _node, e_it) {
133       /* remove edge without cleaning up the node */
134       _remove_edge(edge, false);
135     }
136
137     avl_for_each_element_safe(&node->_attached_networks, a_end, _src_node, ae_it) {
138       olsrv2_tc_endpoint_remove(a_end);
139     }
140   }
141
142   avl_for_each_element_safe(&_tc_tree, node, _originator_node, n_it) {
143     olsrv2_tc_node_remove(node);
144   }
145
146   oonf_class_extension_remove(&_nhdp_neighbor_extension);
147
148   oonf_class_remove(&_tc_endpoint_class);
149   oonf_class_remove(&_tc_attached_class);
150   oonf_class_remove(&_tc_edge_class);
151   oonf_class_remove(&_tc_node_class);
152 }
153
154 /**
155  * Add a new tc node to the database
156  * @param originator originator address of node
157  * @param vtime validity time for node entry
158  * @param ansn answer set number of node
159  * @return pointer to node, NULL if out of memory
160  */
161 struct olsrv2_tc_node *
162 olsrv2_tc_node_add(struct netaddr *originator,
163     uint64_t vtime, uint16_t ansn) {
164   struct olsrv2_tc_node *node;
165
166   node = avl_find_element(
167       &_tc_tree, originator, node, _originator_node);
168   if (!node) {
169     node = oonf_class_malloc(&_tc_node_class);
170     if (node == NULL) {
171       return NULL;
172     }
173
174     /* copy key and attach it to node */
175     os_routing_init_sourcespec_prefix(&node->target.prefix, originator);
176     node->_originator_node.key = &node->target.prefix.dst;
177
178     /* initialize node */
179     avl_init(&node->_edges, avl_comp_netaddr, false);
180     avl_init(&node->_attached_networks, os_routing_avl_cmp_route_key, false);
181
182     node->_validity_time.class = &_validity_info;
183
184     node->ansn = ansn;
185
186     /* initialize dijkstra data */
187     node->target.type = OLSRV2_NODE_TARGET;
188     olsrv2_routing_dijkstra_node_init(&node->target._dijkstra,
189         &node->target.prefix.dst);
190
191     /* hook into global tree */
192     avl_insert(&_tc_tree, &node->_originator_node);
193
194     /* fire event */
195     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
196   }
197   else if (!oonf_timer_is_active(&node->_validity_time)) {
198     /* node was virtual */
199     node->ansn = ansn;
200
201     /* fire event */
202     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
203   }
204   oonf_timer_set(&node->_validity_time, vtime);
205   return node;
206 }
207
208 /**
209  * Remove a tc node from the database
210  * @param node pointer to node
211  */
212 void
213 olsrv2_tc_node_remove(struct olsrv2_tc_node *node) {
214   struct olsrv2_tc_edge *edge, *edge_it;
215   struct olsrv2_tc_attachment *net, *net_it;
216
217   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_REMOVED);
218
219   /* remove tc_edges */
220   avl_for_each_element_safe(&node->_edges, edge, _node, edge_it) {
221     /* some edges might just become virtual */
222     olsrv2_tc_edge_remove(edge);
223   }
224
225   /* remove attached networks */
226   avl_for_each_element_safe(
227       &node->_attached_networks, net, _src_node, net_it) {
228     olsrv2_tc_endpoint_remove(net);
229   }
230
231   /* stop validity timer */
232   oonf_timer_stop(&node->_validity_time);
233
234   /* remove from global tree and free memory if node is not needed anymore*/
235   if (node->_edges.count == 0 && !node->direct_neighbor) {
236     avl_remove(&_tc_tree, &node->_originator_node);
237     oonf_class_free(&_tc_node_class, node);
238   }
239
240   /* all domains might have changed */
241   olsrv2_routing_domain_changed(NULL);
242 }
243
244 /**
245  * Add a tc edge to the database
246  * @param src pointer to source node
247  * @param addr pointer to destination address
248  * @return pointer to TC edge, NULL if out of memory
249  */
250 struct olsrv2_tc_edge *
251 olsrv2_tc_edge_add(struct olsrv2_tc_node *src, struct netaddr *addr) {
252   struct olsrv2_tc_edge *edge = NULL, *inverse = NULL;
253   struct olsrv2_tc_node *dst = NULL;
254   int i;
255
256   edge = avl_find_element(&src->_edges, addr, edge, _node);
257   if (edge != NULL) {
258     edge->virtual = false;
259
260     /* cleanup metric data from other side of the edge */
261     for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
262       edge->cost[i] = RFC7181_METRIC_INFINITE;
263     }
264
265     /* fire event */
266     oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
267     return edge;
268   }
269
270   /* allocate edge */
271   edge = oonf_class_malloc(&_tc_edge_class);
272   if (edge == NULL) {
273     return NULL;
274   }
275
276   /* allocate inverse edge */
277   inverse = oonf_class_malloc(&_tc_edge_class);
278   if (inverse == NULL) {
279     oonf_class_free(&_tc_edge_class, edge);
280     return NULL;
281   }
282
283   /* find or allocate destination node */
284   dst = avl_find_element(&_tc_tree, addr, dst, _originator_node);
285   if (dst == NULL) {
286     /* create virtual node */
287     dst = olsrv2_tc_node_add(addr, 0, 0);
288     if (dst == NULL) {
289       oonf_class_free(&_tc_edge_class, edge);
290       oonf_class_free(&_tc_edge_class, inverse);
291       return NULL;
292     }
293   }
294
295   /* initialize edge */
296   edge->src = src;
297   edge->dst = dst;
298   edge->inverse = inverse;
299   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
300     edge->cost[i] = RFC7181_METRIC_INFINITE;
301   }
302
303   /* hook edge into src node */
304   edge->_node.key = &dst->target.prefix.dst;
305   avl_insert(&src->_edges, &edge->_node);
306
307   /* initialize inverse (virtual) edge */
308   inverse->src = dst;
309   inverse->dst = src;
310   inverse->inverse = edge;
311   inverse->virtual = true;
312   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
313     inverse->cost[i] = RFC7181_METRIC_INFINITE;
314   }
315
316   /* hook inverse edge into dst node */
317   inverse->_node.key = &src->target.prefix.dst;
318   avl_insert(&dst->_edges, &inverse->_node);
319
320   /* fire event */
321   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
322   return edge;
323 }
324
325 /**
326  * Remove a tc edge from the database
327  * @param edge pointer to tc edge
328  * @return true if destination of edge was removed too
329  */
330 bool
331 olsrv2_tc_edge_remove(struct olsrv2_tc_edge *edge) {
332   /* all domains might have changed */
333   olsrv2_routing_domain_changed(NULL);
334
335   return _remove_edge(edge, true);
336 }
337
338 /**
339  * Add an endpoint to a tc node
340  * @param node pointer to tc node
341  * @param prefix address prefix of endpoint
342  * @param mesh true if an interface of a mesh node, #
343  *   false if a local attached network.
344  * @return pointer to tc attachment, NULL if out of memory
345  */
346 struct olsrv2_tc_attachment *
347 olsrv2_tc_endpoint_add(struct olsrv2_tc_node *node,
348     struct os_route_key *prefix, bool mesh) {
349   struct olsrv2_tc_attachment *net;
350   struct olsrv2_tc_endpoint *end;
351   int i;
352
353   net = avl_find_element(&node->_attached_networks, prefix, net, _src_node);
354   if (net != NULL) {
355     return net;
356   }
357
358   net = oonf_class_malloc(&_tc_attached_class);
359   if (net == NULL) {
360     return NULL;
361   }
362
363   end = avl_find_element(&_tc_endpoint_tree, prefix, end, _node);
364   if (end == NULL) {
365     /* create new endpoint */
366     end = oonf_class_malloc(&_tc_endpoint_class);
367     if (end == NULL) {
368       oonf_class_free(&_tc_attached_class, net);
369       return NULL;
370     }
371
372     /* initialize endpoint */
373     end->target.type = mesh ? OLSRV2_ADDRESS_TARGET : OLSRV2_NETWORK_TARGET;
374     avl_init(&end->_attached_networks, os_routing_avl_cmp_route_key, false);
375
376     /* attach to global tree */
377     memcpy(&end->target.prefix, prefix, sizeof(*prefix));
378     end->_node.key = &end->target.prefix;
379     avl_insert(&_tc_endpoint_tree, &end->_node);
380
381     oonf_class_event(&_tc_endpoint_class, end, OONF_OBJECT_ADDED);
382   }
383
384   /* initialize attached network */
385   net->src = node;
386   net->dst = end;
387   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
388     net->cost[i] = RFC7181_METRIC_INFINITE;
389   }
390
391   /* hook into src node */
392   net->_src_node.key = &end->target.prefix;
393   avl_insert(&node->_attached_networks, &net->_src_node);
394
395   /* hook into endpoint */
396   net->_endpoint_node.key = &node->target.prefix;
397   avl_insert(&end->_attached_networks, &net->_endpoint_node);
398
399   /* initialize dijkstra data */
400   olsrv2_routing_dijkstra_node_init(&end->target._dijkstra,
401       &node->target.prefix.dst);
402
403   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_ADDED);
404   return net;
405 }
406
407 /**
408  * Remove a tc attachment from the database
409  * @param net pointer to tc attachment
410  */
411 void
412 olsrv2_tc_endpoint_remove(
413     struct olsrv2_tc_attachment *net) {
414   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_REMOVED);
415
416   /* remove from node */
417   avl_remove(&net->src->_attached_networks, &net->_src_node);
418
419   /* remove from endpoint */
420   avl_remove(&net->dst->_attached_networks, &net->_endpoint_node);
421
422   if (net->dst->_attached_networks.count == 0) {
423     oonf_class_event(&_tc_endpoint_class, net->dst, OONF_OBJECT_REMOVED);
424
425     /* remove endpoint */
426     avl_remove(&_tc_endpoint_tree, &net->dst->_node);
427     oonf_class_free(&_tc_endpoint_class, net->dst);
428   }
429
430   /* free attached network */
431   oonf_class_free(&_tc_attached_class, net);
432
433   /* all domains might have changed */
434   olsrv2_routing_domain_changed(NULL);
435 }
436
437 /**
438  * Inform everyone that a tc node changed
439  * @param node tc node
440  */
441 void
442 olsrv2_tc_trigger_change(struct olsrv2_tc_node *node) {
443   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_CHANGED);
444 }
445
446 /**
447  * Get tree of olsrv2 tc nodes
448  * @return node tree
449  */
450 struct avl_tree *
451 olsrv2_tc_get_tree(void) {
452   return &_tc_tree;
453 }
454
455 /**
456  * Get tree of olsrv2 tc endpoints
457  * @return endpoint tree
458  */
459 struct avl_tree *
460 olsrv2_tc_get_endpoint_tree(void) {
461   return &_tc_endpoint_tree;
462 }
463
464
465 /**
466  * Callback triggered when a tc node times out
467  * @param ptr timer instance that fired
468  */
469 static void
470 _cb_tc_node_timeout(struct oonf_timer_instance *ptr) {
471   struct olsrv2_tc_node *node;
472
473   node = container_of(ptr, struct olsrv2_tc_node, _validity_time);
474
475   olsrv2_tc_node_remove(node);
476   olsrv2_routing_trigger_update();
477 }
478
479 /**
480  * Remove a tc edge from the database
481  * @param edge pointer to tc edge
482  * @param cleanup true to remove the destination of the edge too
483  *   if its not needed anymore
484  * @return true if destination was removed, false otherwise
485  */
486 static bool
487 _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup) {
488   bool removed_node = false;
489
490   if (edge->virtual) {
491     /* nothing to do */
492     return false;
493   }
494
495   /* fire event */
496   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_REMOVED);
497
498   if (!edge->inverse->virtual) {
499     /* make this edge virtual */
500     edge->virtual = true;
501
502     return false;
503   }
504
505   /* unhook edge from both sides */
506   avl_remove(&edge->src->_edges, &edge->_node);
507   avl_remove(&edge->dst->_edges, &edge->inverse->_node);
508
509   if (edge->dst->_edges.count == 0 && cleanup
510       && olsrv2_tc_is_node_virtual(edge->dst)) {
511     /*
512      * node is already virtual and has no
513      * incoming links anymore.
514      */
515
516     olsrv2_tc_node_remove(edge->dst);
517     removed_node = true;
518   }
519
520   oonf_class_free(&_tc_edge_class, edge->inverse);
521   oonf_class_free(&_tc_edge_class, edge);
522
523   return removed_node;
524 }
525
526 static void
527 _cb_neighbor_change(void *ptr) {
528   struct nhdp_neighbor *neigh;
529   struct olsrv2_tc_node *tc_node;
530
531   neigh = ptr;
532   if (memcmp(&neigh->originator, &neigh->_old_originator,
533       sizeof(neigh->originator)) == 0) {
534     /* no change */
535     return;
536   }
537
538   /* remove old tc_node if necessary */
539   _cb_neighbor_remove(ptr);
540
541   /* see if we have a new originator */
542   if (netaddr_is_unspec(&neigh->originator)) {
543     return;
544   }
545
546   /* add tc_node if necessary */
547   tc_node = olsrv2_tc_node_get(&neigh->originator);
548   if (!tc_node) {
549     tc_node = olsrv2_tc_node_add(&neigh->originator, 0, 0);
550     if (!tc_node) {
551       return;
552     }
553   }
554
555   /* mark as direct neighbor */
556   tc_node->direct_neighbor = true;
557 }
558
559 static void
560 _cb_neighbor_remove(void *ptr) {
561   struct nhdp_neighbor *neigh;
562   struct olsrv2_tc_node *tc_node;
563
564   neigh = ptr;
565
566   if (netaddr_is_unspec(&neigh->originator)) {
567     return;
568   }
569
570   tc_node = olsrv2_tc_node_get(&neigh->originator);
571   if (!tc_node) {
572     return;
573   }
574
575   tc_node->direct_neighbor = false;
576
577   if (!oonf_timer_is_active(&tc_node->_validity_time)) {
578     /* virtual node, kill it */
579     olsrv2_tc_node_remove(tc_node);
580   }
581 }