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