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