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