src-plugins/olsrv2/olsrv2/olsrv2_tc.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 "common/avl.h"
  47 #include "common/avl_comp.h"
  48 #include "common/common_types.h"
  49 #include "common/netaddr.h"
  50 #include "subsystems/oonf_class.h"
  51 #include "subsystems/oonf_rfc5444.h"
  52 #include "subsystems/oonf_timer.h"
  53
  54 #include "nhdp/nhdp_domain.h"
  55 #include "nhdp/nhdp.h"
  56
  57 #include "olsrv2/olsrv2_routing.h"
  58 #include "olsrv2/olsrv2_tc.h"
  59
  60 /* prototypes */
  61 static void _cb_tc_node_timeout(struct oonf_timer_instance *);
  62 static bool _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup);
  63
  64 static void _cb_neighbor_change(void *ptr);
  65 static void _cb_neighbor_remove(void *ptr);
  66
  67 /* classes for topology data */
  68 static struct oonf_class _tc_node_class = {
  69   .name = OLSRV2_CLASS_TC_NODE,
  70   .size = sizeof(struct olsrv2_tc_node),
  71 };
  72
  73 static struct oonf_class _tc_edge_class = {
  74   .name = OLSRV2_CLASS_TC_EDGE,
  75   .size = sizeof(struct olsrv2_tc_edge),
  76 };
  77
  78 static struct oonf_class _tc_attached_class = {
  79   .name = OLSRV2_CLASS_ATTACHED,
  80   .size = sizeof(struct olsrv2_tc_attachment),
  81 };
  82
  83 static struct oonf_class _tc_endpoint_class = {
  84   .name = OLSRV2_CLASS_ENDPOINT,
  85   .size = sizeof(struct olsrv2_tc_endpoint),
  86 };
  87
  88 /* keep track of direct neighbors */
  89 static struct oonf_class_extension _nhdp_neighbor_extension = {
  90   .ext_name = "olsrv2_tc tracking",
  91   .class_name = NHDP_CLASS_NEIGHBOR,
  92   .cb_change = _cb_neighbor_change,
  93   .cb_remove = _cb_neighbor_remove,
  94 };
  95
  96 /* validity timer for tc nodes */
  97 static struct oonf_timer_class _validity_info = {
  98   .name = "olsrv2 tc node validity",
  99   .callback = _cb_tc_node_timeout,
 100 };
 101
 102 /* global trees for tc nodes and endpoints */
 103 static struct avl_tree _tc_tree;
 104 static struct avl_tree _tc_endpoint_tree;
 105
 106 /**
 107  * Initialize tc database
 108  */
 109 void
 110 olsrv2_tc_init(void) {
 111   oonf_class_add(&_tc_node_class);
 112   oonf_class_add(&_tc_edge_class);
 113   oonf_class_add(&_tc_attached_class);
 114   oonf_class_add(&_tc_endpoint_class);
 115
 116   oonf_class_extension_add(&_nhdp_neighbor_extension);
 117
 118   avl_init(&_tc_tree, avl_comp_netaddr, false);
 119   avl_init(&_tc_endpoint_tree, os_routing_avl_cmp_route_key, true);
 120 }
 121
 122 /**
 123  * Cleanup tc database
 124  */
 125 void
 126 olsrv2_tc_cleanup(void) {
 127   struct olsrv2_tc_node *node, *n_it;
 128   struct olsrv2_tc_edge *edge, *e_it;
 129   struct olsrv2_tc_attachment *a_end, *ae_it;
 130
 131   avl_for_each_element(&_tc_tree, node, _originator_node) {
 132     avl_for_each_element_safe(&node->_edges, edge, _node, e_it) {
 133       /* remove edge without cleaning up the node */
 134       _remove_edge(edge, false);
 135     }
 136
 137     avl_for_each_element_safe(&node->_attached_networks, a_end, _src_node, ae_it) {
 138       olsrv2_tc_endpoint_remove(a_end);
 139     }
 140   }
 141
 142   avl_for_each_element_safe(&_tc_tree, node, _originator_node, n_it) {
 143     olsrv2_tc_node_remove(node);
 144   }
 145
 146   oonf_class_extension_remove(&_nhdp_neighbor_extension);
 147
 148   oonf_class_remove(&_tc_endpoint_class);
 149   oonf_class_remove(&_tc_attached_class);
 150   oonf_class_remove(&_tc_edge_class);
 151   oonf_class_remove(&_tc_node_class);
 152 }
 153
 154 /**
 155  * Add a new tc node to the database
 156  * @param originator originator address of node
 157  * @param vtime validity time for node entry
 158  * @param ansn answer set number of node
 159  * @return pointer to node, NULL if out of memory
 160  */
 161 struct olsrv2_tc_node *
 162 olsrv2_tc_node_add(struct netaddr *originator,
 163     uint64_t vtime, uint16_t ansn) {
 164   struct olsrv2_tc_node *node;
 165
 166   node = avl_find_element(
 167       &_tc_tree, originator, node, _originator_node);
 168   if (!node) {
 169     node = oonf_class_malloc(&_tc_node_class);
 170     if (node == NULL) {
 171       return NULL;
 172     }
 173
 174     /* copy key and attach it to node */
 175     os_routing_init_sourcespec_prefix(&node->target.prefix, originator);
 176     node->_originator_node.key = &node->target.prefix.dst;
 177
 178     /* initialize node */
 179     avl_init(&node->_edges, avl_comp_netaddr, false);
 180     avl_init(&node->_attached_networks, os_routing_avl_cmp_route_key, false);
 181
 182     node->_validity_time.class = &_validity_info;
 183
 184     node->ansn = ansn;
 185
 186     /* initialize dijkstra data */
 187     node->target.type = OLSRV2_NODE_TARGET;
 188     olsrv2_routing_dijkstra_node_init(&node->target._dijkstra,
 189         &node->target.prefix.dst);
 190
 191     /* hook into global tree */
 192     avl_insert(&_tc_tree, &node->_originator_node);
 193
 194     /* fire event */
 195     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
 196   }
 197   else if (!oonf_timer_is_active(&node->_validity_time)) {
 198     /* node was virtual */
 199     node->ansn = ansn;
 200
 201     /* fire event */
 202     oonf_class_event(&_tc_node_class, node, OONF_OBJECT_ADDED);
 203   }
 204   oonf_timer_set(&node->_validity_time, vtime);
 205   return node;
 206 }
 207
 208 /**
 209  * Remove a tc node from the database
 210  * @param node pointer to node
 211  */
 212 void
 213 olsrv2_tc_node_remove(struct olsrv2_tc_node *node) {
 214   struct olsrv2_tc_edge *edge, *edge_it;
 215   struct olsrv2_tc_attachment *net, *net_it;
 216
 217   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_REMOVED);
 218
 219   /* remove tc_edges */
 220   avl_for_each_element_safe(&node->_edges, edge, _node, edge_it) {
 221     /* some edges might just become virtual */
 222     olsrv2_tc_edge_remove(edge);
 223   }
 224
 225   /* remove attached networks */
 226   avl_for_each_element_safe(
 227       &node->_attached_networks, net, _src_node, net_it) {
 228     olsrv2_tc_endpoint_remove(net);
 229   }
 230
 231   /* stop validity timer */
 232   oonf_timer_stop(&node->_validity_time);
 233
 234   /* remove from global tree and free memory if node is not needed anymore*/
 235   if (node->_edges.count == 0 && !node->direct_neighbor) {
 236     avl_remove(&_tc_tree, &node->_originator_node);
 237     oonf_class_free(&_tc_node_class, node);
 238   }
 239
 240   /* all domains might have changed */
 241   olsrv2_routing_domain_changed(NULL, true);
 242 }
 243
 244 /**
 245  * Add a tc edge to the database
 246  * @param src pointer to source node
 247  * @param addr pointer to destination address
 248  * @return pointer to TC edge, NULL if out of memory
 249  */
 250 struct olsrv2_tc_edge *
 251 olsrv2_tc_edge_add(struct olsrv2_tc_node *src, struct netaddr *addr) {
 252   struct olsrv2_tc_edge *edge = NULL, *inverse = NULL;
 253   struct olsrv2_tc_node *dst = NULL;
 254   int i;
 255
 256   edge = avl_find_element(&src->_edges, addr, edge, _node);
 257   if (edge != NULL) {
 258     edge->virtual = false;
 259
 260     /* cleanup metric data from other side of the edge */
 261     for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
 262       edge->cost[i] = RFC7181_METRIC_INFINITE;
 263     }
 264
 265     /* fire event */
 266     oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
 267     return edge;
 268   }
 269
 270   /* allocate edge */
 271   edge = oonf_class_malloc(&_tc_edge_class);
 272   if (edge == NULL) {
 273     return NULL;
 274   }
 275
 276   /* allocate inverse edge */
 277   inverse = oonf_class_malloc(&_tc_edge_class);
 278   if (inverse == NULL) {
 279     oonf_class_free(&_tc_edge_class, edge);
 280     return NULL;
 281   }
 282
 283   /* find or allocate destination node */
 284   dst = avl_find_element(&_tc_tree, addr, dst, _originator_node);
 285   if (dst == NULL) {
 286     /* create virtual node */
 287     dst = olsrv2_tc_node_add(addr, 0, 0);
 288     if (dst == NULL) {
 289       oonf_class_free(&_tc_edge_class, edge);
 290       oonf_class_free(&_tc_edge_class, inverse);
 291       return NULL;
 292     }
 293   }
 294
 295   /* initialize edge */
 296   edge->src = src;
 297   edge->dst = dst;
 298   edge->inverse = inverse;
 299   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
 300     edge->cost[i] = RFC7181_METRIC_INFINITE;
 301   }
 302
 303   /* hook edge into src node */
 304   edge->_node.key = &dst->target.prefix.dst;
 305   avl_insert(&src->_edges, &edge->_node);
 306
 307   /* initialize inverse (virtual) edge */
 308   inverse->src = dst;
 309   inverse->dst = src;
 310   inverse->inverse = edge;
 311   inverse->virtual = true;
 312   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
 313     inverse->cost[i] = RFC7181_METRIC_INFINITE;
 314   }
 315
 316   /* hook inverse edge into dst node */
 317   inverse->_node.key = &src->target.prefix.dst;
 318   avl_insert(&dst->_edges, &inverse->_node);
 319
 320   /* fire event */
 321   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_ADDED);
 322   return edge;
 323 }
 324
 325 /**
 326  * Remove a tc edge from the database
 327  * @param edge pointer to tc edge
 328  * @return true if destination of edge was removed too
 329  */
 330 bool
 331 olsrv2_tc_edge_remove(struct olsrv2_tc_edge *edge) {
 332   /* all domains might have changed */
 333   olsrv2_routing_domain_changed(NULL, true);
 334
 335   return _remove_edge(edge, true);
 336 }
 337
 338 /**
 339  * Add an endpoint to a tc node
 340  * @param node pointer to tc node
 341  * @param prefix address prefix of endpoint
 342  * @param mesh true if an interface of a mesh node, #
 343  *   false if a local attached network.
 344  * @return pointer to tc attachment, NULL if out of memory
 345  */
 346 struct olsrv2_tc_attachment *
 347 olsrv2_tc_endpoint_add(struct olsrv2_tc_node *node,
 348     struct os_route_key *prefix, bool mesh) {
 349   struct olsrv2_tc_attachment *net;
 350   struct olsrv2_tc_endpoint *end;
 351   int i;
 352
 353   net = avl_find_element(&node->_attached_networks, prefix, net, _src_node);
 354   if (net != NULL) {
 355     return net;
 356   }
 357
 358   net = oonf_class_malloc(&_tc_attached_class);
 359   if (net == NULL) {
 360     return NULL;
 361   }
 362
 363   end = avl_find_element(&_tc_endpoint_tree, prefix, end, _node);
 364   if (end == NULL) {
 365     /* create new endpoint */
 366     end = oonf_class_malloc(&_tc_endpoint_class);
 367     if (end == NULL) {
 368       oonf_class_free(&_tc_attached_class, net);
 369       return NULL;
 370     }
 371
 372     /* initialize endpoint */
 373     end->target.type = mesh ? OLSRV2_ADDRESS_TARGET : OLSRV2_NETWORK_TARGET;
 374     avl_init(&end->_attached_networks, os_routing_avl_cmp_route_key, false);
 375
 376     /* attach to global tree */
 377     memcpy(&end->target.prefix, prefix, sizeof(*prefix));
 378     end->_node.key = &end->target.prefix;
 379     avl_insert(&_tc_endpoint_tree, &end->_node);
 380
 381     oonf_class_event(&_tc_endpoint_class, end, OONF_OBJECT_ADDED);
 382   }
 383
 384   /* initialize attached network */
 385   net->src = node;
 386   net->dst = end;
 387   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
 388     net->cost[i] = RFC7181_METRIC_INFINITE;
 389   }
 390
 391   /* hook into src node */
 392   net->_src_node.key = &end->target.prefix;
 393   avl_insert(&node->_attached_networks, &net->_src_node);
 394
 395   /* hook into endpoint */
 396   net->_endpoint_node.key = &node->target.prefix;
 397   avl_insert(&end->_attached_networks, &net->_endpoint_node);
 398
 399   /* initialize dijkstra data */
 400   olsrv2_routing_dijkstra_node_init(&end->target._dijkstra,
 401       &node->target.prefix.dst);
 402
 403   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_ADDED);
 404   return net;
 405 }
 406
 407 /**
 408  * Remove a tc attachment from the database
 409  * @param net pointer to tc attachment
 410  */
 411 void
 412 olsrv2_tc_endpoint_remove(
 413     struct olsrv2_tc_attachment *net) {
 414   oonf_class_event(&_tc_attached_class, net, OONF_OBJECT_REMOVED);
 415
 416   /* remove from node */
 417   avl_remove(&net->src->_attached_networks, &net->_src_node);
 418
 419   /* remove from endpoint */
 420   avl_remove(&net->dst->_attached_networks, &net->_endpoint_node);
 421
 422   if (net->dst->_attached_networks.count == 0) {
 423     oonf_class_event(&_tc_endpoint_class, net->dst, OONF_OBJECT_REMOVED);
 424
 425     /* remove endpoint */
 426     avl_remove(&_tc_endpoint_tree, &net->dst->_node);
 427     oonf_class_free(&_tc_endpoint_class, net->dst);
 428   }
 429
 430   /* free attached network */
 431   oonf_class_free(&_tc_attached_class, net);
 432
 433   /* all domains might have changed */
 434   olsrv2_routing_domain_changed(NULL, true);
 435 }
 436
 437 /**
 438  * Inform everyone that a tc node changed
 439  * @param node tc node
 440  */
 441 void
 442 olsrv2_tc_trigger_change(struct olsrv2_tc_node *node) {
 443   oonf_class_event(&_tc_node_class, node, OONF_OBJECT_CHANGED);
 444 }
 445
 446 /**
 447  * Get tree of olsrv2 tc nodes
 448  * @return node tree
 449  */
 450 struct avl_tree *
 451 olsrv2_tc_get_tree(void) {
 452   return &_tc_tree;
 453 }
 454
 455 /**
 456  * Get tree of olsrv2 tc endpoints
 457  * @return endpoint tree
 458  */
 459 struct avl_tree *
 460 olsrv2_tc_get_endpoint_tree(void) {
 461   return &_tc_endpoint_tree;
 462 }
 463
 464
 465 /**
 466  * Callback triggered when a tc node times out
 467  * @param ptr timer instance that fired
 468  */
 469 static void
 470 _cb_tc_node_timeout(struct oonf_timer_instance *ptr) {
 471   struct olsrv2_tc_node *node;
 472
 473   node = container_of(ptr, struct olsrv2_tc_node, _validity_time);
 474
 475   olsrv2_tc_node_remove(node);
 476   olsrv2_routing_trigger_update();
 477 }
 478
 479 /**
 480  * Remove a tc edge from the database
 481  * @param edge pointer to tc edge
 482  * @param cleanup true to remove the destination of the edge too
 483  *   if its not needed anymore
 484  * @return true if destination was removed, false otherwise
 485  */
 486 static bool
 487 _remove_edge(struct olsrv2_tc_edge *edge, bool cleanup) {
 488   bool removed_node = false;
 489
 490   if (edge->virtual) {
 491     /* nothing to do */
 492     return false;
 493   }
 494
 495   /* fire event */
 496   oonf_class_event(&_tc_edge_class, edge, OONF_OBJECT_REMOVED);
 497
 498   if (!edge->inverse->virtual) {
 499     /* make this edge virtual */
 500     edge->virtual = true;
 501
 502     return false;
 503   }
 504
 505   /* unhook edge from both sides */
 506   avl_remove(&edge->src->_edges, &edge->_node);
 507   avl_remove(&edge->dst->_edges, &edge->inverse->_node);
 508
 509   if (edge->dst->_edges.count == 0 && cleanup
 510       && olsrv2_tc_is_node_virtual(edge->dst)) {
 511     /*
 512      * node is already virtual and has no
 513      * incoming links anymore.
 514      */
 515
 516     olsrv2_tc_node_remove(edge->dst);
 517     removed_node = true;
 518   }
 519
 520   oonf_class_free(&_tc_edge_class, edge->inverse);
 521   oonf_class_free(&_tc_edge_class, edge);
 522
 523   return removed_node;
 524 }
 525
 526 static void
 527 _cb_neighbor_change(void *ptr) {
 528   struct nhdp_neighbor *neigh;
 529   struct olsrv2_tc_node *tc_node;
 530
 531   neigh = ptr;
 532   if (memcmp(&neigh->originator, &neigh->_old_originator,
 533       sizeof(neigh->originator)) == 0) {
 534     /* no change */
 535     return;
 536   }
 537
 538   /* remove old tc_node if necessary */
 539   _cb_neighbor_remove(ptr);
 540
 541   /* see if we have a new originator */
 542   if (netaddr_is_unspec(&neigh->originator)) {
 543     return;
 544   }
 545
 546   /* add tc_node if necessary */
 547   tc_node = olsrv2_tc_node_get(&neigh->originator);
 548   if (!tc_node) {
 549     tc_node = olsrv2_tc_node_add(&neigh->originator, 0, 0);
 550     if (!tc_node) {
 551       return;
 552     }
 553   }
 554
 555   /* mark as direct neighbor */
 556   tc_node->direct_neighbor = true;
 557 }
 558
 559 static void
 560 _cb_neighbor_remove(void *ptr) {
 561   struct nhdp_neighbor *neigh;
 562   struct olsrv2_tc_node *tc_node;
 563
 564   neigh = ptr;
 565
 566   if (netaddr_is_unspec(&neigh->originator)) {
 567     return;
 568   }
 569
 570   tc_node = olsrv2_tc_node_get(&neigh->originator);
 571   if (!tc_node) {
 572     return;
 573   }
 574
 575   tc_node->direct_neighbor = false;
 576
 577   if (!oonf_timer_is_active(&tc_node->_validity_time)) {
 578     /* virtual node, kill it */
 579     olsrv2_tc_node_remove(tc_node);
 580   }
 581 }