Fix build without DEBUG/INFO output
[oonf.git] / src-plugins / olsrv2 / olsrv2 / olsrv2_routing.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 <errno.h>
47
48 #include "common/avl.h"
49 #include "common/avl_comp.h"
50 #include "common/common_types.h"
51 #include "common/list.h"
52 #include "common/netaddr.h"
53 #include "core/oonf_logging.h"
54 #include "subsystems/oonf_class.h"
55 #include "subsystems/oonf_rfc5444.h"
56 #include "subsystems/oonf_timer.h"
57 #include "subsystems/os_routing.h"
58
59 #include "nhdp/nhdp_db.h"
60 #include "nhdp/nhdp_domain.h"
61 #include "nhdp/nhdp_interfaces.h"
62
63 #include "olsrv2/olsrv2_internal.h"
64 #include "olsrv2/olsrv2_lan.h"
65 #include "olsrv2/olsrv2_originator.h"
66 #include "olsrv2/olsrv2_tc.h"
67 #include "olsrv2/olsrv2_routing.h"
68 #include "olsrv2/olsrv2.h"
69
70 /* Prototypes */
71 static void _run_dijkstra(struct nhdp_domain *domain, int af_family,
72     bool use_non_ss, bool use_ss);
73 static struct olsrv2_routing_entry *_add_entry(
74     struct nhdp_domain *, struct os_route_key *prefix);
75 static void _remove_entry(struct olsrv2_routing_entry *);
76 static void _insert_into_working_tree(struct olsrv2_tc_target *target,
77     struct nhdp_neighbor *neigh, uint32_t linkcost,
78     uint32_t path_cost, uint8_t path_hops,
79     uint8_t distance, bool single_hop,
80     const struct netaddr *last_originator);
81 static void _prepare_routes(struct nhdp_domain *);
82 static void _prepare_nodes(void);
83 static bool _check_ssnode_split(struct nhdp_domain *domain, int af_family);
84 static void _add_one_hop_nodes(struct nhdp_domain *domain, int family, bool, bool);
85 static void _handle_working_queue(struct nhdp_domain *, bool, bool);
86 static void _handle_nhdp_routes(struct nhdp_domain *);
87 static void _add_route_to_kernel_queue(struct olsrv2_routing_entry *rtentry);
88 static void _process_dijkstra_result(struct nhdp_domain *);
89 static void _process_kernel_queue(void);
90 static void _cb_trigger_dijkstra(struct oonf_timer_instance *);
91 static void _cb_nhdp_update(struct nhdp_neighbor *);
92 static void _cb_route_finished(struct os_route *route, int error);
93
94 /* Domain parameter of dijkstra algorithm */
95 static struct olsrv2_routing_domain _domain_parameter[NHDP_MAXIMUM_DOMAINS];
96
97 /* memory class for routing entries */
98 static struct oonf_class _rtset_entry = {
99   .name = "Olsrv2 Routing Set Entry",
100   .size = sizeof(struct olsrv2_routing_entry),
101 };
102
103 /* rate limitation for dijkstra algorithm */
104 static struct oonf_timer_class _dijkstra_timer_info = {
105   .name = "Dijkstra rate limit timer",
106   .callback = _cb_trigger_dijkstra,
107 };
108
109 static struct oonf_timer_instance _rate_limit_timer = {
110   .class = &_dijkstra_timer_info
111 };
112
113 /* callback for NHDP domain events */
114 static struct nhdp_domain_listener _nhdp_listener = {
115   .update = _cb_nhdp_update,
116 };
117
118 static bool _trigger_dijkstra = false;
119
120 /* global datastructures for routing */
121 static struct avl_tree _routing_tree[NHDP_MAXIMUM_DOMAINS];
122 static struct list_entity _routing_filter_list;
123
124 static struct avl_tree _dijkstra_working_tree;
125 static struct list_entity _kernel_queue;
126
127 static bool _initiate_shutdown = false;
128
129 /**
130  * Initialize olsrv2 dijkstra and routing code
131  */
132 void
133 olsrv2_routing_init(void) {
134   int i;
135
136   oonf_class_add(&_rtset_entry);
137   oonf_timer_add(&_dijkstra_timer_info);
138
139   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
140     avl_init(&_routing_tree[i], os_routing_avl_cmp_route_key, false);
141   }
142   list_init_head(&_routing_filter_list);
143   avl_init(&_dijkstra_working_tree, avl_comp_uint32, true);
144   list_init_head(&_kernel_queue);
145
146   nhdp_domain_listener_add(&_nhdp_listener);
147 }
148
149 /**
150  * Trigger cleanup of olsrv2 dijkstra and routing code
151  */
152 void
153 olsrv2_routing_initiate_shutdown(void) {
154   struct olsrv2_routing_entry *entry, *e_it;
155   int i;
156
157   /* remember we are in shutdown */
158   _initiate_shutdown = true;
159
160   /* remove all routes */
161   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
162     avl_for_each_element_safe(&_routing_tree[i], entry, _node, e_it) {
163       /* stop internal route processing */
164       entry->route.cb_finished = NULL;
165       os_routing_interrupt(&entry->route);
166       entry->route.cb_finished = _cb_route_finished;
167
168       if (entry->set) {
169         entry->set = false;
170         _add_route_to_kernel_queue(entry);
171       }
172     }
173   }
174
175   _process_kernel_queue();
176 }
177
178 /**
179  * Finalize cleanup of olsrv2 dijkstra and routing code
180  */
181 void
182 olsrv2_routing_cleanup(void) {
183   struct olsrv2_routing_entry *entry, *e_it;
184   struct olsrv2_routing_filter *filter, *f_it;
185   int i;
186
187   nhdp_domain_listener_remove(&_nhdp_listener);
188
189   oonf_timer_stop(&_rate_limit_timer);
190
191   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
192     avl_for_each_element_safe(&_routing_tree[i], entry, _node, e_it) {
193       /* remove entry from database */
194       _remove_entry(entry);
195     }
196   }
197
198   list_for_each_element_safe(&_routing_filter_list, filter, _node, f_it) {
199     olsrv2_routing_filter_remove(filter);
200   }
201
202   oonf_timer_remove(&_dijkstra_timer_info);
203   oonf_class_remove(&_rtset_entry);
204 }
205
206 /**
207  * Trigger a new dijkstra as soon as we are back in the mainloop
208  * (unless the rate limitation timer is active, then we will wait for it)
209  */
210 void
211 olsrv2_routing_trigger_update(void) {
212   _trigger_dijkstra = true;
213   if (!oonf_timer_is_active(&_rate_limit_timer)) {
214     /* trigger as soon as we hit the next time slice */
215     oonf_timer_set(&_rate_limit_timer, 1);
216   }
217
218   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Trigger routing update");
219 }
220
221 /**
222  * @param domain nhdp domain
223  * @return routing domain parameters
224  */
225 const struct olsrv2_routing_domain *
226 olsrv2_routing_get_parameters(struct nhdp_domain *domain) {
227   return &_domain_parameter[domain->index];
228 }
229
230 /**
231  * Trigger dijkstra and routing update now
232  * @param skip_wait true to ignore rate limitation timer
233  */
234 void
235 olsrv2_routing_force_update(bool skip_wait) {
236   struct nhdp_domain *domain;
237   bool splitv4, splitv6;
238
239   if (_initiate_shutdown) {
240     /* no dijkstra anymore when in shutdown */
241     return;
242   }
243
244   /* handle dijkstra rate limitation timer */
245   if (oonf_timer_is_active(&_rate_limit_timer)) {
246     if (!skip_wait) {
247       /* trigger dijkstra later */
248       _trigger_dijkstra = true;
249
250       OONF_DEBUG(LOG_OLSRV2_ROUTING, "Delay Dijkstra");
251       return;
252     }
253     oonf_timer_stop(&_rate_limit_timer);
254   }
255
256   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Run Dijkstra");
257
258   list_for_each_element(nhdp_domain_get_list(), domain, _node) {
259     /* initialize dijkstra specific fields */
260     _prepare_routes(domain);
261     _prepare_nodes();
262
263     /* run IPv4 dijkstra (might be two times because of source-specific data) */
264     splitv4 = _check_ssnode_split(domain, AF_INET);
265     _run_dijkstra(domain, AF_INET, true, !splitv4);
266
267     /* run IPv6 dijkstra (might be two times because of source-specific data) */
268     splitv6 = _check_ssnode_split(domain, AF_INET6);
269     _run_dijkstra(domain, AF_INET6, true, !splitv6);
270
271     /* handle source-specific sub-topology if necessary */
272     if (splitv4 || splitv6) {
273       /* re-initialize dijkstra specific node fields */
274       _prepare_nodes();
275
276       if (splitv4) {
277         _run_dijkstra(domain, AF_INET, false, true);
278       }
279       if (splitv6) {
280         _run_dijkstra(domain, AF_INET6, false, true);
281       }
282     }
283
284     /* check if direct one-hop routes are quicker */
285     _handle_nhdp_routes(domain);
286
287     /* update kernel routes */
288     _process_dijkstra_result(domain);
289   }
290
291   _process_kernel_queue();
292
293   /* make sure dijkstra is not called too often */
294   oonf_timer_set(&_rate_limit_timer, OLSRv2_DIJKSTRA_RATE_LIMITATION);
295 }
296
297 /**
298  * Initialize the dijkstra code part of a tc node.
299  * Should normally not be called by other parts of OLSRv2.
300  * @param dijkstra pointer to dijkstra node
301  */
302 void
303 olsrv2_routing_dijkstra_node_init(struct olsrv2_dijkstra_node *dijkstra) {
304   dijkstra->_node.key = &dijkstra->path_cost;
305 }
306
307 /**
308  * Set the domain parameters of olsrv2
309  * @param domain pointer to NHDP domain
310  * @param parameter pointer to new parameters
311  */
312 void
313 olsrv2_routing_set_domain_parameter(struct nhdp_domain *domain,
314     struct olsrv2_routing_domain *parameter) {
315   struct olsrv2_routing_entry *rtentry;
316
317   if (memcmp(parameter, &_domain_parameter[domain->index],
318       sizeof(*parameter)) == 0) {
319     /* no change */
320     return;
321   }
322
323   /* copy parameters */
324   memcpy(&_domain_parameter[domain->index], parameter, sizeof(*parameter));
325
326   if (avl_is_empty(&_routing_tree[domain->index])) {
327     /* no routes present */
328     return;
329   }
330
331   /* remove old kernel routes */
332   avl_for_each_element(&_routing_tree[domain->index], rtentry, _node) {
333     if (rtentry->set) {
334       rtentry->set = false;
335
336       if (rtentry->in_processing) {
337         os_routing_interrupt(&rtentry->route);
338         rtentry->set = false;
339       }
340
341       _add_route_to_kernel_queue(rtentry);
342     }
343   }
344
345   _process_kernel_queue();
346
347   /* trigger a dijkstra to write new routes in 100 milliseconds */
348   oonf_timer_set(&_rate_limit_timer, 100);
349   _trigger_dijkstra = true;
350 }
351
352 /**
353  * Get tree of olsrv2 routing entries
354  * @param domain nhdp domain
355  * @return tree of routing entries
356  */
357 struct avl_tree *
358 olsrv2_routing_get_tree(struct nhdp_domain *domain) {
359   return &_routing_tree[domain->index];
360 }
361
362 /**
363  * Get list of olsrv2 routing filters
364  * @return filter list
365  */
366 struct list_entity *
367 olsrv2_routing_get_filter_list(void) {
368   return &_routing_filter_list;
369 }
370
371 /**
372  * Run Dijkstra for a set domain, address family and
373  * (non-)source-specific nodes
374  * @param domain nhdp domain
375  * @param af_family address family
376  * @param use_non_ss dijkstra should include non-source-specific ndoes
377  * @param use_ss dijkstra should include source-specific ndoes
378  */
379 static void
380 _run_dijkstra(struct nhdp_domain *domain, int af_family,
381     bool use_non_ss, bool use_ss) {
382   OONF_INFO(LOG_OLSRV2_ROUTING, "Run %s dijkstra on domain %d: %s/%s",
383       af_family == AF_INET ? "ipv4" : "ipv6", domain->index,
384       use_non_ss ? "true" : "false", use_ss ? "true" : "false");
385
386   /* add direct neighbors to working queue */
387   _add_one_hop_nodes(domain, af_family, use_non_ss, use_ss);
388
389   /* run dijkstra */
390   while (!avl_is_empty(&_dijkstra_working_tree)) {
391     _handle_working_queue(domain, use_non_ss, use_ss);
392   }
393 }
394
395 /**
396  * Add a new routing entry to the database
397  * @param domain pointer to nhdp domain
398  * @param prefix network prefix of routing entry
399  * @return pointer to routing entry, NULL if our of memory.
400  */
401 static struct olsrv2_routing_entry *
402 _add_entry(struct nhdp_domain *domain, struct os_route_key *prefix) {
403   struct olsrv2_routing_entry *rtentry;
404
405   rtentry = avl_find_element(
406       &_routing_tree[domain->index], prefix, rtentry, _node);
407   if (rtentry) {
408     return rtentry;
409   }
410
411   rtentry = oonf_class_malloc(&_rtset_entry);
412   if (rtentry == NULL) {
413     return NULL;
414   }
415
416   /* set key */
417   memcpy(&rtentry->route.p.key, prefix, sizeof(struct os_route_key));
418   rtentry->_node.key = &rtentry->route.p.key;
419
420   /* set domain */
421   rtentry->domain = domain;
422
423   /* initialize path costs and os-route callback */
424   rtentry->path_cost = RFC7181_METRIC_INFINITE_PATH;
425   rtentry->path_hops = 255;
426   rtentry->route.cb_finished = _cb_route_finished;
427   rtentry->route.p.family = netaddr_get_address_family(&prefix->dst);
428
429   rtentry->route.p.type = OS_ROUTE_UNICAST;
430
431   avl_insert(&_routing_tree[domain->index], &rtentry->_node);
432   return rtentry;
433 }
434
435 /**
436  * Remove a routing entry from the global database
437  * @param entry pointer to routing entry
438  */
439 static void
440 _remove_entry(struct olsrv2_routing_entry *entry) {
441   /* stop internal route processing */
442   entry->route.cb_finished = NULL;
443   os_routing_interrupt(&entry->route);
444
445   /* remove entry from database */
446   avl_remove(&_routing_tree[entry->domain->index], &entry->_node);
447   oonf_class_free(&_rtset_entry, entry);
448 }
449
450 /**
451  * Insert a new entry into the dijkstra working queue
452  * @param target pointer to tc target
453  * @param neigh next hop through which the target can be reached
454  * @param linkcost cost of the last hop of the path towards the target
455  * @param pathcost remainder of the cost to the target
456  * @param distance hopcount to be used for the route to the target
457  * @param single_hop true if this is a single-hop route, false otherwise
458  * @param last_node address of the last originator before we reached the
459  *   destination prefix
460  */
461 static void
462 _insert_into_working_tree(struct olsrv2_tc_target *target,
463     struct nhdp_neighbor *neigh, uint32_t linkcost,
464     uint32_t path_cost, uint8_t path_hops,
465     uint8_t distance, bool single_hop,
466     const struct netaddr *last_originator) {
467   struct olsrv2_dijkstra_node *node;
468 #ifdef OONF_LOG_DEBUG_INFO
469   struct netaddr_str nbuf1, nbuf2;
470 #endif
471   if (linkcost > RFC7181_METRIC_MAX) {
472     return;
473   }
474
475   node = &target->_dijkstra;
476
477   /*
478    * do not add ourselves to working queue,
479    * do not add nodes already processed to the working queue
480    */
481   if (node->local || node->done) {
482     return;
483   }
484
485   /* calculate new total pathcost */
486   path_cost += linkcost;
487   path_hops += 1;
488
489   if (avl_is_node_added(&node->_node)) {
490     /* node already in dijkstra working queue */
491
492     if (node->path_cost <= path_cost) {
493       /* current path is shorter than new one */
494       return;
495     }
496
497     /* we found a better path, remove node from working queue */
498     avl_remove(&_dijkstra_working_tree, &node->_node);
499   }
500   
501   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Add dst %s [%s] with pathcost %u to dijstra tree (0x%zx)",
502           netaddr_to_string(&nbuf1, &target->prefix.dst),
503           netaddr_to_string(&nbuf2, &target->prefix.src), path_cost,
504           (size_t)target);
505
506   node->path_cost = path_cost;
507   node->path_hops = path_hops;
508   node->first_hop = neigh;
509   node->distance = distance;
510   node->single_hop = single_hop;
511   node->last_originator = last_originator;
512
513   avl_insert(&_dijkstra_working_tree, &node->_node);
514   return;
515 }
516
517 /**
518  * Initialize a routing entry with the result of the dijkstra calculation
519  * @param domain nhdp domain
520  * @param destination destination of routing entry
521  * @param dst_originator originator address of destination
522  * @param first_hop nhdp neighbor for first hop to target
523  * @param distance hopcount distance that should be used for route
524  * @param pathcost pathcost to target
525  * @param path_hops number of hops to the target
526  * @param single_hop true if route is single hop
527  * @param last_originator last originator before destination
528  */
529 static void
530 _update_routing_entry(struct nhdp_domain *domain,
531     struct os_route_key *prefix,
532     struct nhdp_neighbor *first_hop,
533     uint8_t distance, uint32_t pathcost, uint8_t path_hops,
534     bool single_hop, const struct netaddr *last_originator) {
535   struct nhdp_neighbor_domaindata *neighdata;
536   struct olsrv2_routing_entry *rtentry;
537   const struct netaddr *originator;
538   struct olsrv2_lan_entry *lan;
539   struct olsrv2_lan_domaindata *landata;
540 #ifdef OONF_LOG_DEBUG_INFO
541   struct netaddr_str nbuf1, nbuf2, nbuf3;
542 #endif
543
544   /* test if destination is already part of the local node */
545   originator = olsrv2_originator_get(netaddr_get_address_family(&prefix->dst));
546   if (netaddr_cmp(originator, &prefix->dst) == 0) {
547     /* don't set routes for our own originator */
548     return;
549   }
550   if (nhdp_interface_addr_global_get(&prefix->dst)) {
551     /* don't set routes for our own interface addresses */
552     return;
553   }
554   lan = olsrv2_lan_get(prefix);
555   if (lan) {
556     landata = olsrv2_lan_get_domaindata(domain, lan);
557     if (landata->active && landata->outgoing_metric < pathcost) {
558       /*
559        * don't set routes for our own locally attached
560        * networks with a better metric
561        */
562       return;
563     }
564   }
565
566   if (!netaddr_acl_check_accept(olsrv2_get_routable(), &prefix->dst)) {
567     /* don't set routes to non-routable destinations */
568     return;
569   }
570
571   /* make sure routing entry is present */
572   rtentry = _add_entry(domain, prefix);
573   if (rtentry == NULL) {
574     /* out of memory... */
575     return;
576   }
577
578   /*
579    * routing entry might already be present because it can be set by
580    * a tc node AND by attached networks with a maximum prefix length
581    */
582   if (rtentry->set && rtentry->path_cost < pathcost) {
583     /* active routing entry is already cheaper, ignore new one */
584     return;
585   }
586
587   neighdata = nhdp_domain_get_neighbordata(domain, first_hop);
588   /* copy route parameters into data structure */
589   rtentry->route.p.if_index = neighdata->best_link_ifindex;
590   rtentry->path_cost = pathcost;
591   rtentry->path_hops = path_hops;
592   rtentry->route.p.metric = distance;
593
594   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Initialize route entry dst %s [%s] (firsthop %s, domain %u) with pathcost %u, if %s",
595       netaddr_to_string(&nbuf1, &rtentry->route.p.key.dst),
596       netaddr_to_string(&nbuf2, &rtentry->route.p.key.src),
597       netaddr_to_string(&nbuf3, &first_hop->originator),
598       domain->ext, pathcost, neighdata->best_link->local_if->os_if_listener.data->name);
599
600   /* remember next hop originator */
601   memcpy(&rtentry->next_originator, &first_hop->originator, sizeof(struct netaddr));
602
603   /* remember last originator */
604   memcpy(&rtentry->last_originator, last_originator, sizeof(*last_originator));
605
606   /* mark route as set */
607   rtentry->set = true;
608
609   /* copy gateway if necessary */
610   if (single_hop
611       && netaddr_cmp(&neighdata->best_link->if_addr,
612           &rtentry->route.p.key.dst) == 0) {
613     netaddr_invalidate(&rtentry->route.p.gw);
614   }
615   else {
616     memcpy(&rtentry->route.p.gw, &neighdata->best_link->if_addr,
617         sizeof(struct netaddr));
618   }
619 }
620
621 /**
622  * Initialize internal fields for dijkstra calculation
623  * @param domain nhdp domain
624  * @return true if source-specific and non-source specific can
625  *   be handled in the same dijkstra run, false otherwise
626  */
627 static void
628 _prepare_routes(struct nhdp_domain *domain) {
629   struct olsrv2_routing_entry *rtentry;
630   /* prepare all existing routing entries and put them into the working queue */
631   avl_for_each_element(&_routing_tree[domain->index], rtentry, _node) {
632     rtentry->set = false;
633     memcpy(&rtentry->_old, &rtentry->route.p, sizeof(rtentry->_old));
634   }
635 }
636
637 /**
638  * Initialize internal fields for dijkstra calculation
639  * @param domain nhdp domain
640  * @return true if source-specific and non-source specific can
641  *   be handled in the same dijkstra run, false otherwise
642  */
643 static void
644 _prepare_nodes(void) {
645   struct olsrv2_tc_endpoint *end;
646   struct olsrv2_tc_node *node;
647
648   /* initialize private dijkstra data on nodes */
649   avl_for_each_element(olsrv2_tc_get_tree(), node, _originator_node) {
650     node->target._dijkstra.first_hop = NULL;
651     node->target._dijkstra.path_cost = RFC7181_METRIC_INFINITE_PATH;
652     node->target._dijkstra.path_hops = 255;
653     node->target._dijkstra.local =
654         olsrv2_originator_is_local(&node->target.prefix.dst);
655     node->target._dijkstra.done = false;
656   }
657
658   /* initialize private dijkstra data on endpoints */
659   avl_for_each_element(olsrv2_tc_get_endpoint_tree(), end, _node) {
660     end->target._dijkstra.first_hop = NULL;
661     end->target._dijkstra.path_cost = RFC7181_METRIC_INFINITE_PATH;
662     end->target._dijkstra.path_hops = 255;
663     end->target._dijkstra.done = false;
664   }
665 }
666
667 /**
668  * calculates if source- and non-source-specific targets must be done
669  * in separate dijkstra runs
670  * @param domain nhdp domain for dijkstra run
671  * @param af_family address family for dijkstra run
672  * @return true if two dijkstra runs are necessary, false for one
673  */
674 static bool
675 _check_ssnode_split(struct nhdp_domain *domain, int af_family) {
676   struct olsrv2_tc_node *node;
677   uint32_t ssnode_count, full_count;
678   bool ssnode_prefix;
679
680   ssnode_count = 0;
681   full_count = 0;
682   ssnode_prefix = false;
683
684   avl_for_each_element(olsrv2_tc_get_tree(), node, _originator_node) {
685     /* count number of source specific nodes */
686     if (netaddr_get_address_family(&node->target.prefix.dst) == af_family) {
687       full_count++;
688       if (node->source_specific) {
689         ssnode_count++;
690       }
691     }
692
693     /* remember node domain with source specific prefix */
694     ssnode_prefix |= node->ss_attached_networks[domain->index];
695   }
696
697   OONF_INFO(LOG_OLSRV2_ROUTING, "ss split for %d/%d: %d of %d/%s",
698       domain->index, af_family, ssnode_count, full_count,
699       ssnode_prefix ? "true" : "false");
700
701   return ssnode_count != 0 && ssnode_count != full_count && ssnode_prefix;
702 }
703
704 /**
705  * Add the single-hop TC neighbors to the dijkstra working list
706  * @param domain nhdp domain for dijkstra run
707  * @param af_family address family for dijkstra run
708  * @param use_non_ss include non-source-specific nodes into working list
709  * @param use_ss include source-specific nodes into working list
710  */
711 static void
712 _add_one_hop_nodes(struct nhdp_domain *domain, int af_family,
713     bool use_non_ss, bool use_ss) {
714   struct olsrv2_tc_node *node;
715   struct nhdp_neighbor *neigh;
716   struct nhdp_neighbor_domaindata *neigh_metric;
717 #ifdef OONF_LOG_DEBUG_INFO
718   struct netaddr_str nbuf;
719 #endif
720
721   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Start add one-hop nodes");
722
723   /* initialize Dijkstra working queue with one-hop neighbors */
724   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
725     if (netaddr_get_address_family(&neigh->originator) != af_family) {
726       continue;
727     }
728
729     if (neigh->symmetric == 0
730         || (node = olsrv2_tc_node_get(&neigh->originator)) == NULL) {
731       continue;
732     }
733
734     if (!use_non_ss && !(node->source_specific && use_ss)) {
735       continue;
736     }
737
738     neigh_metric = nhdp_domain_get_neighbordata(domain, neigh);
739
740     if (neigh_metric->metric.in > RFC7181_METRIC_MAX
741         || neigh_metric->metric.out > RFC7181_METRIC_MAX) {
742       /* ignore link with infinite metric */
743       continue;
744     }
745
746     OONF_DEBUG(LOG_OLSRV2_ROUTING, "Add one-hop node %s",
747         netaddr_to_string(&nbuf, &neigh->originator));
748
749     /* found node for neighbor, add to worker list */
750     _insert_into_working_tree(&node->target, neigh,
751         neigh_metric->metric.out, 0, 0, 0, true,
752         olsrv2_originator_get(af_family));
753   }
754 }
755
756 /**
757  * Remove item from dijkstra working queue and process it
758  * @param domain nhdp domain
759  */
760 static void
761 _handle_working_queue(struct nhdp_domain *domain,
762     bool use_non_ss, bool use_ss) {
763   struct olsrv2_tc_target *target;
764   struct nhdp_neighbor *first_hop;
765
766   struct olsrv2_tc_node *tc_node;
767   struct olsrv2_tc_edge *tc_edge;
768   struct olsrv2_tc_attachment *tc_attached;
769   struct olsrv2_tc_endpoint *tc_endpoint;
770
771 #ifdef OONF_LOG_DEBUG_INFO
772   struct netaddr_str nbuf1, nbuf2;
773 #endif
774
775   /* get tc target */
776   target = avl_first_element(&_dijkstra_working_tree, target, _dijkstra._node);
777
778   /* remove current node from working tree */
779   OONF_DEBUG(LOG_OLSRV2_ROUTING, "Remove node %s [%s] from dijkstra tree",
780       netaddr_to_string(&nbuf1, &target->prefix.dst),
781       netaddr_to_string(&nbuf2, &target->prefix.src));
782   avl_remove(&_dijkstra_working_tree, &target->_dijkstra._node);
783
784   /* mark current node as done */
785   target->_dijkstra.done = true;
786
787   /* fill routing entry with dijkstra result */
788   if (use_non_ss) {
789     _update_routing_entry(domain, &target->prefix,
790         target->_dijkstra.first_hop,
791         target->_dijkstra.distance,
792         target->_dijkstra.path_cost,
793         target->_dijkstra.path_hops,
794         target->_dijkstra.single_hop,
795         target->_dijkstra.last_originator);
796   }
797
798   if (target->type == OLSRV2_NODE_TARGET) {
799     /* get neighbor and its domain specific data */
800     first_hop = target->_dijkstra.first_hop;
801
802     /* calculate pointer of olsrv2_tc_node */
803     tc_node = container_of(target, struct olsrv2_tc_node, target);
804
805     /* iterate over edges */
806     avl_for_each_element(&tc_node->_edges, tc_edge, _node) {
807       if (!tc_edge->virtual && tc_edge->cost[domain->index] <= RFC7181_METRIC_MAX) {
808         if (!use_non_ss && !tc_node->source_specific) {
809           continue;
810         }
811
812         /* add new tc_node to working tree */
813         _insert_into_working_tree(&tc_edge->dst->target, first_hop,
814             tc_edge->cost[domain->index],
815             target->_dijkstra.path_cost, target->_dijkstra.path_hops,
816             0, false, &target->prefix.dst);
817       }
818     }
819
820     /* iterate over attached networks and addresses */
821     avl_for_each_element(&tc_node->_attached_networks, tc_attached, _src_node) {
822       if (tc_attached->cost[domain->index] <= RFC7181_METRIC_MAX) {
823         tc_endpoint = tc_attached->dst;
824
825         if (!(netaddr_get_prefix_length(&tc_endpoint->target.prefix.src) > 0
826             ? use_ss : use_non_ss)) {
827           /* filter out (non-)source-specific targets if necessary */
828           continue;
829         }
830         if (tc_endpoint->_attached_networks.count > 1) {
831           /* add attached network or address to working tree */
832           _insert_into_working_tree(&tc_attached->dst->target, first_hop,
833               tc_attached->cost[domain->index],
834               target->_dijkstra.path_cost, target->_dijkstra.path_hops,
835               tc_attached->distance[domain->index], false,
836               &target->prefix.dst);
837         }
838         else {
839           /* no other way to this endpoint */
840           tc_endpoint->target._dijkstra.done = true;
841
842           /* fill routing entry with dijkstra result */
843           _update_routing_entry(domain, &tc_endpoint->target.prefix,
844               first_hop, tc_attached->distance[domain->index],
845               target->_dijkstra.path_cost + tc_attached->cost[domain->index],
846               tc_endpoint->target._dijkstra.path_hops + 1,
847               false, &target->prefix.dst);
848         }
849       }
850     }
851   }
852 }
853
854 /**
855  * Add routes learned from nhdp to dijkstra results
856  * @param domain nhdp domain
857  */
858 static void
859 _handle_nhdp_routes(struct nhdp_domain *domain) {
860   struct nhdp_neighbor_domaindata *neigh_data;
861   struct nhdp_neighbor *neigh;
862   struct nhdp_naddr *naddr;
863   struct nhdp_l2hop *l2hop;
864   struct nhdp_link *lnk;
865   uint32_t neighcost;
866   uint32_t l2hop_pathcost;
867   int family;
868   struct os_route_key ssprefix;
869
870   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
871     family = netaddr_get_address_family(&neigh->originator);
872
873     /* get linkcost to neighbor */
874     neigh_data = nhdp_domain_get_neighbordata(domain, neigh);
875     neighcost = neigh_data->metric.out;
876
877     if (neigh->symmetric == 0 || neighcost > RFC7181_METRIC_MAX) {
878       continue;
879     }
880
881     /* make sure all addresses of the neighbor are better than our direct link */
882     avl_for_each_element(&neigh->_neigh_addresses, naddr, _neigh_node) {
883       if (!netaddr_acl_check_accept(olsrv2_get_routable(), &naddr->neigh_addr)) {
884         /* not a routable address, check the next one */
885         continue;
886       }
887
888       os_routing_init_sourcespec_prefix(&ssprefix, &naddr->neigh_addr);
889
890       /* update routing entry */
891       if (olsrv2_originator_get(family)) {
892         _update_routing_entry(domain, &ssprefix,
893             neigh, 0, neighcost, 1, true, olsrv2_originator_get(family));
894       }
895       else {
896         _update_routing_entry(domain, &ssprefix,
897             neigh, 0, neighcost, 1, true, &NETADDR_UNSPEC);
898       }
899     }
900
901     list_for_each_element(&neigh->_links, lnk, _neigh_node) {
902       avl_for_each_element(&lnk->_2hop, l2hop, _link_node) {
903         /* check if 2hop neighbor is lost */
904         if (nhdp_db_2hop_is_lost(l2hop)) {
905           continue;
906         }
907
908         /* get new pathcost to 2hop neighbor */
909         l2hop_pathcost = nhdp_domain_get_l2hopdata(domain, l2hop)->metric.out;
910         if (l2hop_pathcost > RFC7181_METRIC_MAX) {
911           continue;
912         }
913
914         l2hop_pathcost += neighcost;
915
916         os_routing_init_sourcespec_prefix(&ssprefix, &l2hop->twohop_addr);
917
918         /* the 2-hop route is better than the dijkstra calculation */
919         _update_routing_entry(domain, &ssprefix,
920             neigh, 0, l2hop_pathcost, 2, false, &neigh->originator);
921       }
922     }
923   }
924 }
925
926 /**
927  * Add a route to the kernel processing queue
928  * @param rtentry pointer to routing entry
929  */
930 static void
931 _add_route_to_kernel_queue(struct olsrv2_routing_entry *rtentry) {
932 #ifdef OONF_LOG_INFO
933   struct os_route_str rbuf1, rbuf2;
934 #endif
935
936   if (rtentry->set) {
937     OONF_INFO(LOG_OLSRV2_ROUTING,
938         "Set route %s (%s)",
939         os_routing_to_string(&rbuf1, &rtentry->route.p),
940         os_routing_to_string(&rbuf2, &rtentry->_old));
941
942     if (netaddr_get_address_family(&rtentry->route.p.gw) == AF_UNSPEC) {
943       /* insert/update single-hop routes early */
944       list_add_head(&_kernel_queue, &rtentry->_working_node);
945     }
946     else {
947       /* insert/update multi-hop routes late */
948       list_add_tail(&_kernel_queue, &rtentry->_working_node);
949     }
950   }
951   else {
952     OONF_INFO(LOG_OLSRV2_ROUTING,
953         "Dijkstra result: remove route %s",
954         os_routing_to_string(&rbuf1, &rtentry->route.p));
955
956
957     if (netaddr_get_address_family(&rtentry->route.p.gw) == AF_UNSPEC) {
958       /* remove single-hop routes late */
959       list_add_tail(&_kernel_queue, &rtentry->_working_node);
960     }
961     else {
962       /* remove multi-hop routes early */
963       list_add_head(&_kernel_queue, &rtentry->_working_node);
964     }
965   }
966 }
967
968 /**
969  * process the results of a dijkstra run and add them to the kernel
970  * processing queue
971  * @param domain nhdp domain
972  */
973 static void
974 _process_dijkstra_result(struct nhdp_domain *domain) {
975   struct olsrv2_routing_entry *rtentry;
976   struct olsrv2_routing_filter *filter;
977 #ifdef OONF_LOG_INFO
978   struct os_route_str rbuf1, rbuf2;
979 #endif
980
981   avl_for_each_element(&_routing_tree[domain->index], rtentry, _node) {
982     /* initialize rest of route parameters */
983     rtentry->route.p.table = _domain_parameter[rtentry->domain->index].table;
984     rtentry->route.p.protocol = _domain_parameter[rtentry->domain->index].protocol;
985     rtentry->route.p.metric = _domain_parameter[rtentry->domain->index].distance;
986
987     if (rtentry->set
988         && _domain_parameter[rtentry->domain->index].use_srcip_in_routes
989         && netaddr_get_address_family(&rtentry->route.p.key.dst) == AF_INET) {
990       /* copy source address to route */
991       memcpy(&rtentry->route.p.src_ip, olsrv2_originator_get(AF_INET),
992           sizeof(rtentry->route.p.src_ip));
993     }
994
995     list_for_each_element(&_routing_filter_list, filter, _node) {
996       if (!filter->filter(domain, &rtentry->route.p, rtentry->set)) {
997         /* route modification was dropped by filter */
998         continue;
999       }
1000     }
1001
1002     if (rtentry->set
1003         && memcmp(&rtentry->_old, &rtentry->route.p, sizeof(rtentry->_old)) == 0) {
1004       /* no change, ignore this entry */
1005       OONF_INFO(LOG_OLSRV2_ROUTING,
1006           "Ignore route change: %s -> %s",
1007           os_routing_to_string(&rbuf1, &rtentry->_old),
1008           os_routing_to_string(&rbuf2, &rtentry->route.p));
1009       continue;
1010     }
1011     _add_route_to_kernel_queue(rtentry);
1012   }
1013 }
1014
1015 /**
1016  * Process all entries in kernel processing queue and send them to the kernel
1017  */
1018 static void
1019 _process_kernel_queue(void) {
1020   struct olsrv2_routing_entry *rtentry, *rt_it;
1021   struct os_route_str rbuf;
1022
1023   list_for_each_element_safe(&_kernel_queue, rtentry, _working_node, rt_it) {
1024     /* remove from routing queue */
1025     list_remove(&rtentry->_working_node);
1026
1027     if (rtentry->in_processing) {
1028       continue;
1029     }
1030
1031     /* mark route as in kernel processing */
1032     rtentry->in_processing = true;
1033
1034     if (rtentry->set) {
1035       /* add to kernel */
1036       if (os_routing_set(&rtentry->route, true, true)) {
1037         OONF_WARN(LOG_OLSRV2_ROUTING, "Could not set route %s",
1038             os_routing_to_string(&rbuf, &rtentry->route.p));
1039       }
1040     }
1041     else  {
1042       /* remove from kernel */
1043       if (os_routing_set(&rtentry->route, false, false)) {
1044         OONF_WARN(LOG_OLSRV2_ROUTING, "Could not remove route %s",
1045             os_routing_to_string(&rbuf, &rtentry->route.p));
1046       }
1047     }
1048   }
1049 }
1050
1051 /**
1052  * Callback for checking if dijkstra was triggered during
1053  * rate limitation time
1054  * @param ptr timer instance that fired
1055  */
1056 static void
1057 _cb_trigger_dijkstra(struct oonf_timer_instance *ptr __attribute__((unused))) {
1058   if (_trigger_dijkstra) {
1059     _trigger_dijkstra = false;
1060     olsrv2_routing_force_update(false);
1061   }
1062 }
1063
1064 /**
1065  * Callback triggered when neighbor metrics are updates
1066  * @param neigh
1067  */
1068 static void
1069 _cb_nhdp_update(struct nhdp_neighbor *neigh __attribute__((unused))) {
1070   olsrv2_routing_trigger_update();
1071 }
1072
1073 /**
1074  * Callback for kernel route processing results
1075  * @param route pointer to kernel route
1076  * @param error 0 if no error happened
1077  */
1078 static void
1079 _cb_route_finished(struct os_route *route, int error) {
1080   struct olsrv2_routing_entry *rtentry;
1081   struct os_route_str rbuf;
1082
1083   rtentry = container_of(route, struct olsrv2_routing_entry, route);
1084
1085   /* kernel is not processing this route anymore */
1086   rtentry->in_processing = false;
1087
1088   if (!rtentry->set && error == ESRCH) {
1089     OONF_DEBUG(LOG_OLSRV2_ROUTING, "Route %s was already gone",
1090         os_routing_to_string(&rbuf, &rtentry->route.p));
1091   }
1092   else if (error) {
1093     if (error == -1) {
1094       /* someone called an interrupt */
1095       return;
1096     }
1097     /* an error happened, try again later */
1098     OONF_WARN(LOG_OLSRV2_ROUTING, "Error in route %s %s: %s (%d)",
1099         rtentry->set ? "setting" : "removal",
1100             os_routing_to_string(&rbuf, &rtentry->route.p),
1101             strerror(error), error);
1102
1103     if (error == EEXIST && rtentry->set) {
1104       /* exactly this route already exists */
1105       return;
1106     }
1107
1108     /* revert attempted change */
1109     if (rtentry->set) {
1110       _remove_entry(rtentry);
1111     }
1112     else {
1113       rtentry->set = true;
1114     }
1115     return;
1116   }
1117   if (rtentry->set) {
1118     /* route was set/updated successfully */
1119     OONF_INFO(LOG_OLSRV2_ROUTING, "Successfully set route %s",
1120         os_routing_to_string(&rbuf, &rtentry->route.p));
1121   }
1122   else {
1123     OONF_INFO(LOG_OLSRV2_ROUTING, "Successfully removed route %s",
1124         os_routing_to_string(&rbuf, &rtentry->route.p));
1125     _remove_entry(rtentry);
1126   }
1127 }