Keep statistics of logged warnings
[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
241 /**
242  * Add a tc edge to the database
243  * @param src pointer to source node
244  * @param addr pointer to destination address
245  * @return pointer to TC edge, NULL if out of memory
246  */
247 struct olsrv2_tc_edge *
248 olsrv2_tc_edge_add(struct olsrv2_tc_node *src, struct netaddr *addr) {
249   struct olsrv2_tc_edge *edge = NULL, *inverse = NULL;
250   struct olsrv2_tc_node *dst = NULL;
251   int i;
252
253   edge = avl_find_element(&src->_edges, addr, edge, _node);
254   if (edge != NULL) {
255     edge->virtual = false;
256
257     /* cleanup metric data from other side of the edge */
258     for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
259       edge->cost[i] = RFC7181_METRIC_INFINITE;
260     }
261
262     /* fire event */
263     oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
264     return edge;
265   }
266
267   /* allocate edge */
268   edge = oonf_class_malloc(&_tc_edge_class);
269   if (edge == NULL) {
270     return NULL;
271   }
272
273   /* allocate inverse edge */
274   inverse = oonf_class_malloc(&_tc_edge_class);
275   if (inverse == NULL) {
276     oonf_class_free(&_tc_edge_class, edge);
277     return NULL;
278   }
279
280   /* find or allocate destination node */
281   dst = avl_find_element(&_tc_tree, addr, dst, _originator_node);
282   if (dst == NULL) {
283     /* create virtual node */
284     dst = olsrv2_tc_node_add(addr, 0, 0);
285     if (dst == NULL) {
286       oonf_class_free(&_tc_edge_class, edge);
287       oonf_class_free(&_tc_edge_class, inverse);
288       return NULL;
289     }
290   }
291
292   /* initialize edge */
293   edge->src = src;
294   edge->dst = dst;
295   edge->inverse = inverse;
296   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
297     edge->cost[i] = RFC7181_METRIC_INFINITE;
298   }
299
300   /* hook edge into src node */
301   edge->_node.key = &dst->target.prefix.dst;
302   avl_insert(&src->_edges, &edge->_node);
303
304   /* initialize inverse (virtual) edge */
305   inverse->src = dst;
306   inverse->dst = src;
307   inverse->inverse = edge;
308   inverse->virtual = true;
309   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
310     inverse->cost[i] = RFC7181_METRIC_INFINITE;
311   }
312
313   /* hook inverse edge into dst node */
314   inverse->_node.key = &src->target.prefix.dst;
315   avl_insert(&dst->_edges, &inverse->_node);
316
317   /* fire event */
318   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
319   return edge;
320 }
321
322 /**
323  * Remove a tc edge from the database
324  * @param edge pointer to tc edge
325  * @return true if destination of edge was removed too
326  */
327 bool
328 olsrv2_tc_edge_remove(struct olsrv2_tc_edge *edge) {
329   return _remove_edge(edge, true);
330 }
331
332 /**
333  * Add an endpoint to a tc node
334  * @param node pointer to tc node
335  * @param prefix address prefix of endpoint
336  * @param mesh true if an interface of a mesh node, #
337  *   false if a local attached network.
338  * @return pointer to tc attachment, NULL if out of memory
339  */
340 struct olsrv2_tc_attachment *
341 olsrv2_tc_endpoint_add(struct olsrv2_tc_node *node,
342     struct os_route_key *prefix, bool mesh) {
343   struct olsrv2_tc_attachment *net;
344   struct olsrv2_tc_endpoint *end;
345   int i;
346
347   net = avl_find_element(&node->_attached_networks, prefix, net, _src_node);
348   if (net != NULL) {
349     return net;
350   }
351
352   net = oonf_class_malloc(&_tc_attached_class);
353   if (net == NULL) {
354     return NULL;
355   }
356
357   end = avl_find_element(&_tc_endpoint_tree, prefix, end, _node);
358   if (end == NULL) {
359     /* create new endpoint */
360     end = oonf_class_malloc(&_tc_endpoint_class);
361     if (end == NULL) {
362       oonf_class_free(&_tc_attached_class, net);
363       return NULL;
364     }
365
366     /* initialize endpoint */
367     end->target.type = mesh ? OLSRV2_ADDRESS_TARGET : OLSRV2_NETWORK_TARGET;
368     avl_init(&end->_attached_networks, os_routing_avl_cmp_route_key, false);
369
370     /* attach to global tree */
371     memcpy(&end->target.prefix, prefix, sizeof(*prefix));
372     end->_node.key = &end->target.prefix;
373     avl_insert(&_tc_endpoint_tree, &end->_node);
374
375     oonf_class_event(&_tc_endpoint_class, end, OONF_OBJECT_ADDED);
376   }
377
378   /* initialize attached network */
379   net->src = node;
380   net->dst = end;
381   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
382     net->cost[i] = RFC7181_METRIC_INFINITE;
383   }
384
385   /* hook into src node */
386   net->_src_node.key = &end->target.prefix;
387   avl_insert(&node->_attached_networks, &net->_src_node);
388
389   /* hook into endpoint */
390   net->_endpoint_node.key = &node->target.prefix;
391   avl_insert(&end->_attached_networks, &net->_endpoint_node);
392
393   /* initialize dijkstra data */
394   olsrv2_routing_dijkstra_node_init(&end->target._dijkstra,
395       &node->target.prefix.dst);
396
397   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_ADDED);
398   return net;
399 }
400
401 /**
402  * Remove a tc attachment from the database
403  * @param net pointer to tc attachment
404  */
405 void
406 olsrv2_tc_endpoint_remove(
407     struct olsrv2_tc_attachment *net) {
408   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_REMOVED);
409
410   /* remove from node */
411   avl_remove(&net->src->_attached_networks, &net->_src_node);
412
413   /* remove from endpoint */
414   avl_remove(&net->dst->_attached_networks, &net->_endpoint_node);
415
416   if (net->dst->_attached_networks.count == 0) {
417     oonf_class_event(&_tc_endpoint_class, net->dst, OONF_OBJECT_REMOVED);
418
419     /* remove endpoint */
420     avl_remove(&_tc_endpoint_tree, &net->dst->_node);
421     oonf_class_free(&_tc_endpoint_class, net->dst);
422   }
423
424   /* free attached network */
425   oonf_class_free(&_tc_attached_class, net);
426 }
427
428 /**
429  * Inform everyone that a tc node changed
430  * @param node tc node
431  */
432 void
433 olsrv2_tc_trigger_change(struct olsrv2_tc_node *node) {
434   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_CHANGED);
435 }
436
437 /**
438  * Get tree of olsrv2 tc nodes
439  * @return node tree
440  */
441 struct avl_tree *
442 olsrv2_tc_get_tree(void) {
443   return &_tc_tree;
444 }
445
446 /**
447  * Get tree of olsrv2 tc endpoints
448  * @return endpoint tree
449  */
450 struct avl_tree *
451 olsrv2_tc_get_endpoint_tree(void) {
452   return &_tc_endpoint_tree;
453 }
454
455
456 /**
457  * Callback triggered when a tc node times out
458  * @param ptr timer instance that fired
459  */
460 static void
461 _cb_tc_node_timeout(struct oonf_timer_instance *ptr) {
462   struct olsrv2_tc_node *node;
463
464   node = container_of(ptr, struct olsrv2_tc_node, _validity_time);
465
466   olsrv2_tc_node_remove(node);
467   olsrv2_routing_trigger_update();
468 }
469
470 /**
471  * Remove a tc edge from the database
472  * @param edge pointer to tc edge
473  * @param cleanup true to remove the destination of the edge too
474  *   if its not needed anymore
475  * @return true if destination was removed, false otherwise
476  */
477 static bool
478 _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup) {
479   bool removed_node = false;
480
481   if (edge->virtual) {
482     /* nothing to do */
483     return false;
484   }
485
486   /* fire event */
487   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_REMOVED);
488
489   if (!edge->inverse->virtual) {
490     /* make this edge virtual */
491     edge->virtual = true;
492
493     return false;
494   }
495
496   /* unhook edge from both sides */
497   avl_remove(&edge->src->_edges, &edge->_node);
498   avl_remove(&edge->dst->_edges, &edge->inverse->_node);
499
500   if (edge->dst->_edges.count == 0 && cleanup
501       && olsrv2_tc_is_node_virtual(edge->dst)) {
502     /*
503      * node is already virtual and has no
504      * incoming links anymore.
505      */
506
507     olsrv2_tc_node_remove(edge->dst);
508     removed_node = true;
509   }
510
511   oonf_class_free(&_tc_edge_class, edge->inverse);
512   oonf_class_free(&_tc_edge_class, edge);
513
514   return removed_node;
515 }
516
517 static void
518 _cb_neighbor_change(void *ptr) {
519   struct nhdp_neighbor *neigh;
520   struct olsrv2_tc_node *tc_node;
521
522   neigh = ptr;
523   if (memcmp(&neigh->originator, &neigh->_old_originator,
524       sizeof(neigh->originator)) == 0) {
525     /* no change */
526     return;
527   }
528
529   /* remove old tc_node if necessary */
530   _cb_neighbor_remove(ptr);
531
532   /* see if we have a new originator */
533   if (netaddr_is_unspec(&neigh->originator)) {
534     return;
535   }
536
537   /* add tc_node if necessary */
538   tc_node = olsrv2_tc_node_get(&neigh->originator);
539   if (!tc_node) {
540     tc_node = olsrv2_tc_node_add(&neigh->originator, 0, 0);
541     if (!tc_node) {
542       return;
543     }
544   }
545
546   /* mark as direct neighbor */
547   tc_node->direct_neighbor = true;
548 }
549
550 static void
551 _cb_neighbor_remove(void *ptr) {
552   struct nhdp_neighbor *neigh;
553   struct olsrv2_tc_node *tc_node;
554
555   neigh = ptr;
556
557   if (netaddr_is_unspec(&neigh->originator)) {
558     return;
559   }
560
561   tc_node = olsrv2_tc_node_get(&neigh->originator);
562   if (!tc_node) {
563     return;
564   }
565
566   tc_node->direct_neighbor = false;
567
568   if (!oonf_timer_is_active(&tc_node->_validity_time)) {
569     /* virtual node, kill it */
570     olsrv2_tc_node_remove(tc_node);
571   }
572 }