656cbbd911759a3d775156375ea7627c2d3aaec4
[oonf.git] / src / 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 <oonf/libcommon/avl.h>
47 #include <oonf/libcommon/avl_comp.h>
48 #include <oonf/oonf.h>
49 #include <oonf/libcommon/netaddr.h>
50 #include <oonf/subsystems/oonf_class.h>
51 #include <oonf/subsystems/oonf_rfc5444.h>
52 #include <oonf/subsystems/oonf_timer.h>
53
54 #include <oonf/nhdp/nhdp/nhdp.h>
55 #include <oonf/nhdp/nhdp/nhdp_domain.h>
56
57 #include <oonf/olsrv2/olsrv2/olsrv2_routing.h>
58 #include <oonf/olsrv2/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, uint64_t vtime, uint16_t ansn) {
163   struct olsrv2_tc_node *node;
164
165   node = avl_find_element(&_tc_tree, originator, node, _originator_node);
166   if (!node) {
167     node = oonf_class_malloc(&_tc_node_class);
168     if (node == NULL) {
169       return NULL;
170     }
171
172     /* copy key and attach it to node */
173     os_routing_init_sourcespec_prefix(&node->target.prefix, originator);
174     node->_originator_node.key = &node->target.prefix.dst;
175
176     /* initialize node */
177     avl_init(&node->_edges, avl_comp_netaddr, false);
178     avl_init(&node->_attached_networks, os_routing_avl_cmp_route_key, false);
179
180     node->_validity_time.class = &_validity_info;
181
182     node->ansn = ansn;
183
184     /* initialize dijkstra data */
185     node->target.type = OLSRV2_NODE_TARGET;
186     olsrv2_routing_dijkstra_node_init(&node->target._dijkstra, &node->target.prefix.dst);
187
188     /* hook into global tree */
189     avl_insert(&_tc_tree, &node->_originator_node);
190
191     /* fire event */
192     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
193   }
194   else if (!oonf_timer_is_active(&node->_validity_time)) {
195     /* node was virtual */
196     node->ansn = ansn;
197
198     /* fire event */
199     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
200   }
201   oonf_timer_set(&node->_validity_time, vtime);
202   return node;
203 }
204
205 /**
206  * Remove a tc node from the database
207  * @param node pointer to node
208  */
209 void
210 olsrv2_tc_node_remove(struct olsrv2_tc_node *node) {
211   struct olsrv2_tc_edge *edge, *edge_it;
212   struct olsrv2_tc_attachment *net, *net_it;
213
214   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_REMOVED);
215
216   /* remove tc_edges */
217   avl_for_each_element_safe(&node->_edges, edge, _node, edge_it) {
218     /* some edges might just become virtual */
219     olsrv2_tc_edge_remove(edge);
220   }
221
222   /* remove attached networks */
223   avl_for_each_element_safe(&node->_attached_networks, net, _src_node, net_it) {
224     olsrv2_tc_endpoint_remove(net);
225   }
226
227   /* stop validity timer */
228   oonf_timer_stop(&node->_validity_time);
229
230   /* remove from global tree and free memory if node is not needed anymore*/
231   if (node->_edges.count == 0 && !node->direct_neighbor) {
232     avl_remove(&_tc_tree, &node->_originator_node);
233     oonf_class_free(&_tc_node_class, node);
234   }
235
236   /* all domains might have changed */
237   olsrv2_routing_domain_changed(NULL, true);
238 }
239
240 /**
241  * Add a tc edge to the database
242  * @param src pointer to source node
243  * @param addr pointer to destination address
244  * @return pointer to TC edge, NULL if out of memory
245  */
246 struct olsrv2_tc_edge *
247 olsrv2_tc_edge_add(struct olsrv2_tc_node *src, struct netaddr *addr) {
248   struct olsrv2_tc_edge *edge = NULL, *inverse = NULL;
249   struct olsrv2_tc_node *dst = NULL;
250   int i;
251
252   edge = avl_find_element(&src->_edges, addr, edge, _node);
253   if (edge != NULL) {
254     edge->virtual = false;
255
256     /* cleanup metric data from other side of the edge */
257     for (i = 0; i < NHDP_MAXIMUM_DOMAINS; i++) {
258       edge->cost[i] = RFC7181_METRIC_INFINITE;
259     }
260
261     /* fire event */
262     oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
263     return edge;
264   }
265
266   /* allocate edge */
267   edge = oonf_class_malloc(&_tc_edge_class);
268   if (edge == NULL) {
269     return NULL;
270   }
271
272   /* allocate inverse edge */
273   inverse = oonf_class_malloc(&_tc_edge_class);
274   if (inverse == NULL) {
275     oonf_class_free(&_tc_edge_class, edge);
276     return NULL;
277   }
278
279   /* find or allocate destination node */
280   dst = avl_find_element(&_tc_tree, addr, dst, _originator_node);
281   if (dst == NULL) {
282     /* create virtual node */
283     dst = olsrv2_tc_node_add(addr, 0, 0);
284     if (dst == NULL) {
285       oonf_class_free(&_tc_edge_class, edge);
286       oonf_class_free(&_tc_edge_class, inverse);
287       return NULL;
288     }
289   }
290
291   /* initialize edge */
292   edge->src = src;
293   edge->dst = dst;
294   edge->inverse = inverse;
295   for (i = 0; i < NHDP_MAXIMUM_DOMAINS; i++) {
296     edge->cost[i] = RFC7181_METRIC_INFINITE;
297   }
298
299   /* hook edge into src node */
300   edge->_node.key = &dst->target.prefix.dst;
301   avl_insert(&src->_edges, &edge->_node);
302
303   /* initialize inverse (virtual) edge */
304   inverse->src = dst;
305   inverse->dst = src;
306   inverse->inverse = edge;
307   inverse->virtual = true;
308   for (i = 0; i < NHDP_MAXIMUM_DOMAINS; i++) {
309     inverse->cost[i] = RFC7181_METRIC_INFINITE;
310   }
311
312   /* hook inverse edge into dst node */
313   inverse->_node.key = &src->target.prefix.dst;
314   avl_insert(&dst->_edges, &inverse->_node);
315
316   /* fire event */
317   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
318   return edge;
319 }
320
321 /**
322  * Remove a tc edge from the database
323  * @param edge pointer to tc edge
324  * @return true if destination of edge was removed too
325  */
326 bool
327 olsrv2_tc_edge_remove(struct olsrv2_tc_edge *edge) {
328   /* all domains might have changed */
329   olsrv2_routing_domain_changed(NULL, true);
330
331   return _remove_edge(edge, true);
332 }
333
334 /**
335  * Add an endpoint to a tc node
336  * @param node pointer to tc node
337  * @param prefix address prefix of endpoint
338  * @param mesh true if an interface of a mesh node, #
339  *   false if a local attached network.
340  * @return pointer to tc attachment, NULL if out of memory
341  */
342 struct olsrv2_tc_attachment *
343 olsrv2_tc_endpoint_add(struct olsrv2_tc_node *node, struct os_route_key *prefix, bool mesh) {
344   struct olsrv2_tc_attachment *net;
345   struct olsrv2_tc_endpoint *end;
346   int i;
347
348   net = avl_find_element(&node->_attached_networks, prefix, net, _src_node);
349   if (net != NULL) {
350     return net;
351   }
352
353   net = oonf_class_malloc(&_tc_attached_class);
354   if (net == NULL) {
355     return NULL;
356   }
357
358   end = avl_find_element(&_tc_endpoint_tree, prefix, end, _node);
359   if (end == NULL) {
360     /* create new endpoint */
361     end = oonf_class_malloc(&_tc_endpoint_class);
362     if (end == NULL) {
363       oonf_class_free(&_tc_attached_class, net);
364       return NULL;
365     }
366
367     /* initialize endpoint */
368     end->target.type = mesh ? OLSRV2_ADDRESS_TARGET : OLSRV2_NETWORK_TARGET;
369     avl_init(&end->_attached_networks, os_routing_avl_cmp_route_key, false);
370
371     /* attach to global tree */
372     memcpy(&end->target.prefix, prefix, sizeof(*prefix));
373     end->_node.key = &end->target.prefix;
374     avl_insert(&_tc_endpoint_tree, &end->_node);
375
376     oonf_class_event(&_tc_endpoint_class, end, OONF_OBJECT_ADDED);
377   }
378
379   /* initialize attached network */
380   net->src = node;
381   net->dst = end;
382   for (i = 0; i < NHDP_MAXIMUM_DOMAINS; i++) {
383     net->cost[i] = RFC7181_METRIC_INFINITE;
384   }
385
386   /* hook into src node */
387   net->_src_node.key = &end->target.prefix;
388   avl_insert(&node->_attached_networks, &net->_src_node);
389
390   /* hook into endpoint */
391   net->_endpoint_node.key = &node->target.prefix;
392   avl_insert(&end->_attached_networks, &net->_endpoint_node);
393
394   /* initialize dijkstra data */
395   olsrv2_routing_dijkstra_node_init(&end->target._dijkstra, &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(struct olsrv2_tc_attachment *net) {
407   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_REMOVED);
408
409   /* remove from node */
410   avl_remove(&net->src->_attached_networks, &net->_src_node);
411
412   /* remove from endpoint */
413   avl_remove(&net->dst->_attached_networks, &net->_endpoint_node);
414
415   if (net->dst->_attached_networks.count == 0) {
416     oonf_class_event(&_tc_endpoint_class, net->dst, OONF_OBJECT_REMOVED);
417
418     /* remove endpoint */
419     avl_remove(&_tc_endpoint_tree, &net->dst->_node);
420     oonf_class_free(&_tc_endpoint_class, net->dst);
421   }
422
423   /* free attached network */
424   oonf_class_free(&_tc_attached_class, net);
425
426   /* all domains might have changed */
427   olsrv2_routing_domain_changed(NULL, true);
428 }
429
430 /**
431  * Inform everyone that a tc node changed
432  * @param node tc node
433  */
434 void
435 olsrv2_tc_trigger_change(struct olsrv2_tc_node *node) {
436   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_CHANGED);
437 }
438
439 /**
440  * Get tree of olsrv2 tc nodes
441  * @return node tree
442  */
443 struct avl_tree *
444 olsrv2_tc_get_tree(void) {
445   return &_tc_tree;
446 }
447
448 /**
449  * Get tree of olsrv2 tc endpoints
450  * @return endpoint tree
451  */
452 struct avl_tree *
453 olsrv2_tc_get_endpoint_tree(void) {
454   return &_tc_endpoint_tree;
455 }
456
457 /**
458  * Callback triggered when a tc node times out
459  * @param ptr timer instance that fired
460  */
461 static void
462 _cb_tc_node_timeout(struct oonf_timer_instance *ptr) {
463   struct olsrv2_tc_node *node;
464
465   node = container_of(ptr, struct olsrv2_tc_node, _validity_time);
466
467   olsrv2_tc_node_remove(node);
468   olsrv2_routing_trigger_update();
469 }
470
471 /**
472  * Remove a tc edge from the database
473  * @param edge pointer to tc edge
474  * @param cleanup true to remove the destination of the edge too
475  *   if its not needed anymore
476  * @return true if destination was removed, false otherwise
477  */
478 static bool
479 _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup) {
480   bool removed_node = false;
481
482   if (edge->virtual) {
483     /* nothing to do */
484     return false;
485   }
486
487   /* fire event */
488   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_REMOVED);
489
490   if (!edge->inverse->virtual) {
491     /* make this edge virtual */
492     edge->virtual = true;
493
494     return false;
495   }
496
497   /* unhook edge from both sides */
498   avl_remove(&edge->src->_edges, &edge->_node);
499   avl_remove(&edge->dst->_edges, &edge->inverse->_node);
500
501   if (edge->dst->_edges.count == 0 && cleanup && 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, sizeof(neigh->originator)) == 0) {
524     /* no change */
525     return;
526   }
527
528   /* remove old tc_node if necessary */
529   _cb_neighbor_remove(ptr);
530
531   /* see if we have a new originator */
532   if (netaddr_is_unspec(&neigh->originator)) {
533     return;
534   }
535
536   /* add tc_node if necessary */
537   tc_node = olsrv2_tc_node_get(&neigh->originator);
538   if (!tc_node) {
539     tc_node = olsrv2_tc_node_add(&neigh->originator, 0, 0);
540     if (!tc_node) {
541       return;
542     }
543   }
544
545   /* mark as direct neighbor */
546   tc_node->direct_neighbor = true;
547 }
548
549 static void
550 _cb_neighbor_remove(void *ptr) {
551   struct nhdp_neighbor *neigh;
552   struct olsrv2_tc_node *tc_node;
553
554   neigh = ptr;
555
556   if (netaddr_is_unspec(&neigh->originator)) {
557     return;
558   }
559
560   tc_node = olsrv2_tc_node_get(&neigh->originator);
561   if (!tc_node) {
562     return;
563   }
564
565   tc_node->direct_neighbor = false;
566
567   if (!oonf_timer_is_active(&tc_node->_validity_time)) {
568     /* virtual node, kill it */
569     olsrv2_tc_node_remove(tc_node);
570   }
571 }