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