src-plugins/olsrv2/olsrv2/olsrv2_routing.c

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